泛化能力
 
一、 泛化误差
 
学习方法的泛化能力（generalization ability）：方法学习到的模型对未知数据的预测能力。
 
评价标准：测试误差。
 
但因为测试数据集是有限的，很有可能由此得到的评价结果是不可靠的。统计学习理论试图从理论上对学习方法的泛化能力进行分析。
 
 
泛化误差定义：如果学习到的模型是$\hat{f}$，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）
 $$R_{exp}(\hat{f})=E_p[L(Y,\hat{f}(X))]={\int }_{\chi \times \gamma }L(y,\hat{f}(x))p(x,y)dxdy$$
 实际上，泛化误差就是学习到的模型的期望风险
 
 
意义：反映了学习方法的泛化能力，越小，则泛化能力越好
 
 
二、 泛化误差上界
 
泛化误差上界（generalization error bound）：泛化误差的概率上界。
 
 
通过比较两种学习方法的泛化误差上界的大小来比较它们的优势。
 
 
性质：
 
  
是样本容量的函数，当样本容量增加时，泛化上界趋于0
是假设空间容量的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。
 
 
二分类问题的泛化误差上界：
 
已知训练数据集
      
       
        
         
          T
         
         
          =
         
         
          {
         
         
          (
         
         
          
           x
          
          
           1
          
         
         
          ,
         
         
          
           y
          
          
           1
          
         
         
          )
         
         
          ,
         
         
          (
         
         
          
           x
          
          
           2
          
         
         
          ,
         
         
          
           y
          
          
           2
          
         
         
          )
         
         
          ,
         
         
          .
         
         
          .
         
         
          .
         
         
          ,
         
         
          (
         
         
          
           x
          
          
           N
          
         
         
          ,
         
         
          
           y
          
          
           N
          
         
         
          )
         
         
          }
         
        
        
         T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}
        
       
      T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，它是联合概率分布$P(X,Y)$独立同分布产生的，
      
       
        
         
          X
         
         
          ∈
         
         
          
           R
          
          
           n
          
         
         
          ,
         
         
          Y
         
         
          ∈
         
         
          {
         
         
          −
         
         
          1
         
         
          ,
         
         
          +
         
         
          1
         
         
          }
         
        
        
         X\in R^n, Y\in \{-1,+1\}
        
       
      X∈Rn,Y∈{−1,+1}. 假设空间是函数的有限集合
      
       
        
         
          F
         
         
          =
         
         
          {
         
         
          
           f
          
          
           1
          
         
         
          ,
         
         
          
           f
          
          
           2
          
         
         
          ,
         
         
          .
         
         
          .
         
         
          .
         
         
          ,
         
         
          
           f
          
          
           d
          
         
         
          }
         
        
        
         F=\{f_1,f_2,...,f_d\}
        
       
      F={f1​,f2​,...,fd​}，d是函数个数。设f是从F中选取的函数。损失函数是0-1损失，关于f的期望风险和经验风险分别是：
 $$\begin{gathered} R(f)=E[L(Y,f(X))] \\ \hat{R}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,f(x_i)) \end{gathered}$$
 经验风险最小化函数是：
 $$f_N=argmi{n}_{f\in F}\hat{R}(f)$$
 $f_N$的泛化能力：
 $$R(f_N)=E[L,f_N(X)]$$
 **定理(泛化误差上界)：**对二类分类问题，当假设空间是有限个函数的集合
      
       
        
         
          F
         
         
          =
         
         
          {
         
         
          
           f
          
          
           1
          
         
         
          ,
         
         
          
           f
          
          
           2
          
         
         
          ,
         
         
          .
         
         
          .
         
         
          .
         
         
          
           f
          
          
           d
          
         
         
          }
         
        
        
         F=\{f_1,f_2,...f_d\}
        
       
      F={f1​,f2​,...fd​}时，对任意一个函数$f\in F$，至少以概率$1-\delta$，以下不等式成立：
 $$R(f)\le \hat{R}(f)+ϵ(d,N,\delta )\text{\hspace{1em}(1)}$$
 其中
 $$ϵ(d,N,\delta )=\sqrt{\frac{1}{2N}(logd+log\frac{1}{\delta })}$$
 不等式（1）左端$R(f)$是泛化误差，右端即为泛化误差上界。在泛化误差上界中，第1项是训练误差，训练误差越小，泛化误差越小。第2项$ϵ(d,N,\delta )$是N的单调递减函数，当$N$趋于无穷时，它趋于0；同时它也是$\sqrt{logd}$阶的函数，假设空间$F$包含的函数越多，其值越大。
 
