> For the complete documentation index, see [llms.txt](https://sejkai.gitbook.io/academic/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sejkai.gitbook.io/academic/machine-learning/regularization/overfitting_problem.md).

# Solving the Problem of Overfitting

## The Problem of Overfitting

當我們要尋找 Hypothesis 來 fit 我們的 training set 時

可以遇到三種情況

![](/files/-LpVa4IFv1dEz9goFtys)

1. **Underfit (High bias)** 
   * Hypothesis 不是很好的 fit 這些 example data
2. **Just right** 
   * Hypothesis 很好的 fit 這些 example data
3. **Overfit (High variance)** 
   * Hypothesis 太過 "鑽牛角尖" 於每一個 training set

我們為 Overfitting 下一個定義 :

太多的 features，讓求得的 Hypothesis 在 training data 得到不錯分數 (cost function J 接近 0)

但完全沒辦法讓 test set 或是真實資料套入使用

同樣的事情可以發生在 logistic regression :

![](/files/-LpVa4IH_BkOD2MouGSj)

會造成 overfitting 的原因就是因為 features 使用太多了

但又不知道哪些 features 可以完全消除掉 (可能對 training 有益)

有兩種方法可以解決 :

1. 減少 features 數量
   * 手動選擇不要的 features
   * 使用 **model selection algorithm** (later in other course)
2. Regularization
   * 留下全部 features，但降低 theta's 的 magnitude
   * 這方法就可以不用擔心會不會刪掉對 training 有益的 features 

## Cost Function

若我們想降低多餘 (可能) 的 features 所帶來的 overfitting 影響

我們只要將這些 features 在 cost function 的代價提高，讓他們對 hypothesis 的影響下降就好

以 $$\theta\_0 + \theta\_1x + \theta\_2x^2 + \theta\_3x^3 + \theta\_4x^4$$ 為例

我們將他的 Cost function 調整為

$$
\min\_\theta \frac{1}{2m}\sum\_{i=1}^m(h\_\theta(x^{(i)})-y^{(i)})^2 {\color{red}+1000\cdot \theta\_3^2+1000\cdot\theta\_4^2}
$$

新的 cost function 就可以在不去除 $$\theta\_3$$ 跟 $$\theta\_4$$ 的情況

讓兩者對 hypothesis 的影響降低

1000 可以是其他較大數值，但不能夠過大

不然會使得 $$\theta\_3$$ 跟 $$\theta\_4$$ 直接不見

![](/files/-LpYzFLNkjCa8ksl83zT)

右上的**紫線**就是在 implement regularization 過後的新 hypothesis function

所以除了 $$\theta\_0$$ 不用變更以外

我們將 regularization 套用到所有的 $$\theta$$ (因為我們也不知道到底是哪一個 feature 造成 overfitting)

得到了新的公式 :

$$
J(\theta) = \frac{1}{2m}\sum\_{i=1}^m(h\_\theta(x^{(i)})-y^{(i)})^2+\lambda\sum\_{j=1}^n \theta\_j^2
$$

* $$\lambda$$ 為 **regularization parameter**
  * 將會作為 $$\theta$$ 對於整個 cost function 的影響指標
* 只是多了後面一個式子，就可以讓 overfitting 的影響減少
* 但要小心，若 $$\lambda$$ 非常大的話
  * 會讓每個 $$\theta$$ 都變為 0
  * 變回 underfit 的狀況

## Regularized Linear Regression

現在我們將 regularization 的公式套入 linear regression 和 logistic regression

先從 linear regression 的 gradient descent 開始

### Linear regression - gradient descent

我們會改變所有 $$\theta$$ 但是 $$\theta\_0$$ 要維持原本的樣子

$$
\begin{aligned}
&\text{Repeat {}\\
&\theta\_0 := \theta\_0 - \alpha \frac{1}{m} \sum\_{i=1}^m(h\_\theta(x^{(i)})- y^{(i)})x\_0^{(i)}\\
&\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 \begin{Bmatrix}1, 2, ... n
\end{Bmatrix}\\
&\text{}}
\end{aligned}
$$

我們發現第二行 $$\theta\_j$$ 的公式可以在簡化成這樣 :

$$
\theta\_j := \theta\_j(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m}\sum\_{i=1}^m(h\_\theta(x^{(i)}) - y^{(i)})x\_j^{(i)}
$$

可以發現 $$1-\alpha\frac{\lambda}{m}$$ 永遠都會是小於 1 的正數

所以負號的前一項能表示每回合的 $$\theta\_j$$ 會固定變小

而後面一項跟原本的 gradient descent 一模一樣

### Linear regression - Normal equation

要將 regularization 加入 normal equation 中

只需簡單加入 $$\lambda \cdot L$$ 即可，其中 $$L$$ 為一個像是 identity matrix 但第一項為 0 的特殊矩陣

這個矩陣為一個 $$(n-1)\times(n-1)$$ 的矩陣

有一個 0 的原因就是不想要變動到 $$\theta\_0$$ 的值

$$
\theta = \left(X^TX + \lambda \cdot \begin{bmatrix}
0 \\
& 1 \\
&& 1 \\
&&& \ddots \\
&&&&1
\end{bmatrix} \right)^{-1}X^Ty
$$

將 regularization 套入 normal equation 也有另一個好處

之前說過若 features 大於 training examples 數量太多

則 $$X^TX$$ 有可能會為 non-invertible

但現在有了 $$\lambda \cdot L$$

$$X^TX + \lambda \cdot L$$ 就一定是 invertible 的矩陣了 !

## Regularized Logistic Regression

我們一樣來將 regularization 套用在 logistic regression

讓 overfitting 的藍線變為正常的紫線 hypothesis

![](/files/-LpYzFLPdCagJI3z0sX8)

一樣在 logistic cost function

$$
J(\theta) = -\frac{1}{m}\sum\_{i=1}^m\[y^{(i)}\log(h\_\theta(x^{(i)})) + (1-y^{(i)})\log(1-h\_\theta(x^{(i)}))]
$$

的最後加上 regularization 的式子得到 :

$$
J(\theta) = -\frac{1}{m}\sum\_{i=1}^m\[y^{(i)}\log(h\_\theta(x^{(i)})) + (1-y^{(i)})\log(1-h\_\theta(x^{(i)}))]

* \frac{\lambda}{2m}\sum\_{j=1}^n\theta\_j^2
  $$

注意我們一樣不想變動到 $$\theta\_0$$

所以 regularization 的 summation 從 1 開始 !

接著套進 gradient descent

$$
\begin{aligned}
&\text{Repeat {}\\
&\theta\_0 := \theta\_0 - \alpha \frac{1}{m} \sum\_{i=1}^m(h\_\theta(x^{(i)})- y^{(i)})x\_0^{(i)}\\
&\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 \begin{Bmatrix}1, 2, ... n
\end{Bmatrix}\\
&\text{}}
\end{aligned}
$$

其實跟 linear regression 一樣

只是 $$h\_\theta(x) = \frac{1}{1+e^{-\theta^Tx}}$$

## Advanced optimization

在 Octave 實作 logistic regression 的 advanced optimization 時

這些 code 又該怎麼跟 regularization 一起實作 :

$$
\begin{aligned}
&\text{function \[jVal, gradient] = costFunction(theta)} \\
&\text{jVal = }\[ \text{code to compute } J(\theta) ]; \\
\rightarrow \&J(\theta) = -\frac{1}{m}\sum\_{i=1}^m\[y^{(i)}\log(h\_\theta(x^{(i)})) + (1-y^{(i)})\log(1-h\_\theta(x^{(i)}))]

* \frac{\lambda}{2m}\sum\_{j=1}^n\theta\_j^2\\
  &\text{gradient(1) = } \[ \text{code to compute } \frac{d}{d\theta\_0}J(\theta)]; \\
  \rightarrow &\frac{1}{m} \sum\_{i=1}^m(h\_\theta(x^{(i)})- y^{(i)})x\_0^{(i)} \\

&\text{gradient(2) = } \[ \text{code to compute } \frac{d}{d\theta\_1}J(\theta)]; \\
\rightarrow &\frac{1}{m} \sum\_{i=1}^m(h\_\theta(x^{(i)})- y^{(i)})x\_1^{(i)} + \frac{\lambda}{m}\theta\_1 \\

&\text{gradient(3) = } \[ \text{code to compute } \frac{d}{d\theta\_2}J(\theta)]; \\
\rightarrow &\frac{1}{m} \sum\_{i=1}^m(h\_\theta(x^{(i)})- y^{(i)})x\_2^{(i)} + \frac{\lambda}{m}\theta\_2 \\

\vdots\\
&\text{gradient(n+1) = } \[ \text{code to compute } \frac{d}{d\theta\_n}J(\theta)]; \\
\end{aligned}
$$