Preliminaries

• Domaim set : 一个任意的想进行 label 的集合

• Label set . 后续为了方便一般都会用二分类来讨论一些内容.

• Training Data: 有限集 , 或者记作 .

• 一个 learner 的目标是要得到一个 predictor/hypothesis/prediction rule/classifier . 用 表示算法 在数据集 上训练得到的 predictor, , 其中 是参数空间.

• 数据的生成: 我们总是假定 上有一个 unknown distribution ,目前我们认为存在一个绝对正确的 使得对 中每一对 sample 都有 , 称之为 concept, 于是数据的生成是 i.i.d 地从 上采样并以 标注.

• 用 error/risk 来衡量 learner 是否很好地完成了学习的任务, 这称为 generalized error/ true error, 定义为: predictor 的 error 从 中随机采样 且 的概率. 更正式地, 给定 和概率分布 , 符号 表示观察到某个 满足 的可能性大小, 因此在很多情况下我们会认为 是事件, 并定义 且 , 因此

  原书中许多地方的证明过程都是用 来表示概率的, 为了与概率论相契合, 我们只用 来表示概率.

• learner 关于 是一无所知的, 它只能从训练集中获取信息.

• 一个好的 learner 需要有足够小的 generalized error, 但是由于对 和 一无所知, 只能计算所谓的 empicical error/risk, 定义为 任务替换为最小化 empicical risk , 称为 ERM Rule (经验风险最小化). 我们的终极目标是训练一个具有较小 test loss 或者 population loss 的一个模型.

总结下来就是:

有关符号的说明:

• 或者 都表示在训练集上学习到的模型
• 都表示 training loss
• 都表示 test loss
• 为了方便, 当上下文不出现损失函数的时候或者我们不关心损失函数时, 也可以不用手写体 表示上述 loss, 直接用 , 有时候可能也会用 , 但是会尽量保证符号统一.
• 有 hat 符号 一般都是和训练集相关的内容.
• 假设空间 有时候也会写成函数空间 , 两者是等价的.
• 一般会代指训练集的大小, 一般会指数据的维度.
• 是 distribution, 为了方便, 有时或者大部分时候也不用手写体, 而是使用 .

ERM Rule

ERM rule 会出现过拟合即 小而 大的情况. 我们自然想知道在什么条件下 ERM 不会出现过拟合, 即 ERM predictor 不仅在训练集上表写好, 在 underlying data distribution 上也能表现好的条件.

一个解决过拟合的方法是限制 来限制 predictor 可选的范围. 给定 , 一个 learner 使用 ERM rule 以 上最小可能的误差来选择一个 , 即 , 这里也说明了 . 当限制了 时, 我们对某些特定的 predictor 产生了偏好 (bias), 这样的限制经常称为 inductive bias.

Learning Theory 中的一个基本的问题是在什么样的 下 不会出现过拟合.

在措辞上, 更严格的说法是 “ 一个 learner 是否会出现过拟合”, 为了方便表述, 后文会略去 learner. 符号 可以认为是 的一个元素或者一个子集, 也可以认为是返回或输出一个 的算法, 这个/些元素 满足 最小.

Finite

有限集是最直接的一种限制, 后文将会证明, 当 是有限集时, 在充分大的训练集 (大小和 相关) 的条件下不会出现过拟合.

我们需要先做一些假设.

The Realizability Assumption 存在 s.t. .

这个假设表示对于随机的 ( 采样自 以 标注), w.p. .

由于 是随机采样得到的, 我们无法保证通过 一定能学到一个好的 predictor, 因为总是有可能采样到的数据恰好不能很好地表征 . 我们把采样到“不好的 (不够具有代表性的)” 的概率记作 , 称 为我们预测的置信度 (confidence parameter).

由于我们无法保证做到完美的预测, 因此有必要引入 accuracy parameter , 并且认为 时 predictor 是 “失败的”, 而 时 predictor 被认为是近似正确的.

