条件随机场2021-09-26

条件随机场概述

条件随机场（conditional random field, CRF）是一种条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。对于线性链条件随机场，其问题变成了由输入序列对输出序列预测的判别模型，形式为对数线性模型，学习方法通常是极大似然估计或正则化的极大似然估计。

概率无向图模型

概率无向图模型，又称为马尔可夫随机场，是一个可以由无向图表示的联合概率分布。

$补充：有向图则对应贝叶斯网络。$

基本概念

图 $v$ $e$ $V$ $E$ $G=(V,E)$ 。无向图是指边没有方向的图。

概率图模型 $P(Y)$ $Y \in \mathcal{Y}$ $P(Y)$ $G=(V,E)$ $G$ $v \in V$ $Y_v$ $Y=(Y_v)_{v \in V}$ $e$ 表示随机变量之间的概率依赖关系。

三种马尔可夫性

$P(Y)$ $G$ 。对无向图表示的随机变量之间存在的马尔可夫性进行定义，马尔可夫性包括成对马尔可夫性、局部马尔可夫性、全局马尔可夫性，并且，这三种独立性是等价的。

成对马尔可夫性

成对马尔可夫性

$u$ $v$ $G$ $u$ $v$ $Y_u$ $Y_v$ $O$ $Y_O$ $Y_O$ $Y_u$ $Y_v$ 是条件独立的，即：

\begin{matrix} (1) & P (Y_{u}, Y_{v} ∣ Y_{O}) = P (Y_{u} ∣ Y_{O}) P (Y_{v} ∣ Y_{O}) \end{matrix}

局部马尔可夫性

局部马尔可夫性

$v \in V$ $G$ $W$ $v$ $O$ $v$ $W$ $v$ $Y_v$ $W$ $Y_W$ $O$ $Y_O$ $Y_W$ $Y_v$ $Y_O$ 是独立的，即：

\begin{matrix} (2) & \begin{aligned} P (Y_{v}, Y_{O} ∣ Y_{W}) & = P (Y_{v} ∣ Y_{W}) P (Y_{O} ∣ Y_{W}) \\ = P (Y_{v} ∣ Y_{O}, Y_{W}) P (Y_{O} ∣ Y_{W}) \end{aligned} \end{matrix}

$P\left(Y_{O} \mid Y_{W}\right) > 0$ 时，等价地：

\begin{matrix} (3) & P (Y_{v} ∣ Y_{W}) = P (Y_{v} ∣ Y_{O}, Y_{W}) \end{matrix}

该公式可以概括为：

\begin{matrix} (4) & \begin{matrix} P (Y_{v} ∣ Y_{Q}, v \sim Q) = P (Y_{v} ∣ Y_{S}, v \neq S) \\ 其 中 ， v \sim Q 表 示 所 有 与 v 连 接 的 点 ， v \neq S 表 示 除 了 v 以 外 的 其 它 点 \end{matrix} \end{matrix}

全局马尔可夫性

全局马尔可夫性

$A，B$ $G$ $C$ $A，B$ $C$ $Y_A，Y_B$ $Y_C$ $Y_C$ $Y_A$ $Y_B$ 是条件独立的，即

\begin{matrix} (5) & P (Y_{A}, Y_{B} ∣ Y_{C}) = P (Y_{A} ∣ Y_{C}) P (Y_{B} ∣ Y_{C}) \end{matrix}

概率无向图模型定义

$定义：(概率无向图模型)$ $P(Y)$ $G=(V,E)$ $G$ $P(Y)$ $P(Y)$ 为概率无向图模型，或马尔可夫随机场。

$P(Y)$ $P(Y)$ 可以由无向图表示，且无向图结点间的概率满足马尔可夫性。

概率无向图模型的因子分解

$定义：(团与最大团)$ $G$ $C$ $G$ $G$ $C$ 为最大团。

最大团

$\{Y_1,Y_2,Y_3 \}$ $\{Y_2,Y_3, Y_4 \}$ 。

$定理：(Hammersley-Clifford 定理)$ $P(Y)$ 可以表示为如下形式：

