用于序列标注的CRF模型

文章：Log-linear models and conditional random fields

一、对数线性模型

模型对x下y的条件概率建模。

Fj(x,y)为特征函数，是x与y的对应性度量，每种特征都表征一种不同类型的对应性。相关的参数，是权重，表示该特征函数的影响。wj=0表示Fj与y的预测无关。人定义特征函数，算法学习权重表示。

Z(x,w)为标准化因子（需要计算标准分数时候用到）

模型预测标签：（x下最大概率标签）

条件概率模型可简化为下面的形式：

这种形式也称为softmax函数

二、特征函数

1. 是什么

特征函数表示一种映射关系，

2. 定义

一般会使用特征模板一次定义多个特征函数。

上述特征函数详解：

j表示类，xi表示向量的第i个部分，j = i + (c-1)d，对于i=1到d，c=1到C

除了y标签的候选值c，这些特征函数的每个都是0。 积累：J = dC

（一个逻辑链接）

a索引x函数的集合，b缩影y函数集合。上面的xi*I是该函数的特例，Aa(x)、Bb(y)是二值表征。

对数线性模型，

三、条件随机场

线性链条件随机场

词性标注是一个结构性预测仍无，目标是预测词性标注标签。

结构表示标签有内部结构。

词性标注比较难，不同股标准分类器学习任务，存在三个困难，第一，只学习单词分类器会丢失很多信息。相邻标签的影响必须纳入考虑。第二，不同句子有不同长度，如何用固定的长度向量表示整个句子？第三，所有可能的标签序列集合构成了非常大的标签。

线性条件随机场是一种将对数线性模型应用于这类型任务的一种方法。

label是对象的label tag是单位对象的标注

标准对数线性模型是前面的公式

为了预测输入句子的label，n为label长度，那么函数如下：

首先是特征的加和标准化，整个例子的特征值又需要通过例子中包含的元素的特征值求和获得。求和所有位置的特征值，会获得特征函数的固定集合，没有不是固定长度的烦恼。fi的值取决于yi、yi-1、x（整个句子）、i（位置）

模型训练，最优化，得到参数向量

如何求得w满足以上的最大值，y_存在很多种。

如何不要列举所有可能的y_得到最优解

训练中想要最大化的函数不一定是测试数据想要最大化的哈数。传统地，用regulatization在训练数据上最大化对数条件概率。

除了这样的最大化，还可以最大化预测的赚取恶心，最小化平均方差（标签为数值类型），最优化真实和预测标签的距离度量。

最基本的问题是：我们单单想最优化预测值，还是大量预测值的函数最优化。

对于一个长序列，正确预测整个序列非常难，概率较小。

四、参数的训练

线性链CRF的推理算法

忽略分母以及指数，那么我们需要计算：

在考虑单个输入x_的情况下，x_参数就不必考虑了，i参数是求和的标，也不用假如g，对于每个igi都是一个不同的函数。

每个gi的参数只有两个标签纸，其他的都是固定的。

一直x、w和i，函数gi表示为m*m的向量，m是tags集合大小。

计算该矩阵需要O(m^2*J)的时间。

定义最优label：（注：k的tag要求=v）

扩展：

简化：

一个v需要O(m)时间。那么每个v计算求和就是O(m^2)时间

最后的优化计算：

以上：通过HMM计算最短路径（维特比算法）变种

时间O(m^2nJ + m^2n)  n是y_长度，J是特征大小。

大部分特征值是0，J会非常小。

是y的长度，而非x的长度，输入x事实上不需要是序列，因为它被看做一个单元，可以是二维的，比如图等，也可以是集合。

五、梯度

最优化条件概率，因为是最大化概率，所以要用到梯度上升算法。

对于随机梯度上升（在线梯度上升），通过单个训练样本更新参数。

推导：