病态问题及条件数

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. 解随着初始条件改变而连续改变。

1.6 良态/病态矩阵

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

k(A)=||A||⋅||A−1||

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

  条件数的定义推导如下，假定→b的变化量为Δ→b，对应的解的变化为Δ→b，则有：

A(→x+Δ→x)=→b+Δ→b

  展开后有：

A→x+A⋅Δ→x=→b+Δ→b

  因为A→x=→b，代入式（1-3）有：

A⋅Δ→x=Δ→b

  同时我们假定了A−1存在，所以有：

Δ→x=A−1⋅Δ→b

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

||Δ→x||=||A−1⋅Δ→b||≤||A−1||⋅||Δ→b||

  同时对A→x=→b两边取二范数有：

||A||⋅||→x||≥||A→x||=||→b||

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

||Δ→x||||A||⋅||→x||≤||A−1||⋅||Δ→b||||→b||

  根据上式进一步有：

||Δ→x||||→x||⏟输入的改变率≤||A||⋅||A−1||⏟输入输出改变率比系数⋅||Δ→b||||→b||⏟输出改变率

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

{k(A)=||A||⋅||A−1||≥||A⋅A−1||=1||Δ→x||||→x||≤k(A)⋅||Δ→b||||→b||

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

1.7 二范数条件数

  如果我们取的是二范数，即||⋅||2，则其条件数为：

k(A)=σmax(A)σmin(A)

  上式中的σmax(A)、σmin(A)分别指矩阵A的最大、最小奇异值。

1.7.1 正规阵条件数

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

k(A)=|λmax(A)||λmin(A)|

  式中λmax(A)、λmin(A)分别为矩阵A的最大、最小特征值。

1.7.2 酉矩阵条件数

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

k(A)=1

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

1.7.3 奇异矩阵条件数

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

k(A)→∞

1.8 机器学习和条件数

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

W⋅→x⏟输入=→y⏟输出

  线性方程组的关系为：

A−1⋅→b⏟输入=→x⏟输出

  模型训练好了之后，W是不会改变的，然后将样本→x作为输入（自变量），去生成输出→y（因变量）。因此有如下对应关系：
{W⟺A−1→x⟺→b→y⟺→x

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

k(W)=||W||⋅||(W−1)−1||=||W−1||⋅||W||

2.2 病态的根源

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

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

2.2.1 示例

  给定如下条件：

W=[1333−131331−31],→x=[111]

  可以解出：

→y=[−120−13]

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

{→x1=[1.009711.001]⟹→y1=[−95.2−6.82]⟹Δ→y1=[20.67%47.54%]→x2=[1.002411.010]⟹→y2=[−106.11−9.52]⟹Δ→y2=[11.58%26.92%]

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

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

→w1/→w2=[1333/(−131)331/(−31)]=[10.175610.6774]

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

2.2.2 特征值和特征向量

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

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

{→ξ1≈[0.970.10],λ1≈1300→ξ2≈[0.241.00],λ2≈1.57

  可以看出，输入→x分别沿着两个特征向量→ξ1、→ξ2方向增加1%后，即为式（2-1）中的→x1、→x2，而特征向量→ξ1对应的特征值（λ1=1300）远大于特征向量→ξ2对应的特征值（λ1=1.57）。

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

2.3 机器学习中应用

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

W⋅X=Y

  我们对上式做一个变形：

X⏟A⋅Y−1⏟→x=W−1⏟→b

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

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

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

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

2.4 深度学习中应用

  在深度学习中，我们将损失函数L(x)在点→x(0)的进行二阶泰勒级数展开，如下：
{L(→x)≈L(→x(0))+(→x−→x(0))T →g+12(→x−→x(0))T H (→x−→x(0))L(→x(0)−ϵ→g)≈L(→x(0))−ϵ→gT→g+12ϵ2→gT H →g
  式中：

   ——H：在→x(0)点的梯度的Jacobian矩阵；

   ——→g：在→x(0)点的梯度。

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

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

2.5 参考资料