支持向量机

Support Vector Machines SVM
监督学习，对数据进行二元分类的广义线性分类器，最大化决策超平面和训练集中的样本间的边界的算法
算法思想：找到集合边缘上的若干数据（支持向量），用这些点找出一个平面（决策超平面），使得支持向量到该平面的距离最大。

基本概述

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

线性可分 SVM

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

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

线性不可分 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 (-{\displaystyle \frac{x_i-x_j}{2{\gamma }^2}})$，高斯核函数需要调参

拉格朗日乘数法

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

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

根据约束条件构造拉格朗日函数，约束条件有几个，就设置几个拉格朗日乘子，约束条件和拉格朗日的各个一阶偏导联立，求得可能的极值

目标函数： $u=f(x,y,z,t)$ 约束条件：$\{\begin{array}{l}\phi (x,y,z,t)=0\\ \psi (x,y,z,t)=0\end{array}$
构造拉格朗日函数：