Mathematics in Machine Learning

在學習 Machine Learning 的過程中,接觸到的數學最主要的還是以線性代數 (Linear Algebra) 與機率統計 (Probability & Statistics)為最重要的兩個面向。

在機器學習中碰到這兩個數學領域,有部分的確是大學即會碰到的內容,但有些部分卻也是比較深入的部分,舉例來說,在討論 VC dimension 時所使用的技巧有部分我想應該就比較偏向於研究所的「數理統計」。儘管如此,在學習的時候或許無法這麼嚴謹的證明每一個性質,但從直觀來理解倒也不算是真的非常困難。

以下我試圖將我所碰到的部分整理出來,以提供初學者了解,並且也可以方便我回頭再來 review。

線性代數 Linear Algebre

在機器學習的數學運算中,會經常將手邊有的資料進行向量化,利用矩陣來進行所有的向量操作,向量跟矩陣就此產生了連結。

當然不只有操作產生連結,我們會反過來思考 : 「在矩陣上的特性是否能展現在向量 ( 資料 )上 ?」,而事實證明,我們的確也利用了許多線性代數的性質來解決機器學習上面的問題。

  • 矩陣運算

\vec{A}=(a_1,a_2,\ldots,a_n)
\vec{B}=(b_1,b_2,\ldots,b_n)
\vec{A}\cdot\vec{B}=(a_1b_1,a_2b_2,\ldots,a_nb_n)=\begin{bmatrix}a_1&a_2\cdots a_n\end{bmatrix}\cdot\begin{bmatrix}b_1\\b_2\\\vdots \\b_n\end{bmatrix}=A^TB

  • 擬反矩陣 pseudo-inverse

當我們在進行最佳化找尋解析解時,如若遇到矩陣是不可逆矩陣 ( 不存在反矩陣 ),我們可以利用擬反矩陣(廣義反矩陣) pseudo-inverse來代替

\forall A\in\mathbb{C}^{m\times n}\ ,\ \exists !A^\dagger s.t. :

1.AA^{\dagger}A=A
2.A^{\dagger}AA{^\dagger}=A^{\dagger}
3.(A^\dagger A)^T=A^\dagger A
4.(AA^\dagger)^T=AA^\dagger

  • 矩陣微分

如上所述,我們在機器學習裡面也常利用矩陣微分來找出最佳解,矩陣微分其實類似於一般的函數微分 : ( 以下假設 \boldsymbol{A,B,C} 均為常數矩陣,\boldsymbol{a,b,c} 為向量矩陣,均與 \boldsymbol{X,\mathbf{x}} 無關 )

一次函數微分

\frac{d(\boldsymbol{\mathbf{x}}^T\boldsymbol{A})}{d(\boldsymbol{\mathbf{x}})}=\boldsymbol{A}

\frac{d(\boldsymbol{a}^T\boldsymbol{X}\boldsymbol{b})}{d(\boldsymbol{X})}=\boldsymbol{ab}^T, 若 \boldsymbol{a,b} 換成 \boldsymbol{A,B} 也適用

二次函數微分

\frac{d(\boldsymbol{\mathbf{x}}^T\boldsymbol{A}\boldsymbol{\mathbf{x}})}{d(\boldsymbol{\mathbf{x}})}=(\boldsymbol{A+A})^T\boldsymbol{\mathbf{x}} , 若 \boldsymbol{A} 為 Symmetric,則為 2\boldsymbol{A\mathbf{x}}

\frac{d((\boldsymbol{A}\boldsymbol{\mathbf{x}}+\boldsymbol{b})^T\boldsymbol{C(\boldsymbol{D}\boldsymbol{\mathbf{x}}+\boldsymbol{e}))}}{d(\boldsymbol{\mathbf{x}})}=\boldsymbol{A}^T\boldsymbol{C}(\boldsymbol{D}\boldsymbol{\mathbf{x}}+\boldsymbol{e})+\boldsymbol{D}^T\boldsymbol{C}^T(\boldsymbol{A}\boldsymbol{\mathbf{x}}+\boldsymbol{b})

更多更仔細的矩陣導數可參考 : 矩陣導數 — 線代啟示錄

  • 投影矩陣 Projection Matrix

