感知机算法（Python机器学习）详解

在前面的章节中，我们介绍了用于处理二分类问题的 Logistic Regression 算法和用于处理多分类问题的 Softmax Regression 算法。典型的二分类问题，如图 1 所示。
对于如图 1 所示的二分类问题中，“.”表示正类，“。”表示负类。我们试图寻找到图中的分隔超平面，能够分隔图中的正负样本，其中，分隔超平面为：

最终得到如下所示的分类决策函数：
其中，函数 sign(x) 为符号函数：
当 W^∗·X+b^∗＞0 时，为正类；当 W^∗·X+b^∗＜0 时，为负类。

感知机算法

对于二分类问题，假设有 m 个训练样本{(X⁽¹⁾，y⁽¹⁾)，(X⁽²⁾，y⁽²⁾)，…，(X^(m)，y^(m))}，其中，y∈{-1，1}。那么，应该如何从训练样本中得到分隔超平面 W^∗·X+b^∗=0 呢？

对于如图 1 所示的二分类问题，我们希望构建好的分隔超平面能够将正类（图 1 中的“.”）和负类（图 1 中的“。”）全部正确区分开。

1957 年由 Rosenblatt 提出了感知机算法，在感知机算法中直接使用通误分类的样本到分隔超平面之间的距离 S 作为其损失函数，并利用梯度下降法求得误分类的损失函数的极小值，得到最终的分隔超平面。

对于训练样本点 X⁽ⁱ⁾，其到分隔超平面的距离 S 为：
其中，||W|| 为 W 的 L₂ 范数。对于图 1 中，样本点 X⁽ⁱ⁾ 到分隔超平面的距离 S 如图 2 所示。
在训练样本中，对于误分类的样本 (X⁽ⁱ⁾，y⁽ⁱ⁾)，即预测值 W·X⁽ⁱ⁾+b 与真实值 y⁽ⁱ⁾ 异号，即：
则误分类样本到分隔超平面之间的距离为：
若不考虑 1/(||W||)，即为感知机算法的损失函数。感知机算法的损失函数为：
通过求解损失函数的最小值求得最终的分隔超平面，最小值为：

感知机算法存在的问题

在感知机算法中，通过最小化误分类样本到分隔超平面的距离，求得最终的分隔超平面，但是对于感知机算法来说，分隔超平面参数 W 和 b 的初始值和选择误分类样本的顺序对最终的分隔超平面的计算都有影响，采用不同的初始值或者不同的误分类点，最终的分隔超平面是不同的。

对于如图 1 所示的训练数据，最终的分隔超平面如图 3 所示。
在图 3 中的两个分隔超平面都能将正负样本区分开。对于感知机算法，采用不同的初始值或者不同的误分类点，最终的分隔超平面是不同的。在这些分隔超平面中是否存在一个最好的分隔超平面呢？