没有合适的资源?快使用搜索试试~ 我知道了~
SVM理论与算法分析.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 181 浏览量
2023-11-11
22:13:58
上传
评论
收藏 1.61MB PDF 举报
温馨提示
试读
16页
SVM理论与算法分析.pdf
资源推荐
资源详情
资源评论
硬间隔线性支撑向量机
假设给定一个特征空间上的训练数据集:
T =
{
(
x
1
,y
1
)
,
(
x
2
,y
2
)
, €,
(
x
N
,y
N
)
}
其中,x
i
• R
n
, y
i
•
{
+1,‚1
}
,i = 1,2,€,N, x
i
为第 i 个特征向量或实例, y
i
为x
i
的类标记,当 y
i
= 1时,称x
i
为
正例,当 y
i
= ‚1时,称x
i
为负例;(x
i
,y
i
)为样本点。
假设训练数据集是线性可分的(存在硬间隔),那么学习的目标是在特征空间找到一个分离超平面,能将实
例分到不同的类。分离超平面方程w ƒ x + b = 0,它由法向量 w 和截距 b 决定,可用
(
w,b
)
表示。分离超平面
将特征空间分为两部分,一部分是正类,一部分是负类。法向量指向的一侧为正类,另一侧是负类。
一般地,当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开,感知机利用误分类最小
的策略,求得分离超平面,不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面,
解唯一。
一、模型推导
1.函数间隔:一般来说,一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面w ƒ x + b = 0
确定的情况下,|w ƒ x + b|能够相对地表示(注意:真实距离为
|wƒx+b|
„w„
)点x距离超平面的远近。而w ƒ x + b的
符号与类标记y的符号是否一致能够表示分类是否正确。所以可用标量y
(
w ƒ x + b
)
来表示分类的正确性及确信
度,值为正表示分类正确,值为负表示分类错误。
超平面
(
…,†
)
关于样本点
(‡
ˆ
,
‰
ˆ
)
的函数间隔为:
Š
‹
Œ
= •
Œ
(
Ž ƒ •
Œ
+ •
)
超平面
(
…,†
)
关于训练数据集T 的函数间隔:
Š
‹
= ‘Œ’
Œ=“,”,€,•
Š
‹
Œ
= ‘Œ’
Œ=“,”,€,•
•
Œ
(
Ž ƒ •
Œ
+ •
)
2.几何间隔:函数间隔可以表示分类预测的正确性及确信度,但是选择分离超平面时,只有函数间隔还不够。
因为只要成比例地改变 w 和 b,虽然超平面并没有改变,但函数间隔(它是
(
w,b
)
的线性函数)却依原比例同
等改变。为了将
(
w,b
)
表示的超平面的唯一化,即每个超平面对应R
n+1
中的唯一向量
(
w,b
)
,可以对法向量 w
加以规范化约束„ w „= 1,这时函数间隔称为几何间隔。
超平面
(
…,†
)
关于样本点
(‡
ˆ
,
‰
ˆ
)
的几何间隔为:
Š
Œ
=
Š
‹
Œ
„ Ž „
= •
Œ
(
Ž
„ Ž „
ƒ •
Œ
+
•
„ Ž „
)
超平面
(
…,†
)
关于训练数据集T 的几何间隔为:
Š = ‘Œ’
Œ=“,”,€,•
Š
Œ
= ‘Œ’
Œ=“,”,€,•
•
Œ
(
Ž
„ Ž „
ƒ •
Œ
+
•
„ Ž „
)
3.间隔最大化
支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分
的训练数据集而言,线性可分分离超平面有无穷多个,每一个都是一个感知机,但是几何间隔最大的分离超
平面时唯一的。
间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进
行分类。也就是说,不仅将正负实例点要分开,而且对最难分的实例点(离超平面最近的点)也有足够多大
的确信度将它们分开。
因此所要优化的问题 表示为:
‘–•
Ž,•
Š
—.˜. •
Œ
(
Ž
„ Ž „
ƒ •
Œ
+
•
„ Ž „
) ™ Š, Œ = “,”,€,•
改写为,
€•‚
ƒ,„
…
†
‡ ƒ ‡
ˆ.‰. Š
‹
(
ƒŒ‚
‹
+„
)
• …
†,
‹=Ž,•,•,‘
’†的取值不影响最优化问题的解(如果w
“
,b
“
是最优解,那么”w
“
,”b
“
也是最优解,因此’†是变动的可以取到任
意值,如果固定’†,w
“
,b
“
也就变得唯一了),令’† = 1,等价变换为,
€•‚
ƒ,„
Ž
‡ ƒ ‡
ˆ.‰. Š
‹
(
ƒŒ‚
‹
+„
)
• Ž, ‹ = Ž,•,•,‘
(目标函数是支撑间隔,约束是样本点在间隔边界或外侧,目标是寻找支撑向量使得间隔最大化)等价变换
为(标准无等式约束的凸二次规划,这是为了运算方便),
€‹•
ƒ,„
Ž
•
‡ ƒ ‡
•
ˆ.‰. Ž–Š
‹
(
ƒŒ‚
‹
+„
)
— ˜, ‹ = Ž,•,•,‘
凸二次规划问题存在全局最优解w
“
,b
“
。
(4)分离超平面与分类决策函数
分离超平面:
ƒ
“
Œ‚+ „
“
= ˜
分类决策函数:
™
(
‚
)
= ˆ‹š•
(
ƒ
“
Œ‚ +„
“
)
(5)支撑向量与间隔边界
在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量,支撑向量
是使约束条件等号成立的点,即Ž–Š
‹
(
ƒŒ‚
‹
+„
)
= ˜,对于正例点,支撑向量在超平面ƒŒ‚
‹
+„ = Ž上,对
于负例点,支撑向量在超平面ƒŒ‚
‹
+„ = –Ž上,没有实例点落在这两个平行的超平面(间隔边界)之间,
这两个超平面之间的距离称为间隔,它依赖于分离超平面的法向量 w,等于
•
‡ƒ‡
。
在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。如果移动支持向量将改变所求的解,
但是如果在间隔边界以外移动其他实例点,甚至去掉这些点,则解是不会改变的。显然支撑向量是训练集中
重要的样本。
二、模型求解
将原始问题转化为 Lagrange 对偶问题,通过求解对偶问题来获得原始问题的最优解:对每个不等式约束引入
Lagrange 乘子›
i
,
1.Lagrange 对偶函数:
œ
(
ƒ,„,•
)
=
Ž
•
‡ ƒ ‡
•
–ž•
‹
Š
‹
(
ƒŸ‚
‹
+„
)
‘
‹=Ž
+ž•
‹
‘
‹=Ž
其中› =
(
›
1
,›
2
,•,›
N
)
T
为拉格朗日乘子向量,›
i
• 0,i= 1,2,•,N。
2.对偶问题:
max
›
min
w,b
L
(
w,b,›
)
(1) 求€‹•
ƒ,„
œ
(
ƒ,„,•
)
w
L
(
w,b,›
)
= w–ž›
i
y
i
N
i=1
x
i
= 0
b
L
(
w,b,›
)
= –ž›
i
y
i
N
i=1
= 0
得出
w = ž›
i
y
i
N
i=1
x
i
ۥ
i
y
i
N
i=1
=0
带入拉格朗日函数,得出
‚ƒ„
…,†
‡
(
…,†,ˆ
)
=
‰
Š
€€ˆ
ƒ
ˆ
‹
Œ
ƒ
•
‹=‰
•
ƒ=‰
Œ
‹
(Ž
ƒ
• Ž
‹
)
• €ˆ
ƒ
Œ
ƒ
•
ƒ=‰
((€
ˆ
‹
Œ
‹
•
‹=‰
Ž
‹
) • Ž
ƒ
+ †) + €ˆ
ƒ
•
ƒ=‰
=•
‰
Š
€€ˆ
ƒ
ˆ
‹
Œ
ƒ
•
‹=‰
•
ƒ=‰
Œ
‹
(Ž
ƒ
• Ž
‹
)
+ €ˆ
ƒ
•
ƒ=‰
(2)求‚‘Ž
ˆ
‚ƒ„
…,†
‡
(
…,†,ˆ
)
‚‘Ž
ˆ
(•
‰
Š
€€ˆ
ƒ
ˆ
‹
Œ
ƒ
•
‹=‰
•
ƒ=‰
Œ
‹
(Ž
ƒ
• Ž
‹
)
+ €ˆ
ƒ
•
ƒ=‰
)
’.“. €ˆ
ƒ
Œ
ƒ
•
ƒ=‰
=”
ˆ
ƒ
• ”,ƒ =‰,Š,–,•
转换为求极小
‚ƒ„
ˆ
(
‰
Š
€€ˆ
ƒ
ˆ
‹
Œ
ƒ
•
‹=‰
•
ƒ=‰
Œ
‹
(Ž
ƒ
• Ž
‹
)
• €ˆ
ƒ
•
ƒ=‰
)
’.“. €ˆ
ƒ
Œ
ƒ
•
ƒ=‰
=”
ˆ
ƒ
• ”,ƒ =‰,Š,–,•
根据对偶理论,对上述对偶优化存在,使w
—
,b
—
是原始问题的解,•
—
是对偶问题的解,因此求解原始问题,
可以转化为求解对偶问题。
3.最优解
根据 KKT 条件
˜
w
—
L
(
w
—
,b
—
,•
—
)
=w
—
•
€
•
i
—
y
i
N
i=1
x
i
=0--------------------------(a)
˜
b
—
L
(
w
—
,b
—
,•
—
)
=•
€
•
i
—
y
i
N
i=1
=0----------------------------------(b)
•
i
—
(
y
i
(
w
—
• x
i
+ b
—
)
• 1
)
=0 , i=1,2,–,N---------------------------------(c)
y
i
(
w
—
• x
i
+ b
—
)
• 1 • 0, i =1,2,–,N---------------------------------------(d)
•
i
—
• 0, i =1,2,–,N-----------------------------------------------------------(e)
由(a)求得
…
—
=€ˆ
ƒ
—
Œ
ƒ
•
ƒ=‰
Ž
ƒ
其中至少有一个•
k
—
> 0(如果•
—
=0,那么w
—
=0,b
—
无解,显然它不是原始最优化问题的解),结合 KKT
条件(c),得出
y
k
(
w
—
• x
k
+ b
—
)
• 1 =0
将…
—
带入 KKT 条件,得出
y
k
((€ •
i
—
y
i
x
i
N
i=1
) • x
k
+b
—
) =1
两边同时乘以y
k
,由于
(
y
k
)
2
=1
剩余15页未读,继续阅读
资源评论
hhappy0123456789
- 粉丝: 59
- 资源: 5万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功