病態(tài)問題和條件數(shù)

病態(tài)問題和條件數(shù)

1. 概念定義

1.1 病態(tài)/ 良態(tài)問題
1.2 適定/ 非適定問題
1.3 良態(tài)/ 病態(tài)矩陣和條件數(shù)

2. 病態(tài)的根源
3. 計(jì)算條件數(shù)的方法

3.1 與特征值的關(guān)系
3.2 與奇異值的關(guān)系
3.3 自由數(shù)計(jì)算方法

正規(guī)陣條件數(shù)
酉矩陣條件數(shù)
奇異矩陣條件數(shù)

4. 解釋機(jī)器學(xué)習(xí)中的魯棒性
5. 病態(tài)矩陣規(guī)避：正則化（Regularizaiton）
參考資料

在CV領(lǐng)域大部分問題都是非適定問題（ill-posed problem）。
對(duì)于這個(gè)“非適定”這一概念，我一直沒有探究過。這次看到一篇非常精彩的博客，在這里分享給大家，建議大家查看原文~這里只作筆記，對(duì)原文中的錯(cuò)誤略有修改。

1. 概念定義

1.1 病態(tài)/ 良態(tài)問題

病態(tài)問題（ill-conditioned problem）：?jiǎn)栴}的解關(guān)于條件非常敏感。條件（或數(shù)據(jù)）中即使存在極微妙的噪聲，也會(huì)對(duì)問題的解造成劇烈的變化。
反之，關(guān)于條件不敏感的問題，我們稱之為良態(tài)問題（well-conditioned problem）。

顯然，我們能把這兩個(gè)概念拓展至病態(tài)/ 良態(tài)系統(tǒng)（算法），“條件”即系統(tǒng)的輸入，“問題的解”即系統(tǒng)的輸出。
舉一些例子：

人體體溫調(diào)控系統(tǒng)是良態(tài)的，因?yàn)轶w表溫度微小的變化也只會(huì)帶來微小的體溫調(diào)控；
汽車動(dòng)力系統(tǒng)是良態(tài)的，因?yàn)槲⒉扔烷T時(shí)，汽車動(dòng)力也只會(huì)稍作改變。

再延伸至機(jī)器學(xué)習(xí)算法：

如果一個(gè)算法對(duì)噪聲非常敏感，即病態(tài)的，那么其健壯性（robustness）也不佳（健壯性就是說系統(tǒng)抗擾動(dòng)的能力）。
如果一個(gè)算法是過擬合的，那么該算法一定是病態(tài)的。

1.2 適定/ 非適定問題

適定問題（ill-posed problem）的定義來源于1903年哈達(dá)瑪（Hadamard）的演講：一個(gè)問題是適定的，當(dāng)其滿足以下3個(gè)條件：

解存在；
解是唯一的；
解連續(xù)依賴于輸入（解隨著初始條件的改變而連續(xù)改變）（The solution depends continuously on the input）。

只要不滿足其中一個(gè)條件，那么該問題就是非適定的（ill-posed）。

注意：（非）適定問題既可以是良態(tài)的，也可以是病態(tài)的。

1.3 良態(tài)/ 病態(tài)矩陣和條件數(shù)

設(shè)有線性方程組(mathbf{A} vec{x} = vec{b})，其中(mathbf{A})是(n imes n)方陣，(vec{x})和(vec{b})都是(n imes 1)列向量。

假設(shè)條件(vec{x})變化了(Delta{vec{x}})，解相應(yīng)地變化了(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}})。

假設(shè)(mathbf{A})是非奇異矩陣，即(mathbf{A})為方陣且存在逆矩陣(mathbf{A^{-1}})，那么有：

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

兩邊取范數(shù)，根據(jù)范數(shù)的特性有：

[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}]

對(duì)(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}]

結(jié)合（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})是解的變化率；

雖然是不等號(hào)，但系數(shù)(Vert mathbf{A} Vert cdot Vert mathbf{A^{-1}} Vert)還是有意義的。我們稱之為矩陣(mathbf{A})的條件數(shù)（condition number），表示為：

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

式中的范數(shù)可以是0范數(shù)，無窮范數(shù)等，要注意矩陣(mathbf{A})必須是非奇異矩陣。

由（1-3）可得：

當(dāng)條件數(shù)(k(mathbf{A}))較小時(shí)，若初始條件發(fā)生較小變化，則解的變化也不大；此時(shí)的矩陣(mathbf{A})就是良態(tài)矩陣；
當(dāng)條件數(shù)(k(mathbf{A}))較大時(shí)，即使初始條件發(fā)生較小變化，解的變化也會(huì)很大；此時(shí)的矩陣(mathbf{A})就是病態(tài)矩陣。

因此，條件數(shù)是用來衡量系統(tǒng)敏感度的指標(biāo)，可用于判定病態(tài)/ 良態(tài)矩陣。

回到前面的注，顯然，病態(tài)/ 良態(tài)的概念與非適定/ 適定的概念是不一致的。

條件數(shù)不小于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. 病態(tài)的根源

病態(tài)矩陣的較大條件數(shù)，并非其病態(tài)的根本原因。其根源在于矩陣列向量相關(guān)性過強(qiáng)。
病態(tài)矩陣，實(shí)際上是奇異矩陣和近奇異矩陣的另一個(gè)說法。

我們舉個(gè)例子：

[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}
]

如果我們對(duì)輸入條件作微調(diào)，則結(jié)果會(huì)變?yōu)椋?/p>

[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}
]

可見，解變化的程度遠(yuǎn)遠(yuǎn)大于輸入條件變化的程度。并且，矩陣(mathbf{A})的列向量之間相關(guān)性極強(qiáng)。

3. 計(jì)算條件數(shù)的方法

雖然我們有條件數(shù)的定義，但當(dāng)矩陣為病態(tài)矩陣時(shí)，其中的求逆結(jié)果往往會(huì)有很大誤差。因此通常情況下，我們會(huì)使用矩陣的特征值或奇異值來計(jì)算條件數(shù)。

3.1 與特征值的關(guān)系

特征值較大者，變化自由度高，因此會(huì)導(dǎo)致解的劇烈變化。這有點(diǎn)類似于病態(tài)矩陣的表現(xiàn)。

參見：一篇博文

3.2 與奇異值的關(guān)系

通過SVD分解，解的不穩(wěn)定性也能用矩陣的性質(zhì)加以解釋。參見：一篇博文

3.3 自由數(shù)計(jì)算方法

若我們?nèi)《稊?shù)，則條件數(shù)為矩陣(mathbf{A})的最大、最小奇異值之商：

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

正規(guī)陣條件數(shù)

當(dāng)矩陣(mathbf{A})為正規(guī)陣時(shí)，條件數(shù)為矩陣(mathbf{A})的最大、最小特征值的絕對(duì)值之商：

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

酉矩陣條件數(shù)

當(dāng)矩陣(mathbf{A})為酉矩陣時(shí)，條件數(shù)為1：

[k(mathbf{A}) = 1
]

即當(dāng)且僅當(dāng)(mathbf{A})為酉矩陣時(shí)，條件數(shù)取得最小值1。

奇異矩陣條件數(shù)

當(dāng)(mathbf{A})為奇異矩陣時(shí)，其逆矩陣不存在：

[k(mathbf{A}) o infty
]

4. 解釋機(jī)器學(xué)習(xí)中的魯棒性

假設(shè)我們要用SGD，用一批((X,Y))樣本訓(xùn)練線性模型：

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

變形：

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

由上面所學(xué)的知識(shí)，若樣本(mathbf{X})中存在大量相關(guān)（相似）樣本，或矩陣(mathbf{X})是病態(tài)的，那么當(dāng)標(biāo)簽(mathbf{Y})中存在噪聲時(shí)，會(huì)導(dǎo)致解(mathbf{W})出現(xiàn)劇烈波動(dòng)！

而在實(shí)際情況中，我們很難避免數(shù)據(jù)噪聲。因此我們會(huì)對(duì)樣本進(jìn)行一些預(yù)處理，如異常點(diǎn)檢測(cè)和離群點(diǎn)檢測(cè)，目的都是為了獲得良態(tài)的數(shù)據(jù)矩陣。

5. 病態(tài)矩陣規(guī)避：正則化（Regularizaiton）

當(dāng)樣本數(shù)遠(yuǎn)小于特征向量維度時(shí)，損失函數(shù)表示的矩陣往往是稀疏甚至是病態(tài)的。

此時(shí)我們可以加入正則化項(xiàng)。
正則化項(xiàng)會(huì)增加數(shù)值解與真實(shí)解之間的誤差，但增強(qiáng)了穩(wěn)定性。

參考資料

本文主要參考的博客
一個(gè)超級(jí)超級(jí)大佬的博客，簡(jiǎn)潔明了
一個(gè)數(shù)學(xué)大佬的博客
維基百科：條件數(shù)
關(guān)于正則化的精彩博文
維基百科：正則化

總結(jié)

以上是生活随笔為你收集整理的病态问题和条件数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。