III: Small: Collaborative Research: Approximate Learning and Inference in Graphical Models

III：小：协作研究：图模型中的近似学习和推理

• 批准号: 1526914
• 负责人: Tony Jebara
• 金额: $ 16.41万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-10-01 至 2019-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526914&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Research; Approximate

This project is designing efficient methods for approximate learning and prediction in graphical models. In a typical setting, the parameters of an unknown graphical model are to be estimated from data observations. Once learned, the parameters are often used to make predictions about unseen data. The learning problem can be solved by estimating the parameters of the model that generate the observed data with the highest probability (a process known as maximum likelihood estimation), and the prediction task is typically performed by a statistical inference method. As exact learning and prediction are computationally intractable, in practice, we seek to replace the maximum likelihood estimation and prediction tasks with more tractable surrogates. This project is developing such surrogates that (a) can be leveraged for learning in large, real-world graphical models with hidden variables, (b) are orders of magnitude faster than the current state-of-the-art methods, and (c) provide a rigorous alternative to the more heuristic methods that are often employed at scale.Under certain conditions, surrogates can outperform exact maximum likelihood estimation combined with an approximate inference algorithm for prediction. However, many of the typical approaches are much too slow or too limited in power to be used to learn the kinds of large-scale graphical models with many hidden variables that arise in practice. This project studies the design of fast, distributed approximate learning and inference procedures based on the Bethe approximation, a surrogate that is known to perform well in practice. The core observation is that approximate maximum likelihood estimation using the Bethe surrogate can be reduced to solving a series of approximate inference problems via the Frank-Wolfe algorithm. The benefit of this approach is that many fast, combinatorial algorithms already exist for approximate inference in graphical models. In addition to provable bounds and convergence rates, the methods are practically evaluated using several publicly available datasets, primarily social network and image data. Baselines will be application-specific methods known to work well on those datasets, with the developed code made publicly available.

该项目正在设计用于图形模型中的近似学习和预测的有效方法。 在一个典型的设置中，一个未知的图形模型的参数是从数据观测估计。 一旦学习，这些参数通常用于对看不见的数据进行预测。 学习问题可以通过估计生成具有最高概率的观测数据的模型的参数（称为最大似然估计的过程）来解决，并且预测任务通常通过统计推断方法来执行。 由于精确学习和预测在计算上是难以处理的，在实践中，我们试图用更容易处理的代理来代替最大似然估计和预测任务。 该项目正在开发这样的代理，（a）可以用于在具有隐藏变量的大型真实世界图形模型中学习，（B）比当前最先进的方法快几个数量级，（c）为经常大规模使用的更启发式的方法提供严格的替代方案。替代可以胜过与用于预测的近似推理算法相结合的精确最大似然估计。 然而，许多典型的方法是太慢或太有限的权力，用于学习的大规模图形模型中出现的许多隐藏变量在实践中。 该项目研究基于Bethe近似的快速分布式近似学习和推理程序的设计，Bethe近似是一种在实践中表现良好的代理。 核心观察是，近似的最大似然估计使用Bethe代理可以减少到解决一系列的近似推理问题，通过Frank-Wolfe算法。 这种方法的好处是，已经存在许多用于图模型中近似推理的快速组合算法。 除了可证明的边界和收敛速度，这些方法实际上使用几个公开的数据集进行评估，主要是社交网络和图像数据。 基线将是已知在这些数据集上工作良好的特定于应用程序的方法，开发的代码将公开提供。