RI: Small: Learning and Inference with Perfect Graphs

本提案研究了从数据中学习和对数据进行推理的新的计算和组合工具。因此，它充当了机器学习社区和组合学社区之间的桥梁。后一个领域开发有效的算法或显示何时存在特定问题的有效解决方案。该项目将支持这两个领域交叉的研究生将最新的理论结果与实际数据问题结合起来。该团队将制作一个包含教程、数据集、可下载代码、交互式可视化示例和课程材料的网站，以便更好地整合这两个领域。组合学社区已经确定了一组被称为完美图的输入，在这些输入中，其他困难的问题都可以有效地解决。本提案将研究如何将这一强大的理论结果与机器学习领域联系起来，并正式描述哪些学习和推理问题是可有效解决的。更具体地说，该团队将研究数据学习问题（如将数据集聚类到自相似的子组中或在数据库中发现异常）和统计推断问题（从观察到的测量中计算最可能或最典型的结果）。这些问题将被编译或表示为图和网络。然后，可以使用完美图论更正式地诊断这些图和网络，以确定问题的实例是否容易（或困难），并通过完美图上的精确算法提供有效的解决方案。这些求解器将使用消息传递或凸编程来实现。

This proposal investigates new computational and combinatorial tools for learning from data and performing inference about data. As such, it serves as a bridge between the machine learning community and the combinatorics community. The latter field develops efficient algorithms or shows when an efficient solution to a particular problem exists. The project will support graduate students in the intersection of these two fields to combine recent theoretical results with practical data problems. The team will produce a website of tutorials, data sets, downloadable code, interactive visual examples and course materials to allow better integration across the two fields. The combinatorics community has identified a family of inputs called perfect graphs where otherwise hard problems are efficiently solvable. This proposal will investigate how to bridge this powerful theoretical result to the area of machine learning and formally characterize which learning and inference problems are efficiently solvable.More specifically, the team will investigate data learning problems (such as clustering a data set into subgroups that are self-similar or finding anomalies in a database) and statistical inference problems (computing the most likely or most typical outcome from observed measurements). These problems will be compiled or represented as graphs and networks. Then, these graphs and networks can be more formally diagnosed using perfect graph theory to determine if the instance of the problem is easy (or hard) and to provide efficient solutions via exact algorithms on perfect graphs. These solvers will be implemented using message passing or convex programming.