AAAI 2025 | 用于韦伯区位问题的去奇异性次梯度方法

机器之心

2024-12-30 12:29发布于北京机器之心官方账号

AIxiv专栏是机器之心发布学术、技术内容的栏目。过去数年，机器之心AIxiv专栏接收报道了2000多篇内容，覆盖全球各大高校与企业的顶级实验室，有效促进了学术交流与传播。如果您有优秀的工作想要分享，欢迎投稿或者联系报道。投稿邮箱：liyazhou@jiqizhixin.com；zhaoyunfeng@jiqizhixin.com

暨南大学通用机器学习课题组由网络空间安全学院和信息科学技术学院的多名青年教师、博士生、硕士生和本科生共同组成，研究方向包括通用逼近理论、分布外泛化、非凸优化、稀疏学习、深度学习框架的基础模块开发、优化器开发、隐私保护与增强等。自 2024 年 4 月至 12 月，课题组作为第一单位已获得所有 CCF A 机器学习国际顶级会议 ICML（2 篇）、NeurIPS 和人工智能国际顶级会议 IJCAI、AAAI 录用论文共 5 篇。本文第一作者为课题组负责人赖兆荣，通讯作者为博士生李程，其他合作作者为课题组教师吴小天、方良达、陈子良。

问题背景

韦伯区位问题源自一个经典的运筹优化问题，它首先由著名数学家皮耶・德・费马提出，后被著名经济学家阿尔弗雷德・韦伯（著名社会学家马克斯・韦伯的弟弟）扩展，在机器学习、人工智能、金融工程及计算机视觉等众多领域均有广泛应用。在一般定义下，该问题的目标在于找到一个「中心点」x_*，使得这个中心点到 m 个给定数据点 x_i 的加权距离之和最小 [1][2]：

这里有两个重要参数：用作距离的 l_p 范数中的 p 值，以及距离的幂次 q。一般考虑 p>=1 且 1<=q<=p。p=2 表示常用的欧氏距离；p=1 表示曼哈顿距离，代表一种重要的非欧几何。允许这两个变化参数有助于增强韦伯区位问题的表达力和对更广泛任务的适应性。

为直入主题，计算 (1) 式中损失函数的梯度如下：

其中上标 t 表示第 t 维，并假设数据点 x_i 属于 d 维实空间（1<=t<=d）。容易看出，当 q<p 或 p<2 时，若 y 刚好击中如下奇异集，则梯度不存在：

其中 1<=q<p,p=2 的情形相对比较简单，每个数据点即为奇异点，所以总共只有有限个奇异点，如下图所示。该情形已由本课题组的 IJCAI 2024 论文解决 [3]。

而 1<=q<=p,1<=p<2 的情形就要复杂很多了。由于 p=2 的情形只有有限个奇异点（如下图左的红点所示），所以只要成功设计出一个能保持损失函数下降性质的算法，则可以保证最多只经过每个奇异点一次并脱离奇异集。但对于 1<=p<2 的情形，奇异集是一个包含无限个点的连续点集合（如下图右的红色虚线及红点所示），所以算法可能重新访问奇异集无限次并最终不会逃离奇异集。

该奇异性问题经常且意外地发生。造成奇异性的初始或中间迭代点可在 d>=2 维实空间中的一个开集中稠密，甚至充满整个 d 维实空间 [4]。更为严重的是，该问题无法依靠简单直观的手段来回避，例如随机扰动迭代点使其离开奇异集，或者重选一个随机初始点，等等。事实上，只要采用本文提出的去奇异性次梯度方法，即可在不增加计算复杂度（与一般梯度法相比）的有利条件下解决该奇异性问题，因此完全不需要再借助其他回避手段。

论文标题：De-singularity Subgradient for the q-th-Powered L_p-Norm Weber Location Problem
论文链接：http://arxiv.org/abs/2412.15546
项目地址：https://github.com/laizhr/qPpNWAWS

去奇异性次梯度法

