[ML Notes] SVM：非线性模型

Author: nex3z 2020-08-31

  前文假设样本是线性可分的。如果在原始样本空间内，不能存在能够正确划分两类样本的超平面，则可以将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

  假设将样本 $\boldsymbol{x}$ 映射到特征空间后，得到的特征向量为 $\phi(\boldsymbol{x})$，则在特征空间中的划分超平面对应的模型为

$$f(\boldsymbol{x}) = \boldsymbol{w}^\mathrm{T} \phi(\boldsymbol{x}) + b \tag{1}$$

其中 $\boldsymbol{w}$ 和 $b$ 为参数。类似于线性 SVM，此时的优化问题可以表述为

$$\begin{aligned} \min_{\boldsymbol w, b} \; & \frac{1}{2} ||\boldsymbol w||^2 \\ \mathrm{s.t.} \; & y_i \big(\boldsymbol w^\mathrm{T} \phi(\boldsymbol x) + b \big) \geq 1, \; i = 1, 2, \dots, m \end{aligned} \tag{2}$$

其对偶问题为

$$\begin{aligned} \max_{\boldsymbol \alpha} \; & \sum_{i=1}^m \alpha_i – \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi(\boldsymbol x_i)^\mathrm{T} \phi(\boldsymbol x_j) \\ \mathrm{s.t.} \; & \sum_{i=1}^m \alpha_i y_i = 0, \\ & \alpha_i \geq 0, \;\; i = 1, 2, \dots, m. \end{aligned} \tag{3}$$

  $\phi(\boldsymbol x_i)$ 位于高维的特征空间，式 $(3)$ 中的内积 $\phi(\boldsymbol x_i)^\mathrm{T} \phi(\boldsymbol x_j)$ 的计算量会非常大。为了避免这个计算，可以通过核函数 $\mathcal{K}(\cdot, \cdot)$ 将原始样本空间的内积转换为特征空间的内积，即

$$\mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) = \langle \phi(\boldsymbol x_i), \phi(\boldsymbol x_j) \rangle = \phi(\boldsymbol x_i)^\mathrm{T} \phi(\boldsymbol x_j)\tag{4}$$

此时式 $(3)$ 可以写为

$$\begin{aligned} \max_{\boldsymbol \alpha} \; & \sum_{i=1}^m \alpha_i – \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \mathcal{K}(\boldsymbol x_i, \boldsymbol x_j) \\ \mathrm{s.t.} \; & \sum_{i=1}^m \alpha_i y_i = 0, \\ & \alpha_i \geq 0, \;\; i = 1, 2, \dots, m. \end{aligned} \tag{5}$$

  求解上面的优化问题，得到模型

$$\begin{aligned} f(\boldsymbol x) &= \boldsymbol w^\mathrm{T} \phi(\boldsymbol x) + b \\ &= \sum_{i=1}^m \alpha_i y_i \phi(\boldsymbol x_i)^\mathrm{T} \phi(\boldsymbol x) + b \\ &= \sum_{i=1}^m \alpha_i y_i \mathcal{K}(\boldsymbol x, \boldsymbol x_i) + b \end{aligned} \tag{6}$$

称为支持向量展式（support vector expansion）。