EAGER: AF:Small: Algorithms for Relational Machine Learning

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

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.