机器学习实战3 - 朴素贝叶斯
06 Jan 2018 by LelouchHe
朴素贝叶斯(Naive Bayes)
朴素贝叶斯算法,和前面的k最近邻和决策树相比,数学味道重了很多.其数学基础,贝叶斯法则,通过巧妙结合以往经验与现实数据,来评估可能的假设分布.
贝叶斯法则
贝叶斯法则是用来计算条件概率(conditional probability)的一套方法,条件概率$P(A|B)$是指在B发生的前提之下,A发生的概率情况,其公式为:
\[P(A | B) = \frac{P(B | A)P(A)}{P(B)}\]贝叶斯其实是利用另一个条件概率$P(B|A)$来计算目标条件概率.乍看之下,貌似解决不了问题,但此处的关键在于,条件概率计算的难度不一样,通过贝叶斯法则,我们就可以利用一个较为容易获得的条件概率计算出较难获得的条件概率.这其实很符合科学研究的方法.当某一个问题比较难以处理的时候,通过证明其等价的容易的问题来解决,这个思路是一致的
回到机器学习的角度上来说,在既有数据集(D)和所有可能假设(H)的情况下,我们试图得到一个最为可能的假设(h),这可以看作是在求:
\[h \equiv argmax _ {h \in H} P(h | D)\]抽象的来说,任何学习其实都是在求解这个h.但这个值的求解是比较困难的(单机器学习就汗牛充栋了,不要提其他方法了),所以利用贝叶斯法则,我们做一下转换:
\[h \equiv argmax _ {h \in H} P(h | D) = argmax _ {h \in H} \frac{P(D | h)P(h)}{P(D)} = argmax _ {h \in H} P(D | h)P(h)\]$P(D)$对于既有数据集来说,是常量,可以忽略.
可以看到,本质而言,我们是通过$P(h)$(h本身成立的概率)和$P(D | h)$(h与D吻合的概率)来计算$P(h | D)$.用术语来说:
- $P(h)$: 假设h成立的先验概率,反映的是我们对h成立的背景知识,这个在我们试图获得真正的h之前,就已经有了.比如我们可以通过观察数据,或者干脆假设所有的假设都有同样的可能(此时$P(h) = 1 / | H |$)
- $P(D | h)$: 假设h成立的前提下,观察到D的概率,反映的是假设与数据吻合的情况.我们可以假设h是成立的,然后验证既有数据集,判断其成立的概率.
- $P(h | D)$: 在既有数据集下,假设h成立的概率.反映的是假设h在D上成立的可能.不同于先验概率,这个是经过数据验证的,称之为后验概率.能让后验概率最大化的假设,我们称之为极大后验(Maximum A Posteriori)假设,即$h _ {MAP}$
这样,我们通过2个比较容易获得的量$P(h)$与$P(D | h)$,来求比较困难的$h _ {MAP}$:
\[h _ {MAP} \equiv argmax _ {h \in H} P(D | h)P(h)\]当我们对h没有任何背景知识时,可以继续简化为:
\[h _ {ML} \equiv argmax _ {h \in H} P(D | h)\]此处的ML意为Maximum Likelihood,$h _ {ML}$也成为极大似然假设
贝叶斯法则的应用
从上面可以看到,贝叶斯法则其实是一个通用的基础规则,通过求解$h _ {MAP}$或者$h _ {ML}$,我们可以得到一个在既有数据集(D)和所有可能假设(H)的前提下,最为可能的假设(h).
这就提供了一种理解其他很多学习算法的角度.在处理其他学习算法时,一个比较隐晦或棘手的问题就是如何证明算法的正确性.当然,对于我等工程师来说,这并不是一个非常要命的问题,通常我们都会以常识的方式理解一下分析过程就结束了.但从某种数学角度上给予证明,对于研究者进行研究或者我们进一步理解,还是非常有帮助的.而贝叶斯法则提供了一种可能的框架结构,即使原学习算法是概率无关的,通常也能通过变换,来证明原算法的归纳偏置在贝叶斯法则下是可以导向$h _ {MAP}$或$h _ {ML}$的.
下面我们以ID3的决策树为例,看看如何使用贝叶斯法则.更多的其他分析,见机器学习的第六章.
ID3的决策树
对贝叶斯法则进行一系列的变换:
\[h _ {MAP} = argmax _ {h \in H} P(D | h)P(h) = argmax _ {h \in H} ( \log _ {2} P(D | h) + \log _ {2} P(h) ) = argmin _ {h \in H} ( - \log _ {2} P(D | h) - \log _ {2} P(h) )\]最后一个等式,很明显,已经和ID3使用的信息熵类似了.信息论中$- \log _ {2} A$表示的其实就是使用某种编码,得以编码$A$的最小位数.如果我们假设$L _ {C}(A)$用来表示编码C下A的最小编码长度,也即$L _ {C}(A) = - \log _ {2} (A)$的话,原公式可以表达为:
\[h _ {MAP} = argmin _ {h \in H} ( L _ {C} (D | h) + L _ {C} (h) )\]可以看到,其实要求的就是使得编码最小的假设h.在决策树算法中,编码多少是通过树的高度来体现的(编码的值是通过树的分支来体现的,参考霍夫曼树),因此也就是相当于求最矮的决策树了.这就和ID3的归纳偏置,不谋而合,从这个角度证明了ID3的正确性.这个原则,被称为最小描述长度(Minimum Description Length, MDL),亦即:
\[h _ {MDL} = argmin _ {h \in H} ( L _ {C} (D | h) + L _ {C} (h) )\]计算窍门
当应用贝叶斯法则时,有几个小的窍门,可能能让计算更简单
取对数
如同ID3的决策树的推理过程,在真正使用贝叶斯法则时,我们往往是取对数求和,而非简单的求概率的乘积.一方面乘积容易过小,导致精度问题,另一方面,求导求和一般比求积更快,所以我们通常使用的贝叶斯法则公式应该是:
\[h _ {MAP} = argmax _ {h \in H} ( \log _ {2} P(D | h) + \log _ {2} P(h) )\]扩展概率
一般求概率是直接求数据集中的频率.但在数据集过小,或者数据集本身分布不均衡时,某类型数据很有可能非常少,以至于近乎于0.这个对于连续乘积的贝叶斯法则来说,不是好事,即使我们转用求和,也会因为这个带来的无穷小,导致计算的偏颇.
所以在这个情况下,引入扩展概率,即计算m-估计:
\[P(A) = \frac {N _ A + m p} {N + m}\]其中$N _ A$表示A出现的次数,$N$表示总数,$p$表示对计算$P(A)$的一个先验估计,$m$则是先验估计的常量权重.一般的$p$会取平均概率,表示每种情况都是平均的.$m$可以表示为情况的总数(此时$mp$通常为1)
当既有数据集存在类似问题时,我们就要转而使用m-估计来计算概率,避免因数据问题导致最后的估计错误.
小结
贝叶斯法则就是一种以概率为评估方式,以背景知识与现实数据为衡量标准,来观察世界的一种方式.这种方式虽然不是理解学习算法的唯一途径,但它提供了一种非常符合人类直觉的,有很强因果关系的,而且很数学化的理解方式.条件概率本身就是因果关系的一种近似的衡量,贝叶斯法则通过操作条件概率,指导我们寻找隐藏起来的因果关系链条,并以此求解最为可能的假设.
贝叶斯法则还有非常多的值得学习的地方,大家可以参看机器学习的第六章内容.其中,最让我appalling的是贝叶斯信念网.根据提供的概率分布求信念网的过程,感觉简直就是人工智能的体现啊.对于大尺度上的因果关系,恐怕将来,连人类自己可能都没法和机器媲美了.
朴素贝叶斯分类器
由来
数据实例一般是由数据属性组成的,比如$d = (a_1, a_2, \cdots, a_n)$,因此利用贝叶斯法则,来计算某假设成立的贝叶斯估计,即为:
\[b(h) = P(d | h) P(h) = P(a_1, a_2, \cdots, a_n | h) P(h)\]其中$P(a_1, a_2, \cdots, a_n | h)$表示的是假设h成立时,数据实例各个属性为$(a_1, a_2, \cdots, a_n)$的概率.这就带来的相关的2个问题:
- 如果既有数据集没有这个完全匹配的数据实例,那么这个概率就是0
- 为了让既有数据集有这个数据实例,我们就得扩大数据集范围,即收集更多的数据
为了解决这个问题,我们就要引入其他更强的假设,这就是我们的朴素贝叶斯分类的原理
假设
朴素贝叶斯算法的一个很naive的假设是,数据属性之间是相互独立的,即某假设成立的贝叶斯估计可以变形为:
\[b(h) = P(a_1, a_2, \cdots, a_n | h) P(h) = P(h) \prod _ {i} P(a _ i | h)\]某数据属性出现的概率肯定远远高于某特定实例出现的概率,这样,我们就可以继续在既有数据集上,得到一个naive的贝叶斯估计,而不用收集更多的数据了.(大家有空的话,可以简单计算下,如果要用实例概率的话,数据量要有多大,才会保证至少有一个特定数据实例)
这样的假设究竟靠谱么?乍看之下,可能有些问题,但是对于现实生活中的大多数具体问题来说,这个粗略的假设是足够的.比如垃圾邮件分类器,就有很多是采用朴素贝叶斯进行分类的,准确率和召回都是非常高的,比某些采用更加复杂更加真实的其他学习算法,高了不知道哪里去.
总结 - 朴素贝叶斯
优点
- 计算简单,不需要全部数据,只需要数据的概率分布
- 准确性好
- 数据集要求不多
缺点
- 背后的贝叶斯法则需要深刻理解
思考
朴素贝叶斯算法是非常经典非常好用的学习算法之一.一些经典问题(比如垃圾邮件分类),朴素贝叶斯往往是最优算法里最简单的.有的时候让人很诧异,为何简单的假设就能得到如此好的结果
当然,在这个的基础上,我们还是要好好的理解贝叶斯法则,并且能把贝叶斯法则作为工具,来分析其他学习算法,或者运用于生活当中,这对于我们理解算法和世界,都有莫大的帮助和益处.