與最佳路徑不同的問題
現有語言模型課文推導前向似然及維特比(Viterbi)最佳路徑。這裏使用整段觀測,詢問某一時刻狀態的後驗分布。這是平滑:它不同於只用目前為止觀測的過濾,也不同於選擇一條最可能的完整路徑。
使用有限隱藏狀態集合 、長度 的非空觀測序列 、初始概率 、轉移概率 及發射概率 。與現有課文一樣,模型指定一階狀態鏈,以及給定狀態後條件獨立的發射。初始概率構成概率分布;每個狀態對應的轉移及發射概率也各自構成概率分布。
前綴與後綴量
定義 11.1.1
(前向值與後向值)
狀態 在時刻 的前向值,是觀測前綴與該狀態同時出現的概率:
後向值 把從時刻 的狀態 之後開始的所有可能後綴狀態序列之模型轉移與發射乘積相加:
空後綴(即 )的權重為一。兩者都滿足一步遞推:
記 為整段序列的似然。
當 時, 是給定該狀態後較晚觀測的條件概率。後綴乘積的定義也為零概率狀態指定數值,而不必對零概率事件取條件。
定理 11.1.2
(平滑恆等式)
對每個 及狀態 ,
對 及狀態 ,
若 ,平滑後驗為
而且它們互相一致:,。
證明
(在時刻 t 分割每條路徑)
固定 。在聯合模型中,每條相容完整路徑可分為一段以 結束的前綴,以及由 轉移出去的後綴。把乘積對兩組選擇求和得到 。當 時這就是 ,對 求和便得 。
對 ,按相鄰狀態 、 分割。路徑權重分解為到 為止的前綴、單一步 ,以及 之後的後綴,由此得到所述聯合概率。除以 便得 及 。
關於一致性,後向遞推給出 ,前向遞推給出 。除以 即得兩條邊際化等式。
證明透視
分解在哪裏被使用
模型假設只在一處進入:完整路徑的權重是一個初始因子,加上每一步的一個轉移因子和一個發射因子的乘積。在時刻 把這個乘積切開,涉及 的因子構成前綴,涉及 的因子構成後綴。兩組因子恰好共用一個變量 。這就是必須先固定 的原因,也是前綴與後綴的雙重求和能分離為兩個和之乘積的唯一理由。
所以關鍵一步是分配律:對前綴與後綴各自獨立求和,把指數多條路徑換成兩個長度為 的向量。論證能夠收尾,是因為 使 的情形正好就是 的定義,而每條遞推只是把同一刀移動一步。
有兩點並未聲稱。第一,論證沒有說給定觀測後隱藏狀態彼此獨立:等式只對每個固定的 逐一成立,多個時刻的聯合後驗並不等於各 的乘積。第二,除了模型本身,唯一需要額外假設的是最後的除法,它要求 。
若 ,這些條件後驗不能由該比率定義。例如所有狀態都給觀測到的詞零概率時,每條完整路徑的觀測概率都是零。把 換成均勻向量是額外約定,並非上述後驗。
兩狀態計算
例題 11.1.3
(兩狀態模型中的平滑)
取狀態 、初始向量 、轉移矩陣
以及發射概率 、、、。對觀測 ,前向及後向值為
因此
作比較,時刻一的過濾只用 ,得到 ;較晚觀測令其平滑概率變成 。
反例模式
逐時刻眾數未必是最佳路徑
這裏時刻一最可能狀態是 ,時刻二是 ,所以逐個選邊際眾數得到 ,其後驗概率為 。完整路徑 的後驗概率為 ,更為可能。因此逐個最大化邊際分布並非維特比解碼,即使此例四種轉移都可能。
例題 11.1.4
(單一觀測:平滑等於過濾)
沿用同一模型,但觀測序列只有一個符號 ()。此時 、,所以 ,而
沒有較晚的觀測,所以平滑與過濾一致;又因為不存在 ,所以沒有相鄰狀態後驗 。這是遞推的邊界情形。
例題 11.1.5
(被證據排除的狀態)
保留初始向量及 ,但把狀態 的發射改為 、,並保留 、。對觀測 :
後向值為 ,以及 、。於是
觀測 在狀態 不可能出現,所以狀態 在時刻二的平滑概率為零,儘管它的先驗概率為正。作核對:,,兩者之和為 。
常見錯誤
常見錯誤
(把平滑邊際分布當作互相獨立)
在兩狀態計算中,,但路徑 的後驗概率是 。 只描述單一時刻;要得到多個時刻的聯合後驗,需要相鄰狀態項 (更長路徑則要用完整的鏈分解)。
常見錯誤
(用前綴總和作正規化)
在 時, 是過濾用的常數,並非 。在兩狀態計算中 ,而 。若以 去除 ,所得數值之和不等於一。平滑的分母永遠是整段序列的似然 。
成本與習題
對稠密轉移及常數時間算術,計算全部前向及後向值需 時間。儲存全部前向值並滾動使用一個後向向量,可用 個儲存值按時間倒序輸出狀態後驗;輸出每個 本身便有 個值。長乘積在浮點運算中可能下溢;縮放或 log-sum-exp 實作必須一致地保留正規化。
快速檢查
( 是多少?)
想一想時刻 之後有哪些觀測。
解答 · 答案
:後綴為空,沒有較晚的觀測需要生成,空乘積等於一。
快速檢查
(在觀測為 的兩狀態例子中, 是多少?)
讀出 矩陣第 行第 列的元素。
解答 · 答案
。
快速檢查
(在兩狀態例子中,把 的第一列相加,應等於哪個平滑後驗?)
對較早的狀態 求和。
解答 · 答案
:對 求和 得到時刻二狀態 的後驗。
快速檢查
(若 ,能計算 的公式嗎?)
留意分母。
解答 · 答案
不能。公式是以 為分母的比率, 沒有數值;對概率為零的觀測事件取條件,不能由此比率給出。