---
tags: 機器學習 (Machine Learning)
---

# 線性模型與正則化 (Linear Models and Regularization)

## Linear regression

### 前言
假設數據$X$具有$n$筆資料與$p$個變數，首先對$X$進行正規化，再利用此數據集建立線性模型
$$
Y_{n \times 1}=X_{n \times p} \beta_{p \times 1}+\epsilon
$$
上式的線性模型分為兩個部分，$X\beta$為規律性的部分，而$\epsilon$則代表隨機性。假設線性模型是正確的，我們希望找到一個損失函數(Loss function)來衡量$Y$和$X\beta$的距離，而次損失函數越小越好，將上述文字利用數學表示，即
$$
\min L(\beta)
$$
而在線性模型中通常利用$L_2$-norm來衡量$Y$和$X\beta$的距離
$$
L(\beta)=\| y-X\beta \|_2^2
$$

### 推導
#### 最小平方法
在線性回歸中可以將損失函數(Loss function)改寫為
$$
L(\beta)=( y-X\beta )^T (y-X\beta)
$$
對向量$\beta$微分並令其為0，可得
$$
X^T(X\beta−y)+X^T(X\beta−y)=0
$$
移項後
$$
\hat{\beta}_{OLS}=(X^TX)^{−1}X^Ty
$$

#### 最大概似估計(Maximum Likelihood Method)
由前言我們知道$\epsilon$為隨機的部分，和$X$無關，我們假設
$$
\epsilon \sim \mathcal{N}(0,\sigma^2)
$$
其中$\sigma$為未知且固定的常數。

則可推得
$$
Y=X\beta + \epsilon \sim \mathcal{N}(X\beta, \sigma^2)
$$
因為$Y$之間互為獨立，可以寫下聯合機率密度函數，
$$
L_p(Y|X, \beta, \sigma^2)=\prod_{i=1}^n p(y_i|x_i,\beta,\sigma^2) = \prod_{i=1}^n \frac{1}{\sqrt{2 \pi}\sigma} \exp\{ -\frac{(y_i-x_i\beta)^2}{2 \sigma^2} \}
$$
對上式取$\log$，
$$
\ell(\beta)=\sum_{i=1}^n \log p(y_i|x_i,\beta,\sigma^2) = n \log \frac{1}{\sqrt{2 \pi}\sigma} - \sum_{i=1}^n \frac{(y_i-x_i \beta)^2}{2 \sigma^2}
$$
則最大化概似函數，
$$
\max_{\beta} \ell(\beta)=- \sum_{i=1}^n \frac{(y_i-x_i \beta)^2}{2 \sigma^2}
$$
因為$\sigma^2$為常數，因此$\max \ell(\beta)$等同於最小化損失函數$\min L(\beta)$
$$
L(\beta)=(y-X\beta)^T (y-X\beta)=\sum_{i=1}^n (y_i-x_i \beta)^2
$$
因此利用最大概似估計法所得的$\hat{\beta}$即為
$$
\hat{\beta}=(X^TX)^{−1}X^Ty
$$

### 性質：
1. $Y$和$X$必須存在線性關係
2. 當$X$上升一個單位時，$y$==平均==上升$\beta$個單位
:::danger
因為$\epsilon \sim \mathcal{N}(0,\sigma^2)$
$$
\mathbb{E}(Y|X)=\mathbb{E} (X\beta + \epsilon) = X\beta
$$
:::
3. Log-Log線性模型: 當$X_1$增加$1\%$，$Y$平均增加$\hat{\beta}_1$比例
:::danger
Suppose
\begin{align*}
\log Y &= \beta_0 + \beta_1 \log X_1 + \epsilon\\
\log Y^* &= \beta_0 + \beta_1 \log \left( X_1 (1+\delta) \right) + \epsilon \\
&=\beta_0 + \beta_1\log X_1 + \beta_1 \log (1+\delta) + \epsilon
\end{align*}
By Taylor expansion, we know that
$$
log(1+\delta) \approx \delta
$$
when $\delta \rightarrow 0.$
Hence
\begin{align*}
\log \left( \frac{Y^*}{Y} \right)=\beta_1 \log (1+ \delta) \approx \beta_1 \delta
\end{align*}
Moreover,
\begin{align*}
\log \left( \frac{Y^*}{Y} \right) = \log \left( 1 + \frac{Y^*-Y}{Y} \right) \approx \frac{Y^*-Y}{Y}
\end{align*}

