機器學習算法之隱馬爾可夫模型

2021-01-19 智能與算法之路


點擊上方「智能與算法之路」，選擇「星標」公眾號

資源乾貨，第一時間送達


今天為大家介紹的是隱馬爾可夫模型（Hidden Markov Model），隱馬爾可夫模型最初是在20世紀60年代後半期Leonard E. Baum和其它一些作者在一系列的統計學論文中描述的。HMM最初的應用之一是開始於20世紀70年代中期的語音識別。


隱馬爾可夫模型

簡單介紹

隱馬爾可夫模型是關於時序（順序）的概率模型，描述由一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀態隨機序列，再由各個狀態生成一個觀測而產生觀測隨機序列的過程。隱藏的馬爾可夫鏈隨機生成的狀態的序列，稱為狀態序列（state sequence);每個狀態生成一個觀測，而由此產生的觀測的隨機序列，稱為觀測序列（observation sequence)。序列的每一個位置又可以看作是一個時刻。


我們知道句子的表達不僅與其構成的詞語有關，還與詞的位置以及語法有關。因此對於語言來說，如果忽略語序進行理解，往往得不到句子正常的意思。（儘管如此，樸素貝葉斯在垃圾郵件分類上仍取得很好的效果）HMM在建立模型的時候可以考慮之前狀態對當前的影響。例如，我們要給以下句子做詞性標註

我(名詞)愛(動詞)學習(名詞/動詞？)

如果單獨去給『學習』這個詞標註的話，『學習』可能是名詞也可以是動詞。但在上面那句話裡『學習』顯然是名詞，因為學習前面的詞『愛』是動詞，後面應該接名詞，因此『學習』標註應該標註為名詞。這裡我們在標註的時候考慮前面詞語的詞性對當前詞的詞性的影響。HMM也是這樣去給詞語標註詞性的。只不過HMM是這麼看待以上問題，我 愛 學習 被看做長度為3的序列，這個序列為觀測序列。它們的詞性可以理解為詞語的某個狀態，由於我們現在是要給詞語做標註，因此我們是不知道每個觀測值（詞語）的狀態（詞性）的。並且我們知道句子的基本構成有主謂賓定狀補，詞語的詞性往往與該詞在句子充當的成分有關。例如謂語(愛)之後的詞(學習)很有可能名詞這麼一種轉態改變的規則。


用HMM的概念來說，我愛學習是觀測序列，詞語的詞性序列是一個狀態序列，詞性變化規則為狀態轉移矩陣（描述不同狀態相互轉換的概率）。在深入介紹隱馬爾可夫模型之前先引入一些基本概念。


馬爾可夫性

馬爾可夫性質是概率論中的一個概念。當一個隨機過程在給定現在狀態及所有過去狀態情況下，其未來狀態的條件概率分布僅依賴於當前狀態；換句話說，在給定現在狀態時，它與過去狀態（即該過程的歷史路徑）是條件獨立的，那麼此隨機過程即具有馬爾可夫性質。具有馬爾可夫性質的過程通常稱之為馬爾可夫過程。當前情況盡跟之前n個狀態有關的隨機過程稱為n階馬爾科夫過程。

例子

拿天氣和海藻的例子來說
假設海藻的溼度與天氣有某種關聯，為了簡易的去定義這個問題，定義海藻存在四種觀測值{dry,dryish,damo,soggy},天氣的狀態也只有三種狀態{sunny,cloudy,rainy}。
（這裡我們直接定義了觀測序列為一段時間內，海藻的溼度的一個序列，隱含狀態為同一段時間內，天氣的狀態序列，我們假設一個盲人只能通過觸摸判斷海藻溼度來推測天氣這麼一個情景）


在不同天氣下，觀測到海藻不同的溼度的概率是不同的

上面其實是一個觀測矩陣，表示在不同的隱含狀態下觀測到不同海藻溼度的概率，你會發現該矩陣每一行求和的結果都等於1。這個矩陣的數據是通過經驗獲得的，例如你統計了很多個晴天的狀態下，海藻有著不一樣的溼度，通過對大量數據的一個統計，我們就可以得到晴天狀態下，觀測到不同溼度的海藻的概率。


