病态问题和条件数

病态问题和条件数

1. 概念定义

1.1 病态/ 良态问题
1.2 适定/ 非适定问题
1.3 良态/ 病态矩阵和条件数

2. 病态的根源
3. 计算条件数的方法

3.1 与特征值的关系
3.2 与奇异值的关系
3.3 自由数计算方法

正规阵条件数
酉矩阵条件数
奇异矩阵条件数

4. 解释机器学习中的鲁棒性
5. 病态矩阵规避：正则化（Regularizaiton）
参考资料

在CV领域大部分问题都是非适定问题（ill-posed problem）。
对于这个“非适定”这一概念，我一直没有探究过。这次看到一篇非常精彩的博客，在这里分享给大家，建议大家查看原文~这里只作笔记，对原文中的错误略有修改。

1. 概念定义

1.1 病态/ 良态问题

病态问题（ill-conditioned problem）：问题的解关于条件非常敏感。条件（或数据）中即使存在极微妙的噪声，也会对问题的解造成剧烈的变化。
反之，关于条件不敏感的问题，我们称之为良态问题（well-conditioned problem）。

显然，我们能把这两个概念拓展至病态/ 良态系统（算法），“条件”即系统的输入，“问题的解”即系统的输出。
举一些例子：

人体体温调控系统是良态的，因为体表温度微小的变化也只会带来微小的体温调控；
汽车动力系统是良态的，因为微踩油门时，汽车动力也只会稍作改变。

再延伸至机器学习算法：

如果一个算法对噪声非常敏感，即病态的，那么其健壮性（robustness）也不佳（健壮性就是说系统抗扰动的能力）。
如果一个算法是过拟合的，那么该算法一定是病态的。

1.2 适定/ 非适定问题

适定问题（ill-posed problem）的定义来源于1903年哈达玛（Hadamard）的演讲：一个问题是适定的，当其满足以下3个条件：

解存在；
解是唯一的；
解连续依赖于输入（解随着初始条件的改变而连续改变）（The solution depends continuously on the input）。

只要不满足其中一个条件，那么该问题就是非适定的（ill-posed）。

注意：（非）适定问题既可以是良态的，也可以是病态的。

1.3 良态/ 病态矩阵和条件数

设有线性方程组(mathbf{A} vec{x} = vec{b})，其中(mathbf{A})是(n imes n)方阵，(vec{x})和(vec{b})都是(n imes 1)列向量。

假设条件(vec{x})变化了(Delta{vec{x}})，解相应地变化了(Delta{vec{b}})，即：

[mathbf{A} (vec{x} + Delta{vec{x}}) = vec{b} + Delta{vec{b}}
]

由于(mathbf{A} vec{x} = vec{b})，因此有(mathbf{A} Delta{vec{x}} = Delta{vec{b}})。

假设(mathbf{A})是非奇异矩阵，即(mathbf{A})为方阵且存在逆矩阵(mathbf{A^{-1}})，那么有：

[Delta{vec{x}} = mathbf{A^{-1}} cdot Delta{vec{b}}
]

两边取范数，根据范数的特性有：

[Vert Delta{vec{x}} Vert = Vert mathbf{A^{-1}} cdot Delta{vec{b}} Vert le Vert mathbf{A^{-1}} Vert cdot Vert Delta{vec{b}} Vert
ag{1-1}]

对(mathbf{A} vec{x} = vec{b})有相同的操作：

[Vert mathbf{A} vec{x} Vert = Vert vec{b} Vert le Vert mathbf{A} Vert cdot Vert vec{x} Vert
ag{1-2}]

结合（1-1）、（1-2）式有：

[frac{Vert Delta vec{x} Vert}{Vert vec{x} Vert} le Vert mathbf{A} Vert cdot Vert mathbf{A^{-1}} Vert cdot frac{Vert Delta vec{b} Vert}{Vert vec{b} Vert}
ag{1-3}]

有东西！

(frac{Vert Delta vec{x} Vert}{Vert vec{x} Vert})是初始条件的变化率；
(frac{Vert Delta vec{b} Vert}{Vert vec{b} Vert})是解的变化率；

虽然是不等号，但系数(Vert mathbf{A} Vert cdot Vert mathbf{A^{-1}} Vert)还是有意义的。我们称之为矩阵(mathbf{A})的条件数（condition number），表示为：

[k(mathbf{A}) = Vert mathbf{A} Vert cdot Vert mathbf{A^{-1}} Vert
]

式中的范数可以是0范数，无穷范数等，要注意矩阵(mathbf{A})必须是非奇异矩阵。

由（1-3）可得：

