【Python機器學習】107:機器學習模型的計算複雜性
Computational complexity of Machine Learning
計算複雜性(Computational complexity)是電腦科學研究解決問題所需的資源,諸如時間(要通過多少步演算才能解決問題)和空間(在解決問題時需要多少記憶體),在演算法中常見到的大 O 符號就是表示演算所需時間的表達式。
計算複雜性的問題為什麼會在使用Normal equations的時候出現呢?
在正規方程(normal equations)中必須要透過計算(𝑋的Transpose*𝑋) 的反矩陣來求解𝑤*。
為何計算 (𝑋的Transpose*𝑋) 的反矩陣是在變數個數 𝑛 增多時才有計算複雜性的議題?𝑚 呢?
觀測值量很多(m很大)其實跟計算複雜性是沒有關係,因為𝑋 的外觀為 𝑚×𝑛,𝑋的Transpose 的外觀為 𝑛×𝑚,(𝑋的Transpose*𝑋)的外觀為 𝑛×𝑛。
因此只有在n變大的時候才有計算複雜性的議題!
但是為什麼計算 𝑛 很大的 𝑛×𝑛 反矩陣會產生計算複雜性議題呢?
這就要回到在2006年Numpy套件被發明出來之前,即使沒有Numpy,但線性代數、矩陣相乘還是要用,如果使用Vanilla Python(不用任何套件的Python)要計算𝐴 的反矩陣 𝐴(-1)了話:
在 Vanilla Python 計算一個 2×2 矩陣 𝐴 的反矩陣其實已經有點辛苦了…,更何況計算 3×3 的反矩陣要計算 9 個 2×2 矩陣的行列式(determinant):
以此類推 ,4×4 的反矩陣我們要計算 16 個 3×3 矩陣的行列式,𝑛×𝑛 的反矩陣就要計算 𝑛平方 個 (𝑛−1)×(𝑛−1) 矩陣的行列式。Numpy套件的底層還是用 C 語言與 Python 實作,使用封裝好的函數並不代表計算複雜性的問題不存在。
因此當面對的特徵矩陣n很大時,正規方程的計算複雜性問題就會浮現,這時讀者可能會好奇什麼時候𝑛會很大呢?
在特徵矩陣是圖像時很容易遭遇,例如:
一張28*28的圖片,n就是784
一張 224 x 224 x 3 的圖片,n 就是 15052
因此機器學習、深度學習更傾向使用梯度遞減的方法尋找 𝑤,而非正規方程
延伸閱讀:https://arxiv.org/abs/1609.04747
感謝你閱讀完這篇文章,如果你覺得這些文章對你有幫助請在底下幫我拍個手(長按最多可以拍50下手)。