[机器学习] 5. 一致收敛性 Uniform Convergency

这篇具有很好参考价值的文章主要介绍了[机器学习] 5. 一致收敛性 Uniform Convergency。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

回顾不可知 PAC 的定义

定义 一个假设类 \(\mathcal H\)不可知 PAC 可学习的,如果存在函数 \(m_{\mathcal H} : (0, 1)^2 \to \mathbb N\) 和一个学习算法满足,对任意 \(\epsilon, \delta \in (0, 1)\)\(\mathcal X \times \{0, 1\}\) 上的分布 \(\mathcal D\),学习算法接收长度为 \(m \geq m_{\mathcal H}(\epsilon, \delta)\) 的训练集可以给出一个假设 \(h\),使得有至少 \(1 - \delta\) 的概率

\[L_{\mathcal D}(h) \leq \min_{h' \in \mathcal H} L_{\mathcal D}(h') + \epsilon \]

其总是关心泛化的结果,而不在乎其过程。但一般地讲来,所谓泛化能力,是指在有限的测试集(就是上文的训练集,但此时不关注训练)上能够体现真实分布上的损失的能力。即

\[|L_S(h) - L_{\mathcal D}(h)| \leq \epsilon \]

定义 一个数据集 \(S\) 被称作(关于作用域 \(\mathcal Z\),假设类 \(\mathcal H\),损失函数 \(\ell\),分布 \(\mathcal D\)\(\epsilon\)-representative 的,如果

\[\forall h \in \mathcal H, |L_S(h) - L_\mathcal D(h)| \leq \epsilon \]

这是看似比 PAC 更严的条件。因为其不仅仅要求了找到好的假说的能力,还要求了所有假说的泛化能力。

推论 \(S\)\(\epsilon / 2\)-representative 的,则

\[L_{\mathcal D}(h_S) \leq \min_{h \in \mathcal H} L_{\mathcal D}(h) + \epsilon \]

证明

\[L_{\mathcal D}(h_S) \leq L_S(h_S) + \frac \epsilon 2 \leq L_S(h) + \frac \epsilon 2 + \frac \epsilon 2 = L_{\mathcal D}(h) + \epsilon \tag*{$\square$} \]

对于一个单一的假说 \(h\)\(\mathcal D^m(S \mid |L_S(h) - L_{\mathcal D}(h)| > \epsilon) \to 0\) 的条件,便是采样的均值随着采样数增大高概率 \(\epsilon\)-靠近分布的期望的条件,即 Measure Concentration。这一点在概统中有相当多的结论(注意 Chernoff bound 描述的是两者的比值而不是差,所以这里不用)

引理 (Hoeffding's Ineq) 令 \(\theta_1, \ldots, \theta_m\) 为独立同分布随机变量,\(\mathbb E[\theta_i] = \mu, \mathbb P[a \leq \theta_i \leq b] = 1\),则对任意 \(\epsilon> 0\)

\[\mathbb P \left[\left|\frac 1m \sum_{i=1}^m \theta_i - \mu\right| > \epsilon\right] \leq 2 \exp \left(\frac{-2 m \epsilon^2}{(b - a)^2}\right) \]

于是对任意 \(\epsilon, \delta \in (0, 1)\),对每一个 \(h \in \mathcal H\) 考虑 \(\theta\) 取自分布 \(\ell \circ (h \times \mathcal D)\)(即按照分布 \(\mathcal D\) 生成实例,经过假说的判断后的损失的分布),则一定存在某个 \(m_h\) 使得条件满足。接下来所需要的,便是考虑所有分布 \(\ell \circ (\mathcal H \times \mathcal D)\) 关于由 \(\mathcal D\) 生成的随机变量的一致性。即,对于某个固定的 \(S\)\(\sup_{h \in \mathcal H} |L_{\mathcal D}(h) - L_S(h)| < \epsilon\)。由于这里并不再假设 \(\mathcal H\) 是有限的,不能套用 Union bound,这一条件并不直接满足。

定义 称假设类 \(\mathcal H\) 具有一致收敛性 (Uniform Convergence property),如果存在函数 \(m^{\text{UC}}_{\mathcal H} : (0, 1)^2 \to \mathbb N\) 满足,对任意 \(\epsilon, \delta \in (0, 1)\)\(\mathcal Z\) 上的分布 \(\mathcal D\),长度为 \(m \geq m^{\text{UC}}_{\mathcal H}(\epsilon, \delta)\) 的训练集 \(S\) 有至少 \(1 - \delta\) 的概率是 \(\epsilon\)-representative 的。

推论 假设类 \(\mathcal H\) 关于函数 \(m_{\mathcal H}^{\text{UC}}\) 具有一致收敛性,则该假设类是关于 \(m_{\mathcal H}(\epsilon, \delta) \leq m_{\mathcal H}^{\text{UC}}(\epsilon / 2, \delta)\) 不可知 PAC 可学习的,且 ERM 策略生效。

命题 0-1 loss 下的有限假设类一致收敛的,因此是不可知 PAC 可学习的。

证明 Union bound + Hoeffding's Ineq.

\(\theta_{h, i} = \ell(h, x_i)\),则

\[\begin{aligned} \mathcal D^m(\{(S|_x) \mid \exists h \in \mathcal H, |L_S(h) - L_{\mathcal D}(h)| > \epsilon\}) &\leq \sum_{h \in \mathcal H} \mathcal D^m(\{(S|_x) \mid |L_S(h) - L_{\mathcal D}(h)| > \epsilon\}) \\ &= \sum_{h \in \mathcal H} \mathbb P\left[\left|\frac 1m \sum_{i=1}^m \theta_{h, i} - \mu\right | > \epsilon\right] \\ &\leq 2 |\mathcal H| \exp(-2m \epsilon^2) \end{aligned}\]

\[m \geq \frac{\log (2 |\mathcal H| / \delta)}{2\epsilon^2} \]

则有 \(\mathcal D^m(\{S \mid \exists h \in \mathcal H, |L_S(h) - L_{\mathcal D}(h)| > \epsilon\}) \leq \delta\)。故

\[m_{\mathcal H}(\epsilon, \delta) \leq m^{\text{UC}}_{\mathcal H}(\epsilon / 2, \delta) \leq \left\lceil \frac{2 \log(2|\mathcal H| / \delta)}{\epsilon^2}\right\rceil \tag*{$\square$} \]

需要注意的是,一致收敛性是仅对 \(\mathcal H\)\(\ell\) 说的,\(\mathcal D\)任意的。能这么说的底气在于以下几点

  • 当考虑一个测试集 \(S\) 时,可以只需要考虑

    \[\mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) - L_S(h)|\right] \]

    关于 \(m\) 收敛的条件。

