[ML Notes] SVM:非线性模型

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

  假设将样本 $\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)。