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-07
• 期刊: 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

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

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

A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families

基于局部指数族的对数凹最大似然多项式时间算法

• 发表时间: 2019-12
• 期刊: Advances in Neural Information Processing Systems 32 (NIPS 2019
• 作者: Axelrod, Brian;Diakonikolas, Ilias;Stewart, Alistair;Sidiropoulos, Anastasios;Valiant, Gregory
• 通讯作者: Valiant, Gregory

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

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

• DOI: 10.1137/17m1113527
• 发表时间: 2019-01
• 期刊: 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.

Grouping Words with Semantic Diversity

具有语义多样性的单词分组

• DOI: 10.18653/v1/2021.naacl-main.257
• 发表时间: 2021-06-01
• 期刊: Proceedings of the 8th International Conference on Computing and Artificial Intelligence
• 作者: Karine Chubarian;A. Khan;Anastasios Sidiropoulos;Jia Xu
• 通讯作者: Jia Xu