论文阅读翻译之Deep reinforcement learning from human preferences

关于

• 首次发表日期：2024-09-11
• 论文原文链接：
  https://arxiv.org/abs/1706.03741
• 论文arxiv首次提交日期：12 Jun 2017
• 使用KIMI，豆包和ChatGPT等机翻，然后人工润色
• 如有错误，请不吝指出

Deep reinforcement learning from human preferences（基于人类偏好的深度强化学习）

Abstract （摘要）

对于复杂的强化学习（RL）系统来说，要与现实世界环境有效互动，我们需要向这些系统传达复杂目标。在这项工作中，我们探索了以（非专家）人类对轨迹段对的偏好来定义目标。我们展示了这种方法可以在没有奖励函数的情况下有效解决复杂的RL任务，包括Atari游戏和模拟机器人运动，同时仅需对不到1%的代理与环境交互提供反馈。这大大降低了人类监督的成本，使其能够实际应用于最先进的强化学习系统。为了展示我们方法的灵活性，我们表明可以在大约一小时的人类参与时间内成功训练出复杂的新行为。这些行为和环境比以往任何从人类反馈中学到的都要复杂得多。

1 Introduction （引言）

最近在将强化学习 (RL) 扩展到大规模问题上取得的成功，主要得益于那些具有明确奖励函数的领域（Mnih等, 2015, 2016; Silver等, 2016）。不幸的是，许多任务的目标是复杂的、定义不清的或难以明确说明的。克服这一限制将大大扩展深度强化学习的潜在影响，并可能进一步扩大机器学习的应用范围。

例如，假设我们想使用强化学习训练一个机器人来清洁桌子或炒鸡蛋。如何构建一个合适的奖励函数并不明确，而这个奖励函数需要依赖机器人的传感器数据。我们可以尝试设计一个简单的奖励函数，大致捕捉预期的行为（intended behavior），但这通常会导致机器人行为优化我们的奖励函数，但机器人行为并实际上却不符合我们的偏好。这种困难是构成近期关于我们价值观（values）与强化学习系统目标不一致的基础（Bostrom, 2014; Russell, 2016; Amodei等, 2016）。如果我们能够成功地向智能体（agent）传达我们的实际目标，将是解决这些问题的关键一步。

如果我们拥有所需任务的示范，就可以通过逆向强化学习 (Ng 和 Russell, 2000) 提取一个奖励函数，然后使用该奖励函数来训练通过强化学习训练一个智能体。更直接的方式是使用模仿学习（imitation learning）来复制示范的行为。然而，这些方法并不适用于人类难以演示的行为（例如控制一个具有多自由度且形态与人类差异很大的机器人）。

另一种方法是允许人类对系统当前的行为提供反馈，并利用这些反馈来定义任务。原则上，这符合强化学习的范式，但直接将人类反馈作为奖励函数对于需要数百或数千小时经验的强化学习系统来说成本过高。为了能够在实际上基于人类反馈训练深度强化学习系统，我们需要将所需反馈的量减少几个数量级。

我们的方法是从人类反馈中学习奖励函数，然后优化这个奖励函数。这种基本方法之前已经被考虑过，但我们面对的是如何将其扩展到现代深度强化学习中的挑战，并展示了迄今为止从人类反馈中学到的最复杂的行为。

总之，我们希望找到一个解决方案来处理没有明确指定奖励函数的顺序决策问题，这个解决方案应该满足以下条件：

1. 能够解决我们只能
   识别
   期望行为但不一定能够示范的任务，
2. 允许非专家用户教导智能体，
3. 能够扩展到大型问题，且
4. 在用户反馈方面经济高效。

我们的算法在训练策略优化当前预测的奖励函数的同时，根据人类的偏好拟合一个奖励函数（见图1）。我们要求人类比较智能体行为的短视频片段，而不是提供绝对的数值评分。我们发现，在某些领域，进行比较对人类来说更容易，同时在学习人类偏好时同样有效。比较短视频片段的速度几乎与比较单个状态一样快，但我们证明，这种比较方式显著更有帮助。此外，我们还表明，在线收集反馈能够提高系统性能，并防止它利用所学奖励函数的漏洞。

我们的实验在两个领域进行：Arcade Learning Environment（Bellemare等, 2013）中的Atari游戏，以及物理模拟器MuJoCo（Todorov等, 2012）中的机器人任务。我们展示了即使是非专家人类提供的少量反馈，从十五分钟到五小时不等，也足以学习大多数原始的强化学习任务，即使奖励函数不可观察。随后我们在每个领域中考虑了一些新行为，例如完成后空翻或按照交通流向驾驶。我们证明了我们的算法能够通过大约一小时的反馈学习这些行为——即使很难通过手工设计奖励函数来激励这些行为。

1.1 Related Work（相关研究）

大量研究探索了基于人类评分或排序的强化学习，包括 Akrour 等 (2011)、Pilarski 等 (2011)、Akrour 等 (2012)、Wilson 等 (2012)、Sugiyama 等 (2012)、Wirth 和 Fürnkranz (2013)、Daniel 等 (2015)、El Asri 等 (2016)、Wang 等 (2016) 和 Wirth 等 (2016)。另一些研究则关注从偏好而非绝对奖励值出发的强化学习问题 (Fürnkranz 等, 2012; Akrour 等, 2014)，以及在非强化学习环境中通过人类偏好进行优化的研究 (Machwe 和 Parmee, 2006; Secretan 等, 2008; Brochu 等, 2010; Sørensen 等, 2016)。