\begin{matrix} (6) & \begin{aligned} P (Y) & = \frac{1}{Z} \prod_{C} Ψ_{C} (Y_{C}) \\ Z & = \sum_{Y} \prod_{C} Ψ_{C} (Y_{C}) \\ 其 中 ， C 是 无 向 图 的 最 大 团 ， Y_{C} 是 C 中 的 & 结 点 对 应 的 随 机 变 量 ， Ψ_{C} (Y_{C}) 是 C 上 定 义 的 严 格 正 函 数 ， \\ 乘 积 是 在 无 向 图 所 有 的 最 大 团 上 进 行 的 。 \end{aligned} \end{matrix}

上述定理表明，概率无向图模型的联合概率分布可以表示为其最大团上的随机变量的函数的乘积形式。

条件随机场表示

条件随机场定义

$X$ $Y$ 的马尔可夫随机场。

$定义：(条件随机场)$ $X$ $Y$ $P(Y \mid X)$ $X$ $Y$ $Y$ $G=(V,E)$ 表示的马尔可夫随机场，即：

\begin{matrix} (7) & P (Y_{v} ∣ X, Y_{w}, w \neq v) = P (Y_{v} ∣ X, Y_{w}, w \sim v) \end{matrix}

$v$ $P(Y \mid X)$ $w \sim v$ $G=(V,E)$ $v$ $w$ $w \neq v$ $v$ $Y_v、Y_u、Y_w$ $v、u、w$ 对应的随机变量。

$注意：$ $X$ $Y$ 具有相同的结构。

线性链条件随机场定义

$X$ $Y$ 具有相同结构。现假设无向图为下图所示的线性链的情况，即图的定义为：

\begin{matrix} (8) & G = (V = {1, 2, \dots, n}, E = {(i, i + 1)}), i = 1, 2, \dots, n - 1 \end{matrix}

$X=\left(X_{1}, X_{2}, \cdots, X_{n}\right), Y=\left(Y_{1}, Y_{2}, \cdots, Y_{n}\right)$ ，最大团是相邻两个结点的集合。

线性链条件随机场

同结构线性链条件随机场

$P(Y \mid X)$ $Y$ 预测出的标记序列 $X$ 需要标注的观测序列 $X=\{我爱中国\}$ $Y=\{名词，动词，名词 \}$ 。

$定义：(线性链条件随机场)$ $X=\left(X_{1}, X_{2}, \cdots, X_{n}\right), Y=\left(Y_{1}, Y_{2}, \cdots, Y_{n}\right)$ $X$ $Y$ $P(Y \mid X)$ 构成条件随机场，即满足马尔可夫性：

\begin{matrix} (9) & \begin{matrix} P (Y_{i} ∣ X, Y_{1}, \dots, Y_{i - 1}, Y_{i + 1}, \dots, Y_{n}) = P (Y_{i} ∣ X, Y_{i - 1}, Y_{i + 1}) \\ i = 1, 2, \dots, n (在 i = 1 和 n 时只考虑单边) \end{matrix} \end{matrix}

$P(Y \mid X)$ $X$ $Y$ 表示对应的输出标记序列或状态序列。

条件随机场的参数化形式

$Hammersley-Clifford 定理$ ，可以给出线性链条件随机场的因子分解式，各因子是定义在相邻两个结点（最大团）上的势函数。

$定理：(线性链条件随机场的参数化形式)$ $P(Y \mid X)$ $X$ $x$ $Y$ $y$ 的条件概率具有如下形式：

\begin{matrix} (10) & \begin{matrix} P (y ∣ x) = \frac{1}{Z (x)} \exp (\sum_{i, k} λ_{k} t_{k} (y_{i - 1}, y_{i}, x, i) + \sum_{i, l} μ_{l} s_{l} (y_{i}, x, i)) \\ Z (x) = \sum_{y} \exp (\sum_{i, k} λ_{k} t_{k} (y_{i - 1}, y_{i}, x, i) + \sum_{i, l} μ_{l} s_{l} (y_{i}, x, i)) \\ 其 中 ， t_{k} 是 定 义 在 边 上 的 特 征 函 数 ， 称 为 转 移 特 征 ； s_{l} 是 定 义 在 结 点 上 的 特 征 函 数 ， 称 为 状 态 特 征 ； \\ t_{k} 和 s_{l} 都 依 赖 于 位 置 ， 是 局 部 特 征 函 数 ， 通 常 取 值 为 0 或 1 ； λ_{k} 和 μ_{l} 是 对 应 的 权 值 ； Z (x) 是 规 范 化 因 子 ， \\ 求 和 是 在 所 有 可 能 的 输 出 序 列 上 进 行 的 。 \end{matrix} \end{matrix}

