Learning Graphical Models: Hardness and Tractability

学习图形模型：硬度和易处理性

• 批准号: 1462158
• 负责人: Devavrat Shah
• 金额: $ 30万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2020-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1462158&HistoricalAwards=false
• 关键词: Learning; Graphical; Models; Hardness; Tractability

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.

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

项目成果

Model Agnostic Time Series Analysis via Matrix Estimation

通过矩阵估计进行与模型无关的时间序列分析

• 发表时间: 2018-12
• 期刊: ACM SIGMETRICS performance evaluation review
• 作者: Agarwal, Anish;Amjad, Muhammad Jehangir;Shah, Devavrat;Shen, Dennis
• 通讯作者: Shen, Dennis

Censored Demand Estimation in Retail

零售业的审查需求估计

• DOI: 10.1145/3154489
• 发表时间: 2017-12-19
• 期刊: Proceedings of the ACM on Measurement and Analysis of Computing Systems
• 作者: M. Amjad;Devavrat Shah
• 通讯作者: Devavrat Shah

Model Agnostic Time Series Analysis via Matrix Estimation

通过矩阵估计进行与模型无关的时间序列分析

• DOI: 10.1145/3287319
• 发表时间: 2018-02-25
• 期刊: Proceedings of the ACM on Measurement and Analysis of Computing Systems
• 作者: Anish Agarwal;M. Amjad;Devavrat Shah;Dennis Shen
• 通讯作者: Dennis Shen

mRSC: Multidimensional Robust Synthetic Control

mRSC：多维鲁棒综合控制

• DOI: 10.1145/3309697.3331507
• 发表时间: 2019-07
• 期刊: ACM SIGMETRICS
• 作者: Amjad, Muhammad Jehangir;Misra, Vishal;Shah, Devavrat;Shen, Dennis
• 通讯作者: Shen, Dennis

Q-learning with nearest neighbors

最近邻的 Q 学习

• 发表时间: 2018-10
• 期刊: Nips
• 作者: Shah, Devavrat;Xie, Qiaomin
• 通讯作者: Xie, Qiaomin