Michael Collins NLP Lecture 12

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

课程网盘地址:

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

这一讲介绍了Brown聚类算法。

Brown聚类算法

简介

首先看下算法的输入输出:

  • 输入:大量单词的语料库。
  • 输出1:将单词划分为单词类。
  • 输出2(1的一般化):分层单词聚类。

来看下聚类结果:

第二张图的含义是给同一类的单词相似的编码,可以利用树做到这单。

Brown聚类模型

算法的直觉很简单,即相似的单词的前后单词的分布相似,根据这个思路,构建如下模型:

  • $\mathcal V是语料库w_1,w_2,…,w_n​$中的所有单词。

  • $C:\mathcal V \to \{1,2,…,k\}$是将词汇划分为$k$类的映射。

  • 对每个$v\in \mathcal V,c\in \{1…k\}​$,定义参数$e(v|c)​$。

  • 对每个$c\in \{1…k\},c’\in \{1…k\}$,定义参数$q(c’|c)$。

  • 模型如下:

    其中$C(w_0)$是一个特殊的开始符。

那么该如何评价模型的好坏呢?一个比较直接的度量是对数似然$\frac 1 n \log p(w_1,w_2,…,w_n)$,进行化简处理得到如下结果:

那么

其中$G$是一个常数。

算法

下面分别介绍两个算法,其中算法2的效果更好。

算法1
  • 从$|\mathcal V|$个聚类开始:每个单词属于一类。
  • 我们的目标是找到$k​$个最终聚类。
  • 运行$|\mathcal V|-k$步:
    • 每一步选择两个类$c_i,c_j$,然后将他们合并为一个类。
    • 我们贪婪地选择合并,使得合并步骤之后的聚类$C$的$\text{Quality}(C)$在每个步后达到最大值。

该算法的时间开销为$O(|\mathcal V|^5)$,改进后时间开销为$O(|\mathcal V |^3)$,由于单词量非常大,该算法太慢。

算法2
  • 算法的参数是$m$。
  • 对于出现频率最高的$m$个单词,将每个单词分为一类,$c_1c_2…c_m$。
  • 对$i=(m+1)…|\mathcal V|$:
    • 为出现频率第$i$高的单词创建一个新的聚类$c_{m+1}$。 我们现在有$m + 1$个聚类。
    • 从$c_1…c_{m+1}$中选择两个要合并的类:选择使$\text{Quality}(C)$最大的合并。 我们现在回到$m$个聚类。
  • 执行$(m-1)$步最后的合并,以创建完整的层次结构。

该算法的时间开销为$O(|\mathcal V|m^2 +n)$,其中$n$是语料长度。

应用

下面介绍上述方法应用于名称标记问题,思路是使用对数线性模型,特征结合聚类结果的编码:

实验结果如下:

该方法的优势在于,达到同样精度只需要相对于HMM少得多的数据,这样可以大大减少运行时间。

本文标题:Michael Collins NLP Lecture 12

文章作者:Doraemonzzz

发布时间:2019年03月03日 - 14:30:00

最后更新:2019年05月06日 - 20:21:02

原始链接:http://doraemonzzz.com/2019/03/03/Michael Collins NLP Lecture 12/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。