2018-06-30以问答的方式，做了文章的笔记。
❶ 给出问题，一问是否可解，二是如何解？频率学派和贝叶斯学派都在讲如何解，即回答问题二。那是否可解，但往往不是非此即彼，更多的问法，是在投入计算资源之前，先评估一下机器学习能够学到说明什么程度？(就如软件工程中可行性分析)
答：所以，有了“计算学习理论”来回答这个问题。
❷ 那时什么是“计算学习理论”呢？从一个例子入手，5个三维(0/1)输出，预测3个数据，用机器学习训练，发现，“不管生成机制到底如何，训练数据都没有给出足以决定最优假设的信息。” 那机器学习在学习什么呢？
答：“概率”,不能给出最优解，可以给出近似解啊！
❸ 第二个例子：“红球与白球”，既然用“概率”工具，那么用 ν 来近似 μ 有多高的精确度呢？有没有理论支撑？
答：可以用“Hoeffding不等式”回答，“Hoeffding不等式”描述了训练误差和泛化误差之间的近似关系。
训练误差是模型在训练集上的误差，泛化误差是用来衡量模型的泛化性。
结论是总会存在一个足够大的样本容量 N 使两者近似相等，这时就可以根据模型的训练误差来推导其泛化误差，从而获得关于真实情况的一些信息。
❹ 现在有了“概率”工具，说明问题的可学习性，那需要多少训练数据才能达到给定的准确度参数和置信参数呢？
答：我们可以用“样本复杂度”（sample complexity）来表示。所有假设空间有限的问题都是“概率近似正确”PAC 可学习的，其样本复杂度有固定的下界，输出假设的泛化误差会随着样本数目的增加以一定速度收敛到0。
❺ 有限空间有了，那如何判断具有无限假设空间的问题是否是 PAC 可学习的呢？
答：用“VC维”：对无限假设空间复杂度的一种度量方式。任何 VC 维有限的假设空间都是 PAC 可学习的。由于 VC 维并不依赖于数据分布的先验信息，因此它得到的结果是个松散的误差界（error bound），这个误差界适用于任意分布的数据。
❻ “松散的误差界”？是不是可用性较差？不能加入数据分布的先验信息呢？
答：所以有了“Rademacher 复杂度”。在已知的数据分布下，Rademacher 复杂度既可以表示函数空间的复杂度，也可以用来计算泛化误差界
❼ 学习理论的研究对解决实际问题到底具有什么样的指导意义呢？
答：举一个例子：神经网络的VC维相对较高，因而它的表达能力非常强，可以用来处理任何复杂的分类问题。要充分训练该神经网络，所需样本量为10倍的VC维。如此大的训练数据量，是不可能达到的。所以在20世纪，复杂神经网络模型在out of sample的表现不是很好，容易overfit。但现在为什么深度学习的表现越来越好？
其中一条是：通过修改神经网络模型的结构，以及提出新的regularization方法，使得神经网络模型的VC维相对减小了。例如卷积神经网络，通过修改模型结构(局部感受野和权值共享)，减少了参数个数，降低了VC维。2012年的AlexNet，8层网络，参数个数只有60M；而2014年的GoogLeNet，22层网络，参数个数只有7M。再例如dropout，drop connect，denosing等regularization方法的提出，也一定程度上增加了神经网络的泛化能力。 —— 例子参考《VC维的来龙去脉》
展开作者回复: 回答如此认真，值得点赞👍您的深入思考才是专栏最理想的效果
1 28
2018-06-12可以增加一些参考论文吗？作者回复: VC维这部分可以看看Abu-Mostafa的教材Learning from Data，本文的内容也是参考他的课程，真的深入浅出，水平很高。
计算学习理论可以看以色列人的教材Understanding Machine Learning: From Theory to Algorithm，有中译本。直接以PAC作为基础开始讲起，偏数学推导，比较难读。 6
2018-06-12王老师，我可以这么理解吗？
整篇文章都是围绕着“如何刻画训练误差和泛化误差之间的精度”来进行阐述的
1. 如果在某种条件（样本容量足够大的情况下）下，精度足够小，那么通过计算的方法来学到最优假设是可行的。
2. 引入两个维度来描述样本的复杂度，使我们了解到样本的复杂度其实是会影响到训练误差和泛化误差的精度的。
由此我们可以在设计机器学习任务的时候能够考虑到更多的因素从而使各方面达到一个比较好的均衡。作者回复: 你理解的没问题，学习理论就是要从理论上证明训练误差可以足够接近泛化误差。只要假设不要太复杂，并且数据足够多，训练误差都能收敛到泛化误差上，学习方法也就是有效的。
3
2018-06-12老师，请问学这类课题是不是，主要掌握概率学就基本可以了？还有机器学习是不是人工智能？作者回复: 计算学习理论涉及的数学很深的，概率主要是用到一些概率不等式，包括介绍到的Hoeffding和没介绍的其他不等式。你可以看看vapnik关于统计学习的书，直观感受一下这部分内容。
机器学习是人工智能发展最快的一个领域，不能说它就是人工智能。人工智能还包括知识表示、推理这些方向。 3- 2018-06-19您好，我想问下：“在打散的基础上可以进一步定义 VC 维。假设空间的 VC 维是能被这个假设空间打散的最大集合的大小，它表示的是完全正确分类的最大能力。上面的例子告诉我们，对于具有两个自由度的线性模型来说”这句话的，具有两个自由度的线形模型中的两个自由度是不是理解为：y=kx+b中，k和b是两个可以自由定义的变量？
作者回复: 是的，有些时候也会限制直线的截距为0，这时就只剩一个了。
2 
2018-06-14讲得非常好，但是模仿机器学习基石中的内容，会不会不太好作者回复: 这部分参考的是加州理工Abu-Mostafa的教材Learning from Data，机器学习基石的主讲应该是他的学生或者同事。Abu-Mostafa教授关于学习理论的讲解我认为是最清晰明了的，与其班门弄斧，不如将大师成熟的想法直接呈现出来，也算是见贤思齐吧。
2
2018-06-13周志华在书上说，计算学习理论是机器学习的理论基础，可以根据它来分析学习任务并指导算法设计。但是想请问老师，在具体问题上，是怎么使用它的呢?或者它还有其他什么作用吗?作者回复: 现实中的问题没有非黑即白，我们只能给出一个近似的答案。学习理论的意义就在于对问题的近似能达到什么样的精确程度，这是可以用通用公式算出来的。
但是这套理论给出的是独立于问题的结果，在实际中总会有一些问题接近这个界，另一些问题远离这个界。这时就得具体情况具体分析，利用问题自身的先验来优化。 1- 2020-01-29极客时间
21天打卡行动 42/21
<<机器学习40讲/04>>学什么与怎么学
今日所学:
1,对于机器学习来说，如果不能通过算法获得存在于训练集之外的信息，学习任务在这样的问题上就是不可行的;
2,在概率论中，有界的独立随机变量的求和结果与求和数学期望的偏离程度存在一个固定的上界，这一关系可以用 Hoeffding 不等式（Hoeffding's Inequality）来表示;
3,器学习利用训练集来选择出的模型很可能（对应名称中的“概率”）具有较低的泛化误差（对应名称中的“近似正确”）;
4,PAC 可学习性;
5,样本复杂度（sample complexity）是保证一个概率近似正确解所需要的样本数量。
6,。VC 维（Vapnik-Chervonenkis dimension）的名称来源于统计学习理论的两位先驱名字的首字母，它是对无限假设空间复杂度的一种度量方式，也可以用于给出模型泛化误差在概率意义上的上界。
7,线性模型可以对任何 3 个不共线的点进行划分，也就是将这个数据集打散。
8,在维度有限的前提下，VC 维的大小也会影响模型的特性。较小的 VC 维虽然能够让训练误差和泛化误差更加接近，但这样的假设空间不具备较强的表达能力（想想上面线性模型的例子），训练误差本身难以降低。反过来，VC 维更大的假设空间表达能力更强，得到的训练误差也会更小，但训练误差下降所付出的代价是训练误差和泛化误差之间更可能出现较大的差异，训练集上较小的误差不能推广到未知数据上。这其实也体现了模型复杂度和泛化性能之间的折中关系。
9,要是将数据的分布特性纳入可学习性的框架，复杂性的指标就变成了 Rademacher 复杂度（Rademacher complexity）。
10,“没有经验的”Rademacher 复杂度，它表示了函数空间在给定的数据分布上拟合噪声的性能。
重点:
1,Hoeffding 不等式描述了训练误差和泛化误差之间的近似关系；
2,PAC 学习理论的核心在于学习出来的模型会以较大概率接近于最优模型；
3,假设空间的 VC 维是对无限假设空间复杂度的度量，体现了复杂性和性能的折中；
4,Rademacher 复杂度是结合了先验信息的对函数空间复杂度的度量。展开 
2018-12-20作业：
关于学习理论的研究和解决实际的问题的意义：
个人意见：是指明一个方向，并在这个方向上不断精进和优化！
2018-06-17太书面化了，就没有一种比较生动形象的描述么？作者回复: 这部分内容确实偏理论一些。
2018-06-12有了这些理论基础，明白哪些方式是降低训练误差，哪些方式是减少训练误差和泛化误差的差距的，结合模型的表现判断和选择合适的优化方向或方式，这是我的理解。作者回复: 还可以给出独立于问题的性能评估方式。