---
tags: 機器學習基石下：方法篇
---

Ch10 Logistic Regression
===

## Content

[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Logistic Regression Problem](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/ll5NR/logistic-regression-problem)

### Heart Attack Prediction Problem: Learning Flow
- 我們之前說，target distribution $P(y|x)$ 會對應到我們的理想的 目標函數 $f(x)$。
- > Q: 我們之前說，target distribution $P(y|x)$ ***(要加上 error function 吧?)*** 會對應到我們的理想的 目標函數 ***(是說 target function $f(x)$ 還是 mini-target ? 若是 mini-target 那前面應該真的要加上 error function)***
<!-- - 後來複習了一點點覺得應該是 target function 啦 -->
- 對 binary classification 來說，$f(x)$ 其實就是去看 target distribution 輸出的哪個結果機率比較大而已
- 就是 target distribution 減去 0.5 去取正負號：$\text{sign}(P(+1|x)-0.5)$
- > Q: 應該是因為 noise 導致的結果機率應該會比較小?
- 那為什麼這樣選擇呢? 道理來自我們在乎的是 classification error (0/1 error 錯誤率)
- > Q: 所以這裡的 ideal target function 就是指 mini-target 沒錯吧！？
- (這裡先省略了 $P(x)$ 那部分的圖以便表達)
- 我們今天可能想要輸出機率 => 'soft' binary classification，也就是我想要輸出 $P(+1|x)$ 本身的話怎麼辦呢?

### Soft Binary Classification
- 既然我想要輸出 $P(+1|x)$，那最理想狀況就是我 label 就有這些 $P(+1|x)$ 的機率，但是我們可能拿不到這種資料，因為我們手上就只有圈圈或叉叉。
- **但是我們可以把手上的圈圈叉叉，看成是我們想要的左邊那種資料的有 noise 的版本。我們得到的圈圈叉叉是左邊那個機率做了一次抽樣之後的結果。**
- 0.9 -> 1 誤差小
- 0.2 -> 0 誤差小
- 0.6 -> 0 誤差大
- **所以當我們有興趣的 target function 是那個 0~1 之間的機率，但手上只有圈圈叉叉的 data 的時候，怎樣才能求得一個好的 hypothesis 呢？**

### Logistic Hypothesis
- score $s=\sum_\limits{i=0}^d w_ix_i$
- logistic function $\theta(s)$
- 把分數轉化成機率
- 符號居然是 $\theta$！！！
- logistic hypothesis $h(x)=\theta(w^Tx)$

### Logistic Function
- $\theta(s)=\dfrac{e^s}{1+e^s}=\dfrac{1}{1+e^{-s}}$
<!-- - 我還是習慣用 $z$ 表示分數啊... $\dfrac{1}{1+e^{-z}}$ 順眼多了 -->

### Fun Time: Logistic Regression & Binary Classification

## [Logistic Regression Error](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/rlkDR/logistic-regression-error)

### Three Linear Models
- 前面說過，target distribution 和 error function 決定了我們想要的 target function 長什麼樣子。
- linear classification 選擇了 0/1 error
- (應該是)因為想要得到 ideal mini-target $f(x)=\arg\max_\limits {y\in\mathcal Y} P(y|x)$
- linear regression 選擇了 squared error
- (應該是)因為想要得到 ideal mini-target $f(x)=\sum_\limits{y\in\mathcal Y}y\cdot P(y|x)$ (就 $y$ 的期望值吧)
- logistic regression?
- **那麼，當我們想要的 target function 是 $P(+1|x)$ 這個機率的時候，應該使用什麼樣的 error function 呢？**

### Likelihood
<!--  -->
- target function $f(x)$ 現在是 $P(+1|x)$
- 產生資料 $x,y$ 的機率 $P(x,y)=P(x)P(y|x)$，用 $f(x)$ 表示的話
- 如果 $y=+1$ 則 $P(x,y)=P(x)f(x)$
- 如果 $y=-1$ 則 $P(x,y)=P(x)(1-f(x))$
- > Q: 第一列那個應該是圈圈?
- 如果今天我們的 $h(x)$ 就是 $f(x)$，那就把 $f$ 換成 $h$ 就好
- 可以想像，既然今天這些資料已經產生出來，那通常來說，$f$ 產生這些資料的機率應該是很大的。也就是說，$h$ 如果跟 $f$ 很接近，那 $h$ 產生 data 的機率也要很高。

