课程主页：http://www.cs.columbia.edu/~cs4705/

课程网盘地址：

链接：https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg
提取码：t1i3

这一讲介绍了对数线性模型。

Chapter 6 对数线性模型（Log-Linear Models）

1. 介绍

本文将描述对数线性模型，它在自然语言处理中得到了广泛的应用。对数线性模型的一个关键优势是它们的灵活性：正如我们将看到的，它们允许在模型中使用非常丰富的特征集，远比我们之前在课程中看到的简单估计技术更丰富（例如，我们最初为语言建模引入的平滑方法，后来应用于其他模型，如用于标注的HMM和用于解析的PCFG）。在本文中，我们将给出对数线性模型的动机，给出基本定义，并描述如何在这些模型中估计参数。在后续课程中，我们将看到这些模型如何应用于许多自然语言处理问题。

2. 动机

作为一个激励性的例子，再次考虑语言建模问题，其任务是对任意单词序列$w_1…w_{i}$，导出条件概率的估计

其中$i$可以是任意正整数。 这里$w_i$是文档中的第$i$个单词：我们的任务是对$w_i$这个单词的关于前面的单词序列$w_1…w_{i-1}$的条件分布建模。

​ 在三元语言模型中，我们假设

对于任何三元组$(u,v,w)$，$q(w|u,v)$是模型的参数。 我们研究了各种估计参数$q$的方法；作为一个例子，我们研究了线性插值，其中

这里每个$q_{ML}$是最大似然估计，并且$\lambda_1,\lambda_2,\lambda_3$是分配给每个估计的权重的参数（回想一下，我们有$\lambda_1 +\lambda_2+\lambda_3 = 1$的约束，以及对所有的$i$的$\lambda_i \ge 0$）。

​ 三元语言模型非常有效，但它们对上下文$w_1…w_{i-1 }$的使用相对较少。 例如，考虑上下文$w_1…w_{i-1 }$是以下单词序列的情况：

​ 另外假设我们想估计单词$w_i$为$\text{model}$的概率，即我们想要估计

除了文档中前面两个单词（在三元语言模型中使用）之外，条件概率可能和上下文的各种特征有关，这可能是估计下一个单词为$\text{model}$的概率的有用证据。 例如，我们可以考虑$\text{model}$关于单词$w_{i-2}$的条件概率，完全忽略$w_{i-1}$：

我们可能会根据前一个词是形容词的事实作出判断

这里$\text{pos}$是一个将单词映射到其词性的函数。（为简单起见，我们假设这是一个确定函数，即从单词到其基础词性的映射是明确的。）我们可能会根据前一个单词的后缀是“$\text{ical}$”的事实作出判断：

（这里的$\text{suff4}$是一个将单词映射到最后四个字符的函数）。我们可能会根据单词$\text{model} $没有出现在上下文中这一事实作出判断：

或者我们可能会根据$\text{grammatical}$一词确实出现在上下文中的事实作出判断：

简而言之，上下文中的所有类型的信息可用于估计该上下文中特定单词（例如，$\text{model} $）的概率。

​ 使用此信息的一种朴素方式是简单地扩展我们在三元语言模型中看到的方法。相比于结合三元，二元和一元估计，我们将结合更多的估计。 我们将再次估计反映每项估计的重要性或权重的参数$\lambda $。生成的估计将采用类似下面的形式（仅用于草图）：

问题是随着我们添加越来越多的条件信息，线性插值方法变得非常笨重。 在实际中，很难将这种方法扩展。 相反，我们将看到对数线性模型提供了一种更加令人满意的方法来合并多个上下文信息。

3. 第二个例子：词性标注

我们的第二个例子涉及词性标注。 考虑上下文是一系列单词$w_1…w_n$以及一系列标签$t_1…t_{i-1}$（这里$i<n$）的问题，我们的任务是对第$i$个标签的条件分布建模。 也就是说，我们希望对如下条件分布进行建模

​ 例如，我们可能有以下内容：

这里$w_1…w_n$是句子$\text{Hispaniola quickly … Hemisphere }$，前面的标签序列是$t_1…t_5 =\text{NNP RB VB DT JJ}$。 我们有$i = 6$，我们的任务对如下分布建模

