机器学习笔记之线性分类——感知机算法

引言

上一节介绍了线性回归模型的具体性质，本节将介绍线性分类中第一个具有代表性意义的算法——感知机算法(Perceptron)。

回顾：线性回归与线性分类

线性回归的模型(拟合方程)具体表示如下： f ( W , b ) = W T x ( i ) + b ( i = 1 , 2 , ⋯   , N ) f(\mathcal W,b) = \mathcal W^{T}x^{(i)} + b \quad(i = 1,2,\cdots,N) f(W,b)=WTx(i)+b(i=1,2,⋯,N) 其中 N N N表示数据集合中样本数量。从模型的角度观察，线性回归与线性分类的最根本区别是模型中是否包含非线性激活函数。

非线性激活函数的存在意义本质上是分类任务的需要。由于任务性质的不同:

• 回归任务是 模型拟合样本。它的思路是模型如何精确描述真实样本的趋势。因此，它的策略(损失函数) 主要表示为 模型拟合结果 W T x ( i ) + b \mathcal W^{T}x^{(i)} +b WTx(i)+b与真实标签 y ( i ) y^{(i)} y(i)之间的差距信息： L ( W ) = ∑ i = 1 N ∣ ∣ W T x ( i ) + b − y ( i ) ∣ ∣ 2 \mathcal L(\mathcal W) = \sum_{i=1}^N ||\mathcal W^{T}x^{(i)}+b - y^{(i)}||^2 L(W)=i=1∑N​∣∣WTx(i)+b−y(i)∣∣2

• 分类任务是 模型划分样本。不同于回归任务，此时的样本点并不存在某种趋势，而是聚集在不同的样本子空间中。因此，线性分类的思路是 模型 f ( W , b ) = W T x ( i ) + b f(\mathcal W,b) = \mathcal W^{T}x^{(i)} + b f(W,b)=WTx(i)+b在 p p p维样本子空间中产生的线(超平面)，对样本空间进行划分，从而实现各样本在对应样本子空间的分类效果。

线性分类的类型

以激活函数的连续性对线性分类类型进行划分：

• 硬分类：激活函数是非连续型函数；
• 软分类：激活函数是连续型函数；

以二分类为例，真实标签结果 y ( i ) y^{(i)} y(i)只包含2个具体数值。例如： y ( i ) ∈ { − 1 , 1 } ( i = 1 , 2 , ⋯   , N ) y^{(i)} \in \{-1,1\}\quad (i=1,2,\cdots,N) y(i)∈{−1,1}(i=1,2,⋯,N)

