AIxiv專(zhuān)欄是機(jī)器之心發(fā)布學(xué)術(shù)、技術(shù)內(nèi)容的欄目。過(guò)去數(shù)年，機(jī)器之心AIxiv專(zhuān)欄接收?qǐng)?bào)道了2000多篇內(nèi)容，覆蓋全球各大高校與企業(yè)的頂級(jí)實(shí)驗(yàn)室，有效促進(jìn)了學(xué)術(shù)交流與傳播。如果您有優(yōu)秀的工作想要分享，歡迎投稿或者聯(lián)系報(bào)道。投稿郵箱：liyazhou@jiqizhixin.com；zhaoyunfeng@jiqizhixin.com
暨南大學(xué)通用機(jī)器學(xué)習(xí)課題組由網(wǎng)絡(luò)空間安全學(xué)院和信息科學(xué)技術(shù)學(xué)院的多名青年教師、博士生、碩士生和本科生共同組成，研究方向包括通用逼近理論、分布外泛化、非凸優(yōu)化、稀疏學(xué)習(xí)、深度學(xué)習(xí)框架的基礎(chǔ)模塊開(kāi)發(fā)、優(yōu)化器開(kāi)發(fā)、隱私保護(hù)與增強(qiáng)等。自 2024 年 4 月至 12 月，課題組作為第一單位已獲得所有 CCF A 機(jī)器學(xué)習(xí)國(guó)際頂級(jí)會(huì)議 ICML（2 篇）、NeurIPS 和人工智能?chē)?guó)際頂級(jí)會(huì)議 IJCAI、AAAI 錄用論文共 5 篇。本文第一作者為課題組負(fù)責(zé)人賴(lài)兆榮，通訊作者為博士生李程，其他合作作者為課題組教師吳小天、方良達(dá)、陳子良。問(wèn)題背景韋伯區(qū)位問(wèn)題源自一個(gè)經(jīng)典的運(yùn)籌優(yōu)化問(wèn)題，它首先由著名數(shù)學(xué)家皮耶·德·費(fèi)馬提出，后被著名經(jīng)濟(jì)學(xué)家阿爾弗雷德·韋伯（著名社會(huì)學(xué)家馬克斯·韋伯的弟弟）擴(kuò)展，在機(jī)器學(xué)習(xí)、人工智能、金融工程及計(jì)算機(jī)視覺(jué)等眾多領(lǐng)域均有廣泛應(yīng)用。在一般定義下，該問(wèn)題的目標(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ū)位問(wèn)題的表達(dá)力和對(duì)更廣泛任務(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 的情形相對(duì)比較簡(jiǎn)單，每個(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)過(guò)每個(gè)奇異點(diǎn)一次并脫離奇異集。但對(duì)于 1<=p<2 的情形，奇異集是一個(gè)包含無(wú)限個(gè)點(diǎn)的連續(xù)點(diǎn)集合（如下圖右的紅色虛線及紅點(diǎn)所示），所以算法可能重新訪問(wèn)奇異集無(wú)限次并最終不會(huì)逃離奇異集。
該奇異性問(wèn)題經(jīng)常且意外地發(fā)生。造成奇異性的初始或中間迭代點(diǎn)可在 d>=2 維實(shí)空間中的一個(gè)開(kāi)集中稠密，甚至充滿整個(gè) d 維實(shí)空間 [4]。更為嚴(yán)重的是，該問(wèn)題無(wú)法依靠簡(jiǎn)單直觀的手段來(lái)回避，例如隨機(jī)擾動(dòng)迭代點(diǎn)使其離開(kāi)奇異集，或者重選一個(gè)隨機(jī)初始點(diǎn)，等等。事實(shí)上，只要采用本文提出的去奇異性次梯度方法，即可在不增加計(jì)算復(fù)雜度（與一般梯度法相比）的有利條件下解決該奇異性問(wèn)題，因此完全不需要再借助其他回避手段。
論文標(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
去奇異性次梯度法本文提出一種解決奇異性問(wèn)題的直觀方法：識(shí)別出引發(fā)奇異性的數(shù)據(jù)點(diǎn)及維度，然后把相應(yīng)的分量去除掉。首先是識(shí)別出引發(fā)奇異性的數(shù)據(jù)點(diǎn)及維度，分別用集合 V_t (y) 和 U_i (y) 來(lái)表示。
下圖是 V_t (y) 和 U_i (y) 的一個(gè)直觀示意圖。
然后使用定義 5 來(lái)定義去奇異性次梯度 D_{p,q}(y)。
接著，我們需要驗(yàn)證這個(gè)去奇異性次梯度 D_{p,q}(y) 具有與普通梯度類(lèi)似的良好性質(zhì)。例如，它要能夠刻畫(huà)最小值點(diǎn)（定理 6）和下降方向（定理 7）。這些刻畫(huà)的關(guān)鍵技術(shù)在于引入 p 范數(shù)的共軛范數(shù)，即使得 1/r+1/p =1 成立的 r 范數(shù)。
基于 q 次方 p 范數(shù)的去奇異性 Weiszfeld 算法獲得可行的去奇異性次梯度 D_{p,q}(y) 后，下一步就是建立可行的求解算法。本文基于求解該問(wèn)題常用的 Weiszfeld 算法 [5][2]，建立一種基于 q 次方 p 范數(shù)的去奇異性 Weiszfeld 算法（簡(jiǎn)記為 qPpNWAWS，如 18 式所示）。它在非奇異性情形下使用 (9) 式的常規(guī) Weiszfeld 更新迭代，在奇異性情形下使用 (17) 式的沿下降方向線性搜索法。
通過(guò)這種方式，qPpNWAWS 算法可自由來(lái)回多次（甚至包括無(wú)限次）游走于非奇異集與奇異集之間或之內(nèi)，同時(shí)保證損失函數(shù)隨迭代下降，并最終收斂。在 1<p<2 這一嚴(yán)格凸情形下，qPpNWAWS 算法甚至能進(jìn)一步獲得更強(qiáng)的收斂性質(zhì)，如迭代序列收斂到全局最小值點(diǎn)，等等。具體算法流程較為繁瑣復(fù)雜，請(qǐng)參閱論文附錄 A。算法的收斂性定理、其他性質(zhì)定理以及詳細(xì)證明也請(qǐng)參閱論文。實(shí)驗(yàn)結(jié)果我們以 CSI300 數(shù)據(jù)集 [3] 為例簡(jiǎn)單介紹實(shí)驗(yàn)結(jié)果，其他數(shù)據(jù)集以及詳細(xì)實(shí)驗(yàn)結(jié)果請(qǐng)參閱論文。運(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ù)情形下只需不超過(guò) 3 次線性搜索。
實(shí)驗(yàn)二：該實(shí)驗(yàn)用于記錄 qPpNWAWS 算法完整運(yùn)行一次所需的總迭代次數(shù)以及總時(shí)間。結(jié)果表明在絕大多數(shù)情形下只需不超過(guò)約 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)主要測(cè)試不同 (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 情形下的奇異性問(wèn)題有著非常重要的現(xiàn)實(shí)意義。
關(guān)于通用機(jī)器學(xué)習(xí)通用機(jī)器學(xué)習(xí)是一個(gè)由多個(gè)研究方向有機(jī)結(jié)合而成的整體領(lǐng)域。其往往需要融會(huì)貫通多個(gè)數(shù)學(xué)類(lèi)和計(jì)算機(jī)類(lèi)學(xué)科的知識(shí)，攻關(guān)通用人工智能中最為基礎(chǔ)的科學(xué)與技術(shù)難題。本文屬于該領(lǐng)域中的基礎(chǔ)模塊開(kāi)發(fā)與優(yōu)化器開(kāi)發(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)化器開(kāi)發(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ǔ)模塊開(kāi)發(fā)、優(yōu)化器開(kāi)發(fā)）
參考文獻(xiàn)：[1]. Weber, A. 1909. Uber den Standort der Industrien. Tubingen: Mohr.[2]. Morris, J. G. 1981. Convergence of the Weiszfeld algorithm for Weber problems using a generalized “distance” function. Operations Research, 29(1): 3748.[3]. Lai, Z.-R.; Wu, X.; Fang, L.; and Chen, Z. 2024. A De-singularity Subgradient Approach for the Extended Weber Location Problem. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence.[4]. Chandrasekaran, R.; and Tamir, A. 1989. Open questions concerning Weiszfeld’s algorithm for the Fermat-Weber location problem. Mathematical Programming, 44: 293295.[5]. Weiszfeld, E.. Sur le point pour lequel la somme des distances de n points donnes est minimum. Tohoku Mathematical Journal, 43:355386, 1937.[6]. Li, B.; Sahoo, D.; and Hoi, S. C. 2016. OLPS: a toolbox for on-line portfolio selection. Journal of Machine Learning Research, 17(1): 12421246.[7]. Huang, D.; Zhou, J.; Li, B.; Hoi, S. C. H.; and Zhou, S. 2016. Robust Median Reversion Strategy for Online Portfolio Selection. IEEE Transactions on Knowledge and Data Engineering, 28(9): 24802493.
