Tony102's Blog
type: channel
link: https://tony102.com/
description: A CJOIer
items: 潮汕游记
items: VGGT for 4D Task: A simple survey
items: CF102428F Fabricating Sculptures
items: 简明 ML 作业题解法
items: TOC Undecidability 复习
items: TOC Final Review
items: Pumping Lemma for Regular Languages
items: Machine Learning Midterm Review
items: SVM 的拉格朗日乘数法解
items: TOC Review 1: From Math Preperation to Pumping Lemma

潮汕游记
type: item
date: 2026-07-02T01:02:00+08:00
description: 既然是自己随便写着玩的东西，就没有必要分结构的标题了。现在回想起之前的游记，确实是充满了高中生独有的活力。由于成日被锁在学校里，精神实际上也有一把隐形的锁，导致任何一次出游都是兴奋和期待的，因为再稀疏平常的东西换个地方见到，都会觉得十分新奇十分有意思。然而后知后觉才意识到，所谓“丰富阅历”，最重点的是“丰富”的这个过程，因为一旦丰富了以后，世界就变得无聊了。想起来生活又何尝不能是是做一次 "training"，本质上是 loss 在早期快速收敛（理想情况下），后面慢慢变得十分平缓，最后趋于收敛。什么东西都见过以后，就会”见怪不怪“，遂也没了梯度。本来今天已经是旅行的最后一天了，就在几个小时前回酒店的路上，想起来要写下点什么，现在就已经不记得了。看来成为一个合格的旅行作家，还有很长的路要走。真佩服他们。其实所谓之游记，大概也是一种流水账。鉴于本人的记性一般，很多东西也是有感而发，遂采用想到哪写到哪的方式，今天写一笔，明天添一笔。希望日后再点开的时候有新的感悟，就能加进来。今天是7月2日，星期四，的凌晨。感觉每次旅行结束的后劲都是比较大的，这一次真还挺大的。昨天，其实是前天了，先从汕尾开到东莞把楼放在华子准备实习了，然后又一路到深圳，跟 NUS 大师兄吃个饭然后关桑也回家了，剩下我和tosaka。昨天中午跟 Jackson 再一起吃了个饭，下午打了一下午电动，晚上tosaka就回杭州了，最后只有我一个人开回珠海。一路上一点点人下车，一步步变冷清，遂感到荒凉和委屈。也许这也是成长的阵痛的一种吧。现在回想起来，最开始对这次旅行的珍视程度还是不够。我们这个四个人，去年暑假也是在一起赶ddl，其实现在想起来，是一段很美好的时光。有一个纯粹的，近在眼前的目标，AAAI，然后遇到了各种情况，在 ddl 的催促下，每天12点醒，5点睡，只吃得上一顿饭。那种很纯粹很美好的时光，我想以后很难再有了。更何况天下无不散的筵席，关桑去美国读 PhD 了，实验室的其他小伙伴也有好多人毕业了，大家都有光明的未来。故而我们四个这辈子也不会有挤在实验室一起做事的经历了（很难）。再者，哪怕抛开这些因素，这是一次说走就走的旅行，21号大家说gogogo，其实第一天都已经在高速上了连酒店都还没有订。这是不是也是一种 Grand Turismo.

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…

CF102428F Fabricating Sculptures
type: item
date: 2026-01-09T13:52:00+08:00
description: 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 s…

简明 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!}{…

Machine Learning Midterm Review
type: item
date: 2025-11-01T10:27:00+08:00
description: 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^…

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。首先…