機器學習總結——機率圖模型

文章目錄

• 簡介
• • 常見圖模型
  • NLP中機率圖模型演變
• 隐馬爾可夫模型
• • 馬爾科夫鍊
  • 參數
  • 三個基本問題
  • 存在的問題
• 随機場
• 馬爾可夫随機場
• • 勢函數
  • 團&最大團
  • 基于最大團定義的聯合機率
  • 分離集
  • 性質
• 最大熵馬爾科夫随機場
• • HMM與MEMM的差別
  • 優點
  • 缺點
  • • 标記偏置問題
• 條件随機場
• • 參數化形式
  • 三個基本問題
  • 優點
  • 與馬爾科夫随機場差別
  • 與MEMM差別
• 近似推斷
• • 采樣
  • • MCMC
    • • Metropolis-Hastings
      • 吉布斯采樣
  • 變分推斷

機率圖模型是一類用圖來表達變量相關關系的機率模型。

簡介

常見圖模型

NLP中機率圖模型演變

隐馬爾可夫模型

• 有向圖
• 生成式模型

馬爾科夫鍊

系統的下一個時刻的狀态僅有目前狀态決定，不依賴于以往任何狀态

參數

• 狀态轉移機率
• 輸出觀測機率
• 初始狀态機率

三個基本問題

• 求觀測序列機率
• 由觀測序列求隐藏模型狀态
• 由觀測序列對參數估計使得觀測序列出現機率最大

存在的問題

1. 在很多序列标注任務中，當不能枚舉觀察輸出時，需要用大量的特征來刻畫觀察序列。也就是說需要用特征對觀察輸出參數化。如任務中當出現未登入的公司名字，除了傳統的單詞識别方法外，還需要額外的特征資訊，如大寫字母、結尾詞、詞性等等。
2. 許多NLP任務需要解決的是已知觀察序列求狀态序列，HMM采用的生成式聯合機率模型來求解這種條件機率問題，這種方法不适合用很多特征描述觀察序列的情況（因為生成式模型的特征需要提前給定，而判别式會從觀測中提取特征）。

随機場

Quora

A stochastic process is a family of random variables X ( t ) t ∈ T {X(t)}_{t\in T} X(t)t∈T​where for each t t t, X ( t ) X(t) X(t) is a random variable, and t t t varies in the set T T T called the index set. Theoretically, the definition does not put any restriction on the index set T T T, it can be any set. However, when we say stochastic process, 99% of time we are actually thinking t t t as the time, hence, T T T must be the real line or the set of integers or a part of them.

When this is not the case, most commonly, when T T T is actually a higher dimensional Euclidean space or a part of it, or something like that (a “manifold”), then X ( t ) t ∈ T {X(t)}_{t\in T} X(t)t∈T​is called a random field. The idea is that since the index is no longer one-dimensional, we can not think it as time, so we think it as space. As a result, we don’t get a

“process”, we get a “field”. Thus what we get is a random surface, or a random multivariate function.

馬爾可夫随機場

• 無向圖
• 生成式模型
• 也稱為機率無向圖

勢函數

定義在變量子集上的非負實函數，主要用于定義機率分布函數,作用是定量刻畫變量集 x Q x_Q xQ​中變量之間的相關關系

團&最大團

• 團：結點集合中的任意兩點都有邊相連
• 最大團：團加入另外一個結點後不再形成團

基于最大團定義的聯合機率

P ( x ) = 1 Z ∗ ∏ Q ∈ C ∗ ψ Q ( x Q ) P(x)=\frac{1}{Z^*}\prod_{Q\in C^*}\psi_Q(x_Q) P(x)=Z∗1​∏Q∈C∗​ψQ​(xQ​)

分離集

若從結點集A中的結點到B中的結點都必須經過結點集C中的結點，則稱A和B被C分離

性質

• 全局馬爾科夫性

  給定兩個變量子集的分離集，則這兩個變量子集條件獨立

• 局部馬爾科夫性

  給定某變量的鄰接變量，則該變量條件獨立于其他變量

• 成對馬爾科夫性

  給定所有其他變量，兩個非鄰接變量條件獨立

最大熵馬爾科夫随機場

最大熵馬爾科夫随機場又稱條件馬爾科夫模型，結合了HMM與ME模型的共同特點，用于處理序列标注問題。

MEMM是有向圖和無向圖的混合模型，其主體還是有向圖架構。

上面提到HMM存在的兩個問題，是以MEMM直接采用條件機率模型 P ( S T ∣ O T ) P(S_T|O_T) P(ST​∣OT​)，進而使觀察輸出可以用特征表示，借助最大熵架構進行特征選取。

HMM與MEMM的差別

實線箭頭表示所指結點依賴于箭頭起始結點，虛線箭頭表示箭頭所指的是起始結點條件。

• 在HMM中，目前時刻的觀察值僅取決于目前狀态
• 在MEMM中，目前時刻的觀察還可能取決于前一時刻的狀态

優點

與HMM相比，最大的優點是允許使用任意特征刻畫觀察序列，有利于針對特定任務充分利用領域知識設計特征。

缺點

标記偏置問題

1. 原因一是熵低的狀态轉移分布會忽略它們的觀察輸出
2. 原因二是參數的訓練過程是從左向右依據前面已經标注的标記進行的，一旦實際過程中前面的标記不能确定時，MEMM往往難以處理

條件随機場

https://www.cnblogs.com/pinard/p/7048333.html

CRF是給定一組輸入随機變量條件下另一組輸出随機變量的條件機率分布模型，特點是假設輸出随機變量構成馬爾科夫随機場。

