VC Theory: Hoeffding Inequality

2024-01-28 19:08
文章标签 theory vc hoeffding inequality

本文主要是介绍VC Theory: Hoeffding Inequality,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

建议感兴趣的同学仔细看一下这几课的内容(当然前面几课的内容作为背景铺垫也是非常推荐的),教授讲得非常好,生动形象,并且思路非常清晰,忽略掉了一些细节和不同的 variants,抓住了主要脉络让人理解 Statistical Learning Theory 背后的思想,而不是一下子就陷入一堆复杂的理论和推导中。而本文我希望将教授省略掉的一些细节补全出来,也是帮助自己整理一下学到的东西。

首先是问题设定,在这几课中一直讲的是 binary classification,记 input space 为 ,output space 为 ,假设  上有一未知的概率分布 ,给定一个 hypothesis space ,一个 loss function ,和  个独立地从  里采样出来的数据 sample ,目的是为了得到一个 final hypothesis  作为我们学习的结果,使得 out-of-sample error

足够小。这里有几点需要说明的地方,一是关于 ,这是最 general 的 case,我们可以写为 ,有一种简单的特殊情形是  只取值  或 ,也就是每个  确定地(更确切地说 almost surely)对应一个 ,此时  和  的关系可以用一个函数来刻画,通常称作是 target function。不过在课上教授提到即使是最 general 的 case,通常也不推荐写做联合分布  的样子,因为我们所关注的(需要学习的)其实只是 ,而  只是为了让我们得以在一个概率框架下来讨论问题而引入的,并不是我们很关心的对象11当然,对于 Generative Modeling 派系而言的话  也是需要去学习的,但那并不属于我们这里讨论的问题。。不过有时候为了方便我们仍然会使用联合分布的记号,甚至有时候直接记  以及 

此外,在 binary classification 中,我们将 loss function (在课中称为 error measure 或者 pointwise error measure)定为 binary error:

首先面临的问题是要优化的目标  是无法计算的,因为  是未知的。所以我们采取一种迂回战术:在第 6 课 Theory of Generalization 中最后得到了这样形式的一个 generalization bound,根据 training sample  的随机性,以不低于  的概率满足

eq: 1 »

这里  称为 in-sample error,是在给定的训练数据上计算的 error,具体定义为

这一项是我们可以计算的而  项是这套理论中的一个重点,这里我们需要知道的是它是可以估计的就可以了。这样一来,我们就可以通过优化  的方式来间接地优化无法计算的 。这就是这里所讲的理论的一个简单蓝图。

接下来让我们陷入到细节中去,首先是建立  和  之间的联系。首先,对于任意 ,我们记  为 ,因此  实际上是一个从  到  的函数,将它在  上求期望  实际上就是 out-of-sample error 。现在固定一个 ,将 sample space  中的每一对点  带入进  中,都可以得到  或  这两个值22因为我们这里用的是 binary loss。,在课堂上教授用了花瓶里装的两种不同颜色的鹅卵石来做了一个很形象的比喻。

虽然由于  未知我们没法直接求,但是我们有从  中采样出来的一个 sample,也就是我们的训练数据,在概率论中根据 sample 来估算期望有一个标准的做法,就是计算“经验期望”,可以看到这其实就是我们刚才定义的 。评估这个估计的好坏的方法是使用大数定理,我之前也介绍过大数定理在机器学习中的作用。大数定理有非常多个不同的变种和形式,为了避免混乱,在课上教授只选用了 Hoeffding 不等式 (Hoeffding, 1963),这里我们也集中在这个形式上。

thm: 1 »

定理 Hoeffding Inequality

设相互独立的随机变量  满足 ,记 ,则对任意 ,有

对于固定的 ,我们可以将定理中的  与  对应起来,此时  就和  对应起来,而  则对应了 ,又注意到 binary loss 只取 0 和 1 两个值,因此定理中 ,于是我们可以得到如下的简单形式:

eq: 2 »

注意到在课堂中使用的实际上是这样的形式:

eq: 3 »

实际上只要注意到

其中红色的部分用  与  进行对应,就可以立即从 (eq: 2) 得到 (eq: 3) 了。

接下来,我们记 (eq: 2) 右边为 ,反解出

于是,由 (eq: 2) 我们可以得到以不低于  的概率,满足

eq: 4 »

这正是我们在 (eq: 1) 中所想要的形式。不过我们有一个问题,也是我一直在强调的,这里所有的 formulation 都只是针对一个固定的  而言的,在机器学习问题中我们需要处理一个 hypothesis space  里的所有 ,特别是我们并不事先知道我们的学习算法最终会选取  中的哪一个元素作为 final hypothesis,因此我们需要同时对所有的  保证 (eq: 4) 都成立。如果  是个有限集,可以很容易通过 Union Bound 得到一个结果,这个我在大数定理军团中也介绍过用,不过如果  是无限集,就必须更精细地分析  的结构,这是下次要介绍的内容。本文余下的部分将会用来证明定理 (thm: 1),不感兴趣的同学可以直接跳过。

图 1    indicator function bounded above by the exponential function.

进入证明之前,我们首先注意到定理 (thm: 1) 中式子左边的形式是 ,我们可以用 indicator function 把它换一个形式:

再注意到这个形式的 indicator function 可以被一个指数函数 bound 住,见图 (fig: 1)。于是

这里  是任意一个正数。这个变化在证明包括 Hoeffding 不等式在内的几个类似的不等式里都有用到。直接套用这个式子,我们可以得到

eq: 5 »

上式中最后一步是由  的独立性得到的。接下来我们尝试去 bound 红色的部分。

lem: 1 »

引理

设  是一个随机变量,且 ,则对任意实数 ,我们有

证明很简单,注意到指数函数是凸函数,因此在区间  中的函数图像会在连接  和 两点的直线之下,运用直线方程的两点式公式,然后两边同时求期望即证。

将刚才的红色部分套用这个引理,可以得到:

eq: 6 »

这里  和  分别是为了简化记号而引入的符号,他们所代表的部分用对应的颜色标出。注意 是个常量,而  是依赖于  的量。现在我们记指数部分为 ,对  求导得到:

红色部分的不等式是根据均值不等式得到的。然后我们将  在  点处进行带余项 Taylor 展开:

再由指数函数的单调性加上式 (eq: 6) 立即得到:

最后,再回到式 (eq: 5),我们得到

注意到这个式子对任意  都成立的,所以现在我们可以将不等式的右边对  进行最小化,以期望得到一个最好的 bound 。显然,右边的最小值在  处取到,带入之后立即得到

于是 Hoeffding 不等式就证完了。

References

  • Hoeffding, W. (1963). Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association58(301), 13–30.

这篇关于VC Theory: Hoeffding Inequality的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/654522

相关文章

VC网络协议

// PCControlDlg.cpp : 实现文件//#include "stdafx.h"#include "PCControl.h"#include "PCControlDlg.h"#include "afxdialogex.h"#ifdef _DEBUG#define new DEBUG_NEW#endif// 用于应用程序“关于”菜单项的 CAboutDlg 对话框#ifde

VC环境下字符串转整型最终版

剑指Offer 字符串转化为整型 今天闲来无事,就搜了下这方面的知识,结果发现,这个题就是一个经典的算法题,在剑指Offer里已经详细分析了 直接上代码了,运行可靠,如果大家继续深入理解的话,参考这本书:《剑指Offer——名企面试官精讲典型编程题》 博主:http://blog.csdn.net/cadcisdhht/article/details/36875535 ---------

VC环境下window网络程序:UDP Socket程序

最近在学Windows网络编程,正好在做UDPsocket的程序,贴上来: 服务器框架函数:              socket();    bind();    recfrom();  sendto();  closesocket(); 客户机框架函数:            socket();      recfrom();  sendto();  closesocket();

VC环境下整型转换为字符串型(2)

在串口下位机的发送中,可能会用到需要发送数字,显示为字符串型的 和上一篇文字《串口中字符串转换为整型》一正一反,知识点学习会了: #include<iostream.h> #include <stdio.h> #include <string.h>   void inttostr(int m,unsigned char * str) { int length=0;   int tmp,te

New的VC编译器实现

当我们调用 new 的时候,例如 int *p = new int; 时,编译器到底作了什么工作呢?跟进断点看一看。   (在 vc debug模式下 ) double *p1 = new double ; 00411A6E  push        8    00411A70  call        operator new (4111B8h) 00411A75  add

[VC] Visual Studio中读写权限冲突

前置场景: 编译没有报错,但是运行提示 内存异常: 情景1: 如下代码运行异常,提示引发了异常:写入权限冲突。*** 是 0xFFFFF..... char* str = (char*)malloc(10);str[0] = 0x30;  解决方案:要包含头文件<stdlib.h>  情景2: 在FileA文件调用FileB文件的函数,但是在FileA中却没有声明该B函数的原型

LEAN 类型理论之注解(Annotations of LEAN Type Theory)—— 定义上相等(Definitional Equality)

定义上相等(Definitional Equality)指的是意义上相等,即同义,包括了,定义的缩写(Abbreviatory Definition),alpha转换,相同替代(substituting equals for equals)等。下面是LEAN给定的何谓 定义上相等。          注:罗列的推演规则中,如自明其义的,则不多加解析其前提、结果、或特定注解。

如何在VC中调用CLAPACK

转自http://hi.baidu.com/kaien_space/blog/item/dcb84b8b96347bd4fd1f1011.html     关于CLAPACK的使用网上的资料并不多。主要就是官方网站上的安装说明,以 及LAPACK官方论坛上的一些资料。然而,国外一般科研使用的平台都是UNIX或LINUX, 所以对于windows上使用CLAPACK的相关介绍就很少。幸

[VC MFC] 修改主菜单和子菜单的文本

VC 修改主菜单和子菜单的文本 初始化函数内加入 // ======= 更新菜单 ===================================CMenu *subMenu = this->GetMenu()->GetSubMenu(0);//更改主菜单this->GetMenu()->ModifyMenu(0,MF_BYPOSITION,IDMENU_3, _T("修

c# net8调用vc写的dll

dll程序(vc,x86) 头文件 extern "C" int __declspec(dllexport) WINAPI add(int a, int b); 实现 int WINAPI add(int a, int b) {return a + b;} c#/net8 函数声明: [DllImport("dll/Dll1.dll", CallingConvention