Thus,
$$
\frac{Y^*-Y}{Y} \approx \beta_1 \delta
$$
,which means a percent change in $X_1$ leads to an estimated $\hat{\beta}_1$ percentage change in the average value of $Y$
:::
4. 樣本數必須多於特徵變數($n>p$)
5. 若沒有常數項，則模型必須通過原點
6. 對異常值非常的敏感
7. 遺漏變量
8. 若有多重共線性的問題，估計會變得非常不穩定
:::info
#### 共線性(Collinearity)：
假設我們利用OLS估計，則$\hat{\beta}$為
$$
\hat{\beta}_{OLS}=(X^TX)^{-1}X^Ty=(X^TX)^{-1}X^T(X\beta+\epsilon)=\beta+(X^TX)^{-1}X^T\epsilon
$$
其中$\beta$為真實值。由上式可知，$\hat{\beta}_{OLS}$受到$(X^TX)^{-1}X^T\epsilon$的影響，若$(X^TX)^{-1}X$變大，再乘上$\epsilon$後，會使得$\hat{\beta}_{OLS}$嚴重偏離真實值($\beta$)。為了方便分析，將$X$做SVD轉換，
$$
X=U \Sigma V^T
$$
帶入
$$
(X^TX)^{-1}X^T=V \Sigma^{-1}U
$$
其中
$$
\Sigma^{-1}=\begin{bmatrix}
\frac{1}{\sigma_1} & & & \cdots\\
& \ddots & & \cdots \\
& & \frac{1}{\sigma_p} & \cdots
\end{bmatrix}
$$
出現共線性時，有些$\sigma$會趨近於0，換句話說，$\frac{1}{\sigma}$太大，使得估計式$\hat{\beta}$的干擾過大，偏離真實值($\beta$)
:::

9. 省略變數偏誤 (Omitted Variable Bias)
假設真實模型為
$$
Y=X\beta + Z\delta + U \text{ where $U \sim N(0,I)$}
$$
而我們忽略了變數$Z$而假設模型為
$$
Y=X\beta + U \text{ where $U \sim N(0,I)$}
$$
忽略$Z$後得到的$\hat{\beta}$為
$$
\hat{\beta}=(X^TX)^{-1}X^T Y
$$
得$E(\beta)$為
\begin{align*}
E[\hat{\beta}]&=(X^TX)^{-1}X^T (X\beta + Z\delta + U)\\
&=\beta+(X^TX)^{-1}E[X^TZ|X]\delta+(X^TX)^{-1}X^TE[U]\\
&=\beta+(X^TX)^{-1}E[X^TZ|X]\delta
\end{align*}
其中$(X^TX)^{-1}E[X^TZ|X]\delta$即為省略變數偏誤。

## 嶺回歸 (Ridge regression)

為了解決共線性與樣本數少於特徵向量導致不能計算的缺點，我們需要在損失函數上增加懲罰項，亦即將損失函數(Loss function)改寫為
$$
L(\beta)=( y-X\beta )^T (y-X\beta)+\lambda \beta^T \beta
$$

### 推導
對$\beta$微分並令其為0，可得
$$
\frac{\partial L(\beta)}{\partial \beta}= 2X^T(X\beta−y)+2\lambda \beta=0
$$
移項後得$\beta$的封閉解為
$$
\hat{\beta}_{Ridge}=(X^TX+\lambda I)^{−1}X^Ty
$$

### 性質:
1. 當$n<p$時，仍可估計。當$n<p$時，$X^TX$是不可逆矩陣，而嶺回歸對$\beta$的估計式相當於在對角線上加上$\lambda$值，使得$(X^TX+\lambda I)$成為可逆矩陣。
2. 當數據中的特徵變數增加時($p$增加)，我們就越容易捕捉到共線性的變數。而當模型具有共線性時，估計所得的$\beta$就會非常地不穩定(variance會變很大)
3. 當$\lambda \rightarrow \infty$，則$\hat{\beta}_{Ridge}$會趨近於$0$；反之，若$\lambda=0$則$\hat{\beta}_{Ridge}=\hat{\beta}_{OLS}$

:::info
### Linear, PCA, Ridge regression的比較:
\begin{align*}
\hat{y}_{OLS} &= X \hat{\beta}_{OLS}=X (X^T X)^{-1}X^T y = U U^T y\\
\hat{y}_{PCR} &= X_{PCR} \hat{\beta}_{PCR} = U \mbox{diag}\{ 1,..., 1,0,...,0\} U^T y \\
\hat{y}_{Ridge} &= X \hat{\beta}_{Ridge} = X (X^T X + \lambda I)^{-1}X^T y = U \mbox{diag} \frac{d_i^2}{d_i^2 + \lambda} U^T y
\end{align*}

1. 若 $\lambda=0$，$\hat{y}_{OLS}=\hat{y}_{Ridge}$

2. 若 $\lambda>0$，當$d_i$越大時，ridge regression越不容易受到$\lambda$的影響；當$d_i$越小時，ridge regression對該$\beta$的懲罰越大。

3. 在 PCA regression(PCR)中，對於大的$d_i$並不會影響其對應的$\beta$，然而過小的$d_i$則會被完全移除。可以對應為對前q個大的特徵值其所對應的$\lambda=0$，剩餘的p-q個維度其$\lambda=\infty$

