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的法定任务，并通过使用该基金会的智力功能和广泛的影响来评估Criteria criteria criteria criteria criteria。

项目成果

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.

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

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

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