条件随机场的简化形式

在条件随机场的参数化形式中，同一特征在各个位置都有定义，可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积的形式，即条件随机场的简化形式。

首先，将转移特征和状态特征及其权值用统一的符号表示。

$K_1$ $K_2$ $K=K_1+K_2$ ，记：

\begin{matrix} (11) & f_{k} (y_{i - 1}, y_{i}, x, i) = {\begin{cases} t_{k} (y_{i - 1}, y_{i}, x, i), & k = 1, 2, \dots, K_{1} \\ s_{l} (y_{i}, x, i), & k = K_{1} + l; l = 1, 2, \dots, K_{2} \end{cases} \end{matrix}

$i$ 求和，得到全局特征函数，记作：

\begin{matrix} (12) & f_{k} (y, x) = \sum_{i = 1}^{n} f_{k} (y_{i - 1}, y_{i}, x, i), k = 1, 2, \dots, K \end{matrix}

$w_k$ $f_{k}(y, x)$ 的权值，得到全局特征权值，即：

\begin{matrix} (13) & w_{k} = {\begin{cases} λ_{k}, & k = 1, 2, \dots, K_{1} \\ μ_{l}, & k = K_{1} + l; l = 1, 2, \dots, K_{2} \end{cases} \end{matrix}

$(10)$ 可表示为：

\begin{matrix} (14) & \begin{matrix} 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{matrix} \end{matrix}

$F(y,x)$ 表示全局特征向量，即：

\begin{matrix} (15) & F (y, x) = {(f_{1} (y, x), f_{2} (y, x), \dots, f_{K} (y, x))}^{T} \end{matrix}

$w$ 表示权值向量，即：

\begin{matrix} (16) & w = (w_{1}, w_{2}, \dots, w_{K})^{T} \end{matrix}

$w$ $F(y,x)$ 的内积的形式：

\begin{matrix} (17) & \begin{aligned} 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)) \end{aligned} \end{matrix}

条件随机场的矩阵形式

$P_w(y \mid x)$ $式 (14)$ $x$ $y$ 的条件概率。

$y_0 = start$ $y_{n+1}=stop$ $P_w(y \mid x)$ 可以通过矩阵形式表示并有效计算。

$x$ $i=1,2,\cdots,n+1$ $y_{i-1}$ $y_i$ $m$ $m$ 阶矩阵随机变量：

\begin{matrix} (18) & M_{i} (x) = {[M_{i} (y_{i - 1}, y_{i} ∣ x)]}_{m \times m} \end{matrix}

矩阵随机变量的元素为：

\begin{matrix} (19) & \begin{aligned} 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) \\ 其 中 ， f_{k} 和 w_{k} 分 别 由 & 式 (12) 和 式 (13) 给 出 ， y_{i - 1} 和 y_{i} 是 标 记 随 机 变 量 Y_{i - 1} 和 Y_{i} 的 取 值 。 \end{aligned} \end{matrix}

$x$ $y$ $n+1$ 适当元素 $\prod_{i=1}^{n+1} M_{i}\left(y_{i-1}, y_{i} \mid x\right)$ $P_w(y \mid x)$ 为：

\begin{matrix} (20) & \begin{aligned} P_{w} (y ∣ x) & = \frac{1}{Z_{w} (x)} \prod_{i = 1}^{n + 1} M_{i} (y_{i - 1}, y_{i} ∣ x) \\ = \frac{1}{Z_{w} (x)} \prod_{i = 1}^{n + 1} \exp (W_{i} (y_{i - 1}, y_{i} ∣ x)) \\ = \frac{1}{Z_{w} (x)} \prod_{i = 1}^{n + 1} \exp (\sum_{k = 1}^{K} w_{k} f_{k} (y_{i - 1}, y_{i}, x, i)) \\ = \frac{1}{Z_{w} (x)} \exp (\sum_{i = 1}^{n + 1} \sum_{k = 1}^{K} w_{k} f_{k} (y_{i - 1}, y_{i}, x, i)) \\ 其 中 ， Z_{w} (x) & = {[M_{1} (x) M_{2} (x) \dots M_{n + 1} (x)]}_{start,stop} \end{aligned} \end{matrix}

