第六章统计学习理论
? 6.0 引言
? 6.1 一致性与一致收敛
? 6.2 Vapnik-Chervonenkis (VC)理论
? 6.3 结构风险最小化(Structural Risk
Minimization)
6.0 引言
6.0 引言
?模式识别中的学习问题：
?训练数据集( X,Y )
),,(,),,(),,(
2211 nn
yxyxyx L
},,2,1{ Ky
i
L∈
i
x
随机变量的独立同分布样本。
Y
,
d
i
x?∈
随机变量的独立同分布样本。
X
的类别标识，
6.0 引言
?学习函数集：
?损失函数：
}:),({ Θ∈θθxf
参数参数空间
)).,(,( θxfyL
6.0 引言
?平方误差损失函数：
?不敏感损失函数：
2
)),(()),(,( θθ xfyxfyL?=
{
其他|),(|
|),(|0
|),(|)),(,(
θ
εθ
θθ
ε
xfy
xfy
xfyxfyL
≤?
=
=
ε
6.0 引言
? Soft Margin损失函数：
? Hard Margin损失函数：
?误分类数损失函数：
{
else
xfyxfy
xfyxfyL
0
0),(),(
|),(|)),(,(
>
=
=
+
θθ
θθ
{
else
xfy
xfyhxfyL
0
0),(1
)),(()),(,(
>?
=
=
θ
θθ
)),(()),(,( θθ xyfhxfyL?=
6.0 引言
?例：最小平方误差准则线性分类器。
?训练数据：
?学习函数集：
?损失函数：
.,,},,{?×?=Θ?∈?∈=
dd
bwbwθ
}.1,1{ +?∈
i
y
.),( bxwxf
T
+=θ
.)()),(()),(,(
22
bxwyxfyxfyL
T
=?= θθ
,
d
i
x?∈
6.0 引言
?学习：从学习函数集中挑一个“最优”的。
?什么是“最优”？
?统计推断：期望风险最小化( RM )
?期望风险
∫
=?=
),()),(,()),(()( yxdFxfyLfRR θθθ
YX,
的分布函数。
6.0 引言
?基于最小错误率的Bayes决策：条件错误率的数学期望
)).|((
)()|()()|(
),()(
xePE
xdPxePdxxpxeP
dxxePeP
=
==
=
∫∫
∫
6.0 引言
?经验风险
?经验风险最小化( ERM )原则：用经验风险来逼近期望风险。
.)),(,(
1
)),(()(
1
∑
=
=?=
n
i
iiempemp
xfyL
n
fRR θθθ
6.0 引言
? ERM原则的例子：
?最小平方误差准则线性分类器：
?密度估计的最大似然方法：
.)(
1
),(,(
1
)(
1
2
1
∑∑
==
==
n
i
i
T
i
n
i
iiemp
bxwy
n
xfyL
n
R θθ
),(ln
1
)(
1
∑
=
=
n
i
iemp
xP
n
R θθ
6.0 引言
?关于经验风险最小化(Empirical Risk
Minimization)的问题：
?一致性(consistency)；
?泛化能力(generalization ability) 收敛速度；
?泛化能力的控制：结构风险最小化。
6.1 一致性与一致收敛
6.1一致性与一致收敛
?渐进性质—一致性：
? ERM估计与RM估计：
.)),(,(
1
minarg)(minarg)(
1
∑
=
Θ∈Θ∈
==
n
i
iiempR
xfyL
n
Rn
emp
θθθ
θθ
.),()),(,(minarg)(minarg
∫
Θ∈Θ∈
== yxdFxfyLR
R
θθθ
θθ
6.1一致性与一致收敛
?一致性；
?解收敛：
?风险值收敛：
.0)
())(
(→
∞→n
RR
RnR
emp
θθ
.0)
())(
(→
∞→n
RRemp
RnR
emp
θθ
P
P
6.1一致性与一致收敛
?非平凡一致性：（后简称一致性）
?对函数集定义子集如果对任意非空都有
},),()),(,(:),({)( Θ∈>=Λ
∫
θθθ cyxdFxfyLxfc
}:),({ Θ∈θθxf
),(),( ∞?∞∈Λ cc
)(inf)(inf
)()(
θθ
θθ
RR
c
n
emp
c Λ∈
∞→
Λ∈
→?
6.1 一致性与一致收敛
?一致性的充要条件—一致收敛。
?一致收敛：
? Key Theorem (theorem about equivalence):
ERM原则一致性的充分必要条件是一致收敛。
0}))()((supPr{→?>?
∞?→?
Θ∈
n
emp
RR εθθ
θ
0>?ε
6.1 一致性与一致收敛
?经验风险和期望风险期望风险经验风险
n
6.1 一致性与一致收敛
?经验风险和期望风险都是学习函数集的函数（泛函）。
?学习的目的：通过求使经验风险最小化的学习函数来逼近使期望风险最小化的函数。
?注意：ERM原则一致性的充分必要条件取决于学习函数集中最差函数的性能。
6.1 一致性与一致收敛
?损失函数为示性函数的分析：
?例：
),sgn(),( bxwxf
T
+=θ
≠
=
=
).,(1
).,(0
)),(,(
θ
θ
θ
xfy
xfy
xfyL
}......2,1,{),,( nizZyxz
i
===
令
)).,(,(),( θθ xfyLzQ =记
6.1 一致性与一致收敛
?随机熵：
函数集对样本集所有不同分类数目定义为：
),,,(
21 n
zzzN L
Θ
.2),,,(
21
n
n
zzzN ≤
Θ
L
必有：
)),,,((ln))(()(
21 n
zzzNEZHEnH L
ΘΘ
==
?示性函数集的熵:
),,,(ln)(
21 n
zzzNZH L
Θ
=
)(ZH
6.1 一致性与一致收敛
?一致收敛的充要条件：
.0
)(
lim =
Θ
∞→
n
nH
n
6.1 一致性与一致收敛
?完全不可证伪性
?部分不可证伪性
2ln
)(
lim =
Θ
∞→
n
nH
n
.0
)(
lim >=
Θ
∞→
C
n
nH
n
6.2 VC理论
6.2 VC理论
?函数集的熵与分布函数有关：
?与分布无关的熵：生长函数(Growth
function).
).(),,,(ln
)),,,((ln)(
21
21
zdFzzzN
zzzNEnH
n
n
L
L
Θ
ΘΘ
∫
=
=
依赖具体问题。
)).,,,(supln()(
21
,,
21
n
zzz
zzzNnG
n
L
L
ΘΘ
=
普遍适用。
6.2 VC理论
?函数集的熵与生长函数的关系：
?与分布函数无关的一致收敛：
).()( nGnH
ΘΘ
≤
.0
)(
lim =
Θ
∞→
n
nG
n
6.2 VC理论
? Growth function的结构：
>+≤
≤=
Θ
hn
h
n
h
hnn
nG
)ln1(
2ln
)(
n
h
)(nG
Θ 2lnn
)1(ln +
h
n
h
h:VC维
6.2 VC理论
?示性函数集的VC维：最大的正整数，
使得存在，可以被任意地分成两类。
.2),,,(
21
h
h
zzzN =
Θ
L
h
h
zzz,,,
21
L
),( θzQ Θ∈θ
.2),,,(
1
121
+
+
Θ
<
h
h
zzzN L
.,,,
21 h
zzz L?
.,,,
121 +
h
zzz L
6.2 VC理论
? VC维的例子：
?线性分类器（超平面）：
).sgn(),( bzwzQ
T
+=θ
).,( bw=θ
,
d
z?∈
.1+= dh
VC维:
6.2 VC理论
,2=d
.3=h
存在无论怎么组合总存在直线可以分为两类：
321
,,zzz
6.2 VC理论不存在可以直线任意分为两类：
4321
,,,zzzz
6.2 VC理论
? VC维是函数复杂性的度量，与自由参数有关。
?损失函数对参数是线性的：
).)(sgn(),(
1
∑
=
=
m
i
ii
zzQ?θθ
.mh = VC维数等于参数个数。
6.2 VC理论
? VC维一般正比于但不必定等于参数个数。
?标准Sigmoid阈值的多层感知机的VC维
?函数集的VC维是无穷
?函数集的VC维等于1，与n无关。
2
nh ∝
))(sin(),( zzf αθα =
0),(),(
1
>+=
∑
=
iii
n
i
i
cbzwczf σα
6.2 VC理论
?实值函数集的VC维：
?变实值函数为示性函数：
.),(?∈θzQ
),),(sgn(),,( βθβθ?=
′
zQzQ,?∈β
实值函数集的VC维定义成示性函数集
},:),,({?∈Θ∈
′
βθβθzQ的VC维。
6.2 VC理论
?例：
?线性函数集：
).,( bw=θ
.),( bzwzQ
T
+=θ
,
d
z?∈
),sgn(),,( ββθ?+=
′
bzwzQ
T
.?∈β
.1+= dh
VC维:
6.2 VC理论
? Gauss函数（一维）：
}.
2
)(
exp{
2
1
),(
2
2
σ
μ
σπ
θ
=
x
zQ
).,( σμθ =
).}
2
)(
exp{
2
1
sgn(),,(
2
2
β
σ
μ
σπ
βθ?
=
′
x
zQ
.2=h
VC维:
6.2 VC理论
2
z
1
z
1
z
2
z
可以任意分类。
1
z
2
z
1
z
2
z
无法任意分类。
3
z
3
z
1
z
2
z
1
z
2
z
6.2 VC理论
? ERM的泛化能力（收敛速度）：
.
1
))(
())(
(
n
nRnR
empemp
RempR
+?+≤ θθ
以概率成立。
η?1
.
4ln)
2
ln1(2
4
4ln)2(
4
n
h
n
h
n
nG
η
η
+
≤
=?
Θ
.2hn >
6.2 VC理论
? ERM原则是针对大样本数问题的。当较小时，实际风险接近经验风险的取值。
但是，当较大时，小的经验风险并不能保证小的实际风险。这是ERM原则的缺点，也是过学习问题所在。
nh /
nh /
6.3 结构风险最小化
6.3 结构风险最小化
?结构风险最小化（Structural Risk
Minimization)原则：对风险上界最小化，
而不是单纯使经验风险最小化。
?同时考虑经验风险和VC维(trade off)
.
1
))(
())(
(
n
nRnR
empemp
RempR
+?+≤ θθ
与VC维有关经验风险
6.3 结构风险最小化
?构造结构化的学习函数集：
.
21
LL
k
SSS
.
U
i
i
SS =
}.:),({
ii
xfS Θ= θ,
21
LL?Θ?Θ?Θ
k
]
1
[min
n
R
emp
S
h
+?+
6.3 结构风险最小化
?例：
? ={n阶多项式}
? ={n个中心的RBF}
? ={n个单元的多层感知机}
n
S
n
S
n
S
})(|{ nffS
n
≤Φ=
6.3 结构风险最小化
?给定序列,求解最优化问题：
LL <<<<
m
AAA
21
m
K
n
i
ii
f
Af
xfyL
n
≤
∑
=
2
1
))(,(
1
min
6.3 结构风险最小化
?对每个m,使下式最小
)())(,(
1
2
1
m
K
m
n
i
ii
AfxfyL
n
+
∑
=
λ
6.3 结构风险最小化实际中，给定使下式最小
m
λ
2
1
))(,(
1
K
m
n
i
ii
fxfyL
n
λ+
∑
=
6.3 结构风险最小化
SRM是一致相合的。
风险上界经验风险
h
n
h
Sn的VC维
1
h *h
S1
Sn
S*
“最优”学习函数集。
6.3 结构风险最小化
? SRM原则给出了在给定数据逼近的精度和逼近函数的复杂性之间的一种折中。
6.4 说明
6.4 说明
?用有限数量信息解决问题的基本原则：
在解决一个给定的问题时，要尽量避免把解决一个更为一般的问题作为中间步骤。
? Ockham’s razor:
? Williams of Ockham/Occam (1285-1347?);
? Ockham’s razor:,entities should not be
multiplied beyond necessity,.
参考文献
? [1] Vladimir N,Vapnik,Statistical Learning
Theory,John Wiley & Sons,Inc,1998.
? [2] Vladimir N,Vapnik,The Nature of Statistical
Learning,Springer-Verlag,New York,NY,1995
(中译本《统计学习理论的本质》，张学工译，
清华大学出版社，2000年9月)
? [3] Vladimir N,Vapnik,An overview of
Statistical Learning Theory,IEEE Trans,Neural
Networks,10 (5),988-999,1999.
? 6.0 引言
? 6.1 一致性与一致收敛
? 6.2 Vapnik-Chervonenkis (VC)理论
? 6.3 结构风险最小化(Structural Risk
Minimization)
6.0 引言
6.0 引言
?模式识别中的学习问题：
?训练数据集( X,Y )
),,(,),,(),,(
2211 nn
yxyxyx L
},,2,1{ Ky
i
L∈
i
x
随机变量的独立同分布样本。
Y
,
d
i
x?∈
随机变量的独立同分布样本。
X
的类别标识，
6.0 引言
?学习函数集：
?损失函数：
}:),({ Θ∈θθxf
参数参数空间
)).,(,( θxfyL
6.0 引言
?平方误差损失函数：
?不敏感损失函数：
2
)),(()),(,( θθ xfyxfyL?=
{
其他|),(|
|),(|0
|),(|)),(,(
θ
εθ
θθ
ε
xfy
xfy
xfyxfyL
≤?
=
=
ε
6.0 引言
? Soft Margin损失函数：
? Hard Margin损失函数：
?误分类数损失函数：
{
else
xfyxfy
xfyxfyL
0
0),(),(
|),(|)),(,(
>
=
=
+
θθ
θθ
{
else
xfy
xfyhxfyL
0
0),(1
)),(()),(,(
>?
=
=
θ
θθ
)),(()),(,( θθ xyfhxfyL?=
6.0 引言
?例：最小平方误差准则线性分类器。
?训练数据：
?学习函数集：
?损失函数：
.,,},,{?×?=Θ?∈?∈=
dd
bwbwθ
}.1,1{ +?∈
i
y
.),( bxwxf
T
+=θ
.)()),(()),(,(
22
bxwyxfyxfyL
T
=?= θθ
,
d
i
x?∈
6.0 引言
?学习：从学习函数集中挑一个“最优”的。
?什么是“最优”？
?统计推断：期望风险最小化( RM )
?期望风险
∫
=?=
),()),(,()),(()( yxdFxfyLfRR θθθ
YX,
的分布函数。
6.0 引言
?基于最小错误率的Bayes决策：条件错误率的数学期望
)).|((
)()|()()|(
),()(
xePE
xdPxePdxxpxeP
dxxePeP
=
==
=
∫∫
∫
6.0 引言
?经验风险
?经验风险最小化( ERM )原则：用经验风险来逼近期望风险。
.)),(,(
1
)),(()(
1
∑
=
=?=
n
i
iiempemp
xfyL
n
fRR θθθ
6.0 引言
? ERM原则的例子：
?最小平方误差准则线性分类器：
?密度估计的最大似然方法：
.)(
1
),(,(
1
)(
1
2
1
∑∑
==
==
n
i
i
T
i
n
i
iiemp
bxwy
n
xfyL
n
R θθ
),(ln
1
)(
1
∑
=
=
n
i
iemp
xP
n
R θθ
6.0 引言
?关于经验风险最小化(Empirical Risk
Minimization)的问题：
?一致性(consistency)；
?泛化能力(generalization ability) 收敛速度；
?泛化能力的控制：结构风险最小化。
6.1 一致性与一致收敛
6.1一致性与一致收敛
?渐进性质—一致性：
? ERM估计与RM估计：
.)),(,(
1
minarg)(minarg)(
1
∑
=
Θ∈Θ∈
==
n
i
iiempR
xfyL
n
Rn
emp
θθθ
θθ
.),()),(,(minarg)(minarg
∫
Θ∈Θ∈
== yxdFxfyLR
R
θθθ
θθ
6.1一致性与一致收敛
?一致性；
?解收敛：
?风险值收敛：
.0)
())(
(→
∞→n
RR
RnR
emp
θθ
.0)
())(
(→
∞→n
RRemp
RnR
emp
θθ
P
P
6.1一致性与一致收敛
?非平凡一致性：（后简称一致性）
?对函数集定义子集如果对任意非空都有
},),()),(,(:),({)( Θ∈>=Λ
∫
θθθ cyxdFxfyLxfc
}:),({ Θ∈θθxf
),(),( ∞?∞∈Λ cc
)(inf)(inf
)()(
θθ
θθ
RR
c
n
emp
c Λ∈
∞→
Λ∈
→?
6.1 一致性与一致收敛
?一致性的充要条件—一致收敛。
?一致收敛：
? Key Theorem (theorem about equivalence):
ERM原则一致性的充分必要条件是一致收敛。
0}))()((supPr{→?>?
∞?→?
Θ∈
n
emp
RR εθθ
θ
0>?ε
6.1 一致性与一致收敛
?经验风险和期望风险期望风险经验风险
n
6.1 一致性与一致收敛
?经验风险和期望风险都是学习函数集的函数（泛函）。
?学习的目的：通过求使经验风险最小化的学习函数来逼近使期望风险最小化的函数。
?注意：ERM原则一致性的充分必要条件取决于学习函数集中最差函数的性能。
6.1 一致性与一致收敛
?损失函数为示性函数的分析：
?例：
),sgn(),( bxwxf
T
+=θ
≠
=
=
).,(1
).,(0
)),(,(
θ
θ
θ
xfy
xfy
xfyL
}......2,1,{),,( nizZyxz
i
===
令
)).,(,(),( θθ xfyLzQ =记
6.1 一致性与一致收敛
?随机熵：
函数集对样本集所有不同分类数目定义为：
),,,(
21 n
zzzN L
Θ
.2),,,(
21
n
n
zzzN ≤
Θ
L
必有：
)),,,((ln))(()(
21 n
zzzNEZHEnH L
ΘΘ
==
?示性函数集的熵:
),,,(ln)(
21 n
zzzNZH L
Θ
=
)(ZH
6.1 一致性与一致收敛
?一致收敛的充要条件：
.0
)(
lim =
Θ
∞→
n
nH
n
6.1 一致性与一致收敛
?完全不可证伪性
?部分不可证伪性
2ln
)(
lim =
Θ
∞→
n
nH
n
.0
)(
lim >=
Θ
∞→
C
n
nH
n
6.2 VC理论
6.2 VC理论
?函数集的熵与分布函数有关：
?与分布无关的熵：生长函数(Growth
function).
).(),,,(ln
)),,,((ln)(
21
21
zdFzzzN
zzzNEnH
n
n
L
L
Θ
ΘΘ
∫
=
=
依赖具体问题。
)).,,,(supln()(
21
,,
21
n
zzz
zzzNnG
n
L
L
ΘΘ
=
普遍适用。
6.2 VC理论
?函数集的熵与生长函数的关系：
?与分布函数无关的一致收敛：
).()( nGnH
ΘΘ
≤
.0
)(
lim =
Θ
∞→
n
nG
n
6.2 VC理论
? Growth function的结构：
>+≤
≤=
Θ
hn
h
n
h
hnn
nG
)ln1(
2ln
)(
n
h
)(nG
Θ 2lnn
)1(ln +
h
n
h
h:VC维
6.2 VC理论
?示性函数集的VC维：最大的正整数，
使得存在，可以被任意地分成两类。
.2),,,(
21
h
h
zzzN =
Θ
L
h
h
zzz,,,
21
L
),( θzQ Θ∈θ
.2),,,(
1
121
+
+
Θ
<
h
h
zzzN L
.,,,
21 h
zzz L?
.,,,
121 +
h
zzz L
6.2 VC理论
? VC维的例子：
?线性分类器（超平面）：
).sgn(),( bzwzQ
T
+=θ
).,( bw=θ
,
d
z?∈
.1+= dh
VC维:
6.2 VC理论
,2=d
.3=h
存在无论怎么组合总存在直线可以分为两类：
321
,,zzz
6.2 VC理论不存在可以直线任意分为两类：
4321
,,,zzzz
6.2 VC理论
? VC维是函数复杂性的度量，与自由参数有关。
?损失函数对参数是线性的：
).)(sgn(),(
1
∑
=
=
m
i
ii
zzQ?θθ
.mh = VC维数等于参数个数。
6.2 VC理论
? VC维一般正比于但不必定等于参数个数。
?标准Sigmoid阈值的多层感知机的VC维
?函数集的VC维是无穷
?函数集的VC维等于1，与n无关。
2
nh ∝
))(sin(),( zzf αθα =
0),(),(
1
>+=
∑
=
iii
n
i
i
cbzwczf σα
6.2 VC理论
?实值函数集的VC维：
?变实值函数为示性函数：
.),(?∈θzQ
),),(sgn(),,( βθβθ?=
′
zQzQ,?∈β
实值函数集的VC维定义成示性函数集
},:),,({?∈Θ∈
′
βθβθzQ的VC维。
6.2 VC理论
?例：
?线性函数集：
).,( bw=θ
.),( bzwzQ
T
+=θ
,
d
z?∈
),sgn(),,( ββθ?+=
′
bzwzQ
T
.?∈β
.1+= dh
VC维:
6.2 VC理论
? Gauss函数（一维）：
}.
2
)(
exp{
2
1
),(
2
2
σ
μ
σπ
θ
=
x
zQ
).,( σμθ =
).}
2
)(
exp{
2
1
sgn(),,(
2
2
β
σ
μ
σπ
βθ?
=
′
x
zQ
.2=h
VC维:
6.2 VC理论
2
z
1
z
1
z
2
z
可以任意分类。
1
z
2
z
1
z
2
z
无法任意分类。
3
z
3
z
1
z
2
z
1
z
2
z
6.2 VC理论
? ERM的泛化能力（收敛速度）：
.
1
))(
())(
(
n
nRnR
empemp
RempR
+?+≤ θθ
以概率成立。
η?1
.
4ln)
2
ln1(2
4
4ln)2(
4
n
h
n
h
n
nG
η
η
+
≤
=?
Θ
.2hn >
6.2 VC理论
? ERM原则是针对大样本数问题的。当较小时，实际风险接近经验风险的取值。
但是，当较大时，小的经验风险并不能保证小的实际风险。这是ERM原则的缺点，也是过学习问题所在。
nh /
nh /
6.3 结构风险最小化
6.3 结构风险最小化
?结构风险最小化（Structural Risk
Minimization)原则：对风险上界最小化，
而不是单纯使经验风险最小化。
?同时考虑经验风险和VC维(trade off)
.
1
))(
())(
(
n
nRnR
empemp
RempR
+?+≤ θθ
与VC维有关经验风险
6.3 结构风险最小化
?构造结构化的学习函数集：
.
21
LL
k
SSS
.
U
i
i
SS =
}.:),({
ii
xfS Θ= θ,
21
LL?Θ?Θ?Θ
k
]
1
[min
n
R
emp
S
h
+?+
6.3 结构风险最小化
?例：
? ={n阶多项式}
? ={n个中心的RBF}
? ={n个单元的多层感知机}
n
S
n
S
n
S
})(|{ nffS
n
≤Φ=
6.3 结构风险最小化
?给定序列,求解最优化问题：
LL <<<<
m
AAA
21
m
K
n
i
ii
f
Af
xfyL
n
≤
∑
=
2
1
))(,(
1
min
6.3 结构风险最小化
?对每个m,使下式最小
)())(,(
1
2
1
m
K
m
n
i
ii
AfxfyL
n
+
∑
=
λ
6.3 结构风险最小化实际中，给定使下式最小
m
λ
2
1
))(,(
1
K
m
n
i
ii
fxfyL
n
λ+
∑
=
6.3 结构风险最小化
SRM是一致相合的。
风险上界经验风险
h
n
h
Sn的VC维
1
h *h
S1
Sn
S*
“最优”学习函数集。
6.3 结构风险最小化
? SRM原则给出了在给定数据逼近的精度和逼近函数的复杂性之间的一种折中。
6.4 说明
6.4 说明
?用有限数量信息解决问题的基本原则：
在解决一个给定的问题时，要尽量避免把解决一个更为一般的问题作为中间步骤。
? Ockham’s razor:
? Williams of Ockham/Occam (1285-1347?);
? Ockham’s razor:,entities should not be
multiplied beyond necessity,.
参考文献
? [1] Vladimir N,Vapnik,Statistical Learning
Theory,John Wiley & Sons,Inc,1998.
? [2] Vladimir N,Vapnik,The Nature of Statistical
Learning,Springer-Verlag,New York,NY,1995
(中译本《统计学习理论的本质》，张学工译，
清华大学出版社，2000年9月)
? [3] Vladimir N,Vapnik,An overview of
Statistical Learning Theory,IEEE Trans,Neural
Networks,10 (5),988-999,1999.
