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) 机器学习任务花费的时间比概念上需要的时间要多。 对于关系数据上的标准机器学习问题来说，速度快几个数量级的算法肯定是存在的，本研究项目的目标就是发现它们。 此类算法将允许从目前无法提取的数据中提取信息。该项目的研究目标有三个。 第一个目标是设计和分析常见机器学习查询的关系算法。关系算法直接作用于关系数据，无需形成设计矩阵，并且可以比此类数据的标准机器学习实践快几个数量级。 第二个目标是为常见的子问题设计一层关系算法，数据科学家在设计算法时可以将其用作中间件工具包。 第三个目标是建立一些直觉，了解哪些问题可以通过关系算法解决，哪些问题不能通过关系算法解决，并且研究人员/从业人员在面对新问题时可以依赖这些直觉。 这些目标将需要开发新的算法设计和分析技术。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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.