林軒田機器學習基石筆記 - 第九講、第十講

• 本文為一系列課程之筆記，建議從" 機器學習基石筆記-1 "開始閱讀 >

• 本文討論內容請參考: 機器學習基石第九講 : Linear Regression 機器學習基石第十講 : Logistic Regression

• 本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義

---

在開始接下來的課程前，我想先緩一緩腳步。

從前面的課程一路到現在，我們學到了這麼多的想法、概念、工具，究竟這些東西的關聯性是什麼 ? 它們跟機器學習的關係又是什麼 ?

當我們手中有一堆資料 ( $\mathbb{D}$ )，我們會先問自己，我們想要從這些資料裡面知道什麼 ? 預測什麼 ? ( $ClassificationorRegression$ ) 在這樣的問題下，我們最終會希望有一個模型 ( $g$ ) 可以盡量準確地預測出我們想要知道的事情。( $g\approx f$ )

想要得到這樣的模型，我們就得從許多可能性中 ( $h$ )，找出跟我們手中資料真實狀況誤差最小的 ( $min{E}_{in}(h)=minerr(y,\hat{y})$ ) 來作為我們的模型。而這樣找出最小值的過程，就是我們所謂演算法 ( $algorithm$ )。

PS: 當我們決定了想要什麼樣子型態的模型 ( PLA , Pocket , Linear regression , Logistic regression...) ，那麼找出最小值的演算法也同時被確定下來。

當我們理清楚其中的關係後，很清楚地可以知道，所有演算法就是針對某一個error measure 尋找最小值的方法，也就是說，當我們要決定模型的型態，也要先決定出來我們要用什麼樣子的 error measure 。( 回想一下，當我們決定了 error measure 後，機器學習的可行性便也可以確定¹)

Linear Regression

( 紅線部分我們稱為 剩餘residuals )

Linear regression : 找出 line / hyperplane 有最小的 residuals

Linear Regression Algorithm

在線性回歸中，最常用的 error measure 就是 square error

$err(y,\hat{y})=(y-\hat{y}{)}^2$ $⟹E_{in}(h)=\frac{1}{N}\sum _{n=1}^N(h({\mathbb{X}}_n)-y_n{)}^{2}and{E}_{out}(h)=\underset{(\mathbb{X},y)\sim \mathbb{P}}{\mathbb{E}}({\mathbb{W}}^T\mathbb{X}-y{)}^2$

Step 1 : 先將資料整理成矩陣型態，找出以每一筆資料為列向量的 $\mathbb{X}$ 矩陣及 $\mathbb{Y}$ 矩陣

