こんにちは。
料理にはまっているkzです。
本日はリッジ回帰行きましょう。次回実装します。🐷
Ridge Regression
過学習を防ごうということで導入された正則化回帰の一例。
–
![Rendered by QuickLaTeX.com L_2](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-84db227018e3228ebc26b639aa94bbd0_l3.png)
正則化項を使用した回帰model
– パラメータに上限あり
たまにリッジ回帰はペナルティーありの線形回帰という記事を見かけますがそうではなく多項式回帰でもあります。つまりモデルが
(1) ![Rendered by QuickLaTeX.com \begin{align*} y = \beta_0 + \beta_1x_1 + \beta_2x_2 \cdots + \beta_ix_i + \epsilon \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9cd3701521aa337b69bc27224ec11aab_l3.png)
だけでなく
(2) ![Rendered by QuickLaTeX.com \begin{align*} y = \beta_0 + \beta_1x + \beta_2x^2 \cdots + \beta_ix^i + \epsilon \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9bee9ce4f00d8f81b5e76c86aec56cc8_l3.png)
もOKということ。
Notation
- Number of data:
![Rendered by QuickLaTeX.com N](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-5793832f979c2268e3694c246d53b1bb_l3.png)
- Dimension:
![Rendered by QuickLaTeX.com n](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png)
- Parameters:
![Rendered by QuickLaTeX.com b](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f56d50c26583f9a035ff6b4e3c0ca5c0_l3.png)
つまり各データは
(3) ![Rendered by QuickLaTeX.com \begin{align*} x_i := x^{(i)} = (x_1, x_2, \cdots, x_n)^T \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-7fbb65fada6bb4befb00e661dc3872c2_l3.png)
と表されます。
![Rendered by QuickLaTeX.com b](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f56d50c26583f9a035ff6b4e3c0ca5c0_l3.png)
も同様。
Constrained minimizationは
(4) ![Rendered by QuickLaTeX.com \begin{align*} \texttt{minimize } \sum_{i=1}^N (y_i - x_i^Tb)^2 \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9c5db8302e44fc9f21513267439ed21a_l3.png)
(5) ![Rendered by QuickLaTeX.com \begin{align*} \texttt{subject to } \sum_{i=1}^n b_i^2 \leq t ~~ , ~~ 0\leq t \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-b4d1414a8e27b97948721511607a8159_l3.png)
となりますが扱いずらいのでベクトル表示に変更し同時にKKT条件より最適化問題を同値なものに書き換えます。
(6) ![Rendered by QuickLaTeX.com \begin{align*} \texttt{minimize } |(y-Xb)|_2^2 + \lambda |b|_2^2 ~~ , ~~ 0\leq \lambda \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-e671704c92161869d08cdc653d0008a3_l3.png)
ではまず解を求めましょう。いつも通り微分をゼロとおいて解くだけ。今回のコスト関数は次の通り
(7) ![Rendered by QuickLaTeX.com \begin{align*} g: b \rightarrow |(y-Xb)|_2^2 + \lambda |b|_2^2 \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-29a10a3e1bf8e268c530252ea83db34b_l3.png)
として
![Rendered by QuickLaTeX.com b](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f56d50c26583f9a035ff6b4e3c0ca5c0_l3.png)
で微分する。
–
「ベクトルで微分・行列で微分」公式まとめ
(8) ![Rendered by QuickLaTeX.com \begin{align*} \frac{\partial g}{\partial b} = -2X^Ty + 2bX^TX+2\lambda \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-6e4aca8d344bd234c157ccb5b0d40883_l3.png)
したがって
![Rendered by QuickLaTeX.com \[b_{ridge} = (X^TX + \lambda I)^{-1}X^Ty\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-3f73b5d19e6a7dd1b70bef45f87153d0_l3.png)
![Rendered by QuickLaTeX.com \lambda](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-2b5c45836864531b8e37025dabadd24a_l3.png)
は正則をキープするためのものでしたね。
ここまでは前回の内容をちょっとだけ丁寧にやっただけのおさらいのようなものです。ここからが数学チック。
さて、この解が最適解かどうかを関数の凸性から確認してみましょう。凸性は前回やりましたがお椀型なら極小値が最小値になることでしたね。
–
第2章 凸関数
–
Convex functions
(9) ![Rendered by QuickLaTeX.com \begin{align*} f \in \mathcal{C}^\infty: \mathbb{R}^n \rightarrow \mathbb{R} \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-74423165b8d913116208b2f5a90ef0a8_l3.png)
に対して次は同値である。
–
![Rendered by QuickLaTeX.com f](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9c09a708375fde2676da319bcdfe8b24_l3.png)
が凸である
–
![Rendered by QuickLaTeX.com \forall x\in \mathbb{R}^n](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-a826ab1ecae5c2d2909c571d6f36956f_l3.png)
に対してヘッセ行列
![Rendered by QuickLaTeX.com \nabla^2 f(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-076784850dfacdec0687e5042d5f241e_l3.png)
がpositive-semi-define
では
(10) ![Rendered by QuickLaTeX.com \begin{align*} \frac{\partial^2 g}{\partial b^2} = 2X^TX + 2I_n \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-3c70b7b9292cb70847a40b1071a018df_l3.png)
となりますね。ここでこれがpositive-semi-defineであることは次からわかります。
![Rendered by QuickLaTeX.com \forall y\in \mathbb{R}^n](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-bee3f74b5628c83747a74d8914a9bfd8_l3.png)
に対して
(11) ![Rendered by QuickLaTeX.com \begin{align*} y^T X^TX y = |Xy|_2^2 \geq 0 \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-c5d402e3aba4c01ff1ed089e344becf1_l3.png)
とノルムの定義よりわかりました。
![Rendered by QuickLaTeX.com g](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-d208fd391fa57c168dc0f151de829fee_l3.png)
はほんまに凸か?
今見たのは
(12) ![Rendered by QuickLaTeX.com \begin{align*} H: b \rightarrow |(y-Xb)|_2^2 \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-bff77ce1e4da970c199e27278aa6b5ae_l3.png)
の凸性ですよね。そして
(13) ![Rendered by QuickLaTeX.com \begin{align*} K: b \rightarrow \lambda |b|_2^2 \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-54e0adf10e8672c1f90f93d494312a38_l3.png)
こちらは明らかに凸。では
![Rendered by QuickLaTeX.com g = H + K](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-de850c81dddaeff4fdd632014d98a432_l3.png)
が本当に凸かどうか。これは直感的には明らかですが証明が簡単なのでやってみましょう。
集合
![Rendered by QuickLaTeX.com X](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-d4ee28752517d6062a3ca0314890342d_l3.png)
を定義域とする関数
![Rendered by QuickLaTeX.com H,K](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-968d3bc6cd5a8fe14519042da874cc45_l3.png)
がともに凸関数であると仮定する。
このとき
![Rendered by QuickLaTeX.com \forall x,y \in X ~~ , ~~ \forall \lambda \in [0,1]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f88e69619a3148e59542c32cd07f0949_l3.png)
に対して
![Rendered by QuickLaTeX.com g](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-d208fd391fa57c168dc0f151de829fee_l3.png)
が凸であることを示す。
(14) ![Rendered by QuickLaTeX.com \begin{align*} (H+K)(\lambda x + (1-\lambda)y) = H(\lambda x + (1-\lambda)y) + K(\lambda x + (1-\lambda)y) \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-1e50db928cb3870045c6edddf0e4abdd_l3.png)
(15) ![Rendered by QuickLaTeX.com \begin{align*} \leq \lambda H(x) + (1-\lambda)H(y) + \lambda K(x) + (1-\lambda)K(y) \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-e5dbcecade901aa2c45c89843b802d84_l3.png)
(16) ![Rendered by QuickLaTeX.com \begin{align*} = \lambda (H+K)(x) + (1-\lambda)(H+K)(y) \end{align*}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-7a0a25ec9ea5012671f861b42d72c646_l3.png)
Q.E.D.
Lassoは結構めんどくさいんですよね。。
でわ