統計的学習に基づく推薦方式に関する研究

(1)

統計的学習に基づく推薦方式に関する研究

A Study on the Recommendation Method based on Statistical Learning

2012 ^年 7 ^月

早稲田大学大学院基幹理工学研究科数学応用数理専攻情報理論研究

桑田修平

(2)

第1章序論 1

1.1 はじめに . . . . 1

1.2 本研究の目的 . . . . 2

1.3 本論文の構成 . . . . 3

第2章準備 4 2.1 履歴データの定義 . . . . 4

2.1.1 時系列形式での表現 . . . . 4

2.1.2 行列形式での表現 . . . . 5

2.2 問題設定 . . . . 6

第3章従来研究 7 3.1 従来の推薦手法 . . . . 7

3.2 最近傍法に基づくアプローチ . . . . 8

3.2.1 k近傍法（kNNs） . . . . 8

3.2.2 Uniﬁed method with Similarity Fusion（SF） . . . . 8

3.3 確率モデルに基づくアプローチ . . . . 9

3.3.1 多項分布モデル（MULTI） . . . . 9

3.3.2 混合多項分布モデル（MIXMULTI） . . . . 10

3.3.3 Aspect Model（AM） . . . . 10

3.3.4 User Rating Proﬁle Model（URP） . . . . 11

第4章本研究の概要 12 4.1 従来の推薦方式における視点 . . . . 12

4.2 本研究における視点 . . . . 12 i

(3)

4.3 提案する推薦方式の全体像 . . . . 13

4.3.1 時間的な視点と空間的な視点の両方を考慮した推薦手法 . . . 13

4.3.2 空間的な視点を考慮した推薦手法1 . . . . 15

4.3.3 空間的な視点を考慮した推薦手法2 . . . . 16

4.4 本研究の意義 . . . . 17

第5章ベイズ決定理論に基づくユニバーサルマルコフ決定過程モデル 19 5.1 はじめに . . . . 19

5.2 問題設定 . . . . 21

5.3 準備：マルコフ決定過程モデル . . . . 22

5.4 従来手法 . . . . 23

5.5 提案手法 . . . . 25

5.5.1 マルコフ決定過程モデルの一般化 . . . . 26

5.5.2 履歴データを用いた最適な推薦ルールの学習 . . . . 27

5.5.3 履歴データの蓄積について . . . . 30

5.6 評価実験 . . . . 32

5.6.1 実験手順 . . . . 33

5.6.2 結果と考察 . . . . 34

5.7 本章のまとめ . . . . 38

第6章一括予測型協調フィルタリング 39 6.1 はじめに . . . . 39

6.2 問題設定 . . . . 41

6.2.1 データの定義 . . . . 41

6.2.2 目的 . . . . 41

6.2.3 評価尺度 . . . . 42

6.3 提案手法 . . . . 44

6.3.1 ランダムな欠損 . . . . 44

6.3.2 周辺評点分布に基づく評点予測 . . . . 44

6.3.3 予測アルゴリズム . . . . 46

ii

(4)

6.4.2 従来手法 . . . . 50

6.4.3 結果と考察 . . . . 51

6.5 本章のまとめ . . . . 55

第7章ディリクレ過程混合モデルに基づく共クラスタリング 56 7.1 はじめに . . . . 56

7.2 問題設定 . . . . 58

7.3 従来研究 . . . . 59

7.3.1 非負行列因子分解に基づく手法 . . . . 59

7.3.2 グラフの分割に基づく手法 . . . . 60

7.3.3 確率モデルに基づく手法 . . . . 60

7.3.4 従来手法の共通点 . . . . 61

7.4 無限関係モデル . . . . 61

7.4.1 購入履歴の生成に対するモデル . . . . 62

7.4.2 クラス数の生成に対するモデル . . . . 62

7.4.3 無限関係モデルにおける同時分布 . . . . 63

7.4.4 学習アルゴリズム . . . . 64

7.4.5 無限関係モデルの問題点 . . . . 65

7.5 提案手法 . . . . 65

7.5.1 購買履歴の生成に対するモデル . . . . 65

7.5.2 提案手法における同時分布 . . . . 67

7.5.3 学習アルゴリズム . . . . 68

7.6 実験 . . . . 70

7.6.1 人工データ実験 . . . . 71

7.6.2 実データ実験 . . . . 75

7.6.3 実験結果まとめ . . . . 78

7.7 本章のまとめ . . . . 79

iii

(5)

第8章考察 80 8.1 第6章で提案した推薦方式の応用 . . . . 80 8.2 第7章で提案した推薦方式の応用 . . . . 81

第9章結論 82

9.1 まとめ . . . . 82 9.2 今後の課題 . . . . 83 9.3 将来の展望 . . . . 83

付録A 第7章に関する付録 84

A.1 ディリクレ過程 . . . . 84 A.2 提案手法におけるZ, W の事後確率の導出 . . . . 85

参考文献 87

謝辞 94

研究業績 96

iv

(6)

4.1 各提案手法の位置づけ . . . . 18

5.1 実験結果：モデルを1つに固定した場合と提案手法の割引総利得（真のモデルを含む場合．値は理論値に対する比を表す）． . . . . 35

5.2 実験結果：モデルを1つに固定した場合と提案手法の割引総利得（真のモデルを含まない場合．値は理論値に対する比を表す）． . . . . . 35

5.3 実験結果：同じ商品を2回購入しない場合（真のモデルを含む場合．値は理論値に対する比を表す）． . . . . 37

5.4 実験結果：モデルベースアルゴリズムとの比較結果（値は理論値に対する比を表す）． . . . . 37

6.1 提案する評点予測アルゴリズム . . . . 47

6.2 MovieLensとEachMovieデータセット . . . . 49

6.3 各手法の予測精度．値が小さいほど予測精度が良いことを意味する. 51 6.4 各手法の予測に要した計算時間．要した時間が短いほどスケーラビリティが良いことを意味する. . . . . 52

6.5 予測対象の全評点の予測に要する計算量（computational complexity）． 54 6.6 予測に要する空間計算量（space complexity）． . . . . 54

7.1 ギブズサンプリングに基づく学習アルゴリズム. . . . 69

