TheoreticalML

理论机器学习

我们探索几个本质问题：

1. 使学习成为可学习/不可学习的学习问题的内在属性是什么？

2. 需要多少个样本才能学习一个特定的概念？

3. 为什么简单的假设比复杂的假设更好？

4. 如何定义一个合理且可实现的在线学习目标？

统计学习模型的元素包括：

1.输入：域X、标号集Y，样本集 S = {(x1, y1), . . . ,(xn, yn)} ⊆ X × Y .

S是从独立同分布的样本中得到。

2.输出：假设 h : X → Y

3.数据生成：f : X → Y

4.性能指标：例如 err(h) = Px∼D [h(x) != f(x)] = Ex∼D[|h(x) − f(x)|]

几个概念：

1.经验风险 (Empirical Risk) 和过拟合(Over-fitting)

2.样本复杂度(Sample complexity, 拥有良好泛化能力所需的样本数)和泛化能力(Generalizability).

3.大概近似正确(probably approximately correct)：下一篇讲。

一个定理：

含义：给定标记域的数据（独立同分布），如果样本足够多，那么最小化经验风险算法将对未知数据表现良好。要想得到关于所需样本数目的有意义的理论保证，我们需要知道假设类别（hypothesis class）的规模和其他自然参数。

意义：

1.域D和假设类别H是不受限制的。

2.样本复杂度与假设类别的规模成对数关系。

不足：

1.H的选取太讲究：基于可实现性假设。

2.这个定理假设数据是干净的，并且没有对噪音数据的处理。

3.H必须是有限的。

4.样本需要是独立同分布的。

5.这个定理解释了样本复杂度，但没有解释计算复杂度。

6.这个定理假设样本是批量来的（批学习），没有对样本一个一个来的情况（在线学习）的处理。