条件随机场的学习

【概述】

对于线性链条件随机场的学习问题，即：已知线性链条件随机场 $P(Y|X)$，估计 $P(Y|X)$ 的参数，该问题本质上是无监督学习中的概率估计问题

其学习方法有改进的迭代尺度法 IIS、梯度下降法、拟牛顿法等，这里仅介绍使用改进的迭代尺度法 IIS 和拟牛顿法对线性链条件随机场的学习

【改进的迭代尺度法】

对数似然函数

若已知训练集，那么可知经验概率分布 $\tilde{P}(X,Y)$，那么就可以通过极大化训练数据的对数似然函数来求模型参数

根据极大似然估计，训练数据的对数似然函数为：

$$\begin{align*} L({\mathbf{w}}) &= L_{\tilde{P}}(P_{\mathbf{w}}) \\ &= \log \prod_{x,y} P_{\mathbf{w}}(y|x)^{\tilde{P}(X,Y)} \\ &= \sum_{x,y} \tilde{P}(x,y)\log P_{\mathbf{w}}(y|x) \end{align*}$$

当 $P_{\mathbf{w}}$ 是由下式给出的线性链条件随机场时

$$\begin{align*} P(y|x) &= \frac{1}{Z(x)} \exp \sum_{k=1}^K w_k f_k(y,x) \\ Z(x) &= \sum_{y} \exp \sum_{k=1}^K w_k f_k(y,x) \end{align*}$$

对数似然函数为：

$$\begin{align*} L({\mathbf{w}}) &= \sum_{x,y} \tilde{P}(x,y) \log P_{\mathbf{w}}(y|x) \\ &= \sum_{x,y} \bigg[ \tilde{P}(x,y) \sum_{k=1}^K w_k f_k(y,x) - \tilde{P}(x,y) \log Z_{\mathbf{w}} (x) \bigg] \\ &= \sum_{j=1}^N \sum_{k=1}^K w_k f_k(y_j,x_j) - \sum_{j=1}^N \log Z_\mathbf{w}(x_j) \end{align*}$$

更新方程

改进的迭代尺度法 IIS 是通过迭代的方法，不断优化对数似然函数改变量的下界，极大化对数似然函数

假设模型的当前参数向量 $\mathbf{w}=(w_1,w_2,\cdots,w_K)^T$，向量的增量 $\boldsymbol{\delta}=(\delta_1,\delta_2,\cdots,\delta_K)^T$，则更新参数向量为：

$$\mathbf{w}+\boldsymbol{\delta} = (w_1+\delta_1,w_2+\delta_2,\cdots,w_K+\delta_K)^T$$

根据 IIS，关于转移特征 $t_k$，$\delta_k$ 的更新方程为：

$$\begin{align*} E_{\tilde{P}}[t_k] &= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,x,i) \\ &= \sum_{x,y} \tilde{P}(x) P(y|x) \sum_{i=1}^{n+1} t_k (y_{i-1},y_i,x,i) \exp[\delta_k T(x,y)] \\ &k=1,2,\cdots,K_1 \end{align*}$$

关于状态特征 $s_k$，$\delta_k$ 的更新方程为：

$$\begin{align*} E_{\tilde{P}}[s_l] &= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n+1} s_l(y_{i},x,i) \\ &= \sum_{x,y} \tilde{P}(x) P(y|x) \sum_{i=1}^{n} s_l(y_i,x,i) \exp[\delta_{K_1+l} T(x,y)] \\ &l=1,2,\cdots,K_2 \end{align*}$$

其中，$T(x,y)$ 是在数据 $(x,y)$ 中出现的所有特征数的总和，即：

$$T(x,y) = \sum_{k}f_k(y,x)=\sum_{k=1}^{K} \sum_{i=1}^{n+1} f_k(y_{i-1},y_i,x,i)$$

算法 S

$T(x,y)$ 是在数据 $(x,y)$ 中的特征总数，但对于不同的数据 $(x,y)$，取值可能不同，为此，定义松弛特征：

$$s(x,y) = S-\sum_{i=1}^{n+1}\sum_{k=1}^K f_{k}(y_{i-1},y_i,x,i)$$

其中，$S$ 是一个常数，选择足够大的 $S$ 时，会使得对训练集中的所有数据 $(x,y)$ 满足 $s(x,y)\geq 0$，此时特征总数 $T(x,y)=S$

那么，对于转移特征 $t_k$，$\delta_k$ 的更新方程为：

