科学空间|Scientific Spaces

再次回到低秩近似之路上。在《低秩近似之路（四）：ID》中，我们介绍了“插值分解（Interpolative Decomposition，ID）”，这是为矩阵$\boldsymbol{M}\in\mathbb{R}^{n\times m}$寻找$\boldsymbol{C}\boldsymbol{Z}$形式的近似的过程，其中$\boldsymbol{C}\in\mathbb{R}^{n\times r}$是矩阵$\boldsymbol{M}$的若干列，而$\boldsymbol{Z}\in\mathbb{R}^{r\times m}$是任意矩阵。

这篇文章我们将介绍CUR分解，它跟插值分解的思想一脉相承，都是以原始矩阵的行、列为“骨架”来构建原始矩阵的近似，跟ID只用行或列之一不同，CUR分解同时用到了行和列。

基本定义

其实这不是本站第一次出现CUR分解了。早在《Nyströmformer：基于矩阵分解的线性化Attention方案》我们就介绍过矩阵的Nyström近似，它实际上就是CUR分解，后来在《利用CUR分解加速交互式相似度模型的检索》还介绍了CUR分解在降低交互式相似度模型的检索复杂度的应用。

点击阅读全文...

这篇文章的主角是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}

点击阅读全文...

前天晚上微信群里有群友提出了一个问题：

对于一个任意整数$N > 100$，求一个近似算法，使得$N=a\times b+c$（其中$a,b,c$都是非负整数），并且令$a+b+c$尽量地小。

初看这道题，笔者第一感觉就是“这还需要算法？”，因为看上去自由度太大了，应该能求出个解析解才对，于是简单分析了一下之后就给出了个“答案”，结果很快就有群友给出了反例。这时，笔者才意识到这题并非那么平凡，随后正式推导了一番，总算得到了一个可行的算法。正当笔者以为这个问题已经结束时，另一个数学群的群友精妙地构造了新的参数化，证明了算法的复杂度还可以进一步下降！

整个过程波澜起伏，让笔者获益匪浅，遂将过程记录在此，与大家分享。

点击阅读全文...

在NLP中，我们经常要去比较两个句子的相似度，其标准方法是想办法将句子编码为固定大小的向量，然后用某种几何距离（欧氏距离、$\cos$距离等）作为相似度。这种方案相对来说比较简单，而且检索起来比较快速，一定程度上能满足工程需求。

此外，还可以直接比较两个变长序列的差异性，比如编辑距离，它通过动态规划找出两个字符串之间的最优映射，然后算不匹配程度；现在我们还有Word2Vec、BERT等工具，可以将文本序列转换为对应的向量序列，所以也可以直接比较这两个向量序列的差异，而不是先将向量序列弄成单个向量。

后一种方案速度相对慢一点，但可以比较得更精细一些，并且理论比较优雅，所以也有一定的应用场景。本文就来简单介绍一下属于后者的两个相似度指标，分别简称为WMD、WRD。

Earth Mover's Distance

本文要介绍的两个指标都是以Wasserstein距离为基础，这里会先对它做一个简单的介绍，相关内容也可以阅读笔者旧作《从Wasserstein距离、对偶理论到WGAN》。Wasserstein距离也被形象地称之为“推土机距离”（Earth Mover's Distance，EMD），因为它可以用一个“推土”的例子来通俗地表达它的含义。

点击阅读全文...

刚刚在浏览卢昌海大师的微博时，发现他微博上有一道比较有趣的题目，于是饶有兴致地思考了一翻，构思了一个答案，希望读者们看看这个答案有问题不？

五一”长假微博很闷，出一道题给博友们解闷：

用重载列车运煤，每次可装1万吨，每行驶1公里耗煤1吨，起点处共有N万吨煤（简单起见N为正整数），请问最远可运至何处（是国营煤老板，成本不计，只要运到的数量大于0就算成功）？并求$N\to\infty$时的渐进形式。

点击阅读全文...

在农村，7月是忙碌的月份，农民们要忙着收割稻谷，收割完后要晒谷，同时还得准备“下秧”，准备新一轮的耕，BoJone家自然也不例外。不过我家田比较少（1亩左右），收割机几分钟搞定，谷也三两天就晒完了。不过在晒谷的时候，BoJone在考虑一个“收谷”问题：

晒谷时得先把成堆的谷子摊开，薄薄地平铺在平地上，等到傍晚或即将下雨时（这是最惨的情况，搞不好会淋谷）就将其收起来。问题就源于这里，一般来说我们会把谷均匀地铺成矩形，要把所有的谷都推到矩形里或外的哪一点上，才使得我们做功做小？

这个问题还可以推广开来，例如对于一地任意形状的谷子（如三角形），把它集中堆到哪个点最“轻松”？一堆固定质量的谷子，要把它平铺成什么形状，才使得收谷时最“轻松”？当然，这个问题的解不仅仅用于“收谷”，在很多规划建设中也可以应用到，例如要在一个人口大致均匀的城市中建设一个服务中心，这个服务中心应该建在哪里？这有点类似于我们之前讨论过的费马点问题 ，都是费马点只考虑了三个点的距离，而这个问题得考虑所有点的距离。

点击阅读全文...