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

發表於 更新於 分類於 ， 閱讀次數： Disqus：

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

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

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

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

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

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

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

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

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

Linear Regression

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

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

Linear Regression Algorithm

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

\(err(y,\hat y)=(y-\hat y)^2\) \(\Longrightarrow E_{in}(h)=\frac{1}{N}\sum\limits_{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-inverse23 \(\mathbb{X}^\dagger=\begin{cases}(\mathbb{X}^T\mathbb{X})^{-1}\mathbb{X}^T,& \mbox{if}\ \mathbb{X}^T\mathbb{X}\ \mbox{is invertible}\\defined\ by\ other\ way,&\mbox{if}\ \mathbb{X}^T\mathbb{X}\ \mbox{is'nt invertible}\end{cases}\)

Step 3 : 最佳解 \(\mathbb{W}_{lin}=\mathbb{X}^\dagger\mathbb{Y}\)

\(Proof\)

  1. \(Existence :\)

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

\(=\frac{1}{N}\begin{Vmatrix} {\mathbb{X}_1}^T\mathbb{W}-y_1 \\ {\mathbb{X}_2}^T\mathbb{W}-y_2 \\ \vdots\\ {\mathbb{X}_N}^T\mathbb{W}-y_N \\ \end{Vmatrix}^2=\frac{1}{N}\begin{Vmatrix}\begin{bmatrix}{\mathbb{X}_1}^T \\{\mathbb{X}_2}^T\\ \vdots \\{\mathbb{X}_N}^T\end{bmatrix}\mathbb{W}-\begin{bmatrix}y_1\\y_2\\ \vdots \\y_N\end{bmatrix} \end{Vmatrix}^2=\frac{1}{N}\begin{Vmatrix}\mathbb{X}\mathbb{W}-\mathbb{Y}\end{Vmatrix}^2\)

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

\(\therefore \exists \mathbb{W}_{lin}\) s.t. \(\nabla E_{in}(\mathbb{W}_{lin})=\begin{bmatrix}\frac{\partial E_{in}}{\partial w_0}(\mathbb{W}_{lin})\\\frac{\partial E_{in}}{\partial w_1}(\mathbb{W}_{lin})\\ \vdots\\\frac{\partial E_{in}}{\partial w_d}(\mathbb{W}_{lin})\\\end{bmatrix}=\begin{bmatrix}0\\0\\\vdots\\0\end{bmatrix}\)

\(\because E_{in}(\mathbb{W})=\frac{1}{N}\begin{Vmatrix}\mathbb{X}\mathbb{W}-\mathbb{Y}\end{Vmatrix}^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})\)

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

\(\Longrightarrow \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})\overset{let}{=}0\)

