CAREER: Statistical Methods for Dimensionality Reduction in Machine Learning

职业：机器学习中降维的统计方法

• 批准号: 0650074
• 负责人: Lawrence Saul
• 金额: --
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-30 至 2010-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0650074&HistoricalAwards=false
• 关键词: CAREER; Statistical; Methods; Dimensionality; Reduction

This research addresses the problem of dimensionality reduction, discovering low dimensional structure hidden in high dimensional data. It arises in many fields of information processing, and poses a particular challenge to researchers attempting to build machines that emulate feats of human perception, such as recognizing faces and understanding speech. It also plays an increasingly prominent role in many applications of statistical and scientific computing. With the advent of widespread information technologies, it has become possible to collect and manipulate ever-increasing amounts of experimental data. Thus, scientists interested in the exploratory analysis and visualization of large multivariate data sets face similar challenges in information processing as our perceptual systems.This research focuses on two recently proposed algorithms for dimensionality reduction. The two algorithms address the "curse of dimensionality" as it arises in two different settings of machine learning: (1) unsupervised learning, where the dimensionality reduction is performed without any feedback from the learning environment, and (2) supervised learning, where the dimensionality reduction is performed with the benefit of labeled examples.The first algorithm to be studied is Locally Linear Embedding (LLE), an unsupervised learning algorithm that computes low dimensional, neighborhood preserving embeddings of high dimensional data. The data, assumed to lie on a nonlinear manifold, is mapped into a single global coordinate system of lower dimensionality. The mapping is derived from the symmetries of locally linear reconstructions, and the actual computation of the embedding reduces to a sparse eigenvalue problem. Notably, the optimizations in LLE (though capable of generating highly nonlinear embeddings) are simple to implement, and they do not involve local minima. LLE has applications to exploratory data analysis, scientific visualization, and computer vision.The second algorithm is Multiplicative Margin Maximization (M3), a supervised learning algorithm for nonnegative quadratic programming in support vector machines (SVMs). Support vector machines currently provide state-of-the-art solutions to many problems in machine learning, particularly those involving data sets of high dimensionality. Solving the quadratic programming problem in SVMs, however, remains a significant bottleneck in their implementation. The M3 algorithm is designed to alleviate this bottleneck. Its update rules have a simple closed form, and they converge monotonically to the solution of the maximum margin hyperplane. Moreover, they do not involve any heuristics such as choosing a learning rate or deciding which variables to update at each iteration. They optimize the traditionally proposed objective function for SVMs and can be applied to problems in classification, regression, and novelty detection.The algorithms to be studied in this research are easy to implement, but the problems they solve are quite complex. Compared to previous approaches, they are distinguished not only by their novel simplicity and well-behaved optimizations, but also by the unexpected connections they make to other areas in mathematics, computer science, and statistics. The work will not only develop the theoretical foundations of these algorithms, but also attempt to scale them up to increasingly large problems in machine learning.This CAREER award recognizes and supports the early career-development activities of a teacher-scholar who is likely to become an academic leader of the twenty-first century. The research is expected to have a broad impact across many areas of science and engineering, by overcoming the challenges posed by data sets of extremely high dimensionality. Software toolkits will be published, so that researchers everywhere will have access to state-of-the-art methods for dimensionality reduction. The educational innovations will include new undergraduate and graduate courses in artificial intelligence, machine learning, statistical computing, and sensory processing.

本研究针对高维数据的降维问题，发现高维数据中隐藏的低维结构。它出现在信息处理的许多领域，对试图建造模仿人类感知壮举的机器的研究人员构成了特别的挑战，例如识别人脸和理解语音。它在统计和科学计算的许多应用中也发挥着日益突出的作用。随着广泛使用的信息技术的出现，收集和处理不断增加的实验数据成为可能。因此，对大型多变量数据集的探索性分析和可视化感兴趣的科学家在信息处理方面面临着与我们的感知系统相似的挑战。这两个算法解决了机器学习的两种不同环境中出现的“维度灾难”：(1)无监督学习，其中降维是在没有来自学习环境的任何反馈的情况下执行的；(2)监督学习，其中降维是利用已标记的样本来执行的。第一个要研究的算法是局部线性嵌入(LLE)，这是一种计算高维数据的低维、邻域保持嵌入的无监督学习算法。假设数据位于非线性流形上，将其映射到低维的单个全局坐标系。该映射由局部线性重构的对称性导出，嵌入的实际计算量归结为稀疏特征值问题。值得注意的是，LLE中的优化(尽管能够生成高度非线性的嵌入)很容易实现，并且它们不涉及局部极小值。LLE算法在探索性数据分析、科学可视化和计算机视觉等领域有着广泛的应用。第二种算法是乘性边距最大化算法(M3)，这是一种基于支持向量机的非负二次规划的有监督学习算法。支持向量机目前为机器学习中的许多问题提供了最先进的解决方案，特别是那些涉及高维数据集的问题。然而，解决支持向量机中的二次规划问题仍然是其实现的一个重要瓶颈。M3算法就是为了缓解这个瓶颈而设计的。它的更新规则具有简单的闭合形式，并且单调收敛到最大裕度超平面的解。此外，它们不涉及任何启发式方法，例如选择学习速率或决定在每次迭代中更新哪些变量。它们对传统的支持向量机目标函数进行了优化，可应用于分类、回归和新颖性检测等问题，算法易于实现，但解决的问题比较复杂。与以前的方法相比，它们的不同之处不仅在于它们新颖的简单性和良好的优化，而且还因为它们与数学、计算机科学和统计学中的其他领域建立了意想不到的联系。这项工作不仅将发展这些算法的理论基础，而且还试图将它们扩大到机器学习中越来越大的问题。该职业奖表彰并支持一位可能成为21世纪学术领袖的教师-学者的早期职业发展活动。预计这项研究将通过克服极高维度的数据集带来的挑战，在科学和工程的许多领域产生广泛影响。软件工具包将被发布，这样世界各地的研究人员都可以使用最先进的降维方法。教育创新将包括人工智能、机器学习、统计计算和感觉处理方面的新本科生和研究生课程。