« 贝叶斯分类器----分类器思想的起源Bag of Word闲谈 »

非等级式随机森林----随机蕨分类器

 这几天一直在捣鼓着非等级式的随机森林,在论文[1]中,作者利用各种手段,使得非等级式的随机森林呈现出来,至于是否十行C++代码就可以实现,这还有待考证,毕竟至少我的代码不只十行。

     OK~ 细细来品味[1]中的思想,可谓简单而实用。

     贝叶斯分类器的整体思想来说,都是从前验概率后验概率的转换过程,在整个现实的世界中,某一个物体,或者是非物体的特征维度,我们很希望把它限定在一维的情况,这样仅仅利用几次贝叶斯转换的公式即可。但是并不能这样来做,因为特征的维度还取决于物体之间特征的相似性,如果物体之间的特征非常的相似,那只能再提取别的特征,又或者最终造成识别错误的情况。所以整体来说,利用贝叶斯理论去设计分类器的情况,必须要考虑多特征的融合情况。这里对于多特征的融合情况便衍生出了多种贝叶斯分类器,其中以朴素贝叶斯分类器为主,也诞生了一系列修改的类朴素类型。Anyway, 思考下朴素贝叶斯分类器。

     朴素贝叶斯分类器:
     下式是贝叶斯乃至整个分类领域中最终的目标,即利用已知的特征,去判断分类的结果,可以是二分类,同样也可以是多分类的情。
非等级式随机森林----随机蕨分类器
     OK,知道了上面这样的式子,这里会出现一个很大的疑问,我的特征都是当前的特征,那这样的情况可是不可能求出最大类别的嘛?既然被称为贝叶斯分类器,当然就要利用贝叶斯理论来将这样的一个后验概率做适当的转换,变成先验概率的情况。参照[2]情况,上式变为:
非等级式随机森林----随机蕨分类器
 
     式子右边 p(C=c) 部分是先验的类概率,即一共有多少类,每一类出现的概率为多少,最简单的办法就是所有类别都以同等概率出现。而式子右边p(Fi = fi | C = c)的累乘部分也就是整个朴素贝叶斯分类器的最核心的假设部分。
     朴素贝叶斯分类器假设:特征之间相互独立,即第一个特征对于类的贡献值并不会受到其他所有特征的影响,也就是每一个特征对于类的贡献都可以看作是1。
     虽然朴素贝叶斯分类中对于所有的特征都假设了其相互的独立性,不过在这种极端的思想下所构造的分类器效果显著,而在某些环境下,这样的"极端分类"思想使得该分类器的效果最好。

     Anyway,上面的朴素贝叶斯分类器包括其推到具体过程可参考[2],接下来说说我对随机森林的一点点小小的理解。这一部分应该会考虑重新写一篇关于随机森林的文章出来,所以一言带过其中一个最重要的思想------boostrap思想。即利用重采样思想去做原始样本的估计,具体参考[3]。
     喷了一大堆背景,接下来才算是本文的重点部分,一种非等级式的随机森林的建立。
     Step:
     1:半朴素贝叶斯分类器。
     2:局部特征提取。
     3:随机分配----构建非等级式的随机森林。
     4:识别判断。

     半朴素贝叶斯分类器:
     虽然纯朴素贝叶斯分类器,简单,实用,利于编程实现,但真实的世界,各个特征之间不可能会有绝对的相互独立的极端情况,例如鱼的形状以及眼睛的位置,这两部分本身就存在的一定的联系,如果将其分开,势必会对最后的结果有一定的影响。在这样的情况下,我们是否需要考虑所有的特征之间可能的一种联系呢?当然也是是没有这个绝对的必要,原因有2:
     (1) 真实的情况虽然特征众多,但也会有特征之间相互独立的情况出现,例如一个人的身高和这个人的眼睛的颜色,将这种没有太多联系(至少现在看来)的特征结合也不一定会对分类效果有效。
     (2) 如果要考虑这种所有特征之间相互之间都有联系的情况,分类器的复杂度会非常的高,考虑N个特征之间的内在的联系,那可能会出现2的N次方种可能性,所以没有这个绝对的必要。
     半朴素贝叶斯分类器排除这两种极端的情况,将特征分组进行对待,认为组类特征不独立,组间特征相互独立。论文[1]中利用这样的思想,建立了非等级式的随机森林算法。

     局部特征提取:
     论文[1]的目的是为了利用随机森林以及半朴素贝叶斯分类器思做特征点的匹配工作,那肯定会牵涉到特征点的特征问题。在[1]中提出了一种pixel comparison的思想,即利用特征点周围像素之间的相互比较,将特征点的特征编译成一个二进制数形式的编码,匹配的过程同样照做。可以这么想,如果点的周围环境变化不大,对于点的特征的描述都是很有效的。但如果点的周围环境变化大了,这种描述将失效。所以需要随机森林的思想来弥补这样的缺陷。

     随机分配------构建非等级式的随机森林:
     这也是论文[1]的重点部分,前面提到过,特征点的特征会随着点周围环境变化越来越大而失效,那怎样做一个很好的弥补呢?即利用重采样的思想,将这些特征的pixel comparison的比较随机分配到一些叶子里面去,从多个views的角度去观察这个点,这样可以很有效的弥补环境变化带来的损失。
     例如:一个特征点原始的情况是左边像素大于右边像素,如果此时通过观察到右边的像素大于左边而判断这个点与训练的情况不一致而抛弃的话,那是不明确的。因为这个点连带周围的环境有可能做了一个旋转。但是如果利用不同的views的情况,即在训练的时候在不同的叶子下都记录了不同的可能性,那此时会有两种情况作比较,一种是左边大于右边,另外一种则是相反。显然,效果还是有所改善的。
     上面提到的多views的情况就是随机森林的基本思想的体现,文[1]中对于一个点的局部特征,将pixel comparison的顺序做出随机分配,随后在对随机分配后的比较顺序做出分组,形式化一下就是,对pixel comparison做出N种分配,对这N种分配利用有返回抽样思想,随机分配到M组中,之后,可以知道每一组中都会有N/M中比较,每一个组都是对该点一个局部特征的编码过程。完成之后,每一个叶子节点都会记录下来通过该点的正样本和负样本的数目,最终会有一个后验概率:n(Positive) = n(Positive) + n(Negative)。
     好了,非等级式的随机森林构建完毕。接下来就是识别判断的过程。

     识别判断:
     其实上面对于这样一种新结构以及说明的很清楚了,所以识别判断仅仅是利用相同的手段,即利用每一颗树(组)中的像素比较情况,得到编码后,决定进入哪一颗树,看看树中的后验概率的情况,最终结合所有树对于该点的判断,取一个平均值,如果大于50%则认为与训练中的某点是一致的情况。这一部分其实比较简单。

     心得:
     包括代码在内,对于文章的深入理解过程花了我一个星期,以前为了看TLD算法,粗略的了解了一下。不过深入之后才发现自己理论以及实践的不足。Coding之后慢慢了解到论文的精妙之处----可谓好的创新思想并非要建立独立的框架,一点点小的融合或者小的改动就可以创造奇迹。

参考文献:
[1] Mustafa Ozuysal、Pascal Fua and Vincent Lepetit. Fast Keypoint Recogition in Ten Lines of Code. CVPR, 2007.
[2] http://en.wikipedia.org/wiki/Naive_Bayes_classifier
[3] http://en.wikipedia.org/wiki/Bootstrap
[4] http://cvlab.epfl.ch/alumni/oezuysal/ferns.html

Coding参考:
[1] http://cvlab.epfl.ch/software/ (Ferns软件)

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。