根据 Markov's Ineq,

\[\mathbb P_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) - L_S(h)| \geq \epsilon\right] \leq \delta \]

其中

\[\epsilon = \frac {\mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) - L_S(h)|\right]}{\delta} \]
  • 我们可以由式子中 \(\mathbb E + \sup\) 的机制去除 \(L_{\mathcal D}\),而转化为两组测试集的差。

定义 \(C = \{c_1, \ldots, c_m\} \subset \mathcal X\) 是实例集合的一个有限子集,称假设类 \(\mathcal H\)\(C\) 上的 restriction 为

\[\begin{aligned} \mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) - L_S(h)|\right] &= \mathbb E\left[\sup_{h \in \mathcal H} |(\mathbb E_{S' \sim \mathcal D^m} L_{S'}(h)) - L_S(h)|\right] \\ &\leq \mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} \mathbb E_{S' \sim \mathcal D^m} |L_{S'}(h) - L_S(h)|\right] && |\mathbb EX| \leq \mathbb E|X| \\ &\leq \mathbb E_{S \sim \mathcal D^m}\left[\mathbb E_{S' \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{S'}(h) - L_S(h)|\right]\right] && \sup_{h \in \mathcal H} \mathbb E X(h) \leq \mathbb E \sup_{h \in \mathcal H} X(h) \\ &= \mathbb E_{S, S' \sim \mathcal D^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m (\ell(h, x_i') - \ell(h, x_i))\right|\right] \end{aligned}\]

