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

发表于 更新于 分类于 ， 阅读次数：

SVM支持向量机

作业

1

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

原始问题

软间隔SVM的目标函数为： $$ \min_{\mathbf{w}, b, \xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i $$ 约束条件： yi(wTϕ(xi) + b) ≥ 1 − ξi,  ξi ≥ 0,  i = 1, …, n 其中 C > 0 是惩罚参数，ξi 是松弛变量，ϕ(⋅) 是特征映射。

转化为对偶问题

  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 $$ 其中 αi ≥ 0, βi ≥ 0 是拉格朗日乘子。

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

  • 对 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 $$
  • 对 ξi 求导： $$ \frac{\partial \mathcal{L}}{\partial \xi_i} = C - \alpha_i - \beta_i = 0 \quad \Rightarrow \beta_i = C - \alpha_i $$

  1. 代入拉格朗日函数消去原始变量： 将 w 和 βi 代入 ℒ，得到对偶目标函数： $$ \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(xi, xj) = ϕ(xi)Tϕ(xj) 替换内积，得到最终对偶问题： $$ \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条件

  • 原始可行性：yi(wTϕ(xi) + b) ≥ 1 − ξi,  ξi ≥ 0
  • 对偶可行性：αi ≥ 0,  βi = C − αi ≥ 0
  • 互补松弛性：αi[yi(wTϕ(xi) + b) − 1 + ξi] = 0,  βiξi = 0
  • 梯度为零条件：已通过偏导数消去原始变量。

预测函数

测试样本 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 < αi < C）计算： $$ b = y_i - \sum_{j=1}^n \alpha_j y_j K(\mathbf{x}_j, \mathbf{x}_i) $$

2