Perceptron

如何定义损失函数呢？直观的方法是计算训练数据集在模型中的错误分类点的数量。但是，这个损失函数不是参数 \(\boldsymbol{w}\) 和 \(b\) 的连续可导函数，不易优化。感知器选择了另外的损失函数： 训练数据集在模型中的错误分类点到分离超平面的总距离。

我们知道，输入空间 \(\mathbb{R}^n\) 中任一点 \(\boldsymbol{x}\) 到分离超平面的距离为：
\[\frac{1}{\Vert \boldsymbol{w} \Vert} |\boldsymbol{w} \cdot \boldsymbol{x} + b|\]

特别地，当输入空间为 \(\mathbb{R}^2\) 时，这就是点到线的距离公式 \(d=\frac{|ax_0 + by_0 + c|}{\sqrt{a^2+b^2}}\) ；当输入空间为 \(\mathbb{R}^3\) 时，这就是点到平面的距离公式 \(d=\frac{|Ax_0 + By_0 + Cz_0 + D|}{\sqrt{A^2+B^2+C^2}}\) 。

由于距离公式中含有绝对值符号，不便于计算。考虑到，对于错误分类点 \(\boldsymbol{x_i}\) 有：当 \(\boldsymbol{w} \cdot \boldsymbol{x_i} + b > 0\) 时， \(y_i=f(\boldsymbol{x_i})=-1\) ；当 \(\boldsymbol{w} \cdot \boldsymbol{x_i} + b < 0\) 时， \(y_i=f(\boldsymbol{x_i})=+1\) 。所以错误分类点 \(\boldsymbol{x_i}\) 来说，总有： \(-y_i(\boldsymbol{w} \cdot \boldsymbol{x_i} + b) > 0\) ，利用这个性质可以去掉距离公式中的绝对值符号。即，错误分类点 \(\boldsymbol{x_i}\) 到分离超平面的距离也可表示为：
\[-\frac{1}{\Vert \boldsymbol{w} \Vert} y_i (\boldsymbol{w} \cdot \boldsymbol{x_i} + b)\]

假设分离超平面 \(S\) 下的训练数据集的错误分类点为集合 \(M\) ，则所有错误分类点到超平面 \(S\) 的总距离为：
\[-\frac{1}{\Vert \boldsymbol{w} \Vert} \sum_{\boldsymbol{x_i} \in M} y_i (\boldsymbol{w} \cdot \boldsymbol{x_i} + b)\]

不考虑 \(\frac{1}{\Vert \boldsymbol{w} \Vert}\) （对于线性可分的数据集，我们的目标是使损失函数为 0，所以可以省略了这个正系数，这时，优化过程中的损失函数不会严格等于错误分类点到分离超平面的总距离），得到的就是感知器使用的损失函数。

感知器的损失函数定义为：
\[L(\boldsymbol{w},b) = -\sum_{\boldsymbol{x_i} \in M} y_i (\boldsymbol{w} \cdot \boldsymbol{x_i} + b)\]
其中， \(M\) 为训练数据集中错误分类点的集合。

通过上面的分析，我们可知感知器学习算法对应于下面的最优化问题：
给定一个训练数据集
\[T= \{(\boldsymbol{x_1}, y_1), (\boldsymbol{x_2}, y_2), \cdots, (\boldsymbol{x_N}, y_N)\}\]
其中， \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{+1, -1\}\) ，求 \(\boldsymbol{w}\) 和 \(b\) 使得下面损失函数取得最小值。
\[L(\boldsymbol{w},b) = -\sum_{\boldsymbol{x_i} \in M} y_i (\boldsymbol{w} \cdot \boldsymbol{x_i} + b)\]
其中， \(M\) 为训练数据集中错误分类点的集合。

我们使用“梯度下降法(Gradient descent)”解决这个最优化问题。
这里，直接利用“梯度下降法”的结论公式：
\[\theta_{new} = \theta_{old} - \mu \nabla f(\theta_{old}) = \theta_{old} - \mu \left. \frac{\partial f}{\partial \theta} \right|_{\theta = \theta_{old}}, \quad \mu > 0\]
其中 \(\mu > 0\) 称为步长，也可称为学习率。这是一个迭代式，在迭代过程中使损失函数不断减小。

对于这个最优化问题，假设错误分类点集合 \(M\) 是固定的，损失函数 \(L(\boldsymbol{w},b) = -\sum_{\boldsymbol{x_i} \in M} y_i (\boldsymbol{w} \cdot \boldsymbol{x_i} + b)\) 的梯度为：
\[\nabla_{\boldsymbol{w}} L(\boldsymbol{w},b) = \frac{\partial L(\boldsymbol{w},b)}{\partial \boldsymbol{w}} = -\sum_{\boldsymbol{x_i} \in M} y_i \boldsymbol{x_i}, \qquad \nabla_{b} L(\boldsymbol{w},b) = \frac{\partial L(\boldsymbol{w},b)}{\partial b} = -\sum_{\boldsymbol{x_i} \in M} y_i\]