我们的算法遵循与Akrour等人(2012)和Akrour等人(2014)相同的基本方法。他们研究了四个自由度的连续域和小的离散域，在这些域中，他们可以假设奖励在手编码特征的期望中是线性的。我们则研究具有几十个自由度的物理任务和没有手工设计特征的 Atari 任务；我们环境的复杂性迫使我们使用不同的强化学习算法和奖励模型，并应对不同的算法权衡。一个显著的区别在于，Akrour等人(2012)和Akrour等人(2014)是从整个轨迹中获取偏好，而不是短片段。因此，虽然我们收集了多两个数量级的比较，但我们的实验所需的人类时间少于一个数量级。其他区别主要在于调整我们的训练程序，以应对非线性奖励模型和现代深度强化学习，例如使用异步训练和集成方法。

我们对反馈引导的方法与 Wilson 等人 (2012) 的研究非常接近。然而，Wilson 等人 (2012) 假设奖励函数是到某个未知“目标”策略的距离（该策略本身是手工编码特征的线性函数）。他们通过贝叶斯推理拟合这个奖励函数，而不是执行强化学习，他们根据目标策略的最大后验估计 (MAP) 生成轨迹。他们的实验涉及的是从其贝叶斯模型中抽取的“合成”人类反馈，而我们进行了从非专家用户收集反馈的实验。目前尚不清楚 Wilson 等人 (2012) 的方法是否可以扩展到复杂任务，或是否能够处理真实的人类反馈。

MacGlashan 等 (2017)、Pilarski 等 (2011)、Knox 和 Stone (2009)、以及 Knox (2012) 进行了一些涉及基于真实人类反馈的强化学习实验，尽管他们的算法方法并不十分相似。在 MacGlashan 等 (2017) 和 Pilarski 等 (2011) 的研究中，学习仅在人工训练者提供反馈的回合（episodes）中进行。这在像 Atari 游戏这样的领域似乎是不可行的，因为学习高质量策略需要数千小时的经验，即使对于我们考虑的最简单任务，这种方法的成本也过于昂贵。TAMER（Knox, 2012; Knox 和 Stone, 2013）也学习奖励函数，但他们考虑的是更简单的设置（settings），在这些设置中，期望的策略可以相对快速地学习。

我们的工作也可以看作是合作逆向强化学习框架（ cooperative inverse reinforcement learning framework）（Hadfield-Menell 等, 2016）的一个特定实例。这个框架考虑了一个人类和机器人在环境中互动的两人游戏，目的是最大化人类的奖励函数。在我们的设置中，人类只能通过表达他们的偏好来与这个游戏进行互动。

与之前的所有工作相比，我们的关键贡献是将人类反馈扩展到深度强化学习，并学习更复杂的行为。这符合将奖励学习方法扩展到大型深度学习系统的最新趋势，例如逆强化学习（Finn等人，2016年）、模仿学习（Ho和Ermon，2016年；Stadie等人，2017年）、半监督技能泛化（Finn等人，2017年）以及从示范中引导强化学习（Silver等人，2016年；Hester等人，2017年）。

2 Preliminaries and Method（预备知识与方法）

2.1 Setting and Goal（配置与目标）

我们考虑一个智能体在一系列步骤中与环境进行交互；在每个时刻
\(t\)
，智能体从环境中接收观察
\(o_t \in \mathcal{O}\)
，然后向环境发送动作
\(a_t \in \mathcal{A}\)
。

在传统的强化学习中，环境还会提供奖励
\(r_t \in \mathbb{R}\)
，智能体的目标是最大化奖励的折扣和（discounted sum of rewards）。与假设环境生成奖励信号不同，我们假设有一位人类监督者可以在
轨迹片段
（trajectory segments）之间表达偏好。轨迹片段是观察和动作的序列，
\(\sigma=\left(\left(o_0, a_0\right),\left(o_1, a_1\right), \ldots,\left(o_{k-1}, a_{k-1}\right)\right) \in(\mathcal{O} \times \mathcal{A})^k\)
。我们用
\(\sigma^1 \succ \sigma^2\)
表示人类更偏好轨迹片段
\(\sigma^1\)
而非轨迹片段
\(\sigma^2\)
。非正式地说，智能体的目标是生成人类偏好的轨迹，同时尽量减少向人类询问的次数。

更确切地说，我们将通过两种方式评估我们算法的行为：

定量：
我们说偏好
\(\succ\)
是由一个奖励函数
^[1]
\(r: \mathcal{O} \times \mathcal{A} \rightarrow \mathbb{R}\)
生成的，如果

每当

如果人类的偏好是由奖励函数
\(r\)
生成的，那么我们的智能体应当根据
\(r\)
获得高的总奖励。因此，如果我们知道奖励函数
\(r\)
，我们就能对代理进行量化评估。理想情况下，代理应达到的奖励几乎与其使用强化学习来优化
\(r\)
时一样高。

