【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下手）。
