chapter6-朴素贝叶斯和情感分类

• Naive bayes 模型 p(x|y)

• 训练：求根据极大似然估计（频率代替概率） p(y|x),p(x)，无参估计

• 优化：各种预处理和特征提取

• 验证模型： Precision, Recall, F-measure

• 对于多分类的处理

• 交叉验证

• 比较分类器：统计显著性测试

前言：

文本分类(text categorization) 的应用：

• 情感分析（sentiment analysis）:the extraction of sentiment

• 垃圾邮件检测（spam detection）

• 作者归属（author attribution）

• 主题分类（subject category classification）

除了文本分类外，分类在NLPL领域还有很多其他应用：

• 句号消歧（period disambiguation）

• 单词标记（word tokenization）

• part-of-speech tagger

• 命名实体标注 named-entity tagging

本章节深入介绍 multinomial naive Bayes, 下一章将 nultinomial logistic regression, 又叫 maximum entropy.

同时，简单介绍了一下生成算法和判别算法的区别：可参考前面的机器学习-生成模型到高斯判别分析再到GMM和EM算法

进一步的理解下：

• 判别算法： $p(y|x;\theta)$ 根据交叉熵 $H(\hat y, y)$ 等损失函数，使用梯度下降等来优化参数 $theta$.

• 生成算法:p(x|y)， 可以分为两种，有标签的和无标签的

• 有标签的是监督学习，以高斯判别分析GDA和本章节中的Naive Bayes为例，就是根据 $p(y|x) = \dfrac{p(x|y)p(y)}{p(x)}$,在有标签的情况下，可以根据MLE（用相对频度代替概率）来计算出 likelihood $p(x|y)$ 和先验概率prior $p(y)$,然后带入预测样本数据，得到对于每一个分类p(x|y=0,1,…)的概率，然后 $argmax_yp(x|y)$ 就是预测数据的类别。

• 无标签的是无监督学习，高斯混合模型GMM为例，需要引入隐藏变量z，计算 $p(x,z)=p(x|z)p(z)$,假设p(x|z)是多维高斯分布，然后使用EM算法对高斯分布的参数，以及先验概率p(z)进行估计~ 但因为类标签是不存在的，所以只能对样本数据进行聚类，而无法给对预测数据进行分类。

Naive Bayes Classifiers 朴素贝叶斯分类器

样本数据： $(d_1,c_1),…,(d_N,c_N),\quad c\in C$

贝叶斯分类器是一个概率分类器：

$$\hat c = argmax_{c\in C}P(c|d)$$

Bayesian Inference:

$$p(x|y) = \dfrac{p(y|x)p(x)}{p(y)}$$

则有：

$$\hat c = argmax_{c\in C}P(c|d)=argmax_{c\in C}\dfrac{P(d|c)P(c)}{P(d)}$$

可以直接去掉P(d),因为我们要计算对于每一类 $c\in C$的概率 $\dfrac{P(d|c)P(c)}{P(d)}$, 而P(d)对于任何类别都是不变的。而我们要求的是最后可能的class，其对应的P(d)都一样，所以可以直接去掉。

$$\hat c = argmax_{c\in C}P(c|d)=argmax_{c\in C}P(d|c)P(c)$$

其中P(d|c)是样本数据的 似然概率likelihood, P(c)是 先验概率prior,可以写成特征的形式：

$$\hat c = argmax_{c\in C}P(f_1,f_2,…,f_n|c)p(c)$$

显然 $P(f_1,f_2,…,f_n|d)$ 是很难计算的，以语言模型为例，你不可能考虑所有可能的词的组合，因此朴素贝叶斯分类器做了两个假设以简化模型：

1. bag of words assumption：不考虑词的顺序，也就是说 love 这个词不管出现在 1st,20th等，它对这个sequence所属类别的影响是一样的。

2. naive bayes assumption:所有特征之间相互独立

$$P(f_1,f_2,…,f_n|c)=P(f_1|c)cdot P(f_2|c)\cdots P(f_n|c)$$

因此有：

$$c_{NB}=argmax_{c\in C}P(c)\prod_{f\in F}P(f|c)$$

将朴素贝叶斯分类器应用于文本分类，我们需要考虑词的位置，这里其实也没有考虑词的顺序嘛。。

$$positions \leftarrow all\ word\ position\ in\ test\ document$$

$$c_{NB}=argmax_{c\in C}P(c)\prod_{i\in position}P(w_i|c)$$

为避免数值下溢，在对数域进行计算：

$$c_{NB}=argmax_{c\in C}logP(c)+\sum_{i\in position}logP(w_i|c)$$

Training the Naive Bayes Classifier

分别计算概率P(c), $P(f_i|c)$

$$\hat P(c)=\dfrac{N_c}{N_{doc}}$$

这里 $N_c$ 表示c类中所有词的总数，$N_{doc}$ 表示所有词的总数。

$$\hat P(w_i|c)=\dfrac{count(w_i,c)}{\sum_{w\in V}count(w,c)}$$

