最大间隔
+1
-1
x
f
y
具有最大间隔的线 性分类器叫做最大 间隔线性分类器。
f(x,w,b) = sign(w. x - b)
其就是一种最简单 的支持向量机(SVM) (称为线性支持向量 机，即LSVM)
线性支持向量机
最大间隔
+1
-1
x
f
y
具有最大间隔的线 性分类器叫做最大 间隔线性分类器。
f(x,w,b) = sign(w. x - b)
yk (w . xk + b )>= 1 k=1,2,…,n
What You Should Know
• • • • 线性 SVMs 最大间隔分类器 QP 的作用 (但是, 这里, 你不必知道如何求解它) 最大间隔问题可以转化为一个二次优化(QP)问题
f(x,w,b) = sign(w. x - b)
具有最大间隔的线 1 性分类器叫做最大 ( ) ( ) m arg in 间隔线性分类器。
支持向量(Support Vectors) :是那些距 离超平面最近的点。
其就是一种最简单 的支持向量机(SVM) (称为线性支持向量 机，即LSVM)
支持向量(Support Vectors) :是那些距 离超平面最近的点。
其就是一种最简单 的支持向量机(SVM) (称为线性支持向量 机，即LSVM)
线性支持向量机
Why… 最大间隔?
1. 直观上感觉很好.
+1
-1
2. 学习得到的线性分类器.其对未知样本 的预测能力与分类器间隔有如t Vector Machines
线性分类器
+1
-1
x
f
y
f(x,w,b) = sign(w. x - b)
How would you classify this data?
线性分类器
+1
-1
x
f
y
f(x,w,b) = sign(w. x - b)
How would you classify this data?
x+ xM = |x+ - x- | =| l w |=
M = Margin Width =
2 w .w
现在我们知道: • w . x+ + b = +1 • w . x- + b = -1 • x+ = x- + l w • |x+ - x- | = M 2 •
λ w.w
λ | w | λ w .w
计算间隔
x+ x-
M = Margin Width
现在我们知道: • w . x+ + b = +1 • w . x- + b = -1 • x+ = x- + l w • |x+ - x- | = M 于是很容易由w 和b 得到 M
计算间隔
x+ x-
M = Margin Width
w . (x - + l w) + b = 1
Classify as.. +1
-1
if
if
w . x + b >= 1
w . x + b <= -1 -1 < w . x + b < 1
不可分情况 if
计算间隔
M = Margin
我们怎样利用 w与b 计算margin?
• Plus-plane = { x : w . x + b = +1 } • Minus-plane = { x : w . x + b = -1 }
线性支持向量机
具体化分类超平面及其间隔
Plus-Plane Classifier Boundary Minus-Plane
• 如何在数学上表示? • …在m位空间中?
具体化分类超平面及其间隔
Plus-Plane Classifier Boundary Minus-Plane
• Plus-plane = { x : w . x + b = +1 } • Minus-plane = { x : w . x + b = -1 }
计算间隔
x+ M = Margin
x-
我们怎样利用 w与b 计算margin?
• • • • • •
Plus-plane = { x : w . x + b = +1 }+ x- 与 x 的连线与planes Minus-plane = { x : w . x + b = -1 } 垂直. 向量 w 与 Plus Plane 垂直 于是x- 在w 的方向上移动 设 x- 是 minus plane上任意一点 一段距离就可与到达x+. 设 x+是plus-plane上距离 x-最近的点 注: 对于某实数l， x+ = x- + l w. 为什么?
现在我们知道: • w . x+ + b = +1 • w . x- + b = -1 • x+ = x- + l w • |x+ - x- | = M 于是很容易由w 和b 得到 M
=> w . x - + b + l w .w = 1 =>
-1 + l w .w = 1
=>
λ
2 w.w
计算间隔
线性分类器
+1
-1
x
f
y
f(x,w,b) = sign(w. x - b)
How would you classify this data?
线性分类器
+1
-1
x
f
y
f(x,w,b) = sign(w. x - b)
How would you classify this data?
线性分类器
+1
所以 w 也垂直于Minus Plane 设 u 和 v 是 Plus Plane上的两个向量. 则 w . ( u – v ) 是多少?
计算间隔
x+ M = Margin
x-
我们怎样利用 w与b 计算margin?
• • • • •
Plus-plane = { x : w . x + b = +1 } Minus-plane = { x : w . x + b = -1 } 向量 w 与 Plus Plane 垂直 设 x- 是 minus plane上任意一点 设 x+是plus-plane上距离 x-最近的点
注: 向量 w 与 Plus Plane 垂直. 为什么?
计算间隔
M = Margin
我们怎样利用 w与b 计算margin?
• Plus-plane = { x : w . x + b = +1 } • Minus-plane = { x : w . x + b = -1 }
注: 向量 w 与 Plus Plane 垂直. 为什么?
2 w .w w .w 2 w .w


学习最大间隔分类器
x+ x-
M = Margin Width =
2 w .w
我们现在需要找到一种算法，来求出w 与 b，并且 能匹配 上所有的样本点. 怎么做? 梯度下降? 退火算法? 矩阵求逆? 牛顿法?
利用二次优化求解
Minimize
1 2 w .w
subject to
-1
x
f
y
f(x,w,b) = sign(w. x - b)
Any of these would be fine..
..but which is best?
线性分类器
+1
-1
x
f
y
线性分类器的间隔 （ margin）：到超 平面最近的样本与 此超平面之间的距 离。
f(x,w,b) = sign(w. x - b)
计算间隔
x+ M = Margin
x-
我们怎样利用 w与b 计算margin?
• • • • • •
Plus-plane = { x : w . x + b = +1 } Minus-plane = { x : w . x + b = -1 } 向量 w 与 Plus Plane 垂直 设 x- 是 minus plane上任意一点 设 x+是plus-plane上距离 x-最近的点 注: 对于某实数l， x+ = x- + l w. 为什么?