Deep Learning 筆記3 - LR Gradient Descent

Minimize cost function J(w,b)

我們上次說LR採用的single point error function L會使得whole training set的cost function J 在feature space形成一個有global minimum的convex:

所以這樣可以利用gradient descent 演算法來找出此global minimum，就可以找出(w,b)的最佳解。

注意通常weight vector w的dimension會 >> 1，所以上圖是最簡單的例子，假設|w| = 1。

Gradient Descent

我們可以從任何一個(w,b)的點開始，gradient descent確保我們下一個前進的方向是下降幅度最快的方向(所以稱為deepest/gradient descenet)，詳見此篇的解釋。

簡化來看，假設ignore b，所以feature space是一維的只有w:

gradient descent algorithm就只是一直在update w的值 (位置)而已:

所以w一直透過減去 alpha * J在w的瞬間變化量(代號dw)，此alpha稱為learning rate。
dw = J在w的切線斜率，如果dw為正，則w往小的地方前進:

反之如果切線斜率為負，w往大的地方前進:

所以對這個極度簡化的1-D weight vector來說，gradient descent會讓 w往J(w)為global minimum的方向前進，這個結論可以generalized到high dimensionality  weight vector & b:

注意上面兩個w, b vector要同時update來找出J(w,b)的global minimum。上面牽涉到了partial derivative。

Computation Graph

如果有以下的function J ，在計算上可以拆解成三個部分:

按照計算順序可畫出一個computation graph:

要計算出J(a,b,c)，graph流動方向是左到右，稱為forward computation。
如果要計算derivatives of J，則是從右到左，稱為 backward computation。

Backward computation of derivatives

所以我們有上圖這個computation graph:

如何計算dJ/dv ?  dJ/dv 的意義是如果v改變了趨近於無限小的量，J改變了多少?
在最右邊的node說明了J和v的關係，也就是J的改變量 = 3倍的v的改變量:

也就是dJ/dv = 3
我們在計算derivative of J(a,b,c)的back computation過程中，已經完成了第一步。

再來要問dJ/da? 因為function v = a+u，所以解析出J和a的關係會是第二步。
其實這很好推理，因為a的改變量會造成一樣大小的v的改變量，而v的改變量會造成3倍的J的改變量，所以a的改變量也會造成3倍的J的改變量，也就是dJ/da = 3:

在微積分中，這稱為chain rule:

所以我們現在完成了backward computation的第二步:

事實上我們也完成了 dJ/du，因為跟dJ/da 的分析邏輯一模一樣，所以dJ/du = 3

第三步要算出 dJ/db = dJ/dv * dv/du * du/db = 3 * 1 * du/db。
du/db相當於就是把c看成常數去微分，所以du/db = c， dJ/db = 3c = 6。
同理 dJ/dc = 3b = 9。

Gradient Descent on single training example in Logistic Regression

複習一下logistic regression，對一個single input vector x = (x1,x2)來說:

如果寫成computation graph:

為了要進行gradient descent，我們需要計算derivatives of
dL/dw1
dL/dw2
dL/db

，我們仍然採用backward computation:
1. 先算出 dL/da，我們直接做偏微分就好:

2. 再來算dL/dz 
= dL/da * da/dz  //用到chain rule

dL/da第一步驟已經算出來了，
da/dz 要把a = sigmoid(z) 寫出來:

答案是 a(1-a)，為什麼? 我不懂 XD

所以 dL/dz 為以下兩者相乘:

答案是 a-y


3. 最後要來算我們的目標:
dL/dw1 = dL/dz * dz/dw1 = (a-y) * x1
dL/dw2 = dL/dz * dz/dw2 = (a-y) * x2
dL/db = dL/dz * dz/db = (a-y)



所以在這個例子中，我們的gradient descent algorithm每個iteration update (w1, w2, b):

上面式子中的dw1, dw2, db 代號其實代表了 dL/dw1, dL/dw2, dL/db

Gradient Descent on m training examples in Logistic Regression

複習一下cost function J其實是 所有training example的error function的平均:

這個J function才是我們真正要optimize的，所以gradient descent要apply在這個J function上。
所以要怎麼找出derivatives of J with respect to vector w and b?

上面的式子兩邊都取偏微分的話，等式仍然成立:

上一節中已經說明怎麼計算任意 sample (xi,yi) 的 dL/dw，白話文就是Loss function在(xi,yi)時的在feature space (w1,w2, ... , b)中下降速度最快的方向vector。

每一個iteration算出J(w,b)的gradient演算法如下 (事實上下面會有一個inner for loop 1~n):