分母表示c类中所有词的总数。词典V表示所有类别的词的总数，不仅仅是c类别的。

有个问题: 如果词“fantastic”，从未出现在 positive类别中，那么：

这是不合理的，所以采用 add-one smoothing:

这里要想清楚为啥是V，而不是c类中词的个数？要保证 $\sum_iP(w_i|c)=1$

参考习题：

对于 unknown words: 直接删除。。

对于 stop words: 也就是 the, a,..,这样高频词，可以删掉。也可以不管，效果差不多～

算法流程

总结下：

for each class in C:

  计算 logprior[c]

  for each word in V:

    计算 word在当前class下的likelihood loglikelihood[word,c]



for each class in C:

  sum[c] = logprior[c]

  for each position in testdoc:

    if word in V:

      sum[c] += loglikehood[word,c]

  return argmax(sum[c])

Optimizing for Sentiment Analysis

binary multinominal naive Bayes or binary NB.

将每一个sequence或是documents中的重复词的数量变为1. 比如 great 出现在两个documents中，最后一个有2个great，那么positive中great总数为2，有点类似于归一化。任何一个词的数量不会超过document的数量。

deal with negation

遇到logical negation(n’t, not, no, never)后，前置前缀 NOT_ 给每一个单词，直到遇到标点符号。

sentiment lexicons

如果没有足够多的已经标注好的数据，可以使用预注释好的情感词。四个非常流行的词库：

General Inquirer (Stone et al., 1966), LIWC (Pennebaker et al., 2007), the opinion lexicon of Hu and Liu (2004) and the MPQA Subjectivity Lexicon (Wilson et al., 2005).

以 MPQA 为例，6885 words, 2718 positive and 4912 negative

话说怎么使用。。

Evaluation: Precision, Recall, F-measure

对于数据不均衡是，使用accuracy是不准确了。

举个栗子：

a million tweet: 999,900条不是关于pie的，只有100条是关于pie的

对于一个stupid分类器，他认为所有的tweet都是跟pie无关的，那么它的准确率是99.99%！但这个分类器显然不是我们想要的，因而accuracy不是一个好的metric，当它目标是rare，或是complete unbalanced.

引入另外两个指标：

• 精度 precision: 是分类系统预测出来的positive的中真实positive的比例

• 召回 call： 是真实positive中分类系统也预测为positive的比例。

上面的例子中，目的是要找到tweet中和pie相关的一类，那么其召回率就是 0/10 = 0， 其precision是 0/0

Ｆ-measure

$$F_{\beta}=\dfrac{(\beta^2+1)PR}{\beta^2P+R}$$

当 $\beta>1$时，Recall的比重更大;当 $\beta<1$时，precision的比重更大。使用最多的是 $\beta=1$,也就是 $F_{\beta=1}, F_1$. $\beta$ 的的取值取决于实际应用。

$$F_1 = \dfrac{2PR}{P+R}$$

Ｆ-measure 是 precision 和 recall 的 **加权调和平均值(weighted harmonic mean)**。

调和平均值是倒数的算术平均值的倒数。

为什么要使用调和平均值呢？因为它是一个更 保守的度量(conservative metric). 相比直接计算 P 和 R 的平均值， F-measure的值更看重两者中的较小值。

More than two classes

多分类有两种情况：

• 一种是一个document对应多标签，**（any-of or multi-label

classification）** ：解决方法是对每一个类别使用二分类，比如对于类别c，可分类 positive labeled c 和 negative not labeled c.

• 另外一种是一个document只对应一个标签，但总的类别数大于2. (one-of or multinomial classification)

confusion metrix:

将三个分类分开来看，pooled表示汇总

Test sets and Cross-validation　测试和交叉验证

10折交叉验证：

Statistical Significance Testing 统计显著性测试

比较两个分类器A和B的好坏。

假设检验

对于两个分类器 classifier A and B. 我们需要知道A的性能一定比B好吗？还是只是在特定的数据集上表现比B好？

null hypothesis: A is not really better than B，A 和 B在指标F-measure的差距是 $\delta(x)$

随机变量X是测试集的集合。

接受域： $H_0: P(\delta (X)> \delta (x)|H_0)$

当p-value(X)<0.05 or 0.01,时我们拒绝假设 $H_0$

bootstrap test

在NLP中通常不使用传统的统计方法，因为metrics并不是正态分布(normal distribution),违反了测试的假设。

对于Bootstrap知乎上有个比较清楚的答案：https://zhuanlan.zhihu.com/p/24851814

本质上，Bootstrap方法，是将一次的估计过程，重复上千次上万次，从而便得到了得到上千个甚至上万个的估计值，于是利用这不止一个的估计值，我们就可以估计待估计值的均值以外的其他统计量：比如标准差、中位数等。

应用在这里是因为但样本数据较少时，一次样本估计无法准确的计算出两个分类器A和B的差值，因而采用bootstrap.

参考：

• Speech and Language Processing ,3rd, Chapter 6

• 知乎：https://zhuanlan.zhihu.com/p/24851814