Regression：Case Study

回歸-案例研究

問題的導入：預測寶可夢的CP值

Estimating the Combat Power(CP) of a pokemon after evolution

我們期望根據已有的寶可夢進化前后的信息，來預測某只寶可夢進化后的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，選擇很多，這里采用的是Non-linear Model

設定具體參數

： 表示一只寶可夢，用下標表示該寶可夢的某種屬性

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

： 表示該寶可夢是屬于哪一種物種，比如妙瓜種子、皮卡丘...

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

： 代表該寶可夢的重重量

： 代表該寶可夢的高度

： 表示我們要找的function

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

 

Regression的具體過程

回顧一下machine Learning的三個步驟：

• 定義一個model即function set
• 定義一個goodness of function損失函數去評估該function的好壞
• 找一個最好的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 ( x~i~ is also called feature，即特征值)

w~i~：weight of x~i~

b： bias

 

Step2：Goodness of Function

參數說明

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

：用表示一個實際觀察到的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，將10個估測誤差合起來就是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的樣子如下：

，或者是

也就是那個使最小的或，就是我們要找的或(有點像極大似然估計的思想)

 

利用線性代數的知識，可以解得這個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) 有一個暴力的方法是，窮舉所有的w值，去找到使loss最小的，但是這樣做是沒有效率的；而gradient descent就是用來解決這個效率問題的 * 首先隨機選取一個初始的點 (當然也不一定要隨機選取，如果有辦法可以得到比較接近的表現得比較好的當初始點，可以有效地提高查找的效率) * 計算在的位置的微分，即，幾何意義就是切線的斜率 * 如果切線斜率是negative負的，那么就應該使w變大，即往右踏一步；如果切線斜率是positive正的，那么就應該使w變小，即往左踏一步，每一步的步長step size就是w的改變量 w的改變量step size的大小取決于兩件事 * 一是現在的微分值有多大，微分值越大代表現在在一個越陡峭的地方，那它要移動的距離就越大，反之就越小； * 二是一個常數項η，被稱為==learning rate==，即學習率，它決定了每次踏出的step size不只取決于現在的斜率，還取決于一個事先就定好的數值，如果learning rate比較大，那每踏出一步的時候，參數w更新的幅度就比較大，反之參數更新的幅度就比較小 如果learning rate設置的大一些，那機器學習的速度就會比較快；但是learning rate如果太大，可能就會跳過最合適的global minima的點 * 因此每次參數更新的大小是 η，為了滿足斜率為負時w變大，斜率為正時w變小，應當使原來的w減去更新的數值，即 ηηηη

此時對應的斜率為0，我們找到了一個極小值local minima，這就出現了一個問題，當微分為0的時候，參數就會一直卡在這個點上沒有辦法再更新了，因此通過gradient descent找出來的solution其實并不是最佳解global minima

但幸運的是，在linear regression上，是沒有local minima的，因此可以使用這個方法

 

兩個參數的問題

今天要解決的關于寶可夢的問題，是含有two parameters的問題，即

當然，它本質上處理單個參數的問題是一樣的

• 首先，也是隨機選取兩個初始值，和
• 然后分別計算這個點上，L對w和b的偏微分，即 和
• 更新參數，當迭代跳出時，對應著極小值點 ηηηηηη

實際上，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值與預測值之差的絕對值叫做，而這些誤差之和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可能不是一條直線，可能是稍微更復雜一點的曲線

考慮的model

 

考慮的model

 

考慮的model

 

考慮的model

 

5個model的對比

這5個model的training data的表現：隨著的高次項的增加，對應的average error會不斷地減小；實際上這件事情非常容易解釋，實際上低次的式子是高次的式子的特殊情況(令高次項對應的為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非但不會減小，反而會暴增，在該例中，從含有項的model開始往后的model，testing data上的error出現了大幅增長的現象，通常被稱為overfitting過擬合

 

因此model不是越復雜越好，而是選擇一個最適合的model，在本例中，包含的式子是最適合的model

進一步討論其他參數

物種的影響

之前我們的model只考慮了寶可夢進化前的cp值，這顯然是不對的，除了cp值外，還受到物種的影響

 

因此我們重新設計model：

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

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

 

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

 

Hp值、height值、weight值的影響

考慮所有可能有影響的參數，設計出這個最復雜的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里面所有的的平方和用λ加權(其中i代表遍歷n個training data，j代表遍歷model的每一項)

也就是說，我們期待參數越小甚至接近于0的function，為什么呢？

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

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

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

如果我們有一個比較平滑的function，由于輸出對輸入是不敏感的，測試的時候，一些noises噪聲對這個平滑的function的影響就會比較小，而給我們一個比較好的結果

 

注：這里的λ需要我們手動去調整以取得最好的值

λ值越大代表考慮smooth的那個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就是在該λ下的最佳，即loss最小
• 這里λ的最佳數值是需要通過我們不斷調整來獲取的，因此令λ等于0，10，100，1000，...不斷使用gradient descent或其他算法得到最佳的parameters：，并計算出這組參數確定的function——對training data和testing data上的error值，直到找到那個使testing data的error最小的λ，(這里一開始λ=0，就是沒有使用regularization時的loss function) 注：引入評價的error機制，令error=，分別計算該對training data和testing data(more important)的大小 先設定λ->確定loss function->找到使loss最小的->確定function->計算error->重新設定新的λ重復上述步驟->使testing data上的error最小的λ所對應的所對應的function就是我們能夠找到的最佳的function

本章節總結：

• Pokémon: Original CP and species almost decide the CP after evolution
• There are probably other hidden factors
• Gradient descent More theory and tips in the following lectures
• Overfitting and Regularization
• We finally get average error = 11.1 on the testing data
• How about new data? Larger error? Lower error?(larger->need validation)
• Next lecture: Where does the error come from? More theory about overfitting and regularizationThe concept of validation(用來解決new data的error高于11.1的問題)

附：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過度自信, 非常完美的擬合上了這些數據, 如果具備過擬合的能力, 那么這個方程就可能是一個比較復雜的非線性方程 , 正是因為這里的和使得這條虛線能夠被彎來彎去, 所以整個模型就會特別努力地去學習作用在和上的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表示正規化程度，上面兩式可總結如下：