7.2 人工データ作成に用いたパラメータ値（パターンI）． . . . . 70

7.3 人工データ作成に用いたパラメータ値（パターンII）． . . . . 72

7.4 提案手法と無限関係モデル（IRM）の共クラスタリング性能比較（パターンI）． . . . . 73

v

(7)

7.5 提案手法と無限関係モデル（IRM）の共クラスタリング性能比較（パターンII）．. . . . 74 7.6 提案手法により得られたアイテムクラスごとの映画タイトル（一部） 76

vi

(8)

5.1 マルコフ決定過程モデルにおける変数間の関係を表すイメージ図 . . . 22

6.1 評点行列R（N = 6, M = 5, V = 5）． . . . . 42

6.2 評点行列Rにおける各周辺評点分布（N = 6, M = 5, V = 5）．(a)評点済みと(b)未評点の分布間のKLダイバージェンスを最小化することで，未評点箇所の値を予測する． . . . . 43

7.1 提案手法による共クラスタリング結果． . . . . 77

7.2 無限関係モデルによる共クラスタリング結果．. . . . 77

7.3 上位Lアイテムクラスに対する各手法の再現率． . . . . 79

vii

(9)

1

第 1 ^{章序論}

1.1 はじめに

産学両面において，推薦（レコメンデーション）システムに関する様々な研究が盛んに行われている[1, 40, 58, 59, 60]．そこでは，過去に購入された商品等によって表現される大量の履歴から，機械学習やデータマイニング等のデータ分析技術を利用して，ユーザごとに推薦商品を決定するためのルール（推薦ルール）を自動で導出する研究が進められている．特に，Amazon.com等のEC（Electronic Commerce，電子商取引）サイトにおいては既に実用化が始まっている．また，最近では，Hadoop[44]

を利用することで，大規模なデータに対しても簡単に推薦方式を実装できるようにもなっている[31]．

ここで，殆どの従来手法に共通する点として，推薦を行いたいユーザ（推薦対象ユーザ）と商品の購入履歴が類似している別のユーザ（もしくはユーザグループ）の購入商品履歴に基づいて，推薦対象ユーザに対する推薦商品を決定することが挙げられる（ユーザではなく商品を軸にした手法も考えられている）．従って，推薦対象ユーザへの推薦商品を考える際，ユーザ本人の購入商品履歴だけでなく，別のユーザの購入商品履歴も利用しているという点で，履歴に関するユーザの広がりがあると捉えることができる．言うなれば，従来手法は，空間的な視点に基づく推薦方式と意味づけることができる．さらに，その他の共通点として，推薦対象ユーザに対して推薦する商品は，過去にどのような商品を推薦してきたかに関わらず，毎回独立に決定され，かつ，推薦した結果が評価されていない点が挙げられる．ECサイトの例で言うと，クリック率やコンバージョン率などの指標によって評価されることもあるが，推薦手法とは独立に実施されており，推薦手法自体は推薦した結果に対する評価を考慮していない．すなわち，1回きりの推薦を想定した手法であり，

空間的な視点と対比した表現を用いると，従来手法においては，推薦に関して時

(10)

間的な要素は殆ど考慮されてこなかった．

しかし，推薦システムが実際に適用されることの多い電子商取引サイトを考えると，同じユーザに対して時間間隔を空けて推薦を繰り返し行うことが想定される．そのようなサイトにおいては，ただ単にその時に購入して貰えそうな商品を1度だけ推薦するのではなく，当該サイトをより長く利用して貰えるような商品を継続して推薦していくことが重要となる．そのため，推薦ルールの導出にあたっては，次に示すような，時間的な視点を考慮する必要がある．すなわち，推薦対象ユーザに対して，これまでどのような商品を推薦し，その結果，どのような効果が得られてきたか，言い換えると，ある時点までの購入商品履歴のみならず，過去の推薦商品履歴についても，それらの前後関係を踏まえた上で，推薦ルールを導出する必要がある．推薦することの効果を，より現実に即した形で評価できる枠組みを検討すべきである．

ただし，実際には，推薦対象ユーザ1人分の購入商品履歴と推薦商品履歴の数は非常に少ないことが殆どであり，わずかな履歴から有用な推薦ルールを導出することが困難になる場合が多い．そのため，履歴数の少なさを補うために，別のユーザの購入商品履歴と推薦商品履歴を利用することが必須となる．

1.2 ^{本研究の目的}

以上をまとめると，推薦ルールの導出時には，今回新たに導入する時間的な視点と従来手法における空間的な視点の両方に基づき，購入商品履歴と推薦商品履歴の両履歴から，推薦ルールを学習する方式を検討することが重要である．

そこで，本論文では，

• 空間的な視点：推薦対象ユーザ以外のユーザの履歴も利用する．

• 時間的な視点：時間的な情報を含めた履歴を利用する．

推薦した結果，得られる効果を評価する．

同一ユーザに対して行われた複数回の推薦に対する効果を，

それらの順序も踏まえて評価し，その評価値を直接最大化する．

(11)

第 1章序論 3

の考えに基づいた推薦方式の例として，3つの手法を提案する．1つは，空間的な視点と時間的な視点の両方に基づく手法であり，残りの2つは，空間的な視点に基づく手法である．ここで，空間的な視点に基づく2手法は，それぞれ単独でも推薦ルールの導出が可能であるが，1つ目の提案手法（空間的／時間的な視点の両方を併せ持つ手法）に対するサブルーチンとしても転用可能な手法となっている．

なお，利用する履歴データには個人情報が含まれるため，当該データの扱いには十分注意する必要がある．例えば，個人が特定できないようにマスキング処理を実施することや，データを扱える分析者を限定すること，さらには，外部とは遮断された分析環境を用意することなどが考えられる．本論文においては，これらの処理が事前に施されたことを前提として議論を進めるものとする．

1.3 本論文の構成

本論文の構成は次のとおりである：まず第2章で，本論文全体を通して扱う履歴データに関する定義を行い，第3章で従来の推薦方式を概説する．続いて第4章で本研究の概要を説明した後，第5章から第7章において，提案する3つの推薦方式の詳細をそれぞれ説明する．そして第8章において，第6章と第7章で提案する推薦方式に関する応用について述べ，最後に第9章でまとめと今後の課題について述べる．