• 無向圖
• 判别式模型
• 可以看做給定觀測值的馬爾科夫随機場
• 也可看做對率回歸的擴充

  

參數化形式

三個基本問題

• 特征選取
• 參數訓練，可在訓練集上基于對數似然函數的最大化進行
• 解碼

優點

• 相比HMM，主要優點在于條件随機性，隻需要考慮目前已經出現的觀測狀态的特性，沒有獨立性的嚴格要求，對于整個序列内部的資訊和外部觀測資訊均可有效利用，避免了MEMM和其他線性序列條件馬爾科夫模型會出現的标記偏置問題

與馬爾科夫随機場差別

從公式上看二者均使用團上的勢函數定義機率

• 條件随機場處理的是條件機率，馬爾科夫随機場處理的是聯合機率

與MEMM差別

CRF具有MEMM一切優點，關鍵差別在于

• MEMM使用每一個狀态的指數模型來計算前一個狀态下目前狀态的條件機率
• CRF使用單個指數模型來計算給定觀測序列下與整個标記序列的聯合機率

近似推斷

采樣

MCMC

設法構造一條馬爾科夫鍊，使其收斂至平穩分布恰為待估計參數的後驗分布，然後通過這條馬爾科夫鍊來産生符合後驗分布的樣本，并基于這些樣本進行估計。

假定平穩馬爾科夫鍊 T T T的狀态轉移機率（從狀态 x x x轉移到 x ′ x' x′的機率）為 T ( x ′ ∣ x ) T(x'|x) T(x′∣x)， t t t時刻狀态分布為 p ( x t ) p(x^t) p(xt)，則若某個時刻馬爾科夫鍊滿足平穩條件

p ( x t ) T ( x t − 1 ∣ x t ) = p ( x t − 1 ) T ( x t ∣ x t − 1 ) p(x^t)T(x^{t-1}|x^t)=p(x^{t-1})T(x^t|x^{t-1}) p(xt)T(xt−1∣xt)=p(xt−1)T(xt∣xt−1)

則 p ( x ) p(x) p(x)是該馬爾可夫鍊的平穩分布，且馬爾可夫鍊在滿足該條件時已收斂到平穩狀态。

不同的構造方法将産生不同的MCMC算法。

Metropolis-Hastings

基于拒絕采樣來逼近平穩分布

根據上一輪采樣結果 x t − 1 x^{t-1} xt−1來采樣擷取候選狀态樣本 x ∗ x^* x∗，但是候選樣本會以一定機率被拒絕。假定從狀态 x t − 1 x^{t-1} xt−1轉移到 x ∗ x^* x∗的轉移機率為 Q ( x ∗ ∣ x t − 1 ) A ( x ∗ ∣ x t − 1 ) Q(x^*|x^{t-1})A(x^*|x^{t-1}) Q(x∗∣xt−1)A(x∗∣xt−1)，其中 Q ( x ∗ ∣ x t − 1 ) Q(x^*|x^{t-1}) Q(x∗∣xt−1)， A ( x ∗ ∣ x t − 1 ) A(x^*|x^{t-1}) A(x∗∣xt−1)為 x ∗ x^* x∗被接受的機率，若 x ∗ x^* x∗最終收斂到平穩狀态則

p ( x t − 1 ) Q ( x ∗ ∣ x t − 1 ) A ( x ∗ ∣ x t − 1 ) = p ( x ∗ ) Q ( x t − 1 ∣ x ∗ ) A ( x t − 1 ∣ x ∗ ) p(x^{t-1})Q(x^*|x^{t-1})A(x^*|x^{t-1})=p(x^*)Q(x^{t-1}|x^{*})A(x^{t-1}|x^{*}) p(xt−1)Q(x∗∣xt−1)A(x∗∣xt−1)=p(x∗)Q(xt−1∣x∗)A(xt−1∣x∗)

為了達到平穩狀态，隻需要将接受率設定為

A ( x ∗ ∣ x t − 1 ) = min ⁡ ( 1 , p ( x ∗ ) Q ( x t − 1 ∣ x ∗ ) p ( x t − 1 ) Q ( x ∗ ∣ x t − 1 ) ) A(x^*|x^{t-1})=\min(1,\frac{p(x^*)Q(x^{t-1}|x^*)}{p(x^{t-1})Q(x^{*}|x^{t-1})}) A(x∗∣xt−1)=min(1,p(xt−1)Q(x∗∣xt−1)p(x∗)Q(xt−1∣x∗)​)

吉布斯采樣

可視為MH算法的特例

假定 x = { x 1 , ⋯   , x N } \mathbf{x}=\{x_1,\cdots,x_N\} x={x1​,⋯,xN​}，目标分布為 p ( x ) p(\mathbf{x}) p(x)，在初始化 x \mathbf{x} x的取值後，通過循環執行以下步驟

1. 随機或以某個次序選取某變量 x i x_i xi​
2. 根據 x \mathbf{x} x中除 x i x_i xi​以外的變量的現有取值，計算條件機率 p ( x i ∣ x i ˉ ) p(x_i|\mathbf{x}_{\bar{i}}) p(xi​∣xiˉ​)，其中 x i ˉ = { x 1 , ⋯   , x i − 1 , x i + 1 , ⋯   , x N } \mathbf{x}_{\bar{i}}=\{x_1,\cdots,x_{i-1},x_{i+1},\cdots,x_N\} xiˉ​={x1​,⋯,xi−1​,xi+1​,⋯,xN​}
3. 根據 p ( x i ∣ x i ˉ ) p(x_i|\mathbf{x}_{\bar{i}}) p(xi​∣xiˉ​)對 x i x_i xi​進行采樣，用采樣值代替原值

變分推斷