人对时间的感知，与年龄的关系大概是一个 log 的关系想起来去年今日，还在跟楼爆肝 AAAI。十年一次的 20 岁生日，在爆肝一天文章 + 临时起意去深圳吃东西最后只吃了个海底捞后，匆匆结束。一生又有几个十年，我知道去年今日我想清楚的唯一一个问题，就是不要对未来有任何的期待。如果没有期待，自然也就不会有太大的失落。所谓真正活在当下，大概就是心中清楚自己要干什么，然后尽人事听天命罢了。从某种角度来说，我变成了一个坚定的“命定论”的信徒。生死有命，富贵在天。这一岁回想起来，这样的观点是有缺陷的。如果理解了编译原理，就能类比出以上其实是一个 reduction，或者激进一点，是一个 SLR，而且是一个非常简的 reduction。遂步骤几乎是最优的，导致缺少了对过程的体验。解释一下，是体验过程本身会不易感觉到时间流逝，于是回过头想想，一切似乎还没有抓住就已经得到了命定的结局了。19 岁的自己，想送给 20 岁的自己第一篇 CCF-A，然而没有成功。现在想起来，19 岁果然还是有点幼稚的哈哈哈。不过 20 岁的时候，能对这件事情彻底释怀。体现在实际生活中，转折出现在3月初学期刚开始的时候跟程老师的新学期的第一次组会。既然已经认识到来不及发一篇所谓的 A 会来帮助升学，那就好好做一篇自己的“代表作”。想起来当时自己承受的压力不过是入行 3D Vision 仅一年然而没有任何文章中稿，而已。虽然 20 岁的自己又想给 21 岁的自己来第一篇 CCF-A，不过已经不会太纠结结果了。前三段在输出自己的观念与现实生活的一些主旋律，两段虚无，一段又极为现实。落差之大不免为之一惊。反思起来，或许成长就体现在过去的自己，比如高中或者大一大二年纪尚轻的阶段，会一时沉迷于这样的虚境并无法自拔。而现在，只会是在大量现实的实践后，readout 一下自己的 CoT。说回到 21 岁。一方面，想自由地探索这个世界。想到处去走走，去见见异域的风土人情。也想尝试不同的环境，去 industry 看看我觉得是对我的 academic 有好处的。至于其他的，都是副产品。祝自己生日快乐！
马上大四了，却发现一段实习都没有。感觉身边有很多同学大一的时候就通过各种各样的手段去规模不等的厂商进行实习了。虽然我觉得意义不明，因为大一的时候真的基本什么东西都还不会的吧。最近一年半的研究，主要集中在 3DGS、3D Foundation Model 和三维重建上。另外就是比较感谢 Amy 的 3DV，其实有很多传统的算法以及 Pipeline，并不是说自己学学不明白，而是缺少一个机会沉下心来琢磨其中的流程。我认为对我最近面试是很有帮助的，下面会细说。投 intern 的话，一来想感受一下大厂的氛围，二来也是想打一回富裕仗——有充足的算力资源和 token 之类的。另外的话，通过一些接触发现业内发 paper 也是比较有机会的。老师也是这么建议我去找一些有发 Paper 机会的 Research Intern 但在 industry 这样。下面遂逐一分享一些我面试的岗位。Audi没想到吧，传统主机厂我也是投上了。豪华品牌也给我蹭上了。主要是感谢组爸猛猛发力给我联系上了。不过我和组爸开始想的是做自动驾驶相关的岗位，但是后来发现是 agent。由于本人真的不懂 agent，虽然目睹了夹心组开发生信 agent，现在好想要变成特定在蛋白质的 agent 的开发流程了，但是还是对 agent 实际上是怎么构建的一窍不通。此时本人身处泰国开 ICME，中午休息的间隙找 GPT 临时花 15 分钟补习了一下 agent 相关知识。大概就是 agent 是什么，有些什么功能，以及有什么搭建的框架之类的。由于这些 GPT 都帮我复习到了（分享一下 prompt 吧：我现在要接受 【厂商】的 【岗位】面试，JD 如下：【JD】；任务：由于我是做 【研究方向】 方向的，现在还有十分钟，请你尽快的教会我我需要为面试准备的相关知识所以都美美流畅回答出来。然后 RAG 相关的我确实知道一点。还被问了一下 OI 经历，面试官表示对算法竞赛从来没有感兴趣过。然后这是唯一一个让我展示一下 coding 水平的面试。大概是让我现场 vibe coding 出一个个人主页，要有前后端。由于本人真的不是很了解前后端开发的技术栈，遂先试图晃一下面试官。我说个人主页为啥要后端？面试官即使觉得我说的对，但是说你就硬着头皮弄吧。这方面我确实是有心得的，你必须写清楚约束和简单的需求文档让 codex 干活。然后还没有 coding 结束他对我的表现满意遂终止。补充一点，他说他们 ld 是洋人于是考察了我的英文口语，所以后半段都是英文面试。他反复跟我强调他们在一个厂区，非常偏远。薪资待遇是挺不错的，不过要 on-cite。最后没有接到 offer。这是唯一一个面了没 offer 的。战败。金山西山居我其实知道西山居挺早的，金山确实在国内软件这块妥妥拿捏了。不论是 WPS 还是西山居之前的一些作品，现在肯定不如腾子网易，也不如米哈游鹰角这样的了。这个岗位是 C 哥看我在酒店面试，热心给我推荐的。太感谢了！时间线非常迅速，6号面完奥迪，C 哥就给我联系了，当天就约了 7号面试。由于我不太清楚 JD，所以准备了一下渲染、引擎以及3D资产相关的一些内容。整个面试过程非常愉快轻松，面试官很懂我做的方向，对 3DGS、VGGT 什么的都挺熟的。我当时感觉就不错，后来问我认为 AI 对游戏有什么用，我就瞎编我说我都不知道 AI 怎么定义，我说我的理解就是 learning-based 的方法都叫 AI。我说在这个 scope 下，我觉得可以做一些三维资产生成和重建之类的，有一些公司也在研究 DL rendering 吧，也有像米哈游这样做 AI 游戏的。当时老师可能觉得我说的挺有道理的吧。后来问了一下薪资，他问我有没有别的 offer。其实手上是没有的，我想了一下，如果报奥迪的原价，我就没有涨价的空间了。给奥迪涨了两千报给他，吓得对面惊慌失措。说他们没有那么高。试探性的报了一下奥迪的原价，对面仍然惊慌失措。遂迅速结束面试，说 HR 面会详谈。8号约了9号，我说9号我要回国了，遂改成 10 号。HR 上来就问我喜不喜欢游戏，我说还行。问我玩什么游戏，我说我是 CS 五年老兵，原神开服玩家（其实我是 1.4 入坑的，但是我号是买的。因为入坑是因为胡桃，但是入坑进去的时候已经错过了胡桃版本）。HR 跟我说技术老师给我技术非常高评价，因此想让我火速入职。但 HR 和蔼的告诉我了一个薪资数目，大概比我在外面上一天 OI 课的一半差不多。当时就比较犹豫，说可以先接受但是再考虑一下。当时是 10 号，说最近一个批次 15号入职的名单已经交上去了，所以 22 入职。后来说技术老师听说了要求让我 15 号光速入职，我说也行。但后来托人联系了 HR Head，说涨不了工资，公司规定说是，想了想还是婉拒了。后来听组爸说，米子系的工资都比较克扣。Man! What can I say.商汤这个比较曲折，是 CJOI 的一个学长在商汤。总之，做的岗位比较匹配，但是仍然是比奥迪少，跟我在外面上一天 OI 课薪资接近。接受全 remote。中间过程非常爽，美滋滋体验了一把什么叫做富裕 token 仗。也跟学长学了一些东西，快速了解了自动驾驶相关岗位我能干啥，如果不做 world model 的话，主要是做仿真是比较匹配我的研究的。由于种种原因，并不是非常正式 intern。可以理解为有 offer，但是刚说了不是很正式的 intern，所以不会有 offer。但确实有工资，这里面不由分说的东西，各位细品。阿里其实是阿里旗下的优酷土豆虎鲸文娱。做 3DGS 的，主要是三维资产（我就说吧）。面试很愉快，面试官的水平优于普渡但是没有西山居和商汤懂。技术面感觉是没问题的，但是由于时间和remote的问题，最后没有收到 offer。上海赛索德名不经传小公司一家，HR 很热情。但是他们公司的技术老师居然能直接鸽掉面试，跟下面普渡就对比鲜明了（都是做具身的公司）。遂婉拒了。普渡机器人岗位写的是双目机器人标定，遂拿出了双目相关的，比如说双目视察->深度等相关的知识，还有标定法，都是 Amy 的 3DV 里的内容复习了一番。打算信心满满了（自从被金山的 HR 夸了一下）。进来一个技术老师哥们，我一看英文名牛逼啊。但是老师让我介绍一下三维重建的历史，说“听说了 VGGT 这个很火的模型，但是让我介绍下”，后来的种种包括 3DGS/4DGS 老师都不是很清楚，一直把 3D 理解成 4D，让我其实心里有点不爽。感觉不是很懂技术，甚至说是不懂 3D。因为西山居和商汤的老师都挺懂的所以交流起来没太多障碍。不出所料还是过了技术面，能接受我一周只 on-cite 三天，有一点房补但不多。一个比较闹心的事情是，HR 弄错了我的学历。开始问我期望薪资，我随口报了个xx公司是 a00-b00 / d （乱编的），她说普渡比这个多。当时有点心花怒放，并且因为一个乌龙（等会儿说）就更加开心了，打算等会儿就接了。结果这姐们跟我说发现我是本科生，本科生他们公司统一价格（我的课时费的2/5你们就猜吧）。一来有点少了（按实际到岗天数算），二来感觉技术老师不怎么懂可能学不到东西，遂婉拒跑路。不过 HR 其实也挺好的，当时我说我想考虑下，征求一下老师的意见，她就说等我这边消息，“这边就先不同步其他人啦”。感觉到有被重视。所以想去做具身智能的xdm也可考虑一下普渡。一些不叼我的公司同花顺：做金融的，只看 OI 奖项。问我大学为什么不打 ACM，回了他要做研究之后没下文。没品位，拉。小米：也是要求高，不叼我。拉完了字节跳动：是夯的公司但是投了 Seed 的 Edge 没下文，看不上我就是拉完了小马智行：拉文远知行：说要的是校招。拉美团：已读不回。拉深信服：拉松延动力：昌平乡下，给的少；拉Momenta：说实习期短了，地点不是很行。NPC 吧小鹏：投一万个智驾岗位，给的那么少还不叼我，如果不是欧阳娜娜是最近的Mona的代言人，直接给到一个拉完了。给个 NPC高德地图：说要做 WAM，不匹配。NPC 吧汤元科技：其实这个不错但是要on-cite，NPC吧一些可能 In-Process 但是暂时没下文为什么有这一栏，请看等会儿的地平线。卓驭。没下文，拉蔚来：纯为了嘲讽。我就想问，我要进蔚来了，请问是高了还是低了？审了半个月都没动静，拉先临三维：做隐适美口扫的。拉地平线这个比较有说法，感恩说是。Update 20270730现在是 7 月 30 号晚的凌晨，写一下上次面试吧。跟金山西山居和阿里的情况差不多，就是来面我的人也没有特别懂我做的所有方向（当然这是大部分情况）。我觉得一个比较实在的说法是，由于大部分人并没有正儿八经通过一个课程来学习 3D 相关的知识，因此都是从文章来反过来学所需要的 3D 知识的。对于我所说到的一些东西，可能他们没听过就是懵的。这就是 vv 说的：学养深厚。哈哈哈。不乱吹水。总之面的比较愉快，一个小插曲是技术面的老师让我手写快排，但是我手上只有 vscode 还装了 copilot，我敲的已经很快了但是 copilot 的 tab 补全速度还是太夸张。遂改成我解释快排原理并且给老师随便讲了一下 3 Medians 来稳定快排复杂度（显然他还是没有听说过）。昨天下午 HR 说一面过了，还要约个二面。地平线是截至目前我接触到的唯一一个实习生还要二面的公司。应该就是这两天，到时候再更新吧。Update 2026.8.14: 中间经过了一些很奇妙的事情，本来想收回对米子的差评的，但现在看来没机会了。那么，地平线见！
既然是自己随便写着玩的东西，就没有必要分结构的标题了。现在回想起之前的游记，确实是充满了高中生独有的活力。由于成日被锁在学校里，精神实际上也有一把隐形的锁，导致任何一次出游都是兴奋和期待的，因为再稀疏平常的东西换个地方见到，都会觉得十分新奇十分有意思。然而后知后觉才意识到，所谓“丰富阅历”，最重点的是“丰富”的这个过程，因为一旦丰富了以后，世界就变得无聊了。想起来生活又何尝不能是是做一次 "training"，本质上是 loss 在早期快速收敛（理想情况下），后面慢慢变得十分平缓，最后趋于收敛。什么东西都见过以后，就会”见怪不怪“，遂也没了梯度。本来今天已经是旅行的最后一天了，就在几个小时前回酒店的路上，想起来要写下点什么，现在就已经不记得了。看来成为一个合格的旅行作家，还有很长的路要走。真佩服他们。其实所谓之游记，大概也是一种流水账。鉴于本人的记性一般，很多东西也是有感而发，遂采用想到哪写到哪的方式，今天写一笔，明天添一笔。希望日后再点开的时候有新的感悟，就能加进来。今天是7月2日，星期四，的凌晨。感觉每次旅行结束的后劲都是比较大的，这一次真还挺大的。昨天，其实是前天了，先从汕尾开到东莞把楼放在华子准备实习了，然后又一路到深圳，跟 NUS 大师兄吃个饭然后关桑也回家了，剩下我和tosaka。昨天中午跟 Jackson 再一起吃了个饭，下午打了一下午电动，晚上tosaka就回杭州了，最后只有我一个人开回珠海。一路上一点点人下车，一步步变冷清，遂感到荒凉和委屈。也许这也是成长的阵痛的一种吧。现在回想起来，最开始对这次旅行的珍视程度还是不够。我们这个四个人，去年暑假也是在一起赶ddl，其实现在想起来，是一段很美好的时光。有一个纯粹的，近在眼前的目标，AAAI，然后遇到了各种情况，在 ddl 的催促下，每天12点醒，5点睡，只吃得上一顿饭。那种很纯粹很美好的时光，我想以后很难再有了。更何况天下无不散的筵席，关桑去美国读 PhD 了，实验室的其他小伙伴也有好多人毕业了，大家都有光明的未来。故而我们四个这辈子也不会有挤在实验室一起做事的经历了（很难）。再者，哪怕抛开这些因素，这是一次说走就走的旅行，21号大家说gogogo，其实第一天都已经在高速上了连酒店都还没有订。这是不是也是一种 Grand Turismo.
总结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咕咕咕