课程主页：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少得多的数据，这样可以大大减少运行时间。

本讲测验题

Coursera部分

1.

看前缀即可，(b)(d)

2.

只要dog,walk部分概率为1即可，(a)(d)

3.

注意

所以

所以