将上面式子代入到“梯度下降法”的公式中，得到参数 \(\boldsymbol{w},b\) 的迭代策略：
\[\begin{cases} \boldsymbol{w}_{new} \leftarrow \boldsymbol{w}_{old} -\mu \left(-\sum_{\boldsymbol{x_i} \in M} y_i \boldsymbol{x_i}\right) = \boldsymbol{w}_{old} + \mu \sum_{\boldsymbol{x_i} \in M} y_i \boldsymbol{x_i} \\ b_{new} \leftarrow b_{old} - \mu \left(- \sum_{\boldsymbol{x_i} \in M} y_i \right) = b_{old} + \mu \sum_{\boldsymbol{x_i} \in M} y_i \end{cases}\]

随着迭代的进行，错误分类点会减小，直到没有错误分类点，迭代结束，这时损失函数（错误分类点到分类超平面的总距离）为 0。

说明：上面式子中，每次对 \(\boldsymbol{w},b\) 进行更新时，所有的错误分类点都参与了计算。在实际运用时，也可以只随机地选取一个错误分类点 \((\boldsymbol{x_i}, y_i)\) 对 \(\boldsymbol{w},b\) 进行更新（这就是 随机梯度下降法 ），即对参数 \(\boldsymbol{w},b\) 采用下面的迭代策略 ：
\[\begin{cases} \boldsymbol{w}_{new} \leftarrow \boldsymbol{w}_{old} + \mu y_i \boldsymbol{x_i} \\ b_{new} \leftarrow b_{old} + \mu y_i \end{cases}\]

前面已经完整地介绍了感知器算法，现在总结如下。

感知器学习算法的原始形式：
感知器模型： \(y = f(\boldsymbol{x}) = sign(\boldsymbol{w} \cdot \boldsymbol{x} + b) = \begin{cases} +1 & \text{if} \; \boldsymbol{w} \cdot \boldsymbol{x} + b > 0 \\ -1 & \text{otherwise} \end{cases}\)
输入：线性可分的训练数据集 \(T= \{(\boldsymbol{x_1}, y_1), (\boldsymbol{x_2}, y_2), \cdots, (\boldsymbol{x_N}, y_N)\}\) ，其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{+1, -1\}, \; i = 1,2, \cdots, N\) ，学习率 \(\mu (0< \mu \le 1)\)
输出：感知器模型参数 \(\boldsymbol{w},b\)
\(\boldsymbol{w},b\) 的求解过程如下：
(1) 选取初值 \(\boldsymbol{w_0},b_0\)
(2) 在训练数据集中选取数据 \((\boldsymbol{x_i}, y_i)\)
(3) 如果 \(y_i(\boldsymbol{w} \cdot \boldsymbol{x_i} + b) \le 0\) （即它是一个错误分类点），则按下面方法更新 \(\boldsymbol{w},b\) ：
\[\begin{cases} \boldsymbol{w} \leftarrow \boldsymbol{w} + \mu y_i \boldsymbol{x_i} \\ b \leftarrow b + \mu y_i \end{cases}\]
(4) 转至(2)，直到没有错误分类点。

说明：上面算法，在某一次具体的迭代中，没有让所有的错误分类点都参与迭代，即没有采用式子 \(\begin{cases} \boldsymbol{w}_{new} \leftarrow \boldsymbol{w}_{old} + \mu \sum_{\boldsymbol{x_i} \in M} y_i \boldsymbol{x_i} \\ b_{new} \leftarrow b_{old} + \mu \sum_{\boldsymbol{x_i} \in M} y_i \end{cases}\) ，而是随机选取一个错误分类点参与迭代，这样实现更简单。

