> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](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).

# 条件随机场的预测算法

条件随机场的预测问题是给定条件随机场$$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)$$