読者です 読者をやめる 読者になる 読者になる

でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Alternating Least Square (ALS) でCP分解

テンソル分解の基本中の基本のCP分解を導出して実装した。最適化の方法は色々あるらしいけど多分いちばんよく使われる Alternating Least Square (ALS) を使った。ちなみにここでテンソルって呼んでるのはただの多次元配列のこと。

まとめ

  • CP分解とは
  • AlSによるCP分解の更新式を導出
  • ALSによるCP分解をpythonで実装
  • 人工データを使って実験

CP分解とは

CP分解が何かを知るためには、まず Matrix factorization (MF) について知ると良い。

MFでは、N x M 行列 X を以下のように分解する

{
X \simeq P Q^{T}
}

ここで、{P}は N x R 行列で、{Q}は M x R 行列。この分解を要素ごとに書くとこうなる

{
x_{ij} \simeq \sum_{r} p_{ir} q_{jr} = p_{i}^{T}q_{j}
}

つまり要素 {x_{ij}} を なんかよくわからない{r}次元のベクトル {p_{i}}{q_{j}}内積で表現することにしましょうと言っているわけ。

じゃあこの {p_{i}}{q_{j}} っていうベクトルたちをどうやって求めるかという話になるわけだけど、それはこの辺に良い説明があるので説明しない。

Matrix Factorization: A Simple Tutorial and Implementation in Python @ quuxlabs

Matrix Factorizationとは - Qiita

ここまでわかるとCP分解が何なのかはすぐに理解できる。3階の I x J x K テンソル {\mathcal{X}} のCP分解は要素ごとに書くと以下のようになる

{
x_{ijk} \simeq \sum_{r} u_{ir} v_{jr} w_{kr}
}

これはMFとほぼ同じで、右辺が3つの積になっただけ。簡単簡単。ほんとにこれだけ。

この記事では、この {u_{i}}{v_{j}}{w_{k}} をどう求めるかを説明する。以下では、{u_{i}}{v_{j}}{w_{k}}をまとめて

{
U^{T} = (u_{1}, \cdots, u_{I}), V^{T} = (v_{1}, \cdots, v_{J}), W^{T} = (w_{1}, \cdots, w_{K})
}

と表記する。

ちなみにCP分解はCanonical Polyadic分解の略だけど、ほかにもいろんな呼び名があって、例えばPARAFAC(Parallel Factor Analysis)とか、CANDECOMP(Canonical Decomposition)とか。なぜか知らないけどいろいろある。ここではとりあえずCP分解に統一する。

CP分解のALSによる更新式の導出

上で軽く説明したように、CP分解では3階の I x J x K テンソル {\mathcal{X}} *1 を3つの行列 {U}{V}{W} (潜在変数行列と呼ぶ)に分解するわけだけど、ALS は簡単に言うと「他の2つを固定して、1つの潜在変数を最小二乗法で推定する」という方法。それを繰り返して更新していく。だから "Alternating" Least Square と呼ばれる。

ではまず {U} をどう推定するかを考える。

最小二乗なので、コスト関数を以下で定義する

{
L = \frac{1}{2} \sum_{ijk} \left(x_{ijk} - \sum_r u_{ir}v_{jr}w_{kr}\right)^{2}
}

ただ単に全要素の差の二乗を取っているだけ。これを今後の見通しが良くなるように書き換える

{
L = \frac{1}{2} \sum_{ijk} \left(x_{ijk} - u_{i}^{T}(v_{j} \circ w_{k}) \right)^{2}
}

{\circ} はベクトルの要素積(アダマール積という)。

んで、これを最小化する{U}を求めたいので、{u_{i}}微分する

{
\frac{\partial L}{\partial u_{i}} = - \sum_{jk} \left(x_{ijk} - u_{i}^{T}(v_{j} \circ w_{k})\right)\left(v_{j} \circ w_{k}\right)
}

{
= - \sum_{jk} x_{ijk}(v_{j} \circ w_{k})  + \sum_{jk}u_{i}^{T}(v_{j} \circ w_{k})(v_{j} \circ w_{k})
}

{
= - \sum_{jk} x_{ijk}(v_{j} \circ w_{k})  + \sum_{jk}(v_{j} \circ w_{k})(v_{j} \circ w_{k})^{T}u_{i}
}

{
= - \sum_{jk} x_{ijk}(v_{j} \circ w_{k})  + (V^{T}V \circ W^{T}W)u_{i}
}

ここで、

{
\bar{x}^{vw}_{i} = \sum_{jk}x_{ijk}\left(v_{j} \circ w_{k}\right)
}

というベクトルを定義すると、以下のように書ける

{
\frac{\partial L}{\partial u_{i}} = - \bar{x}^{vw}_{i}  + (V^{T}V \circ W^{T}W)u_{i}
}

これを0と置いて解くと、

{
u_{i} = (V^{T}V \circ W^{T}W)^{-1}\bar{x}^{vw}_{i}
}

となる。また、{(\bar{X}^{wv})^{T} = (\bar{x}^{wv}_{1}, \cdots, \bar{x}^{wv}_{I})} と置いて行列で書くと、

{
U = \bar{X}^{vw}\left(V^{T}V \circ W^{T}W\right)^{-1}
}

となり、これで{U}が求まった。

同様に、{V}{W} もついても以下のように書ける

{
V = \bar{X}^{wu}\left(W^{T}W \circ U^{T}U\right)^{-1}
}

{
W = \bar{X}^{uv}\left(U^{T}U \circ V^{T}V\right)^{-1}
}

このように、ALSでは2つの潜在変数行列を固定して、1つの潜在変数行列を更新するということを繰り返す。まとめると、

  1. {U_{(0)}}{V_{(0)}}{W_{(0)}}を適当に初期化
  2. {t \leftarrow 0}
  3. {U_{(t+1)} \leftarrow \bar{X}^{vw}\left({V_{(t)}}^{T}V_{(t)} \circ {W_{(t)}}^{T}W_{(t)}\right)^{-1}}
  4. {V_{(t+1)} \leftarrow \bar{X}^{wu}\left({W_{(t)}}^{T}W_{(t)} \circ {U_{(t+1)}}^{T}U_{(t+1)}\right)^{-1}}
  5. {W_{(t+1)} \leftarrow \bar{X}^{uv}\left({U_{(t+1)}}^{T}U_{(t+1)} \circ {V_{(t+1)}}^{T}V_{(t+1)}\right)^{-1}}
  6. {t \leftarrow t+1}
  7. 収束するまで3-6を繰り返す

実装

入力データは X[(i,j,k)] = value という辞書で与える。fitで学習して、predictで予測する。self.A[i]にi次のモードに対応する潜在変数行列が入っている。

上の説明では正則化は入れてなかったけど、データによっては逆行列の計算でこける(特異行列)ので、実装ではL2正則化をいれてある。

あと、潜在変数行列は平均 0、分散 0.01 の正規分布で初期化した。

gist36b4c4c07e96e392f9c876ddcc84e7bc

実験

適当な潜在変数を予め用意して、それを使ってデータテンソルを作る。そんで、CP分解でそのテンソルを分解する。

fitすると、self._lossesに各イテレーション時のロスの値が入るので、それをプロットした。

適当に選んだ要素をちゃんとCP分解が復元できるかもためした(うまくいった)。

gist7b56d8330cd117f412b6798123cdb595

*1:3階にかぎらず一般のN階のテンソルに適用できる。