1 概率无向图模型

1.1 定义

又称 Markov 随机场.
回顾图 ${\displaystyle G=(V,E)}$ 由结点和边构成, 不考虑方向时为无向图. 概率图模型 是图表示的概率分布: 假设有概率分布 ${\displaystyle \mathbb{P}(Y),Y\in \mathcal{Y}}$. 在图 ${\displaystyle G}$ 中, 结点构成随机变量: ${\displaystyle Y=(Y_v{)}_{v\in V}}$; 边表示随机变量之间的概率依赖关系. 接下来定义几个性质:

• 成对 Markov 性: 任意没有边连接的结点 ${\displaystyle u,v}$, 对应随机变量 ${\displaystyle Y_u,Y_v}$, 其他结点的集合记为 ${\displaystyle O}$, 则有条件独立性: $$\mathbb{P}(Y_u,Y_v|Y_O)=\mathbb{P}(Y_u|Y_O)\mathbb{P}(Y_v|Y_O).$$
• 局部 Markov 性: ${\displaystyle \mathrm{\forall }v\in V}$, 所有与 ${\displaystyle v}$ 有边连接的结点记为 ${\displaystyle W}$, 此外的所有结点记为 ${\displaystyle O}$, 则 $$\mathbb{P}(Y_v,Y_O|Y_W)=\mathbb{P}(Y_v|Y_W)\mathbb{P}(Y_O|Y_W).$$ 由于 ${\displaystyle \mathbb{P}(Y_v,Y_O|Y_W)=\mathbb{P}(Y_O|Y_W)\mathbb{P}(Y_v|Y_O,Y_W)}$, 因此当 ${\displaystyle \mathbb{P}(Y_O|Y_W)>0}$, 等价于 $$\mathbb{P}(Y_v|Y_W)=\mathbb{P}(Y_v|Y_O,Y_W).$$
• 全局 Markov 性: 假设一个集合 ${\displaystyle C}$, 将 ${\displaystyle G}$ 中的结点分开后取任意两个集合 ${\displaystyle A,B}$, 则 $$\mathbb{P}(Y_A,Y_B|Y_C)=\mathbb{P}(Y_A|Y_C)\mathbb{P}(Y_B|Y_C).$$

这三个性质是等价的.

1.2 因子分解

因子分解 (factorization) 就是把 ${\displaystyle \mathbb{P}(Y)}$ 表示成最大团上随机变量的函数的积的操作. 也即 $$\mathbb{P}(Y)=\frac{1}{Z}\prod _C{\mathrm{\Psi }}_C(Y_C),$$ 这里 ${\displaystyle Z=\sum _Y\prod _C{\mathrm{\Psi }}_C(Y_C)}$ 是规范化因子, ${\displaystyle {\mathrm{\Psi }}_C(Y_C)}$ 是势函数需要恒正, 例如 ${\displaystyle {\mathrm{\Psi }}_C(Y_C)=\exp \{-\mathbb{E}(Y_C)\}}$. 它的存在性由 Hammersley-Clifford 定理保证.

2 条件随机场

2.1 定义

我们主要考虑一类特别的图: 线性链. 即 $$G=(V=\{1,\cdots ,n\},E=\{(i,i+1)\}),1\le i\le n-1.$$
定义对应的条件随机场:

在标注问题中, ${\displaystyle X}$ 表示输入观测序列, ${\displaystyle Y}$ 表示对应的输出标记序列.

2.2 参数化形式

对线性链条件随机场 ${\displaystyle \mathbb{P}(Y|X)}$ 进行因子分解:

2.3 简化形式

