Logistic Regression
Logistic Regression Problem
之前提過的二進制分類器如PLA，其目标函數為， f ( x ) = s i g n ( w T x ) ∈ − 1 , + 1 f(x)=sign(w^Tx)∈{−1,+1} f(x)=sign(wTx)∈−1,+1，輸出要麼是-1要麼是+1，是一個“硬”的分類器。而Logistic Regression是一個“軟”的分類器，它的輸出是y=+1的機率，是以Logistic Regression的目标函數是 f ( x ) = P ( + 1 ∣ x ) ∈ [ 0 , 1 ] f(x)=P(+1|x)∈[0,1] f(x)=P(+1∣x)∈[0,1]。
Logistic Regression use: h ( x ) = 1 1 + e x p ( − w T x ) ∈ [ 0 , 1 ] h(x)=\frac{1}{1+exp(-w^Tx)}∈[0,1] h(x)=1+exp(−wTx)1∈[0,1] 來逼近它的目标函數。
Logistic Regression Error
之前我們講到Linear Regression所使用的平方誤差，那麼Logistic可以使用平方誤差嗎？當然可以，但是使用平方誤差不夠好。
如果使用平方誤差，每個點産生的誤差是：
$
err(h,x_n,y_n) =
\begin{cases}
(\theta(wTx)-(0))2, & y_n=0\
(1-\theta(wTx))2, & y_n=1
\end{cases}\
$
= y n ( 1 − θ ( w T x ) ) 2 + ( 1 − y n ) ( θ ( w T x ) ) 2 =y_n(1-\theta(w^Tx))^2+(1-y_n)(\theta(w^Tx))^2 =yn(1−θ(wTx))2+(1−yn)(θ(wTx))2
此時cost function， E i n ( w ) = ∑ e r r E_{in}(w)=\sum err Ein(w)=∑err就是一個關于w的非凸函數（non-convex）：
非凸函數由于存在很多個局部最小點，是以很難去做最優化。是以我們不使用平方誤差來定義error，而是使用極大似然法來估計模型的參數。那麼我們就要先來了解一下這個似然性（likelihood）。
先介紹一下“似然性”的概念。目标函數 f ( x ) = P ( + 1 ∣ x ) f(x)=P(+1|x) f(x)=P(+1∣x)，如果我們找到了hypothesis很接近target function。也就是說，在所有的Hypothesis集合中找到一個hypothesis與target function最接近，能産生同樣的資料集D，包含y輸出label，則稱這個hypothesis是最大似然likelihood。
Logistic Regression的目标函數的輸出是，在已知x的條件下，y=+1的機率，是以在已知x的條件下，y=+1的機率是f(x)，y=−1的機率是1−f(x):
$
f(x)=P(+1|x)\Leftrightarrow P(y|x)=
\begin{cases}
f(x), &for\ y=+1\
1-f(x) &for\ y=-1
\end{cases}
$
則理想的hypothesis就是能使得似然函數最大的那個h：
g = a r g m a x h l i k e h o o d ( h ) g=argmax_h \ likehood(h) g=argmaxh likehood(h)
當h是logistic函數的時候，即 h ( x ) = θ ( w T x ) h(x)=θ(w^Tx) h(x)=θ(wTx)，由于logistic函數的中心對稱性，有: 1−h(x)=h(−x)
是以：
$
\begin{align}
likelihood(h)&=P(x_1)h(x_1) X P(x_2)(1-h(x_2))X…XP(x_N)(1-h(x_N))\
&=P(x_1)h(x_1) X P(x_2)(h(-x_2))X…XP(x_N)(h(-x_N))\
&=P(x_1)h(x_1) X P(x_2)(h(y_2x_2))X…XP(x_N)(h(y_Nx_N))
\end{align}
$
因為 P ( x n ) P(x_n) P(xn)對所有的n來說是一樣的，是以我們可以忽略它。那麼我們可以得到logistic h正比于所有的 h ( y n ) h(y_n) h(yn)乘積。我們的目标就是讓乘積值最大化。
如果将w帶入的話：
為了把連乘轉換為連加：
然後為了找到最優的解，我們把最大值問題轉換為最小值問題：
将logistic function的表達式帶入，那麼最小化問題就可以轉化為如下形式：
我們把邏輯回歸的誤差函數稱之為交叉熵誤差：
Gradient of Logistic Regression Error
有了誤差函數後，我們就可以定出cost function：
E i n ( w ) = 1 N ∑ n = 1 N l n ( 1 + e x p ( − y n w T x n ) ) E_{in}(w)=\frac{1}{N}\sum^N_{n=1}ln(1+exp(-y_nw^Tx_n)) Ein(w)=N1∑n=1Nln(1+exp(−ynwTxn))
該函數是連續，可微，并且是凸函數
既然是凸函數，我們可以根據之前線性回歸的例子，如果我們能解出一階微分（梯度）為0的點，這個問題就可以解決了。
再把偏微分方程中的 x n , i x_{n,i} xn,i換成向量的形式，就得到了 E i n ( w ) E_{in}(w) Ein(w)的一階微分：
∇ E i n ( w ) = 1 N ∑ n = 1 N θ ( − y n w T x n ) ( − y n x n ) \nabla E_{in}(w)=\frac{1}{N}\sum^N_{n=1}\theta(−y_nw^Tx_n)(−y_nx_n) ∇Ein(w)=N1∑n=1Nθ(−ynwTxn)(−ynxn)
和之前的線性回歸不同，它不是一個線性的式子，要讓 ∇ E i n ( w ) = 0 \nabla E_{in}(w)=0 ∇Ein(w)=0這個式子，是困難的，那麼我們應該如何使之最小化呢？
要讓 θ ( ) \theta() θ()=0的話，隻有 y n w T x n ≫ 0 y_nw^Tx_n\gg0 ynwTxn≫0才行。也就說對于所有的點， y n y_n yn與 w T x n w^Tx_n wTxn都是同号的，這表示資料集D必須是全部線性可分的才能成立。
但是相對來說，保證所有的權重 θ ( − y n w T x n ) \theta(-y_nw^Tx_n) θ(−ynwTxn)為0是不太現實的，總有不等于0的時候，那麼另一種常見的情況是非線性可分，隻能通過使權重和為0，來求解w。這種情況是沒有closed-form解，與Linear Regression不同，隻能用疊代方法求解。
我們嘗試從PLA中找到些許靈感：
w每次更新包含兩個内容：一個是每次更新的方向 y n x n y_nx_n ynxn，用v表示，另一個是每次更新的步長η。參數(v,η)和終止條件決定了我們的疊代優化算法。
Gradient Descent
根據上一小節PLA的思想，那麼：
我們把 E i n ( w ) E_{in}(w) Ein(w)曲線看做是一個山谷的話，要求 E i n ( w ) E_{in}(w) Ein(w)最小，即可比作下山的過程。整個下山過程由兩個因素影響：一個是下山的機關方向v；另外一個是下山的步長η。
利用微分思想和線性近似，假設每次下山我們隻前進一小步，即η很小，那麼根據泰勒Taylor一階展開，可以得到：
E i n ( w t + η v ) ≃ E i n ( w t ) + η v T ∇ E i n ( w t ) E_{in}(w_t+\eta v)\simeq E_{in}(w_t)+\eta v^T\nabla E_{in}(w_t) Ein(wt+ηv)≃Ein(wt)+ηvT∇Ein(wt)
至于泰勒展開（矩陣形式）：
f ( x ) = f ( x k ) + [ ∇ f ( x k ) ] T ( x − x k ) + 1 2 ! [ x − x k ] T H ( x k ) [ x − x k ] + o n f(x)=f(x_k)+[\nabla f(x_k)]^T(x-x_k)+\frac{1}{2!}[x-x_k]^TH(x_k)[x-x_k]+o^n f(x)=f(xk)+[∇f(xk)]T(x−xk)+2!1[x−xk]TH(xk)[x−xk]+on
疊代的目的就是讓 E i n E_{in} Ein越來越小，即讓 E i n ( w t + η v ) < E i n ( w t ) E_{in}(w_t+\eta v)<E_{in}(w_t) Ein(wt+ηv)<Ein(wt)。 η \eta η是标量，因為如果兩個向量方向相反的話，那麼它們的内積最小（為負），也就是說如果方向v與 ∇ E i n ( w t ) \nabla E_{in}(w_t) ∇Ein(wt)反向的話，那麼就能保證每次疊代 E i n ( w t + η v ) < E i n ( w t ) E_{in}(w_t+\eta v)<E_{in}(w_t) Ein(wt+ηv)<Ein(wt)都成立，那麼我們讓 v = ∇ E i n ( w t ) ∣ ∣ ∇ E i n ( w t ) ∣ ∣ v=\frac{\nabla E_{in}(w_t)}{||\nabla E_{in}(w_t)||} v=∣∣∇Ein(wt)∣∣∇Ein(wt).
那麼每次疊代的公式就可以寫出： w t + 1 ← w t − η ∇ E i n ( w t ) ∣ ∣ ∇ E i n ( w t ) ∣ ∣ w_{t+1}\leftarrow w_t-\eta\frac{\nabla E_{in}(w_t)}{||\nabla E_{in}(w_t)||} wt+1←wt−η∣∣∇Ein(wt)∣∣∇Ein(wt)
步長η比較難決定，太小了，更新太慢，太大了，容易矯枉過正:
一個比較好的做法是讓 η \eta η與 ∣ ∣ ∇ E i n ( w t ) ∣ ∣ ||\nabla E_{in}(w_t)|| ∣∣∇Ein(wt)∣∣成一定的比例，讓新的和 ∣ ∣ ∇ E i n ( w t ) ∣ ∣ ||\nabla E_{in}(w_t)|| ∣∣∇Ein(wt)∣∣成比例的 η ′ \eta' η′來代替：
w t + 1 ← w t − η ∇ E i n ( w t ) ∣ ∣ ∇ E i n ( w t ) ∣ ∣ w_{t+1}\leftarrow w_t-\eta\frac{\nabla E_{in}(w_t)}{||\nabla E_{in}(w_t)||} wt+1←wt−η∣∣∇Ein(wt)∣∣∇Ein(wt)
∥ \Vert ∥
w t − η ′ ∇ E i n ( w t ) w_t-\eta' \nabla E_{in}(w_t) wt−η′∇Ein(wt)
我們稱這個 η ′ \eta' η′為fixed learning rate。
整個步驟是這樣的：
initialize w0
for t=0,1,…
1.compute
∇ E i n ( w ) = 1 N ∑ n = 1 N θ ( − y n w T x n ) ( − y n x n ) \nabla E_{in}(w)=\frac{1}{N}\sum_{n=1}^N\theta(-y_nw^Tx_n)(-y_nx_n) ∇Ein(w)=N1∑n=1Nθ(−ynwTxn)(−ynxn)
2.update by
w t − η ∇ E i n ( w t ) w_t-\eta\nabla E_{in}(w_t) wt−η∇Ein(wt)
…until E i n ( w t + 1 ) = 0 E_{in}(w_{t+1})=0 Ein(wt+1)=0 or enough iterations
return last w t + 1 w_{t+1} wt+1 as g.
總結
今天介紹了邏輯回歸。首先指出邏輯回歸将P(+1|x)作為目标函數，将 θ ( w T x ) \theta(w^Tx) θ(wTx)作業hypothesis。接着，我們定義了邏輯回歸的誤差函數，稱之為cross-entropy error交叉熵誤差。然後，我們計算邏輯回歸損失函數的梯度，最後通過梯度下降算法，來逼近最小的 E i n E_{in} Ein。