数学

数学知识前置讲解：后续优化篇中一定会用到的数学工具 在接下来的 SSM 优化系列文章中，我们会频繁用到一些超出本科线性代数和高等数学范畴的数学知识和算法思想。本文集中讲解这些前置知识，让读者在后续阅读中不会因为数学工具的陌生而阻碍对核心思想的理解。 本文假设读者已具备线性代数基础（矩阵运算、特征值、矩阵指数）、高等数学基础（微分方程、积分）以及生成函数的基本概念。在此基础上，本文重点讲解两个读者可能尚未接触的领域：矩阵运算的计算复杂度分析和快速傅里叶变换（FFT）。同时也会简要介绍 Cauchy 矩阵和递推与卷积的联系。 一、矩阵运算的计算复杂度 SSM 优化的核心目标之一，就是把 $O(N^3)$ 的密集矩阵运算降到 $O(N)$。要理解为什么这是可能的，我们需要先理解：不同矩阵运算的复杂度分别是多少，以及为什么是这个数量级。 1. 为什么需要关心复杂度 在深度学习中，“一个算法能不能用"不仅取决于它在数学上是否正确，还取决于它在工程上是否可行。HiPPO 给出了理论上最优的 $\mathbf{A}$ 矩阵，但由于密集矩阵运算的复杂度过高，直到 S4 通过 DPLR 结构将其优化到可接受的范围，这个理论优势才真正落地。 这里还有一个常被跳过的小票据：S4 在效果上的表现，最早是靠 Long Range Arena（LRA）这类长序列基准里的显著结果让大家信服的。比如在 LRA 六项任务里，S4 的算术平均约为 81.84%，而标准 Transformer 约为 45.32%；到了最长的 Path-X（长度 16000）任务上，Performer、BigBird 这些高效注意力方法也和标准 Transformer 一样崩溃至 0%，S4 仍然达到 86.73%。有的总结材料里会把 S4 的平均写成约 86.1%，这个数和从六项明细算出的 81.84% 并不完全一致，可能来源于不同报告版本或平均方式的差异，所以引用时最好还是以逐任务明细为准。 2. 矩阵-向量乘法：$O(N)$ 与 $O(N^2)$ 的区别 一般矩阵乘向量： 设 $\mathbf{A} \in \mathbb{R}^{N \times N}$，$\mathbf{h} \in \mathbb{R}^N$，计算 $\mathbf{y} = \mathbf{A}\mathbf{h}$。矩阵 $\mathbf{A}$ 有 $N^2$ 个元素，每个输出分量 $y_i = \sum_{j=1}^{N} A_{ij} h_j$ 需要 $N$ 次乘法和 $N-1$ 次加法。总共 $N$ 个分量，总计算量为 $N \times N = N^2$ 次乘法，即 $O(N^2)$。 ...

上半学期：多元函数微分学 1. 二重极限与累次极限 二重极限：$\displaystyle \lim_{(x,y)\to(x_0,y_0)} f(x,y)$ 累次极限：$\displaystyle \lim_{x\to x_0}\lim_{y\to y_0} f(x,y)$ 2. 无穷小的阶 设$\rho = | \boldsymbol{x} - \boldsymbol{x_0} |$为两点间的距离（二元函数中即$\sqrt{(x-x_0)^2+(y-y_0)^2}$），若$f(\boldsymbol{x}) = O(\rho^k)$，则称$f$是$k$阶无穷小。 3. 多元函数微分与偏导数 对$n$元函数$u = f(x_1,x_2,\dots,x_n)$，全微分公式： $$du = \frac{\partial u}{\partial x_1} dx_1 + \frac{\partial u}{\partial x_2} dx_2 + \dots + \frac{\partial u}{\partial x_n} dx_n$$ 4. 方向导数 设$\vec{l} = (\cos\alpha_1, \cos\alpha_2, \dots, \cos\alpha_n)$为单位方向向量（$\alpha_i$是$\vec{l}$与第$i$个坐标轴的夹角），则$f(x_1,\dots,x_n)$在$\boldsymbol{x_0}$处沿$\vec{l}$的方向导数为： $$\frac{\partial f}{\partial \vec{l}}(\boldsymbol{x_0}) = \frac{\partial f}{\partial x_1}(\boldsymbol{x_0})\cos\alpha_1 + \frac{\partial f}{\partial x_2}(\boldsymbol{x_0})\cos\alpha_2 + \dots + \frac{\partial f}{\partial x_n}(\boldsymbol{x_0})\cos\alpha_n$$ ...

