はじめに

前回は以下記事にてオーソドックスなBias付きのMatrix Factorizationを実装しました。

rf00.hatenablog.com

そして今回は以下論文のアプローチによる個々人の順序の間の差の違いを考慮したMatrix Factorizationを実装してみたいと思います。

Collaborative Filtering via Additive Ordinal Regression

論文概要

論文の中では行われていることは、評価データにおける個々人によって異なる数値間の幅の違いを取り込もうというものです。

具体的には以下の図を使って説明します。

f:id:rf00:20180526132202p:plain

上段は、1~5点をあるアイテムに対する評価だとしたときに、すべての評価間を均等だと仮定したものです。

一方で、下段は1から2の差が大きく、2,3,4までは近い、そして4から5で差が大きくなっています。

おそらく現実世界での個々人の評価の仕方は下段のように、ある特定の評価値からある評価値までの幅の間隔が違うと思います。そしてもちろん1から2が狭い人もいれば、1,2,3,4までは狭くて5でとても開くといったように多様なあり方があると思います。

こういった値間の差の異なり具合をモデルのパラメータとして取り込んでいるのがこの論文でのアプローチです（bias付きのMatrix Factorizationとやりたいことは近い気がします）。

評価値の分解

このアプローチでは評価行列を以下のように分解します。

f:id:rf00:20180526134055p:plain

この図では評価値の最大が5のデータだとしています。そして、user1のitem2の評価が2で、user2のitem1への評価が4、それ以外は未評価というような状況です。

それを表現しているのが一番左の行列Rで、分解すると右の方のR1~R5になります。やっていることは評価値がc以上だったらRcは1、未満だったら0としているだけです。

このようにバイナリ値になるように行列を分解しています。

この分解した複数の行列に対してそれぞれMatrix Factorizationを行い、その結果を統合していくのがこのアプローチの流れです。

最終的な最小化する式は以下になります。

${min \sum_{(u, i) \in \Omega} (r_{u,i} - \sum_{c=1}^{C} \frac{w_{u}^{c}}{2} (U_{u}^{c} V_{i}^{c T} + 1) )^2 + \sum_{u, c}\lambda_{U, u}||U_{u}^{c}||^{2} + \sum_{i, c}\lambda_{V, i}||V_{i}^{c}||^{2} } \\ s.t. \\ ||U_{u}^{c}||^{2} \le 1 \\ ||V_{i}^{c}||^{2} \le 1 \\ \forall_{u, i, c}$

著者はこの手法を"decomposed matrix factorization(DMF)"と名付けています。

実装

それでは実装を行います。今回の全体のコードは以下です¹。 python_dmf.ipynb · GitHub

また精度確認用のデータはMovie Lensのデータを使います。

grouplens.org

アルゴリズムの流れ

DMFのアルゴリズムの流れとしては大きく次のようになります。

各分解あと行列の潜在変数のパラメータを更新(収束するまで)
個々人のスケールパラメータw^cの更新(収束するまで)
全体的に収束するまで1, 2を複数回繰り返し

各分解あと行列の潜在変数のパラメータ更新方法

各行列の潜在変数部分を確率的最急降下法で更新する式は以下のようになります。

$U_{u}^{c} ← U_{u}^{c} + \eta_1 \cdot(e_{u, i}\cdot W_{u}^{c}\cdot V_{i}^{c} - 2\lambda_{U, u}\cdot U_{u}^{c})\\ V_{i}^{c} ← U_{i}^{c} + \eta_1 \cdot(e_{u, i}\cdot W_{u}^{c}\cdot U_{u}^{c} - 2\lambda_{V, i}\cdot V_{i}^{c})$

