Tony102's Blog - 总结
type: channel
link: https://tony102.com/index.php/category/%E6%80%BB%E7%BB%93/
items: VGGT for 4D Task: A simple survey
items: 简明 ML 作业题解法
items: TOC Undecidability 复习
items: TOC Final Review
items: Pumping Lemma for Regular Languages
items: SVM 的拉格朗日乘数法解
items: TOC Review 1: From Math Preperation to Pumping Lemma
items: FastVGGT 中 token merging 相关代码的解释
items: Deep Generative Models - 2: Diffusion Models
items: Deep Generative Models - 1: Variational Autoencoder (VAE)

VGGT for 4D Task: A simple survey
type: item
date: 2026-01-11T12:56:00+08:00
description: 总结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 e…

简明 ML 作业题解法
type: item
date: 2026-01-02T21:23:00+08:00
description: 太简单了的就不写了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 比较重要的一个做题直接贴一个参考答案就懂了主要是要注意权重

TOC Undecidability 复习
type: item
date: 2025-12-31T11:12:00+08:00
description: 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 …

TOC Final Review
type: item
date: 2025-12-29T14:50:00+08:00
description: 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$ 也是 CFGCo…

Pumping Lemma for Regular Languages
type: item
date: 2025-11-08T14:08:00+08:00
description: 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!}{…

SVM 的拉格朗日乘数法解
type: item
date: 2025-11-01T09:38:00+08:00
description: 原始问题（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
type: item
date: 2025-10-20T12:52:00+08:00
description: 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。首先…

FastVGGT 中 token merging 相关代码的解释
type: item
date: 2025-09-29T10:08:00+08:00
description: 接口参数在 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 = in…

Deep Generative Models - 2: Diffusion Models
type: item
date: 2025-09-03T00:57:00+08:00
description: 总结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（后来改进的，基于信噪比设计）这里给出一个为什么 sche…

Deep Generative Models - 1: Variational Autoencoder (VAE)
type: item
date: 2025-09-01T00:22:00+08:00
description: 前言乱扯几句，最近发现 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_{…