1 Oct

低秩近似之路(二):SVD

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

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

结论初探

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

点击阅读全文...

20 Sep

自然数集中 N = ab + c 时 a + b + c 的最小值

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

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

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

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

点击阅读全文...

13 May

从EMD、WMD到WRD:文本向量序列的相似度计算

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

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

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

Earth Mover's Distance

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

点击阅读全文...

4 May

[问题解答]运煤车的最大路程(更正)

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

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

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

点击阅读全文...

25 Jul

收谷问题(1)

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

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

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

点击阅读全文...

30 Apr

蘑菇的最优形状模型

淡白口蘑

淡白口蘑

达尔文的进化学说告诉我们,自然界总是在众多的生物中挑出最能够适应环境的物种,赋予它们更高的生存几率,久而久之,这些物种经过亿万年的“优胜劣汰”,进化成了今天的千奇百怪的生物。无疑,经过长期的选择,优良的形状会被累积下来,换句话讲,这些物种在某些环境适应能力方面已经达到最优或近乎最优的状态(又是一个极值问题了)。好,现在我们来考虑蘑菇。

蘑菇是一种真菌生物,一般生长在阴暗潮湿的环境中。喜欢湿润的它自然也不希望散失掉过多的水分,因此,它努力地调整自身的形状,使它的“失水”尽可能地少。假设单位面积的蘑菇的失水速度是一致的,那么问题就变成了使一个给定体积的立体表面积尽可能少的问题了。并且考虑到水平各向同性生长的问题,理想的蘑菇形状应该就是一个平面图形的旋转体。那么这个旋转体是什么呢?聪明的你是否想到了是一个球体(的一部分)呢?

点击阅读全文...

28 Nov

《自然极值》系列——4.费马点问题

通过上面众多的文字描述,也许你还不大了解这两个原理有何美妙之处,也或者你已经迫不及待地想去应用它们却不知思路。为了不至于让大家产生“审美疲劳”,接下来我们将试图利用这两个原理对费马点问题进行探讨,看看原理究竟是怎么发挥作用的。运用的关键在于:如何通过适当的变换将其与光学或势能联系起来。

费马点问题

费马点问题

传统费马点问题是指在ΔABC中寻找点P,使得$AP+BP+CP$最小的问题;而广义的费马点则改成使$k_1 AP+k_2 BP+k_3 CP$最小。这是很具有现实意义的,是“在三个村庄之间建立一个中转站,如何才能使运送成为最低”之类的最优问题。我们将从光学和势能两个角度对这个问题进行探讨(也许有的读者已经阅读过了利用重力的原理来求解费马点,但是我想光学的方法依然会是你眼前一亮的。

点击阅读全文...