您的位置: 首页  >  文章  >  哥伦比亚NLP 第二章

哥伦比亚NLP 第二章

分类: 文章 • 2025-02-27 16:53:05

哥伦比亚NLP 第二章

目录

  • 标记问题(Tagging(Tagging problem)problem)
  • 生成模型(Generative(Generative model)model)
  • 隐藏马尔可夫模型(Hidden(Hidden markovmarkov model)model)
  • 隐藏马尔可夫的维特比算法(Viterbi algorithm)
  • 总结

标记问题

词性标注(Part−of−Speech(Part-of-Speech Tagging)Tagging)

  • 词性标注的输入是一个句子或文本，输出是每个词对应的词性。
  • 词性标注的困难在于，在很多语言中很多词具有不同的词性，需要结合具体语境分析判断才能确定最终的词性。
    哥伦比亚NLP 第二章
  • 在上图所示的例子中，ProfitProfit具有名词和动词两种词性，toppingtopping在这里是动词词性但是它也有名词词性的语意。在英语以及很多语言中，许多词在不同语境下有不同词性与不同语意，需要结合语境综合判断。

命名实体识别(Named(Named EntityEntity ExtractionExtraction asas Tagging)Tagging)

哥伦比亚NLP 第二章

  • 命名实体识别的输入是一个句子或文本，输出是标记好这个词是否是实体以及是哪一类命名实体。上图中NANA代表不是实体，其他分类代表不同类型的实体。

我们的目标

  • 我们需要学习一种算法或函数，通过这种算法或函数我们可以将一个训练集映射到他们的标记上。换句话说，我们需要设计一套规则去标记训练集。

生成模型

什么是监督学习

  • 我们现在有一些训练集数据x(i),y(i)x^{(i)},y^{(i)},对于每一个输入x(i)x^{(i)}，它的输出是一个标签y(i)y^{(i)}。
  • 监督学习的任务就是运用训练集数据训练一个模型，这个模型提供一种映射关系，对于给定的输入xx，可以输出它的标签yy。
  • 比如：x(1)=thex^{(1)}=the dogdog laughslaughs, y(1)=DTy^{(1)}=DT NNNN VBVB
    本例子中输入是一个句子，它对应的输出是每个词对应的词性标签。一个监督学习的任务就是通过许许多多这样的例子训练一个模型，这个模型可以对于那些输入的没有见过的句子进行词性标注。

判定模型(Conditional(Conditional models)models)

  • 判定模型通过训练集数据训练一个p(y∣x)p(y|x)的条件分布，从而得到在输入xx的条件下，最可能的输出是哪一个。
  • 对于测试集数据，定义f(x)=argmaxyp(y∣x)f(x)=argmax_{y}p(y|x)，也就是我们说的选择在输入为xx条件下最可能的输出y。

生成模型(Generative(Generative models)models)

  • 生成模型通过训练集数据训练一个联合分布p(x,y)p(x,y)。这个联合分布p(x,y)=p(y)∗p(x∣y)p(x,y)=p(y)*p(x|y)。对于学过概率论的同学这并不难理解。
  • 对于生成模型我们同样希望能求得条件概率p(y∣x)p(y|x)，根据贝叶斯公式可知：
    p(y∣x)=p(y)p(x∣y)p(x)p(y|x)=\frac{p(y)p(x|y)}{p(x)}
    p(x)=∑yp(y)p(x∣y)p(x)=\sum _{y}p(y)p(x|y)
  • 对于测试集数据，我们用训练模型求出来它的联合分布，再应用下面的公式便可以求解在输入条件下最可能的输出。
    输出可做如下化简：
    f(x)=argmaxp(y∣x)f(x)=argmaxp(y|x) =argmaxp(y)p(x∣y)p(x)=argmax\frac{p(y)p(x|y)}{p(x)}
    因为输入中的p(x)p(x)=∑yp(y)p(x∣y)p(x)p(x)=\sum _{y}p(y)p(x|y)是一个只与xx有关的常数，所以不会改变f(x)f(x)的分布，所以最终f(x)=argmaxp(y)p(x∣y)=argmaxp(x,y)f(x)=argmaxp(y)p(x|y)=argmaxp(x,y)，这代表最终f(x)f(x)的分布与联合分布p(x,y)p(x,y)相同，这就体现出了生成模型的意义了。因为我们并不用计算条件概率，可以用模型训练出来的联合概率密度函数作为映射的结果