$$\begin{gather} \sum\limits_{x,y} \tilde{P}(x) P(y|x) \sum\limits_{i=1}^{n+1} t_k (y_{i-1},y_i,x,i) \exp[\delta_k S] = E_{\tilde{P}}[t_k] \\ \delta_k = \frac{1}{S} \log \frac{E_{\tilde{P}}[t_k]}{E_[t_k]} \end{gather}$$

其中，$E_{P}[t_k] $ 为：

$$E_{P}[t_k] = \sum_{x} \tilde{P}(x) \sum_{i=1}^{n+1} \sum_{y_{i-1},y_i} t_k(y_{i-1},y_i,x,i) \frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}$$

同理，对于状态特征 $s_l$，$\delta_k$ 的更新方程为：

$$\begin{gather} \sum_{x,y} \tilde{P}(x) P(y|x) \sum_{i=1}^{n} s_l(y_i,x,i) \exp[\delta_{K_1+l} S] = E_{\tilde{P}}[s_l] \\ \delta_{K_1+l} = \frac{1}{S} \log \frac{E_{\tilde{P}}[s_l]}{E_{P}[s_l]} \end{gather}$$

其中，$E_{P}[s_l] $ 为：

$$E_{P}[s_l] = \sum_{x} \tilde{P}(x) \sum_{i=1}^{n} \sum_{y_i} s_l(y_i,x,i) \frac{\alpha_{i}^T(y_{i}|x)\beta_i(y_i|x)}{Z(x)}$$

算法 T

在算法 S 中，需要使常数 $S$ 足够大，但这样一来，每步迭代的增量向量会变大，算法收敛会变慢

为解决该问题，提出了算法 T，即对每个观测序列 $x$ 计算其特征总数最大值：

$$T(x) = \max_y T(x,y)$$

利用前向-后向递推公式，可计算出 $T(x)=t$

此时，对于转移特征 $t_k$，$\delta_k$ 的更新方程为：

$$\begin{align*} E_{\tilde{P}}[t_k] &= \sum\limits_{x,y} \tilde{P}(x) P(y|x) \sum\limits_{i=1}^{n+1} t_k (y_{i-1},y_i,x,i) \exp[\delta_k T(x)] \\ &= \sum_{x} \tilde{P}(x) \sum_y P(y|x) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,x,i) \exp[\delta_k T(x)] \\ &= \sum_x \tilde{P}(x) a_{k,t} \exp(\delta_k t) \\ &= \sum_{t=0}^{T_{\max}} a_{k,t}\beta_{k}^t \end{align*}$$

其中，$a_{k,t}$ 是 $t_k$ 的期待值，$\delta_k=\log \beta_k$，$\beta_k$ 是上述多项式方程的唯一实根，可用牛顿法求得，进而求得相关的 $\delta_k$

同理，关于状态特征 $s_l$，$\delta_k$ 的更新方程为：

$$\begin{align*} E_{\tilde{P}}[s_l] &= \sum\limits_{x,y} \tilde{P}(x) P(y|x) \sum\limits_{i=1}^{n} s_l (y_i,x,i) \exp[\delta_{K_1+l} T(x)] \\ &= \sum_{x} \tilde{P}(x) \sum_y P(y|x) \sum_{i=1}^{n} s_l(y_i,x,i) \exp[\delta_{K_{1}+l} T(x)] \\ &= \sum_x \tilde{P}(x) b_{l,t} \exp(\delta_k t) \\ &= \sum_{t=0}^{T_{\max}} b_{l,t}\gamma_{l}^t \end{align*}$$

其中，$b_{l,t}$ 是 $s_l$ 的期待值，$\delta_k=\log \gamma_l$，$\gamma_l$ 是上述多项式方程的唯一实根，可用牛顿法求得，进而求得相关的 $\delta_k$

算法流程

综上所述，下面给出线性链条件随机场学习的改进的迭代尺度法的算法流程

输入：特征函数 $t_1,t_2,\cdots,t_{K_1},s_1,s_2,\cdots,s_{K_2}$，经验分布 $\tilde{P}(x,y)$

输出：参数估计值 $\hat{\mathbf{w}}$，模型 $P_{\hat{\mathbf{w}}}(y|x)$

算法步骤：

Step 1：算法初始化，对所有的 $k\in \{ 1,2,\cdots,K \}$，取初值 $w_k=0$

Step 2：对每一 $k\in \{ 1,2,\cdots,K \}$

