Efficient Distribution Classification Tasks via Optimal Transport Embeddings

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

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.