也就是说，我们的任务是对句子中第$6$个单词$\text{base}$的标签的分布建模。

​ 在这种情况下，还有许多上下文信息可能有助于估计$t_i$值的分布。 具体而言，考虑估计$\text{base}$的标注为$\text{V}$的概率（即，$T_6= \text{V}$）。 我们可能会认为该概率取决于第$i$个单词：

我们也可以考虑关于前一个或两个标签的条件概率：

我们可能会考虑关于句子中的前一个单词的条件概率

或者关于下一个单词的条件概率

我们也可以考虑基于单词$w_6$的拼写特征的概率，例如$w_6$的最后两个字母：

（这里的$\text{suff2}$是一个将单词映射到最后两个字母的函数）。

​ 简而言之，我们再次有一个情形，其中各种上下文特征可能对于对感兴趣的随机变量（在这种情况下是第$i$个标注）的分布建模有用。 同样，当面对这个估计问题时，基于线性插值的扩展的简单方法将不幸地严重失败。

4. 对数线性模型

我们现在描述如何将对数线性模型应用于上述形式的问题。

4.1 基本定义

抽象问题如下。 我们有一些可能的输入，$\mathcal X$和一组可能的标签$\mathcal Y$。我们的任务是对任何$(x,y),x\in \mathcal X,y\in \mathcal Y$的条件概率建模

​ 例如，在语言建模任务中，我们在语言中有一些有限的可能单词，称为集合$\mathcal V$。集合$\mathcal Y$简单地等于$\mathcal V$。集合$\mathcal X$是满足$i\ge 1, w_j \in \mathcal V, j\in \{1…(i-1)\}$的可能的序列$w_1…w_{i-1}$的集合。

​ 在词性标注示例中，我们有一些可能的单词集$\mathcal V$和一组可能的标签$\mathcal T$。 集合$\mathcal Y $简单地等于$\mathcal T$。集合$\mathcal X$是如下形式的内容的集合

其中$n\ge 1$是一个整数，指定输入句子的长度，$w_j \in \mathcal V$，其中$ j\in \{1…n\}$，以及$t_j \in \mathcal T$，其中$j\in \{1…(i-1)\}$。

​ 我们将假设整个$\mathcal Y$是一个有限集。 集合$\mathcal X$可以是有限的，可数无限的，甚至是不可数无限的。

​ 然后将对数线性模型定义如下：

定义 1 （对数线性模型）

对数线性模型由以下元素组成：

  • 可能输入的集合$\mathcal X$
  • 可能标签的集合$\mathcal Y$。假设集合$\mathcal Y$为有限集。
  • 正整数$d$，指定模型中的特征和参数的数量。
  • 将任何$(x,y)$对映射到特征向量$f(x,y)$的函数$f:\mathcal X \times \mathcal Y \to \mathbb R^d$。
  • 参数向量$v\in \mathbb R^d$。

对于$x\in \mathcal X, y\in \mathcal Y$，模型定义了条件概率

这里$\exp(x)=e^x,$，$v.f(x,y)=\sum_{k=1}^d v_k f_k(x,y)$是$v$和$f(x,y)$之间的内积。$p(y|x;v)$为“在参数$v$下，$y$关于$x$的条件的概率”。

​ 我们后面更详细地描述模型，首先关注特征向量$f(x,y)$，然后给出如下模型背后的直觉

5. 特征

如前一节所述，对于任何$(x,y )$对，$f(x,y)\in \mathbb R^d$是表示该对的特征向量。 该向量中的每个分量$f_k (x,y),k=1…d$被称为特征。 这些特征允许我们结合标签$y$来表示输入$x$的不同属性。 每个特征都有一个相关参数$v_k$，其值使用一组训练样本进行估计。 训练集由一系列示例$(x^{(i)},y^{(i)})$组成，其中$i=1…n$，$x^{(i)}\in \mathcal X,y ^{(i)}\in \mathcal Y$。

​ 在本节中，我们首先给出一个示例，说明如何为语言建模问题构建特征，如本讲义前面所介绍的那样；然后我们将描述定义特征时的一些实际问题。

