科学空间|Scientific Spaces

这篇文章的主角是ID（Interpolative Decomposition），中文可以称之为“插值分解”，它同样可以理解为是一种具有特定结构的低秩分解，其中的一侧是该矩阵的若干列（当然如果你偏好于行，那么选择行也没什么问题），换句话说，ID试图从一个矩阵中找出若干关键列作为“骨架”（通常也称作“草图”）来逼近原始矩阵。

可能很多读者都未曾听说过ID，即便维基百科也只有几句语焉不详的介绍（链接），但事实上，ID跟SVD一样早已内置在SciPy之中（参考scipy.linalg.interpolative），这侧面印证了ID的实用价值。

基本定义

前三篇文章我们分别介绍了伪逆、SVD、CR近似，它们都可以视为寻找特定结构的低秩近似：
\begin{equation}\mathop{\text{argmin}}_{\text{rank}(\tilde{\boldsymbol{M}})\leq r}\Vert \tilde{\boldsymbol{M}} - \boldsymbol{M}\Vert_F^2\end{equation}

点击阅读全文...

在《低秩近似之路（二）：SVD》中，我们证明了SVD可以给出任意矩阵的最优低秩近似。那里的最优近似是无约束的，也就是说SVD给出的结果只管误差上的最小，不在乎矩阵的具体结构，而在很多应用场景中，出于可解释性或者非线性处理等需求，我们往往希望得到具有某些特殊结构的近似分解。

因此，从这篇文章开始，我们将探究一些具有特定结构的低秩近似，而本文将聚焦于其中的CR近似（Column-Row Approximation），它提供了加速矩阵乘法运算的一种简单方案。

问题背景

矩阵的最优$r$秩近似的一般提法是
\begin{equation}\mathop{\text{argmin}}_{\text{rank}(\tilde{\boldsymbol{M}})\leq r}\Vert \tilde{\boldsymbol{M}} - \boldsymbol{M}\Vert_F^2\label{eq:loss-m2}\end{equation}

点击阅读全文...

上一篇文章中我们介绍了“伪逆”，它关系到给定矩阵$\boldsymbol{M}$和$\boldsymbol{A}$（或$\boldsymbol{B}$）时优化目标$\Vert \boldsymbol{A}\boldsymbol{B} - \boldsymbol{M}\Vert_F^2$的最优解。这篇文章我们来关注$\boldsymbol{A},\boldsymbol{B}$都不给出时的最优解，即
\begin{equation}\mathop{\text{argmin}}_{\boldsymbol{A},\boldsymbol{B}}\Vert \boldsymbol{A}\boldsymbol{B} - \boldsymbol{M}\Vert_F^2\label{eq:loss-ab}\end{equation}
其中$\boldsymbol{A}\in\mathbb{R}^{n\times r}, \boldsymbol{B}\in\mathbb{R}^{r\times m}, \boldsymbol{M}\in\mathbb{R}^{n\times m},r < \min(n,m)$。说白了，这就是要寻找矩阵$\boldsymbol{M}$的“最优$r$秩近似（秩不超过$r$的最优近似）”。而要解决这个问题，就需要请出大名鼎鼎的“SVD（奇异值分解）”了。虽然本系列把伪逆作为开篇，但它的“名声”远不如SVD，听过甚至用过SVD但没听说过伪逆的应该大有人在，包括笔者也是先了解SVD后才看到伪逆。

接下来，我们将围绕着矩阵的最优低秩近似来展开介绍SVD。

结论初探

对于任意矩阵$\boldsymbol{M}\in\mathbb{R}^{n\times m}$，都可以找到如下形式的奇异值分解（SVD，Singular Value Decomposition）：
\begin{equation}\boldsymbol{M} = \boldsymbol{U}\boldsymbol{\Sigma} \boldsymbol{V}^{\top}\end{equation}

点击阅读全文...

可能很多读者跟笔者一样，对矩阵的低秩近似有种熟悉而又陌生的感觉。熟悉是因为，低秩近似的概念和意义都不难理解，加之目前诸如LoRA等基于低秩近似的微调技术遍地开花，让低秩近似的概念在耳濡目染间就已经深入人心；然而，低秩近似所覆盖的内容非常广，在低秩近似相关的论文中时常能看到一些不熟悉但又让我们叹为观止的新技巧，这就导致了一种似懂非懂的陌生感。

因此，在这个系列文章中，笔者将试图系统梳理一下矩阵低秩近似相关的理论内容，以补全对低秩近似的了解。而在第一篇文章中，我们主要介绍低秩近似系列中相对简单的一个概念——伪逆。

优化视角

伪逆（Pseudo Inverse），也称“广义逆（Generalized Inverse）”，顾名思义就是“广义的逆矩阵”，它实际上是“逆矩阵”的概念对于不可逆矩阵的推广。

点击阅读全文...

前两周笔者写了《对齐全量微调！这是我看过最精彩的LoRA（一）》（当时还没有编号“一”），里边介绍了一个名为“LoRA-GA”的LoRA变体，它通过梯度SVD来改进LoRA的初始化，从而实现LoRA与全量微调的对齐。当然，从理论上来讲，这样做也只能尽量对齐第一步更新后的$W_1$，所以当时就有读者提出了“后面的$W_2,W_3,\cdots$不管了吗？”的疑问，当时笔者也没想太深入，就单纯觉得对齐了第一步后，后面的优化也会严格一条较优的轨迹走。

