馬可夫鏈與人工智慧

人工智慧

前言

簡介

知識表達

知識學習

理論方法

搜尋優化

邏輯推論

神經網路

機率統計

實務應用

專家系統

自然語言

分群分類

程式語言

Prolog

javascript

程式實作

邏輯推論

爬山算法

基因算法

機率學習

交談程式

數字辨識

訊息

相關網站

參考文獻

最新修改

簡體版

English

馬可夫鏈

馬可夫鏈是一種具有狀態的隨機過程，從目前狀態轉移 s 到下一個狀態 s' 的機率由 $q(s \rightarrow s')$ (或者 $P(s' | s)$) 所表示，這個狀態之轉移機率並不會受到狀態以外的因素所影響，因此與時間無關。

隨機漫步就是馬可夫鏈的例子。隨機漫步中每一步的狀態是在圖形中的點，每一步可以移動到任何一個相鄰的點，在這裡移動到每一個點的概率都是相同的(無論之前漫步路徑是如何的)。

假如我們不斷的觀察某種隨機現象，會看到許多一連串的觀察值 $x_1, x_2,..., x_n$ ，這些觀察值會形成整個隨機現象空間 $X_1, X_2,..., X_n$ 。

假如這些觀察值之間有某種因果關係，那麼我們就有可能透過馬可夫過程描述此因果關係，舉例而言，如果每個事件只受到前一個事件的影響，那麼就可以用 $P(X_{n+1} | X_n)$ 表示此隨機現象，這種隨機過程稱為時間無關的馬可夫鏈 (Time-homogeneous Markov chains, 或稱為穩定型馬可夫鏈 stationary Markov chains)。

假如下一個觀察值可能受前 m 個觀察值所影響，那麼此種隨機過程可由機率分布 $P(X_{n+1} | X_n, ..., X_{n-m+1})$ 表示，因此稱為 m 階的馬可夫過程。

然而，對於某個機率現象而言，往往不是所有的隨機變數都可觀察到，我們通常只能觀察到部分的隨機變數，也就是系統當中有某些不可觀察的隱含變數。於是我們必須假設有某些不可觀察的隨機變數 Z 的存在。

隱馬可夫模型

隱馬可夫模型 (Hidden Markov Model，HMM) 是用來描述具有隱含變數的隨機過程模型，此模型在人工智慧的許多子領域有很強的應用。

在正常的馬可夫模型中，狀態對於觀察者來說是直接可見的。這樣狀態的轉換概率便是全部的參數。而在隱馬可夫模型中,狀態並不是直接可見的，但受狀態影響的某些變數則是可見的。每一個狀態在可能輸出的符號上都有一概率分佈。因此輸出符號的序列能夠透露出狀態序列的一些資訊。

下圖顯示了 HMM 模型的概念，其中的 X 是隱含變數，Y 是可觀察變數，a 是轉換機率 (transition probabilities)，b 是輸出概率 (output probabilities)。

Hmm1.png

如果將狀態轉換與輸出區分開來，上圖的連線可以進一步詳細區分為輸出線與轉換線，形成下列模型。

Hmm3.png

如果以時間順序為觀察重點，則 HMM 模型可以用下列圖形表示。其中隱含變數 $X_{n}$ 是決定狀態的關鍵，影響了輸出變數 $Y_{n}$ 與下一個狀態 $X_{n+1}$。

Hmm2.png

對於 HMM 模型而言，有三個重要的問題，都有對應的演算法可用。

1. 針對已知的模型，計算某一特定輸出序列的概率：可使用 Forward Algorithm 或 Backward Algorithm 解決.
2. 針對已知的模型，尋找最可能的能產生某一特定輸出序列的隱含狀態的序列：可以使用 Viterbi Algorithm 解決.
3. 針對某輸出序列，尋找最可能的狀態轉移以及輸出概率：通常使用最大可能性法則 (Maximum Likelihood) 的演算法，像是 Baum-Welch algorithm (又稱為 Forward-backward Algorithm) 解決，此種演算法是 EM 演算法的一種特例。

蒙地卡羅演算法

利用亂數隨機抽樣的方式以計算某種解答的演算法，被稱為蒙地卡羅演算法，其中最簡單的方法是直接取樣算法。

舉例而言，假如我們不知道半徑為 1 的圓形面積，那麼就可以利用亂數隨機取樣 1百萬個 X=random[-1…1], Y=random[-1…1] 之間的的值，然後看看有多少點落在 $x^2 + y^2 <=1$ 的範圍之內 P(in circle)。最後利用 4 * P(in circle) 就可以計算出該圓形的面積。

蒙地卡羅法除了用來計算某些曲線或形狀的面積，也可以用來逼近某些聯合隨機變數 $P(x_1, ..., x_n)$ ，像是利用 Gibbs Sampling 程序計算條件獨立下的聯合分布情況，或者利用 Metropolis Hasting 程序計算貝氏網路當中聯合機率分布的值。

Gibbs 取樣程序 (Gibbs Sampling)

Gibbs 取樣程序的使用時機是在聯合分布 $P(X,Y)$ 未知，但是單一變數的條件機率 $P(X|Y), P(Y|X), P(X), P(Y)$ 已知的情況。在此種情況下，我們可以利用亂數產生的樣本，統計聯合機率分布。

該程序首先取得一個樣本 y0 作為初始值，然後利用蒙地卡羅法透過 (X, y0) 產生新樣本 x1，接著再利用 (x1, Y) 產生 y1。於是我們得到下列這個疊代程序

Algorithm GibbsSampling(X, Y)
　$y_0$ = generate sample from P(Y)
　for i = 1 to N
　　$x_i$ = generate sample from $P(X | y_{i-1})$
　　$y_i$ = generate sample from $P(Y | x_i)$
　calculate P(X,Y)
End Algorithm

以上疊代程序是針對兩個隨機變數的情況，假如我們希望延伸到 k 個隨機變數的情況，可以修改演算法如下。

Algorithm GibbsSampling($X_1, ...,X_k$)
　$y_0$ = generate sample from P(Y)
　for i = 1 to N
　　j = random(1..k)
　　$x_j$ = generate sample from $P(X_i | X_1, ..., X_{j-1}, X_{j+1},...,X_k)$
　calculate $P(X_1, ...,X_k)$
End Algorithm

Gibbs 取樣程序是『蒙地卡羅馬可夫算法』(MCMC) 的一個案例，也是 Metropolis-Hasting 取樣程序的一個特例，我們可以利用Metropolis-Hasting 取樣程序計算貝氏網路的聯合機率分布。

Metropolis-Hasting 取樣程序 (Metropolis Hasting Sampling)

Metropolis Hasting (MH) 程序的假設是具有馬可夫性質的，也就是前一個狀態可以完全決定下一個狀態的機率分布，而不受更先前的狀態影響。

早期的 MH 程序是利用一個對稱性的 Q(x;y) = Q(y;x) 函數，作為疊代程序執行的基礎。利用 $Q(x' ; x^t)$ 導出 $x^{t+1}$，然後再利用 $Q(x^{t+1} ; x')$ 導出 $x^{t+2}$，如此不斷進行，以便取得較好的機率分布之方法。

較新的 MH 程序不再強制要求 Q(x;y) = Q(y;x) 這個條件，而是利用其比值 $\frac{Q(x ; y)}{Q(y ; x)}$ 作為疊代的基礎，我們假設 $a_1 = \frac{P(x')}{P(x^t)}$, $a_2 = \frac{Q(x' ; x^t)}{Q(x^t ; x')}$ ，那麼，我們就可以透過下列疊代程序產生適當的機率樣本，並以這些樣本序列做為 MCMC 蒙地卡羅馬可夫程序的統計基礎。

Algorithm Metropolis-Hasting($X$)
　$y_0$ = generate sample from P(Y)
　for t = 1 to N
　　$a = \frac{P(x')}{P(x^t)}*\frac{Q(x' ; x^t)}{Q(x^t ; x')}$
　　if a >= 1
　　　　$x^{t+1} = x'$
　　else
　　　　if random(0..1) < a
　　　　　　$x^{t+1}= x'$
　　　　else
　　　　　　$x^{t+1}= x^t$
　　end if
　End for
End Algorithm

貝氏網路 (Bayesian Network)

貝氏網路是用來描述機率因果關係的網路，對於一個已知的貝氏網路 (Bayesian Network)，其中的某個樣本 $(x_1, ..., x_n)$ 的機率可以用下列算式表示

(1)
\begin{align} P(x_1, ..., x_n) = \prod_{i=1}^{n} P(x_i | parent(X_i)) \end{align}

貝氏網路也可以被視為某種隱馬可夫模型，其中某些節點是可觀察節點 (X)，某些節點是隱含節點 (Z) ，我們可以透過蒙地卡羅馬可夫算法計算某個分布 $P(x_1, ..., x_n)$ 的機率值。

蒙地卡羅馬可夫算法

蒙地卡羅馬可夫演算法 (Markov Chain Monte Carlo) 簡稱 MCMC 法，此方法透過對前一事件進行隨機改變而產生事件樣本，其演算法如下所示。

Algorithm MCMC-Ask(X,e,bn, N) returns an estimate of P(X|e)
  local variables : N[X], a vector of counts over X, initially zero
                            Z, the nonevidence variables in bn
                            x, the current state of the network, initially copied from e.
  initialize x with random values for the variable for the variables in Z
  for j=1 to N do
      N[x] = N[x] + 1 where x is the value of X in x
      for each Zi in Z do
         sample the value of Zi in x from P(Zi | mb(Zi)) given the value of MB(Zi) in X
  return Normalize(N[X])

授權說明

本文之部分來源為維基百科，修改使用時請遵照 Creative Commons Attribution-ShareAlike 授權條款。

參考文獻

  1. 維基百科編者. 隱馬爾可夫模型[G/OL]. 維基百科，自由的百科全書, http://zh.wikipedia.org/w/index.php?title=%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8B&oldid=11012460, 2009年08月28日15:47 [2009年12月21日06:42].
  2. Hidden Markov model. (2009, December 20). In Wikipedia, The Free Encyclopedia. Retrieved 06:43, December 21, 2009, from http://en.wikipedia.org/w/index.php?title=Hidden_Markov_model&oldid=332893255
  3. http://www.shokhirev.com/nikolai/abc/alg/hmm/hmm.html
  4. The Markov Chain Monte Carlo Revolution (pdf)

Facebook
page revision: 38, last edited: 23 Aug 2010 00:27
Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License