--- tags: HMM, python, Bioinformatics --- # Backward Algorithm >本篇只會介紹程式碼,原理與更多解釋請參考[這裡](https://hackmd.io/@XibGbVrGSw6szTtbuQpNBw/HJdmQtqmj) ```python= def Backward(O, a, b): # init beta scaled_beta = np.zeros((O.shape[0], a.shape[0])) # scaled beta beta = np.zeros(a.shape[0]) C = np.zeros(O.shape[0]) # setting beta(T) = 1 scaled_beta[O.shape[0] - 1] = np.ones((a.shape[0])) # compute beta (from time t-1 to 1) for t in range(O.shape[0] - 2, -1, -1): for j in range(a.shape[0]): beta[j] = (scaled_beta[t + 1] * b[:, O[t + 1]]) @ a[j, :] C[t + 1] += beta[j] C[t + 1] = 1 / C[t + 1] scaled_beta[t, :] = beta * C[t + 1] return scaled_beta ``` ## 變數宣告與初始化 首先是宣告各種需要的參數並執行初始化 ```python= scaled_beta = np.zeros((O.shape[0], a.shape[0])) # scaled beta ``` 我們要計算的終極目標,為了解決underflow而產生的scaled_beta, 大小是row:狀態數量、column:序列長度的矩陣,基本上就是跟Forward裡的alpha一樣(畢竟差別只在於從前面算和後面算)。 > 和alpha相同,為了計算方便轉成直的 ```python= beta = np.zeros(a.shape[0]) C = np.zeros(O.shape[0]) ``` 初始化beta和C ## 迴圈計算beta ```python= for t in range(O.shape[0] - 2, -1, -1): for j in range(a.shape[0]): beta[j] = (scaled_beta[t + 1] * b[:, O[t + 1]]) @ a[j, :] C[t + 1] += beta[j] C[t + 1] = 1 / C[t + 1] scaled_beta[t, :] = beta * C[t + 1] ``` 從倒數第二格開始計算,套用公式計算beta,再用beta計算C。最後用計算出來的$C_{t+1}$來計算新的scaled_beta。