隱馬爾可夫模型（HMM）及Viterbi算法

HMM簡介

??對于算法愛好者來說，隱馬爾可夫模型的大名那是如雷貫耳。那么，這個模型到底長什么樣？具體的原理又是什么呢？有什么具體的應(yīng)用場景呢？本文將會解答這些疑惑。
??本文將通過具體形象的例子來引入該模型，并深入探究隱馬爾可夫模型及Viterbi算法，希望能對大家有所啟發(fā)。
??隱馬爾可夫模型（HMM，hidden Markov model）是可用于標(biāo)注問題的統(tǒng)計學(xué)模型，描述由隱藏的馬爾可夫鏈隨機(jī)生成觀測序列的過程，屬于生成模型。HMM模型在實際的生活和生產(chǎn)中有著廣泛的應(yīng)用，包括語音識別，自然語言處理，生物信息，模式識別等領(lǐng)域。

引入

??某天，你的女神告訴你說，她放假三天，將要去上海游玩，準(zhǔn)備去歡樂谷、迪士尼和外灘（不一定三個都會去）。
??她呢，會選擇在這三個地方中的某幾個逗留并決定是否購物，而且每天只待在一個地方。根據(jù)你對她的了解，知道她去哪個地方，僅取決于她去的上一個地方，且是否購物的概率僅取決于她去的地方。已知她去的三個地方的轉(zhuǎn)移概率表如下：

上個地方 歡樂谷 迪士尼 外灘
歡樂谷 0.8 0.05 0.15
迪士尼 0.2 0.6 0.3
外灘 0.2 0.3 0.5

稍微對這個表格做些說明，比如第一行，前一天去了歡樂谷后，第二天還待在歡樂谷的概率為0.8，去迪士尼的概率為0.05，去外灘的概率為0.15。
??她在每個地方的購物概率為：

地點 購物概率
歡樂谷 0.1
迪士尼 0.8
外灘 0.3

??在出發(fā)的時候，她跟你說去每個地方的可能性相同。后來，放假回來后，你看了她的朋友圈，發(fā)現(xiàn)她的購物情況如下：第一天不購物，第二三天都購物了。于是，你很好奇，她這三天都去了哪些地方。
??怎么樣，聰明的你能求解出來嗎？

HMM的模型參數(shù)

??接下來，我們將會介紹隱馬爾可夫模型（HMM）。
??隱馬爾可夫模型是關(guān)于時序的概率模型，描述由一個隱藏的馬爾可夫鏈隨機(jī)生成不可觀測的狀態(tài)隨機(jī)序列，再由各個狀態(tài)生成一個觀測而產(chǎn)生觀測隨機(jī)序列的過程。隱藏的馬爾可夫鏈隨機(jī)生成的狀態(tài)的序列，稱為狀態(tài)序列；每個狀態(tài)生成一個觀測，而由此產(chǎn)生的觀測的隨機(jī)序列，稱為觀測序列。序列的每一個位置又可以看作是一個時刻。
??隱馬爾可夫模型由初始概率分布、狀態(tài)轉(zhuǎn)移概率分布以及觀測概率分布確定。隱馬爾可夫模型的形式定義如下：
??設(shè)Q是所有可能的狀態(tài)的集合，V是所有可能的觀測的集合，也就是說，Q是不可見的，而V是可見的，是我們觀測到的可能結(jié)果。

q=\{q_1,q_2,...,q_N\}, V=\{v_1,v_2,...,v_M\}

其中，N是可能的狀態(tài)數(shù)，M是可能的觀測數(shù)。
??在剛才的例子中，Q是不可見的狀態(tài)集合，應(yīng)為Q=\{歡樂谷，迪士尼，外灘\}，而V是可以觀測的集合，應(yīng)為V=\{購物，不購物\}。
??I是長度為T的狀態(tài)序列，O是對應(yīng)的觀測序列。

I=(i_1,i_2,...,i_T), O=(o_1,o_2,...,o_T)

在剛才的例子中，I這個序列是我們需要求解的，即女生去了哪些地方，而O是你知道的序列，O=\{不購物，購物，購物\}。
??A是狀態(tài)轉(zhuǎn)移概率矩陣：

A=[a_{ij}]_{N\times N}
其中，a_{ij}=P(i_{t+1}=q_j|i_{t}=q_{i}), i=1,2,...,N; j=1,2,..,N是在時刻t處于狀態(tài)q_i的條件下在時刻t+1轉(zhuǎn)移到狀態(tài)q_j的概率。在剛才的例子中，轉(zhuǎn)移概率矩陣為：