### Likelihood of Logistic Hypothesis
<!--  -->
- 注意 Logistic Function 是有對稱性的，這也導致了我們的 $1-h(x)=h(-x)$
- 又 likelihood 可以寫成上圖那個式子，式子中的 $P(x_i)$ 是灰色的因為它和 $h$ 無關，是固定的，所以不是太重要
- 我們把 $1-h(x_i)$ 代換成 $h(-x_i)$，得到 likelihood 就是 $P(x_1)h(+x_1)\times P(x_2)h(-x_2)\times ...P(x_N)h(-x_N)$
- 
- 所以我們的 **$h$ 的可能性 (likelihood)，實際上正比於每筆資料的 $h(y_nx_n)$ 的連乘**
- $\text{likelihood}(h)\propto \prod_\limits{n=1}^N h(y_nx_n)$

### Cross-Entropy Error
- 整理一下，把 $h$ 用 $w$ 來表示，我們可以得到
- $\max_\limits w\text{likelihood}(w)\propto \prod_\limits{n=1}^N \theta(y_nw^Tx_n)$
- 我們不想處理連乘，所以取 log (以 $e$ 為底較好處理) 把它變成連加
- $\max_\limits w \ln\prod_\limits{n=1}^N \theta(y_nw^Tx_n)$
- $\max_\limits w \sum_\limits{n=1}^N \ln\theta(y_nw^Tx_n)$
- 因為我們現在是要推導一個 $E_{in}$ 出來，所以改做 minimize
- $\min_\limits w \frac 1 N\sum_\limits{n=1}^N -\ln\theta(y_nw^Tx_n)$
- 我們加一個不太重要的常數 $\frac 1 N$，這樣等一下的 error 長相會比較好看

- 把 sigmoid function $\theta$ 詳細列出來，就得到這樣的式子
- $\min_\limits w \frac 1 N\sum_\limits{n=1}^N\ln(1+\exp(-y_nw^Tx_n))$
- 這樣終於出現了我們的 $E_{in}(w)$，就是 $\frac 1 N$ 的右邊那坨。
- **而我們相應的 point-wise error measure 也出來了 (在一個 x、一個 y 上就可以衡量)**
- $\text{err}(w,x,y)=\ln(1+\exp(-yw^Tx))$
- **又稱 Cross-Entropy Error**
- > Q: 可能要推導一下為何是 cross entropy
- 原式$=\ln(1+(e^{-s})^y)$
- $=\begin{cases}
\ln(1+e^{-s}), & \text{if}\ y=+1 \\
\ln(1+e^s), & \text{if}\ y=-1
\end{cases}$
- $P_{data}(+1|x)\ln(1+e^{-s})+P_{data}(-1|x)\ln(1+e^{s})$
- $=???$

### Fun Time: Cross-Entropy Error
- 教授建議把圖畫出來
- 個人解法
1. $\ln 1=0$ 所以 $\ln(1+正數)>0$
2. 當 $y$ 和 $w^Tx$ 異號，err 會隨著 $w^Tx$ 變大而無上限地變大
3. 此時 $\exp(-yw^Tx)<1$，所以 $\text{err}<\ln 2$
4. 此時 $\exp(-yw^Tx)\geq 1$，所以 $\text{err}\geq\ln 2$

## [Gradient of Logistic Regression Error](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/Co2BU/gradient-of-logistic-regression-error)

### Minimizing $E_{in}(w)$
- 那麼怎樣才能讓 $E_{in}$ 越小越好呢? 之前我們在解 linear regression 的時候，去求它梯度，然後解梯度是 0 的點。
- 之前講到 linear regression 的函數是平滑的，甚至是 convex 的。
- 什麼是 convex?
- 平滑
- 一次可微
- 二次可微
- 二次微分的矩陣是 positive definite (正定矩陣)
- logistic regression 的 function 也是 convex，所以我們做跟 linear regression 相同的事：求 gradient。
- > Q: 是指 error function 吧

### The Gradient $\nabla E_{in}(w)$
- 利用連鎖律，直接解(看 slide)。
- 解出來 $\dfrac{\partial E_{in}(w)}{\partial w_i}=\frac 1N\sum_\limits{n=1}^N\theta(-y_nw^Tx_n)(-y_nx_{n,i})$
- 因為對每個 $w_i$ 來說，只有橘色部分 $-y_nx_{n,i}$ 會不一樣，所以 $\nabla E_{in}(w)=\frac 1N \sum_\limits{n=1}^N\theta(-y_nw^Tx_n)(-y_nx_n)$
- 注意這是一個向量。

