INCOMING TRANSMISSION

128. 最长连续序列 题目 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1： 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9 示例 3： 输入：nums = [1,0,1,2] 输出：3 提示： 0 <= nums.length <= 10 5 -10 9 <= nums[i] <= 10 9 题解 我们需要在 \(O(1)\) 的时间内查找某个数是否存在。因此，首先将数组中的所有元素放入一个 HashSet 中。这不仅能去重，还能支持快速查找。 避免冗余计算 (关键优化) 如果我们对集合中的每一个数都尝试去向后计数（例如，对于 x ，尝试找 x+1 , x+2 ...），最坏情况下的时间复杂度会退化到 \(O(n^2)\) 。 优化策略 ： 我们 只从序列的起点开始计数 。...

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] ： 右移扩大 ：不断移动...

简介 EfficientNet源自Google Brain的论文EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. 从标题也可以看出，这篇论文最主要的创新点是Model Scaling. 论文提出了compound scaling，混合缩放，把网络缩放的三种方式：深度、宽度、分辨率，组合起来按照一定规则缩放，从而提高网络的效果。EfficientNet在网络变大时效果提升明显，把精度上限进一步提升，成为了当前最强网络。EfficientNetB7在ImageNet上获得了最先进的 84.4%的top1精度 和 97.1%的top5精度，比之前最好的卷积网络（GPipe, Top1: 84.3%, ...

摘掉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...

💡 轻量级网络系列 Introduction Inception 在最初的版本 Inception/GoogleNet，其核心思想是利用多尺寸卷积核去观察输入数据。举个栗子，我们看某个景象由于远近不同，同一个物体的大小也会有所不同，那么不同尺度的卷积核观察的特征就会有这样的效果。于是就有了如下的网络结构图： 于是我们的网络就变胖了，通过增加网络的宽度，提高了对于不同尺度的适应程度。但这样的话，计算量有点大了。 Pointwise Conv 为了减少在上面结构的参数量并降低计算量，于是在 Inception V1 的基础版本上加上了 1x1 卷积核，这就形成了 Inception V1 的最终网络结构，如下图。 这个 1x1 卷积就是 Pointwise Convolution，简称 PW。利...

网络整体介绍 ThunderNet的整体架构如下图所示。 ThunderNet使用320×320像素作为网络的输入分辨率。整体的网络结构分为两部分：Backbone部分和Detection部分。网络的骨干部分为SNet，SNet是基于ShuffleNetV2进行修改得到的。 网络的检测部分，利用了压缩的RPN网络，修改自LightHead RCNN网络用以提高效率。 并提出Context Enhancement Module整合局部和全局特征增强网络特征表达能力。 并提出Spatial Attention Module空间注意模块，引入来自RPN的前后景信息用以优化特征分布。 backbone 部分 1.输入分辨率 为了加快推理（前向操作）速度，作者使用320320大小的输入图像。需要注意的...

概述 众所周知，尽管基于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...