Lasso算法

在統計學和機器學習中，**Lasso 算法**（英語：**least absolute shrinkage and selection operator**，又譯最小絕對值收斂和選擇算子、套索算法）是一種同時進行特徵選擇和正則化（數學）的迴歸分析方法，旨在增強統計模型的預測準確性和可解釋性，最初由史丹福大學統計學教授 Robert Tibshirani 於 1996 年基於 Leo Breiman 的非負參數推斷 (Nonnegative Garrote, NNG) 提出。Lasso 算法最初用於計算最小平方法模型，這個簡單的算法揭示了很多估計量的重要性質，如估計量與嶺迴歸（Ridge regression，也叫吉洪諾夫正則化）和最佳子集選擇的關係，Lasso 係數估計值 (estimate) 和軟閾值（soft thresholding）之間的聯繫。它也揭示了當協變數共線時，Lasso 係數估計值不一定唯一（類似標準線性迴歸）。

雖然最早是為應用最小平方法而定義的算法，lasso 正則化可以簡單直接地拓展應用於許多統計學模型上，包括廣義線性模型，廣義估計方程式，成比例災難模型和 M - 估計。Lasso 選擇子集的能力依賴於限制條件的形式並且有多種表現形式，包括幾何學，貝氏統計，和凸分析。

Lasso 算法與基追蹤降噪聯繫緊密。

## 歷史來源

Robert Tibshirani 最初使用 Lasso 來提高預測的準確性與迴歸模型的可解釋性，他修改了模型擬合的過程，在協變數中只選擇一個子集應用到最終模型中，而非用上全部協變數。這是基於有著相似目的，但方法有所不同的 Breiman 的非負參數推斷。

在 Lasso 之前，選擇模型中協變數最常用的方法是移步選擇，這種方法在某些情況下是準確的，例如一些協變數與模型輸出值有強相關性情況。然而在另一些情況下，這種方法會讓預測結果更差。在當時，嶺迴歸是提高模型預測準確性最常用的方法。嶺迴歸可以通過縮小大的迴歸係數來減少過擬合從而改善模型預測偏差。但是它並不選擇協變數，所以對模型的準確構建和解釋沒有幫助。

Lasso 結合了上述的兩種方法，它通過強制讓迴歸係數絕對值之和小於某固定值，即強制一些迴歸係數變為 0，有效地選擇了不包括這些迴歸係數對應的協變數的更簡單的模型。這種方法和嶺迴歸類似，在嶺迴歸中，迴歸係數平方和被強制小於某定值，不同點在於嶺迴歸只改變係數的值，而不把任何值設為 0。

## 基本形式

Lasso 最初為了最小平方法而被設計出來，Lasso 的最小平方法應用能夠簡單明了地展示 Lasso 的許多特性。

### 最小平方

假設一個樣本包括 N 種事件，每個事件包括 _p_ 個協變數和一個輸出值。讓 $y_{i}$ 為輸出值，並且 $x_{i}:=(x_{1},x_{2},\ldots ,x_{p})^{T}$ 為第 i 種情況的協變數向量，那麼 Lasso 要計算的目標方程式就是：

對所有 $\sum _{j=1}^{p}|\beta _{j}|\leq t$ ，計算 $\min _{\beta _{0},\beta }\left\{{\frac {1}{N}}\sum _{i=1}^{N}(y_{i}-\beta _{0}-x_{i}^{T}\beta )^{2}\right\}$

這裡 $t$ 是一個決定規則化程度的預定的自由參數。 設 $X$ 為協變數矩陣，那麼 $X_{ij}=(x_{i})_{j}$ ，其中 $x_{i}^{T}$ 是 $X$ 的第 _i_ 行，那麼上式可以寫成更緊湊的形式：

　
: 對所有 $\|\beta \|_{1}\leq t$ ，計算 $\min _{\beta _{0},\beta }\left\{{\frac {1}{N}}\left\|y-\beta _{0}-X\beta \right\|_{2}^{2}\right\}$

這裡 $\|\beta \|_{p}=\left(\sum _{i=1}^{N}|\beta _{i}|^{p}\right)^{1/p}$ 是標準 $\ell ^{p}$ 範數， $1_{N}$ 是 $N\times 1$ 維的 1 的向量。

因為 ${\hat {\beta }}_{0}={\bar {y}}-{\bar {x}}^{T}\beta $ ，所以有

　
: $y_{i}-{\hat {\beta }}_{0}-x_{i}^{T}\beta =y_{i}-({\bar {y}}-{\bar {x}}^{T}\beta )-x_{i}^{T}\beta =(y_{i}-{\bar {y}})-(x_{i}-{\bar {x}})^{T}\beta ,$

對變數進行中心化是常用的數據處理方法。並且共變異數一般規範化為 $\textstyle \left(\sum _{i=1}^{N}x_{ij}^{2}=1\right)$ ，這樣得到的解就不會依賴測量的規模。