A= \begin{bmatrix} {0.8}&{0.05}&{0.15}\\ {0.6}&{0.6}&{0.2}\\ {0.2}&{0.3}&{0.5}\\ \end{bmatrix}

??B是觀測概率矩陣：

B=[b_{j}(k)]_{N\times M}

其中，b_{j}(k)=P(o_t = v_{k}|i_{t}=q_{j}), k=1,2,...,M; j=1,2,...,N是在時刻t處于狀態(tài)q_{j}的條件下生成觀測v_{k}的概率。在剛才的例子中：

B= \begin{bmatrix} {0.1}&{0.9}\\ {0.8}&{0.2}\\ {0.3}&{0.7}\\ \end{bmatrix}

??\pi是初始狀態(tài)概率向量\pi=(\pi_i),其中\pi_i = P(i_1 = q_i), i=1,2,...,N是時刻t=1處于狀態(tài)q_{j}的概率。在剛才的例子中， \pi = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3}).
??綜上，我們已經(jīng)講完HMM中的基本概念。同時，我們可以知道，隱馬爾可夫模型由初始狀態(tài)概率向量\pi，狀態(tài)轉(zhuǎn)移概率矩陣A和觀測概率矩陣B決定。\pi和A決定狀態(tài)序列，B決定觀測序列。因此，隱馬爾可夫模型\lambda可用三元符號表示，即

\lambda = (A, B, \pi)

A,B,\pi稱為HMM的三要素。
??當(dāng)然，隱馬爾可夫模型之所以被稱為馬爾可夫模型，是因為它使用了兩個基本的假設(shè)，其中之一為馬爾可夫假設(shè)。它們分別是：

  1. 齊次馬爾科夫假設(shè)，即假設(shè)隱藏的馬爾可夫鏈在任意時刻t的狀態(tài)只依賴于其前一時刻的狀態(tài)，與其他時刻的狀態(tài)及觀測無關(guān)，也與時刻t無關(guān)。

P(i_{i}|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_{t}|i_{t-1}), t=1,2,...,T

  1. 觀測獨立性假設(shè)，即假設(shè)任意時刻的觀測只依賴于該時刻的馬爾可夫鏈的狀態(tài)，與其他觀測及狀態(tài)無關(guān)。

P(o_{i}|i_{T},o_{T},...,i_{t+1},o_{t+1},i_{t}, t_{t-1},o_{t-1},...,i_{1},o_{1})=P(o_{t}|i_{t}), t=1,2,...,T

??在剛才的假設(shè)中，我們對應(yīng)的兩個假設(shè)分別為：她去哪個地方，僅取決于她去的上一個地方；是否購物的概率僅取決于她去的地方。前一個條件為齊次馬爾科夫假設(shè)，后一個條件為觀測獨立性假設(shè)。
??以上，我們就介紹了HMM的基本概念及假設(shè)。而HMM的三個基本問題如下：

  1. 概率計算問題。給定模型\lambda=(A,B,\pi)和觀測序列O=(o_1,o_2,...,o_T),計算在模型\lambda下觀測序列O出現(xiàn)的概率P(O|\lambda).
  2. 學(xué)習(xí)問題。已知觀測序列O=(o_1,o_2,...,o_T)，估計模型\lambda=(A,B,\pi)參數(shù)，使得在該模型下觀測序列概率P(O|\lambda)最大。
  3. 預(yù)測問題。已知模型\lambda=(A,B,\pi)和觀測序列O=(o_1,o_2,...,o_T)，求對給定觀測序列條件概率P(I|O)最大的狀態(tài)序列I=(i_1,i_2,...,i_T).即給定觀測序列，求最有可能的對應(yīng)的狀態(tài)序列。

??上面的例子即為HMM的第三個基本問題，也就是，給定觀測序列{不購物，購物，購物}，結(jié)果最有可能的狀態(tài)序列，即游玩的地方。

Viterbi算法

