#Lecture 5: Logistic Regression

#Step 1: Function Set

上一張提到分類問題，我們把這問題以機率模型解決：

$$y= \left\{ \begin{array}{c} C_1,\space P_{w,b}(C_1|x)\geq0.5 \\ C_2,\space Otherwise\space\space\space\space\space\space\space\space\space \end{array} \right.$$

根據重重推導，我們發現此機率可被簡化為sigmoid function：

$$P_{w,b}(C_1|x)=\sigma{(z)}$$

此sigmoid function的變數z為一線性模型：

$$z=w\cdot x+b=\sum_iw_ix_i+b$$

當我們使用不同的w, b參數，就會得到不同的後驗機率。假設我們觀察到事件x，其在所有不同w, b參數下，發現為 $C_1$ 類別的機率，可以形成一個function set：

$$f_{w,b}(x)=P_{w,b}(C_1|x)\space where\space w,b\in\real$$

以圖形化來看，會長這樣：

訓練這模型的過程，可以被稱為Logistic Regression

#Step 2: Goodness of a Function

#Assumption and Derivation

Traning Data會有Class 1的資料，也會有Class 2的資料：

假設這些資料都在某高斯場產生，而每筆資料在這高斯場發生的機率為：

$$f_{w,b}(x)=P_{w,b}(C_1|x)$$

對於某組給定的w和b，全部資料在此高斯場發生的可能性為：

$$L(w,b)=f_{w,b}(x^1)f_{w,b}(x^2)(1-f_{w,b}(x^3))\cdot......\cdot f_{w,b}(x^N)$$

令發生在可能性最高的高斯場，其參數為 $w^*,b^*$：

$$w^*,b^*=\arg{\max_{w,b}{L(w,b)}}= \arg{\min_{w,b}{-\ln{L(w,b)}}}$$

可以發現上述數學式將取max換成取min，所以多加了負號。然後再對L取natural log，這對結果不影響，所以左右兩式的等號成立，但可以從連乘變為連加，使得計算更簡易。對於L取natural log，可以再進一步推導：

$$-\ln{L(w,b)}=-\ln{f_{w,b}(x^1)} -\ln{f_{w,b}(x^2)} -\ln{(1-f_{w,b}(x^3))}+......$$

這裡可以發現，因為不是所有資料都是Class 1的，所以屬於Class 2的項都要以 $1-f_{w,b}$ 來表示。資料類別的不確定性，導致 $-\ln{L(w,b)}$ 的數學式推導不能以連加來公式化，因此這裡引進了delta function的概念：

$$\hat{y}^n=\left\{ \begin{array}{c} 1,\space for\space class\space1 \\ 0,\space for\space class\space2 \end{array} \right.$$

把 $-\ln{L(w,b)}$ 裡的所有項以 $\hat{y}^n$ 的線性組合表示：

$$-\ln{L(w,b)}=-[\hat{y}^1\ln{f(x^1)}+(1-\hat y^1)\ln{(1-f(x^1))}] \\ -[\hat{y}^2\ln{f(x^2)}+(1-\hat y^2)\ln{(1-f(x^2))}] \\ -[\hat{y}^3\ln{f(x^3)}+(1-\hat y^3)\ln{(1-f(x^3))}] +......$$

這下就可以用sigma整理：

$$-\ln{L(w,b)}=\sum_n{ -[\hat{y^n}\ln{f_{w,b}(x^n)} +(1-\hat{y}^n)\ln{(1-f_{w,b}(x^n))} ] }$$

仔細發現的話，其實這數學式是兩個Bernoulli distribution之間的Cross entropy：

Distribution p ;

$$p(x=1)=\hat{y}^n \\ p(x=0)=1-\hat{y}^n$$

Distribution q :

$$q(x=1)=f(x^n) \\ q(x=0)=1-f(x^n)$$

而 $-\ln{L(w,b)}$ 其實就是兩個分布的交叉熵 $H(p,q)$：

$$-\ln{L(w,b)}=H(p,q)=-\sum_x{p(x)\ln{(q(x))}}$$

#Conclution

定義交叉熵函數 $C(f(x^n),\hat{y}^n)$ 為：

$$C(f(x^n),\hat{y}^n)=-[\hat{y}^n\ln{f(x^n)}+(1-\hat{y}^n)\ln{(1-f(x^n))}]$$

當Training data為 $(x^n,\hat{y}^n)$ 時，因為cross entropy的意義在於兩分佈有多接近，若兩分佈一模一樣的話，則cross entropy為極小值。在logistic regression中，Loss function就是所有資料的likelihood與 $\hat{y}^n$的交叉熵總和：

$$L(f)=\sum_n{C(f(x^n),\hat{y}^n)}$$

#Step 3: Find the best function

#Preview

$$f_{w,b}(x)=\sigma{(z)}=\frac{1}{1+\exp{(-z)}}$$ $$z=w\cdot x+b=\sum_i{w_ix_i}+b$$

#Derivation: Find Gradient Descent

求Loss function能有最小loss ⇒ 使用反向梯度，對Loss function求偏導：

$$\frac{\partial (-\ln{L(w,b)})}{\partial w_i} =\frac{\partial\left\{ \sum_n{-[\hat{y}^n\ln{f_{w,b}(x^n)}+(1-\hat{y}^n)\ln{(1-f_{w,b}(x^n))}]} )\right\}}{\partial w_i}$$ $$=\sum_n{ -[ \hat{y}^n \frac{\partial{(\ln{f_{w,b}(x^n)})}}{\partial{w_i}} + (1-\hat{y}^n) \frac{ \partial{( \ln{(1-f_{w,b}(x^n))} )} } {\partial{w_i}} ] }$$

兩個偏導項先分開處理

求前項偏微分推導

$$\frac{ \partial\ln{f_{w,b}(x)} }{\partial{w_i}} = \frac{\partial\ln{f_{w,b}(x)}}{\partial{z}} \frac{\partial{z}}{\partial{w_i}}$$

先處理後項：

$$\frac{\partial{z}}{\partial{w_i}}= \frac{\partial{(w_i\cdot{x_i}+b)}}{\partial{w_i}}=x_i$$

再處理後項：

$$\frac{\partial\ln{f_{w,b}(x)}}{\partial{z}}= \frac{\partial\ln{\sigma(z)}}{\partial{z}}= \frac{1}{\sigma(z)} \frac{\partial{\sigma(z)}}{\partial{z}}= \frac{1}{\sigma(z)} \sigma(z) (1-\sigma(z))= 1-\sigma(z)$$

所以：

$$\frac{ \partial\ln{f_{w,b}(x)} }{\partial{w_i}} = x_i(1-\sigma(z)) = x_i(1-f_{w,b}(x^n))$$

求後項偏微分推導

$$\frac{\partial{\ln{(1-f_{w,b}(x))}}}{\partial{w_i}}= \frac{\partial{\ln{(1-f_{w,b}(x))}}}{\partial{z}} \frac{\partial{z}}{\partial{w_i}}$$

後項已知是 $x_i$，推導前項：

$$\frac{\partial\ln{(1-\sigma{(z)})}}{\partial{z}}= -\frac{1}{1-\sigma{(z)}} \frac{\partial\sigma{(z)}}{\partial{z}}= -\frac{1}{1-\sigma{(z)}} \sigma{(z)}(1-\sigma{(z)})=\sigma{(z)}$$

所以：

$$\frac{\partial{\ln{(1-f_{w,b}(x))}}}{\partial{w_i}}=x_i\sigma{(z)}=x_if_{w,b}(x^n)$$

繼續推導原公式

$$\frac{\partial (-\ln{L(w,b)})}{\partial w_i} =\sum_n{ -[ \hat{y}^n \frac{\partial{(\ln{f_{w,b}(x^n)})}}{\partial{w_i}} + (1-\hat{y}^n) \frac{ \partial{( \ln{(1-f_{w,b}(x^n))} )} } {\partial{w_i}} ] }$$ $$=\sum_n{-[ \hat{y}^n(1-f_{w,b}(x^n))x_i^n- (1-\hat{y}^n)f_{w,b}(x^n)x_i^n ]}$$ $$=\sum_n{-[ \hat{y}^n-\hat{y}^nf_{w,b}(x^n)- f_{w,b}(x^n)+\hat{y}^nf_{w,b}(x^n) ]x_i^n}$$ $$=\sum_n{-( \hat{y}^n-f_{w,b}(x^n) )x^n_i}$$

#Conclution

在每次迭代時，更新的參數為：

$$w_{i+1} \leftarrow w_i-\eta \sum_n{-( \hat{y}^n-f_{w,b}(x^n) )x^n_i}$$

從這可以看出w的update取決於三件事：

• Learning Rate $\eta$
• $x_i$ from the data
• $\hat{y}^n$ the ideal output
  • 所以 $( \hat{y}^n-f_{w,b}(x^n) )$ 代表目前f的output與理想值的差距，當這差距越大， $w_i$ 更新的幅度越大

#Logistic Regression v.s. Linear Regression

Logistic Regression

• Model:

  Output: between 0 and 1

  $$f_{w,b}(x)=\sigma{( \sum_iw_ix_i+b )}$$

• Loss function:

  $\hat{y}^n$: 1 for class 1, 0 for class 2

  $$L(f)=\sum_nC(f(x^n),\hat{y}^n)$$

• Iteration:

  $$w_{i+1} \leftarrow w_i-\eta\sum_n-(\hat{y}^n-f_{w,b}(x^n))x^n_i$$

Linear Regression

• Model:

  Output: any value

  $$f_{w,b}(x)= \sum_iw_ix_i+b$$

• Loss function:

  $\hat{y}^n$: a real number

$$L(f)=\frac{1}{2}\sum_n(f(x^n)-\hat{y}^n)^2$$

• Iteration:

  $$w_{i+1} \leftarrow w_i-\eta\sum_n-(\hat{y}^n-f_{w,b}(x^n))x^n_i$$

#Why not Square Error?

雖然像linear regression的loss function那樣使用square error很方便、推導簡單，但是套用在logistic regression就不適合了。

從下圖可以看到在loss function較大時，使用交叉熵可以更反映某點在較大值時與最低點的陡斜程度，所以在每次迭代時可以更快找到最低點；如果使用square error的話，就會太過平坦了，在找最低點的速度就會極緩慢。

#Discriminative v.s. Generative

後驗機率的公式，如果從不同角度切入，就會得到不同意義的結果，左半圖為Discriminative Model，右圖為Generative Model：

兩個Model的function set其實是一樣的，但兩個模型做了不同假設，所以同一組taining data得出的結果會不一樣。

• Discriminative Model：直接學習「輸入x屬於哪個類別y」的邊界或機率。
  • 使用迭代，直接學習decision boundary
  • 在數學上學的是「在已知特徵x的情況下，屬於類別y的機率」、「不會去建模 x 的分布」 $P(y|x)$
  • 只根據已知的 x 特徵，直接學習如何分類（或判斷 y），不對 x 的機率分布做任何假設
  • 不關心每一類的樣本長什麼樣，只管怎麼把不同類分開，像是面試官，直接判斷你「該不該錄取」
  • 常見例子：Logistic Regression、SVM、Neural Network
• Generative Model：學習「每個類別下，數據會長什麼樣」以及「每個類別本身的比例」。
  • 算出Gaussion的 $\mu,\Sigma$，估計每個類別下的參數
  • 在數學上學的是「給定類別Y，數據x出現的機率，還有每個類別本身的機率」、「主動建模每個類別下 x 的分布」($P(x|y),P(y)$)
  • 先針對每一類型 y，估計 x 的機率分布（如 Gaussian 的 $\mu,\Sigma$ ），然後再根據這些分布來分類或生成樣本
  • 關心每一類樣本的分布、特徵，像是專門分析各個公司的履歷特徵，知道各種背景的人大致長什麼樣子，再來算你比較像哪一種人
  • 常見例子：Naive Bayes、Guassion Mixture Model、Hidden Markov Model、GAN

#Example

有13組訓練資料，每組資料都有兩個dimention的元素，元素可能為1或0，每組資料的類別如下：

現在有一組測試資料，資料裡的兩個dimention值都是1，求此資料的類別可能會是？

Solve the problem

假設使用Generative Model，且每組資料的每個dimention都是獨立關係，因此挑選其資料分布為Naive Bayes：

$$P(x|C_i)=P(x_1|C_i)P(x_2|C_i)$$

計算每個類別的參數：

$$P(C_1)=\frac{1}{13}$$ $$P(C_2)=\frac{12}{13}$$

因為測試資料的兩個dimention都是1，設資料的第i個dimention為 $x_i$，所以只要算從某類別抽出的 $x_i$ 是1的機率就好：

$$P(x_1|C_1)=1$$ $$P(x_2|C_1)=1$$ $$P(x_1|C_2)=\frac{1}{3}$$ $$P(x_2|C_2)=\frac{1}{3}$$

利用貝式定理求出觀察到某資料的所有dimention為1，其類別可能為 $C_1$ 的機率：

$$P(C_1|x)=\frac{ P(x|C_1)P(C_1) }{ P(x|C_1)P(C_1)+P(x|C_2)P(C_2) }$$ $$=\frac{ \{P(x_1|C_1)P(x_2|C_1)\}P(C_1) }{ \{P(x_1|C_1)P(x_2|C_1)\}P(C_1) + \{P(x_1|C_2)P(x_2|C_2)\}P(C_2) }$$ $$=\frac{ (1\times1)\times\frac{1}{13} }{ (1\times1)\times\frac{1}{13} + (\frac{1}{13}\times\frac{1}{13})\times\frac{12}{13} } = \frac{1}{2029} \ll0.5$$

計算後可以得知此機率非常小，所以此資料為class 2。

#Conclution of the result of the example

但看回訓練資料，可以發現Class 2的所有資料完全沒有兩個dimention值都是1的情況，所以這結果讓人感覺不是那麼直觀。會這樣是因為，一開始就假設所有dimention都是獨立的，使用了Naive Bayes機率分布模型描述資料。所以generative model就根據這假設，在參考所有類別的可能性後，自己腦補了結果，使得結果是訓練資料裡沒有被觀察到的現象。

Generative model這種腦補的行為，在訓練資料量不多時，相比Discriminative model能有較佳的結果。

• Benefit of generative model
  • 由於確定了機率分布的假設，使得訓練資料量可以不用很多，且比較不會受資料的噪音影響
  • 可以從不同的資料算出先驗機率( Priors probabilities，如： $P(C_1)$ )與類別依賴的機率( Class-dependent Probabilities，如： $P(x|C_1)$ )

但當資料量夠多時Discriminative Model還是比Generative Model來的優。

#Multi-Class Classfication

#Previously on Softmax

在解決多類別的分類問題之前，先介紹一下Softmax。Softmax在本問題的解法擔任了關鍵的角色，以下為softmax的流程。

• 前提：每個類別樣本的高斯分布都共用同個covariance matrix

• 輸入資料：由n個類別方程式組成的向量

  $$z=\begin{bmatrix} z_1 \\ z_2 \\\vdots\\ z_n \end{bmatrix}$$

• 計算向量中每個參數取自然指數函數的值⇒取得所有值的總和⇒每個參數$y_i$為函數值除以總和

  • $y_i$為機率，是likelihood
  $$y_i=P(C_i|x)=\frac{ e^{z_i} }{ \sum_{j=1}^ne^{z_j} }$$

• 輸出：由 n 個 $y_i$ 組成的向量

  $$y=\begin{bmatrix} y_1 \\ y_2 \\\vdots\\ y_n \end{bmatrix}$$

Softmax輸出向量每個參數都是機率，其特性有：

• $1>y_i>0$
• $\sum_iy_i=1$

#Solve the problem

對於多個類別的分類問題，可以用下面步驟解決：

• 訓練資料的每個類別都會有自己的權重向量與偏移量形成的線性方程。假設輸入資料是個d維的向量 $x=\{x^1,x^2,.....,x^d\}$，總共有n個類別，則每個類別的方程式為

  $$Class\space1:\space z_1=w_1+b_1 \\ Class\space2:\space z_2=w_2+b_2 \\ \vdots \\ Class\space n:\space z_n=w_n+b_n$$

• 每個方程經過Softmax function運算後得到 $y_i$，而$y_i$就是每個類別的機率 $f_{w,b}(x^n)$

  $$y_1=Softmax(z_1) \\ y_2=Softmax(z_2) \\ \vdots \\ y_n=Softmax(z_n)$$

• 對於所有類別的機率 $y_i$，可以形成向量 $y$

  $$y=\begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}$$

