Efficient Distribution Classification Tasks via Optimal Transport Embeddings

分类允许人们根据相似性组织数据，并可以洞察各种领域的潜在关系，包括癌症研究、调查分析以及图像和文本处理。因此，开发高效的分类算法是一个重要的研究领域。一种方法，机器学习，已被证明在分类任务中是成功的，但它通常专注于向量空间中的数据点。然而，在许多应用中，数据实例自然被解释为整个点云，或者被解释为分布，而不是位于向量空间中。此外，这种数据集的高维导致了理论和计算上的挑战。这个项目致力于开发包含分布的高维数据集的分类算法，并将重点放在它们的理论分析和计算效率上。为此，首席调查员将使用最优运输框架，该框架提供了比较分布的自然方法。学生将参与这个项目的跨学科方面的培训。这个项目应用计算最优传输的知识，如线性嵌入和正则化优化，以及机器学习算法，来研究包含分布的数据集的分类任务。主要目标是开发具有保证误差界的近似方法，同时也允许算法洞察和有效实施。关于近似能力、计算可行性和数值分析的公开问题将被解决。具体地说，该项目解决了该领域中出现的四个基本问题：(1)什么类型的分布可以通过线性嵌入用传统的机器学习技术进行分类，以及正则化函数的选择如何影响精度？(2)通过使用欧几里德距离的线性嵌入，沃瑟斯坦距离和沃瑟斯坦重心的逼近有多好？(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.