专栏名称: 机器学习研究会

机器学习研究会是北京大学大数据与机器学习创新中心旗下的学生组织，旨在构建一个机器学习从事者交流的平台。除了及时分享领域资讯外，协会还会举办各种业界巨头/学术神牛讲座、学术大牛沙龙分享会、real data 创新竞赛等活动。

【干货】计算学习理论

机器学习研究会 · 公众号 · AI · 2017-05-03 20:29

正文

点击上方“机器学习研究会”可以订阅哦

摘要

转自：王的机器

引言

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

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

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

胡碧才是胡逼猜，用丢硬币得出 0 和 0
斯蒂文是王圣元，用支持向量机得出 1 和 0
孟榨田是猛炸天，用 10 层神经网络得出 1 和 1

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

c(x) = x1 ⋁ x2 ：孟砸田完胜

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

c(x) = x1 ⋀ x2 ：胡碧才完胜

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

c(x) = x1：斯蒂文完胜

第 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 增长函数上界

第一章 - 前戏王

1.1

总体和样本

在统计中，把研究对象的全体称为总体，而把组成总体的各个元素称为个体，把从总体中抽取的若干个体称为样本。举个调查中国男性平均身高的例子，全国的男性就是总体，每个男性是个体。有时候普查所有男性金钱花费和时间成本太高，通常我们会抽取若干男性作为样本。我们计算样本里的男性平均身高作为总体里的所有男性平均身高的推理 (inference)。