统计学习方法(7)---CRF

CRF

Posted by weber on February 7, 2020

conditional random field,CRF

1. 一句话概括CRF

CRF是给定一组输入序列条件下另一组输出序列的条件分布模型。

1.1 线性链条件随机场

随机场:若干个位置组成的整体,当给每个位置按某种分布赋予一个值后,其全体就叫随机场。

马尔可夫随机场:每个位置的赋值仅仅与其相邻的位置的赋值有关。

条件随机场:在给定随机变量X的条件下,随机变量Y的马尔可夫随机场,在词性标注时,X为词,Y为词性。

线性链条件随机场

设$𝑋=(𝑋_1,𝑋_2,…𝑋_𝑛),𝑌=(𝑌_1,𝑌_2,…𝑌_𝑛)$均为线性链表示的随机变量序列,在给定随机变量序列$X$的情况下,随机变量$Y$的条件概率分布$P(Y|X)$构成条件随机场,即满足马尔科夫性:

条件随机场定义

1.2 三种表示方式

1.2.1 参数形式

其中,$t_k(y_{i-1},y_i,x,i)$为定义在边上的转移特征,依赖于当前时刻和前一时刻的位置,K为该结点的转移特征函数的总个数;$s_l(y_i,x,i)$为定义在结点上的状态特征,依赖于当前位置,L为该结点的状态特征函数的总个数。Z(x)为所有序列Y的和,即归一化因子。

1.2.2 简化形式

其中,

其中,

1.2.3 矩阵形式

其中,

有矩阵

2. 三个问题

2.1 概率计算

已知输入序列x,输出序列y,模型参数w,特征函数fk

  1. 求解条件概率$P(Y_i=y_i|x)$ 和$P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$
  2. 联合分布和条件分布的数学期望。

2.1.1 前向后向算法

定义

其中,$[M_{i}(y_{i-1},y_i,x)]$为从 $y_{i-1}$ 转移到 $y_i$ 的非规范化概率。

假设 yi 的可能取值有 m 种,则:

同理,有

可以得到

2.1.2 条件概率

2.1.3 数学期望

得到了条件概率,很好求解联合分布和条件分布的数学期望。

已知特征函数为:

其关于P(y x)的数学期望:

同理,P(y,x)的期望:

2.2 学习

描述:给定训练数据集X,对应标记序列Y,K个特征函数 fk(y,x),学习参数wk,并求条件概率Pw(y|x)

输入:特征函数$f_k(y_{i-1},y_i,x,i)$,观测序列 $x=(x_1,x_2,…,x_n)$,状态序列 $y=(y_1,y_2,…,y_n)$,

输出:权值 $\hat w_k$,模型$P_w(y|x)$

思路:使用随机梯度下降来学习。

  1. 条件概率满足条件:
  1. 极大似然:
  1. 转化为损失:
  1. 求梯度:

2.3 解码

输入:特征函数$f_k(y_{i-1},y_i,x,i)$,权值 $w_k$,观测序列 $x=(x_1,x_2,…,x_n)$

输出:最优路径 y

步骤:

  1. 初始化:
  1. 递归:
  1. 回溯:

3. CRF应用

3.1 中文分词

分词的输入为一句话(文字序列)x,要预测每个词的标签 {B,E,M,S} ,对应到CRF。

通过训练数据语料,可以学习参数wk;状态特征根据语料构造,转移特征固定为4x4=16个。

再预测测试数据的文字序列,即CRF的维特比算法。

3.2 词性标注

与中文分词类似。