AF: Small: Approximation Algorithms for Learning Metric Spaces

AF：小：学习度量空间的近似算法

• 批准号: 1815145
• 负责人: Anastasios Sidiropoulos
• 金额: $ 39.99万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2023-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815145&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Algorithms; Learning

The analysis of large and complicated data sets is a task of increasing importance in several brunches of science and engineering. In many application scenarios, the data consists of a set of objects endowed with some information that quantifies similarity or dissimilarity of certain pairs. Examples of such inputs include statistical distributions, user preferences in social networks, DNA sequences, and so on. A natural way to interpret such data sets is as metric spaces. That is, each object is treated as a point, and the dissimilarity between two objects is encoded by their distance. The successful application of this data-analytic framework requires finding a distance function that faithfully encodes the ground truth. The project seeks to develop new algorithms for computing such faithful metrical representations of data sets. The underlying research problems lead to new connections between the areas of computational geometry, algorithm design, and machine learning. The project aims at transferring ideas between these scientific communities, and developing new methods for data analysis in practice. The project will be part of the investigator's curriculum development, teaching, and educational and outreach activities. The main research problems that the project seeks to study will form the basis for the training of both undergraduate and graduate students. The investigator is committed to working with minorities and underrepresented groups.This metrical interpretation of data sets has been successful in practice and has lead to a plethora of algorithmic methods and ideas, such as clustering, dimensionality reduction, nearest-neighbor search, and so on. The area of metric learning is concerned mainly with methods for discovering an underlying metric space that agrees with a given set of observations. Specifically, the problem of learning the distance function is cast as an optimization problem, where the objective function quantifies the extend to which the solution satisfies the input constraints. A common thread in many works on metric learning is the use of methods and ideas from computational geometry and the theory of metric embeddings. Over the past few decades, these ideas have also been the subject of study within the theoretical computer science community. However, there are several well-studied problems in metric learning that have not received much attention in the algorithms and computational geometry communities. Moreover, there are many metric embedding tools and techniques, that where developed within the algorithms community, that have not yet been used in the context of metric learning. The project aims at bridging this gap by a systematic study of algorithmic metric learning problems from the point of view of computational geometry and approximation algorithms. The major goals of this effort are transferring algorithmic tools to the metric learning framework, as well as providing theoretical justification for metric learning methods that are successful in practice but currently lack provable guarantees.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.

在科学和工程的几个分支中，大型复杂数据集的分析是一项日益重要的任务。在许多应用场景中，数据由一组对象组成，这些对象被赋予了一些信息，这些信息量化了某些对的相似性或不相似性。这些输入的例子包括统计分布、社交网络中的用户偏好、DNA序列等，解释这些数据集的一种自然方式是作为度量空间。也就是说，每个对象被视为一个点，两个对象之间的不相似性由它们的距离编码。这种数据分析框架的成功应用需要找到一个距离函数，忠实地编码地面真相。该项目旨在开发新的算法来计算数据集的这种忠实的度量表示。潜在的研究问题导致计算几何，算法设计和机器学习领域之间的新联系。该项目旨在这些科学界之间交流思想，并在实践中开发新的数据分析方法。该项目将成为调查员课程编制、教学、教育和外联活动的一部分。该项目寻求研究的主要研究问题将成为本科生和研究生培训的基础。研究者致力于与少数群体和代表性不足的群体合作。这种对数据集的度量解释在实践中取得了成功，并导致了大量的算法方法和思想，如聚类，降维，最近邻搜索等。度量学习领域主要关注发现与给定观测集一致的底层度量空间的方法。具体地，学习距离函数的问题被转换为优化问题，其中目标函数量化解满足输入约束的程度。许多关于度量学习的作品中的一个共同点是使用计算几何和度量嵌入理论的方法和思想。在过去的几十年里，这些想法也一直是理论计算机科学界研究的主题。然而，在度量学习中有几个研究得很好的问题，在算法和计算几何社区中没有得到太多的关注。此外，有许多度量嵌入工具和技术，在算法社区内开发，尚未在度量学习的上下文中使用。该项目旨在弥合这一差距的算法度量学习问题的角度来看，计算几何和近似算法的系统研究。这项工作的主要目标是将算法工具转移到度量学习框架，以及为在实践中取得成功但目前缺乏可证明保证的度量学习方法提供理论依据。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

Geometric Algorithms for k-NN Poisoning

k-NN 中毒的几何算法

• 发表时间: 2023
• 期刊: Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023
• 作者: Centurion, Diego Ihara;Chubarian, Karine;Fan, Bohan;Sgherzi, Francesco;Rashakrishnan, Thiruvenkadam;Sidiropoulos, Anastasios;Straight, Angelo
• 通讯作者: Straight, Angelo

Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces

低失真嵌入任意一维空间的算法

• 发表时间: 2018
• 期刊: 34th International Symposium on Computational Geometry (SoCG 2018
• 作者: Carpenter, Timothy;Fomin, Fedor V.;Lokshtanov, Daniel;Saurabh, Saket;Sidiropoulos, Anastasios
• 通讯作者: Sidiropoulos, Anastasios

Grouping Words with Semantic Diversity

• DOI: 10.18653/v1/2021.naacl-main.257
• 发表时间: 2021-06
• 作者: Karine Chubarian;A. Khan;Anastasios Sidiropoulos;Jia Xu

Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces

低维空间低失真嵌入的近似算法

• DOI: 10.1137/17m1113527
• 发表时间: 2019
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Sidiropoulos, Anastasios;Badoiu, Mihai;Dhamdhere, Kedar;Gupta, Anupam;Indyk, Piotr;Rabinovich, Yuri;Racke, Harald;Ravi, R.
• 通讯作者: Ravi, R.

NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs

• 发表时间: 2021
• 作者: Evan McCarty;Qi Zhao;Anastasios Sidiropoulos;Yusu Wang