Fit Hidden Markov Model

擬隱馬可夫模

以 Baum-Welch 期望最大（EM）算法擬隱馬可夫模（HMM）於序觀數，以 Viterbi 解最可能隱態序，以信息準擇最宜隱態數。

用時

• 觀放射之序而底生態不可直觀
• 疑數由系於有限幾勢間切換而生
• 須分時序為潛階（如市勢、語素、生物序注）
• 須於生模下算觀序之機率
• 須給觀之最可能隱態序（解）
• 較異隱態數之模於最佳繁—擬衡

入

必要

可選

法

第一步：定隱態與觀模

1.1. 指隱態數 K（或候域供第五步之模擇）

1.2. 按數類擇放射分：

• 續數：高斯（單或多元）
• 計數：Poisson 或負二項
• 類數：離散/多項

1.3. 定模部：

• 轉移陣 A 大 K x K：A[i,j] = P(z_t = j | z_{t-1} = i)
• 各態 k 之放射參 theta_k：分特（如高斯之均與協）
• 初態分 pi：pi[k] = P(z_1 = k)

1.4. 驗觀數格正：序無缺值、維一、相參數之長足

得： 明定之 HMM 架：K 態、擇放射家、清觀數長 T >> K^2。

敗則： 若數含缺值，補或去影段。若 T 對 K 過小，減 K 或取更多數。

第二步：初參

2.1. 為 n_restarts 各重啟生初參：

• 轉移陣：隨機行隨機陣（各行自 Dirichlet 抽）或微擾均陣
• 放射參：於觀用 K-means 聚類以初均；算聚方差供高斯放射
• 初分：均或比 K-means 聚大

2.2. 首啟用 K-means 初（通強起）。後啟用隨機擾

2.3. 驗諸初參有效：

• 轉移陣行和為 1，諸項非負
• 放射參於有效域（如協陣正定）
• 初分和為 1

得： n_restarts 組有效初參，至少一數驅之初。

敗則： 若 K-means 不收斂，純隨機初多啟。若協陣奇，加正則常於對角。

第三步：運 Baum-Welch EM 估參

3.1. E 步（前後向算法）：

• 算前向 alpha[t,k] = P(o_1,...,o_t, z_t=k | model) 以遞推：
  • alpha[1,k] = pi[k] * b_k(o_1)
  • alpha[t,k] = sum_j(alpha[t-1,j] * A[j,k]) * b_k(o_t)
• 算後向 beta[t,k] = P(o_{t+1},...,o_T | z_t=k, model)：
  • beta[T,k] = 1
  • beta[t,k] = sum_j(A[k,j] * b_j(o_{t+1}) * beta[t+1,j])
• 算態後驗 gamma[t,k] = P(z_t=k | O, model)：
  • gamma[t,k] = alpha[t,k] * beta[t,k] / P(O | model)
• 算轉移後驗 xi[t,i,j] = P(z_t=i, z_{t+1}=j | O, model)

3.2. M 步（參再估）：

• 更轉移陣：A[i,j] = sum_t(xi[t,i,j]) / sum_t(gamma[t,i])
• 以權充分統更放射參：
  • 高斯均：mu_k = sum_t(gamma[t,k] * o_t) / sum_t(gamma[t,k])
  • 高斯協：權散陣加正則
  • 離散：b_k(v) = sum_t(gamma[t,k] * I(o_t=v)) / sum_t(gamma[t,k])
• 更初分：pi[k] = gamma[1,k]

3.3. 算對數似然：log P(O | model) = log sum_k(alpha[T,k])。用 log-sum-exp 技以防下溢

3.4. 縮放： 長序用縮前後向變以防下溢。於各時步歸 alpha 並累對縮因

3.5. 重 E M 步至對數似然變於 convergence_tol 下或達 max_iterations

3.6. 諸重啟中留最高末對數似然之參組

得： 諸迭對數似然單調不減，於 max_iterations 內收斂。末參有效（行隨機陣、正定協）。

敗則： 若對數似然減，E 或 M 步有缺——驗式。若收斂極慢，試更佳初或增 max_iterations。若協奇，增正則。

第四步：施 Viterbi 解最可能態序

4.1. 初 Viterbi 變：

• delta[1,k] = log(pi[k]) + log(b_k(o_1))
• psi[1,k] = 0（無前）

4.2. 前遞 t = 2,...,T：

