0.概述

条件随机场（CRF）是一个可用于构建概率模型(probalilistic model)的框架，可用于分词(segment)和标记序列化(label sequence)数据。条件随机场提供了比隐马尔可夫模型（HMM）和随机文法(stochastic grammars)更多的优点，能放宽这些模型中所存在的强独立性猜想。CRF也可以避免MEMM(最大熵马尔可夫模型)、以及其它基于有向图模型的判别式马尔可夫模型的基本限制，这两个模型的状态与一些后续的状态有标注偏差。本文基于CRF的迭代式参数估计模型，比较了与HMM和MEMM在人工合成数据上和自然语言数据集上所生成模型的性能。

1.介绍

许多科学领域中的许多问题，都涉及到分词(segment)与序列化标注(label sequence)。对于这类问题，HMM和随机文法（stochastic grammars）很好理解并被广泛用于解决这类问题的概率模型。在计算生物学上，HMM和随机文法（stochastic grammer）已经成功用于生物序列对齐，寻找序列差异以求证进化族谱，分析RNA二次结构。在计算语言学和计算科学上，HMM和随机文法(stochastic grammars)也被广泛用于文本和语音处理，包括话题分段(topic segmentation)，词性标注（part-os-speech tagging），信息抽取，以及句法消歧。

HMM和随机文法(stochastic grammars)都是生成模型，为成对的观察和标注序列分配了联合概率；它们的参数训练目标是：对训练样本进行最大化联合似然。为了在观察和标注序列上定义一个联合概率，我们需要一个生成模型来枚举所有可能的观察序列，这通常需要一个表示方法来表示哪个观察值是适合任务的原子实体（词或核甘酸）。表示多种交叉特征(interacting features)、或者在观察值上的长范围依赖是不实际的。因为对于这样的模型，这种推断问题是很棘手的。

正因为存在这种困难，我们需要寻找另一种可替代的条件模型(conditional model)。给定观察序列后，该条件模型会给出所有可能标注序列的概率。因此，它不会在观察集上花费建模开销，它会在测试时确定。更进一步，标注序列的条件概率可以靠武断决定，而观察序列的非独立特征，不会强制模型来说明这些依赖的分布。对于相同的观察集，或相同观察序列的聚合属性（例如，文本布局），选中的特征可以表示成不同粒度的属性（例如：英文文本中的词和字符）。如果可能的话，标注之间的转移概率，不仅仅依赖当前观察(observations)，也可以依赖过去和将来的观察。相反的，生成模型必须在观察集上做出十分严格的独立性假设（例如，给定标注的条件独立性），以便更容易处理。

最大熵马尔可夫模型(MEMM)是条件概率序列模型(conditional probabilistic sequence model)，它具备上述提到的所有优点。在MEMM中，每个源状态(source state)都具有一个指数族模型(exponential model)，它的输入是观察集特征，输出是下一可能状态的分布。这种指数族模型，会在在最大熵框架上通过一个合适的迭代归一化方法(iterative scaling method)进行训练。相对于在常用的分词任务中使用的HMM，之前发布的指数族模型的结果展示了MEMM会增加召回率（recall）以及两倍的准确率(precision)。

MEMM和其它的基于下一状态分类器的非生成式有限状态机模型，比如判别式马尔可夫模型(discriminative Marklov model)，都有一个缺点：标注偏差问题（label bias problem）：从一个给定状态(State)完成后离开的转换概率(transition)，与其它状态相互对立，而非与模型中存在的所有转换概率相对对立。在概率术语中，转换分（transition score）指的是：给定当前状态以及观察序列，下一可能状态的条件概率。转换分的每个状态的归一化(per-state normalization of transition scores)，暗示着一个“得分块的保护（conservation of score mass）”，与所有到达某一状态的块(mass)一致，即：必须是分散在可能的后继状态之间。一个观察(observation)可以影响哪个目的状态获得该块(mass)，但不会影响总共有多少个块(mass)传递到给它。这就会引起了一个偏差，出去的转换(outgoing transition)会很少。在极端情况下，一个状态只有单个outgoing transition，会有效忽略观察集。在这种情况下，不同于HMM，Viterbi decoding不能基于分枝点后的观察向下查找分支，而基于状态转移结构的模型（models with state-transition structures），具有状态的稀疏连接链，它们不能被有效处理。这种在MEMM中的马尔可夫猜想(Markovian assumptions)，以及相类似的状态条件模型，会将某一状态的决策，与将来的决策相孤立，不会匹配连续状态间的实际独立性。

