Nothing is perfect, nothing.

一、概念定义

1.1 良态 VS 病态问题

  病态问题（ill-conditioned problem）是指输出结果相对于输入非常敏感的问题，输入数据中哪怕是极少（或者极微妙）的噪声也会导致输出的较大改变（该术语并没有严格的官方定义）。
  相反的，对于输入不敏感的问题，我们就称为良态问题（well-conditioned problem）。

1.2 条件数

  条件数（condition-number）是用来衡量输出相对于输入敏感度的指标，良态问题和病态问题就是靠这个指标来进行区分的。

1.3 良态系统

  注：以下两个概念（良态系统、病态系统）是我为方便叙述提出的，非官方术语。
  我们把良态问题的内涵做一个延伸，对于任意一个系统，系统的输入和输出属于良态问题，我们称之为良态系统（或者这个系统是良态的）。
  这里的系统的概念非常广泛，可以涵盖各种各样的类型。比如，以人体神经系统来说，一个良态的神经系统（身体健康的人），在外界环境温度（输入）发生微小改变时，它对人体温度的调节（输出）也应该是微小的。再比如，一个良态的汽车动力系统，当输入（油门大小）发生微小改变时，输出（动力的加减）也应该是微小的。
  当然，我们主要还是围绕机器学习来讲。一个良态的分类/聚类/回归系统（模型），当输入数据中存在噪声时，其输出与没有噪声时相比，变化不应该太大，否则这个系统的鲁棒性就很差。存在过拟合的系统，因为泛化能力非常差，因此它必然是非良态（病态）的。

1.4 病态系统

  如上所述，一般情况下，非良态的系统就是病态的（除去那些本身就要求输出对输入敏感的系统）。

1.5 适定问题 VS 不适定问题

  注意要把病态/良态系统和适定（well-posed problem）/不适定（ill-posed problem）问题区分开来。适定问题既可以是良态的，也可以是病态的，不适定问题同样如此，不要混为一谈。
  这里贴一下适定问题（well-posed problem）的定义：

  1. 必然存在解；
  2. 解唯一；
  3. 解随着初始条件改变而连续改变。

1.6 良态/病态矩阵

  因为接下来的内容涉及到矩阵，因此需要对相应的概念做个介绍。对于线性方程组A$\vec x = \vec b$，其中A为m*n矩阵，$\vec x、\vec b$均为n*1的列向量。我们定义方程组关于A的条件数为：

$$
k(\textbf{A})= ||\textbf{A}|| \cdot ||\textbf{A}^{-1}||
\tag{1 - 1}
$$

  上式中的范数也可以取其他范数（比如0、$\infty$范数）。当然上式成立的条件是A的逆矩阵$\textbf{A}^{-1}$存在（即A为非奇异矩阵）。当$k(\textbf{A})$较小时，$\vec b$的微小改变不会造成方程组解$\vec x$的改变，我们称A为良态矩阵，反之则成为病态矩阵。

  条件数的定义推导如下，假定$\vec b$的变化量为$\Delta \vec b$，对应的解的变化为$\Delta \vec b$，则有：

$$
\textbf{A} (\vec x + \Delta \vec x) = \vec b + \Delta \vec b
\tag{1 - 2}
$$

  展开后有：

$$
\textbf{A} \vec x + \textbf{A} \cdot \Delta \vec x = \vec b + \Delta \vec b
\tag{1 - 3}
$$

  因为$\textbf{A} \vec x = \vec b$，代入式（1-3）有：

$$
\textbf{A} \cdot \Delta \vec x = \Delta \vec b
\tag{1 - 4}
$$

  同时我们假定了$\textbf{A}^{-1}$存在，所以有：

$$
\Delta \vec x = \textbf{A}^{-1} \cdot \Delta \vec b
\tag{1 - 5}
$$

  对等式两边取范数并根据范数的特性)有：

$$
||\Delta \vec x|| = ||\textbf{A}^{-1} \cdot \Delta \vec b || \leq ||\textbf{A}^{-1}|| \cdot ||\Delta \vec b ||
\tag{1 - 6}
$$

  同时对$\textbf{A} \vec x = \vec b$两边取二范数有：

