6.4.1
线性分类与感知机模型

为阐述方便,我们把问题简化成两类。假设整个数据库共有10,000个模型,但只有两种类型的3D模型:人体的模型和猩猩的模型。在检索之前,我们先上传一个已有的模型(人体或猩猩),接下来算法的目标是:要对此模型进行分析,判断它到底是人体还是猩猩。如果是人体,则将数据库中所有的人体模型列出来;反之,则把所有的猩猩模型列出来。于是,问题的关键在于:视觉算法如何智能地判别我们上传的那个3D模型到底是人体还是猩猩呢?

为了让视觉算法解答这个问题,第一步需要提取出形状的特征。我们这里讨论最直观的几何测量特征,比如,我们对数据库中所有模型都测量它们的身高、手臂长度、头围、两眼之间的距离、大腿长度、嘴巴突起的高度、门牙长度等50个特征。

考虑到数据库中有K=10,000个模型,50个特征将形成很高维的数据量,即所谓的“维数灾难”(又名维度之咒,Curse of Dimensionality。因此我们需要降维。最常用的方法是使用主成分分析PCA,将不重要的或冗余的特征删除。为直观起见,我们假设重新生成的特征中只选择了最重要的两个:“手臂长度与身高的比例”θ、“嘴巴突起的高度与头围的比例”δ

提示:采用主成分分析(PCA)降维后,得到的新特征未必有直观的几何解释,往往都是抽象的、不具备直观意义的。本例采用直观特征主要是为了解说方便。

维数灾难有两个角度的解释。当样本数量很大时,高维会导致数据量很大,占用大量的计算机内存和CPU处理时间。当样本数量较少时,高维又会使得可用数据在空间中变得很稀疏,从很多角度看都不相似,导致分类器的预测能力降低,参数得不到正确的估计。

这样,数据库中的10,000个模型,每个模型都有两个特征。如果把每个模型都远看作一个点(也即一个二维的特征向量),投影到二维屏幕上,每个点的坐标对应那两个特征值(θδ),我们就得到了类似图6-28的一张图。其中,人体模型用红色的“+”号表示,代表正样本;猩猩模型用绿色的“-”号表示,代表负样本。

6-28  模型库中所有模型在二维平面的投影

我们在数据集中间画一条直线(图中蓝色的线),如果能够直接将这10,000个点划分成两类,那么这个数据集也被称为线性可分的(Linearly Separable。如果把这条直线看作一个垂直于纸张的平面H,则其被称为分离超平面(Separating Hyperplane简称超平面

下面我们回到我们最开始的问题。用户提供一个3D模型,经过特征提取和降维后,在二维坐标上投影为一个二维点(是个包含两个坐标值的向量)。下面要判断点位于超平面的哪一边,以此来确定到底是人体模型还是猩猩模型。

我们将上面的文本抽象为数学语言。具体来说,我们可以抽象为如下的函数,这个函数有一个很酷的名字:感知机(Perceptron,是神经网络(Neural Network支持向量机的基础。从上面的描述可以知道,感知机是一个线性分类器(Linear Classifier)。

                                            7

提示:是不是觉得数学符号看得很头疼?其实,抽象的数学所描绘的事物本质往往都是非常简单的,只不过符号化之后让人觉得不太直观和习惯而已。

 

其中,就是超平面H的数学表达。是垂直于超平面的法线向量,是超平面的截距。超平面将特征空间划分为两类,在本例中,法向量指向的一侧为负类,另一侧为正类。

符号函数,只有两个返回值(+1-1),在本例中分别代表是人体模型还是猩猩模型。

有了感知机,我们就可以很方便地判别一个模型属于哪一个类别了。只需把一个新坐标值代入公式(7)中进行计算,如果位于超平面的左边,,则结果应为+1,则知道这个模型是人体;如果位于超平面的右边,,则结果应为-1,则知道这个模型为猩猩。OK,是不是特别简单?!

扩展:Novikoff收敛定理. 如果训练样本集是线性可分的,那么感知机算法可在有限次迭代后收敛。令为输入样本特征向量的最大长度,超平面关于训练样本集的几何间隔距离为,则感知机算法在训练样本集上的误分类次数不超过,也即最多做次更新就会收敛。

证明:感知机算法仅在样本点分类错误时进行更新,令是第次误分类时所更新的(法向量)权值,算法从开始。假设第次误分类发生在样本上,类别标签,并将截距归一化为0,则有:

                                                 8

下面给出感知机的更新规则:当学习率时,我们有。将两边都乘以单位长度法向量):

因为初始,将上式递推可得:

                                               9

根据上面的公式(8)以及,可得到:

同样,经递推可得到:

两边开根号,并根据公式(9),可得:

因此,,证毕。 

 

通过上面这个定理可知,误分类的数目不会超过样本特征向量的最大长度与几何间隔的比值的平方。也即,当训练数据集线性可分时,感知机算法必然收敛(当不可分时,算法不能保证收敛,迭代结果会发生振荡)。此外,权值的整个更新过程实际上就是与新输入样本的线性组合,因此这是个在线学习(Online Learning的过程,即根据新来的样例,边学习边给出结果。