16 Feb

Nyströmformer:基于矩阵分解的线性化Attention方案

标准Attention的$\mathscr{O}(n^2)$复杂度可真是让研究人员头大。前段时间我们在博文《Performer:用随机投影将Attention的复杂度线性化》中介绍了Google的Performer模型,它通过随机投影的方式将标准Attention转化为线性Attention。无偶独有,前些天Arxiv上放出了AAAI 2021的一篇论文《Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention》,里边又提出了一种从另一个角度把标准Attention线性化的方案。

Nyströmformer结构示意图

Nyströmformer结构示意图

该方案写的是Nyström-Based,顾名思义是利用了Nyström方法来近似标准Attention的。但是坦白说,在看到这篇论文之前,笔者也完全没听说过Nyström方法,而纵观整篇论文,里边也全是笔者一眼看上去感觉很茫然的矩阵分解推导,理解起来颇为困难。不过有趣的是,尽管作者的推导很复杂,但笔者发现最终的结果可以通过一个相对来说更简明的方式来理解,遂将笔者对Nyströmformer的理解整理在此,供大家参考。

点击阅读全文...

26 Jan

Seq2Seq重复解码现象的理论分析尝试

去年笔者写过博文《如何应对Seq2Seq中的“根本停不下来”问题?》,里边介绍了一篇论文中对Seq2Seq解码不停止现象的处理,并指出那篇论文只是提了一些应对该问题的策略,并没有提供原理上的理解。近日,笔者在Arixv读到了AAAI 2021的一篇名为《A Theoretical Analysis of the Repetition Problem in Text Generation》的论文,里边从理论上分析了Seq2Seq重复解码现象。从本质上来看,重复解码和解码不停止其实都是同理的,所以这篇新论文算是填补了前面那篇论文的空白。

经过学习,笔者发现该论文确实有不少可圈可点之处,值得一读。笔者对原论文中的分析过程做了一些精简、修正和推广,将结果记录成此文,供大家参考。此外,抛开问题背景不讲,读者也可以将本文当成一节矩阵分析习题课,供大家复习线性代数哈~

点击阅读全文...

1 Mar

构造一个显式的、总是可逆的矩阵

《恒等式 det(exp(A)) = exp(Tr(A)) 赏析》一文我们得到矩阵$\exp(\boldsymbol{A})$总是可逆的,它的逆就是$\exp(-\boldsymbol{A})$。问题是$\exp(\boldsymbol{A})$只是一个理论定义,单纯这样写没有什么价值,因为它要把每个$\boldsymbol{A}^n$都算出来。

有没有什么具体的例子呢?有,本文来构造一个显式的、总是可逆的矩阵。

其实思路非常简单,假设$\boldsymbol{x},\boldsymbol{y}$是两个$k$维列向量,那么$\boldsymbol{x}\boldsymbol{y}^{\top}$就是一个$k\times k$的矩阵,我们就来考虑
\begin{equation}\begin{aligned}\exp\left(\boldsymbol{x}\boldsymbol{y}^{\top}\right)=&\sum_{n=0}^{\infty}\frac{\left(\boldsymbol{x}\boldsymbol{y}^{\top}\right)^n}{n!}\\
=&\boldsymbol{I}+\boldsymbol{x}\boldsymbol{y}^{\top}+\frac{\boldsymbol{x}\boldsymbol{y}^{\top}\boldsymbol{x}\boldsymbol{y}^{\top}}{2}+\frac{\boldsymbol{x}\boldsymbol{y}^{\top}\boldsymbol{x}\boldsymbol{y}^{\top}\boldsymbol{x}\boldsymbol{y}^{\top}}{6}+\dots\end{aligned}\end{equation}

点击阅读全文...

18 Feb

恒等式 det(exp(A)) = exp(Tr(A)) 赏析

本文的主题是一个有趣的矩阵行列式的恒等式
\begin{equation}\det(\exp(\boldsymbol{A})) = \exp(\text{Tr}(\boldsymbol{A}))\label{eq:main}\end{equation}
这个恒等式在挺多数学和物理的计算中都出现过,笔者都在不同的文献中看到过好几次了。

注意左端是矩阵的指数,然后求行列式,这两步都是计算量非常大的运算;右端仅仅是矩阵的迹(一个标量),然后再做标量的指数。两边的计算量差了不知道多少倍,然而它们居然是相等的!这不得不说是一个神奇的事实。

所以,本文就来好好欣赏一个这个恒等式。

点击阅读全文...

16 Oct

再谈非方阵的行列式

几年前,笔者曾经以自己对矩阵的粗浅理解写了一个“理解矩阵”系列,其中有一篇《为什么只有方阵有行列式?》讨论了非方阵的行列式问题,里边给出了“非方针的行列式不好看”和“方阵的行列式就够了”的观点。本文来再次思考这个问题。

首先回顾方阵的行列式,其实行列式最重要的价值在于它的几何意义:

n维方阵的行列式的绝对值,等于它的各个行(或列)向量所张成的n维立体的超体积。

这个几何意义是行列式的一切重要性的源头,相关的讨论可以参考《行列式的点滴》,它也是我们讨论非方阵行列式的基础。

分析

