---
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。