??求解HMM的第三個基本問題，會用到大名鼎鼎的維特比算法（Viterbi Algorithm）。
??維特比算法以安德魯·維特比（Andrew Viterbi）命名，是現(xiàn)代數(shù)字通信中最常用的算法，同時也是很多自然語言處理采用的解碼算法?？梢院敛豢鋸埖刂v，維特比是對我們的生活影音力最大的科學(xué)家之一，因為基于CDMA的3G移動通信標(biāo)準(zhǔn)主要就是他和厄文·雅各布（Irwin Mark Jacobs）創(chuàng)辦的高通公司（Qualcomm）指定的。
??維特比算法是一個特殊但應(yīng)用最廣的動態(tài)規(guī)劃（dynamic programming）算法，利用動態(tài)規(guī)劃，可以解決任何一個圖中的最短路徑問題，同時，它也是求解HMM描述的第三個基本問題的算法。
??在維特比算法中，需要引入兩個變量\delta和\psi.定義在時刻t狀態(tài)i的所有單個路徑(i_1,i_2,...,i_t)中概率最大值為

\delta_{t+1}(i) = \max_{1\leq j \leq N}[\delta_{t}(j)a_{ji}]b_{i}(o_{t+1}), i=1,2,...,N; t=1,2,...,T.

定義在時刻t狀態(tài)為i的所有單個路徑(i_1,i_2,...,i_{t-1},i)中概率最大的路徑的第i-1個節(jié)點為

\psi_{t}(i) = arg \max_{1\leq j \leq N}[\delta_{t-1}(j)a_{ji}], i=1,2,...,N; t=1,2,...,T.

??下面是維特比算法在HMM的第三個基本問題的算法：

Python代碼實現(xiàn)

??下面，對于剛才給出的例子，我們將使用Python，來寫代碼實現(xiàn)Viterbi算法，同時求解剛才的問題。

# -*- coding: utf-8 -*-
# HMM.py
# Using Vertibi algorithm

import numpy as np

def Viterbi(A, B, PI, V, Q, obs):

    N = len(Q)
    T = len(obs)
    delta = np.array([[0] * N] * T, dtype=np.float64)
    phi = np.array([[0] * N] * T, dtype=np.int64)
    # 初始化
    for i in range(N):
        delta[0, i] = PI[i]*B[i][V.index(obs[0])]
        phi[0, i] = 0

    # 遞歸計算
    for i in range(1, T):
        for j in range(N):
            tmp = [delta[i-1, k]*A[k][j] for k in range(N)]
            delta[i,j] = max(tmp) * B[j][V.index(obs[i])]
            phi[i,j] = tmp.index(max(tmp))

    # 最終的概率及節(jié)點
    P = max(delta[T-1, :])
    I = int(np.argmax(delta[T-1, :]))

    # 最優(yōu)路徑path
    path = [I]
    for i in reversed(range(1, T)):
        end = path[-1]
        path.append(phi[i, end])

    hidden_states = [Q[i] for i in reversed(path)]

    return P, hidden_states


def main():

    # 狀態(tài)集合
    Q = ('歡樂谷', '迪士尼', '外灘')
    # 觀測集合
    V = ['購物', '不購物']
    # 轉(zhuǎn)移概率: Q -> Q
    A = [[0.8, 0.05, 0.15],
         [0.2, 0.6, 0.2],
         [0.2, 0.3, 0.5]
        ]

    # 發(fā)射概率, Q -> V
    B = [[0.1, 0.9],
         [0.8, 0.2],
         [0.3, 0.7]
         ]

    # 初始概率
    PI = [1/3, 1/3, 1/3]

    # 觀測序列
    obs = ['不購物', '購物', '購物']

    P, hidden_states = Viterbi(A,B,PI,V,Q,obs)
    print('最大的概率為: %.5f.'%P)
    print('隱藏序列為：%s.'%hidden_states)

main()

輸出結(jié)果如下：

最大的概率為: 0.02688.
隱藏序列為：['外灘', '迪士尼', '迪士尼'].

??現(xiàn)在，你有很大的把握可以確定，你的女神去了外灘和迪士尼。

?? 注意：本人現(xiàn)已開通微信公眾號： Python爬蟲與算法（微信號為：easy_web_scrape）， 歡迎大家關(guān)注哦~~

參考文獻(xiàn)

  1. 一文搞懂HMM（隱馬爾可夫模型）：https://www.cnblogs.com/skyme/p/4651331.html
  2. 李航《統(tǒng)計學(xué)習(xí)方法》 清華大學(xué)出版社
  3. HMM與分詞、詞性標(biāo)注、命名實體識別：http://www.hankcs.com/nlp/hmm-and-segmentation-tagging-named-entity-recognition.html
  4. Hidden Markov Models 1: http://docplayer.net/21306742-Hidden-markov-models-1.html
  5. 吳軍 《數(shù)學(xué)之美》 人民郵電出版社
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容