感知机对偶形式推导

### 关于感知机对偶形式的推导 感知机是一种经典的线性分类模型，其目标是通过训练找到能够将数据集分开的超平面。对于感知机的学习算法，除了常见的原始形式外，还存在一种称为 **对偶形式** 的表达方式[^3]。 #### 原始形式回顾 在感知机的原始形式中，我们试图最小化一个基于误分类样本定义的目标函数 \(L(w, b)\)，其中权重向量 \(w\) 和偏置项 \(b\) 是待优化参数。具体来说，给定一组训练样例 \((x_i, y_i)\)，其中 \(y_i \in \{-1, +1\}\)，感知机希望满足条件： \[ y_i (w^\top x_i + b) > 0 \] 如果某个样例被错误分类，则更新规则如下： \[ w \leftarrow w + \eta y_i x_i \] \[ b \leftarrow b + \eta y_i \] 这里，\(\eta\) 表示学习率[^1]。 --- #### 对偶形式的核心思想 为了更好地理解感知机的对偶形式，我们需要引入一些关键概念。假设最终学到的权重向量可以表示为训练样本的线性组合： \[ w = \sum_{i=1}^{N} \alpha_i y_i x_i \] 这里的系数 \(\alpha_i\) 非零仅当对应的样本参与过权值调整过程（即该样本曾被误分类）。因此，在对偶形式下，我们的目标变为寻找这些系数 \(\alpha_i\) 而不是直接操作 \(w\) 和 \(b\)。 通过对上述关系代入到决策边界方程中，我们可以得到一个新的判定准则： \[ f(x) = sign\left( \sum_{i=1}^N \alpha_i y_i K(x_i, x) + b \right) \] 在这里，\(K(x_i, x_j) = x_i^\top x_j\) 称作核函数。尽管当前讨论的是线性情况下的内积运算，但在更复杂的场景中可以通过替换不同的核函数扩展至非线性问题[^2]。 --- #### 数学推导细节 以下是具体的数学推导步骤摘要： 1. 将损失函数重写为目标变量 \(w\) 及约束条件； 设计一个合适的凸二次规划问题并加入松弛因子处理不可分情形； 2. 应用拉格朗日乘数法构建增广后的目标函数，并考虑不等式约束的影响转换成标准形式； 3. 利用 KKT 条件消去显式的依赖于 \(w\) 参数的部分，从而获得只涉及 \(\alpha_i\) 的最优化子问题； 4. 解决这个简化版本的最大化任务即可恢复原来的分离面信息。 注意整个过程中涉及到大量矩阵运算技巧以及如何有效存储访问历史交互记录等问题都需要额外关注效率方面的考量[^4]。 --- ```python import numpy as np class PerceptronDual: def __init__(self, learning_rate=1e-3, max_iter=100): self.learning_rate = learning_rate self.max_iter = max_iter def fit(self, X, Y): n_samples, _ = X.shape # 初始化 alpha 和 bias self.alpha = np.zeros(n_samples) self.bias = 0. gram_matrix = np.dot(X, X.T) for t in range(self.max_iter): errors = False for i in range(n_samples): update = Y[i]*(np.sum(self.alpha * Y * gram_matrix[:, i]) + self.bias) if update <= 0: self.alpha[i] += self.learning_rate self.bias += self.learning_rate * Y[i] errors = True if not errors: break def predict(self, X_test): result = [] for xi in X_test: prediction = np.sign(np.sum([a*y*K(xi,x)+self.bias for a,y,K in zip(self.alpha,Y,X)])) result.append(prediction) return np.array(result) ``` ---