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。