统计学习理论导论(清华大学张学工讲义)
平凡一致性:假设已经建立了某个函数集 Q(z,α ),α∈Λ,对这个函数集ERM方法是不一致的。考虑另一个扩展的函数集,它包括了这个函数集和一个额外的函数φ (z )。假设这个额外的函数满足不等式 inf Q ( z,α )>φ ( z ), z α∈Λ
严格(非平凡)一致性(Strict(Nontrival) Consistency):对函数集 Q(z,α ),α∈Λ,定义其子集如下:
Λ ( c )={α:∫ Q ( z,α )dF ( z )> c,
α∈Λ} . 如果对函数集的任意非空子集Λ (c), c∈ (∞,∞)都有 α∈Λ ( c )
显然对这个扩展的函数集来说,ERM方法就是一致的了。实际上,对任何分布函数和对任意数量的观测,经验风险的最小值都将在函数φ (z )上取得,而它也给出了期望风险的最小值。
inf Remp (α )→ inf R(α ) l→∞α∈Λ ( c )
P
(2-3)
成立,则我们说ERM方法对函数集 Q(z,α ),α∈Λ和概率分布函数 F(z)是非平凡一致的。
换句话说,一个ERM方法,如果把函数集中取得风险最小值的函数去掉后仍然能够满足(2-3)式的收敛关系,则这个ERM方法是非平凡一致的。可以证明,在严格一致性的情况下,条件(2-1)自动满足。 Xuegong Zhang Tsinghua University 7 Xuegong Zhang Tsinghua University 8
2.2学习理论的关键定理 (The Key Theorem) 定理2.1[Vapnik and Chervonenkis, 1989]设函数集 Q(z,α ),α∈Λ满足条件
A≤∫ Q ( z,α )dF ( z )≤ B
( A≤ R(α )≤ B )
,
那么,ERM原则一致性的充分必要条件是:经验风险 Remp (α )在函数集 Q (z,α ),α∈Λ上在如下意义下一致收敛于实际风险:
lim P sup(R(α ) Remp (α ) )>ε= 0,ε> 0 l→∞α∈Λ
.
(2-4)
一致单边收敛 (uniform one-sided convergence)换言之,ERM原则的一致性等价于(2-4)式的一致单边收敛成立。 Xuegong Zhang Tsinghua University
传统条件 lim P R (α ) R emp (α )>ε= 0 l→∞
对ERM原则的任何分析都必须是“最坏情况分析” 9
SLT条件
lim P sup(R(α ) Remp (α ) )>ε= 0,ε> 0 l→∞ α∈Λ 10
Xuegong Zhang Tsinghua University
ξ l= sup∫ Q ( z,α )dF ( z ) α∈Λ
1 l∑ Q ( zi,α ), l= 1,2, L l i=1
2.3
一致双边收敛的充分必要条件
Necessary& Sufficient Conditions of Uniform Two-sided Convergence关键定理把ERM方法一致性的问题转化为了一致收敛的问题(一致单边收敛)。为讨论一致单边收敛的条件,先讨论一致双边收敛问题。
2.3.1大数定律(The Law of Large Numbers)及其推广 1.大数定律:随着样本数目的增加,随机变量的均值收敛于其期望(如果期望存在的话)。 l若函数集 Q (z,α ),α∈Λ中只包含一个元素,则ξ l→ 0→∞ P
经验过程(empirical processes) 双边经验过程:ξ l= sup Q ( z,α )dF ( z ) 1∑ Q ( zi,α ), l= 1,2, L∫ l i=1α∈Λ一致双边收敛: lim Pξ l>ε= 0,ε> 0 l→∞ l
2.向量空间中的推广:如果函数集 Q (z,α ),α∈Λ包含有限个元素,则 (2-5) (2-6) (2-7) (2-8) 11
{
}
ξl→ 0 l→∞
P
3.是否存在泛函空间中的大数定律?(Law of Large Numbers in Functional Space) l当函数集中包含无限多个元素时,是否ξ→ 0? l→∞ P
l单边经验过程:ξ+l= sup Q ( z,α )dF ( z ) 1∑ Q ( zi,α ),
l= 1,2, L∫ l i=1α∈Λ+
一致单边收敛:
l lim Pξ+>ε= 0,ε> 0 l→∞
{
}
即,一致双边收敛和一致单边收敛的充分必要条件是什么?
——需考察函数集的性质 Xuegong Zhang Tsinghua University Xuegong Zhang Tsinghua University
函数集的熵
12






统计学习理论导论-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页 免费...
热门文档