当前位置: 首页 > news >正文

机器学习第十二章-计算学习理论

目录

12.1基础知识

12.2 PAC学习

12.3有限假设空间

12.3.1可分情形

12.3.2不可分情形

12.4VC维

12.5 Rademacher复杂度


12.1基础知识

        计算学习理论研究的是关于通过"计算"来进行"学习"的理论,即关于机器学习的理论基础,其目的是分析学习任务的困难本质,为学习算法提供理论保证,并根据分析结果指导算法设计。

        给定样例集 = {(X1  , Y2) , (X2,Y2 ),..., (Xm , Ym)} ,x_{i}\epsilon X
        令h为X到Y 的一个映射,其泛化误差为:
                                E(h ; \mathcal{D})=P_{\boldsymbol{x} \sim \mathcal{D}}(h(\boldsymbol{x}) \neq y)
        h在D上的经验误差为:
                                  E(h ; \mathcal{D})=P_{\boldsymbol{x} \sim \mathcal{D}}(h(\boldsymbol{x}) \neq y)\widehat{E}(h ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)
        后面部分将研究经验误差与泛化误差之间的逼近程度会用到几个常用不等式:
        1.Jensen 不等式:对任意凸函数 f(x) ,有:
                                                f(\mathbb{E}(x)) \leqslant \mathbb{E}(f(x))
        2.HoefIding 不等式 : 若 x_{1},x_{2}....x_{m}为m个独立随机变量,且满足 0<x_{i}<1 ,则对任意 \varepsilon >0 ,有:
\begin{array}{l} P\left(\frac{1}{m} \sum_{i=1}^{m} x_{i}-\frac{1}{m} \sum_{i=1}^{m} \mathbb{E}\left(x_{i}\right) \geqslant \epsilon\right) \leqslant \exp \left(-2 m \epsilon^{2}\right) \\ P\left(\left|\frac{1}{m} \sum_{i=1}^{m} x_{i}-\frac{1}{m} \sum_{i=1}^{m} \mathbb{E}\left(x_{i}\right)\right| \geqslant \epsilon\right) \leqslant 2 \exp \left(-2 m \epsilon^{2}\right) \end{array}
3.McDiarmid 不等式 : 若 x_{1},x_{2}...x_{m}为m个独立随机变量,且对任意1<i<m,函数f 满足:
\begin{array}{l} P\left(f\left(x_{1}, \ldots, x_{m}\right)-\mathbb{E}\left(f\left(x_{1}, \ldots, x_{m}\right)\right) \geqslant \epsilon\right) \leqslant \exp \left(\frac{-2 \epsilon^{2}}{\sum_{i} c_{i}^{2}}\right) \\ P\left(\left|f\left(x_{1}, \ldots, x_{m}\right)-\mathbb{E}\left(f\left(x_{1}, \ldots, x_{m}\right)\right)\right| \geqslant \epsilon\right) \leqslant 2 \exp \left(\frac{-2 \epsilon^{2}}{\sum_{i} c_{i}^{2}}\right) \end{array}

12.2 PAC学习

        计算学习理论中最基本的是概率近似正确 ( 简称 PAC) 学习理论 。
PAC 辨识 :对 0<\varepsilon ,\delta <1,所有 c\varepsilon C  和分布D,若存在学习算法\Im,其输出假设 h\epsilon \mathbb{R}  满足:
                                                P(E(h) \leqslant \epsilon) \geqslant 1-\delta
则称学习算法 \Im 能从假设空间中 PAC 辨识概念类 C. 
PAC 可学习 : 令m表示从分布D中独立同分布采样得到的样例数目,0<\varepsilon ,\delta <1,对所有分布D, 若存在学习算法£和多项式函数poly,使得对任何m>poly.
PAC 学习算法: 若学习算法\Im使概念类 C为PAC 可学习的,且 \Im的运行时间也多项式函数 poly ,则称概念类 C 是高效 PAC 可学习  的,称\Im为概念类C的 PAC 学习算法.
样本复杂度 : 满足 PAC 学习算法\Im所需的 m> poly 中最小的m,称为学习算法 \Im的样本复杂度.

12.3有限假设空间