(12)

第 2 ^{章準備}

2.1 履歴データの定義

本論文で扱う履歴データに関する定義を行う．時系列形式で表現する場合と行列形式で表現する場合があるため，それぞれ定義する．この章では，本論文を通して，

共通して使用する変数のみ定義する．各章に閉じて使用する変数については，該当する章においてそれぞれ定義するものとする．

2.1.1 時系列形式での表現

ユーザの購入商品履歴とそのユーザに対する推薦商品履歴の2種類の履歴データがN 人分あるものとする．ただし，両履歴においては，ユーザiごとに以下に示すような順番が分かっているものとする．

a_n_i₋_1(i), x_n_i₋_1(i), . . . , a₋_2(i), x₋_2(i), a₋_1(i), x₋_1(i), a_0(i), x_0(i), i= 1,2, . . . , N.

ここで，a_t(i)(t=· · · ,−2,−1,0)は，時点tにおいてユーザiに対して推薦された商品を表し，xtは商品atが推薦された後にそのユーザiが購入した商品をそれぞれ表すものとする．n_iはユーザiの履歴数を表す．

また，購入商品と推薦商品はいずれも同じ商品集合Iに含まれるものとし，

x_t(i), a_t(i)∈ I ={1,2, . . . , M}, t=. . . ,−2,−1,0,1,2, . . . , i= 1,2, . . . , N, 時点tまでのユーザiの購入商品履歴，および，推薦商品履歴をそれぞれx^t_(i), a^t_(i)と表す．さらに，両履歴をまとめた履歴データをD(i)で表し，ユーザN人分をまとめてDで表すものとする：

D={D(1),D(2), . . . , ,D(N)}={x⁰_(i), a⁰_(i)}^N_i=1.

(13)

第 2章準備 5

2.1.2 行列形式での表現

評点行列

N 人のユーザが M 個のアイテムに対して与えた評点からなる N 行 M 列の評点行列をR とする．R の (i, j) 要素 r_i,j は，i 番目のユーザのj 番目のアイテムに対する評点を表す．評点ri,j は {1,2, . . . , V}の離散値をとり，値が大きいほど良い評価を意味するものとする．ただし，未評価であるr_i,j の値は0とする．また，ˆr_i,j はr_i,j の予測値を表す．以降，iをユーザインデックス，j をアイテムインデックスとし，特にアクティブユーザのインデックスをi_act，ターゲットアイテムのインデックスをj_tarとする．

ユーザi が既に評価した（未評価の）評点の集合をRⁱobs（Rⁱmis）と表す．同様に，

アイテムj に対して既に評価が与えられた（未評価の）評点の集合を R^j_obs（R^j_mis）と表す．また，評点行列R において，既に評価が与えられた（未評価の）評点の集合をRobs（Rmis）と表す．さらに，予測対象の評点集合をRtar（Rtar ⊆ Rmis）とおく．

ここで，既評価の評点数 #{Robs}は，未評価の評点数 #{Rmis} に比べてはるかに小さいことに注意する（#{Robs} ≪#{Rmis}）．ここで，#{}は集合の要素数を表す．推薦問題においてベンチマークデータとしてよく用いられる映画の評価データにおいては，評点行列Rの約95% 以上の評点が未評価である．ただし，予測対象とする評点数は既評価の評点数とほぼ同等であるものとする（#{Rtar} ≈#{Robs} ≪

#{Rmis}）．

購買行列

N 人のユーザとM 個のアイテムからなる，N×M 行列の購買行列をBとする．

ただし，Bの第(i, j)要素b_i,jは，ユーザiとアイテムjの購買関係，

b_i,j =

