马尔科夫链上的矩阵Chernoff Bound和它在共现矩阵中应用

2020-12-02 16:34

导读：在 NeurIPS 2020 上，清华大学，微软雷德蒙德研究院，腾讯量子实验室和佐治亚理工的团队证明了一个马尔科夫链上的矩阵 Chernoff Bound，并介绍了它在共现矩阵收敛速度分析中应用。这项研究为分析马尔科夫链上的随机矩阵均值的特征值提供了有力的工具，被收录为 NeurIPS2020 的 poster。

论文名称： A MatrixChernoff Bound for Markov Chains and Its Application to Co－occurrence Matrices

Chernoff Bound 是一个重要的概率论工具，它刻画了样本均值的尾数概率随着样本数量增加而指数衰减的现象，在计算机科学的各个领域都有应用。传统的 Chernoff Bound 只能处理独立的标量随机变量，如下所示：

Garg 等人在 STOC 18 的工作将 Chernoff Bound 扩展到了马尔科夫相关的矩阵随机变量上。受到这个工作的启发，我们开始研究马尔科夫链上随机矩阵的 Chernoff Bound。我们证明了，给定一个有限状态马尔科夫链和一个把马尔科夫链的状态映射到埃尔米特（Hermitian）矩阵的函数。当我们在这个马尔科夫链上进行采样，并且计算采样得到的矩阵的均值时。矩阵均值的最大最小特征值的尾数概率依然随着样本数量增加而指数衰减。

我们还发现，这个定理可以用来刻画机器学习中一个重要统计量——共现矩阵的收敛行为。假设我们从一个马尔科夫链中采样了一个序列，并且要在这个序列上通过一个滑动窗口来估计窗口内元素的共现（代表性的算法有 NLP 中的 Word2vec 和图学习中的 DeepWalk），我们想研究这一类统计量的采样复杂度。下图给出了一个计算序列 1－2－3－2－3－1 上的共现矩阵的例子：

我们发现这一类统计量的收敛行为可以完美地被上述马尔科夫链上的矩阵 Chernoff Bound 刻画。具体来说，我们证明了为了估计一个准确的马尔科夫链状态共现矩阵，需要在马尔科夫链上进行 O（t（logt ＋ logn））步采样，其中 t 和 n 分别是马尔科夫链的混合时间（Mixing Time）和状态数量。我们还在三个人工数据和一个真实数据及上验证了这一理论。在 log－log scale 图中可以清楚的看到随着序列长度的增加误差指数收敛的现象。