支持向量机 SVM – 周志华教授永垂不朽

  • 从线性分类器说起

    • 线性分类就是从样本空间中找到一个超平面将不同类的样本放到不同的子空间部分

    • 超平面的可能性：我们要找鲁棒性最好的、泛化能力最强的

      • 超平面公式 ωTx+b=0\omega^Tx + b = 0

        • 推导过程: ω\omega 是超平面的法向量，可以决定超平面的朝向问题
        • xx 是超平面内的任意向量，出发点是 (x0,y0,⋯ ,t0)(x_0,y_0,\cdots,t_0), 终点 (x,y,⋯ ,t)(x,y,\cdots,t) 那么有向量表述法 x=(x−x0,⋯ ,t−t0)x = (x-x_0,\cdots,t-t_0)
        • 通过垂直知点乘 ω⋅x=0\omega\cdot x = 0 所以 ω⋅(x,⋯ ,t)=ω⋅(x0,⋯ ,t0)\omega\cdot (x,\cdots,t)=\omega\cdot(x_0,\cdots,t_0) 等式右边是常数，我们写作 −b-b
        • 整体等式写成矩阵形式 ωTx+b=0\omega^T x + b = 0
        • 点到超平面距离 ∣∣ωTx+b∣∣∣∣w∣∣\frac{||\omega^Tx+b||}{||w||}

    • 什么是支持向量：定义了分类平面方向的向量就是支持向量

    • 最大间隔 max_margin γ=∣ωTx+b∣∣∣w∣∣\gamma = \frac{|\omega^T x + b|}{||w||}

      • 思路 arg max⁡2∣∣w∣∣\argmax\frac{2}{||w||} (假设所有点都在 ωTx+b=±1\omega^T x+b = \pm 1 的外侧)

      • 变成 arg min⁡∣∣w∣∣22\argmin\frac {||w||^2} 2 (为了好算)

        • 怎么想呢？我们需要在 已知 ωTx+b=±1\omega^T x + b =\pm1 曲线的外侧，我们需要求的是一个 linear form 的极值点，那么我们就会想到拉格朗日乘子法

        • 定义 yi={1,ωT⋅xi+b≥1−1,ωT⋅xi+b≤1y_i = \begin{cases}1&,& \omega^T \cdot x_i + b \ge 1\\-1&, &\omega^T\cdot x_i + b \le 1\end{cases} 这里 xix_i 表示训练样本，是一个向量

          • 这样上述情况就可以合并写作一个公式： yi(ωT⋅xi+b)≥1y_i(\omega^T \cdot x_i +b) \ge 1 表示在外面

      • 令 f(ω)=∣∣w∣∣22,g(ω)=ωTx+b−1f(\omega) = \frac{||w||^2}{2}, g(\omega) = \omega^Tx+b - 1, 我们有 L=f+λ⃗gL = f + \vec\lambda g 函数，在极值点处取到导数 0

        • L(ω,b,λ)=12∣∣w∣∣2+Σiλi(1−yi(ωTxi+b))L(\omega,b,\lambda) = \frac 1 2||w||^2+\Sigma_i \lambda_i(1-y_i(\omega^Tx_i + b))

      • 对 ω,b\omega,b 求偏导为 0 得到 ω−Σiλiyixi=0;  Σiλiyi=0\omega - \Sigma_i \lambda_i y_i x_i =0;\ \ \Sigma_i \lambda_i y_i = 0

        • 简单理解就是 ∇f+λ∇g=0\nabla f + \lambda \nabla g = 0

  • 无法分类的情况——特征空间映射

    • 对于某种线性不可分的模型，我们加多维度，可能就是线性可分的了
      • 就比如通过已有的数据调查无法分类，我们找到新的分类依据就可以实现分割了
      • 如果原始空间是有限维，那么一定存在一个高维（可能是无限维）特征空间使样本线性可分
    • 公式解释
      • 将样本映射到新空间之后得到的向量是 ϕ(x)\phi(x) , 那么我们就是找新的空间最优解
    • 核函数 kernel function
      • κ(xi,xj)=ϕ(xi)Tϕ(xj)\kappa(x_i,x_j) = \phi (x_i)^T\phi(x_j)
      • Mercer 定理：如果一个对称函数的核矩阵半正定，则它就能作为核函数来使用
        • 什么是核矩阵：ker⁡A={x∣Ax=0,x∈Rn}\ker A = \{x|Ax = 0, x\in \R^n\}
        • 半正定：对于一个矩阵 AA 满足任意向量 xx 使得 xTAx≥0x^T A x \ge 0 （正定是 >0>0）
      • 任何核函数都隐式定义了一个 RKHS 再生核希尔伯特空间
        • 也就是指被核函数映射到了之后的空间
      • 对于最优核函数的选择，就是svm的关键，其中我们有 κ∗∈{κ1,⋯ ,κ∞}\kappa^*\in \{\kappa_1,\cdots,\kappa^\infty\}

  • 软间隔

    • 现实中很难确定合适的核函数，是训练样本在特征空间中线性可分，即使线性可分，也有可能是过拟合导致的

    • 因此引入软间隔 Soft Margin 允许在一定样本上不满足约束（也就是不考虑噪声的存在）

      • 事实上就是让不满足约束的样本尽可能少

      • min⁡ω,b12∣∣w∣∣2+CΣl0/1(yi(wTxi+b)−1)\min_{\omega,b} \frac 1 2 ||w||^2 + C\Sigma l_{0/1}(y_i(w^Tx_i+b)-1)

        • 后面的 yi(wT+b)≥1y_i(w^T+b)\ge 1 表示不满足约束

  • 实操

    • ϵ−\epsilon-不敏感损失函数

      • 其对于一般的线性回归问题，不考虑回归函数 f(x)±ϵf(x)\pm \epsilon 范围内不计入 MSE 损失中