• delta[t,k] = max_j(delta[t-1,j] + log(A[j,k])) + log(b_k(o_t))
• psi[t,k] = argmax_j(delta[t-1,j] + log(A[j,k]))

4.3. 終：

• z*_T = argmax_k(delta[T,k])
• 最佳徑對數機率：max_k(delta[T,k])

4.4. 回溯 t = T-1,...,1：

• z*_t = psi[t+1, z*_{t+1}]

4.5. 出解態序 z* = (z*_1, ..., z*_T) 與其對數機率

4.6. 較 Viterbi 徑機率與前向總序機率以評最佳徑何多主

得： 單最可能態序長 T 各值於 {1,...,K}。Viterbi 對數機率不逾總對數似然。

敗則： 若 Viterbi 徑對數機率為負無窮，某轉或放射機率為零（不當）。加底值以防 log(0)。

第五步：作模擇（諸階之 BIC/AIC）

5.1. 於 state_range 各候 K，擬全 HMM（二至四步）

5.2. 算自由參數 p：

• 轉移陣：K * (K - 1)（各行為單純形）
• 放射參：依家（如 d 維全協高斯：K * (d + d*(d+1)/2)）
• 初分：K - 1

5.3. 算信息準：

• BIC = -2 * log_likelihood + p * log(T)
• AIC = -2 * log_likelihood + 2 * p
• AICc = AIC + 2*p*(p+1) / (T - p - 1)（小樣正）

5.4. 擇最低 BIC（偏一致）或 AIC（偏預測）之模。二者皆報

5.5. 列結：各 K 示對數似然、參數、BIC、AIC、收斂狀

5.6. 若最佳 K 於 state_range 邊，擴域重擬

得： BIC/AIC 有明最小示最佳隱態數。擇模宜已收斂且態義可釋。

敗則： 若無明最小（BIC 單調減），模或誤定——考異放射家。若諸模皆對數似然差，數或不循 HMM 構。

第六步：以留數與後驗解驗

6.1. 分數為訓與驗（如 80/20 或多序可用時）

6.2. 於訓擬模。於留以前向算法算對數似然（勿再擬參）

6.3. 後驗解（替 Viterbi）：

• 各時步賦最高後驗機率之態：z^_t = argmax_k(gamma[t,k])
• 此最大化正解態期數（對 Viterbi 之最大化聯徑機率）

6.4. 較 Viterbi 與後驗解：

• 算二解序之合率
• 不合區示態賦模糊

6.5. 評態可釋：

• 察各態放射參（均、方、離散分）
• 驗態合域脈絡中意勢
• 察態停時（A 對角暗）合理

6.6. 算每觀留對數似然並較諸模階以確訓集模擇

得： 留對數似然近訓對數似然（無重過擬）。Viterbi 與後驗解於 90%+ 時步合。諸態有辨可釋之放射分。

敗則： 若留似然遠差於訓，模過擬——減 K 或增正則。若態不可釋，試異初或異放射家。

驗

• 諸重啟 Baum-Welch 迭中對數似然單調不減
• 轉移陣行隨機（行和 1，諸項非負）
• 放射參於有效域（正定協、有效機率分）
• Viterbi 徑對數機率不逾總序對數機率
• BIC/AIC 曲於擇模階示明最小
• 留對數似然確模越訓集泛化
• 前向與後向機率算合：P(O) = sum_k(alpha[T,k]) = sum_k(pi[k] * b_k(o_1) * beta[1,k])

陷

• EM 局部最優：Baum-Welch 收斂於局部最大，非全局。恆多隨機重啟擇最佳
• 數下溢：前後向機率隨序長指減。以對空算或縮變防下溢至零
• 態過擬：各加隱態加 O(K + d^2) 參。用 BIC（非僅似然）作模擇並於留驗
• 籤換：隱態唯換可識。較諸啟模時以放射參配態，非以指數
• 退態：態或塌為解單觀（高斯近零方）。協陣正則防之
• 混 Viterbi 與後驗解：Viterbi 給單最佳聯徑；後驗解於各時步給最佳邊態。答異問可顯異
• 略態停時：標 HMM 暗幾何停時分或不合長勢數。若停時非幾何，考隱半馬可夫模

參

• Model Markov Chain — 先於解底隱層之轉構
• Simulate Stochastic Process — 可生合成 HMM 數供試，亦可自擬模擬以作後驗預察