定性
：有时我们没有奖励函数来对行为进行定量评估（这正是我们的方法在实际中有用的情况）。在这些情况下，我们只能定性地评估智能体满足人类偏好的程度。在本文中，我们将从一个用自然语言表达的目标开始，要求人类根据智能体实现该目标的情况来评估智能体的行为，然后展示智能体尝试实现该目标的视频。

我们的基于轨迹片段比较的模型与 Wilson 等人 (2012) 中使用的轨迹偏好查询非常相似，不同之处在于我们不假设可以将系统重置为任意状态
^[2]
，并且我们的片段通常从不同的状态开始。这使得人类比较的解释（interpretation of human comparisons）变得更加复杂，但我们展示了即使人类评分者对我们的算法不了解，我们的算法也能够克服这一难题。

2.2 Our Method（我们的方法）

在每个时刻，我们的方法维持一个策略
\(\pi: \mathcal{O} \rightarrow \mathcal{A}\)
和一个奖励函数估计
\(\hat{r}: \mathcal{O} \times \mathcal{A} \rightarrow \mathbb{R}\)
，它们均由深度神经网络参数化。

这些网络通过三个过程进行更新：

1. 策略
   \(\pi\)
   与环境交互，生成一组轨迹
   \(\left\{\tau^1, \ldots, \tau^i\right\}\)
   。使用传统的强化学习算法更新
   \(\pi\)
   的参数，以最大化预测奖励的总和
   \(r_t=\hat{r}\left(o_t, a_t\right)\)
   。
2. 从步骤1生成的轨迹
   \(\left\{\tau^1, \ldots, \tau^i\right\}\)
   中选择片段对
   \(\left(\sigma^1, \sigma^2\right)\)
   ，并将它们发送给人类进行比较。
3. 通过监督学习优化映射
   \(\hat{r}\)
   的参数，以拟合迄今为止从人类收集的比较结果。

2.2.1 Optimizing the Policy （对策略进行优化）

在使用
\(\hat{r}\)
计算奖励后，我们面临的是一个传统的强化学习问题。我们可以使用任何适合该领域的强化学习算法来解决这个问题。一个细微之处在于，奖励函数
\(\hat{r}\)
可能是非平稳的（non-stationary），这使我们倾向于选择对奖励函数变化具有鲁棒性的算法。这导致我们专注于策略梯度方法（policy gradient methods），这些方法已经成功应用于这类问题（Ho 和 Ermon, 2016）。

在本文中，我们使用
优势演员-评论员（advantage actor-critic）
（A2C；Mnih 等, 2016）来玩 Atari 游戏，并使用
信赖域策略优化（trust region policy optimization）
（TRPO；Schulman 等, 2015）来执行模拟机器人任务。在每种情况下，我们都使用了被发现对传统强化学习任务有效的参数设置。我们唯一调整的超参数是 TRPO 的熵奖励（entropy bonus），因为 TRPO 依赖信赖域来确保足够的探索，如果奖励函数不断变化，这可能导致探索不足。

我们将
\(\hat{r}\)
生成的奖励归一化（normalized）为均值为零、标准差恒定。这是一个典型的预处理步骤，尤其适合于我们的学习问题，因为奖励的位置（position of the rewards）在我们的学习过程中是未定的。

2.2.2 Preference Elicitation（偏好获取）

人类监督者会看到两个可视化的轨迹片段，以短视频片段的形式呈现。在我们所有的实验中，这些视频片段的时长在 1 到 2 秒之间。

然后，人类指示他们更喜欢哪个片段，或者表示两个片段同样优秀，或者表示他们无法比较这两个片段。

人类的判断记录在数据库
\(\mathcal{D}\)
中，形式为三元组
\(\left(\sigma^1, \sigma^2, \mu\right)\)
，其中
\(\sigma^1\)
和
\(\sigma^2\)
是两个片段，
\(\mu\)
是一个在
\(\{1,2\}\)
上的分布，表示用户更喜欢哪个片段。如果人类选择一个片段为更优，则
\(\mu\)
将所有权重放在该选择上。如果人类标记这两个片段为同样可取，则
\(\mu\)
是均匀分布。最后，如果人类标记这两个片段不可比较，则该比较将不包含在数据库中。

2.2.3 Fitting the Reward Function （拟合奖励函数）

我们可以将奖励函数估计
\(\hat{r}\)
视为一个偏好预测器，如果我们将
\(\hat{r}\)
看作解释人类判断的潜在因素，并假设人类选择偏好片段
\(\sigma^i\)
的概率呈指数地取决于在片段长度上潜在奖励的合计值：
^[3]

我们选择
\(\hat{r}\)
以最小化这些预测与实际人类标签之间的交叉熵损失：

这遵循了从成对偏好估计评分函数Bradley-Terry模型（Bradley和Terry，1952），并且是Luce-Shephard选择规则（Luce，2005；Shepard，1957）在轨迹片段上的偏好的特化。它可以理解为将奖励等同于一个偏好排序尺度（preference ranking scale），类似于为国际象棋开发的著名的 Elo 排名系统（Elo，1978）。就像两个国际象棋棋手的 Elo 分数之差估计了一个棋手在一盘国际象棋比赛中击败另一个棋手的概率一样，两个轨迹片段的预测奖励之差估计了人类选择一个而不是另一个的概率。