记 表示训练集 ( 表示样本用字母 表示, 后文会略去, 并默认由 表示) , 现在想给一个训练集 预测失败的概率 一个上界.

下面简述求解思路.

考虑 中一些不好的假设 即 , 将它们的集合记作 . 然后一定存在一些 , 使得 虽然是不好的, 但是能够完美地拟合 , 即 , 将这些 的集合记作 . 显然在 上能通过 ERM Rule 学习出的满足 的 , 一定是 中的元素, 且 realizability assumption 表明 , 那么这就意味着事件 发生的充分条件是 .

A Formal Learning Model: PAC Leaning

PAC Learning 的全称是 probably approximately correct learning.

PAC learning 实际上是在研究 sample complexity 的问题, 就是在 的置信度下, 以 的 acc 需要多少样本, 并且什么样的 (在 PAC Learning 的框架下) 是可以学习的. 严格的定义如下:

定义 1 (PAC Learnability) 假设空间 是 PAC learnable 的, 如果存在 使得存在满足下面性质的算法 :

• 对任意 , 对任意 上的分布 , 对任意 , 若 realizable assumption关于 成立, 那么在 个 i.i.d. 的且以 标注的样本所构成的训练集上运行算法 时, 算法 会以至少 的概率返回一个满足 的条件的 .

PAC Learning 的定义中包括两个 approximation parameter, 其中 决定了输出的分类器距离最优的分类器有多"远" (approximately correct), 它允许赦免分类器的少量错误; 表明了分类器有多大的可能满足准确率的要求 (probably) .

决定了学习 所需要的 sample complexity, 即需要多少样本可以保证一个 PAC 的解. 当 时, 是 PAC Learnable 的, 且样本复杂度满足

Agnostic PAC Learning

realizability assumption 是很强的假设, 中不一定存在一个完美的 使得 . 同时 label 不一定完全由已知的特征决定.

在接下来, 被定义为 上的联合分布, 接着定义 上的边缘分布 和 上的条件分布 . 然后上述 的定义依据联合分布进行修正.

The Bayes Optimal Predictor 给定 上的 , 则 是一个最优的 的 predictor. 即对所有分类器 都有 .

如果对数据生成的分布不做任何先验的假设, 则不存在任何算法可以得出一个和 Bayes predictor 一样好的 predictor.

定义 2 (Agnostic PAC Learnability) 是 Agnostic PAC Learnable 的, 如果存在 以及一个满足下述条件的算法 :

• 对任意 , 每一个 上的分布 , 当在 个 i.i.d. 的样本上运行 时, 返回一个 满足 以至少 的概率成立.

的条件其实是非常强的, 当放松这个条件后, 可以得到 Agnostic PAC Learnability 的定义, 与 PAC Learnability 基本完全一致, 除了不需要 realizable 假设以及算法 需要返回的是满足 的 以及分布是 的联合分布而不是 上的分布.

agnostic 的意思是 “不可知的”.

loss function 的严格定义是 . 对于预测问题, , 并且认为 是一个随机变量, 这要求它可测, 此时 , 以及 , 其中 . 然后就很容易得到 Agnostic PAC Learnability 在这种一般定义下的 loss function 的定义.

Learning via Uniform Convergence

任意有限的 都是 PAC Learnable 的, 这里引入一个新的更 general 的工具 uniform convergence, 用来展示任意有限的 在 agnostic PAC model 的框架下以及损失函数时一般的损失函数也是可学习的, 只要 range loss function 有界.

存在一个很好的训练集 , 使得 中的每个元素都具有很好的泛化误差

VC Dimension

有限的 hypothesis class 是可学习的, 而由所有函数构成的类是不可学习的, 那自然就想问决定一个类是否可学习的条件是什么. 我们先探究一些 infinite hypothesis class.

举一个简单的例子, 设 , 其中 是一个阈值函数. 则 在 REM Rule 下是 PAC learnabel 的, 且样本复杂度满足 . 我们证明这一事实.

