正規化最小二乗法

正規化最小二乗法( RLS ) は、正規化を使用して結果の解をさらに制約し ながら最小二乗問題を解く一連の手法です。

RLS が使用される主な理由は 2 つあります。1 つ目は、線形システムの変数の数が観測数を超える場合です。このような設定では、通常の最小二乗問題は不適切であり、関連する最適化問題に無限の解があるため、適合させることができません。RLS を使用すると、解を一意に決定する追加の制約を導入できます。

RLS を使用する 2 番目の理由は、学習したモデルの一般化が不十分な場合に発生します。このような場合、RLS はトレーニング時に制約を課すことでモデルの一般化可能性を向上させるために使用できます。この制約により、ソリューションが何らかの方法で「スパース」になるように強制するか、機能間の相関関係に関する情報など、問題に関するその他の事前知識を反映することができます。これに対するベイジアン理解は、RLS 方法が多くの場合、最小二乗問題のソリューションの 事前情報と同等であることを示すことによって得られます。

確率空間、によって与えられる学習設定を考えます。 は、結合分布 に関するペア iidのトレーニング セットを表します。は損失関数とします。 を、期待されるリスクが明確に定義される関数の空間として 定義します 。 主な目標は、期待されるリスクを最小限に抑えることです。 問題を正確に解決することはできないため、ソリューションの品質を測定する方法を指定する必要があります。 優れた学習アルゴリズムは、リスクの小さい推定値を提供する必要があります。 ${\displaystyle (X\times Y,\rho (X,Y))}$${\displaystyle Y\in R}$${\displaystyle S=\{x_{i},y_{i}\}_{i=1}^{n}}$${\displaystyle n}$${\displaystyle \rho }$${\displaystyle V:Y\times R\to [0;\infty )}$${\displaystyle F}$$${\displaystyle \varepsilon (f)=\int V(y,f(x))\,d\rho (x,y)}$$$${\displaystyle \inf _{f\in F}\varepsilon (f)}$$

結合分布は通常は不明なので、経験的リスクが取られます。正規化された最小二乗法では、二乗損失関数が導入されます。 ${\displaystyle \rho }$$${\displaystyle \varepsilon (f)={\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},f(x_{i}))={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}$$

しかし、関数が 上の二乗積分可能な関数の集合のような比較的制約のない空間からのものである場合、このアプローチはトレーニング データに過剰適合し、一般化が不十分になる可能性があります。したがって、関数 の複雑さを何らかの形で制約するか、ペナルティを課す必要があります。RLS では、これは再生核ヒルベルト空間 (RKHS) から関数を選択し、 における関数のノルムに比例する正則化項を目的関数に追加することによって実現されます。 ${\displaystyle X}$${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}}$$${\displaystyle \inf _{f\in F}\varepsilon (f)+\lambda R(f),\lambda >0}$$

RKHS は、再生特性を持つ 対称 正定値カーネル関数 によって定義できます。 ここで。カーネルの RKHS は、によって張られる関数の空間の完備化で構成されます。ここで、すべては実数です。一般的に使用されるカーネルには、線形関数の空間を誘導する線形カーネル 、次数の多項式関数の空間を誘導する多項式カーネル、 およびガウスカーネルがあります。 ${\displaystyle K(x,z)}$$${\displaystyle \langle K_{x},f\rangle _{\mathcal {H}}=f(x),}$$${\displaystyle K_{x}(z)=K(x,z)}$${\displaystyle K}$${\displaystyle \left\{K_{x}\mid x\in X\right\}}$${\textstyle f(x)=\sum _{i=1}^{n}\alpha _{i}K_{x_{i}}(x),\,f\in {\mathcal {H}}}$${\displaystyle \alpha _{i}}$$${\displaystyle K(x,z)=x^{\mathsf {T}}z,}$$${\displaystyle d}$$${\displaystyle K(x,z)=\left(x^{\mathsf {T}}z+1\right)^{d},}$$$${\displaystyle K(x,z)=e^{-{\left\|x-z\right\|^{2}}/{\sigma ^{2}}}.}$$

