owned this note
owned this note
Published
Linked with GitHub
Mathematics in Machine Learning
==
###### tags: `Mathematics`
在學習 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})$
更多更仔細的矩陣導數可參考 : [矩陣導數 -- 線代啟示錄](https://ccjou.wordpress.com/2013/05/31/%E7%9F%A9%E9%99%A3%E5%B0%8E%E6%95%B8/)
* **投影矩陣 Projection Matrix**
在回歸分析裡面,Projection Matrix 佔有十分重要的分量,尤其在理論推導上面,我們可以將預測值視為真實值經由 Projection Matrix 投射後的結果 (詳見 : [林軒田機器學習基石筆記 - 第九講、第十講](https://hackmd.io/s/rJ7zrsB5V))
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**
給定某事件在母體中機率μ,現有一抽樣,其樣本數 $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)$ 中某一點 $x$ 在 $x_i$ 方向的切線斜率 $=f(x_1,x_2,..,x_n)$ 中某一點 $x$ 在 $x_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](https://hackmd.io/s/ryQypiDK4))
* **拉格朗日算子 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](http://people.duke.edu/~hpgavin/cee201/LagrangeMultipliers.pdf) )
## 二次規劃 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. 為了可以更清楚看見資料間的關係**
![](https://i.imgur.com/lXBu97t.png)
左上圖為各國家GDP與人口之間的關係,經過對數轉換後,可以發現這兩個變量有明顯的線性關係。其實我們也可以說,取對數可以將原本過於左偏的資料轉變成為接近常態分佈的樣貌。
**4. 在經濟學上,取對數會讓整個模型更貼近於真實狀況,換句話來說,沒有取對數的情形與現實會產生落差**
---
參考資料 :
1. 林軒田Hsuan-Tien Lin [機器學習基石Machine Learning Foundations](https://www.youtube.com/watch?v=nQvpFSMPhr0&list=PLXVfgk9fNX2I7tB6oIINGBmW50rrmFTqf)
2. 林軒田Hsuan-Tien Lin [機器學習基石Machine Learning Techniques](https://www.youtube.com/watch?v=A-GxGCCAIrg&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2)
3. [from Probability Theory to Softmax Function, and then Cross Entropy](https://medium.com/@CecileLiu/from-probability-theory-to-softmax-function-775e3c631ede?fbclid=IwAR0AH_s1JE2nB5LhMJg4dutAbiQeyJxhbeehH2SN6ZUjqnccZFnkao0c3pA).
4. [矩阵微分](http://www.cnblogs.com/xuxm2007/p/3332035.html)
5. 王富祥,游雪玲(2017)。七把刀弄懂微積分(三版)
6. 王富祥,游雪玲(2019)。線性代數的天龍八步(三版)
7. 線代啟示錄 --- [Karush-Kuhn-Tucker (KKT) 條件](https://ccjou.wordpress.com/2017/02/07/karush-kuhn-tucker-kkt-%E6%A2%9D%E4%BB%B6/)