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

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

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

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

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

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

2. 去奇異性次梯度法

為了解決這一問題，課題組提出了一種名為“去奇異性次梯度法”的全新方法。該方法通過識別引發(fā)奇異性的數(shù)據(jù)點和維度，去除相應的分量，從而構(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. 通用機器學習研究方向

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

5. 結(jié)論

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

聯(lián)系作者

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