Skip to content

Lecture 1: Regression - Case Study

Regression: Output a scalar

Regression 的例子舉例有:

  • 道瓊斯指數預測
  • 自動駕駛中的方向盤角度預測
  • 推薦系統中購買可能性的預測

Example Application

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

一隻寶可夢可由 5 個參數表示:

$$x = (x_{cp}, x_s, x_{hp}, x_w, x_h).$$

我們希望能計算出,給定寶可夢的一些 features $x$,能過算出他進化後的 CP 值 $y$

Machine Learning Steps

Machine Learning 主要有三個步驟

Step 1: Model

我們假設預測 $y$ 值的 function 為 $y = b + w \cdot x_{cp}$,許多不同的 $w$ 和 $b$ 可構成不同的 $f_1, f_2, \dots$,例如:

$$ \begin{aligned} f_1: y & = 10.0 + 9.0 \cdot x_{cp} \\ f_2: y & = 9.8 + 9.2 \cdot x_{cp} \\ f_3: y & = -0.8 - 1.2 \cdot x_{cp} \\ & \vdots \end{aligned} $$

如此一來,我們就有了 linear model:

$$y = b + \sum w_ib_i$$

其中,

  • $x_i: x_{cp}, x_s, x_{hp}, x_w, x_h$:寶可夢的 features
  • $w_i$:不同 features,給它不同的 weight
  • $b$:bias

Step 2: Goodness of Function

有了一堆 functions 後,我們必需要知道,這些 functions 有多好?因此我們需要一個評比的標準,我們可以用 Loss function $L$,它的 input 為 $f$,output 為 how bad it is?

loss function 可定義如下:

$$ \begin{aligned} L(f) & = \sum_{n = 1}^{10} (\hat y^n - f(x_{cp}^n))^2 \\ L(w, b) & = \sum_{n = 1}^{10} (\hat y^n - (b + w \cdot x_{cp}^n))^2 \end{aligned} $$

Step 3: Best Function

最後,我們要選出 best function,即:選擇 loss 最小的 function(參數):

$$ \begin{aligned} f ^ { * } & = \arg \min _ { f } L ( f ) \\ w ^ { * } , b ^ { * } & = \arg \min _ { w , b } L ( w , b ) \\ & = \arg \min _ { w , b } \sum _ { n = 1 } ^ { 10 } \left( \hat { y } ^ { n } - \left( b + w \cdot x _ { c p } ^ { n } \right) \right) ^ { 2 } \end{aligned} $$

求解最佳參數的方法可以是 Gradient Descent。

Gradient Descent

Gradient Descent 的步驟如下:

  1. (隨機)選擇參數初始值(e.g. $w^0$),上標表示時間點
  2. 計算 loss function $L(w)$ 在 $w = w^0$ 上時的 gradient,即:$\left. \frac { d L } { d w } \right| _ { w = w ^ { 0 } }$

  3. 向負梯度方向迭代更新

    • $\frac{dL}{dw} \Big|_{w = w^0} < 0 \to$ Increase $w$
    • $\frac{dL}{dw} \Big|_{w = w^0} > 0 \to$ Decrease $w$

    \begin{align} w ^ { 1 } & \leftarrow w ^ { 0 } - \eta \left. \frac { d L } { d w } \right| _ { w = w ^ { 0 } } \\ w ^ { 2 } & \leftarrow w ^ { 1 } - \eta \left. \frac { d L } { d w } \right| _ { w = w ^ { 1 } } \end{align}

    其中,$\eta$ 為 learning rate,用來控制一次走多遠、學習速度

重複這 3 個步驟,直到 $w$ 在 local minima 收斂為止。

順帶一提,只有一個參數 $w$ 時,$\nabla L$ 就是 $\frac{\partial L}{\partial w}$ 為 $L$ 的 gradient,所以才叫 Gradient Descent。

若有兩個參數 $w, b$ 時,$\nabla L = \left[ \begin{array} { l } { \frac { \partial L } { \partial w } } \\ { \frac { \partial L } { \partial b } } \end{array} \right]$,本質上概念還是相同的

Gradient Descent 可能使參數停在損失函數的局部最小值、微分為 $0$ 的點,或者微分為極小值的點。Linear regression 中不必擔心局部最小值的問題,因為 loss function 是 convex 的。

在得到 best function 之後,我們真正在意的是它在 testing data 上的表現。選擇不同的 model,會得到不同的 best function,它們在testing data 上有不同表現。

複雜模型的 model space 涵蓋了簡單模型的 model space,因此在 training data 上的錯誤率更小,但並不意味著在 testing data 上錯誤率也會小,因為 Model 太複雜有很高機率會出現 overfitting。

What are the hidden factors?

如果我們收集更多寶可夢進化前後的 CP 值會發現,進化後的 CP 值不只依賴於進化前的 CP 值,可能還有其它的隱藏因素(例如:寶可夢所屬的物種)。同時考慮進化前 CP 值 $x_{cp}$ 和物種 $x_s$,我們可以回到 Step 1: Model 重新選擇新的 model:

$$ \begin{aligned} \text{if } & x_s = \text{pidgey}: & y = b_1 + w_1 \cdot x_{cp} \\ \text{if } & x_s = \text{weedle}: & y = b_2 + w_2 \cdot x_{cp} \\ \text{if } & x_s = \text{caterpie}: & y = b_3 + w_3 \cdot x_{cp} \\ \text{if } & x_s = \text{eevee}: & y = b_4 + w_4 \cdot x_{cp} \end{aligned} $$

這仍是一個線性模型,因為它可以寫作:

$$ \begin{aligned} y = & b_1 \cdot \boldsymbol{\delta(x_s = \text{pidgey}) } & + & w_1 \cdot \boldsymbol{\delta(x_s = \text{pidgey}) \cdot x_{cp}} + \\ & b_2 \cdot \boldsymbol{\delta(x_s = \text{weedle}) } & + & w_2 \cdot \boldsymbol{\delta(x_s = \text{weedle}) \cdot x_{cp}} + \\ & b_3 \cdot \boldsymbol{\delta(x_s = \text{caterpie})} & + & w_3 \cdot \boldsymbol{\delta(x_s = \text{caterpie}) \cdot x_{cp}} + \\ & b_4 \cdot \boldsymbol{\delta(x_s = \text{eevee}) } & + & w_4 \cdot \boldsymbol{\delta(x_s = \text{eevee}) \cdot x_{cp}} \end{aligned} $$

上式中的粗體項都是 linear model $y = b + \Sigma w_i \cdot x_i$ 中的 feature $x_i$。

這個模型在 testing data 上有更好的表現,如果同時考慮寶可夢的其它屬性,選一個很複雜的模型,結果可能會導致 overfitting。

對線性模型來說,我們希望選出的 best function 能平滑一點,也就是權重係數小一些,因為這樣的話,在 testing data 受 noise 影響時,預測值所受的影響會更小。

所以在 Step 2: Goodness of Function 設計 loss function 時,我們可以加一個正則項 $\lambda\Sigma w_i^2$:

$$L = \sum _ { n } \left( \hat { y } ^ { n } - \left( b + \sum w _ { i } x _ { i }^n \right) \right) ^ { 2 } + \lambda \sum \left( w _ { i } \right) ^ { 2 }$$

越大的 $\lambda$,training error 可能會越大,但沒關係,我們希望函數平滑,但也不能太平滑,於是我們調整 $\lambda$,選擇使 testing error 最小的 $\lambda$。