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

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

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

问题背景

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 论文标题: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) 来表示。

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

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

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

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

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

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

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

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

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

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

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

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

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

通过这种方式,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 次线性搜索。

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

实验二:

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

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

实验三:

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

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

实验四:

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

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

关于通用机器学习

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

  • [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.(基础模块开发、优化器开发)

相关资讯

百分点认知智能实验室:基于不完全标注样本集的信息抽取实践

编者按信息抽取是从文本数据中抽取特定信息的一种技术,命名实体识别(Named Entity Recognition, NER)是信息抽取的基础任务之一,其目标是抽取文本中具有基本语义的实体单元,在知识图谱构建、信息抽取、信息检索、机器翻译、智能问答等系统中都有广泛应用。基于监督学习的NER系统通常需要大规模的细粒度、高精度标注数据集,一旦数据标注质量下降,模型的表现也会急剧下降。利用不完全标注的数据进行NER系统的建立,越来越受到专家学者们的关注。第九届国际自然语言处理与中文计算会议(NLPCC 2020)针对此业

关键点检测项目代码开源了!

作者:闫永强,算法工程师,Datawhale成员 本文通过自建手势数据集,利用YOLOv5s检测,然后通过开源数据集训练squeezenet进行手部关键点预测,最后通过指间的夹角算法来判断具体的手势,并显示出来。文章第四部分为用C 实现整体的ncnn推理(代码较长,可先马后看)一、YOLOV5训练手部检测训练及部署思路类似表情识别,需要将handpose数据集标签改成一类,只检测手部,简化流程,更易上手。此部分数据集来源格物钛  ,具体的效果如图:本教程所用训练环境:系统环境:Ubuntu16.04cuda版本:

5 个章节、25 条规范,全方位 Get 数据集选择与创建的「百科全书」

内容一览:如果你正在学习如何创建或选择一个合适的数据集,那么这篇文章会给你一些实用的建议,帮助你在选择和创建数据集时做出明智的决策。 关键词:机器学习 数据集