12.3.1可分情形

        可分情形意味着目标概念c属于假设空间H,即 c\epsilon H。对 PAC 学习来说,只要训练集D 的规模能使学习算法\Im以概率1-\delta 找到目标假设的\varepsilon近似即可.

        我们先估计泛化误差大于 \varepsilon但在训练集上仍表现完美的假设出现的概率. 假定 h的泛化误差大于 \varepsilon,对分布 D上随机来样而得的任何样例 (x y)有:

                        P(E(h) \leqslant \epsilon) \geqslant 1-\delta\begin{aligned} P(h(\boldsymbol{x})=y) & =1-P(h(\boldsymbol{x}) \neq y) \\ & =1-E(h) \\ & <1-\epsilon \end{aligned}

        由于D包含 m个从 D 独立同分布采样而得的样例,因此,h与D  表现一 致的概率为:
                \begin{aligned} P\left(\left(h\left(\boldsymbol{x}_{1}\right)=y_{1}\right) \wedge \ldots \wedge\left(h\left(\boldsymbol{x}_{m}\right)=y_{m}\right)\right) & =(1-P(h(\boldsymbol{x}) \neq y))^{m} \\ & <(1-\epsilon)^{m} \end{aligned}

12.3.2不可分情形

        引理若训练集D包含m个从分布D上独立同分布采样而得的样例,0<\varepsilon <1,则对任意 h\epsilon H,有:\begin{array}{l} P(\widehat{E}(h)-E(h) \geqslant \epsilon) \leqslant \exp \left(-2 m \epsilon^{2}\right) \\ P(E(h)-\widehat{E}(h) \geqslant \epsilon) \leqslant \exp \left(-2 m \epsilon^{2}\right) \\ P(|E(h)-\widehat{E}(h)| \geqslant \epsilon) \leqslant 2 \exp \left(-2 m \epsilon^{2}\right) \end{array}

        推论 :若训练集D 包含 m个从分布 D上独立同分布来样而得的样例, 0<\varepsilon <1 ,则对任意 h\epsilon H以至少 1-\delta 的概率成立:

                        \widehat{E}(h)-\sqrt{\frac{\ln (2 / \delta)}{2 m}} \leqslant E(h) \leqslant \widehat{E}(h)+\sqrt{\frac{\ln (2 / \delta)}{2 m}}

        定理 :若H为有限假设空间,0<\varepsilon <1 ,则对任意 h\epsilon H,有:

                        P\left(|E(h)-\widehat{E}(h)| \leqslant \sqrt{\frac{\ln |\mathcal{H}|+\ln (2 / \delta)}{2 m}}\right) \geqslant 1-\delta

12.4VC维

        现实学习任务所面临的通常是无限假设空间,欲对此种情形的可学习性进行研究,需度量假设空间的复杂度.最常见的办法是考虑假设空间的 "VC维"。
1. 增长函数
        增长函数,也称为VC维增长函数,描述了在给定假设空间下,能够被假设空间所“分割”或“覆盖”的训练样本的最大数量。具体来说,它衡量的是假设空间中能够对样本集进行不同标签分配的能力。增长函数的定义如下:对于一个假设空间  H )和一个样本集  S (大小为 m ),增长函数 (M_{H}(m) ) 表示假设空间 H 能够对样本集 S 进行的不同标签分配的最大数量。

2. 打分
        打分是一个与增长函数紧密相关的概念。它描述了一个假设空间能否对某个样本集进行所有可能的标签分配。具体来说:一个假设空间 (H )能打分一个样本集 S (大小为  m,如果 H  中的假设可以对 S 中的每一种可能的标签分配进行匹配。

 

3. 打散
        打散(或称为分裂)是一个与打分相关的概念,描述了假设空间能否在所有可能的标签分配下对样本集进行准确的分类。具体来说:假设空间  H 能打散一个样本集S (大小为 m )如果H能对 S 中的每一种标签分配进行正确的分类。换句话说,如果假设空间 H 能生成所有可能的标签分配。

 

4. VC维
        VC维是衡量一个假设空间复杂度的指标,它反映了假设空间能够打散的最大样本集的大小。具体来说:VC维是一个假设空间  H 可以打散的最大样本集的大小。即,如果假设空间  H 能打散大小为 d 的样本集,但不能打散大小为 d+1 的样本集,那么 H 的VC维就是 d。

增长函数 衡量假设空间对样本集进行的标签分配的能力。
打分 描述假设空间是否能够覆盖所有可能的标签分配。
打散 具体指假设空间对样本集进行所有可能标签分配的能力。
VC维 是衡量假设空间复杂度的关键指标,反映了最大打散能力。

12.5 Rademacher复杂度

        Rademacher 复杂度 是另一种刻画假设空间复 杂度的途径,与 vc 维不同的是,它在一定程度上考虑了数据分布.

给定训练集 ={(X1 , Y2), (X2,Y2),..., (Xm , Ym)} 假设h 的经验误差为:

                                                        \begin{aligned} \widehat{E}(h) & =\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right) \\ & =\frac{1}{m} \sum_{i=1}^{m} \frac{1-y_{i} h\left(\boldsymbol{x}_{i}\right)}{2} \\ & =\frac{1}{2}-\frac{1}{2 m} \sum_{i=1}^{m} y_{i} h\left(\boldsymbol{x}_{i}\right) \end{aligned}

