AAAI 2025 | 用于韋伯區(qū)位問題的去奇異性次梯度方法

本文提出一種解決奇異性問題的直觀方法。

原標(biāo)題：AAAI 2025 | 用于韋伯區(qū)位問題的去奇異性次梯度方法
文章來源：機器之心
內(nèi)容字?jǐn)?shù)：7070字

暨南大學(xué)通用機器學(xué)習(xí)課題組在韋伯區(qū)位問題研究取得突破

本文報道了暨南大學(xué)通用機器學(xué)習(xí)課題組在解決韋伯區(qū)位問題奇異性問題上的最新研究成果。該課題組由網(wǎng)絡(luò)空間安全學(xué)院和信息科學(xué)技術(shù)學(xué)院的多名師生組成，研究方向涵蓋通用逼近理論、分布外泛化、非凸優(yōu)化等多個領(lǐng)域。2024年4月至12月，課題組已在ICML、NeurIPS、IJCAI、AAAI等頂級會議上發(fā)表5篇論文。

1. 韋伯區(qū)位問題及奇異性挑戰(zhàn)

韋伯區(qū)位問題旨在尋找一個中心點，使其到多個給定點的加權(quán)距離之和最小。該問題廣泛應(yīng)用于機器學(xué)習(xí)、人工智能等領(lǐng)域。其目標(biāo)函數(shù)包含兩個參數(shù)：距離范數(shù)的p值和距離冪次q值。當(dāng)1≤q≤p且1≤p<2時，目標(biāo)函數(shù)存在奇異性問題，即梯度在某些點不存在，算法可能陷入奇異集而無法收斂。此前的研究主要針對p=2的情況，而1≤p<2的情況更為復(fù)雜，奇異集包含無限多個點。

2. 去奇異性次梯度法

為了解決這一問題，課題組提出了一種名為“去奇異性次梯度法”的全新方法。該方法通過識別引發(fā)奇異性的數(shù)據(jù)點和維度，去除相應(yīng)的分量，從而構(gòu)造出一種新的次梯度。該次梯度具有良好的性質(zhì)，例如能夠刻畫最小值點和下降方向。基于此，課題組構(gòu)建了一種名為qPpNWAWS的算法，該算法在非奇異情況下使用常規(guī)Weiszfeld迭代，在奇異情況下使用沿下降方向的線性搜索法，保證損失函數(shù)持續(xù)下降并最終收斂。

3. 算法性能及實驗結(jié)果

課題組在CSI300數(shù)據(jù)集上進行了實驗驗證。實驗結(jié)果表明，qPpNWAWS算法在奇異點通常只需不超過3次線性搜索即可使損失函數(shù)下降，總迭代次數(shù)和時間分別不超過15次和0.02秒，并達到線性收斂速度。此外，在在線資產(chǎn)配置實驗中，該算法在某些(q,p)組合下取得了比原始版本(q,p)=(1,2)更高的投資得分。

4. 通用機器學(xué)習(xí)研究方向

該研究屬于通用機器學(xué)習(xí)領(lǐng)域的基礎(chǔ)模塊開發(fā)和優(yōu)化器開發(fā)方向。課題組近期還在深度學(xué)習(xí)框架、分布外泛化、逼近理論、稀疏學(xué)習(xí)等方向取得了其他重要成果，例如在ICML和NeurIPS發(fā)表的關(guān)于不變風(fēng)險最小化和稀疏投資組合優(yōu)化的論文。

5. 結(jié)論

暨南大學(xué)通用機器學(xué)習(xí)課題組提出的去奇異性次梯度法有效解決了韋伯區(qū)位問題在1≤q≤p且1≤p<2情況下的奇異性問題，為該問題的求解提供了新的思路，并具有重要的實際應(yīng)用價值。該研究成果已發(fā)表在arXiv上，論文鏈接為：http://arxiv.org/abs/2412.15546，項目地址為：https://github.com/laizhr/qPpNWAWS。

聯(lián)系作者

文章來源：機器之心
作者微信：
作者簡介：專業(yè)的人工智能媒體和產(chǎn)業(yè)服務(wù)平臺