马尔可夫模型学习
1.??? 馬爾科夫模型
1.1馬爾可夫過程
?????? 馬爾可夫過程（Markov process）是一類隨機過程。它的原始模型馬爾可夫鏈，由俄國數學家A.A.馬爾可夫于1907年提出。該過程具有如下特性：在已知目前狀態（現在）的條件下，它未來的演變（將來）不依賴于它以往的演變 (過去 )。例如森林中動物頭數的變化構成——馬爾可夫過程。在現實世界中，有很多過程都是馬爾可夫過程，如液體中微粒所作的布朗運動、傳染病受感染的人數、車站的候車人數等，都可視為馬爾可夫過程。
在馬爾可夫性的定義中，"現在"是指固定的時刻，但實際問題中常需把馬爾可夫性中的“現在”這個時刻概念推廣為停時（見隨機過程）。例如考察從圓心出發的平面上的布朗運動，如果要研究首次到達圓周的時刻 τ以前的事件和以后的事件的條件獨立性，這里τ為停時，并且認為τ是“現在”。如果把“現在”推廣為停時情形的“現在”，在已知“現在”的條件下，“將來”與“過去”無關，這種特性就叫強馬爾可夫性。具有這種性質的馬爾可夫過程叫強馬爾可夫過程。在相當一段時間內，不少人認為馬爾可夫過程必然是強馬爾可夫過程。首次提出對強馬爾可夫性需要嚴格證明的是J.L.杜布。直到1956年，才有人找到馬爾可夫過程不是強馬爾可夫過程的例子。馬爾可夫過程理論的進一步發展表明，強馬爾可夫過程才是馬爾可夫過程真正研究的對象。
一個馬爾科夫過程就是指過程中的每個狀態的轉移只依賴于之前的 n個狀態，這個過程被稱為1個 n階的模型，其中 n是影響轉移狀態的數目。最簡單的馬爾科夫過程就是一階過程，每一個狀態的轉移只依賴于其之前的那一個狀態。
?
1.2馬爾可夫鏈
因安德烈·馬爾可夫（Andrey Markov，1856－1922）得名，是數學中具有馬爾可夫性質的離散時間隨機過程。該過程中，在給定當前知識或信息的情況下，過去（即當前以前的歷史狀態）對于預測將來（即當前以后的未來狀態）是無關的。這種性質叫做無后效性。
? ? ? ?時間和狀態都是離散的馬爾可夫過程稱為馬爾可夫鏈,簡記為Xn=X(n),n=0,1,2…
馬爾可夫鏈是隨機變量X1,X2,X3…的一個數列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態空間”，而Xn的值則是在時間n的狀態。如果Xn + 1對于過去狀態的條件概率分布僅是Xn的一個函數，則
這里為過程中的某個狀態。上面這個恒等式可以被看作是馬爾可夫性質。
? ? ? ??馬爾可夫在1906年首先做出了這類過程。而將此一般化到可數無限狀態空間是由柯爾莫果洛夫在1936年給出的。
? ? ? ? 馬爾可夫鏈的在很多應用中發揮了重要作用，例如，谷歌所使用的網頁排序算法（PageRank）就是由馬爾可夫鏈定義的
?
1.3馬爾可夫模型
??????馬爾可夫模型（Markov Model）是一種統計模型，廣泛應用在語音識別，詞性自動標注，音字轉換，概率文法等各個自然語言處理等應用領域。經過長期發展，尤其是在語音識別中的成功應用，使它成為一種通用的統計工具。到目前為止，它一直被認為是實現快速精確的語音識別系統的最成功的方法。
?
1.4實例——不確定的模式
?????? 介紹一個可以隨時間產生概率性模型的系統，天氣在晴天或者雨天或者多云之間變動。系統狀態之間轉移的概率是不確定的。
?????? 假設這個模型的每個狀態都只依賴于之前的狀態，這個假設被稱為馬爾科夫假設，這個假設可以大大的簡化這個問題。顯然，這個假設可能是一個非常糟糕的假設，導致很多重要的信息都丟失了。
下面這個圖展示了天氣這個例子中所有可能的一階轉移：
注意：一個含有M個狀態的一階過程有M的平方個狀態轉移。每一個轉移的概率叫做狀態轉移概率（state transition probability），就是從一個狀態轉移到另一個狀態的概率。這所有的M的平方個概率可以用一個狀態轉移矩陣來表示。注意這里有一個假設，概率不隨時間的變化而變化，這又是一個不現實但很重要的假設。
可知，上圖的狀態轉移矩陣為：
矩陣的意思是，如果昨天是晴天，那么今天又50%的可能是晴天，37.5%的概率是陰天，12.5%的概率會下雨，很明顯，每一行的和都是1。
為了初始化這樣一個系統，我們還需要一個初始的概率向量：
這個向量表示第一天是晴天。因此，一階馬爾科夫過程定義了以下三個部分：
- 狀態：晴天、陰天和下雨
- 初始向量：定義系統在時間為0的時候的狀態的概率
- 狀態轉移矩陣：每種天氣轉換的概率
所有的能被這樣描述的系統都是一個馬爾科夫過程。
1.5總結（Summary）
我們為了找到隨時間變化的模式，就試圖去建立一個可以產生模式的過程模型。我們使用了具體的時間步驟、狀態、并且做了馬爾科夫假設。有了這些假設，這個能產生模式系統就是一個馬爾科夫過程。一個馬爾科夫過程包括一個初始向量和一個狀態轉移矩陣。關于這個假設需要注意的一點是狀態轉移概率不隨時間變化。
?
2.??? 隱馬爾科夫模型
2.1??? 實例引入——隱含模式
在某些情況下馬爾科夫過程不足以描述我們希望發現的模式。回到之前那個天氣的例子，一個隱居的人可能不能直觀的觀察到天氣的情況，但是有一些海藻。民間的傳說告訴我們海藻的狀態在某種概率上是和天氣的情況相關的。在這種情況下我們有兩個狀態集合，一個可以觀察到的狀態集合（海藻的狀態）和一個隱藏的狀態（天氣的狀況）。我們希望能找到一個算法可以根據海藻的狀況和馬爾科夫假設來預測天氣的狀況。
其中，隱藏狀態的數目和可以觀察到的狀態的數目可能是不一樣的。在語音識別中，一個簡單的發言也許只需要80個語素來描述，但是一個內部的發音機制可以產生不到80或者超過80種不同的聲音。同理，在一個有三種狀態的天氣系統（sunny、cloudy、rainy）中，也許可以觀察到四種潮濕程度的海藻（dry、dryish、damp、soggy）。在此情況下，可以觀察到的狀態序列和隱藏的狀態序列是概率相關的。于是我們可以將這種類型的過程建模為一個隱藏的馬爾科夫過程和一個和這個馬爾科夫過程概率相關的并且可以觀察到的狀態集合。
下圖顯示了天氣的例子中隱藏的狀態和可以觀察到的狀態之間的關系。我們假設隱藏的狀態是一個簡單的一階馬爾科夫過程，并且他們兩兩之間都可以相互轉換。
下圖則明確的表示出模型的演化，其中綠色的圓圈表示隱藏狀態，紫色圓圈表示可觀察到狀態，箭頭表示狀態之間的依存概率。一個?HMM?可用一個5元組?{ N, M, π，A，B?}表示，其中 N 表示隱藏狀態的數量，我們要么知道確切的值，要么猜測該值，M 表示可觀測狀態的數量，可以通過訓練集獲得，?π={πi}為初始狀態概率，A={aij}為隱藏狀態的轉移矩陣?Pr(xt(i)?| xt-1(j))，B={bik} 表示某個時刻因隱藏狀態而可觀察的狀態的概率，即混淆矩陣，Pr(ot(i)?| xt(j))。在狀態轉移矩陣和混淆矩陣中的每個概率都是時間無關的，即當系統演化時，這些矩陣并不隨時間改變。對于一個 N 和 M 固的?HMM?來說，用λ={ π,A,?B?} 表示?HMM?參數。
隱藏的狀態和可以觀察到的狀態之間有一種概率上的關系，也就是說某種隱藏狀態H被認為是某個可以觀察的狀態O1是有概率的，假設為P（O1|H）。如果可以觀察的狀態有三種，那么很顯然P（O1|H）+?P（O2|H）+?P（O3|H）?=1。
這樣，我們也可以得到一個另一個矩陣，稱為混淆矩陣。這個矩陣的內容是某個隱藏的狀態被分別觀察成集中不同的可以觀察的狀態的概率，在天氣的例子中，這個矩陣如下圖：
注意到圖中每一行的和為1，但是每一列的和不為1，這里我覺得可能是原文出錯了，或者隱藏狀態還有其他。
總結
我們已經看到有一些過程是和一個隱藏的馬爾科夫過程概率相關的。在這種情況下，可以觀察到的狀態和隱藏的狀態的數目可能是不一樣的。我們可以把這種過程建模為隱馬爾科夫模型（HMM）。這個模型包含兩個狀態集合和三個概率集合。
- 隱藏的狀態：狀態變量，一個隱藏的馬爾科夫過程
- 可以觀察到的狀態：觀測值
- 初始狀態概率（向量）：模型在初始時刻各狀態出現的概率
- 狀態轉移概率（矩陣）：模型在各個狀態間轉換的概率
- 輸出觀測概率（混淆矩陣）：模型根據當前狀態獲得各個觀測值的概率
我們可以認為隱馬爾科夫模型是在一個不可觀察的馬爾科夫過程上添加了一個可以觀察到的狀態集合，加上這個過程到這個集合的一些概率關系得到的。
2.2 隱馬爾科夫模型
隱馬爾可夫模型?(Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。它是結構最簡單的動態貝葉斯網，這是一種著名的有向圖模型，主要用于時序數據建模，在語音識別、自然語言處理等領域有廣泛應用。
定義：隱馬爾科夫模型可以用一個三元組來定義：
(1)???初始狀態概率向量：通常記為，其中，表示模型的初始狀態為的概率。
(2)???狀態轉移概率矩陣：模型在各個狀態間轉換的概率，通常記為，其中
?，表示在任意時刻t，狀態為，下一時刻為狀態為的概率。
(3)???輸出觀測概率矩陣：模型根據當前狀態獲得各個觀測值的概率，,其中
，表示在任意時刻t，若狀態為，則觀測值被獲取的概率。
值得注意的是，在狀態轉移矩陣中的每個概率都是時間無關的，也就是說我們假設這個概率是固定的，不隨時間變化。
?
2.3 隱馬爾科夫模型的三個基本問題
(1)???給定模型，如何有效計算產生觀測序列的概率？換言之，如何評估模型與觀測序列之間的匹配程度？
(2)???給定模型和觀測序列，如何找到與此觀測序列最匹配的狀態序列？換言之，如何根據觀測序列推斷出隱藏的模型狀態？
(3)???給定觀測序列，如何調整模型參數使得該序列出現的概率最大？換言之，如何訓練模型使其能最好地描述觀測數據？
前兩個問題模式識別的問題：1) 根據隱馬爾科夫模型得到一個可觀察狀態序列的概率(評價)；2) 找到一個隱藏狀態的序列使得這個序列產生一個可觀察狀態序列的概率最大(解碼)。第三個問題就是根據一個可以觀察到的狀態序列集產生一個隱馬爾科夫模型（學習）。
上述為題在現實應用中非常重要。例如許多任務需根據以往的觀測序列來推測當前時刻最有可能的觀測值?,這顯然可轉化為求取概率，即上述第一個問題。在語音識別等任務中，觀測值為語音信號，隱藏的狀態為文字，目標就是根據觀測信號來推斷最優可能的狀態序列(即對應的文字)，即上述第二個問題。在大多數現實應用中，人工指定的模型參數已變得越來越不可用，如何根據訓練樣本學得最優的模型參數，恰是上述第三個問題。
2.3.1評價
假設我們有很多隱馬爾科夫模型（也就是說一個三元組的集合）描述不同的系統和一個可觀察狀態序列集。我們也許想知道哪一個隱馬爾科夫模型最可能產生某個可觀察狀態序列。比如說，我們也許有一個海藻的“Summer”模型和一個“Winter”模型，因為海藻在夏天和冬天的狀態應該是不同的，我們希望根據一個可觀察狀態（海藻的潮濕與否）序列來判斷現在是夏天還是冬天。
我們可以使用前向算法來計算在某個特定的HMM下一個可觀察序列的概率，然后據此找到最可能的模型。
這種類型的應用通常出現在語音設別中，通常我們會使用很多HMM，每一個針對一個特別的單詞。一個可觀察狀態的序列是從一個可以聽到的單詞向前得到的，然后這個單詞就可以通過找到滿足這個可觀察狀態序列的最大概率的HMM來識別。
2.3.2 解碼
根據可觀察狀態的序列找到一個最可能的隱藏狀態序列。
和上面一個問題相似的并且更有趣的是根據可觀察序列找到隱藏序列。在很多情況下，我們對隱藏狀態更有興趣，因為其包含了一些不能被直接觀察到的有價值的信息。比如說在海藻和天氣的例子中，一個隱居的人只能看到海藻的狀態，但是他想知道天氣的狀態。這時候我們就可以使用Viterbi算法來根據可觀察序列得到最優可能的隱藏狀態的序列，當然前提是已經有一個HMM。
另一個廣泛使用Viterbi算法的領域是自然語言處中標引詞性。
句子中的單詞是可以觀察到的，詞性是隱藏的狀態。通過根據語句的上下文找到一句話中的單詞序列的最有可能的隱藏狀態序列，我們就可以得到一個單詞的詞性（可能性大）。這樣我們就可以用這種信息來完成其他一些工作。
2.3.3 學習
從一個觀察集中得到一個隱馬爾科夫模型。
第三個問題也是最困難的問題，根據觀察到的序列集來找到一個最有可能的HMM，也就是說確定一個最有可能的三元組(π,A,B）。當A，B矩陣都不是直觀可測量（通過經驗得到）的的時候，可以使用前向后向算法(Baum-Welch 算法)來解決這個問題。
總結
盡管做出了一些不太符合實際的假設，但是用三元組描述的HMMs在描述真實系統并進行分析的時候具有很大的價值，并且可以解決下面這些問題：
參考文獻：
1.?????? 周志華. 機器學習(Machine Learning). 北京:清華大學出版社.
?
總結
- 上一篇： CocosBuilder学习之一：认识C
- 下一篇： Sessions, Window Sta