Perceptron(感知器)
感知机是一种线性分类器，用于二分类问题。它的基本思想是找到一个线性超平面将数据集中的不同类别分开。感知机算法的目标是通过迭代更新权重向量，使其能够正确分类所有训练样本。
感知机的定义
对于给定的训练样本 $(x_i, y_i)$，其中 $x_i$ 是输入特征向量，$y_i$ 是对应的标签，取值为 $1$ 或 $-1$。感知机的决策函数为：
\[f(x) = \text{sign}(w \cdot x + b)\]其中，$w$ 是权重向量，$b$ 是偏置项。感知机的学习规则是根据误分类样本来更新权重和偏置：
- 如果样本被正确分类，则不更新。
- 如果样本被误分类，则更新规则为： \(w_{k+1} = w_k + yx\)
更新规则推导
我们需要证明每次更新都会使权重向量 $w$ 更接近理想的分隔向量 $w^*$。具体来说，我们需要证明：
\[\| w_{k+1} - \alpha w^* \|^2 < \| w_k - \alpha w^* \|^2\]步骤 1: 更新后的权重向量展开
将更新规则代入目标不等式：
\[\| w_k + yx - \alpha w^* \|^2 < \| w_k - \alpha w^* \|^2\]步骤 2: 使用范数展开公式
展开左侧的范数：
\[\| w_k + yx - \alpha w^* \|^2 = \| (w_k - \alpha w^*) + yx \|^2\]应用二次范数展开公式 $| a + b |_2^2 = | a |_2^2 + 2a^Tb + | b |_2^2$，我们得到：
\[\| (w_k - \alpha w^*) + yx \|^2 = \| w_k - \alpha w^* \|^2 + 2((w_k - \alpha w^*)^T yx) + \| yx \|^2\]将其带入到不等式中，得：
\[\| w_k + yx - \alpha w^* \|^2 = \| w_k - \alpha w^* \|^2 + 2y(w_k - \alpha w^*)^T x + \| x \|^2\]步骤 3: 解释每一项
-
当前误差平方： \(\| w_k - \alpha w^* \|^2\)
-
交叉项： \(2y(w_k - \alpha w^*)^T x\)
-
新样本的影响： \(\| yx \|^2 = y^2 \| x \|^2 = \| x \|^2\)
将这些项代入我们需要证明的不等式：
\[\| w_k + yx - \alpha w^* \|^2 = \| w_k - \alpha w^* \|^2 + 2y(w_k - \alpha w^*)^T x + \| x \|^2\]步骤 4: 考虑交叉项的符号
由于 $x$ 被误分类，所以 $y(w_k \cdot x) < 0$，因此：
\[2y(w_k - \alpha w^*)^T x\]是负值（或最小为零）。
步骤 5: 调整不等式
考虑到每次更新时 $2y(w_k - \alpha w^*)^T x$ 项的影响，使其更贴近现实情况。假设 $| x |_2^2$ 的最大值为 $\beta^2$，且 $2yw^T x$ 的最小值为 $\gamma$，我们设置 $\alpha = \frac{\beta^2}{\gamma}$。
步骤 6: 更新后的不等式
代入后，我们得到：
\[\| w_{k+1} - \alpha w^* \|_2^2 < \| w_k - \alpha w^* \|_2^2 - \beta^2\]收敛前的更新次数限制
为了计算感知机收敛前的更新次数上限，我们需要考虑每次更新对误差的减小量。根据之前的推导，我们知道每次更新的误差减少至少为 $\beta^2$。
初始误差为 $| w_0 - \alpha w^* |^2$，总误差减少为：
\[\| w_{k+1} - \alpha w^* \|_2^2 \leq \| w_k - \alpha w^* \|_2^2 - \beta^2\]为了达到收敛，更新次数 $M$ 必须满足：
\[M \leq \frac{\| w_0 - \alpha w^* \|^2}{\beta^2}\]结论
通过引入比例因子 $\alpha$ 并合理选择，使得每次更新都减少了权重向量与理想向量之间的距离，证明了每次更新都会使 $w$ 更接近 $w^*$。因此，感知机算法在有限步内收敛，并且收敛前的更新次数限制为：
\[M \leq \frac{\| w_0 - \alpha w^* \|^2}{\beta^2}\]这意味着每次更新 $w$ 时，都会使其更接近 $w^*$，即每次更新都在减少误分类率，逐步改善模型的分类性能。
Leave a comment