常规分类方法：SVM
文章目录
一、概述
在二维平面中分类正负，用一根直线即可，但是这个方式不能解决非线性情况下的分类问题，那如何解决这个问题呢？有两个思路：一个思路是化直线为弯曲的线，计算机很容易学习直线，不容易学习弯曲的线，这个方向未作深入研究；一个思路是将二维映射到高维（数学：核函数），然后寻找切平面进行分类。
二、SVM核心思想
2.1、最大间距
二维线性分类问题，如何找到一条最佳的直线恰好区分正负，且直线距离每个sample的距离最远？
== >问题转化为求直线斜率和截距。
==>转化为求直线的法向量
w
⃗
\vec{w}
w
。
2.1.1、寻找正负样本与法向量之间的关系，建立函数
==>if 样本向量
u
⃗
\vec{u}
u
点乘
w
⃗
\vec{w}
w
= 样本
u
⃗
\vec{u}
u
在
w
⃗
\vec{w}
w
的投影。该投影要大于人为设定的阈值C。then 为正样本。
==>则转化为：
u
⃗
\vec{u}
u
·
w
⃗
\vec{w}
w
>C
==>令C=-b，
u
⃗
\vec{u}
u
·
w
⃗
\vec{w}
w
+b>0，要寻找
w
⃗
\vec{w}
w
和b。
2.1.2、化简函数得到决策公式
==>正负样本两个公式，一个大于一个小于：
u
⃗
\vec{u}
u
·
w
⃗
\vec{w}
w
+b>1，
u
⃗
\vec{u}
u
·
w
⃗
\vec{w}
w
+b<-1，这里使用一个技巧，令一个参数y，当为正样本，y=1，否则为-1。y(
u
⃗
\vec{u}
u
·
w
⃗
\vec{w}
w
+b)-1>=0。
==>寻找路的两边：当
y
i
(
u
⃗
y_i(\vec{u}
yi(u
·
w
⃗
\vec{w}
w
+b)-1=0时，就是恰好经过正负样本的两根线A、B。
2.2、寻找最大间距
== >寻找最大间距：
(
x
⃗
+
−
x
⃗
−
)
w
⃗
∣
w
∣
(\vec{x}_{+}-\vec{x}_{-})\frac{\vec{w}}{|w|}
(x
+−x
−)∣w∣w
== >
(
x
⃗
+
w
⃗
−
x
⃗
−
w
⃗
)
1
∣
w
∣
(\vec{x}_{+}\vec{w}-\vec{x}_{-}\vec{w})\frac{1}{|w|}
(x
+w
−x
−w
)∣w∣1
== >将
y
i
(
u
⃗
y_i(\vec{u}
yi(u
·
w
⃗
\vec{w}
w
+b)-1=0带入：（1-b+1+b）
1
∣
w
∣
\frac{1}{|w|}
∣w∣1
== >
2
∣
w
∣
\frac{2}{|w|}
∣w∣2
< == >max
1
∣
w
∣
\frac{1}{|w|}
∣w∣1
< == >min
∣
w
∣
|w|
∣w∣
< == >min
∣
∣
w
∣
∣
2
2
\frac{||w||^2}{2}
2∣∣w∣∣2
2.3、目标函数
从而得到目标函数即损失函数： L = ∣ ∣ w ∣ ∣ 2 2 − ∑ i = 1 n α i [ y i ( w ⃗ ⋅ x i ⃗ + b ) − 1 ] L=\frac{||w||^2}{2}-\sum_{i=1}^{n}\alpha_i[y_i(\vec{w}·\vec{x_i}+b)-1] L=2∣∣w∣∣2−∑i=1nαi[yi(w ⋅xi +b)−1]
2.4、优化理论
==>分别对w和b求偏导：
∂
L
∂
w
=
w
−
∑
i
=
1
n
α
i
y
i
x
i
⃗
\frac{\partial L}{\partial w}=w-\sum_{i=1}^{n}\alpha_i y_i \vec{x_i}
∂w∂L=w−∑i=1nαiyixi
=0，
∂
L
∂
b
=
∑
i
=
1
n
α
i
y
i
\frac{\partial L}{\partial b}=\sum_{i=1}^n \alpha_i y_i
∂b∂L=∑i=1nαiyi=0
==>从而得到：w=
∑
i
=
1
n
α
i
y
i
x
i
⃗
\sum_{i=1}^{n}\alpha_i y_i \vec{x_i}
∑i=1nαiyixi
，
∑
i
=
1
n
α
i
y
i
\sum_{i=1}^n \alpha_i y_i
∑i=1nαiyi=0。
==>上式代入目标函数，化简后的答案：
L
=
−
1
2
∑
i
=
1
n
α
i
y
i
x
i
⃗
∑
j
=
1
n
α
j
y
j
x
j
⃗
−
0
+
∑
i
=
1
n
α
i
=
∑
i
=
1
n
α
i
−
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
i
y
j
x
i
⃗
x
j
⃗
L=-\frac{1}{2}\sum_{i=1}^n\alpha_i y_i \vec{x_i} \sum_{j=1}^n\alpha_j y_j \vec{x_j}-0+\sum_{i=1}^n\alpha_i=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i \alpha_j y_i y_j \vec{x_i} \vec{x_j}
L=−21∑i=1nαiyixi
∑j=1nαjyjxj
−0+∑i=1nαi=∑i=1nαi−21∑i=1n∑j=1nαiαjyiyjxi
xj
2.5、带入决策公式
if ∑ i = 1 n α i y i x i ⃗ ⋅ u ⃗ i + b > = 0 \sum_{i=1}^{n}\alpha_i y_i \vec{x_i} · \vec{u}_i +b>=0 ∑i=1nαiyixi ⋅u i+b>=0，then 为正样本
2.6、核函数
==>将2.5的点成转换为核函数，意味着将低维转化为高维解决非线性可分问题：if ∑ i = 1 n α i y i k ( x i ⃗ , u ⃗ i ) + b > = 0 \sum_{i=1}^{n}\alpha_i y_i k(\vec{x_i} ,\vec{u}_i) +b>=0 ∑i=1nαiyik(xi ,u i)+b>=0，then 为正样本
2.7、求解公式中的所有 α \alpha α
使用（梯度上升法）SMO=》仅对凸优化有用：所有的 α \alpha α中，首先预定n-2个 α \alpha α的值，来求其余两个 α \alpha α，以此循环直到求解完所有的 α \alpha α