ラッソ回帰とは？

定義

$$ \begin{bmatrix} y_{1} \\ y_{2} \\ \vdots \\ y_{n} \end{bmatrix} = \begin{bmatrix} 1 & x_{11} & \cdots & x_{p1} \\ 1 & x_{12} & \cdots & x_{p2} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{1n} & \cdots & x_{pn} \end{bmatrix} \begin{bmatrix} \beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p} \end{bmatrix} + \begin{bmatrix} \varepsilon_{1} \\ \varepsilon_{2} \\ \vdots \\ \varepsilon_{n} \end{bmatrix} $$ $n$ 個のデータが与えられており、$p < n$ である場合、線形多重回帰モデルを設計行列で表すと上記のようになり、簡単に $Y = X \beta + \varepsilon$ と表します。この時、次の最適化問題を BPDN^{basis Pursuit Denoising}と呼び、BPDNを解くことを ラッソ^{lASSO, Least Absolute Shrinkage and Selection Operator}またはラッソ回帰^{lASSO regression}と呼びます。 $$ \argmin_{\beta} \left( {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right) $$ ここで、$\lambda \ge 0$ を チューニングパラメーター^{tuning Parameter}と呼びます。

$\left\| \cdot \right\|_{2}$ はユークリッドノルムであり、$\left\| \cdot \right\|_{1}$ は絶対値の合計です。

説明

ラッソは、その名の通り、回帰問題で回帰係数の絶対値を縮小^shrinkageして、最小限^leastのみを選択^selectionします。

機械学習では、BPDNを一般的な最小二乗問題に $\lambda \left\| \beta \right\|_{1}$ を加えた$l_{1}$ 正則化^{regularization}として見ることもできます。

なぜ使うのか？

スパース回帰の文書を先に読んでおくとより良いでしょう。

統計学の観点から: 解釈が簡単なモデルを見つけるためです。基本的に、回帰係数の大きさがデータのスケールに対して十分に大きくなければ統計的に有意ではないとされていました。つまり、必ずしも$0$ではないが、ほとんど$0$であれば、データを説明するために必要なものではないかもしれないということです。この解釈はラッソ回帰でも正確に同じとは限りませんが、結局のところ、‘小さい回帰係数’を見つけ出して処理することが目的です。
機械学習の観点から: オーバーフィッティング^overfittingを防ぐためです。与えられたデータをうまく説明するために非常に複雑な項を追加するか、追加データを確保して非常に特殊なケースまでカバーするモデルを作ることができるかもしれませんが、このように細かく合わせると、トレーニングデータでは優れていても実際のテストではひどい結果になる可能性があります。多くの変数に対して細かい回帰係数を見つけることは、オーバーフィッティングのリスクを増大させるため、データを説明する力を落とすペナルティを背負ってでも防ごうとするのです。

これは観点の違いに過ぎず、よく読むと同じことを言っています。

チューニングパラメーター $\lambda$

この説明はリッジ回帰についてのものですが、チューニングパラメーターを扱う文脈ではラッソ回帰でも同じです。

定義で紹介されたチューニングパラメーター $\lambda$ は、大きければ大きいほどペナルティ^penalty $\left\| \lambda \right\|$ が強くなりますが、これがあまりに小さいと単なる回帰分析と変わらず、あまりに大きいとデータを説明するかどうかにかかわらず、$\beta = \mathbf{0}$ が最良の選択となってしまいます。極端な直感的な例として、データから出てくる値のスケールが0~10程度なのにペナルティに非常に大きな重み $\lambda = 10^{6}$ を与えると、$\left\| \beta \right\|$ を小さくすることに夢中になって、本来の仕事―データをうまく説明するモデルを作ることが全くできなくなってしまいます。要点は、適切な $\lambda$ を選択する必要があるということですが、数式だけを見た場合、$\lambda$ が大きいか小さいか自体には特に良し悪しがないのです。

したがって、特別な直感や基準がない場合は、$\lambda$ を変えながら目的関数が最小になるものを選択することも一つの方法です。上の図は、ある分析で $\lambda$ を変えながらクロスバリデーションを行った後のエラーを $\lambda$ の関数値として描いたグラフです。¹ このグラフは $5 \times 10^{-1}$ の付近で最小値を持つことが縦の点線で示されており、特に理由がなければ $\lambda$ はその値を使用するのが妥当です。

リッジ回帰との違い

歴史的にリッジ^ridgeは1970年バイアス-バリアンストレードオフの関係で不偏性をある程度犠牲にしても少しのバイアスが生じることによりパラメーターの推定における効率性を向上させる方法として紹介され²、ラッソ^lASSOは1986年に地球物理学^geophysicsで初めて登場し、1996年に再紹介されてラッソという名前が付けられました。³

リッジ回帰の目的関数: $$\argmin_{\beta} \left( \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{2}^{2} \right)$$
라쏘 회귀의 목적함수: $$\argmin_{\beta} \left( \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right)$$

見ての通り、リッジ回帰とラッソ回帰の目的関数は非常に似ており、さまざまな点で関連していますが、正直なところ、似ているのは目的関数の形式的な見た目だけであり、これらの長所と短所を比較していること自体があまりにも単純化された視点かもしれません。一般的には、ペナルティ項が $l_{1}$ か $l_{2}$ か、微分可能で最適解が閉形式^{closed form}で簡単に表現できるかどうか、実際に係数を $0$ まで減らすことができるかどうかなど、リッジとラッソの違いについて多くの説明がされています。さらに詳しくなると、Pythonの例示コードが含まれ、経験的には通常どちらが優れているか、どのような場合には他の方がより良い可能性があるという言及が追加される傾向にあります。

…しかし、そのような説明は、書籍、ウィキペディア、ブログなどに溢れています。こうしたよく知られた事柄をきちんと整理した記事は、‘Ridge vs LASSO’とGoogleで検索すると簡単に見つかりますが、この投稿ではそれらよりも少し、ほんの少し深く入ってみようと考えています。

以下の内容は、ラッソ回帰の立場からリッジ回帰とどのように異なるかを説明します。リッジ回帰の立場からラッソ回帰をどのように見るかは該当の投稿で確認しましょう。

一般的に、ラッソ回帰のコストはリッジ回帰よりも高いとか、計算上複雑であるとよく説明されます。決して間違った指摘ではありませんが、そもそもペナルティ $\left\| \lambda \right\|$ を背負いながらスパース回帰をしたいのであれば、そのようなコストは問題にならないかもしれません。

上の図では $\hat{\beta}$ は元の最小二乗問題の最適解であり、左側はラッソ回帰($l_{1}$)、右側はリッジ回帰($l_{2}$)の解空間を直感的に示しています。⁴ このような幾何学的な説明は、前述のように ‘Ridge vs LASSO’ でGoogle画像検索をすると、その数を数えることができないほど多く、それだけで十分に良い説明です。

(左側) ラッソ: 回帰係数 $\beta_{1}$ と $\beta_{2}$ の絶対値がある値 $r$ と等しいということは、一辺の長さが $\sqrt{r}$ の正方形 $\left| \beta_{1} \right| + \left| \beta_{2} \right| = r$ 上のある点であるということです。BPDNの最適解は $\left\| Y - X \beta \right\|_{2}$ が作る等高線の中で最も低く、かつその正方形と重なる点でなければならず、図のように正確に軸上に位置することができます。解がある軸上にあるということは、他の次元のうち少なくとも一つ以上が $0$ になったことを意味するため、ラッソは特定の回帰係数を正確に $0$ にすることができます。
(右側) リッジ: 回帰係数 $\beta_{1}$ と $\beta_{2}$ の二乗がある値 $r$ と等しいということは、半径の長さが $r$ の円 $\beta_{1}^{2} + \beta_{2} ^{2} = r$ 上のある点であるということです。ラッソと同様に、特定のレベルの $r$ であっても $\hat{\beta}$ が作る等高線と円が交わる点は、ほぼ確実に軸上に位置することはありません。

もちろん、リッジ回帰もそれ自体で多くの良い意味を持っていますが、スパース回帰の文脈では、特定の係数を $0$ にできない方法と比較されること自体が奇妙です。⁵ 特定のタイプのデータでは、$\lambda$ を与えることによって、オーバーフィッティングの観点から、計算速度とシンプルさの観点から… そのすべての仮定が無意味になるかもしれません。リッジ回帰はできないことをラッソ回帰はできますし、根本的にこの違いを埋める方法はありません。ラッソかリッジかという比較は、長所と短所や些細な違いで判断するものではないということです。

結果だけを考えると、$\beta_{k} = 0$ と $\beta_{k} \approx 0$ はあまり違わないかもしれませんが、計算のプロセスまで考えると、$\beta_{k} = 0$ の独立変数 $X_{k}$ はそもそも除外できるという点が大きく異なります。もしリッジ回帰では $\beta_{k} \approx 0$ であっても、ラッソ回帰では確実に $\beta_{k} = 0$ となる変数が100万個程度ある場合、モデルとしてのパフォーマンスが似ていても、リッジ回帰は1つのデータポイントのフィッティングごとに100万回の乗算がさらに必要になるのです。

一方で、ラッソは実際に特定の条件下で最適解の閉形式^{closed form}が知られており、その最適解にソフトしきい値処理が使用されます。つまり、数式自体で $\beta_{k}$ を $0$ にする部分があり、ラッソ回帰を視覚的、直感的に頼らずに感覚を掴むには、以下のような数式的な議論を理解する必要があります。

公式

最適解 ⁶

$$ L \left( \beta \right) = {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} $$ $\lambda$ が定数として与えられている場合、ラッソ回帰の目的関数 $L$ を上記のように表します。一般的にラッソ回帰の最適解は閉形式^{closed form}がないのですが、$X$ の全ての列が互いに直交していると仮定すると、$\hat{\beta} = \argmin_{\beta} L \left( \beta \right)$ の $k$ 番目の成分 $\left( \hat{\beta} \right)_{k}$ は以下のようになります。 $$ \begin{align*} \left( \hat{\beta} \right)_{k} =& {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \eta_{\lambda} \left( X^{T} Y \right)_{k} \\ = & {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \begin{cases} \left( X^{T} Y \right)_{k} + \lambda & , \text{if } \left( X^{T} Y \right)_{k} < - \lambda \\ 0 & , \text{if } \left( X^{T} Y \right)_{k} \in [-\lambda, \lambda] \\ \left( X^{T} Y \right)_{k} - \lambda & , \text{if } \left( X^{T} Y \right)_{k} > \lambda \end{cases} \end{align*} $$ ここで $A^{T}$ は $A$ の転置行列、$A^{-1}$ は $A$ の逆行列であり、$\eta_{\lambda}$ はソフトしきい値処理です。

導出 ⁷

ベクトルと行列の勾配: $$ \frac{ \partial }{ \partial \mathbf{w} }\left( \mathbf{w}^{T}\mathbf{R}\mathbf{w} \right)= \left( \mathbf{R} + \mathbf{R}^{T} \right) \mathbf{w} $$

残差二乗和の勾配: $$ f \left( \mathbf{s} \right) := \left( \mathbf{y} - X \mathbf{s} \right)^{T} R \left( \mathbf{y} - X \mathbf{s} \right) $$ ベクトル $\mathbf{y} \in \mathbb{R}^{n}$ と行列 $X \in \mathbb{R}^{n \times p}$、$R \in \mathbb{R}^{n \times n}$ が $\mathbf{s}$ に依存しない場合、次のことが成り立ちます。 $$ {{ \partial f \left( \mathbf{s} \right) } \over { \partial \mathbf{s} }} = - X^{T} \left( R + R^{T} \right) \left( \mathbf{y} - X \mathbf{s} \right) $$

$R = I$ の場合、上記の公式を適用すると $$ \begin{align*} {{ \partial } \over { \partial \beta }} L \left( \beta \right) =& {{ \partial } \over { \partial \beta }} {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + {{ \partial } \over { \partial \beta }} \lambda \left\| \beta \right\| \\ =& {{ \partial } \over { \partial \beta }} {{ 1 } \over { 2 }} \left( Y - X \beta \right)^{T} \left( Y - X \beta \right) + \lambda {{ \partial } \over { \partial \beta }} \left\| \beta \right\| \\ =& - {{ 1 } \over { 2 }} X^{T} \left( I + I^{T} \right) \left( Y - X \beta \right) + \lambda {{ \partial } \over { \partial \beta }} \left\| \beta \right\| \\ =& - X^{T} \left( Y - X \beta \right) + \lambda {{ \partial } \over { \partial \beta }} \left\| \beta \right\| \\ =& - X^{T} Y + X^{T} X \beta + \lambda {{ \partial } \over { \partial \beta }} \left\| \beta \right\| \end{align*} $$ となり、$\beta = \hat{\beta}$ は ${{ \partial } \over { \partial \beta }} L = 0$ を満たさなければならないため、整理すると以下が得られます。 $$ X^{T} X \hat{\beta} = X^{T} Y - \lambda {{ \partial } \over { \partial \beta }} \left\| \beta \right\| $$ これで $k = 0, 1, \cdots, p$ に対して $\hat{\beta}_{k} := \left( \beta \right)_{k}$ を考えると、行列 $A$ の $i$ 番目の行を $\left( A \right)_{i \cdot}$ と表すと、 $$ \begin{align*} & X^{T} X \hat{\beta} = X^{T} Y - \lambda {{ \partial } \over { \partial \beta }} \left\| \beta \right\| \\ \implies & \left( X^{T} X \right)_{i \cdot} \hat{\beta} = \left( X^{T} Y \right)_{i} - \lambda {{ \partial } \over { \partial \hat{\beta}_{i} }} \sum_{j=0}^{p} \left| \beta_{j} \right| \\ \implies & \sum_{j=0}^{p} \left( X^{T} X \right)_{i j} \hat{\beta}_{j} = \left( X^{T} Y \right)_{i} - \lambda {{ \partial } \over { \partial \hat{\beta}_{i} }} \left| \hat{\beta}_{i} \right| \\ \implies & \hat{\beta}_{i} = {{ 1 } \over { \left( X^{T} X \right)_{ii} }} \left[ \left( X^{T} Y \right)_{i} - \lambda {{ \partial } \over { \partial \hat{\beta}_{i} }} \left| \hat{\beta}_{i} \right| - \sum_{j \ne i} \left( X^{T} X \right)_{i j} \hat{\beta}_{j} \right] \end{align*} $$ という方程式が得られます。$\hat{\beta}_{i}$ が他の $\hat{\beta}_{j}$ に依存しているため、この解を閉形式とは言えませんが、$\left( X^{T} X \right)_{i j} = 0$ の場合、$\hat{\beta}_{j}$ を考慮する必要がないことがわかります。したがって、$X$ の列が直交するという仮定を追加すると、$X$ の列が直交するということは $X^{T} X$ が対角行列であることを意味します。

$\hat{\beta}_{k}$ は正、負、または $0$ のいずれかです。もし $\hat{\beta}_{k} > 0$ であれば、 $$ \begin{align*} & \hat{\beta}_{k} > 0 \\ \implies & \hat{\beta}_{k} = {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \left[ \left( X^{T} Y \right)_{k} - \lambda {{ \partial } \over { \partial \hat{\beta}_{k} }} \left| \hat{\beta}_{k} \right| \right] > 0 \\ \implies & \hat{\beta}_{k} = {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \left[ \left( X^{T} Y \right)_{k} - \lambda \right] > 0 \end{align*} $$ となるため、$\hat{\beta}_{k} > 0$ であるだけでなく、$\left( X^{T} Y \right)_{k} > \lambda$ でなければなりません。同様に $\hat{\beta}_{k} < 0$ であれば、 $$ \begin{align*} & \hat{\beta}_{k} < 0 \\ \implies & \hat{\beta}_{k} = {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \left[ \left( X^{T} Y \right)_{k} - \lambda (-1) \right] > 0 \\ \implies & \hat{\beta}_{k} = {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \left[ \left( X^{T} Y \right)_{k} + \lambda \right] < 0 \end{align*} $$ となるため、$\left( X^{T} Y \right)_{k} < - \lambda$ でなければなりません。その他の場合は $\hat{\beta}_{k} = 0$ であり、以下のようにソフトしきい値処理を通じて要約できます。 $$ \begin{align*} \hat{\beta}_{k} =& {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \begin{cases} \left( X^{T} Y \right)_{k} + \lambda & , \text{if } \left( X^{T} Y \right)_{k} < - \lambda \\ 0 & , \text{if } \left( X^{T} Y \right)_{k} \in [-\lambda, \lambda] \\ \left( X^{T} Y \right)_{k} - \lambda & , \text{if } \left( X^{T} Y \right)_{k} > \lambda \end{cases} \\ = & {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \eta_{\lambda} \left( X^{T} Y \right)_{k} \end{align*} $$

■

アルゴリズム

$$ \hat{\beta}_{i} = {{ 1 } \over { \left( X^{T} X \right)_{ii} }} \left[ \left( X^{T} Y \right)_{i} - \lambda {{ \partial } \over { \partial \hat{\beta}_{i} }} \left| \hat{\beta}_{i} \right| - \sum_{j \ne i} \left( X^{T} X \right)_{i j} \hat{\beta}_{j} \right] $$ 導出過程で既に確認したように、暗黙的^implicitな方程式があるだけであっても、$\hat{\beta}_{j}$ を求めることができないという意味ではありません。勾配降下法などの反復的^iterativeなアルゴリズムを用いて近似解を求めることができます。⁸ BPDNを見ただけでは、一般的な最適化問題とは異なり、求めた解を検証する方程式があるため、状況は比較的良好です。一方で、勾配降下法を使用する場合であっても、$X$ の列が適切に直交している場合は、上記の公式で得られる最適解を初期値として使用することができます。変数間の独立性に問題がある場合、その問題をラッソの欠点として指摘するのは困難です。