实例：假设训练数据集有两个正实例点（应该分到+1 类的点）A、B分别为： \(\boldsymbol{x_1} = (3,3)^\mathsf{T}, \boldsymbol{x_2} = (4,3)^\mathsf{T}\) ，和一个负实例点（应该分到-1 类的点）C为： \(\boldsymbol{x_3} = (1,1)^\mathsf{T}\) ，利用感知器学习算法的原始形式求感知器模型。
解：
(1) 取学习率 \(\mu=1\) ，参数 \(\boldsymbol{w_0},b_0\) 分别取初值 \((0,0)^\mathsf{T}, 0\)
(2) 对于正实例点 A，计算得 \(y_i(\boldsymbol{w}_0 \cdot \boldsymbol{x_i} + b_0) = 0\) ，故它没有被正确地分类，更新 \(\boldsymbol{w},b\)
\[\begin{cases} \boldsymbol{w}_1 \leftarrow \boldsymbol{w}_0 + 1 \times (+1) \times (3,3)^\mathsf{T} = (3,3)^\mathsf{T} \\ b_1 \leftarrow b_0 + 1 \times (+1) = 1 \end{cases}\]
(3) 对于正实例点 A、B，计算得 \(y_i(\boldsymbol{w}_1 \cdot \boldsymbol{x_i} + b_1) > 0\) 被正确分类，不用更新 \(\boldsymbol{w},b\) ，对于负实例点 C，计算得 \(y_i(\boldsymbol{w}_1 \cdot \boldsymbol{x_i} + b_1) < 0\) ，故它没有被正确地分类，更新 \(\boldsymbol{w},b\)
\[\begin{cases} \boldsymbol{w}_2 \leftarrow \boldsymbol{w}_1 + 1 \times (-1) \times (1,1)^\mathsf{T} = (2,2)^\mathsf{T} \\ b_2 \leftarrow b_1 + 1 \times (-1) = 0 \end{cases}\]
如此继续下去，直到得到 \(\boldsymbol{w}_7 = (1,1)^\mathsf{T}, b_7 = -3\)
具体迭代过程如下：

此时，对 A、B、C 三个实例点都有 \(y_i(\boldsymbol{w}_7 \cdot \boldsymbol{x_i} + b_7) > 0\) ，没有错误分类点，损失函数达到最小。
所以，我们得到的分离超平面为：
\[x^{(1)} + x^{(2)} - 3 = 0\]
感知器模型为：
\[f(\boldsymbol{x}) = \begin{cases} +1 & \text{if} \; x^{(1)} + x^{(2)} - 3 > 0 \\ -1 & \text{otherwise} \end{cases}\]

上面的迭代过程中，错误分类点先后取的是 A、C、C、C、A、C、C；在迭代过程中，还可以依次取错误分类点 A、C、C、C、B、C、C、C、A、C、C，那么得到的分离超平面为： \(2x^{(1)} + x^{(2)} - 5 = 0\)
可见， 采用不同的初值，或当存在多个错误分类点时采用不同策略选取错误分类点来更新参数，感知机学习算法得到的解可能不同。

Novikoff 于 1962 年证明了感知机算法的收敛性。 即对于线性可分的数据，利用感知器算法经过有限次迭代，一定可以得到训练数据集的分离超平面。 其具体证明过程可以参考：《统计学习方法, 李航著》

在感知器算法的原始形式中，不失一般性，可以假设 \(\boldsymbol{w},b\) 的初始值都是 0。对于某一个错误分类点 \((\boldsymbol{x_i}, y_i)\) 来说，它会以下面的公式来更新参数 \(\boldsymbol{w},b\) :
\[\begin{cases} \boldsymbol{w} \leftarrow \boldsymbol{w} + \mu y_i \boldsymbol{x_i} \\ b \leftarrow b + \mu y_i \end{cases}\]
假设这个错误分类点在更新 \(\boldsymbol{w},b\) 时一共被使用了 \(k_i\) 次，则错误分类点 \((\boldsymbol{x_i}, y_i)\) 对参数 \(\boldsymbol{w},b\) 的贡献为 \(k_i \mu y_i \boldsymbol{x_i}\) 。如果记 \(\alpha_i = k_i \mu \ge 0\) ，则每个训练数据对参数 \(\boldsymbol{w},b\) 的贡献可以记为 \(\alpha_i y_i \boldsymbol{x_i}\) 的形式，从而参数 \(\boldsymbol{w},b\) 可以由下式得到：
\[\begin{cases} \boldsymbol{w} = \sum_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \\ b = \sum_{i=1}^{N} \alpha_i y_i \\ \end{cases}\]
其中，\(\alpha_i \ge 0, i=1,2,\cdots,N\), \(N\) 为训练数据的总数。

