机器学习13——支持向量机下

支持向量机下

非线性支持向量机（Non-linear SVMs）详解

核心思想

当数据在原始空间线性不可分时，通过**核技巧（Kernel Trick）**将数据映射到高维特征空间，使其在该空间中线性可分。

比如以下的样本在一维空间不可分，但是映射到二维空间变得线性可分：

关键步骤

• 特征映射（Feature Mapping）
  定义映射函数 $\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^D$（$D\gg d$），将原始特征 $\mathbf{x}$ 映射到高维空间 $\varphi (\mathbf{x})$。

• 映射后，分类器函数变成了：
  $$g(x)=w^T\varphi (x)+b=\sum _{x_i\in SV}{\lambda }_i{y}_i\varphi \left(x_i\right)\varphi (x)+b$$

• 但是我们其实并不需要找到这个映射函数，然后将样本映射到高维空间后做内积！！我们可以用一个Kernel Trick：

  • 核函数（Kernel Function）
    直接计算高维空间的内积，避免显式映射。也就是我们可以在样本空间（原空间维度）下计算高维下样本的内积结果：
    $$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$$

  • 示例：

    • 一个二维空间样本：$\mathrm{x}=\left[\begin{array}{ll}{x}_1& x_2\end{array}\right];$

    • 让核函数$K\left({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{j}}\right)={\left(1+{\mathrm{x}}_{\mathrm{i}}^{\mathrm{T}}{\mathrm{x}}_{\mathrm{j}}\right)}^2$,即$K\left({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{j}}\right)=\phi {\left({\mathrm{x}}_{\mathrm{i}}\right)}^{\mathrm{T}}\phi \left({\mathrm{x}}_{\mathrm{j}}\right)$

    • 我们有：
      $$\begin{array}{rl}K\left(X_i,X_j\right)& ={\left(1+X_i^{\top }{X}_j\right)}^2\\ & =1+X_{i1}^2{X}_{j1}^2+2X_{i1}{X}_{j1}{X}_{i2}{X}_{j2}+X_{i2}^2{X}_{j2}^2+2X_{i1}{X}_{j1}+2X_{i2}{X}_{j2}\\ & =\left[\begin{array}{llllcc}1& X_{i1}^2& \sqrt{2}{X}_{i1}{X}_{i2}& X_{i2}^2& \sqrt{2}{X}_{i1}& \sqrt{2}{X}_{i2}\end{array}\right]{\left[\begin{array}{llllcc}1& X_{j1}^2& \sqrt{2}{X}_{j1}{X}_{j2}& X_{j2}^2& \sqrt{2}{X}_{j1}& \sqrt{2}{X}_{j2}\end{array}\right]}^{\top }\\ & =\phi {\left(X_i\right)}^{\top }\phi \left(X_j\right),\text{where }\phi (X)={\left[\begin{array}{llllll}1& X_1^2& \sqrt{2}{X}_1{X}_2& X_2^2& \sqrt{2}{X}_1& \sqrt{2}{X}_2\end{array}\right]}^{\top }\end{array}$$

  • 常用核函数：

    • 线性核：$K({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i^T{\mathbf{x}}_j$
    • 多项式核：$K({\mathbf{x}}_i,{\mathbf{x}}_j)=(1+{\mathbf{x}}_i^T{\mathbf{x}}_j{)}^p$
    • 高斯核（RBF）：$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp \left(-\frac{\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2}{2{\sigma }^2}\right)$
    • Sigmoid核：$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\tanh ({\beta }_0{\mathbf{x}}_i^T{\mathbf{x}}_j+{\beta }_1)$

• 对偶问题优化
  使用核函数替换内积，对偶问题变为：
  $$\begin{array}{rl}\underset{\lambda }{\max }& \sum _{i=1}^n{\lambda }_i-\frac{1}{2}\sum _{i,j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)\\ \text{s.t.}& 0\le {\lambda }_i\le C,\sum _{i=1}^n{\lambda }_i{y}_i=0\end{array}$$
  求解后得到判别函数：
  $$g(\mathbf{x})=\sum _{{\mathbf{x}}_i\in SV}{\lambda }_i{y}_{i}K(\mathbf{x},{\mathbf{x}}_i)+b$$
  其中偏移项 $b$ 通过支持向量计算：
  $$b=y_k-\sum _{{\mathbf{x}}_i\in SV}{\lambda }_i{y}_{i}K({\mathbf{x}}_i,{\mathbf{x}}_k),0<{\lambda }_k<C$$

• 算法流程：

  1. 选择核函数
  2. 选择一个C的值
  3. 求解二次规划问题，得到 ${\lambda }_i$ 和 $b$。
  4. 从支持向量构造分类函数

Other issues（使用 SVM 时需要注意的问题）

1. Choice of kernel（核函数的选择）

• 在 SVM 中，核函数（kernel function）是关键，它定义了如何将数据从输入空间映射到高维特征空间。
• 常见的默认核函数是：
  • 高斯核（Gaussian kernel / RBF kernel）
  • 多项式核（Polynomial kernel）
• 这些核函数在很多通用任务上效果不错，但：
  • 如果效果不佳，就需要更复杂的核函数（例如：字符串核、图核、语义核等），这时候可以结合具体任务设计。

2. Domain experts can help formulate appropriate similarity measures

• 专业领域的知识可以帮助设计适合该任务的相似性度量方式，也就是定制核函数；
• 例如在生物信息学、图像识别等任务中，专家可以帮助构建更合适的核函数结构。

3. Choice of kernel parameters（核函数参数的选择）

• 以高斯核为例，其形式是：
  $$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$$
  其中：

  • $\sigma$ 控制核的“宽度”，即数据点之间多远才被认为是“相似”的。
  • 有经验规则认为：$\sigma$ 可设为“类别不同的最近样本点之间的距离”。

• 在缺乏理论依据时，常用：

  • 验证集（validation set）
  • 交叉验证（cross-validation）
    来选择最优参数。

4. Optimization criterion - Hard margin vs. Soft margin（优化标准）

• Hard margin SVM：
  • 要求所有样本完全分开（间隔大，零误差），适用于数据线性可分的情况；
• Soft margin SVM：
  • 允许一定的分类错误，引入松弛变量，更适用于现实世界中不可分的数据；
• 实际应用中常常需要：
  • 通过大量试验调整不同参数来选择最优设置，比如 C 值（正则化参数）、核函数和其参数等。

Comparison with Neural Networks（与神经网络的比较）