**证明：**在证明中要用到$Hoeffding$不等式，先叙述如下
 
设$S_n={\sum }_{i=1}^n{X}_i$是独立随机变量$X_1,X_2,...,X_n$之和，$X_i\in [a_i,b_i]$，则对任意$t>0$，以下不等式成立：
 $$P(S_n-E{S}_n\ge t)\le exp(\frac{-2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2})\text{\hspace{1em}(2)}$$
 
$$P(E{S}_n-S_n\ge t)\le exp(\frac{-2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2})\text{\hspace{1em}(3)}$$
 
对任意函数$f\in F$，$\hat{R}(f)$是N个独立的随机变量$L(Y,f(X))$的样本均值，$R(f)$是随机变量$L(Y,f(X))$的期望值。如果损失函数取值于区间$[0,1]$，即对所有i，$[a_i,b_i]=[0,1]$，那么由$Hoeffding$不等式(3)不难得知，对$ϵ>0$，以下不等式成立：
 $$P(R(f)-\hat{R}(f)\ge ϵ)\le exp(-2N{ϵ}^2)$$
 由于
      
       
        
         
          F
         
         
          =
         
         
          {
         
         
          
           f
          
          
           1
          
         
         
          ,
         
         
          
           f
          
          
           2
          
         
         
          ,
         
         
          .
         
         
          .
         
         
          .
         
         
          ,
         
         
          
           f
          
          
           d
          
         
         
          }
         
        
        
         F=\{f_1,f_2,...,f_d\}
        
       
      F={f1​,f2​,...,fd​}是一个有限集合，故
 
       
        
         
          
           P
          
          
           (
          
          
           ∃
          
          
           f
          
          
           ∈
          
          
           F
          
          
           :
          
          
           R
          
          
           (
          
          
           f
          
          
           )
          
          
           −
          
          
           
            R
           
           
            ^
           
          
          
           (
          
          
           f
          
          
           )
          
          
           ≥
          
          
           ϵ
          
          
           )
          
          
           =
          
          
           P
          
          
           (
          
          
           
            ⋃
           
           
            
             f
            
            
             ∈
            
            
             F
            
           
          
          
           {
          
          
           R
          
          
           (
          
          
           f
          
          
           )
          
          
           −
          
          
           
            R
           
           
            ^
           
          
          
           (
          
          
           f
          
          
           )
          
          
           ≥
          
          
           ϵ
          
          
           }
          
          
           )
          
          
          
           ≤
          
          
           
            ∑
           
           
            
             f
            
            
             ∈
            
            
             F
            
           
          
          
           P
          
          
           (
          
          
           R
          
          
           (
          
          
           f
          
          
           )
          
          
           −
          
          
           
            R
           
           
            ^
           
          
          
           (
          
          
           f
          
          
           )
          
          
           ≥
          
          
           ϵ
          
          
           )
          
          
          
           ≤
          
          
           d
          
          
            
          
          
           e
          
          
           x
          
          
           p
          
          
           (
          
          
           −
          
          
           2
          
          
           N
          
          
           
            ϵ
           
           
            2
           
          
          
           )
          
         
         
           P(\exists f\in F:R(f)-\hat R(f)\geq \epsilon)=P(\bigcup_{f\in F}\{R(f)-\hat R(f) \geq \epsilon\}) \\ \leq \sum_{f\in F}P(R(f)-\hat R(f)\geq \epsilon) \\ \leq d \space exp(-2N\epsilon^2) 
         
        
       P(∃f∈F:R(f)−R^(f)≥ϵ)=P(f∈F⋃​{R(f)−R^(f)≥ϵ})≤f∈F∑​P(R(f)−R^(f)≥ϵ)≤d exp(−2Nϵ2)
 或者等价的，对任意的$f\in F$，有
 $$P(R(f)-\hat{R}(f)<ϵ)\ge 1-dexp(-2N{ϵ}^2)$$
 令
 $$\delta =dexp(-2N{ϵ}^2)\text{\hspace{1em}(4)}$$
 则
 $$P(R(f)<\hat{R}(f)+ϵ)\ge 1-\delta$$
 则至少以概率$1-\delta$有$R(f)<\hat{R}(f)+ϵ$<其中$ϵ$由(4)得到，即为$ϵ(d,N,\delta )$
 