在回歸分析裡面,Projection Matrix 佔有十分重要的分量,尤其在理論推導上面,我們可以將預測值視為真實值經由 Projection Matrix 投射後的結果 (詳見 : 林軒田機器學習基石筆記 – 第九講、第十講)

Projection Matrix \boldsymbol{H} 具有下列性質 :

  1. \boldsymbol{H} is symmetric
  2. \boldsymbol{H}^k=\boldsymbol{H}
  3. (\boldsymbol{I}-\boldsymbol{H})^k=\boldsymbol{I}-\boldsymbol{H}
  4. tr(\boldsymbol{H})=d+1
  • 空間變換 Transformation

\phi : X\longrightarrow Z  via \phi(\boldsymbol{\mathbf{x}})=\boldsymbol{\mathbf{z}}
where \boldsymbol{\mathbf{x}}=(x_1,x_2,\ldots,x_d)\in X and \boldsymbol{\mathbf{z}}=(z_1,z_2,\ldots,z_{\tilde{d}})\in Z

空間變換這樣的概念,在許多的應用層面 ( 不只機器學習 ) 都被廣泛使用,我們在現有空間上遭遇困難,便會試著利用縣性或非線性變換成另外一種空間後,在嘗試利用我們熟悉的方式去解決。
在機器學習上,我們可以利用這種方式解決非線性可分的問題 (將非線性可分的資料經由多項式轉換變成線性可分後,再利用線性模型進行處理 ) ,而廣為人知的支持向量機 (SVM) 也是利用類似的概念處理非線性問題。

  • 特徵值 (eigen-value) & 特徵向量 (eigen-vector)

設 A 為一個 n\times n 階矩陣,當\mathbf{x}\lambda 滿足下列特徵方程 : \mathbf{Ax}=\lambda\mathbf{x},我們稱 \mathbf{x}\mathbf{A} 的特徵向量 (eigan-vector),而 \lambda 則為 \mathbf{A} 的特徵值。

當我們在處理 Deep Learning 的最佳權重時,由於經過多層的加權,最後的方程式可能高達四次式以上,無法找出相對應的解析解,但可以經由特徵分解試圖找出最佳解。

機率論 Probability

  • 聯合機率 Joint Probability

P(X=x_i,Y=y_j)=\frac{n_{ij}}{N}\Longrightarrow P(X=x_i)=\sum\limits_{\forall j}P(X=x_i,Y=y_j)

  • 條件機率 Conditional Probability

P(Y=y_j\mid X=x_i) : 在 $X=x_i$ 已知的條件下 $Y=y_j$也發生的機率

\overset{defn}{\Longrightarrow}P(Y=y_j\mid X=x_i)=\frac{P(X=x_i\cap Y=y_j)}{P(X=x_i)}

\Longrightarrow P(X=x_i\cap Y=y_j)=P(X=x_i,Y=y_j)=P(Y=y_j\mid X=x_i)\cdot P(X=x_i)

  • 貝氏定理 Bayes’ Theorem

P(Y\mid X)=\frac{P(X\mid Y)\cdot P(Y)}{P(X)}

  • 霍夫丁不等氏 Hoeffding’s Inequality

給定某事件在母體中機率 \mu,現有一抽樣,其樣本數 N,此事件在樣本中機率\nu
\mu\nu之誤差大於 \epsilon 的 機率不會超過 2e^{-2\epsilon^2N}
\mathbb{P}(|\mu-\nu|>\epsilon) \leq 2e^{-2\epsilon^2N}

微積分 Calculus

  • 梯度 Gradient

假設 f(x_1,x_2,..,x_n)\mathbb{R}^n 空間中一曲面方程式,
我們便可以求出 在x_i 方向上的偏導函數 \frac{\partial f}{\partial x_i}=f(x_1,x_2,..,x_n) 中某一點 xx_i 方向的切線斜率 =f(x_1,x_2,..,x_n) 中某一點 xx_i 方向的傾斜程度
而偏微分的正負號當然也可以表現出 f(x_1,x_2,..,x_n) 中某一點 x 在各軸上面往上升的方向。