可以看到，矩阵形式展开后与参数化形式或简化形式是一致的。

条件随机场概率计算问题

前向-后向算法

前向向量
$i=0,1,\cdots, n+1$ $\alpha_i(x)$ ：
$\begin{matrix} (21) & α_{0} (y ∣ x) = {\begin{cases} 1, & y = start \\ 0, & 否则 \end{cases} \end{matrix}$
递推公式为：
$\begin{matrix} (22) & \begin{aligned} α_{i}^{T} (y_{i} ∣ x) & = α_{i - 1}^{T} (y_{i - 1} ∣ x) [M_{i} (y_{i - 1}, y_{i} ∣ x)] \\ 其中， i & = 1, 2, \dots, n + 1 \end{aligned} \end{matrix}$
又可表示为：
$\begin{matrix} (23) & \begin{aligned} α_{i}^{T} (x) & = α_{i - 1}^{T} (x) M_{i} (x) \end{aligned} \end{matrix}$
$\alpha_i(y_i \mid x)$ $i$ $y_i$ $i$ $y_i$ $m$ $\alpha_i(x)$ $m$ 维列向量。
后向向量
$i=0,1,\cdots, n+1$ $\beta_i(x)$ ：
$\begin{matrix} (24) & β_{n + 1} (y_{n + 1} ∣ x) = {\begin{cases} 1, & y_{n + 1} = stop \\ 0, & 否则 \end{cases} \end{matrix}$
递推公式为：
$\begin{matrix} (25) & β_{i} (y_{i} ∣ x) = [M_{i + 1} (y_{i}, y_{i + 1} ∣ x)] β_{i + 1} (y_{i + 1} ∣ x) \end{matrix}$
又可表示为：
$\begin{matrix} (26) & β_{i} (x) = M_{i + 1} (x) β_{i + 1} (x) \end{matrix}$
$\beta_i(y_i \mid x)$ $i$ $y_i$ $i+1$ $n$ 的后部分标记序列的非规范化概率。

概率计算

根据前向-后向向量的定义，可以得出如下概率：

\begin{matrix} (27) & \begin{matrix} P (Y_{i} = y_{i} ∣ x) = \frac{α_{i}^{T} (y_{i} ∣ x) β_{i} (y_{i} ∣ x)}{Z (x)} \\ P (Y_{i - 1} = y_{i - 1}, Y_{i} = y_{i} ∣ x) = \frac{α_{i - 1}^{T} (y_{i - 1} ∣ x) M_{i} (y_{i - 1}, y_{i} ∣ x) β_{i} (y_{i} ∣ x)}{Z (x)} \\ 其 中 ， Z (x) = α_{n}^{T} (x) 1 = 1 β_{1} (x) \\ 1 是 元 素 均 为 1 的 m 维 列 向 量 \end{matrix} \end{matrix}

期望值的计算

$P(X,Y)$ $P(Y \mid X)$ 的数学期望。

$f_k$ $P(Y \mid X)$ 的数学期望
$\begin{matrix} (28) & \begin{aligned} E_{P (Y ∣ X)} [f_{k}] & = \sum_{y} 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{α_{i - 1}^{T} (y_{i - 1} ∣ x) M_{i} (y_{i - 1}, y_{i} ∣ x) β_{i} (y_{i} ∣ x)}{Z (x)} \\ Z (x) & = α_{n}^{T} (x) 1 \\ 其中， k & = 1, 2, \dots, K \end{aligned} \end{matrix}$
$f_k$ $P(X,Y)$ 的数学期望
$\tilde{P}(x)$ $f_k$ $P(X,Y)$ 的数学期望为：
$\begin{matrix} (29) & \begin{aligned} 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} (y_{i - 1}, y_{i}, x, i) \frac{α_{i - 1}^{T} (y_{i - 1} ∣ x) M_{i} (y_{i - 1}, y_{i} ∣ x) β_{i} (y_{i} ∣ x)}{Z (x)} \\ Z (x) & = α_{n}^{T} (x) 1 \\ 其中， k & = 1, 2, \dots, K \end{aligned} \end{matrix}$

条件随机场的学习算法

改进的迭代尺度法

$\tilde P(X,Y)$ 。可以通过极大化训练数据的对数似然函数来求模型参数。

训练数据的对数似然函数为：

\begin{matrix} (30) & 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) \end{matrix}