隐藏马尔可夫模型(Hidden(Hidden markovmarkov model)model)

定义模型

  • 定义输入：输入是一个句子我们将其看成一个由词构成的序列x=x1,x2,...,xnx=x_{1},x_{2},...,x_{n}
  • 定义输出：输出是一个由标记构成的序列y=y1,y2,...,yny=y_{1},y_{2},...,y_{n}
  • 定义模型：对于任何输入和输出长度一致的两个序列，我们假设由输入序列映射到输出序列的概率为p(x1,x2,...xn,y1,y2,...,yn)p(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n})。
  • 模型要实现的就是最大化这个概率即：
    argmaxp(x1,x2,...xn,y1,y2,...,yn)argmaxp(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n})

Trigram Hidden Markov Models

  • 对于任意输入句子x=x1,x2,...,xn，xiϵυx=x_{1},x_{2},...,x_{n}，x_{i}\epsilon \upsilon和任意输出序列y=y1,y2,...,yn，yiϵZy=y_{1},y_{2},...,y_{n}，y_{i}\epsilon\mathbb{Z}且定义yn+1=STOPy_{n+1}=STOP，定义其概率为p(x1,x2,...xn,y1,y2,...,yn+1)p(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n+1})。
  • p(x1,x2,...xn,y1,y2,...,yn+1)=∏i=1n+1q(yi∣yi−2,yi−1)∏i=1ne(xi∣yi)p(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n+1})=\prod _{i=1}^{n+1}q(y_{i}|y_{i-2},y_{i-1})\prod _{i=1}^{n}e(x_{i}|y_{i})
    定义x0=x−1=∗x_{0}=x_{-1}=*
  • 解释一下上面的公式，对于TrigramTrigram隐藏马尔可夫模型的概率函数，前一项和我们之前简述的Trigram语言模型的定义很相似，后一项每一个元素条件分布的连乘，它表示在yiy_{i}下，xix_{i}这个词出现的概率。
    哥伦比亚NLP 第二章
  • 如上图所示，输入的句子为thethe dogdog laughslaughs，输出是对应的词性。我们在表示这两个序列的联合概率分布函数如下方所示。

