INCOMING TRANSMISSION

题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2. Example: [代码] Constraints: 10^9 <= nums1[i], nums2[i] <...

Overview 特征工程是机器学习流程中重要的一个环节，即使是通常用来做端到端学习的深度学习模型在训练之前也免不了要做一些特征工程相关的工作。Tensorflow平台提供的FeatureColumn API为特征工程提供了强大的支持。 Feature cloumns是原始数据和Estimator模型之间的桥梁，它们被用来把各种形式的原始数据转换为模型能够使用的格式。深度神经网络只能处理数值数据，网络中的每个神经元节点执行一些针对输入数据和网络权重的乘法和加法运算。然而，现实中的有很多非数值的类别数据，比如产品的品牌、类目等，这些数据如果不加转换，神经网络是无法处理的。另一方面，即使是数值数据，在仍给网络进行训练之前有时也需要做一些处理，比如标准化、离散化等。 在Tensorflow中，通过...

DFS

1. explode hive wiki对于expolde的解释如下： explode() takes in an array (or a map) as an input and outputs the elements of the array (map) as separate rows. UDTFs can be used in the SELECT expression list and as a part of LATERAL VIEW. As an example of using explode() in the SELECT expression list, consider a table named myTable that has a single column (m...

TFRecord TFRecord 是谷歌推荐的一种二进制文件格式，理论上它可以保存任何格式的信息。 tf.Example是一个Protobuffer定义的message，表达了一组string到bytes value的映射。TFRecord文件里面其实就是存储的序列化的tf.Example。关于Protobuffer参考Protobuf 终极教程。 example 我们可以具体到相关代码去详细地看下tf.Example的构成。作为一个Protobuffer message，它被定义在文件core/example/example.proto中： [代码] 只是包了一层Features的message。我们还需要进一步去查找Features的message定义： [代码] 到这里，我们可以看出...

计算几何（Computational Geometry），是一系列使用计算机解决几何问题的算法。与解析几何相比，计算几何更适合计算机运算，精度较高，运算速度较快，并且易于编写。 浮点误差 程序设计中，考虑到浮点数 double 有精度误差，在比较时，通常允许一定的误差，即对于两个数 a 、 b ，如果 [Math] ，则认为 a=b 。一般根据题目要求， d （代码中命名为 EPS）取一个较小值，如 10^{8} 。 [代码] 向量 向量（vector）是一个有大小和方向的量，在几何中，它被表示为带箭头的线段。向量可以用起点和终点的坐标来表示 —— 从点 A到点B 的向量表示为 [Math] 。 向量的书写，两个大写字母上加一个箭头（表示方向） [Math] 向量没有位置，即向量可以在平面内...

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

题目 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。 如果数组元素个数小于 2，则返回 0。 Example 1: [代码] 解题思路：如果进行排序，这里会超时。采用桶排序 排序算法 的思想，可以在线性时间解决。 1. 首先建立桶，每个桶中只需要存放这个桶中元素的最大值和最小值。 1. 我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同，也就是对于所有桶来说，桶内最大值减去桶内最小值都是一样的。可以当成公式来记。 1. 确定桶的数量，最后的加一保证了数组的最大值也能分到一个桶。为什么需要这样规定桶的尺寸呢？因为这样可以让最大的间距的两个元素在两个不同的桶中。可以证明一下，因为我们用元素范围之差除以元素个数，所以桶的尺寸就是平均的元素间距，显然最大间距的两个元素不可能...

1. 可以重复选取 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 画出树状搜索图如下， 为了去除重复的情况， 我们需要按照某种顺序搜索，具体做法是：每一次搜索的时候，设置下一轮搜索的起点 [代码] 2. 不能被重复选取 与上面的区别在于 1. index每次不要重复搜索，而是去寻找下一个 1. 排除重复的元素 [代码]

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