科研速递 | 理工学院沈闓明教授团队在机器学习顶会NeurIPS发表工作
近日,香港中文大学(深圳)理工学院的沈闓明教授团队有关数据聚类的工作被NeurIPS 2024接收。NeurIPS是机器学习领域里最负盛名的顶尖学术会议之一,本届NeurIPS将于今年12月份在加拿大温哥华市举行,论文录用率为25.8%。
论文标题:Multidimensional Fractional Programming for Normalized Cuts
作者:Yannan Chen,Beichen Huang,Licheng Zhao,Kaiming Shen
论文链接:https://kaimingshen.github.io/doc/NeurIPS24_FP.pdf
研究介绍
Normalized Cut (NCut)是数据聚类(data clustering)的核心问题。数学上来讲,该问题考虑如何将加权图划分成若干子图,从而使得子图之间的归一化总权重最小,如图1所示。NCut问题的难点包括:(1)子图划分涉及整型优化;(2)即使将整型变量松弛为连续变量,NCut仍为非凸问题而难以求解。
图1 两个子图之间的总权重,还将进行归一化
首先,我们注意到NCut问题具有如下分式结构:
因此自然而然地想起使用分式规划(fractional programming)方法来解决该问题。由于经典Dinkelbach算法只能适用于单分式问题,这里我们使用更前沿的“二次变换(quadratic transform)”方法来处理NCut问题中的多个分式。通过改良后的二次变换,我们能将NCut原问题转化为更容易求解的二分图匹配(bipartite matching)问题,从而实现高效的数据聚类优化。此外,我们还从MM理论角度对该算法的收敛性进行了分析。
事实上,分式规划问题广泛存在于机器学习、信号处理、通信网络、光学、管理学、经济学等众多领域,论文所提算法的应用潜力有待进一步发掘。
实验结果
表1 所提算法FPC在各数据集上与现有方法SC,FINC,FCD的比较,最佳性能加粗表示
图2 所提算法FPC在图像压缩任务中有更好效果
作者简介
陈雁南,香港中文大学(深圳)理工学院的在读博士生,分别于2018年和2021年在厦门大学获得自动化学士学位和模式识别与智能系统硕士学位。主要研究方向为优化,无线通信和机器学习。
黄北辰,麦克马斯特大学的本科生,曾在香港中文大学(深圳)沈闓明教授课题组担任研究实习生。主要研究方向为优化和机器学习。他是本篇论文的共同第一作者。
赵立成博士现任深圳市大数据研究院研究科学家。于2014年获得东南大学信息工程学士学位,并于2018年获得香港科技大学电子与计算机工程系博士学位。曾于京东担任推荐系统的算法工程师。研究兴趣包括优化理论和高效算法,并将其应用于信号处理、机器学习以及推荐系统中的深度学习领域。
沈闓明博士现任香港中文大学(深圳)理工学院助理教授,校长青年学者。他2011年本科毕业于上海交通大学信息安全专业,并同时取得数学专业学士学位,然后分别于2013年和2020年获得加拿大多伦多大学电子与计算机工程专业的硕士和博士学位。研究方向包括数学优化、无线通信、信息论、数据科学。曾获得2018年国家优秀自费留学生奖学金,2021年IEEE信号处理学会最佳青年论文奖,2024年国际基础科学大会前沿科学奖。沈闓明博士是IEEE高级会员,担任IEEE Transactions on Wireless Communications的编辑。他是本篇论文的通讯作者。
供稿 | 沈闓明教授团队