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

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

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.