浅谈硬边界支持向量机理解
支持向量机是什么?
一个机器学习算法,用于数据分类
使用支持向量机的目的
通过划定超平面,完成数据分类
关键词
- 支持向量: 用于确定超平面的向量
- 超平面: 用于划分样本类型(超平面的一侧就是一种数据类型), 超平面的维度是数据特征数减一
比如数据有两个特征可在 x,y 二维坐标系中表示, 那么超平面就是一根直线
- 极值: 用于确定惟一的超平面
超平面的划分
拿上图举例
假设
黄点中的支持向量的坐标是 (x1,y1)
蓝点中的支持向量的坐标是 (x2,y2)
超平面(蓝色直线)的方程为
w
⃗
∗
x
⃗
+
b
=
0
\vec{w}*\vec{x}+b=0
w
∗x
+b=0
(其中 x为某个点的坐标向量, w为该超平面的法向量)
黄色直线的方程为
w
⃗
∗
x
1
⃗
+
b
=
−
1
\vec{w}*\vec{x1}+b=-1
w
∗x1
+b=−1
(-1代表的是类别, 这个方程的假设是蓝色的支持向量刚好过这个点)
绿色直线的方程为
w
⃗
∗
x
2
⃗
+
b
=
1
\vec{w}*\vec{x2}+b=1
w
∗x2
+b=1
(1代表的是类别,这个方程的假设是黄色的支持向量刚好过这个点)
为什么这两条平行线的方程右边是1和-1？其实也可以是2和-2，或者任意非零常数C和-C，规定1和-1只是为了方便。就像2x+3y+1=0和4x+6y+2=0是等价的，方程同乘一个常数后并不会改变。
什么是最好的超平面
为了保证最佳容错性, 显然我们需要似的黄色和绿色的线的间隔最大(蓝色的线位于他们的正中间). 因为如果黄色和绿色的线之间的距离过于窄的的话,那么对于出现在这个“临界区”的预测点的预测结果可能会不准确.
由两直线的距离公式:
D = ∣ c 1 − c 2 ∣ A 2 + B 2 D = \frac{|c1-c2|}{\sqrt{A^2+B^2}} D=A2+B2 ∣c1−c2∣
因为
A
2
+
B
2
=
∣
∣
w
∣
∣
2
A^2+B^2 = ||w||^2
A2+B2=∣∣w∣∣2
c
1
−
c
2
=
1
−
(
−
1
)
=
2
c1-c2=1-(-1)=2
c1−c2=1−(−1)=2
所以
D
=
2
∣
∣
w
∣
∣
D = \frac{2}{||w||}
D=∣∣w∣∣2
为了使D最大,那么就需要使得
∣
∣
w
∣
∣
||w||
∣∣w∣∣ 最小, 也可以说使得
w
2
2
\frac{w^2}{2}
2w2最小1
极值获取
对目前的所有样本,我们知道
当 y>0 时:
w
⃗
x
⃗
+
b
≧
1
\vec{w}\vec{x}+b\geqq1
w
x
+b≧1
当 y<0 时:
w
⃗
x
⃗
+
b
≦
−
1
\vec{w}\vec{x}+b\leqq-1
w
x
+b≦−1
所以
y
i
(
w
⃗
x
i
⃗
+
b
)
−
1
≧
0
y_{i}(\vec{w}\vec{x_{i}}+b)-1\geqq0
yi(w
xi
+b)−1≧0
y起到的作用就和绝对值一样。之所以要用y替换绝对值，是因为y是已知样本数据
当 上式恰好等于0的时候,就说明找到了支持向量
当 上式大于0的时候,就说明当前点在“临界区”之外
拉格朗日乘数法
对于每个点使用一个
λ
i
\lambda_{i}
λi进行约束,构造这样一个函数
L
(
w
,
b
,
λ
)
=
w
2
2
+
∑
i
=
1
n
λ
⃗
i
y
i
(
(
w
⃗
x
i
⃗
+
b
)
−
1
)
=
w
2
2
+
∑
i
=
1
n
λ
⃗
i
y
i
(
w
⃗
x
i
⃗
+
b
)
−
∑
i
=
1
n
λ
i
L(w,b,\lambda)=\frac{w^2}{2}+\sum_{i=1}^{n}\vec\lambda_{i} y_{i}((\vec{w}\vec{x_{i}}+b)-1) =\frac{w^2}{2}+\sum_{i=1}^{n}\vec\lambda_{i} y_{i}(\vec{w}\vec{x_{i}}+b)-\sum_{i=1}^{n}\lambda_{i}
L(w,b,λ)=2w2+i=1∑nλ
iyi((w
xi
+b)−1)=2w2+i=1∑nλ
iyi(w
xi
+b)−i=1∑nλi
求偏导数得
σ
(
L
)
σ
(
w
)
=
w
+
∑
i
=
1
n
λ
⃗
i
y
i
x
i
⃗
=
0
\frac{\sigma(L)}{\sigma(w)} = w+\sum_{i=1}^{n}\vec\lambda_{i} y_{i}\vec{x_{i}} = 0
σ(w)σ(L)=w+i=1∑nλ
iyixi
=0
σ
(
L
)
σ
(
b
)
=
∑
i
=
1
n
λ
⃗
i
y
i
=
0
\frac{\sigma(L)}{\sigma(b)} = \sum_{i=1}^{n}\vec\lambda_{i} y_{i} = 0
σ(b)σ(L)=i=1∑nλ
iyi=0
连立
L
(
w
,
b
,
λ
)
=
w
2
2
+
∑
i
=
1
n
λ
⃗
i
y
i
(
w
⃗
x
i
⃗
+
b
)
−
∑
i
=
1
n
λ
i
L(w,b,\lambda)=\frac{w^2}{2}+\sum_{i=1}^{n}\vec\lambda_{i} y_{i}(\vec{w}\vec{x_{i}}+b)-\sum_{i=1}^{n}\lambda_{i}
L(w,b,λ)=2w2+∑i=1nλ
iyi(w
xi
+b)−∑i=1nλi和
w
+
∑
i
=
1
n
λ
⃗
i
y
i
x
i
⃗
=
0
w+\sum_{i=1}^{n}\vec\lambda_{i} y_{i}\vec{x_{i}} = 0
w+∑i=1nλ
iyixi
=0解得:
L
(
w
,
b
,
λ
)
=
∑
i
=
1
n
λ
i
−
1
2
(
∑
i
=
1
n
∑
j
=
1
n
λ
i
λ
j
y
i
y
j
x
i
x
j
)
L(w,b,\lambda)= \sum_{i=1}^{n} \lambda_{i} - \frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_{i}\lambda_{j}y_{i}y_{j}x_{i}x_{j})
L(w,b,λ)=i=1∑nλi−21(i=1∑nj=1∑nλiλjyiyjxixj)
这时候函数中的
w
,
b
w,b
w,b 都消掉了,我们需要求的最优化问题变成
min
(
∑
i
=
1
n
λ
i
−
1
2
(
∑
i
=
1
n
∑
j
=
1
n
λ
i
λ
j
y
i
y
j
x
i
x
j
)
)
\min(\sum_{i=1}^{n} \lambda_{i} - \frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_{i}\lambda_{j}y_{i}y_{j}x_{i}x_{j}))
min(i=1∑nλi−21(i=1∑nj=1∑nλiλjyiyjxixj))
通过
∑
i
=
1
n
λ
⃗
i
y
i
=
0
\sum_{i=1}^{n}\vec\lambda_{i} y_{i} = 0
∑i=1nλ
iyi=0和
λ
i
(
y
i
(
w
⃗
x
i
⃗
+
b
)
−
1
)
=
0
\lambda_{i}(y_{i}(\vec{w}\vec{x_{i}}+b)-1)=0
λi(yi(w
xi
+b)−1)=02这两个约束条件,可以把方程解出来
参考
- https://en.wikipedia.org/wiki/Support_vector_machine
- https://zhuanlan.zhihu.com/p/74484361