这篇paper介绍了条件随机场(CRF)，一种序列建模框架，它具有MEMM的所有优点，同时以一种有原则性的方式解决了标注偏差问题(label bias problem)。CRF与MEMM间的最不同之处是，给定当前状态，对于下一状态的条件概率，MEMM使用了一种每状态指数族模型(per-state exponential model)；而CRF则不同，给定观察序列，CRF会给整个序列标注的联合概率生成单一指数族模型。因此，不同状态下的不同特征的权重，可以相互间进行权衡。

我们也可以将一个CRF看成是一个有限状态机模型，它具有未归一化的转移概率。然而，不同于其它一些加权有限状态机方法(LeCun et al.,1998)，CRF分配了一个良好定义的(well-defined)在可能标注上的概率分布，通过最大似然或MAP估计进行训练。更进一步，loss函数是convex的，保证收敛到全局最优。CRF也很容易概括成上下文无关的随机文法(stochastic context-free grammars)的相似物，对于RNA的二等结构预测，以及nlp等问题很有用。

我们提出了该模型，描述两个训练过程，以及收敛的证明结构。我们也会给出在句法结构数据上的实验数据，来展示CRF，解决标注偏差问题（balel bias problem）的经典版本，并会比较CRF与HMM/MEMM间的性能。最后，我们会在基于词性标注任务上，证明这些结果，以及宣称的这些优点。

2.Label Bias Problem

经典的概率自动机(Pax, 1971)，判别式Markov模型(BOttou,1991)，最大熵标注器(Ratnaparkhi, 1996)，以及MEMM，以及非概率序列标注和分词模型（Punyakanok & Roth, 2001）都是标注偏差（Label bias）问题的潜在受害者。

例如，图1所展示了一个简单的有限状态机模型，它设计的目的是，区分两个词: “rib”和”rob”。假设，观察到的序列是：r i b。在第一个时间阶段，r同时满足初始状态的两个转换，因此两种转换间的概率块分布相同。接下来，我们观察到：i。状态1和状态4, 两者都只有一个outgoing transition。状态1经常在训练集中观察到该观察（observation)，状态4则在该观察(observation)中从未见过；与状态1相类似,状态4只能将所有块传递到单个outgoing transition，因为它不能生成该观察（observation），只能基于它。这样，带有单个outgoing transition可以有效的忽略它们的观察。更通用的说法，具有低熵的下一状态分布，将会更少地注意到观察(observations)。回到该例，上面的路径，以及下面的路径，具有相同的可能性和观察序列的依赖性。如果两个词，在训练集中很常见，从起始状态出发的转换，会更偏爱与它相关的转移(概率大)，该词的状态序列将总是获胜。这种行为可以在第5部分进行演示。

Leon Bottou（1991）讨论了label bias问题的两种解决办法。其中一种是，改变该模型的状态转换结构。在以上的示例中，我们可以压缩(collapse)状态1和状态4, 延迟它们的分支，直到我们得到一个判别式观察(observation)。这种操作是决策树determinization (Mohri,1997)的一个特例。但加权有限状态机并不总是可能的，即使可能，它也会导致组合爆炸。另一种解法是，从一个完全连接的模型出发，让训练过程来指出一个好的结构。但它将导致先验结构知识的使用，在信息抽取任务中这被证明很有用(Freitag & McCallum, 2000)

