深入理解Vapnik-Chervonenkis(VC)维度：机器学习泛化能力的理论基础

引言

通过本篇阅读,从理论上去理解为什么:

  1.         要选择复杂度低的模型
  2.         过拟合的时候,增加样本量有用
  3.         以及如何根据样本量选择特征个数
  4.         PAC机器学习框架, VC 维是机器学习最重要的基础理论之一

         在机器学习领域，模型泛化能力是衡量算法性能的核心指标。一个关键问题是：如何确保在有限训练数据上训练的模型能够有效预测未知数据？这正是Vapnik-Chervonenkis(VC)维度理论要解决的核心问题。

   我们核心是了解下面公式

     

公式原理参考：https://www.youtube.com/watch?v=EmSVek5QMnE）

   VC理论的核心贡献是建立了泛化误差上界，当固定模型的复杂度，增加样本量可以降低过拟合风险

如果是线性分类器，其VC维如下：

目录：

  1.     vc维定义
  2.     Shattering
  3.     机器学习VC维
  4.      使用VC维度理论选择模型

一  VC维定义（Vapnik-Chervonenkis Dimension）

        VC维度(Vapnik-Chervonenkis Dimension)由统计学习理论先驱Vladimir Vapnik和Alexey Chervonenkis于1971年提出，是量化模型复杂度的数学工具。

         定义为能被H（Hypothesis Class：  假设空间,指模型可以学习的所有可能函数的集合）完全打散（shatter）的最大样本点数n。完全打散意味着对于这n个点的任意标签组合，H中均存在一个假设能正确分类。

     核心概念

  1. 打散(Shattering)：如果对于任意标签分配方式，假设类H都能完美分离样本点，则称H打散了该点集

  2. VC维度：假设类H能够打散的最大点集的大小

  3. 关键性质：

    • 线性分类器的VC维度 = 特征维度 + 1

    • 有限VC维度 ⇒ 可学习性

    • VC维度越大，模型拟合能力越强，但泛化风险越高

二  Shattering

     

    打散(Shattering)：如果对于任意标签分配方式，假设类H都能完美分离样本点，则称H打散了该点集。

    我们期望的规律： G(x)  x\rightarrow y 代表真实的规律

    如果输入的是x，那么 P(y=G(x))=1 ,我们不知道这个G(x)

    所以我们在各种假设空间里面，找到假设的函数，来对真实规律的猜测

模型假设空间类型表达能力过拟合风险适用场景
线性回归线性函数集合低低线性关系数据（如简单回归）
逻辑回归线性分类器集合中中二分类问题（如垃圾邮件检测）
决策树离散树结构集合高高多特征交互数据（如用户画像）
SVM（线性核）线性决策边界集合中中线性可分数据（如文本分类）
SVM（RBF 核）高维线性决策边界集合高高复杂非线性数据（如图像分类）
神经网络无限维非线性函数集合极高极高复杂模式识别（如语音、图像）

   

   

      1: N=2 两个点的情况（则共有2^N=4种组合）

      

       我们可以看到这些组合都可以被线性分类器Shattering

          A line can shatter 2 points on R^2

        2   N=3 （则共有2^N=8种组合）

  但是这种情况可以被线性分类器shatter,但是同样N=3 下面这种情况，如果共线就不能被shatter,所以shatter 并不是shatter 所有组合，只要shatter 其中一个组合就可以

  3   N=4 （则共有2^N=16种组合）

    

       这个时候我们发现我们找不到一个线性分类器（特征个数为2） 能够shatter 上面的集合，

