【机器学习】感知机原理详解

其他机器学习系列文章见于专题：机器学习进阶之路——学习笔记整理，欢迎大家关注。

  感知机（perceptron）是二分类的线性分类模型，属于监督学习算法。输入为实例的特征向量，输出为实例的类别（取+1和-1）。感知机旨在求出将输入空间中的实例划分为两类的分离超平面。为求得超平面，感知机导入了基于误分类的损失函数，利用梯度下降法对损失函数进行最优化求解。

  如果训练数据集是线性可分的，则感知机一定能求得分离超平面。如果是非线性可分的数据，则无法获得超平面。

  感知机具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的实例进行预测的，因此属于判别模型。感知机是神经网络和支持向量机的基础。

  假设训练数据集为 D = { ( x i , y i ) } i = 1 m D = \left\{ \left( x _ { i } , y _ { i } \right) \right\} _ { i = 1 } ^ { m } D={(xi​,yi​)}i=1m​，其中， x i ∈ X ⊆ R n x _ { i } \in \mathcal { \mathbf X } \subseteq \mathbf { R } ^ { n } xi​∈X⊆Rn， y i ∈ Y = { + 1 , − 1 } y _ { i } \in \mathcal { \mathbf Y } = \left\{ +1 , -1 \right\} yi​∈Y={+1,−1}。

  感知机模型为： (1) f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w⋅x+b)\tag{1} f(x)=sign(w⋅x+b)(1)   其中， w w w和 b b b称为感知机模型参数， w ∈ R n w∈ R^n w∈Rn叫做权值或者权值向量， b ∈ R b∈R b∈R叫做偏置。 w ⋅ x w \cdot x w⋅x表示 w w w和 x x x的内积。 s i g n sign sign函数是符号函数： (2) sign ⁡ ( x ) = { + 1 , x ≥ 0 − 1 , x ; 0 \operatorname { sign } ( x ) = \left\{ \begin{array} { l l } { + 1 , } ; { x \geq 0 } \\ { - 1 , } ; { x ; 0 } \end{array} \right.\tag{2} sign(x)={+1,−1,​x≥0x0时；对所有 y i = − 1 y_i=-1 yi​=−1的样本，都有 w ⋅ x i + b ; 0 w \cdot x_i + b ; 0 w⋅xi​+b0

  因此，误分类点 x i x_i xi​到超平面 S S S的距离是： − 1 ∥ w ∥ y i ( w ⋅ x i + b ) -\frac { 1 } { \| w \| } y _ { i } \left( w \cdot x _ { i } + b \right) −∥w∥1​yi​(w⋅xi​+b)

  假设超平面 S S S的误分类点集合为 M M M，那么所有误分类点到超平面 S S S的总距离为： − 1 ∥ w ∥ ∑ x i ∈ M y i ( w ⋅ x i + b ) -\frac { 1 } { \| w \| } \sum _ { x _ { i } \in M } y _ { i } \left( w \cdot x _ { i } + b \right) −∥w∥1​xi​∈M∑​yi​(w⋅xi​+b)

  不考虑 1 ∥ w ∥ \frac { 1 } { \| w \| } ∥w∥1​，就得到感知机学习的损失函数：

L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L ( w , b ) = - \sum _ { x _ { i } \in M } y _ { i } \left( w \cdot x _ { i } + b \right) L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)

  这个损失函数就是感知机学习的经验风险函数。

为什么可不考虑 1 ∥ w ∥ \frac { 1 } { \| w \| } ∥w∥1​？   这是因为，偏置 b b b可以定义为 b = w 0 x 0 b = w _ { 0 }x_{ 0 } b=w0​x0​，其中 x 0 = 1 x_0=1 x0​=1，将 b b b吸收进 w w w里面。这样我们再来看总距离就变成了 − 1 ∥ w ∥ ∑ x i ∈ M y i w ⋅ x i - \frac { 1 } { \| w \| } \sum _ { x _ { i } \in M } y _ { i } w \cdot x _ { i } −∥w∥1​∑xi​∈M​yi​w⋅xi​。   分子和分母都含有 w w w,当分子的 w w w扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么我们可以固定分子或者分母为1，然后求分母的倒数或者分子自己的最小化作为损失函数，这样可以简化我们的损失函数。在感知机模型中，我们采用的是保留分子。

  至此，感知机学习问题就转化为了求解损失函数的最优化问题。

  由于感知机学习算法是误分类驱动的，这里基于随机梯度下降法（SGD）进行优化求解。即任意选取一个超平面 w 0 w_0 w0​， b 0 b_0 b0​，然后用梯度下降法不断地极小化损失函数。极小化过程中不是一次使 M M M中的所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

  这里不能使用基于所有样本的批量梯度下降（BGD）进行优化。这是因为我们的损失函数里面有限定，只有误分类的 M M M集合里面的样本才能参与损失函数的优化。所以我们不能用最普通的批量梯度下降，只能采用随机梯度下降（SGD）或者小批量梯度下降（MBGD）。

  损失函数 L ( w , b ) L ( w , b ) L(w,b)的梯度为： ∇ 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 } ∇w​L(w,b)=−xi​∈M∑​yi​xi​

∇ b L ( w , b ) = − ∑ x i ∈ M y i \nabla _ { b } L ( w , b ) = - \sum _ { x _ { i } \in M } y _ { i } ∇b​L(w,b)=−xi​∈M∑​yi​

  随机选取一个误分类点 ( x i , y i ) \left( x _ { i } , y _ { i } \right) (xi​,yi​)，对 w w w， b b b进行更新： w ← w + η y i x i w \leftarrow w + \eta y _ { i } x _ { i } w←w+ηyi​xi​

b ← b + η y i b \leftarrow b + \eta y _ { i } b←b+ηyi​

  输入：训练数据集 D = { ( x i , y i ) } i = 1 m D = \left\{ \left( x _ { i } , y _ { i } \right) \right\} _ { i = 1 } ^ { m } D={(xi​,yi​)}i=1m​，其中， x i ∈ X ⊆ R n x _ { i } \in \mathcal { \mathbf X } \subseteq \mathbf { R } ^ { n } xi​∈X⊆Rn， y i ∈ Y = { + 1 , − 1 } y _ { i } \in \mathcal { \mathbf Y } = \left\{ +1 , -1 \right\} yi​∈Y={+1,−1}；学习率 η ( 0 ; η ≤ 1 ) \eta ( 0 ; \eta \leq 1 ) η(0+1,−1}；学习率 η ( 0 ; η ≤ 1 ) \eta ( 0 ; \eta \leq 1 ) η(0