當然天氣之間也是存在互相轉化的，但令人頭疼的是，昨天的天氣或者更久以前的天氣會對今天的天氣有所影響，這樣考慮問題會使得問題變得格外複雜，因此隱馬爾可夫做了最基本的假設，即當前狀態只與前一個狀態有關（齊次馬爾可夫性假設）。同時也做觀測獨立性假設，所有的觀測之間是互相獨立的，某個觀測之和生成它的狀態有關係。

對應狀態轉移矩陣A




其中為狀態：i->j的概率，然後同樣你會發現每一行元素的求和等於1。

我們還需要序列的初始狀態π，這個初始狀態可以通過對多個樣本的初始狀態進行統計得出。


由此我們就已經定義了一個完整的隱馬爾可夫模型，該模型由觀測序列、狀態序列、以及初始狀態概率向量ππ、狀態轉移概率矩陣AA和觀測概率矩陣BB，其中後三個為隱馬爾可夫模型的參數一般用一個三元組表示。即

假設盲人連續記錄三天，得到觀察序列Q = {dry,damp,soggy},這三天的天氣為{sunny,cloudy,rainy}（儘管盲人無法觀測到，但可以通過馬爾可夫模型去估計這幾天的天氣）


隱馬爾可夫三個基本問題

概率計算問題：給定模型參數和觀測序列，計算出現某個觀測序列的概率

預測問題：給定模型參數和觀測序列，求最有可能的狀態序列

學習問題：給定觀測序列和狀態序列，得到模型參數


概率計算問題

給定模型參數和觀測序列計算觀測序列O的出現概率,直接計算即按照概率公式去計算。


如果直接去計算，通過列舉所有可能的長度為T的狀態序列I，求各個狀態序列I與觀測序列的聯合概率,然後對所有可能的狀態序列求和得到結果


對於給定的I序列,O,I同時出現的聯合概率為

然後，對所有可能的狀態序列I求和，得到觀測序列O的概率

利用上述公式計算量很大，因為所有可能的狀態序列有很多種，上述方法時間複雜度是的，這種算法在數據量大的情況下，是不可行的。因此我們用前向算法去計算其時間複雜度為。


前向算法

前向概率 ：給定隱馬爾可夫模型參數λ 定義時刻t部分觀測序列為

，且狀態為的概率為前向概率，記作

每次計算利用了前一時刻Ｎ個狀態下的,避免了重複計算

前向算法其實是以空間換時間的一種方法。具體的第一項的前向概率為

後面的項的前向概率為

因此得出

同理我們可以導出後向概率與後向算法

後向算法的從序列後面開始計算概率，最後一項的後項概率為

其餘項的後向概率表示為

得出

利用前向概率和後向概率的定義可以將概率統一寫成

此式當t = 1 和 t = T -1時，則分別寫為原來的形式


學習問題

監督學習問題

如果訓練數據包含S個長度的長度的觀測序列和對隱狀態序列那麼我們可以直接用極大似然估計隱馬爾可夫模型的參數其中

π̂ 為需要統計S個樣本中初始狀態為的概率。


監督學習需要大量的數據，而且人工標註訓練數據的代價往往很高，故有時就會利用非監督學習的方法。


baum-welch算法

baum-welch算法又稱 前向-後向算法，由baum和welch，算法的本質其實就是用EM算法去估計P(O|λ)P(O|λ)的概率分布對應隱馬爾可夫模型的參數。


確定完全數據的對數似然函數

E步，求Q函數

去掉對λ而言的常數因子

M步

注意到滿足約束條件 ，利用拉格朗日乘子法，對其求偏導並令結果為0，得

對i求和得到γ

代入得

類似的求出

以上式子還可以寫成

預測問題

近似算法

近似算法實際是一種貪心的方法，在每一步選擇概率最大的狀態值作為結果，但這樣得到的結果有可能不是最佳的預測結果，但是近似算法的計算量非常的小。


維特比算法

維特比算法其實用了動態規劃的方法求解HMM的解碼問題。但在小的篇幅中很難把動態規劃講得淺顯易懂。因此有興趣的朋友可以去《數學之美》一書中去了解維特比算法。

資料來源:

《統計學習方法》     李航

  以及網上各位大佬的博文

歡迎關注我們，收穫資源乾貨！

