Vol. 49

No. SIG 4(TOM 20)

Mar. 2008

情報処理学会論文誌：数理モデル化と応用

購買順序を効率的に用いた協調フィルタリング
岩

田

具

治†1

山

田

武

士†1

上

田

修

功†1

高速にパラメータ推定可能な購買順序を考慮した協調フィルタリング手法を提案する．これまでに購買履歴を入力とし次の購入商品を予測する協調フィルタリング問題において，購買順序を考慮した
マルコフモデルや最大エントロピーモデルが適用されている．マルコフモデルはパラメータの推定，更新を高速にできるが，予測精度が低いという問題点がある．一方，最大エントロピーモデルはパラメータ推定，更新に多くの計算量を必要とするが，予測精度は高い．提案法は，複数のマルコフモデ
ルを最大エントロピー原理を用いて統合することにより，高速性と高予測精度を同時に実現する．音楽，動画，漫画配信サービスの実ログデータを用い，提案法の有効性を示す．

Collaborative Filtering Eﬃciently Using Purchase Orders
Tomoharu Iwata,†1 Takeshi Yamada†1 and Naonori Ueda†1
We propose a new collaborative ﬁltering method that can predict the next purchase item by
eﬃciently using the sequential information in purchase histories for recommendations. Markov
models and maximum entropy models are both widely used techniques for such recommendations. In Markov models, parameters can be estimated and updated fast and eﬃciently,
but predictions may not be accurate. On the other hand, the accuracy of maximum entropy
models is generally high, however parameter estimation incurs a high computational cost. We
achieve both fast parameter estimation and high predictive accuracy by combining multiple
simple Markov models based on the maximum entropy principle. Experiments using real log
data sets of music, movie and cartoon distribution services show that the proposed method
outperforms other conventional methods found in the literature.

1. は じ め にる商品を予測する協調フィルタリング問題を扱う．次に購入する商品はユーザのその時点の興味を最も表し

リコメンデーションシステムはオンラインストアにていると考えられ，購入商品予測の精度が高い手法が，おいて広く用いられている18) ．ユーザが興味のある

興味の予測精度が高い手法であると考える．購買履歴と思われる商品を推薦することにより，ユーザは欲しは実際にサービスを展開しているオンラインストアでい情報により早くたどり着くことができ，また，オンあれば蓄積されるものであり，基本的なデータである

ラインストアにとっては収益の増加が見込まれるといといえる．一方，評点情報や商品情報は予測のためのう利点がある．リコメンデーションを実現するための有用な情報となりうるが，前者はユーザに評価の負担13),17)，コンテンツを課し，後者は新商品の発売ごとに人手でデータ登録

フィルタリング11) ，および，そのハイブリッド方式9)しなければならないという，実用上の問題点がある．

など数多く提案されている．協調フィルタリングでは，

そこで本論文では購買履歴のみに着目する．

手法として，協調フィルタリング

似た興味を持つ他のユーザの評点履歴や購買履歴を用

これまでに提案されている協調フィルタリング手法

いて興味を推定する．また，コンテンツフィルタリン

の大半は，商品の購買順序を考慮していない17) ．しかグでは，興味を推定するために商品情報を利用する．

し，昔購入した商品よりも最近購入した商品の方が次商品情報として，たとえば本の著者や映画のジャンルに購入する商品を予測するための情報がより多く含まなどが用いられる．

れると考えられる．簡単な例をあげると，ドラマの第本論文では，購買履歴のみを入力とし，次に購入す

1 話の DVD を借りたユーザは，次にそのドラマの第†1 日本電信電話株式会社 NTT コミュニケーション科学基礎研究
所
NTT Communication Science Laboratories, NTT Corporationともあるため，昔の購買履歴があまり参考にならない

2 話を借りる確率が高いだろうし，興味は変化するこ場合もあるだろう．また，直前に購入された商品のみを考慮する手法6),9) もしばしば使われるが，過去に購
125

126

Mar. 2008

情報処理学会論文誌：数理モデル化と応用入した多くの商品の情報を無視してしまっている．
本論文では，購買順序に着目した新たな協調フィル

た M (x, u) は全ユーザの購買履歴中に含まれる系列(x, u) = (x, x1 , · · · , xL ) の数

タリング手法を提案する．これまでに購買順序を考慮する手法として，マルコフモデルや最大エントロピー
モデルが協調フィルタリングに適用されている8) ．マ
ルコフモデルはパラメータの推定，更新を高速にでき

M (x, u) =

Kn
 



I (xn,k = x)n∈U k=L+1

∧(xn,k−1 = x1 ) ∧ · · · ∧ (xn,k−L = xL ) , (3)るが，予測精度が低いという問題点がある．一方，最を表し，M (u) は全ユーザの購買履歴中に含まれる系

大エントロピーモデルはパラメータ推定，更新に多く

列 u = (x1 , · · · , xL ) の数の計算量を必要とするが，予測精度は高い．提案法では，順序情報を扱うための複数の単純マルコフモデル
を最大エントロピー原理を用いて統合させることによM (u) =Kn I (xn,k−1 = x1 )n∈U k=L+1

