(57)【要約】【課題】購買順序を考慮しつつ、計算コストが低く、かつ、予測精度の高いリコメンド装置を提供する。【解決手段】リコメンド装置１は、ユーザの購買履歴ログ４５を用いて、ユーザごとに購買履歴を抽出した入力データ４６を作成する前処理部２１と、入力データ４６からユーザが商品を購入する事前確率と、ユーザが所定の商品を購入したときにその前に購入した商品が特定の商品である確率を示すギャップマルコフモデルとを推定する拡張マルコフモデル推定部２２と、事前確率４７とギャップマルコフモデル４８とを最大エントロピー原理により結合した結合モデルを構築して未知パラメータを示す重みを推定する重み推定部２３と、入力データ４６と事前確率４７とギャップマルコフモデル４８と重み４９とを用いて、結合モデルから計算されるユーザの購入する確率が最大となる商品を選択してリコメンド対象として提示するリコメンド部２４とを備える。【選択図】図１
2008287550.tif 000002
【特許請求の範囲】
【請求項１】
商品またはサービスを示す販売対象を購買したことのある複数のユーザの購買順序に基づいて、それぞれのユーザに対して、前記販売対象に属する個別対象のいずれかをリコメンド対象として提示するリコメンド装置であって、
前記ユーザが過去に購入した１以上の個別対象に関する情報を含む購買履歴情報を用いて、前記ユーザごとに、前記個別対象の購買履歴を抽出したデータを示す処理用データを作成する前処理手段と、
前記作成された処理用データを用いて、前記ユーザが前記個別対象を購入する確率を示す事前確率を推定する事前確率推定手段と、
前記作成された処理用データを用いて、前記ユーザが所定の個別対象を購入したときにその前に購入した個別対象が特定の個別対象である確率を示すギャップマルコフモデルを推定するギャップマルコフモデル推定手段と、
前記推定された事前確率と前記推定されたギャップマルコフモデルとを最大エントロピー原理により結合したモデルを示す結合モデルを構築し、構築した結合モデルの未知パラメータを示す重みを推定する重み推定手段と、
前記作成された処理用データと、前記推定された事前確率と、前記推定されたギャップマルコフモデルと、前記推定された重みとを用いて、前記結合モデルから計算されるユーザの購入する確率が最大となる前記個別対象を選択してリコメンド対象として提示するリコメンド手段と、
を備えることを特徴とするリコメンド装置。
【請求項２】
前記重み推定手段は、
経験分布による事前分布の対数尤度と、前記結合モデルと前記事前分布の対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第１条件と、
ギャップマルコフモデルの対数尤度と、前記結合モデルと前記ギャップマルコフモデルの対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第２条件とを用いて、前記結合モデルを構築し、
対象とする全ユーザについての前記処理用データから、対象とする全個別対象の購入確率の対数尤度を最大化することで前記重みを推定する、
ことを特徴とする請求項１に記載のリコメンド装置。
【請求項３】
商品またはサービスを示す販売対象を購買したことのある複数のユーザの購買順序に基づいて、それぞれのユーザに対して、前記販売対象に属する個別対象のいずれかをリコメンド対象として提示するリコメンド装置のリコメンド方法であって、
前処理手段によって、前記ユーザが過去に購入した１以上の個別対象に関する情報を含む購買履歴情報を用いて、前記ユーザごとに、前記個別対象の購買履歴を抽出したデータを示す処理用データを作成する前処理ステップと、
事前確率推定手段によって、前記作成された処理用データを用いて、前記ユーザが前記個別対象を購入する確率を示す事前確率を推定する事前確率推定ステップと、
ギャップマルコフモデル推定手段によって、前記作成された処理用データを用いて、前記ユーザが所定の個別対象を購入したときにその前に購入した個別対象が特定の個別対象である確率を示すギャップマルコフモデルを推定するギャップマルコフモデル推定ステップと、
重み推定手段によって、前記推定された事前確率と前記推定されたギャップマルコフモデルとを最大エントロピー原理により結合したモデルを示す結合モデルを構築し、構築した結合モデルの未知パラメータを示す重みを推定する重み推定ステップと、
リコメンド手段によって、前記作成された処理用データと、前記推定された事前確率と、前記推定されたギャップマルコフモデルと、前記推定された重みとを用いて、前記結合モデルから計算されるユーザの購入する確率が最大となる前記個別対象を選択してリコメンド対象として提示するリコメンドステップと、
を有することを特徴とするリコメンド方法。
【請求項４】
前記重み推定ステップは、
経験分布による事前分布の対数尤度と、前記結合モデルと前記事前分布の対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第１条件と、
ギャップマルコフモデルの対数尤度と、前記結合モデルと前記ギャップマルコフモデルの対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第２条件とを用いて、前記結合モデルを構築し、
対象とする全ユーザについての前記処理用データから、対象とする全個別対象の購入確率の対数尤度を最大化することで前記重みを推定する、
ことを特徴とする請求項３に記載のリコメンド方法。
【請求項５】
請求項３または請求項４に記載のリコメンド方法をコンピュータに実行させることを特徴とするリコメンドプログラム。
【請求項６】
請求項５に記載のリコメンドプログラムが記録されたことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、購買履歴を入力として、ユーザが次に購入する商品を予測することで、ユーザに商品をリコメンドするリコメンド技術に係り、特に、オンラインストア等において商品をリコメンド対象として提示するリコメンド技術に関する。
【背景技術】
【０００２】
一般に、商品またはサービス（以下、単に商品という）を販売するオンラインストア等の多くの商品提供者（販売者）は、オンラインストア等を利用するユーザの購買行動に影響を与えるように商品をリコメンド対象として提示する（リコメンドする）。リコメンド（recommendation）は、ユーザへの商品の直接的または間接的な提示であり、ユーザが所望する商品の情報に対して迅速にアクセスできるように利便性を向上させる目的と、商品提供者の収益を増加させる目的とを有している。リコメンドは、多くのオンラインストアで用いられている。
【０００３】
従来、様々なリコメンド技術が知られている（例えば非特許文献１および非特許文献２参照）。商品提供者にとって、オンラインストア等で商品を購買したことのあるユーザに次回も商品を購入してもらうために、ユーザにどのような商品をリコメンドしたらよいかを予測することは重要である。ユーザが次に購入する商品は、ユーザのその時点の興味を最も表していると考えられる。そのため、ユーザの購買の予測精度が高い手法は、ユーザの興味の予測精度が高い手法であると言える。しかしながら、非特許文献１に記載されたリコメンド手法は、商品が購入された順序（以下、順序情報という）を考慮していない。このため、予測精度が低い。
【０００４】
一方、非特許文献２に記載されたリコメンド手法は、順序情報を考慮して最大エントロピーモデルが適用されている。なお、最大エントロピーモデルとは、最大エントロピー原理を用いて求められた確率モデルのことを指す。この非特許文献２に記載されたリコメンド手法では、ユーザが直前に購入した商品のみを考慮するものである。これは、ユーザが直前に、つまり、最近購入した商品には、ユーザの現在の興味に関する多くの情報が含まれていると考えられるためである。また、このように順序情報を考慮した従来のリコメンド技術では、マルコフモデルや最大エントロピーモデルが適用されている。
【非特許文献１】Badrul Sarwar, George Karypis, Joseph Konstan, and John Reidl: Item-based co11aborative fi1tering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web,pp.285-295, New York,NY,USA,2001. ACM Press.
【非特許文献２】Xin Jin, Bamshad Mobasher, and Yanzan Zhou: A web recommendation sustem based on maximum entropy. In Proceedings of the international conference on Information Technology: Coding and Computing(ITCC’05)-Volume I,pp.213-218, Washington,DC,USA,2005. IEEE Computer Society.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献２に記載されたリコメンド手法では、ユーザが直前に購入した商品以外の情報を考慮していない。つまり、ユーザが昔に購入した商品にもある程度は含まれると考えられるユーザの現在の興味に関する情報が無視されていることになる。その結果、予測精度が低いという問題がある。
【０００６】
また、順序情報を考慮した従来のリコメンド技術で用いられるマルコフモデルは、パラメータの推定および更新を高速に行うことができるが、予測精度が低いという問題点がある。また、順序情報を考慮した従来のリコメンド技術で用いられる最大エントロピーモデルは、予測精度は高いが、パラメータの推定および更新に多くの計算量を必要とするという問題点がある。
【０００７】
そこで、本発明は、以上のような問題点に鑑みてなされたものであり、購買順序を考慮しつつ、計算コストが低く、かつ、予測精度の高いリコメンド技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するために、本発明に係るリコメンド装置は、商品またはサービスを示す販売対象を購買したことのある複数のユーザの購買順序に基づいて、それぞれのユーザに対して、前記販売対象に属する個別対象のいずれかをリコメンド対象として提示するリコメンド装置であって、前記ユーザが過去に購入した１以上の個別対象に関する情報を含む購買履歴情報を用いて、前記ユーザごとに、前記個別対象の購買履歴を抽出したデータを示す処理用データを作成する前処理手段と、前記作成された処理用データを用いて、前記ユーザが前記個別対象を購入する確率を示す事前確率を推定する事前確率推定手段と、前記作成された処理用データを用いて、前記ユーザが所定の個別対象を購入したときにその前に購入した個別対象が特定の個別対象である確率を示すギャップマルコフモデルを推定するギャップマルコフモデル推定手段と、前記推定された事前確率と前記推定されたギャップマルコフモデルとを最大エントロピー原理により結合したモデルを示す結合モデルを構築し、構築した結合モデルの未知パラメータを示す重みを推定する重み推定手段と、前記作成された処理用データと、前記推定された事前確率と、前記推定されたギャップマルコフモデルと、前記推定された重みとを用いて、前記結合モデルから計算されるユーザの購入する確率が最大となる前記個別対象を選択してリコメンド対象として提示するリコメンド手段とを備えることを特徴とする。
【０００９】
また、前記課題を解決するために、本発明に係るリコメンド方法は、商品またはサービスを示す販売対象を購買したことのある複数のユーザの購買順序に基づいて、それぞれのユーザに対して、前記販売対象に属する個別対象のいずれかをリコメンド対象として提示するリコメンド装置のリコメンド方法であって、前処理手段によって、前記ユーザが過去に購入した１以上の個別対象に関する情報を含む購買履歴情報を用いて、前記ユーザごとに、前記個別対象の購買履歴を抽出したデータを示す処理用データを作成する前処理ステップと、事前確率推定手段によって、前記作成された処理用データを用いて、前記ユーザが前記個別対象を購入する確率を示す事前確率を推定する事前確率推定ステップと、ギャップマルコフモデル推定手段によって、前記作成された処理用データを用いて、前記ユーザが所定の個別対象を購入したときにその前に購入した個別対象が特定の個別対象である確率を示すギャップマルコフモデルを推定するギャップマルコフモデル推定ステップと、重み推定手段によって、前記推定された事前確率と前記推定されたギャップマルコフモデルとを最大エントロピー原理により結合したモデルを示す結合モデルを構築し、構築した結合モデルの未知パラメータを示す重みを推定する重み推定ステップと、リコメンド手段によって、前記作成された処理用データと、前記推定された事前確率と、前記推定されたギャップマルコフモデルと、前記推定された重みとを用いて、前記結合モデルから計算されるユーザの購入する確率が最大となる前記個別対象を選択してリコメンド対象として提示するリコメンドステップとを有することを特徴とする。
【００１０】
かかる構成のリコメンド装置、または、かかる手順のリコメンド方法によれば、リコメンド装置は、第１段階として、購買履歴情報を用いてユーザごとに処理用データを作成する。ここで、購買履歴情報は、例えば、どのユーザがどのタイミングに何を購買したのかを示す情報である。購買履歴情報は、例えば、オンラインストアの商品を販売対象とする場合に、オンライン処理のログの形式で取得することができる。また、処理用データは、ユーザごとに、何をどんな順序で購買したのかを示すデータである。そして、リコメンド装置は、処理用データを用いる第２段階として、事前確率とギャップマルコフモデルとをそれぞれ推定する。ここで、事前確率は、例えば、これまでに売れた全種類の商品のうち、特定の種類の商品がいずれかのユーザに購入された確率を、商品別（種類別）に求めた確率を意味する。また、ギャップマルコフモデルは、例えば、いずれかのユーザが何回目かの購入タイミングで商品を購入したときに、その数回前に、特定の種類の商品を購入したときの確率を、商品別（種類別）に求めた確率を意味する。これにより、ユーザが昔に購入した商品にもある程度は含まれると考えられるユーザの現在の興味に関する情報を取り込むことが可能となる。また、推定方法には、例えば、最大事後確率（ＭＡＰ：Maximum A Posteriori）推定を用いることができる。
【００１１】
そして、リコメンド装置は、第３段階として、事前確率とギャップマルコフモデルとを最大エントロピー原理により結合した結合モデルの未知パラメータを示す重みを推定する。これにより、結合モデルは、最大エントロピーモデルによる予測精度の高さと、マルコフモデルによる計算コストの低さとを合わせもつ特徴を有することとなる。そして、リコメンド装置は、第４段階として、処理用データおよび事前に推定した各パラメータを用いて、結合モデルから計算されるユーザの購入する確率が最大となる個別対象をリコメンドする。したがって、あるユーザについてその時点の興味を最も表していると考えられる商品を精度よく、低コストの計算で求めることができる。
【００１２】
また、本発明に係るリコメンド装置は、前記重み推定手段が、経験分布による事前分布の対数尤度と、前記結合モデルと前記事前分布の対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第１条件と、ギャップマルコフモデルの対数尤度と、前記結合モデルと前記ギャップマルコフモデルの対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第２条件とを用いて、前記結合モデルを構築し、対象とする全ユーザについての前記処理用データから、対象とする全個別対象の購入確率の対数尤度を最大化することで前記重みを推定することが好ましい。
【００１３】
また、本発明に係るリコメンド方法は、前記重み推定ステップが、経験分布による事前分布の対数尤度と、前記結合モデルと前記事前分布の対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第１条件と、ギャップマルコフモデルの対数尤度と、前記結合モデルと前記ギャップマルコフモデルの対数尤度との積で表した結合モデルについての期待値とが等しいことを示す第２条件とを用いて、前記結合モデルを構築し、対象とする全ユーザについての前記処理用データから、対象とする全個別対象の購入確率の対数尤度を最大化することで前記重みを推定することが好ましい。
【００１４】
かかる構成のリコメンド装置、または、かかる手順のリコメンド方法によれば、推定された結合モデルは、購買順序を考慮した最大エントロピーモデルによる予測精度よりも高い予測精度を実現することが可能である。
【００１５】
また、本発明に係るリコメンドプログラムは、前記したリコメンド方法をコンピュータに実行させることを特徴とする。このように構成されることにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【００１６】
また、本発明に係るコンピュータ読み取り可能な記録媒体は、前記したリコメンドプログラムが記録されたことを特徴とする。このように構成されることにより、この記録媒体を装着されたコンピュータは、この記録媒体に記録されたプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００１７】
本発明によれば、購買順序を考慮しつつ、計算コストが低く、かつ、予測精度の高いリコメンド技術を提供することができる。その結果、ユーザが所望する商品の情報に対して迅速にアクセスできるようになると共に、商品提供者の収益を増加させることが可能となる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して本発明のリコメンド装置およびリコメンド方法を実施するための最良の形態（以下「実施形態」という）について詳細に説明する。
【００１９】
図１は、本発明の実施形態に係るリコメンド装置の構成を示すブロック図である。リコメンド装置１は、商品またはサービスを示す販売対象（商品群）を購買したことのある複数のユーザの購買順序に基づいて、それぞれのユーザに対して、販売対象（商品群）に属する個別対象（商品）のいずれかをリコメンド対象として提示する（リコメンドする）ものである。リコメンド装置１は、図１に示すように、演算手段２と、入力手段３と、記憶手段４と、出力手段５とを備えており、これら各手段２〜５はバスライン６に接続されている。
【００２０】
演算手段２は、例えば、ＣＰＵ（Central Processing Unit）およびＲＡＭ（Random Access Memory）から構成される主制御装置である。この演算手段２は、図１に示すように、前処理部（前処理手段）２１と、拡張マルコフモデル推定部（拡張マルコフモデル推定手段）２２と、重み推定部（重み推定手段）２３と、リコメンド部（リコメンド手段）２４と、メモリ２５とを含んで構成される。なお、各部２１〜２４の詳細な説明は後記する。
【００２１】
入力手段３は、例えば、キーボード、マウス、ディスクドライブ装置などから構成される。この入力手段３は、例えば、データとして購買履歴ログ（購買履歴情報）を入力し、記憶手段４に格納する。
【００２２】
購買履歴ログ（購買情報）は、ユーザが過去に購入した１以上の個別対象（商品）に関する情報を含んでいる。この購買履歴ログは、例えば、表１に示すように、商品の購買ごとに（売買成立ごとに）、ユーザ番号と、商品番号と、購買時刻とを記録したログである。表１の例では、ユーザ番号が「１」であるユーザは、商品番号が「３」，「１」，「６」の商品を購入したことが分かる。
【００２３】
【表１】
2008287550.tif 000003
【００２４】
記憶手段４は、例えば、一般的なハードディスク装置などから構成され、演算手段２で用いられる各種プログラムや各種データ等を記憶する。この記憶手段４は、プログラムとして、前処理プログラム４１と、拡張マルコフモデル推定プログラム４２と、重み推定プログラム４３と、リコメンドプログラム４４とをプログラム格納部４０ａに記憶する。そして、演算手段２は、これらのプログラム４１〜４４を記憶手段４から読み込んでメモリ２５に展開して実行することで、前記した前処理部２１、拡張マルコフモデル推定部２２、重み推定部２３、リコメンド部２４の各機能を実現する。
【００２５】
また、記憶手段４は、購買履歴ログ４５と、入力データ（処理用データ）４６と、事前確率４７と、ギャップマルコフモデル４８と、重み４９とをデータ格納部４０ｂに記憶する。ここで、購買履歴ログ４５は、入力手段３から入力されるデータであり、例えば、前記した表１に示したものである。入力データ４６は、演算手段２の前処理部２１の演算処理結果を示すデータである。事前確率４７とギャップマルコフモデル４８とは、演算手段２の拡張マルコフモデル推定部２２の演算処理結果を示すデータである。重み４９は、演算手段２の重み推定部２３の演算処理結果を示すデータである。
【００２６】
出力手段５は、例えば、グラフィックボード（出力インタフェース）およびそれに接続されたモニタである。モニタは、例えば、液晶ディスプレイ等から構成され、演算処理結果（例えば、リコメンドする商品の情報等）を表示する。
【００２７】
次に、演算手段２の各部の構成の詳細を説明する。
＜前処理部＞
図２は、前処理部の構成を示す機能ブロック図である。前処理部２１は、購買履歴ログ４５を用いて、ユーザごとに、商品（個別対象）の購買系列（購買履歴）を抽出したデータを示す入力データ（処理用データ）を作成するものであり、図２に示すように、購買履歴ログ読込部２１１と、入力データ書込部２１２とを備えている。
【００２８】
購買履歴ログ読込部２１１は、購買履歴ログ４５から、各購買のユーザ、時刻、商品の情報を読み込み、入力データ書込部２１２に出力する。
入力データ書込部２１２は、購買履歴ログ４５に含まれる商品の購買ごとのユーザ番号、商品番号、購買時刻に基づいて、ユーザごとに、購入商品の購買系列を算出するものである。また、入力データ書込部２１２は、ユーザごとに算出した購買系列を、入力データ（処理用データ）４６として、記憶手段４（図１参照）に書き込む。なお、書き込まれた入力データ４６は、拡張マルコフモデル推定部２２と、重み推定部２３と、リコメンド部２４で利用される。
【００２９】
以下では、ユーザ集合Ｕは式（１）で定義され、商品集合Ｓは式（２）で定義されるものとする。式（１）において、ｎはユーザ番号（単にユーザともいう）、Ｎはユーザ数を示す。式（２）において、ｊは商品番号（単に商品ともいう）、Ｖは商品数を示す。
【００３０】
【数１】
2008287550.tif 000004
【００３１】
あるユーザｎがｋ番目に購入した商品ｘn,kは式（３）に示すように商品集合Ｓに含まれ、そのときのユーザｎの購買系列ｕnkは、式（４）で表される。式（４）で示した購買系列ｕnkは、ユーザｎがｋ番目の商品ｘn,kを購入する前に購入した（ｋ−１）個の商品による系列である。この購買系列ｕnkは、入力データ書込部２１２によって、購買履歴ログ４５から算出される。
【００３２】
【数２】
2008287550.tif 000005
【００３３】
ここで、入力データ（処理用データ）４６の具体例について表２を参照して説明する。入力データは、表２に示されるように、各ユーザの購入商品の購買系列で構成される。
【００３４】
【表２】
2008287550.tif 000006
【００３５】
例えば、表１に示す購買履歴ログ４５によれば、ユーザ番号が「１」であるユーザ（ｎ＝１）は、商品番号「３」の商品に続いて商品番号「１」の商品を購入している。これにより、表２に示すように、ユーザ番号ｎが「１」の購買系列の要素である「ｘ1,1」は、商品番号「３」の商品を示し、同様に「ｘ1,2」は、商品番号「１」の商品を示すこととなる。
【００３６】
＜拡張マルコフモデル推定部＞
図３は、拡張マルコフモデル推定部の構成を示す機能ブロック図である。
拡張マルコフモデル推定部２２は、図３に示すように、入力データ読込部２２１と、事前確率推定部２２２と、ギャップマルコフモデル推定部２２３と、拡張マルコフモデル書込部２２４とを備えている。
入力データ読込部２２１は、入力データ４６を読み込み、事前確率推定部２２２およびギャップマルコフモデル推定部２２３に出力する。
【００３７】
≪事前確率推定部≫
事前確率推定部（事前確率推定手段）２２２は、前処理部２１（図１参照）で作成された入力データ４６を用いて、ユーザが商品（個別対象）を購入する確率を示す事前確率を推定するものである。
本実施形態では、事前確率推定部２２２は、式（５）に示す事前確率Ｐ＾（ｉ）の計算を行う。なお、本明細書において、記号「＾（ハット）」は直前の文字の上に記載されることを意味する。
最大事後確率（ＭＡＰ：Maximum A Posteriori）推定によると、商品ｉを購入する事前確率Ｐ＾（ｉ）は、式（５）で推定される。式（５）において、δは、データ数が少ない場合に計算を安定化させる役割を持つハイパーパラメータであり、leave-one-out交差検定法により推定することができる。
【００３８】
【数３】
2008287550.tif 000007
【００３９】
事前確率推定部２２２は、事前確率推定部２２２で推定された事前確率Ｐ＾（ｉ）を拡張マルコフモデル書込部２２４に出力する。
【００４０】
≪ギャップマルコフモデル推定部≫
ギャップマルコフモデル推定部（ギャップマルコフモデル推定手段）２２３は、前処理部２１（図１参照）で作成された入力データ４６を用いて、ユーザが所定の商品（個別対象）を購入したときにその前に購入した商品（個別対象）が特定の商品（個別対象）である確率を示すギャップマルコフモデルを推定するものである。
本実施形態では、ギャップマルコフモデル推定部２２３は、式（６）に示すｌギャップマルコフモデルＰl（ｊl｜ｉ）の計算を行う。ｌギャップマルコフモデルＰl（ｊl｜ｉ）は、商品ｉを購入したｌ個前の商品がｊである確率を表す。ＭＡＰ推定によると、ｌギャップマルコフモデルは、式（６）で推定される。ギャップマルコフモデル推定部２２３は、推定されたｌギャップマルコフモデルを拡張マルコフモデル書込部２２４に出力する。
【００４１】
【数４】
2008287550.tif 000008
【００４２】
前記した式（５）に示した事前確率および式（６）に示したｌギャップマルコフモデルにおけるパラメータは、それぞれ単純な和のみで計算できる。そのため、これらの推定に必要な計算量は少なく、また、新たなデータが増えたときに、これらの更新は容易に行うことができる。
【００４３】
拡張マルコフモデル書込部２２４は、式（５）に示した事前確率を事前確率４７として記憶手段４（図１参照）に格納する。また、拡張マルコフモデル書込部２２４は、式（６）に示したギャップマルコフモデルをギャップマルコフモデル４８として記憶手段４（図１参照）に格納する。なお、格納された事前確率４７およびギャップマルコフモデル４８は、重み推定部２３およびリコメンド部２４で利用される。
【００４４】
＜重み推定部＞
図４は、重み推定部の構成を示す機能ブロック図である。重み推定部２３は、拡張マルコフモデル推定部２２（図１参照）で推定された事前確率４７とギャップマルコフモデル４８とを最大エントロピー原理により結合したモデルを示す結合モデルを構築し、構築した結合モデルの未知パラメータを示す重みを推定するものである。なお、この結合モデルのことを拡張マルコフモデルともいう。
【００４５】
重み推定部２３は、図４に示すように、入力データ読込部２３１と、拡張マルコフモデル読込部２３２と、ギャップ重み推定部２３３と、重み書込部２３４とを備えている。
入力データ読込部２３１は、入力データ４６を読み込み、ギャップ重み推定部２３３に出力する。
拡張マルコフモデル読込部２３２は、事前確率４７とギャップマルコフモデル４８を読み込み、ギャップ重み推定部２３３に出力する。
【００４６】
≪ギャップ重み推定部≫
ギャップ重み推定部２３３は、入力データ４６と、事前確率４７と、ギャップマルコフモデル４８とを用いて、式（７）および式（８）の制約のもと、エントロピーを最大化することにより、事前確率４７と、ギャップマルコフモデル４８とを最大エントロピー原理により結合して式（９）に示す結合モデルを構築し、その重みを推定する。なお、以下では、対数は自然対数、すなわち、対数logの底は「ｅ」であるものとする。また、式（９）において、商品ｉを購入するｌ個前に購入した商品をｊlとする。また、Ｌは、ｋ番目の商品を購入するまでに購入した商品の個数を示す。
【００４７】
【数５】
2008287550.tif 000009
【００４８】
式（７）の左辺は、「経験分布による事前分布の対数尤度」である。また、式（７）の右辺は、「モデルＰ（確率）」と、「事前分布の対数尤度」との積であらわしたもの（これはモデルＰについての期待値に相当する）を示す。そして、式（７）の左辺が、式（７）の右辺と等しいと仮定すること（第１条件）が「制約」を意味する。
【００４９】
式（８）の左辺は、「ギャップマルコフモデルの対数尤度」である。また、式（８）の右辺は、「モデルＰ（確率）」と、「ギャップマルコフモデルの対数尤度」との積であらわしたもの（これはモデルＰについての期待値に相当する）を示す。そして、式（８）の左辺が、式（８）の右辺と等しいと仮定すること（第２条件）が「制約」を意味する。
【００５０】
この場合、式（９）に示す結合モデルは、式（１０）に示すように展開することができる。式（１０）において、Ｚは式（１１）で示される正規化項であり、αは式（１２）で示される未知パラメータ（以下、重みともいう）である。なお、本明細書において、αに添字を付す場合には、個別のパラメータを指し、αに添字を付さない場合には、Ｌ個のパラメータの集合を指す。
【００５１】
【数６】
2008287550.tif 000010
【００５２】
未知パラメータαは、式（１３）に示す対数尤度Ｊを、例えば、準ニュートン法などの最適化手法を用い最大化することにより、大域的最適解を得ることができる。
【００５３】
【数７】
2008287550.tif 000011
【００５４】
式（１３）に示す対数尤度Ｊは、対象とする全ユーザについての購買系列ｕnk、つまり、入力データ（処理用データ）から求められる、対象とする全商品（全個別対象）ｘn,kの購入確率の対数尤度を示す。したがって、ギャップ重み推定部２３３は、式（１３）に示す対数尤度Ｊを最大化することで重みαを推定する。
【００５５】
また、本実施形態では、ギャップ重み推定部２３３は、過学習を抑えるため、未知パラメータαの事前分布として平均０の正規分布を用いることとする。なお、学習に用いなかったデータに対する汎化誤差が大きくなってしまう現象は過学習と呼ばれている。ここで、予め定められた学習データのうち、拡張マルコフモデル推定部２２によって事前確率およびギャップマルコフモデルの推定に用いた学習データを、未知パラメータαの推定に用いると、過学習する可能性がある。そのため、交差検定法により、未知パラメータαを推定する。すなわち、予め定められた学習データを分割し、事前確率およびギャップマルコフモデルの推定に用いなかったデータの対数尤度を準ニュートン法などの最適化手法を用い最大化することにより、重みαを推定する。
【００５６】
重み書込部２３４は、ギャップ重み推定部２３３で推定された重みαを重み４９として記憶手段４（図１参照）に格納する。なお、格納された重み４９は、リコメンド部２４で利用される。
【００５７】
＜リコメンド部＞
図５は、リコメンド部の構成を示す機能ブロック図である。
リコメンド部２４は、入力データ（処理用データ）４６と、推定された事前確率４７と、推定されたギャップマルコフモデル４８と、推定された重み４９とを用いて、結合モデル（拡張マルコフモデル）から計算されるユーザの購入する確率が最大となる商品（個別対象）を選択してリコメンド対象として提示するものである。
【００５８】
リコメンド部２４は、図５に示すように、入力データ読込部２４１と、拡張マルコフモデル読込部２４２と、重み読込部２４３と、最大商品選択部２４４と、リコメンド出力部２４５とを備えている。
【００５９】
入力データ読込部２４１は、入力データ４６を読み込み、最大商品選択部２４４に出力する。
拡張マルコフモデル読込部２４２は、事前確率４７とギャップマルコフモデル４８とを読み込み、最大商品選択部２４４に出力する。
重み読込部２４３は、重み４９を読み込み、最大商品選択部２４４に出力する。
【００６０】
最大商品選択部２４４は、式（１４）に示す演算を実行する。ここで、ユーザｎの購買履歴ｕnを式（１５）とする。なお、Ｋnは、ユーザｎの購入商品数である。
【００６１】
【数８】
2008287550.tif 000012
【００６２】
本実施形態では、最大商品選択部２４４は、式（１４）から計算されるユーザｎの購入する確率が、最も高い商品を選択する。すなわち、最大商品選択部２４４は、ユーザｕが購入した商品の商品集合Ｓ（商品番号  １≦ｉ≦Ｖ）の中から、式（１４）で示される確率が最大になる商品（商品番号）
2008287550.tif 000013
を選択する。
【００６３】
リコメンド出力部２４５は、最大商品選択部２４４で選択された商品番号を出力することで、当該商品番号の商品をリコメンド対象として提示する。このリコメンド対象は、出力手段５に出力される。
【００６４】
[リコメンド装置の動作]
図１に示したリコメンド装置１の動作について図６を参照（適宜図１参照）して説明する。図６は、リコメンド装置の動作を示すフローチャートである。リコメンド装置１は、前処理部２１によって、購買履歴ログ４５を用いて、入力データを生成する（ステップＳ１：前処理ステップ）。そして、リコメンド装置１は、拡張マルコフモデル推定部２２によって、拡張マルコフモデル推定処理を実行する（ステップＳ２：拡張マルコフモデル推定ステップ）。続いて、リコメンド装置１は、重み推定部２３によって、ステップＳ２で推定された事前確率４７とギャップマルコフモデル４８とを用いて、重み推定処理を実行する（ステップＳ３：重み推定ステップ）。そして、リコメンド装置１は、リコメンド部２４によって、結合モデル（拡張マルコフモデル）から計算されるユーザの購入する確率が最大となる商品（個別対象）を選択してリコメンドする（ステップＳ４：リコメンドステップ）。
【００６５】
次に、前記したステップＳ２の拡張マルコフモデル推定処理と、前記したステップＳ３の重み推定処理について図７および図８をそれぞれ参照して説明する。図７は、拡張マルコフモデル推定処理を示すフローチャートであり、図８は、重み推定処理を示すフローチャートである。
【００６６】
まず、前記したステップＳ２の拡張マルコフモデル推定処理では、図７に示すように、
拡張マルコフモデル推定部２２は、入力データ読込部２２１によって、記憶手段４（図１参照）から、入力データ４６を読み込む（ステップＳ２１）。そして、拡張マルコフモデル推定部２２は、事前確率推定部２２２によって、事前確率を推定し（ステップＳ２２）、拡張マルコフモデル推定部２２は、ギャップマルコフモデル推定部２２３によって、ギャップマルコフモデルを推定する（ステップＳ２３）。そして、拡張マルコフモデル推定部２２は、拡張マルコフモデル書込部２２４によって、推定された事前確率とギャップマルコフモデルとを記憶手段４（図１参照）に格納する（ステップＳ２４）。なお、ステップＳ２２の処理と、ステップＳ２３の処理との実行順序は、任意であり、処理を並列に実行してもよい。
【００６７】
次に、前記したステップＳ３の重み推定処理では、図８に示すように、重み推定部２３は、入力データ読込部２３１によって、記憶手段４（図１参照）から、入力データ４６を読み込む（ステップＳ３１）。また、重み推定部２３は、拡張マルコフモデル読込部２３２によって、記憶手段４（図１参照）から、事前確率４７とギャップマルコフモデル４８を読み込む（ステップＳ３２）。続いて、重み推定部２３は、ギャップ重み推定部２３３によって、入力データ４６と、事前確率４７と、ギャップマルコフモデル４８とを用いて、結合モデルの未知パラメータαを推定する（ステップＳ３３）。そして、重み推定部２３は、重み書込部２３４によって、推定されたパラメータαを重み４９として記憶手段４（図１参照）に格納する（ステップＳ３４）。なお、ステップＳ３１の処理と、ステップＳ３２の処理との実行順序は、任意であり、処理を並列に実行してもよい。
【００６８】
なお、リコメンド装置１は、一般的なコンピュータに、前記した各ステップを実行させるリコメンドプログラムを実行することで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００６９】
本実施形態によれば、購買順序を考慮しつつ、計算コストが低く、かつ、予測精度の高い商品をユーザにリコメンドすることができる。その結果、ユーザが所望する商品の情報に対して迅速にアクセスできるようになると共に、商品提供者の収益を増加させることが可能となる。
【００７０】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、リコメンド装置１を構成する装置は、１台に限定されることはなく、複数の装置に機能を分散配置してもよい。例えば、演算手段２の前処理部２１、拡張マルコフモデル推定部２２、重み推定部２３、リコメンド部２４や、記憶手段４のデータ格納部４０ｂを、別々の装置として構成してもよい。これにより、各装置への負荷が分散され、高速な処理が実現可能となる。
【実施例】
【００７１】
本発明の効果を確認するために、本実施形態に係るリコメンド装置１に、音楽配信サービスの購買履歴ログを入力する場合の商品の予測精度と、動画配信サービスの購買履歴ログを入力する場合の商品の予測精度とを求めた。
【００７２】
＜設定＞
音楽配信サービスの購買履歴ログ（以下、音楽データという）は、2005年４月１日から2005年６月30日までの音楽配信サービスにおける購買履歴を示すログである。この音楽データにおいて、ユーザ数は「2,104」、商品数（楽曲数）は「561」、購買数は「15,216」であった。
動画配信サービスの購買履歴ログ（以下、動画データという）は、2007年１月１日の動画配信サービスにおける購買履歴を示すログである。この動画データにおいて、ユーザ数は「3,085」、商品数は「1,569」、購買数は「25,363」であった。
【００７３】
なお、音楽データおよび動画データから、売上数が「10」未満の商品を省くと共に、購買数が「５」未満であるユーザを省いた。また、あるユーザが同じ商品を２回以上購入した場合、その商品に関する２回目以降の購買を購買履歴から省いた。また、各ユーザが最後に購入した商品をテストデータとして用いると共に、それ以前の購買履歴を学習データとして用いた。ここで、ユーザが最後に購入した商品が、学習データに含まれていないものである場合には、その商品をテストデータから省いた。
【００７４】
実施例（Our Method）を以下の６つのモデル（比較例１〜比較例６）と比較した。
比較例１：１次マルコフモデル（1stMarkov）
比較例２：２次マルコフモデル（2ndMarkov）
比較例３：３次マルコフモデル（3rdMarkov）
比較例４：ギャップマルコフモデルがそれぞれ独立と仮定したモデル（GapMarkov）
比較例５：購買順序を考慮した最大エントロピーモデル（MaxEnt(seq)）
比較例６：購買順序を考慮しない最大エントロピーモデル（MaxEnt）
【００７５】
ここで、事前確率およびギャップマルコフモデルにおけるハイパーパラメータは、leave-one-out交差検定法により求めた。すなわち、本実施形態のリコメンド装置１では、前記した式（５）におけるハイパーパラメータ“δ”と、式（６）におけるハイパーパラメータ“δ”とを、leave-one-out交差検定法により求めた。
また、最大エントロピーモデルにおけるパラメータの事前分布は、分散が「１」の正規分布とした。すなわち、本実施形態のリコメンド装置１では、前記した式（１２）における未知パラメータ（重み）αの事前分布は、分散が「１」の正規分布とした。
また、本実施形態のリコメンド装置１では、重みαを１０重交差検定法により求めた。
【００７６】
＜結果（正答率）＞
このときの各手法の実験結果（正答率）を表３に示す。
【００７７】
【表３】
2008287550.tif 000014
【００７８】
比較例４（GapMarkov）、比較例５（MaxEnt(seq)）、実施例（Our Method）において、ｌ個前までの購買履歴を用いた手法（ｌ＝１，…，１０）で実験し、最もよい正答率となったときの値を表示し、そのときのｌを括弧内に表示している。つまり、表３では、例えば、実施例（Our Method）の場合には、音楽データはｌ＝８の場合に正答率が最もよく、動画データはｌ＝９の場合に正答率が最もよいことを示している。
【００７９】
表３に示すように、音楽データおよび動画データのいずれでも、実施例（Our Method）の正答率が最も高かった。比較例４（GapMarkov）の正答率が実施例（Our Method）の正答率に比べて低くなった理由は、「ギャップマルコフモデルがそれぞれ独立である」という仮定が適切ではないためであると考えられる。
【００８０】
また、表３に示すように、比較例３（3rdMarkov）は、すべてのデータセットにおいて、比較例１（1stMarkov）や比較例２（2ndMarkov）に比べて正答率が低くなっている。これは、高次になるとパラメータ数がデータ数に比べて多くなり、頑健な推定ができていないためであると考えられる。
【００８１】
また、比較例５（MaxEnt(seq)）と比較例６（MaxEnt）とを比較すると、すべてのデータセットにおいて、比較例５（MaxEnt(seq)）は、比較例６（MaxEnt）に比べて正答率が高くなっている。これは、購買順序を考慮することは、正答率を上げるために重要であることを示唆している。
【００８２】
＜重みαとギャップｌとの関係＞
また、本実施例でリコメンド装置１により推定された重みαとギャップｌとの関係を図９に示す。図９において、musicは、音楽データを示し、movieは、動画データを示している。なお、αl（ｌ＝１〜１０）は、ｌギャップマルコフモデルの重みを示し、αl（ｌ＝０）は、事前確率の重みを示す。図９のグラフに示すように、全データセットともに、ギャップが小さいギャップマルコフモデルの重みが大きい。これは、最近の履歴が購買予測に関する大きな情報を与えるという直感と一致している。
【００８３】
＜ｄ日前までのデータで推定した重みαを用いた正答率＞
音楽データについて、ｄ日前までのデータで推定した重みαを用いて、事前確率、ギャップマルコフモデルのみを更新したときの正答率を図１０に示す。ここで、事前確率およびギャップマルコフモデルにおけるハイパーパラメータ“δ”もｄ日前までのデータで推定したものを用いた。なお、図１０の縦軸は、正答率（accuracy）であり単位は％である。
【００８４】
図１０に示すように、実施例（Our Method）は、比較例６（MaxEnt）、比較例４（GapMarkov）および比較例１（1stMarkov）と比べて、正答率（accuracy）が高い。また、実施例（Our Method）は、過去何日のデータを用いるかによって正答率（accuracy）が変動する。そのため、実施例（Our Method）は、比較例５（MaxEnt(seq)）よりも正答率が高い場合と、低い場合とがあって、平均すると、比較例５（MaxEnt(seq)）と同程度の性能であると言える。なお、実施例（Our Method）は、過去のデータとして、例えば３０日前までのデータで推定した重みを用いた場合には、正答率が、比較例５（MaxEnt(seq)）の正答率よりも約１％上回った。
【００８５】
これらの結果から、以下のことが理解できる。すなわち、図１に示す購買履歴ログ４５に新規のデータを追加した場合、つまり、入力データ（処理用データ）４６が追加された場合に、事前確率４７、ギャップマルコフモデル４８、重み４９を、それぞれ更新する必要がある。このうち、事前確率４７およびギャップマルコフモデル４８よりも、重み４９の方がパラメータの更新に多くの計算量が必要である。したがって、重みαを１カ月に１回程度の割合で更新し、かつ、事前確率とギャップマルコフモデルをそれよりも短い間隔で更新するようにしても、重みαを頻繁に更新したときと同様な高い予測精度を実現できる。そのため、重みαを１カ月に１回程度の割合で更新することで、長期スパンの計算コストを効果的に抑制することが可能となる。
【図面の簡単な説明】
【００８６】
【図１】本発明の実施形態に係るリコメンド装置の構成を示すブロック図である。
【図２】前処理部の構成を示す機能ブロック図である。
【図３】拡張マルコフモデル推定部の構成を示す機能ブロック図である。
【図４】重み推定部の構成を示す機能ブロック図である。
【図５】リコメンド部の構成を示す機能ブロック図である。
【図６】リコメンド装置の動作を示すフローチャートである。
【図７】拡張マルコフモデル推定処理を示すフローチャートである。
【図８】重み推定処理を示すフローチャートである。
【図９】ギャップとしてｌ個前までの購買履歴を用いて推定された重みを示すグラフである。
【図１０】ｄ日前までのデータで推定した重みを用いたときの音楽データでの正答率を示すグラフである。
【符号の説明】
【００８７】
１      リコメンド装置
２      演算手段
３      入力手段
４      記憶手段
５      出力手段
６      バスライン
２１    前処理部（前処理手段）
２２    拡張マルコフモデル推定部
２３    重み推定部（重み推定手段）
２４    リコメンド部（リコメンド手段）
２５    メモリ
４０ａ  プログラム格納部
４１    前処理プログラム
４２    拡張マルコフモデル推定プログラム
４３    重み推定プログラム
４４    リコメンドプログラム
４０ｂ  データ格納部
４５    購買履歴ログ
４６    入力データ
４７    事前確率
４８    ギャップマルコフモデル
４９    重み
２１１  購買履歴ログ読込部
２１２  入力データ書込部
２２１  入力データ読込部
２２２  事前確率推定部（事前確率推定手段）
２２３  ギャップマルコフモデル推定部（ギャップマルコフモデル推定手段）
２２４  ギャップマルコフモデル書込部
２３１  入力データ読込部
２３２  拡張マルコフモデル読込部
２３３  ギャップ重み推定部
２３４  重み書込部
２４１  入力データ読込部
２４２  拡張マルコフモデル読込部
２４３  重み読込部
２４４  最大商品選択部
２４５  リコメンド出力部
【図１】
2008287550.tif 000015
【図２】
2008287550.tif 000016
【図３】
2008287550.tif 000017
【図４】
2008287550.tif 000018
【図５】
2008287550.tif 000019
【図６】
2008287550.tif 000020
【図７】
2008287550.tif 000021
【図８】
2008287550.tif 000022
【図９】
2008287550.tif 000023
【図１０】
2008287550.tif 000024