【ML学习笔记】8:PAC可能近似正确

2023-12-09 14:58

本文主要是介绍【ML学习笔记】8:PAC可能近似正确,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

简述

PAC的意思

Probably Approximate Correct直译过来就是”可能近似正确”,这里面用了两个描述”正确”的词,可能和近似。
“近似”是在取值上,只要和真实值的偏差小于一个足够小的值就认为”近似正确”;”可能”是在概率上,即只要”近似正确”的概率足够大就认为”可能近似正确”。
这里写图片描述

泛化误差随学习复杂性变大

上节查漏补缺中了解到了,如果训练集不是很大,也就是用来给学习机器学习的样本数量比较有限的情况下,如果过于追求让经验风险小,学习复杂性太高,会导致过学习现象,也就是学习出来的模型的推广能力变差,这可以用泛化误差变大来表征。

机器学习所做的事情

先看看到现在为止理解的,机器学习所做的事情是,从假设空间(暂时理解成要选择的函数集/模型集)中选取一个假设(暂时理解成函数/模型),对于训练集中的样本能较好的完成任务,并且对于外来的样本,也能较好的完成任务(泛化误差较小)。这样学习到的学习机器才是一个有效的模型。
这里写图片描述

PAC所做的事情

上面那张图能看出来,机器学习关心的是从假设空间中以什么样的方式选出的假设才是最优的,也就是选哪个。而PAC关心的是能不能从假设空间空选出一个最优的假设,也就是说在这样有限的训练集下,能不能在假设空间中找到一个好的假设来完成任务。也就是说PAC可以用来判断达没达到可以选择出足够好的假设来解决问题的下限
这里写图片描述

以近似正确(AC)代替正确(C)

如果是完全意义上的正确,那么肯定是对实例空间里的样本经验风险为0,同时又对外来的实例泛化误差为0,这显然是不可能的。而且经验风险太小也不是一件好事(过学习从而推广能力下降),所以只要设定一个阈值,只要选取出的假设h的泛化误差E(h)不超过这个值(即近似正确)就认为是”正确”的了,而不是去追求完全的”正确”。
这里写图片描述

以可能近似正确(PAC)代替近似正确(AC)

实际上,对于所有外来的实例,假设h都能做到”近似正确”,这也几乎是不可能的一件事。只要对于多数的外来实例,都能做到”近似正确”,也就是说设定一个概率的阈值,只要”近似正确”的频率不小于这个概率阈值(即可能近似正确),就认为是”近似正确”的了,而不是去追求对所有训练集外的实例都”近似正确”。
这里写图片描述
这里常常给出显著性水平,也就是说只要机器学习对外来的随机样本失败的频率被限定在这个值以内。用总的概率1减去它就是置信度,作为判断”可能近似正确”的阈值。

PAC可学习

如果学习机器在短时间(多项式级别)内根据少量的(多项式级别)的训练集样本m,能够找到一个好的假设h,满足上面的那个式子,那么就说这个问题是PAC可学习的。

一般理论边界

显然在给定的泛化误差和显著性水平,一个PAC可学习的问题也必须要有足够多的样本m才能完成任务,而这个样本数m有一个一般理论边界M,如果m大于M那么就足以在预期的泛化误差和显著性水平下用机器学习找到的最优的假设h解决问题
这里写图片描述
这里|H|表示假设空间的大小。这个式子的意思可以这样理解,在这个问题下训练样例的数目如果是m,足以保证机器学习得到的最优假设h是可能(置信度是1-δ)近似(泛化误差是ε)正确的。

一般理论边界的局限性

这个式子局限性还很大,一方面M只是m的一个上界,而且可能还比较宽松,对于m<=M也不见得PAC不可学习;另一方面|H|是假设空间的大小,单纯地用它刻画样本复杂度不够合理(显然样本复杂度凭什么随着假设空间的大小线性增长呢),对于无限假设空间的情形显然这个式子完全失效。

函数集的VC维

这里的指示函数可以理解成能指示这个结果属于哪个类别的函数,比如结果为0或1表示两个类别。如果是有界的实函数,可以设定一个阈值,那么就可以根据函数结果转换成二分类的指示函数。

如果问题给的实例只要分成2类,那么对于一个指示函数集H,如果m个样本能被H中的函数按照所有可能的2^m种方式区分开,那么就说这个函数集能把m个样本打散
函数集H的VC维VC(H)也就是它所能打散的最大样本数目。很显然对于有限的函数集H,VC维有界:
这里写图片描述
这很好理解,试想这|H|个函数每个都能产生一种互异的二分类方式,也就有了|H|种二分类方式,而有|H|种二分类方式的样本最多也就是以2为底|H|的对数这么多个了,所以VC(H)绝不会超过它。

一个用烂了的例子

目前没有通用的关于任意函数VC维计算的方法,对一些特殊的函数知道其VC维。这个平面上的点被线性决策线二分类的例子到处都是,可以用来理解一下VC维。
假如函数集H是平面上的所有线性决策线(其实也就是直线,但是根据把点分成两边能做二分类所以叫线性决策线),显然|H|=+∞。给定的实例是平面上的点,现在用线性决策线尝试把给定的一些点打散。
对于3个以内的点,还是能打散的:
这里写图片描述
而对于4个样本点,就不能打散了,试想要把下图中的两个紫色点分到一起,线性决策线做不到:
这里写图片描述
所以这个问题的VC维VC(H)=3。

VC维衡量假设空间复杂度

用VC维代替前面的|H|来刻画假设空间下的样本复杂度,不仅能够把边界M做的更紧凑,而且可以去刻画无限假设空间下的样本复杂度。这时候新的PAC可学习边界:
这里写图片描述

这篇关于【ML学习笔记】8:PAC可能近似正确的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Spring Boot 中正确地在异步线程中使用 HttpServletRequest的方法

《SpringBoot中正确地在异步线程中使用HttpServletRequest的方法》文章讨论了在SpringBoot中如何在异步线程中正确使用HttpServletRequest的问题,... 目录前言一、问题的来源:为什么异步线程中无法访问 HttpServletRequest?1. 请求上下文与线

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

golang1.23版本之前 Timer Reset方法无法正确使用

《golang1.23版本之前TimerReset方法无法正确使用》在Go1.23之前,使用`time.Reset`函数时需要先调用`Stop`并明确从timer的channel中抽取出东西,以避... 目录golang1.23 之前 Reset ​到底有什么问题golang1.23 之前到底应该如何正确的

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu