病态问题和条件数

您所在的位置:网站首页 矩阵特征值重复的算吗 病态问题和条件数

病态问题和条件数

2024-07-16 05:37:48| 来源: 网络整理| 查看: 265

病态问题和条件数 病态问题和条件数 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 \times n\)方阵,\(\vec{x}\)和\(\vec{b}\)都是\(n \times 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 \tag{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 \tag{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} \tag{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} = \begin{bmatrix} 1333 & -131 \\ 331 & -31 \\ \end{bmatrix},\ \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} \\ \vec{x_2} &= \begin{bmatrix} 1.0024 \\ 11.010 \\ \end{bmatrix} \Longrightarrow \vec y_2 &= \begin{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}) \to \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)

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

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

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


【本文地址】

公司简介

联系我们

今日新闻


点击排行

实验室常用的仪器、试剂和
说到实验室常用到的东西,主要就分为仪器、试剂和耗
不用再找了,全球10大实验
01、赛默飞世尔科技(热电)Thermo Fisher Scientif
三代水柜的量产巅峰T-72坦
作者:寞寒最近,西边闹腾挺大,本来小寞以为忙完这
通风柜跟实验室通风系统有
说到通风柜跟实验室通风,不少人都纠结二者到底是不
集消毒杀菌、烘干收纳为一
厨房是家里细菌较多的地方,潮湿的环境、没有完全密
实验室设备之全钢实验台如
全钢实验台是实验室家具中较为重要的家具之一,很多

推荐新闻


图片新闻

实验室药品柜的特性有哪些
实验室药品柜是实验室家具的重要组成部分之一,主要
小学科学实验中有哪些教学
计算机 计算器 一般 打孔器 打气筒 仪器车 显微镜
实验室各种仪器原理动图讲
1.紫外分光光谱UV分析原理:吸收紫外光能量,引起分
高中化学常见仪器及实验装
1、可加热仪器:2、计量仪器:(1)仪器A的名称:量
微生物操作主要设备和器具
今天盘点一下微生物操作主要设备和器具,别嫌我啰嗦
浅谈通风柜使用基本常识
 众所周知,通风柜功能中最主要的就是排气功能。在

专题文章

    CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