$$
||\textbf{A}|| \cdot ||\vec x|| \ge ||\textbf{A} \vec x|| = ||\vec b||
\tag{1 - 7}
$$

  结合上式（1-6）、（1-7）有：

$$
\frac{||\Delta \vec x||}{||\textbf{A}|| \cdot ||\vec x||} \leq \frac{||\textbf{A}^{-1}|| \cdot ||\Delta \vec b ||}{||\vec b||}
\tag{1- 8}
$$

  根据上式进一步有：

$$
\underbrace{\frac{||\Delta \vec x||}{||\vec x||}}_{输入的改变率} \leq \underbrace{||\textbf{A}|| \cdot ||\textbf{A}^{-1}||}_{输入输出改变率比系数} \cdot \underbrace{\frac{||\Delta \vec b ||}{||\vec b||}}_{输出改变率}
\tag{1- 9}
$$

  由上式，我们定义输入改变率和输出改变率的这个系数为条件数，即有：

$$
\begin{cases}
\begin{split}
k(\textbf{A}) &= ||\textbf{A}|| \cdot ||\textbf{A}^{-1}|| \geq ||\textbf{A} \cdot \textbf{A}^{-1}|| = 1 \\\\
\frac{||\Delta \vec x||}{||\vec x||} &\leq k(\textbf{A}) \cdot \frac{||\Delta \vec b ||}{||\vec b||}
\end{split}
\end{cases}
\tag{1 -10}
$$

  由上可知，条件数实际上是输出相对于输入变化的灵敏度系数。

1.7 二范数条件数

  如果我们取的是二范数，即$||\cdot||_2$，则其条件数为：

$$
k(\textbf{A}) = \frac{\sigma_{max}(\textbf{A})}{\sigma_{min}(\textbf{A})}
\tag{1 - 11}
$$

  上式中的$\sigma_{max}(\textbf{A})、\sigma_{min}(\textbf{A})$分别指矩阵A的最大、最小奇异值。

1.7.1 正规阵条件数

  特别的，当A为正规阵时：

$$
k(\textbf{A}) = \frac{|\lambda_{max}(\textbf{A})|}{|\lambda_{min}(\textbf{A})|}
\tag{1 - 12}
$$

  式中$\lambda_{max}(\textbf{A})、\lambda_{min}(\textbf{A})$分别为矩阵A的最大、最小特征值。

1.7.2 酉矩阵条件数

  特别的，当A为酉矩阵时：

$$
k(\textbf{A}) = 1
\tag{1 - 13}
$$

  即当且仅当A为酉矩阵时，条件数取得最小值1。

1.7.3 奇异矩阵条件数

  特别的，当A为奇异矩阵时，A的逆矩阵不存在：

$$
k(\textbf{A}) \rightarrow \infty
\tag{1 - 14}
$$

1.8 机器学习和条件数

  矩阵的条件数是针对一般方程组而言的，对于机器学习，还需要做一些说明。因为在线性方程组中，$\vec b$是输入，而$\vec x$才是我们的输出（要求解的），这点和机器学习模型有所差异，我们要在这两个问题之间做一个转换，以方便接下来的讨论。
  对于机器学习模型而言，神经网络的参数矩阵通常用W表示，输入样本用$\vec x$表示，而输出用$\vec y$表示。三者的关系为：

$$
\textbf{W} \cdot \underbrace{\vec x}_{输入} = \underbrace{\vec y}_{输出} \\\\
\tag{1 - 15}
$$

  线性方程组的关系为：

$$
\textbf{A}^{-1} \cdot \underbrace{\vec b}_{输入} = \underbrace{\vec x}_{输出}
\tag{1 - 16}
$$

  模型训练好了之后，W是不会改变的，然后将样本$\vec x$作为输入（自变量），去生成输出$\vec y$（因变量）。因此有如下对应关系：
$$
\begin{cases}
\begin{split}
\textbf{W} & \iff \textbf{A}^{-1} \\\\
\vec x & \iff \vec b \\\\
\vec y & \iff \vec x
\end{split}
\end{cases}
\tag{1 -17}
$$

  则有机器学习模型的条件数：