经验误差最小的假设是:
                                        \underset{h \in \mathcal{H}}{\arg \max } \frac{1}{m} \sum_{i=1}^{m} y_{i} h\left(\boldsymbol{x}_{i}\right)
\sigma _{i}是Rademacher 随机变量.
函数空间 F 关于 Z 的经验 Rademacher 复杂度:
                                        \widehat{R}_{Z}(\mathcal{F})=\mathbb{E}_{\boldsymbol{\sigma}}\left[\sup _{f \in \mathcal{F}} \frac{1}{m} \sum_{i=1}^{m} \sigma_{i} f\left(\boldsymbol{z}_{i}\right)\right]
函数空间 F 关于Z  上分布D的  Rademacher 复杂度:
                                        R_{m}(\mathcal{F})=\mathbb{E}_{Z \subseteq \mathcal{Z}:|Z|=m}\left[\widehat{R}_{Z}(\mathcal{F})\right]

        

        
     
      

相关文章:

机器学习第十二章-计算学习理论

目录 12.1基础知识 12.2 PAC学习 12.3有限假设空间 12.3.1可分情形 12.3.2不可分情形 12.4VC维 12.5 Rademacher复杂度 12.1基础知识 计算学习理论研究的是关于通过"计算"来进行"学习"的理论&#xff0c;即关于机器学习的理论基础&#xff0c;其目的…...

Java-自定义注解操作日志记录处理(@Pointcut注解不是必须的)

在Java中,使用自定义注解结合Spring AOP来实现操作日志记录是一种常见的做法。这种方式可 以帮助你轻松地在不修改业务代码的情况下增加日志记录的功能。 下面我将详细介绍如何定义一个自定义注解,并结合Spring AOP来实现操作日志记录的功能。 1. 定义自定义注解 首先,我…...

【c++】深入理解别名机制--引用

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;C 目录 前言 一、引用的概念和定义 二、引用的特性 三、引用的实用性 1.引用传参 2.引用做返回值 2.1 引用做返回值的作用 2.2 引用坍缩问题、悬挂引用问…...

简便的qemu img扩容方法

虚拟机用着用着磁盘空间就不够了&#xff0c;那就要想办法增加磁盘空间大小 了。在虚拟机本身磁盘的基础上直接增加空间大小最简便&#xff0c;于是记录一下方法。 首先&#xff0c;在虚拟机关机状态下&#xff0c;使用qemu-img命令给虚拟机的磁盘镜像增加虚拟空间5GB&#xff…...

EPERM: operation not permitted,

这个错误提示 EPERM: operation not permitted, mkdir C:\Program Files\nodejs\node_global\node_modules\pnpm_tmp 通常是因为权限不足导致的。在 Windows 系统中&#xff0c;C:\Program Files\ 目录通常需要管理员权限才能写入。 要解决这个问题&#xff0c;你可以尝试以下…...

将Centos 8 Linux内核版本升级或降级到指定版本

本文以centos 8.0为例&#xff0c;内核版本为4.18.0-80.el8.x86_64&#xff0c;升级到内核版本为4.18.0-80.4.2.el8_0.x86_64。 1.查看当前系统版本信息 [rootcentos80-1905 ~]# uname -sr Linux 4.18.0-80.el8.x86_642.在网站&#xff1a;https://vault.centos.org/里面下载…...

小程序商城被盗刷,使用SCDN安全加速有用吗?

在电子商务蓬勃发展的今天&#xff0c;小程序商城因其便捷性和灵活性成为商家和消费者的新宠。然而&#xff0c;随着其普及&#xff0c;小程序商城的安全问题也日益凸显&#xff0c;尤其是盗刷现象频发&#xff0c;给商家和用户带来了巨大损失。面对这一挑战&#xff0c;是否可…...

nginx的基本使用与其日志

文章目录 1.nginx编译安装脚本2.nginx平滑升级&#xff0c;以及其步骤3.nginx核心配置&#xff0c;及实现nginx多虚拟主机4.nginx日志格式定制5.nginx反向代理及https安全加密6.基于LNMP和Redis的phpmyadmin的会话保持&#xff0c;以及其完整步骤 1.nginx编译安装脚本 #编译安…...

linux | 苹果OpenCL(提高应用软件如游戏、娱乐以及科研和医疗软件的运行速度和响应)