• 硬分类中激活函数映射结果 y p r e d ( i ) = s i g n ( W T x ( i ) + b ) y_{pred}^{(i)} = sign(\mathcal W^{T}x^{(i)} + b) ypred(i)​=sign(WTx(i)+b)与真实标签结果的特征空间相同。即： y p r e d ( i ) ∈ { − 1 , 1 } ( i = 1 , 2 , ⋯   , N ) y_{pred}^{(i)} \in \{-1,1\} \quad (i=1,2,\cdots,N) ypred(i)​∈{−1,1}(i=1,2,⋯,N)
• 软分类中激活函数映射结果是基于连续空间 [ 0 , 1 ] [0,1] [0,1]中的结果，其实际意义为选择上述两种真实标签的概率结果。即： 其中 p p p表示’激活函数映射结果’ y p r e d ( i ) y_{pred}^{(i)} ypred(i)​选择数值1的概率； { P ( y p r e d ( i ) = 1 ) = p P ( y p r e d ( i ) = − 1 ) = 1 − p \begin{cases}P(y_{pred}^{(i)}=1) = p \\ P(y_{pred}^{(i)} = -1) = 1 - p \end{cases} {P(ypred(i)​=1)=pP(ypred(i)​=−1)=1−p​

线性分类算法中：

• 具有代表性的硬分类算法有感知机算法、线性判别分析(Linear Discriminant Analysis,LDA)。
• 具有代表性的软分类算法具体也分为两种：
  • 判别模型：代表模型有逻辑回归(Logistic Regression)； 判别模型的主要思路：直接求解 条件概率 P ( Y p r e d = − 1 ∣ X ) P(\mathcal Y_{pred}=-1 \mid \mathcal X) P(Ypred​=−1∣X)与 P ( Y p r e d = 1 ∣ X ) P(\mathcal Y_{pred}=1 \mid \mathcal X) P(Ypred​=1∣X)之间的大小关系。其中 X , Y p r e d \mathcal X,\mathcal Y_{pred} X,Ypred​分别表示样本集合与预测标签的概率分布集合；
  • 生成模型：代表模型有高斯判别分析(Gaussian Discriminant Analysis,GDA)； 生成模型的主要思路：使用贝叶斯定理将 P ( Y p r e d ∣ X ) P(\mathcal Y_{pred} \mid \mathcal X) P(Ypred​∣X)分解为如下形式： P ( Y p r e d ∣ X ) = P ( X ∣ Y p r e d ) P ( Y p r e d ) P ( X ) P(\mathcal Y_{pred} \mid \mathcal X) = \frac{P(\mathcal X \mid \mathcal Y_{pred})P(\mathcal Y_{pred})}{P(\mathcal X)} P(Ypred​∣X)=P(X)P(X∣Ypred​)P(Ypred​)​ 由于样本集合 X \mathcal X X是给定的，因此可以将分母视为 X \mathcal X X的边缘概率分布，是常数；从而有： P ( Y p r e d ∣ X ) ∝ P ( X ∣ Y p r e d ) P ( Y p r e d ) P(\mathcal Y_{pred} \mid \mathcal X) \propto P(\mathcal X \mid \mathcal Y_{pred})P(\mathcal Y_{pred}) P(Ypred​∣X)∝P(X∣Ypred​)P(Ypred​) 换句话说，就是给 Y p r e d \mathcal Y_{pred} Ypred​一个先验信息 P ( Y p r e d ) P(\mathcal Y_{pred}) P(Ypred​)，通过求解 P ( X ∣ Y p r e d = − 1 ) P ( Y p r e d = − 1 ) P(\mathcal X \mid \mathcal Y_{pred}=-1)P(\mathcal Y_{pred} = -1) P(X∣Ypred​=−1)P(Ypred​=−1)和 P ( X ∣ Y p r e d = 1 ) P ( Y p r e d = 1 ) P(\mathcal X \mid \mathcal Y_{pred} = 1)P(\mathcal Y_{pred} = 1) P(X∣Ypred​=1)P(Ypred​=1)之间的大小关系来映射 P ( Y p r e d = 1 ∣ X ) P(\mathcal Y_{pred} = 1 \mid \mathcal X) P(Ypred​=1∣X)与 P ( Y p r e d = − 1 ∣ X ) P(\mathcal Y_{pred} = -1 \mid \mathcal X) P(Ypred​=−1∣X)之间的大小关系。

本节将介绍硬分类算法中的感知机算法。

感知机算法(Perceptron)

感知机算法作为线性分类中最简单的模型之一，它的模型表示如下： f ( W , b ) = s i g n ( W T x ( i ) + b ) ( i = 1 , 2 , ⋯   , N ) f(\mathcal W,b) = sign(\mathcal W^{T}x^{(i)} +b) \quad(i=1,2,\cdots,N) f(W,b)=sign(WTx(i)+b)(i=1,2,⋯,N) 其中： x ( i ) = ( x 1 ( i ) , x 2 ( i ) , ⋯   , x p ( i ) ) T W = ( w 1 , w 2 , ⋯   , w p ) T x^{(i)} = (x_1^{(i)},x_2^{(i)},\cdots,x_p^{(i)})^T \\ \mathcal W = (w_1,w_2,\cdots,w_p)^T x(i)=(x1(i)​,x2(i)​,⋯,xp(i)​)TW=(w1​,w2​,⋯,wp​)T 记作 x ( i ) ∈ R p , W ∈ R p , b ∈ R x^{(i)} \in \mathbb R^{p},\mathcal W \in \mathbb R^p,b \in \mathbb R x(i)∈Rp,W∈Rp,b∈R。 s i g n sign sign函数被称为符号函数。它的定义如下： s i g n ( a ) = { 1 a ≥ 0 − 1 a < 0 sign(a) = \begin{cases}1 \quad a \geq 0 \\ -1 \quad a < 0\end{cases} sign(a)={1a≥0−1a