Michael Collins NLP Lecture 10
课程主页：http://www.cs.columbia.edu/~cs4705/
课程网盘地址：
链接：https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg
提取码：t1i3
这一讲介绍了对数线性标注模型（MEMMs）。
Chapter 8 MEMMs（对数线性标注模型）
8.1 介绍
在本章中，我们将回到标注问题。 我们之前描述了用于标注问题的隐马尔可夫模型（HMM）。本章将描述HMM的强大替代方案，即对数线性标注模型，它直接构建在对数线性模型的思想上。 对数线性标注模型的一个关键优势是它们允许高度灵活的表示，允许将特征轻松集成到模型中。
对数线性标注模型有时被称为“最大熵马尔可夫模型（MEMMs）”。本章将交替使用术语“MEMM”和“对数线性标注模型”。 MEMM这个名字最初由McCallum等人介绍。
对数线性标注模型是条件标注模型。 回想一下，生成标注模型定义了句子$x_1…x_n$与标注序列$y_1…y_n$的联合分布$p(x_1…x_n,y_1…y_n)$。 相反，条件标注模型定义条件分布
对应于标注序列$y_1…y_n$关于输入句子$x_1…x_n$的条件概率。 我们给出以下定义：
定义 1 （条件标注模型）
条件标注模型包括：
一组单词$\mathcal V$（这个集合可能是有限的，可数无限的，甚至是不可数无限的）。
一组有限的标注$\mathcal K$。
函数$p(y_1…y_n|x_1…x_n)$，使得：
对任意$\langle x_1…x_n,y_1…y_n \rangle \in \mathcal S$，
其中$\mathcal S$是所有序列/标注序列对$\langle x_1…x_n,y_1…y_n \rangle$的集合，其中$n\ge 1,x_i \in \mathcal V,i=1…n$以及$y_i \in \mathcal K,i=1…n$。
对于任何$ x_1…x_n,n\ge 1$以及$x_i \in \mathcal V,i=1…n$，
其中$\mathcal Y(n)$是所有标注序列$y_1…y_n$的集合，其中$y_i \in \mathcal K,i=1…n$。
给定条件标注模型，从句子$x_1…x_n$到标注序列$y_1…y_n$的函数定义为
因此，对于任何输入$x_1…x_n$，我们将最高概率标注序列作为模型的输出。
我们留下以下三个问题：
我们如何定义条件标注模型$p(y_1…y_n|x_1…x_n)$？
我们如何根据训练样样本计模型的参数？
对任何输入$x_1…x_n$，我们如何高效地找到
本章的其余部分将描述MEMM如何为这些问题提供解决方案。 简而言之，对数线性模型用于定义条件标注模型。 可以使用用于对数线性模型中的参数估计的标准方法来估计模型的参数。 MEMM做出马尔可夫独立假设，该假设与HMM中的马尔可夫独立性假设密切相关，并且允许使用动态规划有效地计算上述$\arg \max$。
8.2 三元MEMMs
本节介绍MEMM的模型形式。 我们专注于三元MEMM，它作出二阶马尔可夫假设，即每个标注取决于前两个标注。 对其他阶马尔可夫模型的推广，例如一阶（二元）或三阶（四元）MEMM，是直截了当的。
我们的任务是对任何输入序列$x_1…x_n$与标注序列$y_1…y_n $的如下条件概率建模
我们首先利用如下分解：
根据概率的链式法则，第一个等号是准确的。 第二个等号使用了三元组独立性假设，即任何$i\in \{1…n\}$，
这里我们假设
其中$\star$是模型中表示序列开始的特殊符号。
因此，我们假设随机变量$Y_i$与$Y_1…Y_{i-3}$关于整个输入序列$X_1…X_n$和前两个标注$Y_{i-2}$和$Y_{i-1}$条件独立。 这是一个三元独立假设，即每个标注仅依赖于前两个标注。 我们将看到这种独立性假设允许我们使用动态规划来有效地找到任何输入句子$x_1…x_n $的最高概率标注序列。
请注意，上述假设与三元HMM中的独立性假设有一些相似之处，即
关键的区别在于我们关于整个输入序列$x_1…x_n $和前两个标注$y_{i-2}$和$y_{i-1}$取条件概率。
最后一步是使用对数线性模型来估计概率
对于任何一对序列$x_1…x_n$和$y_1…y_n $，我们将第$i$个“历史”定义为四元组
因此，除了序列中的位置$i$之外，$h_i$还捕捉到序列中标注$y_i $的条件信息。 我们假设我们对任何历史$h_i$以及标注$y\in \mathcal K$有特征向量表示$f(h_i,y) \in \mathbb R^d$。特征向量可能会考虑任何历史$h_i$和标注$y$。作为一个例子，我们可能有如下特征：
第8.3节描述了一组更完整的示例特征。
最后，我们假设参数向量$\theta \in \mathbb R^d$，以及
将上述内容总结后会产生以下结果：
定义 2 （三元MEMMs）
三元MEMM包括
一组单词$\mathcal V$（这个集合可能是有限的，可数无限的，甚至是不可数无限的）。
一组有限的标注$\mathcal K$。
给定$\mathcal V$和$\mathcal K$，将$\mathcal H$定义为所有可能历史的集合。 集合$\mathcal H$包含形如$\langle y_{i-2},y_{i-1},x_1…x_n,i \rangle$的所有四元组，其中
以及$n\ge 1$，对$i=1…n,x_i \in \mathcal V$。 这里*是一个特殊的“开始”符号。
一个整数$d$，指定模型中特征的数量。
指定模型特征的函数$f: \mathcal H \times \mathcal K \to \mathbb R^d$。
参数向量$\theta \in \mathbb R^d$。
给定这些元素，我们定义条件标注模型：
其中$h_i =\langle y_{i-2},y_{i-1},x_1…x_n,i \rangle$以及
此时有许多问题。例如我们如何定义特征向量$f(h_i,y)$？ 我们如何从训练数据中学习参数$\theta $？ 我们如何对任意输入序列$x_1…x_n $找到概率最高的标注序列
以下部分回答了这些问题。
8.3 三元MEMMs中的特征
回顾三元MEMM中的特征向量的定义是函数$f(h,y)\in \mathbb R^d$，其中$h=\langle y_{-2},y_{-1},x_1…x_n,i \rangle$是历史，$y\in \mathcal K $是标注，$d$是指定模型中特征数量的整数。 对$j\in \{1…d\}$的每个特征$f_j(h,y)$可能对历史记录$h$以及标注$y$中的任何信息敏感。这将为模型带来很大的灵活性。 这是三元MEMM相对于三元HMM进行标注的主要优点：可以使用更丰富的一组特征进行标注任务。
在本节中，我们举例说明如何为词性（POS）标注问题定义特征。 我们描述的特征取自Ratnaparkhi（1996）; Ratnaparkhi的实验表明，他们在英语的词性标注问题上给出了很好的表现。 在本节中，我们假设历史$h$是一个四元组$\langle y_{-2},y_{-1},x_1…x_n,i \rangle$。特征如下：
单词/标注特征
一个示例单词/标注特征如下：
此特征对标注的单词$x_i $和该单词的建议标注$y$敏感。 在实际中，除了$\text{base/VB}$，我们将为一组非常大的单词/标注对引入这种形式的特征。例如，我们可以为训练数据中看到的所有单词/标注对引入此形式的特征。
这类特征允许模型捕获特定单词采取特定词性的趋势。 在这个意义上，它和三元HMM中的发射参数$e(x|y)$起类似的作用。 例如，给定上面给出的$f_{100}$的定义，如果$\theta_{100}$取很大的正数，那么$\text{base}$很可能被标注为$\text{VB}$；相反，如果$\theta_{100}$取很小的负数，那么$\text{base}$不大可能被标注为$\text{VB}$。
前缀和后缀特征
此特征对标注的单词$x_i$的后缀和建议的标注$y$很敏感。 在实际中，我们将介绍这种形式的大量特征。例如，在Ratnaparkhi的POS标注中，所有在训练数据中看到的长度为$4$的后缀都作为特征（与所有可能的标注一起）。
前缀特征的示例如下：
同样，大量前缀特征被使用。 Ratnaparkhi的POS标注器使用了训练数据中所有长度为$4$的前缀。
前缀和后缀特征对于英语和许多其他语言的POS标注以及其他任务都非常有用。 例如，在滨州树库中后缀$\text{ing}$和标注$\text{VBG}$常常一起出现，这是用于动名词的标注；还有很多其他的例子。
至关重要的是，为模型引入前缀和后缀特征非常简单。 这与用于标注的三元HMM形成对比，其中我们使用将低频词映射到捕获拼写特征的“伪单词”的想法。 在对数线性模型中对拼写特征（例如前缀和后缀特征）的集成远不如我们为HMM描述的方法那样特殊。 在实际中，当标注测试数据中不常见或根本没有在训练数据中看到的单词时，拼写特征非常有用。
三元，二元，一元标注特征
三元标注特征的示例如下：
此特征，与相关参数$\theta_{103 }$一起，与三元HMM中的$q(\text{VB}| \text{DT,JJ})$参数起类似作用，使模型了解三元标注$\langle\text{DT,JJ,VB}\rangle$是可能出现或不太可能出现。 针对大量标注三元组引入了这种形式的特征，例如在训练数据中看到的所有标注三元组。
以下两个特征是二元和一元标注特征的示例：
第一个特征允许模型了解二元标注$\text{JJ,VB}$是可能出现或不太可能出现；第二个特征允许模型了解标注$\text{VB}$是可能出现或不太可能出现。 同样，模型中通常会引入大量的二元和一元标注特征。
鉴于与三元特征的明显重叠，二元和一元特征乍一看似乎是多余的。例如，可能看起来特征$f_{104}$和$f_{105}$被特征$f_{103}$包含。具体来说，给定参数$\theta_{103},\theta_{104}$和$\theta_{105}$，我们可以将$\theta_{103}$重新定义为$\theta_{103}+\theta_{104}+\theta_{105}$，并且$\theta_{104}=\theta_{105}=0$，在这两组参数下，分布$p(y|x;\theta)$相同。因此，特征$f_{104}$和$f_{105} $显然可以消除。然而，当与参数估计的正则化方法结合使用时，二元和一元特征起着重要作用，类似于在平滑估计技术中使用“后退”估计$q_{ML}(\text{VB|JJ})$和$q_{ML}(\text{VB} )$。粗略地说，加上正则项，如果特征$f_{103}$中的三元组很少，则$\theta_{103}$的值不会在幅度上变得太大，而基于更多样本估计的参数值$\theta_{104}$和$\theta_{105}$将发挥更重要的作用。
其他上下文特征
Ratnaparkhi还使用了考虑$x_i$之前或之后单词，以及建议标注的特征。 示例特征如下：
同样，我们将引入许多这样的特征。 这些特征为模型添加了额外的内容，引入了$x_{i-1}$或$x_{i+1}$与建议标注之间的依赖关系。 再次注意，如何将此形式的上下文特征引入三元HMM并不是很明显。
其他特征
我们已经描述了Ratnaparkhi模型的主要特征。 他包括的其他特征包括：1）拼写特征，考虑被标注的单词$x_i$是否包含数字，包含连字符，或包含大写字母; 2）将$x_{i-2}$和$x_{i+2}$处的单词与当前标注$y$结合使用的上下文特征。
8.4 三元MEME中的参数估计
可以使用前一章中描述的对数线性模型的参数估计方法来执行三元MEMM中的参数估计。训练数据是$m$个样本$(x^{(k)},y^{(k)})$的集合，$k=1…m$，其中每个$x^{(k)}$是单词序列$x^{(k)}_1…x^{(k)}_{n_k}$，并且每个$y^{(k)}$是标注序列$y^{(k)}_1…y^{(k)}_{n_k}$。 这里$n_k$是第$k$个句子或标注序列的长度。 对于任何$k\in \{1…m\}$，$i\in \{1…n_k\}$，将历史$h_i^{(k)}$定义为$\langle y^{(k)}_{i-2},y^{(k)}_{i-1},x^{(k)}_1…x^{(k)}_{n_k},i \rangle$。 我们假设对于某个整数$d$，我们有一个特征向量定义$f(h,y)\in \mathbb R^d $，因此
正则化的对数似然函数为
第一项是参数$\theta $的数据的对数似然。 第二项是正则化项，它惩罚大的参数值。 正参数$\lambda $决定了两项的相对权重。优化方法用于查找最大化此函数的参数$\theta^*$：
总之，估计方法是前一章中描述的方法数线性模型中的参数估计的直接应用。
8.5 对MEMM解码：维特比算法的另一个应用
我们现在转向在三元MEMM下找到输入序列$x_1…x_n$的最可能的标注序列的问题；也就是找到
其中
以及$h_i =\langle y_{i-2},y_{i-1},x_1…x_n,i \rangle$。
首先，请注意上述内容和的三元HMM标注器的解码问题的相似性，其中三元HMM的解码问题是找到
抛开$q(\text{STOP}|y_{n-1},y_n)$项，我们基本上取代
为
两个解码问题的相似性导致三元组MEMM的解码算法与三元HMM的解码算法非常相似。我们再次使用动态规划算法。 算法如图8.1所示。 动态规划算法的基本情形与三元HMM的基本情况相同，即
递归的情况是
其中$h=\langle w,u,x_1…x_n,k \rangle$。（我们再次定义$\mathcal K_{-1}=\mathcal K_{0}=*$，并且$\mathcal K_{-1}=\mathcal K$，$k=1…n$。）
回想一下，三元HMM标注的递归情况是
因此我们简单地用$p(v|h;\theta)$代替$q(v|w,u)\times e(x_{k}|v)$。
该算法的证明与三元HMM的维特比算法的证明非常相似。 特别是，可以证明，对于所有$k\in \{0…n\},u\in \mathcal K_{k-1}, v\in \mathcal K_{k}$
其中$S(k,u,v)$是所有序列$y_{-1}y_0…y_k$的集合，其中$y_i\in \mathcal K_i, i=-1…k$以及$y_{k-1}=u,y_k=v$。
8.6 总结
总而言之，三元MEMM背后的主要思想如下：
我们首先进行独立性假设来推导出模型
然后假设
其中$h_i =\langle y_{i-2},y_{i-1},x_1…x_n,i \rangle$，$f(h,y)\in \mathbb R^d$是特征向量，$\theta \in \mathbb R^d$是参数向量。
可以使用用于对数线性模型中的参数估计的标准方法来估计参数$\theta $，例如通过优化正则化对数似然函数。
解码问题是找到
这个问题可以通过使用维特比算法的变体的动态规划算法来解决。该算法与三元HMM的维特比算法密切相关。
特征向量$f(h,y)$可以对历史记录$h$以及标注$y$中的任何信息敏感。 这是MEMM相对于HMM标注的主要优势：将特征引入模型更加直接。
本讲测验题
Coursera部分
1.
2.
(c)
3.
(a)(d)
4.
(c)
5.
利用公式可得