有趣的是，LoRA-GA才出来没多久，arXiv上就新出了《LoRA-Pro: Are Low-Rank Adapters Properly Optimized?》，其所提的LoRA-Pro正好能回答这个问题！LoRA-Pro同样是想着对齐全量微调，但它对齐的是每一步梯度，从而对齐整条优化轨迹，这正好是跟LoRA-GA互补的改进点。

对齐全量

本文接着上一篇文章的记号和内容进行讲述，所以这里仅对上一节的内容做一个简单回顾，不再详细重复介绍。LoRA的参数化方式是
\begin{equation}W = (W_0 - A_0 B_0) + AB\end{equation}

点击阅读全文...

在矩阵压缩这个问题上，我们通常有两个策略可以选择，分别是低秩化和稀疏化。低秩化通过寻找矩阵的低秩近似来减少矩阵尺寸，而稀疏化则是通过减少矩阵中的非零元素来降低矩阵的复杂性。如果说SVD是奔着矩阵的低秩近似去的，那么相应地寻找矩阵稀疏近似的算法又是什么呢？

接下来我们要学习的是论文《Monarch: Expressive Structured Matrices for Efficient and Accurate Training》，它为上述问题给出了一个答案——“Monarch矩阵”，这是一簇能够分解为若干置换矩阵与稀疏矩阵乘积的矩阵，同时具备计算高效且表达能力强的特点，论文还讨论了如何求一般矩阵的Monarch近似，以及利用Monarch矩阵参数化LLM来提高LLM速度等内容。

Monarch矩阵形式M=PLPR

值得指出的是，该论文的作者也正是著名的Flash Attention的作者Tri Dao，其工作几乎都在致力于改进LLM的性能，这篇Monarch也是他主页上特意展示的几篇论文之一，单从这一点看就非常值得学习一番。

点击阅读全文...

众所周知，LoRA是一种常见的参数高效的微调方法，我们在《梯度视角下的LoRA：简介、分析、猜测及推广》做过简单介绍。LoRA利用低秩分解来降低微调参数量，节省微调显存，同时训练好的权重可以合并到原始权重上，推理架构不需要作出改变，是一种训练和推理都比较友好的微调方案。此外，我们在《配置不同的学习率，LoRA还能再涨一点？》还讨论过LoRA的不对称性，指出给$A,B$设置不同的学习率能取得更好的效果，该结论被称为“LoRA+”。

为了进一步提升效果，研究人员还提出了不少其他LoRA变体，如AdaLoRA、rsLoRA、DoRA、PiSSA等，这些改动都有一定道理，但没有特别让人深刻的地方觉。然而，前两天的《LoRA-GA: Low-Rank Adaptation with Gradient Approximation》，却让笔者眼前一亮，仅扫了摘要就有种必然有效的感觉，仔细阅读后更觉得它是至今最精彩的LoRA改进。

究竟怎么个精彩法？LoRA-GA的实际含金量如何？我们一起来学习一下。

点击阅读全文...

LoRA（Low-Rank Adaptation）是当前LLM的参数高效微调手段之一，此前我们在《梯度视角下的LoRA：简介、分析、猜测及推广》也有过简单讨论。这篇文章我们来学习LoRA的一个新结论：

给LoRA的两个矩阵分配不同的学习率，LoRA的效果还能进一步提升。

该结论出自最近的论文《LoRA+: Efficient Low Rank Adaptation of Large Models》（下称“LoRA+”）。咋看之下，该结论似乎没有什么特别的，因为配置不同的学习率相当于引入了新的超参数，通常来说只要引入并精调超参数都会有提升。“LoRA+”的特别之处在于，它从理论角度肯定了这个必要性，并且断定最优解必然是右矩阵的学习率大于左矩阵的学习率。简而言之，“LoRA+”称得上是理论指导训练并且在实践中确实有效的经典例子，值得仔细学习一番。

结论简析

假设预训练参数为$W_0 \in \mathbb{R}^{n\times m}$，如果使用全量参数微调，那么增量也是一个$n\times m$矩阵。为了降低参数量，LoRA将更新量约束为低秩矩阵，即设$W=W_0 + AB$，其中$A\in\mathbb{R}^{n\times r},B\in\mathbb{R}^{r\times m}$以及有$r\ll \min(n,m)$，用新的$W$替换模型原有参数，然后固定$W_0$不变，训练的时候只更新$A,B$，如下图所示：
$$\style{display: inline-block; width: 24ex; padding: 10ex 0; border: 1px solid #6C8EBF; background-color: #DAE8FC}{W_0\in\mathbb{R}^{n\times m}} \quad + \quad \style{display: inline-block; width: 8ex; padding: 10ex 0; border: 1px solid #D79B00; background-color: #FFE6CC}{A\in\mathbb{R}^{n\times r}}\quad\times\quad \style{display: inline-block; width: 24ex; padding: 3ex 0; border: 1px solid #D79B00; background-color: #FFE6CC}{B\in\mathbb{R}^{r\times m}}$$

点击阅读全文...