【机器学习第十二章——计算学习理论】
机器学习第十二章——计算学习理论
- 12.计算学习理论
- 12.1 基础知识
- 12.1 可能学习近似正确假设(PAC)
- 12.3 有限假设空间
- 12.4 VC维
12.计算学习理论
12.1 基础知识
-
从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力
-
这个理论要回答的问题是:
- 在什么样的条件下成功的学习是可能的?
- 在什么条件下某个特定的学习算法可保证成功运行?
-
机器学习理论的一些问题:
- 是否可能独立于学习算法确定学习问题中固有的难度?
- 能否知道为保证成功的学习有多少训练样例是必要的或充足的?
- 如果学习器被允许向施加者提出查询,而不是观察训练集的随机样本,会对所需样例数目有怎样的影响?
- 能否刻画出学习器在学到目标函数前会有多少次出错?
- 能否刻画出一类学习问题中固有的计算复杂度?
-
主要解决的问题是:
- 需要多少训练样例才足以成功地学习到目标函数
- 学习器在达到目标前会出多少次错
12.1 可能学习近似正确假设(PAC)
- 可能近似正确学习模型(PAC)
- 指定PAC学习模型适用的问题
- 在此模型下,学习不同类别的目标函数需要多少训练样例和多大的计算量
X表示所有实例的集合,C代表学习器要学习的目标概念集合,C中每个目标概念c对应于X的某个子集或一个等效的布尔函数c:
X → { 0 , 1 } X→\{0,1\} X→{0,1}
假定实例按照某概率分布D从X中随机产生
学习器L在学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后,L必须从H中输出某假设h,它是对c的估计
我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新实例与训练数据具有相同的概率分布
我们要求L足够一般,以至可以从C中学到任何目标概念而不管训练样例的分布如何,因此,我们会对C中所有可能的目标概念和所有可能的实例分布D进行最差情况的分析
12.3 有限假设空间
- PAC可学习性很大程度上由所需的训练样例数确定
- 随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度
- 我们把样本复杂度的讨论限定于一致学习器(输出完美拟合训练数据的学习器)
- 能够独立于特定算法,推导出任意一致学习器所需训练样例数的界限
- 变型空间:能正确分类训练样例D的所有假设的集合。
V S H , D = { h ∈ H ∣ ( ∀ < x , c ( x ) > ∈ D ( h ( x ) = c ( x ) ) ) } VS_{H,D}=\{h\in H|(\forall\quad <x,c(x)>\quad\in D(h(x)=c(x)))\} VSH,D={h∈H∣(∀<x,c(x)>∈D(h(x)=c(x)))}
-
变型空间的重要意义是:每个一致学习器都输出一个属于变型空间的假设
-
因此界定任意一个一致学习器所需的样例数量,只需要界定为保证变型中没有不可接受假设所需的样例数量
-
定义:考虑一假设空间H,目标概念c,实例分布D以及c的一组训练样例S。当
V S H , D VS_{H,D} VSH,D
中每个假设h关于c和D错误率小于ε时,变型空间被称为c和D是ε-详尽的。
( ∀ h ∈ V S H , D ) e r r o r D ( h ) < ε (\forall h\in VS_{H,D})error_D(h)<ε (∀h∈VSH,D)errorD(h)<ε
-
详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于ε
-
从学习器的角度看,所能知道的只是这些假设能同等地拟合训练数据,它们都有零训练错误率
-
只有知道目标概念的观察者才能确定变型空间是否为ε-详尽的
-
但是,即使不知道确切的目标概念或训练样例抽取的分布,一种概率方法可在给定数目的训练样例之后界定变型空间为ε-详尽的
-
定理7.1(变型空间的ε-详尽化)
-
若假设空间H有限,且D为目标概念c的一系列m>=1个独立随机抽取的样例,那么对于任意0=<ε<=1,变型空间不是ε-详尽的概率小于或等于:
∣ H ∣ e − ε m |H|e^{-εm} ∣H∣e−εm -
证明:
-
令
h 1 , . . . , h k h_1,...,h_k h1,...,hk
为H中关于c的真实错误率大于ε的所有假设。当且仅当k个假设中至少有一个恰好与所有m个独立随机抽取样例一致时,不能使变型空间ε-详尽化。 -
任一假设真实错误率大于ε,且与一个随机抽取样例一致的可能性最多为1-ε,因此,该假设与m个独立抽取样例一致的概率最多为
( 1 − ε ) m (1-ε)^m (1−ε)m -
由于已知有k个假设错误率大于ε,那么至少有一个与所有m个训练样例都不一致的概率最多为
当 0 ≤ ε ≤ 1 , 则 1 − ε ≤ e ε k ( 1 − ε ) m ≤ ∣ H ∣ ( 1 − ε ) m ≤ ∣ H ∣ e − ε m ( 7.2 ) 当0\leqε\leq1,则1-ε\leq e^ε\\ k(1-ε)^m\leq|H|(1-ε)^m\leq|H|e^{-εm}\quad\quad(7.2) 当0≤ε≤1,则1−ε≤eεk(1−ε)m≤∣H∣(1−ε)m≤∣H∣e−εm(7.2)
-
-
-
定理7.1基于训练样例的数目m、允许的错误率ε和H的大小,给出了变型空间不是ε-详尽的概率的上界
-
即它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设(错误率大于ε的假设)剔除出去的概率
-
利用上面的结论来确定为了减少此“未剔除”概率到一希望程度ε所需的训练样例数
由 ∣ H ∣ e − ε m ≤ δ → m ≥ 1 ε ( ln ∣ H ∣ + ln ( 1 / δ ) ) 由|H|e^{-εm}\leq\delta→m\geq\frac{1}{ε}(\ln|H|+\ln(1/\delta)) 由∣H∣e−εm≤δ→m≥ε1(ln∣H∣+ln(1/δ)) -
式子7.2提供了训练样例数目的一般边界,该数目的样例足以在所期望的值ε和δ程度下,使任何一致学习器成功地学习到H中的任意目标概念
-
训练样例的数目m足以保证任意一致假设是可能(可能性为1-δ)近似(错误率为ε)正确的
-
m随着1/ε线性增长,随着1/δ和假设空间的规模对数增长
-
上面的界限可能是过高的估计,主要来源于|H|项,它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和
12.4 VC维
-
分层有向无环图的特点:
- 节点可划分成层,即所有第1层出来的有向边进入到第l+1层节点
- 没有有向环,即有向弧形成的回路
-
这样网络的VC维的界定可以基于其图的结构和构造该图的基本单元的VC维
-
定义一些术语
-
G表示神经网络
-
n是G的输入数目
-
G只有1个输出节点
-
G的每个内部单元Ni最多有r个输入,并实现布尔函数
c i : R r → { 0 , 1 } c_i:R^r→\{0,1\} ci:Rr→{0,1}
形成函数类C -
定义C的G-合成:网络G能实现的所有函数的类,即网络G表示的假设空间,表示成
C G C_G CG
-
-
定理7.4分层有向无环网络的VC维
- 令G为一分层有向无环图,有n个输入节点和s>=2个内部节点,每个至少有r个输入,令C为VC维为d的
R r R^r Rr
上的概念类,对应于可由每个内部节点s描述的函数集合,令
C G C_G CG
为C的G合成,对应于可由G表示的函数集合,则
V C ( C G ) < = 2 d s log ( e s ) VC(C_G)<=2ds\log(es) VC(CG)<=2dslog(es)
- 令G为一分层有向无环图,有n个输入节点和s>=2个内部节点,每个至少有r个输入,令C为VC维为d的
-
假定要考虑的分层有向无环网络中单个节点都是感知器,由于单独的r输入感知器VC维为r+1,代入定理7.4和式子7.7,得到
V C ( C G p e r c e p t i o n s ) ≤ 2 ( r + 1 ) s log ( e s ) VC(C_G^{perceptions})\leq2(r+1)s\log(es) VC(CGperceptions)≤2(r+1)slog(es)m ≥ 1 ε ( 4 log ( 2 / δ ) + 16 ( r + 1 ) s log ( e s ) log ( 13 / ε ) ) m\geq\frac{1}{\varepsilon}(4\log(2/\delta)+16(r+1)s\log(es)\log(13/\varepsilon)) m≥ε1(4log(2/δ)+16(r+1)slog(es)log(13/ε))
-
上面的结果不能直接应用于反向传播的网络,原因有两个:
- 此结果应用于感知器网络,而不是sigmoid单元网络
- 不能处理反向传播中的训练过程
相关文章:
【机器学习第十二章——计算学习理论】
机器学习第十二章——计算学习理论 12.计算学习理论12.1 基础知识12.1 可能学习近似正确假设(PAC)12.3 有限假设空间12.4 VC维 12.计算学习理论 12.1 基础知识 从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力 这个理论要…...
Docker私人学习笔记
俗话说“好记性不如烂笔头”,编程的海洋如此的浩大,养成做笔记的习惯是成功的一步! 此笔记主要是antlr4.13版本的笔记,并且笔记都是博主自己一字一字编写和记录,有错误的地方欢迎大家指正。 一、基础概念:…...
谷粒商城实战笔记-233~235-商城业务-认证服务-单点登录流程-原理
文章目录 一,场景二,单点登录流程 一,场景 包含以下三节的内容: 一,233-商城业务-认证服务-单点登录流程-1二,233-商城业务-认证服务-单点登录流程-2三,233-商城业务-认证服务-单点登录流程-3…...
机器学习在旅游业的革新之旅
机器学习在旅游业的革新之旅 随着科技的飞速发展,尤其是人工智能(AI)技术的广泛应用,各个行业都迎来了前所未有的变革。其中,旅游业作为全球经济的重要支柱之一,更是受益匪浅。机器学习(Machin…...

OpenCTI:开源网络威胁情报平台
OpenCTI 是一个开源平台,旨在帮助组织管理其网络威胁情报 (CTI) 数据和可观察数据。 该平台由 Filigran 开发,使用基于 STIX2 标准的知识模式构建数据。 它采用现代 Web 应用程序架构,配备 GraphQL API 和用户友好的前端。 OpenCTI 与 MIS…...
linux shell 脚本 let 数学计算
linux shell 脚本 let 数学计算 http://www.codebaoku.com/it-shell/ let命令中的算术表达式必须用双引号括起来,以避免解释器对特殊字符进行处理。 在变量的计算中,不需要使用$符号来表示变量, #!/bin/shweek_daydate %u echo $week_day…...

mp3和mp4的区别是什么?怎么把mp3转成mp4?(全)
在生活中我们或多或少会听到“mp3”和“mp4”,那么什么是mp3和mp4呢?mp3和mp4的区别是什么?mp3是一种音频压缩技术,旨在在不显著牺牲音质的前提下减小音频文件的体积,使其适用于音乐和其他音频内容的存储与传输。相比之…...
合并params和query参数
场景:三级分类只有query参数,搜索框使用params参数。为了解决这个问题,文中在typeNav的index.vue和Head/index.vue分别进行了判断和处理,确保在不同的路径下合并params和query参数能正确合并并传递。 如何当点击联动框时跳转到se…...

[数据集][目标检测]工程机械车辆检测数据集VOC+YOLO格式3189张10类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):3189 标注数量(xml文件个数):3189 标注数量(txt文件个数):3189 标注…...
构建域名服务器-BIND:Linux端的安装过程及配置文件详解
文章目录 构建域名服务器工具-BINDBIND的安装BIND配置文件详解1. /etc/named.conf:2. /etc/named.rfc1912.zones:3. /var/named/named.localhost:4./etc/logrotate.d/named5./etc/named.iscdlv.key6./etc/named.root.key7./etc/rndc.conf8./e…...
linux查询目录文件基础操作
基础命令 展示所有目录 ls 长格式列出(显示文件权限、所有者、大小和最后修改时间): ls -l 忽略大小写查询 ls | grep -i name 查找特定名称的文件: find /path/to/search -name "filename" 忽略大小写查找文件&#…...