想得到合适的解，需要这样的模型：比起其它依赖于相应观察的转换，它可以通过让一些转换(transition)进行更强的“投票”，来对整个状态序列作出解释。这暗示了，分值块(score mass)将不会被保留，而独自的转换可以“放大”或”抑制”它们的接受块(mass)。在上面的例子中，从起始状态的转换，在路径分上会有很弱的影响，而从状态1和状态4上的转换，将会有更强的影响，取决于实际的观察，会进行放大或衰减，对Vierbi路径的选择，会有更高的贡献。

在相关的工作部分，我们讨论了其它启发式模型，它们能为状态序列做出全局解释。充分研究发现，CRF是可以用来在纯概率设置中做到这一点，并且能保证全局最大似然收敛的唯一模型。

3.CRF

X是一个随机变量，用来表示要标注的序列数据，Y表示在相应标签序列上的一个随机变量。Y中的所有成员Yi，假设都在一个有限标注y范围内。例如，X的范围可以是所有自然语言句子，Y的范围可以是这些句子的词性标注(pos taggings)，而y则是可能的词性集合(pos tags set)。随机变量X和Y是联合分布的，但在一个判别式框架上，我们会根据成对的观察和标注序列构建一个条件模型$ p(Y|X) $，而不会显式建模p(X).

定义：G = (V,E)是一个图， $ Y=(Y_v)_{v\in{V}} $， 其中Y通过G的顶点进行索引。接着(X,Y)是一个条件随机场(conditional random field)，当基于条件X，假设随机变量Yv服从该图的马尔可夫属性:

\[P(Y_v|X, Y_w, w\neq{v}) = p(Y_v|X,Y_w,w\sim{v})\]

其中，w~v，意味着w和v在G中是邻居。

这样，CRF就是这样一个随机场，它完全基于条件观察X。整篇paper中，我们严肃地假设，图G是确定不变的。在最简单和最重要的序列建模示例中，G是一个简单的链（chain）或线(line)：G = (V = {1,2,3,…,m}, E = {(i,i+1)})。其中，X也具有一个天然的图结构；但是总的来说，假设X和Y具有相同的图结构这一点不是必要的，X可以有任意的图结构。然后，在本篇paper中，我们最关注的是：序列X = (X1,X2,…Xn)，以及Y=(Y1,Y2,…,Yn).

如果图G=(V,E)，Y是一棵树（树上的一条链就是一个最简单示例），它的成员是边和顶点。因此，通过随机场（Hammersley & Clifford, 1971）的基本理论，对于给定X，在标注序列Y上的联合分布，具有以下的形式：

\(p_\theta(y|x) \subset exp(\sum_{e\in{E,k}}\lambda_{k}f_{k}(e,y|_{e},x)+\sum_{v\in{V,k}}\mu_{k}g_{k}(v,y|_{v},x))\) … (1)

其中，x是数据序列，y是标注序列，$ y|_{S} $是y的成员集合，与S子图中的顶点有关。

我们假设特征fk和gk是给定的，并且是固定不变的。例如，一个Boolean型的顶点特征gk，如果词Xi是大写的，则为true，而Yi的标注会是一个“合适的名词”。

参数估计问题，是从训练数据$ D=\left((x^{(i)},y^{(i)})\right)_{i=1}^{N} $中，根据经验分布p(x,y)， 决定参数θ = (λ1, λ2, … ; µ1, µ2, . . .) ，在第4部分，我们将描述一种迭代归一化算法，来最大化log-likelihood目标函数O(θ):

\[O(\theta)=\sum_{i=1}^{N}logp_\theta(y^{(i)}|x^{(i)}) \subset \sum_{x,y}p(x,y)logp_\theta(y|x)\]

作为特例，我们可以构造一个类HMM的CRF，通过为每个状态对(state pair)(y’,y)定义一个特征，对于为每个状态-观察对(state-observation pair)(y,x)，满足:

\[f_{y',y}(<u,v>,y|_{<u,v>},x)=\sigma(y_u,y')\sigma(y_v,y)\] \[g_{y,x}(v,y|_v,x)=\sigma(y_v,y)\sigma(x_v,x)\]

相应的参数$ \lambda_{y’,y} $和$ \mu_{y’,y} $与常见的HMM参数$ p(y’|y) $和$ p(x|y) $扮演着相似的角色。Boltzmann链模型也具有一个相类似的形式，但它使用单个归一化常数来生成(yield)一个联合分布；而CRF则使用依赖观察(observation-dependent)的归一化分布Z(x)来作为条件分布。

尽管它包含了类HMM的模型，条件随机场的类更具表现力，因为它允许在观察序列上存在独有的依赖。另外，特征不必完整指定一个状态(state)或观察(observation)，因此，模型也可以从较少的训练数据中被估计。另一个更吸引人的特性是，loss function是凸的（convexity）；确实，CRF会共享所有通用最大熵模型所具有的凸特性。

另外，我们假设：Y的依赖是基于条件X的，形成一条链。为了简化表示，我们添加start状态和stop状态：Y0=start和Yn+1=stop. 接着，我们将使用如图2所示的图结构。对于一个链结构来说，一个标注序列的条件概率，可以被表示成矩阵形式，这对于描述第4部分的参数估计和推断(parameter estimation and inference)算法来说很有用，假设$ p_\theta(Y|X) $是一个由(1)给定的CRF。对于在观察序列x上的每个位置i，我们定义了 $ |y|*|y| $ 矩阵的随机变量：$ M_{i}(x)=M_i(y’,y|x) $

\[M_i(y',y|x)=exp(\Lambda_{i}(y',y|x))\] \[\Lambda_i(y',y|x)=\sum_{k}\lambda_{k}f_{k}(e_i, Y|_{e_i}=(y',y),x)+\sum_{k}\mu_{k}g_{k}(v_{i},Y|_{v_i}=y,x)\]

其中ei是标注(Yi-1,Yi)的边(edge)，而vi是标注Yi的顶点。对比于生成模型，像CRF这样的条件模型，不需要枚举所有可能的观察序列x，因此可以从给定的训练或测试观察序列x和参数向量θ上，直接计算出这些矩阵。接着，归一化(配分函数:partition function)$ Z_\theta(x) $是(start,stop)条目上所有这些矩阵的乘积：

\[Z_\theta(x)=(M_1(x)M_2(x)...M_{n+1}(x))_{start,stop}\]

使用该符号，一个标注序列y的条件概率可以写成这样：

\[p_{\theta}(y|x)=\frac{\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)}{(\prod_{i=1}^{n+1}M_i(x))_{start,stop}}\]

其中，y0=start，yn+1=stop.

4.CRF的参数估计

我们现在描述两个迭代归一化算法来寻找参数向量θ，使得它能对训练数据求得最大化条件似然。两种算法都基于改进的迭代归一化算法(IIS)。（Della Pietra et al. (1997)）；证明技术可以基于辅助函数，可以被扩展成展示CRF算法收敛性。

迭代归一化算法（Iterative scaling algorithms），会合理选择$ \delta\lambda_k $和$ \delta\mu_k $，来更新权重：

\[\lambda_k \leftarrow \lambda_k+\delta\lambda_k\] \[\mu_k \leftarrow \mu_k+\delta\mu_k\]

特殊的，迭代归一化算法（IIS）会为一个边特征fk来更新$ \delta\lambda_k $，来求解：

\[(\hat{E})[f_k]=\sum_{x,y}\hat{p}(x,y)\sum_{i=1}^{n+1}f_k(e_i,y|_{e_i},x)=\sum_{x,y}\hat{p}(x)p(y|x)\sum_{i=1}^{n+1}f_k(e_i,y|_{e_i},x)e^{\delta\lambda_kT(x,y)}\]

而T(x,y)是总特征数：

\[T(x,y)=\sum_{i,k}f_k(e_i,y|_{e_i},x)+\sum_{i,k}g_k(v_i,y|_{v_i},x)\]

该方程同样会为顶点特征更新$ \delta\mu_k $，具有相同的形式。

然而，对方程右手边有效计算它们的指数和(exponential sums)是有问题的，因为T(x,y)是一个关于(x,y)的全局属性，动态规划(dynamic programming)会使用潜在不同的T，在序列上求和。为了处理该算法，我们的第一个算法会使用一个”松弛特征（slack feature）”。第二个算法T，会跟踪部分T。

