Topwords
##Introduction
TopWORDS1是近期在PNAS发表的一种方法，它在没有任何先验知识的条件下，快速地从大规模中文语料里学习出一个排序的词典以及语料文本的分词结构。
Note: TopWORDS的实现项目：https://github.com/qf6101/topwords
##Domain Applications
TopWORDS的应用领域包括新词发现、短文本分析等。
新词发现一直是文本挖掘领域的一个难题，目前的方法主要是分为两种：（1）依赖众包手段收集词汇，例如百度的搜索词和搜狗的拼音输入；（2）采用规则方式采集候选词汇，加以人工筛选，例如Matrix67汇总的一些规则2。上述第一种方法需要先天有优势的大产品才能做，第二种方法效果较差，并且它们都需要大量的人工干预。TopWORDS天然可以做新词发现，优点是完全无监督，有理论依据，效果较好。
短文本分析是文本挖掘领域的另一个难题，内容简短、拼写错误、缩写语多、语法随意等原因为它的分析带来很多困难。TopWORDS除了可以抽取常用短语外，还可以为短文本分类等任务提供高频特征。
##Algorithm
#####TopWORDS的问题描述如下（不考虑辅助知识）。
- 输入：一个语料集合
- 输出：一个排序的词典、输入语料的分词结构（与词典一致）
#####TopWORDS采用两步算法：
-
第0步：语料预处理。确定文本片段的粒度，可以是句子、段落、甚至整篇文档作为一个文本片段，前两种粒度适合分布式计算，论文采用后两种。将语料整理为文本片段的集合，清理掉文本片段中的标点符号。
-
第1步：生成一部超完备词典。生成方式依赖两个阈值：词长阈值$\tau_L$和词频阈值$\tau_F$。以文本片段为事务，使用Aprori策略得到长度小于等于$\tau_L$出现频率大于等于$\tau_F$的词，组成超完备词典。用标准化后的词频（范围在0~1之间）初始化每个词的使用率（word use probability），剔除掉使概率小于等于1E-8的词，得到最终的超完备词典。
-
第2步：采用EM算法从语料中估计每个词的实际使概率，下面是有关符号。
超完备词典：$D={w_1,w_2,…w_N}$
超完备词典的使用率：$\vec{\theta}={\theta_1,\theta_2,…\theta_N}$, s.t. $\sum\limits_{i=1}^N\theta_i=1$
文本片段：$T$
$T$的一种分词结构：$S=w_{i1},w_{i2},…w_{iK}$
因为$\vec{\theta}$隐含了$D$，为了简化书写，我在下文推导中省略了$D$。推导中采用了Word Dictionary Model(WDM)模型。
另外，$S$和$T$的关系如下。
其中$C_T$表示$T$所有可能的分词结构。
#####EM算法的推导
- 观测变量：$T$
- 隐藏变量：$S$
- 模型参数：$\vec{\theta}$
每次迭代都要更新词$w_k$的使用数在所有可能的分词结构分布下的期望。
#####动态规划的表示形式
观察发现，$n_k(T)$的分子部分是$w_k$在所有可能的分词结构中出现的频率。从另一个角度，文本片段所有可能的切分方式来看，可以重新表示成递归的形式。
这样一来，每次迭代更新的是词$w_k$的使用数在所有可能的切分分布下的期望。从$T$的尾巴开始就可以动态规划地计算上式。
##词典排序
论文还提出了一种衡量词使用率的排序标准，比较它出现和不出现情况下语料的概率，作为词的重要程度。该标准也可以采用动态规划的方式进行计算，在此不再赘述。
##最优分词结构
论文提出以两种策略来确定最优分词结构：（1）所有可能的分词结构中分词边界的频率大于阈值，且词典中存在对应的词；（2）如果词典中不存在对应的词，就采用MLE策略。该策略也可以采用动态规划的方式进行计算，在此不再赘述。
##References