り，高速なパラメータ推定かつ高い予測精度を実現す∧ · · · ∧ (xn,k−L = xL ) ,る．提案法は新規データ追加によるパラメータ更新もを表す．I(y) は y が真ならば 1，そうでなければ 0

高速にできる．オンラインストアでは時々刻々と購買をとる特性関数を表す．

(4)

履歴が蓄積されるため，高速なパラメータ更新は重要

マルコフモデルにおけるパラメータは，上式のようである．漫画，音楽，動画の配信サービスにおける実に閉形式で書くことができ，かつ，単純な和のみで計

購買履歴データを用い，提案法の有効性を評価する．

算できるため，推定に必要な計算量は少ない．また，

以下の本文では，まず 2 章で提案法の基礎となる

新たなデータが得られた際のパラメータ更新が以下のマルコフモデルと最大エントロピーモデルについて説ように容易にできる．まず，すでにある購買データに明し，3 章で本論文で提案する効率的に順序情報を利含まれる式 (2) の分子，分母に相当する系列の数をそ用する協調フィルタリング法について詳述する．4 章

れぞれ記憶する．そして，新たな購買データが追加さでは関連研究について述べる．そして 5 章でオンラれたとき，追加購買データに含まれるそれぞれの系列

インストアの実購買履歴データを用いて提案法の評価数を数え，記憶しておいた系列数に足すことで，パラを行い，6 章で結論と今後の課題を示す．

メータを更新できる．このとき既存の購買データを改2. 従 来 法

めて読み込む必要はない．しかし，L 次マルコフモデ

ユーザ集合を U ，商品集合を S ，ユーザ n が k 番

モデルではパラメータ数が膨大になるため，頑健なパ目に購入した商品を xn,k ∈ S ，そのときの購買履歴

ルのパラメータ数は O(V L+1 ) であり，高次マルコフ
ラメータ推定は困難であるという問題点がある．

を un,k = (xn,k−1 , · · · , xn,1 ) とする．また N を全商品 x を購入したという条件のもと l 個前に購入

ユーザ数，V を全商品数，Kn をユーザ n が購入しした商品と l 個前に購入した商品は独立であると仮た商品数とする．

定すると，下式

2.1 マルコフモデル
マルコフモデルは順序情報を扱う確率モデルとして

P (x1 , · · · , xL |x) =LPl (xl |x),

(5)

l=1

広く用いられている．L 次マルコフモデルでは，次に購入する商品は L 個前までの購買の履歴に依存し，のように分解でき，L 個前までの購買順序情報を用い，

P (xn,k |un,k ) = P (xn,k |xn,k−1 , · · · , xn,k−L ),(1)

かつ，パラメータ数を少なくすることができる．ここと 表 さ れ る ．L 個 前 ま で の 購 買 の 履 歴 を u

で Pl (x |x) は商品 x を購入した l 個前の商品が xである確率を表し，l ギャップマルコフモデル14) と呼=(x1 , · · · , xL ) とする．ここで xl は l 個前の購買商

ぶ．このとき購買履歴 u が与えられたもとで商品 x品を表す．L 次マルコフモデルにおける，購買履歴 uを購入する確率はベイズの定理より，が与えられたときの商品 x を購入する確率は，MAP
推定により

M (x, u) + δ,(2)
M (u) + δVとなる．ここで δ はハイパーパラメータであり，leaveone-out 交差検定法により推定することができる．まP̂ (x|u) =P (x|u) = 

P (x)P (u|x)
P (x )P (u|x )

x

= 

P (x)
x

L
P (xl |x)
l=1 l
,
L



P (x )l=1

Pl (xl |x )(6)となる．ここで P (x) は商品 x を購入する事前確率Vol. 49

No. SIG 4(TOM 20)127

購買順序を効率的に用いた協調フィルタリングを表す．このときのパラメータ数は O(LV 2 ) となる．

ても最大エントロピーモデルの優位性が確認されてい事前確率の MAP 推定値は

る8) ．しかし，最大エントロピーモデルのパラメータ I(xn,k = x) + δn kP̂ (x) =,n(7)

Kn + δVの推定値は，マルコフモデルとは異なり閉形式で求まらず，計算量の大きい準ニュートン法などの繰返し最となる．また同様に，l ギャップマルコフモデルの MAP

適化法を用いる必要がある．また，新たなデータが追推定値は，加されたとき，既存のデータも読み直す必要があり，P̂l (x |x)パラメータ更新も容易ではない．


I (xn,k = x) ∧ (xn,k−l = x ) + δ
k
 
,

 

=

n

n

k

I(xn,k = x) + δV

(8)

3. 提 案 法
提案法では，複数のギャップマルコフモデルを最大
エントロピー原理により統合することにより，マルコとなる．ここでハイパーパラメータの項を除いて考え

フモデルと同程度のパラメータ更新の容易性と，最大ると，分母は全ユーザの購買履歴中の商品 x の購買

エントロピーモデルと同程度の高い予測精度を同時に数，分子は商品 x の l 個前の購買が商品 xl である数実現する．
まず，事前確率 P (x) を式 (7) により，l ギャップマを表す．

2.2 最大エントロピーモデル
最大エントロピーモデルは，与えられたデータに関