假设有 ${\displaystyle K_1}$ 个转移特征, ${\displaystyle K_2}$ 个状态特征, ${\displaystyle K=K_1+K_2}$, 将 ${\displaystyle t,s}$ 合并为 $$f_k(y_{i-1},y_i,x,i)=\{\begin{array}{rl}& t_k(y_{i-1},y_i,x,i),k=1,\cdots ,K_1,\\ & s_l(y_i,x,i),k=K_1+1,\cdots ,K.\end{array}$$
在所有位置 ${\displaystyle i}$ 求和: $$f_k(y,x)=\sum _{i=1}^n{f}_k(y_{i-1},y_i,x,i).$$ 将系数 ${\displaystyle {\lambda }_k,{\mu }_l}$ 也统一表示为 ${\displaystyle w_k,1\le k\le K}$. 因此 (2.1) 表示为 $$\begin{array}{}\text{(2.2)}& \mathbb{P}(y|x)=\frac{1}{Z(x)}\exp \sum _{k=1}^K{w}_k{f}_k(y,x).\end{array}$$
最后定义向量表示 ${\displaystyle w=(w_1,\cdots ,w_K{)}^{\mathrm{T}},F(y,x)=(f_1(y,x),\cdots ,f_K(y,x){)}^{\mathrm{T}}}$, 则 $${\mathbb{P}}_w(y|x)=\frac{\exp (w\cdot F(y,x))}{Z_w(x)},Z_w(x)=\sum _y\exp (w\cdot F(y,x)).$$

2.4 矩阵形式

在标记序列 ${\displaystyle \{y_i\}}$ 中额外加入 ${\displaystyle y_0,y_{n+1}}$ 表示起始和终止状态. 基于上面的简化形式, 定义矩阵 $$M_i(x)=[M_i(y_{i-1},y_i|x)],$$ 其中 $$\begin{array}{rl}{M}_i(y_{i-1},y_i|x)& =\exp (W_i(y_{i-1},y_i|x)),\\ W_i(y_{i-1},y_i|x)& =\sum _{k=1}^K{w}_k{f}_k(y_{i-1},y_i,x,i).\end{array}$$
这样$$\begin{array}{rl}{\mathbb{P}}_w(y|x)& =\frac{1}{Z_w(x)}\exp (\sum _{k=1}^K{w}_k{f}_k(y,x))\\ & =\frac{1}{Z_w(x)}\exp (\sum _{k=1}^K\sum _{i=1}^n{w}_k{f}_k(y_{i-1},y_i,x,i))\\ & =\frac{1}{Z_w(x)}\exp (\sum _{i=1}^n{W}_i(y_{i-1},y_i|x))\\ & =\frac{1}{Z_w(x)}\prod _{i=1}^{n+1}{M}_i(y_{i-1},y_i|x),\end{array}$$ ${\displaystyle Z_w(x)}$ 是规范化因子 ${\displaystyle [M_1(x)\cdots M_{n+1}(x){]}_{\mathrm{start},\mathrm{stop}}}$, 恰恰就是所有从 start 出发到 stop, 经过所有 ${\displaystyle y_1,\cdots ,y_n}$ 的概率 ${\displaystyle \prod _{i=1}^{n+1}{M}_i(y_{i-1},y_i|x)}$ 之和.

3 概率计算问题

给定 ${\displaystyle \mathbb{P}(Y|X)}$, 输入 ${\displaystyle x}$ 和输出 ${\displaystyle y}$, 计算 ${\displaystyle \mathbb{P}(Y_i=y_i|x),\mathbb{P}(Y_{i-1}=y_{i-1},Y_i=y_i|x)}$ 以及相应的数学期望.

3.1 前向后向算法 概率计算

定义前向向量 $${\alpha }_0(y_0|x)=\{\begin{array}{rl}& 1,y_0=\mathrm{start},\\ & 0,\mathrm{else},\end{array}$$ 然后定义 $${\alpha }_i^{\mathrm{T}}(y_i|x)={\alpha }_{i-1}^{\mathrm{T}}(y_{i-1}|x)[M_i(y_{i-1},y_i|x)],i=1,\cdots ,n+1,$$ 即 $${\alpha }_i^{\mathrm{T}}(x)={\alpha }_{i-1}^{\mathrm{T}}(x)M_i(x).$$
这里 ${\displaystyle {\alpha }_i(y_i|x)}$ 表示从 1 走到 ${\displaystyle i}$, 在位置 ${\displaystyle i}$ 的标记是 ${\displaystyle y_i}$; ${\displaystyle {\alpha }_i(x)\in {\mathbb{R}}^m}$ (${\displaystyle m}$ 是 ${\displaystyle y_i}$ 的可能取值个数) 的概率. 类似地定义后向向量 $${\beta }_{n+1}(y_{n+1}|x)=\{\begin{array}{rl}& 1,y_{n+1}=\text{stop},\\ & 0,\text{else},\end{array}$$

由此 $$\begin{array}{}\text{(3.1)}& & \mathbb{P}(Y_i=y_i|x)=\frac{{\alpha }_i^{\mathrm{T}}(y_i|x){\beta }_i(y_i|x)}{Z(x)},\text{(3.2)}& & \mathbb{P}(Y_{i-1}=y_{i-1},Y_i=y_i|x)=\frac{{\alpha }_{i-1}^{\mathrm{T}}(y_{i-1}|x)M_i(y_{i-1},y_i|x){\beta }_i(y_i|x)}{Z(x)},\end{array}$$
其中 ${\displaystyle Z(x)={\alpha }_n^{\mathrm{T}}(x)\mathbf{1}=\mathbf{1}{\beta }_1(x)}$.

3.2 期望计算

首先计算特征函数 ${\displaystyle f_k}$ 关于条件分布 ${\displaystyle \mathbb{P}(Y|X)}$ 的数学期望. 应用 (3.2): $$\begin{array}{rl}{\mathbb{E}}_{\mathbb{P}(Y|X)}[f_k]& =\sum _y\mathbb{P}(y|x)f_k(y,x)\\ & =\sum _{i=1}^{n+1}\sum _{y_{i-1}{y}_i}{f}_k(y_{i-1},y_i,x,i)\frac{{\alpha }_{i-1}^{\mathrm{T}}(y_{i-1}|x)M_i(y_{i-1},y_i|x){\beta }_i(y_i|x)}{Z(x)}\end{array}$$
假设经验分布为 ${\displaystyle \tilde{P}(X)}$, 则 ${\displaystyle f_k}$ 关于 ${\displaystyle P(X,Y)}$ 的期望为 $$\begin{array}{rl}{\mathbb{E}}_{P(X,Y)}[f_k]& =\sum _{x,y}P(x,y)\sum _{i=1}^{n+1}{f}_k(y_{i-1},y_i,x,i)\\ & =\sum _x\tilde{P}(x)\sum _{y}P(y|x)\sum _{i=1}^{n+1}{f}_k(y_{i-1},y_i,x,i)\\ & =\sum _x\tilde{P}(x)\sum _{i=1}^{n+1}\sum _{y_{i-1},y_i}{f}_k\frac{{\alpha }_{i-1}^{\mathrm{T}}{M}_i{\beta }_i}{Z(x)}.\end{array}$$

4 学习算法

4.1 改进的迭代尺度法

假设我们根据训练集得到经验分布 ${\displaystyle \tilde{P}(X,Y)}$, 则对数似然 $$L(w)=L_{\tilde{P}}(P_w)=\log \prod _{x,y}{P}_w(y|x{)}^{\tilde{P}(x,y)}=\sum _{x,y}\tilde{P}(x,y)\log P_w(y|x).$$ 而若 ${\displaystyle P}$ 由因子分解式给出: $$\begin{array}{rl}L(w)& =\sum _{x,y}[\tilde{P}(x,y)\sum _{k=1}^K{w}_k{f}_k(y,x)-\tilde{P}(x,y)\log Z_w(x)]\\ & =\sum _{j=1}^N\sum _{k=1}^K{w}_k{f}_k(y_j,x_j)-\sum _{j=1}^N\log Z_w(x_j)\end{array}$$
为了高效地道对数似然的极大值, 采用迭代的方法不断优化对数似然函数改变量的下界. 假设当前参数为 ${\displaystyle w=(w_1,\cdots ,w_K{)}^{\mathrm{T}}}$, 更新增量为 ${\displaystyle \delta =({\delta }_1,\cdots ,{\delta }_K{)}^{\mathrm{T}}}$, 则需要求解以下方程(对转移和状态特征分别给出): $$\begin{array}{rl}{\mathbb{E}}_{\tilde{P}}[t_k]& =\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{t}_k(y_{i-1},y_i,x,i)\\ \text{(4.1)}& & =\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)),\end{array}$$ 以及 $$\begin{array}{}\text{(4.2)}& {\mathbb{E}}_{\tilde{P}}[s_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)),\end{array}$$ 这里 ${\displaystyle T}$ 是 ${\displaystyle (x,y)}$ 中出现的特征数总和 $$\begin{array}{}\text{(4.3)}& 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).\end{array}$$

