# Machine Learning Class2
# **Regression : Case Study**
> **案例 - 預測寶可夢的CP值**
我們期望根據已有的寶可夢進化前後的信息，來預測某隻4寶可夢進化後的cp值的大小

**確定Senario、Task和Model**
++Senario++
首先根據已有的data來確定Senario，我們擁有寶可夢進化前後cp值的這樣一筆數據，input是進化前的寶可夢(包括它的各種屬性)，output是進化後的寶可夢的cp值；因此我們的data是labeled，使用的Senario是Supervised Learning
++Task++
然後根據我們想要function的輸出類型來確定Task，我們預期得到的是寶可夢進化後的cp值，是一個scalar，因此使用的Task是Regression
++Model++
關於Model，選擇很多，這里採用的是Linear & Non-linear Model

**設定具體參數**
***X***：表示一只寶可夢，用下標表示該寶可夢的某種屬性

***X~cp~***：表示該寶可夢進化前的cp值

***X~s~***：表示該寶可夢是屬於哪一種物種，比如妙娃種子、皮卡丘...

***X~hp~***：表示該寶可夢的hp值即生命值是多少

***X~w~***：代表該寶可夢的重重量

***X~h~***：代表該寶可夢的高度

***f()***：表示我們要找的function

***Y***：表示function的output，即寶可夢進化後的cp值，是一個scalar

**回顧一下machine Learning的三個步驟：**
+ Step1 定義一個model即function set
+ Step2 定義一個goodness of function損失函數去評估該function的好壞
+ Step3 找一個最好的function

## ==**Step1：Model (function set)**==

如何選擇一個function的模型呢？畢竟只有確定了模型才能調參。這里沒有明確的思路，只能憑經驗去一種種地試

**Linear Model 線性模型**

y代表進化後的cp值，代表進化前的cp值，w和b代表未知參數，可以是任何數值

根據不同的w和b，可以確定不同的無窮無盡的function，而這個抽象出來的式子就叫做model，是以上這些具體化的function的集合，即function set

實際上這是一種Linear Model，但只考慮了寶可夢進化前的cp值，因而我們可以將其擴展為：

***X~i~***： an attribute of input X ( xi is also called feature，即特征值)

***w~i~***：weight of xi

***b***： bias(偏壓、偏差)

## ==**Step2：Goodness of Function**==

### **參數說明**

***X^i^***：用上標來表示一個完整的object的編號，表示第i只寶可夢(下標表示該object中的component)

***Y^i^***：用表示一個實際觀察到的object輸出，上標為i表示是第i個object

注：由於regression的輸出值是scalar，因此里面並沒有component，只是一個簡單的數值；但是未來如果考慮structured Learning的時候，我們output的object可能是有structured的，所以我們還是會需要用上標下標來表示一個完整的output的object和它包含的component

### **Loss function 損失函數**
為了衡量function set中的某個function的好壞，我們需要一個評估函數，即Loss function，損失函數，簡稱L；loss function是一個function的function


input：a function；
output：how bad/good it is

由於，即f是由b和w決定的，因此input f就等價於input這個f里的b和w，因此Loss function實際上是在++衡量一組參數的好壞++

之前提到的model是由我們自主選擇的，這里的loss function也是，最常用的方法就是采用類似於方差和的形式來衡量參數的好壞，即預測值與真值差的平方和；這裡真正的數值減估測數值的平方，叫做估測誤差，Estimation error，將估測誤差合起來就是loss function

如果越大，說明該function表現得越不好；越小，說明該function表現得越好

### **Loss function可視化**
下圖中是loss function的可視化，該圖中的每一個點都代表一組(w,b)，也就是對應著一個function；而該點的顏色對應著的loss function的結果L(w,b)，它表示該點對應function的表現有多糟糕，顏色越偏紅色代表Loss的數值越大，這個function的表現越不好，越偏藍色代表Loss的數值越小，這個function的表現越好

比如圖中用紅色箭頭標注的點就代表了b=-180 , w=-2對應的function，即
，該點所在的顏色偏向於紅色區域，因此這個function的loss比較大，表現並不好

## ==**Step3：Pick the Best Function**==

我們已經確定了loss function，他可以衡量我們的model里面每一個function的好壞，接下來我們要做的事情就是，從這個function set里面，挑選一個最好的function

挑選最好的function這一件事情，寫成formulation/equation的樣子如下：
，或者是
也就是那個使
最小的f或(w,b)，就是我們要找的f^*^或(w^*^,b^*^)(有點像極大似然估計的思想)
利用線性代數的知識，可以解得這個closed-form solution，但這里採用的是一種更為普遍的方法 —— ++Gradient Descent(梯度下降法)++

### **Gradient Descent 梯度下降**
上面的例子比較簡單，用線性代數的知識就可以解；但是對於更普遍的問題來說，gradient descent的厲害之處在於，++只要是可微分的++，gradient descent都可以拿來處理這個，找到表現比較好的parameters

### **單個參數的問題**
以只帶單個參數w的Loss Function L(w)為例，首先保證是可微的
我們的目標就是找到這個使Loss最小的，實際上就是尋找切線L斜率為0的global minima最小值點(注意，可能存在一些local minima極小值點，其斜率也是0，但Linear沒有local minima)

有一個暴力的方法是，窮舉所有的w值，去找到使loss最小w^*^的，但是這樣做是沒有效率的；而gradient descent就是用來解決這個效率問題的

+ 首先隨機選取一個初始的點w^0^(當然也不一定要隨機選取，如果有辦法可以得到比較接近w^*^的w^0^當初始點，可以有效地提高查找w^*^的效率)
+ 計算L在w=w^0^的位置的微分，即，幾何意義就是切線的斜率
+ 如果切線斜率是negative負的，那麽就應該使w變大，即往右踏一步；如果切線斜率是positive正的，那麽就應該使w變小，即往左踏一步，每一步的步長step size就是w的改變量。而w的改變量step size的大小取決於兩件事
* 一是現在的微分值有多大，微分值越大代表現在在一個越陡峭的地方，那它要移動的距離就越大，反之就越小；
* 二是一個常數項η，被稱為++learning rate，即學習率++，它決定了每次踏出的step size，step size不只取決於現在的斜率，還取決於一個事先就定好的數值，如果learning rate比較大，那每踏出一步的時候，參數w更新的幅度就比較大，反之參數更新的幅度就比較小。
- 如果learning rate設置的大一些，那機器學習的速度就會比較快；但是learning rate如果太大，可能就會跳過最合適的global minima的點
+ 因此每次參數更新的大小是，為了滿足斜率為負時w變大，斜率為正時w變小，應當使原來的w減去更新的數值，即
此時w^i^對應的斜率為0，我們找到了一個極小值local minima，此時出現了一個問題，當微分為0的時候，參數就會一直卡在這個點上沒有辦法再更新了，因此通過gradient descent找出來的solution其實可能不是最佳解global minima
但幸運的是，在linear regression上，是沒有local minima的，因此可以使用這個方法

### **兩個參數的問題**
今天要解決的關於寶可夢的問題，是含有two parameters的問題，即
當然，它本質上與處理單個參數的問題是一樣的

+ 首先，也是隨機選取兩個初始值，w^0^和b^0^
+ 然後分別計算(w^0^,b^0^)這個點上，L對w和b的偏微分，即和
+ 更新參數，當叠代跳出時，(w^i^,b^i^)對應著極小值點

實際上，L 的gradient就是微積分中的那個梯度的概念，即
可視化效果如下：(三維坐標顯示在二維圖像中，loss的值用顏色來表示)

橫坐標是b，縱坐標是w，顏色代表loss的值，越偏藍色表示loss越小，越偏紅色表示loss越大

每次計算得到的梯度gradient，即由和組成的vector向量，就是該等高線的法線方向(對應圖中紅色箭頭的方向)；而的作用就是讓原先的朝著gradient的方向即等高線法線方向前進，其中η(learning rate)的作用是每次更新的跨度(對應圖中紅色箭頭的長度)；經過多次叠代，最終gradient達到極小值點

※這裡兩個方向的η(learning rate)必須保持一致，這樣每次更新坐標的step size是等比例縮放的，保證坐標前進的方向始終和梯度下降的方向一致；否則坐標前進的方向將會发生偏移

### **Gradient Descent的缺點**
gradient descent有一個令人擔心的地方，也就是之前提到的，它每次叠代完畢，尋找到的梯度為0的點必然是極小值點，local minima；卻不一定是最小值點，global minima

這會造成一個問題是說，如果loss function長得比較坑坑窪窪(極小值點比較多)，而每次初始化的取值又是隨機的，這會造成每次gradient descent停下來的位置都可能是不同的極小值點；而且當遇到梯度比較平緩(gradient≈0)的時候，gradient descent也可能會效率低下甚至可能會stuck卡住；也就是說通過這個方法得到的結果，是看人品的
但是！在++Linear++ regression里，loss function實際上是++convex++的，是一個凸函數，是沒有local optimal局部最優解的，他只有一個global minima，visualize出來的圖像就是從里到外一圈一圈包圍起來的橢圓形的等高線(就像前面的等高線圖)，因此隨便選一個起始點，根據gradient descent最終找出來的，都會是同一組參數

# **回到pokemon的問題上來**
## **偏微分的計算**
現在我們來求具體的L對w和b的偏微分

## **How's the results?**
根據gradient descent，我們得到的中最好的參數是b=-188.4, w=2.7

我們需要有一套評估系統來評價我們得到的最後這個function和實際值的誤差error的大小；這里我們將training data里每一只寶可夢進化後的實際cp值與預測值之差的絕對值叫做e^i^，而這些誤差之和Average Error on Training Data為

## **What we really care about is the error on new data (testing data)**

當然我們真正關心的是generalization的case，也就是用這個model去估測新抓到的pokemon，誤差會有多少，這也就是所謂的testing data的誤差；於是又抓了10只新的pokemon，算出來的Average Error on Testing Data為；可見training data里得到的誤差一般是要比testing data要小，這也符合常識

## **How can we do better?**
我們有沒有辦法做得更好呢？這時就需要我們重新去設計model；如果仔細觀察一下上圖的data，就會发現在原先的cp值比較大和比較小的地方，預測值是相當不準的

實際上，從結果來看，最終的function可能不是一條直線，可能是稍微更覆雜一點的曲線

### **考慮(X~cp~)^2^的model**
### **考慮(X~cp~)^3^的model**
### **考慮(X~cp~)^4^的model**
### **考慮(X~cp~)^5^的model**

### **5個model的對比**
這5個model的training data的表現：隨著(X~cp~)^i^高次項的增加，對應的average error會不斷地減小；這件事情非常容易解釋，實際上低次的式子是高次的式子的特殊情況(令高次項(X~cp~)^i^對應的w~i~為0，高次式就轉化成低次式)

也就是說，在gradient descent可以找到best function的前提下(多次式為Non-linear model，存在local optimal局部最優解，gradient descent不一定能找到global minima)，function所包含的項的次數越高，越覆雜，error在training data上的表現就會越來越小；但是，我們關心的不是model在training data上的error表現，而是model在testing data上的error表現

在training data上，model越覆雜，error就會越低；但是在testing data上，model覆雜到一定程度之後，error非但不會減小，反而會暴增，在該例中，從含有(X~cp~)^4^項的model開始往後的model，testing data上的error出現了大幅增長的現象，通常被稱為++overfitting過擬合++

因此model不是越覆雜越好，而是選擇一個最適合的model，在本例中，包含(X~cp~)^3^的式子是最適合的model

## **進一步討論其他參數**
### **物種X~s~的影響**
之前我們的model只考慮了寶可夢進化前的cp值，這顯然是不對的，除了cp值外，還受到物種X~s~的影響
因此我們重新設計model：


也就是根據不同的物種，設計不同的linear model(這裡)，那如何將上面的四個if語句合並成一個linear model呢？

這裡引入δ(條件表達式)的概念，當條件表達式為true，則δ為1；當條件表達式為false，則δ為0，因此可以通過下圖的方式，將4個if語句轉化成同一個linear model

有了上面這個model以後，我們分別得到了在training data和testing data上測試的結果：

### **Hp值X~hp~、height值X~h~、weight值X~w~的影響**
考慮所有可能有影響的參數，設計出這個最覆雜的model：


算出的training error=1.9，但是，testing error=102.3！這麽覆雜的model很大概率會发生overfitting(按照我的理解，overfitting實際上是我們多使用了一些input的變量或是變量的高次項使曲線跟training data擬合的更好，但不幸的是這些項並不是實際情況下被使用的，於是這個model在testing data上會表現得很糟糕)，overfitting就相當於是那個範圍更大的文氏圖，它包含了更多的函數更大的範圍，代價就是在準確度上表現得更糟糕

## regularization解決overfitting(L2正則化解決過擬合問題)
regularization可以使曲線變得更加smooth，training data上的error變大，但是testing data上的error變小。有關regularization的具體原理說明詳見下一部分

原來的loss function只考慮了prediction的error，即；而regularization則是在原來的loss function的基礎上加上了一項，就是把這個model裡面所有的w~i~的平方和用λ加權(其中i代表遍歷n個training data，j代表遍歷model的每一項)

也就是說，我們++期待參數w~i~越小甚至接近於0的function++，為什麽呢？

因為參數值接近0的function，是比較平滑的；所謂的平滑的意思是，當今天的輸入有變化的時候，output對輸入的變化是比較不敏感的

舉例來說，對這個model，當input變化，output的變化就是，也就是說，如果越小越接近0的話，輸出對輸入就越不sensitive敏感，我們的function就是一個越平滑的function；說到這里你會发現，我們之前沒有把bias——b這個參數考慮進去的原因是bias的大小跟function的平滑程度是沒有關系的，bias值的大小只是把function上下移動而已

那為什麽我們喜歡比較平滑的function呢？

如果我們有一個比較平滑的function，由於輸出對輸入是不敏感的，測試的時候，一些noises噪聲對這個平滑的function的影響就會比較小，而給我們一個比較好的結果
※：這里的λ需要我們手動去調整以取得最好的值

λ值越大代表考慮regularization那一項的影響力越大，我們找到的function就越平滑

觀察下圖可知，當我們的λ越大的時候，在training data上得到的error其實是越大的，但是這件事情是非常合理的，因為當λ越大的時候，我們就越傾向於考慮w的值而越少考慮error的大小；但是有趣的是，雖然在training data上得到的error越大，但是在testing data上得到的error可能會是比較小的

下圖中，當λ從0到100變大的時候，training error不斷變大，testing error反而不斷變小；但是當λ太大的時候(>100)，在testing data上的error就會越來越大


++我們喜歡比較平滑的function，因為它對noise不那麽sensitive；但是我們又不喜歡太平滑的function，因為它就失去了對data擬合的能力++；而function的平滑程度，就需要通過調整λ來決定，就像上圖中，當λ=100時，在testing data上的error最小，因此我們選擇λ=100
※：這里的error指的是

# **Conclusion總結**
**關於pokemon的cp值預測的流程總結：**
+ 根據已有的data特點(labeled data，包含寶可夢及進化後的cp值)，確定使用supervised learning監督學習
+ 根據output的特點(輸出的是scalar數值)，確定使用regression回歸(linear or non-linear)
+ 考慮包括進化前cp值、species、hp等各方面變量屬性以及高次項的影響，我們的model可以採用這些input的一次項和二次型之和的形式，如：
而為了保證function的平滑性，loss function應使用regularization，即，注意bias——參數b對function平滑性無影響，因此不額外再次計入loss function(y的表達式里已包含w、b)
+ 利用gradient descent對regularization版本的loss function進行梯度下降叠代處理，每次叠代都減去L對該參數的微分與learning rate之積。
假設所有參數合成一個vector：，那麽每次梯度下降的表達式如下:
當梯度穩定不變時，即為0時，gradient descent便停止，此時如果采用的model是linear的，那麽vector必然落於global minima處(凸函數)；如果采用的model是Non-linear的，vector可能會落於local minima處(此時需要采取其他辦法獲取最佳的function)
假定我們已經通過各種方法到達了global minima的地方，此時的vector：所確定的那個唯一的function就是在該λ下的最佳f^*^，即loss最小
+ 這里λ的最佳數值是需要通過我們不斷調整來獲取的，因此令λ等於0，10，100，1000，...不斷使用gradient descent或其他算法得到最佳的parameters：，並計算出這組參數確定的function——f^*^對training data和testing data上的error值，直到找到那個使testing data的error最小的λ，(這里一開始λ=0，就是沒有使用regularization時的loss function)
※：引入評價f^*^的error機制，令error=，分別計算該f^*^對training data和testing data(more important)的error(f^*^)大小
>先設定λ->確定loss function->找到使loss最小的->確定function->計算error->重新設定新的λ重覆上述步驟->使testing data上的error最小的λ所對應的所對應的function就是我們能夠找到的最佳的function

# **附：Regularization(L1 L2 正則化解決overfitting)**
>Regularization -> redefine the loss function

關於overfitting的問題，很大程度上是由於曲線為了更好地擬合training data的數據，而引入了更多的高次項，使得曲線更加“蜿蜒曲折”，反而導致了對testing data的誤差更大

回過頭來思考，我們之前衡量model中某個function的好壞所使用的loss function，僅引入了真實值和預測值差值的平方和這一個衡量標準；我們想要避免overfitting過擬合的問題，就要使得高次項對曲線形狀的影響盡可能小，因此我們要在loss function里引入高次項(非線性部分)的衡量標準，也就是將高次項的系數也加權放進loss function中，這樣可以使得訓練出來的model既滿足預測值和真實值的誤差小，又滿足高次項的系數盡可能小而使曲線的形狀比較穩定集中

以下圖為例，如果loss function僅考慮了這一誤差衡量標準，那麽擬合出來的曲線就是紅色虛線部分(過擬合)，而過擬合就是所謂的model對training data過度自信, 非常完美的擬合上了這些數據, 如果具備過擬合的能力, 那麽這個方程就可能是一個比較覆雜的非線性方程 , 正是因為這裡的x^2^和x^3^使得這條虛線能夠被彎來彎去, 所以整個模型就會特別努力地去學習作用在x^2^和x^3^上的c、d參數. 但是在這個例子里，我們期望模型要學到的卻是這條藍色的曲線. 因為它能更有效地概括數據.而且只需要一個就能表達出數據的規律.

或者是說, 藍色的線最開始時, 和紅色線同樣也有c、d兩個參數, 可是最終學出來時, c 和 d 都學成了0, 雖然藍色方程的誤差要比紅色大, 但是概括起數據來還是藍色好


這也是我們通常採用的方法，我們不可能一開始就否定高次項而直接只採用低次線性表達式的model，因為有時候真實數據的確是符合高次項非線性曲線的分布的；而如果一開始直接採用高次非線性表達式的model，就很有可能造成overfitting，在曲線偏折的地方與真實數據的誤差非常大。我們的目標應該是這樣的：

==**在無法確定真實數據分布的情況下，我們盡可能去改變loss function的評價標準**==

+ 我們的model的表達式要盡可能的覆雜，包含盡可能多的參數和盡可能多的高次非線性項；
+ 但是我們的loss function又有能力去控制這條曲線的參數和形狀，使之不會出現overfitting過擬合的現象；
+ 在真實數據滿足高次非線性曲線分布的時候，loss function控制訓練出來的高次項的系數比較大，使得到的曲線比較彎折起伏；
+ 在真實數據滿足低次線性分布的時候，loss function控制訓練出來的高次項的系數比較小甚至等於0，使得到的曲線接近linear分布

那我們如何保證能學出來這樣的參數呢? 這就是 L1 L2 正規化出現的原因.

之前的loss function僅考慮了這一誤差衡量標準，而L1 L2正規化就是在這個loss function的後面多加了一個東西，即model中跟高次項系數有關的表達式；
+ L1正規化即加上這一項，loss function變成，即n個training data里的數據的真實值與預測值差值的平方和加上λ權重下的model表達式中所有項系數的絕對值之和
+ L2正規化即加上這一項，loss function變成，即n個training data里的數據的真實值與預測值差值的平方和加上λ權重下的model表達式中所有項系數的平方和

相對來說，L2要更穩定一些，L1的結果則不那麽穩定，如果用p表示正規化程度，上面兩式可總結如下：