机器学习——期末复习（上）

SVM支持向量机

作业

1

关于核化软间隔支持向量机，推导目标函数的原始问题转换为对偶问题的过程、KKT条件、预测函数。

原始问题

软间隔SVM的目标函数为：

$$\min_{\mathbf{w}, b, \xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i$$

约束条件：

$$y_i (\mathbf{w}^T \phi(\mathbf{x}_i) + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad i=1,\dots,n$$

其中 $C>0$ 是惩罚参数，$\xi_i$ 是松弛变量，$\phi(\cdot)$ 是特征映射。

转化为对偶问题

1. 构造拉格朗日函数：

   $$\mathcal{L}(\mathbf{w}, b, \xi, \boldsymbol{\alpha}, \boldsymbol{\beta}) = \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i - \sum_{i=1}^n \alpha_i \left[y_i (\mathbf{w}^T \phi(\mathbf{x}_i) + b) - 1 + \xi_i\right] - \sum_{i=1}^n \beta_i \xi_i$$

   其中 $\alpha_i \geq 0, \beta_i \geq 0$ 是拉格朗日乘子。

2. 对原始变量求偏导并令其为零：

• 对 $\mathbf{w}$ 求导： $$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^n \alpha_i y_i \phi(\mathbf{x}_i) = 0 \quad \Rightarrow \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \phi(\mathbf{x}_i)$$
• 对 $b$ 求导： $$\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^n \alpha_i y_i = 0 \quad \Rightarrow \sum_{i=1}^n \alpha_i y_i = 0$$
• 对 $\xi_i$ 求导： $$\frac{\partial \mathcal{L}}{\partial \xi_i} = C - \alpha_i - \beta_i = 0 \quad \Rightarrow \beta_i = C - \alpha_i$$

1. 代入拉格朗日函数消去原始变量：
   将 $\mathbf{w}$ 和 $\beta_i$ 代入 $\mathcal{L}$，得到对偶目标函数：

   $$\max_{\boldsymbol{\alpha}} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)$$

   约束条件：

   $$0 \leq \alpha_i \leq C, \quad \sum_{i=1}^n \alpha_i y_i = 0$$

2. 引入核函数：
   用核函数 $K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)$ 替换内积，得到最终对偶问题：

   $$\max_{\boldsymbol{\alpha}} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(\mathbf{x}_i, \mathbf{x}_j)$$

   约束条件不变。

KKT条件

• 原始可行性：$y_i (\mathbf{w}^T \phi(\mathbf{x}_i) + b) \geq 1 - \xi_i, \quad \xi_i \geq 0$
• 对偶可行性：$\alpha_i \geq 0, \quad \beta_i = C - \alpha_i \geq 0$
• 互补松弛性：$\alpha_i [y_i (\mathbf{w}^T \phi(\mathbf{x}_i) + b) - 1 + \xi_i] = 0, \quad \beta_i \xi_i = 0$
• 梯度为零条件：已通过偏导数消去原始变量。

预测函数

测试样本 $\mathbf{x}$ 的预测函数为：

$$f(\mathbf{x}) = \text{sign} \left( \sum_{i=1}^n \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \right)$$

其中 $b$ 可通过任一支持向量（满足 $0 < \alpha_i < C$）计算：

$$b = y_i - \sum_{j=1}^n \alpha_j y_j K(\mathbf{x}_j, \mathbf{x}_i)$$

2