ルコフモデル Pl (x |x)，l = 1, · · · , L を式 (8) により推定する．そして，購買履歴 u のとき商品 x を購入する制約を満たす確率分布のなかでエントロピーが最する確率 P (x|u) を，購買順序が反映されたものにす大となる分布を求める手法であり，協調フィルタリン

るため，P (x|u) によるギャップマルコフモデルの対

グ9),13),19) だけでなく，自然言語処理12) など幅広い

数尤度の期待値は，与えられたデータにおける対数尤

分野で応用されている．最大エントロピーモデルでは，度の経験的期待値と一致するという制約



購買履歴 u が与えられたとき商品 x を購入する確
率は

n


1
exp
P (x|u) =αf yf (x, u) ,
Z(u)
f ∈F

となる．ここで，Z(u) =



exp
x

=

(9)




n

if i = xl and j = x,otherwise,を用いる．このときのパラメータ数は LV

=
(10)


n

log P (xn,k |un,k ),

k


n

P (x|un,k ) log P̂ (x)xlog P̂ (xn,k ),

(13)

k

を設定する．最大エントロピー原理に従い，式 (12)，2となる．

未知パラメータ集合 {αf }f ∈F は，対数尤度J=l = 1, · · · , L,率の対数尤度の期待値も一致するという制約

た商品情報

0

log P̂l (xn,k−l |xn,k ),kを設定する．また，同様に全体的な人気を表す事前確

買順序を考慮するため，特徴量として l 個前に購入しyl,i,j (x, u) =n

P (x|un,k ) log P̂l (xn,k−l |x)

x

(12)

α y (x, u)
f f f

は正規化項，yf は特徴量，F は特徴量集合を表す．購1k(13) を制約条件として，P (x|u) のエントロピーを最大にする分布を求めると

P (x|u)(11)

k

を準ニュートン法10) などの最適化手法を用いて最大=凸性より，解の大域的最適性が保証される．過学習を=抑えるため，実験では未知パラメータの事前分布とし一般に，識別モデルである最大エントロピーモデル
は，生成モデルであるマルコフモデルに比べ性能が高いといわれており15) ，協調フィルタリング問題においL

l=1

化することにより推定できる．なお，目的関数 J のて平均 0 の正規分布を用いた1) ．


1
αl log P̂l (xl |x)
exp α0 log P̂ (x) +
Z(u)
L

α

1
P̂ (x) 0Z(u)P̂l (xl |x)αl ,l=1を得る．ここで Z(u) =lαl log P̂l (xl |x)


x

(14)



exp α0 log P̂ (x) +は正規化項，α = {αl }L
l=0 は未知パラメータ集合であり，α0 は事前確率の重み，αlは l ギャップマルコフモデルの重みを表す．提案モデ

128

情報処理学会論文誌：数理モデル化と応用

Mar. 2008

図 1 提案モデル：複数のギャップマルコフモデルの重み付き統合
Fig. 1 The proporsed model: multiple gapped Markov models are conbined with weights.

ルは L 個のギャップマルコフモデルを重みを付けて統である．実験では αl の事前分布として平均 0 の正規合した形となっており (図 1)，重みがすべて 1 のとき分布を用いた．

(αl = 1，l = 0, · · · , L)，各ギャップマルコフモデルが独立と仮定したモデルである式 (6) と一致する．換言提案モデルのパラメータ数は LV (V −1)+V +L である．このうち L 個のギャップマルコフモデルと事前すれば，提案モデルは独立ギャップマルコフモデルを確率に対応する LV (V − 1) + V − 1 のパラメータは，

特殊なケースとして包含する．

上述のように高速に求めることができ，また，データ

最大エントロピーモデルと同様に，式 (11) の対数尤追加にともなうパラメータ更新も容易である．多くの度を最大化することにより未知パラメータ集合 α を推計算時間がかかる繰返し最適化が必要なのは L + 1

定できる．ここで，事前確率およびギャップマルコフモ個の重み α のみである．そのため，O(LV 2 ) のパラ

デルの推定に用いた学習データを α の推定に用いるとメータの繰返し最適化が必要な最大エントロピーモデ

過学習を起こす可能性がある．そのため，M 重交差検ルと比べ，少ない計算量でパラメータを求めることが定法により α を推定する．まず，ユーザ集合 U を Mできる．

個の部分集合 {Um }M
m=1 に分割し，U −m = {U j }j=m

また，重み α は以前に学習したものを用い，事前確を用いて事前確率 P̂ (x; U−m ) およびギャップマルコ

率とギャップマルコフモデルのみを更新する場合，さフモデル P̂l (x |x; U−m ) を式 (15)，(16) で各々推定

らに計算量を削減することができる．事前確率やギャッする．

プマルコフモデルは新商品の発売開始の際など，大きn∈U −mP̂ (x; U−m ) =kn∈U −mI(xn,k = x) + δk

1 + δV

くそのパラメータが変化するが，l 個前の購買商品が,(15)
P̂l (x |x; U−m )n∈U −m=I(xn,k = x ∧ xn,k−l = x )+δkn∈U −mk

I(xn,k = x) + δV

次の購買に与える影響を表すギャップマルコフモデルの重みは新たにデータが追加されても急激には変化しないと考えられる．なお，α の再学習のために全デー
タを保持している必要がある．

.

4. 関 連 研 究(16)

