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