一、感知机模型
感知机是一个二分类的线性分类模型，输入为实例的特征向量，输出实例的类别，取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论
四、感知机的对偶算法
在原始形式的算法中，不妨假设
通过训练数据集计算的参数是
(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的分类准确率）