对于算法S，我们定义了slack feature：

\[s(x,y)=S-\sum_{i}\sum_{k}f_k(e_i,y|_{e_i},x)-\sum_{i}\sum_{k}g_k(v_i,y|_{v_i},x)\]

其中，S是一个常数，以便$ s(x^{(i)},y) $，对于在训练集中所有的y，以及所有的观察向量x(i)，这样使得T(x,y)=S. 特征s是“全局”的，它不会对应于任何特定的边或顶点。

对于每个索引i=0,…,n+1,我们现在定义了前进向量(forward vector)$ \alpha_i(x) $，它的基本特例为：

\[\alpha_\theta(y|x)= \begin{cases}1&(y = start)\\0&(otherwise)\end{cases}\]

以及递归式：

\[\alpha_i(x)=\alpha_{i-1}(x)M_i(x)\]

相似的，后退向量$ \beta_i(x) $定义如下：

\[\beta_\theta(y|x)=\begin{cases}1&(y=stop)\\0&(otherwise)\end{cases}\]

其中：

\[\beta_i(x)^T=M_{i+1}(x)\beta_{i+1}(x)\]

有了这样的定义，更新方程为：

\[\delta\lambda_k=\frac{1}{S}log\frac{\hat{E}f_k}{Ef_k}\] \[\delta\mu_k=\frac{1}{S}log\frac{\hat{E}g_{k}}{Eg_k}\]

其中，

\[Ef_k=\sum_{x}\hat{p}(x)\sum_{i=1}^{n+1}\sum_{y',y}f_k(e_i,y|_{e_i}=(y',y),x)*\frac{\alpha_{i-1}(y'|x)M_i(y',y|x)\beta_i(y|x)}{Z_\theta(x)}\] \[Eg_k=\sum_{x}\hat{p}(x)\sum_{i=1}^{n}\sum_{y}g_k(v_i,y|_{v_i}=y,x)*\frac{\alpha_i(y|x)\beta_i(y|x)}{Z_\theta(x)}\]

在上面公式中，涉及到前进和后退向量的因子，与标准的马尔可夫模型(HMM)，具有相同的含义。例如：

\[p_\theta(Y_i=y|x)=\frac{\alpha_i(y|x)\beta_i(y|x)}{Z_\theta(x)}\]

对于给定的观察序列x, 上面的p即是标注Yi=y的边际概率。该算法与Darroch and Ratcliff (1972)相近，其中MART算法用于图片重构上。

算法S中的常数S可以相当大，因为实际上，它是与最长训练观察序列的长度是成比例的。作为结果，算法可以收敛很慢，在每次迭代时，朝着最大化的方向前进一小步。如果观察$ x^{(i)} $以及激活特征的数目十分不同，通过为各个观察序列独自跟综特征总数，可以获取一个快速收敛算法。

定义： $ T(x)=max_yT(x,y) $。算法T累积特征期望到计数器中，由T(x)进行索引。更特别的是，给定T(x)=t，我们使用已引入的前向-后向递归（forward-backward recurrences）来计算特征fk日期望ak,t，以及特征gk的期望bk,t。接着，我们的参数更新是：

\[\delta\lambda_k=log\beta_k\] \[\delta\mu_k=log\gamma_k\]

其中，βk和γk是由以下多项式方程得到的唯一的正定根：

\(\sum_{i=0}^{T_{max}}a_{k,t}\beta_k^t=\hat{E}f_k,\sum_{i=0}^{T_{max}}b_{k,t}\gamma_{k}^{t}=\hat{E}g_k\) … (2)

它可以很容易由牛顿法进行计算。

算法S和算法T的单个迭代，与HMM的Baum-Welch算法相比，具有基本相同的时间和空间复杂度。为了证明我们算法的收敛性，我们派生了一个辅助函数，来限制似然的变化；这个方法由Della Pietra et al. (1997)提出。完整的证明很详细；然而，这里我们给出了一个点子来如何派生辅助函数。为了简化解释，我们假设，只有边特征fk带有参数λk。

