Efficient Distribution Classification Tasks via Optimal Transport Embeddings

分类允许人们根据相似性组织数据，并可以提供对各种领域的潜在关系的洞察，包括癌症研究、调查分析以及图像和文本处理。因此，开发高效的分类任务算法是一个重要的研究领域。一种方法，机器学习，在分类任务中已经被证明是成功的，但它通常集中在向量空间中的数据点上。然而，在许多应用程序中，数据实例自然地被解释为整个点云或分布，而不是位于向量空间中。此外，这些数据集的高维导致了理论和计算上的挑战。该项目致力于开发由分布组成的高维数据集的分类算法，并将重点放在理论分析和计算效率上。为此，首席研究员将使用最优传输的框架，它提供了一种比较分布的自然方式。学生将参与并接受本项目跨学科方面的培训。该项目应用了计算最优传输的知识，如线性嵌入和正则化优化，以及机器学习算法，来研究由分布组成的数据集的分类任务。主要目标是开发具有保证误差范围的近似方法，同时允许算法洞察力和有效实现。将讨论关于近似能力、计算可行性和数值分析的开放性问题。具体来说，该项目解决了该领域出现的四个基本问题：(1)通过线性嵌入，传统机器学习技术可以对哪些类型的分布进行分类，正则化器的选择如何影响准确性？(2)利用欧氏距离通过线性嵌入近似Wasserstein距离和Wasserstein质心的效果如何？(3)对于分布的不相交类，在哪些条件下可以保证嵌入空间中简单分类器的可分性？(4)我们如何定制我们的框架以解决各种应用，例如音频或视频片段中的分类结构？该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Classification allows one to organize data based on similarities and can provide insight into underlying relationships in a large variety of fields, including cancer research, survey analysis, and image and text processing. As a result, the development of efficient algorithms for classification tasks is an important research area. One approach, machine learning, has proved successful in classification tasks, but it is usually focused on data points in vector spaces. In many applications, however, instances of data are naturally interpreted as entire point clouds, or as distributions, and do not lie in a vector space. Furthermore, the high dimension of such datasets leads to theoretical and computational challenges. This project is devoted to the development of classification algorithms for high-dimensional datasets consisting of distributions, and will focus both on their theoretical analysis and computational efficiency. To this end, the principal investigator will use the framework of optimal transport, which provides a natural way of comparing distributions. Students will be involved and trained in interdisciplinary aspects of this project.This project applies knowledge from computational optimal transport, such as linear embeddings and regularized optimization, and machine learning algorithms, to study classification tasks for datasets consisting of distributions. The main goal is to develop approximation methods with guaranteed error bounds that also allow for algorithmic insights and efficient implementation. Open problems on approximation power, computational feasibility, and numerical analysis will be addressed. Specifically, the project addresses four fundamental questions that arise in the field: (1) What are the types of distributions that can be classified with traditional machine learning techniques through linear embeddings, and how does the choice of a regularizer affect accuracy? (2) How well can the Wasserstein distance and Wasserstein barycenters be approximated through linear embeddings using Euclidean distances? (3) Under which conditions can we guarantee separability with simple classifiers in the embedding space for disjoint classes of distributions? (4) How can we tailor our framework to address various applications, such as classifying structures in audio or video segments?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.