Step 2 : 計算出 pseudo-inverse²³ ${\mathbb{X}}^{†}=\{\begin{array}{ll}({\mathbb{X}}^T\mathbb{X}{)}^{-1}{\mathbb{X}}^T,& \text{if}{\mathbb{X}}^T\mathbb{X}\text{is invertible}\\ definedbyotherway,& \text{if}{\mathbb{X}}^T\mathbb{X}\text{is'nt invertible}\end{array}$

Step 3 : 最佳解 ${\mathbb{W}}_{lin}={\mathbb{X}}^{†}\mathbb{Y}$

---

$Proof$

1. $Existence:$

$E_{in}(\mathbb{W})=\frac{1}{N}\sum _{n=1}^N({\mathbb{W}}^T{\mathbb{X}}_n-y_n{)}^2=\frac{1}{N}\sum _{n=1}^N({{\mathbb{X}}_n}^T\mathbb{W}-y_n{)}^2$

$=\frac{1}{N}{\Vert \begin{array}{c}{{\mathbb{X}}_1}^T\mathbb{W}-y_1\\ {{\mathbb{X}}_2}^T\mathbb{W}-y_2\\ ⋮\\ {{\mathbb{X}}_N}^T\mathbb{W}-y_N\end{array}\Vert }^2=\frac{1}{N}{\Vert \begin{array}{c}\left[\begin{array}{c}{{\mathbb{X}}_1}^T\\ {{\mathbb{X}}_2}^T\\ ⋮\\ {{\mathbb{X}}_N}^T\end{array}\right]\mathbb{W}-\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_N\end{array}\right]\end{array}\Vert }^2=\frac{1}{N}{\Vert \begin{array}{c}\mathbb{X}\mathbb{W}-\mathbb{Y}\end{array}\Vert }^2$

$\because E_{in}(\mathbb{W})$ is a conti , diff ,convex function

$\therefore \mathrm{\exists }{\mathbb{W}}_{lin}$ s.t. $\mathrm{\nabla }{E}_{in}({\mathbb{W}}_{lin})=\left[\begin{array}{c}\frac{\partial E_{in}}{\partial w_0}({\mathbb{W}}_{lin})\\ \frac{\partial E_{in}}{\partial w_1}({\mathbb{W}}_{lin})\\ ⋮\\ \frac{\partial E_{in}}{\partial w_d}({\mathbb{W}}_{lin})\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right]$

$\because E_{in}(\mathbb{W})=\frac{1}{N}{\Vert \begin{array}{c}\mathbb{X}\mathbb{W}-\mathbb{Y}\end{array}\Vert }^2=\frac{1}{N}({\mathbb{W}}^T{\mathbb{X}}^T\mathbb{X}\mathbb{W}-2{\mathbb{W}}^T{\mathbb{X}}^T\mathbb{Y}+{\mathbb{Y}}^T\mathbb{Y})$

$\stackrel{let}{=}\frac{1}{N}({\mathbb{W}}^T\mathbb{A}\mathbb{W}-2{\mathbb{W}}^T\mathbb{B}+\mathbb{C})$

$⟹\mathrm{\nabla }{E}_{in}(\mathbb{W})=\frac{1}{N}(2\mathbb{A}\mathbb{W}-2\mathbb{B})=\frac{2}{N}({\mathbb{X}}^T\mathbb{X}\mathbb{W}-{\mathbb{X}}^T\mathbb{Y})\stackrel{let}{=}0$

$⟹\mathbb{W}={\mathbb{W}}_{lin}={\mathbb{X}}^{†}\mathbb{Y}where{\mathbb{X}}^{†}=\{\begin{array}{ll}({\mathbb{X}}^T\mathbb{X}{)}^{-1}{\mathbb{X}}^T,& \text{if}{\mathbb{X}}^T\mathbb{X}\text{is invertible}\\ definedbyotherway,& \text{if}{\mathbb{X}}^T\mathbb{X}\text{is'nt invertible}\end{array}$

Linear Regression 的可行性

由上述我們可以找出有最小誤差的預測模型 $\hat{\mathbb{Y}}=\mathbb{X}{\mathbb{W}}_{lin}=\mathbb{X}({\mathbb{X}}^T\mathbb{X}{)}^{-1}{\mathbb{X}}^T\mathbb{Y}\stackrel{let}{=}\mathbb{H}\mathbb{Y}$

我們可以把這個 $\mathbb{H}$ 看作是一種線性變換，將 $\mathbb{Y}$ 轉換到 $\hat{\mathbb{Y}}$ ，再更白話一點說，$\mathbb{H}$ 就是 $\mathbb{Y}$ 與 $\hat{\mathbb{Y}}$ 的一個線性關係。而這樣的一個關係它有一些特別的特性 : 1. $\mathbb{H}$ is symmetric 2. ${\mathbb{H}}^k=\mathbb{H}$ 3. $(\mathbb{I}-\mathbb{H}{)}^k=\mathbb{I}-\mathbb{H}$ 4. $tr(\mathbb{H})=d+1$

我們可以利用這些特性推導出 $\overline{E_{in}}=\underset{\mathbb{D}\stackrel{i.i.d}{\sim }\mathbb{P}}{\mathbb{E}}[E_{in}({\mathbb{W}}_{lin}w.r.t\mathbb{D})]=noiselevel\cdot (1-\frac{d+1}{N})$⁴ $\overline{E_{out}}=noiselevel\cdot (1+\frac{d+1}{N})$ ( 此式在僅用於Linear Regression，因此證明僅放在註釋中 )

這兩式指出，只要是從 $\mathbb{P}$ 這個分佈出來的，且尺寸為 $N$ ，那麼 $E_{in}$ 與 $E_{out}$ 的平均都會跟 $Noise$ 的平均有上述關係。

所以我們可以得出下圖 :

當 $N⟶\mathrm{\infty }$ ，$\overline{E_{in}}$ 與 $\overline{E_{out}}⟶{\sigma }^2$

$⟹\overline{E_{out}}$ 會被限制住

$⟹$ Linear Regression 是可行的 !

Linear Regression for Binary Classification

$⟹er{r}_{0/1}=([[sign({\mathbb{W}}^T\mathbb{X})\ne y_n]])\le er{r}_{sqr}=({\mathbb{W}}^T\mathbb{X}-y_n{)}^2$

$⟹classification{E}_{out}\le classification{E}_{in}+\mathrm{\Omega }(N,\mathbb{H},\delta )\le regression{E}_{in}+\mathrm{\Omega }(N,\mathbb{H},\delta )$

$⟹$ Linear regression 的誤差上界的確比 classification 的誤差上界來的大，但是其為解析解，非常容易可以求出解，所以用一些準確度來換得效率也是一個可以接受的選項，誘惑者可先用regression求出解析解後，再拿這個解作為初始值放入PLA去求得更好的解，這樣也可以避免PLA花太多時間再做迭代。

Logistic Regression

在現實生活中，我們有時候會想知道的事情不是單純的、絕對的、硬性的是非問題 ( 病人是否活著? )，或許我們會希望能夠有比較 soft 的分類 ( 病人活著的機率? )，或許，我們可以把這樣的 soft binary classification 視為是帶有 $Noise$ 的 classification ( 機器學習基石筆記-5 內談到的 "翻轉"機率 flipping noise level )。

$\mathbb{X}\stackrel{i.i.d}{\sim }\mathbb{P}$ , $\mathbb{Y}\stackrel{i.i.d}{\sim }\mathbb{P}(\mathbb{Y}\mid \mathbb{X})$

$⟹\{\begin{array}{l}Binaryclassificationf(\mathbb{X})=Sign(\mathbb{P}(+1\mid \mathbb{X})-\frac{1}{2})\in \{+1,-1\}\\ Softbinaryclassificationf(\mathbb{X})=\mathbb{P}(+1\mid \mathbb{X})\in [0,1]\end{array}$

上圖白話翻譯就是 : 對於每一個特徵，我們一樣可以給予不同的權重，計算出一個分數，再將這分數經由一個 連續(conti) , 可微(diff) , 單調(monotonic) $\theta$ 函數轉換成機率 ( $\theta :\mathbb{R}\to [0,1]$)，這樣的 $\theta$ 函數最常用的是 $Sigmoidfunction=\theta (s)=\frac{1}{1+e^s}$

Logistic Regression Algorithm

這樣機率型態的 error measure 我們使用 cross-entropy ( 交叉熵 ) error

$E_{in}(\mathbb{W})=cross-entropy=\frac{1}{N}\sum _{n=1}^N\ln (1+e^{-y_n{\mathbb{W}}^T{\mathbb{X}}_{\mathbb{n}}})$⁵

挑選一個初始值 ${\mathbb{W}}_0$ Step 1 : 計算當下 ${\mathbb{W}}_t$ 的梯度 $\mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)=\frac{1}{N}\sum _{n=1}^N\theta (-y_n{\mathbb{W}}^T\mathbb{X})(-y_n{\mathbb{X}}_n)$

Step 2 : 進行權重迭代更新 ${\mathbb{W}}_{t+1}={\mathbb{W}}_t-\eta \cdot \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)$

停止條件 : (1) $\mathrm{\nabla }{E}_{in}({\mathbb{W}}_{t+1})=0$ (2) 迭代次數夠多

---

$Proof$

$\because$ 我們要找出 $min(cross-entropyerror)=min(\frac{1}{N}\sum _{n=1}^N\ln (1+e^{(-y_n{\mathbb{W}}^T\mathbb{X})})$ 以求出 $g$

$\therefore \mathrm{\nabla }{E}_{in}(\mathbb{W})\stackrel{let}{=}0$

$\frac{\partial E_{in}}{\partial w_i}(\mathbb{W})=\frac{1}{N}\sum \frac{\partial \ln (A)}{\partial A}\cdot \frac{\partial A}{\partial B}\cdot \frac{\partial B}{\partial w_i}$ , where A$=1+e^{(-y_n{\mathbb{W}}^T\mathbb{X})}$ , B$=-y_n{\mathbb{W}}^T\mathbb{X}$ $=\frac{1}{N}\sum \frac{1}{A}\cdot e^B\cdot (-y_n\cdot x_{n_i})$ $=\frac{1}{N}\sum \frac{e^B}{1+e^B}\cdot (-y_n\cdot x_{n_i})$ $=\frac{1}{N}\sum \theta (B)\cdot (-y_n\cdot x_{n_i})$ $⟹\mathrm{\nabla }{E}_{in}(\mathbb{W})=\frac{1}{N}\sum \theta (-y_n{\mathbb{W}}^T\mathbb{X})\cdot (-y_n\cdot x_{n_i})\stackrel{let}{=}0$

在這裡有兩種可能性 :

Case 1 : $\theta (-y_n{\mathbb{W}}^T\mathbb{X})=0,\mathrm{\forall }\mathbb{W}⟹y_n{\mathbb{W}}^T\mathbb{X}⟶+\mathrm{\infty }⟹\mathbb{D}$ is linear separable ( $\because \mathrm{\forall }i$ , $y_i$ 與 ${\mathbb{W}}^T\mathbb{X}$ 同號 )

Case 2 : $\frac{1}{N}\sum \theta (-y_n{\mathbb{W}}^T\mathbb{X})\cdot (-y_n\cdot x_{n_i})=0⟹$ 非線性方程求解困難不可行

這邊我們可以發現想要找到類似 Linear Regression 的解析解會非常窒礙難行，所以我們要利用類似PLA的方式做迭代優化 :

${\mathbb{W}}_{t+1}={\mathbb{W}}_t+{\eta }^{\prime }\cdot \nu$

Gradient Descent 梯度下降⁶

How to choose $\eta$ & $\nu$ ?

Assume $\Vert \nu \Vert =1$ and ${\eta }^{\prime }>0$ is small enough

$E_{in}({\mathbb{W}}_{t+1})=E_{in}({\mathbb{W}}_t+{\eta }^{\prime }\cdot \nu )\approx E_{in}({\mathbb{W}}_{t+1})+{\eta }^{\prime }\cdot {\nu }^T\cdot \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)$

( ${\eta }^{\prime }$ : 大小 , $\nu$ : 方向 , $\mathrm{\nabla }{E}_{in}({\mathbb{W}}_t):角度$)

方向 $\nu$ :

最好的方向是 $-\mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)$ 且 $\Vert \nu \Vert =1$

$\therefore \nu =-\frac{\mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)}{\Vert \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)\Vert }$