给定两个特征设置：θ=(λ1,λ2, . . .) ，θ’=(λ1+δλ1, λ2+δλ2, . . .)，我们使用一个辅助函数(auxiliary function)A(θ’,θ)，来限定目标函数的变化:

\[O(\theta')-O(\theta)=\sum_{x,y}\hat{p}(x,y)log\frac{p_{\theta'}(y|x)}{p_{\theta}(y|x)}\] \[=(\theta'-\theta)\hat{E}f-\sum_{x}\hat{p}(x)log\frac{Z_{\theta'}(x)}{Z_\theta(x)}\] \[\geq(\theta'-\theta)\hat{E}f-\sum_{x}\hat{p}(x)\frac{Z_{\theta'}(x)}{Z_\theta(x)}\] \[=\delta\lambda\hat{E}f-\sum_{x}\hat{p}(x)\sum_{y}p_\theta(y|x)e^{\delta\lambdaf(x,y)}\] \[\geq\delta\lambda\hat{E}f-\sum_{x,y,k}\hat{p}(x)p_\theta(y|x)\farc{f_k(x,y)}{T(x)}e^{\delta\lambda_kT(x)}\] \[=A(\theta',\theta)\]

其中，不等式遵循log和exp的凸特征（convexity）。按$ \delta\lambda_k $对A进行微分，以及设置结果为0,会产生方程(2).

5.实验

我们首先使用人造数据讨论了两组试验，用来强调CRF和MEMM间的不同。第一组试验，是第二部分讨论的标注偏差问题的直接验证。第二组实验，我们会使用HMM模型来生成人造数据，它们中的每一个都是一阶和二阶的混合模型。接着训练竞争型的一阶模型，并在测试集上进行比较。随着数据变成二阶，训练模型的测试误差率（test error rates）会上升。该试验通过一阶马尔可夫模型符合常用的建模实践（近似复杂局部和长范围依赖），正如自然数据中会发生的那样。我们的结果明显指出，即使当模型以相同的方式进行参数化，CRF也比MEMM或HMM更健壮，并能解决标注偏差问题（会影响MEMM的性能）。为了避免不同影响的混淆，MEMM和CRF在实验中不会使用观察集上的重复特征。最终，在词性标注试验中，我们确认了CRF优于MEMM。我们也展示了CRF和MEMM的重复特征，它们比HMM性能更好。

5.1 建模偏注偏差

从一个简单的HMM中生成的数据，它可以编码成一个噪声版本的有限状态网络，如图1所示。每个状态会触发相应的符号，对应概率29/32,其余符号的概率为1/32. 我们同时训练了MEMM和CRF，使用与HMM生成数据相似的拓朴。观察特征可以简化成观察符号的id。在运行了2000个训练和500个测试样本中，迭代归一化算法的收敛，CRF的error只有4.6%，而MEMM的error则为42%，这说明MEMM在判别分支时失败了。

5.2 建模混合阶的源数据

对于这些结果，我们使用五种标注：a-e($ |y|=5 $)，以及26个观察值，A-Z($ |X|=26 $);然而，对于y和X的size的范围取值，结果本质上是相同的。我们从一个混合阶的HMM生成数据，它具有状态转移概率：

\[p_\alpha(y_{i}|y_{i-1},y_{i-2})=\alpha p_2(y_i|y_{i-1},y_{i-2})+(1-\alpha)p_1(y_i|y_{i-1})\]

相似的，触发概率(emission probabilities)为：

\[p_\alpha(x_{i}|y_{i},x_{i-1})=\alpha p_2(x_i|y_{i},x_{i-1})+(1-\alpha)p_1(x_i|y_i})\]

这样，对于α = 0, 我们具有一个标准的一阶HMM。为了限制对于产生的模型的Bayes error rate的size，条件概率表Pα被限制为稀疏的。特别的，对于每个y,y’，$ p_\alpha(\cdot|y,y’) $具有至多两个非零条目。对于每个y,x’，$ p_\alpha(\cdot|y,x’) $可以至多三个非零条目。对于每个随机生成的模型，会生成1000个长度为25序列的样本，用于训练和测试。

在每个随机生成的训练集上，CRF会使用算法S进行训练（注意，因为序列长度，活跃特征数是常数，算法S和算法T是相同的）。该算法收敛相当慢，通常会在500次模型迭代后开始稳定。在我们的500 MHz Pentium PC上，每次迭代会花费0.2s。在相同的数据上使用MEMM进行迭代归一化训练，它不会需要前后向计算，因而更有效。MEMM训练收敛更快，在100次迭代在右就开始稳定。对于每个模型，Viterbi算法用于标注一个测试集；当使用forward-backward decoding来最小化每个符号的错误率时，试验结果不会有巨大变化。

运行结果如图3所示。每个plot都会比较了模型的两个类，每个point表示单个测试集上错误率。随着α的增加，错误率会总体增加，一阶模型会对二阶数据拟合失败。该图比较了模型参数$ \mu_y, \lambda_{y’,y}, \lambda_{y’,y,x} $；以及模型参数 $ \mu_y, \lambda_{y’,y}, \mu_{y,x} $本质上是相同的。如第一图所示，CRF总体上比MEMM更好，通常有10%-20%相对误差。（对于非常小的错误率的点，α < 0.01, 其中MEMM比CRF表现更好，这归因于CRF的训练迭代次数不够）

5.3 词性标注试验

为了证实我们的人造数据结果，我们也在Penn treebank词性标注数据集上比较了HMM，MEMM，以及CRF。其中，在结定的输入句子上的每个词，必须标注成45种标注之一。

我们在该自然语言数据集上运行了两个实验。第一个，我们在人造数据实验中训练了一阶HMM，MEMM，CRF模型，在训练集中为每个标注-词对(tag-word pair)引入了参数$ \mu_{y,x} $，以及为每个标注-标注对(tag-tag pair)引入了$ \lambda_{y’,y} $。结果与人造数据上观察到的相一致：HMM比MEMM效果更好，因为标注偏差问题，而CRF则比HMM表现更好。训练的错误率，使用了如图5.3所示的50%-50%的训练-测试集划分。结果与其它数据划分相类似。对于不在词汇表的词(oov：out-of-vocabulary)的错误率，它们不会在训练集中观察到，会独立报告结果。

在第二个实验中，通过添加少量拼字特征（orthographic features），我们充分利用了条件模型的威力：一个拼写是否从数字或大写字母开始，是否包含连字号，是否以如下的后缀结尾：-ing,-ogy,-ed, -s, -ly, -ion, -tion, -ity, -ies. 正如我们期望的那样，这里我们发现，MEMM和CRF极大地受益于这些特征的使用，整体错误率减小到了25%左右，oov错误率减小到50%左右。

6.CRF的更进一步

CRF的许多方面对于将来学习很有吸引力。这一部分我们提到两点。

条件随机场可以通过AdaBoost算法使用指数loss目标函数进行训练(Freund & Schapire, 1997). 通常的，boosting常用于分类问题，会有一个小的、固定数目的分类；boosting应用于序列化标注，可以将每个label看成是独立的分类问题(Abney et al., 1999)。然而，可以使用并行更新算法（Collins et al. 2000)来最小化单序列的指数loss。这需要一个forward-backward算法来有效计算特定的特征期望，沿着算法T的线，期望每个特征需要一个独立集合的前向和后向累加器。

CRF的另一个吸引人的特征是，你可以为它们实现有效地特征选择，以及特征引入算法。也就是说，不必指定要使用哪个(X,Y)特征，我们可以从特征生成规则开始，并在数据上自动评估生成特征的好处。特别地，特征引入算法，可以用来拟合条件随机场的动态规划技术。

致谢

对于标注偏差问题，感谢：Yoshua Bengio, Leon Bottou, Michael Collins，Yann LeCun，

对于相关工作部分，感谢：Andrew Ng、Sebastian。

参考

http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162&context=cis_papers