5.1 语言模型示例的特征

再次考虑语言模型问题，其中输入$x$是单词序列$w_1w_2…w_{i-1}$，标签$y$是单词。 图$1$显示了此问题的一组特征示例。 每个示例都是一个示性函数：也就是说，每个特征都是一个返回1或0的函数。在NLP应用程序中，将示性函数作为特征是非常常见的。 如果输入$x$与标签$y$结合的某些属性为真，则每个特征返回$1$，否则返回$0$。

前三个特征，$f_1, f_2$和$f_3$类似于常规三元语言模型中的一元，二元和三元特征。 如果标签$y$等于单词$\text{model} $，则第一个特征返回$1$，否则返回$0$。 如果二元组$\langle w_{i-1}, y\rangle$等于$\langle\text{statistical model}\rangle$，则第二个特征返回$1$，否则返回$0$。 如果三元组$\langle w_{i-2}, w_{i-1},y\rangle$等于$\langle\text{any statistical model} \rangle$，则第三个特征返回$1$，否则返回$0$。 回想一下，每个特征都有参数$v_1,v_2$或$v_3$； 这些参数将扮演与常规三元语言模型中的参数类似的角色。

​ 图1中的特征$f_4…f_8$考虑的特性超出了一元，二元和三元特性。 特征$f_4$将单词$w_{i-2}$与标签$y$一起考虑，忽略单词$w_{i-1}$；这种类型的特征通常被称为“跳跃二元组”。 特征$f_5$考虑前一个单词的词性（再次假设前一个单词的词性已知，例如通过从单词到其词性的确定性映射，或者可能通过POS标签输出单词$w_1…w_{i-1}$的词性）。 特征$f_6$考虑前一个单词的后缀，特征$f_7$和$f_8$考虑输入$x=w_1…w_{i-1}$的各种其他特征。

​ 从这个例子中我们可以看到，可以使用作为示性函数的特征将大量的上下文信息合并到语言模型问题中。

5.2 特征模板

我们现在讨论定义特征的一些实际问题。 在实际中，定义特征的关键思想是特征模板。 我们在本节介绍这个想法。

​ 回想一下前一个例子中的前三个特征如下：

这些特征跟踪一元组$\langle \text{model} \rangle $，二元组$\langle\text{statistical model}\rangle$和三元组$\langle\text{any statistical model}\rangle$。
这些特征中的每一个都针对特定的一元组，二元组或三元组。在实际中，我们想要定义更多种类的特征，这些特征考虑训练数据中看到的所有可能的一元组，二元组或三元组。 为此，我们使用要特征模板生成大量特征。

​ 举个例子，这是一个三元组的特征模板：

定义 2 （三元特征模板）

对于在训练数据中看到的任何三元组$(u,v,w)$，创建一个特征

其中$N(u,v,w)$是将训练数据中的每个三元组映射到唯一整数的函数。

​ 关于这个定义的几点说明：

  • 请注意，模板仅为训练数据中看到的三元组生成三元组函数。 这种限制有两个原因。 首先，为每个可能的三元组生成一个特征是不可行的，即使是那些在训练数据中没有看到的特征：这将产生$|V|^3$个特征，其中$|V| $是词汇表中的单词数，这将是一组非常大的特征。 其次，对于在训练数据中没有看到的任何三元组$(u,v,w) $，我们没有证据来估计相关的参数值，所以在任何情况下都没有意义。

  • 函数$N(u,v,w)$将每个三元组映射到一个唯一的整数：也就是说，它是一个函数，对于任何满足$u\neq u’$或$v\neq v’$或$w\neq w’$的三元组$(u,v,w)$和$(u’,v’,w’)$，我们有

    在特征模板的实现中，函数$N$通过散列函数实现。 例如，我们可以使用哈希表来散列字符串，例如将$\text{trigram=any_statistical_model}$映射到整数。 每个不同的字符串都被散列为不同的整数。

继续该示例，我们还可以定义二元和一元特征模板：

定义 3 （二元特征模板）

对于在训练数据中看到的任何二元组$(v,w)$，创建一个特征