点击上方"蓝字"关注我们 01、引言 >>> OpenCL 1.0 于 2008 年 11 月发布。 OpenCL 是为个人电脑、服务器、移动设备以及嵌入式设备的多核系统提供并行编程开发的底层 API。OpenCL 的编程语言类似于 C 语言。其可以用于包含 CPU、GPU 以及来自主流制造商如 …...

算法-UKF中Sigma点生成

void UKF::MakeSigmaPoints() {Eigen::VectorXd x_aug_ Eigen::VectorXd(n_x_);x_aug_.head(n_x_) x_;Eigen::MatrixXd P_aug Eigen::MatrixXd::Zero(n_x_, n_x_);// 转成正定矩阵P_aug pdefinite_svd(P_);// LLT分解Eigen::MatrixXd L P_aug.llt().matrixL();sigma_point…...

精选五款热门骨传导耳机分享,让你避免踩坑的陷阱

因为骨传导耳机独特的佩戴方式和声音的传播方式&#xff0c;受到了小耳、油耳以及运动爱好者的的喜爱&#xff0c;但也由于市面上的骨传导耳机品牌越来越多&#xff0c;很多朋友不知道该怎么选择&#xff0c;今天我挑选出市面上体验感较好&#xff0c;各方面比较出色的骨传导给…...

「字符串」前缀函数|KMP匹配:规范化next数组 / LeetCode 28(C++)

概述 为什么大家总觉得KMP难&#xff1f;难的根本就不是这个算法本身。 在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略&#xff0c;把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身&#xff0c;而是它令人痛苦的百花齐放的定义。 有…...

python人工智能002:jupyter基本使用

小知识&#xff1a;将jupyter修改为中文&#xff0c;修改用户变量&#xff0c; 注意是用户变量&#xff0c;不是系统变量 新增用户变量 变量名&#xff1a;LANG 变量值&#xff1a;zh_CN.UTF8 然后重启jupyter 上一章的软件安装完成之后&#xff0c;就可以创建文件夹来学习写…...

Linux使用 firewalld管理防火墙命令

Linux 发行版中使用的动态防火墙管理工具。使用 firewalld&#xff0c;你可以查看防火墙状态、当前配置的规则以及开放的端口。以下是一些常用的 firewalld 命令来管理和查看防火墙状态及端口配置。 1. 查看防火墙状态 检查 firewalld 是否正在运行 sudo systemctl status f…...

二叉树(三)

一、二叉树的遍历 二叉树遍历是按照某种特定的规则&#xff0c;依次对二叉树中的结点进行相应的操作&#xff0c;并且每个结点只操作一次。 1.前序遍历&#xff08;先根遍历&#xff09; 前序遍历&#xff08;Preorder Traversal也叫先序遍历&#xff09;——根、左子树、右…...

05--kubernetes组件与安装

前言&#xff1a;终于写到kubernetes&#xff08;k8s&#xff09;&#xff0c;容器编排工具不止k8s一个&#xff0c;它的优势在于搭建集群&#xff0c;也是传统运维和云计算运维的第一道门槛&#xff0c;这里会列出两种安装方式&#xff0c;详细步骤会在下文列出&#xff0c;文…...

EmguCV学习笔记 VB.Net和C# 下的OpenCv开发 C# 目录

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 EmguCV是一个基于OpenCV的开源免费的跨平台计算机视觉库,它向C#和VB.NET开发者提供了OpenCV库的大部分功能。 教程VB.net版本请访问…...

探索TensorFlow:深度学习的未来

标题&#xff1a;探索TensorFlow&#xff1a;深度学习的未来 在当今快速发展的人工智能领域&#xff0c;TensorFlow无疑是最耀眼的明珠之一。TensorFlow是由Google Brain团队开发的一个开源机器学习框架&#xff0c;它以其强大的灵活性、易用性和高效的性能&#xff0c;迅速成…...

探索地理空间分析的新世界:Geopandas的魔力

文章目录 探索地理空间分析的新世界&#xff1a;Geopandas的魔力背景&#xff1a;为何选择Geopandas&#xff1f;这个库是什么&#xff1f;如何安装这个库&#xff1f;五个简单的库函数使用方法场景应用&#xff1a;Geopandas在实际工作中的应用常见bug及解决方案总结 探索地理…...

如何为网站申请免费SSL证书?

一、准备阶段 确定证书类型&#xff1a; 对于大多数个人博客和小型企业网站&#xff0c;DV&#xff08;域名验证&#xff09;SSL证书已足够使用&#xff0c;因为它仅验证域名所有权&#xff0c;成本较低且验证快速。准备域名&#xff1a; 确保你拥有一个有效的域名&#xff0c…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...