在VC理论中， 仅仅考虑了Eout < Ein + \delta, 其中\delta 与growth function， N相关， 但是却没考虑到target function的影响， noise的影响， 现在我们要来补全它。

• 下面从一个简单的例子开始。还记得我们之前的， 给定两个点， 用一根线拟合sin的例子吧， y = ax + b表现的并不那么好， 可以看出来它的variance非常大， 虽然bias小(y=b这个简单的假设反而variance没那么大)。 而当我们加了regularization的时候， things become better。 Regularization减小variance的代价是稍微增大了bias， 而显然这是可以接受了。 Regularization在这里的一种理解是假如我们有0,1,2,3阶模型， regularization不选择到具体的模型， 而是处于a gap between them。

  
  
  example
  
  
  winner

• 多项式模型。更一般化的， 我们将线性回归表达成矩阵/向量的形式，看成是变换到Z空间，再做回归， 每个Z空间对应一个勒让德多项式。采用勒让德多项式的好处是它们之间两两正交， 代表着假设空间是不会重复的。 然后就是跟之前一样的求解步骤了。

  
  
  polynomial
  
  
  sol

• 事实上， 我们可以加constrain， hard的形式是直接把某些项置零， 这样子有些粗暴， soft的形式是让w≤C， 加了soft constrain， VC维度更小(对不加constrain而言)， better generalization。

  
  
  constrain

• 那么如何求解constrain形式的规划问题呢。 问题的解空间是一个椭圆(蓝色)， 而约束是一个圆(红色)， 最优解存在与两者的梯度反向平行的位置上， 即夹角越大越好。 转成第二个表达式， 我们可以将问题重新转化， 可以看到C越大的话， \lambda就越小。

  
  
  constrain sol

• 代入， 求解。 求解结果有点是矩阵加了扰动的意思？？？

  
  
  problem
  
  
  solution

• 从结果我们看到， 需要选择一个比较好的lambda， 结果才能更好。

  
  
  Result

• 上面提到的技术其实是称之为weight decay。 我们可以看到， 它就是在梯度更新的时候， 不选择原来的w(t)， 而是让w(t)更小一些(1-xx)， 这样可以防止w一直上涨的太厉害， 起到一种shrinkage的效果。另外， 我们也可以规定不同的w赋予不同的regularization， 起到importance emphasis的作用。

  
  
  weight decay
  
  
  weight decay2

• 如果使用weight growth呢， 效果显然是不好的， Eout直线上升。 前面我们提到的随机noise是高频的， 而确定性noise也是非平滑的， 其实价格regularization就是让最终选择到的hypothesis更加平滑！ 这样可以消除这两种noise的影响。

  
  
  weight growth

• 更一般形式的表达。 相比于Ein， Eaug是Eout更好的表达。

  
  
  general

• 如何选择regularizer呢， 指导思想是要往target function的方向去， 这个方向是一个更加平滑或者说让模型更加简单的方向。在神经网络中， 观察tanh函数， 如果w比较小， 那么激活之后就是在线性区域， 而如果w比较大， 激活之后就是1， -1 这样的布尔值了。 或者说， 我们可以删除权重， 这将使得VC维更小， better generation。 如图中的公式， 若w比较小， beta dominant， 若w比较大， 值接近雨1， beta diminish， 这样就起到了删除权重的作用了。

  
  
  choice
  
  
  NN

• 更一般的， 用early stopping， validation来防止过拟合。对随机噪声来说， 如果它不存在， 我们就不用regularization了， 噪声越多， 需要的regularization也就越多了； 确定性噪声同理。

  
  
  regularizer
  
  
  lambda