• 有了每個類別的機率，接下就需要每個類別的target，也就是真實答案 $\hat{y}_i$，其實就是delta function的概念

  • 定義 $\hat{y}$ 是個包含所有類別真實答案的vector

    $$\hat{y}=\begin{bmatrix} \hat{y}_1 \\ \hat{y}_2 \\ \vdots \\ \hat{y}_n \end{bmatrix}$$

  • 如果 $x\in Class\space j$，則 $\hat{y}_j = 1$，然後 $\hat{y}_i=0\space\forall\space i\neq j$：

  

• 向量 $y$ 與向量 $\hat{y}$ 的交叉熵就是Loss function

  $$L(y)=-\sum_n\hat{y}_i\ln{y_i}$$

• 最後照著Logistic Regression的方式去minimize cross entropy (=minimize loss function=maximize likelihood)，就可以解決多類別的分類問題

#Limitation of Logistic Regression

#Introduction

因為Logistic Regression的Boundary是一條直線，假設資料的分佈長這樣，則不管boundary在哪裡，都無法完美地分類：

解決方法就是把資料換到另一個space上，以下以範例說明。

#Example

假設有四組資料，每組資料都有兩個特徵：

其方程式為：

$$y=\sigma(z)\space where\space z=w_1x_1+w_2x_2+b$$