利用上面的结论，我们把感知器算法的原始形式表述为下面形式（即感知器算法的对偶形式）。
感知器学习算法的对偶形式描述如下：
感知器模型：
\[\begin{aligned} f(\boldsymbol{x}) & = sign(\boldsymbol{w} \cdot \boldsymbol{x} + b) \\ & = sign \left(\langle \boldsymbol{w}, \boldsymbol{x} \rangle + b \right) \\ & = sign \left( \left \langle \sum_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \\ & = sign \left(\sum_{i=1}^{N} \alpha_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x} \rangle + b \right) \\ \end{aligned}\]
输入：线性可分的训练数据集 \(T= \{(\boldsymbol{x_1}, y_1), (\boldsymbol{x_2}, y_2), \cdots, (\boldsymbol{x_N}, y_N)\}\) ，其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{+1, -1\}, \; i = 1,2, \cdots, N\) ，学习率 \(\mu (0< \mu \le 1)\)
输出：感知器模型参数 \(\boldsymbol{\alpha} = (\alpha_1, \alpha_2, \cdots, \alpha_N)^{\mathsf{T}} ,b\)
\(\boldsymbol{\alpha},b\) 的求解过程如下：
(1) \(\boldsymbol{\alpha} = (\alpha_1, \alpha_2, \cdots, \alpha_N)^{\mathsf{T}} \leftarrow (0,0,\cdots,0)^{\mathsf{T}} ,b \leftarrow 0\)
(2) 在训练数据集中选取数据 \((\boldsymbol{x_i}, y_i)\)
(3) 如果 \(y_i(\sum_{j=1}^{N} \alpha_j y_j \langle \boldsymbol{x_j}, \boldsymbol{x_i} \rangle + b) \le 0\) （即它是一个错误分类点），则按下面方法更新 \(\alpha_i,b\) ：
\[\begin{cases} \alpha_i \leftarrow \alpha_i + \mu \\ b \leftarrow b + \mu y_i \end{cases}\]
(4) 转至(2)，直到没有错误分类点。

感知器算法的对偶形式中，训练数据仅以“内积”的形式（即 \(\langle \boldsymbol{x_j}, \boldsymbol{x_i} \rangle\) ）出现。 利用这个特点我们可以把 Kernel Method 应用到感知器（本文不介绍）。

为了方便使用感知器算法的对偶形式，我们可以提前把训练数据集中所以训练数据间的“内积”计算出来。这个矩阵就是格拉姆矩阵(Gram Matrix)。

对于 \(n\) 个向量 \(\boldsymbol{x_1}, \boldsymbol{x_2}, \cdots, \boldsymbol{x_n}\), 它对应的 Gram Matrix 定义为：
\[\mathbf{G} = \left( \begin{array}{cccc} \langle \boldsymbol{x_1}, \boldsymbol{x_1} \rangle & \langle \boldsymbol{x_1}, \boldsymbol{x_2} \rangle & \cdots & \langle \boldsymbol{x_1}, \boldsymbol{x_n} \rangle \\ \langle \boldsymbol{x_2}, \boldsymbol{x_1} \rangle & \langle \boldsymbol{x_2}, \boldsymbol{x_2} \rangle & \cdots & \langle \boldsymbol{x_2}, \boldsymbol{x_n} \rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle \boldsymbol{x_n}, \boldsymbol{x_1} \rangle & \langle \boldsymbol{x_n}, \boldsymbol{x_2} \rangle & \cdots & \langle \boldsymbol{x_n}, \boldsymbol{x_n} \rangle \\ \end{array} \right)\]

显然，Gram Matrix 是一个对称矩阵（因为 \(\langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle = \langle \boldsymbol{x_j}, \boldsymbol{x_i} \rangle\) ）。

实例（这个例子的数据集和前面介绍感知器算法原始形式时的例子是相同的）：假设训练数据集有两个正实例点（应该分到+1 类的点）A、B分别为： \(\boldsymbol{x_1} = (3,3)^\mathsf{T}, \boldsymbol{x_2} = (4,3)^\mathsf{T}\) ，和一个负实例点（应该分到-1 类的点）C为： \(\boldsymbol{x_3} = (1,1)^\mathsf{T}\) ，利用感知器学习算法的对偶形式求感知器模型。
解：
(1) 取 \(\alpha_1 = \alpha_2 = \alpha_3 = 0, b = 0, \mu = 1\)
(2) 计算数据集对应的 Gram 矩阵：
\[\mathbf{G} = \left( \begin{array}{ccc} 18 & 21 & 6 \\ 21 & 25 & 7 \\ 6 & 7 & 2 \\ \end{array} \right)\]
(3) 随机选择一个点 \(\boldsymbol{x_i}\) ，判断 \(y_i(\sum_{j=1}^{3} \alpha_j y_j \langle \boldsymbol{x_j}, \boldsymbol{x_i} \rangle + b) \le 0\) 是否成立，如果成立（说明它是一个错误分类点），则按下面方法更新 \(\alpha_i,b\) ：
\[\begin{cases} \alpha_i \leftarrow \alpha_i + 1 \\ b \leftarrow b + y_i \end{cases}\]
反复迭代，直到没有错误分类点。具体迭代过程（共迭代了 7 次）如表 2 所示。

(4) 由计算出来的 \(\alpha_1=2, \alpha_2=0, \alpha_3=5, b=-3\) ，可得 \(\boldsymbol{w} = \sum_{i=1}^{3} \alpha_i y_i \boldsymbol{x_i} = 2 \boldsymbol{x_1} + 0 \boldsymbol{x_2} - 5 \boldsymbol{x_3} = (1,1)^\mathsf{T}\) ，从而感知器为：
\[f(\boldsymbol{x}) = sign \left( x^{(1)} + x^{(2)} - 3 \right)\]