Xenon's Blog

我们之前学习的 6 篇数值最优化方法都是目标函数处处可微的光滑函数。然而，在现实问题中，我们同样经常遇到梯度不存在的问题。比如说，在机器学习中，我们就可能会使用 LASSO 回归来得到稀疏解：

$$\min_x \frac{1}{n} \Vert Ax - b \Vert _2^2 + \mu \Vert x \Vert _1$$

而在它折起来的那个“折点”，这些目标函数根本不可微。既然连 $\nabla f(x)$ 都找不到，那之前学的所有方法就都用不了了。

次微分

数学老师说，我们要把未知问题转化为已知问题来解决。考虑到正常来说我们要优化的函数绝无可能存在一堆不可微的点，就一般而言取到“折点”的测度为零，我们不妨“假装”函数处处可微，然后用传统方法继续做。

我们之前说过很多普适的优化方法，大概就是给定一个任意的连续函数 $\phi(x)$，然后我们盯着它优化就可以了。不过对于一些形式比较好的函数，比如说 $\phi(x) = x^\top A x - b^\top x$，我们就不必用 GD 或是什么 L-BFGS，而是可以用共轭梯度法针对性地进行超级加速。

今天我们要来研发的另外一类形式也不错的函数，即最小二乘问题：

$$\min_{x \in \mathbb{R}^n} \phi(x) := \frac{1}{2} \Vert r(x) \Vert _2^2 = \frac{1}{2}\sum_{i=1}^m r_i(x)^2 \quad (m \ge n)$$

高斯-牛顿法（GN 法）

在高斯的年代，拟牛顿法还没有出生呢！但当时的人们已经发现，梯度下降法总是会遇到不收敛之类的麻烦问题，所以牛顿法就成为了当时的首选。那么我们不妨先用牛顿法试一下。牛顿法的核心更新公式是：

在之前的梯度下降法中，我们提到，即使在精确线搜索下，梯度下降法也大概率走出一条全是直角拐弯的优化路径。牛顿法虽然解决了这个问题，然而它的存储开销和计算开销实在太大了。我们最希望的当然是既只用一阶梯度，又能快速下降。

在通常的函数中这可能比较难以做到，那让我们退而求其次，来考察一下严格正定的二次型函数：

$$f(x) = \frac{1}{2} x^\top A x - b^\top x, \quad A \in \mathbb{R}^{n \times n}, \quad A \succ 0, \quad A^\top = A$$

求这个函数的最小值当然就是求 $\nabla f(x) = Ax - b = 0$。

其实，共轭梯度法最初在 1952 年就是为了求出 $Ax = b$ 而设计的。不过这里我们为了逻辑上的通畅，选择先有函数再算梯度的逻辑。

牛顿法要存的 Hessian 矩阵实在是太占地方了，解起来也很耗时。而且考虑到复杂地形中没法做到处处正定，牛顿法就不得不在曲率上做出很多妥协，把它硬掰成正定的，也拟合的没有很好。

改良的想法是我们干脆不算 Hessian 矩阵了，而是使用相邻迭代点处的一阶梯度差来积累曲率信息。反正一阶展开还是准的，二阶曲率的准确性要求倒也没那么迫切了。或者说，在工程上，我们愿意多牺牲一点二阶曲率来换取更快的时间和更少的空间。

根据这种思想，我们构造近似模型 $f(x_k + p_k) \approx m_{k}(p_k) = f(x_k) + \nabla f(x_k)^\top p_k + \frac{1}{2} p_k^\top B_k p_k$。接下来的任务就是求出一个合适的 $B_k$。

在梯度下降法中，我们只使用了一阶的泰勒展开信息，那如果使用二阶信息呢？

$$f(x_k + p_k) \approx f(x_k) + \nabla f(x_k)^\top p_k + \frac 1 2 p_k^\top \nabla^2 f(x_k) p_k$$

我们将其视作一个关于 $p_k$ 的函数，那么我们得到 $\psi(p_k) = \frac 1 2 p_k^\top \nabla^2 f(x_k) p_k + \nabla f(x_k)^\top p_k + f(x_k)$。我们希望 $\psi(p_k)$ 最小，那么就肯定有 $\nabla \psi(p_k) = 0$，即

$$\nabla^2 f(x_k) p_k + \nabla f(x_k) = 0$$

另外，如果 $\psi(p_k)$ 存在唯一最小值，那么它的二次项系数 $\nabla^2 f(x_k)$ 必须是正定的。而正定矩阵总满秩，所以当 $\nabla^2 f(x_k)$ 正定时，搜索方向唯一确定：

