标签：机器学习的本质，霍夫定不等式，成长函数，break-point，vc-维
vc维的引入，是为了证明机器学习是能够学到东西的。我们认为，机器学习的目标是从现有的数据当中学习出符合现有数据的规律g，而这个g与实际的数据规律f之间肯定是有差距的。
这样我们可以引申出两个概念：Ein，Eout，这两个概念是用来衡量一个假设函数的，Ein指的是假设函数在训练数据上的误差，Eout指的是假设函数在整个数据分布上的误差。我们学到一个假设函数以后，有两个目标：一是让Ein尽量小，而是要让Ein与Eout尽量一致，不能相差太大。
那么我们如何保证这种差距是比较小的呢？这里我们可以假设有一个罐子，每个罐子里面有黄色，绿色的珠子，黄色的珠子表示g得到的结果与f不一致，绿色的表示一致，那么我们可以认为每个罐子代表一个假设g。因为罐子中的珠子太多，我们不能全部拿出来，因此我们只能抽样查看绿色珠子的比例。那么又有一个问题，就是如何衡量抽样带来的误差，即我抽样出来的黄，绿珠子的比例与这个假设罐子中的真实比例差距有多大？关于这个，有霍夫定不等式，能够保证，抽样比例和实际比例之间的误差是有一个上界的。这就保证我对一个罐子进行抽样的时候，得到关于这个假设罐子的Ein与Eout的差距比较大的可能性是比较小的。但是，我们在假设空间寻找假设函数的时候，是对无穷个罐子进行搜索，这样，我们保证没有一个罐子会抽样到Ein与Eout相差比较大的情况的概率，就会被放大。这个放大的倍数就是罐子的个数，也就是假设空间中假设的个数。
但是其实这又是一个比较宽松的上界，在这个上界的系数是描述假设空间中假设的个数，但是其实我们想象一下线性分类（以下距离都是以线性分类为例），将分割平面稍微转动一下，就会是另外的假设，这这些假设是非常相似的，是有很大交集的，那么为了让这个上限更紧确些。我们需要重新考虑如何衡量假设空间的复杂度。这时候我们对假设空间中的函数做一下分类，即将数据点分割成同样结果的作为一类，用假设空间中函数的类别来衡量其复杂度。
按照数据点的多少，假设的类别肯定是变化的。而且数据点在空间排列的不同，数据点所属的类别不同，假设的类别肯定也是不同的。我们考虑在给定数据个数的情况下，在不同的数据分布的情况下，假设空间最多能有多少类。这是一个关于数据个数的函数。例如在数据点为3的时候, 下图显示了两种不同的数据分布，左图的分布情况下，八种情况都可以线性可分，这时假设空间中假设有8类，右图中，第三行的情况是线性不可分的，因此在当前的数据分布情况下，假设空间中只有6类假设。因此，在数据个数为3的情况下，假设空间的类别数为8。在这里，我们将这种描述假设空间类别的函数称为 成长函数（按照数据点的个数进行成长的）。
按照成长函数的定义，我们自然想到成长函数的上限是2^n,但是指数增长是非常快的，我们是否能够找到一个更加紧确的上限呢？这里我们提出了叫做“shater”的概念，指的是在数据量一定的情况下，存在一种数据分布情况，分割平面能够将数据空间中的所有点标记的所有情况都分割成功（即上图这种情况）。随着数据量的增加，肯定存在一个数据量的情况（我们称这时候的数据点的个数为break-point），假设空间不能够shater所有的数据点，这时候，我们的假设空间的类别个数就不再是指数增加了，说不定就变成多项式了呢。。（先小小的幻想一下，后面证明的确是多项式）
上段中提到了break-point的概念，这里举几个例子，具体说明一下什么是break-point。例如在假设空间是正向射线的情况下，在数据点为2的情况下，假设空间有三种类别：起始点分别位于比两个数据点都小，两个数据点中间，比两个数据点都大。这时候假设空间的类别为3，不等于2^2，因此break-point为2。
知道了成长函数不总是指数增长的，接下来我们想要证明出来一个比较紧确的多项式的上界。我们可以将成长函数的上限表示成B(N,k),其中N是数据点的个数，k是break-point。B(N,k)的概念就是在一定数据量的情况下，将数据点的标记情况进行排列组合，排列组合的结果不能shater到k个点（也就是不能将k个点中的所有情况都拍哦咧组合出来）。由此我们可以想象到，B(N,k)是一个动态规划的情况，有以下递推公式：
现在，我们证明了成长函数的上界的上界是一个多项式的表达式，因此，我们接下里的问题就是是否可以利用成长函数的上界来将Ein和Eout的差别很大的概率限制到一个更加紧确的上界。这里我就不加证明了，肯定是可以的。详细可以看林老师的机器学习基石的第六节。
接下来，我们看面试中常问到的vc维。vc维的定义就是假设空间的类别个数等于2^n的最大数据量，就是break-point减1.
概率分布在机器学习中占有非常重要的作用。尤其是在贝叶斯相关的理论中，参数，训练数据，预测变量等都是在一定的概率分布下形成的，我们预测的目标也主要是在对概率分布建模。而现实生活中的概率分布是非常复杂的，而我们只能利用简单的概率分布对其进行估计，近似。最常用的，最基本的一些概率分布模型就是指数族的概率分布了，包括很多基本的概率分布。
标签：beta分布，二项分布，泊松分布，正态分布，狄利克雷分布，极限关系，共轭关系，一致性
伯努利分布：一次抛硬币实验中（硬币未必均匀），投掷结果的概率分布；
二项分布：伯努利试验重复多次，投掷结果就服从二项分布；多次抛硬币实验中，投掷结果的概率分布。
泊松分布：泊松分布描述的是单位时间内某件小概率事件发生次数的分布。判断一件事情是否服从于泊松分布的条件：某件事情发生属于小概率事件，某件事情的发生是独立的，某件事情发生的概率是稳定的。泊松分布的表达可以由二项分布推导出来，当二项分布中n趋向于无穷，p趋向于0，而np是常数。因此，泊松分布可以理解为单位时间内无穷多次的伯努利实验，这些伯努利实验的和是稳定的，为lambda。
指数分布：主要描述相互独立的随机事件之间的时间间隔的概率；指数分布的形式可以由泊松分布推导出来。
gamma分布：gamma分布是独立同分布的指数分布的积分。gamma分布可以理解从头开始，到第n次事件发生的时间的分布。
beta分布：一定范围内的n个随机变量进行排序后，第k个变量的取值就是一个beta分布，其中alpha = k , beta = n - k + 1。其中gamma函数起到了将变量从整数空间延拓到实数空间的作用。
狄利克雷分布：一定范围内的n个随机变量进行排序后，第k1个变量，第k2个变量的联合分布就是一个狄利克雷分布。
高斯分布：在n趋近于无穷的时候，随机变量的均值收敛于正态分布。
卡方分布：n个服从正态分布的随机变量的平方和的分布。
t分布：x服从标准正态分布，y服从卡方分布。
F分布：x服从自由度为n的卡方分布，y服从自由夫为m的卡方分布。
t检验：适用于方差齐性的两组小样本之间的比较。
f检验：
卡方检验：理论频数和实际频数的吻合程度
p值：
自由度：
标签：F1，AUC，ROC，k折交叉验证，AIC，BIC，L1，L2，bootstrapping
回归任务中常用的性能度量是最小平方差
分类任务中，由于我们一般通过混淆矩阵来定义不同的度量方式：
3.1 参数化贝叶斯
最大后验分布
最大边缘概率分布
3.2 非参数贝叶斯
两者的不同在于先验的不同