{ 1, ユーザiはアイテムjを購入済, 0, ユーザiはアイテムjを未購入,

を表す．評点行列の場合と同様に，購入された履歴数（b_i,j= 1である要素数）は，行列全体のサイズN ×Mと比べて非常に少なく，行列が疎である性質を持つ．

(14)

2.2 問題設定

ユーザの履歴データをもとに，次に推薦する商品を定めるためのルール（推薦ルール）を自動で抽出する問題を考える．個別の設定については，章ごとに説明するものとする．

(15)

7

第 3 ^{章従来研究}

3.1 従来の推薦手法

従来の推薦手法は，以下のように3つのタイプに分けて説明することができる [1, 54]：

1. メモリーベースアルゴリズム：

利用者間の購買履歴データの類似性をもとに推薦する商品を決定する．協調フィルタリング[25, 35, 36, 46]などが提案されており，購買履歴が類似している利用者の間で人気のある商品を推薦する．最近傍法に基づくアプローチとも呼ばれる．

2. モデルベースアルゴリズム：

購買履歴データに対して確率モデルを当てはめ，得られたモデルをもとに推薦する商品を決定する．顧客セグメントを潜在クラスによって表現した潜在クラ

スモデル[17, 55, 56]などが提案されており，購入される確率の高い商品を推

薦する．確率モデルに基づくアプローチとも呼ばれる．

3. ハイブリッドアルゴリズム：

メモリーベースアルゴリズムとモデルベースアルゴリズムを足し合わせた手法 [39]．

以降，メモリーベースアルゴリズムとして代表的な最近傍法に基づくアプローチと，モデルベースアルゴリズムとして代表的な確率モデルに基づくアプローチを概説する．

(16)

3.2 最近傍法に基づくアプローチ

このアプローチでは，類似ユーザを評点履歴データベースから抽出し，類似ユーザの評点済みの評点を用いて予測を行う．アルゴリズムが単純なため実装が容易で，

実用化されている[25, 35]．ここで，類似ユーザに基づいて予測を行う手法[35]に対して，最近では，類似アイテムに基づいて予測を行う手法[25, 11, 36]も提案されている．後者は，評点行列Rを転置した行列に対して，従来通りの最近傍法に基づく予測手法を適用する手法である．以降，類似ユーザ（類似アイテム）に基づく手法をuser-base（item-base）と呼ぶ．通常，ユーザ数N よりもアイテム数Mの方が少ないため，類似ユーザを探索するよりも類似アイテムを探索する方が計算時間の点で優れている．以下，このアプローチに基づく2つの従来手法について説明する．

3.2.1 k 近傍法（ kNNs ）

何らかの類似尺度を用いて抽出したk人（個）の類似ユーザ（アイテム）のターゲットアイテム（アクティブユーザ）に対する評点を，類似度によって重みづけた値により予測を行う[25, 35, 36]．具体的には以下の式により予測値を求める．

user-base : rˆ_i_act_,j_tar =

∑k

i=1W_iⁱ_act(r_i,j_tar−r¯_i)

∑k

i=1|W_iⁱ_act| + ¯r_i_act, item-base : rˆ_i_act_,j_tar =

∑_k

j=1W_j^j

tar(r_i_act_,j−r¯_j)

∑k

j=1|W_j^j_tar| + ¯r_j_tar. ここで，W_iⁱ

actはアクティブユーザi_actとユーザiの類似度を表す．同様に，W_j^j

tarはターゲットアイテムj_tarとアイテムjの類似度を表す．

kNNsを適用する際には，使用するデータに依存して，類似性を測る対象，類似尺度，近傍数kを決定する必要がある．

3.2.2 Unified method with Similarity Fusion （ SF ）

user-base kNNsとitem-base kNNsを統合，拡張した手法である[43]．類似ユーザと類似アイテムからなる評点行列に存在する全ての評点済みの評点（Rnnsとおく）

(17)

第 3章従来研究 9

と，個々の評点に対する重みを用いた重み付き平均により予測する．そのため，類似ユーザのターゲットアイテムに対する評点や，類似アイテムのアクティブユーザに対する評点だけでなく，類似ユーザの類似アイテムに対する評点も予測式に取り込まれることになる．予測式は以下で表される．

ˆ

r_i_act_,j_tar = ∑

ri,j∈Rnns

W_i^i,j

act,jtarf_i_act_,j_tar(r_i,j), fiact,jtar(ri,j) = ri,j −(¯ri−¯riact)−(¯rj −¯rjtar).

ここで，W_i^i,j

act,jtarはr_i_act_,j_tarに対するr_i,jの重みを表す．

SFは，1つの評点を予測するごとに，類似ユーザと類似アイテムの抽出を行う必要がある．

3.3 確率モデルに基づくアプローチ

このアプローチでは，各評点が生成される確率モデルを仮定し，過去のデータをもとに学習したモデルを用いることで，将来の評点を予測する[17, 27, 26, 45, 48]．予測対象の評点が離散値（1,2, . . . , V）であることから，各評点が従う分布として多項分布が仮定される．評点を予測する際には，以下で定義されるmedian rating[27]，

{ r

Pr{r_i_act_,j_tar < r} ≤ 1 2, 1

2 ≤Pr{r_i_act_,j_tar > r} }

, や，評点の平均値，

∑V r=1

rP r{r_i_act_,j_tar =r},

が，r_i_act_,j_tar の予測値rˆ_i_act_,j_tar として用いられる．以下，このアプローチに基づく4 手法について説明する．

3.3.1 多項分布モデル（ MULTI ）

ユーザに依存せず，各アイテムの評点分布に対して1つの多項分布を仮定するモ

デル[27]．多項分布のパラメータ（各評点の出現確率）は式(6.2)により計算する．

(18)

アイテムjの評点が従う多項分布をp(r_i,j|j)で表すと，ユーザiの評点が従う結合評点分布は以下で表される．

p(r_i,1, r_i,2, . . . , r_i,M) =

∏M j=1

p(r_i,j|j)^δ(r^i,j^̸⁼⁰⁾.

3.3.2 混合多項分布モデル（ MIXMULTI ）

ユーザは幾つかの嗜好の似通ったグループ（潜在クラス）に分かれると仮定する

モデル[27]．つまり，同じ潜在クラスに属すユーザの評点は，アイテムごとに同一の

多項分布に従うと仮定する．ユーザiの評点が従う結合評点分布は以下で表される．

p(r_i,1, r_i,2, . . . , r_i,M) =

∑C c=1

p(z_c)

∏M j=1

p(r_i,j|j, z_c)^δ(r^i,j^̸⁼⁰⁾.

ここで，p(z_c)はクラスz_cが生起する確率，p(r_i,j|j, z_c)はクラスz_cにおけるアイテムjの評点が従う多項分布をそれぞれ表す. 明らかに予測精度はクラス数Cに依存する．

3.3.3 Aspect Model （ AM ）

ユーザはC個の潜在クラスに分かれ，同じ潜在クラスに属すユーザの評点は，アイテムごとに同一の多項分布に従うと仮定するモデル[17, 27]．MIXMULTIと異なる点は，AMではアイテムごとにユーザが属すクラスが異なること（ユーザが複数のクラスに属すこと）を許している点である．ユーザiの評点が従う結合評点分布は以下で表される．

p(r_i,1, r_i,2, . . . , r_i,M) =

∏M j=1

∑C c=1

p(z_c|i)p(r_i,j|j, z_c)^δ(r^i,j^̸⁼⁰⁾. (3.1) ここで，AMは潜在クラスの出現確率をユーザで条件付けるため，新規ユーザに対して予測を行う場合にはモデルの再学習が必要であること（生成モデルではないこと）に注意．このモデルは情報検索の分野で考案されたpLSA[18]を推薦問題に適用したモデルである．

(19)

第 3章従来研究 11

3.3.4 User Rating Profile Model （ URP ）

式(3.1)中のp(z_c|i)をp(z_c|θ)p(θ;γ)で置き換えることでAMを拡張し，厳密に生成モデル化したモデルである[27, 26]．ここで，p(θ;γ)はγを既知のハイパーパラメータとするディリクレ分布を表す. ユーザiの評点が従う結合評点分布は以下で表される．

p(r_i,1, r_i,2, . . . , r_i,M;γ) =

∫

θ

p(θ;γ)

∏M j=1

∑C c=1

p(z_c|θ)p(r_i,j|j, z_c)^δ(r^i,j^̸⁼⁰⁾dθ.

URP は AM のように新規ユーザに対する予測を行う度にモデルを再学習する必要はないが，推定すべきパラメータ数が増え，学習はAM に比べて複雑になる．

(20)

第 4 ^{章本研究の概要}

4.1 従来の推薦方式における視点

殆どの従来手法に共通する点は，推薦を行いたいユーザ（推薦対象ユーザ）と商品の購入履歴が類似している別のユーザ（もしくはユーザグループ）の購入商品履歴に基づいて，推薦対象ユーザに対する推薦商品を決定することにある（ユーザではなく商品を軸にした手法も考えられている）．従って，推薦対象ユーザへの推薦商品を考える際に，そのユーザの購入商品履歴だけでなく，別のユーザの購入商品履歴も利用しているという点で，ユーザに関する広がりがあると捉えることができる．言うなれば，従来手法は，空間的な視点に基づく推薦方式であると意味づけることができる．なお，購入商品履歴は，1年前に購入された商品も，昨日購入された商品と区別されることなく，同じ購入履歴として利用される．さらに，その他の共通点として，推薦対象ユーザに対して推薦する商品は，過去にどのような商品を推薦してきたかに関わらず，毎回独立に決定され，かつ，推薦した結果が評価されていないことが挙げられる．つまり，1回きりの推薦を想定した手法であり，空間的な視点と対比した表現を用いると，従来手法においては，推薦に関して時間的な要素は殆ど考慮されていない．

4.2 本研究における視点

しかし，推薦システムが実際に適用されることの多い電子商取引サイトを考えると，商品の推薦は1 回きりではなく，同じユーザに対して推薦を複数回に渡って行うことが想定される．そこでは，当該サイトをより長く利用して貰うことが重要となる．

(21)

第 4章本研究の概要 13

そのため，推薦ルールの導出にあたっては，次に示すような，時間的な視点を考慮する必要がある．すなわち，推薦対象ユーザに対して，これまでどのような商品を推薦し，その結果，どのような効果が得られてきたか，言い換えると，ある時点までの購入商品履歴のみならず，過去の推薦商品履歴についても，それらの前後関係を踏まえた上で，推薦ルールを導出する必要がある．

• 空間的な視点として，

推薦対象ユーザ以外のユーザの履歴も利用する．

• 時間的な視点として，

時間的な情報を含めた履歴を利用する．

推薦した結果，得られる効果を評価する．

同一ユーザに対して行われた複数回の推薦に対する効果を，

それらの順序も踏まえて評価し，その評価値を直接最大化する．

などである．

ただし，実際には，推薦対象ユーザ1人分の購入商品履歴と推薦商品履歴の数は非常に少ない．そのため，推薦ルールの導出時には，今回新たに導入する時間的な視点と従来手法における空間的な視点の両方に基づき，購入商品履歴と推薦商品履歴の両履歴から，推薦ルールを学習する方式を検討することが重要である．

4.3 提案する推薦方式の全体像

本論文においては，上記考えに基づいた推薦方式の例として，3つの推薦手法を提案する．1つは，空間的な視点と時間的な視点の両方に基づく手法であり，残りの2つは，空間的な視点に基づく手法である．以降で，提案する3つの推薦手法の概要を述べる．

4.3.1 時間的な視点と空間的な視点の両方を考慮した推薦手法

1つ目の推薦手法として，履歴の順序を考慮した確率モデルをもとに，推薦対象ユーザ以外の履歴も利用して推薦ルールを統計的に学習することで，時間的な視点

(22)

と空間的な視点の両方を考慮した手法を提案する．

具体的には，時間的な視点を導入するため，マルコフ決定過程モデルを利用する．

ここで，マルコフ決定過程モデルとは，現在の状態と，その時に実施した行動に依存して，次の状態への遷移が確率的に定まる確率過程である（この確率は状態遷移確率と呼ばれる．現在の状態とそのときにとった行動を条件部に持つ，

次の時点の状態に関する条件付確率である）．なお，状態が遷移する度に，遷移後の状態に紐づく利得が得られる．そこで，商品の購入等のユーザの反応結果を状態，商品の推薦を行動，商品が売れた時に得られる収入を利得とすることで，マルコフ決定過程モデルを推薦問題へ適用する．推薦ルールは，割引総利得を最大化するようなルールとして得る．ここで，割引総利得とは，将来に渡って得られる利得の重み付き期待値であり，直近で得られる利得ほど大きな重みが与えられる．

推薦問題へ適用するためのマルコフ決定過程モデルの一般化

ただし，既存のマルコフ決定過程モデルは，上述した通り，次に遷移する状態は，

直前の状態とその時に実施した行動にのみ依存するという制限を持つ．すなわち，次に購入する商品は，直前に購入した商品とその時に推薦された商品にのみ依存するモデルしか表現できない．しかし，実際には，2つ前に購入した商品や，3つ前に推薦された商品等，過去の様々な時点における履歴に依存して，次に購入する商品が定まると考える方がより自然である．故に，既存のマルコフ決定過程モデルを一般化したもとで，推薦問題へ適用する．ただし，一般化とは，直前の状態や行動だけでなく，状態と行動に関して過去の任意の時点の履歴を条件部に持つことが表現可能な状態遷移確率を設定することを意味する．

統計的決定理論に基づく最適な推薦ルールの学習

以上の内容は，状態集合や状態遷移確率など，全ての変数は既知であるもとでの議論である．本論文では，さらに，推薦問題への適用を想定し，状態遷移確率を未知とした問題を検討する．ここで，状態遷移確率が未知であるとは，状態遷移確率

(23)

の構造自体が未知であることを意味する．そのため，解くべき問題は，履歴データから推薦ルールを求める問題に変わり，推薦ルールの導出手順を新規に検討する必要が生じる．なお，状態遷移確率を未知とした問題設定はこれまでにも考えられているが，状態遷移確率の構造自体は既知の場合に限られている．

すなわち，一般化したマルコフ決定過程モデルにおいて，何時点前の履歴に依存して次に購入する商品が決定するかを事前に把握することは通常困難である．そこで，マルコフ決定過程モデルにおける状態遷移確率の構造は事前には未知（条件付き確率の条件部に入る変数群が未知）としたもとで，推薦対象ユーザ以外の履歴も利用した推薦ルールの導出法を提案する．具体的には，統計的決定理論（特にベイズ決定理論）に基づいて推薦ルールを学習する手法を提案する：割引総利得を最大化するのではなく，未知であるモデルとモデルパラメータに関する事前分布で割引総利得をさらに平均化したベイズ期待効用を最大化することにより，ベイズ基準のもとで最適な推薦ルールを得る．人工データを用いた評価実験により，従来の推薦方式や，既存のマルコフ決定過程モデルを用いた場合よりも，より多くの割引総利得が得られることを確認する．

1つ目の推薦手法では，推薦ルールの導出時に，推薦対象ユーザ以外の時間情報を含んだ履歴が利用され，かつ，推薦することの効果を利得によって表現した効用関数をもとに推薦ルールが導出されており，冒頭に述べた2つの視点を考慮した手法となっている．特長として，既存の確率モデルを拡張した点，さらに，最適性を保証した推薦ルールの導出法を示した点が挙げられる．

4.3.2 空間的な視点を考慮した推薦手法 1

2つ目の推薦手法として，商品購入履歴ではなく，購入した商品に対する評価値

（例えば，1〜5点満点評価などの離散値）を利用した手法を提案する．つまり，空間的な視点に基づき，推薦対象ユーザ以外のユーザの評価値履歴も利用して統計的学習を行うことで，推薦対象ユーザが未購入である商品に対する評価値を予測する

（欠損値を補間する方法として捉えることもできる）．推薦する商品としては，予測された評価値の大きい商品が選択される．

具体的には，まず，全ての評価値が与えられた状態から，ランダムに欠損が発生

(24)

した結果，今現在の評価済み履歴が得られているとの仮定を置く．すると，評価済みの履歴から算出されるユーザごとの評点分布，商品ごとの評点分布，および，全評点に対する評点分布（いずれも多項分布によって表現される）が，予測対象の未評価商品に対して同様に算出されるそれぞれの評点分布と類似していると見なせる．

そこから，評点済みの履歴に対する各評点分布と，未評価商品に対する各評点分布との間の類似度を最小化する問題に帰着させることにより予測値を一括して求める．

ここで，分布間の類似度として，分布間の擬距離を表すＫＬダイバージェンスを用いる．映画に対する評価値履歴データを用いた実験の結果，未評価商品に対する評価値の予測精度は，従来の代表的手法とほぼ同程度であるが，計算時間の面で顕著な優位性を持つことを示す．

提案手法の特長は，従来手法が評価値の予測を商品ごとに独立に行うのに対して，

提案手法は予測対象の評価値に対する予測値を互いに依存させ，予測対象の評価値全てを一括して高速に予測する点にある．

4.3.3 空間的な視点を考慮した推薦手法 2

3つ目の推薦手法として，空間的な視点に基づき，推薦対象ユーザ以外の商品購入履歴も含めたモデル学習に基づく手法を提案する．ここで，提案手法は，ユーザと商品を同時にクラスタリング（共クラスタリング）することができる確率モデルに基づく．共クラスタリングの結果，同じ商品を購入しているユーザクラスタと，同じユーザに購入されている商品クラスタが同時に得られ，得られたクラスタごとに推薦ルールを定めることができる（例えば，同じクラスタに属す他のユーザがよく購入している商品を含む商品クラスタ中の商品を推薦する）．

具体的には，ユーザと商品の共クラスタリングにディリクレ過程混合モデルを用いる．ここで，ディリクレ過程混合モデルとは，複数の分布を足し合わせることで表現される混合分布において，その混合数についても確率分布（ディリクレ過程事前分布）を仮定するモデルである．ここで，混合数はクラスタ数に対応する変数である．これにより，各分布のパラメータだけでなく分布の混合数についても，パラメータ学習として履歴から統計的に学習することが可能となる．提案手法は，ユーザ（もしくは商品）クラスタごとに商品（もしくはユーザ）クラスタ数次元の多項

(25)

分布を仮定し，互いに同じクラスタを選択しあったときに購入行動が生じると仮定したモデルに基づいて共クラスタリングする．実データを用いた実験により，ディリクレ過程混合モデルに基づく従来手法（無限関係モデル）と比べて，より精度の高い推薦ルールが得られることを示す．

提案手法の特長は，商品購入履歴のような欠損を含むデータが表現可能な確率モデルに基づいている点にある．

4.4 本研究の意義

商品を推薦した結果，ユーザにどのような反応（行動）を示して欲しいか，という推薦すること自体の本来の目的について，当該分野ではこれまで殆ど考慮されてこなかった．しかし，推薦の本質とは，推薦対象ユーザとの1対1のやり取りの中で得た，当該ユーザのこれまでの反応をもとに，次の推薦商品を決定することにある．また,推薦する目的を明確にすることで，推薦問題において，初めて最適性について論じることができるようになった．本研究により，“真の推薦”が初めて実現可能となったと言える．

推薦手法に関する研究が始まった頃は，ユーザの反応履歴を蓄積することは技術的に困難な面もあったが，ここ最近では，推薦履歴やその反応履歴を蓄積する仕組みが整備されつつある．従って，本論文で主張する2 つの視点に基づく推薦方式の研究や実用化は今後さらに進んでいくものと考えられ，本研究は，新たな研究の方向性におけるひとつの礎として意味のある研究であると言える．

提案する3つの推薦手法を表4.1に整理する．

(26)

表 4.1: 各提案手法の位置づけ

PPPPPPPPPPPP 空間的な視点時間的な視点

従来手法[1]

最適性の保証なし第6章従来手法[16]

第7章

最適性の保証あり第5章

(27)

19

第 5 章ベイズ決定理論に基づくユニバーサルマルコフ決定過程モデル

推薦問題を扱うためのより一般化されたマルコフ決定過程モデルに対して，ベイズ基準のもとで最適な推薦ルールを履歴データから求める方法を提案する．提案手法の特徴は，ある商品を推薦した後に何が買われたのかを考慮していること，さらに，一回の推薦結果だけでなく一定期間内に行った複数の推薦結果を評価している点にある．ここで，従来の推薦手法と大きく異なる点は，推薦ルールを求めるためのプロセスを統計的決定問題として厳密に定式化したことにある．その結果，推薦する目的に対して最適な推薦が行えるようになった．人工データを用いた評価実験により，提案する推薦手法の有効性を示す．

5.1 はじめに

従来の推薦手法は，以下のように3つのタイプに分けて説明することができる [1, 54]：

1. メモリーベースアルゴリズム 2. モデルベースアルゴリズム 3. ハイブリッドアルゴリズム

ここで，上記3つのタイプに属す殆どの従来手法に共通する特徴として，商品を推薦した結果を考慮していない点を挙げることができる．つまり，過去に購入した

(28)

商品履歴（以降，購入商品履歴と呼ぶ）のみから次に推薦する商品を決める手法が殆どであり，ある商品を推薦した結果どのような商品が購入されてきたかを踏まえて，次に推薦する商品を決めていない．つまり，推薦した商品の履歴（以降，推薦商品履歴と呼ぶ）を考慮していない．

また，別の共通点として，推薦は1回のみ行うことを想定している点が挙げられる．しかし，会員制のECサイト等を考えると，同じユーザに対して，推薦は1回限りではなく複数回，継続的に行うことが想定できる場合もある[19]．

そこで，本章では，上記2点を考慮した推薦手法を提案する．すなわち，ある商品を推薦した後に何が買われたのかを考慮し，さらに，一時点の推薦結果だけでなく一定期間内に行った複数の推薦結果を評価する推薦手法を提案する．

ここで，その2点を考慮した従来手法として文献[16]がある．文献[16]では，マルコフ決定過程[50, 57]をベースにした推薦手法を提案しており，推薦商品履歴や推薦を複数回行うことが考慮されている．具体的には，直近に購入された3つの商品からなる順列をマルコフ決定過程モデルの1つの“状態”と見なし，次に購入される商品は，1時点前の状態とその時に推薦された商品によって確率的に定まるものと仮定する．そして，その仮定のもとで，将来に渡って得られる“利得”を最大化する

“定常政策”を求めている．ここで，定常政策は推薦ルールに該当し，商品3個分の

購入商品履歴ごとに推薦する商品が1つ定まる．

これに対して，本章では，商品購入履歴と推薦商品履歴を考慮するための，より一般化されたマルコフ決定過程モデル（ユニバーサルマルコフ決定過程モデル）を提案する．さらに，提案するモデルに対して，事前に得られている履歴データを用いて，最適な定常政策（推薦ルール）を求める方法を提案する．ここで，マルコフ決定過程モデルベースの従来手法[16]を含め，従来の推薦手法と大きく異なる点は，

推薦ルールを求めるためのプロセスを統計的決定問題として厳密に定式化したことにある．本章では特に，ベイズ決定理論に基づいて最適な推薦ルールを求める方法を提案する．提案手法を用いることにより，推薦する目的に合わせて，統計的決定の観点で常に最適な推薦が行えるようになる．

本章の構成は次のとおりである：まず，5.2節において，本章で扱う推薦問題を定義し，5.3節で，提案手法がベースとして用いるマルコフ決定過程モデルの概要を説明する．続いて5.4節で，マルコフ決定過程モデルをベースにした従来手法[16]を

(29)

第 5章ベイズ決定理論に基づくユニバーサルマルコフ決定過程モデル 21

説明した後，5.5節で一般化したマルコフ決定過程モデル（ユニバーサルマルコフ決定過程モデル）を提案し，さらに，統計的決定理論に基づいて最適な推薦ルールを導出する方法を提案する．5.6節で人工データを用いた評価を行い，最後に5.7節でまとめる．

5.2 ^問題設定

本節では，本章が対象とする推薦問題を定義する．各変数の定義は，第2章の定義（時系列形式による表現）に従うものとする．

本節では，履歴データDを蓄積したもとで，履歴(x⁰, y⁰)を持つ推薦対象ユーザに対する推薦商品を自動で決めるためのルール（推薦ルール）を求める問題を考える．ここで，推薦対象ユーザは，履歴データDに含まれるN人のユーザとは異なるユーザであるものとする．以下に，本節で想定する推薦の流れを整理する：

1. N 人分の履歴データDを蓄積する．

2. 履歴データDから推薦ルールを求める．

3. 2.で求めた推薦ルールを用いて，推薦対象ユーザに対して商品を推薦する．

4. 推薦対象ユーザが反応を示す（商品を購入する，何も購入しない等）．

5. （3.と4.を繰り返す）．

なお，推薦ルールの更新は考えないものとする¹．また，各時点では常に1個の商品を推薦するものとする（複数個への拡張は自然に行われる）．さらに，推薦対象ユーザによる同一商品の購入は1度きりでも複数回でも良いものとする．

以上の設定のもとで，本章では，一定期間内に行った複数の推薦結果を評価する．

すなわち，時点t= 1以降に購入された商品x₁, x₂, . . . がもたらす利益を最大にする推薦ルールを求めることを本章の目的とする．

1本章では，商品が購入される度に得られる履歴データを用いて推薦ルールを逐次更新することは想定しない．実際，推薦ルールの更新は，月に1回更新する等，定期的に行われる場合が多い．

(30)

利得系列行動系列状態系列

時点

図 5.1: マルコフ決定過程モデルにおける変数間の関係を表すイメージ図

5.3 準備：マルコフ決定過程モデル

本節では，従来手法及び提案手法がベースとして用いるマルコフ決定過程モデルの概要を説明する．ここで，（有限）マルコフ決定過程モデルは，以下の4つの要素で構成される確率過程である：

• 有限状態集合：S ={1,2, . . . , S},

• 有限行動集合：A ={1,2, . . . , A},

• 状態遷移確率：{p(s|s^′, a)|s, s^′ ∈ S, a∈ A},

• 利得集合：{r(s, a)|s∈ S, a ∈ A}.

各構成要素間の関係を5.1に示す．5.1が示すとおり，時点tの状態s_t∈Sは，1つ前の時点の状態s_t₋₁∈ Sと時点tでの行動a_t∈ Aにのみ依存して確率的に定められる．つまり，時点tの状態s_tは，条件付確率p(s_t|s_t₋₁, a_t)に従って定まる（この条件付き確率は状態遷移確率と呼ばれる）．ここで，時点tにおける行動atは，時点 tでの状態s_tに基づいて決定される．このとき，状態に基づいて次の行動を定めるルールを政策d(s_t)と呼ぶ．さらに，行動a_tを選択したもとで状態s_tに遷移した場合には，利得r(s_t, a_t)が得られるものとする．

上に示した4つの要素全ての値が既知であるもとで，最適な政策d(s_t)を求める種々の方法が提案されている（価値反復法，動的計画法など[2]）．ここで，最適な

(31)

政策とは，以下の式で表される割引総利得（一定期間の間に得られる利得の総和），

∑T t=1

γ^t⁻¹r(s_t, a_t), (5.1)

を最大化する政策であることを意味する．ただし，現在の時点をt= 0とし，γ(0<

γ <1)は割引率を表す．式(5.1)は，一定期間内に得られる全ての利得において，直

近に得られる利得ほど重視することを意味している．

5.4 従来手法

本節で設定した問題に対する従来手法として文献[16]がある．具体的には，以下のような対応付けを行うことで，マルコフ決定過程モデルを推薦問題に適用している：

• 推薦対象ユーザが購入する商品x_t(t=. . . ,−2,−1,0,1,2, . . .)は，以下に示す状態遷移確率に従うものとする：

x_t∼p(x_t|x_t₋₃, x_t₋₂, x_t₋₁, a_t;θ). (5.2) ここで，θは，状態遷移確率を規定する未知のパラメータである．式(5.2)は，

直前に購入された3つの購入商品履歴(x_t₋₃, x_t₋₂, x_t₋₁)とその時に推薦された商品a_tに依存して，次の商品x_tが選択されることを表している．

• 商品x_tが購入されることで得られる利益を，時点tにおける利得r(x_t)とし

（利得関数の引数に行動aが含まれないことに注意），将来に渡って得られる利得の合計を最大化する推薦ルールを求める．ここで，割引総利得は以下で表される：

∑∞ t=1

γ^t⁻¹r(x_t).

• 履歴(x⁰, a⁰)を持つ推薦対象ユーザに対する推薦ルールを，定常政策dとして表現する：

a_t=d(x_t₋₃, x_t₋₂, x_t₋₁).

(32)

ここで，定常政策とは，時点に依存せずに当該時点の状態のみによって選択すべき行動が定まる政策である．つまり，直前に購入された3つの購入商品履歴のみから，その時点での推薦商品が定まる．

• 推薦した結果，何も購入されなかった場合には利得を0とする．さらに，その場合には状態は変化しないものとし，前の時点と同じ状態にいるものとして次に推薦する商品を定める．

上記の対応付けは，商品3個分の購入商品履歴(x_t₋₂, x_t₋₁, x_t)を1つの状態s_tと見なしたマルコフ決定過程モデルとして解釈できる（5.1参照）．

ここで，定常政策dは，以下に示す期待割引総利得Vを最大化することで求められる[2]．

V((x₋₂, x₋₁, x₀), d, θ)

=

∑∞ t=1

γ^t⁻¹r(x_t)p(x_t|x_t₋₃, x_t₋₂, x_t₋₁, a_t=d(x_t₋₃, x_t₋₂, x_t₋₁);θ). (5.3) ただし，(x₋₂, x₋₁, x₀)は推薦対象ユーザの初期状態s₀を表す．

文献[16]で提案されている，推薦ルールの導出手順を以下に示す：

1. N 人分の履歴データDを蓄積する．

2. 履歴データDからパラメータθの最尤推定量θˆを求める．

3. 2.で求めたパラメータの推定値を式(5.2)に埋め込んだもとで，価値反復法を適

用する．すなわち，商品3個分の順列によって表現される状態を{x⁽¹⁾x⁽²⁾x⁽³⁾} と置いたとき（x⁽¹⁾, x⁽²⁾, x⁽³⁾∈ I），期待割引総利得Vから導かれる以下のベルマン方程式，

Vl+1({x⁽¹⁾x⁽²⁾x⁽³⁾}) = max

j∈I

∑

x⁽⁴⁾∈I

p(xt=x⁽⁴⁾|st−1 ={x⁽¹⁾x⁽²⁾x⁽³⁾}, at=j; ˆθ)

× {

r(x⁽⁴⁾) +γVl({x⁽²⁾x⁽³⁾x⁽⁴⁾})} ,

を用いて，状態ごとの評価値V({x⁽¹⁾x⁽²⁾x⁽³⁾})を求める．ここで，添え字l, l+ 1 は，計算上のループ回数を表すインデックスを表し，評価値Vの値が収束する

(33)

まで繰り返しVlの値をVl+1の値で更新する．そして，最終的に得られた評価値V^∗をもとに，推薦ルール（状態ごとに推薦する商品aを定めたルール）を求める：

a = d({x⁽¹⁾x⁽²⁾x⁽³⁾}),

= arg max

j∈I

∑

x⁽⁴⁾∈I

p(x_t=x⁽⁴⁾|s_t₋₁ ={x⁽¹⁾x⁽²⁾x⁽³⁾}, a_t=j; ˆθ)

× {

r(x⁽⁴⁾) +γV^∗({x⁽²⁾x⁽³⁾x⁽⁴⁾})} .

なお，文献[16]では，初期の履歴データDには推薦商品履歴は含まれないものとし，購入商品履歴のみから近似的に状態遷移確率を求める手法を提案している．具体的には，推薦された商品は，推薦されなかった場合と比べて購入される確率が上がる，という仮説を置いたもとで，混合多項分布を当てはめることで状態遷移確率を求める．ただし，実際に推薦を行っていくことで推薦商品履歴が蓄積された後は，

上記に示した手順のとおり，最尤推定により状態遷移確率が更新されるため，本章では，前述した近似的な算出法については考えないものとする．

文献[16]では，マルコフ決定過程モデルを用いた推薦ルールの方が，従来の推薦方式（モデルベースアルゴリズム）よりも，より多くの割引総利得が得られることを実験的に示している．すなわち，1人のユーザに対して推薦を複数回行うような場合には，商品を推薦した後のユーザの反応，及び，一定期間内に行った複数の推薦結果を考慮することの有用性が示されている．しかし，文献[16]では，既存のマルコフ決定過程モデルをそのまま推薦問題へ適用するに留まっており，より多くの推薦問題への適用を考えた場合，より表現能力の高いマルコフ決定過程モデルを用いる必要がある．また，その有効性は実験的に示されただけである．