$P_w$ $式(14)$ 给出的条件随机场模型时，对数似然函数为：

\begin{matrix} (31) & \begin{aligned} L (w) & = \sum_{x, y} \tilde{P} (x, y) \log P_{w} (y ∣ x) \\ = \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{aligned} \end{matrix}

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

$w = (w_1, w_2, \cdots, w_K)^T$ $\delta = (\delta_1, \delta_2,\cdots, \delta_K)$ $w+\delta = (w_1+\delta_1, w+\delta_2,\cdots,w_K+\delta_K)^T$ $式(32)$ $式(33)$ $\delta = (\delta_1, \delta_2,\cdots, \delta_K)$ 。

$t_k$ 的更新方程
$\begin{matrix} (32) & \begin{aligned} 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 (δ_{k} T (x, y)) \\ 其中， k & = 1, 2, \dots, K_{1} \end{aligned} \end{matrix}$
$s_l$ 的更新方程

\begin{matrix} (33) & \begin{aligned} 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 (δ_{K_{1} + l} T (x, y)) \\ 其 中 ， l & = 1, 2, \dots, K_{2} \end{aligned} \end{matrix}

$T(x,y)$ $(x,y)$ 中出现所有特征数的总和：

\begin{matrix} (34) & 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{matrix}

$算法 (条件随机场模型学习的改进的迭代尺度法)$

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

$输出：参数估计值 \hat{w}；模型P_{\hat{w}}$

$(1) 对所有 k \in \{1,2,\cdots,K \}，初始化w_k=0$

$(2) 对每一 \; k \in \{1,2,\cdots,K \}：$

$(a) 当 K=1,2,\cdots,K_1 时，令 \delta_k是如下方程的解：$

$\sum_{x, y} \tilde{P}(x) P(y \mid x) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1}, y_{i}, x, i\right) \exp \left(\delta_{k} T(x, y)\right)=E_{\tilde{P}}\left[t_{k}\right]。$

