Liuyi Wen's Blog

该篇为《算法导论》学习笔记，包含部分章节的理论阐释、典型问题、和代码实现。 算法 时间复杂度 1.渐近符号： θ--渐近紧确界； f(n)=θ(g(n)):g(n)是f(n)的渐进紧确界. 定义:存在c1,c2,n0,对任意n>=n0,有：0<=c1g(n)<=f(n)<=c2g(n). f(n)=θ(g(n)),当且仅当:f(n)=O(g(n))且f(n)=欧姆. O--渐近上界；[欧姆]--渐近下界 o--非紧确渐近上界；ω--非紧确渐近下界 f(n)=O(g(n))中,0<=f(n)<cg(n)对某个常量c>0成立； f(n)=o(g(n))中,0<=f(n)<cg(n)对所有常量c>0成立. 2.主定理求时间复杂度: T(n)=aT(n/b)+f(n). 比较n1和f(n):选择多项式意义上更大的。 1.f(n)=O(n(logb(a)-ε)),则:T(n)=θ(n(logb(a)). 2.f(n)=0(n(logb(a))),则:T(n)=θ(n(logb(a)lgn)....

该平台为北航2024年秋暑期软件工程实践项目。 CICD部署 (function(){var player = new DPlayer({"container":document.getElementById("dplayer0"),"theme":"#FADFA3","loop":true,"video":{"url":"/posts/8b715a29/4-CICD.mp4","pic":"1.png"}});window.dplayers||(window.dplayers=[]);window.dplayers.push(player);})() 降级服务 (function(){var player = new...

该平台为北航2024年秋软件系统分析与设计课程团队项目，致谢我的9位伙伴们，和Bug-捉迷藏小组。 平台演示 (function(){var player = new DPlayer({"container":document.getElementById("dplayer3"),"theme":"#FADFA3","loop":true,"video":{"url":"/posts/39315f07/1.mp4","pic":"1.png"}});window.dplayers||(window.dplayers=[]);window.dplayers.push(player);})() 系统架构图 alt text

...

该篇摘自The Ultra-Scale Playbook: Training LLMs on GPU Clusters. 在单个GPU上训练 在单个GPU上训练，通常包括三个步骤： 1. forward pass：将输入传入模型，产生输出； 2. backward pass：计算梯度； 3. optimization：使用梯度更新参数。 batch size的影响 超参数batch size：小的batch size在训练初期有助于快速完成训练过程，达到一个较优learning point；但在训练后期，小的batch size导致梯度噪声增大，模型难以收敛至最优性能点；大的batch size虽然能给出精确的梯度估计，但会降低每个训练样本的利用效率，从而导致收敛变慢，并可能浪费计算资源。 batch...

本篇隶属C++ Primer中C++标准库专题，当前关注范型算法。 标准库容器只定义了很少的操作；因此提供了一组范型算法，其中大多数独立于特定的容器，具备通用性。 范型算法 概述 大多数算法在头文件algorithm中；头文件numeric中定义了一组数值范型算法。 范型算法本身不会执行容器的操作；只会运行于迭代器之上，执行迭代器的操作。 只读算法 只读取输入范围的元素，从不改变元素 find 12int val=42;auto result=find(vec.cbegin(), vec.cend(), val); find前两个参数：表示元素范围的迭代器；第三个参数：一个值。将范围中每个元素与给定值比较： 返回指向第一个等于给定值元素的迭代器； 若范围内无匹配元素，返回第二个参数，表示搜索失败。 accumulate 1int sum=accumulate(vec.cbegin(), vec.cend(), 0); // 将sum设置为：vec中元素之和 第三个参数指定保存和的对象类型，在该类型上必须定义了"+"运算符 12// 错误：const...

VLM-R1基于TRL框架。 GROP方法 GRPO 是一种在线学习算法，它通过使用训练模型本身在训练期间生成的数据进行迭代改进。其理念是：最大程度利用生成补全，同时确保模型始终接近参考策略。 分为4个步骤：生成补全、计算奖励、估计KL散度、计算损失。 要点 引入critic：使用预测baseline改进奖励 使用绝对奖励，单纯比较大小，会导致：奖励波动大，以及对部分改进的激励不足；因此引入Critic：使用“预测baseline”来改进奖励 对于给定状态(\(s_t\))和动作(\(o_t\))，该baseline为价值函数\((V_\psi(s))\)；训练目标由单纯的reward，转为超过该baseline的程度，由优势函数表示为： \[ A_t=r_t-V_\psi(s_t) \] 即训练中优化内容为： \[ \mathcal{J}_{adv}(\theta)=\mathbb{E}[A(o)] \\ where...

VAE 信息论 信息量 \(I(x)=-\log{P(x)}\),描述事件x中包含的信息量。 信息熵 设随机变量X~p(X),则X的熵被定义为： \[ H(p)=\mathbb{E}_{X\sim p(X)}[-\log p(X)]. \] 当X为离散随机变量时， \[ H(p)=-\sum_{i=1}^{n}p(x_i)\log p(x_i) \] 熵的数学化理解： 编码随机变量所需的最短平均编码长度 即对于更大概率的事件，采用更短的编码(同Huffman编码思路一致)。 证明： 假设编码的字符集大小为\(D\)，若采用二进制编码，则\(D=2\). 假设存在需要编码的\(m\)个事件，每个事件的编码长度为\(l_i\). 根据编码理论中的Kraft–McMillan Inequality，在给定的码字字长下能够成功编码，当且仅当: \[ \sum_{i=1}^{m}D^{-l_i}\leq 1. \] 转为如下优化问题： \[ \min_{l_i}\sum_{i=1}^{m}p(x_i)l_i \] \[\sum_{i=1}^{m}D^{-l_i}\leq 1.\]...

这是北航2024春《人工智能导论》课的理论笔记，由笔者整理。 绪论 三种主流方法：符号主义、联结主义、行为主义 机器学习 从数据中学习知识：f(x)=y 按数据标注情况分类： * 监督学习：数据有标签、直接反馈、预测结果 * 无监督学习：数据无标签、无反馈、寻找数据规律 * 半监督学习：部分数据有标签，部分反馈，预测结果...

在冯诺依曼架构中，数据存储在磁盘上，但必须加载到内存中才能执行操作。因此，如果数据库管理系统希望处理大量数据，它就必须能够高效地在磁盘与内存之间移动数据。这个任务由缓冲池管理器（Buffer Pool...