对于方阵$\boldsymbol{A}_{n\times n}$来说,可以将它看成$n$个行向量的组合,也可以看成$n$个列向量的组合,不管是哪一种,行列式的绝对值都等于这$n$个向量所张成的$n$维立体的超体积。换句话说,对于方阵来说,行、列向量的区分不改变行列式。

对于非方阵$\boldsymbol{B}_{n \times k}$就不一样了,不失一般性,假设$n > k$。我们可以将它看成$n$个$k$维列向量的组合,也可以看成$k$个$n$维行向量的组合。非方针的行列式,应该也具有同样含义,即它们所张成的立体的超体积。

我们来看第一种情况,如果看成$n$个$k$维列向量,那么就得视为这$n$个向量张成的$n$维体的超体积了,但是要注意$n > k$,因此这$n$个向量必然线性相关,因此它们根本就张不成一个$n$维体,也许是一个$n-1$维体甚至更低,这样一来,它的$n$维体的超体积自然为0。

但是第二种情况就没有那么平凡了。如果看成$k$个$n$维行向量,那么这$k$个向量虽然是$n$维的,但它们张成的是一个$k$维体,这$k$维体的超体积未必为0。我们就以这个非平凡的体积作为非方阵行列式的定义好了。

点击阅读全文...

12 Nov

实数域上有限维可除代数只有四种

今天上近世代数课,老师谈到除环,举了一个非交换的除环的粒子,也就是四元数环,然后谈到“实数域上有限维可除代数只有4种”,也就是实数本身、复数、四元数和八元数(这里的可除代数就是除环)。这句话我听起来有点熟悉,又好像不大对劲。我记得在某本书上看过,定义为实数上的超复数系,如果满足模的积性,那么就只有以上四种。但是老师的那句话表明即使去掉模的积性,也只有四种。我自然以为老师记错了,跟老师辩论了一翻,然后回到宿舍又找资料,最终确定:实数域上有限维可除代数真的只有四种!下面简单谈谈我对这个问题的认识。

当然,这里不可能给出这个命题的证明,因为这个证明相当不简单,笔者目前也没有弄懂,但是粗略感觉一下为什么,还是有可能的。看到这个命题,我们一下子的感觉可能是:怎么会这么少!我们这里通过例子简单说明一下,确实不会多!

我们已经对复数系很熟悉了,也就是定义在实数上的向量空间,基为$\{1,i\}$,并且给定乘法为
$$1\times i=i \times 1=i,\quad 1^2=1,\quad i^2=-1$$

点击阅读全文...

15 Jul

《新理解矩阵6》:为什么只有方阵有行列式?

学过线性代数的朋友都知道,方阵和非方阵的一个明显不同是,对于方阵我们可以计算它的行列式,如果不是方阵的话,就没有行列式这个概念了。在追求统一和谐的数学系统中,为什么非方阵却没有行列式?也许对于这个问题最恰当的回答是——因为不够美。对于非方阵,其实也可以类似地定义它的行列式,定义出来的东西,跟方阵的行列式具有同样的性质,比如某行乘上一个常数,行列式值也就乘以一个常数,等等;而且还可以把其几何意义保留下来。但是,非方阵的行列式是不够美的,因为对于一个一般的整数元素的方阵,我们的行列式是一个整数;而对于一个一般的整数元素的非方阵,却导致了一个无理数的行列式值。另外,一个也比较重要的原因是,单单是方阵的行列式也够用了。综合以上两个理由,非方阵的行列式就被舍弃不用了。

非方阵的行列式不够漂亮

$n$阶方阵的行列式是每个向量的线性函数,它代表着向量之间的线性相关性;从几何上来讲,它就是向量组成的平行n维体的(有向)体积。我们当然期望非方阵的行列式也保留这些性质,因为只有这样,方阵行列式的那些运算性质才得以保留,比如上面说的,行列式的一行乘上一个常数,行列式值也乘上一个常数。我们考虑$m\times n$的矩阵,其中$ m < n $,我们将它看成是$m$个$n$维向量的组合。最简单的,我们先考虑$1\times 2$矩阵的行列式,也就是二维向量$(a,b)$的行列式。

点击阅读全文...

11 Jan

几何的数与数的几何:超复数的浅探究

这也是我的期末论文之一...全文共17页,包括了四元数的构造方法,初等应用等。附录包括行列式与体积、三维旋转的描述等。使用LaTex进行写作(LaTex会让你爱上数学写作的)

几何的数与数的几何
――超复数的浅探究

摘要
今天,不论是数学还是物理的高维问题,都采用向量分析为基本工具,数学物理中难觅四元数的影子。然而在历史上,四元数的发展有着重要的意义。四元数(Quaternion)运算实际上是向量分析的“鼻祖”,向量点积和叉积的概念也首先出现在四元数的运算中,四元数的诞生还标记着非交换代数的开端。即使是现在,四元数还是计算机描述三维空间旋转问题最简单的工具。另外,作为复数的推广,四元数还为某些复数问题的一般化提供了思路。

本文把矩阵与几何适当地结合起来,利用矩阵行列式$\det (AB) =(\det A)(\det B)$这一性质得出了四元数以及更高维的超复数的生成规律,并讨论了它的一些性质以及它在描述旋转方面的应用。部分证明细节和不完善的思想放到了附录之中。

点击阅读全文...