轉移矩陣的穩定狀態與Google搜尋引擎

轉移矩陣的穩定狀態與Google搜尋引擎 (The Stationary of a Transition Matrix, and Google Search)
國立臺南第一高級中學數學科林倉億老師

若 \(n\) 階方陣 \(M = {\left[ {{a_{i{\kern 1pt} j}}} \right]_{\;n \times n}}\) 滿足：

                         (1) 每個 \(a_{ij}\) 都滿足 \(0\leq a_{ij}\leq 1\) ；

                         (2) 每行的各元之和為1。

我們就稱 \(M\) 為「 \(n\) 階轉移矩陣」，簡稱為「轉移矩陣」。

多找幾個轉移矩陣來試試，就會發現有些矩陣不管初始狀態 \(X_0\) 為何，隨著 \(n\) 越來越大，

\(M^nX\) 就會越來越趨近於某個 \(X\)。

例如在本網站〈轉移矩陣〉一文中的例子，\(M = \left[ {\begin{array}{*{20}{c}} {\frac{4}{5}}&{\frac{3}{5}}\\ {\frac{1}{5}}&{\frac{2}{5}} \end{array}} \right]\)，\({X_0} = \left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\)，

\(M^nX_0\) 會越來越趨近於 \(X = \left[ {\begin{array}{*{20}{c}} {\frac{3}{4}}\\ {\frac{1}{4}} \end{array}} \right]\)，我們稱之為「穩定狀態」。

但有些轉移矩陣可不是這樣子的，比如說當  \(M = \left[ {\begin{array}{*{20}{c}} 0&1\\ 1&0 \end{array}} \right]\) 時，

只要初始狀態不是 \(\left[ {\begin{array}{*{20}{c}} {\frac{1}{2}}\\ {\frac{1}{2}} \end{array}} \right]\) ，比如說 \({X_0} = \left[ {\begin{array}{*{20}{c}} {\frac{1}{3}}\\ {\frac{2}{3}} \end{array}} \right]\)，

乘下去就會發現 \(M^nX\) 的值就永遠在 \(\left[ {\begin{array}{*{20}{c}} {\frac{1}{3}}\\ {\frac{2}{3}} \end{array}} \right]\) 與 \(\left[ {\begin{array}{*{20}{c}} {\frac{2}{3}}\\ {\frac{1}{3}} \end{array}} \right]\) 兩者間跳來跳去，永遠不會穩定下來。

因此，我們必須給「穩定狀態」一個明確的定義：

 \(M\) 為轉移矩陣，無論初始狀態 \(X_0\) 為何，

當 \(n\) 越來越大時， \(M^nX\) 會越來越趨近於某一個 \(X\) ，

我們就稱 \(X\) 為轉移矩陣 \(M\) 的「穩定狀態」。

搞清楚什麼是「穩定狀態」後，我們就可以看看轉移矩陣跟時下的科技巨擘Google有何淵源。

我們還是先從一個簡單的例子談起。現在有 \(A,B,C\) 三個網頁，假設：

\(A\) 網頁中有3個連結，有1個連結連往 \(B\) 網頁，另2個連往 \(C\) 網頁。
也就是說，在 \(A\) 網頁的使用者，當他隨機離開 \(A\) 前往下一個網頁時，
有 \(\frac{1}{3}\) 的機率會前往 \(B\) 網頁，有 \(\frac{2}{3}\) 的機率會前往 \(C\) 網頁；

\(B\) 網頁中有4個連結，有1個連結連往 \(A\) 網頁，另3個連往 \(C\) 網頁。
也就是說，在 \(B\) 網頁的使用者，當他隨機離開 \(B\) 前往下一個網頁時，
有 \(\frac{1}{4}\) 的機率會前往 \(A\) 網頁，有 \(\frac{3}{4}\) 的機率會前往 \(C\) 網頁；

\(C\) 網頁中有2個連結，有1個連結連往 \(A\) 網頁，另1個連往 \(B\) 網頁。
也就是說，在 \(C\) 網頁的使用者，當他隨機離開 \(C\) 前往下一個網頁時，
前往 \(A,B\) 網頁的機率都是 \(\frac{1}{2}\)。