所以其VC 维=d(特征个数+1=3

   所以上面能够shatter 最大的点的个数是N=3 

   N= d+1(其中d 是特征个数，为2维度）

  

  

三   机器学习VC维

       在机器学习领域，模型的复杂度与性能之间存在着微妙的平衡，即欠拟合与过拟合的权衡。欠拟合指的是模型过于简单，无法捕捉数据中的复杂模式，导致在训练和测试数据上表现均不佳。而过拟合则是模型过于复杂，过度拟合了训练数据中的噪声，虽然在训练数据上表现优异，但在测试数据上表现糟糕。

       模型的表示能力，即其学习或表示数据复杂模式的能力，是影响模型性能的关键因素。表示能力越强的模型，越能够捕捉数据中的复杂关系，但同时也可能更容易过拟合。因此，在选择模型时，需要根据具体问题的复杂度来权衡模型的表示能力。

     为了量化模型的表示能力，机器学习领域引入了VC维（Vapnik-Chervonenkis维度）这一概念。VC维提供了模型能够分类的最大点集数量的一个指标，VC维越高，模型的表示能力通常也越强。然而，高VC维也意味着模型更容易过拟合，因此在实际应用中，需要结合具体问题和数据特征来选择合适的模型复杂度。

总之，在机器学习中，理解欠拟合与过拟合的权衡、模型的表示能力以及VC维等概念，对于选择和优化模型具有重要的指导意义。

3.1  机器学习中的风险与经验风险

      在机器学习中，我们通常假设训练数据是从某个分布 p(x) 中独立同分布采样得到的。为了评估模型的性能，我们引入了两个重要概念：风险和经验风险。

  • 风险（R(θ)）代表了模型的“长期”测试误差，即模型在未见过的数据上的预期表现。其数学表达式为：

    其中，δ 是指示函数，当条件满足时取值为1，否则为0；

  •   c 是真实标签，c^(x;θ) 是模型预测的标签。

  • 经验风险（Remp(θ)）则是我们在训练数据上观察到的误差，也称为训练误差。其数学表达式为：

    其中，m 是训练样本的数量，c(i) 和 x(i) 分别是第 i 个样本的真实标签和特征。

风险与经验风险之间的关系反映了模型的过拟合程度：

  • 在欠拟合领域，风险与经验风险非常相似，意味着模型在训练和测试数据上的表现相近，但都可能不够理想。
  • 在过拟合领域，经验风险可能很低（模型在训练数据上表现很好），但风险却可能很高（模型在测试数据上表现糟糕）。

3.2  跟VC dimension 的关系

3.3    shattering

      假设我们特征的个数是2 ，我们可以看到其可以正确分类所有2个点的集合

常见机器学习模型的VC维度:
--------------------------------------------------
▪ 线性分类器 (d维空间)        → d+1
▪ 决策树 (k个叶子节点)        → k
▪ 神经网络 (含L层，W个参数)   → O(WL)
▪ 支持向量机 (RBF核)         → ∞ (理论上)
▪ k近邻算法 (k=1)            → ∞
▪ 简单阈值函数                → 1

四   使用VC维度理论选择模型

    在机器学习中，避免过拟合和选择合适复杂度的模型至关重要。除了常用的交叉验证（Cross-Validation）外，VC 维度（Vapnik-Chervonenkis Dimension） 提供了一种基于理论的方法来指导模型选择。

     核心思想：结构风险最小化 (SRM)

  1. 衡量模型复杂度： VC 维度 (h) 量化了一个模型类（例如，所有可能的线性分类器、所有特定深度的决策树）的“拟合能力”或复杂度。VC 维度越高的模型类，拟合复杂模式的能力越强，但也更容易过拟合。

  2. 泛化误差边界： 统计学习理论提供了基于 VC 维度的泛化误差边界。这个边界通常具有以下形式：
    测试误差 ≤ 训练误差 + 惩罚项(VC维度 h, 样本量 N, 置信度 δ)
    这个惩罚项随着模型 VC 维度 (h) 的增加而增大，随着训练样本量 (N) 的增加而减小。

  3. 模型选择流程 (SRM)：

    1. 定义一组具有不同 VC 维度的候选模型结构（例如，不同次数的多项式、不同层数的神经网络、不同最大深度的树）。

    2. 对于每个候选结构：

      • 在训练数据上找到该结构下表现最好的模型（最小化训练误差）。

      • 计算该模型的训练误差。

      • 计算基于该结构 VC 维度 (h) 和样本量 (N) 的惩罚项。

      • 计算泛化误差上界 = 训练误差 + 惩罚项。

    3.  选择那个给出最小泛化误差上界的模型结构。

 [VC Dimension]https://www.youtube.com/watch?v=puDzy2XmR5c&t=833s

[Model Complexity and VC Dimension]https://www.youtube.com/watch?v=8yWG7fhCpTw

[Understanding VC Dimension(Vapnik Chervonenkis Dimension) - Simplified Explanation for ]

[]https://www.youtube.com/watch?v=7O7RL5jHHNM

Machine Learning 15: VC-Dimension
[]https://www.youtube.com/watch?v=7O7RL5jHHNM

https://www.youtube.com/watch?v=XxPB9GlJEUk

https://www.youtube.com/watch?v=EmSVek5QMnE

  1. Vapnik, V. N., & Chervonenkis, A. Y. (1971). On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities.

  2. Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms.

  3. Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of Machine Learning (2nd ed.).

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/913083.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/913083.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

redis持久化-纯缓存模式

redis持久化-纯缓存模式

redis持久化-纯缓存模式 文档 redis单机安装redis常用的五种数据类型redis数据类型-位图bitmapredis数据类型-基数统计HyperLogLogredis数据类型-地理空间GEOredis数据类型-流Streamredis数据类型-位域bitfieldredis持久化-RDBredis持久化-AOFredis持久化-RDBAOF混合模式 官…
阅读更多...
HTML DOM 访问

HTML DOM 访问

HTML DOM 访问 引言 HTML DOM（文档对象模型）是现代Web开发中不可或缺的一部分。它允许开发者通过JavaScript操作HTML文档中的元素，从而实现丰富的交互效果。本文将详细介绍HTML DOM的访问方法，包括如何获取元素、如何修改元素属…
阅读更多...
双系统如何做接口认证-V1

双系统如何做接口认证-V1

现有A系统，B系统，A系统启动的时候调用B系统的注册接口API1（把A系统配置信息注册到B系统），A系统定时向B系统接口AP2发送心跳信息，B系统根据业务情况，调用A系统的业务接口AP3，请设计两…
阅读更多...
Wireshark TS | 诡异的光猫网络问题

Wireshark TS | 诡异的光猫网络问题

前言 来自于朋友分享的一个案例，最后定位的原因是光猫问题，而类似这类的设备所产生的网络问题，也曾碰到过两三次，但这一次的数据包现象挺特别，分析思路和过程也有所不同，故记录分享一下。 问题背景 用户所反…
阅读更多...
mac mini m4安装node.js@16以下版本方法

mac mini m4安装node.js@16以下版本方法

设备：mac mini m4 目的：使用nvm 安装 node.js14.x 版本 结果：安装不上 原因：Node.js 14 发布时，Apple Silicon（M1/M2）尚未普及，因此 没有官方预编译的 macOS ARM64 版本 处理方案&am…
阅读更多...
系统安全设计方案，软件系统安全设计方案

系统安全设计方案，软件系统安全设计方案

1.1 总体设计 1.1.1 设计原则 1.2 物理层安全 1.2.1 机房建设安全 1.2.2 电气安全特性 1.2.3 设备安全 1.2.4 介质安全措施 1.3 网络层安全 1.3.1 网络结构安全 1.3.2 划分子网络 1.3.3 异常流量管理 1.3.4 网络安全审计 1.3.5 网络访问控制 1.3.6 完整性检查 1.…
阅读更多...
Python入门Day3

Python入门Day3

Python的基础数据类型 1.Python中提供了六种内置的数据类型，一般用于存储数据： –数值Number –字符串String –列表List –元组Tuple –字典Dictionary –集合Set 2.Python中的数据类型可以做以下几个分类： –有序：可以使用下标…
阅读更多...
前端富文本添加录音功能方案

前端富文本添加录音功能方案

为富文本编辑器添加录音功能可以增强内容创作的多样性。以下是几种实现方案： 方案一：基于Web Audio API原生实现 实现步骤获取用户麦克风权限 navigator.mediaDevices.getUserMedia({ audio: true }).then(stream > { /* 处理音频流 */ }).catch(err …
阅读更多...
解锁阿里云Hologres：开启实时数据分析新时代

解锁阿里云Hologres：开启实时数据分析新时代

引言在当今这个数字化浪潮汹涌澎湃的大数据时代，数据就如同企业和组织的 “数字石油”，成为了最具价值的资产之一。随着信息技术的飞速发展，各行业所产生和收集的数据量正以指数级的速度增长，从社交媒体上的用户互动信息&#xff…
阅读更多...
python学习打卡day59

python学习打卡day59

DAY 59 经典时序预测模型3 知识点回顾： SARIMA模型的参数和用法：SARIMA(p, d, q)(P, D, Q)m模型结果的检验可视化（昨天说的是摘要表怎么看，今天是对这个内容可视化）多变量数据的理解：内生变量和外部变量多变…
阅读更多...
java中agent的作用

java中agent的作用

一 java中agent1.1 agent-javaagent 是 Java 虚拟机 (JVM) 提供的一个启动参数，用于在 Java 程序 main 方法执行之前，加载一个特殊的 Java 代理程序（Java Agent）。它的核心作用是对运行中的 Java 程序进行字节码层面的动态修改、监…
阅读更多...
[C/C++内存安全]_[中级]_[如何避免数组访问越界]

[C/C++内存安全]_[中级]_[如何避免数组访问越界]

场景 C/C的标准在C26以前还没支持内存安全的访问连续内存的类或特性。在开发分析内存数据或文件数据的程序时，经常需要把一段内存数据复制到另一个堆空间里。 这时目标内存空间由于起始地址的移动，剩余大小的计算错误，经常会导致访问越界错误…
阅读更多...
rabbitmq 与 Erlang 的版本对照表 win10 安装方法

rabbitmq 与 Erlang 的版本对照表 win10 安装方法

win10 64位系统 安装的版本 otp_win64_27.3.3.exe rabbitmq-server-4.1.1.exe rabbitmq 与 Erlang 的版本对照表 Erlang Version Requirements This guide covers Erlang/OTP version requirements https://www.rabbitmq.com/docs/which-erlang Erlang 28 is not currently…
阅读更多...
kali安装教程

kali安装教程

kali教程 我下载的是kali的集成环境，可以直接进行打开，无需进行安装。 Get Kali | Kali Linux， 官网下载路径 直接按enter键 安装完成 生成一个小皮安装链接 会给你生成一个外网和内网地址， 可以进行浏览 点击我同意这个协议…
阅读更多...
微信小程序入门实例_____快速搭建一个快递查询小程序​

微信小程序入门实例_____快速搭建一个快递查询小程序​

🌷🌷之前几篇博文我们一起开发了天气查询、单词速记和待办事项小程序，这次我们来对生活中常用的功能 —— 快递查询来探索相关的小程序。网购已经成为大家生活的一部分，有了自己的快递查询小程序，不用切换多个应用&…
阅读更多...
【防火墙基础之传统墙到 UTM 到 NGFW 再到 AI 的变化】

【防火墙基础之传统墙到 UTM 到 NGFW 再到 AI 的变化】

防火墙技术演进与未来趋势：从传统防御到AI驱动的智能安全 防火墙技术历经数十年发展，已从早期的简单包过滤演进为融合AI的智能安全平台。当前，传统爬虫防护技术如频率限制和人机校验已无法应对现代攻击，而全面风控体系通过多维协同…
阅读更多...
【仿muduo库实现并发服务器】Poller模块

【仿muduo库实现并发服务器】Poller模块

仿muduo库实现并发服务器 1.Poller模块成员变量创建epoll模型对于一个描述符添加或修改事件监控对于一个描述符移除事件监控启动epoll事件监控，获取所有活跃连接 1.Poller模块 Poller模块主要是对任意的描述符进行IO事件监控。 它是对epoll的封装，可以让…
阅读更多...
小程序学习笔记：使用 MobX 实现全局数据共享，实例创建、计算属性与 Actions 方法

小程序学习笔记：使用 MobX 实现全局数据共享，实例创建、计算属性与 Actions 方法

在小程序开发过程中，组件间的数据共享是一个常见且关键的问题。今天，我们就来深入探讨一下如何在小程序中实现全局数据共享，借助 MobX 相关的包，让数据管理变得更加高效便捷。 什么是全局数据共享 全局数据共享，也被…
阅读更多...
观测云 × AWS SSO：权限治理可观测实践

观测云 × AWS SSO：权限治理可观测实践

AWS IAM Identity Center 介绍 AWS IAM Identity Center（原 AWS Single Sign-On）是 AWS 提供的一项云原生身份与访问管理（IAM）服务，旨在集中简化多 AWS 账户、多业务应用的安全访问控制。 观测云 观测云是一款专为 …
阅读更多...
springboot整合配置swagger3

springboot整合配置swagger3

一. swagger3介绍 Swagger 3 是基于 OpenAPI 规范 3.0 的 API 文档工具，用于设计、构建和消费 RESTful API。它通过标准化描述 API 的接口、参数、响应等元数据，实现以下核心功能： 自动生成交互式文档API 测试与调试代码生成（客…
阅读更多...
最新文章

Copyright @ 2022~2023