INCOMING TRANSMISSION

160. 相交链表 题目 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交 ： 题目数据 保证 整个链式结构中不存在环。 注意 ，函数返回结果后，链表必须 保持其原始结构 。 自定义评测： 评测系统 的输入如下（你设计的程序 不适用 此输入）： intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。 示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2,...

48. 旋转图像 题目 给定一个 \(n × n\) 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]] 示例 2： 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] 提示： n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 题解 这是一个经典的矩阵操作问题。要在原地（In-place）将图像顺时针旋转 90 度，我们可以利用矩阵的几何性质。 最直观且易于实现的方法是将...

11. 盛最多水的容器 题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明： 你不能倾斜容器。 示例 1： 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例 2： 输入：height = [1,1] 输出：1 提示： n == height.length 2 <= n <= 10 5 0 <= height[i] <= 10 4 题解 在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为 \(min(1,7)∗8=8\) 。 此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由 两个指针指向的数字中较小值∗指针之间的距离...

如果把 近几年对比学习在视觉领域有代表性的工作做一下总结，那么对比学习的发展历程大概可以分为四个阶段： 百花齐放 这个阶段代表性工作有InstDisc（instance discrimination，）、CPC、CMC等。在这个阶段中，方法、模型、目标函数、代理任务都还没有统一，所以说是一个百花齐放的时代 CV双雄 代表作有MoCo v1、SimCLR v1、MoCo v2、SimCLR v2；CPC、CMC的延伸工作、SwAV等。这个阶段发展非常迅速，有的工作间隔甚至不到一个月，ImageNet上的成绩基本上每个月都在被刷新。 不用负样本 BYOL及其改进工作、SimSiam（CNN在对比学习中的总结性工作） transformer MoCo v3、DINO。这个阶段，无论是对比学习还是最新的掩码学习，都是用Vision Transformer做的。 第一阶段：百花齐放（2018-2019Mid） InstDisc（instance discrimination） 这篇文章提出了个体判别任务（代理任务）以及 memory bank ，非常经典，后人给它的方法起名为InstDisc。...

DINO Emerging Properties in Self-Supervised Vision Transformers 论文地址： arxiv.org/pdf/2104.14294 DINO摇摆到了动量式更新，果然【加动量】还是比【只用梯度停止】香。DINO的名字来自于Self- di stillation with no labels中的蒸馏和No标签。 DINO的训练步骤 其实以前的对比学习方案也可以理解为知识蒸馏，DINO里更具体得描述了知识蒸馏的含义。 下图展示了一个样本通过数据增强得到一对views \((x_1,x_2)\) 。注意DINO后面还会使用更复杂的裁剪和对比方案，但这里简单起见先不考虑那些。模型将输入图像的两种不同的随机变换 \(x_1\) 和 \(x_2\) 分别传递给学生和教师网络。 这两个网络具有相同的架构，但参数不同 。教师网络的输出以batch内计算的平均值，进行中心化（减去均值）。每个网络输出一个 \(K\)...

Self-Supervised Learning ，又称为自监督学习，我们知道一般机器学习分为有监督学习，无监督学习和强化学习。 而 Self-Supervised Learning 是无监督学习里面的一种，主要是希望能够学习到一种 通用的特征表达 用于 下游任务 (Downstream Tasks) 。 其主要的方式就是通过自己监督自己。作为代表作的 kaiming 的 MoCo 引发一波热议， Yann Lecun也在 AAAI 上讲 Self-Supervised Learning 是未来的大势所趋。所以在这个系列中，我会系统地解读 Self-Supervised Learning 的经典工作。 总结下 Self-Supervised Learning 的方法，用 4 个英文单词概括一下就是： Unsupervised Pre-train, Supervised Fine-tune. 这段话先放在这里，可能你现在还不一定完全理解，后面还会再次提到它。 在预训练阶段我们使用 无标签的数据集 (unlabeled data) ，因为有标签的数据集 很贵...

总结下 Self-Supervised Learning 的方法，用 4 个英文单词概括一下就是： Unsupervised Pre-train, Supervised Fine-tune. 在预训练阶段我们使用 无标签的数据集 (unlabeled data) ，因为有标签的数据集 很贵 ，打标签得要多少人工劳力去标注，那成本是相当高的，所以这玩意太贵。相反，无标签的数据集网上随便到处爬，它 便宜 。在训练模型参数的时候，我们不追求把这个参数用带标签数据从 初始化的一张白纸 给一步训练到位，原因就是数据集太贵。于是 Self-Supervised Learning 就想先把参数从 一张白纸 训练到 初步成型 ，再从 初步成型 训练到 完全成型 。注意这是2个阶段。这个 训练到初步成型的东西 ，我们把它叫做 Visual Representation 。预训练模型的时候，就是模型参数从 一张白纸 到 初步成型 的这个过程，还是用无标签数据集。等我把模型参数训练个八九不离十，这时候再根据你 下游任务 (Downstream Tasks) 的不同去用带标签的数据集把参数训练到 完全成型...

