本节主要为以下内容的笔记：https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/environment.html 训练到底在做什么？ 训练其实是在最小化通过数据集得到的经验风险： $$ \mathop{\mathrm{minimize}}_f \frac{1}{n} \sum_{i=1}^n l(f(\mathbf{x}_i), y_i), $$ 其中 $l$ 是损失函数，用来度量对于给定的标签 $y_i$，预测值 $f(\mathbf {x}_i)$ 的糟糕程度。 但是我们想要得到的又是什么呢？我们想要的是最小化实际风险，也就是最小化下面这个期望： $$ E_{p(\mathbf{x}, y)} [l(f(\mathbf{x}), y)] = \int\int l(f(\mathbf{x}), y) p(\mathbf{x}, y) \;d\mathbf{x}dy $$ 然而在实践中，我们通常无法获得总体数据。 因此，经验风险最小化， 是一种实用的机器学习策略，希望能近似最小化真实风险。 协变量偏移 在不同分布偏移中，协变量偏移可能是最为广泛研究的。这里我们假设：虽然输入的分布可能随时间而改变，但标签函数（即条件分布 $P(y \mid \mathbf{x})$ ）没有改变。统计学家称之为协变量偏移 （covariate shift），因为这个问题是由于协变量（特征）分布的变化而产生的。虽然有时我们可以在不引用因果关系的情况下对分布偏移进行推断，但在我们认为 $\mathbf{x}$ 导致 $y$ 的情况下，协变量偏移是一种自然假设。 协变量偏移的例子 现在我们使用猫狗照片 $\mathbf x$ 来训练一个猫狗分类器来给出猫狗标签 $y$ 训练数据集是真实的猫狗图片 测试数据集是卡通形象的猫狗图片 虽然猫狗图片的分布 $P(\mathbf{x})$ 被改变了（测试集上图片的分布改变了），但是猫狗图片对于猫狗分类的条件分布 $P(y \mid \mathbf{x})$ 并未改变（确定了照片，分类也就确定了） 这是由于特征分布的变化导致的（协变量的变化，这里的协变量就是图片风格） 在这种情况下，是猫狗图片 $\mathbf x$ 导致猫狗分类 $y$ 的，所以我们一般可以使用协变量偏移假设 协变量偏移的纠正 见：https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/environment.html#subsec-covariate-shift-correction 总结一下： 设目标分布为 $p(x)$，源分布为 $q(x)$，则根据协变量偏移假设 $$ p(y \mid \mathbf x) = q(y \mid \mathbf x) $$ 则 $$ \begin{aligned} &\int\int l(f(\mathbf{x}), y) p(\mathbf{x},y) \;d\mathbf{x}dy \\ =&\int\int l(f(\mathbf{x}), y) p(y \mid \mathbf{x})p(\mathbf{x}) \;d\mathbf{x}dy \\ =&\int\int l(f(\mathbf{x}), y) q(y \mid \mathbf{x})q(\mathbf{x})\frac{p(\mathbf{x})}{q(\mathbf{x})} \;d\mathbf{x}dy. \end{aligned} $$ 所以现在我们需要一个额外的权重 $$ \beta_i \stackrel{\mathrm{def}}{=} \frac{p(\mathbf{x}_i)}{q(\mathbf{x}_i)} $$ 来调整训练方式： $$ \mathop{\mathrm{minimize}}_f \frac{1}{n} \sum_{i=1}^n \beta_i l(f(\mathbf{x}_i), y_i) $$ 为了得到这个权重，我们可以通过训练一个二元分类器，来学习数据到底是来自于训练集还是来自于测试集。如果无法区分这两个分布，则意味着想相关的样本可能来自这两个分布中的任何一个。 另一方面，任何可以很好区分的样本都应该相应地显著增加或减少权重。 接下来是训练的方法：为了简单起见，假设我们分别从 $p(x)$ 和 $q(x)$ 两个分布中抽取相同数量的样本。 现在用标签 $z$ 表示：从 $p$ 抽取的数据为 $1$，从 $q$ 抽取的数据为 $-1$。 根据上面的假设，我们有： $$ P(z=1 \mid \mathbf{x}) = \frac{p(\mathbf{x})}{p(\mathbf{x})+q(\mathbf{x})} $$ $$ P(z=-1 \mid \mathbf{x}) = \frac{q(\mathbf{x})}{p(\mathbf{x})+q(\mathbf{x})} $$ 所以混合分布，也就是权重 $\beta$ 的分布可以由下式给出： $$ \frac{P(z=1 \mid \mathbf{x})}{P(z=-1 \mid \mathbf{x})} = \frac{p(\mathbf{x})}{q(\mathbf{x})} = \beta (\mathbf x) $$ 下一个问题就是如何训练得到 $P(z=1 \mid \mathbf{x})$ 了。我们可以使用对数回归： $$ P(z=1 \mid \mathbf{x})=\frac{1}{1+\exp(-h(\mathbf{x}))} = \sigma(h(\mathbf x)) $$ 这样的话： $$ \beta_i = \frac{1/(1 + \exp(-h(\mathbf{x}_i)))}{\exp(-h(\mathbf{x}_i))/(1 + \exp(-h(\mathbf{x}_i)))} = \exp(h(\mathbf{x}_i)) $$ 标签偏移 标签偏移（label shift）描述了与协变量偏移相反的问题。这里我们假设标签边缘概率 $P(y)$ 可以改变，但是类别条件分布 $P(\mathbf{x} \mid y)$ 在不同的领域之间保持不变。当我们认为 $y$ 导致 $\mathbf{x}$ 时，标签偏移是一个合理的假设。例如，预测患者的疾病，我们可能根据症状来判断，即使疾病的相对流行率随着时间的推移而变化。标签偏移在这里是恰当的假设，因为疾病会引起症状。在另一些情况下，标签偏移和协变量偏移假设可以同时成立。例如，当标签是确定的，即使 $y$ 导致 $\mathbf{x}$ ，协变量偏移假设也会得到满足。有趣的是，在这些情况下，使用基于标签偏移假设的方法通常是有利的。这是因为这些方法倾向于包含看起来像标签（通常是低维）的对象，而不是像输入（通常是高维的）对象。 标签偏移的例子 现在我们通过症状 $\mathbf x$ 来预测疾病 $y$ 然而，疾病随着时间的推移，疾病的流行程度发生了变化，也就是 $P(y)$ 发生了变化 但是尽管如此，一种确定的疾病导致的症状是不怎么会发生改变的，也就是 $P(\mathbf x \mid y)$ 基本保持不变 注意：这个情况下是 $y$ 决定 $\mathbf x$，所以我们就可以使用标签偏移假设 标签偏移的纠正 见：https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/environment.html#id14 总结一下： 设目标分布为 $p(x)$，源分布为 $q(x)$，则标签偏移假设 $$ p(\mathbf x \mid y) = q(\mathbf x \mid y) $$ 则 $$ \begin{aligned} &\int\int l(f(\mathbf{x}), y) p(\mathbf{x},y) \;d\mathbf{x}dy \\ =&\int\int l(f(\mathbf{x}), y) p(\mathbf{x} \mid y)p(y) \;d\mathbf{x}dy \\ =&\int\int l(f(\mathbf{x}), y) q(\mathbf{x} \mid y)q(y)\frac{p(y)}{q(y)} \;d\mathbf{x}dy \end{aligned} $$ 我们同样需要一个额外的权重： $$ \beta_i \stackrel{\mathrm{def}}{=} \frac{p(y_i)}{q(y_i)} $$ 其中，$q(y)$ 很容易估计，只需要使用训练数据集进行计算即可： $$ q(y_i) = \frac {\sum_{j=1}^n 1 \{y_i = y_j\}} {n} $$ 但是 $p(y)$ 就没有这么容易了。我们需要另辟蹊径。 虽然我们不能获得真实数据，但是我们有测试数据，我们可以用测试数据来估计真实数据。令 $\mu(\hat {\mathbf {y}}) \in \mathbb {R}^k$ 为模型测试时各个标签的预测均值，即 $\mu(\hat y_i)$ 为预测标签为 $i$ 时的预测均值。那么，我们可以有： $$ \mathbf Cp(\mathbf y) = \mu (\mathbf y) $$ 其中，$\mathbf C$ 是一个 $k \times k$ 的混淆矩阵，其中 $c_{ij}$ 代表验证集中真实标签为 $j$ 但是模型预测为 $i$ 的占比。因为作为一个估计，我们将矩阵乘法按照行向量拆解来看 $\sum_{j = 1}^k c_{ij} p(y_j) = \mu (\hat y_i)$。 对于 $\mathbf C$，应该存在 $\mathbf C^{-1}$，这样我们就能得到 $p(\mathbf y)$ $$ p(\mathbf{y}) = \mathbf{C}^{-1} \mu(\hat{\mathbf{y}}) $$ 也就能得到权重 $\beta$.
Preface 证明思路 Q&A 网络流的定义 网络流的性质 最大流解决的问题 Ford-Fulkerson方法 残存网络 增广路径 网络流的切割 最大流最小割定理 Ford-Fulkerson 算法 Preface 本文为我初三下时学习网络流的笔记整理，大多源自算法导论。当时学习的是网络流代数法建模。（手动@金牌教练） 证明思路 明确 Ford-Fulkerson 算法的思路：在残存网络找增广路，直到不存在增广路径为止 证明如果残存不存在增广路径等价于现在的网络流已经是最大流 Q&A Q: 增广路会不会越变越多？或者说，在找增广路的过程中会不会陷入死循环？ A: 首先我们要明确：最大流问题在正权有向无环图上必定有解。而增广路必然会增广 $f$，所以增广路的条数必然是有限的，所以必然不会陷入死循环。 网络流的定义 网络流：$G = (V,E)$为一个有向图，每条边 $(u,v) \in E$都有一个非负的容量值，即$c(u,v) \geq 0$。对于每条边$(u,v) \in E$，不存在反向边$(v,u)$。若$(u,v) \notin E$，规定$c(u,v) = 0$，图中不允许出现环，即为有向无环图。在网络流的所有节点$v \in V$当中，存在两个特殊节点：源点$s$，汇点$t$。对于所有$v \in V - \{s,t\}$，都存在路径$s \rightsquigarrow v \rightsquigarrow t$，即所有节点都是互相联通的，对于每个节点，至少存在一条进入与离开的路径，即：$|E| ≥ |V| - 1$。 网络流的性质 容量限制（capacity constraint）：对于每一条边$(u,v) \in E$，存在： $$ 0 ≤ f(u,v) ≤ c(u,v) $$ 流量守恒（flow conservation）：对于每一个节点$v \in V - \{s,t\}$，必定存在： $$ \sum_{u \in V} f(u,v) = \sum_{u \in V} f(v,u) $$ 其中，$f(u,v)$表示的是从节点$u \rightarrow v$的流。 上式成立是因为对于每个节点来说，流入流量必定等于流出流量。 在此，对一个图上的流$f$定义其的$|f|$值： $$ |f| = \sum_{v\in V} f(s,v) - \sum_{v\in V} f(v,s) $$ 尽管在一个最大流当中，并不会存在流入源点的边，因此对于其来说上式的后半部分$\sum_{v\in V} f(v,s)$的值为$0$，但是这在稍后讨论的残存网络中会有应用。 最大流解决的问题 现在有一张有向无环图，将其想象成一个水管，水流会从高向低流，图中的每一条边就是一根水管，水流是单向的，而水流的方向就是图中边的方向。水在水管中流动时，会有一个流量限制，也就是它的最大容积，在这里每条边同样有流量限制，若$C_i$表示第$i$根水管的流量上限，$x_i$表示第$i$根水管当前的水流流量，则可以表示为： $$ x_i \leq C_i,~i \in [1,n] $$ 在这个问题当中：$S$点和$T$点表示起点和终点。 在这个概念定义完成之后，便可以讨论最大流问题，也就是在一群水管当中（连接起点和终点），从起点到终点，最多可以流多少水。 举一个简单形象的例子：先看下面这幅图，每条边代表的是最大流量： 很明显，这里有两条路可以走，首先看上面那条，显然能够流过的最大流量为3，另外一条则为7，所以由$S$到$T$的最大流为10： 上面是一个简单的例子，类似于这样的问题是最大流问题。 通过网络流的表述，可以将其表达为，需要求在满足网络流的两个性质的情况下： $$ \max \{|f|\} $$ 其中$|f|$表示网络$G$的流，即为 $$ \begin {aligned} &\max \{\sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s)\} \\ =&\max \{\sum_{v \in V} f(s,v) - 0\} \\ =&\max \{\sum_{v \in V} f(s,v)\} \end {aligned} $$ 其根据流量守恒，亦为$\max\{\sum_{v\in V} f(v,t)\}$。 Ford-Fulkerson方法 对于一个网络$G$，存在对应的残存网络，每次在残存网络中寻找增广路径，当找到了一条增广路径，不难找出其原先对应的边，对于两个网络的这些边上的流进行修改，从而增加流的值，但是对于原图$G$来说，每一条增广路径却可能会对边增加或减少，但是这确实是非常必要的，比如在某一张有向图中，每个节点的值都相等，则若找到一条增广路径可能会使得其他增光路径消失，但是却会停止循环而得不到正确答案。虽然会不断增广，但是每次寻找的增广路径确实有源点出发，以汇点结束，所以总能使得$G$的流$f$不断增大。后面将进行证明。 $$ \begin {aligned} &\text{FORD-FULKERSON-METHOD}(G,s,t) \\ &1~~~~\text{initialize flow } f \text{ to }0 \\ &2~~~~\mathbf{while} \text{ there exists an augmenting path } p \text{ in the residual network }G_f \\ &3~~~~~~~~\text{augument flow } f \text{ along }p\\ &4~~~~\mathbf{return}~f \end {aligned} $$ 残存网络 残存网络记录的是流网络$G$中每条边的最大流量与当前流量之差。残存网络$G_f$由那些仍然可以调整流量的边构成。定义其残存容量$c_f(u,v) = c(u,v) - f(u,v)$，当$c_f$为正时，$(u,v)$仍可以添加流量，当$c_f(u,v) = 0$且$(u,v) \in E$时代表此边已满，所以$(u,v)$便不会是该残存网络的边。 同时由于前面的论述，需要给程序一个反悔的机会，所以一些不属于原网络的边也会出现在残余网络当中，那些边就是原网络的某些边的反向边，其的作用就是对这些边进行缩减。举个例子，若$(u,v) \in E$，为了表示一个正流量$f(u,v) > 0$的缩减，会将$(v,u)$添加入残余网络，由于原网络中不允许出现反向边，所以这样的行为不会产生任何问题。同样这样的操作又是必须的。 残余容量的定义： $$ c_f(u,v) = \begin {cases} c(u,v) - f(u,v)~~&(u,v) \in E \\ f(v,u)&(v,u) \in E \\ 0 &\text{otherwise} \end {cases} $$ 所以在此给出残余网络的定义：给定一个流网络$G = (V,E)$和一个流$f$，由$f$所诱导的图$G$的残存网络为$G_f = (V, E_f)$，其中： $$ E_f = \{(u,v)|c_f(u,v) > 0, (u,v) \in V\times V\} $$ 很容易证明： $$ |E_f| ≤ 2|E| $$ 所以可以发现虽然残存网络不完全符合流网络的定义，但是其仍然遵循其性质，比如容量限制： $$ 0 ≤ f'(u,v) ≤ c_f(u,v), ~~(u,v) \in E_f $$ 顺带一提，对于残差网络，流量也是守恒的。 若$f$为网络$G$当中的一个流，$f'$为对应的残存网络$G_f$中的一个流，定义$f \uparrow f'$为流$f'$对$f$的递增，就是增加后状态的$f$，它是一个由$V \times V$到$\mathbb{R}$的一个函数： $$ (f \uparrow f')(u,v) = \begin {cases} f(u,v) + f'(u,v) - f'(v,u) ~~~&(u,v) \in E\\ 0 &\text{otherwise} \end {cases} $$ 其中减少的是在残存网络中对应的$(u,v)$的反向边$(v,u)$的量，就是一种抵消的操作，和前文的操作一致。 定理$1$：设$G= (V,E)$为一个流网络，源点为$s$，汇点为$t$，设$f$为$G$中的一个流。设$G_f$为由流$f$所诱导的残存网络，设$f'$为$G_f$的一个流，那么定义的函数$f \uparrow f'$亦为$G$中的一个流，其值为$|f \uparrow f'| = |f| + |f'|$。其中$|\cdot|$符号所代表的就是网络的整个流。 证明：首先需要证明$f \uparrow f'$所构成的网络亦满足流网络的两个条件，即容量限制和流量守恒。 证明$f\uparrow f'$函数存在下界：若$(u,v) \in E$，则 $$ \begin {aligned} ~(f \uparrow f')(u,v) =&~f(u,v) + f'(u,v) - f'(v,u) \\ ≥&~f(u,v) + f'(u,v) - f(u,v)~~~~~(\text{because }f'(v,u) ≤f(u,v)) \\ =&~f'(u,v) \\ ≥&~0 \end {aligned} $$ 证明$f \uparrow f'$函数存在上界：若$(u,v) \in E$，则 $$ \begin {aligned} (f \uparrow f')(u,v) =&~f(u,v) + f'(u,v) - f'(v,u) \\ ≤&~f(u,v) + f'(u,v)~~~~~~~~~~~~~~~~~~~~(\text{because }f'(v,u) ≥ 0) \\ ≤&~f(u,v) + c_f'(u,v) \\ =&~f(u,v) + c(u,v) - f(u,v) \\ =&~c(u,v) \end {aligned} $$ 由前两点证明：函数$f\uparrow f'$存在上界下界，且上下界被容量约束，满足容量限制： $$ 0 ≤ (f\uparrow f')(u,v) ≤ c(u,v),~(u,v) \in E $$ 证明$f \uparrow f'$遵守流量守恒，由于$f,f’$均遵循流量守恒，即： $$ \sum_{v\in V} f(u,v) = \sum_{v\in V} f(v,u),~ \sum_{v\in V} f'(u,v) = \sum_{v\in V} f'(v,u) $$ 所以 $$ \begin{aligned} \sum_{v \in V} (f \uparrow f')(u,v) =&\sum_{v \in V} (f(u,v) + f'(u,v) - f'(v,u)) \\ =& \sum_{v \in V} f(u,v) + \sum_{v \in V}f'(u,v) - \sum_{v \in V}f'(v,u) \\ =& \sum_{v \in V} f(v,u) + \sum_{v \in V}f'(v,u) - \sum_{v \in V}f'(u,v) \\ =& \sum_{v \in V} (f(v,u) + f'(v,u) - f'(u,v)) \\ =& \sum_{v \in V} (f \uparrow f')(v,u) \end{aligned} $$ 证明原式：设$V_1 = \{v|(s,v) \in E\}$，$V_2 = \{v|(v,s) \in E\}$。可以很容易得到：$V_1\cup V_2 \subseteq V$，$V_1 \cap V_2 = \varnothing$。 根据定义可以发现： $$ \begin{aligned} |f| &= \sum_{v \in V}f(s,v) - \sum_{v \in V} f(v,s) \\ &= \sum_{v \in V_1} f(s,v) - \sum_{v \in V_2} f(v,s) \end {aligned} $$ 对于$f’$，由于$G_f$当中会存在反向边，所以： $$ \begin {aligned} |f'| &= \sum_{v \in V} f'(s,v) - \sum_{v \in V}f'(v,s) \\ &= \sum_{v\in V_1} f'(s,v) + \sum_{v\in V_2} f'(s,v) - \sum_{v\in V_1} f'(v,s) - \sum_{v\in V_2} f'(v,s) \end {aligned} $$ 对于$|f\uparrow f’|$，由于$(f \uparrow f’)(u,v)$在$(u,v) \in E$时才可能不为零，所以同样地： $$ \begin{aligned} |f \uparrow f'| &= \sum_{v \in V} (f \uparrow f')(s,v) - \sum_{v \in V} (f \uparrow f')(v,s) \\ &= \sum_{v \in V_1} (f \uparrow f')(s,v) - \sum_{v \in V_2} (f \uparrow f')(v,s) \\ &= \sum_{v \in V_1} (f(s,v) + f'(s,v) - f'(v,s)) - \sum_{v \in V_2} (f(v,s) + f'(v,s) - f'(s,v)) \\ \end {aligned} $$ 所以可得：$|f \uparrow f’| = |f| + |f’|$，证毕。 增广路径 对于给定网络$G = (V,E)$和流$f$，增广路径为残存网络$G_f$中一条从$s$到$t$的路径，对于任意一条可以找到的路径$p$，这条路径的容量限制显而易见，为： $$ c_f(p) = \min\{c_f(u,v), (u,v) \in p\} $$ 此时定义一个函数，也就是残存网络$G_f$的一个流： $$ f_p(u,v) = \begin {cases} c_f(p)~~~~~&\text{if }(u,v) \text{ is on the route }p \\ 0&\text{otherwise} \end {cases} $$ 此时根据$f \uparrow f'$以及$f_p$的定义，若必然可以得到： 推论$1$： $$ |f \uparrow f_p| = |f| + |f_p| > |f| $$ 因为 $|f_p| = c_f(p) > 0$. 其意义即为每次增广路径增广原路径时，原网络$G$中的$f(s,t)$将不断递增。也就是说，每次被增光之后，其总是比前一次更优的。 网络流的切割 对于流网络$G = (V,E)$中的一个切割，将节点集合$V$化为$S$和$T = V - S$，且满足$s \in S,~t\in T$。若$f$为一个流，则横跨切割$(S,T)$的净流量给出如下定义： $$ f(S,T) = \sum_{u \in S}\sum_{v\in T}f(u,v) - \sum_{u\in S}\sum_{v\in T}f(v,u) $$ 切割$(S,T)$的容量是： $$ c(S,T) = \sum_{u \in S}\sum_{v \in T} c(u,v) $$ 而对于网络$G$来说，其最小的切割就是切割容量的最小值。 注：这里的容量是单向的，因为要使网络切断，只需要计算从$S$到$T$的边的容量和，因为由$T$到$S$的边若不经过$S$到$T$是无法构成一条从$s$到$t$的路径，所以这种做法是有意义的。 定理$2$：设$f$为流网络$G$当中的一个流，该流网络的源点为$s$，汇点为$t$，设$(S,T)$为$G$的任意切割，存在$f(S,T) = |f|$。 证明：对于任意节点$u \in V -\{s,t\}$，由于其流量守恒，改写式子，得到： $$ \sum_{v\in V}f(u,v) - \sum_{v\in V} f(v,u) = 0 $$ 易得： $$ \sum_{u\in S-\{s\}}(\sum_{v\in V}f(u,v) - \sum_{v\in V} f(v,u)) = 0 $$ 因为 $t \notin S$。 所以： $$ \begin{aligned} |f| &= \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s) \\ &= \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s) + \sum_{u\in S-\{s\}}(\sum_{v\in V}f(u,v) - \sum_{v\in V} f(v,u)) \\ &= \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s) + \sum_{u\in S-\{s\}}\sum_{v\in V}f(u,v) - \sum_{u\in S-\{s\}}\sum_{v\in V} f(v,u) \\ &= \sum_{v \in V}(f(s,v) + \sum_{u\in S - \{s\}}f(u,v)) - \sum_{v \in V}(f(v,s) + \sum_{u\in S -\{s\}}f(v,u)) \\ &=\sum_{v \in V}\sum_{u\in S} f(u,v) - \sum_{v \in V}\sum_{u\in S} f(v,u) \end{aligned} $$ 由于$V = S \cup T$，$S \cap T = \varnothing$，所以可以将$V$按照$S$和$T$分解： $$ \begin {aligned} |f| &= \sum_{v \in V}\sum_{u \in S} f(u,v) - \sum_{v \in V}\sum_{u \in S} f(v,u) \\ &= \sum_{v \in S}\sum_{u \in S} f(u,v) + \sum_{v \in T}\sum_{u \in S} f(u,v) - \sum_{v \in S}\sum_{u \in S} f(v,u) - \sum_{v \in T}\sum_{u \in S} f(v,u) \\ &= (\sum_{u\in S}\sum_{v \in T}f(u,v) - \sum_{u\in S}\sum_{v \in T}f(v,u)) + (\sum_{v \in S}\sum_{u\in S}f(u,v) - \sum_{v \in S}\sum_{u\in S}f(v,u)) \\ &= (\sum_{u\in S}\sum_{v \in T}f(u,v) - \sum_{u\in S}\sum_{v \in T}f(v,u)) + 0 \\ &= f(S,T) \end {aligned} $$ 证毕。 推论$2$：网络流$G$当中任意流$f$的值不能超过$G$的任意切割$(S,T)$的容量，即$|f| ≤ c(S,T)$。 证明：根据定理$2$易得： $$ \begin {aligned} |f| &= f(S,T) \\ &= \sum_{u \in S}\sum_{v\in T} f(u,v) - \sum_{u \in S}\sum_{v\in T} f(v,u) \\ &≤\sum_{u \in S}\sum_{v \in T}f(u,v) \\ &≤\sum_{u \in S}\sum_{v \in T}c(u,v) \\ &= c(S,T) \end {aligned} $$ 证毕，但是这个推论非常具有意义，其意义为流的值不能超过割的容量，即最大流的值不能超过最小割的容量，即： $$ \begin {aligned} |f| ≤ |f|_{\max} ≤ c_{\min}(S,T) ≤ c(S,T) \end {aligned} $$ 最大流最小割定理 设$f$为流网络$G = (V,E)$中的一个流，该流的源节点为$s$，汇点为$t$，则下面的条件是等价的： $f$为$G$的最大流。 残存网络$G_f$中不包含任何增广路径。 $|f| = c(S,T)$，其中$(S,T)$为流网络$G$的某个切割。 证明： $(1) \Rightarrow (2)$：使用反证法。假设$f$为网络$G$中的最大流，而其残存网络$G_f$中却又存在增广路径，根据推论$1$，设这条增广路径为$p$，则这条增广路径的流即为$f_p$且$f_p > 0$，那么由于推论$1$，必定存在$|f \uparrow f_p| = |f| + |f_p| > |f|$，此时$|f \uparrow f_p|$亦为$G$当中的流，但是其却是严格大于$|f|$的，所以与假设矛盾，故可得出若为最大流则不再存在增广路径的结论。 $(2) \Rightarrow (3)$：若残存网络$G_f$中不包括任何增广路径，也就是说，在残存网络$G_f$中不存在任何从源点$s$到汇点$t$的路径。定义$S = \{v | v \in V, (s,v) \in E_f\}$，$T = V - S$，显然，$s \in S, t \in T$，所以可以定义$(S,T)$为网络流$G$的一个切割。现在考虑一对节点$u \in S, v \in T$。讨论： $(u,v) \in E$，必定存在$f(u,v) = c(u,v)$，使得$c_f(u,v) = c(u,v) - f(u,v) = 0$。由于$G$中不存在反向边，所以$f(v,u) = 0$。 $(v,u) \in E$，则必定有$f(v,u) = 0$，使得$c_f(u,v) = f(v,u) = 0$。 $(u,v) \notin E, (v,u) \notin E$，则必定存在$f(u,v) = f(v,u) = c(u,v) = c(v,u) = 0 = c_f(u,v) = c_f(v,u)$。 根据上述三点可以得出无论何种情况，$f(v,u)$都为$0$，所以便可以根据定理$2$：$|f| = f(S,T)$列出方程并化简： $$ \begin {aligned} |f| &= f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) - \sum_{u \in S}\sum_{v \in T} f(v,u) \\ &= \sum_{u \in S}\sum_{v \in T}f(u,v) - \sum_{u \in S}\sum_{v \in T} 0 \\ &= c(S,T) \end {aligned} $$ 所以得到$|f| = c(S,T)$。 $(3) \Rightarrow (1)$：根据推论$2$，对于所有切割$(S,T)$，$|f| ≤ c(S,T)$，由于现在$|f| = c(S,T)$，则证明此时$f$为最大流。 综上所述，此定理成立。 同样地，在此根据最大流最小割定理及推论$2$，可以简单得出结论：由于 $$ |f| = \max\{\sum_{v\in V} f(s,v) - \sum_{v\in V} f(v,s)\} \Leftrightarrow |f|_{\max} =c(S,T) $$ 所以根据推论$2$得出的不等式，若$f$为最大流，则： $$ \begin {aligned} &|f| ≤|f|_{\max} \\ \Rightarrow &|f| ≤|f|_{\max} = c_k(S,T),~ |f|_{\max} ≤ c(S,T) \\ \Rightarrow &c_k(S,T) ≤ c(S,T) \\ \Rightarrow &c_k(S,T) = \min\{c(S,T)\} \\ \Rightarrow &c_{\min}(S,T) = |f|_{\max} \end {aligned} $$ 即证明了： 网络的最大流就是其的最小割（切割容量） Ford-Fulkerson 算法 根据上一节的推导，不断地在残存网络中寻找增广路径$p$，使得$f$更新为$f \uparrow f_p$并且更新残存网络$G_f$的不断地迭代的过程中，知道不再存在增广路径时，根据最大流最小割定理，这个流$f$已经是最大流了： $$ \begin {aligned} &\text{FORD-FULKERSON}(G,s,t) \\ &1~~~~\mathbf{for}\text{ each edge }(u,v)\in G.E \\ &2~~~~~~~~~~~~(u,v).f = 0\\ &3~~~~\mathbf{while}\text{ there exist a path from }s\text{ to }t\text{ in the residual network }G_f \\ &4~~~~~~~~~~~~c_f(p) = \min\{c_f(u,v) ~| ~(u,v) \text{ is in the route }p\} \\ &5~~~~~~~~~~~~\mathbf{for }\text{ each edge }(u,v)\text{ in }p \\ &6~~~~~~~~~~~~~~~~~~~~\mathbf{if}\text{ }(u,v) \in E \\ &7~~~~~~~~~~~~~~~~~~~~~~~~~~~~(u,v).f = (u,v).f+c_f(p) \\ &8~~~~~~~~~~~~~~~~~~~~~~~~~~~~c_f(u,v) = c_f(u,v) - c_f(p) \\ &9~~~~~~~~~~~~~~~~~~~~~~~~~~~~c_f(v,u) = c_f(v,u) + c_f(p) \\ 1&0~~~~~~~~~~~~~~~~~~~~\mathbf{else}\\ 1&1~~~~~~~~~~~~~~~~~~~~~~~~~~~~(v,u).f = (v,u).f - c_f(p) \\ 1&2~~~~~~~~~~~~~~~~~~~~~~~~~~~~c_f(v,u) = c_f(v,u) - c_f(p) \\ 1&3~~~~~~~~~~~~~~~~~~~~~~~~~~~~c_f(u,v) = c_f(u,v) + c_f(p) \\ 1&4~~~~\mathbf{return}\text{ }\sum_{v \in G.V}f(s,v) \end {aligned} $$ 这是基本Ford-Fulkerson的算法，但是它很废，时间复杂度较高，而且当遇到某些奇葩网络的时候就会被强奸。之后我们会讨论他的优化：Dinic 算法。
为什么要正则化？ 在探讨这个问题之前，我们需要先引入欠拟合和过拟合的概念。 左侧：欠拟合，high bias, $error_{train} \gg error_{dev}$ 右侧：过拟合，high variance, $error_{train} \rightarrow 0\%$ 在过拟合的时候我们需要引入正则化，来避免过拟合。 这里介绍两种正则化方式： 权重衰减 (weight decay) Dropout Weight Decay Weight Decay 的主要思想就是加快参数的更新幅度，也就是说增大损失函数，使得梯度下降的步幅变大。但为什么这样可以防止过拟合？根据奥卡姆剃刀法则，我们倾向于认为，参数越小，网络越不复杂，越不容易过拟合，而实践也证明了这一点。 下面的公式节选自我之前的汇报笔记： 逻辑回归: $\min_{w, b}J(w, b), w\in \mathbb R^{n_x}, b\in \mathbb R$ L2 正则化：重定义 $J(w, b)$ $$ J(w, b) = \frac{1}{m}\sum_{i = 1}^{m}\mathcal L(\hat y^{(i)}, y^{(i)}) + \frac{\lambda}{2m}||w||_2^2,~||w||_2^2 = \sum_{j = 1}^{n_x}w_j^2 = w^\mathrm T w $$ L1 正则化：重定义 $J(w, b)$ $$ J(w, b) = \frac{1}{m}\sum_{i = 1}^{m}\mathcal L(\hat y^{(i)}, y^{(i)}) + \frac{\lambda}{2m}||w||_1,~||w||_1 = \sum_{j = 1}^{n_x} |w_j| $$ 神经网络：重定义损失函数： $$ J(W^{[1]}, b^{[1]},\cdots, W^{[l]}, b^{[l]}) = \frac{1}{m}\sum_{i = 1}^m \mathcal L(\hat y^{(i)}, y^{(i)}) + \frac{\lambda}{2m}\sum_{i = 1}^m ||W^{[l]}||_\mathrm F^2 $$ $$ ||W^{[l]}||_\mathrm F^2 = \displaystyle\sum_{i = 1}^{n^{[l]}}\displaystyle\sum_{j=1}^{n^{[l-1]}}(W^{[l]}_{ij})^2 $$ 红色的项标出了正则化后迭代中增加的项： $$ dW^{[l]} = \frac{1}{m} dZ^{[l]} A^{[l-1] T} \color{red}{ + \frac {\lambda}{m}W^{[l]}} $$ $$ W^{[l]} \leftarrow W^{[l]} - \alpha\frac{1}{m} dZ^{[l]} A^{[l-1] T}\color{red}{ - \alpha \frac {\lambda}{m}W^{[l]}} $$ 下面的公式出自 d2l 教科书，能让我们更好的理解超参数 $\lambda$ 的作用： 对于线性回归的损失函数： $$ L(\mathbf{w}, b) = \frac{1}{n}\sum_{i=1}^n \frac{1}{2}\left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right)^2 $$ 我们将其重定义为： $$ J(\mathbf{w}, b) = L(\mathbf{w}, b) + \frac{\lambda}{2} \|\mathbf{w}\|^2, $$ 我们来看参数的迭代式发生了什么变化。这是原来的迭代式： $$ \begin{aligned} \mathbf{w} &\leftarrow \mathbf{w} - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \partial_{\mathbf{w}} l^{(i)}(\mathbf{w}, b) = \mathbf{w} - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \mathbf{x}^{(i)} \left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right),\\ b &\leftarrow b - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \partial_b l^{(i)}(\mathbf{w}, b) = b - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right). \end{aligned} $$ 这是经过 L2 正则化后的迭代式： $$ \begin{aligned} \mathbf{w} & \leftarrow \left(1{\color{red}{- \eta\lambda}} \right) \mathbf{w} - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \mathbf{x}^{(i)} \left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right) \end{aligned} $$ Intuitive understanding of L2 Regularization $$ \lambda \uparrow \Longrightarrow W \downarrow \Longrightarrow \text{ some of the hidden units may loss effect} $$ $$ \lambda \uparrow \Longrightarrow W \downarrow \Longrightarrow Z = WA + b \downarrow \Longrightarrow \tanh (z) \rightarrow \text {linear} \Longrightarrow \text {simpler network} $$ $$ \lambda \uparrow \Longrightarrow \text {high variance, overfit} \rightarrow \text{just right} \rightarrow \text {high bias, underfit} $$ Weight Decay 的代码实现 如果是自己写，那么我们只需要： def l2_penalty(w): return torch.sum(w.pow(2)) / 2 l = loss(net(X), y) + lambd * l2_penalty(w) 如果使用 pytorch，我们可以更好地定义 optimizer: trainer = torch.optim.SGD([ {"params": net[0].weight,'weight_decay': wd}, {"params": net[0].bias}], lr=lr) Dropout 另一种正则化，也就是防止过拟合的方法就是 dropout。 下面的内容引用自 d2l 教课书: 在探究泛化性之前，我们先来定义一下什么是一个“好”的预测模型？ 我们期待“好”的预测模型能在未知的数据上有很好的表现： 经典泛化理论认为，为了缩小训练和测试性能之间的差距，应该以简单的模型为目标。 简单性以较小维度的形式展现， 我们在 4.4节 讨论线性模型的单项式函数时探讨了这一点。 此外，正如我们在 4.5节 中讨论权重衰减（正则化）时看到的那样， 参数的范数也代表了一种有用的简单性度量。 简单性的另一个角度是平滑性，即函数不应该对其输入的微小变化敏感。 例如，当我们对图像进行分类时，我们预计向像素添加一些随机噪声应该是基本无影响的。 1995年，克里斯托弗·毕晓普证明了 具有输入噪声的训练等价于Tikhonov正则化 [Bishop, 1995]。 这项工作用数学证实了“要求函数光滑”和“要求函数对输入的随机噪声具有适应性”之间的联系。 然后在2014年，斯里瓦斯塔瓦等人 [Srivastava et al., 2014] 就如何将毕晓普的想法应用于网络的内部层提出了一个想法： 在训练过程中，他们建议在计算后续层之前向网络的每一层注入噪声。 因为当训练一个有多层的深层网络时，注入噪声只会在输入-输出映射上增强平滑性。 这个想法被称为暂退法（dropout）。 暂退法在前向传播过程中，计算每一内部层的同时注入噪声，这已经成为训练神经网络的常用技术。 这种方法之所以被称为暂退法，因为我们从表面上看是在训练过程中丢弃（drop out）一些神经元。 在整个训练过程的每一次迭代中，标准暂退法包括在计算下一层之前将当前层中的一些节点置零。 需要说明的是，暂退法的原始论文提到了一个关于有性繁殖的类比： 神经网络过拟合与每一层都依赖于前一层激活值相关，称这种情况为“共适应性”。 作者认为，暂退法会破坏共适应性，就像有性生殖会破坏共适应的基因一样。 那么关键的挑战就是如何注入这种噪声。 一种想法是以一种无偏向（unbiased）的方式注入噪声。 这样在固定住其他层时，每一层的期望值等于没有噪音时的值。 在毕晓普的工作中，他将高斯噪声添加到线性模型的输入中。 在每次训练迭代中，他将从均值为零的分布 $\epsilon \sim \mathcal{N}(0,\sigma^2)$ 采样噪声添加到输入 $\mathbf{x}$， 从而产生扰动点 $\mathbf{x}' = \mathbf{x} + \epsilon$， 期望是 $E[\mathbf{x}'] = \mathbf{x}$。 在标准暂退法正则化中，通过按保留（未丢弃）的节点的分数进行规范化来消除每一层的偏差。 换言之，每个中间值 $h$ 以暂退概率 $p$ 由随机变量 $h'$ 替换，如下所示： $$ \begin{aligned} h' = \begin{cases} 0 & \text{ 概率为 } p \\ \frac{h}{1-p} & \text{ 其他情况} \end{cases} \end{aligned} $$ 根据此模型的设计，其期望值保持不变，即 $E[h'] = h$。 Dropout 的代码实现 纯手写： def dropout_layer(X, dropout): assert 0 <= dropout <= 1 # 在本情况中，所有元素都被丢弃 if dropout == 1: return torch.zeros_like(X) # 在本情况中，所有元素都被保留 if dropout == 0: return X mask = (torch.rand(X.shape) > dropout).float() return mask * X / (1.0 - dropout) pytorch: net = nn.Sequential(nn.Flatten(), nn.Linear(784, 256), nn.ReLU(), # 在第一个全连接层之后添加一个dropout层 nn.Dropout(dropout1), nn.Linear(256, 256), nn.ReLU(), # 在第二个全连接层之后添加一个dropout层 nn.Dropout(dropout2), nn.Linear(256, 10)) def init_weights(m): if type(m) == nn.Linear: nn.init.normal_(m.weight, std=0.01) net.apply(init_weights) 注意：对于 pytorch： net.eval() # 不启用 dropout （这两个 method 还有其他作用） net.train() # 启用 dropout Reference https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/weight-decay.html https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/dropout.html https://blog.csdn.net/jialibang/article/details/108991631
注：本节内容为《具体数学》(原书第二版) 第五章 二项式系数 5.1 基本恒等式 的旁注，但可以独立阅读。 多项式推理法 对于多项式 $A(x)$ 与 $B(x)$ 而言。我们设其都是关于 $x$ 的不高于 $n$ 次多项式。 现在，我们求 $A(x)$ 与 $B(x)$ 的差，记作 $C(x)$： $$ A(x) - B(x) = C(x) $$ 其中，$C(x)$ 为一个不高于 $n$ 次的多项式，也就是说 $C(x)$ 有不多于 $n$ 个零点，除非 $C(x)$ 恒为零。 所以，如果我们要证明 $A(x)$ 与 $B(x)$ 相等，我们只需要证明，$A(x) - B(x)$ 存在多于 $n$ （也就是 $A(x), B(x)$ 最高次幂）个零点。换句话说，如果我们能找到多余 $n$ 个 $x_i$ 使得 $A(x_i) = B(x_i)$，我们便能证明 $A(x) = B(x)$ 多项式推理法在组合数恒等式证明中的应用 由于二项式系数在上指标与下指标均为整数的情况下会有非常简洁且容易处理的形式，我们通常能够简单地给出证明。但是，当上指标是实数时就会变得十分困难。这个时候，我们便可以使用多项式推理法。在进行向实数的推广之前，我们首先需要确认我们想要证明的式子是有限次数的式子。接下来，由于我们能够找到无穷多组正整数解，所以必然能将式子推广到实数域。证毕。 Reference 《组合数学》 P130
注：本节内容为《具体数学》(原书第二版) 第五章 二项式系数 5.1 基本恒等式 的旁注。 P129 关于超出范围的整数 $k$ 的讨论 $$ \binom{n}{k} = 0, k < 0 $$ $$ \binom{n}{k} = \frac {n^{\underline{k}}}{k!} = \frac {n!\times 0 \times (-1)^{k-n-1}(k-n-1)!}{k!} = 0, k > n \geq 0, n,k \in \mathbb Z $$ 帕斯卡定理的推论 我在其他文章里写过，这里就再写一遍吧。 $$ \sum_{i=0}^k \binom{n}{n+i} =\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} = \binom{n+k+1}{n+1} $$ 证明： $$ \begin{aligned} \sum_{i=0}^k \binom{n}{n+i} &=\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} \\ &= \binom{n+1}{n+1} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} \\ &= \binom{n+2}{n+1} + \binom{n+2}{n} + \cdots + \binom{n+k}{n} \\ &= \cdots \\ &= \binom{n+k+1}{n+1} \end{aligned} $$ 再列一下书上证明的其他推论： $$ \sum_{i \leq n} \binom{n+i}{i} = \binom{n}{0} + \binom{n+1}{1} + \cdots + \binom{n + k}{k} = \binom{n+k+1}{k} $$ $$ \sum_{i = 0}^k \binom{i}{n} = \binom{0}{n} + \binom{1}{n} + \cdots + \binom{k}{n} = \binom{k+1}{n+1} $$ P135 证明二项式定理的级数收敛 二项式定理： $$ (1+z)^r = \sum_{k=-\infty}^{+\infty} \binom{r}{k} z^k, |z| < 1 $$ 证明： 令 $$ f(z) = (1+z)^r $$ 不难由归纳法证明 $$ f^{(k)} (z) = r^{\underline{k}}(1+z)^{r-k} $$ 根据泰勒级数： $$ f(z) = \frac {f(0)} {0!} z^0 + \frac {f'(0)}{1!} z^1 + \frac {f''(0)}{2!} z^2 + \cdots = \sum_{k \geq 0} \frac {f^{(k)}(0)} {k!} z^k $$ 不难发现， $$ (1+z)^r = \sum_{k=-\infty}^{-1} \binom{r}{k} z^k + \sum_{k=0}^{+\infty} \binom{r}{k} z^k = \sum_{k\geq 0} \binom{r}{k} z^k $$ 而其中的每一项都与泰勒级数对应： $$ \binom{r}{k}z^k = \frac {f^{(k)}(0)} {k!}z^k $$ 故恒等式成立。接下来，我们要证明收敛。 不难发现： $$ \sum_{k\geq 0} \binom{r}{k} z^k \leq \sum_{k\geq 0} \left | \binom{r}{k} z^k \right | $$ 根据比较审敛法，我们证明右侧那个级数收敛即可。右侧级数： $$ u_k = \left | \binom{r}{k} z^k \right | $$ $$ \frac {u_{k+1}} {u_k} = \left | \frac {\binom{r}{k+1} z^{k+1}} {\binom{r}{k} z^k} \right | = \left | \frac {r-k} {k+1} z \right | = \left | \left ( \frac {r+1} {k+1} - 1 \right) z \right| $$ $$ \rho = \lim_{k \rightarrow \infty} \frac {u_{k+1}} {u_k} = |z| < 1 $$ 故根据比值审敛法，收敛。故原级数收敛。 P137 证明 $(5.18)$ $$ \sum_{k\leq m} \binom rk \left ( \frac r 2 - k\right) = \frac {m+1} 2 \binom{r}{m+1} $$ 假设 $m$ 成立，归纳 $m+1$ $$ \begin{aligned} &\sum_{k\leq m+1} \binom rk \left ( \frac r 2 - k\right) \\ =& \sum_{k\leq m} \binom rk \left ( \frac r 2 - k\right) + \binom{r}{m+1}\left( \frac r 2 - m - 1\right) \\ =& \frac {m+1} 2 \binom{r}{m+1} + \binom{r}{m+1}\left( \frac r 2 - m - 1\right) \\ =& \frac {r-m-1} {2} \binom{r}{m+1} \\ =& \frac {r-m-1} {2} \frac {m+2} {r-m-1} \binom{r}{m+2} = \frac {m+2}2\binom{r}{m+2} \end{aligned} $$ 证毕。 P137 证明 $(5.19)$ P138, 递归式补充：这一页第二个和第三个公式： $$ \sum_{k \leq m} \rightarrow \sum_{k \leq m-1} + \sum_{k=m} $$ $$ \sum_{k \leq m} \rightarrow \sum_{k-1 \leq m-1} $$ 关于等式右侧的补充，记 $$ \begin{aligned} S_m &= \sum_{k \leq m} \binom{-r}{k}(-x)^k(x+y)^{m-k} \\ &= \sum_{k \leq m-1} \binom{-r}{k}(-x)^k(x+y)^{m-k} + \binom{-r}{m}(-x)^m \\ &=(x+y)S_{m-1} + \binom{-r}{m}(-x)^m \end{aligned} $$ P138 $(5.19)$ 推论补充 取 $x=y=1$, $r=m+1$ 时： $$ \sum_{k \leq m} \binom{2m+1}{k} = \sum_{k\leq m} \binom{-m-1}{k}(-1)^k 2^{m-k} = \sum_{k \leq m} \binom{m+k}{k}2^{m-k} $$ 后两步使用了上指标反转。 以及，左边之所以是上指标是 $2m+1$ 的二项式系数的一半，是因为我们看帕斯卡三角形，对于 $m$ 而言，$2m+1$ 层有 $2m+2$ 项（从零开始），所以 $0\sim m$ 正好记一半，$m+1$ 项。以及，这里还用到了： $$ (1+1)^n = \sum_k \binom{n}{k} $$ P139 多项式定理补充 二项式定理的多项式系数写法： $$ (x+y)^n = \sum_{0\leq a, b \leq n, a+b=n} \frac {(a+b)!} {a!b!} x^ay^b = \sum_{0\leq a, b \leq n, a+b=n} \binom{a+b}{a,b} x^ay^b $$ 以及多项式系数的组合意义： $$ \begin{aligned} \binom{a_1+a_2+\cdots+a_m}{a_1,a_2,\cdots,a_m} &= \frac {(a_1+a_2+\cdots+a_m)!}{a_1!a_2!\cdots a_m!} \\ &= \binom{a_1+a_2+\cdots+a_m}{a_2+a_3+\cdots+a_m}\cdots\binom{a_{m-1}+a_m}{a_m} \end{aligned} $$ 组合意义： 先在 $\sum_{k=1}^ma_k$ 中选出 $a_1$ 个，作为 $x_1$ 的幂的贡献 再在 $\sum_{k=2}^{m}a_k$ 中选出 $a_{2}$ 个，作为 $x_{2}$ 的幂的贡献 $\cdots$ 最后在 $\sum_{k=m-1}^{m}a_k$ 中选出 $a_{m-1}$ 个，作为 $x_{m-1}$ 的幂的贡献 Reference http://www.doczj.com/doc/2e368f0b08a1284ac95043a8.html https://baike.baidu.com/item/%E6%AF%94%E8%BE%83%E5%AE%A1%E6%95%9B%E6%B3%95/7543573
Softmax 运算 softmax 运算用于将实数序列映射为和为一的概率序列，换句话说，softmax 运算用于将实数值规格化，使其和为一，映射成一个合理的概率分布。 下面是 softmax 的定义： $$ \hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o})\quad \text{where}\quad \hat{y}_j = \frac{\exp(o_j)}{\sum_k \exp(o_k)} $$ 对数似然与交叉熵损失函数 这里应用 d2l 教科书上的一系列公式与语段： softmax函数给出了一个向量 $\hat{\mathbf{y}}$， 我们可以将其视为“对给定任意输入$\mathbf{x}$的每个类的条件概率”。 例如，$P(y=\text{猫} \mid \mathbf{x})$。 假设整个数据集 $\{\mathbf{X}, \mathbf{Y}\}$ 具有 $n$ 个样本， 其中索引 $i$ 的样本由特征向量 $\mathbf{x}^{(i)}$ 和独热标签向量 $\mathbf{y}^{(i)}$ 组成。 我们可以将估计值与实际值进行比较： $$ P(\mathbf{Y} \mid \mathbf{X}) = \prod_{i=1}^n P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) $$ 根据最大似然估计，我们最大化 $P(\mathbf{Y} \mid \mathbf{X})$ ，相当于最小化负对数似然： $$ -\log P(\mathbf{Y} \mid \mathbf{X}) = \sum_{i=1}^n -\log P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) = \sum_{i=1}^n l(\mathbf{y}^{(i)}, \hat{\mathbf{y}}^{(i)}) $$ 其中，对于任何标签 $\mathbf{y}$ 和模型预测 $\hat{\mathbf{y}}$ ，损失函数为： $$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j $$ 再论交叉熵损失函数 我们一定要明确一个点：交叉熵损失函数的值是一个数。我们再来看这个公式： $$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j $$ $\mathbf{y}$ 是一个独热编码的向量 $\hat{\mathbf{y}}$ 是经过 softmax 计算的各分量和为一的预测向量 对于所有的 $y_j$，只有一个值为 $1$，其余皆为 $0$. 交叉熵损失函数的实现 # y_hat: [vector] -> matrix # y: [scalar, represent index] -> vector # the outer dimension represent sample count def cross_entropy(y_hat, y): # 这里的 range(len(y_hat)) 的意思是对于每一个 sample 都做计算，是一个 index 集合 return - torch.log(y_hat[range(len(y_hat)), y]) y_hat = torch.tensor( [[0.2, 0.7, 0.1], [0.2, 0.7, 0.1], [0.4, 0.6, 0]]) y = [1, 1, 1] cross_entropy(y_hat, y) Out: tensor([0.3567, 0.3567, 0.5108]) 由于是批量计算，所以这里 y_hat 是矩阵，y 是向量，返回值也是一个向量。 Softmax 带来的问题 https://zh-v2.d2l.ai/chapter_linear-networks/softmax-regression-concise.html#subsec-softmax-implementation-revisited 简而言之，就是 softmax 既有可能带来指数所造成的数值过大的问题，也有可能带来除法所造成的精度丧失的问题。 为了解决第一个问题，我们可以尝试通过在计算 softmax 之前从每个参数 $o_k$ 中减去 $\max(o_k)$ : $$ \begin{aligned} \hat y_j & = \frac{\exp(o_j - \max(o_k))\exp(\max(o_k))}{\sum_k \exp(o_k - \max(o_k))\exp(\max(o_k))} \\ & = \frac{\exp(o_j - \max(o_k))}{\sum_k \exp(o_k - \max(o_k))} \end{aligned} $$ 为了解决第二个问题，我们可以将 softmax 与交叉熵损失函数结合起来一起计算。因为交叉熵损失函数带了一个对数运算，可以与指数运算相抵消： $$ \begin{aligned} \log{(\hat y_j)} & = \log\left( \frac{\exp(o_j - \max(o_k))}{\sum_k \exp(o_k - \max(o_k))}\right) \\ & = \log{(\exp(o_j - \max(o_k)))}-\log{\left( \sum_k \exp(o_k - \max(o_k)) \right)} \\ & = o_j - \max(o_k) -\log{\left( \sum_k \exp(o_k - \max(o_k)) \right)}. \end{aligned} $$ pytorch 中上述的过程 在 pytorch 中，softmax 与 cross entropy loss 是一起实现的，具体我们可以看 pytorch 的文档，其中对 nn.CrossEntropyLoss 是这样定义的： $$ \ell(x, y) = L = \{l_1,\dots,l_N\}^\top, \text{where} $$ $$ l_n = - w_{y_n} \log \frac{\exp(x_{n,y_n})}{\sum_{c=1}^C \exp(x_{n,c})} \cdot \mathbb{1}\{y_n \not= \text{ignore\_index}\} $$ 可以发现，其自带了 softmax 运算。 一般来说，我们会使用 loss = nn.CrossEntropyLoss(reduction='none') 来计算。 至于这个 reduction 参数，其实就是保留 mini-batch 每个样本的值，返回一个向量。其他的选择： $$ \ell(x, y) = \begin{cases} \sum_{n=1}^N \frac{1}{\sum_{n=1}^N w_{y_n} \cdot \mathbb{1}\{y_n \not= \text{ignore\_index}\}} l_n, & \text{if reduction} = \text{“mean";}\\ \sum_{n=1}^N l_n, & \text{if reduction} = \text{“sum".} \end{cases} $$ Reference https://zh-v2.d2l.ai/chapter_linear-networks/softmax-regression-concise.html https://pytorch.org/docs/master/generated/torch.nn.CrossEntropyLoss.html#torch.nn.CrossEntropyLoss https://github.com/pytorch/pytorch/blob/master/torch/csrc/api/include/torch/nn/modules/loss.h https://blog.csdn.net/goodxin_ie/article/details/89645358
注：本节内容为《具体数学》(原书第二版) 第四章 数论 基础题的答案。 4.14 (a) $$ \begin{aligned} ~& \gcd(km, kn) = t \\ \Leftrightarrow ~& t_p = \min(k_p+m_p,k_p+n_p) \\ \Leftrightarrow ~& t_p = k_p + \min(m_p,n_p) \\ \Leftrightarrow ~& t_p - k_p = \min(m_p,n_p) \\ \Leftrightarrow ~& \frac t k = \gcd(m,n), \text{According to (4.12)} \\ \Leftrightarrow ~& k\gcd(m,n) = \gcd(km, kn) \end{aligned} $$ (b) $$ \begin{aligned} ~&\operatorname{lcm}(k m, kn)=t \\ \Leftrightarrow ~& t_{p}=\max \left(k_{p}+k_{m}, k_{p}+k_{n}\right) \\ \Leftrightarrow ~& t_{p}=k_{p}+\max \left(k_{m}, k_{n}\right) \\ \Leftrightarrow ~& t_{p}-k_{p}=\max \left(k_{m}, k_{n}\right) \\ \Leftrightarrow ~& \frac{t}{k}=\operatorname{lcm}(m, n), \text{According to (4.12)} \\ \Leftrightarrow ~& k \operatorname{lcm}(m, n)=\operatorname{lcm}(k m, k n) \\ \end{aligned} $$ 4.15 不可能 引理 1：除了 $e_1$，所有欧几里得数都是奇数。 证明：根据欧几里得数的构造，每两个欧几里得数都互相互素，而 $e_1 = 2$，故后面的欧几里得数都必然不是偶数，为奇数。 引理 2：所有欧几里得数同余 $5$ 交替于 $2$ 与 $3$。 证明：通过归纳法证明： $e_1 = 2$，$e_2 = 3$，成立。 设对于所有 $k \leq 2n$ 题设都成立。 对于 $$ e_{2n+1} = \prod_{k=1}^{2n} e_k + 1 \equiv (2 \times 3) ^ n + 1 \equiv 1^n+1 \equiv 2 \pmod 5 $$ $$ e_{2n+2} = e_{2n}\prod_{k=1}^{2n} e_k + 1 \equiv 2 \times 1^n + 1 \equiv 3 \pmod 5 $$ Q.E.D. 故根据引理 2，素数 $5$ 不是任何一个欧几里得数的因子。 4.16 可由归纳法证得 $$ \sum_{i=1}^n \frac 1 {e_i} = 1 - \frac 1 {e_{n+1} - 1} $$ 证明： $$ \sum_{i=1}^{n+1} \frac 1 {e_i} = 1 - \frac 1 {e_{n+1} - 1} + \frac 1 {e_{n+1}} = 1 - \frac 1 {e_{n+1}(e_{n+1} - 1)} = 1 - \frac 1 {e_{n+2}} $$ 4.17 当 $n > m$ 时，我们有 $$ 2^{2^n} = 2^{2^m2^{n-m}} = \left(2^{2^m}\right)^{2^{n-m}} $$ $$ \begin{aligned} 2^{2^n} &= 2^{2^n} + 2^{2^m} - 2^{2^m} \\ &= \left(2^{2^m}\right)^{2^{n-m}} + 2^{2^m} - 2^{2^m} \\ &= 2^{2^m}\left(1 + \left(2^{2^m}\right)^{2^{n-m}-1}\right) - 2^{2^m} \\ &= 2^{2^m}\left(1 + 2^{2^m}\right)\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - 2^{2^m} \end{aligned} $$ $$ 2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) = \frac {2^{2^n} + 2^{2^m}} {2^{2^m}+1} $$ 所以 $$ \begin{aligned} \left\lfloor \frac {f_n} {f_m} \right\rfloor &= \left\lfloor \frac {2^{2^n}+1} {2^{2^m}+1} \right\rfloor \\ &= \left\lfloor \frac {2^{2^m}\left(1 + 2^{2^m}\right)\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - 2^{2^m}+1} {2^{2^m}+1} \right\rfloor \\ &= 2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) + \left\lfloor \frac {1 - 2^{2^m}} {2^{2^m}+1} \right\rfloor \\ &= 2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - \left\lceil \frac {2^{2^m}-1} {2^{2^m}+1} \right\rceil \\ &= \frac {2^{2^n} + 2^{2^m}} {2^{2^m} + 1} - \left\lceil \frac {2^{2^m}-1} {2^{2^m}+1} \right\rceil = \frac {2^{2^n} + 2^{2^m}} {2^{2^m} + 1} - 1 = \frac {2^{2^n} - 1} {2^{2^m} + 1} \end{aligned} $$ 所以 $$ \begin{aligned} f_n \bmod f_m = f_n - f_m\left\lfloor \frac {f_n} {f_m} \right\rfloor = 2^{2^n} + 1 - \frac {2^{2^n} - 1} {2^{2^m} + 1}({2^{2^m} + 1}) = 2 \end{aligned} $$ 故根据欧几里得递推式 $$ \gcd(f_n, f_m) = \gcd(f_n \bmod f_m, f_m) = \gcd(f_m, 2) = 1 $$ 即 $$ f_n \perp f_m $$ 4.18 试证逆否命题： 若 $n$ 不是 $2$ 的幂次，则 $2^n + 1$ 为合数。 证明： 根据题设，$n$ 可表示为 $$ n = qm, q \text{ is odd} $$ 则 $$ 2^n + 1 = (2^m + 1) (2^{n-m} - 2^{n-2m} + \cdots - 2^{m} + 1) $$ 4.19 试证： $$ \begin{aligned} \sum_{1 \leqslant k<n}\left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor &=\sum_{1<m \leq n}\left\lfloor\left(\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor\right)^{-1}\right\rfloor \\ &=n-1-\sum_{k=1}^{n}\left\lceil\left\{\frac{(k-1) !+1}{k}\right\}\right\rceil \end{aligned} $$ 证明： 考察等式左边的求和项 $$ \left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor $$ 根据 $\varphi$ 函数的性质： $$ \varphi(k + 1) \leq k $$ 而 $\displaystyle \left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor = 1 \Leftrightarrow \varphi(k+1)=k$ 当且仅当 $k$ 是素数。所以等式左侧即为 $$ \sum_{1 \leqslant k<n}\left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor = \pi(n) $$ 类似地，考察右侧第一个式子： $$ \left \lfloor \frac {\frac m k} {\left \lceil \frac m k \right \rceil} \right \rfloor =1 \Leftrightarrow \frac {\frac m k} {\left \lceil \frac m k \right \rceil} = 1 \Leftrightarrow {\frac m k} = {\left \lceil \frac m k \right \rceil} \Leftrightarrow k \backslash m $$ 故 $$ \sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor = \sum_{1\leqslant k < m}[k\backslash m] $$ $$ \begin{aligned} \sum_{1<m \leq n}\left\lfloor\left(\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor\right)^{-1}\right\rfloor = \sum_{1<m \leq n}\left\lfloor\left(\sum_{1\leqslant k < m}[k\backslash m]\right)^{-1}\right\rfloor \end{aligned} $$ 接下来我们来考察其内部： 易得 $$ \left\lfloor\left(\sum_{1\leqslant k < m}[k\backslash m]\right)^{-1}\right\rfloor \leq 1 $$ 且 $$ \left\lfloor\left(\sum_{1\leqslant k < m}[k\backslash m]\right)^{-1}\right\rfloor =1 \Leftrightarrow \sum_{1\leqslant k < m}[k\backslash m] = 1 \Leftrightarrow [m \in P] $$ 故等式右侧亦为 $\pi(n)$ $$ \sum_{1<m \leq n}\left\lfloor\left(\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor\right)^{-1}\right\rfloor = \sum_{1<m \leq n} [m\in P] = \pi(n) $$ 最后，我们来分析最后一个式子： $$ n-1-\sum_{k=1}^{n}\left\lceil\left\{\frac{(k-1) !+1}{k}\right\}\right\rceil $$ 不难看出 $$ \left\lceil\left\{\frac{(k-1) !+1}{k}\right\}\right\rceil = 0 \Leftrightarrow \left\{\frac{(k-1) !+1}{k}\right\} = 0 \Leftrightarrow k \backslash [(k-1) !+1] $$ 根据威尔逊定理，等价于 $$ k \in P, k > 1 $$ 故最后一个式子中的和式减去的都是不是素数的数，故最后留下来的就是素数的个数，故也为 $\pi(n)$。Q.E.D. 4.20 构造见答案。这里证明答案的正确性。 若 $b = \lg^{(n)} p_n$，那么 $\displaystyle\left\lfloor 2^b \right\rfloor, \left\lfloor 2^{2^b} \right\rfloor, \left\lfloor 2^{2^{2^b}} \right\rfloor, \cdots, \left\lfloor \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^b}}}}}_{n} \right\rfloor$ 都是素数。 证明： 考察第 $n$ 项： $$ \left\lfloor \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^b}}}}}_{n} \right\rfloor = \lfloor p_n \rfloor = p_n $$ 为素数。 考察第 $n-1$ 项： $$ \left\lfloor \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^b}}}}}_{n-1} \right\rfloor = \left\lfloor \lg p_n \right\rfloor $$ 根据构造 $$ 2^{p_{n-1}} < p_n < 2^{p_{n-1}+1} \Rightarrow p_{n-1} < \lg p_n < p_{n-1} + 1 $$ 所以 $$ \left\lfloor \lg p_n \right\rfloor = p_{n-1} $$ 为素数。 不难看出，我们可以使用归纳法证得这些数都是素数。 然后这里规避了一个问题： $$ \lim_{n\rightarrow \infty} \lg^{(n)}p_n $$ 是否存在？答案是肯定的。我们这就来证明。 首先证明 $\lg^{(n)}p_n$ 上下有界： 根据定义： $$ \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^2}}}}}_{n} < \cdots < 2^{2^{p_{n-2}}} < 2^{p_{n-1}} < p_n < 2^{p_{n-1}+1} < 2^{2^{p_{n-2}+1}+1} < \cdots < \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}+1}}_{n} $$ 所以 $$ \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^2}}}}}_{n} < p_n < \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}+1}}_{n} $$ 故显然有下界: $$ \lg^{(n)}p_n > 1 $$ 上界则比较难分析： $$ \begin{aligned} \lg^{(n)}p_n &< \lg^{(n)}\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}+1}}_{n} \\ &= \lg^{(n-1)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-1}+1 \right ) \\ &< \lg^{(n-1)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-1}\times 2 \right ) \\ &= \lg^{(n-1)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+2}}}_{n-1} \right ) \\ &= \lg^{(n-2)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-2}+2 \right ) \\ &< \lg^{(n-2)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-2} \times 2 \right ) \\ &\cdots \\ &< \lg^{(2)} \left ( 2^{2+1} + 2 \right) \approx 1.91795 \end{aligned} $$ 故上界亦存在。 接下来我们证明 $\lg^{(n)}p_n$ 是递增的。这是显然的。因为根据定义 $$ \begin{aligned} &2^{p_{n}} < p_{n+1} < 2^{p_{n}+1} \\ \Rightarrow~ & \lg p_{n+1} > p_n \\ \Rightarrow~ & \lg^{(n)}\lg p_{n+1} > \lg^{(n)} p_n \\ \Rightarrow~ & \lg^{(n+1)} p_{n+1} > \lg^{(n)} p_n \end{aligned} $$ Q.E.D. 4.21 构造见答案。这里证明答案的正确性。 证明： 根据贝特朗假设，我们有： $$ 1 < p \leq 2 $$ $$ 2 < p \leq 4 $$ $$ 4 < p \leq 8 $$ $$ \cdots $$ 由于这些区间互相独立且并集可以构成整个正整数集，我们便可以给这些素数都加上下标。 $$ 1 < P_1 \leq 2 $$ $$ 2 < P_2 \leq 4 $$ $$ 4 < P_3 \leq 8 $$ $$ \cdots $$ 所以 $$ 2^{n-1} < P_n \leq 2^{n} < 10^n $$ 令 $$ {K}=\sum_{{k} \geqslant 1} 10^{-{k}^{2}} {P}_{{k}}=.200300005 \ldots $$ 则 $$ \begin{aligned} &\left\lfloor\left(10^{n^{2}} K\right) \bmod 10^{n}\right\rfloor \\ =&\left\lfloor\left(10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor \\ \end{aligned} $$ 其中 $$ P_k < 10^k \Rightarrow \frac {P_k} {10^k} < 1\Rightarrow \frac {P_k} {10^{k^2}} < \frac {10^k} {10^{k^2}} = \frac {1} {10^{k^2-k}} $$ 但是和式仍然十分复杂，所以我们不妨对于 $k$ 的大小拆开分析： $$ \begin{aligned} &\left\lfloor\left(10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor \\ =& \left\lfloor10^{n^{2}}\left(\frac {P_n} {10^{n^2}} + \sum_{1 \leqslant {k} < n} \frac {{P}_{{k}}} {10^{{k}^{2}}} + \sum_{{k} > n} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor \end{aligned} $$ 对于 $k > n \geq 1$ ，令 $k = n + \Delta k, \Delta k > 0$，有 $$ \begin{aligned} 10^{n^2}\frac {P_k} {10^{k^2}} &< \frac {10^{n^2}} {10^{k^2-k}} \\ &= 10^{n^2-k^2+k} \\ &\leq 10^{n-2n\Delta k + \Delta k - \Delta k^2} \\ &\leq 10^{n-2n\Delta k - \Delta k + 1} \\ &\leq 10^{-n - \Delta k + 1} \end{aligned} $$ 故 $$ 10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}=\sum_{k=n+1}^{\infty}10^{n^2}\frac {P_k} {10^{k^2}} < \sum_{\Delta k = 1}^{\infty} 10^{-n-\Delta k + 1} \leq 1 $$ 对于 $1 \leq k < n$，我们有 $$ 10^{n^2}\frac {P_k} {10^{k^2}} = P_k 10^{n^2-k^2} = P_k10^{2n-1} \times10^{n^2-k^2-2n+1} $$ 其中 $n^2-k^2-2n+1 \geq 0$。所以 $$ 10^{n^2}\frac {P_k} {10^{k^2}} \equiv 0 \pmod {10^{2n-1}} \Rightarrow 10^{n^2}\frac {P_k} {10^{k^2}} \equiv 0 \pmod {10^{n}} $$ 接下来带入回拆分后的原式： $$ \begin{aligned} &\left\lfloor10^{n^{2}}\left(\frac {P_n} {10^{n^2}} + \sum_{1 \leqslant {k} < n} \frac {{P}_{{k}}} {10^{{k}^{2}}} + \sum_{{k} > n} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \right\rfloor \\ \equiv &\left\lfloor P_n + 0 + \epsilon \right\rfloor \pmod {10^{n}}, 0 < \epsilon < 1 \\ \equiv & P_n \pmod {10^{n}} \end{aligned} $$ 因为 $P_n < 10^n$，所以有 $$ \left\lfloor\left(10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor = \left\lfloor\left(10^{n^{2}} K\right) \bmod 10^{n}\right\rfloor = P_n $$ 4.22 试证逆否命题： $$ (11\cdots 11)_b $$ 中 $1$ 的个数不是素数，则此数必定不是素数。 证明： 设 $1$ 的个数为 $n$。因为 $n$ 不是素数，故有两种情况： (1) $n = 1$，原数为 $1$ 不是素数，成立。 (2) $n$ 为合数，我们能找到一个 $d \backslash n, d > 1$ 所以 $$ \underbrace{(11\cdots 11)_b}_{n} = \underbrace{\underbrace{(1\cdots 1)}_{d} \cdots \underbrace{(1\cdots 1)_b}_{d}}_{n / d} $$ 接下来的分解留给读者思考。 4.23 不难给出通式： $$ \rho (x) = \sum_{k \geq 1} [2^k \backslash x] $$ 同样不难看出： $$ \rho (2x) = \rho(x) + 1, x \geq 1 $$ $$ \rho (2x + 1) = 0 $$ 关于与河内塔的关联，答案已经给出，不再详述。有兴趣的话可以用归纳法证得。 4.24 $$ \epsilon_{p}(n !)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\cdots=\sum_{k \geqslant 1}\left\lfloor\frac{n}{p^{k}}\right\rfloor $$ 思考将 $n$ 表达成 $p$ 进制。 $$ (\cdots a_1 a_0) _p $$ 这个和式就是右位移求和。思考每一个数位 $a_k$ 在此过程中的贡献，让我们记其为 $s_k$ $$ s_k = a_k ( p^0 + p^1 + \cdots + p^{k-1} ) = a_k \frac {p^k - 1} {p - 1} = \frac {a_k p^k} {p-1} - \frac {a_k} {p-1} $$ 对 $s_k$ 求和，我们就能得到 $\epsilon_p(n!)$: $$ \begin{aligned} \epsilon_p(n!) &= \sum_k s_k = \sum_k \left ( \frac {a_k p^k} {p-1} - \frac {a_k} {p-1} \right ) \\&= \frac 1 {p-1} \left ( \sum_ {k} a_k p^k - \sum_k a_k \right) = \frac {n - v_p(n)} {p - 1} \end{aligned} $$ 4.25 (a) $k\perp m$，试证 $$ k \backslash\backslash n, m \backslash\backslash n \Leftrightarrow km \backslash\backslash n $$ 证明： $$ k \backslash\backslash n, m \backslash\backslash n $$ 等价于 $$ \gcd(n/k, k) = \gcd(n/m, m) = 1 $$ 等价于 $$ \min(n_p - k_p, k_p) = 0 $$ $$ \min(n_p - m_p, m_p) = 0 $$ 因为 $k \perp m$，所以 $$ m_p k_p = 0 $$ 故可推出 $$ \min(n_p - k_p - m_p, k_p + m_p) = \min(n_p - \max (k_p, m_p), \max (k_p, m_p)) = 0 $$ 即 $$ km \backslash\backslash n $$ 现在我们反过来证明。假设 $km \backslash\backslash n$ 成立，则 $$ \min(n_p - \max (k_p, m_p), \max (k_p, m_p)) = 0 $$ 对于 $m_p \neq 0$ 与 $k_p \neq 0$ 分别可推出： $$ \min(n_p - m_p, m_p) = 0, m_p \neq 0 $$ $$ \min(n_p - k_p, k_p) = 0, k_p \neq 0 $$ 同时等于 $0$ 的情况显然成立，因为 $n_p \geq 0$ 由于都是等价变换。证毕。 (b) 不成立。 取 $\gcd(m,n)=12, m = 24, n = 36$ 即可推翻。 4.26 可以证明，$\mathcal G_N$ 为 Stern-Brocot Tree 的一颗子树。 证明： 若 $\mathcal G_N$ 不是 Stern-Brocot Tree 的一颗子树，那么可能会有如下情况： 不递增【根据构造，排除】 不是最简分数【根据构造，排除】 儿子元素出现，然而父亲元素不出现。 我们着重证明第三种情况不可能发生。因为儿子元素的分子分母大于任意父亲元素的分子分母，根据 $m'n'\leq N$ 可知 $mn < N$。 故 $\mathcal G_N$ 一定是 Stern-Brocot Tree 的一颗子树。 而 $m'n-n'm=1$ 是 Stern-Brocot Tree 子树的性质，故一定为真。 4.27 见答案，容易得出。总体思路就是字典序。 4.28 打表易得。 4.29 由构造法可知，Stern-Brocot Tree 以中间的 $\frac 1 1$ 为界，左右对称，除了会交换分子分母的位置，因为左侧是 $\frac 0 1, \frac 1 1$，右侧是 $\frac 1 1 \frac 1 0$。这个结论可以对 Stern-Brocot Tree 的每一层的数的情形做归纳证得。 此外，我们发现，如果将构造序列中的 L 与 R 交换，我们就达到的两个位置关于 $\frac 1 1$ 对称。 结合第一个结论，我们可知，交换构造序列的 L 和 R 可以得到一对倒数。 题目中 $x$ 是一个二进制序列 $(.b_1b_2b_3\cdots)_2$，而 $1-x = (.\bar{b_1}\bar{b_2}\bar{b_3}\cdots)_2$，其中 $\bar{b} = 1 - b$。故 $1-x$ 对应的构造序列就是 L 和 R 交换的序列。所以我们可以得到 $1 / \alpha$。 4.30 中国剩余定理 已独立写成文章。 4.31 证明： 我们不妨首先将这个数表示为 $$ (a_n a_{n-1} \cdots a_0)_{10} $$ 因为 $$ 10 \equiv 1 \pmod 3 $$ 所以我们有 $$ 10^n \equiv 1 \pmod 3 $$ $$ a_n 10^n \equiv a_n \pmod 3 $$ 故 $$ \begin{aligned} a &= \sum_{k=0}^n a_k 10^k \\ &\equiv \sum_{k=0}^n a_k \pmod 3 \end{aligned} $$ Q.E.D. 推广： 对于 $b$ 进制数，若 $b \equiv 1 \pmod m$，则这个数能被 $m$ 整除等价于这个数在 $b$ 进制下的数位表示之和能够被 $d$ 整除。 4.32 见其他文章。欧拉定理专门写过一篇文章证明过。 4.33 若 $f(m)$ 和 $g(m)$ 都为积性函数，则对于 $m = m_1m_2, m_1 \perp m_2$，我们总有： $$ f(m) = f(m_1)f(m_2) $$ $$ g(m) = g(m_1)g(m_2) $$ 且 $$ f(1) = g(1) = 1 $$ 接下来我们看 $h(m)$ $$ h(1) = \sum_{d\backslash 1} f(d)g(m/d) = f(1)g(1) = 1 $$ 满足条件，再看一般的 $m_1 \perp m_2$: $$ \begin{aligned} h(m_1m_2) &= \sum_{d\backslash m_1m_2} f(d) g(m_1m_2/d) \\ &= \sum_{d = 1, m_1, m_2, m_1m_2} f(d) g(m_1m_2/d) \\ &=f(1)g(m_1m_2) + f(m_1)g(m_2)+f(m_2)g(m_1)+f(m_1m_2)g(1) \\ &=g(m_1)g(m_2) + f(m_1)g(m_2) + f(m_2)g(m_1) + f(m_1)f(m_2) \\ &=(g(m_1) + f(m_1))(g(m_2)+f(m_2)) \\ &=\left(\sum_{d\backslash m_1} f(d)g(m_1/d)\right)\left(\sum_{d\backslash m_2} f(d)g(m_2/d)\right) \\ &=h(m_1)h(m_2) \end{aligned} $$ 所以 $h(m)$ 为积性函数。Q.E.D. 4.34 试证前者为后者的特例。 $$ g(m) = \sum_{d\mid m}f(d) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) $$ $$ g(x) = \sum_{d \geq 1} f\left(\frac x d\right) \Leftrightarrow f(x) = \sum_{d \geq 1} \mu(d) g\left(\frac xd\right) $$ 我们不妨先把前者写为与后者更加相符的等价形式： $$ g(m) = \sum_{d\mid m}f\left(\frac m d\right) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) $$ 接下来我们开始证明： 我们设函数 $f, g$ 满足莫比乌斯反演，且都为定义在整数集上的函数，即 $$ f(x) = 0, x \notin \mathbb Z $$ $$ g(x) = 0, x \notin \mathbb Z $$ 则有 $$ g(m) = \sum_{d \geq 1} f\left(\frac m d\right) = \sum_{d \backslash m} f\left(\frac m d\right) $$ $$ f(m)=\sum_{d \geq 1} \mu(d) g\left(\frac md\right)=\sum_{d \backslash m} \mu(d) g\left(\frac{m}{d}\right) $$ 此时，由于普遍莫比乌斯反演成立，我们便能推出特殊的莫比乌斯反演。
注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 节中的项链问题的旁注。 P116 $mN(m,n)$ $$ m N(m, n)=\sum_{a_{0}, \ldots, a_{m-1} \in S_{n}} \sum_{0 \leqslant k<m}\left[a_{0} \ldots a_{m-1}=a_{k} \ldots a_{m-1} a_{0} \ldots a_{k-1}\right] $$ 这个式子没有问题。注意 $k$ 的下标，$k$ 包含了 $0$，所以不支持循环位移的数也会被计入。 我们来考察一下这个和式到底计入了那些值： $k=0$，不考虑循环位移产生的影响，完全对 $S_n$ 进行枚举，贡献为 $n^m$ $0<k<m$，考虑循环位移产生的影响，贡献为 $mN(m,n)-n^m$ P116 引理回顾 这页的下半部分在阐述循环位移的等价情况。这里我们回顾一下 4.8 节证明的引理。 对于 $\bmod m$ 来说，$0 \bmod m, k \bmod m, 2k \bmod m, \cdots, (m-1)k\bmod m$ 为 $0, d, 2d, \cdots, m-d$ 的排列的 $d$ 次循环。 P117 $N(m,n)$ 推导补充 $$ \begin{aligned} {N}({m}, {n}) &=\frac 1 m\sum_{0 \leqslant {k}<{m}} n^{\gcd(m,k)} \\ &=\frac 1 m\sum_{0 \leqslant {k}<{m}}\sum_{d\backslash m} n^{d}[d=\gcd(m,k)] \\ &=\frac 1 m\sum_{d\backslash m} \sum_{0 \leqslant {k}<{m}}n^{d}[d=\gcd(m,k)] \\ &=\frac{1}{{m}} \sum_{{d} \backslash {m}} {n}^{{d}} \sum_{0 \leqslant {k}<{m}}[{d}=\operatorname{gcd}({k}, {m})] \\ &=\frac{1}{{m}} \sum_{{d} \backslash {m}} n^{{d}} \sum_{0 \leqslant {k}<{m}}[{k} / {d} \perp {m} / {d}] \\ &=\frac{1}{{m}} \sum_{{d} \backslash {m}} n^{{d}} \sum_{0 \leqslant {k}<{m} / {d}}[{k} \perp {m} / {d}] \end{aligned} $$ P119 归纳证明的补充 我们还需要证明当 $m=p^k$ 时， $$ \sum_{d\backslash m} \varphi(d) n^{m/d} \equiv 0 \pmod m $$ 证明： $$ \begin{aligned} \sum_{d\backslash m} \varphi(d) n^{m/d} &= n^{p^k} + \varphi(p) n^{p^{k-1}} + \cdots + \varphi(p^{k-1})n^p + \varphi(p^k)n \\ &=n^{p^k} + (p^2-p)n^{p^{k-1}} + \cdots + (p^{k-2}-p^{k-1})n^p + (p^k-p^{k-1})n \\ &=(n^{p^k}-n^{p^{k-1}}) + p(n^{p^{k-1}}-n^{p^{k-2}}) + \cdots + p^{k-1}(n^p-n) + p^k \end{aligned} $$ （上面的每一步都可以用归纳法证得） 接下来，我们将要证明： $$ n^{p^k}-n^{p^{k-1}} \equiv 0 \pmod {p^k} $$ $$ n^{p^{k-1}}-n^{p^{k-2}} \equiv 0 \pmod {p^{k-1}} $$ $$ \cdots $$ $$ n^p - n \equiv 0 \pmod {p^{k}} $$ 为了证明这个，我们可以用归纳的方式以及二项式展开证明下面这个结论： $$ n^{p^k} = n^{p^{k-1}} + p^k \mathfrak{O}, \mathfrak O \in \mathbb Z $$ P119 为什么内和对 $m_2$ 同余于 $0$? 考察和式 $$ \sum_{d_1\backslash m_1} \varphi(d_1) \left ( \sum_{d_2 \backslash m_2} \varphi(d_2) (n^{m_1/d_1}) ^ {m_2/d_2} \right) $$ 这里有 $$ N(m_2, n^{m_1 / d_1}) = \sum_{d_2 \backslash m_2} \varphi(d_2) (n^{m_1/d_1}) ^ {m_2/d_2} $$ 根据假设 $$ N(m_2, n') \equiv 0 \pmod {m_2}, n'\in\mathbb Z $$ 故内和对 $m_2$ 同余于 $0$.
注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注。 P112 $\mu$ 函数为什么能递推？ 先看定义： $$ \boxed{\sum_{d\mid m}\mu(d)}=\boxed{[m=1]} $$ $\mu(m)$ 之所以是递归式，是因为最初我们可以很轻松地确定：$\mu(1)=1$，之后随着 $m$ 值的增长，我们计算 $\mu(m)$ 时用到的值 $\mu(d)$ 一定有 $d < m$。故整个过程可以通过递推得到。 P113 莫比乌斯反演的证明 试证: $$ g(m) = \sum_{d\mid m}f(d) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) $$ 证明： 若 $g(m) = \sum_{d\mid m}f(d)$，则 $$ \begin{aligned} &\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) \\ &=\sum_{d \backslash m} \mu\left(\frac{m}{d}\right) g(d) \\ &=\sum_{d \backslash m} \mu\left(\frac{m}{d}\right) \sum_{k \backslash d} f(k) \\ &=\sum_{d \backslash m} \sum_{k \backslash d} \mu\left(\frac{m}{d}\right) f(k) \\ &=\sum_{k \backslash m} \sum_{d \backslash(m / k)} \mu\left(\frac{m}{k d}\right) f(k), \text{by equation (4.9)} \\ &=\sum_{k \backslash m} \sum_{d \backslash(m / k)} \mu(d) f(k) \\ &=\sum_{k \backslash m} f(k) \sum_{d \backslash(m / k)} \mu(d) \\ &=\sum_{k \backslash m} f(k)\left[\frac m k=1\right]=f(m) \end{aligned} $$ 若 $f(m)=\sum_{d \backslash m} \mu(d) g\left(\frac{m}{d}\right)$，则 $$ \begin{aligned} &\sum_{d\backslash m}f(d) \\ =&\sum_{d\backslash m} \sum_{k\backslash d} \mu\left(\frac d k\right) g\left(k\right) \\ =&\sum_{k\backslash m} \sum_{d\backslash (m/k)} \mu\left ( \frac {dk} {k} \right) g(k) \\ =&\sum_{k\backslash m} \sum_{d\backslash (m/k)} \mu(d) g\left (k\right) \\ =&\sum_{k\backslash m} g\left (k\right) \sum_{d\backslash (m/k)} \mu(d) \\ =&\sum_{k\backslash m} g\left (k\right) \left[\frac m k = 1\right] \\ =&\sum_{k\backslash m} g\left (k\right) \left[m = k\right] \\ =&g(m) \end{aligned} $$ Q.E.D. 此处也包含了习题 12 的证明。 P114 $\sum\Phi\left(\frac x d\right)$ 的含义 我们来考察下面的式子的含义: $$ \sum_{d \geq 1} \Phi \left( \frac xd\right) $$ 其中 $$ \Phi(x) = \sum_{1 \leq k \leq x} \varphi(k) $$ 这个式子代表了 满足 $0\leq m < n \leq x$ 的基本分数 $\displaystyle\frac m n$的个数（既有最简分数，又有）。 为什么？我们不妨来逐项分析。同时，我们首先考虑 $x\in \mathbb Z$ 的情况。 $\displaystyle\Phi \left( \frac xd\right)$ 代表的是最大分母为 $\displaystyle \left \lfloor\frac xd \right\rfloor$ 的法里级数的个数减去 1 (那个 1/1)，也就是在所有满足条件的基本分数中被约分 $d$ 后的个数（因为法里级数都是最简分数）。 所以，我们只要穷举 $d \geq 2$，便能得到所有可以约分的情况下的被约分的非最简分数的个数。而当 $d = 1$，即 $\frac x d = x$ 时，得到的就是最简分数的个数，也就是法里级数的个数减去 1. 故 $$ \sum_{d \geq 1} \Phi \left( \frac xd\right) $$ 就代表了所有基本分数的个数。 接下来，我们来论证为什么 $x\in \mathbb R$ 结论仍然成立。注意到，我们这里唯一使用到 $x$ 的地方就是 $\displaystyle \left \lfloor\frac xd \right\rfloor$ 与 $1 \leq k \leq x$，我们不妨稍作改写，使之对整数仍然成立： 变为 $\displaystyle \left\lfloor\frac {\left\lfloor x\right\rfloor}d \right\rfloor$ 与 $1 \leq k \leq \lfloor x\rfloor$。可以发现，根据我们在第三章证明的性质： $$ \left\lfloor\frac {\left\lfloor x\right\rfloor}d \right\rfloor = \left \lfloor\frac xd \right\rfloor $$ 以及 $k \in \mathbb Z$，我们可以发现所有关系依旧成立！所以 $x\in\mathbb R$ 的范围仍然是对的。 故 $$ \sum_{d \geq 1} \Phi \left( \frac xd\right) = \frac 1 2 \lfloor x \rfloor \lfloor 1+x \rfloor $$ P115 更广泛的莫比乌斯反演 $$ g(x) = \sum_{d \geq 1} f\left(\frac x d\right) \Leftrightarrow f(x) = \sum_{d \geq 1} \mu(d) g\left(\frac xd\right) $$ 证明： 若 $g(x) = \sum_{d \geq 1} f\left(\frac x d\right)$，则 $$ \begin{aligned} \sum_{d \geqslant 1} \mu(d) g(x / d) &=\sum_{d \geqslant 1} \mu(d) \sum_{k \geqslant 1} f(x / k d) \\ &=\sum_{d \geqslant 1} \sum_{k \geqslant 1} f(x / k d) \mu(d) \\ &=\sum_{d \geqslant 1} \sum_{k \geqslant 1} \sum_{m} f(x / m) \mu(d) [m=kd] \\ &=\sum_{m \geqslant 1} f(x / m) \sum_{d, k \geqslant 1} \mu(d)[m=k d] \\ &=\sum_{m \geqslant 1} f(x / m) \sum_{d \backslash m} \mu(d) \\ &=\sum_{m \geqslant 1} f(x / m)[m=1]=f(x) \end{aligned} $$ 若 $f(x) = \sum_{d \geq 1} \mu(d) g\left(\frac xd\right)$，则 $$ \begin{aligned} \sum_{d \geq 1} f\left(\frac x d\right) &= \sum_{d \geq 1} \sum_{k\geq 1} \mu(k) g(x/kd) \\ &=\sum_{d \geq 1} \sum_{k\geq 1} \sum_m \mu(k) g(x/m) [m=kd] \\ &=\sum_{m \geq 1}g(x/m)\sum_{d,k\geq 1}\mu(k)[m=kd] \\ &=\sum_{m \geq 1}g(x/m)\sum_{k\backslash m}\mu(k) \\ &=\sum_{m \geq 1}g(x/m)[m=1] \\ &=g(x) &\square \end{aligned} $$
注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注。 P111 最上方的推导 $$ n \perp m \Leftrightarrow n \perp m_1 , n \perp m_2 $$ $$ \Leftrightarrow \gcd(n, m_1) = 1, \gcd(n, m_2) = 1 $$ $$ \Leftrightarrow \gcd(n \bmod m_1, m_1) = 1, \gcd(n \bmod m_2, m_2) = 1 $$ $$ \Leftrightarrow n \bmod m_1 \perp m_1, n \bmod m_2 \perp m_2 $$ P111 “好的”的推导 这里的将互素定义为“好的”的一系列论述让人摸不着头脑。其实它就是指出互素的充要条件。然后注意 $n < m$，所以整个逻辑链可以构成递推： $$ n \bmod m \perp m \Leftrightarrow n \bmod m_1 \perp m_1, n \bmod m_2 \perp m_2 $$ 这个可以一直往下递推到素数 (以及素数的幂) 的情况。 注意：有一点原文中讲的有些含糊，那就是： 根据独立剩余得到的性质，我们任取 $n \bmod m_1$ 与 $n \bmod m_2$ 的值，总能找到唯一的 $0 \leq n < m$ 使之成立。这是这个递推能够成立的至关重要的一点！ 完成了上面的论述，我们便有： $$ \varphi(m) = \varphi(m_1) \varphi(m_2), m_1\perp m_2, m = m_1m_2 $$ P111 $\varphi$ 函数公式推导的补充 $$ \begin{aligned} \varphi(m) &= \prod _{p\mid m} \varphi(p^{m_p}) \\ &= \prod _{p\mid m} (p^{m_p} - p^{m_p-1}) \\ &= \prod _{p\mid m} p^{m_p} \Big (1 - \frac 1 p \Big) \\ &= \prod _{p\mid m} p^{m_p} \prod _{p\mid m}\Big (1 - \frac 1 p \Big) \\ &= m \prod _{p\mid m}\Big (1 - \frac 1 p \Big) \\ \end{aligned} $$ P112 为什么 $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12$? 求证：对于 $d\mid m$，$\displaystyle \frac i d (i \leq d)$一定出现在 $\displaystyle \frac j m (j \leq m)$ 中。 证明： $$ \frac i d = \frac i d \frac {m/d}{m/d} = \frac {im/d} {m}, \frac {im}d \leq m $$ 所以我们可以知道：对于 $\displaystyle \frac j {12}$，约分后的最简分数 $\displaystyle\frac i d$ 一定有 $i \perp d$，且根据我们证明的引理，$\forall i \in [0..d), i \perp d$ 一定会出现原分数组 $\displaystyle \frac j {12}$ 中。 故 $$ \varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12 $$ 用同样的方式推广，即 $$ \sum_{d\mid m} \varphi(d) = m $$ P112 $g$ 是积性的则 $f$ 必然是积性的，证明补充 稍作补充。对于 $m=1$ $$ g(1) = \sum _{d\mid 1} f(d) = f(1) = 1 $$ 其中 $g(1)=1$ 是积性函数的定义。 对于 $m > 1$，根据归纳假设，$m_1m_2 < m, m_1\perp m_2$ 时有 $f(m_1)f(m_2) = f(m_1m_2)$，我们现在需要证明 $m_1m_2 = m$ 的情况。 $$ \begin{aligned} g(m_1m_2) &= \boxed{\sum _{d \mid m_1m_2} f(d) = \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1d_2)}^{\text{ note: }1} \\ &= \Big (\sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1)f(d_2)\Big ) - f(m_1)f(m_2) + f(m_1m_2) \\ &= \Big (\sum_{d_1\mid m_1} f(d_1)\sum_{d_2\mid m_2}f(d_2)\Big ) - f(m_1)f(m_2) + f(m_1m_2) \\ &= g(m_1)g(m_2) - f(m_1)f(m_2) + f(m_1m_2) \end{aligned} $$ 下面是方框的注释： 因为 $m_1 \perp m_2$，所以 $\gcd(d_1, d_2)=1$ 又因为 $g$ 是积性的，所以 $$ g(m_1m_2) = g(m_1)g(m_2) $$ 所以 $$ f(m_1m_2) = f(m_1) f(m_2) $$ 故 $f$ 也是积性的。 P112 $f$ 是积性的则 $g$ 必然是积性的 证明: $$ \begin{aligned} g(m_1m_2) &= \sum _{d \mid m_1m_2} f(d) = \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1d_2) \\ &= \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1)f(d_2) \\ &= \sum_{d_1\mid m_1} f(d_1)\sum_{d_2\mid m_2}f(d_2) \\ &= g(m_1)g(m_2) & \square \end{aligned} $$