EAGER: Novel sampling algorithms for scaling up spectral methods for unsupervised learning

EAGER：用于扩大无监督学习光谱方法的新型采样算法

• 批准号: 1650080
• 负责人: Claire Monteleoni
• 金额: $ 9万
• 依托单位: George Washington University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-15 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1650080&HistoricalAwards=false
• 关键词: EAGER; Novel; sampling; algorithms; scaling

In the era of big data, unsupervised learning has become increasingly important. At a high-level, unsupervised learning serves to reduce the data size, while capturing its important underlying structure. For a powerful and widely-used family of unsupervised learning techniques (those based on spectral methods), scaling up to large data sets poses significant computational challenges. This research project will develop extremely simple and lightweight sampling techniques for scaling up this family of unsupervised learning methods. Since big data is ubiquitous, these research advances are likely to be transformative to a range of fields. This project will benefit society through the research team's ongoing collaborations in climate science, agriculture, and finance. The team will also continue to engage the computer science community in this endeavor, by training students, developing tutorials, and broadening the participation of women and minorities in computing.This project will advance machine learning research by scaling up spectral methods for the analysis of large data sets. While spectral methods for the unsupervised learning tasks of clustering and embedding have found wide success in a variety of practical applications, scaling them up to large data sets poses significant computational challenges. In particular, the storage and computation needed to handle the affinity matrix (a matrix of pairwise similarities between data points) can be prohibitive. An approach that has found promise is to instead approximate this matrix in some sense. The goal of this project is to provide simple approximation techniques that manage the tradeoff between their space and time complexity vs. the quality of the approximation. The proposed approach involves sampling techniques that address this goal by exploiting latent structure in a data set, in order to minimize the amount of information that needs to be stored to (approximately) represent it. This leads to techniques that speed up the computation and reduce the memory requirements of spectral methods, while simultaneously providing better approximations. The project will also continue the team's momentum on leveraging advances in machine learning for data-driven discovery.

在大数据时代，无监督学习变得越来越重要。在高层次上，无监督学习有助于减少数据大小，同时捕获其重要的底层结构。对于一个强大且广泛使用的无监督学习技术家族（基于谱方法的技术），扩展到大数据集带来了巨大的计算挑战。该研究项目将开发非常简单和轻量级的采样技术，以扩大这一系列无监督学习方法的规模。由于大数据无处不在，这些研究进展可能会对一系列领域产生变革性影响。该项目将通过研究团队在气候科学，农业和金融方面的持续合作造福社会。该团队还将通过培训学生、开发教程以及扩大妇女和少数民族在计算领域的参与，继续让计算机科学界参与这一奋进。该项目将通过扩大光谱方法用于分析大型数据集来推进机器学习研究。虽然用于聚类和嵌入的无监督学习任务的谱方法在各种实际应用中取得了广泛的成功，但将其扩展到大型数据集带来了重大的计算挑战。特别是，处理亲和矩阵（数据点之间的成对相似性矩阵）所需的存储和计算可能是禁止的。一种有希望的方法是在某种意义上近似这个矩阵。这个项目的目标是提供简单的近似技术，管理它们的空间和时间复杂度与近似质量之间的权衡。所提出的方法涉及采样技术，通过利用数据集中的潜在结构来实现这一目标，以最大限度地减少需要存储的信息量（近似）表示it.This导致的技术，加快计算速度，减少谱方法的内存需求，同时提供更好的近似。该项目还将延续团队在利用机器学习的进步进行数据驱动发现方面的势头。

项目成果

Beyond the Nystrom Approximation: Speeding up Spectral Clustering using Uniform Sampling and Weighted Kernel k-means

• DOI: 10.24963/ijcai.2017/347
• 发表时间: 2017-08
• 作者: Mahesh Mohan;C. Monteleoni

Convergence Rate of Stochastic k-means

随机 k 均值的收敛率

• 发表时间: 2017
• 期刊: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics
• 作者: Tang, Cheng;Monteleoni, Claire
• 通讯作者: Monteleoni, Claire