总结4D VGGT基本来说还是依赖于 Easi3R 的 mask 策略。其实目前两篇文章都还比较 naive。PAGE-4D: DISENTANGLED POSE AND GEOMETRY ESTIMATION FOR 4D PERCEPTION作者用这张图说明了一件事情：在这个对极几何中（假设所有的运动都是刚性的），运动为动态场景下的几何估计提供了关键线索，但同时也由于破坏静态对极约束而对相机位姿估计造成干扰，如图 2(a) 所示。换言之，用于重建动态物体的信号，恰恰也是阻碍可靠位姿恢复的因素补充说明一下对极几何：对极几何接下来作者这一段推导我觉得是很好的，但是后面的方法却没有很好的考虑这些东西。也有可能是太难了。首先作者给出了在静态场景下：$$ x_t= K [R_{t \leftarrow r} D_{r}(x_r) K^{-1} x_r + t_{t \leftarrow r}] $$其中 $t$ 代表 target frame，$r$ 代表 reference frame。$x_{t/r}$ 为齐次像素坐标，$K$ 为相机参数，$t_{t \leftarrow r}$ 是从 reference frame 的相机坐标中心到 target frame 的相机坐标中心的偏移向量。$D_r$ 代表 reference frame 的深度。$R$ 为 Rotation Matrix。这个式子说明了经典的刚性场景几何假设：一旦深度与相机运动已知，跨帧像素对应关系即可无歧义地预测。在 VGGT 中，由于相对相机运动的集中性，位姿估计往往可简化为对本质矩阵 $E$ 的拟合，从而在齐次像素坐标之间施加对极约束。$$ \widetilde{x_t}^T E \widetilde{x_r} = 0, E = [t_{t \leftarrow r}] \times R_{t \leftarrow r} $$在静态场景中，对于所有未被遮挡的像素对上述几何关系与对极约束均成立。因此，在同一帧内对camera token 与geometry token 进行联合优化是一种合理的设计选择。之后在动态场景下：$$ x_t= K [R_{t \leftarrow r} D_{r}(x_r) K^{-1} x_r + t_{t \leftarrow r}] + KM_{t \leftarrow r} $$只需要在 $(1)$ 式的基础上考虑物体运动：$M_{t \leftarrow r}$ 表示由物体运动引起的位移。然而，在存在动态运动时，用于位姿估计的对极约束（式 2）不再成立，其违背可表示为如下残差：$$ \delta(x_r) \equiv \tilde{x}_t^{\top} E \tilde{x}_r \approx \frac{1}{Z_r}\, n(x_r)^{\top} \Delta X_{\perp}(x_r) $$其中，$n(x_r)$ 为与 $x_r$ 关联的对极线单位法向量，$\Delta X_\perp(x_r)$ 为动态位移在该法向方向上的分量。该残差刻画了动态运动将像素对应关系“推离”由相机运动预测的对极几何的程度。残差越大，静态场景假设的违背越严重，从而导致更大的位姿估计误差。式 (4) 表明，在动态场景中，仅有静态的未遮挡像素对 $(x_r^{\text{sta}}, x_t^{\text{sta}})$满足对极约束，而一般的未遮挡像素对仅满足几何关系（式 3）。结果作者就把这个作为一个理论分析，告诉大家要遮掩 motion 保留 static 部分，这一大段分析就没有别的用了。尔后作者就弄了一个 soft mask，并且施加给 attention。当然由于 soft mask 是一个卷积块给出的，因此作者是 Fine-Tuning 了 Middle Layer。注意这里就非常有说法了，与后面的 VGGT4D 主张在浅层、中间层和深层做不同的事情是有比较大的出入的。VGGT4D: Mining Motion Cues in Visual Geometry Transformers for 4D Scene Reconstruction先记录一下两条比较冲突的 advocation：Moreover, its core assumption that tokens violating epipolar geometry receive low attention does not generalize to VGGT, whose global attention aggregates signals across multiple views.Our design is motivated by empirical evidence of a consistent layer-wise trend in the original VGGT: shallow transformer layers capture salient motion information, which gradually fade in deeper layers.其他的做法就跟 Easi3R 差不太多了。不过一个比较迷惑的事情是，看起来他们的 mask 并不非常精确。应该说可能可以有一个比较大的改进。
太简单了的就不写了A1-Q2-a-ivSGD: 每iteration只用一个 data point 进行 update，所以梯度：$$ \theta' \leftarrow \theta - \frac{2\alpha}{N} (\theta x_i - y_i) x_i $$总梯度：$$ \nabla_{\theta}\mathcal{L} = \frac{2}{N} \sum_{i=1}^{N}(\theta x_i - y_i) x_i $$A1-Q4A2-Q2补充两个公式吧。对于均匀分布：$$ \left\{ \begin{array}{l} \mu_k = \dfrac{a_k+b_k}{2} \\[6pt] \sigma_k = \dfrac{(b_k-a_k)^2}{12} \end{array} \right. $$一般的二分类的边界：$$ d(x) = \ln \frac{P(X|Y=0)P(Y=0)}{P(X|Y=1)P(Y=1)} $$当然也可以写成超平面的形式。A2-Q4重点：$$ \frac{P(Y=1|X)}{P(Y=0|X)} = \frac{P(Y=1)P(X|Y=1)}{P(Y=0)P(X|Y=0)} = \frac{\pi \prod_{i=1}^{n} \frac{1}{\sqrt{2 \pi \sigma_{i,1}}} \exp \left( - \frac{(X_i - \mu_{i,1})^2}{2\sigma_{i,1}^2}\right)}{(1 - \pi ) \prod_{i=1}^{n} \frac{1}{\sqrt{2 \pi \sigma_{i,0}}} \exp \left( - \frac{(X_i - \mu_{i,0})^2}{2\sigma_{i,0}^2}\right)} \label{eq:og-disc-form} $$A3-SVM见 Cheat PaperA4-BPFeed-Forward 不写了一个需要记的结论：$\delta = (W_{i+1}^{T} \delta_{i+1}) \odot f'(Z_1)$注意，如果是最后一层，需要先算出 Loss 对输出的导数，再逐元素乘以激活函数的导数。：$\delta_{last} = \frac{\partial L}{\partial \hat{y}} \odot \sigma'(Z)$如果是 BCE + Sofmax，那么 $\delta_{last} = \hat{y} - y$A5-Q1K-means 做题方法：比如是让你最后分成两类，直接选一个 $k=2$ 就行了。然后初始化 centroid 也随便取前 $k$ 个点就行了（随便都行，只是为了方便）。然后算距离，分配每一个点给 centroid，然后重新计算 centroid。迭代更新到收敛就行了（不再有点发生变化）A5-Q2EM 比较重要的一个做题直接贴一个参考答案就懂了主要是要注意权重
Gemini 大手子发力了！你好！我是 Theory of Computation 课程的出题专家。根据你提供的 Lecture 12 (Undecidability and Reducibility)、Assignment 3 (Turing Machine) 以及 Chomsky 体系结构的相关材料，我为你设计了 10 道模拟选择题。考查核心逻辑在 Theory of Computation 的考试中，区分 Decidable (Recursive) 和 Recognizable (Recursively Enumerable) 是核心难点。你需要掌握以下层级关系：Regular $\subset$ Context-Free $\subset$ Decidable $\subset$ Recognizable。如果一个语言是 Regular 或 CFL，它必然是 Decidable 的。Decidable (判定)：TM 总是会停机（接受或拒绝）。Recognizable (识别)：对于属于语言的串，TM 会停机接受；对于不属于的串，TM 可能拒绝，也可能死循环。模拟选择题 (10道)题目说明： 对于下列每一个语言 $L$，请从选项中选出最准确的分类描述。 选项： A. Turing-decidable (Recursive) B. Turing-recognizable but not decidable C. Not Turing-recognizable D. Context-FreeQ1. 基础正则语言语言： $L = { w \in {0, 1}^* \mid w \text{ 包含子串 } 101 }$ 分析： 这是一个典型的正则语言。 解答： A (Turing-decidable) 详解： 正则语言（Regular Language）是 Decidable 的子集。我们可以设计一个 DFA 来接受它，DFA 可以转化为一个总是停机的 TM。虽然它是 Regular，但如果没有 Regular 选项，Decidable 是正确的归类。Q2. 经典的非 CFL语言： $L = { a^n b^n c^n \mid n \ge 0 }$ 分析： 在 Assignment 3 Q1 中，要求设计一个 "Standard TM to decide" 这个语言。 解答： A (Turing-decidable) 详解： 这个语言虽然不是 Context-Free 的（Lecture 8），但我们可以设计一个 TM，利用 "Zig-zag" 策略来回扫描并标记 $a, b, c$，这台机器对于任何输入都能在有限步内给出 Accept 或 Reject 的结果。因此它是 Decidable 的。Q3. 停机问题 (Halting Problem)语言： $HALT = { \langle M, w \rangle \mid \text{TM } M \text{ 在输入 } w \text{ 上停机} }$ 分析： Lecture 12 明确指出了这是 "Undecidable" 的。 解答： B (Turing-recognizable but not decidable) 详解：Undecidable: 我们无法设计一个 TM 来判定任意 TM 是否停机（Lecture 12）。Recognizable: 我们可以设计一个通用图灵机（Universal TM）来模拟 $M$ 在 $w$ 上的运行。如果 $M$ 停机，模拟器就接受。但如果 $M$ 不停机，模拟器也会一直运行下去（无法拒绝）。因此它符合 Recognizable 的定义。Q4. 接受问题 (Acceptance Problem)语言： $ACCEPT = { \langle M, w \rangle \mid \text{TM } M \text{ 接受输入 } w }$ 分析： Lecture 12 证明了 $ACCEPT$ 是 Undecidable 的，并且通过归约（Reduction）证明了 $HALT$ 也不比它容易。 解答： B (Turing-recognizable but not decidable) 详解： 同样地，我们可以模拟 $M$。如果 $M$ 接受 $w$，我们就接受。如果 $M$ 拒绝或死循环，我们可能永远无法给出答案。因此它是 Recognizable 但不是 Decidable。Q5. 上下文无关语言 (CFL)语言： $L = { a^n b^n \mid n \ge 0 }$ 分析： 这是一个经典的 Context-Free Language。 解答： A (Turing-decidable) 详解： 所有的 CFL 都是 Decidable 的。我们可以将 PDA 转化为 TM，或者直接设计一个 TM（Assignment 3 Q1a 的简化版）来判定它。如果在选项中没有 "Context-Free"，则 "Turing-decidable" 是正确答案。Q6. 空语言检测 (Emptiness Problem)语言： $EMPTY = { \langle M \rangle \mid L(M) = \emptyset }$ (即 M 不接受任何字符串) 分析： Lecture 12 证明了 $EMPTY$ 是 Undecidable 的。 解答： C (Not Turing-recognizable) 详解：这是一个较难的考点。$EMPTY$ 是 Undecidable 的。它的补集 $\overline{EMPTY}$（即 $L(M) \neq \emptyset$）是 Recognizable 的（我们可以并行模拟 $M$ 在所有字符串上的运行，一旦有一个被接受，就接受）。根据定理：如果 $L$ 和 $\overline{L}$ 都是 Recognizable，则 $L$ 是 Decidable。因为 $EMPTY$ 不是 Decidable，而 $\overline{EMPTY}$ 是 Recognizable，所以 $EMPTY$ 本身必然是 Not Recognizable。Q7. 有限自动机判定语言： $L = { \langle D, w \rangle \mid D \text{ 是一个 DFA，且 } D \text{ 接受 } w }$ 分析： 这里的对象是 DFA，而不是 TM。 解答： A (Turing-decidable) 详解： Lecture 12 提到我们可以用 DFA 来构建 TM 的证明逻辑。因为 DFA 没有任何死循环（Loop）的可能，它总是在读取完输入后停在某个状态。我们可以编写一个 TM 来模拟这个 DFA，它一定会在有限步内结束并给出答案。因此是 Decidable。Q8. 语言的补集性质语言： $\overline{HALT}$ (即 ${ \langle M, w \rangle \mid M \text{ 在 } w \text{ 上死循环/不停机} }$) 分析： 考察 Recognizable 的封闭性。 解答： C (Not Turing-recognizable) 详解：已知 $HALT$ 是 Recognizable。已知 $HALT$ 是 Undecidable。如果 $\overline{HALT}$ 也是 Recognizable，那么 $HALT$ 就必须是 Decidable（定理：$L$ 和 $\bar{L}$ 都 RE $\implies$ $L$ is Recursive）。因为 $HALT$ 不 Decidable，所以 $\overline{HALT}$ 甚至连 Recognizable 都不是。Q9. 简单的数学运算语言： $L = { a \mid a \text{ 是二进制数且 } a \text{ 是 2 的幂} }$ 分析： 考察 Assignment 3 Q2 类型的计算能力。 解答： A (Turing-decidable) 详解： 虽然 Assignment 3 Q2 讨论的是 "Computation" (impure TM)，但判定一个数是否为 2 的幂（例如 $1, 10, 100...$）完全可以在有限步骤内完成（不断除以 2 或者检查二进制是否只有一个 1）。这属于 Decidable。Q10. Rice's Theorem (莱斯定理) 的应用语言： $L = { \langle M \rangle \mid L(M) \text{ 是一个正则语言} }$ 分析： 这是一个关于 TM 语言属性的判断。 解答： B (or C, depending on strictness, usually B is safe context, but strictly C/Undecidable is key) 注：在 Lecture 12 中提到了 Rice's Theorem。 详解： Rice's Theorem 指出，任何关于 TM 所识别语言的非平凡属性（Non-trivial property）都是 Undecidable 的。判断 $L(M)$ 是否 Regular 是一个非平凡属性。因此它肯定不是 A。通常这类属性也不具备 Recognizable 的特征（既难证明它 Regular，也难证明它不 Regular），但在简单的二元选择题逻辑中，首要判断是 Undecidable。 (修正：严格来说，正则性检测属于 $\Sigma_2$ 或 $\Pi_2$ 级别的复杂度，通常既不是 RE 也不是 co-RE，所以选 C 更准确。但如果题目只区分 Decidable vs Undecidable，则它是 Undecidable)。如果是标准本科考试，通常考查点在于它 "Undecidable"，若必须在 B/C 选，选 C 更稳妥，但核心是它违反了 Decidable。备考建议牢记层级： 看到 DFA/NFA/Regex $\rightarrow$ 选 Decidable；看到 PDA/CFG $\rightarrow$ 选 Decidable；看到 $a^n b^n c^n$ $\rightarrow$ 选 Decidable。区分 HALT/ACCEPT 和 EMPTY：涉及 "TM M 接受/停机" ($HALT, ACCEPT$) $\rightarrow$ 选 Recognizable (but not decidable)。涉及 "TM M 语言为空/语言等于..." ($EMPTY, EQUAL, ALL$) $\rightarrow$ 通常是 Not Recognizable (C)。Assignment 3 的启示： 只要是 Assignment 3 Q1 中让你画图设计的（如倍数关系、加法关系），全部都是 Decidable 的，因为题目要求 "Design a standard TM to decide"。
Lec 7 CFGPDA形式化定义：A pushdown automaton is a 6-tuple$$ (Q, \Sigma, \Gamma, \delta, q_0, F), where: $$$Q$ is the finite set of states;$\Sigma$ is the finite input alphabet;$\Gamma$ is the finite stack alphabet;$\delta : Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon} \rightarrow \mathcal{P}(Q \times \Gamma_{\varepsilon})$ is the transition function;$q_0 \in Q$ is the initial state; and$F \subseteq Q$ is the set of final states.Problem 1： 设计 PDA一些比较基本的经验和操作。对于栈操作来说，比如是 $op_a \to op_b$ 代表当前栈顶是 $op_a$，将栈顶变为 $op_b$。那么这个意思就比较丰富了：若形如：$a \to b$，其中 $a, b \in L$（就是说现在在栈里面要匹配的字符属于当前language的字符集），那么实际上的意思是 pop(a) + push(b)，相当于是用 $b$ 替换当前栈顶的元素 $a$。若形如：$\epsilon \to b$， 意思是 push(b)。因为 $\epsilon$ 是要匹配一个空。若形如：$b \to \epsilon$，意思是 pop(b)，其中 $b$ 一定是栈顶元素！！！！。要时刻记得 $op_a$ 是栈顶元素。下面是一些常见的设计PDA需要的栈操作：$\epsilon \to \$$ 一定要加！： 这一步是为了让一个空的栈有一个”空“的标记 （即 $\$$ ）$\epsilon \to \epsilon$ ：相当于是我们不对栈进行任何操作 （见 A2-Q1-a）。一个比较好用的东西: $\epsilon, \epsilon \to \epsilon$ 可以用来处理 $n, m = 0$ 的 case。e.g.1$L = a^nb^{n+m}c^m$这道题可以学习的点：注意到其实我们设计的都是NPDA，那么对于一个 $w \in L$ （属于当前language的串），我们只要 PDA 存在一个路径让他到达 Final state 即可。我们这里通过 $a, b, c$ 的标志来区分数量，中间用 $\epsilon, \epsilon \to \epsilon$ 来转移到下一个计数 state。e.g.2$L = a^n b^{2n}$这道题可以学习的点：这里需要处理的主要是 $n$ 个 a 和 $2n$ 个 b 的倍数关系。难点在于我们需要设计使得每读进来一个 $a$ 可以往栈里面 push 两个 $a$。实现可以参考答案。e.g.3$L = a^nb^{m}c^{l}, n \geq m | n \geq l$答案错了。权威这一块，拿捏的死死的。一些小细节：最后进入 Final state 的时候，由于可能 $n > m | l$ ，那么 stack 里面还有剩余的 $a$，设计转移的时候要注意。此外就是一个标准的双分支结构，用 $\epsilon, \epsilon \to \epsilon$ 转移就好。Problem 2：PDA 和 CFG 的互相转换感觉比较能出的实际上是CFG 2 PDA比较要注意的实际上是：Type做法Terminals1. 先从 $NT \to T$ （从变量推导出 Terminals）；再加入：$T \to \epsilon$ （处理完毕，出栈）; 2. 对于每一个 Terminals，都要有出栈。Non-Terminals（Recursion)注意一定是从右到左；比如说有：$S \to aSb$，那么要有转移 $\epsilon, S \to b\epsilon \to S\epsilon \to a$最后一定要加入 $\epsilon, \$ \to \epsilon$ 到 final state 的转移。放个作业题Problem 3: 证明 CFG 是 ambiguous 的Compiler 题型，做法也很简单：找一个属于这个CFG的串，画出两棵不同的 parsing tree 即可CFG Properties感觉不是很重要，一笔带过吧满足的性质：Union: $L_1, L_2$ 都是 CFG $\Rightarrow$ $L_1 \cup L_2$ 也是 CFGConcat: $L_1 \cdot L_2$ 也是 CFGStar与 regular language 的交：$L_R \cup L_C$ 也是 CFG不满足的性质：ComplementPumping Lemma感觉其实会简单一些，主要是由于 CFL 的构造会复杂一些，所以枚举的case必须要覆盖全面。其他的倒是比较简单。Lec 9 TMA Turing Machine is a 7-tuple$$ M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) $$$Q$ is the set of states;$\Sigma$ is the input alphabet$$ \sqcup \notin \Sigma $$$\Gamma$ is the tape alphabet$$ \sqcup \in \Gamma \quad \text{and} \quad \Sigma \subseteq \Gamma $$The transition function is$$ \delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\} $$$q_0 \in Q$ is the start state;$q_{\text{accept}} \in Q$ is the accept state; and$q_{\text{reject}} \in Q$ is the reject state, where$$ q_{\text{reject}} \neq q_{\text{accept}} $$感觉一些比较容易忽略的点：TM rejects a string $w$ ifit halts on the input $w$ at a reject state orit has no where to move in the middle of the processTuring-decideable: A language $L$ is recursive (or Turing-decidable) if there is a TM $M$ such that$\forall w \in L$, $M$ accpets $w$;$\forall w \not \in L$, M rejects $w$Turing-recognizable: A language $L$ is recursively enumerable (or Turing-recognizable) if there is a TM $M$ such that:$\forall w \in L$, $M$ accpets $w$;$\forall w \in L$, $M$ rejects $w$ or $M$ loops foreverProblem 4a: 设计 TM (Decider)一些比较好的设计规范：要对不同字符操作的时候最好退回到纸带起点可以用不同的字母表示不同的含义，比如说 (a,b) 配对用 x，(b,c) 配对用 y 这样。类型 1: 数量倍数关系判定对于 $L_1 = \{a^nb^{m} | n = 2m, n \geq 0, m \geq 0\}$ 设计思路：参考 A3-Q1 中的 $a^ib^jc^k$策略：每次划掉一个 a，然后去找一个 b，退回到纸带最左边，然后再划掉一个 a，最后又退回到最左边。如果 a 找不到了，就可以 accept 了<?xml version="1.0" encoding="UTF-8"?> acc x → x, R □ → □, R a → x, R a → a, R x → x, R b → x, L a → a, L x → x, L □ → □, R x → x, R a → x, R x → x, L □ → □, R 类型 2: 逆序结构判定（回文）对于 $L_2 = \{w \in \{0, 1\}^{*} | w = w^{R } \}$设计思路：读取最左边的字符，记住它是 0 还是 1（通过状态来记忆，相当于走到不同状态分支）。标记然后移动到最右边未被标记的字符，检查其是否与左边的一致。如果一致，删掉右边这个字符并移回最左边；注意到奇数长度的串需要特别判断：如果从右边往左边扫的时候遇到空格了，可以直接进入 acc 状态<?xml version="1.0" standalone="no"?> acc x \to x, R space \to space, R 0 \to x, R 1 \to x, R space \to space, R space \to space, R 0 \to x, L x \to x, L x \to x, L 1 \to x, L x \to x, L / 0 \to 0 L / 1 \to 1, L x \to x, L / 0 \to 0, L / 1 \to 1, L space \to space, R space \to space, R space \to space, R space \to space, R 类型 3：加法对于 $L_3 = \{a^ib^jc^k | i + k = j, i, j, k \geq 1\}$ 设计思路：可以先匹配 a 和 b。每次划掉一个 a，对应划掉一个 b。当 a 全部划掉后，继续匹配 c 和剩余的 b。如果 c 耗尽时 b 也刚好耗尽，则接受。类型 4: 幂次判定对于 $L_4 = \{a^n | n = 2^k, k \geq 0\}$ 设计思路：通过重复“除以 2”的过程。从左到右扫描，每隔一个 a 划掉一个 a（保留一半）。如果扫描过程中发现总数是奇数（且总数大于1），则拒绝。扫描完一轮后，将读写头移回开头，重复步骤 1。如果最后只剩下一个 a，则接受。Problem 4b: 设计 TM (Computation)由于TM会在tape上写写画画（称之为 side effect），故可以用来做一些 computation 任务类型 1: 前驱后继作业已经设计过一个前驱了，现在来考虑一下后继。主要的问题都是：低位在右边考虑进位设计思路：设计提示：◦ 这是 Q2x 的逆运算。你需要先将读写头移动到最右端的 LSB。◦ 从右向左扫描：如果你看到 1，将其变为 0 并继续向左进位（Carry）；如果你看到 0，将其变为 1 并停止（进入 Halt 状态）。◦ 边界情况： 如果移动到最左边还是进位（例如 11 + 1），你需要处理溢出，可能需要整体右移数据或在左边插入一个 1。<?xml version="1.0" standalone="no"?> acc any \to any, R space \to space, L 1 \to 0, L 0 \to 1, L / space \to 1, L 类型 2: 一进制转二进制 (Unary to Binary Conversion)双带（2-tape）TM设计思路：这道题可以直接复用 Q1 的逻辑作为子程序（Subroutine）。◦ 策略： 纸带 2 作为一个计数器，初始当作 0。读写头在纸带 1 上每读到一个 x，就在纸带 2 上执行一次“加 1”操作（调用 Q1 的逻辑）。◦ 当纸带 1 的 x 读完时，纸带 2 上的内容即为结果。其他的我感觉考试也不可能出太过分了，据说去年出了一个去模，我感觉思路应该类似于辗转相除法。如果出了我就认账。
Beginner1. $\{0^n1^n| n \geq 0\}$Suppose $L$ is regularExists a "pumping constant" $p$ for $L$重点技巧：不管你这个 $p$ 是啥，直接 substitute 到 n 上。也就是变成 $0^p1^p$Choose a string $w = 0^p1^p$重点技巧：然后找一个拆分这个 string 变成 $xyz$ 的方式，满足（本来是有三个条件的，但是你最后一个条件是用来引起反例的，因此这里只需要考虑前两个条件）$|xy| \leq p$$|y| \geq 1$这里的话，假设：$x = 0^{\alpha}, y = 0^{\beta}$, 其中 $a \geq 0, \beta \geq 1$ 因为上面的条件2要求了 $|y| \geq 1$，然后当然满足：$\alpha + \beta = p$。这样的话有：$z = 0^{p - (\alpha + \beta) 1^p}$现在要满足 Pumping Lemma，写出来 $xy^iz = 0^{\alpha}0^{\beta}0^{p - (\alpha + \beta) }1^p = 0^{p + (i-1)\beta}1^p$ 然后要让当前构造的 $w \not\in L$ 的话， 只要是 $p + (i - 1)\beta \not = p$ 即可，推出来 $i \neq 1$。那么简单选一个 $i = 2$ 就可以让 $w \not\in L$。因此，$L$ 不是 regular language。2. $\{w \in \{0,1\}^*|w \text{ has the same number of 0's and 1's}\}$法一因为 regex 在 intersection 是 close 的，所以因为 $\{0^n1^n| n \geq 0\}$ 是 regular 的而其又属于当前这个 language，所以当前 language 是 regular 的。法二说白了，其实可以假设一个长度为 $p$ 的排列，使得所有为 $0$ 的位置都在前面，为 $1$ 的位置都在后面。因为这样的排列一定存在，所以该langauge自然退化到$\{0^n1^n| n \geq 0\}$ 这个langauge 的情形。3. $\{w \in \{0,1\}^*|w \text{ has the more number of 1's than 1's}\}$还是按照 2. 的法二，因为我们存在一个排列重排 $0,1$ 的顺序，那么我们只要证明 $L' = \{0^n1^{n+1}| n \geq 0\}$ 不是 regular 就行了。这里简单地取 $n + 1$ 就可以保证 1 比 0 多了嘛。然后还是 1. 的过程，最后是得到了 $\beta(i-1) < 1 \Leftrightarrow (i-1) < \frac{1}{\beta} $ ，因为 $i \in \mathbb{N} \land i \geq 0$ 又有 $\beta \geq 1$，所以 $i = 2$。套进去效果类似。不写了。4. $\{0^{2n} 1^n | n \geq 0\}$类似于 1. ，如果按照 1 的分解最后是 $i \not = 1$，选个 $i = 2$ 即可。5. $\{0^{n}1 0^n | n \geq 0\}$类似于 1. ，如果按照 1 的分解最后是 $i \not = 1$，选个 $i = 2$ 即可。总结1：对于 $\{0^m1^n0^{f(m, n)} | m, n \geq 0 \}$以上所有都可以泛化成该形式，比如可以定义: $f(m, n) = m + n$ 或者 $f(m, n) = m \times n $。 对于不钦定顺序的，可以直接给一个排列 $p$ 使其有序，然后令 $f(m, n) = 0$ 即可（当然也可以是别的常数）6. $\{0^n1^m| n \neq m\}$重点技巧：p! 方法 (相当于不管我们要配多少使得 $n = m$，这个差值（体现在指数上就是加减法了）都被阶乘包含了)选择：$w = 0^{p}1^{p + p!}$令：$x = 0^{\alpha}, y = 0^{\beta}, z = 0^{p - \alpha - \beta}1^{p + p!}$，其中注意：$\beta \in [0, p]$ 那么写成：$xy^iz$ 发现 $(i - 1) \beta \neq p!$ ，然后因为 $\beta | p!$ ，所以 $i \neq \frac{p!}{\beta} + 1$，那么选择这个 $i = \frac{p!}{\beta} + 1$ 即可。7. $\{0^n1^m | n < 3m\}$不写了，唯一需要注意的是 $|xy| \leq p$Regular8. $\{0^{n^2} | n \geq 0\}$取 $t$ 使 $2t+1>p$（例如直接取 $t=p$）。令$$ w=0^{t^2}\in L. $$对 任意 分解 $w=xyz$ 且 $|xy|\le p,\ |y|>0$，因为全是 0，所以设 $y=0^k$，其中 $1\le k\le p$。考虑泵一次：$i=2$。此时$$ |xy^2z|=t^2+k. $$又因为 $1\le k\le p<2t+1$，所以$$ t^2< t^2+k \le t^2+p < t^2+(2t+1)=(t+1)^2. $$因此 $|xy^2z|$ 的长度严格处在两个相邻平方数 $t^2$ 与 $(t+1)^2$ 之间，不可能是完全平方数，故 $xy^2z\notin L$。这与泵引理“对所有 $i\ge 0$ 仍在 $L$”矛盾。于是 $L$ 非正则，证毕。（同理也可取 $i=0$ 得到 $t^2-k$ 落在 $(t-1)^2$ 与 $t^2$ 之间，依然不为平方数。）9. Power of 2例如：$\{0^{2^n} | n \geq 0\}$设 Pumping Length $p$，选择 $w = 0^{2^p}$。 令 $x = 0^{\alpha}, y = 0^{\beta}, z = \text{rest}$若 $xy^iz \in L$ ，$xy^iz = 0^{\alpha}0^{i\beta}0^{2^p - \alpha - \beta} = 0^{2p + (i - 1)\beta}$， 则：$2^{p} + (i - 1)\beta$ 是 2 的幂令 $i = 2$ ，则 $2^p <2^p + \beta \leq 2^p + p < 2^{p} + 2^{p} = 2^{p+1}$ ，因为 $\beta \geq 1 \land \beta \leq p$10. Primes例如：$\{0^k | k \text{ is a prime}\}$假设我们有 $w = 0^{r}$，r 是 pumping lenth p 的 $p+2$ 的下一个质数拆分 $xy^iz \not\in L$，有： $|xy^iz| = |xz| + i|y|$ ，想要的形式是：$(|y| + 1)|xz|$ 当 $i = |xz|$ 的时候取到。这样一来因为 $|xy| \leq p, |w| \geq p + 2 \Rightarrow |z| \geq 2$ ，所以 $|xz| \geq 2$。 又有 $(|y| + 1) \geq 2 $，所以这必然是一个合数。11. $\{0^m1^n | \frac{m}{n} \text{is an interger}\}$选择 $w = 0^{4p}1^{2p}$最后分出来条件是：$\frac{4p + (i - 1)\beta}{2p}$ ， 选一个 $i = 2$ ，那么 $\beta = 2p$ 才行。但是 $\beta \in [1, p]$12. $\{w \in \{0, 1\}^{*} | \text{00 or 11 appear same \# of times in w}\}$懒得写了13. $\{w \in \{0,1\}^* | w \text{ is not a palindrome}\}$选择 $w = 0^p110^{p + p!}$$x = 0^{\alpha}, y = 0^{\beta}, z = 0^{p - \alpha - \beta}110^{p+ p !}$所以有 $xy^iz = 0^{p + (i - 1)\beta}110^{p + p !}$然后就是套路了
原始问题（Primal Problem）我们从 SVM 的优化目标开始：$$ \min_{w, b} \ \frac{1}{2}\|w\|^2 $$约束条件：$$ y_i(w^T x_i + b) \ge 1, \quad i=1,\dots,m $$找到最大间隔的超平面（即使 $\|w\|$ 尽量小），同时保证每个样本被正确分类。拉格朗日乘子（Lagrange Multipliers）当约束条件存在时，我们不能直接最小化目标函数。于是引入拉格朗日乘子 $\alpha_i \ge 0$，建立拉格朗日函数：$$ \mathcal{L}(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^{m} \alpha_i [y_i(w^T x_i + b) - 1] $$每个 $\alpha_i$ 对应一个约束条件。它的含义是：如果某个样本点违反了约束（即离间隔太近或分错），那它的 $\alpha_i$ 就会“发力”惩罚。然后：原始约束：$$y_i(w^T x_i + b) - 1 \ge 0$$乘子非负：$$\alpha_i \ge 0$$互补松弛性（Complementary Slackness）：$$\alpha_i [y_i(w^T x_i + b) - 1] = 0$$梯度为零（Stationarity）：对 $w$ 和 $b$ 求偏导：$$ \frac{\partial \mathcal{L}}{\partial w} = 0, \quad \frac{\partial \mathcal{L}}{\partial b} = 0 $$求导并消去 $w$ 和 $b$1️⃣ 对 $w$ 求偏导：$$ \frac{\partial \mathcal{L}}{\partial w} = w - \sum_i \alpha_i y_i x_i = 0 \Rightarrow w = \sum_i \alpha_i y_i x_i $$2️⃣ 对 $b$ 求偏导：$$ \frac{\partial \mathcal{L}}{\partial b} = -\sum_i \alpha_i y_i = 0 \Rightarrow \sum_i \alpha_i y_i = 0 $$带回去得到对偶问题（Dual Problem）把上面的 $w$ 代入原式中，得到仅关于 $\alpha$ 的优化：$$ \mathcal{L}(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i[y_i(w^T x_i + b) - 1] $$化简后得到对偶形式：$$ \boxed{ \max_{\alpha} \ W(\alpha) = \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i \alpha_j y_i y_j (x_i^T x_j) } $$约束：$$ \sum_i \alpha_i y_i = 0, \quad \alpha_i \ge 0 $$为什么要用对偶形式？对偶的好处非常关键：消掉了 $w, b$，只剩下 $\alpha$；训练样本只以内积 $x_i^T x_j$ 的形式出现，⇒ 可以使用 核函数（Kernel Trick） 来扩展到高维空间；对偶问题是一个凸二次规划问题（Quadratic Programming），有唯一全局最优解。求得最优 $\alpha$ 后恢复分类器当我们得到最优 $\alpha^*$ 后：$$ w^* = \sum_i \alpha_i^* y_i x_i $$分类函数为：$$ f(x) = \text{sign}(w^{*T}x + b^*) $$其中 $b^*$ 可通过任意一个支持向量（即 $0 < \alpha_i < C$ 的样本）求出：$$ b^* = y_i - \sum_j \alpha_j^* y_j (x_j^T x_i) $$🧩 八、支持向量的意义若 $\alpha_i = 0$：该样本不影响边界（离得远）若 $0 < \alpha_i < C$：该样本恰在边界上，是支持向量若 $\alpha_i = C$：该样本被误分类或在边界内侧✅ 九、总结成一句话：SVM 的对偶问题通过拉格朗日乘子法把约束优化转化为仅依赖 $\alpha$ 的二次规划问题，既保证了凸性（一定能找到全局最优），又能自然地引入核函数扩展非线性问题。
TOC Review 1: From Math Preperation to Pumping Lemma
Lec 02: Math好像是一些概念，先放点重要的Constructive Proof规范步骤：Used to prove a predicate with existential quantifiers, i.e. $\exist x, P(x)$First, construct an object $x$Second, prove $P(x)$ is trueContradiction Proof懒得写了，大概就是：写一个命题 $\exist x, P(x)$然后给出逆否命题 $\exist \neg x$，并且证明 $P(\neg x)$ 为真自然得到 $x$ 为假Induction要证明 $\forall x \in \mathbb{N}, P(x)$，一句话：一般归纳法只要 $k \to k+1$ 就行，但是 strong induction 要求 $1 \land 2 \land 3 \land \dots \land k \to k + 1$### Cardinality （范数）首先抄一下定义： 证明 Countable/Uncountable 的方法主要有两个方法Construct a bijection: $f: A \to \mathbb{N}$ 核心在于 Bijection可以是一个函数，比如你要弄到 $(0,1)$ 就可以用 sigmoid 或者其他 activation function；你要证明 $[0, 10]$ 是 uncountable 的话，即可以说明其 subset 不可数，亦可以写一个 $f(x) = \frac{x}{10}$ 之类的也可以是一个可以 map to $\mathbb{N}$ 的遍历顺序如果是一个形如 $(x_i, y_i)$ 这样的二元组要给一个遍历顺序的话，可以构造 zig-zag否则的话就需要用 Diagonal Proof 了，说实话这个比较唐。相当于你要给出一个遍历表，然后想办法构造一个不存在于表中的元素来说明你要证明的集合 uncountable.Lec 03/04: (Non-)Finite Automata定义：需要包含一下元素5 tuple $(Q, \Sigma, \delta, q_0, F)$ where:$Q$ is a finite set of states$\Sigma$ is a finite set, called the alphabet (set of input symbols)$\delta$: $Q \times \Sigma \to Q$ is the transition function$q_0 \in Q$ is the start (initial) state$F \subseteq Q$ is the set of final (accept) states做题1：设计 DFA / NFA类型1: 数量型这类是比较简单的题型。Solution: 设计足够的转移边来满足数量匹配即可。比如说：类型2: 后缀（子串）匹配型说白了，就是 KMP。想一下，KMP 做的事情是匹配一个真前缀和真后缀是吧。那么假设我们已经有了一个匹配所有合法串的自动机，那么现在这个自动机要判定一个新的串是否合法，可以把 initial state 当作构造串的分隔符（也就是吧新输入的串当作后缀，自动机里的串当作前缀）。那么这个自动机的状态就是要设计成匹配所有长度的后缀的状态。感觉说的比较抽象。下面来点例子：类型3: 匹配带条件后缀（子串）型一个例子：{w|w contains no runs of length less than four}. A run in a string is a substring of length at least one and consisting entirely of the same symbol. For example, abbbaab has four runs: a, bbb, aa, b.做这个不要慌，先化简一下问题。假如我们现在要搞一个DFA来匹配不包含长度 $\leq 4$ 的全由 $a$ 组成的子串的串。那么很显然构造的DFA至少要有四条 $a$ 的转移边：<?xml version="1.0" standalone="no"?> a a a a 然后你只要没有走完这四条边的 input 都是非法的，也就是出现 $b$ 就得到 dead state，遂：<?xml version="1.0" standalone="no"?> <?xml version="1.0" standalone="no"?> a a a a b b b a,b 然后考虑怎么设置 Final state。首先要注意，实际上我们的条件是两个条件的联立：长度 $\geq 4$不能存在长度 $< 4$ 的substring因此：<?xml version="1.0" standalone="no"?> a a a a b b b a,b a b 因此，那么这个题只要对称地画出另外一半即可。<?xml version="1.0" standalone="no"?> a a a a b b b a,b a b b b b b b a a a a 设计 NFA说实话，设计 NFA 应该是一个不会考的题型。因为合法的NFA应该是不唯一的。只要注意 NFA 的 transition function 是 partial function，然后也不需要考虑所谓的 input 顺序，因为，input string 只要在 NFA 找到一条路径到 final states 就行。简单给一个例子吧：设计一个 NFA 接受：The language $1^{*}(001^+)^*$ with three states<?xml version="1.0" standalone="no"?> 0 0 1 1 Union and Concatenation of NFA比较好说：Concatenation 就是把 M1 和 M2 用一个 $\epsilon$ transition 连起来即可Union 就是把 M1 和 M2 的 initial states，用 $\epsilon$ transition 连到一个新的 state 即可。做题2: NFA2DFA一句话：找闭包然后连接首先你要找到 Initial state 的 $\epsilon-$closure，然后这些状态都是要加入DFA的initial state作为新的 DFA 的initial state的然后枚举每一条出边，先记下来到达的集合，再计算到达集合的 $\epsilon-$closure。检查这个状态是否已经存在，如果不存在就建立一个新状态然后连接，否则直接连接。例外：加入 NFA 没有某一个符号的出边，那么在新的 DFA 中要建立一个 dead state 然后死循环比如说图中的 $\{q_3\}$ 由于没有 $a$ 的出边，在新的 DFA 中就要连接一个 dead state 并且设置死循环做题3：多个 DFA 的叉积本质上，多个 DFA 的叉积等价于对 state sets 做叉积 + 对 transition function 做叉积。在此给出一个比较方便做题的方法：Lec05: Regular LanguageTo study the properties of regular languages, we define the regular operations.DefinitionLet $ A $ and $ B $ be languages.Union: $ A \cup B = \{ x \mid x \in A \text{ or } x \in B \} $Concatenation: $ A \circ B = \{ xy \mid x \in A \text{ and } y \in B \} $Star: $ A^* = \{ x_1 x_2 \cdots x_k \mid k \geq 0 \text{ and each } x_i \in A \} $Note: each $ x_i $ is a string in the language $ A $. And $ x_1 x_2 \cdots x_k $ is the concatenation of $ x_1, x_2, $ until $ x_k $. Equivalently, $ A^* = A^0 \cup A^1 \cup A^2 \cup \cdots $Regular Expression当时上课的时候没怎么认真听，觉得是个简单内容。后来发现这个东西会在 CFG 中间出现。遂导致掉线。不过本来CFG那节课我也没去，忘了是什么原因了。正则语言可以递归构造。正则表达式描述了正则语言中字符串的 common 模式（与机器无关）。定义（递归定义）如果 $ R $ 满足以下条件，则 $ R $ 是字母表 $ \Sigma $ 上的正则表达式：基础情况$ a $，其中 $ a \in \Sigma $，$ \varepsilon $，或$ \emptyset $递归情况$ (R_1 \cup R_2) $，其中 $ R_1 $ 和 $ R_2 $ 是正则表达式，$ (R_1 \circ R_2) $，其中 $ R_1 $ 和 $ R_2 $ 是正则表达式，或$ (R_1^*) $，其中 $ R_1 $ 是正则表达式。Languages Defined by Regular Expression一种 language 的 regular expression 展示了该 language 中所有string的共同模式。因此，定义设 $ R $ 是一个正则表达式。由 $ R $ 定义的语言 $ L(R) $ 为：基础情况：$ L(\emptyset) = \emptyset $$ L(\varepsilon) = \{ \varepsilon \} $$ \forall a \in \Sigma $，$ L(a) = \{ a \} $递归情况：如果 $ R = R_1 \cup R_2 $，那么 $ L(R_1 \cup R_2) = L(R_1) \cup L(R_2) $如果 $ R = R_1 \circ R_2 $，那么 $ L(R_1 \circ R_2) = L(R_1) \circ L(R_2) $如果 $ R = R_1^* $，那么 $ L(R_1^*) = (L(R_1))^* $做题4: 证明 Languages 的等价性（or 不等价）挖坑待填，其实是不会做题6: NFA2Regular Expression说白了，课件给的代码就是Floyd。相当于你的转移有两种：$i \to k \to j$$k \to k$ 走自环所以，要消除 $k$ 这个中间点，连成 $i \to k* \to j$ 即可。实操一个比较好的办法是弄一个“超级源点”和“超级汇点” （当然不是网络流），然后每次记录 in 和 out （相当于枚举 $k$）。见 assignment 1 Q5。这里给出两个更难一点的例子Example 1<?xml version="1.0" standalone="no"?> <?xml version="1.0" standalone="no"?> <?xml version="1.0" standalone="no"?> 1 2 s 1 2 t s 1 t b b a a a b b a a | ba*b ba* 比如这里的步骤是消除 2，那么画表（入度和出度）：inOutEdge1t(1 -> t): ba* 1(1 -> 1): $a \cup ba^*b$Example 2<?xml version="1.0" standalone="no"?> 1 2 3 1 2 3 t1 t2 1 3 t1 t2 a,b a b b a a a,b b b a (a|b)a*b a ba*b 最后的结果显然是一个 union 形式的 NFALec 06: Pumping Lemma （包含 Context-Free Language 版本）尝试策清楚，不一定对。不过一定会保证做题是对的。正确性证明<?xml version="1.0" standalone="no"?> x y z 抄一下定义：If $A$ is a regular language, then there is a positive constant $p$ such that every string $w \in A$ of length at least $p$ can be written as $w = xyz$ satisfying the following conditions:$\forall i \geq 0, xy^iz \in A$$|y| > 0$ and$|xy| \leq p$其中 $p$ 是 pumping length想一下为什么是对的。首先 regular language 一定是一个可以被 DFA 或者 NFA 识别的 language。所以我们对于这个 $A$ 是一定可以构造一个 DFA/NFA 来识别的。为了方便，以下讨论 DFA。假设 $n$ 是这个 DFA 的 state 的数量假设 $w \in L$ 并且 $|w| \geq n$在这个自动机读入 $w$ 的前 $n$ 个字符后一定有一个状态达到过两次​ 感觉这里是要详细说明一下的，如果不搞懂的话后面非常不好懂。$|w| = 0$ 的情形先不讨论了，直接看 $|w| \geq 1$所以就是说，必然存在一个 state 被重复走了。对应上面的 $y$做题 5: 证明一个 Language 不是 regular language反证法证明 ：套路大概如下：假设要证明的 language 是 regular language$n$ 是未知的$w$ 可以在满足 $w \in L$ 和 $|w| \geq n$ 的条件下自由选择$x, y, z$ 也是未知的找到一个 $k$ 使得 $xy^kz \not\in L$还是非常抽象，来看一些例子。见另外一个文档。证明 Language type 方法的总结给定一个 language $L$To prove $L$ is regularconstruct a DFA/NFATo prove $L$ is not regularUse pumping lemma (For Reg)To prove $L$ is CFGconstruct PDATo prove $L$ is not CFGPumping lemma (For CF)Lec 8: P? $L = \{a^nb^nc^n| n \geq 0\}$ is not CF
接口参数在 Aggregator.py 中：global_merging=True：是否在“global attention”阶段允许执行合并（默认允许）merging=0：在第几个注意力 block 之后开始执行合并实际用到 token merging 相关逻辑的地方只在于 global attention 中。相关逻辑调用在 layers/attention.py 中，部分函数实现在 merging/merge.py 中attention.py他这里还实现了分 chunk 计算。应该也有一部分对于最终提速的贡献。当然他论文是一点没说啊，但既然他这样干了，我们也没必要改回去吃这个哑巴亏。具体实现流程：调用 token_merge_bipartite2d 返回一对 (merge, unmerge) 函数用 merge() 对 q、k、v 的“token 维度”进行merging（将一部分 src token 聚合到 dst token），得到更短的 $N_m$用mering后的 q,k,v 做 scaled dot-product attention注意力输出后，再调用 unmerge() 把输出恢复到合并前的原始顺序与长度if global_merging is not None and global_merging in merge_num: generator = torch.Generator(device=x.device) generator.manual_seed(33) merge_ratio = 0.9 r = int(x.shape[1] * merge_ratio) m, u = token_merge_bipartite2d( x, self.patch_width, self.patch_height, 2, 2, r, False, generator, enable_protection=True, ) m_a, u_a = (m, u) B_q, H_q, N_q, D_q = q.shape q_merge_in = q.permute(0, 2, 1, 3).reshape(B_q, N_q, H_q * D_q) k_merge_in = k.permute(0, 2, 1, 3).reshape(B_q, N_q, H_q * D_q) v_merge_in = v.permute(0, 2, 1, 3).reshape(B_q, N_q, H_q * D_q) q_out, k_out, v_out = m_a( q_merge_in, mode="mean", extra_tensors=k_merge_in, extra_tensors_2=v_merge_in, ) del q_merge_in, k_merge_in, v_merge_in N_m = q_out.shape[1] q = q_out.reshape(B_q, N_m, H_q, D_q).permute(0, 2, 1, 3) k = k_out.reshape(B_q, N_m, H_q, D_q).permute(0, 2, 1, 3) v = v_out.reshape(B_q, N_m, H_q, D_q).permute(0, 2, 1, 3) del q_out, k_out, v_out N = N_mtoken_merge_barpartite()函数声明将标记分为源（src）组和目标（dst）组，并从源组向目标组合并r个标记。目标标记通过从每个（sx，sy）区域随机选择一个标记来选择。可选地，根据重要性得分保护顶部10%的标记不被合并。 参数： - metric [B, N, C]：用于相似度计算的张量，B = 批量大小，N = 标记数量，C = 特征维度 - w：图像宽度的标记数 - h：图像高度的标记数 - sx：目标在x维度的步长，必须能均匀整除w - sy：目标在y维度的步长，必须能均匀整除h - r：通过合并要移除的标记数量 - no_rand：如果为True，禁用随机性（仅使用左上角标记） - generator：如果no_rand为False且不为None时的随机数生成器 - enable_protection：如果为True，启用重要性保护特征 返回： - (merge, unmerge)：两个函数，分别用于合并标记和恢复合并前状态Function call:m, u = token_merge_bipartite2d( x, // tokens self.patch_width, self.patch_height, 2, //sx 2, //sy r, // r = int(x.shape[1] * merge_ratio) 即要“移除”并合并的 src token 数约占 90% False, generator, enable_protection=True, //实现上会均匀抽取 N 的 10% 的 token 索引为 protected_indices )具体实现论文中提到固定 stride=10%N 作为 protected tokens（保持 spatial consistency），首先实现于：# 是否启用保护：当前实现为均匀抽样 N 的 10% 作为 protected 索引，防止被合并 if enable_protection: num_protected = int(N * 0.1) step = max(1, N // num_protected) # 均匀步进采样出受保护的索引列表 protected_indices = torch.arange(0, N, step, device=metric.device)[ :num_protected ]接下来开始划分 dst 和 src token、区分 frame 0 和 其他 frame# idx_buffer_seq：长度为 N 的标记向量；-1 表示 dst，0 表示 src idx_buffer_seq = torch.zeros(N, device=metric.device, dtype=torch.int64) # hsy、wsx：分别是以 sy、sx 网格步幅划分后，每张图上的网格块数量（高、宽方向） hsy, wsx = h // sy, w // sx # Number of blocks within each image # 第一张图像（含 5 个特殊 token + 所有 patch）全部作为 dst 聚合目标 if num_imgs > 0: idx_buffer_seq[:tokens_per_img] = -1 # 因为 frame 0 的 tokens (including cam/reg) 都在 [0:tokens_per_img] # 其他 Frame： # 1) 每张图的 5 个特殊 token 标记为 dst # 2) 在每个 (sy, sx) 网格中选择 1 个 token 为 dst（其余默认 src） if num_imgs > 1: # 计算所有其它图像的 5 个特殊 token 的全局索引，并标记为 dst cls_indices = ( torch.arange(1, num_imgs, device=metric.device) * tokens_per_img ) cls_indices = cls_indices[:, None] + torch.arange(5, device=metric.device) idx_buffer_seq[cls_indices.flatten()] = -1 # 有效网格尺寸（避免越界）：当 h 或 w 不能被 sy/sx 完整整除时，按可覆盖区域截断 effective_h = min(hsy * sy, h) effective_w = min(wsx * sx, w) effective_grid_size = effective_h * effective_w if no_rand: # 非随机：每个网格只选择固定（左上）位置为 dst。因为没有调用，遂掠过 else: # 随机：在每个 (sy, sx) 子网格里随机选一个索引作为 dst total_other_imgs = num_imgs - 1 all_rand_idx = torch.randint( sy * sx, size=(total_other_imgs, hsy, wsx), device=metric.device, generator=generator, ) # scatter_src 为 -1，用于把被选中的网格位置标记为 dst scatter_src = -torch.ones( total_other_imgs, hsy, wsx, device=metric.device, dtype=torch.int64 ) # idx_buffer_batch 的最后一维大小为 sy*sx，代表每个网格内的所有位置； # 先在该维度上做 scatter，把随机选中的位置置为 -1（dst），其余保持 0（src） idx_buffer_batch = torch.zeros( total_other_imgs, hsy, wsx, sy * sx, device=metric.device, dtype=torch.int64, ) idx_buffer_batch.scatter_( dim=3, index=all_rand_idx.unsqueeze(-1), src=scatter_src.unsqueeze(-1), ) # 将每个网格的 sy*sx 展开成二维平面，并按 (H, W) 的顺序重排（transpose + reshape） idx_buffer_batch = ( idx_buffer_batch.view(total_other_imgs, hsy, wsx, sy, sx) .transpose(2, 3) .reshape(total_other_imgs, hsy * sy, wsx * sx) ) # 将每张图对应的二维标记平面（-1 或 0）批量写入到全局 idx_buffer_seq 中对应的 patch 区域 # 注意 grid_start 跳过了前 5 个特殊 token for i in range(total_other_imgs): img_idx = i + 1 grid_start = img_idx * tokens_per_img + 5 flat_view = idx_buffer_batch[ i, :effective_h, :effective_w ].flatten() idx_buffer_seq[grid_start : grid_start + effective_grid_size] = ( flat_view )说结论：如果要修改的话，可以仿照这一段的写法。可以是实现一个函数返回一个 indicies ，表示这些位置都需要设成 dst tokens。即现在代码的：scatter_src最后这一部分简单说一下几个不太会用的点：_scatter : 然后过度一下，拼接一下 dst token 和 src token，并且判断是否需要使用 protection 机制。最后记录 dst/src token 分别的数量。# 通过 argsort 将 -1（dst）排在前面，0（src）排在后面，得到两侧的索引集合 rand_idx = idx_buffer_seq.reshape(1, -1, 1).argsort(dim=1) num_dst_orig = int((idx_buffer_seq == -1).sum()) # 原始 src 与 dst 的索引切分（形状 [1, K, 1]） a_idx_orig = rand_idx[:, num_dst_orig:, :] b_idx_orig = rand_idx[:, :num_dst_orig, :] a_idx = a_idx_orig b_idx = b_idx_orig # 若启用保护，构造受保护索引的形状以适配 gather（[1, P, 1]） if enable_protection: protected_idx = protected_indices.unsqueeze(0).unsqueeze(-1) num_protected_actual = protected_idx.shape[1] else: protected_idx = None num_protected_actual = 0 # 记录两侧的数量，便于后续分割与 scatter/gather num_src = a_idx.shape[1] num_dst = b_idx.shape[1] # 内部辅助函数：根据 a_idx/b_idx/protected_idx 将输入 x 分割为 src/dst/(protected) def split(x): C = x.shape[-1] if enable_protection: src = gather(x, dim=1, index=a_idx.expand(B, num_src, C)) dst = gather(x, dim=1, index=b_idx.expand(B, num_dst, C)) protected = gather( x, dim=1, index=protected_idx.expand(B, num_protected_actual, C) ) return src, dst, protected else: src = gather(x, dim=1, index=a_idx.expand(B, num_src, C)) dst = gather(x, dim=1, index=b_idx.expand(B, num_dst, C)) return src, dst然后开始计算 src 和 dst token 之间的 similarity 以及对应的 dst token 的 index# 创建未初始化的张量用于存储每个 src 的最大相似度与对应的 dst 索引 node_max = torch.empty(B, num_src_actual, device=a.device, dtype=a.dtype) node_idx = torch.empty(B, num_src_actual, device=a.device, dtype=torch.long) # 将 dst 转置为 [B, C, num_dst]，用于 a 与 bmm 计算 b_transposed = b.transpose(-1, -2) # 分块计算每个 src 的最大相似度与 argmax dst node_max, node_idx = fast_similarity_chunks(a, b_transposed, chunk_size) # 按最大相似度由大到小排序，得到 src 的优先级队列（edge_idx） edge_idx = node_max.argsort(dim=-1, descending=True)[..., None]similarity 的代码等会儿讲。最后保存结果：如果要修改构图 or merging 的方式，则应该开始修改接下来这一段代码# 若启用保护：过滤掉属于保护集合的 src，保证这些 token 不被合并 if enable_protection: src_indices = a_idx[0, :, 0] protected_mask_src = torch.isin(src_indices, protected_indices) edge_flat = edge_idx[0, :, 0] # 仅保留未被保护的边 valid_mask = ~protected_mask_src[edge_flat] # 取反 valid_edges = edge_flat[valid_mask] valid_count = valid_edges.shape[0] r_actual = min(r, valid_count) # 根据 r_actual 切分：前 r_actual 为待合并 src，后面为未合并 src unm_idx = valid_edges[r_actual:].unsqueeze(0).unsqueeze(-1) src_idx = valid_edges[:r_actual].unsqueeze(0).unsqueeze(-1) else: # 无保护时，直接用 edge_idx 切分；前 r 为待合并 src，其余为未合并 src unm_idx = edge_idx[..., r:, :] src_idx = edge_idx[..., :r, :] r_actual = r # 为每个待合并的 src 查出它指向的 argmax dst 索引 dst_idx = gather(node_idx[..., None], dim=-2, index=src_idx) # 用 r_actual 回写 r，便于后续一致性（extra_tensors 同步） r = r_actual最终参与 merge 的 tensor注意到，这里实际上最后出来了三个存 token 的 tensor：src, umn, dst 如果 enable_protection = True，则还会有一个额外的 protected tensorsrc 对应要 merge 掉的 tensorumn 对应：当前的合并比例是 $r$，那么剩下的 $N \times (1 - r)$ 个 tensor 就是不合并的，存储在 umn 中dst 对应：src token 要合并到 dst token 上merge()函数声明# 定义合并函数：把选中的 src 汇聚到对应的 dst（默认 reduce=mean），并返回拼接结果 def merge( x: torch.Tensor, mode: str = "mean", extra_tensors=None, # 额外同步合并的 tensor，保证后续 q@k 的序列长度一致。 extra_tensors_2=None, # 额外同步合并的 tensor 2，同上 ) -> Union[ torch.Tensor, Tuple[torch.Tensor, torch.Tensor], Tuple[torch.Tensor, torch.Tensor, torch.Tensor], ]:Function call (in attention.py)：q_merge_in = q.permute(0, 2, 1, 3).reshape(B_q, N_q, H_q * D_q) k_merge_in = k.permute(0, 2, 1, 3).reshape(B_q, N_q, H_q * D_q) v_merge_in = v.permute(0, 2, 1, 3).reshape(B_q, N_q, H_q * D_q) q_out, k_out, v_out = m_a( q_merge_in, mode="mean", extra_tensors=k_merge_in, extra_tensors_2=v_merge_in, )具体实现# 按与 metric 相同的分割策略拆分 x if enable_protection: src, dst, protected = split(x) else: src, dst = split(x) n, t1, c = src.shape # 未合并的 src：根据 unm_idx 取出保留的 src 片段 unm_len = unm_idx.shape[1] unm = gather(src, dim=-2, index=unm_idx.expand(n, unm_len, c)) # 待合并的 src：根据 src_idx 选出前 r 个 src_len = src_idx.shape[1] src = gather(src, dim=-2, index=src_idx.expand(n, src_len, c)) # 将待合并的 src 聚合到对应的 dst；mode 默认为 mean，可改为 sum 等 dst = dst.scatter_reduce(-2, dst_idx.expand(n, src_len, c), src, reduce=mode)后面 extra_tensors / extra_tensors1 的流程是一样的。unmerge()# 先按顺序切分短序列：未合并 src（unm）、聚合后 dst、（可选）protected unm_len = unm_idx.shape[1] dst_len = num_dst src_len = src_idx.shape[1] unm = x[..., :unm_len, :] dst = x[..., unm_len : unm_len + dst_len, :] if enable_protection: protected = x[ ..., unm_len + dst_len : unm_len + dst_len + num_protected_actual, : ] # 用 dst 的聚合结果反向还原被合并的 src：根据 dst_idx 把 dst 拷回合适位置 _, _, c = unm.shape src = gather(dst, dim=-2, index=dst_idx.expand(B, src_len, c)) # 准备完整输出，并逐块 scatter 到原始索引位置 out = torch.zeros(B, N, c, device=x.device, dtype=x.dtype) # 1) 把 dst 放回原来的 b_idx（目标侧）位置 out.scatter_(dim=-2, index=b_idx.expand(B, num_dst, c), src=dst) # 2) 把未合并的 src 放回 a_idx 对应的 unm_idx 位置 out.scatter_( dim=-2, index=gather( a_idx.expand(B, a_idx.shape[1], 1), dim=1, index=unm_idx ).expand(B, unm_len, c), src=unm, ) # 3) 把被合并的 src（从 dst 反向恢复出来的片段）放回 a_idx 对应的 src_idx 位置 out.scatter_( dim=-2, index=gather( a_idx.expand(B, a_idx.shape[1], 1), dim=1, index=src_idx ).expand(B, src_len, c), src=src, ) # 4) 若启用保护，将 protected 片段 scatter 回 protected_idx 对应位置 if enable_protection: out.scatter_( dim=-2, index=protected_idx.expand(B, num_protected_actual, c), src=protected, ) return outfast_similarity_chunks()函数声明def fast_similarity_chunks( a: torch.Tensor, b_transposed: torch.Tensor, chunk_size: int ) -> Tuple[torch.Tensor, torch.Tensor]:Function call:node_max, node_idx = fast_similarity_chunks(a, b_transposed, chunk_size)具体实现注：torch.bmm 的全称是 batch matrix-matrix product，也就是 批量矩阵乘法。它一次性对一批（batch）里的多个矩阵做乘法运算。输入：两个三维张量 input 和 mat2形状分别是 (b, n, m) 和 (b, m, p)输出：三维张量，形状是 (b, n, p)其中 b 表示 batch size，也就是一批里有多少个矩阵要相乘。 每个 batch 内对应位置的矩阵会被相乘。核心代码：# Process in chunks for i in range(0, num_src, chunk_size): end_i = min(i + chunk_size, num_src) a_chunk = a_bf16[:, i:end_i, :] # [B, chunk_size, C] scores_chunk = torch.bmm(a_chunk, b_transposed_bf16) # 由于外层已对 a、b 做 L2 归一化，点积近似余弦相似度 chunk_max_bf16, chunk_idx = torch.max(scores_chunk, dim=2) # 在每个 src 行上找出最大值及其列索引（对应某个 dst chunk_max = chunk_max_bf16.to(original_dtype) node_max[:, i:end_i] = chunk_max node_idx[:, i:end_i] = chunk_idx return node_max, node_idx总结如果考虑要修改 protected token 的代码，那么所有 enable_protection 的代码都应该被考虑修改...
Deep Generative Models - 2: Diffusion Models
总结Diffusion 的操作其实非常简单，核心算法的框架伪代码如下图所示：其中 Training 的部分，主要包含了 Add Noise 这个步骤（Forward Process）。每次我们选取一张图 $x_0$ （真值），一个 $[1, T]$ 的数 $t$，和一个高斯噪声 $\epsilon \sim \mathcal{N}(0, I)$ 。每次把高斯噪声 $\epsilon$ 加给 $x_0$ 的步骤就是 add noise。一个比较精巧（奇妙）的操作时这个 $t$。当然，如果从 Autoregressive 的角度来看待 Diffusion，这个 $t$ 是非常合理的。在 Sampling 部分，主要是包含了一个 Denoise 的步骤 （Reverse Process）。其中，一个用以预测整体噪声的网络 $\epsilon_{\theta}$ 是我们优化的目标。$\epsilon_{\theta}$ 要生成在 Training 阶段对应位置加过噪声的图片中，真实的噪声分布。我们不可以把 Denoise 简单的看成是一个 add noise 的逆过程。原因有两点：Denoise 过程中消去的噪声是 $\epsilon_{\theta}$ 的预测值而非真实值。注意到 Sampling 阶段的末尾加上了一个神秘 $\sigma_t\mathbf{z}$。这个东西非常有说法。在这里我想提供李宏毅老师课中的一个解释。以 GPT 为例，如果预测的下一个位置永远是 Confidence 最高的 candidate，那么生成出来的文本很有可能是一段不断重复一个意思的段落。因此，LLM 中也会类似地加上一个这样的随机噪声。同理可得，如果没有在 denoise 阶段加上这个随机噪声，那么我们生成的图像可能是一张单一颜色的图像。因此对于 denoise 过程，我目前的理解是：由于真实的图像的噪声可必然是一个比我们目前假设的噪声分布——即高斯分布，更加复杂的分布。 因此，Diffusion 的 denoise 实际上是在产生一个其噪声符合一个低级（简单）分布的图像。Add NoiseDefinition在 DDPM（Denoising Diffusion Probabilistic Models）中，前向过程定义为一个 马尔科夫链：$$ q(x_t|x_{t-1}) = \mathcal{N}(x_t; \sqrt{1 - \beta_t} x_{t-1}, \beta_t\mathbf{I}) $$其中：$\beta_t$ 是一个噪声方差的超参数（通常很小，且逐渐变小）条件分布是高斯分布，均值缩小原输入，方差是 $\beta_t$也就是说，每次我们加上去一个高斯噪声 $\epsilon \sim \mathcal{N}(0, \mathbf{I})$ 给 $x_{t}$:$$ x_t = \sqrt{1 - \beta_t} x_{t - 1} + \beta_t\epsilon $$从这个式子我们可以看出：均值：$\sqrt{1 - \beta_t} x_{t - 1}$，表示对输入的逐步衰减。方差: $\beta_t$ ，表示每一步加的高斯噪声强度。这样设计的好处是：整个过程可以解析化地推出任意 $t$ 时刻的分布：$$ q(x_t|x_0) = \mathcal{N}(\sqrt{\bar{\alpha_t}}x_0, (1 - \bar{\alpha_t})\mathbf{I}) $$其中：$\bar{\alpha_t} = \prod_{i = 1}^{t} (1 - \beta_i)$ 这个原理是说，假如我们已知 $x_0$ （即输入的图像），由于我们整个 add noise 的过程是一个线性高斯马尔科夫链，假如我们用 $x_1: x_{T}$ 来表示中间步的结果，那么：$$ q(x_1:x_T|x_0) = q(x_1|x_0) q(x_2|x_1) \dots q(x_T|x_{T- 1}) $$因此，我们将这个式子的 $x_i, i \in [0, T)$ 拆出来之后，就发现 $\alpha_i = \sqrt{1 - \beta_1}\sqrt{1 - \beta_2}\cdots\sqrt{1 - \beta_t}$Scheduler在上文中我们提到了 $t \sim \text{Uniform} (\{1, \dots, T\})$ ，这里的 $t$ 是一个时间步。$t$ 对于 Diffusion models 非常关键，因为其控制随时间演化噪声的分配方式。常见的 schedule 有：LinearCosine （噪声增加得更平滑）自适应 schedule（后来改进的，基于信噪比设计）这里给出一个为什么 schedule 关键的解释。schedule 使得：不同时间步的信噪比分布合理；模型能在全程学到有用的去噪任务；反向采样过程稳定，最终生成质量高。Reverse ProcessDefinition我们现在的目标是要学习一个反向马尔科夫链：$$ p_{\theta}(x_{t-1}|x_t), t = T, T - 1, \dots, 1 $$使得：$$ p_{\theta}(x_{0:T}) = p(x_T) \prod_{t=1}^{T} p_{\theta}(x_{t-1}|x_t) $$其中，$p(x_T) \sim \mathcal{N}(0, \mathbf{I})$我们有 Forward Process 的式子（线性高斯马尔可夫链），我的理解是：相当于一个有先验概率得后验概率。那么 Reverse Process 就是一个 Bayes 公式（因为我们是要从 $x_{t}$ 推导 $x_{t-1}$。那么有：$$ q(x_{t - 1} | x_t, x_0) = \mathcal{N}(x_{t-1}; \tilde{\mu_t}(x_t, x_0), \tilde{\beta_t}\mathbf{I}) $$其中：$$ \tilde{\mu_t} = \frac{\sqrt{\alpha_t}(1 - \bar{\alpha_{t-1}})}{1 - \bar{\alpha_t}} x_t + \frac{\sqrt{\bar{\alpha_{t-1}}} \beta_t}{1 - \bar{\alpha_t}}x_0 $$$$ \tilde{\beta_t} = \frac{1 - \bar{\alpha_{t-1}}}{1 - \bar{\alpha_{t}}} \beta_t $$这里面大概是涉及多个高斯分布的联合分布的推导，具体不展开了。比较神秘。DDPM 的附录里面有提到。在此不多赘述。解释：$\tilde{\mu}_t$ 是反向高斯分布的均值，由当前 noisy 样本 $x_t$ 和真实干净样本 $x_0$ 决定。$\tilde{\beta}_t$ 是方差，依赖于 schedule。问题是：反向过程需要 $x_0$，但生成时我们并不知道 $x_0$。Learn a Distribution因此，Diffusion 会训练一个用以预测整体噪声的网络 $\epsilon_{\theta}(x_t, t)$，这里就再次体现了时间步 $t$ 的重要性。因为 $t$ 是被当做参数一起传入 $\epsilon_{\theta}$ 中的。根据 Forward Process ，移项可得：$$ x_0 \approx \frac{1}{\sqrt{\bar{\alpha_t}}} (x_t - \sqrt{1 - \bar{\alpha_t}}\epsilon_{\theta}(x_t, t)) $$再把这个 $x_0$ 代入 $\tilde{\mu_t}$ 中，就得到了反向分布的近似均值：$$ \mu_{\theta}(x_t, t) = \frac{1}{\sqrt{\alpha_t}} \left(x_t - \frac{1 - \alpha_t}{\sqrt{1 - \bar{\alpha_t}}} \epsilon_{\theta}(x_t, t) \right) $$因此，最终的 $p_{\theta}(x_{t-1}|x_t)$ 就可以表示为：$$ p_{\theta}(x_{t-1}|x_t) = \mathcal{N} (x_{t-1}; \mu_{\theta}(x_t, t), \tilde{\beta}_t\mathbf{I}) $$Train Loss论文中有提到如何转换成 ELBO 形式。由于过于复杂，中间的主要步骤是通过类似于累乘过程中分母分子抵消来花间，这里不过多赘述。这里主要展示最后的结果：$$ \mathcal{L} = \mathbb{E}_{x_0, t, \epsilon} \left[ || \epsilon - \epsilon_{\theta} (x_t, t) ||^2\right] $$
Deep Generative Models - 1: Variational Autoencoder (VAE)
前言乱扯几句，最近发现 Anything + 生成式 还是有许多工作可以做的，算是一片蓝海吧。虽然感觉自己做什么都比别人慢几拍，前两年追热点死活追不上，不过也不能完全这么说，因为刚进大学时还屁都不懂呢。3DGS是2023年的文章，Diffusion 甚至比 GPT 要早一年（2022）就在学术圈火爆了。离开学还有一段时间，打算慢慢补一些生成式相关的知识。遂写下一些笔记，纯当是自己在这个世界存在的证明。Motivation如果我们有一个这样的 Data Generation 的过程，其中我们给 Generator 的输入是一个 Latent Vector （Embedding） $z$，最终输出的是图像/视频/音频之类的数据，记为 $x$Process假设：给定的所有训练数据 $x$ 构成的分布记为 $p_{data}$所有的 Latent Vectors $z_i$ 构成的分布为 $q(z)$，即：$z_i \sim q(z)$，其中 $p(z_i)$ 指的是从这个分布中 sample 到 $z_i$ 的概率密度。最终的生成结果 $x' = p_{\theta}(x|z)$记所有的 $x'$ 构成的分布为 $p_{\theta}(x)$，其中 $\theta$ 为 Decoder 的 Learnable Parameters我们最终的训练目标，是 $p_{\theta}$ 接近 $p_{data}$ 的分布。我们希望用一个量化的指标来衡量两个分布的接近程度，此处选择 KL-DivergenceQuestion: 是否有别的 Metrics?形式化地，我们的目标为：$$ \min_{\theta} D_{KL}(P_{data} || P_{\theta}) $$我们的训练目标 $\theta$ 即为：$$ \begin{align} & \arg\min_{\theta} D_{KL}(P_{data} || P_{\theta}) \\ = & \arg\min_{\theta} \sum_{x} P_{data}(x) \log(\frac{P_{data}(x)}{P_{\theta}(x)}) \\ = & \arg\min_{\theta} \sum_{x} -P_{data}(x) \log P_{\theta}(x) + C \\ = & \arg\max_{\theta} \sum_{x} \log P_{\theta}(x) \\ = & \arg\max_{\theta} \mathbb{E}_{x \sum P_{data}(x)} \log P_{\theta}(x) \end{align} $$其中，很明显 $P_{data}$ 是我们已知的（训练集已知），因此完全不与 $P_{\theta}$ 相关的项都写成一个常数 $C$。进一步地，由于我们此处只关心 $\theta$ ，因此 $-P_{data}(x)$ 也可以视为一个常系数。现在我们只关心 $P_{\theta}(x)$，由于其全部由条件概率 $P_{\theta}(x|z)$ 给出，由全概率公式：$$ P_{\theta}(x) = \int_z P_{\theta}(x|z)P(z)\mathrm{d}z $$回到主题，我们现在的麻烦是计算 $\log P_{\theta}(x)$，我们有：$$ \begin{align} \log P_{\theta}(x) & = \int_z \log P_{\theta}(x) q(z) \mathrm{d}z \\ & = \int_z \log \left( \frac{P_{\theta}(x|z)P_{\theta}(z)}{P_{\theta}(x)} \right) q(z) \mathrm{d}z \\ & = \int_z \log \left( \frac{P_{\theta}(x|z)P_{\theta}(z)}{P_{\theta}(x)} \cdot \frac{q(z)}{q(z)}\right) q(z) \mathrm{d}z \\ & = \int_z \left( \log P_{\theta}(x|z)+ \log(\frac{P_{\theta}(z)}{q(z)}) + \log(\frac{q(z)}{P_{\theta}(z|x)}) \right) q(z) \mathrm{d}z \\ & = \mathbb{E}_{z \sim q(z)} \left[ \log P_{\theta}(x|z) \right] - D_{KL}\left(q(z) || P_{\theta}(z)\right) + D_{KL}\left( q(z) || P_{\theta}(z|x) \right) \end{align} $$注意第三步用到了一个很经典的 $\cdot 1$ 的技巧，此处是为了避免拆 log 的时候相关变量无法分离（导致 +/- 和括号同时产生的大混乱情况）+ 与外面的 $q(z)$ 写成 KL-散度。我们称 Evidence Lower Bound：$$ RHS = \text{ELBO} = \mathbb{E}_{z \sim q(z)} \left[ \log P_{\theta}(x|z) \right] - D_{KL}\left(q(z) || P_{\theta}(z)\right) $$原因很显然，最后一项通过移项到 LHS 后显然会出现一个 $\log P_{\theta}(x)$ 的下界的形式：$$ LHS =\log P_{\theta}(x) -D_{KL}\left( q(z) || P_{\theta}(z|x) \right) $$观察到：LHS 中的 $\log P_{\theta}(x)$ 显然是无法计算的（不然根本没有这么些步骤），$P_{\theta}(z|x)$ 这个后验概率的分布显然也是无法表示的。那么希望寄托在 ELBO 身上。此外，另一个关键的问题是，$z$ 作为一个 Embedding 具有以下特征：$z$ 会是一个高维向量$q(z)$ 无法量化计算因此，我们引入了 Latent Variable Models，也就是变分自编码器的由来。既然我们无法确定一个“真”的 $q(z)$，如果我们可以让一个 $q_{\phi}(z|x)$ 输出一个“可控的”结果作为 $q(z)$ 的 PDF 的值，那么这个结果是可以接受的。我们可以将期望项视作一个 Reconstruction Loss由于我们将 $q(z)$ 认为是可以近似为一个 Learnable Distribution $q_{\phi}(z|x)$ ，其中 $\phi$ 是学习的参数，那么后一项可以视为一个 Regularization Loss。其鼓励 $\phi$ 导出的网络表示的分布与真实的 $q(z)$ 越来越接近。至此，整个流程就结束了。下面我们来具体关注这两个 Loss 的实现细节。由于 Reconstruction Loss 和 Regularization Loss 的方法是一样的，下面以 Reconstruction Loss 为例。我们关注的是：$$ - \mathbb{E}_{z \sim q(z)} \left[ \log P_{\theta}(x|z) \right] $$我们现在已经用一个易采样的近似分布：$q_{\phi}(z|x)$ 了，这里的 $\phi$ 导出的网络通常会输出分布的参数，比如说是 Gaussian 的话，那么就输出 $\mu$ 和 $\sigma$：$$ q_{\phi}(z|x) = \mathcal{N}(\mu_{\phi}(x), \sigma^2_{\phi}(x)I) $$这样的好处是：我们可以直接采样 $z^{(i)} \sim q_{\phi}(z|x)$采到的 $z$ 可以直接输入生成网络 $P_\theta$ 去算概率由此，这个期望就可以用 One-Step Monte Carlo 法计算：采样 $z^{(i)}$用生成网络 $P_{\theta}$ 计算 $\log (P_{\theta}(x, z^{(i)}))$：由于：$P(x, z^{(i)}) = P(x) \cdot P(z^{(i)})$再计算 $\log q_{\phi} (z^{(i)}|x)$用平均值近似期望现在的问题是，由于 $\phi$ 导出的分布参数是抖动的（即 $z$ 是取决于 $\mu_{\phi}$ 和 $\sigma_{\phi}$ 生成的），但这个采样操作里有噪声，计算梯度时不能直接对采样过程求导，反向传播会断掉。这里我们就要用到一个技巧：重参数化。具体地，把采样过程重写为“可导的确定性变换 + 独立噪声”：先采一个与参数无关的随机变量：$\epsilon \sim \mathcal{N}(0, I)$再用可导的线性变换得到 $z$：$$ z = \mu_{\phi}(x) + \sigma_{\phi}(x) \odot \epsilon $$这样的话：随机性来自于 $\epsilon$$\mu_{\phi}$ 和 $\sigma_{\phi}$ 直接参与计算 $z$，且过程可导反向传播时，梯度可以从$ z$ 传到 $\mu_{\phi}$ 和 $\sigma_{\phi}$ ，从而更新 encoder 参数现在得到 $z$ 以后，我们假设 $P_{\theta}(x|z)$ 是一个 Gaussian 分布：$$ P_{\theta}(x|z) = \mathcal{N}(x | \mu_{\theta}(z), \sigma^2I) $$接下来，使用负对数似然 (Negative Log-Likelihood, NLL) 作为损失。在 Gaussian 分布的这个假设下又有：$$ - \log P_{\theta}(x|z) = \frac{1}{2\sigma^2} ||x - \mu_{\theta}(z)||^2 + C $$这等价于 L2 Loss，常数项不影响优化。