機器學習演算法數學基礎之 —— 線性代數篇（2）

02-26

核心問題

求多元方程組的解。

核心技能

乘積、內積、秩

已知矩陣 A 和矩陣 B，求 A 和 B 的乘積 C=AB。

矩陣 A 大小為 mxn，矩陣 B 大小為 nxp。

常規方法：矩陣 C 中每一個元素 Cij = A 的第i行乘以（點乘）B 的第 j 列。

設有 n 維向量

令 $[x,y]=x_{1}y_{1}+x_{2}y_{2}+...+x_{n}y_{n}$ ，稱 $[x,y]$ 為向量 x 與 y 的內積。

在線代中秩的定義：

一個矩陣 A 的列秩是 A 的線性無關的列的極大數目。類似地，行秩是 A 的線性無關的行的極大數目。矩陣的列秩和行秩總是相等的，因此它們可以簡單地稱作矩陣 A 的秩，通常表示為 rank(A)。

矩陣列空間、行空間的維度相等。任意一個矩陣都可以經過一些列的初等變換為階梯形矩陣，而且階梯形矩陣的秩等於其中非零行的個數。

所以矩陣秩的計算方法：

用初等變換把矩陣華為階梯形，則該階梯形矩陣中的非零行數就是所求矩陣的秩。

高斯消元法

高斯消元法（Gaussian Elimination），是線性代數中的一個演算法，可用來為線性方程組求解，求出矩陣的秩，以及求出可逆方陣的逆矩陣。當用於一個矩陣時，高斯消元法會產生出一個「行梯陣式」。

值得提一下的是，雖然該方法以數學家卡爾·高斯命名，但最早出現於中國古籍《九章算術》，成書於約公元前150年。

複雜度：高斯消元法的演算法複雜度是 $O(n^{3})$ ；這就是說，如果係數矩陣的是 n × n，那麼高斯消元法所需要的計算量大約與 $n^{3}$ 成比例。

矩陣求逆

求矩陣的逆矩陣的常用方法有兩種：

伴隨矩陣法
初等變換法

最小二乘法

最小二乘法是對過度確定系統，即其中存在比未知數更多的方程組，以回歸分析求得近似解的標準方法。在這整個解決方案中，最小二乘法演算為每一方程式的結果中，將殘差平方和的總和最小化。

回歸分析模型

主要思想：選擇未知參數，使得理論值與觀測值之差的平方和達到最小：

$H=sum_{0}^{m}{(y-y_{i})^{2}}$

最重要的應用是在曲線擬合上。最小平方所涵義的最佳擬合，即殘差（殘差為：觀測值與模型提供的擬合值之間的差距）平方總和的最小化。

應用

求解線性回歸

最小二乘法
梯度下降法

假設有一個估計函數： $h_{0}(x)= heta^{T}X$ ，

其錯誤函數為： $J( heta)=frac{1}{2}sum_{i=1}^{m}{(h_{ heta}(x^{(i)})-y^{(i)})^{2}}$

這個錯誤估計函數是 x(i) 的估計值與真實值 y(i) 的差的平方和，前面乘上 1/2，是因為在求導的時候，這個係數就不見了。

梯度下降法的流程：

1）首先對 θ 賦值，這個值可以是隨機的，也可以讓 θ 是一個全零的向量。
2）改變 θ 的值，使得 J(θ) 的值按梯度下降的方向減小。

參數 θ 與誤差函數 J(θ) 的關係圖

紅色部分表示 J(θ) 有著比較高的取值，我們希望能夠讓 J(θ) 的值儘可能的低，也就是取到深藍色的部分。θ0、θ1 表示 θ 向量的兩個維度。上面提到梯度下降法的第一步，是給 θ 一個初值，假設隨機的初值位於圖上紅色部分的十字點。然後我們將 θ 按梯度下降的方向進行調整，就會使 J(θ) 往更低的方向進行變化，如圖所示，演算法的結束將在 θ 下降到無法繼續下降為止。

θ 的更新： $heta_{i}= heta_{i}-alphafrac{partial}{partial heta}J( heta)$

θi 表示更新前的值，減號後邊的部分表示按梯度方向減少的量，α 表示步長，也就是每次按梯度減少的方向變化多少。

梯度是有方向的，對於一個向量 θ，每一維分量 θi 都可以求出一個梯度的方向，我們就可以找到一個整體的方向，在變化的時候，我們就朝著下降最多的方向進行變化，就可以達到一個最小點，不管它是局部的還是全局的。

主成分分析（PCA）

主成分分析（Principal components analysis，PCA）是一種分析、簡化數據集的技術。常用於降低數據集的維數，同時保持數據集中對方差貢獻最大的特徵。這是通過保留低階主成分，忽略高階主成分做到的。

其方法主要是通過對協方差矩陣進行特徵分解，以得出數據的主成分（即特徵向量）與它們的權值（即特徵值）。PCA 是最簡單的以特徵量分析多元統計分布的方法。其結果可以理解為對原數據中的方差做出解釋：哪一個方向上的數據值對方差的影響最大？換而言之，PCA 提供了一種降低數據維度的有效辦法；如果分析者在原數據中除掉最小的特徵值所對應的成分，那麼所得的低維度數據必定是最優化的（也即，這樣降低維度必定是失去訊息最少的方法）。

主成分分析在分析複雜數據時尤為有用，比如人臉識別。

實例參考：PCA 簡單實例

奇異值分解（SVD）

奇異值分解（Singular Value Decomposition, SVD）是線性代數中一種重要的矩陣分解，在信號處理、統計學等領域有重要應用。

PCA 的實現一般有兩種，一種是通過特徵值分解實現，另一種就是用奇異值分解來實現。但特徵值分解只是針對方針而言的，當處理 m*n 的矩陣時，就需要特徵值分解了。

在吳軍老師的《數學之美》中也有提到用 SVD 做文本分類的篇幅，提到的例子是這樣的：首先用一個 M * N 的大型矩陣 A 來描述一百萬篇文章和五十萬個詞的關聯性。矩陣中，每一行對應一篇文章，每一列對應一個詞。

在該矩陣中，M=1,000,000 ，N=500,000 ，第 i 行第 j 列的元素是字典中第 j 個詞在第 i 篇文章中出現的加權詞頻（比如，TF/IDF) 。奇異值分解就是把這樣一個大矩陣，分解成三個小矩陣相乘：

（矩形面積的大小也對應了信息量的大小～）

這個大矩陣被分解成一個100萬乘100的矩陣 X ，一個100乘100的矩陣 B ，以及一個100乘50萬的矩陣 Y 。分解後，相應的存儲量和計算量都小了三個數量級以上。

第一個矩陣 X 中的每一行表示意思相關的一類詞，其中的每個非零元素表示這類詞中每個詞的相關性，數值越大越相關。最後一個矩陣 Y 中的每一列表示同一主題一類文章，其中每個元素表示這類文章中每篇文章的相關性。中間的矩陣則表示類詞和文章雷之間的相關性。因此，我們只要對關聯矩陣 A 進行一次奇異值分解，w 我們就可以同時完成了近義詞分類和文章的分類。（同時得到每類文章和每類詞的相關性）。

在實際應用過程中，可以直接調用 numpy.linalg.svd

實例參考：機器學習中 SVD 的應用

王天宇：機器學習演算法數學基礎之 —— 微積分篇（1）zhuanlan.zhihu.com

王天宇：機器學習演算法數學基礎之 —— 統計與概率論篇（3）zhuanlan.zhihu.com