4 CRFs

我们现在转向条件随机场。为了方便，我们使用 $\underline{x}$ 表示输入序列 $x_1\dots x_m$ , $\underline{s}$ 表示状态序列 $s_1\dots s_m$ , $\mathcal{S}$ 表示所有可能状态的集合， $\mathcal{S}^m$ 表示所有可能的状态序列的集合。

在条件随机场里，我们依然是为条件概率
$p(s_1\dots s_m|x_1\dots x_m)=p(\underline{s}|\underline{x})$ 建立模型。CRFs的第一个关键思想是定义一个特征向量
$\underline{\Phi}(\underline{x},\underline{s}) \in \mathbb{R}^d$
该函数将整个输入序列 $\underline{x}$ 和与其配对的整个状态序列 $\underline{s}$ 映射到某个 $d$ 维特征向量。我们很快就会给出一个 $\underline{\Phi}$ 的具体定义。但是现在我们假设函数已经定义好了，我们经常将 $\underline{\Phi}$ 成为全局特征向量（之所以被称为全局，是因为它将整个状态序列纳入其中）。

这样我们就有了一个巨型的对数线性模型，
$p(\underline{s}|\underline{x},\underline{\omega})= \cfrac{exp(\underline{\omega}\cdot\underline{\Phi}(\underline{x},\underline{s}))} {\sum_{s\prime\in\mathcal{S}} exp(\underline{\omega}\cdot\underline{\Phi}(\underline{x},\underline{s\prime})}$
该线性模型之所以称为巨型，是因为：
1）所有可能的状态序列 $\underline{s}$ ，也就是 $\mathcal{S}^m$ 非常大。
2）归一化常数包括对集合 $\mathcal{S}^m$ 求和，一眼看去，仿佛这会引起非常复杂的计算问题，但是很快我们将看到，在合理的假设下，我们可以非常有效的训练和解码该模型。

第二个问题是我们怎么定义函数 $\underline{\Phi}(\underline{x},\underline{s})$ ，答案是
$\underline{\Phi}(\underline{x},\underline{s}) = \sum_{j=1}^m \underline{\phi}(\underline{x},j,s_{j-1},s_j)$
这里的 $\underline{\phi}(\underline{x},j,s_{j-1},s_j)$ 和MEMMs定义的特征向量是一样的。以另一种方式来说，就是我们假设第 $k$ 个全局特征是
$\underline{\Phi_k}(\underline{x},\underline{s})= \sum_{j=1}^m\underline{\phi}(\underline{x},j,s_{j-1},s_j)$ ,所以 $\underline{\Phi_k}$ 通过累加状态序列 $s_1\dots s_m$ 的每个状态转移上的局部特征 $\underline{\phi_k}$ 而得到的。

现在我们来解决CRFs的两个关键问题，第一个是解码，第二个是参数估计。

解码CRFs CRFs的解码问题如下：给定一个输入序列 $\underline{x}=x_1,x_2\dots x_m$ ,我们要找到模型下最可能的状态序列，也就是,
$\arg\,\max_{s\in\mathcal{S}^m} p(\underline{s}|\underline{x};\underline{\omega})$

我们可以将表达式向如下这么简化
$\begin{aligned} \arg\,\max_{s\in\mathcal{S}^m}p(\underline{s}|\underline{x};\underline{\omega})&= \arg\,\max_{\underline{s}\in\mathcal{S}^m} \cfrac{exp(\underline{\omega}\cdot\underline{\Phi}(\underline{x},\underline{s}))} {\sum_{s\prime\in\mathcal{S}} exp(\underline{\omega}\cdot\underline{\Phi}(\underline{x},\underline{s\prime})} \\ &=\arg\,\max_{\underline{s}\in\mathcal{S}^m} exp(\underline{\omega}\cdot\underline{\Phi}(\underline{x},\underline{s}))\\ &=\arg\,\max_{\underline{s}\in\mathcal{S}^m}\underline{\omega}\cdot\underline{\Phi}(\underline{x},\underline{s})\\ &=\arg\,\max_{\underline{s}\in\mathcal{S}^m}\underline{\omega}\cdot\sum_{j=1}^m\underline{\phi}(\underline{x},j,s_{j-1},s_j)\\ &=\arg\,\max_{\underline{s}\in\mathcal{S}^m}\sum_{j=1}^m\underline{\omega}\cdot \underline{\phi}(\underline{x},j,s_{j-1},s_j) \end{aligned}$

所以在模型下寻找最有可能的序列等价于寻找满足
$\arg\,\max_{\underline{s}\in\mathcal{S}^m}\sum_{j=1}^m\underline{\omega}\cdot \underline{\phi}(\underline{x},j,s_{j-1},s_j)$
的序列。这个问题有个直观的解释，每个从状态 $s_{j-1}$ 到 $s_j$ 的转移有一个分数
$\underline{\omega}\cdot \underline{\phi}(\underline{x},j,s_{j-1},s_j)$
这个分数可以是真的也可以是负的。直觉的，如果状态转移很有可能则分数相对较高。解码问题就是找到使转移分数之和最高的那个状态序列。

我们可以使用一个维特比算法来解决这个问题。

初始化，对所有 $s\in\mathcal{S}$
$\pi[1,s]=\underline{\omega}\cdot\underline{\phi}(x,1,s_0,s)$
这里 $s_0$ 是一个特殊的初始状态。
对 $j=2\dots m$ ,所有 $s\in\mathcal{S}$ :
$\pi[j,s]=\max_{s\prime\in\mathcal{S}}\big( \pi[j-1,s\prime]+\underline{\omega}\cdot\underline{\phi}(\underline{x},j,s\prime,s)\big)$

最后我们可以得到
$\max_{\underline{s}\in\mathcal{S}^m}\sum_{j=1}^m\underline{\omega}\cdot \underline{\phi}(\underline{x},j,s_{j-1},s_j)=\max_s\pi[m,s]$
然后利用回指，我们可以得到最高分的状态序列，这个算法具有 $O(mk^2)$ 时间复杂度，所以解码算法是很高效的。

估计CRFs的参数。假设我们有一个打好标签的样本集 $\{(\underline{x}^i,\underline{s}^i)\}_{i=1}^n$ ，每个 $\underline{x}^i$ 是一个输入序列 $x_1^i\dots x_m^i$ ,每个 $\underline{s}^i$ 是一个状态序列 $s_1^i\dots s_m^i$
。我们可以用对数线性空间参数估计一样的方法来估计CRFs的参数。正则化的对数似然函数是
$\mathcal{L}(\underline{\omega})=\sum_{i=1}^n\log p(\underline{s}^i|\underline{x}^i,\underline{\omega})-\cfrac{\lambda}{2}||\omega||^2$

CRFs的参数估计就是
$\underline{\omega}^*=\arg\,\max_{\underline{\omega}\in\mathbb{R}^d}\sum_{i=1}^n\log p(\underline{s}^i|\underline{x}^i,\underline{\omega})-\cfrac{\lambda}{2}||\omega||^2$

我们使用基于梯度的最优化方式求解 $\underline{\omega}^*$ ,偏导数是
$\cfrac{\partial}{\partial\omega_k}\mathcal{L}(\underline{\omega})=\sum_i \Phi_k(\underline{x}^i,\underline{s}^i)-\sum_i\sum_{\underline{s}\in\mathcal{S}^m}p(\underline{s}|\underline{x}^i;\underline{\omega})\Phi_k(\underline{x}^i,\underline{s})-\lambda\omega_k$
第一项是很容易计算的，因为
$\sum_i \Phi_k(\underline{x}^i,\underline{s}^i)= \sum_i\sum_{j=1}^m \phi_k(\underline{x}^i,j,s_{j-1},s_j^i)$ 只需要对所有训练样本集 $i=1\dots n$ ,对每个样本所有位置 $j=1\dots m$ 求和即可。
第二项就复杂多了，需要对巨大的集合 $\mathcal{S}^m$ 求和，但是注意观察，这里可以使用动态规划的方法有效的计算。
$\begin{aligned} \sum_{\underline{s}\in\mathcal{S}^m}p(\underline{s}|\underline{x}^i;\underline{\omega})\Phi_k(\underline{x}^i,\underline{s})&=\sum_{\underline{s}\in\mathcal{S}^m}p(\underline{s}|\underline{x}^i)\sum_{j=1}^m\phi_k(\underline{x}^i,j,s_{j-1},s_j)\\ &=\sum_{j=1}^m\sum_{\underline{s}\in\mathcal{S}^m} p(\underline{s}|\underline{x}^i;\underline{\omega})\phi_k(\underline{x}^i,j,s_{j-1},s_j)\\ &=\sum_{j=1}^m\sum_{a\in\mathcal{S},b\in\mathcal{S}}\sum_{\underline{s}\in\mathcal{S}^m,s_{j-1}=a,s_j=b}p(\underline{s}|\underline{x}^i;\underline{\omega}) \phi_k(\underline{x}^i,j,s_{j-1},s_j) \\ &=\sum_{j=1}^m\sum_{a\in\mathcal{S},b\in\mathcal{S}}\phi_k(\underline{x}^i,j,s_{j-1},s_j)\sum_{\underline{s}\in\mathcal{S}^m,s_{j-1}=a,s_j=b}p(\underline{s}|\underline{x}^i;\underline{\omega}) \\ &=\sum_{j=1}^m\sum_{a\in\mathcal{S},b\in\mathcal{S}}q_j^i(a,b)\phi_k(\underline{x}^i,j,a,b) \end{aligned}$
其中 $q_j^i(a,b)=\sum_{\underline{s}\in\mathcal{S}^m\\s_{j-1}=a,s_j=b}p(\underline{s}|\underline{x}^i;\underline{\omega})$ 如果能有效的计算 $q_j^i(a,b)$ ,也就可以有效的计算这个偏导数， $q_j^i(a,b)$ 有个直观的解释，它是第 $i$ 个训练样本位置 $j-1$ 具有状态a和位置 $j$ 具有状态b的概率。