一、感知机模型
感知机是一个二分类的线性分类模型,输入为实例的特征向量,输出实例的类别,取1,-1两个值,输入判别模型。它适用于线性可分的数据集的分类,所谓线性可分,就是两类数据可以用空间中的一个超平面分离,即存在参数
,当
属于其中一类时,
,当
属于另一类时,
。对于平面情况示意图如下所示:
线性可分示意图
定理:样本集线性可分的充要条件是两类数据集张成的凸包的交集为空集
证明:
必要性:显然(只需注意到开半平面是凸集,每类点各包含在一个开半平面中,所以每类点的凸包各包含在一个开半平面中,由于两个开半平面不交,所以两类点的凸包不交)
充分性:显然(只需注意到有限个点生成的凸包是闭的且是有界的,则是紧的,由于它们不交,所以必有正距离。由超平面严格分离定理,存在超平面,将这两个凸包严格分离,即将两类点严格分离)
注:两个闭集互不相交不能推出两个闭集间有正距离,除非至少有一个是紧致的。
我们的目的是计算出该超平面的参数,即确定
,得到函数
,对于一个新样本
,即可根据
的符号进行分类。即最终需要构造的函数为:
,当
时取1,否则取-1。这样对于新样本,即可根据
的输出1,-1进行分类。为了简单起见,我们将每个实例点
增加一维,变成
,同时将
合成一个向量:
,这样,要训练模型就变成了:
,其中
是需要计算的参数。对于训练数据集来说,第一类标签
,第二类标签
,如果超平面可以将训练数据集完全分类正确,那么
定号,我们训练使得对所有
,
的超平面。即
的点是误分类点。将所有误分类点构成的集合记为
,如果没有误分类点,则:
如果存在误分类点,则
所以我们将
定义为损失函数,并将它极小化。
二、感知机原始形式算法
,我们采用梯度下降法对
进行更新。极小化过程不是一次对
中所有点进行梯度下降,而是一次随机选取一个误分类点进行。即随机选取一个误分类点,
,则参数更新:
,
称为学习率。这就是感知机的原始算法:
(1)、将每一类的
增加一维1,仍然记为
(2)、第一类所有
不变,第二类所有
反号,构成的集合仍称为训练集
(3)、在训练集任取一个
,如果
,则
(4)、转至(2),直到没有误分类点
在实际训练中,我们往往设置训练的次数来决定训练是否结束。
三、原始算法的实现
我们使用感知机算法对
数据集进行两类分类,关于该数据集的格式以及读取代码,在前面
以及朴素
分类器的推文中都有介绍,这里不再赘述。下面给出分类源代码
%调用自定义函数读取训练集中的数据
Train=loadMNISTImages('train-images.idx3-ubyte');
%增加一位特征,仍记为Train
A(1,1:60000)=1;
Train=[A;Train];
%调用自定义函数读取训练集中数据标签
Trainlabels=loadMNISTLabels('train-labels.idx1-ubyte');
%根据标签对训练集中的数据分类,分别记为M{1,1},M{1,2}...M{1,10}
count=ones(1,10);
for i=1:60000
M{1,Trainlabels(i,1)+1}(:,count(1,Trainlabels(i,1)+1))=Train(:,i);
count(1,Trainlabels(i,1)+1)=count(1,Trainlabels(i,1)+1)+1;
end
%调用自定义函数读取测试集中的数据
Test=loadMNISTImages('T10K-images.idx3-ubyte');
%增加一位特征,仍记为Test
B(1,1:10000)=1;
Test=[B;Test];
%调用自定义函数读取测试集中数据标签
Testlabels=loadMNISTLabels('t10k-labels.idx1-ubyte');
%根据标签对训练集中的数据分类,分别记为N{1,1},N{1,2}...N{1,10}
count=ones(1,10);
for i=1:10000
N{1,Testlabels(i,1)+1}(:,count(1,Testlabels(i,1)+1))=Test(:,i);
count(1,Testlabels(i,1)+1)=count(1,Testlabels(i,1)+1)+1;
end
%设置学习率
eta=1;
%迭代算法,训练模型,得到感知机参数w
%两两分类,循环45次
for s=1:9
for t=(s+1):10
M{1,t}=-M{1,t};
P=[M{1,s},M{1,t}];
[m,n]=size(P);
w=randn(1,785);
for j=1:200
for i=1:n
if (w)*P(:,i)<0
w=w+eta*(P(:,i))';
end
end
end
%计算训练准确率
k=0;
for i=1:n
if (w)*P(:,i)>=0;
k=k+1;
end
end
Trainaccuracy(s,t)=k/n;
%将得到的模型用于测试
N{1,t}=-N{1,t};
Q=[N{1,s},N{1,t}];
[m,n]=size(Q);
k=0;
for i=1:n
if (w)*Q(:,i)>=0;
k=k+1;
end
end
%计算测试准确率
Testaccuracy(s,t)=k/n;
end
end
%Trainaccuracy,Testaccuracy分别是训练得到的模型在训练集与测试集上,
%对数字i-1与数字j-1分类的准确率(j>i)
由于该算法中有随机参数,每次运行得到的结果是不一样的。
在训练集与测试集上两两分类的准确率如下所示
训练200论:
训练500论
训练2000论
四、感知机的对偶算法
在原始形式的算法中,不妨假设
的初始值为0,对误分类点
,修改
的系数为:
,在学习率给定的情况下,
的增量只与误分类点
有关,通过这种方式逐步修改
的值。假设共修改了
次,假设其中有
次是由错分样本
而引起的修改,则
关于样本
的增量为
,其中
。最后学习得到的参数
,其中
为训练集中的总样本个数。如果
分类错误一次,对应的
的增量为
,对应的
的增量为
,这样就得到了感知机的对偶形式。对于一个特征向量
,如果
,则分类正确,反正则分类错误。
通过训练数据集计算的参数是
。对偶算法如下:
(1)、随机初始化参数
(2)、在训练集中选取数据
(3)、如果
,则:
。这样算法复杂度过高。我们进行批更新,即对所有
都遍历一遍后,更新一次
(4)、转至(2),直到没有误分类数据。
这样就得到了
,从而得到
,进而可对测试数据集分类。
在实际训练中,我们往往设置训练的次数来决定训练是否结束。在对偶形式中,训练实例只与内积形式出现,为了方便,可以预先将实例间的内积计算出来并以矩阵形式存储,这就是
矩阵,
。
五、对偶算法的实现
源代码如下:
%调用自定义函数读取训练集中的数据
Train=loadMNISTImages('train-images.idx3-ubyte');
%增加一位特征,仍记为Train
A(1,1:60000)=1;
Train=[A;Train];
%调用自定义函数读取训练集中数据标签
Trainlabels=loadMNISTLabels('train-labels.idx1-ubyte');
%根据标签对训练集中的数据分类,分别记为M{1,1},M{1,2}...M{1,10}
count=ones(1,10);
for i=1:60000
M{1,Trainlabels(i,1)+1}(:,count(1,Trainlabels(i,1)+1))=Train(:,i);
count(1,Trainlabels(i,1)+1)=count(1,Trainlabels(i,1)+1)+1;
end
%调用自定义函数读取测试集中的数据
Test=loadMNISTImages('T10K-images.idx3-ubyte');
%增加一位特征,仍记为Test
B(1,1:10000)=1;
Test=[B;Test];
%调用自定义函数读取测试集中数据标签
Testlabels=loadMNISTLabels('t10k-labels.idx1-ubyte');
%根据标签对训练集中的数据分类,分别记为N{1,1},N{1,2}...N{1,10}
count=ones(1,10);
for i=1:10000
N{1,Testlabels(i,1)+1}(:,count(1,Testlabels(i,1)+1))=Test(:,i);
count(1,Testlabels(i,1)+1)=count(1,Testlabels(i,1)+1)+1;
end
%设置学习率
eta=1;
%迭代算法,训练模型,得到感知机参数a
%两两分类,循环45次
for s=1:9
for t=(s+1):10
M{1,t}=-M{1,t};
P=[M{1,s},M{1,t}];
[m,n]=size(P);
%计算训练数据集的Gram矩阵
Gram_Train=P'*P;
% a初始化
a=randn(1,n);
for j=1:200
T=Gram_Train*a';
for i=1:n
if T(i,1)<0
a(1,i)=a(1,i)+eta;
end
end
end
%计算训练准确率
k=0;
T=Gram_Train*a';
for i=1:n
if T(i,1)>0
k=k+1;
end
end
%Trainaccuracy,Testaccuracy分别是训练得到的模型在训练集与测试集上,
%对数字i-1与数字j-1分类的准确率(j>i)
Trainaccuracy(s,t)=k/n;
%将得到的模型用于测试
w=P*a';
N{1,t}=-N{1,t};
Q=[N{1,s},N{1,t}];
[m,n]=size(Q);
k=0;
for i=1:n
if (w')*Q(:,i)>=0;
k=k+1;
end
end
%计算测试准确率
Testaccuracy(s,t)=k/n;
end
end
学习率设为1,两两循环200论,得到在训练集上的准确率与测试上的准确率如下(矩阵的ij元表示数字i-1与数字j-1的分类准确率)
训练集上的准确率
测试集上的准确率