从泛化误差上界可知，
 $$R(f_N)\le \hat{R}(f_N)+ϵ(d,N,\delta )$$
 其中$ϵ(d,N,\delta )$和$f_N$在上面表示。因此，训练误差小的模型，其泛化误差也会小。
 
以上的讨论的只是假设空间包含有限个函数情况下的泛化误差上界，对一般的假设空间要找到的泛化误差界就没这么简单。
 

读STL源码分析
 
前言 
 再好的编程技巧，也无法让一个笨拙的算法起死回生。 
 选择了错误的算法，便注定了失败的命运。
 
何为算法 
 以有限的步骤，解决逻辑或数学上的问题，Algorithms!
 
算法分析 
 空间复杂度、时间复杂度
 
分类 
 质变算法：会改变操作对象的值，例如拷贝、互换。 
 非质变算法：不改变操作对象的值，例如查找、匹配。
 
算法的泛化过程
 
举例说明： 
 从一个array中寻找特定的值：
 
我们的直觉反应是：
 
int *find(int *array,int size,int target)
{
    for(int i=0;i<size;i++)
    {
        if(array[i]==target)
            break;
    }
    return &(array[i]);
}
 
上面的做法暴露了容器太多的实现细节，因此太过依赖特定容器。 
 让find()接收两个指针作为参数：
 
int *find(int *begin,int *end,int value)
{
    while(begin!=end&&*begin!=value)
        begin++;
    return begin;
}
 
为了不仅仅适用于array，我们使用模板：
 
template<class T>
T *find(T *begin,T *end,const T& value)
{  
    while(begin!=end&&*begin!=value)
        begin++;
    return begin;
}
 
上面的函数虽然能适用大部分容器，但是还还不能用于list，进一步演化： 
 在C++中，上述操作符或操作行为都可以被重载。如果我们以一个原生指针指向某个list，则对该指针进行“++”操作并不能指向下一个串行节点，但如果哦我们设计一个class，拥有原生指针的行为，并使其”++“操作指向list的下一个节点，那么find()就可以施行于list容器上了。这便是迭代器（iterator）的观念。迭代器是一种行为类似指针的对象，下面将find()函数内的指针以迭代器取代
 
template<class Iterator,class T>
Iterator *find(Iterator *begin,Iterator *end,const T& value)
{
    while(begin!=end&&*begin!=value)
        begin++;
    return begin;
}

目录
 
1.什么是泛化能力
 
2.什么是好的机器学习模型的提出
 
3.泛化误差
 
4.模型泛化能力的评价标准 
 
4.提高泛化能力
 
5.举例
 
6.相关引用文献
 

1.什么是泛化能力
 
百度百科解释：机器学习算法对新鲜样本的适应能力。
 
更加具体的解释：学习到的模型对未知数据的预测能力，这个未见过的测试数据必须是和训练数据处于同一分布,不在同一分布的数据是不符合独立同分布假设的（对同一规律不同的数据集的预测能力）。通常通过测试误差来评价学习方法的泛化能力。
 
通俗+形象解释：
 就是通过数据训练学习的模型，拿到真实场景去试，这个模型到底行不行，如果达到了一定的要求和标准，它就是行，说明泛化能力好，如果表现很差，说明泛化能力就差。为了更好的理解泛化能力，这里引入三种现象，欠拟合、过拟合以及不收敛。泛化能力的本质就是反映模型有没有对客观世界做真实的刻画，还是发生了过拟合。
 考试成绩差的同学，有这三种可能：
 一、泛化能力弱，做了很多题，始终掌握不了规律，不管遇到老题新题都不会做，称作欠拟合；
 二、泛化能力弱，做了很多题，只会死记硬背，一到考试看到新题就蒙了，称作过拟合；
 三、完全不做题，考试全靠瞎蒙，称作不收敛。
 
 
2.什么是好的机器学习模型的提出
 
奥卡姆的威廉是 14 世纪一位崇尚简单的修士和哲学家。 他认为科学家应该优先采用更简单（而非更复杂）的公式或理论。
 
