ホーム » 「リッジ」タグがついた投稿

タグアーカイブ: リッジ

レコメンデーション　Biased-MFの実装

2020年1月10日 / コメントする

こんにちは。kzです。

前回レコメンデーションの入門を行いました。 シンプルなMatrix Factorizationで終わってしまったので今回は一つ発展したBiased-Matrix Factorizationを実装してみようと思います。その前に簡単な解説から入りましょう。

Biased-Matrix Factorization

前回のSimple Matrix Factorizationをおさらいすると次のような分解でした。
そして、モデルとそのコスト関数は次のように表されるのでした。
しかし、次のような場合を考えてください。Aさんは非常に映画マニアで彼のratingは非常に辛口、つまり平均が低いとしましょう。たとえば1.5にしましょう。一方でBさんは一般的は普通の映画愛好家で平均3.8のratingをするとしましょう。

この時、お互いが同じとある映画「ミイダスリサーチ」を見たとします。Aさんは辛口にもかかわらずratingを4としたとします。そしてBさんは安定に3.8より少し高い4をつけたとします。

ここでデータXにはX_{A, MIIDAS RESEARCH}, X_{B, MIIDAS RESEARCH}=4と同じ値が入るわけです。しかし、仮定から察することができるようにユーザーごとのバイアスを考えるとこの4を同じ扱いにするのはよくないのではないか？と思うのが普通ですよね。同様の考えでアイテム（今の場合映画）自体にもバイアスを考慮したモデルを考えます。
\beta_i, \gamma_j, \in \mathbb{R}がそれぞれユーザーi、アイテムjのバイアスになります。そしてこのモデルのコスト関数は前回と似た形になります。
ただ、これでは第二項の中がスマートではないので新たに変数を次のように定義することで前回と全く同じコスト関数をえることができます。
で、思ったんですけどこれってリッジ回帰とめっちゃ似てるんですよね。ということはあの頃のように閉じた解が見つかるはずなんです。

しかし、今回はr_{ij}がベクトルではなく行列なのでその点だけ注意が必要です。そこでこちらの論文が登場します。
この論文を参考にすると次のようにパラメータ更新のための解がもとまります。
詳しい導出は論文の説明も必要でちょっと長くなるので、纏めだけ貼って簡単に説明します。

p_{ui}というフラグを定義します。ユーザーu、アイテムiです。そしてc_{ui}が今回でいうバイアスのようなものです。論文中ではconfidenceという単語になっています。パラメータ\alphaでratingに重みづけしたのち、1を加算することで最終的なconfidenceを定義しています。

あとはいつも通り微分をとっていくだけです。行列で書き直すときに僕はよく頭がこんがらがるんですがそこは耐えです。
で、今回の更新式をどうやって得たかといいますとC=I, P = Xとしただけです。
結果から言いますとSMFの方がいい結果が得られました。というのは元の行列と予測を引き算してフロベニウスノルムの平方でlossを比較した結果、SMFの方が小さかったからです。ただ、パラメータのチューニングなどは行っておらず、実装にのみ焦点を当てたのでそうなってしまっただけかもしれません。
まだNon-Negative Matrix Factorizationというものがあるらしいです。。。。でわ

Lassoはなんでスパース？

2019年2月15日 / コメントする

こんにちは。
素人にfish_shellは無理でした。kzです。

リッジが終わりましたね。ついに来ました

ラッソ

最近色々ラッソについて調べていたんですが、微分不可能な関数の最適化ってやっぱ難しいですね。機械学習において非常に重要な２つのキーワード
– ラグランジュの未定乗数法
– KKT条件
は別の記事でゆっくり解説します。では本題に入りましょう。

Lasso

過学習を考慮した回帰モデルの一つ
– L_1正則化項を使用した回帰model
– スパース性を考えるときに用いる（これについては次の記事で詳しく説明します。）

(1)   \begin{align*} \beta = \texttt{argmin}_b { |y-Xb |^2_2 + \lambda|b|_1^1 } \end{align*}

リッジ回帰との唯一の違いは正規化項がL1(絶対値)であるということ。

微分できない？

ちょっと微分について復習しよう。おまけで複素解析も出てくるよ

L1とL2

これまでに何度か説明していると思いますがまずは
– 微分可能性
が大きな違いです。L1は尖っているので0で微分できませんね。

他の違いは？

リッジ回帰ではデカイパラメータbがでかくなりすぎないよう上限を設けましたね。
ラッソも上限はありますが、ゼロがKEYWORDです。なぜなら
– 無関係な特徴量はゼロで排除する
という特徴があります。ゆえに、モデルで初めに設定したものよりも少ない特徴量で済む可能性があります。これが先ほどのスパース性と言われる所以です。

パラメータが0を図から考察

では図を用いて直感的に理解しましょう。次の図はRidge,　Lassoを議論するときに使われるとてもポピュラーなものです。

「スパース」とは「スカスカ」なイメージ

つまり、ゼロがいっぱいあるイメージでいい。
しかし重要なのは常にスパースなわけじゃないこと。

スパースと言われるのはこの「尖ったポイント」に最適解がある時。

これはL1だからできますよね。L2は円だったのでスパース性はありません。

パラメータが0を数式から考察

次のように超シンプルな回帰モデルを考えます。(以下転置使ってますが無くてもいいです)

(2)   \begin{align*} y = bx + \epsilon \end{align*}

次の最小化を考えます。

(3)   \begin{align*} \texttt{minimize } y^Ty - 2y^T xb + b x^Tx b + 2\lambda |b|_1^1 \end{align*}

(この2は計算の都合上のもの)

ここで解がb>0と仮定します。

すると、y = bx \Leftrightarrow <y,y> = b<y,x>より
y^Tx >0と仮定するのと同値であることがわかります。さて、目的関数をbに関して微分しましょう

仮定より今は微分できます

(4)   \begin{align*} \frac{\partial }{\partial b} \texttt{objective function} = -2y^Tx + 2x^Tx b + 2\lambda \end{align*}

であり、これをゼロと置くことでこの解は次のものだとわかります

(5)   \begin{align*} b = \frac{y^Tx - \lambda}{x^Tx } \end{align*}

ここで\lambdaを増やしていくと\lambda = y^Txでゼロになることがわかりますね。
この瞬間にLassoはスパース性を持ちます。

一方、リッジの場合は　

(6)   \begin{align*} \textrm{minimize } & y^Ty - 2y^T xb + b x^Tx b + 2\lambda |b|_2^2　 \end{align*}

(7)   \begin{align*} b &= \frac{y^Tx}{x^Tx + \lambda} \end{align*}

となるので、b \neq 0よりパラメータはゼロにはならないですね。

でわ

PythonでRidgeを数式から実装する

2019年2月12日 / コメントする

こんにちは。
本日はRidge回帰の実装とパラメータの交差検証を行いましょう。
色々やっていると少し長くなりましたがお許しください。

最後の２セルはinteractを使ったんですがjupyterだと表示されませんね。。コピーして実行してみてください。

個人的に今回の収穫は
– 交差検証は4分割するといい
– センタリングでinterceptionが消える

次はLasso頑張るぞ！

でわ

Ridgeを数式から実装まで(理論)

2019年2月10日 / コメントする

こんにちは。
料理にはまっている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は結構めんどくさいんですよね。。
でわ