### Minimizing $E_{in}(w)$
- 那是不是像 linear regression 一樣直接解 gradient 等於 0 就好了呢？
- 看式子 $\nabla E_{in}(w)=\frac 1N\sum_\limits{n=1}^N\theta(-y_nw^Tx_n)(-y_nx_n)=0$
- gradient 是 $-y_nx_n$ 的 $\theta$-weighted sum
- 那我們能不能直接把所有 $\theta$-weight 變成 0，即 $\theta(-y_nw^Tx_n)$ 變成 0 就好呢?
- 那代表所有的 $y_nw^Tx_n$ 都要大於 0(其實要無限大)，那 $D$ 必須是 linearly separable 的。
- 那我們只好直接解 gradient = 0 了
- 好難解RRR，它甚至不是一個多項式，$w$ 擺在 exponential 次方，我們似乎沒辦法一步登天解出來。
- **它沒有 closed-form solution。**
- > Q: 要怎麼證明它沒有 closed-form solution?

### PLA Revisited: Iterative Optimization
- 只好從 PLA 借一些 idea 來用了
- 回想一下 PLA 的那兩步
- 我們可以簡化成一步

- 簡化成一步之後，我們可以看成這個式子裡有兩個東西
- $v$：更新的方向
- $\eta$：更新多大步
- 這在 PLA 中固定是 1
- 對 $v$ 和 $\eta$ 做改變就會得到不同的演算法，這種演算法一般我們叫 iterative optimization。
- 下個影片會介紹一個特別的 iterative optimization。

### Fun Time: Gradient of Logistic Regression
- 注意這裡的最小是指很負
- 犯錯的權重會特別大，這跟剛剛 PLA 講說犯錯我們才更新權重很類似
- 所以在 logistic regression 的梯度，某種程度上也是在看我們犯錯的在哪裡。
- 梯度裡面，融合了我對每個 data point 到底犯大錯還是小錯，綜合出來的值。

## [Gradient Descent](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/JZmEA/gradient-descent)

### Iterative Optimization
- 注意我們為了推導簡單起見會把 $v$ 做正規化(讓 $v$ 的 norm 是 1)，讓跟步數大小有關的資訊都保留在 $\eta$ 裡面。
- 想要 $v$ 帶領我們往 $E_{in}$ 最小的地方走，那現在我們使用一個 greedy 的方法，我找一個方向 $v$ 使得走完這一步 $\eta v$ 會讓 $E_{in}$ 最小。

### Linear Approximation
- 但是現在這樣問題還是很難解啊，它對 $v$ 來說還是 non-linear 的，而且還多了 constraint！
- 怎麼簡化問題成 linear 的呢？我們可以說，這個 function 的每一小段其實都是 linear 的
- $E_{in}(w_t+\eta v)\approx E_{in}(w_t)+\eta v^T\nabla E_{in}(w_t)$
- **這樣的 approximation 我們又叫它 (多維的) 泰勒展開式，Taylor expansion**
- 另外既然我們說這是一小段線段，那就代表 $\eta$ 要夠小。

### Gradient Descent
- $E_{in}(w_t)$ 對 $v$ 來說是常數，不用理它
- $\eta$ 是正的常數，不會影響到我們要找的 $v$，也不用理它
- 所以目標就是 $\min_\limits{\|v\|=1} v^T\nabla E_{in}(w_t)$
- 可以看成是 $v$ 和 $\nabla E_{in}(w_t)$ 的內積
- 兩個向量內積怎樣會最小？方向相反，所以 $v=-\dfrac{\nabla E_{in}(w_t)}{\|\nabla E_{in}(w_t)\|}$。
- 除以那個絕對值因為 $v$ 必須是單位向量。
- 所以 gradient descent 就是：
- for small $\eta$, $w_{t+1}\leftarrow w_t-\eta \dfrac{\nabla E_{in}(w_t)}{\|\nabla E_{in}(w_t)\|}$

### Choice of $\eta$
- 當你跨很大步，我們 Taylor's Expansion 那個 $\eta$ 已經不適用了 (大段距離非線性)
- 一個可能不錯的方式：坡度大，就用大 $\eta$；坡度小，就用小 $\eta$。

- 既然我們希望 $\eta$ 跟 $\|\nabla E_{in}(w_t)\|$ 成正相關，那最後其實會導出
- $w_{t+1}\leftarrow w_t-\eta\nabla E_{in}(w_t)$
- 這裡的 $\eta$ 是固定的那個紫色的 $\eta$

### Putting Everything Together

### Fun Time: Gradient Descent
- 注意 $w_0=0$

### Summary