总结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 并不非常精确。应该说可能可以有一个比较大的改进。
Fabricating Sculptures题意米格尔·安杰洛（Miguel Angelo）是一位伟大的雕塑家，以其户外雕塑作品而闻名。在他的家乡，人们经常能在广场和花园里看到他的作品。人们喜爱这些雕塑，不仅因为它们美观，还因为即使经历数十年，看上去仍然像新的。这些雕塑不易老化，这得益于米格尔和他的团队多年来开发的材料与工艺。为了制作雕塑，他首先通过堆叠防水石膏块（他秘密的材料）来搭建底座：将若干个“块堆”（stack）按一条直线排成一排。所有石膏块完全相同，并且每一堆至少包含一个石膏块。为了让结构更稳固，他会在这些块堆的前后各放置一块大的玻璃板（即一块在块堆后面，一块在块堆前面）。然后他会等待雨水降落，不管需要等多久。如果该结构在这个过程中不会积水，米格尔就确信这个底座可以用来制作一件经久耐用的艺术品。注意：当一个石膏块的左右两侧（左边和右边）都存在障碍（其他石膏块）时，水就会在该石膏块上方积累。题目中的图片展示了若干不同底座的正视图。它们都由 3 个块堆组成，总共使用 6 个石膏块，并且每个块堆至少一个石膏块（满足要求）。其中，左边的 8 种底座不会积水，而右边的 2 种会积水。米格尔目前接到大量雕塑请求。虽然他可以自由创作，但他希望公平起见，所有雕塑都使用相同数量的块堆与相同数量的石膏块。由于他不想把完全相同的雕塑卖给不同客户，因此每次都会构造一个不同的底座。他担心自己无法满足所有请求。请你帮助他计算：给定块堆数量和石膏块总数时，不积水的不同底座共有多少种。Sol首先想办法刻画一下这个题目要求的状态。大概是只能是“凸“形的，不能是”凹“形的。这个凸形的本身就很有灵性了，凸形意味着它是 单峰 的。简单考虑从左到右， 比如说是设 $dp_{i, n, j}$ 表示现在搞到了第 $i$ 个 stack，还剩下 $n$ 个 block 可以用，当前 stack 已经用了 $j$ 个 block。考虑转移是不可能的，因为发现这样只能处理单调的情况，对于“凸”这种单峰的形式是做不了的。实际上处理单峰的手段也比较少吧。核心思路 基本都是想办法弄成单调的。比如说：三分实际上是利用了单峰函数一阶导为一次函数单调 。考虑怎么把问题刻画成单调的。如果我们是从下往上堆，你会发现凸这个性质在每一“层”都只需要是数量单调不增即可并且连续的一段 block。比如说，最底下（记为 $h_1$ 层）放了5个 block，那么第四层一定是连续的一段，数量 $\leq 5$ 即可。这样计数的话，我们只要考虑枚举每一层放的数量（仅仅依赖于上一层放的数量）+ 放的位置（可以想象成一个“滑动窗口”在每一层上）设 $dp_{i, j}$ 表示当前层还剩下 $i$ 个block可以放，上一层放了 $j$ 个。考虑如何转移：$$ dp_{i, j} = \sum_{k = 1}^{\min(i,j)} dp_{i-k, k} \times (j - k + 1) $$然后我们会需要枚举 $O(B)$ 个 block （注意实际上按照现在状态的定义，最多是放 $B - S$ 个，因为最底下一层必须全部放一个），然后枚举上一层放了多少个 $O(S)$，然后再算这个和式 $O(S)$，然后 $B,S$ 同阶，可以认为是立方级别的复杂度。观察到这个和式是比一个比较经典的下标和为 $i$ 的和式，也就是对对角线求和。那么可以考虑前缀和优化。不过由于这个转移比较 naive，所以需要一些技巧来处理这个和式。首先是经典的参变分离：$$ dp_{i, j} = (j + 1) \sum_{k = 1}^{\min(i,j)} \times dp_{i-k, k} + \sum_{k = 1}^{\min(i,j)} k \times dp_{i - k, k} $$注意这里的 $i$ 对于和式是一个常量，所以直接提出去。这样的话，对于每一个 $i$，可以线性预处理出 $dp_{i - k,k}$ 和 $k \times dp_{i - k, k}$ 的前缀和。具体的，记第一项的前缀和为 $A_k$, 那么$$ A_k = A_{k - 1} + dp_{s - k, k} $$记第二项的前缀和为 $Bw_k$，那么$$ Bw_k = Bw_{k - 1} + k \times dp_{s - k, k} $$那么转移写成$$ dp_{i, j } = (j + 1) \times A_m - Bw_m \bmod p $$其中 $p = 10^9 + 7$ 为题目给定的模数，$m = \min(i, j)$Idea单峰状态的处理手段：转换成单调经典和式的处理Code知道你们爱看#include <iostream> #include <cstdio> using namespace std; #define int long long const int mod = 1e9 + 7; const int SIZE = 5000 + 5; int dp[SIZE][SIZE], A[SIZE], Bw[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; signed main() { // freopen("test.in", "r", stdin); int S = read(), Btotal = read(); int E = Btotal - S; int W = S; for (int n = 0; n <= W; ++n) dp[0][n] = 1; for (int s = 1; s <= E; ++s) { A[0] = Bw[0] = 0; int K = min(s, W); for (int k = 1; k <= K; ++k) { A[k] = (A[k - 1] + dp[s - k][k]) % mod; Bw[k] = (Bw[k - 1] + 1ll * k * dp[s - k][k]) % mod; } for (int n = 1; n <= W; ++n) { int m = min(s, n); long long val = (n + 1) * A[m] - Bw[m]; val %= mod; if (val < 0) val += mod; dp[s][n] = val; } } cout << dp[E][W] << "\n"; return 0; }
太简单了的就不写了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 !}$然后就是套路了
Preface当第一次接触黑盒的时候，你的脑子就会变成黑盒。第一次学这些东西的时候，应该还是 Andrew Ng 在 coursera 那一个非常通俗的 ML，没有微积分基础，也没有什么概率论的基础，故而对大部分算法的理解存在于：我有一个多元函数，参数未知，遂变成最大似然估计问题。剩下的都是技巧了。于是如果不懂，当作一个黑盒了解起输入输出和功能即可。不可置否的是，这种方法对于快速学习新东西非常有效果。但一旦深入，该补的功课还是一样都少不了。已经是彻彻底底的 Midterm 了，再不 review 之前的内容，期末等着挂科吧。3-Supervised Learning I3.1 Logistic Regression任务：分类（Classification）。接下来首先讨论二分类。实际上模型通过 activation function输出的是一个概率，比如说 Sigmoid:$$ \sigma(x) = P(y=1|x;\theta) = \frac{1}{1 + e^{-\theta^T}x} $$决策边界（Decision Boundary）：当 $\theta^Tx = 0$ 时分割两类。设计 loss function当我们要衡量预测好不好时，理想的损失函数也应该与概率预测相匹配，而不是MSE。如果用 MSE 的话，例如：$J(\theta) = \frac{1}{2m} \sum (h_{\theta}(x_i) - y_i)^2$，存在的问题是：Sigmoid 是非线性的，导致 损失函数非凸（non-convex），优化时容易卡在局部最小值。从概率角度看，它也不是在最大化正确分类的概率。因此，我们要设计一个新的 loss function。从概率建模角度出发，我们希望模型能最大化样本出现的概率（最大似然估计）：$$ L(\theta) = \prod_{i=1}^{m} P(y_i|x_i;\theta) $$取 log：$$ \log L(\theta) = \sum_{i=1}^{m} [y_i \log h_{\theta}(x_i) + (1 - y_i) \log (1 - h_{\theta}(x_i))] $$最大化这个“对数似然”就等价于最小化它的负数：$$ J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} [y_i \log h_{\theta}(x_i) + (1 - y_i) \log (1 - h_{\theta}(x_i))] $$这就是 Cross Entropy Loss（交叉熵损失）。Multiclass classificationOne-vs-All 策略：对每个类别分别训练一个分类器。预测时选择概率最大的类别。Regularization目的：防止过拟合。在代价函数中加入惩罚项, i.e.：$$ J(\theta) = J(\theta) + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2 $$调节参数 $\lambda$ 的大小可平衡偏差（Bias）*与*方差（Variance）。注意，此时梯度更新公式也要加上这一项：$$ \theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j} - \alpha \frac{\lambda}{m}\theta_j $$3.2 Suppor vector machine这个之前真没学过，因此详细写一下Motivation分类任务也可以视为找到一个“面”，可以把各个类隔离开。具体地，这个“面”：Hyperplane，超平面，是n维欧氏空间中，余维度为1的子空间[1]。即超平面是 $n$ 维空间中的 $n-1$维的子空间。具体的，SVM的目标是：找到一个能把两类样本分开的最优超平面，并使得两类之间的“间隔（margin）”最大。直觉上：它不像逻辑回归那样关心“概率”，而是关心“边界离样本多远”。只有最靠近边界的样本点（即“支持向量”）对模型有影响。假如我们有 Training data: $\{(\vec{x_1}, y_1) \dots (\vec{x_n}, y_n)\}$，我们的目标是找到一个 Hyperplane: $w^Tx + b = 0$ 满足：$$ \begin{align} w^Tx_i+b \geq 1, & y_i = +1 \\ w^Tx_i+b \leq -1, & y_i = -1 \\ \end{align} $$合并写成：$$ y_i(w^Tx_i + b) \geq 1 $$Design超平面定义：$$ \mathcal{H} = \{x \mid w^T x + b = 0\} $$对于任意一个点 x，它到超平面 H 的距离为：$$ d = \frac{|w^T x + b|}{\|w\|} $$个最靠近超平面的点（各一类）之间的距离就是“间隔”：$$ \gamma(w, b) = \min_{x \in D} \frac{2|w^T x + b|}{\|w\|} $$注意到有 scale invariance:$$ \gamma(\beta w, \beta b) = \gamma(w, b) $$所以直接可以令：$2|w^Tx+b| = 1$，故有：$$ \gamma = \frac{2}{||w||} $$要让间隔最大化，相当于让$||w||$ 最小化。约束：$\forall i, y_i(w^Tx_i+b) \geq 1$所以目标函数：$$ \min_{w,b} \frac{1}{2} ||w||^2 $$可用拉格朗日乘数法解，具体结果见另附说明。3.3 Support Vector Machine IISoft Margin目的：让 SVM 能处理非线性可分或含噪声的数据。引入“松弛变量”（Slack Variable） $\xi_i$，允许部分样本违背约束：$$ y_i(w^T x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0 $$新目标函数：$$ \min_{w, b, \xi} \ \frac{1}{2}\|w\|^2 + C \sum_i \xi_i $$其中 $C$：平衡项，用于控制“间隔大小”与“误分类惩罚”。$C \uparrow$：重视分类准确率；$C \downarrow$：重视大间隔、容忍误差。等价于使用 Hinge Loss：$$ l_{\text{hinge}}(z) = \max(0, 1 - z) $$软间隔的拉格朗日函数引入拉格朗日乘子 $\alpha_i \ge 0$，$\mu_i \ge 0$，构造拉格朗日函数：$$ \mathcal{L}(w, b, \xi, \alpha, \mu) = \frac{1}{2}\|w\|^2 + C \sum_i \xi_i - \sum_i \alpha_i [y_i(w^T x_i + b) - 1 + \xi_i] - \sum_i \mu_i \xi_i $$原始约束：$$y_i(w^T x_i + b) - 1 + \xi_i \le 1, \quad \xi_i \ge 0$$乘子非负：$$\alpha_i \ge 0, \quad \mu_i \ge 0$$互补松弛性：$$\alpha_i [y_i(w^T x_i + b) - 1 + \xi_i - 1] = 0, \quad \mu_i \xi_i = 0$$梯度为零：$$ \frac{\partial \mathcal{L}}{\partial w} = 0 \Rightarrow w = \sum_i \alpha_i y_i x_i $$$$ \frac{\partial \mathcal{L}}{\partial b} = 0 \Rightarrow \sum_i \alpha_i y_i = 0 $$$$ \frac{\partial \mathcal{L}}{\partial \xi_i} = 0 \Rightarrow C - \alpha_i - \mu_i = 0 $$软间隔的对偶问题将 $w = \sum_i \alpha_i y_i x_i$ 和 $\sum_i \alpha_i y_i = 0$ 代入拉格朗日函数，得到对偶问题：$$ \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) $$约束：$$ 0 \le \alpha_i \le C, \quad \sum_i \alpha_i y_i = 0 $$软间隔的支持向量若 $0 < \alpha_i < C$：样本在间隔边界上，是支持向量；若 $\alpha_i = 0$：样本满足原始约束，不在间隔边界上；若 $\alpha_i = C$：样本不满足原始约束，是误分类或在间隔内部的点。软间隔的分类器分类函数为：$$ f(x) = \text{sign}(w^{*T}x + b^*) $$其中 $w^* = \sum_i \alpha_i^* y_i x_i$，$b^*$ 可通过支持向量求得：$$ b^* = y_j - \sum_i \alpha_i^* y_i (x_i^T x_j) $$Kernel TrickMotivation核技巧让 SVM（以及任何只依赖“内积”的算法）在高维特征空间里学习一个线性分类器，但无需显式计算高维映射，只要把所有的内积 $x_i^\top x_j$ 换成一个核函数 $K(x_i,x_j)$ 就行。这样我们在原空间做“低成本的高维学习”。把原始样本 $x$ 通过非线性映射 $\phi(x)$ 送到高维甚至无限维空间，让原本线性不可分的数据线性可分（见“Feature Mapping”示意图，页 15）。但直接算 $\phi(x)$ 的维度可能爆炸。核技巧用$$ K(x,z)=\langle \phi(x),\phi(z)\rangle $$间接完成高维内积计算（页 17–21）。FormulaSVM 的对偶问题里，训练与预测都只出现样本间内积：$$ \max_\alpha \sum_i \alpha_i-\frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_i y_j \,\underbrace{x_i^\top x_j}_{\text{只出现内积}} $$预测：$$ h(x)=\operatorname{sign}\left(\sum_i \alpha_i y_i\, \underbrace{x_i^\top x}_{\text{只出现内积}}+b\right) $$把所有内积统一替换为核函数 $K(x_i,x_j)$ 与 $K(x_i,x)$：$$ \begin{aligned} \max_\alpha~& \sum_i \alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\, K(x_i,x_j) \\ h(x)=&~\operatorname{sign}\Big(\sum_i \alpha_i y_i K(x_i,x)+b\Big) \end{aligned} $$这就是核化后的 SVM（页 20–21）。Kernel 的选择核形式何时用线性 Linear$K(x,z)=x^\top z$特征很多、基本线性可分；大 $n$、小 $m$（页 27、29）。多项式 Polynomial$K(x,z)=(x^\top z+c)^d$引入特征交互/曲线边界，$d$ 为次数（页 22–23）。高斯/RBF$K(x,z)=\exp(-\x-z\^2/2\sigma^2)=\exp(-\gamma\x-z\^2)$通用首选；可形成复杂非线性边界（页 25、27）。Sigmoid$\tanh(\beta x^\top z+\theta)$类神经网络，实践中较少做标准 SVM 的默认。经验法则（页 29）：$n$ 大（特征多）→ 线性核；$n$ 小、$m$ 中等 → RBF；$n$ 小、$m$ 很大 → 先造特征再用线性模型。一个函数是不是合法核？必要且充分条件：对任意有限样本集 $\{x_i\}$，构造核矩阵 $K_{ij}=K(x_i,x_j)$，它必须对称半正定（页 26）。实际中通常直接用“现成的”核族。多项式核 $K(x,z)=(x^\top z+c)^d$ 等价于在 $O(n^d)$ 维空间做线性内积，但计算核仍是 $O(n)$核化后的 SVM 一般配合 软间隔：$$ \min \tfrac12\|w\|^2 + C\sum_i\xi_i \quad\text{s.t.}\quad y_i(w^\top \phi(x_i)+b)\ge 1-\xi_i $$对偶里出现 $0\le \alpha_i\le C$ 与核 $K(\cdot,\cdot)$（页 7–12, 20）。4.1 Ensemble LearningIntro集成学习 通过组合多个基学习器（base learners）来获得更强的泛化能力（最终使用多数投票或加权平均）。它之所以有效：不同模型的误差模式互补，组合后能降低方差/偏差，稳定性能提升（页 31–34、35 的投票示意图）。常见组合方式：Voting / Averaging：多模型独立训练后，分类取多数、回归取均值（页 35）。Stacking：把各模型的预测当作“特征”，再训练一个二级模型融合（页 36，示意图展示 Level 1→Level 2）。Bagging（Bootstrap Aggregation）MotivationBagging 的核心是：对训练集自助采样（bootstrap, 有放回），得到多份“不同但同分布”的数据子集，分别训练多个基学习器，最后分类投票/回归平均。这样能显著降低方差、提升稳定性（不改偏差）。自助采样性质：样本量为 $m$ 时，某个样本至少出现一次的概率约 0.632；因此每个子集中约有 63.2% 的独立样本出现（另一部分是重复样本）。推导：未出现概率 $\lim_{m\to\infty}(1-\tfrac1m)^m\approx e^{-1}\approx 0.368$。“平均降方差”直觉：独立同分布情形下，$K$ 次测量的均值方差约为 $\sigma^2/K$（课件给出期望与方差公式）。Formula分类（多数投票）：$$ H(x)=\arg\max_{y\in\{\text{classes}\}}\sum_{t=1}^{T}\mathbf{1}\big(y=h_t(x)\big). $$这里 $h_t$ 是第 $t$ 个基学习器，$T$ 是模型数。回归（平均）：用各模型输出的算术平均（课件概念性说明）。Pseudo Code输入：训练集 $D$，基学习算法 $\mathcal{L}$，轮数 $T$。循环 $t=1\ldots T$：$D_t \leftarrow \text{Bootstrap}(D)$（有放回采样，大小与 $D$ 相同）$h_t \leftarrow \mathcal{L}(D_t)$输出：分类用多数投票的 $H(x)$（如上式）。何时有用主要降低：方差（把“对训练集很敏感”的不稳定模型平均掉）。通常不改变：偏差（模型系统性误差不变）。最适合：高方差基学习器（如未剪枝的决策树）。若基模型本身高偏差、对数据扰动不敏感，Bagging 收益有限（课件结论）。Random Forest随机森林 = 决策树的 Bagging + 结点级特征子采样：对样本做 bootstrap（与 Bagging 一样）；每个结点仅在随机选取的少量特征上寻找最优切分（课件示例：给定 $d$ 个特征，每个结点使用 $\log|d|$ 个特征），进一步去相关化各棵树，提高集成增益；预测阶段通过投票/平均融合。BoostingIntroBoosting 用很多个“弱学习器”（略好于随机猜）串行地训练：每一轮根据上轮的错误提高难样本的权重，迫使下一轮更关注这些样本；最后把所有弱学习器加权投票/加权求和，得到一个强模型（第 47 页）。与 Bagging 的关键差异：Boosting 是串行、降低偏差为主，而 Bagging 并行、降低方差为主（第 58 页）。AdaBoost设训练集 $\{(x_i,y_i)\}_{i=1}^m$，二分类 $y_i\in\{-1,+1\}$。初始化权重：$D_1(i)=1/m$（第 48–51 页）。第 $t$ 轮：在分布 $D_t$ 上训练弱分类器 $h_t(x)$。计算带权错误率$\displaystyle \epsilon_t=\sum_i D_t(i)\,\mathbf{1}[y_i\neq h_t(x_i)]$（第 51 页）。设置该弱分类器的重要性系数$\displaystyle \alpha_t=\tfrac12\log\frac{1-\epsilon_t}{\epsilon_t}$（第 51 页）。更新样本分布$$ D_{t+1}(i)=\frac{D_t(i)\exp\big(-\alpha_t y_i h_t(x_i)\big)}{Z_t}, $$其中 $Z_t$ 为归一化常数（第 51 页）。最终模型（加权投票）：$$ H(x)=\operatorname{sign}\!\Big(\sum_{t=1}^T \alpha_t\, h_t(x)\Big) \quad\text{（第 49、51 页）。} $$为什么 work：课件指出：Boosting（以 AdaBoost 为例）等价于在最小化指数损失$$ \sum_{i=1}^m \exp\!\big(-y_i\,H(x_i)\big),\quad H(x)=\sum_t \alpha_t h_t(x), $$因此它会逐轮降低偏差（bias）（第 57 页）。直觉：被分错的样本有 $y_i H(x_i)<0$，损失被指数函数放大，下一轮权重更高→后续模型更“盯”难点。偏差：Boosting 通过逐轮拟合难样本，通常能显著降偏差（第 57–58 页）。方差：组合多个弱模型也有助于稳定，但主效应仍在降偏差。噪声/离群点：因会持续提升“分错样本”的权重，Boosting 更易受噪声影响；Bagging 对噪声更稳（第 58 页总结）。一些 formula：$\epsilon_t=\sum_i D_t(i)\mathbf{1}[y_i\neq h_t(x_i)]$（带权错率）$\alpha_t=\tfrac12\log\frac{1-\epsilon_t}{\epsilon_t}$（弱学习器权重）$D_{t+1}(i)\propto D_t(i)\exp(-\alpha_t y_i h_t(x_i))$（样本权重更新）$H(x)=\operatorname{sign}(\sum_t \alpha_t h_t(x))$（最终分类器）5 Neural Network咕咕咕
原始问题（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 的代码都应该被考虑修改...