Learning Theory

如何形式化机器学习问题
问题 “learnable” 是什么含义
如何建立学习算法

Introduction to generalization

Aim: 收集数据 -> (训练)模型 -> (预测)未知数据

模型应该 fit unknown data

胡克定律 -> 用 simple model 去 fit data，but not simpler -> simple and fit well for unknown data

奥卡姆剃刀 -> 在所有 hypotheses 中，选择假设最少的那种

Probability Theory

Markov’s inequality
$P(X \geq{a}) \leq{\frac{E(X)}{a}}$
Chebyshev’s inequality
$P(|X-\mu| \geq{k\sigma}) \leq{\frac{1}{k^2}}$
大数定律
- $n \rightarrow \infty$，$X_{n} \rightarrow p$
- concentration property
- Q：收敛速度有多快？
  切比雪夫大数定律，$O(\frac{1}{n})$ 的速度收敛
中心极限定理：描述均值 $X_{n}$
$X_{n} \rightarrow N(\mu, \frac{\sigma^{2}}{n})$
Concentration Inequality: provide bounds on how a random variable deviates from some value

Chernoff Bound:

$Pr[|\bar{X} - p| \geq{\epsilon}] \leq{2\epsilon^{-2n\epsilon^2}}$
Other Bounds:

结论：这些不等式都得到了随着数据点数 n 的增长，均值以 $O(e^{-n})$ 的速度收敛于期望

VC Theory

Basic Notation

Input/Feature space: $\mathcal{X}$
Output/Label space: $\mathcal{Y}$
concept $\mathcal{c} : \mathcal{X} \rightarrow \mathcal{Y}$
concept class: $\mathcal{C}$
数据点 $\mathcal{x}$ 以分布 $\mathcal{D}$ 从 $\mathcal{X}$ 中生成
Loss: $\mathcal{l} : \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}$
hypothesis: $\mathcal{h} \in \mathcal{H}$

简单举例理解一下，一类神经模型架构可以理解为限定的假设空间 H ，而某个特定参数的该神经模型即是 h，训练的过程可以看作是在假设空间 H 中不断的寻找最优模型 h 的过程。

Generalization and empirical error

generalization error

$R(h) = Pr_{x\sim{D}}[h(x)\neq{c(x)}] = E(1\{h(x)\neq{c(x)}\})$

机器学习理论需要研究的是 generalization error

empirical error

$\tilde{R}_{S}(h) = \frac{1}{n}\sum_{i=1}^{n}1\{h(x_{i})\neq{c(x_{i})})\}$

注：这里我其实有点不懂，我查到的泛化误差的定义，
与这里不符。按照维基的解释，这里的泛化误差公式实际上应该是期望误差（expected error），而真正的泛化误差 = 期望误差 - 经验误差。

Probably Approximately Correct（PAC）learning

Goal: generalization error as small as possible

with high probability (the “probably” part), the selected function will have low generalization error (the “approximately correct” part) — from Wikipedia

Uniform Generalization

在具体实验中，我们的模型 $\mathcal{h}$ 是从假设空间 $\mathcal{H}$ 中挑选出来的，那我们应该挑选怎样的 $\mathcal{h}$ 呢。注意在训练的时候，我们只有训练数据集 $\mathcal{S}$ 可以使用。由于我们不清楚真实分布 $\mathcal{D}$ 是怎样的，因此没法得到泛化误差 $R(h)$。

一个直观的近似是训练集的经验误差 $\tilde{R}_{S}(h)$ ，按照 2. 中的论述，$\tilde{R}_{S}(h)$ 应该能以很快的速度逼近 $R(h)$。

$Pr(R(h) \geq \tilde{R}_{S}(h)+\epsilon) \leq \mathcal{e}^{-2n\epsilon^{2}}$

然而实际实验中我们观察到的并不是这样，在简单的数据集上，我们可以轻易的训练到 $\tilde{R}_{S}(h) = 0$ ，但此时在测试集上的表现非常差。问题出在我们在选择 $\mathcal{h}$ 时，考虑了训练数据集 $\mathcal{S}$，因此不满足 2. 中独立性的要求。

换个角度理解，如果在训练之前就固定了一个 $\mathcal{h}$（也就是参数都锁死不变），那么训练过后该 $\mathcal{h}$ 也依然是原样，没有用到任何训练集 $\mathcal{S}$ 的信息，那么此时就可以应用之前的公式，显然有 $\tilde{R}_{S}(h) \rightarrow R(h), n\rightarrow \infty$

出于这样的原因，我们不考虑某个 $\mathcal{h}$ 的泛化误差，而是转而考虑所有 $\mathcal{h}$ 的泛化误差的 bound，也就是考虑对整个假设空间 $\mathcal{H}$的泛化性描述，称作 Uniform Generalization。我的理解就是，直接考虑模型架构本身的泛化性能，与参数设定无关。