奥卡姆剃刀定律在机器学习方面的运用如下： 
 
 
 
机器学习模型越简单，良好的实证结果就越有可能不仅仅基于样本的特性。
 
 
现今，我们已将奥卡姆剃刀定律正式应用于 统计学习理论 和 计算学习理论 领域。这些领域已经形成了 泛化边界，即统计化描述模型根据以下因素泛化到新数据的能力： 
 
 
模型的复杂程度
 
 
模型在处理训练数据方面的表现
 
虽然理论分析在理想化假设下可提供正式保证，但在实践中却很难应用。 机器学习速成课程则侧重于实证评估，以评判模型泛化到新数据的能力。
 
机器学习模型旨在根据以前未见过的新数据做出良好预测。 但是，如果要根据数据集构建模型，如何获得以前未见过的数据呢？ 一种方法是将您的数据集分成两个子集：
 
 
训练集 - 用于训练模型的子集。
 
 
测试集 - 用于测试模型的子集。
 
一般来说，在测试集上表现是否良好是衡量能否在新数据上表现良好的有用指标，前提是：
 
 
测试集足够大。
 
 
您不会反复使用相同的测试集来作假。
 
3.泛化误差
 
首先给出泛化误差的定义， 如果学到的模型是 f^ ， 那么用这个模型对未知数据预测的误差即为泛化误差
 
 
 泛化误差反映了学习方法的泛化能力，如果一种方法学习的模型比另一种方法学习的模型具有更小的泛化误差，那么这种方法就更有效， 事实上，泛化误差就是所学到的模型的期望误差。
 
4.模型泛化能力的评价标准 
 
回归任务常用的性能度量是“均方误差”。
 
1. 错误率与精度
 