我们实际的算法对这个基本方法进行了一些修改，早期实验发现这些修改很有帮助，并在第3.3节中进行了分析：

• 我们拟合一个预测器的集合（ensemble），每个预测器都是在从
  \(\mathcal{D}\)
  中抽样的
  \(|\mathcal{D}|\)
  个三元组上训练的（允许重复抽样）。估计值
  \(\hat{r}\)
  通过独立地对每个预测器进行归一化，然后对结果取平均来定义。
• 数据中有
  \(1/e\)
  的部分被保留，作为每个预测器的验证集。我们使用
  \(\ell_2\)
  正则化，并调整正则化系数，以保持验证损失在训练损失的1.1到1.5倍之间。在某些领域，我们还应用 dropout 进行正则化。
• 我们不是像公式 1 中描述的那样直接应用 softmax，而是假设人类有 10%的概率随机均匀地（uniformly）做出响应。概念上，这种调整是必要的，因为人类评估者有一个固定的犯错误概率，这个概率不会随着奖励差异变得极端而衰减至0。

2.2.4 Selecting Queries （选择查询）

我们根据奖励函数估计器的不确定性近似来决定如何查询偏好，这类似于Daniel等人(2014)的方法：我们采样大量的长度为
\(k\)
的轨迹片段对，使用我们集合中的每个奖励预测器来预测每一对中哪个片段会被偏好，然后选择那些在集合成员之间预测方差最高的轨迹。这是一种粗糙的近似，第三节中的消融实验表明，在某些任务中它实际上损害了性能。理想情况下，我们希望基于查询的信息价值来查询(Akrour等人, 2012; Krueger等人, 2016)，但我们留待未来的工作进一步探索这一方向。

前言

万字长文！这里有我的一些思考和领会，网络上的教程都太潦草了。

并且我
发现了新的反演公式
！

概述

二项式反演用于转化两个具有特殊关系的函数
\(f\)
和
\(g\)
，从而方便求解问题。一般来说，直接计算恰好满足
\(n\)
个限制的答案不好求，但是可以计算出“至少” / “至多”满足
\(n\)
个限制的答案，运用二项式反演，就能求出“恰好”满足
\(n\)
个限制的答案。

想直接看结论的可以
戳我
。

证明 & 推导

一些引理

引理
\(1\)
：二项式定理

普通二项式定理为：

证明可以用数学归纳法，不做展开。本篇主要利用
\(a = -1, b = 1\)
的特殊情形，即：

注意到当
\(n = 0\)
的时候，没有意义。观察原式发现此时
\(\dbinom{0}{0} (-1)^0 = 1\)
。所以我们有：

引理
\(2\)
：多步容斥

记
\(S_i\)
（
\(1 \leq i \leq n\)
）表示一个集合，我们有：

即：

证明该式等价于证明
\(\forall x \in \bigcup \limits_{i = 1}^{n} S_i\)
，其在右边
\(\sum \limits _ {a_i < a_{i + 1}} \Bigg \vert \bigcap \limits _ {i = 1} ^ m S_{a_i} \Bigg \vert\)
计算的系数之和为
\(1\)
。记所有包含
\(x\)
的集合为
\(T_1, \ldots, T_m\)
（
\(m \neq 0\)
），则有：

故成立。

引理
\(3\)
：组合数

我们考虑变换
\(\dbinom{n}{i} \dbinom{i}{j}\)
。其组合意义为，
\(n\)
个小球里选出
\(i\)
个，再从
\(i\)
个里面选出
\(j\)
的方案数。我们也可以先从
\(n\)
个里面选出
\(j\)
个，再从剩下
\(n - j\)
里选出
\(i - j\)
个。表达为：

当然也可以代数证明：

引理
\(4\)
：
\(-1\)
的幂次特点

\((-1) ^ {a + b} = (-1) ^ {a - b}\)
。这还用证明？

模型
\(0\)

\[\large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i)
\]

容斥证明

不妨记
\(\overline{S_i}\)
表示
\(S_i\)
的补集，有：

由于
\(\overline{\ \overline{S_i}\ } = S_i\)
，所以得到类似的式子：

发现形式很像，但是还差一步构造。我们假设能够早出一组
\(S_i\)
，使任意
\(k\)
个集合的交集大小相等。

不妨记
\(f(x)\)
表示任意
\(x\)
个补集的交集大小，对于原集同理记
\(g(x)\)
，上式可以分别改写为：

即证。

代数证明

容斥比较抽象，尝试代数证明。我们把
\(g\)
带到
\(f\)
中去，得到：

即证。

模型
\(1\)
：“至少”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i)
\]

为了解决实际问题，考虑实际意义。考虑有
\(n\)
个限制，
\(f(x)\)
表示至少满足
\(x\)
个限制，
\(g(x)\)
表示恰好满足
\(x\)
个限制。

注意到，
\(f\)
不是简单
\(g\)
的前缀和，因为会重复计数。

\(g(x)\)
即为我们的答案，而
\(f(x)\)
就是我们通过其他算法求出的结果。

