A Generic Coordinate Descent Framework for Learning from Implicit Feedback

k分離(k-separability)

introduction

MFの効率的な学習戦略として、２種類ある

• SGDを利用しているBPR
• interactionがあったものとなかったものを対比させる
• ランキング学習に適している
• ネガティブサンプリングを取り入れているが、item数が多い場合に収束の問題がある→複雑で不均一なサンプリング設計が必要
• CD
• interactionがあったものとなかったものの両方に対して要素ごとの損失を与える交互最小二乗法
• 数値データに適している
• 効率的な計算をするCD-MF(BPRと違いサンプリング不要)が提案されており、CD-MFとBPR-MFの成績は様々検証で精度は均衡していると報告されている
• Collaborative filtering for implicit feedback datasets

複雑な因子分解モデルに関する研究のほとんどは、BPRを用いたSGD最適化に依存している。

今回のiCDが利用可能になることによって、BPRとCDの選択可能性の幅を広げている。

モデル紹介

$I$: Item集合

$C$: Context集合(ユーザー、時刻、場所、属性などが含まれる)

$S$: 観測されたフィードバック

$\alpha$: confidence

一般的なModel

一般的にLossは以下で定義される

Coordinate Descent Algorithm

Lossを1回微分、2回微分したものを利用して、ニュートン法で更新していく

$\eta\in(0,1]$

ただし、学習データ数に対して線形に増加するため、適用困難である。

補題1: implicit学習は小さなpositiveデータにおける組み合わせ学習とcontext-itemペアのスコア関数の最小化といえる

証明

ここでは、$S_{impl}$を$\{c,i,0,-\alpha_0\}$と$\{c,i,y,\alpha\}$してまとめている

implicit regularizer, $R\Theta$を追加したone-classモデル（0を予測する）とも言いかえることができる

implicit regularizerを持った小さな$S$集合に対するexplicit learningであるとも言える

補題2: k-separable modelのimplicit regularizerは以下に分解される

証明

定義より

contextとitemの計算を独立して実行可能であることが示された。

補題3: いかなるk分離可能モデルにおけるimplicit regularizerの勾配は簡略化できる

証明

補題2より導出

計算手順

• モデルを$\Phi,\Psi$の内積で表現する
• モデルパラメータ$\theta$に対して、Loss, Rをそれぞれ1階,2階微分を行う
• $\theta$をニュートン法で更新

以下、MF, Feature-base MF, FM, Tensor Factorizationでの適用法をそれぞれ紹介している

ここまでで解説している内容と大きく変わらないので詳細は省略

この論文では、iCDとBPRを比較する目的ではなく、多様なモデルで適用できるiCDの汎用性(versatility)を紹介する形で実験を行っている。

内容も一般的な結果なので、詳細は省略

実装例

https://github.com/google-research/google-research/blob/master/ials/vae_benchmarks/icd_main.cc