任意の損失関数に対して、このアプローチは Tikhonov 正則化と呼ばれるアルゴリズムの一般的なクラスを定義することに注意してください。たとえば、ヒンジ損失を使用するとサポート ベクター マシンアルゴリズムが実現され、イプシロン非感受性損失を使用するとサポート ベクター回帰が実現されます。 ${\displaystyle V}$

代表者定理は、ある に対して、解が次のように記述できることを保証します 。 $${\displaystyle f(x)=\sum _{i=1}^{n}c_{i}K(x_{i},x)}$$${\displaystyle c\in \mathbb {R} ^{n}}$

最小化問題は次のように表現できます。 ここで、表記法を多少乱用すると、カーネル行列のエントリ（カーネル関数ではなく）は になります。 $${\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\left\|Y-Kc\right\|_{\mathbb {R} ^{n}}^{2}+\lambda \left\|f\right\|_{H}^{2},}$$${\displaystyle i,j}$${\displaystyle K}$${\displaystyle K(\cdot ,\cdot )}$${\displaystyle K(x_{i},x_{j})}$

このような機能の場合、 $${\displaystyle {\begin{aligned}\left\|f\right\|_{H}^{2}&=\langle f,f\rangle _{H}\\[1ex]&=\left\langle \sum _{i=1}^{n}c_{i}K(x_{i},\cdot ),\sum _{j=1}^{n}c_{j}K(x_{j},\cdot )\right\rangle _{H}\\[1ex]&=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}\left\langle K(x_{i},\cdot ),K(x_{j},\cdot )\right\rangle _{H}\\&=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})\\&=c^{\mathsf {T}}Kc,\end{aligned}}}$$

次の最小化問題が得られます。 $${\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\left\|Y-Kc\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}Kc.}$$

凸関数の和は凸であるため、解は一意であり、その最小値はに対する勾配を に設定することによって見つけることができます。 ここで${\displaystyle c}$${\displaystyle 0}$$${\displaystyle -{\frac {1}{n}}K\left(Y-Kc\right)+\lambda Kc=0\Rightarrow K\left(K+\lambda nI\right)c=KY\Rightarrow c=\left(K+\lambda nI\right)^{-1}Y,}$$${\displaystyle c\in \mathbb {R} ^{n}.}$

トレーニングの複雑さは、基本的にカーネル行列の計算コストと線形システムを解くコストの合計で、これはおよそ です。線形カーネルまたはガウスカーネルのカーネル行列の計算は です。テストの複雑さは です。 ${\displaystyle O(n^{3})}$${\displaystyle O(n^{2}D)}$${\displaystyle O(n)}$

新しいテストポイントでの予測は次のとおりです。 ${\displaystyle x_{*}}$$${\displaystyle f(x_{*})=\sum _{i=1}^{n}c_{i}K(x_{i},x_{*})=K(X,X_{*})^{\mathsf {T}}c}$$

便宜上、ベクトル表記が導入されています。を行列とし、行を入力ベクトル、エントリを対応する出力とするベクトルとします。ベクトルでは、カーネル行列は と表記できます。学習関数は次のように表記できます。 ${\displaystyle X}$${\displaystyle n\times d}$${\displaystyle Y}$${\displaystyle n\times 1}$${\displaystyle K=XX^{\mathsf {T}}}$$${\displaystyle f(x_{*})=K_{x_{*}}c=x_{*}^{\mathsf {T}}X^{\mathsf {T}}c=x_{*}^{\mathsf {T}}w}$$