4. 由上述2點和第3點可知，ridge regression相較於PCA regression(PCR)為較為平滑之版本；但是若每個特徵值皆差不多大，則ridge regression可視為平均懲罰所有的特徵向量，此時和PCR會非常的不一樣

5. 在實務上，Ridge regression表現得比較好。

:::

## LASSO

### 前言
我們希望在估計模型的時候，可以順便選取重要的變數，換句話說，將不重要的變數估計為0。因此我們可以將其用數學式表達之
$$
\min_{\beta \in \mathbb{R}^p} \|y-X\beta \|_2^2 \text{ subject to $\|\beta \|_0 \leq k$}
$$
上式又稱之為Best Subset Selection。然而此限制式並非凸函數且不可微分，因此在估計$\beta$相當的困難。而在數學上我們已知當$L_p$-norm的$p$介在0到1之間時具有稀疏性(Sparsity)，且$p=1$時恰巧為凸函數，因此我們將Best Subset Selection的限制範圍改為
$$
\min_{\beta \in \mathbb{R}^p} \|y-X\beta \|_2^2 \text{ subject to $\|\beta \|_1^1 \leq t$}
$$
上式即為著名的Least Absolute Shrinkage and Selection Operator(LASSO)。透過KKT條件，可以將其改寫為
$$
\min_{\beta \in \mathbb{R}^p} \|y-X\beta \|_2^2 + \lambda \|\beta \|_1^1
$$

### 定義
假設我們的損失函數(Loss function)為
$$
L(\beta)=\sum_{i=1}^n \left( y_i-\sum_{j=1}^p x_{ij} \beta_j \right)^2 + \lambda \sum_{j=1}^p \| \beta_j \|_1
$$

令
\begin{align*}
RSS(\beta) &= \sum_{i=1}^n \left( y_i-\sum_{j=1}^p x_{ij} \beta_j \right)^2\\
d(\beta) &= \lambda \sum_{j=1}^p \| \beta_j \|_1
\end{align*}

其中$d(\beta)$為懲罰項。

### 推導

1. 對$RSS(\beta)$偏微分可得
\begin{align*}
\frac{\partial RSS(\beta)}{\partial \beta} &=-2 \sum_{i=1}^n x_{ik} \left( y_i-\sum_{j=1}^p x_{ij} \beta_j \right)\\
&=-2 \sum_{i=1}^n \left( x_{ik}y_i-x_{ik}\sum_{j=1,j \not=k}^p x_{ij} \beta_j -x_{ik}^2\beta_k \right)\\
&=-2 \sum_{i=1}^n x_{ik} \left( y_i-\sum_{j=1,j \not=k}^p x_{ij} \beta_j\right)+2 \beta_k \sum_{i=1}^n x_{ik}^2
\end{align*}
假設
\begin{align*}
p_k&=\sum_{i=1}^n x_{ik} \left( y_i-\sum_{j=1,j \not=k}^p x_{ij} \beta_j\right)\\
z_k&=\sum_{i=1}^n x_{ik}^2
\end{align*}
則
$$
\frac{\partial RSS(\beta)}{\partial \beta_k}=-2p_k+2z_k \beta_k
$$
2. 對$d(\beta)$微分：在這邊微分必須利用sub-gradient的技巧
$$
\lambda \frac{\partial \sum_{j=1}^p|\beta_j|}{\partial \beta_k} =
\begin{cases}
-\lambda & \text{if $\beta_k<0$} \\
[-\lambda,\lambda] & \text{if $\beta_k=0$} \\
\lambda & \text{if $\beta_k>0$} \\
\end{cases}
$$
3. 因此$L(\beta)$的對$\beta_k$的偏微分即為
$$
\frac{\partial L(\beta)}{\beta_k}=-2p_k+2z_k \beta_k+\begin{cases}
-\lambda & \text{if $\beta_k<0$} \\
[-\lambda,\lambda] & \text{if $\beta_k=0$} \\
\lambda & \text{if $\beta_k>0$}
\end{cases}
$$
令$\frac{\partial L(\beta)}{\beta_k}=0$得到
$$
\hat{\beta}_k=
\begin{cases}
\frac{p_k+\frac{\lambda}{2}}{z_k} & \text{if $p_k<-\frac{\lambda}{2}$} \\
0 & \text{if $-\frac{\lambda}{2} \leq p_k \leq \frac{\lambda}{2}$} \\
\frac{p_k-\frac{\lambda}{2}}{z_k} & \text{if $p_k>\frac{\lambda}{2}$}
\end{cases}
$$
通過上述的公式，我們可以每次選取一個維度進行最佳化，直到收斂，此方法又稱為Coordinate Descent。

### 性質
1. 具有可解釋性
2. 當$n<p$時仍可運算
3. LASSO同時進行選模和估計，將不重要的變數，直接估計為$0$；但亦會壓縮到重要的變數，使重要的特徵變數具有偏誤(bias)

## Elastic-Net

###### tags: `Linear Model`, `Ridge`, `PCR`, `LASSO`, `Elastic-net`, `Regularization`