Preliminaries

• Domaim set : 一个任意的想进行 label 的集合

• Label set . 后续为了方便一般都会用二分类来讨论一些内容.

• Training Data: 有限集 , 或者记作 .

• 一个 learner 的目标是要得到一个 predictor/hypothesis/prediction rule/classifier . 用 表示算法 在数据集 上训练得到的 predictor, , 其中 是参数空间.

• 数据的生成: 我们总是假定 上有一个 unknown distribution ,目前我们认为存在一个绝对正确的 使得对 中每一对 sample 都有 , 称之为 concept, 于是数据的生成是 i.i.d 地从 上采样并以 标注.

• 用 error/risk 来衡量 learner 是否很好地完成了学习的任务, 这称为 generalized error/ true error, 定义为: predictor 的 error 从 中随机采样 且 的概率. 更正式地, 给定 和概率分布 , 符号 表示观察到某个 满足 的可能性大小, 因此在很多情况下我们会认为 是事件, 并定义 且 , 因此

  原书中许多地方的证明过程都是用 来表示概率的, 为了与概率论相契合, 我们只用 来表示概率.

• learner 关于 是一无所知的, 它只能从训练集中获取信息.

• 一个好的 learner 需要有足够小的 generalized error, 但是由于对 和 一无所知, 只能计算所谓的 empicical error/risk, 定义为 任务替换为最小化 empicical risk , 称为 ERM Rule (经验风险最小化). 我们的终极目标是训练一个具有较小 test loss 或者 population loss 的一个模型.

总结下来就是:

有关符号的说明:

• 或者 都表示在训练集上学习到的模型
• 都表示 training loss
• 都表示 test loss
• 为了方便, 当上下文不出现损失函数的时候或者我们不关心损失函数时, 也可以不用手写体 表示上述 loss, 直接用 , 有时候可能也会用 , 但是会尽量保证符号统一.
• 有 hat 符号 一般都是和训练集相关的内容.
• 假设空间 有时候也会写成函数空间 , 两者是等价的.
• 一般会代指训练集的大小, 一般会指数据的维度.
• 是 distribution, 为了方便, 有时或者大部分时候也不用手写体, 而是使用 .

ERM Rule

ERM rule 会出现过拟合即 小而 大的情况. 我们自然想知道在什么条件下 ERM 不会出现过拟合, 即 ERM predictor 不仅在训练集上表写好, 在 underlying data distribution 上也能表现好的条件.

一个解决过拟合的方法是限制 来限制 predictor 可选的范围. 给定 , 一个 learner 使用 ERM rule 以 上最小可能的误差来选择一个 , 即 , 这里也说明了 . 当限制了 时, 我们对某些特定的 predictor 产生了偏好 (bias), 这样的限制经常称为 inductive bias.

Learning Theory 中的一个基本的问题是在什么样的 下 不会出现过拟合.

在措辞上, 更严格的说法是 “ 一个 learner 是否会出现过拟合”, 为了方便表述, 后文会略去 learner. 符号 可以认为是 的一个元素或者一个子集, 也可以认为是返回或输出一个 的算法, 这个/些元素 满足 最小.

Finite

有限集是最直接的一种限制, 后文将会证明, 当 是有限集时, 在充分大的训练集 (大小和 相关) 的条件下不会出现过拟合.

我们需要先做一些假设.

The Realizability Assumption 存在 s.t. .

这个假设表示对于随机的 ( 采样自 以 标注), w.p. .

由于 是随机采样得到的, 我们无法保证通过 一定能学到一个好的 predictor, 因为总是有可能采样到的数据恰好不能很好地表征 . 我们把采样到“不好的 (不够具有代表性的)” 的概率记作 , 称 为我们预测的置信度 (confidence parameter).

由于我们无法保证做到完美的预测, 因此有必要引入 accuracy parameter , 并且认为 时 predictor 是 “失败的”, 而 时 predictor 被认为是近似正确的.

记 表示训练集 ( 表示样本用字母 表示, 后文会略去, 并默认由 表示) , 现在想给一个训练集 预测失败的概率 一个上界.