其中$N(v,w)$将每个二元组映射到唯一的整数。

定义 4 （一元特征模板）

对于在训练数据中看到的任何一元组$(w)$，创建一个特征

其中$N(w)$将每个一元组映射到唯一的整数。

​ 我们实际上需要对这些定义稍微小心一些，以避免三元组，二元组和一元族函数之间的重叠。 将$T,B,U$定义为训练数据中看到的三元组，双元组和一元组。定义

然后我们需要确保这些集合之间没有重叠——否则，两个不同的$n$元组将映射到同一个特征。 更正式地说，我们需要

在实现对数线性模型时很容易确保这一点，使用单个哈希表来散列如下字符串

到不同的整数。

定义 5 （长度为4的后缀模板）

对于在训练数据中看到的每对$(v,w)$，其中$v=\text{suff4}(w_{i-1})$和$w=y$，创建一个特征

其中$N(\text{suff4}=v,w)$将每对$(v,w )$映射到唯一的整数，与模型中使用的其他特征模板没有重叠（其中重叠的定义类似于上面的等式$2$）。

5.3 特征稀疏性

我们上面定义的特征的一个非常重要的特性是特征稀疏性。 许多NLP应用中的特征数量$d$可能非常大。 例如，仅使用上面定义的三元组模板，我们将对训练数据中看到每个三元组定义一个特征。 看到成百上千甚至数百万个特征的模型并不奇怪。

​ 上述现象引起了对所得模型效率的明显关注。 但是，我们在本节将描述特征稀疏性会如何导致高效模型。

​ 关键的观察结果如下：对于任何给定的$(x,y)$，满足如下条件的$k\in \{1…d\}$的数量通常非常小：

并且通常比特征总数$d$小得多。 因此，除了非常小的特征子集之外的所有特征都是$0$：特征向量$f(x,y)$是非常稀疏的位串，其中几乎所有特征$f_k(x,y)$都等于$0$，并且只有少数特征等于$1$。

​ 作为一个示例，考虑语言模型的例子，其中我们仅使用之前所述的三元，二元和一元模板。 此模型中的特征数量很大（它等于训练数据中看到的不同三元组，二元组和一元组的数量）。 然而，可以立即看出，对于任何$(x,y )$，最多三个特征是非零的（在最坏的情况下，$(x,y ) $包含三元组，二元组和一元组特征，这些特征都在训练数据中出现，所以总共给出三个非零特征）。

​ 在实现对数线性模型时，具有稀疏特征的模型可以非常高效，因为不需要明确地表示和操作$d$维特征向量$f(x,y)$。 相反，实现函数（通常通过散列表）来计算任何$(x,y )$非零特征的索引，通常更有效：即，计算如下集合的函数

这个集合在稀疏特征空间中很小——例如单独使用三元/二元/一元特征，集合的大小最多为$3$个。通常，使用哈希函数在$O(|Z(x,y)|)$时间内计算$Z(x,y)$是直截了当的。 注意$|Z(x,y)| \ll d $，因此这比明确地计算所有$d$个特征效率要高得多，而这个操作将花费$O(d)$的时间。

​ 作为一个有效计算$Z(x,y) $如何有用的例子，考虑内积的计算

该计算在对数线性模型中是核心。 一种朴素的方法将依次迭代所有$d$个特征，这将花费$O(d)$的时间。 相反，如果我们利用如下恒等式

因此，仅查看非零特征，我们可以在$O(|Z(x,y)|) $时间内计算内积。

6. 对数线性模型的模型形式

我们现在将更详细地描述对数线性模型的模型形式。 回想一下，对于任何$(x,y)$，其中$x\in \mathcal X $以及$y\in \mathcal Y$，模型下的条件概率是

​ 内积

在这个表达式中发挥关键作用。 再次，为了说明，请考虑我们的语言模型示例，其中输入$x=w_1…w_{i-1} $是以下单词序列：

​ 计算文档中下一个单词关于$x$的条件分布的第一步，计算每个可能标签$y$的内积$v.f(x,y)$（即，对于词汇表中的每个可能单词）。 例如，我们可能会计算以下值（我们只显示几个可能的单词的值——实际上我们会计算每个可能单词的内积）：