そして実装は以下のようにしました（9~10行目は制約を満たすための処理です）。

    def sgd(self, c):
        np.random.shuffle(self.samples[c])
        for user, item, rating in self.samples[c]:
            err = rating - self.predict_pair(user, item, c)  
            
            # Update user and item
            self.user_factors[c][user] += self.alpha_1 * (err * self.w[c][user] * self.item_factors[c][item] - 2 * self.beta * self.user_factors[c][user])
            self.item_factors[c][item] += self.alpha_1 * (err * self.w[c][user] * self.user_factors[c][user] - 2 * self.beta * self.item_factors[c][item])                        
            self.user_factors[c][user] = self.user_factors[c][user] / np.sqrt(np.inner(self.user_factors[c][user], self.user_factors[c][user]))
            self.item_factors[c][item] = self.item_factors[c][item] / np.sqrt(np.inner(self.item_factors[c][item], self.item_factors[c][item]))

引数のcで更新するのがどの評価値の行列かを指定しています。

個々人のスケールパラメータw^cの更新

個々人のスケールパラメータw^cを確率的最急降下法で更新する式は以下になります。

$w_{u}^{c} ← w_{u}^{c} + \eta_2 \cdot e_{u, i} \cdot (U_{u}^{c}V_{i}^{c T} + 1)$

実装は以下です。

    def sgd_user_scale(self, c):
        np.random.shuffle(self.samples[c])
        for user, item, rating in self.samples[c]:
            err = rating - self.predict_pair(user, item, c)
            #Update user scale
            self.w[c][user] += self.alpha_2 * err * (np.inner(self.user_factors[c][user], self.item_factors[c][item]) + 1)

引数のcは先程と同じで更新対象がどの評価値の行列かを指定しています。

精度

それでは学習して精度を見てみたいと思います。

データを読み込みます。

import pandas as pd

def load_ml100k():
    samples = pd.read_csv('data/ml-100k/u.data', sep = '\t', header=None)
    
    samples = samples.iloc[:, :3]
    samples.columns = ['user', 'item', 'rate']
    
    samples['user'] = samples['user'] - 1
    samples['item'] = samples['item'] - 1
    
    return samples

df = np.array(load_ml100k())

n_user = np.unique(df[:, 0]).max() + 1
n_item = np.unique(df[:, 1]).max() + 1
n_rate = np.unique(df[:, 2]).max()

random.shuffle(df)
train_size = int(df.shape[0] * 0.8)
train_df = df[:train_size]
test_df = df[train_size:]

次に学習です。

DMF = DecomposedMatrixFactorization(K = 20, alpha_1 =  0.01, alpha_2 =  0.001, beta = 0.5)
DMF.fit(train_df, n_user, n_item, n_rate, n_iter = 2)

pre3 = DMF.predict(test_df)
ret3 = np.hstack((test_df, np.array(pre3).reshape(-1, 1)))
np.sqrt(pow((ret3[:, 2] - ret3[:, 3]), 2).mean())

精度は、

0.99228762189688302

あまり高くないですね。。。²

収束の判定をきちんとやっていないのがあまり良くないのかもしれません。

まとめ

Matrix Factorizationの実装をある程度事前に理解していたおかげで、比較的に簡単に実装できました。

ただし並列化等できていないため計算にかなり時間がかかるのが課題です（論文では並列化することを前提に書かれている）。その点を含めるとPythonでやるのは限界があるのでしょうか。

また精度も論文で示されているほど、高く出なかったなという印象です。もちろん収束の判定やパラメータの調整きちんと実装すれば改善される可能性はあると思います。

間違い等ありましたら指摘お願いいたします。

論文中のアルゴリズムは並列して書かれていますが、今回は並列化していません。したがって計算には結構時間かかります。。。↩
前回のbias付きのMatrix Factorizationでは0.96でした。↩

Deep Karmaning

技術系の話から日常のことまで色々と書きます

【論文実装】Collaborative Filtering via Additive Ordinal Regression

はじめに

論文概要

評価値の分解

実装

アルゴリズムの流れ

各分解あと行列の潜在変数のパラメータ更新方法

個々人のスケールパラメータw^cの更新

精度

まとめ

はじめに

論文概要

評価値の分解

実装

アルゴリズムの流れ

各分解あと行列の潜在変数のパラメータ更新方法

個々人のスケールパラメータwcの更新

精度

まとめ

個々人のスケールパラメータw^cの更新