\(\Longrightarrow\mathbb{W}=\mathbb{W}_{lin}=\mathbb{X}^\dagger\mathbb{Y}\ where\ \mathbb{X}^\dagger=\begin{cases}(\mathbb{X}^T\mathbb{X})^{-1}\mathbb{X}^T,& \mbox{if}\ \mathbb{X}^T\mathbb{X}\ \mbox{is invertible}\\defined\ by\ other\ way,&\mbox{if}\ \mathbb{X}^T\mathbb{X}\ \mbox{is'nt invertible}\end{cases}\)

Linear Regression 的可行性

由上述我們可以找出有最小誤差的預測模型 \(\hat{\mathbb{Y}}=\mathbb{X}\mathbb{W}_{lin}=\mathbb{X}(\mathbb{X}^T\mathbb{X})^{-1}\mathbb{X}^T\mathbb{Y}\overset{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}\overset{i.i.d}{\sim}\mathbb{P}}{\mathbb{E}}[E_{in}(\mathbb{W}_{lin}\ w.r.t\ \mathbb{D})]=noise\ level\cdot(1-\frac{d+1}{N})\)4 \(\overline{E_{out}}=noise\ level\cdot(1+\frac{d+1}{N})\) ( 此式在僅用於Linear Regression，因此證明僅放在註釋中 )

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

所以我們可以得出下圖 :

當 \(N\longrightarrow\infty\) ，\(\overline{E_{in}}\) 與 \(\overline{E_{out}}\longrightarrow\sigma^2\)

\(\Longrightarrow\overline{E_{out}}\) 會被限制住

\(\Longrightarrow\) Linear Regression 是可行的 !

Linear Regression for Binary Classification

\(\Longrightarrow err_{0/1}=([\![sign(\mathbb{W}^T\mathbb{X})\neq y_n]\!])\leq err_{sqr}=(\mathbb{W}^T\mathbb{X}-y_n)^2\)

\(\Longrightarrow\ classification\ E_{out}\leq\ classification\ E_{in}+\Omega(N,\mathbb{H},\delta)\leq\ regression\ E_{in}+\Omega(N,\mathbb{H},\delta)\)

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

Logistic Regression

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

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

\(\Longrightarrow\begin{cases}Binary\ classification\ f(\mathbb{X})=Sign(\mathbb{P}(+1\mid\mathbb{X})-\frac{1}{2})\in\left\{+1,-1\right\}\\Soft\ binary\ classification\ f(\mathbb{X})=\mathbb{P}(+1\mid\mathbb{X})\in\left[0,1\right]\end{cases}\)

上圖白話翻譯就是 : 對於每一個特徵，我們一樣可以給予不同的權重，計算出一個分數，再將這分數經由一個 連續(conti) , 可微(diff) , 單調(monotonic) \(\theta\) 函數轉換成機率 ( \(\theta:\mathbb{R}\rightarrow\left[0,1\right]\))，這樣的 \(\theta\) 函數最常用的是 \(Sigmoid\ function=\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\limits_{n=1}^{N}\ln(1+e^{-y_n\mathbb{W}^T\mathbb{X_n}})\)5

挑選一個初始值 \(\mathbb{W}_0\) Step 1 : 計算當下 \(\mathbb{W}_t\) 的梯度 \(\nabla E_{in}(\mathbb{W}_t)=\frac{1}{N}\sum\limits_{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\nabla E_{in}(\mathbb{W}_t)\)

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

\(Proof\)

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

\(\therefore \nabla E_{in}(\mathbb{W})\overset{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})\) \(\Longrightarrow\nabla E_{in}(\mathbb{W})=\frac{1}{N}\sum\theta(-y_n\mathbb{W}^T\mathbb{X})\cdot(-y_n\cdot x_{n_i})\overset{let}{=}0\)

在這裡有兩種可能性 :

Case 1 : \(\theta(-y_n\mathbb{W}^T\mathbb{X})=0\ ,\ \forall\mathbb{W}\Longrightarrow y_n\mathbb{W}^T\mathbb{X}\longrightarrow +\infty\Longrightarrow\mathbb{D}\) is linear separable ( \(\because\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\Longrightarrow\) 非線性方程求解困難不可行

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

\(\mathbb{W}_{t+1}=\mathbb{W}_t+\eta'\cdot\nu\)

Gradient Descent 梯度下降6

How to choose \(\eta\) & \(\nu\) ?

Assume \(\left\lVert\nu\right\rVert=1\) and \(\eta'>0\) is small enough

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

( \(\eta'\) : 大小 , \(\nu\) : 方向 , \(\nabla E_{in}(\mathbb{W}_t) : 角度\))

方向 \(\nu\) :

最好的方向是 \(-\nabla E_{in}(\mathbb{W}_t)\) 且 \(\left\lVert\nu\right\rVert=1\)

\(\therefore\nu=-\frac{\nabla E_{in}(\mathbb{W}_t)}{\left\lVert\nabla E_{in}(\mathbb{W}_t)\right\rVert}\)

大小 \(\eta\) :

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

\(\Rightarrow \eta'\varpropto\left\lVert\nabla E_{in}(\mathbb{W}_t)\right\rVert\Rightarrow\eta'=\eta\cdot\left\lVert\nabla E_{in}(\mathbb{W}_t)\right\rVert\)

\(PS: \eta'\) 隨著迭代不斷更動，但更動"固定"比例為 \(\eta\)

綜合上述 :

\(\mathbb{W}_{t+1}\leftarrow\mathbb{W}_t+\eta'\cdot\nu\Longrightarrow\mathbb{W}_{t+1}\leftarrow\mathbb{W}_t+\eta'\cdot-\frac{\nabla E_{in}(\mathbb{W}_t)}{\left\lVert\nabla E_{in}(\mathbb{W}_t)\right\rVert}\Longrightarrow\mathbb{W}_{t+1}\leftarrow\mathbb{W}_t-\eta\cdot\nabla E_{in}(\mathbb{W}_t)\)

註釋

\(\because\mathbb{H}\mathbb{Y}=\hat{\mathbb{Y}}\Longrightarrow\mathbb{H}\) transform \(\mathbb{Y}\) to \(\hat{\mathbb{Y}}\) \(\because\mathbb{Y}-\hat{\mathbb{Y}}=(\mathbb{I}-\mathbb{H})\mathbb{Y}\Longrightarrow(\mathbb{I}-\mathbb{H})\) transform \(\mathbb{Y}\) to \(\mathbb{Y}-\hat{\mathbb{Y}}\) \(Suppose\ that\ f(\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}\begin{Vmatrix}\mathbb{Y}-\hat{\mathbb{Y}}\end{Vmatrix}^2=\frac{1}{N}\begin{Vmatrix}(\mathbb{I}-\mathbb{H})\cdot Noise\end{Vmatrix}^2=\frac{1}{N}(N-(d+1))\begin{Vmatrix}Noise\end{Vmatrix}^2\) ( \(\because\begin{Vmatrix}\mathbb{I}-\mathbb{H}\end{Vmatrix}^2=tr(\mathbb{I}-\mathbb{H})=tr(\mathbb{I})-tr(\mathbb{H})=N-(d+1)\) ) \(\Longrightarrow\overline{E_{in}}=\underset{\mathbb{D}\overset{i.i.d}{\sim}\mathbb{P}}{\mathbb{E}}[E_{in}(\mathbb{W}_{lin}\ w.r.t\ \mathbb{D})]=noise\ level\cdot(1-\frac{d+1}{N})\) 同理可證 : \(\overline{E_{out}}=noise\ level\cdot(1+\frac{d+1}{N})\)

\(g=\arg\max\limits_{\forall h}( likelyhood(h) )\) \(\Leftrightarrow g=\arg\max\limits_{\forall\mathbb{W}}(\prod_{n=1}^{N}\theta(y_n\mathbb{W}^T\mathbb{X}))\) \(\Leftrightarrow g=\arg\max\limits_{\forall\mathbb{W}}(\ln\prod_{n=1}^{N}\theta(y_n\mathbb{W}^T\mathbb{X}))\) \(\Leftrightarrow g=\arg\min\limits_{\forall\mathbb{W}}(\frac{1}{N}\sum\limits_{n=1}^{N}-\ln\theta(y_n\mathbb{W}^T\mathbb{X}))\) \(=\arg\min\limits_{\forall\mathbb{W}}(\frac{1}{N}\sum\limits_{n=1}^{N}-\ln(1+e^{(-y_n\mathbb{W}^T\mathbb{X})})^{-1})\) \(\begin{matrix}=\arg\min\limits_{\forall\mathbb{W}}(\underbrace{\frac{1}{N}\sum\limits_{n=1}^{N}\ln(1+e^{(-y_n\mathbb{W}^T\mathbb{X})})})\\cross-entropy\ error\end{matrix}\)

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

  2. 擬反矩陣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\)↩︎

  3. 廣義反矩陣在數學上的應用之一便是用來求出最小平方法之解 \(Assume\ \min\parallel AX-Y\parallel_2\ ,\ then\ X=A^\dagger Y+(I-A^\dagger A)w\ ,\ where\ w\ is\ arbitrary\ vector\)↩︎

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

  5. Cross-Entropy \(f(\mathbb{X})=\mathbb{P}(+1\mid\mathbb{X})\iff\mathbb{P}(\mathbb{Y}\mid\mathbb{X})=\begin{cases}f(\mathbb{X})&y=+1\\1-f(\mathbb{X})&y=-1\end{cases}\) \(\Longrightarrow\prod_{n=1}^{N}\mathbb{P}(\mathbb{X}_n)\mathbb{P}(y_n\mid\mathbb{X}_n)\) \(\Longrightarrow\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\max\limits_{\forall h}(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})\ and\ 1-\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 梯度下降 一文↩︎