こんにちは。 料理にはまっているkzです。 本日はリッジ回帰行きましょう。次回実装します。🐷

Ridge Regression

過学習を防ごうということで導入された正則化回帰の一例。 – L_2正則化項を使用した回帰model – パラメータに上限あり たまにリッジ回帰はペナルティーありの線形回帰という記事を見かけますがそうではなく多項式回帰でもあります。つまりモデルが

(1)   \begin{align*} y = \beta_0 + \beta_1x_1 + \beta_2x_2 \cdots + \beta_ix_i + \epsilon \end{align*}

だけでなく

(2)   \begin{align*} y = \beta_0 + \beta_1x + \beta_2x^2 \cdots + \beta_ix^i + \epsilon \end{align*}

もOKということ。

Notation

  • Number of data: N
  • Dimension: n
  • Parameters: b
つまり各データは

(3)   \begin{align*} x_i := x^{(i)} = (x_1, x_2, \cdots, x_n)^T \end{align*}

と表されます。bも同様。 Constrained minimizationは

(4)   \begin{align*} \texttt{minimize } \sum_{i=1}^N (y_i - x_i^Tb)^2 \end{align*}

(5)   \begin{align*} \texttt{subject to } \sum_{i=1}^n b_i^2 \leq t ~~ , ~~ 0\leq t \end{align*}

となりますが扱いずらいのでベクトル表示に変更し同時にKKT条件より最適化問題を同値なものに書き換えます。

(6)   \begin{align*} \texttt{minimize } |(y-Xb)|_2^2 + \lambda |b|_2^2 ~~ , ~~ 0\leq \lambda \end{align*}

ではまず解を求めましょう。いつも通り微分をゼロとおいて解くだけ。今回のコスト関数は次の通り

(7)   \begin{align*} g: b \rightarrow |(y-Xb)|_2^2 + \lambda |b|_2^2 \end{align*}

としてbで微分する。 – 「ベクトルで微分・行列で微分」公式まとめ

(8)   \begin{align*} \frac{\partial g}{\partial b} = -2X^Ty + 2bX^TX+2\lambda \end{align*}

したがって

    \[b_{ridge} = (X^TX + \lambda I)^{-1}X^Ty\]

\lambdaは正則をキープするためのものでしたね。 ここまでは前回の内容をちょっとだけ丁寧にやっただけのおさらいのようなものです。ここからが数学チック。 さて、この解が最適解かどうかを関数の凸性から確認してみましょう。凸性は前回やりましたがお椀型なら極小値が最小値になることでしたね。 – 第2章 凸関数 – Convex functions

(9)   \begin{align*} f \in \mathcal{C}^\infty: \mathbb{R}^n \rightarrow \mathbb{R} \end{align*}

に対して次は同値である。 – fが凸である – \forall x\in \mathbb{R}^nに対してヘッセ行列\nabla^2 f(x)がpositive-semi-define
では

(10)   \begin{align*} \frac{\partial^2 g}{\partial b^2} = 2X^TX + 2I_n \end{align*}

となりますね。ここでこれがpositive-semi-defineであることは次からわかります。\forall y\in \mathbb{R}^nに対して

(11)   \begin{align*} y^T X^TX y = |Xy|_2^2 \geq 0 \end{align*}

とノルムの定義よりわかりました。
gはほんまに凸か？
今見たのは

(12)   \begin{align*} H: b \rightarrow |(y-Xb)|_2^2 \end{align*}

の凸性ですよね。そして

(13)   \begin{align*} K: b \rightarrow \lambda |b|_2^2 \end{align*}

こちらは明らかに凸。ではg = H + Kが本当に凸かどうか。これは直感的には明らかですが証明が簡単なのでやってみましょう。
集合Xを定義域とする関数H,Kがともに凸関数であると仮定する。 このとき\forall x,y \in X ~~ , ~~ \forall \lambda \in [0,1]に対してgが凸であることを示す。

(14)   \begin{align*} (H+K)(\lambda x + (1-\lambda)y) = H(\lambda x + (1-\lambda)y) + K(\lambda x + (1-\lambda)y) \end{align*}

(15)   \begin{align*} \leq \lambda H(x) + (1-\lambda)H(y) + \lambda K(x) + (1-\lambda)K(y) \end{align*}

(16)   \begin{align*} = \lambda (H+K)(x) + (1-\lambda)(H+K)(y) \end{align*}

Q.E.D.
Lassoは結構めんどくさいんですよね。。 でわ