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] ： 右移扩大 ：不断移动...
Reinforcement Learning
2026-01-11
引言与背景 蒙特卡洛方法是强化学习中的重要算法类别，它标志着从基于模型到无模型算法的转变。这类算法不依赖环境模型，而是通过与环境的直接交互获取经验数据来学习最优策略。 蒙特卡洛方法在强化学习算法谱系中处于"无模型"方法的起始位置，是从基于模型的方法（如值迭代和策略迭代）向无模型方法过渡的第一步。 无模型强化学习的核心理念可以简述为：如果没有模型，我们必须有数据；如果没有数据，我们必须有模型；如果两者都没有，我们就无法找到最优策略。在强化学习中，"数据"通常指智能体与环境交互的经验。 均值估计问题 在介绍蒙特卡洛强化学习算法之前，我们首先需要理解均值估计问题，这是理解从数据而非模型中学习的基础。 考虑一个可以取有限实数集合 X 中值的随机变量 X ，我们的任务是计算 X 的均值或期望值： E[...
Large Model
2026-01-11
引言与背景 FlashAttention的关键创新在于使用类似于在线Softmax的思想来对自注意力计算进行分块（tiling），从而能够融合整个多头注意力层的计算，而无需访问GPU全局内存来存储中间的logits和注意力分数 在深度学习中，Transformer模型的自注意力机制是计算密集型操作。传统实现需要在GPU全局内存中存储大量中间结果，这导致： 内存瓶颈：中间矩阵占用大量显存 I/O开销：频繁的全局内存访问降低效率 扩展性限制：难以处理超长序列 FlashAttention通过算法创新解决了这些问题。 SelfAtention 自注意力机制的计算可以总结为（为简化说明，忽略头数和批次维度，也省略注意力掩码和缩放因子 [Math] ）： [公式] 其中： Q, K, V, O 都是形...
Reinforcement Learning
2026-01-11
引言 DDPG同样使用了ActorCritic的结构，Deterministic的确定性策略是和随机策略相对而言的，对于某一些动作集合来说，它可能是连续值，或者非常高维的离散值，这样动作的空间维度极大。如果我们使用随机策略，即像DQN一样研究它所有的可能动作的概率，并计算各个可能的动作的价值的话，那需要的样本量是非常大才可行的。于是有人就想出使用确定性策略来简化这个问题。 作为随机策略，在相同的策略，在同一个状态 s 处，采用的动作 [Math] 是基于一个概率分布的，即是不确定的。而确定性策略则决定简单点，虽然在同一个状态处，采用的动作概率不同，但是最大概率只有一个，如果我们只取最大概率的动作，去掉这个概率分布，那么就简单多了。即作为确定性策略，相同的策略，在同一个状态处，动作是唯一确定的...
Reinforcement Learning
2026-01-11
引言与背景 价值函数方法是强化学习中的核心技术，它解决了传统表格方法在处理大型状态或动作空间时的效率问题。本文探讨了从表格表示向函数表示的转变，这是强化学习算法发展的重要里程碑。 在强化学习的发展路径中，价值函数方法位于从基于模型到无模型、从表格表示到函数表示的演进过程中。它结合了时序差分学习的思想，并通过函数近似技术来处理复杂环境。 价值表示：从表格到函数 表格与函数表示的对比 传统的表格方法将状态值存储在一个表格中： 而函数近似方法则使用参数化函数来表示这些值，例如： [公式] 其中 [Math] 称作是状态 s 的特征向量， w 是参数向量。 两种不同的表现形式的区别主要体现在以下几个方面： 值的检索方式 值的更新方式 函数复杂度与近似能力 函数的复杂度决定了其近似的能力： 一阶线性函...
Large Model
2026-01-11
通常我们训练神经网络模型的时候默认使用的数据类型为单精度FP32。近年来，为了加快训练时间、减少网络训练时候所占用的内存，并且保存训练出来的模型精度持平的条件下，业界提出越来越多的混合精度训练的方法。这里的混合精度训练是指在训练的过程中，同时使用单精度（FP32）和半精度（FP16）。 浮点数据类型 浮点数据类型主要分为双精度（FP64）、单精度（FP32）、半精度（FP16）。在神经网络模型的训练过程中，一般默认采用单精度（FP32）浮点数据类型，来表示网络模型权重和其他参数。在了解混合精度训练之前，这里简单了解浮点数据类型。 根据IEEE二进制浮点数算术标准（IEEE 754）的定义，浮点数据类型分为双精度（FP64）、单精度（FP32）、半精度（FP16）三种，其中每一种都有三个不同的...
Reinforcement Learning
2026-01-11
概述与理论背景 ActorCritic方法是强化学习中的一类重要算法，它巧妙地结合了基于策略(policybased)和基于价值(valuebased)的方法。在这种结构中，"Actor"指策略更新步骤，负责根据策略执行动作；而"Critic"指价值更新步骤，负责评估Actor的表现。从另一个角度看，ActorCritic方法本质上仍是策略梯度算法，可以通过扩展策略梯度算法获得。 ActorCritic方法在强化学习中的位置非常重要，它既保留了策略梯度方法直接优化策略的优势，又利用了值函数方法的效率。这种结合使得ActorCritic方法成为解决复杂强化学习问题的强大工具。 最简单的ActorCritic算法(QAC) QAC算法通过扩展策略梯度方法得到。策略梯度方法的核心思想是通过最大化标...
Large Model
2026-01-11
概述 Kimi k1.5采用了一种简化而有效的强化学习框架，其核心在于长上下文扩展和改进的策略优化方法，而不依赖于更复杂的技术如蒙特卡洛树搜索、价值函数和过程奖励模型。 问题设定 给定训练数据集 D = \{(x_i, y^_i)\}_{i=1}^n ，其中包含问题 x_i 和对应的真实答案 y^_i ，目标是训练一个策略模型 [Math] 来准确解决测试问题。在复杂推理场景中，思维链(CoT)方法提出使用一系列中间步骤 z = (z_1, z_2, ..., z_m) 来连接问题 x 和答案 y ，每个 z_i 是解决问题的重要中间步骤。 当解决问题 x 时，思维 [Math] 被自回归采样，最终答案 [Math] 。 强化学习目标 基于真实答案 y^ ，分配一个值 [Math] , Ki...
💡 引言 Trust Region Policy Optimization (TRPO) 是2015年的ICML会议上提出的一种强大的基于策略的强化学习算法。TRPO 解决了传统策略梯度方法中的一些关键问题，特别是训练不稳定和步长选择困难的问题。与传统策略梯度算法相比，TRPO 具有更高的稳健性和样本效率，能够在复杂环境中取得更好的性能。 优化基础 在深入了解 TRPO 之前，我们需要先简单回顾一些优化方法的基础知识。 梯度上升法 梯度上升法是一种迭代优化算法，用于寻找函数的局部最大值。 目标：找到使目标函数 [Math] 最大化的参数 [Math] ： [公式] 梯度上升迭代过程： 1. 在当前参数 [Math] 处计算梯度： [Math] 1. 更新参数： 梯度上升法的主要问题是学习率的...
Large Model
2026-01-11
概述 Medusa 是自投机领域较早的一篇工作，对后续工作启发很大，其主要思想是 multidecoding head + tree attention + typical acceptance(threshold)。Medusa 没有使用独立的草稿模型，而是在原始模型的基础上增加多个解码头（MEDUSA heads），并行预测多个后续 token。 正常的LLM只有一个用于预测 t 时刻token的head。Medusa 在 LLM 的最后一个 Transformer层之后保留原始的 LM Head，然后额外增加多个（假设是 k 个） 可训练的Medusa Head（解码头），分别负责预测 ...
Reinforcement Learning
2026-01-11
引言 时序差分（TemporalDifference，TD）方法是强化学习中的一类核心算法，它结合了动态规划与蒙特卡洛方法的优点。TD方法是无模型（modelfree）学习方法，不需要环境模型即可学习价值函数和最优策略。 TD方法的核心特点是通过比较不同时间步骤的估计值之间的差异来更新价值函数，这种差异被称为"时序差分误差"（TD error）。TD方法可以被视为解决贝尔曼方程或贝尔曼最优方程的特殊随机逼近算法。 基础TD算法：状态值函数学习 给定策略 [Math] ，基础TD算法用于估计状态值函数 [Math] 。假设我们有一些按照策略 [Math] 生成的经验样本 (s_0, r_1, s_1, ..., s_t, r_{t+1}, s_{t+1}, ...) ，TD算法的更新规则为： ...
Large Model
2026-01-11
概述 MTP（Multitoken Prediction）的总体思路是：让模型使用n个独立的输出头来预测接下来的n个token，这n个独立的输出头共享同一个模型主干。这样通过解码阶段的优化，将1token的生成，转变成multitoken的生成，从而提升训练和推理的性能。 在DeepSeek之前也有几个MTP方案，其侧重点各自不同。 侧重推理时解码加速。比如论文“MEDUSA: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads”、论文“EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty”等。这些方案通过一次生成多个...