如果我們把上述每一個方向的偏導函數收集起來,便是我們的梯度 :
\nabla f(x_1,x_2,..,x_n) =(\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},..,\frac{\partial f}{\partial x_n})
那麼,若我們想要找到 f(x_1,x_2,..,x_n) 的極值,最簡單的方式便是令 \nabla f(x_1,x_2,..,x_n) =0

在機器學習的範疇中,我們很常利用梯度作為最佳化的方式,我們可能無法找到梯度為0的最佳解,但可以經由不停的梯度下降迭代出更好的解,經過夠多次數的迭代或是真的找到梯度為0,我們便可以找出相對最佳解來。
(詳見 : 梯度下降法 Gradient Descent)

  • 拉格朗日算子 Lagrange Multiplier

基本上沒有條件限制的求解最小值,就是直接令導數為0來求解,但如果 f(x_1,x_2,\ldots,x_n) 必須滿足 \begin{cases}g_1(x_1,x_2,\ldots,x_n)=0\\g_2(x_1,x_2,\ldots,x_n)=0\\\vdots\\g_m(x_1,x_2,\ldots,x_n)=0\end{cases} 這些條件,在數學上我們會使用 Lagrange 乘數法 :令 h(x_1,x_2,\ldots,x_n)=f+\sum\limits_{\forall m}\lambda_mg_m ,然後對 h 求取梯度且令其為0來找出 x_1,x_2,\ldots,x_n\lambda_m的關係式後再帶回條件式中求得最佳解( 不難證明經過 Lagrange 乘數法處理之後的解並不會跑掉 )

當然我們的條件式若為不等式也仍然可以處理 :
f(x_1,x_2,\ldots,x_n) 必須滿足 \begin{cases}g_1(x_1,x_2,\ldots,x_n)\leq0\\g_2(x_1,x_2,\ldots,x_n)\leq0\\\vdots\\g_m(x_1,x_2,\ldots,x_n)\leq0\end{cases} 這些條件,一樣我們可以使用 Lagrange 乘數法 : h(x_1,x_2,\ldots,x_n)=f+\sum\limits_{\forall m}\lambda_mg_m ,但這邊需要注意的地方是,條件式為不等式之解並非 closed-form ,我們可以用許多優化演算法來找出最優解,而這個最佳解必定要符合 Karush-Kuhn-Tucker Condition。

( 參閱 : Constrained Optimization Using Lagrange Multipliers )

二次規劃 Quadratic Programming

當我們在處理 SVM 的最佳化過程,我們會遭遇到一個難題 : 有條件的 error function 想要手動硬解並非易事,有條件的 Gradient Descent 也是相同困難。

然而我們最後得到的 error function 為二次式,且條件均為線性不等式,我們就可以先利用 Lagrange multiplier 得出 h 後再經由 Quadratic Programming solver 進行對偶空間的最佳化後再回傳到原本空間來得出最佳解。


補充 : 在統計學中取 log 的意義

對數函數本身是單調 ( monotonic ) 函數,將原本數據取對數後並不會改變數據間的相對關係,這樣取對數的步驟主要有幾個原因 :

1. 將資料的數據range變小,便於計算
原本 資料分布由 1-1000,取對數後約分布在0-7之間,方便我們進行各種運算。

2. 將乘法運算轉換為加法運算
也就是我們可以經由取對數將複雜、非線性模型轉換成為線性模型

3. 為了可以更清楚看見資料間的關係

左上圖為各國家GDP與人口之間的關係,經過對數轉換後,可以發現這兩個變量有明顯的線性關係。其實我們也可以說,取對數可以將原本過於左偏的資料轉變成為接近常態分佈的樣貌。

4. 在經濟學上,取對數會讓整個模型更貼近於真實狀況,換句話來說,沒有取對數的情形與現實會產生落差


參考資料 :

  1. 林軒田Hsuan-Tien Lin 機器學習基石Machine Learning Foundations
  2. 林軒田Hsuan-Tien Lin 機器學習基石Machine Learning Techniques
  3. from Probability Theory to Softmax Function, and then Cross Entropy.
  4. 矩阵微分
  5. 王富祥,游雪玲(2017)。七把刀弄懂微積分(三版)
  6. 王富祥,游雪玲(2019)。線性代數的天龍八步(三版)
  7. 線代啟示錄 — Karush-Kuhn-Tucker (KKT) 條件
廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s