大小 $\eta$ :

若 ${\eta }^{\prime }$ 太小，迭代次數會很多且容易落在相對極小值 ( 而非絕對最小值 ) 若 ${\eta }^{\prime }$ 太大，迭代結果震盪大，不夠穩定 因此最好的方式是 ${\eta }^{\prime }$ 隨著每一次迭代做調整

$\Rightarrow {\eta }^{\prime }\propto \Vert \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)\Vert \Rightarrow {\eta }^{\prime }=\eta \cdot \Vert \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)\Vert$

$PS:{\eta }^{\prime }$ 隨著迭代不斷更動，但更動"固定"比例為 $\eta$

綜合上述 :

${\mathbb{W}}_{t+1}\leftarrow {\mathbb{W}}_t+{\eta }^{\prime }\cdot \nu ⟹{\mathbb{W}}_{t+1}\leftarrow {\mathbb{W}}_t+{\eta }^{\prime }\cdot -\frac{\mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)}{\Vert \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)\Vert }⟹{\mathbb{W}}_{t+1}\leftarrow {\mathbb{W}}_t-\eta \cdot \mathrm{\nabla }{E}_{in}({\mathbb{W}}_t)$

註釋

2. 

$\because \mathbb{H}\mathbb{Y}=\hat{\mathbb{Y}}⟹\mathbb{H}$ transform $\mathbb{Y}$ to $\hat{\mathbb{Y}}$ $\because \mathbb{Y}-\hat{\mathbb{Y}}=(\mathbb{I}-\mathbb{H})\mathbb{Y}⟹(\mathbb{I}-\mathbb{H})$ transform $\mathbb{Y}$ to $\mathbb{Y}-\hat{\mathbb{Y}}$ $Supposethatf(\mathbb{X})\in \hat{\mathbb{Y}}=\mathbb{X}{\mathbb{W}}_{lin}$ $\therefore (\mathbb{I}-\mathbb{H})$ transform $Noise$ to $\mathbb{Y}-\hat{\mathbb{Y}}$ ( $\because \mathbb{Y}=f(\mathbb{X})+Noise$ ) 3. $E_{in}({\mathbb{W}}_{lin})=\frac{1}{N}{\Vert \begin{array}{c}\mathbb{Y}-\hat{\mathbb{Y}}\end{array}\Vert }^2=\frac{1}{N}{\Vert \begin{array}{c}(\mathbb{I}-\mathbb{H})\cdot Noise\end{array}\Vert }^2=\frac{1}{N}(N-(d+1)){\Vert \begin{array}{c}Noise\end{array}\Vert }^2$ ( $\because {\Vert \begin{array}{c}\mathbb{I}-\mathbb{H}\end{array}\Vert }^2=tr(\mathbb{I}-\mathbb{H})=tr(\mathbb{I})-tr(\mathbb{H})=N-(d+1)$ ) $⟹\overline{E_{in}}=\underset{\mathbb{D}\stackrel{i.i.d}{\sim }\mathbb{P}}{\mathbb{E}}[E_{in}({\mathbb{W}}_{lin}w.r.t\mathbb{D})]=noiselevel\cdot (1-\frac{d+1}{N})$ 同理可證 : $\overline{E_{out}}=noiselevel\cdot (1+\frac{d+1}{N})$

