前言
因為想做一下文本自動摘要，文本自動摘要是NLP的重要應用，搜了一下，有一種TextRank的算法，可以做文本自動摘要。其算法思想來源於Google的PageRank，所以先把PageRank給了解一下。
馬爾科夫鏈
我感覺說到PageRank，應該要提起馬爾科夫鏈，因為PageRank在計算的過程中，和馬爾科夫鏈轉移是十分相似的，只是PageRank在馬爾科夫鏈的轉移上做了一些動。
馬爾科夫鏈的維基百科裡是這麼說的：
形式定義好像有點複雜。我這裡只想介紹自己所認識的馬氏鏈，一個簡單通俗易懂的馬氏鏈。
假設有一個離散型隨機變量，表示的是當前社會中貧窮，中等和富有的人的概率，其初始分布是：
表示社會中貧窮的人佔28%，中等的人佔68%，富有的人佔11%，
這是初始狀態，可以想像成這是我們所處地球的第一代人X1（那個時候就有貧富差距了），接下來第一代人要生小孩，形成第二代人X2，這個叫做狀態的轉移，從X1轉移到X2。怎麼轉移呢，這是有一個概率的：
上述表格代表的是，父親屬於哪個階級，那兒子屬於某個階級的概率。比如父親是富人，兒子也是富人的概率是 0.52，這表示大概一半的富二代以後都會敗光家產。所以根據以上表格，第二代窮人X2的概率是
以上的計算過程實際上矩陣相乘，表格裡的數據組成一個矩陣P 叫做概率轉移矩陣
以此類推，不斷計算，不斷狀態轉移，我們發現從第7代開始，就穩定不變了：
這不是偶然，從任意一個X1的分布出發，經過概率轉移矩陣，都會收斂到一個穩定的分布
這個轉移的鏈條就是馬爾科夫鏈，它最終會收斂到穩定分布π ，也就是π.P=π ，至於為什麼會這樣，肯定是和狀態轉移矩陣有關，最終的穩定分布不是由初始狀態X1決定的，而是由轉移矩陣P決定的，具體就不細究了。
總之，我們得出這樣一個結論，如果有一個隨機變量分布為X 和狀態轉移矩陣P，隨機變量分布的下一個狀態X(next) 可以由上一個狀態X(pre) 乘以矩陣P得來，那麼經過n步迭代，最終會得到一個不變的，平穩的分布。
PageRank
PageRank 是谷歌搜尋引擎的進行網頁排名算法，它是把所有網頁都構成一張圖，每個網頁是一個節點，如果一個網頁中有鏈向其他網頁的連結，那麼就有一條有向邊連接這兩個點。
有了這張圖可以幹嘛嗎？PageRank 認為，每條邊都是一個投票動作，A > B 是A在給B投票，B的權重就會增加。
舉個例子就非常清楚了，假設網際網路上一共就4個頁面，全球幾十億網名，每天只能看這個4個web頁面，這四個頁面分別是A,B,C,D，其中B頁面有兩個超連結指向A,C，C中有1個超連結指向A，D中有三個超連結指向A。其畫成一張圖，就是這樣的：
這裡要清楚 PageRank 計算的值是什麼，PageRank 計算的最終值，是每個網頁被往點擊瀏覽的概率，也就相當於權重。所以這還是一個離散型隨機變量，
。一開始假設每個網頁被瀏覽的概率都是相同的，每個頁面被網民點擊的概率都是0.25，
PageRank 的計算過程就和上面所說的馬爾科夫鏈一樣，初始狀態0就是全球網民同時上網，每個網民每次都只點擊一次網頁，每個網頁被訪問的概率。那麼狀態2 1就是全體網民開始點擊瀏覽第二個網頁時，每個網頁被訪問的概率。PageRank 也有一個概率轉移矩陣，而就存在於上圖中，其中,表i網頁鏈向j的連接數除以i網頁的所有外鏈數。其實意思就是，當你訪問到i網頁的時候，有多大的概率訪問j網頁。所以對於某個特定的狀態，全體網民開始訪問第n個網頁，它是由上一個狀態1全體網民訪問到第n-1個網頁，通過某種概率得來。這和上面的窮人，富人非常相似。我們計算A頁面在第n次，也就是狀態n的時候被訪問的概率
所以
整個PageRank 計算直到得到平穩分布，這就是最終每個網頁被網民點擊的概率，或者叫做權重，排名。
接下來咱們具體計算一下，上述四個頁面A,B,C,D的最終權重是多少。我們寫一段C++ 程序來模擬PageRank 的計算過程。
其中p是轉移矩陣，a是我們要求的隨機變量的分布。
運行結果如下
我們發現，到最後的平穩分布居然是，為什麼會發生這樣的情況呢？因為D這個網頁，沒有任何網頁連結到它，所以在轉移的過程中，它的下一個狀態肯定為0，又因為D變成0了，所以影響到它所連結的網頁，最終會導致所有網頁的概率值都變成0。
為了避免這樣的情況，PageRank 引入了一個阻尼係數d和隨機訪問的概念 ,d是一個概率值在0-1之間，這個d的物理意義是當你瀏覽到一個網頁的時候，繼續點擊網頁中的連結瀏覽下一個網頁的概率。那麼1-d 表示的就是瀏覽到一個網頁的時候，不通過網頁中的連結，而是額外新開了一個窗口隨機訪問其他網頁的概率。所以PageRank 認為訪問網頁，要麼是通過網頁中的連結點擊，要麼是隨機訪問。
有了這個阻尼係數d，原先圖中的情況就發生變化了，每個網頁，都有很多條隱形的邊，指向所有其他的網頁，這些隱形的邊表示的是隨機訪問不通過連結點擊。因此在計算A頁面在第n次，也就是狀態n的時候被訪問的概率公式就要發生變化了
物理意義也很好了解，原先從別的網頁通過連結點擊過來的是有一定概率的，概率就是d。而從任意一個網頁隨機訪問而來的概率是1/N，還要乘以1-d 。
因此
修改一下程序，再運行一下
最終四個網頁的權重再第五步的時候就收斂了，可以看到A網頁的權重是最高的，因為它被指向的連結是最多的。
我對 PageRank 算法的初步了解就這麼多了，我覺得PageRank 也應該算是馬爾科夫鏈的應用之一吧。