当条件数(k(mathbf{A}))较小时，若初始条件发生较小变化，则解的变化也不大；此时的矩阵(mathbf{A})就是良态矩阵；
当条件数(k(mathbf{A}))较大时，即使初始条件发生较小变化，解的变化也会很大；此时的矩阵(mathbf{A})就是病态矩阵。

因此，条件数是用来衡量系统敏感度的指标，可用于判定病态/ 良态矩阵。

回到前面的注，显然，病态/ 良态的概念与非适定/ 适定的概念是不一致的。

条件数不小于1：

[k(mathbf{A}) = Vert mathbf{A} Vert cdot Vert mathbf{A^{-1}} Vert ge Vert mathbf{A} mathbf{A^{-1}} Vert = Vert mathbf{I} Vert = 1
]

2. 病态的根源

病态矩阵的较大条件数，并非其病态的根本原因。其根源在于矩阵列向量相关性过强。
病态矩阵，实际上是奇异矩阵和近奇异矩阵的另一个说法。

我们举个例子：

[mathbf{W} = egin{bmatrix}
1333 & -131 \
331 & -31 \
end{bmatrix}, vec{x} = egin{bmatrix}
1 \
11 \
end{bmatrix}
]

解为：

[vec{y} = egin{bmatrix}
-120 \
-13 \
end{bmatrix}
]

如果我们对输入条件作微调，则结果会变为：

[egin{cases}
egin{split}
vec{x_1} &= egin{bmatrix}
1.0097 \
11.001 \
end{bmatrix} Longrightarrow vec{y_1} &= egin{bmatrix}
-95.2 \
-6.82 \
end{bmatrix} \
vec{x_2} &= egin{bmatrix}
1.0024 \
11.010 \
end{bmatrix} Longrightarrow vec y_2 &= egin{bmatrix}
-106.11 \
-9.52 \
end{bmatrix}
end{split}
end{cases}
]

可见，解变化的程度远远大于输入条件变化的程度。并且，矩阵(mathbf{A})的列向量之间相关性极强。

3. 计算条件数的方法

虽然我们有条件数的定义，但当矩阵为病态矩阵时，其中的求逆结果往往会有很大误差。因此通常情况下，我们会使用矩阵的特征值或奇异值来计算条件数。

3.1 与特征值的关系

特征值较大者，变化自由度高，因此会导致解的剧烈变化。这有点类似于病态矩阵的表现。

参见：一篇博文

3.2 与奇异值的关系

通过SVD分解，解的不稳定性也能用矩阵的性质加以解释。参见：一篇博文

3.3 自由数计算方法

若我们取二范数，则条件数为矩阵(mathbf{A})的最大、最小奇异值之商：

[k(mathbf{A}) = frac{sigma_{max}{mathbf{A}}}{sigma_{min}{mathbf{A}}}
]

正规阵条件数

当矩阵(mathbf{A})为正规阵时，条件数为矩阵(mathbf{A})的最大、最小特征值的绝对值之商：

[k(mathbf{A}) = frac{vert lambda_{max}{mathbf{A}} vert}{vert lambda_{min}{mathbf{A}} vert}
]

酉矩阵条件数

当矩阵(mathbf{A})为酉矩阵时，条件数为1：

[k(mathbf{A}) = 1
]

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

奇异矩阵条件数

当(mathbf{A})为奇异矩阵时，其逆矩阵不存在：

[k(mathbf{A}) o infty
]

4. 解释机器学习中的鲁棒性

假设我们要用SGD，用一批((X,Y))样本训练线性模型：

[mathbf{W} cdot mathbf{X} = mathbf{Y}
]

变形：

[underbrace{mathbf{X}}_{A} cdot underbrace{mathbf{Y}^{-1}}_{vec{x}} = underbrace{mathbf{W}^{-1}}_{vec{b}}
]

由上面所学的知识，若样本(mathbf{X})中存在大量相关（相似）样本，或矩阵(mathbf{X})是病态的，那么当标签(mathbf{Y})中存在噪声时，会导致解(mathbf{W})出现剧烈波动！

而在实际情况中，我们很难避免数据噪声。因此我们会对样本进行一些预处理，如异常点检测和离群点检测，目的都是为了获得良态的数据矩阵。

5. 病态矩阵规避：正则化（Regularizaiton）

当样本数远小于特征向量维度时，损失函数表示的矩阵往往是稀疏甚至是病态的。

此时我们可以加入正则化项。
正则化项会增加数值解与真实解之间的误差，但增强了稳定性。

参考资料

本文主要参考的博客
一个超级超级大佬的博客，简洁明了
一个数学大佬的博客
维基百科：条件数
关于正则化的精彩博文
维基百科：正则化