Proof. 我们考虑 realizable assumption 成立的情况, 即存在 , 使得 . 设 是 在 上的边缘分布, 这里 , 于是原问题是一个二分类问题. 首先对当 满足一定条件时:

• 当 且 时, 一定存在 满足 使得

• 当 时, 令
• 当 时, 令

确定 之后, 考虑一个数据集 . 令 , 倘若不存在标签为 的样本, 令 ; 令 , 倘若不存在标签为 的样本, 则令 . 设 是在 上通过 ERM rule 学到的阈值, 相应的 hypothesis 记作 , 由 ERM Rule 我们知道 , 于是必然有 , 以确保所有的正样本落在 中, 所有的负样本落在 中, 来保证经验误差为 0. 我们现在来计算 的泛化误差: 这里 的含义是 介于 和 之间. 我们想让泛化误差 , 只需要让 落入 中即可, 而我们又知道 , 于是 的充分条件是 且 , 因此 第二个不等号用到了 Union Bound, 即对于一系列事件 , 有 并且略去了 下方的 . 我们知道 中的样本是独立同分布的, 要使 , 只需要让所有样本都不落入 中即可, 令 , 这里用到了不等式 . 当 时, 显然有 , 于是有 . 同理有 , 因此在 的条件下, 这也就意味着在这样的样本复杂度的条件下, 成立的概率至少是 , 这就是 PAC learnable 的定义, 也就完成了证明.

这个例子中的 是无限的, 但它却是可学习的, 说明 finite hypothesis class 只是可学习的充分非必要条件. 为了知道什么样的 是可学习的, 我们可以考虑给一个衡量 的复杂程度的 measurement, 这是因为从直观上来看越复杂的 越 "不易学习". 接下来我们用 "打散(shatter)" 这个概念来给 的复杂程度一个衡量标准.

定义 1 (打散, shatter, informal) 对于 的任意一个有限的子集 , 也就是一个(目前没有标签的)数据集, 考虑二分类问题, 即样本的标签为 , 如果我们不限制标签, 那么 根据标签的不同总共有 种, 或者说, 可以用 所有的元素来作为给 打标签的 ground truth. 如果对任意 , 给 打上标签后, 都存在 能够完美拟合 , 即 , 那么就称 能够打散 (shatter) .

定义 2. (VC dimension) 的 VC Dimension, 记作 , 定义为 , 即 中能被 打散的有限子集的最大基数.

为什么定义打散并通过打散来定义 的 VC dimension 呢? 可以借助线性函数与多项式函数对一系列点的拟合来理解 (也就是一个回归问题). 设在坐标系上有 个(不共线的)点, 无论怎么挑选线性函数, 都不可能找到一条直线同时经过这 个点, 但是对于 的多项式函数而言, 很容易就能找到一个这样的多项式函数, 同时经过这 个点. 这正印证了所有线性函数构成的集合的在拟合能力这一点上, 是不如多项式函数的, 也就是线性函数类的"复杂程度"不如多项式函数类. 能够打散 , 说明了不管 中样本的标签怎么变化, 中都存在一个假设能够拟合 , 说明 本身足够复杂, 越大则越说明 更复杂. 所以我们才使用 中能被 打散的有限子集的最大基数来定义 VC dimension, 作为衡量 hypothesis class 的复杂程度的一个 measurement.

如果 可以打散任意大的集合, 就称 .

我们在这里联合没有免费的午餐定理 (No free lunch theorem) 给出一个推论. No free lunch theorem 的严格表述如下:

定理 1. (No Free Lunch) 设 表示任意一个学习算法, 它接收一个样本集合返回一个 hypothesis. 对于 上的二分类问题 (标签为 ), 对任意一个满足 的样本数, 存在一个 上的分布 , 使得:

1. 存在 使得 , 即存在一个泛化误差为 0 的 ground truth;
2. 在样本集合 上, 以至少 的概率成立.

