“统计大讲堂”第146讲回顾—“数据科学专题”3：大维数据谱聚类算法的性能与复杂度权衡
2021-03-25
3月24日下午，“统计大讲堂”系列讲座第146讲举行。本次讲座采取在线会议及直播的方式，邀请加州大学伯克利分校博士后廖振宇作题为“大维数据谱聚类算法的性能与复杂度权衡”的报告。讲座由师资博士后王睿老师主持，统计学院王星、许王莉等教师与众多学生参与本次讲座。
王睿首先介绍了报告人的相关信息。廖振宇是加州大学伯克利分校的博士后，合作导师是Michael Mahoney，即将入职华中科技大学任副教授。廖振宇的研究兴趣包括机器学习、信号处理、随机矩阵理论和高维统计。廖振宇于2019年获得巴黎萨克雷大学的ED STIC Ph.D. Student Award，于2016年获得 Supélec Foundation Ph.D. Fellowship；在IEEE Transactions on Signal Processing，The Annals of Applied Probability等学术期刊与ICLR, NeurIPS, ICML等学术会议上发表学术论文10余篇；担任加拿大自然科学和工程研究理事会外部评审专家以及JMLR, IEEE TPAMI, IEEE TSP, NeurIPS, ICML, ICLR, AAAI等期刊和会议的审稿人。
廖振宇首先介绍了研究的背景、问题和目标。在大数据时代，数据的数目和维度都非常大，带来了计算层面的挑战。一般解决思路是把机器学习的模型或算法进行某种程度的压缩。此时，关于算法性能与计算、储存复杂度的平衡关系的问题自然产生。那么一个重要的课题是：如何从理论上来刻画并理解算法性能和复杂度的平衡问题，如何给出最优设计，以及这个设计应该如何依赖于数据。在本项工作中，廖振宇针对基于核方法的无监督谱聚类算法研究了以上问题。
廖振宇首先回顾了基于核方法的谱聚类。基于核方法的谱聚类分两个步骤：首先构建核矩阵并提取特征值和特征向量，然后通过特征向量实现高维数据的低维表示，并针对低维表示用EM或k-means方法进行聚类。他还分两部分详细介绍了研究结果：在第一部分，考虑了对格莱姆矩阵做均匀稀疏化，给出了相应的极限谱测度和特征向量的收敛性与相变现象；在第二部分，进一步考虑了对格莱姆矩阵进行非线性的稀疏化、量化、二值化等非均匀处理，同样给出了极限谱测度和特征向量的收敛性与相变现象。
最后，廖振宇总结：本次报告尝试理解机器学习算法的性能和计算复杂度之间均衡的关系，详细研究了经过压缩的谱聚类算法的性能。他们的理论工作表明，非均匀的压缩方式比均匀的稀疏化处理方式具有更好的算法性能，并且其效果可以量化比较。此外，要特别注意在做非均匀的压缩时，有可能得到完全不带任何统计信息的特征向量，因此存在完全摧毁算法的风险。
在提问交流环节，廖振宇耐心解答了同学们的提问，进一步解释了在计算过程等方面的问题。
本次讲座介绍了大维数据谱聚类算法的性能与复杂度权衡，并就其中的方法思路和实际应用作了进一步阐释。此后“统计大讲堂”系列将陆续推出更多精彩讲座，敬请关注。
