形状限定適応モデルを用いた評価行列生成
元論文 : Improving collaborative filtering recommendations by estimating user preferences from clickstream data
1.研究背景とモチベーション
1.1 協調フィルタリング
一言で表すと、ユーザーの行動履歴に基づいた推薦アルゴリズム。
近隣ベースの手法とモデルベースの手法の二種類があります。
近隣ベース手法
ユーザ間の類似性やアイテム間の類似性に着目して推薦を生成する手法です。このうち、さらにユーザーベースの手法とアイテムベースの手法に分類されます。
ユーザーベース
対象となるユーザーと類似した嗜好を持つユーザーのグループを調べることによって、各ユーザーに適したレコメンデーションを提供する手法です。本論文ではユーザーベースの手法を用いる。
ユーザーの類似度を評価する方法
- ピアソン相関係数
いわゆる相関係数というやつ。ユーザー同士の線形な関係が強いほど大きな値をとり、ユーザー同士の類似度を図ることができる。
- コサイン類似度
ユーザー同士の評価ベクトルr (あるユーザーのそれぞれのアイテムに対する評価値を表現したベクトル)の類似度をベクトルのなす角の余弦の値によって評価する。
アイテムベース
あるユーザーのアイテムに対する評価値をそのアイテムと似ているアイテムに付けられた評価値を利用して予測する手法です。Amazonで採用されているらしい。
モデルベース手法
決定木、ルールベース推論、ナイーブベイズ分類器、行列因数分解技術などの機械学習やデータマイニング技術を用いて、対象となるユーザーに適したアイテムを予測する手法です。今回は特に非負行列因数分解(NMFアルゴリズム) というアルゴリズムに着目します。
非負行列因数分解(NMFアルゴリズム)
ユーザー・アイテム評価行列X(M×N)を、ユーザーとアイテムそれぞれの特徴量行列W(N×K)とH(K×M)に分解することを考えます。ここで未知のW,Hを求めるためにXとWHとの距離を最小化する事を考えます。この際の距離はフロベニウスノルムと呼ばれ
のように表されます。これを最小化する事で求めたWとHの積WHをまだ未知のあるアイテムに対するあるユーザーによる評価値として利用します。
1.2 既存の協調フィルタリング手法のデメリット
低品質な評価マトリックス
協調フィルタリングアルゴリズムのほとんどは、ユーザ項目のレーティングマトリクスに基づいて推薦を生成するのだが、ユーザーからの評価値にはノイズが多くこれは推薦システムの精度を著しく低下させる。
コールドスタート問題
データがある程度たまらないとそもそも有意な推薦ができないという問題。
つまり、新たなユーザーに対してアイテムを推薦したり、新たなアイテムをユーザーに推薦することが出来ないことになります。
1.3 本論文の目的
学習サンプル数にかかわらず高いレコメンダー性能を維持する推薦システム実現のための高品質な評価行列の生成法、形状制限付き推定を提案する。
提案した形状制限付き推定による手法が従来の手法に対して有意であることを実証する。
2.提案モデルの詳細
2.1 リーセンシ―を考慮した協調フィルタリング
本論文で用いられている手法ではPVの頻度(過去にあるアイテムがあるユーザーにどれだけ参照されていたか)に加えてPVのリーセンシ―(あるユーザーがアイテムを最後に参照した時からどれだけ時間が経っているか)を取り入れた手法になっています。過去の研究ではこれらのうち片方だけを考慮したフィルタリング手法が用いられていたため、本研究の手法の最大の利点はPVのリーセンシ―と頻度の両方の相互作用を有効に利用して推薦を行うことができる点です。これにより少ない学習サンプルでも高いレコメンド性能を実現しています。
2.2 確率テーブル
PVのリーセンシ―と頻度の相互作用を表現するために本論文では確率テーブルというものを導入しています。これは各リーセンシ―と頻度の組み合わせを持つユーザーとアイテムのペアについて、購買が起こる確率を表しています。
この確率テーブルを求めるために本研究では提案手法と経験的手法の二つを提示しています。
経験的手法(Iwanaga et al(2016))
経験的な手法ではまず与えられたクリックストリームデータ中で基準日を設定します。そして各リーセンシj―と頻度kについてテーブルの要素xに対して
x = (基準日以降に購入に至ったペアの数) / (基準日の時点でj,kを所持するユーザーとアイテムペアの数)
として計算します。この手法は実装は簡単ですが推定されたxの精度がxを計算するためのサンプル数に大きく依存してしまうという欠点があります。
形状限定最適化モデル(提案モデル)
本論文で提案する手法では確率表Xの要素に以下のような制約を加えます。
ここでjはリーセンシ―、k は頻度を表しています。
-
単調制約性
リーセンシ―や頻度が大きくなるほど項目選択確率xが高くなるというもので、これはリーセンシ―や頻度の定義からも明らかです(よくチェックするアイテムは購買確率が高い)
- リーセンシ―に関する凸性制約
これはあるアイテムのリーセンシ―が低いユーザは、その項目を長期間閲覧していないことを意味します。したがって、リーセンシ―の低い値の変化は、再帰性の高い値の変化と比較して、項目選択確率にほとんど影響を与えないという仮説に基づいた制約です。
- 頻度に関する凸性制約
こちらは逆にユーザーが特定のアイテムを何度も見る場合、1回のビューの影響は小さくなるという仮定に基づいています。上の式は高頻度の値の変化はアイテム選択確率に比較的小さな影響を与えるという制約を表しています。
二項定理を用いてアイテムの購入確率を対数をとることで以下のように表します。
この凹関数を上記の３つの制約のもとで最大化する事で確率テーブルを最適化します。
以上の内容をまとめると形状限定最適化モデルで解くべき問題は以下のように表せます。
2.3アルゴリズム詳細
形状限定最適化モデルのアルゴリズムの詳細を追っていきます。
1.訓練セットの準備
クリックストリームデータ中の各ユーザー-アイテムペアについて、過去に収集された「リーセンシ―」「頻度」「購入状況」のデータから構成されるトレーニングセットを準備します。
2.確率表の推定
1で準備した学習データを用いて最適化問題を解くことで確率表を推定します。論文ではこの部分の最適化には NTT DATA Mathematical Systems 社の数値最適化ソフトウェア Numerical Optimizer V17 を用いたようです。
3.項目選択確率の割り当て
確率表から適切な値を選択することで、レーティングセットのユーザ-アイテムのペアにアイテム選択確率を割り当てます。
4.評価行列の作成
下図左下のレーティングセットの項目選択確率を参照して、評価行列(右下)を作成します。下図右上の2次元の確率表を用いる事でPVのリーセンシ―と頻度の相互作用が十分に反映された評価行列が得られます。
3.実験と結果
3.1 実験手法
本論文での提案手法である形状限定最適化手法によって求められた評価行列の性能を評価するために、求めた評価行列を用いて協調フィルタリングのためのユーザベース手法とNMFアルゴリズム手法の両方での実験を行っています。
実験データセット
衣料品、アクセサリー、靴、バッグなどのアパレルとその関連商品を扱うECサイトが2015年8月1日から2015年10月30日までに収集した実世界のクリックストリームデータを採用しており、そのうち2015年9月に記録された購入データを確率表を推定するための学習セット、2015年10月に記録された購入データをレコメンド性能を評価するためのテストセットとして用いています。下表にそれぞれのデータセットの内訳が記載されています。
それぞれユーザー数、アイテム数、そしてユーザーとアイテムのペア数(サンプル数)、購入数が記載されています。
特徴量の設計
本論文ではそれぞれ独立の3つの時間単位をPV(View)、Session、Dayの3つを用いてそれぞれリーセンシ―と頻度を定義しています。つまりそれぞれの時間単位に対してそれぞれのリーセンシ―と頻度を定義し、合計6つの特徴量を考えています。
|J|, |K| はそれぞれリーセンシ―集合、頻度集合の大きさを表しています。
例えばDayRは日単位でのリーセンシ―であるユーザーのあるアイテムに対するDayR が 4だとそのユーザーがアイテムを最後に閲覧したのが4日前であることを意味し、ViewFが 6 だとすると、ある期間でのユーザーがアイテムを閲覧した回数が6回であることを意味します。実験ではリーセンシー3種類と頻度3種類それぞれ全ての組み合わせ9種類のリーセンシーと頻度について性能が評価されています(後述)
比較手法
今回、提案手法である形状限定最適化モデル(以下MCCモデルとします)の性能を評価するために、比較対象としてデータのリーセンシーのみを用いた手法(Rece)、頻度データのみを用いた手法(Freq)、そして2.2で述べたIwanagaらが提案した経験的手法(EMP)を用いています。
性能評価方法
本論文では上記の4つのレコメンド性能を評価するためにヒット数という概念に基づいて性能評価をしています。ヒット数とは、アルゴリズムによってレコメンドされ、ユーザーによって購入されたアイテムの数のことです。
このヒット数に基づいて各予測の再現率と精度を計算し、最終的にF1スコアを算出して各アルゴリズムのレコメンド性能の指標としています。
ここでの再現率は、ユーザーが購入したアイテムの数に対するヒット数の割合、精度は、推薦されるアイテムの数に対するヒット数の割合です。これらを用いて、F1スコアを算出しています。
3.2 実験結果
ユーザーベース手法での結果
3種類のリーセンシーと3種類の頻度全ての組み合わせ9種類について各手法Rece,Freq,そして提案手法MCCによるレコメンドのF1スコアが縦軸に記されています。横軸は推薦するアイテムの数でNで表され、1 ~ 100までの値が計算されています。
MCC は、特徴量の組み合わせにかかわらずほぼすべての N について、3 つの手法の中で最も高い F1 スコアを叩き出しています。特に、3 つの手法間の F1 スコアの差は、N 10 で比較的大きく、N が大きくなるにつれて小さくなっていることが分かります(たくさん推薦させれば正答率が下がるのは感覚的にも実感できそう)。
Rece の性能は用いるリーセンシー特徴量によって変わるみたいです。とくにRece は ViewR を使用した場合に限り、非常に小さい N で高い F1 スコアを示していることが分かります（図 2(a)-(c)）。
Freqの性能は特徴量の表現にほぼ依存しておらず、一貫して3つの手法の中で常に最低のF1スコアを出しています。アイテムを閲覧する頻度だけでユーザーの嗜好を評価するのは難しいようです。
MCCの性能は、再帰性特徴量に大きく依存しており、DayRを用いたMCCは特に他の手法を大幅に上回る性能を発揮しています。
次に、確率表の推定に使用した訓練サンプル数とユーザに提供された推薦の数の影響を調べることで、MCCモデルの利点を実証しています。
EMPは学習サンプル数が多くなるとをMCCと比較しても高いF1スコアを示している一方で1%サンプルセットを用いた場合には、ReceやFreqと同程度までスコアが低下していることがわかります。
MCCはEMPとは対照的に、訓練サンプル数に関係なく高いF1スコアを維持しており、これは確率テーブルの形状を限定した推定による恩恵だと考えられます。実際にMCCは、1%サンプルセットを使用した場合でも、常にReceとFreqを上回りました。1%標本集合には約75個の購入サンプルしか含まれていないことを考えると驚くべき結果です。
NMFアルゴリズムによる手法での結果
NMFアルゴリズムによる手法でもユーザーベースと同様に各リーセンシ―と頻度の組み合わせに対してF1スコアが算出されています。
ユーザーベースの手法と同様にMCC は、ほぼすべての N で最高の F1 スコアを達成しており、特に DayR を用いた場合には、他の手法よりもはるかに優れた性能を示していることが分かります。
ユーザーベースの手法と同様に、特徴量の表現に関わらず、Freq の性能は 3 つの手法の中で常に最低のスコアを算出しています。
ユーザーベースの手法とは異なり、MCC の性能は頻度特徴量の影響をわずかに受けていることが分かりました。特に DayR を用いて小さいNの場合の F1スコアを比較するとMCCの性能がどの頻度特徴量を用いるかに依存していることが分かります。（図 4(g)-(i)）。
- ユーザーベースの場合と同様に、EMP は全サンプルセットで非常に高い F1 スコアを示したが、訓練サンプル数が減るにつれて性能が低下しているようです。
- MCCのF1スコアは、訓練データの数に限らずほとんどの場合でMCCが4つの手法の中で最も高いF1スコアを達成しています。
ユーザーベースとNMFアルゴリズムでの手法の結果を比較すると、特徴的だったのが
* NMFアルゴリズムは、特徴の表現方法の選択に対してより敏感であることがわかります。
* ユーザベースアルゴリズムとNMFアルゴリズムを利用する利点は推奨項目の数Nに依存していることが分かります。例えば，DayR×DayFを用いたMCCの結果をユーザーベースとNMFで比較してみるとN=1 の場合には NMF アルゴリズムの方がユーザーベースのアルゴ リズムよりも優れている一方でN が 4 個程度になるとその関係は逆転していることが分かります(下図)
ユーザーベース(左)とNMF(右)のMCCでのF1スコア。 N=4あたりで確かに精度が逆転しているように見えます。
4.まとめ
提案されたMCCモデルによってクリックストリームデータからユーザの嗜好を合理的に推定することが可能になったことを実証しています。
本研究では一般的に使用されている2つの協調フィルタリングアルゴリズムであるユーザーベースとNMFアルゴリズムを用いた計算実験を通じて、MCCモデルの有効性を実証しています。その結果、どちらのアルゴリズムにおいても限られた学習サンプル数でもMCCモデルによって高いレコメンダー性能が得られることが検証されました。
過去のクリックストリームデータから確率テーブルを作成しておけば、ECサイトに実装されている協調フィルタリングアルゴリズムと組み合わせて、簡単にMCCモデルを構築することができ、ビジネスや経営上非常に有用であることが示唆されます。
一方で提案手法の課題として、クリックストリームのデータ（バスケットの配置、閲覧時間、閲覧順など）を最大限に活用していないことや確率テーブルの推定の際に販売促進やウェブナビゲーションが悪影響を及ぼしうることが挙げられていました。確率テーブルを推定する手法を改良する方向性の一つとして例えば、ユーザーとアイテムの不均一性を取り入れるようなモデリングを取り入れる事を提案しています。