複数の生成モデルの最大エントロピー原理による統そして，学習に用いなかった Um の対数尤度の和合は，タイトルや参考文献など複数の付加情報を含む

log P (xn,k |un,k ; U−m ), (17)

テキストデータの分類器設計3),15) で提案されており，

L=



単体の生成モデル，最大エントロピーモデルと比べ

m n∈U m k

を最大化することにより α を推定する．ここで報ではなく，順序情報を考慮するためにモデルを統合

P (x|u; U−m )
1P̂l (xl |x; U−m )αl ,P̂ (x; U−m )α0
Z(u)
L

=

高い分類性能が確認されている．提案法では，付加情

l=1

(18)

している．また，協調フィルタリング問題においてはデータが時々刻々と蓄積されるため，パラメータ更新
が高速に行えることが重要であるため，提案法では性能を下げることなくパラメータ更新を容易にすることVol. 49

No. SIG 4(TOM 20)129

購買順序を効率的に用いた協調フィルタリング

表 1 各データの開始日，終了日，ユーザ数，商品数，購買数
Table 1 The start date, end date, the number of users, items and transactions.

Music4
Music5
Music6
Movie
Cartoon1
Cartoon2
Cartoon3

開始日
2005/4/1
2005/4/1
2005/4/1
2007/1/1
2005/4/1
2005/4/1
2005/4/1

終了日
2005/4/30
2005/5/31
2005/6/30
2007/1/1
2006/1/31
2006/2/28
2006/3/31を目的に，生成モデルの統合を利用している．
遠い過去の購買情報を扱うため，共起関係が強い商

ユーザ数

商品数

購買数

247
1,120
2,104
3,085
42,18453,83069,217

132
348
561
1,569
153
161
175

1,508
7,588
15,21625,363453,386
599,196808,182

年 1 月 1 日の動画配信サービスにおける購買履歴であり，Movie と呼ぶ．漫画データは，携帯電話用漫画配品ペアのみをトリガとして素性に組み込んだ最大エン信サービスにおける購買履歴であり，2005 年 4 月 1 日

トロピーモデルが提案さている13) ．しかし，トリガモから 2006 年 1 月 31 日まで，2006 年 2 月 28 日まで，

デルでは過去の情報を扱うことはできるが，順序情報

2006 年 3 月 31 日までの 3 種類のデータセットを作成が無視されてしまう．購買時間を考慮した協調フィル

した．それぞれ Cartoon1，Cartoon2，Cartoon3 とタリング手法も提案されている2) ．彼らは経過時間に呼ぶ．ここで 1 つの漫画が複数巻あるものは同一の商応じて，パラメータの重みを指数減衰させることで，品として扱った．各データともに，売上数が 10 未満

最近のデータに重みを置いている．それゆえ，過去のの商品，および，購買数が 5 未満のユーザは省いた．

情報が有用な場合や，減衰が指数関数で近似できない

また，ある商品が 2 回以上同一ユーザに購入された場

場合には適切でない．

合，2 回目以降の購買は履歴から省いた．このときの，また言語処理の分野で，高次のマルコフモデルの頑各データのユーザ数，商品数，購買数を表 1 に示す．

健な推定のため，低次のマルコフモデルの線形和で補各ユーザの最後に購入した商品をテストデータ，それ間する，削除補間法が提案されている7) ．削除補間法

以前の購買履歴を学習データとして用いる．ここで，では，高次のマルコフモデルが必要であるため，膨大最後に購入した商品が学習データに含まれないものはな数のパラメータを記憶する容量が必要になるといテストデータから省いた．

う問題点がある．言語では文法などで単語の並びに規則性が高いため高次のマルコフモデルが必要であると考えられる．一方，購買履歴では言語ほど規則性が高くないため，l 個前に購入した商品の情報だけを持つ
ギャップマルコフモデルでも実用上十分と考えられる．
提案法はギャップマルコフモデルを最大エントロピー
原理に基づき統合したが，ギャップマルコフモデルを線形結合する手法が提案されている14) ．線形結合の場
合，混合係数およびギャップマルコフモデルを EM ア
ルゴリズムを用いて，収束するまで交互に推定する必
要がある．

5. 実

験

5.2 比 較 手 法
提案法を評価するため，以下の 9 つのモデルを用いて実験を行った．

OurMethod：提案法
Markov1：1 次マルコフモデル．式 (2) L = 1．
Markov2：2 次マルコフモデル．式 (2) L = 2．
Markov3：3 次マルコフモデル．式 (2) L = 3．
GapMarkov：各ギャップマルコフモデルがそれぞれ独立と仮定したモデル．式 (6)．
MaxEntSeq：特徴量として式 (10) を用いた，購買順序を考慮した最大エントロピーモデル．
MaxEnt：特徴量として下式を用いた，購買順序を考慮しない最大エントロピーモデル．

提案法を評価するため，音楽，動画，漫画の 3 種類の実購買履歴データを用い実験を行った．

yi,j (x, u) =1

if i ∈ u and j = x,0otherwise.

(19)

5.1 データセット
音楽データは，音楽配信サービスにおける購買履歴

Cosine：コサイン類似度に基づくアイテムベース