它的目標方程式還可以寫為：

　
: $\min _{\beta \in \mathbb {R} ^{p}}\left\{{\frac {1}{N}}\left\|y-X\beta \right\|_{2}^{2}\right\}{\text{ subject to }}\|\beta \|_{1}\leq t.$

其拉格朗日形式為：

　
: $\min _{\beta \in \mathbb {R} ^{p}}\left\{{\frac {1}{N}}\left\|y-X\beta \right\|_{2}^{2}+\lambda \|\beta \|_{1}\right\}$

其中 $t$ 和 $\lambda $ 的關係取決於數據特徵。

### Orthonormal covariates

Some basic properties of the lasso estimator can now be considered.

Assuming first that the covariates are orthonormal so that $(x_{i}\mid x_{j})=\delta _{ij}$ , where $(\cdot \mid \cdot )$ is the inner product and $\delta _{ij}$ is the Kronecker delta, or, equivalently, $X^{T}X=I$ , then using subgradient methods it can be shown that

　
: ${\begin{aligned}{\hat {\beta }}_{j}={}&S_{N\lambda }({\hat {\beta }}_{j}^{\text{OLS}})={\hat {\beta }}_{j}^{\text{OLS}}\max \left(0,1-{\frac {N\lambda }{|{\hat {\beta }}_{j}^{\text{OLS}}|}}\right)\\&{\text{ where }}{\hat {\beta }}^{\text{OLS}}=(X^{T}X)^{-1}X^{T}y\end{aligned}}$

 $S_{\alpha }$ is referred to as the soft thresholding operator, since it translates values towards zero (making them exactly zero if they are small enough) instead of setting smaller values to zero and leaving larger ones untouched as the hard thresholding operator, often denoted $H_{\alpha }$ , would.

This can be compared to ridge regression, where the objective is to minimize

　
: $\min _{\beta \in \mathbb {R} ^{p}}\left\{{\frac {1}{N}}\|y-X\beta \|_{2}^{2}+\lambda \|\beta \|_{2}^{2}\right\}$

yielding

　
: ${\hat {\beta }}_{j}=(1+N\lambda )^{-1}{\hat {\beta }}_{j}^{\text{OLS}}.$

So ridge regression shrinks all coefficients by a uniform factor of $(1+N\lambda )^{-1}$ and does not set any coefficients to zero.

It can also be compared to regression with best subset selection, in which the goal is to minimize

　
: $\min _{\beta \in \mathbb {R} ^{p}}\left\{{\frac {1}{N}}\left\|y-X\beta \right\|_{2}^{2}+\lambda \|\beta \|_{0}\right\}$

where $\|\cdot \|_{0}$ is the " $\ell ^{0}$ norm", which is defined as $\|z\|=m$ if exactly m components of z are nonzero. In this case, it can be shown that

　
: ${\hat {\beta }}_{j}=H_{\sqrt {N\lambda }}\left({\hat {\beta }}_{j}^{\text{OLS}}\right)={\hat {\beta }}_{j}^{\text{OLS}}\mathrm {I} \left(\left|{\hat {\beta }}_{j}^{\text{OLS}}\right|\geq {\sqrt {N\lambda }}\right)$

where $H_{\alpha }$ is the so-called hard thresholding function and $\mathrm {I} $ is an indicator function (it is 1 if its argument is true and 0 otherwise).

Therefore, the lasso estimates share features of the estimates from both ridge and best subset selection regression since they both shrink the magnitude of all the coefficients, like ridge regression, but also set some of them to zero, as in the best subset selection case. Additionally, while ridge regression scales all of the coefficients by a constant factor, lasso instead translates the coefficients towards zero by a constant value and sets them to zero if they reach it.

### Correlated covariates

Returning to the general case, in which the different covariates may not be independent, a special case may be considered in which two of the covariates, say _j_ and _k_, are identical for each case, so that $x_{(j)}=x_{(k)}$ , where $x_{(j),i}=x_{ij}$ . Then the values of $\beta _{j}$ and $\beta _{k}$ that minimize the lasso objective function are not uniquely determined. In fact, if there is some solution ${\hat {\beta }}$ in which ${\hat {\beta }}_{j}{\hat {\beta }}_{k}\geq 0$ , then if $s\in [0,1]$ replacing ${\hat {\beta }}_{j}$ by $s({\hat {\beta }}_{j}+{\hat {\beta }}_{k})$ and ${\hat {\beta }}_{k}$ by $(1-s)({\hat {\beta }}_{j}+{\hat {\beta }}_{k})$ , while keeping all the other ${\hat {\beta }}_{i}$ fixed, gives a new solution, so the lasso objective function then has a continuum of valid minimizers. Several variants of the lasso, including the Elastic Net, have been designed to address this shortcoming, which are discussed below.

## 一般形式

## 算法解釋

## 應用

LASSO 已被應用於經濟和金融領域，可以改善預測結果並選擇有時被忽視的變數。例如：公司破產預測和高增長公司預測。

## 參見

* 降維
* 特徵選擇

## 參考文獻