林軒田機器學習基石筆記 - 第九講、第十講
- 本文為一系列課程之筆記，建議從” 機器學習基石筆記-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-inverse^註2 $\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}$
(2)
$\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}}$ 的一個線性關係。而這樣的一個關係它有一些特別的特性 :
- $\mathbb{H}$ is symmetric
- $\mathbb{H}^k=\mathbb{H}$
- $(\mathbb{I}-\mathbb{H})^k=\mathbb{I}-\mathbb{H}$
- $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)$
註釋
[^註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$
$Assume\ \min\parallel AX-Y\parallel_2\ ,\ then\ X=A^\dagger Y+(I-A^\dagger A)w\ ,\ where\ w\ is\ arbitrary\ vector$
$Proof$
$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$
$\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})$
$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})$
$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}$
[^註6]:
有關於梯度下降法的更詳細討論可以參閱 Gradient descent 梯度下降 一文