上篇主要介紹了半監督學習，首先從如何利用未标記樣本所蘊含的分布資訊出發，引入了半監督學習的基本概念，即訓練資料同時包含有标記樣本和未标記樣本的學習方法；接着分别介紹了幾種常見的半監督學習方法：生成式方法基于對資料分布的假設，利用未标記樣本隐含的分布資訊，使得對模型參數的估計更加準确；TSVM給未标記樣本賦予僞标記，并通過不斷調整易出錯樣本的标記得到最終輸出；基于分歧的方法結合了內建學習的思想，通過多個學習器在不同視圖上的協作，有效利用了未标記樣本資料 ；最後半監督聚類則是借助已有的監督資訊來輔助聚類的過程，帶限制k-均值算法需檢測目前樣本劃分是否滿足限制關系，帶标記k-均值算法則利用有标記樣本指定初始類中心。本篇将讨論一種基于圖的學習算法–機率圖模型。
#15、機率圖模型
現在再來談談機器學習的核心價值觀，可以更通俗地了解為：根據一些已觀察到的證據來推斷未知，更具哲學性地可以闡述為：未來的發展總是遵循着曆史的規律。其中基于機率的模型将學習任務歸結為計算變量的機率分布，正如之前已經提到的：生成式模型先對聯合分布進行模組化，進而再來求解後驗機率，例如：貝葉斯分類器先對聯合分布進行最大似然估計，進而便可以計算類條件機率；判别式模型則是直接對條件分布進行模組化。
機率圖模型（probabilistic graphical model）是一類用圖結構來表達各屬性之間相關關系的機率模型，一般而言：圖中的一個結點表示一個或一組随機變量，結點之間的邊則表示變量間的相關關系，進而形成了一張“變量關系圖”。若使用有向的邊來表達變量之間的依賴關系，這樣的有向關系圖稱為貝葉斯網（Bayesian nerwork）或有向圖模型；若使用無向邊，則稱為馬爾可夫網（Markov network）或無向圖模型。
##15.1 隐馬爾可夫模型(HMM)
隐馬爾可夫模型（Hidden Markov Model，簡稱HMM）是結構最簡單的一種貝葉斯網，在語音識别與自然語言處理領域上有着廣泛的應用。HMM中的變量分為兩組：狀态變量與觀測變量，其中狀态變量一般是未知的，是以又稱為“隐變量”，觀測變量則是已知的輸出值。在隐馬爾可夫模型中，變量之間的依賴關系遵循如下兩個規則：
1. 觀測變量的取值僅依賴于狀态變量；
2. 下一個狀态的取值僅依賴于目前狀态，通俗來講：現在決定未來，未來與過去無關，這就是著名的馬爾可夫性。
基于上述變量之間的依賴關系，我們很容易寫出隐馬爾可夫模型中所有變量的聯合機率分布：
易知：欲确定一個HMM模型需要以下三組參數：
當确定了一個HMM模型的三個參數後，便按照下面的規則來生成觀測值序列：
在實際應用中，HMM模型的發力點主要展現在下述三個問題上：
###15.1.1 HMM評估問題
HMM評估問題指的是：給定了模型的三個參數與觀測值序列，求該觀測值序列出現的機率。例如：對于賭場問題，便可以依據骰子擲出的結果序列來計算該結果序列出現的可能性，若小機率的事件發生了則可認為賭場的骰子有作弊的可能。解決該問題使用的是前向算法，即步步為營，自底向上的方式逐漸增加序列的長度，直到獲得目标機率值。在前向算法中，定義了一個前向變量，即給定觀察值序列且t時刻的狀态為Si的機率：
基于前向變量，很容易得到該問題的遞推關系及終止條件：
是以可使用動态規劃法，從最小的子問題開始，通過填表格的形式一步一步計算出目标結果。
###15.1.2 HMM解碼問題
HMM解碼問題指的是：給定了模型的三個參數與觀測值序列，求可能性最大的狀态序列。例如：在語音識别問題中，人說話形成的數字信号對應着觀測值序列，對應的具體文字則是狀态序列，從數字信号轉化為文字正是對應着根據觀測值序列推斷最有可能的狀态值序列。解決該問題使用的是Viterbi算法，與前向算法十分類似地，Viterbi算法定義了一個Viterbi變量，也是采用動态規劃的方法，自底向上逐漸求解。
###15.1.3 HMM學習問題
HMM學習問題指的是：給定觀測值序列，如何調整模型的參數使得該序列出現的機率最大。這便轉化成了機器學習問題，即從給定的觀測值序列中學習出一個HMM模型，該問題正是EM算法的經典案例之一。其思想也十分簡單：對于給定的觀測值序列，如果我們能夠按照該序列潛在的規律來調整模型的三個參數，則可以使得該序列出現的可能性最大。假設狀态值序列也已知，則很容易計算出與該序列最契合的模型參數：
但一般狀态值序列都是不可觀測的，且即使給定觀測值序列與模型參數，狀态序列仍然遭遇組合爆炸。是以上面這種簡單的統計方法就行不通了，若将狀态值序列看作為隐變量，這時便可以考慮使用EM算法來對該問題進行求解：
【1】首先對HMM模型的三個參數進行随機初始化；
【2】根據模型的參數與觀測值序列，計算t時刻狀态為i且t+1時刻狀态為j的機率以及t時刻狀态為i的機率。
【3】接着便可以對模型的三個參數進行重新估計：
【4】重複步驟2-3，直至三個參數值收斂，便得到了最終的HMM模型。
##15.2 馬爾可夫随機場（MRF）
馬爾可夫随機場（Markov Random Field）是一種典型的馬爾可夫網，即使用無向邊來表達變量間的依賴關系。在馬爾可夫随機場中，對于關系圖中的一個子集，若任意兩結點間都有邊連接配接，則稱該子集為一個團；若再加一個結點便不能形成團，則稱該子集為極大團。MRF使用勢函數來定義多個變量的機率分布函數，其中每個（極大）團對應一個勢函數，一般團中的變量關系也展現在它所對應的極大團中，是以常常基于極大團來定義變量的聯合機率分布函數。具體而言，若所有變量構成的極大團的集合為C，則MRF的聯合機率函數可以定義為：
對于條件獨立性，馬爾可夫随機場通過分離集來實作條件獨立，若A結點集必須經過C結點集才能到達B結點集，則稱C為分離集。書上給出了一個簡單情形下的條件獨立證明過程，十分貼切易懂，此處不再展開。基于分離集的概念，得到了MRF的三個性質：
全局馬爾可夫性：給定兩個變量子集的分離集，則這兩個變量子集條件獨立。
局部馬爾可夫性：給定某變量的鄰接變量，則該變量與其它變量條件獨立。
成對馬爾可夫性：給定所有其他變量，兩個非鄰接變量條件獨立。
對于MRF中的勢函數，勢函數主要用于描述團中變量之間的相關關系，且要求為非負函數，直覺來看：勢函數需要在偏好的變量取值上函數值較大，例如：若x1與x2成正相關，則需要将這種關系反映在勢函數的函數值中。一般我們常使用指數函數來定義勢函數：
##15.3 條件随機場（CRF）
前面所講到的隐馬爾可夫模型和馬爾可夫随機場都屬于生成式模型，即對聯合機率進行模組化，條件随機場則是對條件分布進行模組化。CRF試圖在給定觀測值序列後，對狀态序列的機率分布進行模組化，即P(y | x)。直覺上看：CRF與HMM的解碼問題十分類似，都是在給定觀測值序列後，研究狀态序列可能的取值。CRF可以有多種結構，隻需保證狀态序列滿足馬爾可夫性即可，一般我們常使用的是鍊式條件随機場：
與馬爾可夫随機場定義聯合機率類似地，CRF也通過團以及勢函數的概念來定義條件機率P(y | x)。在給定觀測值序列的條件下，鍊式條件随機場主要包含兩種團結構：單個狀态團及相鄰狀态團，通過引入兩類特征函數便可以定義出目标條件機率：
以詞性标注為例，如何判斷給出的一個标注序列靠譜不靠譜呢？轉移特征函數主要判定兩個相鄰的标注是否合理，例如：動詞+動詞顯然文法不通；狀态特征函數則判定觀測值與對應的标注是否合理，例如： ly結尾的詞–>副詞較合理。是以我們可以定義一個特征函數集合，用這個特征函數集合來為一個标注序列打分，并據此選出最靠譜的标注序列。也就是說，每一個特征函數（對應一種規則）都可以用來為一個标注序列評分，把集合中所有特征函數對同一個标注序列的評分綜合起來，就是這個标注序列最終的評分值。可以看出：特征函數是一些經驗的特性。
##15.4 學習與推斷
對于生成式模型，通常我們都是先對變量的聯合機率分布進行模組化，接着再求出目标變量的邊際分布（marginal distribution），那如何從聯合機率得到邊際分布呢？這便是學習與推斷。下面主要介紹兩種精确推斷的方法：變量消去與信念傳播。
###15.4.1 變量消去
變量消去利用條件獨立性來消減計算目标機率值所需的計算量，它通過運用乘法與加法的配置設定率，将對變量的積的求和問題轉化為對部分變量交替進行求積與求和的問題，進而将每次的運算控制在局部，達到簡化運算的目的。
###15.4.2 信念傳播
若将變量求和操作看作是一種消息的傳遞過程，信念傳播可以了解成：一個節點在接收到所有其它節點的消息後才向另一個節點發送消息，同時目前節點的邊際機率正比于他所接收的消息的乘積：
是以隻需要經過下面兩個步驟，便可以完成所有的消息傳遞過程。利用動态規劃法的思想記錄傳遞過程中的所有消息，當計算某個結點的邊際機率分布時，隻需直接取出傳到該結點的消息即可，進而避免了計算多個邊際分布時的備援計算問題。
1.指定一個根節點，從所有的葉節點開始向根節點傳遞消息，直到根節點收到所有鄰接結點的消息**（從葉到根）；
2.從根節點開始向葉節點傳遞消息，直到所有葉節點均收到消息（從根到葉）**。
##15.5 LDA話題模型
話題模型主要用于處理文本類資料，其中隐狄利克雷配置設定模型（Latent Dirichlet Allocation，簡稱LDA）是話題模型的傑出代表。在話題模型中，有以下幾個基本概念：詞（word）、文檔（document）、話題（topic）。
詞：最基本的離散單元；
文檔：由一組詞組成，詞在文檔中不計順序；
話題：由一組特定的詞組成，這組詞具有較強的相關關系。
在現實任務中，一般我們可以得出一個文檔的詞頻分布，但不知道該文檔對應着哪些話題，LDA話題模型正是為了解決這個問題。具體來說：LDA認為每篇文檔包含多個話題，且其中每一個詞都對應着一個話題。是以可以假設文檔是通過如下方式生成：
這樣一個文檔中的所有詞都可以認為是通過話題模型來生成的，當已知一個文檔的詞頻分布後（即一個N維向量，N為詞庫大小），則可以認為：每一個詞頻元素都對應着一個話題，而話題對應的詞頻分布則影響着該詞頻元素的大小。是以很容易寫出LDA模型對應的聯合機率函數：
從上圖可以看出，LDA的三個表示層被三種顔色表示出來：
corpus-level（紅色）： α和β表示語料級别的參數，也就是每個文檔都一樣，是以生成過程隻采樣一次。
document-level（橙色）： θ是文檔級别的變量，每個文檔對應一個θ。
word-level（綠色）： z和w都是單詞級别變量，z由θ生成，w由z和β共同生成，一個單詞w對應一個主題z。
通過上面對LDA生成模型的讨論，可以知道LDA模型主要是想從給定的輸入語料中學習訓練出兩個控制參數α和β，當學習出了這兩個控制參數就确定了模型，便可以用來生成文檔。其中α和β分别對應以下各個資訊：
α：分布p(θ)需要一個向量參數，即Dirichlet分布的參數，用于生成一個主題θ向量；
β：各個主題對應的單詞機率分布矩陣p(w|z)。
把w當做觀察變量，θ和z當做隐藏變量，就可以通過EM算法學習出α和β，求解過程中遇到後驗機率p(θ,z|w)無法直接求解，需要找一個似然函數下界來近似求解，原作者使用基于分解（factorization）假設的變分法（varialtional inference）進行計算，用到了EM算法。每次E-step輸入α和β，計算似然函數，M-step最大化這個似然函數，算出α和β，不斷疊代直到收斂。
在此，機率圖模型就介紹完畢。上周受到協同訓練的啟發，讓實驗的小夥伴做了一個HMM的slides，結果擴充了好多知識，是以完成這篇筆記還是花費了不少功夫，還剛好趕上實驗室沒空調回到解放前的日子，可謂汗流之作…