ラッソ回帰とは?

定義

$$ \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}$は絶対値の和である。

説明

ラッソはその名前のとおり回帰問題において回帰係数^operatorの絶対値^absoluteを収縮^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の例題コードが含まれ、経験的には普通どちらが優れている、ある場合には別のものがより良いことがあるという言及が追加される具合である。

… しかしそういった説明は各種の本、ウィキペディア、ブログなどにあり余るほど溢れている。このようによく知られたものをきれいに整理した文章はGoogleで「Ridge vs LASSO」と検索すれば簡単に見つけることができ、このポストでは我々はそれらより少しだけ、ほんの少しだけ深く入り込んでみようとする。

以下の内容はラッソ回帰の立場からリッジ回帰とどう違うのかを説明する。リッジ回帰の立場からラッソ回帰をどう見るかは当該のポストで確認しよう。

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

上の図で$\hat{\beta}$は元の最小二乗問題の最適解であり、左はラッソ回帰($l_{1}$)、右はリッジ回帰($l_{2}$)の解空間を直観的に示している⁴。このように幾何的にする説明は、先に言及したようにGoogleで「Ridge vs LASSO」と画像検索をすればその数を数えきれないほど多く、それほどに良い説明である。

(左)ラッソ: 回帰係数$\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万個ほどあるとすれば、モデルとしてのパフォーマンスは似ていてもリッジ回帰は一つのデータポイントのフィッティングごとに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{s}$に従属しないベクトル$\mathbf{y} \in \mathbb{R}^{n}$と行列$X \in \mathbb{R}^{n \times p}$, $R \in \mathbb{R}^{n \times n}$に対して次が成り立つ。 $$ {{ \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$より大きいか、小さいか、$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$の列がまずまず直交するなら上の公式で得る最適解を初期点として使えそうでもある。どうせ変数どうしの独立性に問題があったのなら、それをラッソの欠点だと指摘するのは難しい。