[ML Notes] SVM：非线性模型

Author: nex3z 2021-03-14

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

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

f(x)=wTϕ(x)+b

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

其对偶问题为

\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）。