倘若利用Google搜尋某個關鍵字後，發現就只有 \(A,B,C\) 這三個網頁符合，請問要將哪一個網頁排在最前面？

上述這個問題其實就是網頁的排序問題，也就是我們搜尋到的網頁，該以何種方式排序會比較「好」、比較「合理」。直觀的回答是：越重要的排越前面，或是越有用的排越前面。這回答沒錯，但問題就是如何要電腦程式去判斷什麼叫做「重要」、「有用」，就算是用人腦好了，每個人對「重要」、「有用」的標準也不會完全一致，更不用說我們要判斷的是數十萬、數百萬個網頁！

因此，我們就需要一個方式來排序，而這方式必須簡單到讓電腦可以在短時間內運算出來。Google採取的方式，就是依據網頁的連結情形來計算。我們將網路使用者在上述 \(A,B,C\) 三個網頁的隨機行為模式（隨機前往下一個網頁）用矩陣表示出來，

就得到轉移矩陣 \(M = \left[ {\begin{array}{*{20}{c}} 0&{\frac{1}{4}}&{\frac{1}{2}}\\ {\frac{1}{3}}&0&{\frac{1}{2}}\\ {\frac{2}{3}}&{\frac{3}{4}}&0 \end{array}} \right]\) ，接下來求出 \(M\) 的穩定狀態：

\(\left[ {\begin{array}{*{20}{c}} 0&{\frac{1}{4}}&{\frac{1}{2}}\\ {\frac{1}{3}}&0&{\frac{1}{2}}\\ {\frac{2}{3}}&{\frac{3}{4}}&0 \end{array}} \right] \cdot \left[ {\begin{array}{*{20}{c}} x\\ y\\ z \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} x\\ y\\ z \end{array}} \right]\;\; \Rightarrow \;\;\left[ {\begin{array}{*{20}{c}} {\frac{1}{4}y + \frac{1}{2}z}\\ {\frac{1}{3}x + \frac{1}{2}z}\\ {\frac{2}{3}x + \frac{3}{4}y} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} x\\ y\\ z \end{array}} \right]\)，

又 \(x+y+z=1\) ，可得 \(\left\{ \begin{array}{l} x + y + z = 1\\ x – \frac{1}{4}y – \frac{1}{2}z = 0\\ \frac{1}{3}x – y + \frac{1}{2}z = 0 \end{array} \right.\;\; \Rightarrow \;\;\left\{ \begin{array}{l} x = \frac{{15}}{{53}}\\ y = \frac{{16}}{{53}}\\ z = \frac{{21}}{{53}} \end{array} \right.\)

也就是說，當有一群人隨機在 \(A,B,C\) 這三個網頁中隨機連來連去時，

在一段時間之後，停留在 \(A,B,C\) 這三個網頁的比例大概就是 \(\frac{15}{53},\frac{16}{53},\frac{21}{53}\)。

這個比例可以當作網頁排序的指標，依據這個指標，我們要將 \(C\) 網頁排在最前面，接下來才是 \(B\) 和 \(A\) 。這就是Google搜尋引擎所採用的排序方式。

當然啦，Google搜尋引擎的計算模式比上述的例子複雜太多太多了，不然它也不會那麼值錢，讓兩位創辦人都成為億萬富豪。不過，Google搜尋引擎最原始的概念其實就來自轉移矩陣的穩定狀態，然後再發展出他們獨特的計算法則。

接下來讀者或許會問，既然轉移矩陣不一定會有穩定狀態，那遇到這種情況的話，該如何排序網頁呢？這問題的回答必須牽涉到更多Google搜尋的計算法則，也會觸及更多、更高深的數學，我們在此不再深入下去了。有興趣的的讀者，上網Google一下吧！不過，在此有必要點出一個定理，那就是轉移矩陣有沒有穩定狀態的判別定理：

\(M\) 是轉移矩陣，若 \(M\) 或 \(M\) 的某個次方的所有元都是正數，則 \(M\) 會有穩定狀態。

這個定理的說明與證明都必須使用到更高深的理論，也只好請有興趣的讀者自行找線性代數的書籍來看。