edfward

爆肝 Naive Bayes Classifier

今天终于解决了困扰我多时的 Naive Bayes Classifier 的问题,于是在晚上爆肝写篇文章纪念一下。

内容大致有以下部分:

  1. 关于不同类型 NB 的介绍
    • Multivariate Bernoulli NB
    • Multinomial NB with TF / Boolean attributes
  2. NLTK 里 NB Classifier 的实现

1.关于 Naive Bayes Classifier

关于两种 NB 的介绍都用 text classification 做为背景吧。

Multivariate Bernoulli NB (简称 BNB) 需要一个字典 D(不一定是所有的词汇,可能进行过降维),之后将每篇文档看做 D 维的二值向量,词典里的词出现了记为1否则为0。两个重要的 formula 如下,


docs(word,class) 指的是该类的文档中包含该 word 的文档数,docs(class) 指的是该类一共包含的文档数。
- 某一类别出现该特征向量的概率:


要考虑到词典里每一个词的情况,运算量相对较大。

Multinomial NB (简称MNB) 不需要词典,每个文档看做从词汇里独立抽取 d 个 token(可重复)的结果。对应的 formula 如下(如果用 term frequency 作为 attribute),

count(word, class) 在该类中 word 出现的总次数(1篇文档可出现多次该词),count(class) 指该类文档的总词数(包括重复),V 表示所有文档的词汇数量(无重复,因为是词汇)。

如果 MNB 使用 boolean attributes 的话就与 BNB 很像(但计算基本同 MNB with TF),区别在于

MNB 的算法可以这么表示:

MNB_algo

接下来用一个 working example 来解释一下这三者的区别。

  docID words in document class
training set 1 Chinese Beijing Chinese c
  2 Chinese Chinese Shanghai c
  3 Chinese Macao c
  4 Tokyo Japan Chinese j
test set 5 Chinese Chinese Chinese Tokyo Japan ?

BNB :
D = {Chinese, Beijing, Shanghai, Macao, Tokyo, Japan}

P(c) = 3/4, P(j) = 1/4  
P(Chinese|c) = (3+1)/(3+2) = 4/5  
P(Tokyo|c) = (0+1)/(3+2) = 1/5  
P(Japan|c) = (0+1)/(3+2) = 1/5 
P(Chinese|j) = (1+1)/(1+2) = 2/3  
P(Tokyo|j) = (1+1)/(1+2) = 2/3  
P(Japan|j) = (1+1)/(1+2) = 2/3    

therefore, according to the dictionary

P(c|d5) = 3/4 * {4/5 * (1-2/5) * (1-2/5) * (1-2/5) * 1/5 * 1/5} = 0.024
P(j|d5) = 1/4 * {2/3 * (1-1/3) * (1-1/3) * (1-1/3) * 2/3 * 2/3} = 0.074

MNB with TF attributes :

P(c) = 3/4, P(j) = 1/4  
P(Chinese|c) = (5+1)/(8+6) = 3/7  
P(Tokyo|c) = (0+1)/(8+6) = 1/14  
P(Japan|c) = (0+1)/(8+6) = 1/14  
P(Chinese|j) = (1+1)/(3+6) = 2/9  
P(Tokyo|j) = (1+1)/(3+6) = 2/9  
P(Japan|j) = (1+1)/(3+6) = 2/9   

therefore,

P(c|d5) ~ 3/4 * (3/7)^3 * 1/14 * 1/14 = 0.0003  
P(j|d5) ~ 1/4 * (2/9)^3 * 2/9 * 2/9 = 0.0001

MNB with binary attributes :

P(c) = 3/4, P(j) = 1/4  
P(Chinese|c) = (3+1)/(4+6) = 2/5  
P(Tokyo|c) = (0+1)/(4+6) = 1/10 
P(Japan|c) = (0+1)/(4+6) = 1/10  
P(Chinese|j) = (1+1)/(3+6) = 2/9  
P(Tokyo|j) = (1+1)/(3+6) = 2/9  
P(Japan|j) = (1+1)/(3+6) = 2/9   

therefore,

P(c|d5) ~ 3/4 * 2/5 * 1/10 * 1/10 = 0.003  
P(j|d5) ~ 1/4 * 2/9 * 2/9 * 2/9 = 0.0027

