统计学习理论导论(清华大学张学工讲义)
2.3.2指示函数集的熵 目标:建立考查函数集性质(能力)的指标考查指示函数集 Q (z,α ),α∈Λ和样本z1, L, z l。定义: NΛ ( z1, L, z l ):用指示函数集中的函数能够把给定的样本分成多少种不同的
2.3.3实函数集的熵 定义:
分类。
用这个量来表征函数集在给定的数据集上的多样性。
A≤ Q ( z,α )≤ B,α∈Λ是一个有界损失函数集合。用这个函数集和训练集 z1, L, zl,可以构造下面的 l维向量集合: q(α )= (Q ( z1,α ), L, Q ( z l,α )),α∈Λ . (2-9)这个向量集合处在 l维立方体之中,并且在C度量(或在 L p度量)下有一个有限的最小ε-网格。令 N= NΛ (ε; z1, L, zl )是向量集 q(α ),α∈Λ的最小ε网格的元素数目。 随机ε-熵: HΛ (ε; z1, L, zl )= ln NΛ (ε; z1, L, z l ) VC熵:
随机熵: HΛ ( z1, L, z l )= ln NΛ ( z1, L, z l ) --函数集在给定数据上的多样性 Random Entropy
VC熵: HΛ (l )= E ln NΛ ( z1, L, z l ) VC Entropy
--函数集在数量为l的样本上的熵
HΛ (ε; l )= EHΛ (ε; z1, L, z l ) NΛ (ε; z1, L, z l )= NΛ ( z1, L, z l )
ε显然:指示函数集可以看作是实函数集的特例,对指示函数集,< 1有: HΛ (ε; z1, L, z l )= HΛ ( z1, L, z l )
Xuegong Zhang Tsinghua University
13
Xuegong Zhang Tsinghua University
HΛ (ε; l )= HΛ (l )
14
2.3.4一致双边收敛的条件 定理2.3[Vapnik and Chervonenkis, 1981]一致双边收敛 lim Psup Q( z,α )dF ( z ) 1 l→∞
2.4
一致单边收敛的充分必要条件 1 l lim P sup∫ Q( z,α )dF ( z )∑ Q( z i,α )>ε= 0,ε> 0 l→∞ l i=1α∈Λ
Necessary& Sufficient Conditions of Uniform one-sided Convergence
∫α∈Λ
l
∑ Q( z,α )>ε= 0, i=1 i
l
ε> 0
的充分必要条件是 lim l→∞
HΛ (ε, l )= 0,ε> 0 l
.
(2-10)
lim P sup(R (α ) Remp (α ) )>ε或 sup(Remp (α ) R (α ) )>ε = 0 α l→∞ α
即,随着观测数目的增加,VC熵与观测数目的比值应该趋近于零。推论[Vapnik and Chervonenkis, 1968, 1971]指示函数集 Q ( z,α ),α∈Λ一致双边收敛的充分必要条件是 HΛ (l ) lim=0 l→∞, l这是(2-10)的一个特例。 Xuegong Zhang Tsinghua University
一致双边收敛包含了一致单边收敛,因此,一致双边收敛是ERM方法一致性的一个充分条件。
充分必要条件?
提示:相对于样本数目来说,学习机器的能力不应太强。 15
Xuegong Zhang Tsinghua University
16
定
理2.4[Vapnik and Chervonenkis, 1989]对完全有界函数集Q ( z,α ),α∈Λ,经验均值一致单边收敛于其期望的充分必要条件是:对任意的正δ,η和ε,存在一个函数集Q * ( z,α * ),α *∈Λ*,使得 1.对任意函数 Q ( z,α ),存在一个函数Q * ( z,α * ),满足:
2.5, 2.6用不可证伪性理论对一致性条件的说明 两种推理模型(two models of reasoning):–演绎(deduction):从一般到特殊–归纳(induction):从特殊到一般如何区分正确的(科学的)归纳与不正确的归纳?–如何区分科学的(一致的)学习与不一致的学习?波普(Popper)的不可证伪理论(Theory of Nonfalsifiability):–一个理论可以被证实(可能成为真理论)的必要条件是它存在被证伪的可能性(从逻辑上存在推翻它的可能)定理2.6[Vapnik and Chervonenkis, 1989]设对一致有界实函数集合 Q (z,α ),α∈Λ,存在一个ε 0,使得 HΛ (ε 0, l ) lim= c*> 0 l→∞ l那么采用这个函数集的学习机器是潜在不可证伪的。 Xuegong Zhang Tsinghua University
Q ( z,α ) Q * ( z,α * )≥ 0, z,
∫ (Q ( z,α ) Q lim l→∞
*
( z,α * )) dF ( z )≤δ .
(2-12)
* * * * 2.函数集 Q ( z,α ),α∈Λ在l个样本上的VC熵满足下面的不等式:
HΛ (ε, l )<η l
*
.
(2-13)
根据关键定理,这也是ERM方法一致性的充分必要条件。
结论: ERM学习过程一致的条件是:相对于样本数目来说,学习机 17器的能力不应太强。
Xuegong Zhang Tsinghua University
z
18






统计学习理论导论-6 6页 免费 统计学习理论导论-4 6页 免费 统计学习理论导论-2 6页 免费 统计学习理论导论-5 3页 免费 统计学习理论导论-7 5页 免费...
统计学习理论导论-2 统计学习理论导论-3 统计学习理论导论-4 统计学习理论导论-5 统计学习理论导论-6 统计学习理论导论-7 统计学习理论导论-10...
统计学习理论导论-2 6页 免费 统计学习理论导论-4 6页 免费 统计学习理论导论-6 6页 免费 统计学习理论导论-3 4页 免费 统计学习理论导论(清华大学... 6...
统计学习理论导论-6 6页 免费 统计学习理论导论-2 6页 免费 统计学习理论导论-5 3页 免费 统计学习理论导论-3 4页 免费 统计学习理论导论-4 6页 免费...
统计学习理论导论(清华大学... 6页 免费 统计学习理论导论-5 3页 免费 统计学习理论导论-4 6页 免费 统计学习理论导论-6 6页 免费 统计学习理论导论-3 4...
统计学习理论导论-4_经管营销_专业资料。统计学习理论导论(清华大学张学工讲义)...(相对于经验风险) 学习机器的推广能力 Xuegong Zhang Tsinghua University 3 3....
统计学习理论导论-4 6页 免费 统计学习理论导论-5 3页 免费 统计学习理论导论-2 6页 免费 统计学习理论导论-3 4页 免费 统计学习理论导论(清华大学... 6...
统计学习理论导论-9 rtrt隐藏>> 6.1 线性SVR原问题 第六章 用于函数估计的...Xuegong Zhang Tsinghua University 3 Xuegong Zhang Tsinghua University 4 实际是...
统计学习理论导论-6 6页 免费 统计学习理论导论-5 3页 免费 统计学习理论导论-2 6页 免费 统计学习理论导论-10 9页 免费 统计学习理论导论-7 5页 免费...
28页 免费 统计学习理论导论-6 6页 免费 统计学习理论导论(清华大学... 6页 免费 统计学习理论导论-3 4页 免费 统计学习理论导论-4 6页 免费...
热门文档