暨南大學(xué)通用機(jī)器學(xué)習(xí)課題組由網(wǎng)絡(luò)空間安全學(xué)院和信息科學(xué)技術(shù)學(xué)院的多名青年教師、博士生、碩士生和本科生共同組成，研究方向包括通用逼近理論、分布外泛化、非凸優(yōu)化、稀疏學(xué)習(xí)、深度學(xué)習(xí)框架的基礎(chǔ)模塊開發(fā)、優(yōu)化器開發(fā)、隱私保護(hù)與增強(qiáng)等。自 2024 年 4 月至 12 月，課題組作為第一單位已獲得所有 CCF A 機(jī)器學(xué)習(xí)國際頂級會議 ICML（2 篇）、NeurIPS 和人工智能國際頂級會議 IJCAI、AAAI 錄用論文共 5 篇。本文第一作者為課題組負(fù)責(zé)人賴兆榮，通訊作者為博士生李程，其他合作作者為課題組教師吳小天、方良達(dá)、陳子良。

問題背景

韋伯區(qū)位問題源自一個(gè)經(jīng)典的運(yùn)籌優(yōu)化問題，它首先由著名數(shù)學(xué)家皮耶?德?費(fèi)馬提出，后被著名經(jīng)濟(jì)學(xué)家阿爾弗雷德?韋伯（著名社會學(xué)家馬克斯?韋伯的弟弟）擴(kuò)展，在機(jī)器學(xué)習(xí)、人工智能、金融工程及計(jì)算機(jī)視覺等眾多領(lǐng)域均有廣泛應(yīng)用。在一般定義下，該問題的目標(biāo)在于找到一個(gè)「中心點(diǎn)」x_*，使得這個(gè)中心點(diǎn)到 m 個(gè)給定數(shù)據(jù)點(diǎn) x_i 的加權(quán)距離之和最小 [1][2]：

這里有兩個(gè)重要參數(shù)：用作距離的 l_p 范數(shù)中的 p 值，以及距離的冪次 q。一般考慮 p>=1 且 1<=q<=p。p=2 表示常用的歐氏距離；p=1 表示曼哈頓距離，代表一種重要的非歐幾何。允許這兩個(gè)變化參數(shù)有助于增強(qiáng)韋伯區(qū)位問題的表達(dá)力和對更廣泛任務(wù)的適應(yīng)性。

為直入主題，計(jì)算 (1) 式中損失函數(shù)的梯度如下：

其中上標(biāo) t 表示第 t 維，并假設(shè)數(shù)據(jù)點(diǎn) x_i 屬于 d 維實(shí)空間（1<=t<=d）。容易看出，當(dāng) q<p 或 p<2 時(shí)，若 y 剛好擊中如下奇異集，則梯度不存在：

其中 1<=q<p,p=2 的情形相對比較簡單，每個(gè)數(shù)據(jù)點(diǎn)即為奇異點(diǎn)，所以總共只有有限個(gè)奇異點(diǎn)，如下圖所示。該情形已由本課題組的 IJCAI 2024 論文解決 [3]。

而 1<=q<=p,1<=p<2 的情形就要復(fù)雜很多了。由于 p=2 的情形只有有限個(gè)奇異點(diǎn)（如下圖左的紅點(diǎn)所示），所以只要成功設(shè)計(jì)出一個(gè)能保持損失函數(shù)下降性質(zhì)的算法，則可以保證最多只經(jīng)過每個(gè)奇異點(diǎn)一次并脫離奇異集。但對于 1<=p<2 的情形，奇異集是一個(gè)包含無限個(gè)點(diǎn)的連續(xù)點(diǎn)集合（如下圖右的紅色虛線及紅點(diǎn)所示），所以算法可能重新訪問奇異集無限次并最終不會逃離奇異集。

該奇異性問題經(jīng)常且意外地發(fā)生。造成奇異性的初始或中間迭代點(diǎn)可在 d>=2 維實(shí)空間中的一個(gè)開集中稠密，甚至充滿整個(gè) d 維實(shí)空間 [4]。更為嚴(yán)重的是，該問題無法依靠簡單直觀的手段來回避，例如隨機(jī)擾動(dòng)迭代點(diǎn)使其離開奇異集，或者重選一個(gè)隨機(jī)初始點(diǎn)，等等。事實(shí)上，只要采用本文提出的去奇異性次梯度方法，即可在不增加計(jì)算復(fù)雜度（與一般梯度法相比）的有利條件下解決該奇異性問題，因此完全不需要再借助其他回避手段。

• 論文標(biāo)題：De-singularity Subgradient for the q-th-Powered L_p-Norm Weber Location Problem
• 論文鏈接：http://arxiv.org/abs/2412.15546
• 項(xiàng)目地址：https://github.com/laizhr/qPpNWAWS

去奇異性次梯度法

本文提出一種解決奇異性問題的直觀方法：識別出引發(fā)奇異性的數(shù)據(jù)點(diǎn)及維度，然后把相應(yīng)的分量去除掉。首先是識別出引發(fā)奇異性的數(shù)據(jù)點(diǎn)及維度，分別用集合 V_t (y) 和 U_i (y) 來表示。

下圖是 V_t (y) 和 U_i (y) 的一個(gè)直觀示意圖。

然后使用定義 5 來定義去奇異性次梯度 D_{p,q}(y)。

