-条件随机场（CRF）)
1. 引言《NPL基于词典分词(四)》介绍第一个感知机是一个强大的序列标注模型。但有一种基于“无向概率图模型”的条件随机场性能比感知机还要强大。它们特征函数相同打分函数相同预测算法相同唯一的不同点是误差传递函数2. 无向概率图模型无向图模型不探究每个事件的因果关系。无向图模型的边没有方向仅仅代表两个事件有关联。无向图模型将概率分解为所有最大团上的某种函数之积。在图论中最大团指的是满足所有节点相互连接的最大子图。因为最大团需要考虑所有变量为此无向图模型定义了一些虚拟的因子节点每个因子节点只连接部分节点组成更小的最大团。蓝色虚线表示最大团黑色方块表因子节点圆圈则表示变量节点无向图模型将多维随机变量的联合分布分解为一系列最大团中的因子之积:其中a 是因子节点Ψa 则是一个因子节点对应的函数参数 Xa,Ya 是与因子节点相连的所有变量节点。为了将式子约束为概率分布定义常数 Z 为如下归一化因子:这种建模方式存在明显困难我们的任务是给定观测序列 x预测标签序列 y我们并不关心输入 x 自身的概率分布文本的输入序列 x 维度高、特征复杂想要准确估计 P(x)\十分困难会引入很大的建模误差。既然我们不需要建模输入 x 的分布就可以对无向图模型做改造保持因子函数 Ψa 的形式不变修改配分函数的归一化规则。不再对所有的输入 x 求和而是把输入 x 固定下来只对所有可能的标签序列 y 做求和。边缘概率 P(x) 是对所有 y 求和消去变量 yP ( x ) ∑ y P ( x , y ) P(x)\sum_{y} P(x,y)P(x)∑yP(x,y)代入联合分布P ( x ) ∑ y 1 Z ∏ a ψ a ( x , y ) 1 Z ∑ y ∏ a ψ a ( x , y ) P(x)\sum_{y}\frac{1}{Z}\prod_{a}\psi_a(x,y) \frac{1}{Z}\sum_{y}\prod_{a}\psi_a(x,y)P(x)∑yZ1∏aψa(x,y)Z1∑y∏aψa(x,y)定义条件配分函数得到最终关系P ( x ) Z ( x ) Z P(x)\frac{Z(x)}{Z}P(x)ZZ(x)然后 P(x,y) 就转化为判别式模型所需的条件概率分布:3.条件随机场条件随机场( Conditional Random Field, CRF)是一种给定输入随机变量 x求解条件概率 p(y| x) 的概率无向图模型。用于序列标注时特例化为线性链( linear chain )条件随机场。此时输人输出随机变量为等长的两个序列。3.1. 线性链条件随机场线性链条件随机场如下图所示:每个 Xt 上方有 3 个灰色节点代表 Xt 的 3 个特征当然还可以是任意数量的特征体现了特征的丰富性黑色方块是因子节点可以理解为一个特征函数f k ( y t − 1 , y t , x t ) f_k(y_{t-1},y_t,x_t)fk(yt−1,yt,xt)其中仅仅利用了X t X_tXt和Y t Y_tYt的特征称作状态特征利用了Y t − 1 Y_{t-1}Yt−1的特征则称作转移特征与感知机的特征函数相同。线性链条件随机场的定义如下:其中Z(x)为归一化函数:上式定义在所有可能的标注序列上。如果将所有特征函数与权重分别写作向量形式则线性链条件随机场的定义可简化为:对比结构化感知机的打分函数,由于给定实例 xZ(x) 就是一个常数 c, 可以发现结构化感知机打分函数与条件随机场的指数部分完全相同。 其不同点是感知机更新参数时只使用一个训练实例没有考虑整个数据集难免顾此失彼而条件随机场对数似然函数及其梯度则使用了整个数据集。即对上述CRF 条件概率公式对w \boldsymbol ww求导得 损失公式CRF 相当于在结构化感知机的基础上增加了「所有候选序列按概率加权」这一因素通俗比喻 看全班所有人的作弊可能性每个人按照自己的嫌疑程度都要受到相应的处理哪怕第一名是好学生只要还有其他人嫌疑不小依然要调整规则。4. 条件随机场训练下面是基于条件随机场的中文分词步骤第一步接受纯文本语料商 s 中 B 品 p 中 E 和 h 中 S 服 f 中 B 务 w 中 E A a 英 B K k 英 M B b 英 M 4 s 数 M 8 b 数 E每一行特征1 特征2 … 标签即序列的一个时刻X t , Y t X_t,Y_tXt,Yt,最后一列为输出变量 y 之外其它列都是输入变量 x第一行字商拼音s类别中标签B第一句话则对应的是x { 商 , 品 , 和 , 服 , 务 } , y g o l d { B , E , S , B , E } x\{\text{商},\text{品},\text{和},\text{服},\text{务}\},\quad y_{gold}\{B,E,S,B,E\}x{商,品,和,服,务},ygold{B,E,S,B,E}第二步提取特征。x是字符y是{B,M,E,S}转移特征状态特征y t − 1 y_{t-1}yt−1x t − 1 x_{t-1}xt−1x t x_{t}xtx t 1 x_{t1}xt1x t − 2 / x t − 1 x_{t-2}/x_{t-1}xt−2/xt−1x t − 1 / x t x_{t-1}/x_{t}xt−1/xtx t / x t 1 x_{t}/x_{t1}xt/xt1x t 1 / x t 2 x_{t1}/x_{t2}xt1/xt2根据特征表格提取出特征以“商”为例如下1. U00:# B2. U01:商 B3. U02:品 B4. U03:#/# B5. U04:#/商 B6. U05:商/品 B7. U06:品/和 B第三步特征代入损失公式损调节因子w \boldsymbol ww第四步 推理在获得稳定的w \boldsymbol ww再根据公式 找出最大可能y ^ arg max y P ( y ∣ x ) arg max y exp ( w ⋅ ϕ ( x , y ) ) Z ( x ) arg max y w ⋅ ϕ ( x , y ) \begin{aligned} \hat y \mathop{\arg\max}_{y} P(y|x) \\ \mathop{\arg\max}_{y} \frac{\exp\big(\boldsymbol w\cdot\boldsymbol\phi(x,y)\big)}{Z(x)} \\ \mathop{\arg\max}_{y} \boldsymbol w\cdot\boldsymbol\phi(x,y) \end{aligned}y^argmaxyP(y∣x)argmaxyZ(x)exp(w⋅ϕ(x,y))argmaxyw⋅ϕ(x,y)5. 主要参考《概率图 - 图表示 - 马尔可夫随机场MRF》《从零开始理解-概率图模型PGM》《条件随机场与序列标注》 NPL基于词典分词(五)-条件随机场（CRF）
1. 引言《NPL基于词典分词(四)》介绍第一个感知机是一个强大的序列标注模型。但有一种基于“无向概率图模型”的条件随机场性能比感知机还要强大。它们特征函数相同打分函数相同预测算法相同唯一的不同点是误差传递函数2. 无向概率图模型无向图模型不探究每个事件的因果关系。无向图模型的边没有方向仅仅代表两个事件有关联。无向图模型将概率分解为所有最大团上的某种函数之积。在图论中最大团指的是满足所有节点相互连接的最大子图。因为最大团需要考虑所有变量为此无向图模型定义了一些虚拟的因子节点每个因子节点只连接部分节点组成更小的最大团。蓝色虚线表示最大团黑色方块表因子节点圆圈则表示变量节点无向图模型将多维随机变量的联合分布分解为一系列最大团中的因子之积:其中a 是因子节点Ψa 则是一个因子节点对应的函数参数 Xa,Ya 是与因子节点相连的所有变量节点。为了将式子约束为概率分布定义常数 Z 为如下归一化因子:这种建模方式存在明显困难我们的任务是给定观测序列 x预测标签序列 y我们并不关心输入 x 自身的概率分布文本的输入序列 x 维度高、特征复杂想要准确估计 P(x)\十分困难会引入很大的建模误差。既然我们不需要建模输入 x 的分布就可以对无向图模型做改造保持因子函数 Ψa 的形式不变修改配分函数的归一化规则。不再对所有的输入 x 求和而是把输入 x 固定下来只对所有可能的标签序列 y 做求和。边缘概率 P(x) 是对所有 y 求和消去变量 yP ( x ) ∑ y P ( x , y ) P(x)\sum_{y} P(x,y)P(x)∑yP(x,y)代入联合分布P ( x ) ∑ y 1 Z ∏ a ψ a ( x , y ) 1 Z ∑ y ∏ a ψ a ( x , y ) P(x)\sum_{y}\frac{1}{Z}\prod_{a}\psi_a(x,y) \frac{1}{Z}\sum_{y}\prod_{a}\psi_a(x,y)P(x)∑yZ1∏aψa(x,y)Z1∑y∏aψa(x,y)定义条件配分函数得到最终关系P ( x ) Z ( x ) Z P(x)\frac{Z(x)}{Z}P(x)ZZ(x)然后 P(x,y) 就转化为判别式模型所需的条件概率分布:3.条件随机场条件随机场( Conditional Random Field, CRF)是一种给定输入随机变量 x求解条件概率 p(y| x) 的概率无向图模型。用于序列标注时特例化为线性链( linear chain )条件随机场。此时输人输出随机变量为等长的两个序列。3.1. 线性链条件随机场线性链条件随机场如下图所示:每个 Xt 上方有 3 个灰色节点代表 Xt 的 3 个特征当然还可以是任意数量的特征体现了特征的丰富性黑色方块是因子节点可以理解为一个特征函数f k ( y t − 1 , y t , x t ) f_k(y_{t-1},y_t,x_t)fk(yt−1,yt,xt)其中仅仅利用了X t X_tXt和Y t Y_tYt的特征称作状态特征利用了Y t − 1 Y_{t-1}Yt−1的特征则称作转移特征与感知机的特征函数相同。线性链条件随机场的定义如下:其中Z(x)为归一化函数:上式定义在所有可能的标注序列上。如果将所有特征函数与权重分别写作向量形式则线性链条件随机场的定义可简化为:对比结构化感知机的打分函数,由于给定实例 xZ(x) 就是一个常数 c, 可以发现结构化感知机打分函数与条件随机场的指数部分完全相同。 其不同点是感知机更新参数时只使用一个训练实例没有考虑整个数据集难免顾此失彼而条件随机场对数似然函数及其梯度则使用了整个数据集。即对上述CRF 条件概率公式对w \boldsymbol ww求导得 损失公式CRF 相当于在结构化感知机的基础上增加了「所有候选序列按概率加权」这一因素通俗比喻 看全班所有人的作弊可能性每个人按照自己的嫌疑程度都要受到相应的处理哪怕第一名是好学生只要还有其他人嫌疑不小依然要调整规则。4. 条件随机场训练下面是基于条件随机场的中文分词步骤第一步接受纯文本语料商 s 中 B 品 p 中 E 和 h 中 S 服 f 中 B 务 w 中 E A a 英 B K k 英 M B b 英 M 4 s 数 M 8 b 数 E每一行特征1 特征2 … 标签即序列的一个时刻X t , Y t X_t,Y_tXt,Yt,最后一列为输出变量 y 之外其它列都是输入变量 x第一行字商拼音s类别中标签B第一句话则对应的是x { 商 , 品 , 和 , 服 , 务 } , y g o l d { B , E , S , B , E } x\{\text{商},\text{品},\text{和},\text{服},\text{务}\},\quad y_{gold}\{B,E,S,B,E\}x{商,品,和,服,务},ygold{B,E,S,B,E}第二步提取特征。x是字符y是{B,M,E,S}转移特征状态特征y t − 1 y_{t-1}yt−1x t − 1 x_{t-1}xt−1x t x_{t}xtx t 1 x_{t1}xt1x t − 2 / x t − 1 x_{t-2}/x_{t-1}xt−2/xt−1x t − 1 / x t x_{t-1}/x_{t}xt−1/xtx t / x t 1 x_{t}/x_{t1}xt/xt1x t 1 / x t 2 x_{t1}/x_{t2}xt1/xt2根据特征表格提取出特征以“商”为例如下1. U00:# B2. U01:商 B3. U02:品 B4. U03:#/# B5. U04:#/商 B6. U05:商/品 B7. U06:品/和 B第三步特征代入损失公式损调节因子w \boldsymbol ww第四步 推理在获得稳定的w \boldsymbol ww再根据公式 找出最大可能y ^ arg max y P ( y ∣ x ) arg max y exp ( w ⋅ ϕ ( x , y ) ) Z ( x ) arg max y w ⋅ ϕ ( x , y ) \begin{aligned} \hat y \mathop{\arg\max}_{y} P(y|x) \\ \mathop{\arg\max}_{y} \frac{\exp\big(\boldsymbol w\cdot\boldsymbol\phi(x,y)\big)}{Z(x)} \\ \mathop{\arg\max}_{y} \boldsymbol w\cdot\boldsymbol\phi(x,y) \end{aligned}y^argmaxyP(y∣x)argmaxyZ(x)exp(w⋅ϕ(x,y))argmaxyw⋅ϕ(x,y)5. 主要参考《概率图 - 图表示 - 马尔可夫随机场MRF》《从零开始理解-概率图模型PGM》《条件随机场与序列标注》