下面简述求解思路.

考虑 中一些不好的假设 即 , 将它们的集合记作 . 然后一定存在一些 , 使得 虽然是不好的, 但是能够完美地拟合 , 即 , 将这些 的集合记作 . 显然在 上能通过 ERM Rule 学习出的满足 的 , 一定是 中的元素, 且 realizability assumption 表明 , 那么这就意味着事件 发生的充分条件是 .

A Formal Learning Model: PAC Leaning

PAC Learning 的全称是 probably approximately correct learning.

PAC learning 实际上是在研究 sample complexity 的问题, 就是在 的置信度下, 以 的 acc 需要多少样本, 并且什么样的 (在 PAC Learning 的框架下) 是可以学习的. 严格的定义如下:

定义 1 (PAC Learnability) 假设空间 是 PAC learnable 的, 如果存在 使得存在满足下面性质的算法 :

• 对任意 , 对任意 上的分布 , 对任意 , 若 realizable assumption关于 成立, 那么在 个 i.i.d. 的且以 标注的样本所构成的训练集上运行算法 时, 算法 会以至少 的概率返回一个满足 的条件的 .

PAC Learning 的定义中包括两个 approximation parameter, 其中 决定了输出的分类器距离最优的分类器有多"远" (approximately correct), 它允许赦免分类器的少量错误; 表明了分类器有多大的可能满足准确率的要求 (probably) .

决定了学习 所需要的 sample complexity, 即需要多少样本可以保证一个 PAC 的解. 当 时, 是 PAC Learnable 的, 且样本复杂度满足

Agnostic PAC Learning

realizability assumption 是很强的假设, 中不一定存在一个完美的 使得 . 同时 label 不一定完全由已知的特征决定.

在接下来, 被定义为 上的联合分布, 接着定义 上的边缘分布 和 上的条件分布 . 然后上述 的定义依据联合分布进行修正.

The Bayes Optimal Predictor 给定 上的 , 则 是一个最优的 的 predictor. 即对所有分类器 都有 .

如果对数据生成的分布不做任何先验的假设, 则不存在任何算法可以得出一个和 Bayes predictor 一样好的 predictor.

定义 2 (Agnostic PAC Learnability) 是 Agnostic PAC Learnable 的, 如果存在 以及一个满足下述条件的算法 :

• 对任意 , 每一个 上的分布 , 当在 个 i.i.d. 的样本上运行 时, 返回一个 满足 以至少 的概率成立.

的条件其实是非常强的, 当放松这个条件后, 可以得到 Agnostic PAC Learnability 的定义, 与 PAC Learnability 基本完全一致, 除了不需要 realizable 假设以及算法 需要返回的是满足 的 以及分布是 的联合分布而不是 上的分布.

agnostic 的意思是 “不可知的”.

loss function 的严格定义是 . 对于预测问题, , 并且认为 是一个随机变量, 这要求它可测, 此时 , 以及 , 其中 . 然后就很容易得到 Agnostic PAC Learnability 在这种一般定义下的 loss function 的定义.

Learning via Uniform Convergence

任意有限的 都是 PAC Learnable 的, 这里引入一个新的更 general 的工具 uniform convergence, 用来展示任意有限的 在 agnostic PAC model 的框架下以及损失函数时一般的损失函数也是可学习的, 只要 range loss function 有界.

存在一个很好的训练集 , 使得 中的每个元素都具有很好的泛化误差

VC Dimension

VC Dimension 是为了弥补 PAC Learning 的缺陷, 即 finite . 将 的 cardinality 替换成了 VC Dimension.

时是一定 PAC learnable 的, 其实甚至可以不用学习的方法直接穷举 即可. 那 时就一定不可学习吗? 事实上 时也是 PAC Learnable 的.

那为了确保不出现过拟合, 我们需要 bound .

generalization gap 定义为 , 于是 最小化 的目标转化为最小化 generalization gap 和 training loss (optimization error).

No-Free-Lunch

no free lunch 是在说, 不存在一个算法 , 存在一个对抗分布 , 使得即使存在一个好的 predictor, 也会很大概率找不到这个 predictor.