通常来说，我们会钦定
\(x\)
个限制必须满足，剩下的限制可以满足可以不满足，这样就能不用考虑限制的问题，求出
\(f\)
。

考虑如何用
\(g\)
表示出
\(f\)
。有两种思考方式：

1. 我们考虑求
   \(g(x)\)
   的过程。初始令
   \(g(x) \gets f(x)\)
   ，这显然是不对的。我们考虑一个
   \(i > x\)
   ，
   \(g(i)\)
   在
   \(f(x)\)
   中贡献次数是
   \(\dbinom{i}{x}\)
   ，所以得到：
   
   
   
   \[g(x) = f(x) - \sum _ {i = x + 1} ^ n \binom{i}{x} g(i)
   \]
   
   
   
   移项后就有：
   
   
   
   \[\begin{aligned}
   f(x) &= g(x) + \sum _ {i = x + 1} ^ n \binom{i}{x} g(i) \\
   &= \sum _ {i = x} ^ n \binom{i}{x} g(i)
   \end{aligned}
   \]
   
   

2. 更直接的思考方式为，我们考虑枚举钦定
   \(x\)
   个限制必须满足后，还有
   \(i - x\)
   个限制也被满足了，即一共有
   \(i\)
   个限制被满足，其中任选
   \(x\)
   个都能被计数，乘上
   \(\dbinom{i}{x}\)
   后，求和就能不重不漏：
   
   
   
   \[f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i)
   \]
   
   

这就是左边那一条等式了。证明右边等式是对的，可将其带入。

即证。

模型
\(2\)
：“至多”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Leftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i)
\]

当然我们可以直接采用模型
\(1\)
的方式推式子。记
\(f(x)\)
表示至多满足
\(x\)
个限制的方案，
\(g(x)\)
表示恰好。

首先用
\(g\)
表示出
\(f\)
，这可以枚举并钦定
\(i \leq x\)
个限制，最后求和得出：

然后把它带到
\(g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i)\)
中。

得证。

当然，如果不考虑问题的实际意义，利用模型
\(0\)
也可以证明。设
\(h(x) = (-1) ^ x g(x)\)
，有：

那么有：

则：

将
\(h\)
视作命题中的
\(g\)
，即证。

更多思考

注意到「至多满足
\(x\)
个条件」，可以看做「至少不满足
\(n - x\)
个条件」；同理，「至少满足
\(x\)
个条件」，可以看做「至多不满足
\(n - x\)
个条件」，然后就可以相互推导，形成新的一对反演公式，我愿称它们为形式
\(2\)
。

模型
\(1\)
：“至少”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Leftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i)
\]