$$p_k^{\text{Newton}} = - \left( \nabla^2 f(x_k) \right)^{-1} \nabla f(x_k)$$

在上一篇文章中，我们讲了线搜索是如何确定步长的。能确定步长的前提是已经确定了方向，而如何确定方向则是连续优化算法设计中最重要的一环。从这一篇文章开始，我们将一起从零发明多种经典的连续优化方法，一起理解这些方法是怎么确定方向的。

接上一篇文章，$\phi(\alpha) = f(x_k + \alpha p_k)$。要使 $\phi(\alpha)$ 下降，$p_k$ 方向上必须存在一个点使得 $\phi(\alpha^\star) < \phi(0)$。直觉上看，这个条件可以通过往梯度下降的方向走来解决，也就是使得 $\nabla f(x_k)^\top p_k < 0$。

在 $f(x_k)$ 的附近，$f(x_k + p_k)$ 可以用一阶泰勒展开近似表现为 $f(x_k + p_k) \approx f(x_k) + \nabla f(x_k)^\top p_k$。$f(x_k)$ 和 $\nabla f(x_k)$ 显然都是目前已知的常量，所以，既然我们希望能取到一个 $p_k$ 使 $f(x_k) + \nabla f(x_k)^\top p_k$ 最小，我们就应该让 $\nabla f(x_k)^\top p_k$ 尽可能小，也就是让 $p_k$ 的方向正好与 $\nabla f(x_k)$ 相反。

连续优化问题

我们常常会遇到这样的问题：给定一个函数的公式，求它的最小值。我们在初中学二次函数的时候就知道二次函数的最小值在对称轴处取到。而到了高中，我们开始求各种各样的复杂一元函数的最小值。到了大学，我们还在求最小值，不过现在变成了多维的情况。

那么，通常我们怎么求最小值呢？按之前的经验，我们会使用一些漂亮的公式，比如说二次函数的配方，比如说不等式的取等条件，然后解决掉这些题目。然而，真实的世界中，这种情况总是不常遇到的。我们面对的函数千奇百怪，没有太多好的性质，所以也很难像做试卷那样流畅地把结果搞出来。

当然，你会想到求导。解一个导数等于零的方程，这种活儿卡西欧都能干，应该不难吧？这就是第二个问题，那就是维数。只有一个自变量的单一方程确实有很成体系的近似解法。然而，对于多维函数，它的导数（更准确说，梯度）也是一个多维向量。如果让它的每一维等于零，我们就会得到多个等于零的方程，每个方程中大概率还不止一个未知数。你绝对不会想看到这个有一堆东西耦合着的超大方程组的！

蛋白质预测任务

我们有一个链，链条上有不同的小零件。把链条放进水里一泡，它便会自己组装成一个三维结构——这条链叫肽链，而链条的组装就叫蛋白质的折叠。小零件的顺序几乎完全决定了三维结构，所以根据零件顺序预测三维结构便成了避不开的话题。

三维结构怎么表示呢？一般使用分子坐标，即，一个预测要给出所有非氢原子的三维笛卡尔坐标和对该位置的置信度估计。

核心思想

AlphaFold 1 认为，如果把链上的这一个个氨基酸残基当成刚性的小零件，那么对于每一个氨基酸而言，只要给定它的坐标，那么三维结构就解析了出来，至于侧链原子的预测就简单不少。那我们就先只考虑怎么把一条肽链堆起来组装成一个蛋白质。

scGPT 在想什么？

如果我们认为 Transformer 能理解文意与文法，那我们也不妨假定 Transformer 能理解基因之间的关系。如果文字能变成 token 喂进 Transformer 训练，然后吐出文字，那基因和它的表达量也可以喂进 Transformer 训练，然后吐出未知表达量基因的表达量。

scGPT 是怎么做的？

总览

大致概念

scGPT 是一个预训练模型。换而言之就是，我们认为它对细胞内的情况了解得不错，所以它既能直接被拿来生成其他的基因，又能在输出层的位置加点东西改装一下，然后通过微调完成其他的生物学任务。

前情提要

上一回我们通过修改 MTU 的方式解决了无法通过 curl 下载和无法连接学校内网的问题。这让我对网络代理，尤其是 Clash Verge 的 TUN 模式，有了不少兴趣。不过由于时间关系，也一直没来得及学。

恰好最近又遇到一堆网络问题，正好趁着解决这些问题的机会把 Clash Verge 弄明白一点，重整所有的 Clash Verge 配置，也方便以后的各种工作。