参数估计

  • 由于之前定义的模型需要求解类似q(yi∣yi−2,yi−1)q(y_{i}|y_{i-2},y_{i-1})这样的条件概率，所以视频刚开始的部分老师复习了一下线性差值的方法，这部分知识是第一章刚刚学过的，想要复习的小伙伴不如翻阅之前的notesnotes来学习一下吧！
  • 模型中另一个需要求解的部分就是e(xi∣yi)e(x_{i}|y_{i})，对于这部分求解的公式为：
    e(xi∣yi)=Count(xi,yi)Count(yi)e(x_{i}|y_{i})=\frac{Count(x_{i},y_{i})}{Count(y_{i})}
  • 模型的一个缺陷就是如果用上面的方法求解e(xi∣yi)e(x_{i}|y_{i})，对于那些没有在训练集中出现过的情况Count(xi,yi)=0Count(x_{i},y_{i})=0，即使这样的情况在实际中是可能存在的，由于这样的组合在训练集中没有出现，模型作用于测试集时，这种情况的概率将变为0，这代表模型将直接判定这种情况不存在，这样降低了模型的泛化能力。
    哥伦比亚NLP 第二章
  • 上图所示的例子很好的解释了我们定义模型的这个缺陷，上图的句子来自测试集，我们看到画红色框的词MulallyMulally是一个生僻词，假设在所有训练集数据中均未出现过这个词，那么对于所有TaggingTagging e(Malally∣y)=0e(Malally|y)=0。因为根据定义联合概率函数一定会包含e(Malally∣y)e(Malally|y)这一项，所以p(x1,x2,...xn,y1,y2,...,yn+1)=0p(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n+1})=0，这样模型将无法给出一组相应的输出词性标注，模型崩溃。为解决上述问题我们用下面的办法。
  1. 首先划分这个词是一个常用词还是低频词汇，对于那些在训练集中出现次数大于等于5次的单词我们界定为常用词汇，对于那些出现次数小于5次的界定为低频词汇
  2. 对于低频词汇我们根据他们的一些特征，比如：前缀、后缀、首字母大小写等特征将其”抱团“，划分成不同类别，如下图所示：
    哥伦比亚NLP 第二章
    上图描述了根据不同特征将不同类型的低频词汇分成几类。
  3. 最后，我们用不同类别代替那些低频词作为e(xi∣yi)e(x_{i}|y_{i})中的xix_{i}统计条件概率。也就是我们将低频词运用上图的表格做了一种映射，把映射的结果作为xix_{i}运用于模型中，从而解决了低频词的问题。

隐藏马尔可夫的维特比算法(Viterbi algorithm)

隐藏马尔可夫模型要解决的问题

  • 我们在之前的学习中学习了隐藏马尔可夫模型的联合概率密度函数，我们的输入是一个单词序列x=x1,x2,...,xnx=x_{1},x_{2},...,x_{n}，输出是标记序列y=y1,y2,...,yny=y_{1},y_{2},...,y_{n}，我们要做的就是求解在输入条件下，最可能的输出是什么，所以其实我们要求的就是最大化联合概率密度函数：
    argmaxp(x1,x2,...xn,y1,y2,...,yn+1)argmaxp(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n+1})
  • 根据之前的定义：
    p(x1,x2,...xn,y1,y2,...,yn+1)=∏i=1n+1q(yi∣yi−2,yi−1)∏i=1ne(xi∣yi)p(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n+1})=\prod _{i=1}^{n+1}q(y_{i}|y_{i-2},y_{i-1})\prod _{i=1}^{n}e(x_{i}|y_{i})
    我们假设yiϵS，y_{i}\epsilon S，对于求解上面概率密度的最大值，最朴素的想法就是遍历所有可能，所以在求解∏i=1ne(xi∣yi)\prod _{i=1}^{n}e(x_{i}|y_{i})的时候一共需要遍历∣S∣n+1|S|^{n+1}种情况，对于一个序列长度未知的输入，这个长度可能很长，试验次数是指数级的增长，这样的增长导致这种方法在实际运用中是不可能实现的。为了解决这一问题我们要引入一种叫做维特比算法的方法。