2.NLTK 中 NB Classifier 的实现

前一阵子在 python 上用一个自然语言处理的库 NLTK 用得比较多,相比起之前自己手写的 NB 来说代码的可读性好了很多,但始终有些让人不能理解的问题。一般的使用可以看这个 gist,130行左右。似乎可以看出这是个典型的 BNB, 42行build_features函数返回一个包含所有词汇的字典, 55行extract_features函数从一个文档里提取所有的 contains(%word) 这样的 boolean attribute,接着调用 NLTK 的 NB classifier 进行训练。但是之前发现一个很奇怪的现象,如果63-64行

for word in self.word_features:
    features['contains(%s)' % word] = (word in document_words)

改为

for word in document_words:
    features['contains(%s)' % word] = True

最后的分类效果会提升许多。现在我们可以知道后者其实就是 MNB with boolean attributes 的写法,但是我们并不清楚 NLTK 提供的 NB classifer 究竟支不支持 MNB (因为涉及到计算方法的改变)。接下来就要去看看 NLTK 的源码了。

NaiveBayesClassifier.train 函数中,关键部分代码如下

for featureset, label in labeled_featuresets:
    label_freqdist.inc(label)
    for fname, fval in featureset.items():
        # Increment freq(fval|label, fname)
        feature_freqdist[label, fname].inc(fval)
# ...... other parts
for ((label, fname), freqdist) in feature_freqdist.items():
    probdist = estimator(freqdist, bins=len(feature_values[fname]))
    feature_probdist[label,fname] = probdist

featureset 是一个特征词典,形如 {‘contains(big)’:True …}。 feature_freqdist 以 label 和 fname 为 key, 对应的 value 是 NLTK 对 dict 类型的一个封装,用来统计内容出现的频数,inc(fval)即是增加对应 fval 的频数。

用之前的 working example in BNB 举例,d1 对应的 featureset 和 label 为{‘contains(Chinese)’:True … }, ‘c’,而训练完 training set 后

feature_freqdist['c', "contains(Beijing)"] = {True: 1, False: 2}

这样就表示了 P(fname=fval|label)。代码的后半部分就对这个封装好后的频数字典进行 smoothing,代码里的 estimator 用的是 ELEProbDist,相当于的 alpha=0.5 的 additive smoothing,按上面的例子来说就是把 True 和 False 的概率平滑了一下。

再看 NaiveBayesClassifier.prob_classify 函数, 关键部分是

# Then add in the log probability of features given labels.
for label in self._labels:
    for (fname, fval) in featureset.items():
        if (label, fname) in self._feature_probdist:
            feature_probs = self._feature_probdist[label,fname]
            logprob[label] += feature_probs.logprob(fval)

倒数第二行拿到 smoothing 后对应 label 和 fname 的频数/概率字典后直接取 fval 的 log probability,加到结果中去。这个过程与词的总数没有关系,相反,如果给的 featureset 每次都包含 negative feature,那这个得到的 logprob 就相当于 docs(c,fname=fval) / docs(c) 经过平滑再取对数的结果。

这样看来很明确了,NLTK 的这个实现完全就是基于 BNB的,所以要求在给出 featureset 时需要一个字典以及里面所有 fname 对应的 fval (通常是 true or false),但是不支持 MNB。这可真是太让人伤心了,于是只好回去用以前手工实现的虽然丑陋但好歹能用的 NB classifier。

Reference

  1. Metsis, Vangelis, Ion Androutsopoulos, and Georgios Paliouras. “Spam filtering with Naive Bayes—which Naive Bayes?” Third conference on email and anti-spam (CEAS). Vol. 17. 2006.
  2. NLTK 2.0 documentation
  3. lecture slides from Coursera NLP course by Dan Jurafsky and Christopher Manning
  4. Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to information retrieval (Vol. 1). Cambridge: Cambridge University Press.

PS

第一次贴较复杂的数学公式,本来想在服务器上加一个渲染公式的脚本,想了想担心这样对移动平台的支持会减弱,结果还是用的 svg。推荐一个在线的 latex 矢量图生成网站, 能够把公式转变成图片而且通过本身的 api 直接嵌入到网站中,好评。