であり，2005 年 4 月 1 日から 2005 年 4 月 30 日ま協調フィルタリング17) ．商品 x と x のコサイン類似

で，2005 年 5 月 31 日まで，2005 年 6 月 30 日まで

度はの 3 種類のデータセットを作成した．それぞれ Mu-

sic4，Music5，Music6 と呼ぶ．動画データは，2007

sim(x, x ) = cos(r, r  ) =rT r
, r  r  

(20)

130

Mar. 2008

情報処理学会論文誌：数理モデル化と応用で表される．ここで r = (r1 , · · · , rN )T はユーザ n が商品 x を購入したことがあれば rn = 1，そうでなけ

sine，PLSA は購買順序を考慮しない手法である．
MaxEnt は何個前にどの商品を購入したかという順

れば rn = 0，を要素に持つ列ベクトル，r T はベクト序は考慮しないが，購買履歴 u が与えられたときの条

ル r の転置， ·  はユークリッドノルムを表す．商件付き確率 P (x|u) をモデル化するため，前後関係は品 x を購入する確率は購買履歴に含まれる商品との考慮する．つまり，商品 x の後に商品 x に購入する類似度の和ことはあるが，商品 x の後に商品 x に購入する可能P (x|u) ∝sim(x, x ),

(21)

x ∈u

性は低いなどをモデル化できる．一方，コサイン類似度は対称であり sim(x, x ) = sim(x , x)，また PLSAによって推定される．つまり，これまでに購入した商は商品 x とユーザ n の同時分布 P (x, n) をモデル化

品と似た商品は購入する確率が高くなる．この手法はしているため，Cosine と PLSA は前後関係も考慮し主に評点を予測する場合に利用される．パラメータ数

ない．

2

は O(V ) である．商品の類似度ではなくユーザの類

提案法における重み α は 10 重交差検定により推似度を基にした協調フィルタリング手法も提案されて定した．マルコフモデル，事前確率およびギャップマ

いる16) が，一般にユーザ数は商品数に比べて多いた

ルコフモデルにおけるハイパーパラメータ δ は leaveone-out 交差検定法により求めた．また，最大エント

め，より多くの計算量が必要となる．

PLSA：Probabilistic latent semantic analysis 4) ．
ユーザ n が商品 x を購入する確率はP (x|n) =P (x|z)P (z|n),

(22)

z

ロピーモデルにおいて，上記の特徴量に加え履歴に無関係な全体的な商品の人気を表すための特徴量

yi (x, u) =で与えられる．ここで z は隠れクラスであり，P (x|z)

10if i = x,otherwise,(26)

はクラス z に属するユーザが商品 x を購入する確率，もあわせて用い，パラメータの事前分布は分散 1 の正P (z|n) はユーザ n がクラス z に属する確率を表す．

規分布とした．

確率 P (x|z) および P (z|n) は対数尤度

5.3 結果
漫画，音楽，動画データにおける各手法の正答率を表 2 に，トップ 3 正答率を表 3 に示す．正答率は下

J=


n

log P (xn,k , n),

(23)

k

を EM アルゴリズムを用いて最大化することにより推定できる．PLSA は協調フィルタリングだけでな
く，情報検索や自然言語処理にも応用されている5) ．

式により計算した．
1 A=
I(xn,Kn = x̂(un,Kn )),
N

(27)

n

隠れクラスの数を Z としたとき，パラメータ数は

ここで xn,Kn はユーザ n の最後の購買商品を表す．

O(N Z + V Z) である．

また，x̂(u) は購買履歴 u が与えられたときの予測商

Mixture：混合ギャップマルコフモデル14) ．商品 xを購入する確率はギャップマルコフモデルの線形結合

品を表し，購買確率が最大の商品とする．

P (x|u) =Lx̂(u) = arg max P (x|u),x∈S −uP (l)Pl (x|xl ),

(24)

l=1

(28)

ここで S−u は購買履歴 u に含まれない商品の集合を表す．また，トップ 3 正答率とは購買確率が高い 3

で 表 さ れ る ．こ こ で P (l)≥ 0 は混合係数で

P
(l)
=
1
，
P
(x|x
)
は
l
個前の購買商品が x
ll=1

商品中に実際の購買商品が含まれる割合を表す．GapMarkov，MaxEntSeq，Mixture，提案法における最のとき商品 x を購入する確率を表す．混合係数 P (l)大ギャップ L，および，PLSA における隠れクラス

L



および確率 Pl (x|x ) は対数尤度

J=


n

log P (xn,k |un,k ),数 Z は本来交差検定などによりデータから学習すべ

(25)

k

を EM アルゴリズムによって最大化することにより推定できる．パラメータ数は O(LV 2 ) であり，提案法と同程度である．

Markov，GapMarkov，MaxEntSeq，Mixture，提案法は購買順序を考慮する手法であり，MaxEnt，Co-きであるが，本実験ではそれぞれ L ∈ {1, · · · , 10}，Z ∈ {5, 10, · · · , 50} として実験を行い，最も良い正答率を表示している．括弧内はそのときの L もしくは
Z の値である．なお，後述のように，提案法では最大ギャップ L を大きくしても予測性能はあまり下がらな
いため，計算資源が許す限り L を大きくするという設定法も可能である．

Vol. 49

