---
# System prepended metadata

title: Ch10 Logistic Regression
tags: [機器學習基石下：方法篇]

---

---
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
![](https://i.imgur.com/xK7lnWd.png)
- 我們之前說，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
![](https://i.imgur.com/lDyJCsf.png)
- 既然我想要輸出 $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
![](https://i.imgur.com/hs3OSk4.png)
- score $s=\sum_\limits{i=0}^d w_ix_i$
- logistic function $\theta(s)$
    - 把分數轉化成機率
    - 符號居然是 $\theta$！！！
- logistic hypothesis $h(x)=\theta(w^Tx)$


### Logistic Function
![](https://i.imgur.com/7eciTqA.png)
- $\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
![](https://i.imgur.com/X65lnVm.png)


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


### Three Linear Models
![](https://i.imgur.com/WgraR47.png)
- 前面說過，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
<!-- ![](https://i.imgur.com/ExwjMF2.png) -->
![](https://i.imgur.com/m1lGDki.png)
- 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
<!-- ![](https://i.imgur.com/nE50YYc.png) -->
![](https://i.imgur.com/KBfw1Yq.png)
- 注意 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)$
    - ![](https://i.imgur.com/dvYLqhZ.png)
    - 所以我們的 **$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 長相會比較好看


![](https://i.imgur.com/MqejJS9.png)
- 把 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
![](https://i.imgur.com/aWDWzg3.png)
- 教授建議把圖畫出來
- 個人解法
    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)$
![](https://i.imgur.com/yYsIhnp.png)
- 那麼怎樣才能讓 $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)$
![slide10_24](https://i.imgur.com/uOZ8OdU.png)
- 利用連鎖律，直接解(看 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)$
![](https://i.imgur.com/u1nEId9.png)
- 那是不是像 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
![](https://i.imgur.com/66joUyD.png)
- 只好從 PLA 借一些 idea 來用了
- 回想一下 PLA 的那兩步
- 我們可以簡化成一步


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


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


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

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


### Linear Approximation
![](https://i.imgur.com/THJJCsY.png)
- 但是現在這樣問題還是很難解啊，它對 $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
![](https://i.imgur.com/5gT0FaF.png)
- $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$
![](https://i.imgur.com/e629XVF.png)
- 當你跨很大步，我們 Taylor's Expansion 那個 $\eta$ 已經不適用了 (大段距離非線性)
- 一個可能不錯的方式：坡度大，就用大 $\eta$；坡度小，就用小 $\eta$。



![](https://i.imgur.com/A3l1pm9.png)
- 既然我們希望 $\eta$ 跟 $\|\nabla E_{in}(w_t)\|$ 成正相關，那最後其實會導出
    - $w_{t+1}\leftarrow w_t-\eta\nabla E_{in}(w_t)$
        - 這裡的 $\eta$ 是固定的那個紫色的 $\eta$


### Putting Everything Together
![](https://i.imgur.com/h2IGv5O.png)


### Fun Time: Gradient Descent
![](https://i.imgur.com/kfMftbd.png)
- 注意 $w_0=0$


### Summary
![](https://i.imgur.com/Xl8N8Qj.png)
