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

从历史上看，统计领域是围绕着对现象的多次独立观察而发展起来的。然而，从生物学到社交网络，现代应用的进步越来越需要对依赖于观察的更深层次的理解。相依观察引入了在独立抽样中看不到的偏差。如果解释不当，它们往往会导致误导性的结论。这项研究开发了一个统计框架来解释由相依观察产生的样本。然后，问题被扭转，以开发检测数据中有意义的依赖关系的算法。例如，这类算法被用来识别协同工作的基因，或发现社交网络在某些问题上的两极分化程度。这项研究不仅被转化为课堂、示范和推广计划，而且夏威夷的地理位置也被用来接触科学和工程领域中代表性较低的社区，特别是妇女和太平洋岛民社区。有限样本可能不能很好地反映马尔可夫过程的统计特性，无论样本大小有多大。这种偏差通常被形式化为混合，在独立抽样中看不到。本研究在马尔可夫样本反映渐近平稳性质之前就对其进行了分析，并发展了一个慢混合马尔可夫过程的推理、分析和模拟的框架。然后，针对图中被广泛研究的社区发现任务，开发了基于过去耦合的算法基元，其中顶点被划分成簇，使得簇内的顶点比不同簇中的节点连接得更紧密。针对机器学习中的几种重采样方法，如交叉验证法和Bootstrap法都是以独立采样为前提的，并且在马尔可夫环境下没有很好的相似性，本研究针对潜在的慢混合马尔可夫过程，提出了新的重采样方法。

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.