感知机（perceptron）由Rosenblatt于1957年提出，是一种二类分类的线性分类器模型，输入的是实例（样本）的特征向量，输出的是实例的类别，一般以+1和-1两个值。感知机其实就是输入空间中将实例划分的超平面，属于判别模型。如果熟悉SVM的同学可能会联想到那个支持向量，两者的几何含义差不多。感知机学习旨在求出将训练数据进行线性划分的超平面，利用梯度下降法，将损失函数极小化，求得感知机模型。感知机是神经网络和SVM的基础。
定义 1.1 （感知机） 假设输入空间（特征空间） X⊆Rn X ⊆ R n ，输出空间是 Y={+1,−1} Y = { + 1 , − 1 } ，输入 x∈X x ∈ X 表示实例的特征向量，代表输入空间的点，输出 y∈{+1,−1} y ∈ { + 1 , − 1 } 表示实例的类别，从输入空间到输出空间的映射：
f(x)=sign(w⋅x+b) f ( x ) = s i g n ( w ⋅ x + b ) 称为感知机。其中 w,b w , b 是感知机的参数， w∈Rn w ∈ R n 称为权重或者权值向量， b∈R b ∈ R 称为偏置（bias）。sign(x)是符号函数，即：sign(x)={+1,x≥0−1,x<0 s i g n ( x ) = { + 1 , x ≥ 0 − 1 , x < 0
感知机有如下几何解释，线性方程 w⋅x+b=0 w ⋅ x + b = 0 ，对应于特征空间 Rn R n 的一个超平面 S S ，其中 ww 是超平面的法向量， b b 是超平面的截距，这个超平面将特征空间里样本点分为正负两类。
定义1.2 （ 数据集的线性可分性） 给定一个数据集 T={(x1,y1),(x2,y2),...,(xN,yN)}T={(x1,y1),(x2,y2),...,(xN,yN)}，其中 xi∈X=Rn x i ∈ X = R n ， yi∈Y={+1,−1},i=1,2,3,...,N y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , 3 , . . . , N ，如果存在一个超平面 S S ：w⋅x b=0w⋅x b=0 能够将 数据集的正样本和负样本完全分到超平面的两侧，对于所有 yi=+1 y i = + 1 的样本，有 w⋅xi+b>0 w ⋅ x i + b > 0 ，所有 yi=−1 y i = − 1 的样本，有 w⋅xi+b<0 w ⋅ x i + b < 0 ，则称数据 T T 为线性可分数据集
为了找到能将数据集分开的超平面，也就是找到参数 w,bw,b ，我们需要确定一个学习策略，即定义一个损失函数并将损失最小化。我们自然想到会使用分类点的错误数作为损失函数，但是这个损失函数关于 w,b w , b 不是连续可导的，不容易优化求解。我们可选择每一个误分类点到超平面 S S 的总距离，根据空间几何知识，点 x0x0 到平面 S S 的距离为: 1∥w∥|w⋅x0 b|1‖w‖|w⋅x0 b| 其中 ∥w∥ ‖ w ‖ 是 w w 的 L2L2 范数。对于分类错误的点来说， yi y i 和 w⋅xi+b w ⋅ x i + b 异号，所以 −yi(w⋅xi+b)>0 − y i ( w ⋅ x i + b ) > 0 因此，误分类点到超平面的距离是
−1∥w∥yi(w⋅xi+b) − 1 ‖ w ‖ y i ( w ⋅ x i + b )那么对于所有误分类点集合 M M ，所有点到超平面的总距离为 −1∥w∥∑xi∈Myi(w⋅xi b)−1‖w‖∑xi∈Myi(w⋅xi b) 不考虑 1∥w∥ 1 ‖ w ‖ (个人感觉这里稍微有点问题，不考虑这一项，结果和加上这一项肯定是有差异的，这里这样操作应该是出于方便求导的考虑)，就得到感知机的损失函数
对于给定的训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)} T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } ，感知机 sign(w⋅x+b) s i g n ( w ⋅ x + b ) 学习的损失函数定义为：
L(w,b)=−∑xi∈Myi(w⋅xi+b) L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) 显然这个损失函数是非负的，分类错误的点越少，损失函数值越小，给定一个训练数据集 T T ，损失函数 L(w,b)L(w,b) 是 w,b w , b 的连续可导函数感知机算法用于求解一下最优化问题：
minw,bL(w,b)=−∑xi∈Myi(w⋅xi+b) min w , b L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) 其中 M M 是分错点的集合输入：训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)}T={(x1,y1),(x2,y2),...,(xN,yN)}，其中 xi∈X=Rn x i ∈ X = R n ， yi∈Y={+1,−1} y i ∈ Y = { + 1 , − 1 } ， i=1,2,3,...,N i = 1 , 2 , 3 , . . . , N ，学习率 η (0<η≤1) η ( 0 < η ≤ 1 ) 输出： w,b w , b ，感知机模型 f(x)=sign(w⋅x+b) f ( x ) = s i g n ( w ⋅ x + b ) (1) 选取初始值 w0,b0 w 0 , b 0 (2) 在训练集中选取(x_i, y_i) (3) 如果 yi(w⋅xi+b)≤0 y i ( w ⋅ x i + b ) ≤ 0
wb⟵w+ηyixi,x≥0⟵b+ηyi,x<0 w ⟵ w + η y i x i , x ≥ 0 b ⟵ b + η y i , x < 0
(4) 转至(2) ，直到训练集中没有误分类点
我们可以直观的来理解这个算法，当有一个样本点被分错时，改变 w,b w , b ，也就是调整了超平面，让它减少与分错点的距离，直到被分对。 以下例子摘自《统计学习方法》p29
这是在计算中误分类点先后取 x1,x3,x3,x3,x1,x3,x3 x 1 , x 3 , x 3 , x 3 , x 1 , x 3 , x 3 得到的分离超平面和感知机模型，如果在计算中误分类点依次取 x1,x3,x3,x3,x2,x3,x3,x3,x1,x3,x3 x 1 , x 3 , x 3 , x 3 , x 2 , x 3 , x 3 , x 3 , x 1 , x 3 , x 3 ，那得到的平面就是 2x(1)+x(2)−5=0 2 x ( 1 ) + x ( 2 ) − 5 = 0 ，可以看到，感知机算法由于采用不同的初值或者选取不同的误分类点，解可能不一样。
可以证明，对于线性可分数据集感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全划分的分离超平面和感知机模型，详细推导参考《统计学习方法》p31-p32
感知机算法的对偶形式，基本想法就是将 w,b w , b 表示为 xi,yi x i , y i 线性组合的形式
wb=∑i=1Nαiyixi=∑i=1Nαiyi w = ∑ i = 1 N α i y i x i b = ∑ i = 1 N α i y i
这里 αi≥0 α i ≥ 0 ，表示第 i 个样本点由于分类错误而进行更新的次数，样本点如果更新次数越多，表示它离超平面越近，越难被区分。
输入：训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)} T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } ，其中 xi∈X=Rn x i ∈ X = R n ， yi∈Y={+1,−1} y i ∈ Y = { + 1 , − 1 } ， i=1,2,3,...,N i = 1 , 2 , 3 , . . . , N ，学习率 η (0<η≤1) η ( 0 < η ≤ 1 ) 输出： α,b α , b ，感知机模型 f(x)=sign(∑Nj=1yjxjx+b) f ( x ) = s i g n ( ∑ j = 1 N y j x j x + b ) ， α=(α1,α2,...,αN)T α = ( α 1 , α 2 , . . . , α N ) T (1) α⟵0 α ⟵ 0 ， b⟵0 b ⟵ 0 (2) 在训练集中选取(x_i, y_i) (3) 如果 yi(∑Nj=1yjxjx+b)≤0 y i ( ∑ j = 1 N y j x j x + b ) ≤ 0
αib⟵αi+η⟵b+ηyi α i ⟵ α i + η b ⟵ b + η y i
(4) 转至(2) ，直到训练集中没有误分类点
对偶形式中训练样本仅以内积的形式出现，为了方便，可以预先将训练集中样本间的内急计算出来存入到矩阵中，高等代数里这个矩阵称为 Gram矩阵
G=[xi⋅xj]N∗N G = [ x i ⋅ x j ] N ∗ N以下例子摘自《统计学习方法》p34-35