$g=\arg \underset{\mathrm{\forall }h}{max}(likelyhood(h))$ $\iff g=\arg \underset{\mathrm{\forall }\mathbb{W}}{max}(\prod _{n=1}^N\theta (y_n{\mathbb{W}}^T\mathbb{X}))$ $\iff g=\arg \underset{\mathrm{\forall }\mathbb{W}}{max}(\ln \prod _{n=1}^N\theta (y_n{\mathbb{W}}^T\mathbb{X}))$ $\iff g=\arg \underset{\mathrm{\forall }\mathbb{W}}{min}(\frac{1}{N}\sum _{n=1}^N-\ln \theta (y_n{\mathbb{W}}^T\mathbb{X}))$ $=\arg \underset{\mathrm{\forall }\mathbb{W}}{min}(\frac{1}{N}\sum _{n=1}^N-\ln (1+e^{(-y_n{\mathbb{W}}^T\mathbb{X})}{)}^{-1})$ $\begin{array}{c}=\arg \underset{\mathrm{\forall }\mathbb{W}}{min}(\underbrace{\frac{1}{N}\sum _{n=1}^N\ln (1+e^{(-y_n{\mathbb{W}}^T\mathbb{X})})})\\ cross-entropyerror\end{array}$

---

1. 可參閱 機器學習基石筆記-4↩︎