记
\(f(x) = f'(n - x)\)
，表示至少满足
\(x\)
个条件，其中
\(f'\)
就符合模型
\(2\)
了。有
\(f'(x) = \sum \limits _ {i = 0} ^ x \dbinom{x}{i} g'(i)\)
，其中
\(g'(x)\)
表示恰好不满足
\(x\)
个条件，相当于
\(g(n - x)\)
，即恰好满足
\(n - x\)
个条件，可以得到：

由于
\(g'(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f'(i)\)
，所以有：

所以成立。

模型
\(2\)
：“至多”
\(\Leftrightarrow\)
“恰好”

\[\large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Leftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i)
\]

类似地，记
\(f(x) = f'(n - x)\)
，表示至多满足
\(x\)
个条件，其中
\(f'\)
就符合模型
\(1\)
了。有
\(f'(x) = \sum \limits _ {i = x} ^ n \dbinom{i}{x} g'(i)\)
，其中
\(g'(x)\)
表示恰好不满足
\(x\)
个条件，相当于
\(g(n - x)\)
，即恰好满足
\(n - x\)
个条件。可以得到：

由于
\(g'(x) = \sum \limits_ {i = x} ^ n (-1)^{i - x} \dbinom{i}{x} f'(i)\)
，所以有：

所以成立。

例题 & 习题

等有时间再写啦。

结论

模型
\(0\)

模型
\(1\)
：“至少”
\(\Leftrightarrow\)
“恰好”

形式
\(1\)

形式
\(2\)

模型
\(2\)
：“至多”
\(\Leftrightarrow\)
“恰好”

形式
\(1\)

形式
\(2\)

根据与源表相联接的结果，对目标表进行插入、更新、删除等操作。 例如，对目标表，如果源表存在的数据则更新，没有的则插入，就可以使用MEREG进行同步。

基本语法

MERGE INTO target_table
USING source_table
ON condition
WHEN MATCHED THEN 
XXX
WHEN NOT MATCHED THEN 
XXX

这里的Source table 不限于单独的表格，也可以是子查询的内容

示例

INSERT tbl_A (col, col2)
SELECT col, col2
FROM tbl_B
WHERE NOT EXISTS (SELECT col FROM tbl_A A2 WHERE A2.col = tbl_B.col);

上面的SQL是为了向 tbl_A 中插入 tbl_B 含有的，但是 tbl_A 不包含的col
改为MERGE可以写为

MERGE INTO tbl_A  t  
    USING tbl_B v  
    ON t.col = v.col  
    WHEN MATCHED THEN   
        UPDATE SET y.c2 = v.c2  
    WHEN NOT MATCHED THEN  
        INSERT (col, col2) VALUES (v.c1, v.c2);

（这里为了展示更多的选项，加多了一句UPDATE）
当一个表需要依托于另一个表进行更新操作的时候，使用MERGE可以快捷的实现

标记压缩通过减少冗余标记的数量（例如，修剪不重要的标记或合并相似的标记）来加快视觉变换器（
ViTs
）的训练和推理。然而，当这些方法应用于下游任务时，如果训练和推理阶段的压缩程度不匹配，会导致显著的性能下降，这限制了标记压缩在现成训练模型上的应用。因此提出了标记补偿器（
ToCom
），以解耦两个阶段之间的压缩程度。该插件通过在预训练模型上额外执行了一个快速参数高效的自蒸馏阶段获得一个小型插件，描述了不同压缩程度下模型之间的差距。在推理过程中，
ToCom
可以直接插入到任何下游现成模型中，无论训练和推理的压缩程度是否匹配，都能获得通用的性能提升，而无需进一步训练。

来源：晓飞的算法工程笔记 公众号，转载请注明出处

论文: Token Compensator: Altering Inference Cost of Vision Transformer without Re-Tuning

• 论文地址：
  https://arxiv.org/abs/2408.06798
• 论文代码：
  https://github.com/JieShibo/ToCom

Introduction

视觉变换器（
ViTs
）在计算机视觉的多个领域取得了显著成功，包括图像分类、目标检测、语义分割等。然而，随着
ViTs
规模的快速增长，计算成本的增加已成为一个迫切问题。因此，大量研究工作集中在加速
ViTs
的训练和推理上。
ViTs
的特点在于能够处理可变数量的输入标记，除了卷积神经网络中广泛使用的传统技术，如模型剪枝、量化和蒸馏，近期的研究通过标记压缩来加速
ViTs
，例如修剪不重要的标记或合并相似的标记。

与剪枝和蒸馏等技术相比，标记压缩技术具有明显的优势。一些标记压缩方法（例如，
ToMe
）可以以零样本的方式应用于现成模型或用于加速训练。与量化不同，标记压缩方法不需要对低精度操作符的支持。此外，标记压缩方法与上述其他技术在操作上是正交的，使其在
ViTs
中具有广泛的适用性。

然而，当标记压缩应用于下游任务时，论文观察到如图
1
所示的以下缺点：

1. 尽管一些标记压缩技术可以应用于现成模型，但通常会导致显著的性能下降。
2. 即使标记压缩仅在训练期间应用以加速过程，而在推理期间不进行压缩，模型的性能仍然低于未经标记压缩训练的模型。
3. 总之，当训练和推理阶段的标记压缩程度不一致时，模型的性能表现不佳。

论文指出，经过不同标记压缩程度微调的模型在参数层面存在一定的差距，这导致在推理过程中改变压缩程度时性能下降。此外，这一差距可以在不同的下游数据集之间转移。基于此，论文提出标记补偿器（
Token Compensator
，简称
ToCom
），这是一种旨在解耦训练和推理过程中的标记压缩程度的预训练插件。
ToCom
是一个参数高效的模块，仅包含少量参数，用于描述具有不同压缩程度的模型之间的差距。为了获得
ToCom
，在预训练数据集上通过不同压缩程度之间的快速自蒸馏过程进行训练。具体来说，教师模型和学生模型都是相同的冻结预训练模型，其中学生模型包括
ToCom
。在每一步中，教师模型和学生模型被随机分配不同的压缩程度，同时
ToCom
通过蒸馏学习它们之间的差距。此外，为不同的压缩程度设置分配不同
ToCom
参数的子集，使
ToCom
能够通过单一的训练过程适应各种压缩程度对。

在推理过程中，将
ToCom
直接集成到在下游任务上进行微调的现成模型中，而无需进一步训练。通过选择
ToCom
参数的子集，微调后的模型可以直接应用于各种标记压缩程度，并达到与训练和推理压缩程度一致时相当的性能。重要的是，
ToCom
只需预训练一次，即可应用于在任意下游数据集上经过微调的模型，不论其标记压缩程度如何，从而使任何单一的现成模型能够处理动态延迟约束，而无需修改参数。

论文在超过
20
个数据集上进行了实验，涵盖了各种压缩程度设置。实验结果表明，
ToCom
作为一个即插即用的模块，能够有效地解耦训练和推理过程中的标记压缩程度。例如，在
VTAB-1k
基准测试中，
ToCom
在
DeiT-B
的平均性能上比
ToMe
最高可提升
2.0%
，如图
1
所示。
ToCom
还可以应用于不同规模的模型或在不同对象上预训练的模型，或者用于增强各种标记压缩方法，包括标记合并和标记剪枝。

Delve into Token Compression

Impact of Compression Degrees

首先，对
ViTs
中的标记压缩方法进行公式化。
ViTs
的单层由两个模块组成，即多头自注意力（
MHSA
）和多层感知机（
MLP
）。该层可以被形式化为

其中，
\(\mathbf{X}^l \in \mathbb{R}^{N \times d}\)
是第
\(l\)
层的输入，具有长度
\(N\)
和维度
\(d\)
，
LN
表示层归一化。

论文主要关注一种具有代表性且最先进的无训练标记压缩方法
ToMe
，并进一步推广到其他方法。
ToMe
在
MHSA
和
MLP
模块之间操作，利用图像块标记的键来评估它们的相似性，并通过二分软匹配将
\(r\)
个相似的标记进行合并。

在
ToMe
中，每层合并的标记数量被视为超参数，以调整
ViTs
的吞吐量，这通常在训练之前根据推理需求来确定。合并的标记越多，模型在训练和推理时的速度就越快，如图
3
所示。然而，在实际场景中，训练期间的压缩程度（称为源压缩程度）和推理期间的压缩程度（称为目标压缩程度）可能不一定相等。也就是说，一个在某一压缩程度下训练好的现成模型，可能会在没重新训练的情况下进行不同的压缩程度下的应用。这种情况具有实际意义，例如，使用下载的
checkpoint
而无法访问训练数据或重新训练资源时，或根据服务器负载动态调整推理期间的压缩程度。此外，在现有计算资源有限的情况下，可能需要在训练期间使用较高的压缩程度以减少内存和时间开销，但在推理期间恢复到较低的压缩程度以确保性能。

为了研究标记压缩方法在源压缩程度与目标压缩程度不一致时的性能，论文在五个下游数据集上进行了实验。如图
2
所示，论文对
DeiT-B
进行了
ToMe
的
\(r=0\)
和
\(16\)
的微调，并报告了在推理期间使用
\(r=0, 2, 4, \ldots, 16\)
的性能。可以看到，对于特定的目标压缩程度，当源压缩程度与其匹配时，模型的表现更好。源压缩程度与目标压缩程度之间的差距越大，性能下降的程度就越显著。

然而，由于在较低压缩程度下训练的模型在训练期间接触到了更多的标记，这意味着它们遇到的信息范围比在较高压缩程度下训练的模型更广泛，因此，前者在各种目标压缩程度下理应优于后者。这表明，不同源压缩程度下训练的模型之间存在差距，使得在不同压缩程度之间的迁移效果较差。

Transfer across Tasks

对于具有不同源压缩程度的模型之间的差距，是否可以在不同任务之间转移？更具体地说，令
\(\mathcal{M}_m^{\mathcal{D_A}}\)
和
\(\mathcal{M}_{n}^{\mathcal{D_A}}\)
表示在数据集
\(\mathcal{D_A}\)
上以压缩程度
\(m\)
和
\(n\)
训练的模型，
\(\mathcal{M}_m^{\mathcal{D_B}}\)
和
\(\mathcal{M}_{n}^{\mathcal{D_B}}\)
表示在数据集
\(\mathcal{D_B}\)
上训练的模型。如果这种差距是可转移的，应该有

其中
\(+\)
和
\(-\)
分别是逐元素的加法和减法。为了验证这一点，将公式重新写为

这意味着
\((\mathcal{M}_{m}^{\mathcal{D_A}} - \mathcal{M}_n^{\mathcal{D_A}} + \mathcal{M}_n^{\mathcal{D_B}})\)
在以目标压缩程度
\(m\)
对数据集
\(\mathcal{D_B}\)
进行评估时，应当比
\(\mathcal{M}_n^{\mathcal{D_B}}\)
的表现更好。换句话说，
\((\mathcal{M}_{m}^{\mathcal{D_A}} - \mathcal{M}_n^{\mathcal{D_A}})\)
在数据集
\(\mathcal{D_A}\)
上的差距可以转移到
\(\mathcal{D_B}\)
，并有助于缩小
\(\mathcal{M}_{m}^{\mathcal{D_B}}\)
和
\(\mathcal{M}_n^{\mathcal{D_B}}\)
之间的差距。

在
ToMe
上进行初步实验，使用
CIFAR100
作为
\(\mathcal{D_A}\)
，
\(m=16\)
，
\(n=0\)
。在表
1
中，展示了使用不同
FGVC
数据集作为
\(\mathcal{D_B}\)
时的结果。通过添加
\((\mathcal{M}_{16}^{\mathcal{D_A}} - \mathcal{M}_0^{\mathcal{D_A}})\)
，
\(\mathcal{M}_0^{\mathcal{D_B}}\)
在
\(r=16\)
下的表现明显提高，验证了在不同任务中存在源压缩程度之间的模型差距的正向迁移，这表明可以使用通用插件来建模这种差距，从而在各种下游任务中提高具有不等源和目标压缩程度的标记压缩性能。

Token Compensator

Arithmetic of Parameter-Efficient Modules

当训练和推理过程中的压缩程度不相等时，由于不同压缩程度的模型在行为上存在差异，导致其参数空间中出现不同的局部最小值，从而使模型性能下降。为了在这种情况下提升标记压缩的性能，尤其是在现成模型上，论文打算寻找一个通用插件以弥补具有不同压缩程度的模型之间的差距，假设两个特定压缩程度的模型在不同数据集上表现出类似的差距。假设有一个插件
\(\mathcal{P}_{m\rightarrow n}\)
，可以弥补在
ToMe
训练下的模型
\(\mathcal{M}_m\)
（压缩程度
\(r=m\)
）和模型
\(\mathcal{M}_{n}\)
（压缩程度
\(r=n\)
）之间的差距。如果
\(\mathcal{M}_m\)
是现成模型，可以期望

其中
\(\oplus\)
表示架构层面的聚合，
\(\mathcal{M}'_n\)
是用于以
\(r=n\)
进行推理的合成模型。

然而，由于压缩程度选择的范围广（例如，
DeiT-B
在
ToMe
中的
\(r \in \{0, 1, ..., 16\}\)
），为所有可能的压缩程度对（即
\(16\times17\)
种
\((m,n)\)
组合）训练和存储这些插件会导致显著的训练和存储开销。为此，论文从三个方面解决这个问题。

首先，受到参数高效微调的启发，该方法使用轻量级模块来描述预训练模型与微调模型之间的差距，论文也采用了参数高效模块来描述具有不同压缩程度的模型之间的差距。具体来说，使用
LoRA
作为
\(\mathcal{P}_{m\rightarrow n}\)
，即对
\(\mathcal{M}'_n\)
的所有权重矩阵
\(\mathbf{W}\in\mathbb{R}^{d_1\times d_2}\)
，有

其中，
\(\mathbf{W}_q\)
和
\(\mathbf{W}_v\)
是查询和值变换的权重矩阵，
\(s\)
是一个超参数，
\(\mathbf{A}\in\mathbb{R}^{d_1\times h}\)
和
\(\mathbf{B}\in\mathbb{R}^{h\times d_2}\)
是
LoRA
模块。
LoRA
模块仅占模型参数的约
0.1%
，并且在推理时不会增加额外的计算。

其次，使用
LoRA
来估计仅相邻压缩程度之间的差距，即
\(n=m+1\)
。对于
\(n>m+1\)
的情况，简单地累积
\(m\)
和
\(n\)
之间的所有插件，即

第三，假设模型之间的差距是可逆的，即
\(\mathcal{P}_{n\rightarrow m}=\ominus \mathcal{P}_{m\rightarrow n}\)
。当
\(n<m\)
时，插件被“减去”，即

其中，
\(\ominus\)
是
\(\oplus\)
的逆运算。为了实现
\(\ominus\)
，我们从权重中减去
LoRA
乘积
\(\mathbf{A}\mathbf{B}\)
，而不是加上它。

现在，只需训练和存储
16
组
LoRA
插件，以支持所有压缩程度对，这些插件的大小仍然相对于
ViT
主干来说微不足道，这些插件的集合称为
Token Compensator
（
ToCom
）。由于
ToCom
的轻量特性，它可以以最小的开销加载到
RAM
中，从而实现实时推理吞吐量切换。

Training ToCom

如前所述，
ToCom
应该是一个适用于任何下游数据集的通用插件。为了增强
ToCom
的泛化能力，将
ToCom
的训练整合为
ViT
主干的预训练阶段的扩展。具体而言，利用预训练数据（例如
ImageNet
）来训练
ToCom
。

为了获得支持任意压缩程度对的
ToCom
，论文提出了一种自蒸馏方法来训练它。以
ToMe
为例，使用
\(\widehat{\mathcal{M}}_n\)
来表示通过在现成的预训练模型上直接应用
ToMe
（
\(r=n\)
）得到的模型。训练损失的构造如下，

其中
\(m\)
和
\(n\)
在每次训练步骤中随机抽取，且满足
\(m \neq n\)
，
\(\mathcal{L}_{KD}\)
是带有软目标的知识蒸馏损失，即，

其中
\(\textrm{KL}\)
表示
Kullback
–
Leibler
散度，
\(\boldsymbol{x}\)
是输入。

如图
4
所示，在蒸馏过程中，冻结所有预训练的参数，包括分类头，只更新参数高效的
ToCom
。值得注意的是，虽然
ToCom
需要在大规模数据集上进行训练，但它的模型较轻量且收敛迅速。因此，与主干网络的预训练相比，它的训练开销可以忽略不计。

在训练完成
ToCom
后，可以直接将其部署到任何在下游任务上微调的现成模型上，进行任何源度数到目标度数的转换。将
ToCom
的
LoRA
产物加到或减去现成模型的权重上，用于推理而无需进一步训练。

Experiments

如果本文对你有帮助，麻烦点个赞或在看呗～
更多内容请关注 微信公众号【晓飞的算法工程笔记】

前提条件,使用最新版的
17.12.0 Preview2
,并且有有效的Copilot AI订阅,那么可以体验这些新鲜好用的功能

增强了Copilot AI对IEnumerable Visualizer的可编辑表达式功能

我们可以通过AI实现一些复杂的条件筛查,并且可以即时验证结果是否符合预期,对于开发和调试提供了极大的便利性!

提供对单元测试验证失败的信息帮助

当单元测试失败的时候,可以询问AI,为什么失败了,AI会给出相应的断点建议,
当它遇到断点时,Copilot提供受监视变量的值和期望值予以比较
如果存在多个验证错误,你可以继续追问,直到认为满意的解决办法为止!

提供对调试时变量的基本分析功能

当你对特定变量感兴趣时,你只需要点击询问AI即可获得此变量的一手信息,修复建议以及调用链等情况