此时,\(S, S'\) 对称。于是我们可以通过交换两者进行配对,这样每一对的期望是 \(0\),于是可以用 Hoeffding's Ineq 控制。

  • 在有限的测试集上,我们可以仅关心那些出现过的实例。更关键的是,由于是两者相减且经过配对,\(\ell\) 具体为多少无关紧要,因此只要没有重复元素,无论基于什么分布生成的任何实例集都是平等的。
\[\begin{aligned} \mathbb E_{S, S' \sim \mathcal D^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m (\ell(h, x_i') - \ell(h, x_i))\right|\right] &= \mathbb E_{\bm \sigma \in \{\pm 1\}^m}\mathbb E_{S, S' \sim \mathcal D^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m \sigma_i(\ell(h, x_i') - \ell(h, x_i))\right|\right] \\ &= \mathbb E_{S, S' \sim \mathcal D^m}\mathbb E_{\bm \sigma \in \{\pm 1\}^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m \sigma_i(\ell(h, x_i') - \ell(h, x_i))\right|\right] && \text{Fubini} \\ &= \mathbb E_{S, S' \sim \mathcal D^m}\mathbb E_{\bm \sigma \in \{\pm 1\}^m} \left[\sup_{h \in \mathcal {\mathcal H}_C} \frac 1m \left|\sum_{i=1}^m \sigma_i(\ell(h, x_i') - \ell(h, x_i))\right|\right] && C = \{x_i\} \cup \{x_i'\} \\ \end{aligned}\]

其中,\(\mathcal H_C = \{(h(c_1), \ldots, h(c_m)) \mid h \in \mathcal H\}\) 称为 \(\mathcal H\)\(C \subset \mathcal X\) 上的 restriction。

\(\theta_i = \sigma_i (\ell(h, x_i') - \ell(h, x_i))\),若 \(\mathcal X\) 为无限集,则 \(\theta_1, \ldots, \theta_m\)\(1\) 的概率是 i.i.d. 的,且 \(\mathbb E_{\sigma_i \sim \{\pm 1\}} [\theta_i] = 0\),而如果考虑 0-1 loss,则 \(-1 \leq \theta_h \leq 1\),根据 Hoeffding's Ineq 可知

\[\mathbb P_{\bm \sigma \in \{\pm 1\}^m}\left[\left|\frac 1m\sum_{i=1}^m \sigma_i (\ell(h, x_i') - \ell(h, x_i))\right| > \rho\right] \leq 2 \exp\left(-\frac 12 m \rho^2\right) \]
\[\mathbb P_{\bm \sigma \in \{\pm 1\}^m}\left[\max_{h \in \mathcal H_C}\left|\frac 1m\sum_{i=1}^m \sigma_i (\ell(h, x_i') - \ell(h, x_i))\right| > \rho\right] \leq 2|\mathcal H_C| \exp\left(-\frac 12 m \rho^2\right) \]

现在把它积成 \(\mathbb E\) 的形式。

引理 若存在 \(a > 0, b \geq e\) 使得对所有 \(t \geq 0\)\(\mathbb P[|X - x'| > t] \leq 2b \exp(-t^2 / a^2)\),则 \(\mathbb E[|X - x'|] \leq a\left(2 + \sqrt{\log b}\right)\)

证明\(t_i = a \left(i + \sqrt{\log b}\right)\)\(t_i\) 单调增,因此

\[\begin{alignat}{2} \mathbb E[|X - x'|] &\leq a \sqrt{\log b} + \sum_{i=1}^{\infty} t_i \mathbb P[|X - x'| > t_{i-1}] \notag \\ &\leq a \sqrt{\log b} + 2ab \sum_{i=1}^{\infty} \left(i + \sqrt{\log b} \right) \exp\left(-\left(i - 1 + \sqrt{\log b}\right)^2\right) \notag \\ &\leq a \sqrt{\log b} + 2ab \int_{1 + \sqrt{\log b}}^{\infty} x \exp(-(x - 1)^2) \mathrm dx \notag \\ &= a \sqrt{\log b} + 2ab \int_{\sqrt{\log b}}^{\infty} (x + 1) e^{-x^2} \mathrm dx \notag \\ &\leq a \sqrt{\log b} + 4ab \int_{\sqrt{\log b}}^{\infty} x e^{-x^2} \mathrm dx & b \geq e \notag \\ &= a \left(2 + \sqrt{\log b}\right) \tag*{$\square$} \end{alignat}\]

我们不关心常数,直接用 \(4|\mathcal H_C| > e\) 来做,则

\[\mathbb E_{\bm \sigma \in \{\pm 1\}^m}\left[\max_{h \in \mathcal H_C}\left|\frac 1m\sum_{i=1}^m \sigma_i (\ell(h, x_i') - \ell(h, x_i))\right|\right] \leq \frac{\left(2 + \sqrt{2 + \log|\mathcal H_C|}\right)\sqrt 2}{\sqrt m} \leq \frac{4 + 2\sqrt{\log |\mathcal H_C|}}{\sqrt m} \]

定义 假设类 \(\mathcal H\) 在实例 \(\mathcal X\) 上的增长函数 \(\tau_{\mathcal H} : \mathbb N \to \mathbb N\) 定义为

\[\tau_{\mathcal H}(m) := \max_{|C| = m} |\mathcal H_C| \]

定理 对任意 \(\mathcal D, \delta \in (0, 1)\),有至少 \(1 - \delta\) 的概率有

\[|L_{\mathcal D}(h) - L_S(h)| \leq \frac{4 + 2\sqrt{\log(\tau_{\mathcal H}(2m))}}{\delta\sqrt m} \]

由此,我们得到

定理 对 0-1 loss,若

\[\lim_{m \to \infty} \frac{\log(\tau_{\mathcal H}(m))}{m} = 0 \]

\(\mathcal H\) 是不可知 PAC 可学习的。

这是一个相当一般的结论,其不依赖于 \(\mathcal D\),只与 \(\mathcal H\) 自身的性质有关。文章来源地址https://www.toymoban.com/news/detail-737125.html

到了这里,关于[机器学习] 5. 一致收敛性 Uniform Convergency的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据一致性在人工智能与机器学习中的应用

    数据一致性是指在分布式系统中,当多个节点或进程访问和修改共享数据时,确保所有节点或进程看到的数据都是一致的状态。在人工智能(AI)和机器学习(ML)领域,数据一致性是一个重要且复杂的问题。随着数据规模的增加,分布式计算变得越来越普遍,这使得数据一致性问

    2024年02月21日
    浏览(57)
  • 基于python/scipy学习概率统计(1):均匀分布(Uniform Distribution)

    目录 1. 前言 2. 均匀分布 Uniform Distribution 2.1 统计特征 2.2 概率密度函数 2.3 随机采样实验 2.4 其它常用函数         本系列借助scipy.stats模块对机器学习中常用的概率统计基础知识进行基于实验的学习。         这第一篇先从最简单的均匀分布(uniform distribution)。     

    2023年04月14日
    浏览(36)
  • 深度学习中常见概念(收敛、优化器、学习率等)

    打个简单的比方,训练网络模型,就好比解方程,为了得到这个方程的极值点,训练的过程就好比是找准一个方向,不断的朝这个方向靠近,使得方程的值不断减小,最终达到极值点,而不收敛,就是,不论你怎么跑,方程的解都不减小。即达不到最后的极值点.在loss上就表现

    2024年02月01日
    浏览(43)
  • 概率论的学习和整理15: 超几何分布,二项分布,泊松分布是如何趋近收敛的?

    目录 1 问题: 2 结论 3 实验1  4 实验2  5 实验3  6 实验4 5 各种规律总结 5.1   1  5.2  2 5.3  3 5.4 4 6 超几何分布,二项分布,泊松分布,三者用EXCEL模拟 6.1 简单的扩展到泊松分布 6.2  比较整体的动态过程,增加实验次数时 从一个简单模型说开去 比如,有10个球,其中有x个

    2024年02月16日
    浏览(40)
  • 多机器人协同避障路径规划 — 一致性算法和人工势场算法

    多机器人协同避障路径规划 — 一致性算法和人工势场算法 现代机器人技术的发展给人们的生产和生活带来了巨大的影响。在复杂环境下,多个机器人通过协同控制可以完成更复杂的任务。但是,在多机器人协同运动时,避免碰撞及实现合理路径规划是一个重要的问题。因此

    2024年02月10日
    浏览(45)
  • random.uniform()详解

    函数原型: numpy.random.uniform(low,high,size) 功能:从一个 均匀分布[low,high)中随机采样 ,注意定义域是 左闭右开 ,即包含low,不包含high. 参数解释: shape: 张量形状 minval: 随机值范围下限,默认0 maxval:   随机值范围上限(若薇浮点数,则默认为1) dtype:   输出的类型:float

    2024年02月15日
    浏览(36)
  • 【6】uniform颜色写入

    之前的Basic.shader: 这里 color = vec4(1.0, 0.0, 0.0, 1.0); 是写死的,但我们想要从代码里进行更改,因此将片元着色器部分修改为这样: 在主程序里就可以写入颜色( GLCall 属于错误检测宏,去掉不影响使用): 如果在 while (!glfwWindowShouldClose(window)) 里每次都设置其unifrom的话,就可以

    2024年02月10日
    浏览(38)
  • CesiumJS 源码杂谈 - 从光到 Uniform

    目录 1. 有什么光 2. 光如何转换成 Uniform 以及何时被调用 2.1. 统一值状态对象(UniformState) 2.2. 上下文(Context)执行 DrawCommand 2.3. 对 WebGL Uniform 值的封装 2.4. 自动统一值(AutomaticUniforms) 3. 在着色器中如何使用 3.1. 点云 3.2. 冯氏着色法 3.3. 地球 3.4. 模型架构中的光着色阶段

    2023年04月16日
    浏览(29)
  • 通过kafka学习数据一致性

    数据从主节点(leader)复制到从节点(follower)的过程中,由于网络延迟、节点故障或其他原因 可能导致从节点未能及时获取或处理主节点的数据变更,从而产生数据不一致 消息提交涉及多个阶段,包括生产者发送消息、消息被写入日志、消息被复制到从节点等。 如果在这

    2024年02月19日
    浏览(38)
  • Continuous Distributions: Uniform, Normal, and Gamma

    作者:禅与计算机程序设计艺术 在过去的几十年里,许多领域都出现了很多统计分布的变化。从早期的正态分布到后来的指数分布、卡方分布等,各种分布也逐渐形成自己的发展历史。统计学中的一些技术或者模型需要根据数据分布进行选择和建模,所以需要对不同分布的特

    2024年02月07日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包