在这之前整理一下之前的脉络。 首先我们一直强调的是让Ein尽量靠近Eout， 最开始用了Hoeffding不等式， 其实右边可以看成是所有的Error area相加？最开始是以M(size of hypothesis set)作为估计的， 显然M中的Error区域是有很多重复的， 如果以这个作为估计的话， 不等式是容易满足的； 于是我们从无穷的Hypothesis set过度到只研究N个点上面的Hypothesis set大小， 产生了growth function； 然后又发展了VC dimension = break point - 1， 并且推导了growth function与VC dimension的关系是polynomial(实际计算的时候可以只考虑主项，N^d)；最终我们得到是Eout的上界(泛化能力)Eout < Ein + \delta。 以下是一点关于VC dimension= infinite的理解， 之前可能有一种理解就是M如果是无穷大（其实就是没有break point， VC dimension无穷， 那么岂不是所有的样例都能被分开， 然而到后面发展到VC inequality的角度来看这意味着需要更无穷的数据来拟合呢， 显然是无法达到的。Hypothesis set大了， Ein会小，但是\delta会大， 这其中是有tradeoff的。

• size of hypothesis set is related to the ability of generalization. Hypothesis set越大， 说明更有可能选择到g约等于f， 但是， 有个前提是我们是从training data来训练选择到g的， 这样做的结果就是模型泛化能力差。

  
  
  relation

• Bias-variance衡量了H能多靠近target function(bias)， 以及靠近target function的h的范围有多大(variance)。

  
  
  quantifying

• 推导环节。Eout就是在一个数据集中所有的点的Error的均值， 为了使它是与independent of different dataset， 可以选择在不同的data set上面取均值。 并且定义了average hypothesis就是在所有的数据集上面得到的hypothesis的均值。最终得到了E_D的表达式， bias就是在不同的数据集上面能够取得的g(x)与target function的偏差(我们实际能取得的最好的能力）， variance就是在最优的g(x)上面我们的波动有多大。

  
  
  start
  
  
  average
  
  
  using it
  
  
  bias and variance

• 下面的解释很直观， 左边的图只有一个hypothesis， bias很大， 但是根本就没variance； 右边的图的hypothesis大很多， 因此总能找到一个跟target function f靠的很近的hypothesis， 因此bias小， 但是variance也随之变大了。

  
  
  illustrate

• example：拟合sine。我们并不知道target function就是sine， H0是用线h(x)=b来拟合， H1 是用线h(x) = ax + b来拟合。在本例子中每次都是从数据集中采样两个点， 让模型去学习， 毫无疑问， H0 的最终学习到的final hypothesis 一定是h(x)=0， 而H1是一根斜线； 而灰色区域就是各自的variance。虽然H1的bias高， 但是其variance更低，OK， the winner is H0。

  
  
  sine
  
  
  H0
  
  
  H1
  
  
  winner

• 接下来分析Ein， Eout随着data size N是如何变化的， 主要是推断模型的泛化能力。无论简单或者复杂的模型， 当数据点少的时候， 如N = 5 肯定比 N = 20 容易些， 所以Ein是随着N的增大而增大的， 而Eout是out of sample的点， 若数据点太少模型泛化能力不能保障导致Eout也会增加。 而对于复杂的模型， Ein一开始是0是因为VC dimension大， 能够shatter这些点， 随着数据点增多， 不能区分的pattern逐渐显现， 所以Ein又增加了。 同样， 复杂的模型需要更多的点来保证generalization， Eout才会降低。

  
  
  Expected
  
  
  versus

• 接下来从VC理论和bias-variance tradeoff来分析generalization bound。 对于VC来说， Eout < Ein + \delta， Ein就是蓝色的区域， 而红色就是\delta, generalization error; 从bias-variance来看， Eout = bias + variance， 图中的黑线就是模型在所有的数据集上面能达到的误差， 所谓average g，它就是与target function之间存在的bias， 而红色区域就是variance，波动有多大。

  
  
  view

• case: linear regression。 用y加上一些noise来模拟out of sample。 显然， 如果不加的话， 图中的黑线就在纵坐标为0的地方了， 而现在刚好是在noise的variance的地方。 d+1是VC dimension。

  
  
  case
  
  
  curve