$$
\begin{split}
k(\textbf{W}) &= ||\textbf{W}|| \cdot ||(\textbf{W}^{-1})^{-1}||\\\\
&= ||\textbf{W}^{-1}|| \cdot ||\textbf{W}||
\end{split}
\tag{1 - 18}
$$

二、应用

2.2 病态的根源

  既然已经定义了条件数，定义了什么是病态，什么是良态，我们不禁会想，引起病态的根源是什么，或者说什么样的矩阵具备病态特征。
  当然，你可能会说，前面不是定义了条件数较大的矩阵属于病态矩阵吗，这不是多此一问吗？
  过大的条件数会导致矩阵病态只是我们的结论，并不是根本的原因。最根本的原因在于矩阵的列之间的相关性过大。

  为了说明这个问题，我们举一个最简单的二维方阵来说明。

2.2.1 示例

  给定如下条件：

$$
\textbf{W} =
\begin{bmatrix}
1333 & -131 \\
331 & -31 \\
\end{bmatrix} \quad , \quad
\vec x =
\begin{bmatrix}
1 \\
11 \\
\end{bmatrix}
$$

  可以解出：

$$
\vec y =
\begin{bmatrix}
-120 \\
-13 \\
\end{bmatrix}
$$

  现在我们分别对输入做细微的调整，并计算输出结果，如下所示：

$$
\begin{cases}
\begin{split}
\vec x_1 &=
\begin{bmatrix}
1.0097 \\
11.001 \\
\end{bmatrix} \Longrightarrow
\vec y_1 &=
\begin{bmatrix}
-95.2 \\
-6.82 \\
\end{bmatrix} \Longrightarrow
\Delta \vec y_1 &=
\begin{bmatrix}
20.67\% \\
47.54\% \\
\end{bmatrix} \\\\
\vec x_2 &=
\begin{bmatrix}
1.0024 \\
11.010 \\
\end{bmatrix} \Longrightarrow
\vec y_2 &=
\begin{bmatrix}
-106.11 \\
-9.52 \\
\end{bmatrix} \Longrightarrow
\Delta \vec y_2 &=
\begin{bmatrix}
11.58\% \\
26.92\% \\
\end{bmatrix}
\end{split}
\end{cases}
\tag{2 - 1}
$$

  由上可知，即使输入的微小改变，也会引起输出的大幅变动。比如上面的$\vec x_1$对应的输出$\vec y_1$分量最高变动率高达近50%。

  我们来看看其列之间的相关性，有：

$$
\vec w_1/ \vec w_2 =
\begin{bmatrix}
1333/(-131) \\
331/(-31) \\
\end{bmatrix} = \begin{bmatrix}
10.1756 \\
10.6774 \\
\end{bmatrix}
\tag{2 - 2}
$$

  可以看出，矩阵W的列之间的线性相关性非常高！

2.2.2 特征值和特征向量

  与此同时，虽然上面两个输入$\vec x_1、\vec x_2$与原始输入$\vec x$改变的绝对值不一样，但实际上在其两个特征向量方向上的改变率却是一样的，换句话说，不同特征向量方向上相同的改变率，其输出的改变率是不同的。

  利用Numpy内置的函数numpy.linalg.eig()我们可以非常方便的求解出$\textbf{W}$的特征值及其特征向量如下：

$$
\begin{cases}
\begin{split}
\vec \xi_1 &\approx
\begin{bmatrix}
0.97 \\
0.10 \\
\end{bmatrix} \quad , \quad \lambda_1 \approx 1300\\\\
\vec \xi_2 &\approx
\begin{bmatrix}
0.24 \\
1.00 \\
\end{bmatrix} \quad , \quad \lambda_2 \approx 1.57
\end{split}
\end{cases}
\tag{2 - 3}
$$

  可以看出，输入$\vec x$分别沿着两个特征向量$\vec \xi_1、\vec \xi_2$方向增加1%后，即为式（2-1）中的$\vec x_1、\vec x_2$，而特征向量$\vec \xi_1$对应的特征值（$\lambda_1 = 1300$）远大于特征向量$\vec \xi_2$对应的特征值（$\lambda_1 = 1.57$）。

  因此，当矩阵的特征值差异过大时，即使输入沿着较大特征值的方向有微小的改变，也会导致最终的输出结果的较大改变。原因很简单，较大的特征值意味着对应特征方向上较大的自由度。