No Free Lunch theorem 是在说不存在一个通用的学习器 (或者说学习算法) 可以在所有的学习任务上都表现的很好. 上面的定理就是说存在一个分布使得任意一个学习器学习出的的泛化误差都有不小的概率有一个下界, 这是学习器失败的表现, 但是同样存在另一个学习器可以成功学习这个分布, 或者说任务. 我们现在给出一个推论:

推论 1. 设 , 是训练集的大小, 假设存在一个大小为 的集合 能被 打散, 则对任意学习算法 , 都存在一个分布 和 使得 但是 以至少 的概率成立, 其中 .

这个推论是在说如果 能够打散大小为 的集合, 则没有算法能通过大小为 的集合来学习 . 这是个很自然的推论, 因为当 足够复杂的时候, 比如神经网络, 样本数量太少将造成欠拟合. 还有另一种解释方法, 如果对于某个能被 打散的 , 我们只能得到 中一般的样本, 那么这一半的样本对于我们预测 中另一半的样本的标签没有任何帮助, 因为对于另一半样本, 不管是哪一种标签组合, 里都能找到一个与之对应的 hypothesis. 从哲学上讲, 如果有人可以解释所有现象, 那么他的解释本身就是毫无意义的.

时是一定 PAC learnable 的, 其实甚至可以不用学习的方法直接穷举 即可. 那 时就一定不可学习吗? 事实上 时也是 PAC Learnable 的.现在我们可以通过 VC dimension 给出一定不可学习的 hypothesis class 了.

定理 2. 若 满足 , 则 不是 PAC learnable 的.

下面我们给出一些常见的 hypothesis class 的 VC dimension:

• 阈值函数 (即文章最开始的例子中提到的) 类的: .
• 区间函数 () 类:
• 平行于坐标轴的矩形函数类: .
• 有限 hypothesis class: .

The Fundamental Theorem of PAC Learning

现在不加证明地给出统计学习的基本定理.

定理 3. (统计学习基本定理) 设 , 是 0-1 loss, 则下述命题等价:

• 具有一致收敛性
• 是 PAC learnable 的
• 是 Agnostic PAC learnable 的
• .

这可以同时由 VC dimension 给出定量形式, 设 , 则样本复杂度在满足

1: 时, 具有一致收敛性.

2: 时, 是 Agnostic PAC learnable 的.

3: 时, 是 PAC learnable 的, 其中 是两个常数.

那为了确保不出现过拟合, 我们需要 bound .

generalization gap 定义为 , 于是 最小化 的目标转化为最小化 generalization gap 和 training loss (optimization error).

No-Free-Lunch

no free lunch 是在说, 不存在一个算法 , 存在一个对抗分布 , 使得即使存在一个好的 predictor, 也会很大概率找不到这个 predictor.

传统统计模型

主要回顾线性模型和广义线性模型.

参数模型 (parameter model) 的定义是: 一个可学习的可以被有限维参数给 index 住的模型.

线性模型是 , 其中 是 ground true. 可以学习一个 linear classifier , 这是有限维的, 所以该线性模型被 给 index 住, 它是参数模型.

学习一个模型实际上是给参数一个估计, 我们希望这个参数满足 consistency, 即 时需要有 .

对于线性模型而言, 当考虑最小二乘法时, , , , 可以证明它是 unbiased 且满足 consistency, 证明 consistency 时除了求 以外, 也可以求 . 现在对 进行研究: 其中第一项就是 bias, 第二项是 variance. 如果采取 作为估计量的话, 有可能会碰到 的某一个特征值非常小的情况, 这就会导致 是 unbiased 但是有很大的 variance, 这就导致整体的误差 偏大. 所以可以考虑找一个 biased 但是具有较小的 variance 的量, 使得 整体不太大, 这就是岭回归的 intuition, 即 . 此时 但具有更小的 variance term, 事实上存在 , 在某些很松的假设下, .

岭回归还有其他的 intuition, 比如:

• 在 loss 上增加惩罚项
• 保证求逆时数值稳定

广义线性模型

当假设 时, , 这样不够灵活, 如果有先验 或者 这样假设就不是很好的选择.