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

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

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

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

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

1. 韋伯區位問題及奇異性挑戰

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

2. 去奇異性次梯度法

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

3. 算法性能及實驗結果

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

4. 通用機器學習研究方向

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

5. 結論

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