EAGER: AF:Small: Algorithms for Relational Machine Learning

EAGER：AF：Small：关系机器学习算法

• 批准号: 2036077
• 负责人: Kirk Pruhs
• 金额: $ 14.88万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2036077&HistoricalAwards=false
• 关键词: EAGER; AF; Small; Algorithms; Relational

Relational database-management systems constitute a mature, ubiquitous, sophisticated technology that is deeply entrenched. Seemingly all organizations are collecting vastly increasing volumes of structured as well as unstructured data, and want to extract knowledge from this data using machine-learning techniques/algorithms. Thus many learning tasks faced by working data scientists involve relational data. Thus a marriage of machine learning and relational databases seems inevitable. However, standard machine-learning algorithms are not designed to operate directly on relational data, and further, it is far from obvious if and how one can adapt many of these algorithms to work on relational data without suffering a significant loss of efficiency. The current standard practice for a data scientist, confronted with a machine-learning task on relational data, is to issue a feature-extraction query to extract the (carefully curated) data from the relational database by joining together multiple tables to create a design matrix, and then to import this design matrix into some machine-learning tool to train the model. This standard practice is wasteful because (1) computing relational joins is computationally expensive, both in terms of time and space, (2) the resulting design matrix will likely contain much redundant information and consume much more space than the original tables, and thus (3) the machine-learning task takes more time than should conceptually be necessary. Algorithms that are orders of magnitude faster for standard machine-learning problems on relational data are certain to exist, and the goal of this research program is to discover them. Such algorithms would allow the extraction of information from data that is now not currently feasibly extractable.The research goals of this project are threefold. The first goal is to design and analyze relational algorithms for common machine-learning queries. A relational algorithm works directly on the relational data, without forming the design matrix, and can be orders of magnitude faster than standard machine-learning practice for such data. The second goal is to design a layer of relational algorithms for commonly arising subproblems and that can be utilized by the data scientists as a sort of middleware toolkit when designing their algorithms. The third goal is to build some intuition as to what problems are, and are not, solvable by relational algorithms and that researchers/practitioners can rely on when faced with a new problem. These goals will require the development of new algorithmic-design and -analysis techniques.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.

关系数据库管理系统构成了一种成熟的、无处不在的、复杂的、根深蒂固的技术。似乎所有组织都在收集大量的结构化和非结构化数据，并希望使用机器学习技术/算法从这些数据中提取知识。因此，数据科学家面临的许多学习任务都涉及到关系数据。因此，机器学习和关系数据库的结合似乎是不可避免的。然而，标准的机器学习算法并不是为直接操作关系数据而设计的，而且，如果以及如何在不遭受显著效率损失的情况下调整许多这些算法来处理关系数据还远远不明显。数据科学家在面对关系数据的机器学习任务时，目前的标准做法是发出一个特征提取查询，通过将多个表连接在一起创建设计矩阵，从关系数据库中提取（精心策划的）数据，然后将该设计矩阵导入某些机器学习工具以训练模型。这种标准实践是浪费的，因为(1)计算关系连接在计算上是昂贵的，无论是在时间和空间方面，(2)最终的设计矩阵可能包含许多冗余信息，并且比原始表消耗更多的空间，因此(3)机器学习任务花费的时间比概念上必要的时间要多。在关系型数据的标准机器学习问题上，速度快几个数量级的算法肯定是存在的，而本研究项目的目标就是发现它们。这样的算法将允许从目前无法提取的数据中提取信息。这个项目的研究目标有三个方面。第一个目标是为常见的机器学习查询设计和分析关系算法。关系算法直接在关系数据上工作，而不形成设计矩阵，并且可以比此类数据的标准机器学习实践快几个数量级。第二个目标是为经常出现的子问题设计一层关系算法，数据科学家在设计算法时可以将其用作一种中间件工具包。第三个目标是建立一些直觉，了解哪些问题可以用关系算法解决，哪些问题不能用关系算法解决，研究人员/从业者在面临新问题时可以依靠这些直觉。这些目标将需要开发新的算法设计和分析技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Relational Algorithms for k-means Clustering

• DOI: 10.4230/lipics.icalp.2021.97
• 发表时间: 2020-08
• 期刊: ArXiv
• 作者: Benjamin Moseley;K. Pruhs;Alireza Samadian;Yuyan Wang

Instance Optimal Join Size Estimation

实例最佳连接大小估计

• DOI: 10.1016/j.procs.2021.11.019
• 发表时间: 2021
• 期刊: Procedia Computer Science
• 作者: Abo-Khamis, Mahmoud;Im, Sungjin;Moseley, Benjamin;Pruhs, Kirk;Samadian, Alireza
• 通讯作者: Samadian, Alireza

An Approximation Algorithm for the Matrix Tree Multiplication Problem

• DOI: 10.4230/lipics.mfcs.2021.6
• 发表时间: 2021
• 作者: Mahmoud Abo Khamis;Ryan R. Curtin;Sungjin Im;Benjamin Moseley;H. Ngo;K. Pruhs;Alireza Samadian

Unconditional Coresets for Regularized Loss Minimization

• 发表时间: 2020-06
• 作者: Alireza Samadian;K. Pruhs;Benjamin Moseley;Sungjin Im;Ryan R. Curtin

A Relational Gradient Descent Algorithm For Support Vector Machine Training

支持向量机训练的关系梯度下降算法

• DOI: 10.1137/1.9781611976489.8
• 发表时间: 2021
• 期刊: Symposium on Algorithmic Principles of Computer Systems (APOCS
• 作者: Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
• 通讯作者: Samadian, A.