2. 擬反矩陣pseudo-inverse 又稱廣義反矩陣 $\mathrm{\forall }A\in {\mathbb{C}}^{m\times n},\mathrm{\exists }!A^{†}$ s.t. :
   $1.A{A}^{†}A=A$ $2.A^{†}AA{}^{†}=A^{†}$ $3.(A^{†}A{)}^T=A^{†}A$ $4.(A{A}^{†}{)}^T=A{A}^{†}$↩︎

3. 廣義反矩陣在數學上的應用之一便是用來求出最小平方法之解 $Assumemin\parallel AX-Y{\parallel }_2,thenX=A^{†}Y+(I-A^{†}A)w,wherewisarbitraryvector$↩︎

4. 此證明為簡易證明，雖不夠嚴謹，但仍可有不錯的解釋力 $Proof$ 1. $E_{in}({\mathbb{W}}_{lin})=\frac{1}{N}{\Vert \begin{array}{c}\mathbb{Y}-\hat{\mathbb{Y}}\end{array}\Vert }^2=\frac{1}{N}{\Vert \begin{array}{c}\mathbb{Y}-\mathbb{X}{\mathbb{X}}^{†}\mathbb{Y}\end{array}\Vert }^2=\frac{1}{N}{\Vert \begin{array}{c}(\mathbb{I}-\mathbb{X}{\mathbb{X}}^{†})\mathbb{Y}\end{array}\Vert }^2=\frac{1}{N}{\Vert \begin{array}{c}(\mathbb{I}-\mathbb{H})\mathbb{Y}\end{array}\Vert }^2$↩︎