ここで を定義します。目的関数は次のように書き直すことができます。 ${\displaystyle w=X^{\mathsf {T}}c,w\in \mathbb {R} ^{d}}$$${\displaystyle {\begin{aligned}{\frac {1}{n}}\left\|Y-Kc\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}Kc&={\frac {1}{n}}\left\|y-XX^{\mathsf {T}}c\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}XX^{\mathsf {T}}c\\[1ex]&={\frac {1}{n}}\left\|y-Xw\right\|_{\mathbb {R} ^{n}}^{2}+\lambda \left\|w\right\|_{\mathbb {R} ^{d}}^{2}\end{aligned}}}$$

最初の項は、残差平方和に対応する、通常の最小二乗法(OLS) 回帰からの目的関数です。2 番目の項は、OLS には存在しない正則化項であり、大きな値にペナルティを課します。滑らかな有限次元の問題が考慮されるため、標準的な微積分ツールを適用できます。目的関数を最小化するために、勾配は に関して計算され、ゼロに設定されます。 ${\displaystyle w}$${\displaystyle w}$$${\displaystyle X^{\mathsf {T}}Xw-X^{\mathsf {T}}y+\lambda nw=0}$$ $${\displaystyle w=\left(X^{\mathsf {T}}X+\lambda nI\right)^{-1}X^{\mathsf {T}}y}$$

この解は、項 を追加した標準的な線形回帰の解によく似ています。OLS 回帰の仮定が成り立つ場合、を伴う解 は不偏推定量であり、ガウス・マルコフの定理によれば、 は最小分散線形不偏推定量です。したがって、項 は偏った解につながりますが、分散を減らす傾向もあります。これは、 -値の共分散行列が に比例し、したがって の値が大きいほど分散が低くなることから簡単にわかります。したがって、 を操作することは、バイアスと分散のトレードオフに対応します。が比較的小さい場合や相関のある回帰変数の場合など、分散の大きい推定値を持つ問題では、非ゼロの を使用し、分散を減らすためにバイアスを導入することで、最適な予測精度が得られる場合があります。さらに、機械学習ではの場合が珍しくなく、その場合は がランク不足であり、を計算するために非ゼロが必要になります。 ${\displaystyle \lambda I}$${\displaystyle w=\left(X^{\mathsf {T}}X\right)^{-1}X^{\mathsf {T}}y}$${\displaystyle \lambda =0}$${\displaystyle \lambda nI}$${\displaystyle w}$${\displaystyle \left(X^{\mathsf {T}}X+\lambda nI\right)^{-1}}$${\displaystyle \lambda }$${\displaystyle \lambda }$${\displaystyle w}$${\displaystyle n}$${\displaystyle \lambda }$${\displaystyle n<d}$${\displaystyle X^{\mathsf {T}}X}$${\displaystyle \lambda }$${\displaystyle \left(X^{\mathsf {T}}X+\lambda nI\right)^{-1}}$

パラメータ は、行列 の可逆性を制御します。上記の線形システムを解くにはいくつかの方法を使用できますが、行列 が対称で正定値であるため、コレスキー分解がおそらく最適な方法です。この方法の複雑さは、トレーニングとテストのためです。コストは基本的に を計算するコストですが、逆計算 (または線形システムの解) はおよそ です。 ${\displaystyle \lambda }$${\displaystyle X^{\mathsf {T}}X+\lambda nI}$${\displaystyle X^{\mathsf {T}}X+\lambda nI}$${\displaystyle O(nD^{2})}$${\displaystyle O(D)}$${\displaystyle O(nD^{2})}$${\displaystyle X^{\mathsf {T}}X}$${\displaystyle O(D^{3})}$