No. SIG 4(TOM 20)131

購買順序を効率的に用いた協調フィルタリング
表 2 正答率 (%)
Table 2 Accuracies (%).

Music4
Music5
Music6
Movie
Cartoon1
Cartoon2
Cartoon3

Markov1 Markov2 Markov3 GapMarkov MaxEntSeq MaxEnt Cosine
PLSA Mixture OurMethod
15.7
10.6
2.1
19.5(2)19.5(1)
15.7
8.9 12.3( 5) 16.1(3)19.5( 2)
12.8
6.4
1.4
12.9(1)14.7(8)10.4
5.7 8.3( 5) 12.8(1)14.0( 6)
11.4
7.1
2.0
10.9(2)12.5(6)
9.1
4.6 6.9(15) 11.5(2)12.9( 8)
39.1
31.1
30.1
39.4(1)38.7(3)27.7
5.4 6.1(50) 39.5(7)39.6( 3)
15.8
16.2
10.4
17.7(3)19.1(5)17.3
8.9 11.3( 5) 16.4(2)19.5(10)
16.2
18.3
14.4
20.7(4)21.8(6)19.1
8.4 8.8( 5) 16.7(2)21.7(10)
16.1
17.1
14.4
18.3(5)20.9(7)18.8
8.4 9.6(30) 16.1(1)19.6(10)

表 3 トップ 3 正答率 (%)
Table 3 Top-3 accuracies (%).

Music4
Music5
Music6
Movie
Cartoon1
Cartoon2
Cartoon3

Markov1 Markov2 Markov3 GapMarkov MaxEntSeq MaxEnt Cosine
PLSA Mixture OurMethod
30.5
15.3
2.1
32.2(2)36.4(3)25.4
17.4 26.7(10) 31.4( 3)34.7( 6)
24.7
12.0
3.2
24.3(2)28.0(3)22.6
14.4 19.6(25) 24.7( 1)
27.6( 7)
21.9
11.4
3.3
22.2(1)25.0(3)
18.4
12.1 14.7(15) 23.2( 6)
25.6(10)
44.4
32.7
31.0
44.3(1)43.9(3)35.3
10.3 13.5(50) 44.7(10)45.0( 6)
29.1
28.3
17.8
31.7(4)34.5(7)34.1
17.9 22.9(40) 30.1( 2)
34.4(10)
29.6
31.0
22.6
34.4(4)36.7(7)35.0
17.3 21.5( 5) 31.6( 2)42.7( 4)
28.8
30.2
23.5
32.8(6)35.6(8)33.4
18.3 23.8(30) 30.1( 2)
35.1(10)(a) Music6(b) Movie(c) Cartoon3

図 2 提案法における重み αlFig. 2 Weights in our method αl .

提案法と MaxEntSeq は他と比べ同程度に正答率がことが示唆される．Mixture の正答率は Markov1 と高い．GapMarkov は提案法に比べ正答率が低くなっ同程度であった．Mixture において推定された混合係ている．これは各ギャップマルコフモデルが独立であ数は P (l = 1)  1，P (l = 1)  0 であることが多るという仮定が適切でないためと考えられる．すべ

かった．つまり，ギャップマルコフモデルを線形和でてのデータセットで Markov3 は Markov1，Markov2

結合した場合，1 ギャップマルコフモデルのみが優勢に比べ正答率が低くなっている．これは高次になるになり，2 以上個前の購買商品情報を有効に利用できとパラメータ数がデータ数に比べ多くなり，頑健な推ていない．

定ができないためと考えられる．また，MaxEntSeq

図 2 に提案法（L = 10）における事前確率およびと MaxEnt を比較すると，全データセットで Max-

ギャップマルコフモデルの重み α を示す．全データ

EntSeq の方が正答率が高く，購買順序は正答率を上げるために重要であることが示唆される．Cosine とセットでギャップが小さいマルコフモデルの重みが大きい傾向があり，最近の履歴が購買予測に関する大きPLSA の正答率は低い．これは購買順序を考慮していないためであると考えられる．Cosine や PLSA は評

上のマルコフモデルの重みもある程度あり，過去の購な情報を与えるという直感と一致する．2 ギャップ以点予測のためによく用いられるが，今回の実験で用い買商品情報も有効に利用していることが分かる．また，た購買商品予測問題の場合，順序は大きな情報となる

終了日が異なるデータでも，それほど重みは異なって

132

Mar. 2008

情報処理学会論文誌：数理モデル化と応用(a) Music6(b) Movie(c) Cartoon3

図 3 提案法，MaxEntSeq，GapMarkov の最大ギャップ L に対する正答率
Fig. 3 Accuracies of our method, MaxEntSeq and GapMarkov with maximum gap L.

(a) Music6(b) Cartoon3

図 4 d 日前までのデータで推定した重み α を用いたときの提案法の正答率（OurMethod2）．
OurMethod および MaxEntSeq は d 日前のデータを用いて全パラメータを推定した
ときの正答率を表す
Fig. 4 Accuracies of our method, in which weights α are estimated by using data
until d days before the end date (OurMethod2). OurMethod and MaxEntSeq represent accuracies when all parameters are estimated using data
until d days before the end data.

いない．

率を表す．OurMethod2 において，事前確率，ギャッ