维特比算法

  • 维特比算法实际是一种动态规划的思想，维特比算法定义了一些符号如下：
    定义nn是句子的长度；
    定义Sk,(k=−1...n)S_{k},(k= -1...n)是从第一个词到第kk个词出现的所有标记的集合,规定S−1=S0=∗S_{-1}=S_{0}={*}；
    定义：r(y−1,y0,y1,...,yk)=∏i=1kq(yi∣yi−2,yi−1)∏i=1ke(xi∣yi)r(y_{-1},y_{0},y_{1},...,y_{k})=\prod _{i=1}^{k}q(y_{i}|y_{i-2},y_{i-1})\prod _{i=1}^{k}e(x_{i}|y_{i})
    定义：π(k,u,v)=max(y−1,y0,y1,...yk−2,yk−1=u,yk=v)r(y−1,y0,y1,...,yk)\pi (k,u,v)=max_{(y_{-1},y_{0},y_{1},...y_{k-2},y_{k-1}=u,y_{k}=v)}r(y_{-1},y_{0},y_{1},...,y_{k})
  • 解释上面的定义，根据动态规划的基本思想，先解决部分问题，然后解决更大规模的问题，在这个问题种我们需要解决的最终问题是maxp(x1,x2,...xn,y1,y2,...,yn+1)maxp(x_{1},x_{2},...x_{n},y_{1},y_{2},...,y_{n+1}),一次性求解（1−n）（1-n）的问题太难，那么不妨先求解从11到kk的最大值，于是我们先求解π(k,u,v)\pi (k,u,v)。求解π(k,u,v)\pi (k,u,v)的好处就是我们在11到kk涉及到的标记个数不再是总体的∣S∣|S|，而是部分值∣Sk∣|S_{k}|，减小了底数，从而大大减小了遍历的次数。
  • 维特比算法的状态转移方程：
    定义状态转移的开始π(0,∗,∗)=1\pi(0,*,*)=1
    定义状态转移方程:π(k,u,v)=maxωϵSk−2(π(k−1,w,u)∗q(v∣w,u)∗e(xk∣v))\pi(k,u,v)=max_{\omega \epsilon S_{k-2}}(\pi(k-1,w,u)*q(v|w,u)*e(x_{k}|v))
    解释一下状态转移方程，在计算11到kk的最大值的时候，我们假设局部最优11到k−1k-1已经计算出来了，我们假设ω\omega是第k−2k-2个元素，uu是第k−1k-1个元素，vv是第kk个元素，于是便得到了上面的状态转移方程。
    哥伦比亚NLP 第二章
    在上图所示的例子中标记的集合S=D,N,V,PS={D,N,V,P}，我们要求π(7,P,D)\pi(7,P,D)，根据上述状态转移方程可知：π(7,P,D)=maxωϵsπ(6,ω,P)∗q(D∣ω,P)∗e(the∣D)\pi(7,P,D)=max_{\omega\epsilon s}\pi(6,\omega,P)*q(D|\omega,P)*e(the|D)。在这个状态转移方程中ω\omega根据集合SS有四种取值，分别计算四个值，π(7,P,D)\pi(7,P,D)就是其中最大的那个的值。这个方法成立的前提是，在计算后面的π\pi值时，前面的π\pi值已经是被计算出来的。我们只需要定义递归的起点，就可以依次求出来所有长度下的π\pi值。其中最终求出来的，长度为nn的对应的π\pi值就是pp的最大值。
  • 维特比算法的backpointersbackpointers：
    定义bp(k,u,v)=argmaxωϵSk−2(π(k−1,ω,u)∗q(v∣ω,u)∗e(xk∣v))bp(k,u,v)=argmax_{\omega \epsilon S_{k-2}}(\pi(k-1,\omega,u)*q(v|\omega,u)*e(x_{k}|v))
    对于序列的最后两个输出(yn−1,yn)=argmax(u,v)(π(n,u,v)∗q(STOP∣u,v))(y_{n-1},y_{n})=argmax_{(u,v)}(\pi(n,u,v)*q(STOP|u,v))
    对于序列的前k−2k-2个输出，yk=bp(k+2,yk+1,yk+2)y_{k}=bp(k+2,y_{k+1},y_{k+2})
    根据上面的方法得出序列y=(y1,y2,....,yn)y=(y_{1},y_{2},....,y_{n})

总结

  • 隐藏马尔可夫模型的优点之一是它训练起来十分容易
  • 优点之二是在测试集上的表现十分良好，特别是在命名实体识别这个问题上，准确率能高达90%
  • 缺点就是需要处理低频词汇，我们之前也介绍了一些处理低频词汇的方法，比如给低频词分类。但是这种分类随着训练集单词复杂性的提高而变得越发的困难，这就是隐藏马尔可夫模型的缺点

相关推荐