# 条件随机场的预测算法

条件随机场的预测问题是给定条件随机场$$P(Y|X)$$和输入序列(观测序列)$$x$$, 求条件概率最大的输出序列(标记序列)$$y^\*$$(例如应用在对观测序列进行标注的问题上).

条件随机场的预测算法与HMM一样, 都是采用**维特比算法**.

## 维特比算法

由条件随机场的简化(向量)表示形式得:

$$\begin{aligned} y^\* &= \arg\max\limits\_{y}P\_w(y|x) \ &= \arg\max\limits\_{y}\frac{\exp\left(\textbf{w}\cdot{F(y,x)}\right)}{Z\_w(x)} \ &= \arg\max\limits\_{y}\exp\left(\textbf{w}\cdot{F(y,x)}\right) \ &= \arg\max\limits\_{y}\left(\textbf{w}\cdot{F(y,x)}\right) \end{aligned}$$

其中:

$$\textbf{w}=(w\_1,w\_2,\cdots,w\_K)^T$$

$$\textbf{F}(y,x)=(f\_1(y,x),f\_2(y,x),\cdots,f\_K(y,x))^T$$

$$f\_k(y,x)=\sum\limits\_{i=1}^{n}f\_k(y\_{i-1},y\_{i},x,i),\ k=1,2,\cdots,K$$

于是, 条件随机场的预测问题就称为求非规范化概率最大的最优路径问题.

$$\max\limits\_{y}\left(\textbf{w}\cdot{F(y,x)}\right)$$

这时, 就只需要计算非规范化概率, 不必计算概率, 可以大大提高效率, 将上式写成如下形式:

$$\max\limits\_{y}\sum\limits\_{i=1}^{n}\textbf{w}\cdot{F\_i(y\_{i-1},y\_i,x)}$$

其中$$F\_i$$是一个长度为$$K$$的**局部特征向量**:

$$F\_i(y\_{i-1},y\_i,x)=(f\_1(y\_{i-1},y\_{i},x,i),f\_2(y\_{i-1},y\_{i},x,i),\cdots,f\_K(y\_{i-1},y\_{i},x,i))^T$$

维特比算法如下进行:

对于位置1的各个标记($$y\_1$$取值的所有可能)$$j=1,2,\cdots,m$$的非规范化概率为:

$$\delta\_1(j)=\textbf{w}F\_1(y\_0=\text{start},y\_1=j,x),\ j=1,2,\cdots,m$$

由地推公式, 求出各个位置$$i$$的各个标记$$j=1,2,\cdots,m$$的非规范化概率的最大值, 同时记录非规范化概率最大值的路径:

$$\delta\_i(l)=\max\limits\_{1\le{j}\le{m}}\left{\delta\_{i-1}(j)+\textbf{w}F\_i(y\_{i-1}=j,y\_i=l,x)\right}$$

对应的路径为:

$$\Phi\_i(l)=\arg\max\limits\_{1\le{j}\le{m}}\left{\delta\_{i-1}(j)+\textbf{w}F\_i(y\_{i-1}=j,y\_i=l,x)\right}$$

迭代直到$$i=n$$时终止. 此时求得的非规范化概率的最大值为:

$$\max\limits\_{y}\left(\textbf{w}\cdot{F(y,x)}\right)=\max\limits\_{1\le{j}\le{m}}\delta\_n(j)$$

及最优路径的终点:

$$y\_n^\*=\arg\max\limits\_{1\le{j}\le{m}}\delta\_n(j)$$

由最优路径的终点返回:

$$y\_i^*=\Phi\_{i+1}(y\_{i+1}^*),\ i=n-1,n-2,\cdots,1$$

得到最优路径$$y^*=(y^*\_1,y^*\_2,\cdots,y^*\_n)$$

### 条件随机场预测的维特比算法

* 输入:
  * 特征向量$$F(x,y)$$
  * 条件随机场权值向量$$w$$
  * 观测序列$$x=(x\_1,x\_2,\cdots,x\_n)$$
* 输出:
  * 最优路径$$y^*=(y^*\_1,y^*\_2,\cdots,y^*\_n)$$
* 过程
  * 初始化

    $$\delta\_1(j)=\textbf{w}F\_1(y\_0=\text{start},y\_1=j,x),\ j=1,2,\cdots,m$$
  * 递推, 对$$i=1,2,\cdots,n$$

    $$\delta\_i(l)=\max\limits\_{1\le{j}\le{m}}\left{\delta\_{i-1}(j)+\textbf{w}F\_i(y\_{i-1}=j,y\_i=l,x)\right},\ l=1,2,\cdots,m$$

    $$\Phi\_i(l)=\arg\max\limits\_{1\le{j}\le{m}}\left{\delta\_{i-1}(j)+\textbf{w}F\_i(y\_{i-1}=j,y\_i=l,x)\right},\ l=1,2,\cdots,m$$
  * 终止

    $$\max\limits\_{y}\left(\textbf{w}\cdot{F(y,x)}\right)=\max\limits\_{1\le{j}\le{m}}\delta\_n(j)$$

    $$y\_n^\*=\arg\max\limits\_{1\le{j}\le{m}}\delta\_n(j)$$
  * 返回路径

    $$y\_i^*=\Phi\_{i+1}(y\_{i+1}^*),\ i=n-1,n-2,\cdots,1$$

    求得最优路径: $$y^*=(y^*\_1,y^*\_2,\cdots,y^*\_n)$$


---

# 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/pan-bie-shi-mo-xing/crf/tiao-jian-sui-ji-chang-de-yu-ce-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.