\begin{matrix} (35) & \begin{matrix} 解 得 ： δ_{k} = \frac{1}{S} \log \frac{E_{\tilde{P}} [t_{k}]}{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{α_{i - 1}^{T} (y_{i - 1} ∣ x) M_{i} (y_{i - 1}, y_{i} ∣ x) β_{i} (y_{i} ∣ x)}{Z (x)} \end{matrix} \end{matrix}

$\quad 当K=K_1+l, \; l=1,2,\cdots,K_2时，令\delta_{K_1+l}是如下方程的解：$

$\sum_{x, y} \tilde{P}(x) P(y \mid x) \sum_{i=1}^{n} s_{l}\left(y_{i}, x, i\right) \exp \left(\delta_{K_{1}+l} T(x, y)\right)=E_{\tilde{P}}\left[s_{l}\right]$

\begin{matrix} (36) & \begin{matrix} 解 得 ： δ_{K_{1} + l} = \frac{1}{S} \log \frac{E_{\tilde{P}} [s_{l}]}{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{α_{i}^{T} (y_{i} ∣ x) β_{i} (y_{i} ∣ x)}{Z (x)} \end{matrix} \end{matrix}

$(b) 更新w_k的值：w_{k} \leftarrow w_{k}+\delta_{k}$

$(3)如果不是所有w_k都收敛，重复步骤(2)$

$式(34)$ $T(x,y)$ $(x,y)$ $(x,y)$ 取值可能不同。为了处理该问题，定义松弛特征：

\begin{matrix} (37) & s (x, y) = S - \sum_{i = 1}^{n + 1} \sum_{k = 1}^{K} f_{k} (y_{i - 1}, y_{i}, x, i) \end{matrix}

$S$ $S$ $(x,y)$ $s(x,y) \geq 0$ $S$ 。

拟牛顿法

条件随机场的对数似然函数为：

\begin{matrix} (38) & L (w) = \sum_{x, y} \tilde{P} (x, y) \log P_{w} (y ∣ x) \end{matrix}

将条件随机场的简化形式带入得：

\begin{matrix} (39) & \begin{aligned} L (w) & = \sum_{x, y} \tilde{P} (x, y) \log [\frac{\exp \sum_{k = 1}^{K} w_{k} f_{k} (y, x)}{Z_{w} (x)}] \\ = \sum_{x, y} \tilde{P} (x, y) [\log (\exp \sum_{k = 1}^{K} w_{k} f_{k} (y, x)) - \log Z_{w} (x)] \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{k = 1}^{K} w_{k} f_{k} (y, x) - \sum_{x, y} \tilde{P} (x, y) \log Z_{w} (x) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{k = 1}^{K} w_{k} f_{k} (y, x) - \sum_{x} \sum_{y} \tilde{P} (x, y) \log Z_{w} (x) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{k = 1}^{K} w_{k} f_{k} (y, x) - \sum_{x} \log Z_{w} (x) (\sum_{y} \tilde{P} (x, y)) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{k = 1}^{K} w_{k} f_{k} (y, x) - \sum_{x} \log Z_{w} (x) \tilde{P} (x) \\ = \sum_{x, y} \tilde{P} (x, y) \sum_{k = 1}^{K} w_{k} f_{k} (y, x) - \sum_{x} \tilde{P} (x) \log \sum_{y} \exp \sum_{k = 1}^{K} w_{k} f_{k} (y, x) \end{aligned} \end{matrix}

$f(w) = -L(w)$ $L(w)$ $f(w)$ ，所以，优化目标函数为：

\begin{matrix} (40) & min_{w \in R^{n}} f (w) = \sum_{x} \tilde{P} (x) \log \sum_{y} \exp (\sum_{i = 1}^{K} w_{i} f_{i} (x, y)) - \sum_{x, y} \tilde{P} (x, y) \sum_{i = 1}^{K} w_{i} f_{i} (x, y) \end{matrix}

$f(w)$ 的梯度函数是：

\begin{matrix} (41) & g (w) = \sum_{x, y} \tilde{P} (x) P_{w} (y ∣ x) f (x, y) - E_{\tilde{P}} (f) \end{matrix}

$算法 \; (条件随机场模型学习的 \mathbf{BFGS}算法)$

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

$输出：最优参数值\hat{w}；最优模型P_{\hat{w}}(y \mid x)$

$(1)选定初始点w^{(0)}，取 \mathbf{B}_0为正定对称矩阵，置k=0$

$(2)计算g_k=g(w^{(k)})。若g_k=0，则停止计算，否则转(3)$

$(3)由 \mathbf{B}_{k} p_{k} = -g_k求出p_k$

$(4)一维搜索：求\lambda_k使得：$

$f\left(w^{(k)}+\lambda_{k} p_{k}\right)=\min _{\lambda \geqslant 0} f\left(w^{(k)}+\lambda p_{k}\right)$

$(5) 置w^{(k+1)} = w^{(k)} + \lambda_k p_k$

$(6)计算g_{k+1} = g(w^{(k+1)})，若g_{k+1} = 0，则停止计算；否则，按下式求出 \mathbf{B}_{k+1}$

$\large B_{k+1}=B_{k}+\frac{y_{k} y_{k}^{\mathrm{T}}}{y_{k}^{\mathrm{T}} \delta_{k}}-\frac{B_{k} \delta_{k} \delta_{k}^{\mathrm{T}} B_{k}}{\delta_{k}^{\mathrm{T}} B_{k} \delta_{k}}$

$其中，y_{k}=g_{k+1}-g_{k}, \quad \delta_{k}=w^{(k+1)}-w^{(k)}$

$(7)置k=k+1，转(3)$

条件随机场的预测算法

已知：

\begin{matrix} (42) & \begin{aligned} w & = {(w_{1}, w_{2}, \dots, w_{K})}^{T} \\ F (y, x) & = {(f_{1} (y, x), f_{2} (y, x), \dots, f_{K} (y, x))}^{T} \\ f_{k} (y, x) & = \sum_{i = 1}^{n} f_{k} (y_{i - 1}, y_{i}, x, i), k = 1, 2, \dots, K \end{aligned} \end{matrix}

根据条件随机场的矩阵形式，可得：

\begin{matrix} (43) & \begin{aligned} y^{*} & = \arg max_{y} P_{w} (y ∣ x) \\ = \arg max_{y} \frac{\exp (w \cdot F (y, x))}{Z_{w} (x)} \\ = \arg max_{y} \exp (w \cdot F (y, x)) \\ = \arg max_{y} (w \cdot F (y, x)) \end{aligned} \end{matrix}

于是，条件随机场的预测问题成为求非规范化概率最大的最优路径问题：

\begin{matrix} (44) & max_{y} (w \cdot F (y, x)) \end{matrix}

根据定义可以推导：

\begin{matrix} (45) & \begin{aligned} w \cdot F (y, x) & = {(w_{1}, w_{2}, \dots, w_{K})}^{T} \cdot {(f_{1} (y, x), f_{2} (y, x), \dots, f_{K} (y, x))}^{T} \\ = {(w_{1}, w_{2}, \dots, w_{K})}^{T} \cdot {(\sum_{i = 1}^{n} f_{1} (y_{i - 1}, y_{i}, x, i), \sum_{i = 1}^{n} f_{2} (y_{i - 1}, y_{i}, x, i), \dots, \sum_{i = 1}^{n} f_{K} (y_{i - 1}, y_{i}, x, i))}^{T} \\ = \sum_{i = 1}^{n} {(w_{1}, w_{2}, \dots, w_{K})}^{T} \cdot {(f_{1} (y_{i - 1}, y_{i}, x, i), f_{2} (y_{i - 1}, y_{i}, x, i), \dots, f_{K} (y_{i - 1}, y_{i}, x, i))}^{T} \\ = \sum_{i = 1}^{n} w \cdot F_{i} (y_{i - 1}, y_{i}, x, i) \\ 其 中 ， F_{i} (y_{i - 1}, y_{i}, x, i) & = {(f_{1} (y_{i - 1}, y_{i}, x, i), f_{2} (y_{i - 1}, y_{i}, x, i), \dots, f_{K} (y_{i - 1}, y_{i}, x, i))}^{T} \end{aligned} \end{matrix}

因此，优化目标可以写成如下形式：

\begin{matrix} (46) & max_{y} \sum_{i = 1}^{n} w \cdot F_{i} (y_{i - 1}, y_{i}, x) 其 中 ， F_{i} (y_{i - 1}, y_{i}, x, i) = {(f_{1} (y_{i - 1}, y_{i}, x, i), f_{2} (y_{i - 1}, y_{i}, x, i), \dots, f_{K} (y_{i - 1}, y_{i}, x, i))}^{T} \end{matrix}

$算法 \; (条件随机场的维特比算法)$

$输入：模型特征向量F_i(y_{i-1},y_i,x, i),i=1,2,\cdots,n；权值向量w；观测序列x=(x_1,x_2,\cdots,x_n)$

$输出：最优路径y^*=(y_1^*,y_2^*,\cdots,y_n^*)$

$(1)初始化$

$\delta_{1}(j)=w \cdot F_{1}\left(y_{0}=\text { start }, y_{1}=j, x\right), \quad j=1,2, \cdots, m$

$(2)递推：对i=2,3,\cdots,n$

$\delta_{i}(l)=\max _{1 \leqslant j \leqslant m}\left\{\delta_{i-1}(j)+w \cdot F_{i}\left(y_{i-1}=j, y_{i}=l, x\right)\right\}, \quad l=1,2, \cdots, m$

$\Psi_{i}(l)=\arg \max _{1 \leqslant j \leqslant m}\left\{\delta_{i-1}(j)+w \cdot F_{i}\left(y_{i-1}=j, y_{i}=l, x\right)\right\}, \quad l=1,2, \cdots, m$

$(3)终止$

$\max _{y}(w \cdot F(y, x))=\max _{1 \leqslant j \leqslant m} \delta_{n}(j)$

$y_{n}^{*}=\arg \max _{1 \leqslant j \leqslant m} \delta_{n}(j)$

$(4)返回路径$

$y_{i}^{*}=\Psi_{i+1}\left(y_{i+1}^{*}\right), \quad i=n-1, n-2, \cdots, 1$

$求得最优路径：y^*=(y_1^*,y_2^*,\cdots,y_n^*)$