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.