5. Cross-Entropy $f(\mathbb{X})=\mathbb{P}(+1\mid \mathbb{X})⟺\mathbb{P}(\mathbb{Y}\mid \mathbb{X})=\{\begin{array}{ll}f(\mathbb{X})& y=+1\\ 1-f(\mathbb{X})& y=-1\end{array}$ $⟹\prod _{n=1}^N\mathbb{P}({\mathbb{X}}_n)\mathbb{P}(y_n\mid {\mathbb{X}}_n)$ $⟹\prod _{y_n=+1}\mathbb{P}({\mathbb{X}}_n)f({\mathbb{X}}_n)\prod _{y_m=-1}\mathbb{P}({\mathbb{X}}_m)(1-f({\mathbb{X}}_m))$ ---(1) 我們希望我們的預測 $h$ 可以有 $f$ 的表現 $\therefore \prod _{y_n=+1}\mathbb{P}({\mathbb{X}}_n)h({\mathbb{X}}_n)\prod _{y_m=-1}\mathbb{P}({\mathbb{X}}_m)(1-h({\mathbb{X}}_m))$ --- (2) * 若 $h\approx f$，則上述(1)(2)兩式理應接近 且 (1)式應該會非常接近1 * 我們將(2)式定義成一個函數 稱為 $likelyhood(h)$，則我們想要的 $g=\arg \underset{\mathrm{\forall }h}{max}(likelyhood(h))$ $\therefore likelyhood(h)$ $=\prod _{y_n=+1}\mathbb{P}({\mathbb{X}}_n)h({\mathbb{X}}_n)\prod _{y_m=-1}\mathbb{P}({\mathbb{X}}_m)(1-h({\mathbb{X}}_m))$ $=\prod _{y_n=+1}\mathbb{P}({\mathbb{X}}_n)h({\mathbb{X}}_n)\prod _{y_m=-1}\mathbb{P}({\mathbb{X}}_m)$$(-h({\mathbb{X}}_m))$ $(\because h(\mathbb{X})=\theta ({\mathbb{W}}^T\mathbb{X})and1-\theta (s)=-\theta (s))$ $\propto \prod _{n=1}^{N}h(y_n{\mathbb{X}}_n)=\prod _{n=1}^N\theta (y_n{\mathbb{W}}^T\mathbb{X})$↩︎

6. 有關於梯度下降法的更詳細討論可以參閱 Gradient descent 梯度下降 一文↩︎