Random Thoughts

22 Dec 2016 - less than 1 minute read

写程序无非是做两件事：解一个数学问题和把数据转换成问题要求的输入格式。

在课堂上，我们学习的是解问题。然而到了工业界，更多的人做的是转格式。

Photo

21 Dec 2016 - less than 1 minute read

大坂 クリスタルタワー

仿佛大楼带了自发光……

最小二乘问题（四）

21 Dec 2016 - 6 minute read

前面我们发现各种类型的线性最小二乘最后都可以变成一个最朴素的标准型。那么接下来是不是该讲怎么解标准型最小二乘问题了呢？很遗憾我们不会介绍怎么求解最小二乘问题。

为什么？前面我们提到了，使最小二乘问题最优的解，就是它的标准方程的解。也就是说，我们应该转而研究如何求解线性方程。这就在本系列话题之外了，会另外开辟内容介绍。

今天我们介绍最小二乘问题的概率背景，即最大似然估计（MLE）。

首先解释什么叫最大似然估计。白话说就是：这么多事儿里头就这个最容易发生，那就是这个了。概率上讲就是求使得概率 $P(x)$ 最大的 $x$ 。还有一个比较突出重点的解释，就是最大似然估计是求解随机分布中的众数（mode）。

设 $r\equiv Ax-b$ ，一般我们称 $r$ 为残差。这个名字是有来由的，通常我们认为它是个误差项，并且满足均值为零的高斯分布。在很多问题中，我们认为 $r$ 的每一维都是独立同分布的，在这样的条件下，我们知道 $P\left(r\right) \propto \exp-\frac{r^Tr}{2\sigma^2}$ 。

那么最大化上述概率就是：

\[\arg\max \exp -\frac{r^Tr}{2\sigma^2} = \arg\min \frac{r^Tr}{2\sigma^2} = \arg\min \|r\|^2.\]

由此可见两者是等价的。

接下来，我们来看一个重要的变形：如果 $r$ 的每一维不是独立同分布的，但都是高斯的。此时 $r$ 符合一个一般的多变量高斯分布。如果设 $r$ 的协方差矩阵为 $\Sigma$ ，那么此时 $r$ 的最大似然估计则是：

\[\arg\max \exp -r^T\Sigma^{-1}r = \arg\min r^T\Sigma^{-1}r.\]

如果我们引入 Mahalanobis 距离 $\|x\|_P = \sqrt{x^TPx}$ 。令矩阵 $H = \Sigma^{-1}$ ，那么上面的问题可以简写成 $\min \|r\|_H^2$ 。

引入这个记法除了简化记号外有啥别的帮助么？范数都变了呀，是不是现在我们终于得到了一个不能写成线性最小二乘标准型的问题呢？

别着急，如果我们设矩阵 $U$ 满足 $U^TU = H$ ，那么我们便知道

\[\|r\|_H^2 = r^THr = r^TU^TUr = \|Ur\|^2.\]

怎么样，又回到最小二乘了吧？前面我们介绍过了 Cholesky 分解，因此我们知道当 $H$ 是对称正定矩阵的时候，对应的 $U$ 肯定能找得到。

……那如果不是高斯分布呢？（你闭嘴！

Cholesky 分解（番外）

20 Dec 2016 - 3 minute read

前面我们介绍了 Schur 补，它可以看做是块状高斯消元的产物。Cholesky 分解同样可以看做一种特殊的高斯消元，因此它们之间存在着一些联系。

我们将对称正定矩阵 $A$ 按满足 Schur 补的条件分块。得到

\[A/A_{11} = A_{22}-A_{21}A_{11}^{-1}A_{21}^T.\]

与此同时，我们按块进行 Cholesky 分解，将 $A$ 分解为 $LL^T$ 。参考我们系列文章的第一篇可以知道 $L$ 的对应块满足：

\[\begin{aligned} L_{11} &= \mathrm{chol}(A_{11}) \\ L_{21} &= A_{21}L_{11}^{-T} \\ L_{22} &= \mathrm{chol}(A_{22}-L_{21}L_{21}^T). \end{aligned}\]

如果将 $L_{11}$ 、$L_{21}$ 代入到 $L_{22}$ 中，整理可得：

\[L_{22} = \mathrm{chol}(A_{22}-A_{21}A_{11}^{-1}A_{21}^T) = \mathrm{chol}(A/A_{11}).\]

也就是说在 Cholesky 分解中，每一步消去后得到的剩余方阵恰好是原始矩阵关于消去行列的 Schur 补。因此我们可以直接利用已知的知识来分析和处理计算 Schur 补时产生的 fill-in 情况。

最小二乘问题（三）

19 Dec 2016 - 4 minute read

上回介绍了三种（线性）最小二乘问题的变形，我们采用了相同的手段，就是构造出新的系数矩阵，然后将原始的问题变成新的系数矩阵下的单项的最小二乘问题。

从上文的三个问题稍加总结，便可以看出原始问题中的系数矩阵在新的系数矩阵里有这样的关系：

• 每一项的系数矩阵单独占据一行
• 每个变量的系数矩阵单独占据一列

同时，原始问题中的常数向量直接纵向连接便得到等价问题中的常数向量。

根据这个规则，下面我们介绍一般的多个二次项，多变量的最小二乘问题，以及如何将它化为单个二次项，单变量的最小二乘标准形式。

设一系列残差函数 $r_i(x_1, x_2, \dots, x_n) = \sum_j^n A_{ij} x_j - b_i$ ，$i = 1\dots m$ 。一个一般的线性最小二乘问题具有如下的形式：

\[\min_{x_1, x_2, \dots, x_n} \sum_i^m \|r_i\|^2.\]

定义系数矩阵 $A$ 、常数向量 $b$ 以及向量 $x$，分别为：

\[\begin{aligned} A &= \begin{pmatrix} A_{11} & \cdots & A_{1n} \\ \vdots & \ddots & \vdots \\ A_{m1} & \cdots & A_{mn} \end{pmatrix} & b &= \begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix} & x &= \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \end{aligned}\]

那么上面的最小二乘一般形式可以转化为如下的标准形式：

\[\min_x \|Ax-b\|^2.\]

于是我们兜了个大圈子又回来了……