このセクションでは、RLS を任意の種類の再生カーネル K に拡張する方法を示します。線形カーネルの代わりに、特徴空間と呼ばれるヒルベルト空間 の特徴マップが考慮されます。この場合、カーネルは次のように定義されます。行列は、 または の- 番目の要素である新しいデータ行列 に置き換えられます。 これは、指定されたトレーニング セット に対して であることを意味します。したがって、目的関数は次のように記述できます。 ${\displaystyle \Phi :X\to F}$${\displaystyle F}$${\displaystyle X}$${\displaystyle \Phi }$${\displaystyle \Phi _{ij}=\varphi _{j}(x_{i})}$${\displaystyle j}$${\displaystyle \varphi (x_{i})}$$${\displaystyle K(x,x')=\langle \Phi (x),\Phi (x')\rangle _{F}.}$$${\displaystyle K=\Phi \Phi ^{\mathsf {T}}}$$${\displaystyle \min _{c\in \mathbb {R} ^{n}}\left\|Y-\Phi \Phi ^{\mathsf {T}}c\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}\Phi \Phi ^{\mathsf {T}}c.}$$

このアプローチはカーネル トリックとして知られています。この手法により、計算操作を大幅に簡素化できます。が高次元の場合、計算はかなり集中的になる可能性があります。カーネル関数の明示的な形式がわかっている場合は、カーネル マトリックスを計算して保存するだけで済みます。 ${\displaystyle F}$${\displaystyle \varphi (x_{i})}$${\displaystyle n\times n}$${\displaystyle K}$

実際、ヒルベルト空間は と同型である必要はなく、無限次元になることができます。これは、連続、対称、正定値カーネル関数は、およびの正規直交基底を形成する と述べる マーサーの定理に従っています。特徴マップがコンポーネント で定義されている場合、 が成り立ちます。これは、任意のカーネルを特徴マップに関連付けることができ、RLS が一般に、おそらくより高次元の特徴空間で実行される線形 RLS で構成されることを示しています。マーサーの定理は、カーネルに関連付けることができる 1 つの特徴マップを示していますが、実際には複数の特徴マップを特定の再生カーネルに関連付けることができます。たとえば、マップは任意の再生カーネルの プロパティ を満たします。${\displaystyle F}$${\displaystyle \mathbb {R} ^{m}}$$${\displaystyle K(x,z)=\sum _{i=1}^{\infty }\sigma _{i}e_{i}(x)e_{i}(z)}$$${\displaystyle e_{i}(x)}$${\displaystyle \ell ^{2}(X)}$${\displaystyle \sigma _{i}\in \mathbb {R} }$${\displaystyle \varphi (x)}$${\displaystyle \varphi _{i}(x)={\sqrt {\sigma _{i}}}e_{i}(x)}$${\displaystyle K(x,z)=\langle \varphi (x),\varphi (z)\rangle }$${\displaystyle \varphi (x)=K_{x}}$${\displaystyle K(x,z)=\langle \varphi (x),\varphi (z)\rangle }$

最小二乗法は、残差が正規分布するという仮定の下での尤度最大化と見なすことができます。これは、ガウス分布の指数がデータ内で 2 次関数であり、最小二乗目的関数も 2 次関数であるためです。このフレームワークでは、RLS の正則化項は上の事前分布をエンコードするものと理解できます。たとえば、Tikhonov 正則化は、0 を中心とする 上の正規分布事前分布に対応します。これを確認するには、まず、各サンプルがの周りに正規分布している場合、 OLS 目的関数は対数尤度関数に比例することに注目してください。次に、0 を中心とする 上の正規事前分布がという形式の対数確率を持つことに注目してください。ここで、およびは事前分布の分散に依存する定数であり、 とは独立しています。したがって、尤度の対数と事前分布を乗じたものを最小化することは、OLS 損失関数とリッジ回帰正則化項の合計を最小化することと同じです。 ${\displaystyle w}$${\displaystyle w}$${\displaystyle y^{i}}$${\displaystyle w^{\mathsf {T}}\cdot x^{i}}$${\displaystyle w}$$${\displaystyle \log P(w)=q-\alpha \sum _{j=1}^{d}w_{j}^{2}}$$${\displaystyle q}$${\displaystyle \alpha }$${\displaystyle w}$

これにより、ティホノフ正規化が最小二乗問題に一意の解をもたらす理由について、より直感的な解釈が得られます。データから取得された制約を満たすベクトルは無限にありますが、原点の周りに正規分布している事前の信念を持って問題に取り組むため、この制約を念頭に置いて解を選択することになります。 ${\displaystyle w}$${\displaystyle w}$

