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つの潜在変数行列を更新するということを繰り返す。まとめると、

${U_{(0)}}$ 、 ${V_{(0)}}$ 、 ${W_{(0)}}$ を適当に初期化
${t \leftarrow 0}$
${U_{(t+1)} \leftarrow \bar{X}^{vw}\left({V_{(t)}}^{T}V_{(t)} \circ {W_{(t)}}^{T}W_{(t)}\right)^{-1}}$
${V_{(t+1)} \leftarrow \bar{X}^{wu}\left({W_{(t)}}^{T}W_{(t)} \circ {U_{(t+1)}}^{T}U_{(t+1)}\right)^{-1}}$
${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}}$
${t \leftarrow t+1}$
収束するまで3-6を繰り返す