支持向量机

Support Vector Machines SVM
监督学习，对数据进行二元分类的广义线性分类器，最大化决策超平面和训练集中的样本间的边界的算法

算法思想：找到集合边缘上的若干数据（支持向量），用这些点找出一个平面（决策超平面），使得支持向量到该平面的距离最大。

基本概述

假如数据是完全的线性可分的，那么学习到的模型可以称为硬间隔支持向量机。（硬间隔：完全分类准确，不能存在分类错误的情况；软间隔：允许一定量的样本分类错误。）

线性可分 SVM

任意超平面可表示为：$w^{T}x+b=0$, 点 $x=(x_1,x_2,\cdots ,x_n)$ 到超平面的距离为：$\frac{\left|w^{T}x+b\right|}{\left|\left|w\right|\right|}\left|\left|w\right|\right|=\sqrt{w_1^2+\cdots +w_n^2}$ 支持向量机的最终目的：最大化支持向量到超平面的距离 $d$ ，则 $\{\begin{array}{l}\frac{\left|w^{T}x+b\right|}{\left|\left|w\right|\right|}\ge dy=1\\ \frac{\left|w^{T}x+b\right|}{\left|\left|w\right|\right|}\le dy=-1\end{array}$

函数间隔：$d^{\ast }=y_i(w^T{x}_i+b)$ 几何间隔：$d=\frac{\left|w^{T}x+b\right|}{\left|\left|w\right|\right|}$， 当数据被正确分类时，几何间隔就是点到超平面的距离 求几何间隔最大，SVM基本问题可以转化为求解：$max\frac{d^{\ast }}{\left|\left|w\right|\right|}\to max\frac{1}{\left|\left|w\right|\right|}\to \min \frac{1}{2}{\left|\left|w\right|\right|}^{2}s.t.y_i(w^T{x}_i+b)\ge 1$

线性可分情况: 对于线性可分的数据，SVM 寻找一个超平面，使得它到最近的训练数据点（这些点被称为支持向量 (Support Vectors)）的距离最大化。这个距离被称为间隔。

• 超平面方程：${\mathbf{w}}^T\mathbf{x}+b=0$
• 支持向量到超平面的距离为 $1/||\mathbf{w}||$。最大化间隔等价于最小化 $||\mathbf{w}|{|}^2$。
• 分类决策函数：$f(\mathbf{x})=\text{sgn}({\mathbf{w}}^T\mathbf{x}+b)$

线性不可分 SVM

核函数方法

核函数：它可以将样本从原始空间映射到一个更高维的特质空间中，使得样本在新的空间中线性可分。使用原来的推导来进行计算，用核函数来替换当中的内积

常用核函数：

• 线性核函数 $K(x_i,x_j)=x_i^T{x}_j$
• 多项式核函数 $K(x_i,x_j)=(x_i^T{x}_j{)}^d$
• 高斯核函数 $K(x_i,x_j)=\exp (-\frac{x_i-x_j}{2{\gamma }^2})$，高斯核函数需要调参

• 当数据在原始特征空间中线性不可分时，SVM 引入核技巧 (Kernel Trick)。
• 核技巧通过一个非线性映射函数 $\varphi (\mathbf{x})$ 将原始数据映射到更高维的特征空间，使得数据在该高维空间中变得线性可分。
• 常见的核函数包括：
  • 线性核 (Linear Kernel): $K({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i^T{\mathbf{x}}_j$
  • 多项式核 (Polynomial Kernel): $K({\mathbf{x}}_i,{\mathbf{x}}_j)=(\gamma {\mathbf{x}}_i^T{\mathbf{x}}_j+r{)}^d$
  • 径向基函数核 (Radial Basis Function Kernel, RBF Kernel): $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma ||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2)$
• 核技巧的巧妙之处在于，它避免了在高维空间中显式计算 $\varphi (\mathbf{x})$，而是直接计算核函数 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$，从而大大降低了计算复杂度。

软间隔

软间隔 (Soft Margin):

• 为了处理存在噪声或异常值的情况，以及允许一些数据点落在间隔内甚至超平面的错误一侧，SVM 引入了软间隔的概念。
• 通过引入松弛变量 (Slack Variables) ${\xi }_i\ge 0$ 和惩罚参数 $C$，允许一定程度的分类错误，同时最小化 $||\mathbf{w}|{|}^2$ 和错误分类的惩罚。

优化目标

SVM 的优化问题是一个凸二次规划问题，其目标是最小化以下函数：

${\min }_{\mathbf{w},b,\xi }\frac{1}{2}||\mathbf{w}|{|}^2+C{\sum }_{i=1}^m{\xi }_i$

受限于：

$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i$ ${\xi }_i\ge 0$

其中 $C$ 是惩罚参数，用于平衡最大化间隔和最小化分类错误。$C$ 值越大，对错误分类的惩罚越大，模型越倾向于过拟合；$C$ 值越小，模型越倾向于欠拟合。

拉格朗日乘数法

拉格朗日乘数法：不等式约束、等式约束、无约束 Lagrange multiplier method 适用于求解带有等式约束条件的优化问题

目标函数：$z=f(x,y)$ 约束条件：$\phi (x,y)=0$ 拉格朗日乘子：$\lambda =-\frac{f_x}{{\phi }_x}=-\frac{f_y}{{\phi }_y}$ 构造辅助函数：拉格朗日函数 $L(x,y)=f(x,y)+\lambda \phi (x,y)$ 拉格朗日函数的各个一阶偏导数与约束条件联立, 由此方程组求得 $x,y,\lambda$, 得到的 $(x,y)$ 是在约束条件下的可能的极值点

L_{x}(x,y)=f_{x}(x,y)+\lambda \varphi_{x}(x,y)=0 \\ L_{y}(x,y)=f_{y}(x,y)+\lambda \varphi_{y}(x,y)=0 \\ \varphi(x,y)=0 \end{cases}$$ 根据约束条件构造拉格朗日函数，约束条件有几个，就设置几个拉格朗日乘子，约束条件和拉格朗日的各个一阶偏导联立，求得**可能的极值** 目标函数： $u=f (x, y, z, t)$ 约束条件：$\begin{cases}\varphi (x, y, z, t)=0 \\\psi (x, y, z, t)=0\end{cases}$ 构造拉格朗日函数： $$\begin{align} L(x,y,z,t)=f (x, y, z, t)+\lambda \varphi(x,y,z,t)+\mu \psi(x,y,z,t) \end{align}$$ $$\begin{cases} L_{x}(x,y,z,t)=0 \\ L_{y}(x,y,z,t)=0 \\ L_{z}(x,y,z,t)=0 \\ L_{t}(x,y,z,t)=0 \\ \varphi(x,y,z,t)=0 \\ \psi(x,y,z,t)=0 \end{cases}$$