INCOMING TRANSMISSION

76. 最小覆盖子串 题目 给定两个字符串 s 和 t ，长度分别是 m 和 n ，返回 s 中的 最短窗口 子串 ，使得该子串包含 t 中的每一个字符（ 包括重复字符 ）。如果没有这样的子串，返回空字符串 "" 。 测试用例保证答案唯一。 示例 1： 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。 示例 2： 输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。 示例 3: 输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。 提示： m == s.length n == t.length 1 <= m, n <= 10 5 s 和 t 由英文字母组成 题解 这是一个经典的 滑动窗口 (Sliding Window) 问题 我们需要维护一个动态的窗口 [left, right] ： 右移扩大 ：不断移动...

进程 一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间，一个进程可以有多个线程，比如在Windows系统中，一个运行的xx.exe就是一个进程。 线程 进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据。 与进程不同的是同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间作切换工作时，负担要比进程小得多，也正因为如此，线程也被称为轻量级进程。 Java 程序天生就是多线程程序，我们可以通过 JMX 来看一下一个普通的 Java 程序有哪些线程，代码如下。 [代码] 上述程序输出如下（输出内容可能不同，不用太纠结下面每个线...

UITARS 简介 UITARS（User Interface Task Automation and Reasoning System）是由字节跳动（ByteDance）研发的原生 GUI 智能体模型： 输入方式：仅使用屏幕截图作为视觉输入 交互方式：执行类人操作（键盘输入、鼠标点击、拖拽等） 模型特性：端到端的原生智能体模型，无需复杂的中间件或框架 传统 GUI 智能体的开发往往依赖于文本信息，例如 HTML 结构和可访问性树。虽然这些方法取得了一些进展，但它们也存在一些局限性： 平台不一致性：不同平台的 GUI 结构差异很大，导致智能体难以跨平台通用。 信息冗余：文本信息往往过于冗长，增加了模型的处理负担。 访问限制：获取系统底层的文本信息通常需要较高的权限，限制了应用的范围。 模块化...

摘掉Softmax 制约Attention性能的关键因素，其实是定义里边的Softmax！事实上，简单地推导一下就可以得到这个结论。 [Math] 这一步我们得到一个 [Math] 的矩阵，就是这一步决定了Attention的复杂度是 [Math] ；如果没有Softmax，那么就是三个矩阵连乘 [Math] ，而矩阵乘法是满足结合率的，所以我们可以先算 [Math] ，得到一个 [Math] 的矩阵，然后再用 [Math] 左乘它，由于 [Math] ，所以这样算大致的复杂度只是 [Math] （就是 [Math] 左乘那一步占主导）。 也就是说，去掉Softmax的Attention的复杂度可以降到最理想的线性级别 [Math] ！这显然就是我们的终极追求：Linear Attentio...

概述 本文介绍一个比较有意思的高效Transformer工作——来自Google的《Transformer Quality in Linear Time》，经过细读之后，笔者认为论文里边真算得上是“惊喜满满”了～ 什么样的结果值得我们用“惊喜”来形容？有没有言过其实？我们不妨先来看看论文做到了什么： 1. 提出了一种新的Transformer变体，它依然具有二次的复杂度，但是相比标准的Transformer，它有着更快的速度、更低的显存占用以及更好的效果； 1. 提出一种新的线性化Transformer方案，它不但提升了原有线性Attention的效果，还保持了做Decoder的可能性，并且做Decoder时还能保持高效的训练并行性。 说实话，笔者觉得做到以上任意一点都是非常难得的，而这篇论...

概述 SSM的概念由来已久，但这里我们特指深度学习中的SSM，一般认为其开篇之作是2021年的 S4，不算太老，而SSM最新最火的变体大概是Mamba。当然，当我们谈到SSM时，也可能泛指一切线性RNN模型，这样RWKV、RetNet还有此前LRU都可以归入此类。不少SSM变体致力于成为Transformer的竞争者，尽管笔者并不认为有完全替代的可能性，但SSM本身优雅的数学性质也值得学习一番。 尽管我们说SSM起源于S4，但在S4之前，SSM有一篇非常强大的奠基之作《HiPPO: Recurrent Memory with Optimal Polynomial Projections》（简称HiPPO），所以本文从HiPPO开始说起。 另外值得一提的是，SSM代表作HiPPO、S4、Mam...

分布式深度学习里的通信严重依赖于规则的集群通信，诸如 allreduce, reducescatter, allgather 等，因此，实现高度优化的集群通信，以及根据任务特点和通信拓扑选择合适的集群通信算法至关重要。 本文以数据并行经常使用的 allreduce 为例来展示集群通信操作的数学性质。 Allreduce 在干什么？ 如图 1 所示，一共 4个设备，每个设备上有一个矩阵（为简单起见，我们特意让每一行就一个元素），allreduce 操作的目的是，让每个设备上的矩阵里的每一个位置的数值都是所有设备上对应位置的数值之和。 如图 2 所示， allreduce 可以通过 reducescatter 和 allgather 这两个更基本的集群通信操作来实现。基于 ring 状通信可以高...

概述 众所周知，尽管基于Attention机制的Transformer类模型有着良好的并行性能，但它的空间和时间复杂度都是 [Math] 级别的， n 是序列长度，所以当 n 比较大时Transformer模型的计算量难以承受。近来，也有不少工作致力于降低Transformer模型的计算量，比如模型剪枝、量化、蒸馏等精简技术，又或者修改Attention结构，使得其复杂度能降低到 [Math] 甚至 [Math] 。 改变这一复杂度的思路主要有两种： 一是走稀疏化的思路，比如OpenAI的Sparse Attention，通过“只保留小区域内的数值、强制让大部分注意力为零”的方式，来减少Attention的计算量。经过特殊设计之后，Attention矩阵的大部分元素都是0，因此理论上它也能节...

Preformer Performer的出发点还是标准的Attention，所以在它那里还是有 [Math] ，然后它希望将复杂度线性化，那就是需要找到新的 [Math] ，使得： [公式] 如果找到合理的从 [Math] 到 [Math] 的映射方案，便是该思路的最大难度了。 激活函数 线性Attention的常见形式如 式3，其中 [Math] 、 [Math] 是值域非负的激活函数。那么如何选取这个激活函数呢？Performer告诉我们，应该选择指数函数 [公式] 首先，我们来看它跟已有的结果有什么不一样。在 Transformers are RNNs 给出的选择是： [公式] 我们知道 1+x 正是 e^x 在 x=0 处的一阶泰勒展开，因此 [Math] 这个选择其实已经相当接近 ...

简介 承接 Transformers are RNNs 这篇论文 目的： 为了分析之前linear transformer的效果为什么不好。发现主要是两个原因造成的： 1. 无界梯度（unbounded gradient），会导致模型在训练时不稳定，收敛不好； 1. 注意力稀释（attention dilution），transformer在lower level时应该更关注局部特征，而higher level更关注全局特征，但线性transformer中的attention往往weight 更均匀化，不能聚焦在local区域上，因此称为attention稀释。 解决方案： 1. 对linear attention算出来的output接着做个normalization，形成NormForme...