CRF [¹]

• 定义：条件随机场(conditional random field, CRF)是给定一组输入随机变量条件 下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。

• 马尔可夫随机场：由无向图表示的联合概率分布满足成对，局部或全局马尔科夫性。（这几个马尔可夫性是等价的）

• 在马尔科夫随机场中的联合概率分布可以表示为其最大团的随机变量的函数的概率分布的乘积。

  \[\begin{equation} P(Y)=\frac{1}{Z} \prod_{C} \Psi_{C}\left(Y_{C}\right) \end{equation}\]

• 条件随机场：条件随机场(conditional random field)是给定随机变量X条件下，随机变量Y的马尔可夫随机场。应用的主要是定义在线性链上的特殊的条件随机场，称为线性链条件随机场(linear chain conditional random field) 。线性链条件随机场可以用于标注问题。

• 线性链条件随机场上的最大团是相邻两个结点的集合。所以可以分解为两个节点上随机变量相关函数的乘积。

• 参数化表示：

  \[\begin{align} P(y \mid x) &=\frac{1}{Z(x)} \exp \left(\sum_{i, k} \lambda_{k} t_{k}\left(y_{i-1}, y_{i}, x, i\right)+\sum_{i, l} \mu_{l} s_{l}\left(y_{i}, x, i\right)\right) \\ Z(x) &=\sum_{y} \exp \left(\sum_{i, k} \lambda_{k} t_{k}\left(y_{i-1}, y_{i}, x, i\right)+\sum_{i, l} \mu_{l} s_{l}\left(y_{i}, x, i\right)\right) \end{align}\]
• 矩阵化表示：pass
• 条件概率计算：

  • 标记序列在位置i是标记$y_i$的条件概率:前向后向算法，具体看书吧，少两个公式

    \[\begin{equation} P\left(Y_{i}=y_{i} \mid x\right)=\frac{\alpha_{i}^{\mathrm{T}}\left(y_{i} \mid x\right) \beta_{i}\left(y_{i} \mid x\right)}{Z(x)} \end{equation}\]
• 学习算法：
  • 迭代尺度算法：每次更新一个参数？
  • 拟牛顿法：直接就是求梯度，最优化问题
• 预测算法：条件随机场的预测问题是给定条件随机场\(P(Y \mid X)\)和输入序列(观测序列)x,求条件概率最大的输出序列(标记序列) y*,即对观测序列进行标注。
  • 维特比算法：直接求计算量太大，可以用动态规划的思想，不用重复求解子问题。

    • 从1-n，依次求解从i位置j状态的最大概率。

      \[\begin{align} \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 \end{align}\]

参考文献