补充知识 表示学习 （Representation Learning）： 学习数据的表征，以便在构建分类器或其他预测器时更容易提取有用的信息 ，无监督学习也属于表示学习。 互信息 （Mutual Information）：表示两个变量 \(X\) 和 \(Y\) 之间的关系，定义为： \[I(X;Y)=\sum_{x\in X}\sum_{y\in Y}p(x,y)log\frac{p(x|y)}{p(x)}\] 对比损失(contrastive loss) ：计算成对样本的匹配程度，主要用于降维中。计算公式为： \[L=\frac{1}{2N}\sum_{n-1}^N[yd^2+(1-y)max(margin-d, 0)^2]\] 其中, \(d=\sqrt{(a_n-b_n)^2}\) 为两个样本的欧式距离， \(y=\{0,1\}\) 代表两个样本的匹配程度， \(margin\) 代表设定的阈值。这种损失函数可以很好的表达成对样本的匹配程度，也能够很好用于训练提取特征的模型。当 \( y=1\) （即样本相似）时，损失函数只剩下 \(∑d^2\)...

从 NLP 入手 n-gram 语言模型（language model）就是假设一门语言所有可能的句子服从一个概率分布，每个句子出现的概率加起来是1，那么语言模型的任务就是预测每个句子在语言中出现的概率。如果把句子 \(s\) 看成单词 \(w\) 的序列 \(s=\{w_1,w_2,...,w_m\}\) ，那么语言模型就是建模一个 \(p(w_1,w_2,...,w_m)\) 来计算这个句子 \(s\) 出现的概率，直观上我们要得到这个语言模型，基于链式法则可以表示为每个单词出现的条件概率的乘积，我们将条件概率的条件 \((w_1,w_2,...,w_{i-1})\) 称为单词 \(w_i\) 的上下文，用 \(c_i\) 表示。 \[\begin{aligned} p\left(w_{1}, w_{2}, \ldots, w_{m}\right)&=p\left(w_{1}\right) * p\left(w_{2} \mid w_{1}\right) * p\left(w_{3} \mid w_{1}, w_{2}\right) \ldots p\left(w_{m}...

数组&链表&字符串 双指针 滑动窗口 哈希表 哈希表 栈&队列 单调队列 树与堆 图 数学 Math

2022年中旬，以扩散模型为核心的图像生成模型将AI绘画带入了大众的视野。实际上，在更早的一年之前，就有了一个能根据文字生成高清图片的模型——VQGAN。VQGAN不仅本身具有强大的图像生成能力，更是传承了前作VQVAE把图像压缩成离散编码的思想，推广了「先压缩，再生成」的两阶段图像生成思路，启发了无数后续工作。 VQGAN 核心思想 VQGAN的论文名为 Taming Transformers for High-Resolution Image Synthesis，直译过来是「驯服Transformer模型以实现高清图像合成」。可以看出，该方法是在用Transformer生成图像。可是，为什么这个模型叫做VQGAN，是一个GAN呢？这是因为，VQGAN使用了两阶段的图像生成方法： 训练时，先训练一个图像压缩模型（包括编码器和解码器两个子模型），再训练一个生成压缩图像的模型。 生成时， 先用第二个模型生成出一个压缩图像，再用第一个模型复原成真实图像 。 其中，第一个图像压缩模型叫做VQGAN，第二个压缩图像生成模型是一个基于Transformer的模型。...

本文受启发于著名的国外博文 《Wasserstein GAN and the Kantorovich-Rubinstein Duality》 ，内容跟它大体上相同，但是删除了一些冗余的部分，对不够充分或者含糊不清的地方作了补充。 Wasserstein距离 显然，整篇文章必然围绕着Wasserstein距离（ \(\mathcal{W}\) 距离）来展开。假设我们有了两个概率分布 \(p(x),q(x)\) ，那么Wasserstein距离的定义为 \[\mathcal{W}[p,q]=\inf_{\gamma\in \Pi[p,q]} \iint \gamma(\boldsymbol{x},\boldsymbol{y}) d(\boldsymbol{x},\boldsymbol{y}) d\boldsymbol{x}d\boldsymbol{y}\] 事实上，这也算是最优传输理论中最核心的定义了。 成本函数 首先 \(d(x,y)\) ，它不一定是距离，其准确含义应该是一个成本函数，代表着从 \(x\) 运输到 \(y\) 的成本。常用的 \(d\) 是基于 \(l\)...