搭建TestBench,收藏这几条基本框架就够了
Verilog功能模块HDL设计完成后,并不代表设计工作的结束,还需要对设计进行进一步的仿真验证。掌握验证的方法,即如何调试自己的程序非常重要。在RTL逻辑设计中,要学会根据硬件逻辑来写测试程序即写Testbench。Verilog测试平台是一个…...
怎么利用住宅代理提高数据抓取效率
在大数据时代,数据抓取已经是从互联网收集数据的关键手段,得到了广泛的应用。不论是网络营销、电商平台、或者是新闻网站,数据抓取都可以帮助企业或者是个人收集到大量的数据。但是随着反爬虫技术的不断发展,传统的爬虫方法已经不…...
c#中的ManuaResetEvent
在C#中,ManualResetEvent 是一个同步事件,用于线程间通信。它允许一个或多个等待的线程等待某个事件的发生。当事件被设置为已发生(或称为“信号”)状态时,所有等待的线程都会被释放,并且可以继续执行。 以…...

EE trade:黄金投资的利弊与要点
黄金投资作为一种相对传统的投资途径,存在着特定的优势与风险。接下来详细剖析一下黄金投资的优缺点。 1、黄金投资的优点 有效对抗通货膨胀 在通货膨胀时期,黄金往往能有出色的表现,其价值通常会上升,如此一来便能够为投资者提…...
数据仓库模型评估的标准
面试中,肯定有数仓同学被问到:数据模型如何去评估、如何优化,那今天就聊一聊这个话题。 基本概念 模型:表达的是某一个主题、某一个业务过程,赋值业务价值,最终落地还是一个建表的过程 数仓模型…...
121231
实打实大苏打...

【机器学习】逻辑回归原理(极大似然估计,逻辑函数Sigmod函数模型详解!!!)
目录 🍔 逻辑回归应用场景 🍔 极大似然估计 2.1 为什么要有极大似然估计? 2.2 极大似然估计步骤 2.3 极大似然估计的例子 🍔 Sigmod函数模型 3.1 逻辑斯特函数的由来 3.2 Sigmod函数绘图 3.3 进一步探究-加入线性回归 3…...

网络热门编程项目导学:黑马点评
本文作者:程序员鱼皮 免费编程学习 - 编程导航网:https://www.code-nav.cn 大家好,我是鱼皮。 之前已经给大家分享了三个全栈项目,比如瑞吉外卖什么的,这几个项目都是侧重于带大家学习框架的运用、以及一些简单的业务…...

如何在本地和远程删除 Git 分支?
如何在本地和远程删除 Git 分支? 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰,211科班出身,就职于医疗科技公司,热衷分享知识,武汉城市开发者社区主理人 擅长.n…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...