# 吳恩達_機器學習_第3週_2_Regularization
###### tags: `andrew` `machine learning` `coursera`
[課程連結](https://www.coursera.org/learn/machine-learning/home/week/3)

[TOC]

## Solving the Problem of Overfitting
### The Problem of Overfitting
[課程連結](https://www.coursera.org/learn/machine-learning/lecture/ACpTQ/the-problem-of-overfitting)
#### Example: Linear regression(housing prices)

回到線性迴歸的範例，我們以房子的大小來預測房價
* 左圖：
* 簡單線性來
* underfitting
* high bias(高偏差)
* 中圖：
* 二次式，我們看到似乎較為完美
* just right
* 右圖：
* 更高項式(polynomial)(四次)
* 此線會配合資料走動的扭來扭去
* overfitting
* high variance(高方差)

過高的項式造成了函數過於龐大的問題，如果沒有足夠的資料去約束變量過多的模型即產生overfitting的問題，此時你的成本函數幾乎是接近或是等於0，也造成泛化(generalize)效果不好的問題。

註：generalize指一個模型應用到新樣本的能力

#### Example: Logistic regression

在邏輯斯迴歸上也是一樣的問題，透過更高的多項式，都是有可能造成決策邊界滿足去訓練資料集因而造成overfitting。

過多的特徵，甚至特徵數超過你的數據集量，也會造成overfitting。

#### Addressing overfitting

避免overfitting作法如下：
* 減少特徵，將特徵再精選。(reduce number of features)
* 透過模型選擇演算法來挑選特徵(如隨機森林..)
* 在捨棄特徵的同時，你也捨棄了一些資料所給出的訊息。
* 正規化(Regularization)
* 保留所有的特徵
* 減少$\theta_j$的值，讓每一個特徵都為預測值做一些貢獻

### Cost Function
[課程連結](https://www.coursera.org/learn/machine-learning/lecture/B1MnL/cost-function)

#### Intuition

稍早提到，透過更高的多項式會造成overfitting的問題(上圖右)，但是，假如我們透過『懲罰(penalize)』使得$\theta_3 , \theta_4$變小，相對的也是降低了成本函數的均方誤差，如下式子(1000只是假設上的亂填)：
$min_\theta\ \dfrac{1}{2m}\sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 + 1000\cdot\theta_3^2 + 1000\cdot\theta_4^2$

我們發現到以上述式子計算成本函數非常的大，所以我們的目標是將$\theta_3,\theta_4$盡可能的接近於零，直到可以忽略它的影響，這樣雖然是使用多項式，但因為3次方與4次方被我們調整到接近於0，整個影響力變小了，就相對於是利用了2次式加上一點點點的影響來擬合數據，也因此，多項次的圈形將不再扭曲，變的像2次式一樣(上圖右紫線)。
#### Regularization

這後面的概念，就是正規化(Regularization)，透過較小的參數值來取得一個簡單的演算法，因此上一個案例中$\theta_3,\theta_4$是接近於0的值，對應於較為平滑的函數，就可以有效降低overfitting的問題。

實務上，我們可能有上百上千個特徵，也不知道那幾個特徵較為重要，所以，我們就在參數計算上直接加入了正規項如下
$min_\theta\ \dfrac{1}{2m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 + \lambda\ \sum_{j=1}^n \theta_j^2$
* $\lambda\ \sum_{j=1}^n \theta_j^2$
* 正規化項目
* 從$\theta_1$開始的，不會懲罰$\theta_0$
* $\lambda$為正規化參數
* $\lambda$做的就是維持資料集與參數的平衡，從而保持hypothesis的相對簡單(因為參數會因為正規項而減小)

#### Regularization

當$\lambda$設置過大就意味著懲罰項的值很大，意思上就像是我們將$\theta_1....\theta_n$調整到接近0，只會剩下$\theta_0$是有效的，導致呈現一條水平線的結果，造成的就是underfitting。

### Regularized Linear Regression
[課程連結](https://www.coursera.org/learn/machine-learning/lecture/QrMXd/regularized-linear-regression)

#### Regularized Linear Regression

上圖是上節最後加入正規化之後的成本函數，目標是尋找可以最小化成本函數的參數$\theta$。前面的部份是一般線性迴歸的目標函數，而後面是加入的正規項，$\lambda$則為正規項的參數。
#### Gradient Descent

$\begin{align*} & \text{Repeat}\ \lbrace \newline & \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \newline & \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\newline & \rbrace \end{align*}$

$\theta_0$不做正規化，另外分開計算，再將原始成本函數加入正規項，就是完整的成本函數，再利用梯度下降來優化：
$\theta_j:=\theta_j(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m}\sum^m_{i=1}(h_\theta(x^{(i)}-y^{(i)}))x_j^{(i)}$

其中$\theta_j(1-\alpha\frac{\lambda}{m})$得到的結果就有點像是將$\theta$的原始值乘上0.99一般的效果，因為$1-\alpha\frac{\lambda}{m}$是一個小於1又很接近1的值，而後面的$\alpha\frac{1}{m}\sum^m_{i=1}(h_\theta(x^{(i)}-y^{(i)}))x_j^{(i)}$則與原始未加入正規項一樣沒有改變。

現在我們知道，正規化就是先將每一個被正規化的參數$\theta_j$先乘上一個比1小一點的值，也就是將參數縮壓了一點，再減掉原始梯度更新的數值。
#### Normal equation

梯度下降只是我們擬合線性迴歸的兩種演算法中的其中一種，另一種稱為正規方程，作法如下：
1. 建立一個矩陣-$X$，每一個row都對應一個訓練樣本，維度為$m\times(n+1)$
2. 建立一個向量-$y$，$m$維，為訓練集的標籤
3. 令$\theta=(X^TX)^{-1}X^Ty$
* 如果加入正規項的話就加入一個矩陣($n+1,n+1$)，其對角元素除第一個元素為0之外其餘為1，剩餘元素也皆為0，再乘上參數$\lambda$。

以上面的正規方程來實作的話可以讓參數直接達到全域最小值。
#### Non-invertibility (optional/advanced)

這邊討論不可逆性的問題，做為上次可選課程的補充說明。

假設，資料集總數小於特徵數，即$m \leq n$，那$X^TX$會是不可逆的，或稱[奇異的](http://terms.naer.edu.tw/detail/2124786/)，或另一種說法，這矩陣是退化的(degenerate)。這種時候如果你用Octive的函數-`pinv`來取得偽逆矩陣，會有值，但那可能不是一個很好的演算法。如果在Octave用函數-`inv`或其它語言的線性計算的話，基本上是計算不出來的，那會回傳矩陣為奇異，不可逆的。但**加入正規項**會讓這個不可逆的矩陣變為可逆。

### Regularized Logistic Regression
[課程連結](https://www.coursera.org/learn/machine-learning/lecture/4BHEy/regularized-logistic-regression)

#### Regularized Logistic Regression

之前的課程中我們看到Logistic Regression在使用高階多項式來擬合資料的情況下會出現overfitting的情況，可以看到它的決策邊界會完美的擬合，但這不是一個好的hypothesis，即使你不是使用高階多項式，一但特徵過多，也是會造成overfitting的情況。

原始的cost function：
$J(\theta)=-\dfrac{1}{m}\sum^m_{i=1}\left[y^{(i)}\log(h_\theta(x^{(i)}))+(1-y^{(i)})\log(1-h_\theta(x^{(i)}))\right]$

加入正規項：
$J(\theta)=-\dfrac{1}{m}\sum^m_{i=1}\left[y^{(i)}\log(h_\theta(x^{(i)}))+(1-y^{(i)})\log(1-h_\theta(x^{(i)}))\right]+\dfrac{\lambda}{2m}\sum^n_{j=1}\theta^2_j$

一樣的，正規項的懲罰並不會針對$\theta_0$，這樣整個決策邊界看起來就會合理很多(紫線)
#### Gradient descent

$\begin{align*} & \text{Repeat}\ \lbrace \newline & \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \newline & \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\newline & \rbrace \end{align*}$

跟Linear Regression一樣，我們另外將$\theta_0$拉出來計算，其餘的參數就加入正規項，雖然整個項目看起來跟Linear Regression是一樣的，但注意到，兩者的$h_\theta$是不同的，Logistic Regression的$h_\theta$是$\dfrac{1}{1+e^{-\theta^Tx}}$
#### Advanced optimization

這邊說明在Octave中使用高階最佳化演算法來優化Logistic Regression的方法，需注意到的是Octave的索引是從1開始，因此$\theta_0$在Octave是1。