CAREER: Principled Unsupervised Learning via Minimum Volume Polytopic Embedding

一般来说，无监督学习问题比机器学习中的有监督问题要困难得多。这不仅在机器学习研究中，而且在教育中都带来了相当大的挑战，因为几乎所有的模型都是NP难的（可能只有PCA例外），而且几十年来，社区一直在研究没有最优性保证的算法。该项目旨在开发一个最小体积多面体嵌入的原则性框架，该框架统一了各种无监督学习问题，如独立成分分析，字典学习和非负矩阵分解，通过将数据点集嵌入到规则多面体（如单纯形，盒子或正交多面体）中来处理问题，同时由新的矩阵体积标准指导。好处是双重的：1）它提供了有限样本的可识别性保证，2）它取决于算法的发展，可以在温和的假设下最优地解决这些NP难问题。PI先前的工作已经显示出对前一个好处的强可识别性保证，而本项目将专注于解决后一个问题，从Frank-Wolfe算法框架开始，该框架已经显示出巨大的经验成功。此外，该项目还将大大扩展其应用领域，如强化学习中的POMDP识别，电力系统中的聚合灵活性，以及自然语言处理中的深度多面体词嵌入。在数学框架方面，还开发了处理非线性和深度表示学习的扩展，这些扩展一直难以实现，预计将在该项目的理论和算法开发的主要焦点之外产生广泛的影响。我们制定了广泛的教育和推广计划，以证实研究的影响，并鼓励来自各种背景的学生从事计算机科学和机器学习研究。在这个项目中，我们提出了一个新颖的框架，试图将所有数据点转换为规则多面体中的点。（例如单纯形、盒子或正交复合形），因此目标多面体嵌入，同时由新的矩阵体积优化准则指导。PI先前的工作不仅显示了潜在表示的强可识别性保证，而且在应用中也取得了广泛的实际成功。先前的成功激励PI进一步研究这个方向，解决未解决的理论挑战，拓宽学习框架，并寻求更多的应用领域。这个项目将沿着以下协同推力发展：在推力1中，设计了一个Frank-Wolfe算法来解决NP难的多面体嵌入问题。受最近在分析保证非凸学习方面的发展的启发，提出了一种有希望的途径来提供可证明的全局最优性保证。在推力2中，所提出的学习框架将用于仅从具有计算保证的观测中识别未知的POMDP。研究沿着这一推力将适用于医疗保健建议的医疗数据。在推力3中，引入了电力系统中的聚合柔性问题，这提供了一个有趣的多面体嵌入的双重解释。在真实的数据上的实验将验证性能并扩展框架以处理非线性约束。在Thrust 4中，我们提出了一种新的词嵌入方案，不仅具有计算保证，而且具有语义解释。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Unsupervised learning problems are in general significantly more difficult than their supervised counterparts in machine learning. This poses considerable challenges in not only machine learning research but also education, as nearly all models are NP-hard (with possibly the sole exception of PCA), and the community has been dwelling on algorithms without optimality guarantees for several decades. This project aims at developing a principled framework of minimum volume polytopic embedding that unifies various unsupervised learning problems such as independent component analysis, dictionary learning, and nonnegative matrix factorization, by treating the problem as embedding the set of data points into a regular polytope such as a simplex, a box, or an orthoplex, while guided by a novel matrix volume criterion. The benefit is two-fold: 1) it provides identifiability guarantee with finite samples, and 2) it hinges on the development of algorithms that could optimally solve these NP-hard problems under mild assumptions. The PI’s prior work has showed strong identifiability guarantees for the former benefit, while this project will focus on resolving the latter one, starting from a Frank-Wolfe algorithmic framework that has shown great empirical success. Furthermore, this project will greatly expand its application domains such as POMDP identification in reinforcement learning, aggregate flexibility in power systems, and deep polytopic word embedding in natural language processing. In terms of the mathematical framework, extensions to handle nonlinearity and deep representation learning are also developed, which have been elusive and are expected to be widely impactful beyond the main focus of theory and algorithm development in this project. Extensive education and outreach plans are laid out to corroborate the research impact and encourage students from all backgrounds to engage in computer science and machine learning research.In this project we propose a novel framework that tries to transform all data points as points in a regular polytope (such as a simplex, a box, or an orthoplex), hence the aim polytopic embedding, while guided by a novel matrix volume optimization criterion. The PI's prior work not only showed strong identifiability guarantees of the latent representation, but also found a wide variety of practical success in applications. Prior success inspires the PI to further investigate this direction, resolve unsettled theoretical challenges, broaden the learning framework, and seek even more application domains. This project will evolve along the following synergistic thrusts: in Thrust 1, a Frank-Wolfe algorithm is designed to solve the NP-hard polytopic embedding problem. Inspired by recent developments in analyzing guaranteed non-convex learning, a promising pathway is laid out to provide provable global optimality guarantees. In Thrust 2, the proposed learning framework will be used to identify an unknown POMDP from only observations with computational guarantees. Research along this thrust will be applied to healthcare recommendations from medical data. In Thrust 3, the problem of aggregate flexibility in power systems is introduced, which provides an interesting dual interpretation of polytopic embedding. Experiments on real data will validate the performance and expand the framework to handle nonlinear constraints. In Thrust 4, we propose a novel word embedding scheme with not only computational guarantee but also semantic interpretation. An extension to deep polytopic embedding framework is also introduced.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.