【干货】计算学习理论

胡碧才 ， 斯蒂文 和 孟榨田 都是玩机器学习的，他们都觉得自己的模型厉害谁也不服谁。有一次他们来一场比赛，他们三个人的模型在前两个数据训练数据上表现非常好，模型的输出完全和样例真实标记一样。

其中 x = [x1, x2] 里面都是布尔型变量 (boolean variable)。

训练数据表现好不算什么，判断模型真的好坏还是要看在后两个测试数据上的表现，让人惊讶的是，他们三人在测试集上的结果完全不同。

• 胡碧才 是 胡逼猜 ，用丢硬币得出 0 和 0

• 斯蒂文 是 王圣元 ，用支持向量机得出 1 和 0

• 孟榨田 是 猛炸天 ，用 10 层神经网络得出 1 和 1

仅仅看他们的模型， 孟榨田 水平应该高于 斯蒂文 高于 胡碧才 ，真是这样吗？现在假设 y 和 x 的真实函数 y = c(x) 关系是：

• c(x) = x 1 ⋁ x 2 ： 孟砸田 完胜

• 第 3 个 x = [1, 0]，因此 y = 1⋁0 = 1

• 第 4 个 x = [0, 1]，因此 y = 0⋁1 = 1

  
  

• c(x) = x 1 ⋀ x 2 ： 胡碧才 完胜

• 第 3 个 x = [1, 0]，因此 y = 1⋀0 = 0

• 第 4 个 x = [0, 1]，因此 y = 0⋀1 = 0

  
  

• c(x) = x 1 ： 斯蒂文 完胜

• 第 3 个 x = [1, 0]，因此 y = 1

• 第 4 个 x = [0, 1]，因此 y = 0

阳春白雪来 讲，这个是机器学习中的“无免费午餐” (no free lunch, NFL) 定理，即所有算法，无论高级初级，它们的期望表现相同！下里巴人来讲，一切脱离具体问题来讨论机器学习算法优劣的行为都是耍流氓。

注：NFL 定理的推导见附录 1

现在所有机器学习痴迷者有没有一种冷水浇头的感觉：

• 既然 胡逼猜 和 猛炸天 的模型期望表现相同，哪还有什么可学的？

• 既便 猛炸天 比 胡逼猜 模型表现要好，真实函数 c 是未知的，完美预测样本内数据对预测样本外数据没有什么帮助！只有样本外的表现才是真正的学习，但样本外又是未知的。机器学习是个骗局吗？

如果机器学习没什么可学或是骗局，那就好了，我也不用呕心沥血的研究它了。幸运 (或不幸) 的是，机器学习是可学或可行 (feasible) 的，但是需要从概率的角度来把玩它。

目录

第一章 - 前戏王

1.1 总体和样本

1.2 二分类问题

1.3 对分

1.4 增长函数

1.5 打散和突破点

1.6 联合上界

第二章 - 理论皇

2.1 学习心路历程

2.2 从已知到未知

2.3 从民调到学习

2.4 从单一到有限

2.5 从有限到无限

2.6 从无限到有限

第三章 - 实践王

3.1 VC 不等式

3.2 VC 维度

总结和下帖预告

附录

1 NFL 定理

2 霍夫丁不等式

3 增长函数上界

注：小节 2.2 会用 到