SVM软间隔对偶问题推导

支持向量机(SVM)最初设计的是为了找到一个最大化分类边界的线性模型，但是通过引入软间隔（也称为松弛变量），SVM可以处理数据集中的噪声和非线性的决策边界。硬间隔SVM的目标是最小化支持向量到超平面的距离，而软间隔SVM则允许一些样本稍微偏离这个边界。

软间隔对偶问题是这样的：
给定训练数据 \( \mathcal{D} = \{(x_1, y_1), ..., (x_m, y_m)\} \)，其中 \( x_i \in \mathbb{R}^n \) 是特征向量，\( y_i \) 是对应的类别标签（+1 或 -1），目标函数加上Lagrange乘子项可以表示为：

\[
\min_{w, b, \xi} \frac{1}{2} w^\top w + C \sum_{i=1}^{m} \xi_i
\]

其中 \( w \) 是权重向量，\( b \) 是偏置项，\( \xi_i \) 是松弛变量，表示第 \( i \) 个样本点能否完全被正确分类（如果 \( y_i(w^\top x_i + b) > 1 \)，则 \( \xi_i = 0 \)；若未满足，\( 0 \leq \xi_i \leq C \)）。\( C \) 是惩罚系数，控制了错误容忍度。

对偶问题通过拉格朗日乘数法构造，将原始优化问题转换为求解一组拉格朗日乘数 \( \alpha_i \) 的最大值（\( \alpha_i \geq 0 \)），同时满足KKT条件：

\[
y_i(w^\top x_i + b) - 1 = \xi_i, \quad \text{for } i = 1, ..., m
\]
\[
0 \leq \alpha_i \leq C, \quad \sum_{i=1}^{m} \alpha_i y_i = 0
\]
\[
\alpha_i \xi_i = 0, \quad \text{for all } i
\]

通过对偶问题求解，得到最优的 \( w \) 和 \( b \) 可以用于预测新的数据点。