本文提出一种解决奇异性问题的直观方法：识别出引发奇异性的数据点及维度，然后把相应的分量去除掉。首先是识别出引发奇异性的数据点及维度，分别用集合 V_t (y) 和 U_i (y) 来表示。

下图是 V_t (y) 和 U_i (y) 的一个直观示意图。

然后使用定义 5 来定义去奇异性次梯度 D_{p,q}(y)。

接着，我们需要验证这个去奇异性次梯度 D_{p,q}(y) 具有与普通梯度类似的良好性质。例如，它要能够刻画最小值点（定理 6）和下降方向（定理 7）。这些刻画的关键技术在于引入 p 范数的共轭范数，即使得 1/r+1/p =1 成立的 r 范数。

基于 q 次方 p 范数的去奇异性 Weiszfeld 算法

获得可行的去奇异性次梯度 D_{p,q}(y) 后，下一步就是建立可行的求解算法。本文基于求解该问题常用的 Weiszfeld 算法 [5][2]，建立一种基于 q 次方 p 范数的去奇异性 Weiszfeld 算法（简记为 qPpNWAWS，如 18 式所示）。它在非奇异性情形下使用 (9) 式的常规 Weiszfeld 更新迭代，在奇异性情形下使用 (17) 式的沿下降方向线性搜索法。

通过这种方式，qPpNWAWS 算法可自由来回多次（甚至包括无限次）游走于非奇异集与奇异集之间或之内，同时保证损失函数随迭代下降，并最终收敛。在 1<p<2 这一严格凸情形下，qPpNWAWS 算法甚至能进一步获得更强的收敛性质，如迭代序列收敛到全局最小值点，等等。具体算法流程较为繁琐复杂，请参阅论文附录 A。算法的收敛性定理、其他性质定理以及详细证明也请参阅论文。

实验结果

我们以 CSI300 数据集 [3] 为例简单介绍实验结果，其他数据集以及详细实验结果请参阅论文。运行实验的机器配置为：Intel Core i9-14900KF 中央处理器 1 个，64-GB DDR5 6000-MHz 内存，带 16-GB 独立显存的 Nvidia RTX 4080 SUPER 显卡 1 张。

实验一：

该实验用于记录 qPpNWAWS 算法在奇异点需要几次线性搜索才能使损失函数下降。结果表明在绝大多数情形下只需不超过 3 次线性搜索。

实验二：

该实验用于记录 qPpNWAWS 算法完整运行一次所需的总迭代次数以及总时间。结果表明在绝大多数情形下只需不超过约 15 次迭代以及 0.02 秒的总时间。

实验三：

该实验用于记录 qPpNWAWS 算法的实际计算收敛率。结果表明在绝大多数情形下收敛率均远小于 1，即达到线性收敛速度。

实验四：

该实验主要测试不同 (q,p) 情形下使用 qPpNWAWS 算法进行在线资产配置实验 [6][7] 所得到的投资得分 —— 累计财富（CW）和夏普比率（SR）。结果表明一定数目的其他 (q,p) 情形（例如 (q,p)=(1,1.6)）的得分要比原始版本 (q,p)=(1,2) 的得分高。因此解决 1<=q<=p,1<=p<2 情形下的奇异性问题有着非常重要的现实意义。

关于通用机器学习

通用机器学习是一个由多个研究方向有机结合而成的整体领域。其往往需要融会贯通多个数学类和计算机类学科的知识，攻关通用人工智能中最为基础的科学与技术难题。本文属于该领域中的基础模块开发与优化器开发研究方向。以下是近期本课题组在该领域的一些主要论文与主攻方向，欢迎阅读并与我们交流讨论。

[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.（深度学习框架、分布外泛化）
[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.（逼近理论、稀疏学习）
[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.（优化器开发、稀疏学习）
[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.（基础模块开发、优化器开发）

参考文献：

[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): 37–48.

[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: 293–295.

[5]. Weiszfeld, E.. Sur le point pour lequel la somme des distances de n points donnes est minimum. Tohoku Mathematical Journal, 43:355–386, 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): 1242–1246.

[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): 2480–2493.

查看原图 13K