他の正規化方法は異なる事前分布に対応します。詳細については、以下のリストを参照してください。

ペナルティ関数の特に一般的な選択肢の 1 つは、2 乗ノルム、つまり、 です 。これは、ティホノフ正規化やリッジ回帰 と呼ばれることがよくあります。これは、 の閉じた形式の解を許容します。 リッジ回帰という名前は、項がサンプル共分散行列の対角線の「リッジ」に沿って正のエントリを追加する という事実を暗示しています。 ${\displaystyle R}$${\displaystyle \ell _{2}}$$${\displaystyle R(w)=\sum _{j=1}^{d}w_{j}^{2}}$$ $${\displaystyle {\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda \sum _{j=1}^{d}\left|w_{j}\right|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$$${\displaystyle w}$$${\displaystyle w=\left(X^{\mathsf {T}}X+\lambda I\right)^{-1}X^{\mathsf {T}}Y}$$${\displaystyle \lambda I}$ ${\displaystyle X^{\mathsf {T}}X}$

のとき、すなわち、通常の最小二乗法の場合、サンプル共分散行列がフルランクを持たない条件が成立し、そのため逆行列をとおして一意の解を得ることができません。これが、 のときに通常の最小二乗法の問題に無限の解が存在する可能性がある理由です。しかし、 のとき、すなわち、リッジ回帰を使用する場合、サンプル共分散行列に を加えることで、そのすべての固有値が 0 より大きくなることが保証されます。言い換えると、逆行列が成立し、解が一意になります。 ${\displaystyle \lambda =0}$${\displaystyle d>n}$ ${\displaystyle X^{\mathsf {T}}X}$${\displaystyle d>n}$${\displaystyle \lambda >0}$${\displaystyle \lambda I}$

通常の最小二乗法と比較すると、リッジ回帰は偏りがありません。分散と平均二乗誤差を減らすために、バイアスを受け入れます。

最小絶対選択と縮小（LASSO）法も人気の選択肢です。LASSO回帰では、LASSOペナルティ関数が標準であり、つまり ${\displaystyle R}$${\displaystyle \ell _{1}}$$${\displaystyle R(w)=\sum _{j=1}^{d}\left|w_{j}\right|}$$ $${\displaystyle {\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda \sum _{j=1}^{d}|w_{j}|\rightarrow \min _{w\in \mathbb {R} ^{d}}}$$

lasso ペナルティ関数は凸関数ですが、厳密には凸関数ではないことに注意してください。Tikhonov正則化とは異なり、この方式には便利な閉形式の解はありません。代わりに、解は通常、2 次計画法またはより一般的な凸最適化法、および最小角度回帰アルゴリズムなどの特定のアルゴリズムを使用して見つけられます。

Lasso 回帰と Tikhonov 正則化の重要な違いは、Lasso 回帰では、 のより多くのエントリが実際に 0 に等しくなるように強制されることです。対照的に、Tikhonov 正則化では のエントリが小さくなるように強制されますが、 のエントリの多くが 0 に等しくなるように強制されることはありません。したがって、 の非ゼロ エントリの数が少ないと予想される場合は、LASSO 正則化の方が Tikhonov 正則化よりも適切であり、 のエントリが一般に小さいが必ずしも 0 ではないと予想される場合は、Tikhonov 正則化の方が適切です。これらのレジームのどちらがより適切であるかは、手元にある特定のデータ セットによって異なります。 ${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$

上で説明した特徴選択の他に、LASSOにはいくつかの制限があります。リッジ回帰は、相関の高い変数の場合に優れた精度を提供します。^[1]別のケースでは、LASSOは最大で 個の変数を選択します。さらに、LASSOは相関の高いサンプルのグループからいくつかの任意の変数を選択する傾向があるため、グループ化効果はありません。 ${\displaystyle n>d}$${\displaystyle n<d}$${\displaystyle n}$

$${\displaystyle {\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda \left\|w_{j}\right\|_{0}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$$ スパース性を強化する最も極端な方法は、 の係数の実際の大きさは重要ではないと言うことです。むしろ、 の複雑さを決定するのは非ゼロのエントリの数だけです。これは、を のノルムに設定することに相当します。この正規化関数は、それが保証するスパース性のために魅力的ですが、弱凸 でさえない関数の最適化が必要になるため、解決が非常に困難です。Lasso 回帰は、弱凸最適化問題を生成するペナルティ の可能な限り最小限の緩和です。${\displaystyle w}$${\displaystyle w}$${\displaystyle R(w)}$${\displaystyle \ell _{0}}$${\displaystyle w}$${\displaystyle \ell _{0}}$

任意の非負の場合、目的関数は次の形式になります。 ${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{2}}$$${\displaystyle {\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda _{1}\sum _{j=1}^{d}\left|w_{j}\right|+\lambda _{2}\sum _{j=1}^{d}\left|w_{j}\right|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}}$$

とすると、最小化問題の解は、 ある に対して次のように記述されます。 ${\displaystyle \alpha ={\frac {\lambda _{1}}{\lambda _{1}+\lambda _{2}}}}$$${\displaystyle {\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}{\text{ s.t. }}(1-\alpha )\left\|w\right\|_{1}+\alpha \left\|w\right\|_{2}\leq t}$$${\displaystyle t}$

Elastic Net ペナルティ関数として 考えてみましょう。${\displaystyle (1-\alpha )\left\|w\right\|_{1}+\alpha \left\|w\right\|_{2}\leq t}$

のとき、Elastic Net はリッジ回帰になりますが、Lasso になります。Elastic Net ペナルティ関数は 0 で 1 次導関数を持たず、Lasso 回帰とリッジ回帰の両方の特性を持つ厳密に凸です。 ${\displaystyle \alpha =1}$${\displaystyle \alpha =0}$${\displaystyle \forall \alpha \in (0,1]}$${\displaystyle \forall \alpha >0}$

弾性ネットの主な特性の一つは、相関のある変数のグループを選択できることである。サンプルと重みベクトルの差は次のように与えられる。 ここで、^[2]${\displaystyle x_{i}}$${\displaystyle x_{j}}$$${\displaystyle \left|w_{i}^{*}(\lambda _{1},\lambda _{2})-w_{j}^{*}(\lambda _{1},\lambda _{2})\right|\leq {\frac {\sum _{i=1}^{n}|y_{i}|}{\lambda _{2}}}{\sqrt {2(1-\rho _{ij})}},}$$${\displaystyle \rho _{ij}=x_{i}^{\mathsf {T}}x_{j}}$

と の相関が高い場合( )、重みベクトルは非常に近くなります。 負の相関サンプル ( ) の場合は、サンプルを取得できます。 要約すると、相関の高い変数の場合、重みベクトルは負の相関変数の場合、符号まで等しくなる傾向があります。 ${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle \rho _{ij}\to 1}$${\displaystyle \rho _{ij}\to -1}$${\displaystyle -x_{j}}$

以下は、正則化関数の可能な選択肢のリストと、それぞれの名前、単純な事前確率がある場合はそれに対応する事前確率、および結果として得られる最適化問題の解を計算する方法を示しています。 ${\displaystyle R(\cdot )}$

• 最小二乗法
• 数学における正規化。
• 一般化誤差。正則化が使用される理由の 1 つです。
• チホノフ正規化
• Lasso回帰
• 弾性ネット正規化
• 最小角回帰

• http://www.stanford.edu/~hastie/TALKS/enet_talk.pdf 弾性ネットによる正規化と変数選択 (プレゼンテーション)
• 正規化最小二乗法とサポートベクターマシン（プレゼンテーション）
• 正規化最小二乗法(プレゼンテーション)