導讀：在 NeurIPS 2020 上，清華大學，微軟雷德蒙德研究院，騰訊量子實驗室和佐治亞理工的團隊證明了一個馬爾科夫鏈上的矩陣 Chernoff Bound，并介紹了它在共現(xiàn)矩陣收斂速度分析中應用。這項研究為分析馬爾科夫鏈上的隨機矩陣均值的特征值提供了有力的工具，被收錄為 NeurIPS2020 的 poster。

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

Chernoff Bound 是一個重要的概率論工具，它刻畫了樣本均值的尾數(shù)概率隨著樣本數(shù)量增加而指數(shù)衰減的現(xiàn)象，在計算機科學的各個領域都有應用。傳統(tǒng)的 Chernoff Bound 只能處理獨立的標量隨機變量，如下所示：

Garg 等人在 STOC 18 的工作將 Chernoff Bound 擴展到了馬爾科夫相關的矩陣隨機變量上。受到這個工作的啟發(fā)，我們開始研究馬爾科夫鏈上隨機矩陣的 Chernoff Bound。我們證明了，給定一個有限狀態(tài)馬爾科夫鏈和一個把馬爾科夫鏈的狀態(tài)映射到埃爾米特（Hermitian）矩陣的函數(shù)。當我們在這個馬爾科夫鏈上進行采樣，并且計算采樣得到的矩陣的均值時。矩陣均值的最大最小特征值的尾數(shù)概率依然隨著樣本數(shù)量增加而指數(shù)衰減。

我們還發(fā)現(xiàn)，這個定理可以用來刻畫機器學習中一個重要統(tǒng)計量——共現(xiàn)矩陣的收斂行為。假設我們從一個馬爾科夫鏈中采樣了一個序列，并且要在這個序列上通過一個滑動窗口來估計窗口內元素的共現(xiàn)（代表性的算法有 NLP 中的 Word2vec 和圖學習中的 DeepWalk），我們想研究這一類統(tǒng)計量的采樣復雜度。下圖給出了一個計算序列 1－2－3－2－3－1 上的共現(xiàn)矩陣的例子：

我們發(fā)現(xiàn)這一類統(tǒng)計量的收斂行為可以完美地被上述馬爾科夫鏈上的矩陣 Chernoff Bound 刻畫。具體來說，我們證明了為了估計一個準確的馬爾科夫鏈狀態(tài)共現(xiàn)矩陣，需要在馬爾科夫鏈上進行 O（t（logt ＋ logn））步采樣，其中 t 和 n 分別是馬爾科夫鏈的混合時間（Mixing Time）和狀態(tài)數(shù)量。我們還在三個人工數(shù)據(jù)和一個真實數(shù)據(jù)及上驗證了這一理論。在 log－log scale 圖中可以清楚的看到隨著序列長度的增加誤差指數(shù)收斂的現(xiàn)象。