Learning Graphical Models: Hardness and Tractability

图形模型提供了以简洁的方式捕获复杂的非结构化数据中存在的不确定性的方法。它们特别适合于进行大规模的推理计算。它们有可能成为现代数据驱动的决策任务中不确定性建模的主要方式。这个项目将通过开发有效的方法来从观察中学习图形模型表示法来实现这一点。该项目的成果将在社会和行业产生广泛的影响。这将包括但不限于，我们理解人类在社交网络中的行为、处理在生物实验中捕获的信息、自动化语言和语音处理以及捕获各种金融工具之间的相互关系的能力。图形模型的一般应用需要解决两个基本任务。首先，给定数据，什么是合适的图形模型？其次，给出一个图形模型，人们如何从部分观察中进行推断？在历史上，通常使用领域知识来选择模型，例如语音处理中的隐马尔可夫模型。因此，大量的工作被投入到第二个问题上，即开发推理算法(例如，信念传播)。然而，对于大多数现代应用程序，使用哪种类型的模型完全不清楚。因此，对于现代应用来说，学习模型的第一个问题是至关重要的。该项目的目标是发展对从观测数据中学习GM的问题的概念和算法方面的理解。该项目的一个方面是得出新的下限，以便了解基本统计限制和计算限制之间的相互作用。受这些下限的影响，该项目将寻求确定新的和相关的模型子类，对于这些模型子类，学习是容易处理的，并伴随着有效的学习算法。

Graphical models provide means to capture uncertainty present in complex, unstructured data in a succinct manner. They are particularly suited for performing inference computation at scale. They hold potential to become primary way to model uncertainty in modern data-driven decision-making tasks. This project will enable this by developing efficient methods to learn graphical model representation from observations. The outcome of this project will have wide ranging impact in society and industry. This will include, but not restricted to, our ability to understand human behavior in social networks, processing information captured in biological experiments, automated language and speech processing as well as capturing inter-relationship between various financial instruments. A generic application of Graphical model requires solving two basic tasks. First, given data, what is an appropriate graphical model? And second, given a graphical model, how does one perform inference from partial observations? Historically, domain knowledge was used to choose the model, for example Hidden Markov Models in speech processing. Therefore, a significant amount of effort has been devoted to the second problem, of developing inference algorithms (for example, Belief propagation). However, it is not at all clear what type of model to use for most modern applications. Thus for modern applications the first problem of learning the model is paramount. The goal of this project is to develop understanding, both conceptual and algorithmic, of the problem of learning GMs from observed data. One aspect of the project is to derive new lower bounds in order to understand the interplay between fundamental statistical and computational limits. Informed by these lower bounds, the project will seek to determine new and relevant model subclasses for which learning is tractable accompanied by efficient learning algorithms.