在Introduction中，我們可以看到因為boundary為一條直線，而feature的分佈使得這條直線無法完美分類。若要解決此問題，就要將資料換到另一個space，使得：

$$\left\{ \begin{array}{c} Class \space 1, \space y\geq0.5 \\ Class \space 2, \space y\lt0.5 \end{array} \right.$$

而轉換的方法被稱為 Feature Transformation

#Feature Transformation: Cascading logistic regression models

Introduction

有很多種特徵轉換的方法，但比較簡單、常見的做法是串接多個logistice regression模型的加權組合，並產生新的輸出：

上述範例的 $x_1,x_2$ 經過特徵轉換後變成新的 $x_1',x_2'$ ，其轉換方程式為(塗上少了每個特徵的獨立權種與偏移)：

$$\begin{bmatrix} x_1' \\ x_2' \end{bmatrix} = \sigma( \begin{bmatrix} w_{11} & w_{12} \\ w_{21} & w_{22} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \begin{bmatrix} b_1 \\ b_2 \end{bmatrix} )$$

Apply to the example

把特徵轉換套用到範例後，會發現boundary可以完美分類data。

Multi-Level Cascades form a Neural Network

若有多層級的Logistic Regression Cascade，某級Cascade的輸入是上一級Cascade的輸出；輸出是下一級Cascade的輸入。則此級被稱為Neuron，多個Neuron串接在一起，形成的網路被稱為Neural Network