# Calculus for Machine Learning and Data Science(Week3: Lesson 2 - Newton's Method)
###### tags: `coursera` `Linear Algebra` `math`
[Week3 - Optimization in Neural Networks and Newton's Method](https://www.coursera.org/learn/machine-learning-calculus/home/week/3)

## Newton's Method
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/VXoqj/newtons-method)

課程說明牛頓法

### Newton's Method

原則上，牛頓法是拿來找出函數的零點，不過稍加調整就可以拿來最佳化了。

先來說說什麼是找出函數的零點，假設有一個函數是如上圖的趨勢，我們要找的就是$f(x)=0$的點，以上圖為例就是$x=2$。

首先我們隨機初始一個點$x_0$，然後計算它的切線，把這條切線一路延伸跟跟x軸相交得到$x_1$，然後再得到$f(x_1)$的切線，一樣把這條切線延伸到x軸得到$x_2$，最終我們可以得到$x=2$。
### Update Approximation

剛剛說完觀念，現在以數學來表示，$x_0$的切線斜率就會是$f(x_0)$除$x_0-x_1$，也就是$f'(x_0)=\dfrac{f(x_0)}{x_0-x_1}$，把它拉拉哩拉拉的移一移之後就可以得到$x_1 = x_0 - \dfrac{f(x_0)}{f'(x_0)}$，這就是我們迭代計算的一個基本觀念。
### Update Approximation

總的來看，大概就是這樣的一個計算，總之只要知道$x_k$，那就可以算出$x_{k+1}$

### Newton's Method for Optimization

梯度下降是找出函數的最小值，而牛頓法是找出函數的零值，這實務上可能有點差異。不過我們可以這麼想，如果我們想最小化$g(x)$，那就找出$g'(x)$的零點，如果找的導數的零點，那意義上就很接近是將它最小化。我們只要把所有的解排一排，然後看那一個能得到最佳解就好了。

換句話說，我們假設$f(x)$是$g'(x)$，那求其函數零點的計算就從$f'(x)$變成是$(g'(x))'$，也就是計算其二階導數

:::success
我的理解是，斜率=0的地方通常是最佳解(區域或是全域)，所以目標變成是計算其導數為0的解。
:::

## Newton's Method: An example
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/V1Egr/newtons-method-an-example)

### Newton's Method for Optimization

這個範例是之前說過的，最佳解就是傳說中的歐妹嘎數，0.5671，現在就嚐試利用牛頓法來找出近似解。

我們要做的就是找出其導數的零點。
### Newton's Method for Optimization

當我們要找的是導數的零點的時候，就代表我們的$f'(x)=(g'(x)')'=e^x+\dfrac{1}{x^2}$。

有目標之後就可以開始進行迭代，首先是$x_0=0.05$，帶入公式之後怒算一發得到其值為$0.097$，這也是$x_1$。

### Newton's Method for Optimization

然後就是一直迭代計算，一直算，一直算，得到$x_2=0.183$、$x_3=0.320$、$x_4=0.477$、$x_5=0.558$，最後得到$x_6=567$。

你看，不過就是六次的迭代我們取得近似最佳解。

## The second derivative
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/9XtuI/the-second-derivative)

課程說明二階導數特性以及於最佳化問題中的應用

### Second Derivative

二階導數是我們在推導牛頓法的時候出現的一個名詞，這在最佳化問題中有很大的幫助。

如果是以Leibniz(萊布尼茨)表示的話就是$\dfrac{d^2 f(x))}{dx^2}=\dfrac{d}{dx}\left(\dfrac{df(x)}{dx}\right)$，如果是Largrange的話比較簡單，就$f''(x)$
### Understanding Second Derivative

這是課程介紹導數的第一個範例，假設$x$是行駛的距離，$v$是速度，速度本身距離$x$相對於時間$t$的變化率，也就是$\dfrac{dx}{dt}$。

速度$v$相對於時間$t$的變化率則是加速度，也就是$\dfrac{dv}{dt}=\dfrac{d^2x}{dt^2}$。

當加速度為正值，就代表速度隨著時間增加，負值則代表速度隨著時間降低，如果加速度是零，那就代表定速。
### Understanding Second Derivative

上圖是一個時間跟距離的關係圖，時間跟車速的關係就在下圖。

旅程的開始汽車是靜止狀態的，然後就開始加速一直到一個定速(constant speed)，這時候斜率會隨著時間的推移而變大。假設，這時候的時間與距離的函數為$750t^2$(草綠色線)。很明顯的，第一分鐘的導數就是$1500t$

再來開始上坡了，假設這個坡的函數為$50t-\dfrac{5}{6}$(黃色線)，這個距離是線性的，所以我們可以得到一個常數的時速，也就是$50$。

糟了，出門才發現忘了帶水，只好踩個煞車準備回頭，因為停下來了，所以導數為0(芥茉綠線)，這時候的距離是最高的峰值，因為再來就要準備回家拿東西了。假設這一段的函數表示為$-1500t^2+300t-11.26$，這邊的導數就會是$300-3000t$

好啦，無奈掉回準備回家，回家的函數就是$\dfrac{55}{6}-50t$，這時候的速度，也就是導數就是$-50$
### Understanding Second Derivative

現在我們手上有一個基於距離圖表的速度圖，我們要嚐試利用這個速度圖來找加速度圖。

前兩分鐘我們正起步，速度逐步的上去，導數(加速度)為$1500$，速度上去之後穩穩的在走，導數(加速度)為$0$，接著發現忘了帶水，只好煞車，導數(加速度)為$-3000$，最後要回家，沿路也沒心情踩，所以導數(加速度)為$0$

### Understanding Second Derivative

現在把距離圖與加速度圖放一起，可以看的到距離跟加速度之間的關聯，這也是二階導數所給出的曲線偏離直線的量值。這也稱為curvature(曲率)。

### Curvature

當我們有一個正值的二階導數時，正如第一部份(出門踩下去的那個部份)那個凹上去函數，也稱為convex function(凸函數)。如所見，這種情況下的二階導數為正值，函數會是遞增，因為距離在增加，速度也在增加。

另外中間那邊是相反的，那是一個下凹函數，這種情況下的二階導數會是負值。

剩餘的兩個中間行走區域的二階導數為0，這是不確定的(inconclusive)，所以沒有曲率。

### Curvature

想像一下，上圖左可以是一個笑臉，所以二階導數為正，上圖右可以是一個哭臉，所以二階導數為負。
### Second Derivative and Optimization

那二階導數到底能做什麼？一階導數為0的時候我們並不能確定它到底是最大值還是最小值，但二階導數能告訴我們。

當二階導數大於0的時候，它會是局部最小值，二階導數小於0的時候，它會是局部最大值，二階導數為0的時候並不確定。

### Curvature

總結一階、二階導數帶給我們的訊息。

上圖左說明一階導數的訊息，大於0是增加，小於0是減少。

上圖右說明二階導數的訊息，大於0是微笑函數，小於零是哭哭函數。
## The Hessian
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/KRhHp/the-hessian)

課程說明牛頓法應用於多變數的最佳化求解

### Second Derivative

上表說明著一個變數與兩個變數的函數求導的差異。

一個變數的情況下，就只需要計算該變數對於函數的變化率。

但兩個變數的話就需要分別計算兩個變數對於函數的變化率，放在一起就是梯度，這是個向量。

對於二階導數的話又有那麼一點不一樣。
### Second Derivative

舉例，有個函數$f(x,y)=2x^2+3y^2-xy$，各自計算其導數可以得到：
* w.t.f $x=4x-y$
* $f'_x(x, y) \text{ w.r.t } x$的變化率為4
* $f'_x(x, y) \text{ w.r.t } y$的變化率為-1
* w.t.f $y=6y-x$
* $f'_y(x, y) \text{ w.r.t } x$的變化率為-1
* $f'_y(x, y) \text{ w.r.t } y$的變化率為6

上面最終的四個值就是變化率的變化。有個地方值得注意，就是有兩個$-1$，這是很常發生的事(指一樣的變化率這件事)。
### What Do These Mean?

前面兩個比較單純，就跟一個變數一樣，像$f'_x(x, y) \text{ w.r.t } x$，就是計算對$x$的變化率，$y$也是一樣。這你可以對照上一張簡報的圖會比較有感覺(ex，$f'_x(x, y) \text{ w.r.t } x$的變化率為4)。

然而，後面兩個比較有趣。這是沿著一個坐標軸的斜率相對於沿著正交坐標軸的微小變化的變化，也就是$\Delta{y}$會正交於$x$軸，$\Delta{x}$會正交於$y$軸。

這必需要兩個偏導數都是可微分的狀態才行。只要兩個偏導數都可微，那它們兩個就會是一樣的。

### Notation

以Leibniz寫下來的話就像上面那樣。分子是對同一個函數做二次求導，所以是$\partial^2{f}$，分母的話就根據是那一個變數而有所不同。

Lagrange的話看起來就比較優雅一點。

在大多數情况下，這兩者實際上是相同的。 你需要兩個偏導數都是可微的。當兩個偏導數都是可微的，那麼導數對y的對x的導數與導數對x的對y的導數相同。

在萊布尼茨的記法中，我們可以把它寫成d平方f在dx平方上，d平方x在dy平方上。 對於另外兩個，d在dxdy上求f的平方，d在dydx上求f平方。 拉格朗日記法，我們得到f_xx，f_yy，f_xy和f_yx。 現在，讓我給你們看看Hessian矩陣是什麼。讓我們回到這張圖，我們得到了對x和y的導數，然後是對x和y的偏導數。 當我們把這四個矩陣放在一起時，我們得到了Hessian矩陣。 這裡的Hessian矩陣是4，負1，負1、6
### Hessian Matrix

把我們剛剛的觀念整理一下，四個二階導數的結果放在一個矩陣，這就是Hessian Matrix。這給了我們很多關於二階導數的信息。

### Hessian Matrix - General Case

結論，以符號來表述Hessian Matrix。
### Second Derivative

現在，我們可以把一開始的表格的最後一個二階導數的結果放進去了，答案就是Hessian Matrix。
## Hessians and concavity
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/FS7A3/hessians-and-concavity)

### Remember...

這邊就是回顧一下二階導數的特性觀念，總之，當二階導數是微笑曲線的話，那它是正值，有局部最小值，反之是個哭哭臉的話就是負值，有局部最大值。
### Concave Up

那，兩個變數的函數中所謂的Concave Up是什麼？

舉例函數，$f(x,y)=2x^2+3y^2-xy$，把它畫出來的話就如上圖左那般。它的最小值就在$(0,0)$的地方。它的數學表示方式就要請出Hessian，$H(0,0)=\begin{bmatrix}4 & -1 \\ -1 & 6 \end{bmatrix}$。

如果是在一個變數的情況下，我們只需要確定二階導數是否為正就知道它是否存在最小值。但現在我們所擁有的是一個矩陣，那就需要計算它的eigenvalue，也就是$\det(H(0,0)-\lambda I)$，展開之後就是$\det\left(\begin{bmatrix} 4-\lambda & -1 \\ -1 & 6-\lambda \end{bmatrix}\right)=\lambda^2 - 10\lambda + 23$，求解之後可以得到$\lambda-1=6.41, \lambda_2=3.59$，這兩個eigenvalues都是正數，這意謂著這個矩陣是一個正定(positive definite)的，也就是說，這個函數就會是一個concave up的形狀。
### Concave Down

這邊給出的是concave down的函數範例，$f(x,y)=-2x^2+-3y^2-xy+15$，計算其梯度之後可得其Hessian matrix。然後一樣的計算這個hessian matrix的eigenvalues，最終可得兩個eigenvalues分別為$\lambda_1=-3.59,\lambda_2=-6.41$。

兩個eigenvalues都是負數，這意謂著它是一個concave down函數，也因為兩個eigenvalues都是負數，因此稱為負定(negative definite)。

### Saddle Point

不過要注意，並非所有的矩陣都的eigenvalues都一定是正或者都一定是負。這邊給出一個範例，Saddle Point，鞍點。圖中那個灰灰的點既不是最小值也不是最大值。

一樣的計算它的梯度，然後寫下它的Hessian matrix，然後計算Hessian matrix的eigenvalues，這時候得到的就是$\lambda_1=-4, \lambda_2=4$。跟剛剛的情況完全不一樣，這邊得到的是一正、一負。

### Summary


上表做出總結。總之，如果Hessian matrx的eigenvalues不是全正或是全負的情況，那就是未定情況。

## Newton's Method for two variables
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/RcMDZ/newtons-method-for-two-variables)

課程總結Newton's Method

### Newton's Method

課程一開始提過一個變數的最佳化，$X_{k+1}=x_k-f''(x_k)^{-1}f'(x_k)$，用現在，一階、二階導數來求得下一個迭代。

兩個變數的話就是將二階導數的部份變成Hessian matrix，一階導數的部份則變成梯度。唯一要注意的就是二階導數是倒數，因為是除，所以Hessian matrix也要一樣的處理。

### Newton's Method

這邊一個提醒，不能把梯度跟Hessian matrix的位置調換，因為matrix是2x2，而梯度是2x1，調換後是無法計算的。

### An Example

這邊給出一個範例，$f(x,y)=x^4+0.8y^4+4x^2+2y^2-xy-0.2x^2y$，我們嚐試來找出最小值。

首先計算一階(梯度)、二階導數(Hessian matrix)。

### An Example

然後把它們寫下數學表示。

### An Example

我們從$(4, 4)$做為起始開始計算，帶入公式計算可以很愉快的得到下一個位置$2.58, 2.62$
### An Example

重覆同樣的計算，一直到第八次迭代就可以得到一個接近$(0,0)$的點。