CIF:Small:Collaborative Research:Statistics of slow mixing Markov processes: theory and applications to community detection

CIF：小：协作研究：慢混合马尔可夫过程的统计：社区检测的理论和应用

• 批准号: 1619452
• 负责人: Narayana Santhanam
• 金额: $ 49.95万
• 依托单位: University of Hawaii
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-15 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1619452&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Statistics

Historically, the field of statistics developed around multiple independent observations of phenomena. Yet progress in modern applications from biology to social networks increasingly requires deeper understanding of observations that are dependent. Dependent observations introduce biases unseen in independent sampling. If not interpreted properly, they often lead to misleading conclusions. This research develops a statistical framework to interpret samples generated by dependent observations. The problem is then turned around to develop algorithms that detect meaningful dependencies in data. Such algorithms are used, for example, to identify genes working together, or find the extent to which social networks are polarized on certain issues. Not only is this research translated to classes, demonstrations and outreach programs, but also the location in Hawaii is leveraged to reach out to underrepresented communities in science and engineering, in particular, women and the Pacific Islander community.Stationary properties of Markov processes may not be very well reflected by finite samples, no matter how large the sample size. This bias is often formalized as mixing, and is unseen in independent sampling. This research analyzes Markov samples even before the samples reflect the asymptotic stationary properties, and develops a framework for inference, analysis and simulation of slow mixing Markov processes. Then, algorithmic primitives based on coupling from the past are developed for the widely studied task of community detection in a graph, where vertices are partitioned into clusters so that intra-cluster vertices are connected tighter than those in disparate clusters. As several resampling procedures in machine learning such as cross validation and bootstrap are premised on independent sampling and have no good analogs in the Markov setting, this research develops new resampling approaches for potentially slow mixing Markov processes.

从历史上看，统计学领域是围绕着对现象的多个独立观察而发展起来的。然而，从生物学到社交网络的现代应用的进展越来越需要对依赖性观察的更深入理解。相关观测引入了独立抽样中看不到的偏差。如果解释不当，往往会得出误导性的结论。本研究开发了一个统计框架来解释相关观测产生的样本。然后将问题转向开发检测数据中有意义的依赖关系的算法。例如，这种算法被用来识别共同工作的基因，或者发现社交网络在某些问题上的两极分化程度。 这项研究不仅被翻译成课程，示范和推广计划，而且在夏威夷的位置是利用接触到代表性不足的社区在科学和工程，特别是妇女和太平洋岛民community.Stationary性能的马尔可夫过程可能不会很好地反映有限的样本，无论多大的样本量。这种偏差通常被形式化为混合，在独立抽样中是看不到的。 本研究分析马尔可夫样本，甚至在样本反映渐近平稳特性，并开发了一个框架的推理，分析和模拟慢混合马尔可夫过程。然后，从过去的耦合的基础上开发的算法原语的广泛研究的任务，社区检测图中，顶点被划分为集群，使集群内的顶点连接紧密比那些在不同的集群。由于机器学习中的几个重新排序过程，如交叉验证和自举，都是基于独立采样的，并且在马尔可夫环境中没有很好的类似物，因此本研究为潜在的慢混合马尔可夫过程开发了新的重新排序方法。