當然每個iteration也要update w,b才能做descent :

Vectorization

上面的gradient descent (single iteration)演算法內含了兩個for loops，這是performance硬傷，我們需要善用平行化運算，其中一個方法稱為data parallelism，也就是把data vectorize。

Deep Learning 筆記2 - Logistic Regression

Logistic Regression for Binary Classification

LR是用來做二元分類的，例如判斷一張影像中的動物是貓或不是貓。假設有一張影像64x64大小，則以RGB 3個channel來說的話，總共有64x64x3 = 12288個數值，如果把這12288個數值當成feature vector的話(1D)，定義 feature vector維度 = n = nx = 12288 :

Notation

ML的課很容易被數學符號搞混，先說明以下符號是本課程使用:
首先對classification來說，input x一定是一個nx維度的vector，而output y不是1就是0:

training sample 會是一個pair (x, y)，每個data set總共有m個training samples

如果把所有m個training samples x(1) x(2) 依照column順序放入matrix X的話，會形成一個 m by nx matrix:

記住為了之後programming方便起見，不要把xi 弄成row vector放入X。
所以所有的training samples中的label y(1) y(2) ... 也可以變成一個1 by m的matrix Y:

Logistic Regression

這個之前的筆記都有了，簡單來說，就是一個input vector x，LR希望能吐出一個對class的預測y hat，但是是一個機率:

logistic regression簡單來說就是linear regression經過sigmoid function mapping之後，會落在[0,1]區間內，符合機率定義:

sigmoid function的圖如上，所以可以知道z在趨近無限大和無限小時候，會趨近於1和0:

這門課Andrew Ng不使用把bias b編寫成W0=1的notation，因為他說在programming的時候，最方便還是把bias和W分開來最好。

Logistic Regression Loss (Error) Function L

要train出w vector和bias b，我們需要知道LR對training example的預測y hat成效如何?
定義loss (error) function為單一sample x的預測值y hat和label值y 的預測誤差

一個可能的error function為squared difference:

不過由於之後要用gradient descent的演算法來找出cost function J的global minimum，而error function 使用squared difference的話會造成J形成曲折的幾何型態，會有多個local minimums，所以在LR中不予採用。

LR採用的error function如下:

採用上面這個function算是不難理解其效用，因為當:

label y = 1，則後項為零，前項要最小化的話，則log(y hat)必須要最大化，意即y hat要最大化，而y hat最大化為1，因為sigmoid function的關係，所以這邊的直覺就是當y = 1，我們希望y hat也趨近於1。

同理label y = 0的時候，上面的error function希望最小化-log(1 - y_hat)，這會簡化成要最小化y hat，也就是希望y hat趨近於0。

Logistic Regression Cost Function J

Cost function定義為整個training set要找出最佳weight vector w和bias b所需要minimize的 function，合理的定義就是整個training set的平均loss:

LR 可以視為很簡單的一種NN。

Deep Learning 筆記1 - 什麼是Deep Learning?

什麼是Neural Networks?

假設有以下的data，我們如果用某個function來fit這個dataset (例如linear regression)，這個function可以說就是一個最簡單的neural network (事實上這個藍色的線代表的function叫做rectified linear unit, ReLu):

我們把size資訊丟進去一個neuron，最後吐出一個price prediction:

所以neuron代表的就是一個function。

如果考慮更多input feature的話，一個較大型的neural network就會出現了:

我們在training的時候只要提供input x和label y，中間的features或weights演算法會幫我們完成。我們要implement的neural network事實上是每個中間layer (hidden layer)的node都連接所有的input value:

Applications

Structured Data vs Unstructured Data

structured data就是某些數字量化的，跟要預測事務有相關性的data，例如年齡, 價錢, ...

Unstructured data通常是某個整體性instance的呈現，例如一張圖的pixels，或是一段錄音檔的震幅，或是一篇文字，這樣的raw data還不知道如何抽出量化的資訊者 (patterns):

為何Neural networks近年來快速發展？
由於data變多了，以及有更好演算法能力train更大型的NN，兩者都是NN會比傳統ML例如svm / logistic regression好的原因：

由上圖可以看出，當x軸 (m = number of training data)增加時，傳統ML方法（紅線）並無法提升performance，而NN可以exploit big data，而且performance隨著NN的scale成長。但是在small data領域，則傳統ML不輸給NN，所以取決於feature engineering等技巧。

另一個推進NN的動力是硬體計算能力大幅提升，因為training NN是一個iterative action:

train的越快，越能改進NN。