这里 ${\displaystyle T(x,y)}$ 对不同的 ${\displaystyle (x,y)}$ 取值可能不同. 为此, 定义松弛特征 $$s(x,y)=S-\sum _{i=1}^{n+1}\sum _{k=1}^K{f}_k(y_{i-1},y_i,x,i).$$ 选取足够大的常数 ${\displaystyle S}$ 使 ${\displaystyle s(x,y)\ge 0}$ 恒成立, 则特征总数取 ${\displaystyle S}$. 此时 (4.1) 变为 $$\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}S)={\mathbb{E}}_{\tilde{P}}[t_k],$$ 其中$$\begin{array}{rl}{\delta }_k& =\frac{1}{S}\log \frac{{\mathbb{E}}_{\tilde{P}}[t_k]}{{\mathbb{E}}_P[t_k]},\\ {\mathbb{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}^{\mathrm{T}}(y_{i-1}|x)M_i(y_{i-1},y_i|x){\beta }_i(y_i|x)}{Z(x)},\end{array}$$ 同理有状态部分的方程改写, 其中 $${\mathbb{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^{\mathrm{T}}(y_i|x){\beta }_i(y_i|x)}{Z(x)}.$$
在上述算法中, ${\displaystyle S}$ 由于要取得足够大, 则 ${\displaystyle \delta }$ 增大, 收敛变慢. 为此计算 $$T(x)=\underset{y}{max}T(x,y)=t$$ (由前向后向递推公式看出). 此时更新方程进一步改写为$$\begin{array}{rl}{\mathbb{E}}_{\tilde{P}}[t_k]& =\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{array}$$ 这里 ${\displaystyle {\delta }_k=\log {\beta }_k}$, 可以用牛顿法求得 ${\displaystyle {\beta }_k}$. 类似地 $${\mathbb{E}}_{\tilde{P}}[s_l]=\sum _{t=0}^{T_{\max }}{b}_{l,t}{\gamma }_l^t,{\delta }_l=\log {\gamma }_l.$$

4.2 拟牛顿法

回顾模型 (2.2), 优化目标函数为 $$\underset{w\in {\mathbb{R}}^n}{min}f(w)=\sum _x\tilde{P}(x)\log \sum _y\exp \sum _{i=1}^n{w}_i{f}_i(x,y)-\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{w}_i{f}_i(x,y),$$ 梯度函数为 $$g(w)=\sum _{x,y}\tilde{P}(x)P_w(y|x)f(x,y)-{\mathbb{E}}_{\tilde{P}}(f).$$
参考 BFGS算法:

5 预测算法

给定 ${\displaystyle P(Y|X)}$ 和输入序列 ${\displaystyle x}$, 求条件概率最大的输出序列 ${\displaystyle y^{\ast }}$. 注意到 $$y^{\ast }=\arg \underset{y}{max}{P}_w(y|x)=\arg \underset{y}{max}\frac{\exp (w\cdot F(y,x))}{Z_w(x)}=\arg \underset{y}{max}(w\cdot F(y,x)).$$ 等价于求解以下问题 $$\underset{y}{max}\sum _{i=1}^{n}w\cdot F_i(y_{i-1},y_i,x),$$ 其中 ${\displaystyle F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_i,x,i),\cdots ,f_K(y_{i-1},y_i,x,i){)}^{\mathrm{T}}}$ 是局部特征向量.