1. 各种分解 1.1 LU 与 LDU 分解 定义：某矩阵 $A=LU$，则 $U$ 是对 $A$ 作行简化后得到的上三角矩阵。 例子： $$ A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 4 & 6 \\ 2 & 2 & 6 \end{pmatrix} \sim \begin{pmatrix} 1 & 2 & 3 \\ 0 & -4 & -6 \\ 0 & -2 & 0 \end{pmatrix} \sim \begin{pmatrix} 1 & 2 & 3 \\ 0 & -4 & -6 \\ 0 & 0 & 3 \end{pmatrix} \leftarrow \text{这个是 } U $$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 基本的推理公式 $(\forall x)P(x)\lor(\forall x)Q(x)\Rightarrow(\forall x)(P(x)\lor Q(x))$⭐️ $(\exists x)(P(x)\land Q(x))\Rightarrow (\exists x)P(x)\land (\exists x)Q(x)$⭐️ $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\forall x)P(x)\rightarrow (\forall x)Q(x)$ $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\exists x)P(x)\rightarrow (\exists x)Q(x)$ $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\forall x)P(x)\leftrightarrow (\forall x)Q(x)$ $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\exists x)P(x)\leftrightarrow (\exists x)Q(x)$ $(\forall x)(P(x)\rightarrow Q(x))\land (\forall x)(Q(x)\rightarrow R(x))\Rightarrow (\forall x)(P(x)\rightarrow R(x))$⭐ $(\forall x)(P(x)\rightarrow Q(x))\land P(a)\Rightarrow Q(a)$⭐ $(\forall x)(\forall y)P(x,y)\Rightarrow (\exists x)(\forall y)P(x,y)$ $(\exists x)(\forall y)P(x,y)\Rightarrow (\forall y)(\exists x)P(x,y)$ 这些推理公式的逆一般是不成立的，所以记住和理解顺序很重要。 推理演算 注意，本节按照老师上课讲义的符号和规则来描述，不同的规定和不同的讲述方式可能导致本节内容在一定程度上不是普适性的。本节适配内容为T大软件学院离散数学（1）的课程及考试内容。 ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 由命题公式得来的等值公式 这部分我们把谓词逻辑看做命题逻辑中的命题变元，命题逻辑中正确的公式也是谓词逻辑中正确的公式。 例如，命题逻辑中，$\neg\neg p=p$是重言式，那么对于谓词逻辑$\neg\neg (\forall x)P(x)=(\forall x)P(x)$是一个有效式。 这部分是谓词逻辑的一个重要基石，因为谓词逻辑中很多细节性的、不涉及量词变换的等值公式都是由此得来的。 否定型等值式⭐⭐ 这部分是最最重要的基础。 $\neg(\forall x)P(x)=(\exists x)\neg P(x)$ $\neg(\exists x)P(x)=(\forall x)\neg P(x)$ 可以这样直观的理解和解释： 并不是对于所有的$x,P(x)$都成立，那么肯定存在一个$x,P(x)$不成立，即$\neg P(x)$成立。 不存在一个$x$让$P(x)$成立，那么对于所有的$x,P(x)$都不成立，即$\neg P(x)$成立。 谓词公式和命题变项的分配律 有关$\land$和$\lor$的分配律⭐ $(\forall x)(P(x)\land q)=(\forall x)P(x)\land q$ $(\forall x)(P(x)\lor q)=(\forall x)P(x)\lor q$ $(\exists x)(P(x)\land q)=(\exists x)P(x)\land q$ $(\exists x)(P(x)\lor q)=(\exists x)P(x)\lor q$ 这部分是比较好理解的，也是非常基础性的定律。 有关$\rightarrow$的分配律 $(\forall x)(P(x)\rightarrow q)=(\exists x)P(x)\rightarrow q$ $(\exists x)(P(x)\rightarrow q)=(\forall x)P(x)\rightarrow q$ $(\forall x)(q\rightarrow P(x))=q \rightarrow (\forall x)P(x)$ $(\exists x)(q\rightarrow P(x))=q \rightarrow (\exists x)P(x)$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 一些定义和名称 个体词就是命题逻辑里面的主词。包括了个体常项和个体变项。将个体变化的范围成为个体域或者论域$D$。 谓词指的是用来刻画对象性质和关系的符号，一般用大写字母$P,Q,R$表示，可以理解为语法上的谓语的作用。把在谓词的定义中涉及到的个体词的个数称为该谓词的元数。如$P(x,y)$表示$x=y$就是一个二元谓词；命题逻辑中的命题就是一个零元谓词。注意，谓词的值域是$\{T,F\}$ 函数指的是一些从$D$到$D$的映射。他们与谓词的区别在于值域。例如，$f(x)$表示“$x$的父亲”是一个函数，而$P(x)$表示“$x$是父亲”就是一个谓词。 项是用于表示论语中对象的符号表达式。个体词和函数都是项。 量词是对个体数量加以约束和限制的词。量词分为全称量词和存在量词。全称量词就是$\forall$，存在量词就是$\exists$，具体内涵就是我们高中就熟知的。量词的辖域指的就是某个量词所约束的范围。一般而言，我们可以认为如果量词后不加括号，那辖域就是后一个谓词符号；如果量词后有括号，那就是括号里的内容。 一些实例 在这里给出一些自然语言形式化变成一阶谓词逻辑的结果，便于理解。注意，这些结果中有些是特别需要注意的。 所有的有理数都是实数 取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\forall x)(P(x)\rightarrow R(x))$ 注意，“所有的……都是……”这样类型的语句只能用$\rightarrow$ 有的实数是有理数 取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\exists x)(R(x)\land P(x))$ 注意，“有的……是……”这样类型的语句一般用$\land$ 有的实数不是有理数 取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\exists x)(R(x)\land \neg P(x))$ 没有无理数是有理数 取$P(x)$表示$x$是有理数，$Q(x)$表示$x$是无理数数。则原句可以形式化为$\neg(\exists x)(Q(x)\land P(x))$ 至少有一个偶数是素数 取$A(x)$表示$x$为偶数，$B(x)$表示$x$为素数。则原句可以形式化为$(\exists x)(A(x)\land B(x))$ 至少有一个偶数并且至少有一个素数 取$A(x)$表示$x$为偶数，$B(x)$表示$x$为素数。则原句可以形式化为$(\exists x)A(x)\land(\exists x) B(x)$ 函数$f(x)$在$[a,b]$上的点$x_0$处连续 根据微积分的知识，可以形式化为$(\forall \epsilon)(\epsilon >0\rightarrow (\exists \delta)(\delta>0\land (\forall x)(|x-x_0|<\delta\rightarrow|f(x)-f(x_0)|<\epsilon)))$ 自然数集合的形式描述 即，论域是自然数集，我们要形式化下列语句（自然数集合建立公理）：$\\(1)$对于每个数，有且仅有一个相继后元$\\(2)$没有一个数的相继后元是0 $\\(3)$ 对于除0以外的数，有且仅有一个相继前元。 设谓词$P(x,y)$表示$x=y$，函数$f(x)=x+1$，函数$g(x)=x-1$。则原句可以形式化为：$\\(1)(\forall x)(\exists y)(P(y,f(x))\land(\forall z)(P(z,f(x))\rightarrow P(y,z)) )\\(2)\neg(\exists x)P(0,f(x))\\(3)(\forall x)(\neg P(0,x)\rightarrow (\exists y)(P(y,g(x))\land(\forall z)(P(z,g(x))\rightarrow P(y,z))))$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 一般公理系统的结构 通常而言，一个公理系统一般包括如下几部分： 初始符号：公理所允许出现的全体符号的集合。 形成规则：由出事符号可以组成各种符号序列。 公理：选出几个最基本的重言式作为推演其他所有重言式的依据。 变形规则：变形规则就是公理系统所规定的推理规则。 建立定理：这是公理系统内做演算的主要内容，应该包括所有的重言式和对它们的证明。 罗素系统 初始符号 $A,B,C……$，大写英文字母（表示命题） $\neg , \lor$表示联结词 （ ），表示圆括号 $\vdash$，写在一个公式之前表示其为重言式 形成规则 符号形成规则的符号序列成为合式公式。 符号$\pi$是合式公式（$\pi$取值为$A,B……$） 如果$A,B$是合式公式，那么$A\lor B$也是合式公式 如果$A$是合式公式，那么$\neg A$也是合式公式 只有符合1,2,3的符号序列才是合适公式 定义 除了由形成规则构成的合式公式之外，还可以通过定义来引入新的合式公式，这样引入的合式公式有着缩写和简化表达的作用。 定义1 $A\rightarrow B$定义为$\neg A\lor B$ 定义2 $A\land B$定义为$\neg(\neg A\lor\neg B)$ 定义3 $A\leftrightarrow B$定义为$(A\rightarrow B)\land(B\rightarrow A)$ 或者换句话说，罗素公理系统中只有“非”和“或”两种逻辑，其余逻辑都要求用“非”和“或”来表示。并且注意，上述定义中的顺序关系是严格的。 公理⭐️ 公理1 $\vdash (P\lor P)\rightarrow P$ 公理2 $\vdash P\rightarrow (P\lor Q)$ 公理3 $\vdash (P\lor Q)\rightarrow (Q\lor P)$ 公理4 $\vdash (Q\rightarrow R)\rightarrow((P\lor Q)\rightarrow (P\lor R))$ 注意，只有这些公理才能够直接运用在罗素公理系统的推导过程中！我们其余所知道的所有公式定理都不能够直接在罗素公理系统中用，包括交换律、结合律、互反律、摩根律等等等等。 变形规则⭐️ 代入规则：将合式公式$A$中出现的某一个符号$\pi$到处都带一某一个合适的公式$B$，从而得到合式公式$A\frac{\pi}{B}$叫代入。带入规则说，如果$\vdash A$,则$\vdash A\frac{\pi}{B}$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 推理形式 我们将用自然语句描述的推理关系引入符号，抽象化并以条件式表现出来，就得到了一种推理形式。 比如： 如果$P$，则$Q$。非$Q$，所以非$P$ 形式化之后就得到了 ： $((P\rightarrow Q)\land\neg Q)\rightarrow \neg P$ 当然，也有一些推理形式是错误的，比如$((P\rightarrow Q)\land\neg P)\rightarrow \neg Q$。这种推理形式我们不太关心。我们关心的是那些前提真则结论必真的推理形式，我们叫它正确的推理形式。 即，给定两个命题公式$A,B$，如果$A$取值为真，那么$B$取值也必为真，那么说$A\rightarrow B$就是一个正确的推理形式。这时候，我们称$A$重言蕴含$B$，或者称$B$为$A$的逻辑推论，并用符号$A\Rightarrow B$表示。 $\Rightarrow$可以理解为我们之前在初高中常见的“推导出”的符号。 基本的推理公式 常用公式 $P\land(P\rightarrow Q)\Rightarrow Q$⭐️⭐️ 假言推理，或者说叫分离规则，最常用的公式 $(P\rightarrow Q)\land(Q\rightarrow R) \Rightarrow P\rightarrow R$⭐️⭐️ 三段论 $P\land Q\Rightarrow P$⭐️ 最基础的公式，常用于分离合取的不同公式 $P\Rightarrow P\lor Q$⭐️ 常用于增加条件，方便三段论规范性 其余常见公式 这里的公式都可以由常用公式推导出。 $\neg(P\rightarrow Q)\Rightarrow P$ $\neg(P\rightarrow Q)\Rightarrow \neg Q$ $\neg P\Rightarrow P\rightarrow Q$ $Q\Rightarrow P\rightarrow Q$ $\neg P\land(P \lor Q)\Rightarrow Q$ $\neg Q\land(P\rightarrow Q)\Rightarrow\neg P$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 命题公式的真值表 对于一个含有$n$个命题变元$P_1,P_2,……,P_n$的命题公式$A$来说，可以根据$P_1,P_2,……,P_n$的真值给出$A$的真值，从而建立起了一个命题公式的真值表。 一般我们认为，从真值表出发写命题公式可以从列表中值为$T$或者值为$F$来写。 比如，如果真值表为 $$\begin{array}{|cc|c|}P&Q&{A}\\0&0&0\\0&1&1\\1&0&0\\1&1&1\end{array}$$ 那么，从取到$T$的那几行来看，$A=(\neg P\land Q)\lor(P\land Q)$。即，A在取$T$的时候，$P,Q$的取值应该让$A$的表达式中某个括号的真值为1。 从取到$F$的那几行来看，$A=(\neg P \lor\neg Q)\land(P\lor\neg Q)$。即，A在取到$F$的时候，$P,Q$的取值应该让$A$的表达式中某个括号的真值为0。 联结词的完备集 除了常见的5个联结词外，我们还可以定义更多的联结词。以下是三个较为常见的联结词。 异或$\overline\lor$ $$\begin{array}{|cc|c|}P&Q&{P\overline\lor Q}\\0&0&0\\0&1&1\\1&0&1\\1&1&0\end{array}$$ 与非$\uparrow$ $$\begin{array}{|cc|c|}P&Q&{P\uparrow Q}\\0&0&1\\0&1&1\\1&0&1\\1&1&0\end{array}$$ 或非$\downarrow$ $$\begin{array}{|cc|c|}P&Q&{P\downarrow Q}\\0&0&1\\0&1&0\\1&0&0\\1&1&0\end{array}$$ 理论上，其他的联结词都是存在的，但是因为使用甚少，所以常常不予讨论。 还有一个问题是，对于$n$个命题变项而言，我们可以定义出多少个联结词。容易知道，答案是$2^{2^n}$个。这由归纳法或者直接构造即可得证。 对偶式和补公式 将$A$中所有出现的$\land,\lor,T,F$分别以$\lor,\land,F,T$替换，得到公式$A^$，则称，$A^$是$A$的对偶式。或者说，$A$和$A^*$互为对偶式。 设$A=A(P_1,P_2,……,P_n)$，令$A^-=A(\neg P_1,\neg P_2,……,\neg P_n)$，则称$A^-$为A的补公式 那么，我们由如下定理： $\neg(A^* )=(\neg A)^* ,\neg(A^-)=(\neg A)^-$ $(A^* )^* =A=(A^-)^-$ $\neg A=(A^* )^-$ 其中，性质2.非常显然，性质1.和3.可以通过对式子中联结词个数进行归纳来证明。实际上，3.是摩根律的推广形式。 以下是对偶式、补公式有关真值性的的一些性质。 如果$A=B$，那么$A^* =B^*$ 如果$A\rightarrow B$永真，那么$B^* \rightarrow A^*$永真 若$A$永真，那么$A^-$永真。反之亦然 若$\neg A$永真，那么$A^*$永真。反之亦然。 范式 一些定义 为了描述方便，先定义几个术语。 简单命题$P$和$\neg P$被称为文字 一些文字的合取被称为合取式 一些文字的析取被称为析取式 ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 等值的定义 给定两个命题公式$A,B$，以及在$A,B$中出现的所有命题变相$P_1,P_2,……,P_n$，那么公式$A,B$一共有$2^n$种解释。如果在所有的解释下有$A$和$B$的真值都相等，那么称$A$和$B$等值,记做$A=B$ 等值定理指的是，$A=B$的充要条件是$A\leftrightarrow B$是重言式 等值公式 这部分极其重要。 转换公式 $P\rightarrow Q=\neg P\lor Q$ ⭐️⭐️ $P\leftrightarrow Q=(P\land Q)\lor(\neg P\land\neg Q)=(P\lor\neg Q)\land(\neg P\lor Q)$ ⭐️ 一般认为，在进行公式的转化和计算的时候，我们会把所有的蕴含和双蕴含转化为我们熟悉的与或非，这样计算会比较简单。 双重否定律 $\neg\neg P=P$ 结合律 $(P\lor Q)\lor R=P\lor(Q\lor R)$ $(P\land Q)\land R=P\land(Q\land R)$ $(P\leftrightarrow Q)\leftrightarrow R=P\leftrightarrow(Q\leftrightarrow R)$ $(P\rightarrow Q)\rightarrow R\not=P\rightarrow(Q\rightarrow R)$ ⚠️ 交换律 $P\lor Q=Q\lor P$ $P\land Q=Q\land P$ $P\leftrightarrow Q=Q\leftrightarrow P$ $P\rightarrow Q\not =Q\rightarrow P$ ⚠️ 分配律 $P\lor(Q\land R)=(P\lor Q)\land(P\lor R)$⭐️ $P\land(Q\lor R)=(P\land Q)\lor(P\land R)$⭐️ $P\rightarrow(Q\rightarrow R)=(P\rightarrow Q)\rightarrow(P\rightarrow R)$ $P\leftrightarrow(Q\leftrightarrow R)\not=(P\leftrightarrow Q)\leftrightarrow(P\leftrightarrow R)$ ⚠️ 摩根律 $\neg(P\lor Q)=\neg P\land\neg Q$ ⭐️⭐️ $\neg(P\land Q)=\neg P\lor\neg Q$ ⭐️⭐️ 其他常用公式 $\neg P\rightarrow Q=\neg Q\rightarrow P$ ⭐️ $P\rightarrow(Q\rightarrow R)=(P\land Q)\rightarrow R$ $(P\rightarrow R)\land(Q\rightarrow R)=(P\lor Q)\rightarrow R$ 置换和置换规则 对于公式$A$的子公式，用与之等值的公式代换称之为置换。 ...