# 林軒田機器學習基石筆記 - 第九講、第十講
###### tags: `林軒田` `Maching Learning` `機器學習基石`

---

>* **本文為一系列課程之筆記，建議從" [機器學習基石筆記-1](https://hackmd.io/s/ryxzB7LwN) "開始閱讀**
>>
>* **本文討論內容請參考:
機器學習基石第九講 : 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...) ，那麼找出最小值的演算法也同時被確定下來。

##

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

[^1]:可參閱 [機器學習基石筆記-4](https://hackmd.io/s/Sk6y3RMYE)

# 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][^3] $\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}$

[^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$

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}}$ 的一個線性關係。而這樣的一個關係它有一些特別的特性 :
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，因此證明僅放在註釋中 )

[^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$
<br>
2. 
<br>
$\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})$

這兩式指出，只要是從 $\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](https://hackmd.io/s/rJaSpwpFV) 內談到的 "翻轉"機率 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]

[^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)$<br>
$\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)<br>
我們希望我們的預測 $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))$<br>
$\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))$<br>
$=\prod_{y_n=+1}\mathbb{P}(\mathbb{X}_n)h(\mathbb{X}_n)\prod_{y_m=-1}\mathbb{P}(\mathbb{X}_m)$<font color="#dd0000">$(-h(\mathbb{X}_m))$</font>
$( \because h(\mathbb{X})=\theta(\mathbb{W}^T\mathbb{X})\ and\ 1-\theta(s)=-\theta(s) )$<br>
$\propto\prod_{n=1}^{N}h(y_n\mathbb{X}_n)=\prod_{n=1}^{N}\theta(y_n\mathbb{W}^T\mathbb{X})$
<br>
$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}$


挑選一個初始值 $\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}$<br>
$=\frac{1}{N}\sum\frac{1}{A}\cdot e^B\cdot(-y_n\cdot x_{n_i})$<br>
$=\frac{1}{N}\sum\frac{e^B}{1+e^B}\cdot(-y_n\cdot x_{n_i})$<br>
$=\frac{1}{N}\sum\theta(B)\cdot(-y_n\cdot x_{n_i})$<br>
$\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]
[^6]: 有關於梯度下降法的更詳細討論可以參閱 [Gradient descent 梯度下降](https://hackmd.io/s/ryQypiDK4) 一文

### 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)$