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

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

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

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

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

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