CRF模型参数求解

背景

之前有一篇文章介绍了CRF模型，但是没有具体讲述怎么求得CRF模型的参数，只说明了可以使用最大熵模型参数的求解方法去求解CRF模型的参数，主要有GIS和IIS等方法。本文主要介绍使用梯度下降法求解CRF模型参数。

求解过程

我们有一堆数据样本$(X,Y)$，现在我们要求最大似然：

$$L(w)=\log\prod_{x,y}P_{w}(y|x)^{\hat{P}(x,y)}=\sum_{x,y}\hat{P}(x,y)\log P_{w}(y|x)$$

上面这条式子是统计数据集$(X,Y)$在已知$X$的情况下的最大似然，根据CRF模型，我们知道：

$$P_w(y|x)=\frac{1}{Z(x)}\exp(\sum_{k}w_kf_k(x,y))$$ $$Z(x)=\sum_y\exp(\sum_kw_kf_k(x,y))$$

极大化最大似然等于极小化目标函数，有：

$$f(w)=-\sum_{x,y}\hat{P}(x,y)\log P_w(y|x)\\=\sum_{x,y}\hat{P}(x,y)\log Z(x)-\sum_{x,y}\hat{P}(x,y)\sum_kw_kf_k(x,y)\\=\sum_x\hat{P}(x)\log (\sum_y\exp(\sum_kw_kf_k(x,y)))-\sum_{x,y}\hat{P}(x,y)\sum_kw_kf_k(x,y)$$

上式对$w$求导得到：

$$\frac{\partial f(w)}{\partial w_k}=\sum_{x,y}\hat{P}(x,y)P_w(y|x)f_k(x,y)-\sum_{x,y}\hat{P}(x,y)f_k(x,y)$$

以上就是对$w$求导的式子，利用这个式子求得梯度，然后利用梯度更新模型参数，直到模型收敛求得最大似然的极大值。

编解码过程

如果是线性的图，可以使用动态规划的方法进行编解码；如果是一些特殊的图，可以使用一些特殊设计的方法进行编解码；如果是复杂的图，可以使用一些启发式算法，比如遗传算法，模拟退火算法等进行编解码。

概率估计过程

如果是线性的图，可以使用动态规划的方法进行概率估计；如果是一些特殊的图，可以使用一些特殊设计的方法进行概率估计；如果是复杂的图，可以使用一些采样估计方法进行概率估计。