相關焦點

  • 【機器學習】隱馬爾可夫模型
    值得注意的是隱馬爾可夫模型中：即由此，馬爾科夫模型定義完成。至於為何這樣定義，隱狀態的意義是什麼，就是模型的價值所在，如何理解隱狀態也是一種個人體會。有了隱馬爾科夫模型，接下來看隱馬爾科夫模型能做什麼？
  • 隱馬爾可夫模型
    圖 2 隱馬爾可夫模型結構圖隱馬爾可夫模型是由初始概率分布、狀態轉移概率分布以及觀測概率分布確定。隱馬爾可夫模型由初始狀態概率向量π、狀態轉移概率矩陣 A 和觀測概率矩陣 B 決定。π和 A 決定了狀態序列，B 決定觀測序列。因此，隱馬爾可夫模型λ可以用三元符號表示，即：
  • 詳解隱馬爾可夫模型(HMM)
    它是典型的自然語言中處理標註問題的統計機器學模型，本文將重點介紹這種經典的機器學習模型。假設有三個不同的骰子(6面、4面、8面)，每次先從三個骰子裡面選擇一個，每個骰子選中的概率為1/3，如下圖所示，重複上述過程，得到一串數值[1,6,3,5,2,7]。這些可觀測變量組成可觀測狀態鏈。
  • 賽爾筆記 | 隱馬爾可夫模型
    說到隱馬爾可夫模型(HMM)，我們先來了解下馬爾可夫模型(Markov模型)，Markov模型是一種統計模型，廣泛地應用在語音識別，詞性自動標註，音字轉換，概率文法等各個自然語言處理的應用領域。一. 馬爾可夫模型(Markov模型)設是隨機變量序列，其中每個隨機變量的取值在有限集
  • 三張圖讀懂機器學習:基本概念、五大流派與九種常見算法
    四大會計師事務所之一的普華永道（PwC）近日發布了多份解讀機器學習基礎的圖表，其中介紹了機器學習的基本概念、原理、歷史、未來趨勢和一些常見的算法。為便於讀者閱讀，機器之心對這些圖表進行了編譯和拆分，分三大部分對這些內容進行了呈現，其中也加入了一些擴展連結，希望能幫助你進一步擴展閱讀。
  • 隱馬爾可夫模型攻略
    這就是本文重點介紹的隱馬爾可夫模型。　　隱馬爾可夫模型 (Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數，然後利用這些參數來作進一步的分析。
  • 隱馬爾可夫模型(HMM)攻略
    這就是本文重點介紹的隱馬爾可夫模型。隱馬爾可夫模型 (Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數，然後利用這些參數來作進一步的分析。
  • 隱馬爾可夫模型怎麼畫?3分鐘學會使用模型圖
    隱馬爾可夫模型既是一類非常有名的向圖模型，也可以用作有關時序的概率模型，又是一種典型的用於處理自然語言中標註問題的統計方面的機器學模型。馬爾可夫模型不斷推廣改進，截止目前已經推廣到了適用於更加複雜的數據結構與非穩定數據建模的兩兩馬爾可夫模型和三重態馬爾可夫模型。
  • 盤點| 機器學習入門算法:從線性模型到神經網絡
    原標題：盤點 | 機器學習入門算法：從線性模型到神經網絡 選自Dataconomy 機器之心編譯 參與：王宇欣、吳攀、蔣思源幾十年來，機器學習實際上已經變成了一門獨立的領域。由於現代計算能力的進步，我們最近才能夠真正大規模地利用機器學習。而實際上機器學習是如何工作的呢？答案很簡單：算法（algorithm）。 機器學習是人工智慧（artificial intelligence）的一種，其本質上講，就是計算機可以在無需編程的情況下自己學習概念（concept）。
  • 驚為天人,NumPy手寫全部主流機器學習模型,代碼超3萬行
    最近，來自普林斯頓的一位博士後將 NumPy 實現的所有機器學習模型全部開源，並提供了相應的論文和一些實現的測試效果。項目地址：https://github.com/ddbourgin/numpy-ml根據機器之心的粗略估計，該項目大約有 30 個主要機器學習模型，此外還有 15 個用於預處理和計算的小工具，全部.py 文件數量有 62 個之多。
  • 白白說算法:相親中的馬爾科夫模型
    按照未來網際網路的發展趨勢以及日趨激烈的人才競爭中，產品經理也須掌握基礎的技術算法。因此，本文以相親為例，介紹了什麼是馬爾科夫模型。大家好，我是白白，第一時刻來講講算法系列。產品經理是否需要懂技術，對於這個問題網際網路圈看法各不相同。
  • 本座選股談量化投資—隱馬爾可夫模型
    首先這篇文章是寫給沒有什麼基礎人士看的，目的是讓更多可能數學上有些障礙，但是又想要了解量化投資的朋友，無障礙的理解隱馬爾可夫模型框架。此文不適合追求嚴密邏輯和追求簡潔符號建立模型的數學大神。如果您是，請選擇性忽略。
  • 流行的機器學習算法總結,幫助你開啟機器學習算法學習之旅
    AI的ML領域是為實現非常精確的目標而創建的，它引入了多種算法，從而可以更順暢地進行數據處理和決策。什麼是機器學習算法？機器學習算法是任何模型背後的大腦，可讓機器學習並使其更智能。這些算法的工作方式是，為它們提供第一批數據，並且隨著時間的流逝和算法的準確性的提高，額外的數據也被引入到算法中。
  • 新手必看的十種機器學習算法
    然而，在眾多的機器學習算法中，哪些是又上手快捷又功能強大、適合新手學習的呢？Towards Data Science 上一篇文章就介紹了十種新手必看的機器學習算法，雷鋒網 AI 科技評論全文編譯如下。如果早就知道，我們就可以直接使用它，而不需要再通過機器學習算法從數據中進行學習了。最常見的機器學習就是學習 Y=f(X) 的映射，針對新的 X 預測 Y。這叫做預測建模或預測分析。我們的目標就是讓預測更加精確。針對希望對機器學習有個基本了解的新人來說，下面將介紹數據科學家們最常使用的 10 種機器學習算法。1.
  • 人工智慧機器學習三大類之回歸模型(RM)
    人工智慧機器學習三大類之回歸模型（RM） 工程師1 發表於 2018-07-13 01:39:00 人工智慧之機器學習主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點探討一下回歸模型（RM）。
  • 人工智慧研學社 · 入門組 | 《終極算法》研習第二期
    可以說，機器學習所代表的人工智慧，已經不再是一個新鮮的概念，科技、醫療、金融、安防，甚至政治、社會研究，都逐漸將這類強大的算法整合到自己的架構中去，以發揮更大的效能。在這樣的浪潮之下，了解人工智慧與機器學習，是每一個關心科技與社會發展的人必做的功課。然而，這並不是一個低門檻的領域，人工智慧也有其漫長的歷史和複雜的發展結構，想要了解事情的全貌，無法一蹴而就。
  • 算法應用|機器學習python應用,簡單機器學習項目實踐
    在選擇算法的過程中會採用統計學方法來評估算法模型。但是，我們更想知道算法模型對真實數據的準確度如何，這就是保留一部分數據來評估算法模型的主要原因。下面將按照70%的訓練數據集，30%的評估數據集來分離數據。
  • 入門| 機器學習新手必看10大算法
    如果我們知道的話，我們將會直接使用它，不需要用機器學習算法從數據中學習。 最常見的機器學習算法是學習映射 Y = f(X) 來預測新 X 的 Y。這叫做預測建模或預測分析，我們的目標是儘可能作出最準確的預測。 對於想了解機器學習基礎知識的新手，本文將概述數據科學家使用的 top 10 機器學習算法。
  • Python機器學習10:機器學習中的六種分類算法及實現(上)
    在機器學習中，可以使用多種算法模型解決同一個問題，那麼如何從中選擇出最佳的算法模型呢？當然，這個問題沒有一種固定的答案，需要根據不同的問題，嘗試使用多種機器學習方法，比較各種算法模型在該問題上的效果，最終才能決定究竟選擇哪一種模型。
  • Python機器學習7:如何保存、加載訓練好的機器學習模型
    本文將介紹如何使用scikit-learn機器學習庫保存Python機器學習模型、加載已經訓練好的模型。學會了這個，你才能夠用已有的模型做預測，而不需要每次都重新訓練模型。本文將使用兩種方法來實現模型的保存和加載：Pickle和joblib。