本文主要是介绍Foundation of Machine Learning 笔记第五部分 (2) —— Rademacher Complexity 和 VC 维,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
注意事项:
这个系列的文章虽然题为书本《Foundation of Machine Learning》的读书笔记,但实际我是直接对书本的部分内容进行了个人翻译,如果这个行为有不妥当的地方,敬请告知。 由于知识面限制,部分名词的翻译可能存在错误,部分难以翻译的名词保留英文原词。为了防止误导大家,在这里声明本文仅供参考。 本文基本翻译自《Foundation of Machine Learning》的3.1节。
正文
接下来的内容将关系到假设集 H 的 empirical Rademacher complexity 和与 H 相关的二元损失函数族 G ( 我的补充 :如上一步所提出的,损失函数族 G 是基于假设集 H 定义的,已知假设是一个从 X 映射到 Y 的函数,而损失函数 L 是从 Y × Y 映射到 R 的函数,把上面这两个映射结合起来得到一个新的损失函数的定义 g : ( X × Y ) → R ,用函数的形式表达,也就是 g ( x , y ) = L ( h ( x ) , y ) 。而二元损失函数是取值只为 0 或者 1 的损失函数,本节把映射 L 定义为 1 h ( x ) ≠ y 这个函数 ) 。
引理 3.1
用 H 代表一族在 { − 1 , + 1 } 上取值的函数,用 G 代表一族与 H 相关的二元损失函数: G = { ( x , y ) ↦ 1 h ( x ) ≠ y : h ∈ H } 。对于任意的在空间 X × { − 1 , + 1 } 中取样的样本集 S = ( ( x 1 , y 1 ) , … , ( x m , y m ) ) ,用 S X 表示这个样本集到空间 X 上的投影: S X = ( x 1 , … , x m ) 。那么, G 和 H 的 empirical Rademacher complexity 满足以下关系 ( 我的理解 :注意Rademacher complexity 是一种描述函数族性质的量):
R ^ S ( G ) = 1 2 R ^ S X ( H ) . (3.16)
证明 对于空间 X × { − 1 , + 1 } 中的任意样本集 S = ( ( x 1 , y 1 ) , … , ( x m , y m ) ) ,通过定义, G 的 empirical Rademacher complexity 可以写成:
R ^ S ( G ) = = = = E σ [ sup h ∈ H 1 m ∑ i = 1 m σ i 1 h ( x i ) ≠ y i ] E σ [ sup h ∈ H 1 m ∑ i = 1 m σ i 1 − y i h ( x i ) 2 ] 1 2 E σ [ sup h ∈ H 1 m ∑ i = 1 m − σ i y i h ( x i ) ] ( σ i 的 数 学 期 望 为 0 ) 1 2 E σ [ sup h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) ] = 1 2 R S X ( H ) ,
这里我们使用了两个事实:
1 h ( x i ) ≠ y i = ( 1 − y i h ( x i ) ) / 2 ,以及对于固定的
y i ∈ { − 1 , + 1 } ,
σ i 和
− y i σ i 是相同的分布 ( 都是在
{ − 1 , + 1 } 上取值、期望为 0 的均匀分布 )。证毕。
值得注意的是,通过取两边的数学期望,这个引理意味着对于任意 m ≥ 1 , R m ( G ) = 1 2 R m ( H ) 。这种 empirical Rademacher complexity 和 average Rademacher complexity 之间的关系可以用以引出二分类问题使用了假设集 H 的 Rademacher complexity 的泛化上限。
定理 3.2 Rademacher complexity bounds ——二元分类 用 H 表示一族从 { − 1 , + 1 } 中取值的函数,用 D 表示输入空间 X 上的分布。那么,对于任意 δ > 0 ,下列不等式在一个从 D 中抽取 m 个样本构成的样本集 S 上,对于任意假设 h ∈ H ,至少有 1 − δ 的概率成立:
R ( h ) ≤ a n d R ( h ) ≤ R ^ ( h ) + R m ( H ) + log 1 δ 2 m − − − − − √ R ^ ( h ) + R ^ m ( H ) + 3 log 1 δ 2 m − − − − − √ . (3.17) (3.18)
证明 由定理 3.1 和引理 3.1 直接得证。要注意的是,根据上述定义的二元损失函数
g ( z ) = 1 h ( x i ) ≠ y i ,定理 3.1 中的
E [ g ( z ) ] 等于泛化误差
R ( h ) ,同理,
1 m ∑ m i = 1 g ( z i ) 这一项等于经验误差
R ^ ( h ) 。
这个定理为二元分类提供了基于 Rademacher complexity 的泛化上限。注意 (3.18) 中的上限是只依赖于样本数据的:empirical Rademacher complexity R ^ m ( H ) 是关于某个从 D 中抽取出来的特定样本集的函数。因此,只要我们能计算 R ^ m ( H ) ,这个上限完全可以算出。但是我们要怎样才能算出 empirical Rademacher complexity 呢?通过 σ i 和 − σ i 是相同分布这个事实,我们可以写出
R ^ m ( H ) = E σ [ sup h ∈ H 1 m ∑ i = 1 m − σ i h ( x i ) ] = − E σ [ inf h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) ] .
那么,对于固定的值
σ ,计算
inf h ∈ H 1 m ∑ m i = 1 σ i h ( x i ) 等价于一个经验风险最小化问题 (
empirical risk minimization ),而这个问题对于某些假设集来说是计算上很复杂的问题 ( 因为需要把每一个假设都带进去试才能得到最小值,所以这是个 NP 难问题 )。因此,
R ^ m ( H ) 是一个计算复杂的问题。在下一部分中,我们将把 Rademacher complexity 联系到组合测度 (
combinatorial measure ,可能是测度论中的概念 ) 上去,而组合测度更加容易计算。
这篇关于Foundation of Machine Learning 笔记第五部分 (2) —— Rademacher Complexity 和 VC 维的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!