RI: Small: Learning and Inference with Perfect Graphs

RI：小：通过完美图进行学习和推理

• 批准号: 1117631
• 负责人: Tony Jebara
• 金额: $ 44.94万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117631&HistoricalAwards=false
• 关键词: RI; Small; Learning; Inference; Perfect

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.

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