# 前向算法

前向算法与后向算法用来计算**观测序列**概率$$P(O|\lambda)$$, 即以当前的HMM产生指定的观测序列$$O$$的概率.

## 前向算法

* **前向概率/部分概率**: 对于给定的隐马尔可夫模型$$\lambda$$, 定义为$$t$$时刻部分观测序列为$$o\_1$$, $$o\_2$$, ..., $$o\_t$$且当前状态为$$q\_i$$的概率. 即在给定观测序列的情况下, $$t$$时刻到达某一中间状态的概率. 记为:

  $$\alpha\_t(i)=P(o\_1,o\_2,...,o\_t,i\_t=q\_i|\lambda), i=1,2,...,N$$
* **观测序列概率的前向算法**
  1. 初始状态, 对于每一个状态, 都是直接指定的, 没有路径到达, 因此定义初始状态的前向概率为:

     $$\alpha\_1(i)=\pi\_ib\_i(o\_1), i=1,2,...,N$$
  2. **递推**获得中间某一时刻某个状态下的前向概率. 计算方法如下

     $$\alpha\_t(i)=P(observation|hidden\ state\ is\ i)\*P(all\ paths\ to\ state\ i\ at\ time\ t)$$

     前者是从**混淆矩阵**中得到的, 后者表示到达$$t$$时刻状态所经过的**所有可能路径之和**的概率, 如图所示:

     ![image](/files/-MI7Nmffo1En0tVpGMAc)

     由于我们已经计算得到了$$t$$时刻任一状态的**前向概率**, 因此在计算$$t+1$$时刻的某一状态的前向概率只需要考虑$$t$$时刻就可以了, 因此有递推公式:

     $$\alpha\_{t+1}(i)=\[\sum\_{j=1}^{N}\alpha\_t(j)a\_{ji}]b\_i(o\_{t+1}), i=1,2,...,N$$

     这个式子含义为: 当前观察概率(状态$$i$$下, $$t+1$$时刻所真正看到的观察状态的概率)乘以此时所有到达该状态的概率和(前一时刻所有状态的概率与相应的转移概率的积).
  3. **观测序列的概率**

     观测序列$$O$$的概率$$P(O|\lambda)$$可以由下式得出:

     $$P(O|\lambda)=\sum\_{i=1}^{N}\alpha\_T(i)$$

     即最后的$$T$$时刻所有状态的前向概率之和. 这是由于:

     $$\alpha\_T(i)=P(o\_1,o\_2,...,o\_T,i\_T=q\_i|\lambda)$$

     因此, 将所有的$$T$$时刻的概率加起来就有

     $$P(O|\lambda)=\sum\_{i=1}^{N}\alpha\_T(i)=P(o\_1,o\_2,...,o\_T|\lambda)$$
* **时间复杂度**

  HMM的前向算法的时间复杂度为$$O(N^2T)$$, 其中$$N$$为状态的数量, $$T$$为时序的长度, 前向算法的时间复杂度是$$T$$的**线性级别**.
* **作用**

  前向算法可以用来计算观测序列概率$$P(O|\lambda)$$, 因此如第一节HMM作用的第一条**评估**所说, 根据观测到的序列, 使用不同的已经固定参数的HMM进行评估, 选取观测概率最大的模型. 每个模型都代表着一定的意义, 模型观测序列符合这个HMM代表的某种意义.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/ji-qi-xue-xi/gai-shuai-tu-mo-xing/sheng-cheng-shi-mo-xing/hmm/qian-xiang-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.