図 3 に提案法，MaxEntSeq，GapMarkov の最大

プマルコフモデルのハイパーパラメータ δ は d 日前

ギャップ L に対する正答率を示す．提案法は L を増までのデータを用いて推定したものを用いた．漫画，

加させた場合に正答率がそれほど下がることはない

音楽データともに，過去の重みを用いても正答率はそが，MaxEntSeq，GapMarkov は正答率の低下が見ら

れほど変わらず，全データを用いて推定した提案法，れる．MaxEntSeq では過学習が起こっているため，また，GapMarkov では L を大きくしたとき各ギャップ

MaxEntSeq と同程度の性能であった．この結果は，新
規データ追加によるパラメータの更新に多くの計算量

マルコフモデルが独立であるという仮定が不適切になが必要な重み α の更新頻度は少なくし（たとえば 1

りやすいためと考えられる．

カ月に 1 回程度），更新が容易な事前確率，ギャップ

d 日前までのデータで推定した重み α を用い，事前
確率，ギャップマルコフモデルのみ全データで推定したときの提案法（OurMethod2）の正答率を図 4 に示

マルコフモデルのみ短い間隔で更新するだけでも，高い予測精度を実現できることを示している．
各手法のパラメータ学習に必要な計算時間を比較しす．ここで OurMethod および MaxEntSeq は d 日前

た．Xeon3.6 GHz，メモリ 2 GB の計算機での計算時間のデータを用いて全パラメータを推定したときの正答を表 4 に示す．OurMethod2 は，重み α は過去のデー

Vol. 49

No. SIG 4(TOM 20)133

購買順序を効率的に用いた協調フィルタリング
表 4 計算時間（秒）Table 4 Computational time (second).

Music4
Music5
Music6
Movie
Cartoon1
Cartoon2
Cartoon3

Markov1 Markov2 Markov3 GapMarkov MaxEntSeq MaxEnt Cosine PLSA Mixture OurMethod OurMethod2
0.03
0.06
0.05
0.04
12.77
6.28
0.01
1.07
0.17
3.66
0.08
0.12
0.69
0.76
0.23
456.56217.540.06 10.31
1.52
87.21
0.45
0.30
2.15
2.65
0.67
1969.55
916.470.18 29.05
3.87
345.90
1.12
2.00
11.04
9.35
5.16
9316.09 8267.11
0.97 117.69
14.53
2968.72
7.49
1.61
4.50
20.45
2.82 132001.62 16046.90
7.97 239.01 753.77
5267.85
4.39
2.13
5.66
27.42
3.83 216770.25 21597.25 11.36 356.28 1242.36
7931.55
5.59
2.96
7.58
40.05
5.23 347511.57 42994.86 16.08 478.59 1553.69
10444.11
7.50

タでの計算済のものを用い，事前確率とギャップマルコ
フモデルのみ学習する手法である．GapMarkov，Max-

EntSeq，Mixture，OurMethod，OurMethod2 での最大ギャップは L = 10 とし，PLSA での隠れクラス数
は Z = 10 とした．Markov，GapMarkov，Cosine，

OurMethod2 は計算時間が短く，最も規模が大きい
データである Cartoon3 でも数十秒以内で終了している．重み計算まで含めた提案法（OurMethod）は，上記の 4 手法と比べると多くの計算量を必要とするが，正答率が同程度に高い MaxEntSeq と比べると，漫画
データの場合約 30 倍高速である．

6. む す び
本論文では，購買順序を考慮した複数のマルコフモ
デルを最大エントロピー原理で統合した協調フィルタリング手法を提案した．提案法は，パラメータ推定お
よび新規データ追加によるパラメータ更新を高速にできるという利点を持つ．実データを用いた実験で，提案法は多くの計算量が必要な購買順序を考慮した従来
法と同程度の性能であること，また，計算量が少ない手法に比べ高い性能であることを確認した．今回は購買履歴のみを入力としたが，最大エントロピー原理の枠組みで，コンテンツ情報やユーザ情報も組み込むことも可能であるため，今後はそれらの情報も考慮しモデルの性能向上を進めていきたい．また，今回は重みをそれぞれ未知パラメータとして個別に推定したが，重みを指数分布 αl = λ exp(−λl) などによりモデル化することも考えられる．個別に推定することにより，事前知識を必要とせず各重みをデータから適応的に推定することができ，また，通常の最大エントロピーモ
デルと同様に大域的最適解が得られるという利点がある．一方，モデル化する場合にもパラメータの削減ができるという利点があるため，今後，重みのモデル化についても検討していきたい．

参 考

文

献