请注意，内积可以在实数中取任何值。 直观地，如果单词$y$的内积$v.f(x,y)$很大，则表示在给定上下文$x$的情况下该单词具有较高的概率。 相反，如$v.f(x,y)$很低，则表明$y$在此上下文中的概率较低。

​ 内积$v.f(x,y) $可以取实数中的任何值；然而，我们的目标是定义条件分布$p(y|x)$。 如果我们对任何标签$y$计算

我们现在有一个大于$0$的值。如果$v.f(x,y)$很大，则该值很大；如果$v.f(x,y)$很低，例如如果它很小的负值，则该值将很小（接近零）。

​ 接下来，如果我们将上述数量除以

得到

那么很容易验证我们有一个形式良好的分布：即

因此，公式3中的分母是归一化项，它确保我们有一个总和为$1$的分布。 总之，函数

执行一个转换，它将一组值$\{v.f(x,y):y\in \mathcal Y\}$作为输入，其中每个$v.f(x,y)$可以取实数中的任何值，然后输出关于标签$y\in \mathcal Y$的概率分布。

​ 最后，我们考虑对数线性模型的名称源自何处。 从以上定义得到

其中

第一项$v.f(x,y)$关于特征$f(x,y)$是线性的。 第二项$g(x)$仅取决于$x$，不依赖于标签$y$。 因此，对数概率$\log p(y|x;v) $关于特征$f(x,y) $是线性函数，只要我们保持$x$固定；这证明了“对数线性”一词的合理性。

7. 对数线性模型中的参数估计

7.1 对数似然函数和正则化

我们现在考虑对数线性模型中的参数估计问题。 我们假设我们有一个训练集$(x^{(i)}, y^{(i)})$，其中$i\in \{1…n\}, x^{(i)} \in \mathcal X, y^{(i)} \in \mathcal Y$。

​ 给定参数值$v$，对于任何样本$i$，我们可以计算在模型下的对数条件概率

直观地，该值越高，模型越适合这个特定的例子。 对数似然考虑训练数据中样本的对数概率的总和：

这是参数$v$的函数。对于任何参数向量$v$，$L(v)$的值可以解释为参数向量与训练样例的拟合程度的度量。

​ 我们将考虑的第一种估计方法是最大似然估计，我们选择参数为

在下一节中，我们将介绍如何有效地找到参数$v_{ML}$。 直观地，该估计方法尽可能找到适合数据的参数。

​ 最大似然估计可能会遇到问题，特别是在模型中的特征数量非常大的情况下。 为了说明这点，再次考虑语言模型模问题，并假设我们有三元，二元和一元特征。 现在假设我们有某个三元组$(u,v,w) $，它只在训练数据中看到过一次；具体来说，假设三元组是$\text{any statistical model}$，并假设仅在第$100$个训练样本中看到这个三元组。 更确切地说，我们假设

另外，假设这是训练数据中唯一满足$u=\text{any}, v=\text{statistical}$的三元组$(u,v,w)$。 在这种情况下，可以证明$v_{100}$的最大似然参数估计是$+\infty$，事实上，当$v_{100}= +\infty$时，

​ 实际上，对于常规三元模型的最大似然估计，我们碰到的情况和这里非常相似，对于三元组，我们有

正如本课程前面所讨论的那样，这个模型显然不够平滑，并且它对新的测试示例的推广很差。基于二元组$\text{any statistical}$据曾经被看到过一次，并且在那个例子中，二元组后面跟着单词$\text{model}$，然后按如下方式赋值并不合理

​ 对数线性模型产生的问题的一个非常常见的解决方案是修改公式$4$中的目标函数，使其包括正则化项，防止参数值变得太大（并且特别地，防止参数值发散到无穷大）。 常见的正则化项是参数值的$L_2$范数，即

这里$||v||$是向量$v$的长度或欧几里德范数；即，$||v|| =\sqrt{\sum_k v_k ^2}$。 修改后的目标函数是