传统统计模型

主要回顾线性模型和广义线性模型.

参数模型 (parameter model) 的定义是: 一个可学习的可以被有限维参数给 index 住的模型.

线性模型是 , 其中 是 ground true. 可以学习一个 linear classifier , 这是有限维的, 所以该线性模型被 给 index 住, 它是参数模型.

学习一个模型实际上是给参数一个估计, 我们希望这个参数满足 consistency, 即 时需要有 .

对于线性模型而言, 当考虑最小二乘法时, , , , 可以证明它是 unbiased 且满足 consistency, 证明 consistency 时除了求 以外, 也可以求 . 现在对 进行研究: 其中第一项就是 bias, 第二项是 variance. 如果采取 作为估计量的话, 有可能会碰到 的某一个特征值非常小的情况, 这就会导致 是 unbiased 但是有很大的 variance, 这就导致整体的误差 偏大. 所以可以考虑找一个 biased 但是具有较小的 variance 的量, 使得 整体不太大, 这就是岭回归的 intuition, 即 . 此时 但具有更小的 variance term, 事实上存在 , 在某些很松的假设下, .

岭回归还有其他的 intuition, 比如:

• 在 loss 上增加惩罚项
• 保证求逆时数值稳定

广义线性模型

当假设 时, , 这样不够灵活, 如果有先验 或者 这样假设就不是很好的选择.

指数分布族是具有形如 的 PDF 的分布, 其中 是变量, 是参数. 当有广义线性模型时, 假设可以写作 , 其中 .

• 对于线性模型,
• 对于二分类 / Bernoulli 分布, ,
• 对于 Poisson 分布, , 假设是 .

统计学习理论基本概念

经验风险 (empirical risk)是模型 关于训练集的平均损失: .

设 服从分布 , 则 的期望风险为 .

时, .

设学习到的模型是 , 那么 的泛化误差为 即 在未知数据上的误差.

在假设空间有限的条件下, 可以给出二分类问题的泛化误差上界 其中 是训练误差, 为假设空间的大小.

且

鞅

定义 1 称随机变量序列 是关于 的一个鞅, 如果 是 的函数, 且 , 且 .

REF

[1] Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.

[2] Roman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. HDP-book.pdf (uci.edu)

%%设 PIB 前后的 token 分别为 和 , 并且认为 token 的每个维度都是独立的, 设 token 估计的概率为 , 那么 , 且 由于计算 的时候是 个 之间的数相乘, 的值可能会很小, 因此也要对 进行 softmax. 对 也是同理. 那么 %%分布 , 那么借助极大似然估计就有无偏估计 然后计算当 时熵: 那么熵的估计量为 然后得到熵的序列 . 当然这里算的时候还是要判断 是否可逆. torch 算 应该已经封装了谱分解或奇异值分解了, 就没必要在这里再提一嘴了.

定理: 任意 维度随机变量 , , 则 .

也就是说, 正态分布的熵是最大的.

还有一种熵的计算方式. 且 .

这两种计算方式有什么差别呢?

当采样出 个答案 时, 熵的估计就是 能算 embedding 的熵吗?

近来，多模态大模型在多种视觉-文本任务上已经取得了不错的效果，但是幻觉仍然阻碍着多模态大模型的发展。既有的多模态大模型大多通过projector实现视觉信息与文本信息的对齐，即将图像tokens映射到文本空间，进行图像与文本信息的交互。我们的研究表明，图像信息在模态对齐和大语言模型处理过程中存在被缺失或被遗忘的情况，这加剧了幻觉的产生。基于此，我们提出了Post Interaction Block（PIB），该模块用于LLM backbone和lm head中间，实现了图像信息与文本信息的二次交互。此外，我们还考察了大模型内部状态的动态变化，通过输出token和输入token的关系矩阵变化佐证图像信息的缺失，以及句子embedding分布的熵及熵的变化和 PIB 前后输入的 embedding 的相似度设置拒绝回答的阈值，以规避幻觉内容的输出。 -->