1) Chen, S.F. and Rosenfeld, R.: A Gaussianprior for smoothing maximum entropy models,Technical report, CMUCS-99-108 (1999).
2) Ding, Y. and Li, X.: Time weight collaborative ﬁltering, CIKM ’05: Proc. 14th ACM
international conference on Information andknowledge management, New York, NY, USA,pp.485–492, ACM Press (2005).
3) Fujino, A., Ueda, N. and Saito, K.: A
hybrid generative/discriminative approach totext classiﬁcation with additional information, Information Processing and Management,
Vol.43, pp.379–392 (2007).
4) Hofmann, T.: Probabilistic Latent Semantic Analysis, Proc. 15th Conference on Uncertainty in Artificial Intelligence, UAI-99 , San
Francisco, CA, pp.289–296, Morgan Kaufmann
Publishers (1999).
5) Hofmann, T.: Probabilistic Latent Semantic Indexing, Proc. Annual International SIGIR Conference on Research and Development
in Information Retrieval, SIGIR-99 , pp.50–57(1999).
6) Iwata, T., Saito, K. and Yamada, T.: Recommendation methods for extending subscription
periods, Proc. Conference on Knowledge Discovery and Data Mining, pp.574–579 (2006).
7) Jelinek, F. and Mercer, R.L.: Interpolated estimation of Markov source parameters fromsparse data, Proc. Workshop on Pattern Recognition in Practice (1980).
8) Jin, X., Mobasher, B. and Zhou, Y.: A Web
Recommendation System Based on Maximum
Entropy, Proc. International Conference on Information Technology: Coding and Computing (ITCC’05 ), Vol.I , Washington, DC, USA,
pp.213–218, IEEE Computer Society (2005).
9) Jin, X., Zhou, Y. and Mobasher, B.: A maximum entropy web recommendation system:
combining collaborative and content features,
Proc. ACM SIGKDD Conference on Knowl-

134

Mar. 2008

情報処理学会論文誌：数理モデル化と応用

edge Discovery and Data Mining (2005).
10) Liu, D.C. and Nocedal, J.: On the limited
memory BFGS method for large scale optimization, Math. Programming, Vol.45, No.3,
pp.503–528 (1989).
11) Mooney, R.J. and Roy, L.: Content-based
book recommending using learning for text categorization, Proc. 5th ACM Conference on Digital Libraries, pp.195–204 (2000).
12) Nigam, K., Laﬀerty, J. and McCallum, A.: Using maximum entropy for text classiﬁcation,
Proc. IJCAI-99 Workshop on Machine Learning for Information Filtering, pp.61–67 (1999).
13) Pavlov, D.Y. and Pennock, D.M.: A maximum entropy approach to collaborative ﬁltering in dynamic, sparse, high-dimensional domains, Proc. Neural Information Processing
Systems, pp.1441–1448 (2002).
14) Raftery, A.E.: A model for high-order Markov
chains, Journal of the Royal Statistical Society
B , Vol.47, No.3, pp.528–539 (1985).
15) Raina, R., Shen, Y., Ng, A.Y. and McCallum,
A.: Classiﬁcation with Hybrid Generative /Discriminative Models, Proc. Neural Information Processing Systems (2004).
16) Resnick, P., Iacovou, N., Suchak, M.,
Bergstrom, P. and Riedl, J.: Grouplens: anopen architecture for collaborative ﬁlteringof netnews, Proc. ACM Conference on Computer Supported Cooperative Work , pp.175–186(1994).
17) Sarwar, B., Karypis, G., Konstan, J. andReidl, J.: Item-based collaborative ﬁltering
recommendation algorithms, Proc. 10th International Conference on World Wide Web,New York, NY, USA, pp.285–295, ACM Press(2001).
18) Schafer, J.B., Konstan, J.A. and Riedl,
J.: E-commerce recommendation applications,
Data Mining and Knowledge Discovery, Vol.5,
pp.115–153 (2001).
19) Zitnick, L. and Kanade, T.: Maximum entropy
for collaborative ﬁltering, Proc. 20th Conference on Uncertainty in Artificial Intelligence,
pp.636–643 (2004).
(平成 19 年 11 月 22 日受付)
(平成 19 年 12 月 20 日採録)

岩田 具治（正会員）
昭和 54 年生．平成 13 年慶應義塾大学環境情報学部環境情報学科卒
業．平成 15 年東京大学大学院総合文化研究科広域科学専攻修了．同年

NTT 入社．機械学習，可視化の研究に従事．現在，NTT コミュニケーション科学基礎研究所に所属．FIT 船井ベストペーパー賞（平成 16年），FIT ヤングリサーチャー賞（平成 19 年）受賞．
電子情報通信学会会員．
山田 武士（正会員）
昭和 39 年生．昭和 63 年 3 月東京大学理学部数学科卒業．同年 NTT
入社．平成 8 年より 1 年間英国コベントリー大学客員研究員．現在，

NTT コミュニケーション科学基礎研究所創発環境研究グループリーダ．主として機械学
習，データマイニング，メタヒューリスティクスによる組合せ最適化等の研究に従事．博士（情報学）．電子情報通信学会，ACM，IEEE 各会員．
上田 修功（正会員）
昭和 33 年生．昭和 57 年大阪大学
工学部通信工学科卒業．昭和 59 年
同大学大学院修士課程修了．工学博士．同年 NTT 入社．平成 5 年より1 年間 Purdue 大学客員研究員．画
像処理，パターン認識・学習，ニューラルネットワー
ク，統計的学習，Web 統計解析の研究に従事．現在，

NTT コミュニケーション科学基礎研究所協創情報研究部長，奈良先端科学技術大学院大学客員教授．電気通信普及財団賞受賞，電子情報通信学会論文賞，FIT 船
井ベストペーパー賞等受賞．電子情報通信学会，IEEE各会員．