其中$\lambda >0$是一个参数，通常通过交叉验证的方法来选择。 我们再次选择参数以最大化目标函数：即，我们的最优参数值是

​ 修改公式5中目标函数的背后的关键思想是现在我们平衡两个不同的项。 第一项是训练数据的对数似然，可以解释为参数$v$与训练样本的匹配程度。 第二项是对大参数值的惩罚：它鼓励参数值尽可能接近零。 参数$\lambda $定义了两项的相对权重。 在实际中，最终参数$v^*$将是在尽可能拟合数据和保持它们的值尽可能小直接的折中。

​ 在实际中，正则化项的使用在对数线性模型的平滑方面非常有效。

7.2 找到最优参数

首先，考虑找出最大似然参数估计：即找到

其中

​ 坏消息是，在一般情况下，最大似然参数$v_{ML}$没有封闭形式的解。好消息是找到$\arg \max_{v} L(v)$是一个相对容易的问题，因为$L(v) $可以被证明为凸函数。 这意味着简单的梯度上升法将相对快速地找到最佳参数$v_{ML}$。

​ 图$2$给出了用于优化$L(v) $的基于梯度的算法。参数向量初始化为全零的向量。 在每次迭代时，我们首先计算$k=1…d$的梯度$\delta _k$。 然后我们沿着梯度的方向移动：更确切地说，我们令$v\leftarrow v+\beta’ \times \delta$，其中$\beta’$是给出目标函数的最佳移动距离。 这是一种“爬山”法，在每个点我们计算最陡的方向（即梯度的方向）; 然后我们朝那个方向移动使$L(v)$最大的距离。

​ 如图2所示，简单的梯度上升可以很慢地收敛。 幸运的是，有许多基于梯度的优化的标准包，它使用更复杂的算法，并且提供了更快的收敛。 作为一个示例，用于对数线性模型中的参数估计的常用方法是LBFG。 LBFG也是一种梯度上升方法，但它在每一步都能更智能地选择搜索方向。 然而，它依赖于在每个步骤中对于$k=1…d$的$L(v)$和$\frac {dL(v)}{dv_k}$的计算——实际上这是关于被优化的函数所需的唯一信息。 总之，如果我们可以有效地计算$L(v)$和$\frac {dL(v)}{dv_k}$，则使用现有的基于梯度的优化包（例如，基于LBFG）来找到最大似然估计是简单的。

​ 正则化目标函数的优化，

可以使用基于梯度的方法以非常类似的方式执行。$L’(v)$也是凸函数，因此基于梯度的方法将找到参数估计的全局最优。

​ 剩下的一步是描述梯度

以及

如何计算。这是下一节的主题。

7.3 梯度

我们首先考虑如下导数

其中

对于任何$k\in \{1…d\}$，容易得到（参见本讲义的附录）

其中

公式6中的表达具有非常直观的形式。 表达式的第一部分，

简单地说，在训练样样本上特征$f_k$等于$1$的次数（假设$f_k$是示性函数；即，假设$f_k (x^{(i)},y^{(i)})$是$1$或$0$）。 表达式的第二部分，

可以解释为特征等于$1$的期望次数，其中期望是关于由当前参数指定的如下分布取的

梯度为这两项之差。 可以看出，梯度很容易计算出来。

​ 梯度

其中

可以用类似的方式推导，我们有

因此

因此，与公式6中的梯度的唯一区别是该表达式中增加了$-\lambda v_k$项。

A 导数的计算

在本附录中，我们将展示如何推导出导数的表达式，如公式6所示。 我们的目标是找到下式的表达式

其中

​ 首先，考虑单项$\log p(y^{(i)}|x^{(i)};v)$。 因为

我们有

此表达式中第一项的导数很简单：

​ 现在考虑第二个项。 该项的形式如下

其中

根据通常微分的规则，

此外，还可以验证

因此

​ 结合公式8和公式12可得

本讲测验题

Coursera部分

1.

结果为(a)

2.

一个样本会产生一个特征，所以结果为(a)

3.

4.

一共有如下几种特征：

所以答案为

5.

所以分数为

6.

答案为

7.

所以答案为

8.

注意有

所以

9.

注意有

所以