感知机（perception）是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。
2.1 感知机模型
f ( x ) = sign ( w ⋅ x + b ) f(x)=\operatorname{sign}(w \cdot x+b) f(x)=sign(w⋅x+b)
w w w和 b b b为感知机模型参数， w ∈ R n w \in \mathbf{R}^{n} w∈Rn叫做权重或权值向量， b ∈ R b \in \mathbf{R} b∈R叫做偏置， w ⋅ x w\cdot x w⋅x表示内积。
几何解释：
线性方程 w ⋅ x + b = 0 w\cdot x + b = 0 w⋅x+b=0对应于特征空间 R n \mathbf{R}^{n} Rn的一个超平面 S S S，其中 w w w是超平面的法向量， b b b是超平面的截距。这个超平面 S S S将特征空间划分为正负两类样本的空间。 S S S称为分离超平面。
线性可分性：如果存在某个超平面 S S S能够将正实例点和负实例点完全正确地划分到超平面两侧，则数据集具有线性可分性。
定理（Novikoff）:设训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T = \{ (x_1, y_1), (x_2, y_2), ... , (x_N, y_N)\} T={(x1,y1),(x2,y2),...,(xN,yN)}是线性可分的，其中 x i ∈ X = R n x_{i} \in \mathcal{X}=\mathbf{R}^{n} xi∈X=Rn, y i ∈ Y = { − 1 , + 1 } y_{i} \in \mathcal{Y}=\{-1,+1\} yi∈Y={−1,+1}，则：
（1）存在满足条件 ∣ ∣ w ^ o p t ∣ ∣ = 1 ||\hat w_{opt}|| = 1 ∣∣w^opt∣∣=1的超平面 w ^ o p t ⋅ x ^ = w o p t ⋅ x + b o p t = 0 \hat{w}_{\mathrm{opt}} \cdot \hat{x}=w_{\mathrm{opt}} \cdot x+b_{\mathrm{opt}}=0 w^opt⋅x^=wopt⋅x+bopt=0将数据集完全正确分开；且存在 γ > 0 \gamma >0 γ>0，满足：
y i ( w ^ o p t ⋅ x ^ i ) = y i ( w o p t ⋅ x i + b o p t ) ⩾ γ y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)=y_{i}\left(w_{\mathrm{opt}} \cdot x_{i}+b_{\mathrm{opt}}\right) \geqslant \gamma yi(w^opt⋅x^i)=yi(wopt⋅xi+bopt)⩾γ
（2）令 R = m a x { ∣ ∣ x ^ i ∣ ∣ } R = max\{||\hat x_i||\} R=max{∣∣x^i∣∣},则感知算法在训练数据集上的误分类次数 k k k满足不等式：
k ⩽ ( R γ ) 2 k \leqslant\left(\frac{R}{\gamma}\right)^{2} k⩽(γR)2
2.2 感知机学习策略
对于误分类点 ( x i , y i ) (x_i,y_i) (xi,yi), 当 w ⋅ x + b > 0 w\cdot x+b >0 w⋅x+b>0时， y i = − 1 y_i=-1 yi=−1;当 w ⋅ x + b < 0 w\cdot x+b <0 w⋅x+b<0时， y i = + 1 y_i=+1 yi=+1,所以有:
− y i ( w ⋅ x + b ) > 0 -y_i(w\cdot x + b ) > 0 −yi(w⋅x+b)>0
误分类点 ( x i , y i ) (x_i,y_i) (xi,yi)到超平面 S S S的距离为：
d = − y i ( w ⋅ x + b ) ∣ ∣ w ∣ ∣ d = -\dfrac{y_i(w\cdot x + b)}{||w||} d=−∣∣w∣∣yi(w⋅x+b)
设所有误分类点到超平面 S S S的集合为 M M M，则总距离(忽略 1 ∣ ∣ w ∣ ∣ \dfrac{1}{||w||} ∣∣w∣∣1) 为：
d s = − ∑ x i ∈ M y i ( w ⋅ x + b ) d_s = -\sum_{x_i \in M}y_i(w\cdot x +b) ds=−xi∈M∑yi(w⋅x+b)
因此，感知机 sign ( w ⋅ x + b ) \operatorname{sign}(w \cdot x+b) sign(w⋅x+b)的损失函数定义为：
L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x + b ) L(w,b) = -\sum_{x_i \in M}y_i(w\cdot x + b) L(w,b)=−xi∈M∑yi(w⋅x+b)
即感知机学习的是经验风险最小化的损失函数（经验风险函数）。
2.3 原始形式的感知机学习算法
感知机学习算法是误分类驱动，采用随机梯度下降（SGD）算法。随机选取超平面 ( w 0 , b 0 ) (w_0,b_0) (w0,b0)，采用梯度下降算法最小化损失函数。对于误分类点 ( x i , y i ) (x_i,y_i) (xi,yi)，满足: y i ( w ⋅ x + b ⩽ 0 ) y_i(w\cdot x + b \leqslant 0) yi(w⋅x+b⩽0)，采用如下更新方式：
w w w的梯度计算： ∇ w L ( w , b ) = − ∑ x i ∈ M y i x i \nabla_{w} L(w, b)=-\sum_{x_{i} \in M} y_{i} x_{i} ∇wL(w,b)=−∑xi∈Myixi；更新公式： w ← w + η y i x i w \leftarrow w+\eta y_{i} x_{i} w←w+ηyixi；
b b b的梯度计算： ∇ b L ( w , b ) = − ∑ x i ∈ M y i \nabla_{b} L(w, b)=-\sum_{x_{i} \in M} y_{i} ∇bL(w,b)=−∑xi∈Myi；更新公式： b ← b + η y i b \leftarrow b+\eta y_{i} b←b+ηyi；
注:感知机学习由于采用不同的初值或选取不同的误分类点，解可以不同。由Novikoff定理可知，误分类次数 k k k存在上界，经过有限次搜索可以找到将训练数据集完全分开的分离超平面，即当数据集线性可分时，感知学习算法是收敛的。为了得到唯一超平面，需要对超平面添加约束条件，即线性支持向量机。当训练数据集线性不可分时，感知机学习算法不收敛，迭代结果会发生振荡。
2.4 对偶形式的感知机学习算法
感知机模型：
f ( x ) = sign ( ∑ j = 1 N α j y j x j ⋅ x + b ) f(x)=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b\right) f(x)=sign(j=1∑Nαjyjxj⋅x+b)
其中 α = ( α 1 , α 2 , ⋯   , α N ) T \alpha=\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{N}\right)^{\mathrm{T}} α=(α1,α2,⋯,αN)T， α i = n i η \alpha_{i}=n_{i} \eta αi=niη，对于 y i ( ∑ j = 1 N α j y j x j ⋅ x i + b ) ⩽ 0 y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+b\right) \leqslant 0 yi(∑j=1Nαjyjxj⋅xi+b)⩽0,采用如下更新公式：
w ← w + η y i x i w \leftarrow w+\eta y_{i} x_{i} w←w+ηyixi，最终学习的 w = ∑ i = 1 N α i y i x i w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} w=∑i=1Nαiyixi
b ← b + η y i b \leftarrow b+\eta y_{i} b←b+ηyi，最终学习的 b = ∑ i = 1 N α i y i b=\sum_{i=1}^{N} \alpha_{i} y_{i} b=∑i=1Nαiyi
为了方便，可以预定义并存储实例间内积矩阵，即Gram Matrix: G = [ x i ⋅ x j ] N × N G=\left[x_{i} \cdot x_{j}\right]_{N\times N} G=[xi⋅xj]N×N。
![简单文档分类——朴素贝叶斯算法朴素贝叶斯算法简单文档分类实例步骤总结朴素贝叶斯分类调用(sklearn)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)