第二课《学习的可行性》，可惜一课听下来，原以为会讲可学习的概率问题，结果整堂课在推导为什么频率在样本数量足够大的时候可以等于概率（hoeffding不等式）。

又从网上查阅其他资料，理解了虽然这节没有介绍算法，但是和第一课一样，是让我们理解为什么机器可以学习，掌握基本问题的分析思路。

一、基础

假设有一个应用，我们想知道机器学习能否在其中发挥作用。那我们应该如何验证？如何挑选？

学习=表示 + 评价+ 优化

表示（Representation）　：是指可用计算机可处理的语言表示。为学习器选择一种表示，意味着选择一个特定的分类器集合，就是假设空间(hypothesis space）。

评价（Evaluation）:需要一个评价函数（亦称为目标函数或打分函数）来判断分类器的优劣。机器学习算法内部使用的评价函数和我们希望分类器进行优化的外部评价函数有所不同。

优化（Optimization）:我们需要一个搜索方法，能够在假设空间中找到评价函数得分最高的那个分类器。

二、PAC学习模型（probably approximately correct，PAC）

背景：假定数据按照某概率分布P从实例X中随机产生，一般P可为任意分布，并且它对学习型算法是未知的。对于P，所要求的是它的稳定性，即该分布不会随时间变化（不然我们就没有学习的意义了）。训练数据的由P分布随机抽取而产生x，然后x及其目标值（可以理解为y，标签）被提供给学习器.

学习器在学习目标函数时考虑可能假设集H。

在观察了一系列训练数据后，学习器需要从假设集H中得到最终的假设g，这是对未知的符合P分布的理想模型f的估计。

最后，我们通过精心挑选出来的假设h对X中新的数据的性能来评估训练器。

定义两种错误率：

1、真实错误率Eout(h)（true error），也可以说是out-of-sample error,即样本之外，对于从任意分布中抽取的所有数据而言。g的真实错误率是应用g到未来按分布P抽取的数据时的期望错误率

2、样本错误率（sample error），也可以说是in-sample error，即针对所训练的样本数据的。

因为h关于f的错误率不能直接由学习器观察到。学习器只能观察到在训练数据上h的性能如何，所以训练器也只能在此性能基础上选择其假设输出。我们用训练错误率Ein(h)（training error）来指代训练样本中被h误分类的数据所占的比例，以区分真实错误率。

那么，数据集合X的样本错误率为数据集合X中被h误分类的数据所占的比例。训练错误率就是当X为训练数据集合时的样本错误率。

PAC可学习性(PAC Learnability)

我们训练学习器的目标是，能够从合理数量的训练数据中通过合理的计算量可靠的学习到知识。

机器学习的现实情况：

1、除非对每个可能的数据进行训练，否则总会存在多个假设使得真实错误率不为0，即学习器无法保证和目标函数完全一致

2、训练样本是随机选取的，训练样本总有一定的误导性

为此，我们要弱化对学习器的要求：

1、我们不要求学习器输出零错误率的假设，只要求错误率被限制在某常数ε范围内，ε可为任意小。

2、不要求学习器对所有任意抽取的数据都能成功预测，只要求其失败的概率被限定在某个常数μ的范围内，μ可取任意小。

3、简而言之，我们只要求学习器可能学习到一个近似正确的假设，故得到了“可能近似正确学习”或PAC学习。

如果学习机器在短时间(多项式级别)内根据少量的(多项式级别)的训练集样本m，能够找到一个好的假设h，满足上面的那个式子，那么就说这个问题是PAC可学习的。

参考：https://blog.csdn.net/qq_34662278/java/article/details/83961427