错误率与精度是分类任务中最常用的两种性能度量。既适用于二分类，也适用于多分类。

 错误率：分类错误的样本数占总样本数的比例。
 精度 ： 分类正确的样本数占总样本数的比例。

 精度 + 错误率 = 1 

          假设，总的样本数为m个，我们对这m个样本进行预测，其中预测对了的样本有p个，预测错的样本有n个（p+n = m），则：
          错误率 = n/m
          精度  = p/m
 
 2. 查全率、查准率、F1
 
   当任务有所偏好时，错误率与精度便不能满足任务的需求。比如我们关心的是“检索出来的信息中有多少是用户感兴趣的”或者“用户感兴趣的信息有多少被检索出来了”。此时就需要查全率、查准率、F1值来进行模型的性能度量。

   假设，总的测试样本有m个，其中正样本有z个，负样本有f个。

   查全率：对这m个样本进行预测，其中z个正样本中有zm个被预测对。查全率 = zm / z
   查准率： 对这m个样本进行预测，预测的结果中有ym个是正样本，ym个样本中有y个是z的，则：查准率 = y / ym
   ![这里写图片描述](https://img-blog.csdn.net/20170323192002648?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdnZ5dWVydnY=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
   上图为混淆矩阵，TP + FN + FP + TN = 样例总数。
   对应的查准率P和查全率R分别定义为：
   ![这里写图片描述](https://img-blog.csdn.net/20170323192302192?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdnZ5dWVydnY=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
  查准率和查全率是一对矛盾的度量。
  查准率越高时，查全率往往偏低。而查全率越高时，查准率往往偏低。
 
P-R曲线：（查准率-查全率曲线） 
 
P-R曲线是以查全率为横轴，以查准率为纵轴的二维坐标图。
 
P-R曲线的建立过程： 
 根据学习器的预测结果对样例进行排序，排在前面的是学习器认为“最可能”是正例的样本，排在后面的则是学习器任务“最不可能”是正例的样本。按此排序，逐个把样本作为正例进行预测，则每次可以计算出当前的查全率和查准率。以此为纵轴和横轴作图，便得到了查全率-查准率曲线，即P-R曲线。
 
P-R曲线作用： 
 用来对比不同学习器的好坏的。例如上图2.3中学习器A包含学习器C，则说学习器A优于学习器C。但当两个学习器的P-R曲线有交叉时，难以判断那个学习器较好。通常的做法是计算每个学习器曲线所包含的面积，比较面积的大小。但这值不太容易估算。于是人们便使用“平衡点”（简称BEP）这一度量，即“查准率 = 查全率”时的取值。例如上图中的平衡点可判定，学习器A优于学习器B。
 
F1值： 
 F1值为查全率和查准率的协调平均值， 
 
在一些应用中，对查全率和查准率的重视程度有所不同，F1度量的一般形式能让我们表达出对查全率和查准率的的不同偏好。
![这里写图片描述](https://img-blog.csdn.net/20170323200924929?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdnZ5dWVydnY=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)

其中β > 0 度量的查全率对查准率的相对重要性。β = 1 时便为标准的F1。β > 1时查全率有更大的影响，β < 1时查准率有更大的影响。

当我们在多个二分类混淆矩阵上综合考虑查全率和查准率时有两种方法：
第一种，先在各混淆矩阵上分别计算出查全率和查准率，再计算平均值。这样就得到了“宏查全率”、“宏查准率”、以及“宏F1”
![这里写图片描述](https://img-blog.csdn.net/20170323201635647?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdnZ5dWVydnY=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
 
第二种，先将各混淆矩阵的对应元素进行平均，再基于这些平均值进行计算，得出“微查全率”“微查准率”以及“微F1”， 
 
 
3.ROC与AUC
 
ROC曲线与AUC常被用来评价一个二分类器的优劣。
 
和P-R曲线类似，“ROC曲线”是根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要的量值（真正例率TRP和假正例率FPR），分别以他们作为横、纵坐标作图，就得到了“ROC曲线”。
 
 
 
    上图（a）中的虚线表示“随机猜测”模型。在(0,1)点处，即FPR=0, TPR=1，这意味着FN = 0，并且FP = 0。这是一个完美的分类器，它将所有的样本都正确分类。在(1,0)点处，即FPR=1，TPR=0，类似地分析可以发现这是一个最糟糕的分类器，因为它成功避开了所有的正确答案。在(0,0)点处，即FPR=TPR=0，即FP = TP =0，可以发现该分类器预测所有的样本都为负样本。在（1,1）点处，分类器实际上预测所有的样本都为正样本。经过以上的分析，我们可以断言，ROC曲线越接近左上角，该分类器的性能越好。
 
 
现实任务中通常是利用有限个测试样本来绘制ROC图的，所以仅能或得有限个（真正例率TRP和假正例率FPR）坐标对，绘制出的图如上图中的（b）。
 
ROC曲线绘制过程：
 
   给定m个正例和n个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设置为最大，即把所有样例均预测为反例，此时真正例率和假正例率均为0，在坐标（0，0）出标记一个点。然后，将分类的阈值依次设置为每个样例的预测值，即依次将每个样例划分为正例。设前一个标记的坐标为（x,y），当前若为真正例，则对应的标记点的坐标为（x, y+1/m）;若当前为假正例，则对应标记点的坐标为（x+1/n, y）， 然后用线段连接相邻的点即可。
 
 
学习器比较：
 
  若一个学习器A的ROC曲线包含另外一个学习器B的ROC曲线，则认为学习器A的性能优于学习器B。
  若两者的ROC曲线相交，则需要对各自ROC曲线下得面积（即AUC）进行比较。
 
AUC可通过对ROC曲线下各部分面积求和而得。 
 
4.代价敏感错误率与代价曲线
 
不同类型的错误所造成的后果不同。
 
为权衡不同类型错误造成的不同损失，可为错误赋予“非均等代价”。
 
以二分类为例，可设定一个“代价矩阵” 
 
表中cost10 表示将第1类错分为第0类的代价，cost01同样，表示将第0类错分为第1类的代价。此二分类也可拓展为多分类costij表示将第i类错分为第j类的代价。
 
前面的性能度量都默认的假设了均等代价，所有错误率是直接计算错误的次数，并没有考虑不同错误会造成的不同的后果。在非均等代价下，我们希望的不再是简单地最小化错误次数，而是希望最小化“总体代价”。 
 
 上式中，D+和D-分别表示样例集D中的正例子集和反例子集。
 
在非均等代价下，ROC曲线不能直接反应学习器期望的总体代价，而“代价曲线”则可达到该目的。 
 代价曲线图的横轴是取值为[0,1]的正例概率代价： 
 
 上式中p是样例为正例的概率。
 
纵轴是取值为[0，1]的归一化代价：
 
 
FNR表示假正例率，FNR = 1 - TPR
 
代价曲线的绘制：
 
   ROC曲线上每一点对应了代价平面上的一条线段，设ROC曲线上的坐标为（TPR，FPR），则可相应的计算出FNR，然后在代价平面上绘制一条从（0，FPR）到（1，FNR）的线段，线段下面的面积即表示了该条件下得期望总体代价。如此将ROC曲线上的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价。
 
 
 
 
 
4.提高泛化能力
 
提高泛化能力的方式大致有三种：1.增加数据量。2.正则化。3.凸优化。
 
 
 
5.举例
 
下面图片中每个点代表一棵树的位置，蓝点代表生病的树，橙点代表健康的树。
 
 
给你样本数据，要求提供一个机器学习算法算法，区分开两种树。
 
你千辛万苦画出来一条曲线能够很好地进行聚类，而且模型的损失非常低(损失函数)，几乎完美的把两类点一分为二。但这个模型真的就是好模型吗？
 
 
用该算法预测新样本时，没有很好的区分两类点，表现得有些差劲。
 
 
上述模型过拟合了训练数据的特性，过拟合模型在训练过程中产生的损失很低，但在预测新数据方面的表现却非常糟糕。如果某个模型在拟合当前样本方面表现良好，那么我们如何相信该模型会对新数据做出良好的预测呢？过拟合是由于模型的复杂程度超出所需程度而造成的。机器学习的基本冲突是适当拟合我们的数据，但也要尽可能简单地拟合数据。
 
 
 
6.相关引用文献
 
https://blog.csdn.net/tiankong_/article/details/78361496
 
https://zhuanlan.zhihu.com/p/59673364?utm_source=wechat_session
 
https://segmentfault.com/a/1190000016425702?utm_source=tag-newest
 
https://my.oschina.net/u/4604431/blog/4476343
 
https://www.jianshu.com/p/849423297c7f
 
https://blog.csdn.net/vvyuervv/article/details/65449079
 
 

目录
 
一、方法
 
（一）模型：
 
（二）策略：（最优化问题）
 
1.损失函数（指标）
 
2.期望与均值
 
3.最优化问题 
 
（三）算法
 
 二、误差与泛化能力
 
1.训练误差与测试误差
 
2.泛化能力与泛化误差
 
3.过拟合
 
 

一、方法
 
所有的统计学习（机器学习）的方法都是由：模型、策略和算法构成
 
其中，非监督学习、强化学习同样有三要素，但此处仅说监督学习
 
（一）模型：
 
所需要进行学习（训练）的模型类别，也就是确定假设空间
 
在监督学习中，这一要素即为所需要学习的条件概率分布或决策函数
 
其中，
 
假设空间（斜体F）通常是由一个参数向量决定的函数簇
 
假设空间可能是有限集，但一般有无穷多个模型
 
所有参数向量取值组成的集合称为参数空间
 
（二）策略：（最优化问题）
 
学习的过程就是从模型当中选择一个最优模型的过程，也就是解决一个最优化问题
 
1.损失函数（指标）
 
为了将模型参数选择问题转化为数学中的最优化问题，就需要一个量度作为指标，即为损失函数：
 
L(Y,f(X))
 
其中，Y为真实值，对应样本数据的标签
 
           f(X)为预测值，即为模型的输出
 
常见的损失函数：
 
对于分类问题：常见有0-1损失函数、对数损失函数（0-1损失上界）
 
对于回归问题：常见有平方损失函数（均值方差MSE）、绝对值损失函数（绝对值ALF）（绝对值相比均值方差收敛较快，但效果不如均值方差）
 
2.期望与均值
 
（1）期望损失（风险函数）：对于一个损失函数，它在样本空间中的平均意义下的损失，即为损失函数的期望=（定积分），代表着模型的预测和真实规律的误差
 
这个指标的最小化就是机器学习所追求的目标， 然而我们很难或者说几乎不可能得到所有的样本空间，我们只能够得到样本空间中的一部分样本来训练模型，所以就有了有限样本情况下的经验损失。
 
（2）经验损失：在样本有限的情况下，对训练数据集中的所有样本的损失函数求均值
 
 度量训练数据的预测值和真值的误差。
 
综上，期望损失和经验损失就有了下图中的关系：
 
 
3.最优化问题 
 
最优化问题可以分为经验风险最小化和结构风险最小化
 
（1）经验风险最小化
 
对于训练数据集，有了可操作的评价指标经验风险，将问题转化为了最优化问题——经验风险最小化（ERM）
 
根据经验风险最小化的策略，经验风险最小的模型就是最优的模型
 
其中一个典型的例子就是极大似然估计（模型：条件概率分布，损失函数：对数损失函数）
 
当样本容量比较大的时候，经验风险最小化能够有很好的学习效果
 
但是，当样本容量不够多的时候，经验风险最小化很难有好的学习效果，会产生过拟合的现象。
 
（2）结构风险最小化（SRM）：
 
为了防止过拟合而提出了结构风险最小化，具体操作方法是加入正则化项。
 
结构风险最小化表示：
 
Rsrm(f)=Remp+lamadaJ(f)
 
J(f)为模型复杂度，lamada是系数，用以权衡经验风险和模型复杂度。
 
结构风险最小化往往能够对训练数据和未知数据都有很好的预测
 
例如：最大后验概率估计
 
（三）算法
 
学习模型的具体计算方法即求解最优化问题的计算方法
 
如果问题存在显式的解析解，则最优化问题较为简单
 
但通常解析解并不存在，需要找到最优解
 
可以利用已有的最优化方法，有时也需要开发独自的最优化方法
 
 二、误差与泛化能力
 
1.训练误差与测试误差
 
（1）训练误差：学习后的模型关于训练数据集的平均损失
 
训练误差的大小意义仅仅在于判断一个问题是不是一个容易学习的问题，即训练的难度，本质并不重要。
 
可以用来判断学习的难易度以及实现训练过程可视化
 
（2）测试误差：学习后模型关于测试数据集的平均损失
 
测试误差反映了学习方法对未知的测试数据集的预测能力，是学习中的重要概念
 
在多种学习方法中，测试误差小的方法具有更好的预测能力，是更有效的方法。
 
测试误差是泛化误差的估计，在下面会详述。
 
2.泛化能力与泛化误差
 
（1）泛化能力：学习方法的泛化能力是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。
 
（2）泛化误差：一个方法在（所有）新样本或者说对未知数据预测的误差成为泛化误^
 
Rexp(^f)=Ep[L(Y,^f(X))] (期望)
 
泛化误差反映了学习方法的泛化能力，也就是学习后模型的期望风险。
 
泛化误差是泛化能力的量度
 
（3）泛化误差上界
 
学习方法的泛化能力往往是通过研究泛化误差的概率上界进行的，简称为泛化误差上界。
 
具体上，可以通过比较两种方法的泛化误差上界来比较优劣。
 
性质：
 
1.样本空间的函数：当样本容量不断增加时，泛化上界趋于0
 
2.假设空间的函数：假设空间容量越大，模型越难学，泛化误差上界越大
 
二分类问题的泛化误差上界（统计学习方法定理1.1）【在其他笔记中我会专门给出证明】
 
（4）泛化误差与测试误差
 
由于无法得到所有的样本，所以很难得到泛化误差。
 
但可以得到部分其他样本，用这些样本测试模型得到的是测试误差，因此测试误差、泛化误差就有了类似经验风险和期望风险的关系，即测试误差是泛化误差的估计：
 
 
3.过拟合
 
实际上，影响方法的泛化能力的首要因素是过拟合，训练误差不适合作为泛化能力的标准正是因为过拟合的存在。
 
对于一个问题的学习方法来说，所期望学习到的是样本的普遍规律，然而，要学习样本的普遍规律就需要整个样本空间，和上文所遇到的困难一样，我们无法得到整个样本空间，只能得到一部分样本，所以就有了一个问题：
 
取到的这一部分样本不仅包含样本空间的普遍规律，还包含了此部分样本的独有规律，我们期望着能够学习到普遍规律，不希望学习到独有规律。然而机器是无法判断独有和普遍规律的，所以如果样本空间比较小，一味的追求训练误差（经验风险最小化），就会导致过拟合，所以训练误差不适合作为泛化能力的标准，更不能估计泛化误差。
 
过拟合是机器学习面临的关键障碍，各类机器学习算法都必然带有一些针对过拟合的措施；然而，过拟合是无法彻底避免的，只能做到缓解或者说减小其风险。
 
其中一种缓解过拟合的思路就是控制模型复杂度：