接著，我們需要驗(yàn)證這個(gè)去奇異性次梯度 D_{p,q}(y) 具有與普通梯度類似的良好性質(zhì)。例如，它要能夠刻畫最小值點(diǎn)（定理 6）和下降方向（定理 7）。這些刻畫的關(guān)鍵技術(shù)在于引入 p 范數(shù)的共軛范數(shù)，即使得 1/r+1/p =1 成立的 r 范數(shù)。

基于 q 次方 p 范數(shù)的去奇異性 Weiszfeld 算法

獲得可行的去奇異性次梯度 D_{p,q}(y) 后，下一步就是建立可行的求解算法。本文基于求解該問題常用的 Weiszfeld 算法 [5][2]，建立一種基于 q 次方 p 范數(shù)的去奇異性 Weiszfeld 算法（簡記為 qPpNWAWS，如 18 式所示）。它在非奇異性情形下使用 (9) 式的常規(guī) Weiszfeld 更新迭代，在奇異性情形下使用 (17) 式的沿下降方向線性搜索法。

通過這種方式，qPpNWAWS 算法可自由來回多次（甚至包括無限次）游走于非奇異集與奇異集之間或之內(nèi)，同時(shí)保證損失函數(shù)隨迭代下降，并最終收斂。在 1<p<2 這一嚴(yán)格凸情形下，qPpNWAWS 算法甚至能進(jìn)一步獲得更強(qiáng)的收斂性質(zhì)，如迭代序列收斂到全局最小值點(diǎn)，等等。具體算法流程較為繁瑣復(fù)雜，請參閱論文附錄 A。算法的收斂性定理、其他性質(zhì)定理以及詳細(xì)證明也請參閱論文。

實(shí)驗(yàn)結(jié)果

我們以 CSI300 數(shù)據(jù)集 [3] 為例簡單介紹實(shí)驗(yàn)結(jié)果，其他數(shù)據(jù)集以及詳細(xì)實(shí)驗(yàn)結(jié)果請參閱論文。運(yùn)行實(shí)驗(yàn)的機(jī)器配置為：Intel Core i9-14900KF 中央處理器 1 個(gè)，64-GB DDR5 6000-MHz 內(nèi)存，帶 16-GB 獨(dú)立顯存的 Nvidia RTX 4080 SUPER 顯卡 1 張。

實(shí)驗(yàn)一：

該實(shí)驗(yàn)用于記錄 qPpNWAWS 算法在奇異點(diǎn)需要幾次線性搜索才能使損失函數(shù)下降。結(jié)果表明在絕大多數(shù)情形下只需不超過 3 次線性搜索。

實(shí)驗(yàn)二：

該實(shí)驗(yàn)用于記錄 qPpNWAWS 算法完整運(yùn)行一次所需的總迭代次數(shù)以及總時(shí)間。結(jié)果表明在絕大多數(shù)情形下只需不超過約 15 次迭代以及 0.02 秒的總時(shí)間。

實(shí)驗(yàn)三：

該實(shí)驗(yàn)用于記錄 qPpNWAWS 算法的實(shí)際計(jì)算收斂率。結(jié)果表明在絕大多數(shù)情形下收斂率均遠(yuǎn)小于 1，即達(dá)到線性收斂速度。

實(shí)驗(yàn)四：

該實(shí)驗(yàn)主要測試不同 (q,p) 情形下使用 qPpNWAWS 算法進(jìn)行在線資產(chǎn)配置實(shí)驗(yàn) [6][7] 所得到的投資得分 —— 累計(jì)財(cái)富（CW）和夏普比率（SR）。結(jié)果表明一定數(shù)目的其他 (q,p) 情形（例如 (q,p)=(1,1.6)）的得分要比原始版本 (q,p)=(1,2) 的得分高。因此解決 1<=q<=p,1<=p<2 情形下的奇異性問題有著非常重要的現(xiàn)實(shí)意義。

關(guān)于通用機(jī)器學(xué)習(xí)

通用機(jī)器學(xué)習(xí)是一個(gè)由多個(gè)研究方向有機(jī)結(jié)合而成的整體領(lǐng)域。其往往需要融會貫通多個(gè)數(shù)學(xué)類和計(jì)算機(jī)類學(xué)科的知識，攻關(guān)通用人工智能中最為基礎(chǔ)的科學(xué)與技術(shù)難題。本文屬于該領(lǐng)域中的基礎(chǔ)模塊開發(fā)與優(yōu)化器開發(fā)研究方向。以下是近期本課題組在該領(lǐng)域的一些主要論文與主攻方向，歡迎閱讀并與我們交流討論。

• [a]. Zhao-Rong Lai, Weiwen Wang*, "Invariant Risk Minimization Is A Total Variation Model", the 41st International Conference on Machine Learning (ICML, main track), 2024.（深度學(xué)習(xí)框架、分布外泛化）
• [b]. Yizun Lin, Yangyu Zhang, Zhao-Rong Lai*, Cheng Li,"Autonomous Sparse Mean-CVaR Portfolio Optimization", the 41st International Conference on Machine Learning (ICML, main track), 2024.（逼近理論、稀疏學(xué)習(xí)）
• [c]. Yizun Lin, Zhao-Rong Lai*, Cheng Li,“A Globally Optimal Portfolio for m-Sparse Sharpe Ratio Maximization”, the 38th Annual Conference on Neural Information Processing Systems（NeurIPS, main track), 2024.（優(yōu)化器開發(fā)、稀疏學(xué)習(xí)）
• [d]. Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen*, "A De-singularity Subgradient Approach for the Extended Weber Location Problem", the 33rd International Joint Conference on Artificial Intelligence (IJCAI, main track), 2024.（基礎(chǔ)模塊開發(fā)、優(yōu)化器開發(fā)）