统计学习no-free-lunch

2020/7/141统计学习理论2020/7/142概要机器学习的基本问题和方法统计学习理论－－VC维和风险的界结构风险最小化2020/7/143机器学习的基本问题和方法•机器学习问题的表示机器学习问题的基本模型：y预测输出y’系统（S）学习机器（LM）输入x输出y(,)Fxy(,),fx2020/7/144学习问题就是：从给定的函数集中选择出能够最好地逼近系统响应的函数。这种选择是基于训练集的。训练集由根据联合分布抽取出的n个独立的同分布（i.i.d.）观测组成。(,),fx(,)Fxy11(,),,(,)nnxyxyy预测输出y’系统（S）学习机器（LM）输入x输出y(,)Fxy(,),fx2020/7/145何谓最好－－风险最小化准则损失函数：风险函数：(,(,))Lyfx()(,(,))(,)RLyfxdFxy三种主要学习问题的损失函数：0(,)(,(,))1(,)yfxLyfxyfx2(,(,))((,))Lyfxyfx((,))log((,))Lpxpx模式识别问题函数拟合问题密度估计问题2020/7/146学习的目标就是：在联合概率分布函数F(x,y)未知，所有可用的信息都包含在训练数据集中的情况下，寻找函数使它（在函数类）最小化风险泛函(,),fx0(,)fx()R。2020/7/147经验风险最小化(ERM)函数拟合问题：最小二乘概率密度估计：最大似然方法模式识别：使训练集样本错误率最低的分类器机器学习的基本问题和方法11()(,(,))NempiRLyfxN211()((,))NempiiRyfxN11()log((,))NempiiRpxN2020/7/148经验风险最小化方法的问题有限样本下：•经验风险最小是否是期望风险最小？•以经验风险最小得到的解，其期望风险如何？•如果存在多个使经验风险最小的解的情况(比如线性可分的情况)，那一个使期望风险最小？2020/7/149机器学习的基本问题和方法•复杂性与推广能力例1：函数拟合f(x,α)=sin(αx)经验风险最小并不意味着期望风险最小。2020/7/1410例2：模式识别以经验风险最小得到的解，其期望风险可能很大2020/7/1411经验风险都为0，那一个使期望风险最小？例3:线性可分问题2020/7/1412统计学习理论－－VC维和风险的界•VC维－－描述学习机器的复杂性线性函数正弦函数的VC维()()?empRR2020/7/1413推广性的界的定理：hVC(/)VC(/)//(/)/nhnhhnhnhnh其中n为样本数，为学习机器维，称为置信范围或信任。是随n增大而减小的函数。由上式可知：越小，越大，用经验风险近似期望风险就有较大的误差，用经验风险最小化取得的最优解可能具有较差的推广性。而较大，则期望风险最小化得到的最优解就接近实际的最优解。()()(/)empRRnh2020/7/1414VChVC对于特定的问题，样本数目n一般是固定的，维越大，真实风险与期望风险间的差就越大。因此我们在设计分类器时，不但要使经验风险最小化，还要使机器的复杂性也即维尽量小，从而使期望风险最小。()()(/)empRRnh(/)/nhh是随n增大而减小的函数2020/7/1415VC维与推广性的界的讨论：•函数集的VC维不一定等于自由参数的个数。•尚无一般方法对任意函数集计算VC维。•推广性的界是对最坏情况下的结论，所给出的界往往是松的。•这个界在对同一类学习函数进行比较时是有效的，可以指导我们从函数集中选择最好的函数，但不同函数集间比较不一定成立。•近邻法的讨论：近邻法的VC维无穷大，但一般结果却较好。原因－－未使用经验风险最小化原则。2020/7/1416设计学习机器的目标：同时最小化经验风险和置信范围。如何同时最小化－结构风险最小化原则把函数集S分解为一个函数子集序列（子集结构）S1≤S2……≤Sk……≤S,使得各子集能够按照VC维的大小排列h1≤h2≤……hk≤…，这样同一个子集中的置信范围就相同。容许子集结构的条件：VC维的条件:各子集的VC维有限损失函数的条件:有界非负满足或者对一定的参数对满足：结构风险最小化2020/7/1417(/)nh结构风险最小化原则（SRM）2020/7/1418两种构造性方法：2020/7/1419•理论如何应用到SVMSVM的直观形式2020/7/1420没有免费的午餐在很多的算法中，哪一个是最好的？两个分类器A和B在训练集上有同样好的性能，我们相信其中简单的一个在测试集上的性能更好。为什么？我们更倾向与比较平滑的分类器。为什么？2020/7/1421没有免费的午餐物理学守恒定律：能量守恒，热力学第二定律模式识别领域是否存在类似的定理？2020/7/1422举例训练集测试集两个分类器2020/7/1423没有免费的午餐2020/7/1424图示说明2020/7/1425没有免费的午餐不存在任何一种模式分类算法具有天然的优越性，甚至不比随机猜测更好。如果某种算法对某个特定的问题看上去比另一种算法更好，其原因仅仅是它更适合这一特定的模式分类任务。2020/7/1426没有免费的午餐对于要解决的分类问题，什么是事物的本质？先验信息数据的分布训练样本的数量代价函数2020/7/1427特征与模式是否存在最好的特征表示？2020/7/1428特征与模式4个人：正常，左眼瞎，右眼瞎，全瞎2020/7/1429丑小鸭定理如果只使用有限的谓词集合来区分待研究的任意两个模式，那么任意这样两个模式所共享的谓词数目是一个与模式的选择无关的常数。此外，如果模式的相似程度是基于两个模式共享的谓词的总数，那么任何两个模式都是“等相似”的。2020/7/1430丑小鸭定理不存在与问题无关的最好的特征集合或属性集合。