統計學習方法；機器學習；隐馬爾可夫模型
今天是2020年3月13日星期五。不知不覺已經在家待了這麼多天了，從上一節EM算法開始，數學推導越來越多，用mathtype碼公式真的是太漫長了。本來該筆記是打算把《統計學習方法》這本書做詳細的解讀，起初面對書裡大量的數學推導，感到非常恐懼。假期“空窗”時間不少，才有了細嚼慢咽學習的機會。其實很大的原因是自己掌握的東西太少，知道的算法太少，是以才對這本書恐懼。買了一直放着不願意學。現在到隐馬爾可夫模型，再有一章條件随機場，監督學習部分就結束了。這一個月來，最大的收獲是知道了“怎麼學”。
新的章節抛出一個新的算法模型，往往丈二和尚摸不着頭腦，什麼都是新的。越是拖延進度越慢，更不能一口吃個胖子指望看一遍就能懂。書讀百遍，其意自見，一遍不懂就再看一遍，一遍有一遍的收獲。但這個過程千萬不要盯着一本書看，一定要多找部落格，多看知乎、CSDN，保持審視的态度，保留自己的見解。另外，我是喜歡直接看文字，實在不懂了才去翻視訊看，覺得這種模式挺适合我。
學到第十章，發現書中的很多東西，沒必要面面俱到，要适當的取舍和放過。因為畢竟這本書不是一次性消耗品，是值得深究和研習的。第一次不懂的東西，完全可以學習完所有章節，建立大的思維格局後，再重新考慮小細節。
接下來的所有章節，從例子出發，引入各個概念；手寫推導過程；圖解算法流程；最後實作代碼。掰扯開來，其實也就是三個問題：該模型是什麼樣子的（考慮如何引入）；該模型為什麼可以這樣做（考慮如何了解推導過程）；該模型怎麼應用（考慮代碼實作和應用場景）。
GitHub：https://github.com/wangzycloud/statistical-learning-method
隐馬爾科夫模型
引入
隐馬爾科夫模型描述由隐藏的馬爾可夫鍊随機生成觀測序列的過程，屬于生成模型。把這句話倒着思考一下：(1)該模型屬于生成模型，會不會類似EM算法中考慮的，一個觀測資料y的生成，中間需要經過一個隐藏狀态z。(2)很明顯這裡生成的不是單個資料，而是單個資料構成的一個序列，并存在時序關系。（3）馬爾可夫鍊是什麼？在生成資料序列的過程中扮演什麼角色？
先區分兩個概念，“狀态and觀測”。在我的了解裡，“狀态”也好，“觀測”也罷，不過是表達随機變量的一個說法。狀态會有多個狀态，觀測會有多個觀測，但同時隻允許一個狀态或者一個觀測出現。例如，現在有四個盒子（灰、黃、綠、藍），李華在五天内選盒子取球，規定每天隻能取一個盒子（每個盒子被選的機率一樣大）。問，李華這五天可能會有多少種取盒子的序列，并問取到某種序列的機率是多少？如下：
你知道的，這個組合數不小。因為每個盒子被選到的機率一樣大，是以每個序列出現的機率相同。李華每天在盒子裡取球（紅、白），現在限制每個盒子紅球、白球數目相同(紅、白球各有五個)。問，李華五天内取到球的顔色的序列有多少種，并問取到某種序列的機率是多少？
顯然，這個組合數要小一些。因為每個盒子中紅白球數目相同，且此時盒子的選擇（狀态）對球的選取無影響，是以每個序列出現的機率相同。可是如果每個盒子中，紅白球的數量不是五五開，各不相同呢？李華五天内取球的某個序列的機率，就不再相同了。另外，除了受到盒子内紅白球的機率分布影響，還要受到某天會抽到哪個盒子的機率分布影響。
在上述例子中，把可能取到的盒子情況，稱作“狀态”；把可能會取到的球的情況，稱作“觀測”。在隐馬爾科夫模型中，盒子會取到的各種狀态，我們是觀測不到的。而球的各種情況我們是知道的，可以被觀測到。
取球要受到盒子所在狀态的影響，示意圖如下：
此時，還不能叫做隐馬爾可夫模型的示例。需要繼續給“取盒子->取球->得到觀測序列”的過程施加限制條件。比如說，t時刻取到某個盒子，要受到t-1時刻盒子的狀态影響。一個簡單的例子，t-1時刻盒子是綠盒子，t時刻一定取灰色盒子，且t-1時刻取到綠盒子不對t+1、t+2、...、T時刻産生影響。具體一點，就是讓“目前時刻隐藏狀态”隻受上一時刻“隐藏狀态”影響，且與所處的時刻t無關。
通過一步步施加的各個條件，此時可以稱作隐馬爾可夫模型的示例了。
隐馬爾科夫模型的基本概念
先上例子，盒子和球模型。
在這個例子中有兩個随機序列，一個是盒子的序列（狀态序列），也就是每次選取到的盒子序列，這個過程是隐藏的，觀測不到從哪個盒子取球；一個是球的顔色序列（觀測序列），我們隻能知道取出來的各個球的顔色。
先分析一下取盒子環節，這是一個環環相扣的過程。從目前t-1時刻的盒子出發，考慮t時刻會取到哪個盒子，要符合規則。如目前盒子是1，根據上述規則，下一個盒子一定是盒子2。考慮t+2時刻會取到哪個盒子，要站在t+1時刻的盒子狀态上，決定取哪一個盒子。所謂的馬爾可夫性，很重要的一點，就是t-1時刻的狀态隻決定t時刻的狀态（盒子1之後一定會取到盒子2），并不能決定t+1時刻狀态的取值（盒子1之後，決定不了盒子2之後會取哪個盒子）。
再看一下取球環節，對應着描述中的從盒子中随機取球的過程。每個盒子裡邊紅、白球的數目不同，不同的盒子取到紅色球的機率不同。目前盒子有屬于自己的機率分布，取球的機率不盡相同。
用數學語言完善完善以下過程：盒子可以構成一個集合；目前時刻的盒子如何确定下一個盒子，需要有狀态轉移機率；球可以夠成一個集合；從不同盒子裡邊取球，需要知道每個盒子的機率分布；取了多少個球，需要有序列長度；最開始怎麼選第一個盒子。
根據所給的條件，有以下：
重點看一下狀态轉移矩陣。
熟悉了這個例子，再來了解數學上的各個概念。
這裡的狀态随機序列就是每次取到盒子組成的序列，觀測序列就是球顔色的序列。隐馬爾科夫模型由狀态的初始機率分布、狀态中間的轉移機率分布以及觀測機率分布組成。
對應着看，Q就是例子中盒子的集合，V就是球顔色的集合，I是盒子序列，O是顔色序列。
令A為狀态轉移矩陣：
這裡的變量i有點混亂，注意區分。公式10.2中，(1)aij中的i是狀态轉移矩陣A中的第i行的意思，aij也就是矩陣A中的第i行第j個元素，該值表示從第i個元素轉移到第j個元素的機率；(2)it+1、it中的i是指該狀态序列中的第t+1、第t個狀态，這裡i是序列的意思；(3)qi中的i是在狀态集合中取到哪個狀态的意思。
t+1時刻能夠取到哪個狀态，要受到t時刻狀态的影響。也就是在t時刻狀态取某個值的條件下，t+1時刻才會有什麼樣的取值。矩陣A次元為N*N，也就是要知道該時刻每個狀态對下一時刻每個狀态的影響。
觀測有M種，vk可以了解為觀測集合V中的第k個觀測。在盒子和球的例子中，可以看到每個觀測的取值，是由隐變量的狀态->哪個盒子決定的，并且隻與目前的盒子有關系，每個盒子有各自取球的機率分布。用機率符号表示就是公式10.4，表示在狀态為第j個盒子的情況下，觀測到vk的機率。
用π來表示初始機率向量，也就是t=1序列起始時，根據一定的機率分布選擇第一個盒子。
在這裡，狀态轉移機率矩陣A與初始狀态機率向量π确定了隐藏的馬爾可夫鍊，可生成不可觀測的狀态序列。觀測機率矩陣B确定了如何從狀态生成觀測，與狀态序列綜合确定了如何産生觀測序列。
從上述描述及定義10.1可以看到，隐馬爾科夫模型做了兩個基本假設：
(1)再次回顧盒子和球模型，盒子的選擇是不是隻規定了時序上前後相鄰的盒子該怎麼選；而沒有第一次選盒子1，第三次一定會選到盒子3這樣的規定。也就是在任意時刻t的狀态隻依賴于其前一時刻t-1的狀态，這就是馬爾科夫鍊“齊次”的重要性質。
(2)觀測獨立性假設是指我們觀測到的每一次現象（紅球、白球），隻與該球所在盒子的機率分布有關，與其它盒子的機率分布沒有一點關系！與其它時刻的觀測沒有一點關系！
觀測序列的生成過程可以由算法10.1描述。
HMM和CRF，與之前學習的各個模型，差别是比較大的，學習思路是要換一換。了解了隐馬爾科夫模型的基本概念，下一步就是要考慮該模型可以做什麼？怎麼做？這裡我接觸的不多，隻能順着書本的思路，學習隐馬爾可夫模型的三個基本問題。
1）機率計算問題。很自然的，考慮一下某個觀測序列O出現的機率P(O|λ)。
2）學習問題。已知觀測序列，用極大似然估計的方法估計模型參數λ=（A,B,Π）。
3）預測問題，也稱解碼問題。知道模型參數，給定觀測序列，求最有可能的對應的狀态序列。
機率計算算法
1）直接計算
已知模型參數λ=（A,B,π）和觀測序列O=(o1,o2,...,oT)，計算觀測序列O出現的機率P(O|λ)。很容易想到，可以按照機率公式直接進行計算。把得到觀測資料的過程，想象成兩個階段：選取狀态和生成觀測。第一步得到狀态序列，第二步得到觀測序列，可以應用乘法原理。不同的觀測序列可以得到不同的觀測序列，可以應用加法原理。類似于全機率公式，通過列舉所有可能的狀态序列I，求各個狀态序列I上生成觀測O的機率（也就是I,O的聯合機率），然後對所有可能的狀态序列求和，得到P(O|λ)。
容易了解，公式(10.10)為全部狀态序列中某個狀态序列I的機率計算公式；公式(10.11)為在該狀态序列I條件下，觀測序列為O時的條件機率計算方法；公式(10.12)為聯合機率公式；公式(10.13)對所有可能的狀态I求和，也就是求O的邊緣機率（考慮在I出現的所有情況條件下，O出現的機率）。簡單分析下，若狀态數目為N，一共有T個狀态序列，是以狀态序列的可能性為NT。每一種狀态序列都要相應乘T個觀測機率，是以最後的時間複雜度為O(TNT)。用這種方法計算觀測序列O出現的機率，是非常低效的。接下來介紹高效的計算方式，前向-後向算法。
2）前向算法
先來看一個新概念“前向機率”：
放在示意圖上，如藍色虛線框α3(i)=P(o1,o2,o3,it=qi|λ)，可以從聯合機率的角度了解。具體為 αt=3(灰色盒子)=P(o1=紅球,o2=白球,o3=紅球,it=3=灰色盒子|λ)：
在前向機率的基礎上，定義前向算法為：
步驟(1),計算初值。注意這裡α1(i)應用向量來表示，在t=1，觀測取到o1時，各個隐藏狀态i都有到達o1的機率。計算分兩步，從初始機率πi到隐狀态qi，再從qi經發射矩陣到觀測o1，需要對每個隐藏狀态i計算。
步驟(2)，前向算法遞推公式。αt(i)遞推到αt+1(i)，公式(10.16)中的bi(ot+1)可以了解為下圖第二步，由所在的狀态qi經發射矩陣得到觀測ot+1；aji可以了解為下圖中的第一步，也就是由t時刻狀态qj經轉移矩陣在t+1時刻狀态為qi的過程。
公式(10.16)中的求和符号，實際上反映的是t+1時刻取qi時，其實t時刻的任何一個狀态都可以轉移到qi，是以要把t時刻的每種狀态都考慮到。
步驟(3)，終止。公式(10.17)的求和符号挺好了解的，因為
，對iT=qi求和，實際上相當于求觀測序列O的邊緣機率。
再來看一下書中的詳細解釋：
通過畫圖，是不是要好了解一些~前向算法高效就高效在利用先前的局部計算結果，通過路徑結構将局部結果“遞推”到全局。
看一下例10.2，基本上就可以了解這個計算過程了。
3）後向算法
相應的，後向算法先了解“後向機率”這個概念。
放在示意圖上，如綠色虛線框β2(i)=P(o3,...,oT-1,oT,it=qi|λ)，可從條件機率的角度了解。具體為βt=2(綠色盒子)=P(o3=紅球,oT-1=紅,oT=紅球|it=2=綠色盒子,λ)：
在後向機率的基礎上，定義後向算法為：
步驟（1），初始化後向機率。這裡将最終時刻的所有狀态qi規定為βT(i)=1以下示意圖簡單分析。
這就好像是βt(i)=P(ot+1,ot+2,…,oT|it=qi, λ)變成了βt(i)=P(it=qi, λ)，此時對于it的所有取值，it=qi，是一個不争的事實。
步驟（2），後向算法遞推公式。這裡的遞推方向是反向由T+1遞推到T,圖示如下：
這裡由T+1遞推到T，仍然需要①②兩處的連接配接。①是公式(10.20)中的aij，②是公式(10.20)中的bj(ot+1)。求和符号是t時刻qi到t+1時刻qj所有情況的彙總。取(qi=灰色盒子，ot+1=白球)進行分析：
T+1遞推到T，我覺得圖畫的應該差不多了...①②部分是怎樣起到連接配接作用的...大概就是上圖這樣吧...我解釋不出來...當然了，知乎也好CSDN也好，有詳細推導公式，我就不班門弄斧了。書面解釋如下：
于是，利用前向機率和後向機率的定義，可以将觀測序列機率P(O|λ)同一寫成：
示意圖好像是這個樣子：
公式(10.22)中，先來看前向機率的求和部分，i=1時，αt(1)是t時刻盒子為灰盒子，觀測序列為(o1,o2,...ot,it=q1)的機率；相應的，αt(2)是t時刻盒子為黃盒子，觀測序列為(o1,o2,...ot,it=q2)的機率；αt(3)是t時刻盒子為綠盒子，觀測序列為(o1,o2,...ot,it=q3)的機率；αt(4)是t時刻盒子為藍盒子，觀測序列為(o1,o2,...ot,it=q4)的機率。那麼求和自然就代表着，不考慮盒子的影響，觀測序列為(o1,o2,...ot)的邊緣機率。對應示意圖，也就是消除了t時刻狀态的影響。
同理，後向機率的求和部分，在示意圖中相當于消除了t+1時刻狀态的影響。①對應着公式(10.22)中的aij，建立連接配接。②對應着公式(10.22)中的bj(ot+1)，将ot+1時刻的觀測計入統計。
4）一些機率與期望值的計算
利用前向機率和後向機率，可以得到關于單個狀态和兩個狀态機率的計算公式。頭幾遍看這幾個公式的時候，丈二和尚摸不着頭腦，不知道這幾個機率計算有什麼用，就沒怎麼好好看。編寫這部分代碼的時候，發現這幾個公式挺重要的。在學習算法小結，對估計模型參數非常有用。公式介紹的挺具體的，這裡就不在畫圖了...學習的時候随手畫畫圖，就能了解了~
1)求單個狀态的條件機率：
還是畫吧，這裡γt(i)反映是在給定觀測序列O條件下，t時刻處于狀态qi的機率。如下圖，γt(i=灰色盒子)。
2)求兩個連續狀态的條件機率：
如下圖所示ξt(i,j)反映的是，在給定觀測序列O的條件下，t時刻狀态為灰色盒子、t+1時刻狀态為綠色盒子的條件機率。
3)一些有用的期望，在學習算法小節可以看到用處：
學習算法
書中提到，我們進行隐馬爾可夫模型的學習，也就是對模型參數進行估計。根據訓練資料是包括觀測序列和對應的狀态序列，還是隻有觀測序列，可以分别由監督學習和無監督學習實作，這裡監督學習方法實際上就是利用極大似然估計。
1)監督學習方法。書中直接給出了參數估計公式，這裡簡單摘抄下~
2)無監督學習方法。顧名思義，無監督方法也就是隻有觀測序列，進行參數估計的方法。由于監督學習需要使用标注的訓練資料，而人工标注訓練資料往往代價很高。是以有時候就會利用無監督學習的方法。我們可以将觀測序列資料看作EM算法中的不完全資料，狀态序列資料看作EM算法中不可觀測的隐資料，那麼隐馬爾可夫模型就可以看作是含有隐變量的機率模型。于是，可以通過EM算法求解。
詳細過程如下：
1.确定完全資料的對數似然函數
2.EM算法的E步：求Q函數Q(λ,λ^)
3.EM算法的M步：極大化Q函數Q(λ,λ^)求模型參數A,B,π
書本上有詳細的推導公式，看懂了2/3，先不摘抄了。有空了把了解了的整理上來，參數估計公式如下：
于是，有以下Baum-Welch算法，從這裡可以發現一些期望的用處：
預測算法
預測算法，也就是根據已知的觀測序列，找到機率最大的狀态序列（最有可能的對應的狀态序列）。
應用維特比算法，相當于有向無環圖求最短路徑，網上有大量詳細的資料，暫不整理了~