网易公开课，第9,10课
notes，http://cs229.stanford.edu/notes/cs229-notes4.pdf
这章要讨论的问题是，如何去评价和选择学习算法
Bias/variance tradeoff
还是用这组图，学习算法追求的是generalization error（对未知数据的预测误差），而不是training error（只是对训练集）
最左边，underfit，我们说这种学习算法有较大的bias
Informally, we define the bias of a model to be the expected generalization error even if we were to fit it to a very (say, infinitely) large training set.
即在用足够多的训练集的情况下，仍然有较大的generalization error
最右边，overfit， 我们说这种学习算法有较大的variance
在比较小或有限的训练集的情况下，更容易发生
所以对于学习算法，我们需要tradeoff bias VS. variance，避免过于简单或复杂的学习模型
Preliminaries
在这章为了达到评价和选择算法的目的，我们需要解决下面几个问题，
First, can we make formal the bias/variance tradeoff that was just discussed? The will also eventually lead us to talk about model selection methods, which can, for instance, automatically decide what order polynomial to fit to a training set.
是否可以形式化bias/variance，因为这样的话，我们就可以对每个学习模型计算出bias/variance ，从而可以自动选择模型
Second, in machine learning it’s really generalization error that we care about, but most learning algorithms fit their models to the training set. Why should doing well on the training set tell us anything about generalization error? Specifically, can we relate error on the training set to generalization error?
对于学习算法，我们真正关心的是generalization error，而我们之前都是用training error来作为优化目标
这样想当然应该是合理的，但是有理论依据吗？我们真的可以用training error来近似generalization error吗？他们之间有怎样的关系？
这是我们下面首先要讨论的问题
Third and finally, are there conditions under which we can actually prove that learning algorithms will work well?
结论性的问题，在满足什么样的条件下，我们就可以证明这个学习算法是work well的？
在讨论上面问题之前，先介绍两个lemma，后面会用到，
第一个是union bound，这个定理显而易见
第二个是Hoeffding inequality
其实要表达的意思是， 当m足够大的时候，预估值
会逼近真实值
给个例子，Z满足bernoulli分布，最好的例子就是抛硬币，对于均匀的硬币，正面的概率是1/2
但是如果你抛10次，计算出现正面的概念可能不是1/2，但如果你抛100万次或更多，你抛的越多，那么得到正面的概念一定是趋向于1/2（bernoulli大数定理）
参考，机器学习物语(2):大数定理军团 Free Mind
下面开始定义我们的问题，即上面提到的第二问题，
定义实验误差
，对于训练集S，m个数据点
实验误差，实验值不等于真实值的个数/m，很容易理解
前面定义过
，成立为1，不成立为0
定义真实误差
，即给出一个新的满足D分布的点（x，y），预测出的h不等于真实值y的概率
现在为了阐述简单，假设h为线性分类函数
那么最简单的最基本的学习算法是，Empirical risk minimization (ERM)，即以最小化training error为目标去求得最优参数
这个算法的问题是，往往很难求解，并且是非凸的，而逻辑回归或SVM都可以看做是ERM的凸化的近似优化算法
但这里讨论学习理论，出于简单考虑，就以ERM为例子
上面的ERM是以为优化参数，其实一个就对应于一个h
所以从通用考虑，我们这里用h做为优化参数，这样更通用，因为h可以为任意函数，只要可以将input映射到{0,1}即可
所以上面的ERM就表示成这样，容易理解吗？
The case of finite H
下面先讨论的case是，H用的h函数为有限个，我们要从有限个h中找到最优的h
好，然后这节的内容就是想证明，对于有限个，这里假设k个h，training error是对于generalization error的可靠的estimate
其实，我觉得的基于Hoeffding inequality，这个证明是显然成立的呵呵，当然下面的证明关键是可以给出formal的形式
对于
，我们定义，
那么就有，只是把上面公式中的换成Z
然后我们的目标是，证明对于H中的所有h都满足，
是有个上届的，所以可以用后者来近似的预估后者
首先，H中存在h满足
的概念如下，存在即或，所以可以用union bound
并把Hoeffding inequality代入的到一个不等式
然后关键的一步，两边取反
存在h使，取反就是对于所有的h满足
，这个的概率是
这个说明什么，即是有个上界
，这个事件发生的概率当m足够大的时候是趋于1的，即必定发生，即完成证明
这个结果称为uniform convergence result，一致性收敛结果
这个式子中有3个要素，常量
，样本大小m，和概率值
一致性收敛就是给定和m的情况下，如果算出概率值
当然这个式子，其实还有另外两种表达方式，
1. 给定和概率值
，求出至少要多大的m
这个用上面的式子很容易算出，算出的m称为algorithm’s sample complexity，样本复杂度
可以理解为，需要多大的样本，样本误差才可以近似于一般误差，满足上面的不等式
2. 给定和m，求出上届
大家看看一致性收敛结果，证明半天，只是证明对于某个h，他的实验误差和真实误差之间的关系，我们可以更进一步，
，h hat表示通过实验误差最小化，找出的h，即训练出的h
，h star表示通过一般误差最小化，找出的h，即真正的最优的h
那么我们是否可以找出h hat和h star之间误差的关系了？ 于是得到如下结论
第一个不等式就是h hat一致性收敛不等式的转换，
第二个不等式，因为对于实验误差
而言，h hat是最小的，所以h star的实验误差也至少>=h hat的实验误差
第三个不等式，将h star的一致性收敛不等式代入的结果，
所以大家看到，h hat和h star的一般性误差之间的差距也是有上界
的，即我们可以用h hat来近似h star
正式的写成Theorem，并且将其中的
和
替换成具体的公式
这个式子很有意思，可以非formal的反应出之前说的bias/variance之间的tradeoff
在模型选择时，目的是尽量减小
，即我们训练出的h的真实误差
比较自然的想法是将hypothesis class H，推到更高的函数空间
，比如将线性函数族扩展成二次函数族，后者是包含前者的，选择的对象函数多了，自然更有可能找到真实的h，即上面的第一项
会减小，所以可以将第一项用于表示bias
但更大的函数空间，会导致k变大，所以第二项会变大，这个对应于variance
最后，得到这个推论，即满足上面定理，m的样本复杂度，这个其实和前面那个一样，因为这个定理本身就是由一致性收敛推导出的，所以两个样本复杂度也是一样的
The case of infinite H
上面讨论的是有限的hypothesis，但对于一些hypothesis classes是包含无限的functions的，比如任何以real number作为参数的case
对于无限的case，我们是否仍然可以得到上面类似的结论？
我们先来直观的看一个argument，虽然不是很formal或right
我们假设H是以实数作为参数的，因为计算机里面是用64bit来表示实数的，当我们有d个参数的时候，
我们近似有
个hypothesis函数，可以看成无限个我们把k代入上面的Corollary定理，
可以看到那个log很关键，它把一个指数关系变成线性关系了
上面的式子说明，对于无限的hypothesis而言，如果要满足Corollary定理，样本复杂度m只需要和参数个数d满足线性关系
虽然这个argument不是那么正确或formal，不过很直观
下面我们更formal的来阐述这个argument，
先介绍一些定义，
首先是，shatter
直观的说，就是如果H中总能找到一个function可以正确的将S中的item正确分类（item可以任意取值）
看这个图，可以说明二维的线性分类是可以shatter这个3个元素的集合的
再者，定义VC维
H可以shatter的最大集合的size就是H的VC维
前面说明的二维的线性分类器的VC维就是3，你可以试试对于任意size为4的set，二维线性分类器都无法shatter
其实对于某些size为3的set，也无法shatter，比如下面这个set
但是只要存在size为3的set可以被H shatter，我们就可以说H的VC维为3
并且可以证明对于n维的线性分类器，它的VC维为n+1
故可以给出一致性收敛，
表明对于无限的H中的每个h，一般误差和实验误差的差值是有上届的，并且对于有限的VC维，只要让样本复杂度m足够大，就可以达到一致性收敛
第二个式子，因为对于有限的case，我们可以从一致性收敛推导出
故对于无限的case，这里可以直接代入，从而给出无限维的corollary定理
表明只需要样本复杂度m和H的VC维成线性关系，那么就可以满足一致性收敛
本文章摘自博客园，原文发布日期：2014-06-06