2.3 机器学习中应用

  现在我们换个思路，我们手里已经有了大量的样本，要训练一个机器学习的模型，即已知$\vec x、\vec y$，要求W，考虑SGD（随机梯度下降）算法，因为每次送进去的样本数量$N > 1$，所以上式（1-14）就变成了：

$$
\textbf{W} \cdot \textbf{X} = \textbf{Y} \\\\
\tag{2 - 4}
$$

  我们对上式做一个变形：

$$
\underbrace{\textbf{X}}_{A} \cdot \underbrace{\textbf{Y}^{-1}}_{\vec x} = \underbrace{\textbf{W}^{-1}}_{\vec b} \\\\
\tag{2 - 5}
$$

  这个时候我们把输入的样本X视作参数矩阵，把要求解的参数W矩阵视作输出。由之前的结论可知，如果X为病态矩阵，即样本之间的相关性过大，可能会导致训练的收敛过程非常慢，甚至不收敛。因为整个训练过程中，相似样本之间的标签即使存在微小的差异，也会导致W的较大波动，导致解的不稳定性。

  正是由于解的这种不稳定性，训练过程结束后，我们很难保证求解出来的模型能够足够优秀。另一方面，病态矩阵从另一个角度揭示了过拟合现象产生的原因，即通过解的大幅波动，去拟合我们的训练数据。

  无论是数据的生成还是采集过程中，我们都很难保证没有噪声，因此一般我们都会对样本进行一些预处理，比如异常点检测、离群点检测等等，或者将解集限定在一组正交基的空间内（正交意味着不相关，求解出的参数矩阵就是一个良态矩阵）。无论采取什么措施，最终的目的都只有一个，那就是获得一个良态参数矩阵。

  病态矩阵为我们提供了很多理论上的指导，同时也启发我们去思考其它很多问题。

2.4 深度学习中应用

  在深度学习中，我们将损失函数$L(x)$在点$\vec{x}^{(0)}$的进行二阶泰勒级数展开，如下：
$$
\begin{split}
\begin{cases}
\mathcal{L}(\vec{x}) &\approx \mathcal{L}(\vec{x}^{(0)}) + (\vec{x} - \vec{x}^{(0)})^T \ \vec{g} + \frac{1}{2}(\vec{x} - \vec{x}^{(0)})^T \ \textbf{H} \ (\vec{x} - \vec{x}^{(0)}) \\
\mathcal{L}(\vec{x}^{(0)} - \epsilon \vec{g})&\approx \mathcal{L}(\vec{x}^{(0)}) - \epsilon \vec{g}^T \vec{g} + \frac{1}{2} \epsilon^2 \vec{g}^T \ \textbf{H} \ \vec{g}
\end{cases}
\end{split}
\tag{2 - 6}
$$
  式中：

   ——$\textbf{H}$：在$\vec{x}^{(0)}$点的梯度的Jacobian矩阵；

   ——$\vec{g}$：在$\vec{x}^{(0)}$点的梯度。

  上式中当$\frac{1}{2} \epsilon^2 \vec{g}^T \ \textbf{H} \ \vec{g}$超过$\epsilon \vec{g}^T \vec{g}$时，$\textbf{H}$的病态会成为非常严重的问题，因为此时即使梯度$\vec{g}$的小幅波动也会导致损失的大幅增加。为了消除这个影响，学习率$\epsilon$就必须大幅收缩，此时虽然梯度仍然很大(通常平方梯度范数$\vec{g}^T \vec{g}$不会在训练过程中显著缩小)，但是学习过程却变得非常缓慢。

  所以在神经网络的训练过程中，我们需要检测平凡梯度范数$\vec{g}^T \vec{g}$和$\vec{g}^T \ \textbf{H} \ \vec{g}$，以便评估当前的病态是否不利于训练任务的执行并设法改善它。

2.5 参考资料