【本記事の内容】L1正則化を初学者向けに説明
今回は初学者向けに「L1正則化」を説明していきます。
また、L1正則化による回帰では「なぜスパース性をもつのか」についても幾何学的解釈を用いて説明していきます。
本記事は前回の記事の続きになります。
【目次】
L1正則化とは
L1正則化
まず、正則化とは機械学習において、モデルの過学習を抑えるために損失関数（誤差関数）に正則化項を導入する手法のことを言います。
「L1正則化（またはLasso）」とは、特に正則化項（罰則項）として「L1ノルム」を採用した正則化のことを言います。
・L1正則化 :
$$ S_{\lambda}(\boldsymbol{\beta}) = f(\boldsymbol{\beta}) + \lambda \sum_{j=0}^{p} |\boldsymbol{\beta}_j|\\
$$
- \(\boldsymbol{\beta} = (\beta_0,\beta_1, … , \beta_p)^T \) : 回帰係数ベクトル（これが求めたいもの！！！）
- \(S_{\lambda}(\boldsymbol{\beta})\) : コスト関数(=損失関数+正則化項）
- \(f(\boldsymbol{\beta})\) : 損失関数（誤差関数）
- \(\lambda （≧0）\) : 正則化パラメータ →この値が大きいほど（モデルの複雑さに）より強いペナルティを与える
- \(\lambda \sum_{j=0}^{p} |\boldsymbol{\beta}_i|\) : 正則化項（罰則項）→ モデルの複雑さ（回帰係数の大きさ）にペナルティを科すことで過学習を抑制している ; \(\beta_i 大\) →コスト大
L1正則化の特徴（長所・短所）
【長所】
- 過学習を抑制できる
- 変数選択と推定が同時に行える
→スパース性（回帰係数の多くを0と推定する性質）をもつため、0と推定された回帰係数に対応する変数を重要でないと考えることで、変数選択にも使うことができます。
【短所】
- 解析的に（回帰係数の）解を求めることができない
https://tjo.hatenablog.com/entry/2015/03/03/190000 から引用
Lasso回帰(重回帰分析+L1正則化)
L1正則化を用いた回帰のことを「Lasso回帰」と言います。
今回は特に重回帰分析にL1正則化を用いた例を取り上げます。
設定
データ
| サンプルNo | 説明変数\(x_1\) | 説明変数\(x_2\) | … | 説明変数\(x_p\) | 目的変数\(y\) |
| 1 | \(x_{11}\) | \(x_{21}\) | … | \(x_{p1}\) | \(y_{1}\) |
| 2 | \(x_{12}\) | \(x_{22}\) | … | \(x_{p2}\) | \(y_{2}\) |
| … | … | … | … | … | … |
| \(n\) | \(x_{1n}\) | \(x_{2n}\) | … | \(x_{pn}\) | \(y_{n}\) |
詳しくは前々回の記事を参照ください。（具体例などが載っています。）
設定
- 説明変数（入力）を標準化
→これにより罰則項（正則化項）から切片\(\beta_0\)を除いて議論することができます。
→実用上では、スケーリングをそろえて精度を出すために説明変数（入力）の標準化は必須です。
※標準化は平均を0,分散を1にする変換のことを言います。
- 入力サンプル数 : \(n\)
- 説明変数の個数 : \(p\)
- 目的変数ベクトル : \(\boldsymbol{y}=(y_1, … ,y_n)^T\)
- 説明変数行列 :
$$\boldsymbol{X}=\begin{pmatrix} x_{11} & … & x_{p1}\\ x_{12} & … & x_{p2} \\ … & … & … \\ x_{1n} & … & x_{pn}\end{pmatrix} $$
→\(\beta_0\)は別で推定するため、前々回の記事で説明した「説明変数行列」の1列目の「要素1のみをもつn×1ベクトル」を省きます。
- 回帰係数ベクトル : \( \boldsymbol{\beta}=(\beta_1, … ,\beta_p)^T\)
→\(\beta_0\)は別で推定します。
コスト関数（=損失関数（誤差関数)+正則化項）
$$ S_{\lambda}(\boldsymbol{\beta}) = \sum_{i=1}^{n} \{y_i – (\beta_0 +\beta_1 x_{1i} + … + \beta_px_{pi}) \}^2 + \lambda \sum_{j=1}^{p}| \boldsymbol{\beta}_j| $$
回帰係数の最適化問題の式表現
$$ \hat{\boldsymbol{\beta}} = argmin_{~\beta} ~[~ \sum_{i=1}^{n} \{y_i – (\beta_0 + \beta_1 x_{1i} + … + \beta_px_{pi}) \}^2 + \lambda \sum_{j=1}^{p} |\boldsymbol{\beta}_j| ~] $$
あるいは、等価な式として以下の式で書ける。
$$ \hat{\boldsymbol{\beta}} = argmin_{~\beta} ~[~ \sum_{i=1}^{n} \{y_i – (\beta_0 + \beta_1 x_{1i} + … + \beta_px_{pi}) \}^2 ~]$$
$$ subject ~~to ~~ \sum_{j=1}^{p} |\boldsymbol{\beta}_j| ≦ t $$
ただし、
・回帰係数ベクトル : \(\hat{\boldsymbol{\beta}}=(\beta_1, … ,\beta_p)^T\)
・\(arg min_{~\beta} ~f\) : \(f\)を最小にする\(\boldsymbol{\beta}\)
・\(subject ~to\) : 制約条件
※上の最適化問題の式は「Lagrange form（ラグランジェ形式）」と呼ぶこともあります。（下の最適化問題を「Lagrangeの未定乗数法」を使うことで上式の最適化問題に帰着させることができることに由来します。）
回帰係数の推定方法
Lasso回帰は、Ridge回帰と異なり解析的に解が求まらない（式変形を繰り返し行うことで求まらない）ので、数値計算的に解くことによって解を推定します。
以下にその推定アルゴリズムのいくつかを載せます。（太字のアルゴリズムはよく使われているものです。）
【Lassoの推定アルゴリズム】
- Shooting アルゴリズム
- LARS(最小角回帰)
- CD法(Coordinate Descent,座標降下法)
- 交互方向乗数法
参考文献 : スパースモデリング、スパースコーディングとその数理(第11回WBA若手の会)
CD法(座標降下法）
ここでは推定アルゴリズムの中でもよく使われるCD法について簡単に説明します。
CDでは，各パラメータ \( (\beta_1, … ,\beta_p) \) 毎に誤差関数を微分して更新式を得て，それを用いて更新を繰り返し行うことにより，収束した最適な推定値得ることができます.
Lassoの理論と実装 -スパースな解の推定アルゴリズム- から引用
また、CD法は「アルゴリズムが単純」であり「計算量が最小二乗推定とほぼ変わらない」ため、よく使われるアルゴリズムとなっています。
【アルゴリズム】
スパースモデリング、スパースコーディングとその数理(第11回WBA若手の会) p67 から引用
※自分の説明に合わせると\(wは\beta\)に対応します。
より詳しい説明は
- A Coordinate Descent Algorithm for the Lasso Problem – Jocelyn T. Chi
- lecture 24: coordinate descent – YouTube (カーネギーメロン大学の凸最適化の講義動画)
にあります。
Lassoの派生形
Lassoには派生形も多くあり、具体的には以下のようなものがあります。
- Elastic Net
- Grouped Lasso
- Fused Lasso
- Adaptive Lasso
など
なぜLassoはスパース性をもつのか
Lassoの最大の特徴は「スパース性」をもつことで変数選択と推定を同時に行えることです。
そこでここでは「どうしてLassoがスパース性をもつのか」を幾何学的解釈を交えつつ説明したいと思います。
結論を最初に言うと、
「Lassoの解は幾何学的に解釈すると、制約領域の角、すなわち解が軸上に落ちやすい」ため、スパース性をもつ
と考えられます。
以下で具体的に説明していきます。
まず、説明するにあたって「最適化問題の数式表現」と「等高線」について確認しておきましょう。
以下では、問題を分かりやすくするために 「p = 2」 として説明していきます。
※ここで説明する理由は「厳密な数学的な証明」ではなく「幾何学的解釈による直感的な説明」であることをご了承ください。
Lassoの最適化問題の式表現
$$ \hat{\boldsymbol{\beta}} = argmin_{~\beta} ~[~ \sum_{i=1}^{n} \{y_i – (\beta_0 + \beta_1 x_{1i} + … + \beta_px_{pi}) \}^2 ~] ・・・①$$
$$ subject ~~to ~~ \sum_{j=1}^{p} |\boldsymbol{\beta}_j| ≦ t ・・・②$$
→この最適化問題は
$$ f(\boldsymbol{\beta}) = ~ \sum_{i=1}^{n} \{y_i – (\beta_0 + \beta_1 x_{1i} + \beta_2x_{2i}) \}^2 ~$$
\begin{eqnarray}
f(\beta_1,\beta_2) &=& ~ \sum_{i=1}^{n} \{y_i – (\beta_0 + \beta_1 x_{1i} + \beta_2x_{2i}) \}^2 ~\\
&=& A_0 + A_1(\beta_1)^2+A_2(\beta_2)^2+A_3(\beta_1\beta_2)\\
\end{eqnarray}
※\(A_0, A_1, A_2, A_3\)は定数。
※（補足）\(\beta_1 ,\beta_2\)以外は定数なのでこのような式で書くことができます。
の最小値をとる \(\beta_1,\beta_2\)を求めよ。
ただし、
$$ |\boldsymbol{\beta}_1| + |\boldsymbol{\beta}_1| ≦ t $$
を満たすものとする。
という問題ととらえることができます。
3Dplot
\((A_0, A_1, A_2, A_3) = (2,3,4,5)\)としたときの
関数\(f = 2 + 3 \beta_1^{~2}+4 \beta_2^{~2}+5 \beta_1\beta_2 \)
のグラフは以下のようになります。
※\(x が \beta_1 , yが\beta_2\)に対応しています。
※\(A_0, A_1, A_2, A_3\)の値を変えても、式の形が似ているので、似たような概形になります。
※WolframAlpha によるプロット
等高線
同様に\((A_0, A_1, A_2, A_3) = (2,3,4,5)\)としたときの関数\(f\)の等高線は以下のようになります。
【補足】等高線の見方
等高線は「関数\(f\)をxy平面に射影したときの様子」を「z座標の値（関数の値）と一緒に」表します。
この上の等高線の見方としては、「3Dplotのへこんでる部分」が「z座標の値（関数の値）の小さいところ」であり「等高線の内側の部分」に対応します。
また、等高線の同じ色の部分は「関数の値が同じ」です。
まとめると、
- 等高線の内側ほど、関数の値が小さい
- 等高線の同じ色は同じ関数の値を表す
ということになります。
なぜLassoはスパース性をもつのか
上記の最適化問題の置き換えにより、Lassoの最適化問題の解は以下の左図において、「等高線のなるべく内側にある」かつ「正方形の内部（②式で表される）にある」点が解となります。
https://towardsdatascience.com/regularization-in-machine-learning-76441ddcf99a から引用
左図をみてもわかる通り、解は「正方形の端っこ」にぶつかりやすい状況にあります。（等高線の形状は、問題によって変わるのが、定数\(A_i\)の部分のみなのでそれほど大きく変わることはないです。）
「正方形の端っこ」では\(\beta_1 = 0 または\beta_2 = 0\)となる、すなわち解がスパースになります。
これは一般に高次元でも成り立ちます。
まとめると、「Lassoの解は幾何学的に解釈すると、制約領域の角、すなわち解が軸上に落ちやすい」ため、スパース性をもつと考えられます。
※ちなみに、右図はRidgeの幾何学的解釈の図になります。
参考文献
【参考サイト】
次回予告
次回の勉強まとめは「決定木」になると思います。
その後はよく決めていませんが、「数学の勉強」かまた「機械学習手法の勉強」のまとめをあげるかもしれないです。（そもそも、もうすぐ夏休み終わって卒論とかあるので、そっちが忙しくて手が回らなくなるかもしれませんが）
何かあればコメント欄にてお待ちしています。
コメント