1）当 $k=1,2,\cdots,K_1$ 时，令 $\delta_k$ 是下述方程的解

$$\sum_{x,y} \tilde{P}(x) P(y|x) \sum_{i=1}^{n+1} t_k (y_{i-1},y_i,x,i) \exp[\delta_k T(x,y)] = E_{\tilde{P}}[t_k]$$

其中，$T(x,y)$ 可采取算法 S，亦可采取算法 T

2）当 $k=K_{1}+l,l=1,2,\cdots,K_2$ 时，令 $\delta_{K_1+l}$ 是下述方程的解

$$\sum_{x,y} \tilde{P}(x) P(y|x) \sum_{i=1}^{n} s_l(y_i,x,i) \exp[\delta_{K_1+l} T(x,y)] = E_{\tilde{P}}[s_l]$$

其中，$T(x,y)$ 可采取算法 S，亦可采取算法 T

3）更新 $w_{k}$ 的值

$$w_k := w_{k}+\delta_k$$

Step 3：若不是所有的 $w_k$ 都收敛，重复 Step 2

【拟牛顿法】

线性链条件随机场的学习，还可采用牛顿法或拟牛顿法

目标优化函数

对于线性链随机场模型：

$$\begin{align*} P_{\mathbf{\mathbf{w}}}(y|x) &= \frac{1}{Z(x)} \exp \sum_{k=1}^K w_k f_k(y,x) \\ Z(x) &= \sum_{y} \exp \sum_{k=1}^K w_k f_k(y,x) \end{align*}$$

学习的优化目标函数为：

$$\min_{\mathbf{w}\in \mathbb{R}^n} f(\mathbf{w}) = \sum_{x}\tilde{P}(x) \log \sum_y \exp \sum_{k=1}^K w_k f_k(x,y) - \sum_{x,y} \tilde{P}(x,y) \sum_{k=1}^{K} w_i f_i(x,y)$$

其梯度函数为：

$$g(\mathbf{w}) = \sum_{x,y} \tilde{P}(x) P_{\mathbf{w}}(y|x) f(x,y)-E_{\tilde{P}}[f]$$

算法流程

基于目标优化函数，下面仅给出线性链条件随机场学习的 BFGS 算法 的算法流程

输入：特征函数 $f_1,f_2,\cdots,f_n$，经验分布 $\tilde{P}(X,Y)$

输出：参数估计值 $\hat{\mathbf{w}}$，模型 $P_{\hat{\mathbf{w}}}(y|x)$

算法步骤：

Step 1：算法初始化，选定初始点 $\mathbf{w}^{(0)}$，取初始近似矩阵 $B_0$ 为正定对称矩阵，并令 $k=0$

Step 2：计算梯度向量 $\mathbf{g_k} = g(\mathbf{w}^{(k)})$，若 $\mathbf{g_k}=0$，停止计算

Step 3：由 $B_k\mathbf{p_k}=-\mathbf{g_k}$，求出搜索方向 $\mathbf{p}_k$

Step 4：求步长 $\lambda_k$，使得

$$f(\mathbf{w}^{(k)}+\lambda_k \mathbf{p_k}) = \min_{\lambda\geq 0} f(\mathbf{w}^{(k)}+\lambda \mathbf{p_k})$$

Step 5：令 $\mathbf{w}^{(k+1)}=\mathbf{w}^{(k)}+\lambda_k \mathbf{p}_k$

Step 6：计算 $\mathbf{g_{k+1}}=g(\mathbf{w}^{(k+1)})$，若 $\mathbf{g_{k+1}}=0$，停止计算

Step 7：计算第 $k+1$ 步的近似矩阵 $B_{k+1}$

$$B_{k+1} = B_k + \frac{\mathbf{y_k} \mathbf{y_k}^T}{\mathbf{y_k}^T \boldsymbol{\delta_k}} - \frac{B_k\boldsymbol{\delta_k}\boldsymbol{\delta_k}^T B_k}{\boldsymbol{\delta_k}^T B_k \boldsymbol{\delta_k}}$$

其中，$\mathbf{y_k}$ 为两次迭代的梯度差

$$\mathbf{y_k}=\mathbf{g_{k+1}}-\mathbf{g_k}$$

$\boldsymbol{\delta_k}$ 为两次迭代估计值的差

$$\mathbf{\delta_k}=\mathbf{w}^{(k+1)}-\mathbf{w}^{(k)}$$