(57)【要約】【課題】個々のユーザの特性を考慮した適切な推薦が可能な推薦装置、推薦方法、及びプログラムを提供する。【解決手段】推薦システムは、最適政策算出部１５１と、行動決定部１５２と、出力部と、を備える。最適政策算出部１５１は、ユーザの初期状態とユーザのクラスの事前確率と制御期間とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出する。行動決定部１５２は、最適政策算出部１５１によりユーザの状態と時点とが与えられると、遷移確率テーブル１４１及び利得テーブル１４２からユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定し、最適政策算出部１５１に出力する。出力部は、最適政策算出部１５１が決定した最適政策に関する情報を出力する。【選択図】図２
2018190409.tif 000002
【特許請求の範囲】
【請求項１】
ユーザの初期状態とユーザのクラスの事前確率と制御期間とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出する最適政策算出部と、
前記最適政策算出部によりユーザの状態と時点とが与えられると、遷移確率テーブル及び利得テーブルからユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定し、前記最適政策算出部に出力する行動決定部と、
前記最適政策算出部が決定した最適政策に関する情報を出力する出力部と、
を備え、
前記最適政策算出部は、前記制御期間内の各時点とその時点でのユーザの状態とを前記行動決定部に与え、前記行動決定部から各時点における最適行動及び期待総利益の最大値を取得し、取得された各時点における最適行動及び期待総利益の最大値に基づいて最適政策を算出する推薦装置。
【請求項２】
前記最適政策算出部は、前記制御期間におけるマルコフ決定過程問題を動的計画法で解くことにより最適政策を算出する、
請求項１に記載の推薦装置。
【請求項３】
マルコフ連鎖に従って変化するユーザのクラスの遷移確率とユーザの状態遷移確率と期待利得とを記憶する記憶部を備え、
前記最適政策算出部は、前記記憶部に記憶されたユーザのクラスの遷移確率とユーザの状態遷移確率と期待利得とに基づいて、前記制御期間における期待総利得を最大にする最適政策を算出する、
請求項２に記載の推薦装置。
【請求項４】
前記最適政策算出部は、ユーザの初期状態を起点にして、前記制御期間の各時点におけるユーザの状態の遷移を各々のノードに展開したＤＰ木を作成し、前記制御期間内の各時点とその時点におけるユーザの状態とを、ＤＰ木の末端のノードから順に前記行動決定部に与え、
前記行動決定部は、前記最適政策算出部が作成したＤＰ木の与えられた時点のノードにおいて選択し得る行動毎の期待総利得を、与えられたユーザの状態と各々の行動に対応する遷移確率と期待利得とから算出して、期待総利得が最大となる行動を最適行動として決定する、
請求項１から３のいずれか１項に記載の推薦装置。
【請求項５】
前記最適政策算出部は、前記行動決定部が決定したＤＰ木の全ノードにおける最適行動と各ノード以降の期待総利得の最大値とに基づいて算出した最適政策を出力する、
請求項４に記載の推薦装置。
【請求項６】
ユーザのクラスが既知である履歴情報とユーザのクラスが未知である履歴情報とに基づいて半教師付学習を実行することで、ユーザのクラスの事前確率、ユーザのクラスの遷移確率及びユーザの状態遷移確率を推定する確率推定部を備え、
前記最適政策算出部に与えられるユーザのクラスの事前確率は、前記確率推定部により推定されたユーザのクラスの事前確率であり、
前記行動決定部が参照するユーザのクラスの遷移確率及びユーザの状態遷移確率は、前記確率推定部により推定されたユーザのクラスの遷移確率及びユーザの状態遷移確率である、
請求項１から５のいずれか１項に記載の推薦装置。
【請求項７】
前記最適政策算出部は、ユーザの初期状態とクラスの事前確率と質問回数と推薦回数とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出し、
前記行動決定部は、ユーザに対する質問及び当該質問へのユーザの回答並びにユーザに対する推薦及び当該推薦へのユーザの反応を含む履歴と、時点と、が与えられると、当該時点以降の期待総利得を最大にする最適行動と期待総利得の最大値とを決定する、
請求項１から６のいずれか１項に記載の推薦装置。
【請求項８】
ユーザの初期状態とユーザのクラスの事前確率と制御期間とを取得するデータ取得ステップと、
ユーザの状態と時点とが与えられると、ユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定する行動決定ステップと、
前記行動決定ステップで決定された各時点における最適行動及び期待総利益の最大値に基づいて、前記制御期間における期待総利得を最大にする最適政策を算出する最適政策算出ステップと、
前記最適政策算出ステップが決定した最適政策に関する情報を出力する出力ステップと、
を含む推薦方法。
【請求項９】
コンピュータを、
ユーザの初期状態とユーザのクラスの事前確率と制御期間とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出する最適政策算出部、
前記最適政策算出部によりユーザの状態と時点とが与えられると、ユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定し、前記最適政策算出部に出力する行動決定部、
前記最適政策算出部が決定した最適政策に関する情報を出力する出力部、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推薦装置、推薦方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、インターネット上でユーザ（顧客）に商品やサービスを販売する通信販売サイトが広く普及している。通信販売サイトでは、ユーザがＷｅｂサイトを閲覧した際に、その嗜好やニーズに合わせて適切な商品やサービスを推薦する推薦システムが用いられている。
【０００３】
例えば、特許文献１には、特定のユーザと他のユーザとの属性の重複度合いを表す指標に基づいて、特定のユーザの好みに適した商品やサービスを推薦する推薦システムが開示されている。
【０００４】
また、非特許文献１には、マルコフ決定過程を用いて作成した予測モデルを用いて、ユーザに商品を推薦する推薦システムが開示されている。非特許文献１の推薦システムでは、商品の好みなどが似たユーザが同一のクラスに属すると仮定し、クラス未知のユーザに対して当該ユーザの売上高を統計的決定理論に基づきベイズ基準のもとで最大化している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−１４６６１０号公報
【非特許文献】
【０００６】
【非特許文献１】岩井秀輔、外３名、「推薦対象ユーザのクラスが未知の推薦問題におけるマルコフ決定過程を用いた推薦システムに関する一考察」、電子情報通信学会技術研究報告ＩＴ、Ｖｏｌ．１１４、Ｎｏ．１３８、ｐｐ．４９−５４（２０１４）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
実際のユーザでは、時間の経過とともにユーザの健康状態や趣味等が変化するため、ユーザのクラスも徐々に変化することが想定される。例えば、いかなる食品や薬品を購入するかは、時間の経過とともに変化するユーザの健康状態等に依存する。しかし、特許文献１及び非特許文献１の推薦システムでは、ユーザのクラス変化を考慮しておらず、ユーザのクラス変化に応じた適切な商品やサービスを推薦できない、という問題がある。また、特許文献１及び非特許文献１の推薦システムでは、関連する情報を全く保有していない新規ユーザの場合を考慮しておらず、新規ユーザに適切な商品やサービスを推薦できない、という問題がある。そして、これらの問題は、ユーザに商品やサービスを推薦する場合に限られず、ユーザに他の被推薦対象を推薦する場合にも存在している。
【０００８】
本発明は、このような背景に基づいてなされたものであり、個々のユーザの特性を考慮した適切な推薦が可能な推薦装置、推薦方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明の第１の観点に係る推薦装置は、
ユーザの初期状態とユーザのクラスの事前確率と制御期間とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出する最適政策算出部と、
前記最適政策算出部によりユーザの状態と時点とが与えられると、遷移確率テーブル及び利得テーブルからユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定し、前記最適政策算出部に出力する行動決定部と、
前記最適政策算出部が決定した最適政策に関する情報を出力する出力部と、
を備え、
前記最適政策算出部は、前記制御期間内の各時点とその時点でのユーザの状態とを前記行動決定部に与え、前記行動決定部から各時点における最適行動及び期待総利益の最大値を取得し、取得された各時点における最適行動及び期待総利益の最大値に基づいて最適政策を算出する。
【００１０】
前記最適政策算出部は、前記制御期間におけるマルコフ決定過程問題を動的計画法で解くことにより最適政策を算出してもよい。
【００１１】
マルコフ連鎖に従って変化するユーザのクラスの遷移確率とユーザの状態遷移確率と期待利得とを記憶する記憶部を備え、
前記最適政策算出部は、前記記憶部に記憶されたユーザのクラスの遷移確率とユーザの状態遷移確率と期待利得とに基づいて、前記制御期間における期待総利得を最大にする最適政策を算出してもよい。
【００１２】
前記最適政策算出部は、ユーザの初期状態を起点にして、前記制御期間の各時点におけるユーザの状態の遷移を各々のノードに展開したＤＰ木を作成し、前記制御期間内の各時点とその時点におけるユーザの状態とを、ＤＰ木の末端のノードから順に前記行動決定部に与え、
前記行動決定部は、前記最適政策算出部が作成したＤＰ木の与えられた時点のノードにおいて選択し得る行動毎の期待総利得を、与えられたユーザの状態と各々の行動に対応する遷移確率と期待利得とから算出して、期待総利得が最大となる行動を最適行動として決定してもよい。
【００１３】
前記最適政策算出部は、前記行動決定部が決定したＤＰ木の全ノードにおける最適行動と各ノード以降の期待総利得の最大値とに基づいて算出した最適政策を出力してもよい。
【００１４】
ユーザのクラスが既知である履歴情報とユーザのクラスが未知である履歴情報とに基づいて半教師付学習を実行することで、ユーザのクラスの事前確率、ユーザのクラスの遷移確率及びユーザの状態遷移確率を推定する確率推定部を備え、
前記最適政策算出部に与えられるユーザのクラスの事前確率は、前記確率推定部により推定されたユーザのクラスの事前確率であり、
前記行動決定部が参照するユーザのクラスの遷移確率及びユーザの状態遷移確率は、前記確率推定部により推定されたユーザのクラスの遷移確率及びユーザの状態遷移確率であってもよい。
【００１５】
前記最適政策算出部は、ユーザの初期状態とクラスの事前確率と質問回数と推薦回数とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出し、
前記行動決定部は、ユーザに対する質問及び当該質問へのユーザの回答並びにユーザに対する推薦及び当該推薦へのユーザの反応を含む履歴と、時点と、が与えられると、当該時点以降の期待総利得を最大にする最適行動と期待総利得の最大値とを決定してもよい。
【００１６】
上記目的を達成するために、本発明の第２の観点に係る推薦方法は、
ユーザの初期状態とユーザのクラスの事前確率と制御期間とを取得するデータ取得ステップと、
ユーザの状態と時点とが与えられると、ユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定する行動決定ステップと、
前記行動決定ステップで決定された各時点における最適行動及び期待総利益の最大値に基づいて、前記制御期間における期待総利得を最大にする最適政策を算出する最適政策算出ステップと、
前記最適政策算出ステップが決定した最適政策に関する情報を出力する出力ステップと、
を含む。
【００１７】
上記目的を達成するために、本発明の第３の観点に係るプログラムは、
コンピュータを、
ユーザの初期状態とユーザのクラスの事前確率と制御期間とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出する最適政策算出部、
前記最適政策算出部によりユーザの状態と時点とが与えられると、ユーザのクラスの遷移確率、ユーザの状態遷移確率及び期待利得を参照して、当該時点以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定し、前記最適政策算出部に出力する行動決定部、
前記最適政策算出部が決定した最適政策に関する情報を出力する出力部、
として機能させる。
【発明の効果】
【００１８】
本発明によれば、個々のユーザの特性を考慮した適切な推薦が可能な推薦装置、推薦方法、及びプログラムを提供できる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態１に係る推薦システムの構成を示すブロック図である。
【図２】本発明の実施の形態１に係る推薦装置の構成を示すブロック図である。
【図３】（ａ）は、遷移確率テーブルのデータテーブルの一例、（ｂ）は、利得テーブルのデータテーブルの一例を示す図である。
【図４】本発明の実施の形態１に係る推薦装置の制御部の構成を示すブロック図である。
【図５】本発明の実施の形態１に係るユーザ端末の構成を示すブロック図である。
【図６】本発明の実施の形態１に係る最適政策算出処理の流れを示すフローチャートである。
【図７】本発明の実施の形態１に係るＤＰ木の一例を示す図である。
【図８】本発明の実施の形態１に係る行動決定処理の流れを示すフローチャートである。
【図９】本発明の実施の形態２に係る推薦装置の構成を示すブロック図である。
【図１０】本発明の実施の形態２に係る確率推定処理の流れを示すフローチャートである。
【図１１】本発明の実施の形態３に係る推薦装置の制御部の構成を示すブロック図である。
【図１２】本発明の実施の形態３に係るＤＰ木の一例を示す図である。
【図１３】実施例２における数値計算結果を示す図である。
【図１４】（ａ）、（ｂ）は、実施例３における商品推薦に対するユーザの反応確率、（ｃ）は、実施例３における質問に対する回答確率を示す図である。
【図１５】実施例４における数値計算結果を示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明に係る推薦装置、推薦方法、及びプログラムの実施の形態を、図面を参照しながら詳細に説明する。各図面においては、同一又は同等の部分に同一の符号を付す。以下、ユーザに商品を推薦する場合を例に説明するが、本発明に係る推薦装置、推薦方法、及びプログラムがユーザに推薦する被推薦対象は商品に限られない。
【００２１】
（実施の形態１）
図１〜図８を参照して、実施の形態１に係る推薦装置、推薦方法、及びプログラムを説明する。実施の形態１に係る推薦システムは、ユーザのクラスの変化をマルコフ連鎖（Markov Chain）で表現し、マルコフ決定過程（Markov Decision Process：ＭＤＰ）の問題を解くことにより、ユーザのクラスの変化に応じてユーザに適切な商品を推薦する。ＭＤＰは、確率システムの動的な最適化問題を定式化できる数理モデルである。
【００２２】
実施の形態１に係る推薦システムでは、ユーザのクラスが未知、各種確率分布を支配する真のパラメータが既知であると仮定する。そして、実施の形態１に係る推薦システムでは、ユーザの初期状態、未知であるクラスの事前確率及び制御期間（推薦回数）を受け付けると、期待利得値（売上高）をベイズ基準のもとで最大化するように、各時点及び各履歴における商品の推薦方法を最適政策として出力する。状態は、前回の推薦商品と反応に関する情報（履歴）であり、初期状態は、初期段階の状態、言い換えると初期段階から一つ前の段階の推薦商品と反応に関する情報である。また、クラスの事前確率は、初期段階においてユーザが属するクラスを決定する確率である。
【００２３】
図１は、推薦システム１の構成を示すブロック図である。図１に示すように、推薦システム１は、推薦装置１００と、ユーザ端末２００と、を備える。
【００２４】
推薦装置１００は、ユーザの嗜好やニーズ（ユーザのクラス）に合わせて商品又はサービスを推薦する。推薦装置１００は、例えば、プログラムに基づいて動作するサーバ等の情報処理装置である。推薦装置１００は、専用のシステムで実現してもよく、小型汎用コンピュータを用いて実現してもよい。ユーザ端末２００は、ユーザに対して入出力のインターフェースを提供する。ユーザ端末２００は、例えば、スマートフォン、タブレット、パーソナルコンピュータ等の情報処理端末である。
【００２５】
推薦システム１のデータの流れの概要について説明する。ユーザ端末２００は、ユーザの指示を受け付けることによって、通信ネットワーク（例えば、インターネット）を介して、推薦装置１００に所望のＷｅｂページをリクエストする。推薦装置１００は、リクエストされたＷｅｂページに関する情報を記憶しているものとする。推薦装置１００は、記憶されたユーザの過去の商品又はサービスの購入履歴等に基づいて、ユーザに推薦する商品又はサービスを決定する。そして、推薦装置１００は、ユーザがリクエストしたＷｅｂページの情報と、ユーザに推薦する商品又はサービスの画像に関する情報と、をユーザ端末２００に送信する。ユーザ端末２００は、推薦装置１００から情報を受信し、ユーザがリクエストしたＷｅｂページと、推薦された商品又はサービスに関する画像と、をユーザに向けて表示する。
【００２６】
次に、図２を参照して、推薦装置１００の構成について説明する。図２は、推薦装置１００の構成を示すブロック図である。推薦装置１００は、指示受付部１１０と、表示部１２０と、通信部１３０と、記憶部１４０と、制御部１５０と、を備える。指示受付部１１０、表示部１２０、通信部１３０及び記憶部１４０は、制御部１５０と有線又は無線の通信回線を介して相互に通信可能に接続されている。
【００２７】
指示受付部１１０は、ユーザの指示を受け付け、受け付けた操作に対応する操作信号を制御部１５０に供給する。指示受付部１１０は、ユーザの初期状態、未知であるクラスの事前確率及び制御期間等に関する情報を受け付ける。指示受付部１１０は、例えば、ボタン、キーボード、マウス等であってもよく、外部の指示装置等を接続可能なコネクタ等であってもよい。
【００２８】
表示部１２０は、制御部１５０から供給される各種の画像データ等に基づいて各種の画像等を表示する。表示部１２０は、例えば、液晶パネル、有機ＥＬ（Electro Luminescence）パネルを備える。また、表示部１２０は、推薦システム１に設けられたコネクタを介して接続可能な外部の表示装置等であってもよい。
【００２９】
なお、指示受付部１１０と表示部１２０とは、タッチパネルによって一体に構成されてもよい。タッチパネルは、所定の操作を受け付ける操作画面を表示すると共に、操作画面においてユーザが接触操作を行った位置に対応する操作信号を制御部１５０に供給する。
【００３０】
通信部１３０は、インターネット等の通信ネットワークに接続することが可能なインターフェースである。通信部１３０は、ユーザ端末２００、外部サーバ、メモリ等（図示せず）と通信ネットワークを介して通信する。通信部１３０は、推薦装置１００により推薦された最適な商品又はサービスに関するに関する情報を出力する出力部の一例である。
【００３１】
記憶部１４０は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ、ハードディスク装置等を備え、制御部１５０により実行され、制御部１５０を後述する最適政策算出部１５１、行動決定部１５２として機能させるプログラムや各種データを記憶する。また、記憶部１４０は、制御部１５０が処理を実行するためのワークメモリとして機能する。
【００３２】
記憶部１４０は、遷移確率テーブル１４１と、利得テーブル１４２と、を備える。以下、図３のデータテーブルを参照して、各テーブルについて説明する。
【００３３】
図３（ａ）は、遷移確率テーブル１４１を示すデータテーブルの一例である。遷移確率テーブル１４１は、マルコフ連鎖に従って変化するユーザのクラスの遷移確率ｐ（ｗｔ＋１｜ｗｔ，φ＊）及びユーザの状態遷移確率ｐ（ｚｔ｜ｙｔ−１，ｚｔ−１，ｙｔ，ｗｔ，θ＊）を記憶する。遷移確率テーブル１４１は、全ユーザに対して共通である。
【００３４】
図３（ｂ）は、利得テーブル１４２を示すデータテーブルの一例である。利得テーブル１４２は、ＭＤＰにおける商品又はサービスの利得ｒ（ｎｉ）を記憶する。利得テーブル１４２は、遷移確率テーブル１４１と同様に、全ユーザに対して共通である。
【００３５】
さらに、記憶部１４０は、ユーザ端末２００に配信するＷｅｂページに関する情報を記憶する。
【００３６】
図２に戻り、制御部１５０は、例えば、ＣＰＵ（Central Processing Unit）等のプロセッサを備え、推薦装置１００の各部の制御を行う。制御部１５０は、記憶部１４０に記憶されているプログラムを実行することにより、図６の最適政策算出処理及び図８の行動決定処理を実行する。
【００３７】
制御部１５０は、機能的には、最適政策算出部１５１と、行動決定部１５２と、を備える。以下、図４を参照して、制御部１５０の機能的な構成を説明する。図４は、制御部１５０の機能的な構成を示すブロック図である。
【００３８】
最適政策算出部１５１は、ユーザの初期状態ｘ１、クラスの事前確率ｐ（ｗ１）及び制御期間Ｔが与えられると、制御期間Ｔの期待総利得を最大にする最適政策を算出する。より詳細に説明すると、最適政策算出部１５１は、ユーザの初期状態ｘ１、クラスの事前確率ｐ（ｗ１）及び制御期間Ｔが与えられると、行動決定部１５２と連携して動的計画法（Dynamic Programming：ＤＰ）の問題を解くことにより、マルコフ連鎖に従って変化するユーザのクラスの遷移確率とユーザの状態の遷移確率と期待利得とに基づいて、制御期間Ｔの期待総利得を最大にする最適政策を算出する。ＤＰは、最適性原理を持つ多段階決定過程に対して適用され、ＤＰ木（ＤＰグラフ）で表現される全探索問題を解くための手法である。
【００３９】
最適政策算出部１５１は、ＤＰ木作成部１５１ａと、ＤＰ実施部１５１ｂと、を備える。ＤＰ木作成部１５１ａは、ユーザの初期状態ｘ１、クラスの事前確率ｐ（ｗ１）及び制御期間Ｔに基づいて、ＤＰで用いられるＤＰ木を作成する。
【００４０】
ＤＰ実施部１５１ｂは、ＤＰ木作成部１５１ａにより作成されたＤＰ木において制御期間Ｔの最後の時点から遡りながらＤＰの問題を解くことにより、制御期間Ｔの期待総利得を最大にする最適政策を算出する。
【００４１】
行動決定部１５２は、最適政策算出部１５１からユーザの状態ｘｔを含む履歴と時点ｔとが与えられると、当該時点ｔの当該履歴のもとで、それ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を算出する。行動決定部１５２は、マルコフ連鎖に従って変化するユーザのクラスの遷移確率と、ユーザの状態遷移確率と、期待利得と、に基づいて、期待総利得を最大にする最適行動を決定する。
【００４２】
推薦装置１００が実行する処理は、例えば、上述の物理的な構成を備える装置が、記憶部１４０に記憶されたプログラムを実行することによって実現される。本発明は、プログラムとして実現されてもよく、そのプログラムが記録されたフレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disk Read-Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＭＯ（Magneto-Optical disk）等のコンピュータ読み取り可能な記憶媒体として実現されてもよい。
【００４３】
図５は、ユーザ端末２００の構成を示すブロック図である。ユーザ端末２００は、指示受付部２１０と、表示部２２０と、通信部２３０と、記憶部２４０と、制御部２５０と、を備える。指示受付部２１０、表示部２２０、通信部２３０及び記憶部２４０は、制御部２５０と有線又は無線の通信回線を介して相互に通信可能に接続されている。
【００４４】
指示受付部２１０は、ユーザの指示を受け付け、受け付けた操作に対応する操作信号を制御部２５０に供給する。指示受付部２１０は、例えば、ユーザが訪問したいＷｅｂページに関する指示を受け付ける。
【００４５】
表示部２２０は、制御部２５０から供給される各種の画像データ等に基づいて各種の画像等を表示する。表示部２２０は、表示部１２０と同様の構成を備えている。表示部２２０は、例えば、ユーザがリクエストしたＷｅｂページと、推薦装置１００により推薦された商品又はサービスに関する画像と、を表示する。表示部２２０は、推薦装置１００により推薦された最適な商品又はサービスに関するに関する情報を出力する。
【００４６】
なお、指示受付部２１０と表示部２２０とは、タッチパネルによって一体に構成されてもよい。タッチパネルは、所定の操作を受け付ける操作画面を表示すると共に、操作画面においてユーザが接触操作を行った位置に対応する操作信号を制御部２５０に供給する。
【００４７】
通信部２３０は、インターネット等の通信ネットワークに接続することが可能なインターフェースである。通信部２３０は、推薦装置１００、外部サーバ、メモリ等と通信ネットワークを介して通信する。
【００４８】
記憶部２４０は、ＲＡＭ、ＲＯＭ、フラッシュメモリ等を備え、制御部２５０により実行されるプログラムや各種データ、アプリケーションを記憶する。また、記憶部２４０は、制御部２５０が処理を実行するためのワークメモリとして機能する。
【００４９】
制御部２５０は、例えば、ＣＰＵ等のプロセッサを備え、ユーザ端末２００の各部の制御を行う。制御部２５０は、記憶部２４０に記憶されているプログラムを実行することにより各種処理を実行する。
【００５０】
次に、ＭＤＰを利用した商品の推薦方法の数理モデルを説明する。ここでは、初期状態から商品の推薦をＴ回行うＭＤＰ問題を扱うこととする。また、ユーザのクラスは、前述のように未知であり、マルコフ連鎖に従って変化するものとする。以下、商品を推薦する時点をｔ（１≦ｔ≦Ｔ）とする。ｔ＝１のとき、初期段階であり、ｔ＝Ｔのとき、最後の推薦を行う時点である。
【００５１】
まず、推薦方法の数理モデルで使用する記号を以下に定義する。理解を容易にするために、推薦システム１がユーザに対して書籍を推薦する場合を例に説明する。
【００５２】
ｃｉ，ｃｉ∈Ｃ（ｉは自然数）は、ユーザのクラスであり、Ｃ＝｛ｃ１，ｃ２，…，ｃ｜Ｃ｜｝（｜Ｃ｜は自然数）は、ユーザのクラスの集合である。ユーザのクラスｃｉは、例えば、推理小説を好むクラス、エッセイを好むクラス、漫画を好むクラス等である。
【００５３】
ｍｉ，ｍｉ∈Ｍ は、推薦対象の商品であり、Ｍ＝｛ｍ１，ｍ２，…，ｍ｜Ｍ｜｝（｜Ｍ｜は自然数）は、推薦対象の商品の集合（商品集合）である。商品ｍｉの推薦は、ＭＤＰにおける行動選択に相当する。推薦対象の商品ｍｉは、例えば、推理小説、エッセイ、漫画等のジャンルに属する書籍である。
【００５４】
ｎｉ，ｎｉ∈Ｎ は、推薦に対するユーザの反応であり、Ｎ＝｛ｎ１，ｎ２，…，ｎ｜Ｎ｜｝（｜Ｎ｜は自然数）は、推薦に対するユーザの反応の集合（反応集合）である。１≦ｉ≦｜Ｍ｜では、ｎｉ＝ｍｉであり、ユーザの反応ｎｉは、商品ｍｉの購入に相当する。｜Ｎ｜と｜Ｍ｜とは｜Ｎ｜＝｜Ｍ｜＋１の関係にあり、ｎ｜Ｍ｜＋１はユーザが何も購入しなかったことを示す。
【００５５】
ｒ（ｎｉ）は、１≦ｉ≦｜Ｍ｜において、商品ｍｉの売上高を示し、ＭＤＰの利得に相当する。ｉ＝｜Ｍ｜＋１の場合、ｒ（ｎ｜Ｍ｜＋１）＝０である。商品ｍｉの売上高ｒ（ｎｉ）は、例えば、通販サイト上で販売されている推理小説、エッセイ、漫画等の販売価格である。
【００５６】
ｙｔ，ｙｔ∈Ｍは、ｔ回目の推薦商品を示し、ＭＤＰのｔ期の行動に相当する。
【００５７】
ｚｔ，ｚｔ∈Ｎは、ｔ回目の推薦に対するユーザのｔ期の反応を示す。
【００５８】
ｗｔ，ｗｔ∈Ｃは、ｔ期のユーザのクラスを示す。前述のとおりｔ期のユーザのクラスｗｔは未知である。初期段階のユーザのクラスも未知であるため、初期段階においてユーザが属するクラスを決定する確率であるクラスの事前確率ｐ（ｗ１）を導入する。クラスの事前確率ｐ（ｗ１）は、既知である。
【００５９】
クラスの事前確率ｐ（ｗ１）は、例えば、ユーザ本人及び他のユーザのプロファイル情報（例えば、通販サイトでの会員登録時のアンケートへの回答結果等）、ユーザ本人及び他のユーザの履歴情報、通販サイトで扱っている商品に関する専門家等の経験則、多数のユーザを対象にした趣味や嗜好に関する調査結果、各クラスを代表する商品の過去の売上高等のいずれか一つ又はこれらの組み合わせに基づいて推定される。例えば、クラスが既知の履歴情報は、ユーザの自己申告、専門家の経験等に基づいて推定できる。また、事前の履歴情報等が存在しない場合、クラスの事前確率ｐ（ｗ１）は、例えば、等確率に設定できる。
【００６０】
また、クラスの事前確率ｐ（ｗ１）は、ユーザ本人及び他のユーザのクラス既知の履歴情報又はクラス未知の履歴情報を用いて、統計学的に推定してもよく、専門家の経験則に基づいて推定してもよい。例えば、クラスの事前確率ｐ（ｗ１）の推定には、最尤推定法を用いてもよい。また、クラス未知の履歴情報の場合又はクラス未知の履歴情報とクラス既知のクラス情報が混在する場合、クラスの事前確率ｐ（ｗ１）の推定にＥＭ（Expectation Maximization）アルゴリズムを用いてもよい。
【００６１】
ｘｔは、ｔ回目の推薦を受ける際のユーザの状態で、ＭＤＰのｔ期の状態に相当する。ｔ回目のユーザの状態ｘｔは、１期前（ｔ−１回目）の推薦商品ｙｔ−１と、それに対するユーザの反応ｚｔ−１と、により構成されるため、（ｙｔ−１，ｚｔ−１）とも表現される。
【００６２】
通販サイトを初めて利用する新規のユーザの場合、初期状態ｘ１は、前回の推薦商品と反応に相当する情報がないため、空列である。この場合、反応集合Ｎに「何も買わない」、商品集合Ｍにも「何も推薦しない」との要素を含めておき、初期状態ｘ１を「何も買わない」との要素及び「何も推薦しない」との要素の少なくとも一つで表現してもよい。また、通販サイトを以前から利用しているユーザの場合、初期状態ｘ１は、前回（履歴情報中の最後）の推薦商品と反応とで構成できる。
【００６３】
ｐ（ｗｔ＋１｜ｗｔ，φ＊）は、ユーザのクラスの遷移確率を示す。ユーザのクラスの遷移確率ｐ（ｗｔ＋１｜ｗｔ，φ＊）は、例えば、ユーザ本人又は他のユーザの履歴情報、通販サイトで扱っている商品に関する専門家等の経験等に基づいて設定される。また、ユーザのクラスの遷移確率ｐ（ｗｔ＋１｜ｗｔ，φ＊）は、ユーザ本人及び他のユーザのクラス既知の履歴情報又はクラス未知の履歴情報を用いて統計学的に推定してもよく、専門家の経験則に基づいて推定してもよい。
【００６４】
ｐ（ｘｔ＋１｜ｘｔ，ｙｔ，ｗｔ，θ＊） は、ユーザの状態遷移確率を示し、ＭＤＰの状態遷移確率に相当する。ユーザの状態遷移確率ｐ（ｘｔ＋１｜ｘｔ，ｙｔ，ｗｔ，θ＊）は、１期前（ｔ−１回目）の推薦商品ｙｔ−１に対する反応がｚｔ−１の場合に、クラスｗｔのユーザが推薦商品ｙｔに対する反応がｚｔとなる確率であるため、ｐ（ｚｔ｜ｙｔ−１，ｚｔ−１，ｙｔ，ｗｔ，θ＊）とも表現される。ユーザの状態遷移確率ｐ（ｘｔ＋１｜ｘｔ，ｙｔ、ｗｔ，θ＊）は、ユーザ本人又は他のユーザの履歴情報、当該通販サイトで扱っている商品に関する専門家等の経験等に基づいて設定される。また、ユーザの状態遷移確率ｐ（ｘｔ＋１｜ｘｔ，ｙｔ，ｗｔ，θ＊）は、ユーザ本人及び他のユーザのクラス既知の履歴情報又はクラス未知の履歴情報を用いて統計学的に推定してもよく、専門家の経験則に基づいて推定してもよい。
【００６５】
φ＊、θ＊ は、確率分布を支配する真のパラメータであり、既知である。また、ｘｔｙｔｚｔｗｔは、履歴（系列）であり、ｘ１ｙ１ｚ１ｗ１…ｘｔｙｔｚｔｗｔを示す。
【００６６】
次に、統計的決定理論に基づいて推薦方法の数理モデルを定式化する。パラメータφ＊、θ＊のもとで決定関数ｄ（・，・）によって商品ｙｔを推薦し、履歴ｘＴｙＴｚＴｗＴへと遷移した場合の総利得（総売上）を示す効用関数Ｕ（ｄ（・，・），ｘＴｙＴｚＴｗＴ，θ＊，φ＊）は、以下の式で表される。
【００６７】
【数１】
2018190409.tif 000003
【００６８】
ここで、決定関数ｄ（・、・）は、ｔ期までの履歴ｘｔｙｔ−１ｚｔ−１と、期を示すｔとを受けとって、ｔ期の推薦商品ｙｔを出力する関数である。
【００６９】
次に、ユーザの初期状態ｘ１、ユーザの初期のクラスｗ１、パラメータθ＊、φ＊のもとで、決定関数ｄ（・，・）を用いた場合の総利得の期待値である期待効用ＥＵ（ｄ（・，・），ｘ１，ｗ１，θ＊，φ＊）は、式（１）の効用関数Ｕ（ｄ（・，・），ｘＴｙＴｚＴｗＴ，θ＊，φ＊）を用いて以下の式で表される。
【００７０】
【数２】
2018190409.tif 000004
【００７１】
ただし、ｘＴ２= ｘ２…ｘＴ、ｗＴ２ = ｗ２…ｗＴである。クラスｗ１は未知であるため、期待効用ＥＵ（ｄ（・，・），ｘ１，ｗ１，θ＊，φ＊）に事前確率ｐ（ｗ１）を導入する必要がある。式（２）の期待効用ＥＵ（ｄ（・，・），ｘ１，ｗ１，θ＊，φ＊）に事前確率ｐ（ｗ１）を導入したベイズ期待効用ＢＥＵ（ｄ（・，・），ｘ１，ｐ（ｗ１），θ＊，φ＊）は、以下の式で表される。
【００７２】
【数３】
2018190409.tif 000005
【００７３】
式（３）のベイズ期待効用ＢＥＵ（ｄ（・，・），ｘ１，ｐ（ｗ１），θ＊，φ＊）を最大にする決定関数ｄ（・，・）がベイズ基準のもとで総売上を最大にする最適な推薦方法に相当する。式（３）のベイズ期待効用ＢＥＵ（ｄ（・，・），ｘ１，ｐ（ｗ１），θ＊，φ＊）を書き下すと、Ｔ期間の入れ子構造になるため、プログラムの構造を再帰的に繰り返されるように記述できる。この入れ子構造にＤＰを適用することにより、最適な推薦商品（最適政策）を算出する数理モデルを導出できる。
【００７４】
次に、指定されたノード（時点、履歴）以降の期待総利得の最大値を算出する方法を説明する。ｔ=Ｔ（Ｔ期目）の場合、行動決定部１５２は、以下に表される式を用いて、指定されたノード以降の期待総利得の最大値Ｖ（ｘＴｙＴ−１ｚＴ−１，Ｔ）を算出する。
【００７５】
【数４】
2018190409.tif 000006
【００７６】
ただし、式（４）は、以下の式（５）〜式（７）を満たす。
【００７７】
【数５】
2018190409.tif 000007
【数６】
2018190409.tif 000008
【数７】
2018190409.tif 000009
【００７８】
式（５）のｐ（ｚＴ｜ｙＴ，ｚＴ−１，ｙＴ−１，ｙＴ，θ＊）は、ユーザの反応確率の事後確率ｐ（ｗＴ｜ｙＴ−１ｚＴ−１） による期待値であり、式（４）のＶ（ｘＴｙＴ−１ｚＴ−１，Ｔ） は最後の期ｔ＝Ｔの期待利得の最大値である。式（４）の右辺を最大化する行動ｙＴが推薦商品である。ｐ（ｚＴ｜ｙＴ−１，ｚＴ−１，ｙＴ，ｗＴ，θ＊）とｐ（ｗＴ｜ｗＴ−１、φ＊）は遷移確率テーブル１４１から読み取ったものであり、ｒ（ｚＴ）は利得テーブル１４２ から読み取ったものである。
【００７９】
１≦ｔ≦Ｔ−１の場合、行動決定部１５２は、以下に表される式を用いて、ｔ時点目以降の期待総利得Ｖ（ｘｔｙｔ−１ｚｔ−１，ｔ）を算出する。式（８）の右辺を最大化する行動ｙｔが推薦商品である。
【００８０】
【数８】
2018190409.tif 000010
【００８１】
次に、図６のフローチャートを参照して、実施の形態１に係る最適政策算出部１５１が実行する最適政策算出処理について説明する。最適政策算出処理は、期待値をベイズ基準のもとで最大化する最適政策を算出する処理である。
【００８２】
まず、最適政策算出部１５１は、ユーザの初期状態ｘ１、未知クラスの事前確率ｐ（ｗ１）及び制御期間Ｔに関するデータを取得する（ステップＳ１０１）。ユーザの初期状態ｘ１、未知クラスの事前確率ｐ（ｗ１）及び制御期間Ｔは、最適政策算出処理を実行する前に記憶部１４０に記憶されているものとする。
【００８３】
次に、ＤＰ木作成部１５１ａは、ユーザの初期状態ｘ１、未知クラスの事前確率ｐ（ｗ１）及び制御期間Ｔに基づいて、Ｔ期間の期待総利得を最大化するためのＤＰの問題を解くためのＤＰ木を作成する（ステップＳ１０２）。ＤＰ木は、式（３）に基づいて作成する。
【００８４】
図７は、商品数が２つの場合にＤＰ木作成部１５１ａが作成するＤＰ木の一例である。図７のＤＰ木では、１時点目はユーザの初期状態ｘ１で表現され、２時点目からＴ時点目までは、ユーザの想定される履歴（当該時点までに推薦された商品ｙｔと当該商品への反応ｚｔ）で表現される。例えば、２時点目の上部には、状態ｘ１、商品ｍ１、反応ｎ１、状態ｘ２からなる履歴が載せられている。なお、ｔ時点目の状態ｘｔは、ｔ−１時点目の推薦商品と反応（ｙｔ−１，ｚｔ−１）で表される。推薦システム１を適用する以前の履歴データが存在しない新規ユーザの場合、初期状態ｘ１は空列（履歴なしの状態）である。
【００８５】
次に、ＤＰ実施部１５１ｂは、ＤＰ木の末端（Ｔ時点目）ノードから遡りながら順にノードを選択し、当該ノードでの最適な行動（最適な推薦商品）と当該ノード以降の期待総利得の最大値とを、図８の行動決定処理を実行する行動決定部１５２と連携して決定する（ステップＳ１０３）。
【００８６】
ここで、図８のフローチャートを参照して、行動決定部１５２が実行する行動決定処理を説明する。行動決定処理は、各ノードにおける最適な行動と各ノード以降の期待総利得の最大値とを決定する処理である。
【００８７】
まず、行動決定部１５２は、ノードの時点ｔと、ユーザの履歴（ｔ時点目までの系列ｘｔｙｔ−１ｚｔ−１）と、を取得する（ステップＳ２０１）。
【００８８】
次いで、行動決定部１５２は、ステップＳ２０１で受け取った時点ｔとユーザの履歴（ｔ時点目までの系列ｘｔｙｔ−１ｚｔ−１）とに応じて、当該ノードにおける最適行動を決定し、当該ノード以降の期待総利得の最大値を算出する（ステップＳ２０２）。具体的には、行動決定部１５２は、遷移確率テーブル１４１及び利得テーブル１４２から読み取った遷移確率ｐ（ｗｔ＋１｜ｗｔ，φ＊）、ｐ（ｚｔ｜ｙｔ−１，ｚｔ−１，ｙｔ，ｗｔ，θ＊）及び利得ｒ（ｎｉ）を参照して、式（４）又は式（８）の右辺を最大化する行動ｙｔを推薦商品とする。最大化された式（４）又は式（８）の右辺の値は、期待総利得の最大値である。
【００８９】
次に、行動決定部１５２は、当該ノードにおける最適行動と当該ノード以降の期待総利得の最大値とをＤＰ実施部１５１ｂへ出力し（ステップＳ２０３）、処理をリターンする。以上が行動決定処理の流れである。
【００９０】
再び図６に戻り、ステップＳ１０３の処理の終了後、最適政策算出部１５１は、ＤＰの問題をＤＰ木の１時点目のノードまで全て解き終わったかどうかを判定する（ステップＳ１０４）。
【００９１】
ＤＰの問題をＤＰ木の１時点目のノードまで全て解き終わった場合（ステップＳ１０４：ＹＥＳ）、最適政策算出部１５１は、ＤＰ木の全ノードにおける最適な行動と当該ノード以降の期待総利得の最大値を最適政策として出力し（ステップＳ１０５）、処理を終了する。
【００９２】
他方、ＤＰの問題をＤＰ木の１時点目のノードまで全て解き終わっていない場合（ステップＳ１０４：ＮＯ）、最適政策算出部１５１は、処理をステップＳ１０３に戻し、ＤＰの問題を全て解き終わるまでステップＳ１０３、ステップＳ１０４の処理を繰り返す。以上が、最適政策算出処理の流れである。
【００９３】
制御部１５０は、最適政策算出処理により算出された最適政策に関する情報を記憶部１４０に記憶させ、通信部１３０からユーザ端末２００の通信部２３０に送信させる。ユーザ端末２００は、最適政策に関する情報を通信部２３０に受信させ、表示部２２０に表示させる。
【００９４】
以上説明したように、実施の形態１に係る推薦装置１００は、ユーザの初期状態ｘ１とユーザのクラスの事前確率ｐ（ｗ１）と制御期間Ｔとに基づいて、当該制御期間Ｔにおける期待総利得を最大にする最適政策を算出する最適政策算出部１５１と、ユーザの状態ｘｔと時点ｔとが与えられると、当該時点ｔ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を決定する行動決定部１５２と、を備える。このため、ユーザのクラスの変化に対応して制御期間Ｔにおける期待総利得を最大にする最適政策を出力でき、ユーザのクラスの変化に応じて適切な商品を推薦できる。
【００９５】
（実施の形態２）
図９及び図１０を参照して、実施の形態２に係る推薦装置、推薦方法、及びプログラムを説明する。実施の形態１に係る推薦装置１００は、各種確率を支配する真のパラメータθ＊、φ＊が既知であると仮定していたが、実施の形態２に係る推薦装置１００は、履歴を含む学習系列に基づく半教師付き学習を実行することで各種確率を推定する。
【００９６】
図９は、実施の形態２に係る推薦装置１００の構成を示すブロック図である。記憶部１４０は、学習系列テーブル１４３をさらに備える。学習系列テーブル１４３は、ユーザのクラスが既知である完全データの学習系列と、ユーザのクラスが未知である不完全データの学習系列と、を記憶する。
【００９７】
制御部１５０は、機能的には、確率推定部１５３をさらに備える。確率推定部１５３は、完全データの学習系列と不完全データの学習系列とに基づいて半教師付き学習を実行することで各種確率を推定する。以下、確率推定部１５３がＥＭアルゴリズムを用いて半教師付き学習を実行する場合を例に説明する。
【００９８】
まず、完全データ及び不完全データの学習系列を説明する。データ数Ｌｃの完全データの学習系列Ｗ’Ｙ’Ｚ’は、
Ｗ’１Ｙ’１Ｚ’１Ｗ’２Ｙ’２Ｚ’２…Ｗ’ＬＣＹ’ ＬＣＺ’ ＬＣ
で表される。
【００９９】
Ｗ’ｉ、Ｙ’ ｉ、Ｚ’ ｉは、それぞれｉ本目の完全データにおけるユーザのクラス系列、推薦商品系列、ユーザの反応系列であり、すべて既知である。Ｗ’ｉＹ’ｉＺ’ｉは、以下の式で表される。
【０１００】
【数９】
2018190409.tif 000011
【０１０１】
ｗ’ｉ，ｊ、ｙ’ｉ，ｊ、ｚ’ｉ，ｊは、それぞれｉ本目の完全データにおけるｊ期目のユーザのクラス、推薦商品、反応を示し、Ｔ’ｉは、ｉ本目の完全データの推薦回数（ｉ本目の完全データの長さ）である。なお、ｙ’ｉ，０、ｚ’ｉ，０ は、１期目のＭＤＰの状態を構成するための情報（１期前の推薦と反応）であるため、推薦回数に含めない。
【０１０２】
他方、データ数Ｌｕの不完全データの学習系列ＹＺは、ユーザのクラスに関する系列を含まないため、
Ｙ１Ｚ１Ｙ２Ｚ２…ＹＬｃＺＬｃ
で表される。
【０１０３】
Ｙｉ、Ｚｉ は、それぞれｉ本目の不完全データにおける推薦商品系列、ユーザの反応系列であり、すべて既知である。ＹｉＺｉは、
ｙｉ，０ｚｉ，０ｙｉ，１ｚｉ，１…ｙｉ，Ｔｉｚｉ，Ｔｉ
と表される。
【０１０４】
ｙｉ，ｊ 、ｚｉ，ｊ は、それぞれｉ本目の不完全データにおけるｊ期目の推薦商品、反応を示し、Ｔｉ はｉ本目の不完全データの推薦回数（ｉ本目の不完全データの長さ）である。なお、ｙｉ，０、ｚｉ，０ は１期目のＭＤＰの状態を構成するための情報（１期前の推薦と反応）であるため、推薦回数には含めない。
【０１０５】
次に、不完全データに対してＥＭアルゴリズムを適用する手法を説明する。ＥＭアルゴリズムは、期待値ステップ（Ｅステップ）と最大化ステップ（Ｍステップ）を交互に繰り返すことで、確率モデルのパラメータを最尤推定する。Ｅステップでは、現在推定されている潜在変数の分布に基づいて、尤度の期待値を算出する。Ｍステップでは、Ｅステップで算出された尤度の期待値を最大化するパラメータを算出する。Ｍステップで算出されたパラメータは、次のＥステップで用いられる潜在変数の分布を決定するために用いられる。
【０１０６】
まず、ＥＭアルゴリズムの適用に必要な不完全データに対する各種確率の更新式を導出する。不完全データの生起確率ｐ（ＹＺ｜θ）は、以下のとおりである。ただし、Ｗ は、不完全データに対応する未知であるユーザのクラス系列である。
【０１０７】
【数１０】
2018190409.tif 000012
【数１１】
2018190409.tif 000013
【０１０８】
以下、各種確率の更新式の導出を容易にするために、各種記号の簡略化した書き方を定義する。ρｉは、ユーザのクラスの初期確率を示す。ａｉｊは、ユーザが所属するクラスが１期先に変化する確率であるユーザのクラスの遷移確率を示す。ｂｉｊｋｌｑは、１期前の推薦商品と反応がｍｊ，ｎｋでクラスｃｉの顧客が推薦商品ｍｌに対して反応がｎｑとなる確率であるユーザの状態遷移確率を示す。
【数１２】
2018190409.tif 000014
【数１３】
2018190409.tif 000015
【数１４】
2018190409.tif 000016
【０１０９】
また、ＥＭアルゴリズムの計算に必要な以下の確率を定義する。αｖ，ｔ（ｉ）βｖ，ｔ（ｉ）は、ｖ本目の不完全データの長さＴｖの推薦商品系列Ｙｖとユーザの反応系列Ｚｖが発生し、かつｔ期目のユーザのクラスｗｖ，ｔがｃｉである確率を示す。なお、αｖ，ｔ（ｉ）は、長さＴｖ中の１期目からｔ期目までの推薦商品系列ｙｖ，１…ｙｖ，ｔとユーザの反応系列ｚｖ，１…ｚｖ，ｔ及びｔ期目の顧客クラスｃｉが発生する確率であり、βｖ，ｔ（ｉ）は、ｔ期目の顧客クラスがｃｉという条件のもとで、ｔ＋１期目以降の推薦商品系列ｙｖ，ｔ＋１…ｙｖ，Ｔｖとユーザの反応系列ｚｖ，ｔ＋１…ｚｖ，Ｔｖが発生する確率である。
【数１５】
2018190409.tif 000017
【数１６】
2018190409.tif 000018
【数１７】
2018190409.tif 000019
【０１１０】
αｖ，ｔ（ｉ）及びβｖ，ｔ（ｉ）は、以下の式を用いて再帰的に計算される。αｖ，ｔ（ｉ）は、１期目から再帰的に計算され、βｖ，ｔ（ｉ）は、最後の期（Ｔｖ期目）から遡りながら再帰的に計算される。２≦ｔ≦Ｔｖの場合、αｖ，ｔ（ｉ）は、以下に示すように再帰的に計算できる。
【０１１１】
【数１８】
2018190409.tif 000020
【数１９】
2018190409.tif 000021
【数２０】
2018190409.tif 000022
【０１１２】
他方、１≦ｔ≦Ｔｖ−１の場合、βｖ，ｔ（ｉ）は、以下の式で表される。
【０１１３】
【数２１】
2018190409.tif 000023
【０１１４】
【数２２】
2018190409.tif 000024
【０１１５】
不完全データのｖ本目の推薦商品系列Ｙｖと顧客の反応系列Ｚｖとが得られた場合、ｔ期目のユーザのクラスｗｖ，ｔ がｃｉである確率は、以下の式で表される。
【０１１６】
【数２３】
2018190409.tif 000025
【０１１７】
不完全データのｖ本目の推薦商品系列Ｙｖと顧客の反応系列Ｚｖとが得られた場合、ｔ期目のユーザのクラスＷｖ，ｔがｃｉであって、ｔ＋１期目の顧客クラスｗｖ，ｔ＋１ がｃｊである確率は、以下の式で表される。
【０１１８】
【数２４】
2018190409.tif 000026
【０１１９】
次に、ＥＭアルゴリズムにおいて最大化するＱ（θ０，θ）関数を説明する。Ｑ（θ０，θ）は、ＥＭアルゴリズムの処理の導出を容易にする観点から、以下の式で表される。ただし、θはθ０の更新後のパラメータである。また、以下のρ、Ａ、Ｂは、それぞれρｉ、ａｉｊ、ｂｉｊｋｌｑを簡略的に表記したものである。
【０１２０】
【数２５】
2018190409.tif 000027
【０１２１】
関数Ｑ（θ０，ρ）、Ｑ（θ０，Ａ）、Ｑ（θ０，Ｂ）は、それぞれ以下の式で表される。
【０１２２】
【数２６】
2018190409.tif 000028
【数２７】
2018190409.tif 000029
【数２８】
2018190409.tif 000030
【０１２３】
次に、関数Ｑ（θ０，ρ）の最大化する確率ρｉの推定値を導出する。関数Ｑ（θ０，ρ）は、以下のように変形できる。
【０１２４】
【数２９】
2018190409.tif 000031
【数３０】
2018190409.tif 000032
【０１２５】
ρｉの総和（ｉ＝１〜｜ｃ｜）が１であるとの制約条件のもとで、ｆ＝Ｑ（θ０，ρ）を最大化する確率ρｉをラグランジュの未定乗数法によって求める。ラグランジュの未定乗数法より、
【０１２６】
【数３１】
2018190409.tif 000033
として、Ｌを確率ρｉで偏微分して０とおくと以下の式が得られる。
【０１２７】
【数３２】
2018190409.tif 000034
【数３３】
2018190409.tif 000035
【０１２８】
式（３３）の両辺をｉについて足し合わせて上記の制約を考慮すると、以下の式が得られる。
【０１２９】
【数３４】
2018190409.tif 000036
【０１３０】
よって、関数Ｑ（θ０，ρ）を最大化する確率ρｉの推定値ρ＾ｉは、以下の式で表される。
【０１３１】
【数３５】
2018190409.tif 000037
【０１３２】
関数Ｑ（θ０，Ａ）最大化する確率ａｉｊの推定値ａ＾ｉｊは、関数Ｑ（θ０，ρ）の場合と同様に、ｉ毎に関数Ｑ（θ０，Ａ）を最大化する確率ａｉｊをラグランジュの未定乗数法によって求めることで導出できる。確率の推定値ａ＾ｉｊは、以下の式で表される。
【０１３３】
【数３６】
2018190409.tif 000038
【数３７】
2018190409.tif 000039
【０１３４】
関数Ｑ（θ０，ρ）を最大化する確率ｂｉｊｋｌｑの推定値ｂ＾ｉｊｋｌｑは、関数Ｑ（θ０，ρ）の場合と同様に、ｉ，ｊ，ｋ，ｌの組み合わせ毎に関数Ｑ（θ０，Ｂ）を最大化する確率ｂｉｊｋｌｑをラグランジュの未定乗数法によって求めることで導出できる。確率の推定値ｂ＾ｉｊｋｌｑは、以下の式で表される。
【０１３５】
【数３８】
2018190409.tif 000040
【数３９】
2018190409.tif 000041
【数４０】
2018190409.tif 000042
【数４１】
2018190409.tif 000043
【０１３６】
次に、不完全データに対する各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの更新式である式（３５）、式（３６）、式（３８）を、完全データに対応するように拡張する。
【０１３７】
式（３５）の分子は、データ数Ｌｕの不完全データ系列において先頭のユーザのクラスがｃｉの頻度の期待値である。データ数Ｌｃの完全データでは、ユーザのクラスが既知であるため、完全データ中で先頭のユーザのクラスがｃｉである頻度をｇｉとすると、完全データを追加した場合の確率ρｉの推定値ρ＾ｉは、以下の式で表される。
【０１３８】
【数４２】
2018190409.tif 000044
【０１３９】
式（３６）の分子は、データ数Ｌｕの不完全データ系列においてユーザのクラスｃｉからｃｊへ遷移した頻度の期待値であり、式（３６）の分母は、遷移元がユーザのクラスｃｉの頻度の期待値である。完全データでは、ユーザのクラスは既知であるため、完全データ中でユーザのクラスｃｉからｃｊへ遷移した頻度をｇｉｊとすると、完全データを追加した場合の確率ａｉｊの推定値ａ＾ｉｊは、以下の式で表される。
【０１４０】
【数４３】
2018190409.tif 000045
【０１４１】
式（３８）の分子は、データ数Ｌｕの不完全データ系列においてユーザのクラスｃｉの顧客が１期前に商品ｍｊを推薦されて反応ｎｋを返し、当該期に商品ｍｌを推薦されて反応ｎｑを返す頻度の期待値である。式（３８）の分母は、クラスｃｉのユーザが１期前に商品ｍｊを推薦されて反応ｎｋを返し、当該期に商品ｍｌを推薦される頻度の期待値である。完全データでは、ユーザのクラスが既知であるため、完全データを追加した場合の確率ｂｉｊｋｌｑの推定値ｂ＾ｉｊｋｌｑは、以下の式で表される。ただし、ｇｉｊｋｌｑは、完全データ中でユーザのクラスｃｉの顧客が１期前に商品ｍｊを推薦されて反応ｎｋを返し、当該期に商品ｍｌを推薦されて反応ｎｑを返した頻度である。
【０１４２】
【数４４】
2018190409.tif 000046
【０１４３】
図１０を参照して、最適政策算出部１５１が最適政策算出処理を実行する前に、確率推定部１５３が実行する確率推定処理の流れを説明する。
【０１４４】
まず、確率推定部１５３は、各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの初期値を設定する（ステップＳ３０１）。各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの初期値は、例えば、一様乱数で与えられる。
【０１４５】
次に、確率推定部１５３は、式（４２）〜式（４４）を用いて各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑを推定して更新する（ステップＳ３０２）。式（４２）〜式（４４）の計算には、式（１８）〜式（２４）を用いる。
【０１４６】
次に、確率推定部１５３は、各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの全ての推定結果が収束しているかどうかを判定する（ステップＳ３０３）。各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの全ての推定結果が収束したかどうかは、例えば、各種確率の直近の差分が所定の閾値以下であるかどうかで判定する。各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの全ての推定結果が収束している場合（ステップＳ３０３；ＹＥＳ）、ステップＳ３０４に移動する。他方、各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑの全ての推定結果が収束していない場合（ステップＳ３０３；ＮＯ）、確率推定部１５３は、推定結果が収束するまで各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑを更新する処理（ステップＳ３０２）を繰り返す。
【０１４７】
ステップＳ３０３でＹＥＳの場合、確率推定部１５３は、収束した各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑを記憶部１４０（遷移確率テーブル１４１）に記憶させ（ステップＳ３０４）、処理を終了する。以上が、確率推定処理の流れである。
【０１４８】
その後、最適政策算出部１５１は、図１０の確率推定処理で推定された各種確率に基づいて図６の最適政策算出処理及び図８の行動決定処理を実行し、制御期間における最適政策を算出する。そして、制御部１５０は、最適政策算出部１５１により算出された最適政策に関する情報を出力する。
【０１４９】
以上説明したように、実施の形態２に係る推薦装置１００は、ユーザのクラスが既知である履歴情報とユーザのクラスが未知である履歴情報とに基づいて半教師付学習を実行することで各種確率を推定する確率推定部１５３を備える。このため、真のパラメータが未知の場合であっても、適切な商品を推薦できる。
【０１５０】
（実施の形態３）
図１１及び図１２を参照して、本発明の実施の形態３に係る推薦装置、推薦方法、及びプログラムを説明する。実施の形態３に係る推薦装置１００は、新規顧客であるユーザに対する質問と当該質問に対するユーザの回答とに基づいて、期待総利得を最大にする最適政策を算出する。
【０１５１】
図１１は、実施の形態３に係る制御部１５０の構成を示すブロック図である。最適政策算出部１５１は、ユーザの初期状態ｘ１、未知クラスの事前確率ｐ（ｗ）、質問回数Ｔ’及び推薦回数Ｔが与えられると、行動決定部１５２と連携して各時点ｔのユーザの各履歴ｘｔのもとでの各行動に対する期待利得を取得し、推薦期間における期待総利得を最大にする最適政策を算出する。
【０１５２】
行動決定部１５２は、ユーザに対する質問及び当該質問への回答並びにユーザへの推薦商品及び当該推薦商品への反応を含む履歴（状態）ｘｔと時点ｔが与えられると、当該時点ｔの当該履歴ｘｔのもとで、当該時点ｔ以降の期待総利得を最大にする最適行動（最適な質問及び最適な推薦商品）と期待総利得の最大値とを決定する。
【０１５３】
まず、推薦方法の数理モデルで使用する各種記号を説明する。以下、実施の形態３に係る推薦システムでは、新規ユーザに対してＴ’回の質問を行った後、Ｔ回の商品の推薦を行うため、Ｔ’＋Ｔ期間のＭＤＰ問題を扱うこととする。
【０１５４】
ｑｉ，ｑｉ∈Ｃは、新規ユーザに関する情報を入手するための質問を示し、Ｑ＝｛ｑ１、ｑ２，…，ｑ｜Ｑ｜｝は質問集合である。ａｉ，ａｉ∈Ａは、質問ｑｉに対する回答を示し、Ａ＝｛ａ１、ａ２，…，ａ｜Ａ｜｝は回答集合である。なお、質問ｑｉに対して利得ｒ（ｎｉ）は発生しないものとする。
【０１５５】
ｙｔは、ＭＤＰにおけるｔ期の行動を示す。行動ｙｔは、質問期間（１≦ｔ≦Ｔ’）の場合、ｔ回目の質問ｙｔ∈Ｑに相当し、推薦期間（Ｔ’＋１≦ｔ≦Ｔ’＋Ｔ）の場合、ｔ回目の商品の推薦ｙｔ∈Ｍに相当する。新規ユーザのアクセス時にＴ’回の質問と１回目の推薦ｙＴ’＋１を実施し、当該ユーザの２回目のアクセス時に２回目の推薦ｙＴ’＋２を実施する。
【０１５６】
ｚｔは、ＭＤＰにおける行動ｙｔに対するユーザの回答又は反応を示す。反応ｚｔは、質問期間（１≦ｔ≦Ｔ’）の場合、ｔ回目の質問ｙｔ∈Ｑに対する回答ｚｔ∈Ａに相当し、推薦期間（Ｔ’＋１≦ｔ≦Ｔ’＋Ｔ）の場合、ｔ回目の商品の推薦ｙｔ∈Ｍに対する反応ｚｔ∈Ｎに相当する。
【０１５７】
ｗ，ｗ∈Ｃ は、ＭＤＰにおける新規ユーザのクラスを示し、未知である。以下、理解を容易にするために、クラスの事前確率ｐ（ｗ）は、既知とし、ユーザのクラスは変化しないものとする。
【０１５８】
ｘｔは、ｔ回目（ｔ≧Ｔ’＋２）の推薦を受ける時点のユーザの状態で、ＭＤＰのｔ期の状態に相当する。状態ｘｔは、１期前の推薦商品とユーザの反応で構成されるため、ｘｔ＝（ｙｔ−１，ｚｔ−１）である。質問期間及び１回目の推薦の時点における状態ｘｔが未定義であるが、系列ｙｔ−１ｚｔ−１を計算に用いることでＤＰの問題を解くことができる。
【０１５９】
ｐ（ａｋ｜ｑｋ，ｃｊ，φ＊）は、クラスｃｊに属するユーザが質問ｑｋに対して回答ａｋを返す確率を示す。ｐ（ｐａｓｓ｜ε＊）は、質問期間において新規ユーザが質問に回答せずに推薦期間に移行する確率（質問回避確率）である。新規ユーザが実際に質問に回答するかどうかは不確実であるため、これらの確率を導入する。
【０１６０】
ｐ（ｎ０｜ｍｋ，ｎｊ，ｍｋ，ｃｌ，θ＊）は、クラスｃｌに属するユーザが１期前の推薦ｍｉ及び反応ｎｊのもとで、商品ｍｋを推薦されたときに反応ｎ０を返す確率を示す。確率ｐ（ｘｔ＋１｜ｘｔ，ｙｔ，ｗ，θ＊）は、ＭＤＰにおける状態遷移確率に相当し、以下の式で表される。ただし、ｔ≧Ｔ’＋２である。
【０１６１】
【数４５】
2018190409.tif 000047
【０１６２】
ｐ（ｎｋ｜ｍｉ，ｃｊ，θ＊）は、１回目の推薦（ｔ＝Ｔ’＋１）において、クラスｃｊに属するユーザが商品ｍｉを推薦されたときに反応ｎｋを返す確率である。確率ｐ（ｘｔ＋１｜ｙｔ，ｗ，θ＊）は、ＭＤＰにおける状態ｘＴ’＋２の生起確率に相当し、以下の式で表される。
【０１６３】
【数４６】
2018190409.tif 000048
【０１６４】
θ＊ 、ψ＊ 、ε＊ は、各種確率を支配する真のパラメータであり、既知であると仮定する。
【０１６５】
ｘＴ＋Ｔ’ Ｔ’＋２ｙＴ＋Ｔ’ ｚＴ＋Ｔ’は、推薦期間終了後の系列を示し、ｘＴ＋Ｔ’ Ｔ’＋２＝ｘＴ’＋２ｘＴ’＋３…ｘＴ＋Ｔ’、ｙＴ＋Ｔ’＝ｙ１…ｙＴ＋Ｔ’、ｚＴ＋Ｔ’＝ｚ１…ｚＴ＋Ｔ’である。質問期間の場合、状態ｘｔが未定義であるため、系列は、質問及び回答のみのｙｔｚｔになる。
【０１６６】
ｄ（・，・）は、期を示すｔと当該期までの系列とを受け取って当該期ｔの行動ｙｔを返す決定関数である。
【０１６７】
次に、統計的決定理論に基づいて数理モデルを定式化する。パラメータθ＊ 、ψ＊ 、ε＊のもとで、クラスｗに属する新規ユーザに対して決定関数ｄ（・，・）を使って、Ｔ’回の質問とＴ回の商品の推薦ｙＴ’＋Ｔを行って、新規ユーザの質問への回答と推薦への反応がｚＴ’＋Ｔだった場合の総利得を示す効用関数Ｕは、以下の式で表される。
【０１６８】
【数４７】
2018190409.tif 000049
【０１６９】
期待効用 はパラメータθ＊ 、ψ＊ 、ε＊のもとで、クラスｗに属する新規顧客に対して決定関数ｄ（・，・）を使って質問と商品の推薦を行う場合の総売上（総利得）の期待値を示す期待効用ＥＵは、効用関数Ｕを用いて以下の式で表される。
【０１７０】
【数４８】
2018190409.tif 000050
【０１７１】
新規ユーザのクラスｗは未知であるため、事前確率ｐ（ｗ）を導入する必要がある。式（４８）の期待効用ＥＵに事前確率ｐ（ｗ）を導入したベイズ期待効用ＢＥＵは、以下の式で表される。
【０１７２】
【数４９】
2018190409.tif 000051
【０１７３】
式（４９）のベイズ期待効用ＢＥＵを最大にする決定関数ｄ（・，・）は、ベイズ基準のもとで総売上を最大にする最適な質問及び推薦方法に相当し、以下の式で表される。
【０１７４】
【数５０】
2018190409.tif 000052
【０１７５】
式（４９）のベイズ期待効用ＢＥＵを書き下すと、Ｔ’＋Ｔ期間の入れ子構造になる。このため、最適政策算出部１５１は、当該入れ子構造にＤＰを適用してＤＰの木を作成することで、各時点における最適な質問及び推薦商品を含む最適政策を算出できる。
【０１７６】
次に、ＤＰの問題を解くために用いる事後確率を算出する方法を説明する。事後確率は、データを考慮に入れた条件での変数の条件付確率であり、ベイズの定理により事前確率に尤度関数の出力値を乗算することで導出できる。ｔ期（１≦ｔ≦Ｔ’＋１）に使用する事後確率ｐ（ｗ｜ｙｔ−１ｚｔ−１）は、以下の式で表される。ただし、ｐ（ｗ｜ｙ０ｚ０）＝ｐ（ｗ）である。
【０１７７】
【数５１】
2018190409.tif 000053
【０１７８】
質問期間のｔ期（１≦ｔ≦Ｔ） にユーザが質問を回避して推薦期間に進んだ場合には、推薦期間の最初の期である期で使用する事後確率は、ｐ（ｗ｜ｙＴ’ｚＴ’）＝ｐ（ｗ｜ｙｔ−１ｚｔ−１）とする。
【０１７９】
ｔ期（ｔ＝Ｔ’＋２）に使用する事後確率ｐ（ｗ｜ｘｔＴ’＋２ｙｔ−１ｚｔ−１）は、以下の式で表される。
【０１８０】
【数５２】
2018190409.tif 000054
【０１８１】
ｔ期（Ｔ’＋３≦ｔ≦Ｔ’＋Ｔ）に使用する事後確率ｐ（ｗ｜ｘｔＴ’＋２ｙｔ−１ｚｔ−１）は、以下の式で表される。ただし、ｐ（ｚｔ−１｜ｘｔ−１，ｙｔ−１，ｗ，θ＊）＝ｐ（ｚｔ−１｜ｙｔ−２，ｚｔ−２，ｙｔ−１，ｗ，θ＊）である。
【０１８２】
【数５３】
2018190409.tif 000055
【０１８３】
次に、行動決定部１５２が指定されたノード以降の期待総利得の最大値を算出する方法を説明する。Ｔ’＋Ｔ 期目のすべての遷移系列 に対して、以下の式（５４）の右辺を最大化する行動ｙＴ’＋Ｔをベイズ最適な最後の推薦商品として決定する。Ｖ（ｘＴ’＋ＴＴ’＋２ｙＴ’＋Ｔ−１ｚＴ’＋Ｔ−１，Ｔ’＋Ｔ）は、最後の期の期待利得の最大値であり、ｐ（ｚＴ’＋Ｔ｜ｘＴ’＋ＴＴ’＋２ｙＴ’＋Ｔ−１ｚＴ’＋Ｔ−１，ｙＴ’＋Ｔ，θ＊）は、ユーザの反応確率の事後確率ｐ（ｗ｜ｘＴ’＋ＴＴ’＋２ｙＴ’＋Ｔ−１ｚＴ’＋Ｔ−１）による期待値である。
【０１８４】
【数５４】
2018190409.tif 000056
【数５５】
2018190409.tif 000057
【０１８５】
ｔ期目（Ｔ’＋２≦ｔ≦Ｔ’＋Ｔ−１）のすべての遷移系列 に対して、以下の式（５６）の右辺を最大化する行動ｙＴ’＋Ｔをベイズ最適なｔ期の推薦商品として決定する。Ｖ（ｘｔＴ’＋２ｙｔ−１ｚｔ−１，ｔ）は、ｔ期以降の期待利得の最大値である。
【０１８６】
【数５６】
2018190409.tif 000058
【数５７】
2018190409.tif 000059
【０１８７】
ｔ期目（ｔ＝Ｔ’＋１）のすべての遷移系列ｙｔ−１ｚｔ−１に対して、式（５８）の右辺を最大化する行動 をベイズ最適なｔ期の推薦商品として決定する。Ｖ（ｙｔ−１ｚｔ−１，ｔ）は、ｔ期以降の期待利得の最大値である。
【０１８８】
【数５８】
2018190409.tif 000060
【数５９】
2018190409.tif 000061
【０１８９】
ｔ期目（１≦ｔ≦Ｔ’）のすべての遷移系列 ｙｔ−１ｚｔ−１に対して、式（６０）の右辺を最大化する行動ｙｔをベイズ最適なｔ期の質問として決定する。Ｖ（ｙｔ−１ｚｔ−１，ｔ）はＴ＋１期以降の期待総利得の最大値である。なお、式（６０）では、質問回避確率ｐ（ｐａｓｓ｜ε＊）を導入することで、新規ユーザが質問に回答せずに推薦期間に移行する場合を考慮している。また、Ｑ−ｙｔ−１は未実施の質問集合である。
【０１９０】
【数６０】
2018190409.tif 000062
【数６１】
2018190409.tif 000063
【０１９１】
以下、図６を参照して、最適政策算出部１５１が実行する最適政策算出処理の流れを説明する。まず、最適政策算出部１５１は、記憶部１４０から、ユーザの初期状態、未知クラスの事前確率、質問回数及び推薦回数を取得する（ステップＳ１０１）。
【０１９２】
次に、ＤＰ木作成部１５１ａは、推薦期間の期待総利得を最大化するためのＤＰ問題を解くためのＤＰ木を作成する（ステップＳ１０２）。ＤＰ木作成部１５１ａは、例えば、図１２に示すようなＤＰ木を作成する。ＤＰ木の１期目はユーザの初期状態、２期目からＴ’＋１期目までは想定される質問及び回答のすべての履歴（系列）、Ｔ’＋２期目からＴ’＋Ｔ期目までは想定される質問及び回答並びに推薦商品及び反応のすべての履歴（系列）で表現される。初期の履歴に相当する初期状態は、新規ユーザが推薦対象であるため、空列である。なお、図１２では、理解を容易にするために、１期前の推薦と反応で表現される各ノードの状態を省略している。
【０１９３】
次に、ＤＰ実施部１５１ｂは、行動決定部１５２に図８の行動決定処理を実行させ、末端のＴ’＋Ｔ期目のノードから遡りながらＤＰでＴ’＋Ｔ期間のＭＤＰを解くことによって、各ノードにおける推薦期間の期待総利得を最大化するのに最適な行動と当該ノード以降の期待総利得の最大値とを決定する（ステップＳ１０３）。より詳細に説明すると、ＤＰ実施部１５１ｂは、ＤＰ木の末端の各ノードから順に、当該ノードの時点とユーザの履歴（履歴を表現する系列）を行動決定部１５２に提供する。そして、ＤＰ実施部１５１ｂは、行動決定部１５２から当該ノードにおける最適行動と当該ノード以降の期待総利得の最大値とを取得する。行動は、質問期間において質問の選択であり、推薦期間において推薦商品の選択である。
【０１９４】
次に、ＤＰの問題をＤＰ木の末端のＴ’＋Ｔ期目のノードから１時点目のノードまで全て解き終わったかどうかを判定する（ステップＳ１０４）。ステップＳ１０４でＹＥＳの場合、最適政策算出部１５１は、ＤＰ木の全ノードにおける最適行動と当該ノード以降の期待総利得の最大値とを最適政策として出力する（ステップＳ１０５）。以上が、最適政策算出処理の流れである。
【０１９５】
以上説明したように、実施の形態３に係る推薦装置は、ユーザの初期状態とクラスの事前確率と質問回数と推薦回数とが与えられると、当該制御期間における期待総利得を最大にする最適政策を算出する最適政策算出部１５１と、ユーザに対する質問と当該質問へのユーザの回答、ユーザに対する推薦と当該推薦へのユーザの反応を含む履歴と時点とが与えられると、当該時点以降の期待総利得を最大にする最適行動と期待総利得の最大値とを決定する行動決定部１５２と、を備える。このため、新規顧客のようにユーザのクラスが未知の場合であっても、ユーザに対する質問と当該質問へのユーザの回答を得ることで、期待総利得を最大にする最適政策を算出できる。
【０１９６】
（実施の形態４）
実施の形態４に係る推薦装置、推薦方法、及びプログラムを説明する。実施の形態３に係る推薦装置は、ユーザのクラスが変化せず、各種確率を支配する真のパラメータθ＊、φ＊、ε＊が既知であると仮定していたが、実施の形態４に係る推薦装置は、実施の形態２、３に係る推薦装置を組み合わせて、ユーザのクラスが変化し、真のパラメータが未知の場合であっても、半教師付学習を実行することで真のパラメータを推定する。
【０１９７】
以下、理解を容易にするために、質問回避確率ｐ（ｐａｓｓ｜ε＊）がゼロ（既知）であり、その他の確率が未知である場合を例に説明するが、質問回避確率（ｐａｓｓ｜ε＊）が未知の場合でも半教師付学習を実行することで真のパラメータを推定できる。
【０１９８】
確率推定部１５３は、ユーザに対する質問と当該質問へのユーザの回答を含んでおり、ユーザのクラスが既知である完全データとユーザのクラスが未知である不完全データを有する学習系列に基づいて、ＥＭアルゴリズムを適用することで半教師付学習を実行して各種確率を推定する。
【０１９９】
実施の形態２の場合と同様に、不完全データにＥＭアルゴリズムを適用する場合のパラメータの更新式を導出し、当該更新式を完全データに対応するように拡張することで、確率推定部１５３が用いるＥＭアルゴリズムのＱ関数を最大化する以下の更新式が得られる。以下の更新式は、実施の形態２と同様の手順で導出できるため、具体的な導出方法については説明を省略する。
【０２００】
ｐ（ｃｊ｜θ）は、ユーザクラスの生起確率を示す。ｐ（ｃｊ｜θ）の推定値ｐ＾（ｃｊ｜θ）は、以下の式で表される。ただし、Ｈ’（ｃｊ）は、完全データ中でユーザのクラスがｃｊである頻度を示す。
【０２０１】
【数６２】
2018190409.tif 000064
【０２０２】
ｐ（ａｋ３｜ｑｋ２，ｃｋ１，θ）は、クラスｃｋｌに属する顧客が質問ｑｋ２に対して回答ａｋ３を返す確率を示す。ｐ（ａｋ３｜ｑｋ２，ｃｋ１，θ）の推定値ｐ＾（ａｋ３｜ｑｋ２，ｃｋ１，θ）は、以下の式で表される。ただし、Ｈ’（ｃｋ１，ｑｋ２，ａｋ３）は、完全データ中でクラスがｃｋ１であるユーザが質問ｑｋ２を質問され、回答ａｋ３を返した頻度を示す。また、Ｈ’（ｃｋ１，ｑｋ２）は、完全データ中でクラスｃｋ１のユーザが質問ｑｋ２を質問される頻度を示す。
【数６３】
2018190409.tif 000065
【０２０３】
ｐ（ｎｋ３｜ｍｋ２，ｃｋ１，θ）は、１回目の推薦（ｔ＝Ｔ’＋１）において，クラスｃｋｌに属するユーザが商品ｍｋ２を推薦されたときに反応ｎｋ３を返す確率である。ｐ（ｎｋ３｜ｍｋ２，ｃｋ１，θ）の推定値ｐ＾（ｎｋ３｜ｍｋ２，ｃｋ１，θ）は、以下の式で表される。ただし、Ｈ’（ｃｋ１，ｍｋ２，ｎｋ３）は、完全データ中でクラスがｃｋ１であるユーザが１回目の推薦で商品ｍｋ２を推薦され、反応ｎｋ３を返した頻度を示す。また、Ｈ’（ｃｋ１，ｍｋ２）は、完全データ中でクラスｃｋ１のユーザが１回目の推薦で商品ｍｋ２を推薦される頻度を示す。
【０２０４】
【数６４】
2018190409.tif 000066
【０２０５】
ｐ（ｎｋ５｜ｍｋ２，ｎｋ３，ｍｋ４，ｃｋ１，θ）は、２回目以降の推薦（ｔ≧Ｔ’＋２）において、クラスｃｋｌに属する顧客が１期前の推薦と反応がｍｋ２とｎｋ３のもとで商品ｍｋ４を推薦されたときに反応ｎｋ５を返す確率を示す。ｐ（ｎｋ５｜ｍｋ２，ｎｋ３，ｍｋ４，ｃｋ１，θ）の推定値ｐ＾（ｎｋ５｜ｍｋ２，ｎｋ３，ｍｋ４，ｃｋ１，θ）は、以下の式で表される。ただし、Ｈ’ （ｃｋ１，ｍｋ２，ｎｋ３，ｍｋ４，ｎｋ５）は、完全データ中でクラスがｃｋ１であるユーザが、２回目以降の推薦で１期前の推薦と反応がｍｋ２とｎｋ３という状況で、商品ｍｋ４を推薦されて反応ｎｋ５を返した頻度を示す。また、Ｈ’ （ｃｋ１，ｍｋ２，ｎｋ３，ｍｋ４）は、完全データ中でクラスがｃｋ１であるユーザが、２回目以降の推薦で１期前の推薦と反応がｍｋ２とｎｋ３という状況で、商品ｍｋ４を推薦された頻度を示す。
【０２０６】
【数６５】
2018190409.tif 000067
【０２０７】
図１０を参照して、ＥＭアルゴリズムを用いた確率推定処理の流れを説明する。まず、確率推定部１５３は、各種確率ｐ＾（ｃｊ｜θ）、ｐ＾（ａｋ｜ｑｋ２，ｃｋ１，θ）、ｐ（ｎｋ３｜ｍｋ２，ｃｋ１，θ）、ｐ＾（ｎｋ５｜ｍｋ２，ｎｋ３，ｍｋ４，ｃｋ１，θ）の初期値を設定する（ステップＳ３０１）。
【０２０８】
次に、確率推定部１５３は、式（６２）〜式（６５）を用いて各種確率ｐ＾（ｃｊ｜θ）、ｐ＾（ａｋ｜ｑｋ２，ｃｋ１，θ）、ｐ（ｎｋ３｜ｍｋ２，ｃｋ１，θ）、ｐ＾（ｎｋ５｜ｍｋ２，ｎｋ３，ｍｋ４，ｃｋ１，θ）が収束するまで更新を繰り返す（ステップＳ３０２、ステップＳ３０３）。各種確率を更新するには、事後確率の更新式である以下の式（６７）〜式（７１）を用いればよい。質問期間（１≦ｋ≦Ｔ’ｉ）の場合、事後確率の更新式は、以下の式で表される。
【０２０９】
【数６６】
2018190409.tif 000068
【数６７】
2018190409.tif 000069
【数６８】
2018190409.tif 000070
【数６９】
2018190409.tif 000071
【０２１０】
１回目の推薦（ｋ＝Ｔ’ｉ＋１）の場合、事後確率の更新式は、以下の式で表される。
【０２１１】
【数７０】
2018190409.tif 000072
【０２１２】
２回目以降の推薦（Ｔ’ｉ＋２≦ｋ≦Ｔ’ｉ＋Ｔｉ）の場合、事後確率の更新式は、以下の式で表される。
【０２１３】
【数７１】
2018190409.tif 000073
【０２１４】
ステップＳ３０３でＹＥＳの場合、確率推定部１５３は、推定された各種確率を記憶部１４０（遷移確率テーブル１４１）に記憶させ（ステップＳ３０４）、処理を終了する。以上が、確率推定処理の流れである。
【０２１５】
以上説明したように、実施の形態４に係る推薦装置１００は、ユーザに対する質問と当該質問へのユーザの回答を含み、ユーザのクラスが既知である完全データとユーザのクラスが未知である不完全データを有する学習系列に基づいて、半教師付学習を実行することで各種確率を推定する確率推定部１５３を備える。このため、真のパラメータが未知の場合であっても、適切な商品を推薦できる。
【０２１６】
以下、実施例を挙げて本発明を具体的に説明する。ただし、本発明はこれらの実施例に限定されるものではない。
【０２１７】
（実施例１）
実施例１では、実施の形態１に係る推薦装置１００の有効性を検証するために数値計算を実施した。ユーザのクラス数｜Ｃ｜＝３、商品数｜Ｍ｜＝８、推薦回数Ｔ= ４とし、クラスの事前確率ｐ（ｗ１）は等確率とした。ユーザの反応確率ｐ（ｚＴ｜ｙＴ−１，ｚＴ−１，ｙＴ，ｗＴ，θ＊）及びクラスの遷移確率ｐ（ｗＴ＋１｜ｗＴ，ψ＊）を支配する真のパラメータθ＊、ψ＊は、一様乱数に従って設定し、商品の利得ｒ（ｎｉ）は、１０以上１００以下の一様乱数で設定した。
【０２１８】
本実施例では、上記の設定のもとで期待総利得の最大値を算出した。空列を含む｛Ｍ（Ｍ＋１）＋１｝個の初期状態ｘ１の各候補に対するＴ回の推薦での期待総利得の最大値の算出を、上記の一様乱数による設定で５００パターンに対して行った。履歴のあるユーザの初期状態の候補数は、Ｍ（Ｍ＋１）個であり、履歴のない新規ユーザの初期状態の候補数は、１個である。また、比較例として、クラス遷移を無視した場合の最適な推薦における期待総利得の最大値も算出した。
【０２１９】
数値計算の結果、実施の形態１に係る推薦装置１００を用いた場合、期待総利得の最大値の平均値は２６４．２１であった。また、クラス遷移を無視した場合、期待総利得の最大値の平均値は２５４．３３であった。このことは、ユーザのクラスが時間経過に伴い変化することが想定される場合、クラス遷移を考慮することで期待総利得の最大値が増加することを示している。したがって、実施の形態１に係る推薦装置１００を商品又はサービスの推薦、例えば、インターネット上の通販サイトを構成する情報システムに適用した場合、商品又はサービスの売上高の増加を実現できる。
【０２２０】
（実施例２）
実施例２では、実施の形態２に係る推薦装置の有効性を検証するために、以下の数値計算を実施した。ユーザのクラス数｜Ｃ｜＝３、商品数｜Ｍ｜＝４、推薦回数Ｔ= ４とし、各種確率ρｉ、ａｉｊ、ｂｉｊｋｌｑと商品の利得ｒ（ｎｉ）を一様乱数によって２００ パターンで設定した。商品の利得ｒ（ｎｉ）は、１００〜１０００の範囲、１００きざみで設定した。ＥＭ アルゴリズムの初期値は、一様乱数で設定し、ＥＭアルゴリズムの繰り返し回数は、１０００とした。
【０２２１】
学習データの完全データ数Ｌｃ及び不完全データ数Ｌｕは、それぞれ１０、１００、１０００とし、データ数の組み合わせを９組に設定した。学習データの系列長は、推薦回数Ｔ＝４と同じとした。学習データは、各シミュレーションパターンの真のパラメータに従って生成した。完全データＷ’Ｙ’Ｚ’、不完全データＹＺ及び０期の推薦商品とユーザの反応は、一様乱数で生成した。比較例として、真のパラメータが既知の場合の数値計算も実行した。この比較例のクラス事前確率としてはρｉを用いた。
【０２２２】
図１３は、実施例２における数値計算結果を示す。図１３の数値は、真のパラメータ既知の場合の総利得に対する、実施の形態２に係る推薦方法による総利得の割合（達成率）である。なお、各数値は、ＭＤＰの試行を１０００回実施した結果を平均したものである。本検証により、完全データが少量の場合でも不完全データが増加すれば総利得が大きくなることが確認できた。また、学習データの増加に伴い総利得も増加するため、十分なデータ数があれば真のパラメータが既知の場合と同等の利得を得られることも確認できた。
【０２２３】
（実施例３）
実施の形態３に係る推薦装置の有効性を検証するために、以下の数値計算を実施した。ユーザのクラス数｜Ｃ｜＝２、商品数｜Ｍ｜＝２、質問回数Ｔ’＝１、推薦回数Ｔ＝３、質問数｜Ｑ｜＝２、回答数｜Ａ｜＝２、質問の回避確率ｐ（ｐａｓｓ｜ε＊）＝０．２とし、クラスの事前確率ｐ（ｗ）は、等確率とした。また、商品推薦に対するユーザの反応確率ｐ（ｎ０｜ｍｉ，ｎｊ，ｍｋ，ｃｌ，θ＊）、ｐ（ｎｋ｜ｍｉ，ｃｊ，θ＊）、質問回答確率ｐ（ａｋ｜ｑｋ，ｃｊ，φ＊）は、それぞれ図１４（ａ）〜図１４（ｃ）に示すとおりに設定した。比較例として、質問を用いない場合、質問選択にエントロピー関数を利用する場合の数値計算も実行した。
【０２２４】
数値計算の結果、実施の形態３に係る推薦方法の期待総利得は、１８５，３９５であり、質問を用いない場合の期待総利得は、１７１，１２５であり、質問選択にエントロピー関数を利用する場合の期待総利得は、１７１，２２５であった。以上より、小規模な数値計算例であるが、売上高の最大化を目的とする質問選択の有効性を確認できた。
【０２２５】
（実施例４）
実施例４では、実施の形態４に係る推薦装置の有効性を検証するために、以下の数値計算を実施した。ユーザのクラス数｜Ｃ｜＝４、質問数｜Ｑ｜＝３、回答数｜Ａ｜＝２、商品数｜Ｍ｜＝５、質問回数Ｔ’＝２、推薦回数Ｔ＝４とした。また、真のパラメータ及び商品の利得ｒ（ｎｉ）は、一様乱数で１００パターン設定した。商品の利得ｒ（ｎｉ）は、１０〜１００の範囲内で１０きざみに設定した。
【０２２６】
ＥＭアルゴリズムの初期値は、一様乱数で設定し、ＥＭアルゴリズムの繰り返し回数は、収束を考慮して１０００とした。完全データＷ’Ｙ’Ｚ’のデータ数Ｌｃ及び不完全データＹＺのデータ数Ｌｕは、それぞれ１０、１００、１０００、１００００とし、データ数の組み合わせを１６組に設定した。学習データの系列長は、質問回数Ｔ’=２、推薦回数Ｔ=４と同じにした。学習データは、各シミュレーションパターンの真のパラメータに従って生成した。また、比較例として、ユーザのクラスの生起確率をクラスの事前確率とし、真のパラメータが既知である場合の数値計算も実行した。
【０２２７】
図１５は、実施例４における数値計算結果を示す。図１５の数値は、真のパラメータ既知の場合の期待総利得の最大値に対する、実施の形態４に係る推薦方法で得られた期待総利得の割合（達成率）である。完全データ数が少量の１０の場合でも、不完全データ数の増加に伴い達成率が８８．５０％（不完全データ数１０）から９４．９８％（不完全データ数１００００）まで増加した。また、学習データ全体が増加するにつれて達成率が増加する傾向を確認できた。完全データ数Ｌｃと不完全データ数Ｌｕとがいずれも１００００の場合、９８．８５％という高い達成率が得られた。
【０２２８】
そして、本発明はこれに限られず、以下に述べる変形も可能である。
【０２２９】
（変形例）
上記実施の形態では、推薦装置１００とユーザ端末２００とは個別の装置として構成されているが、本発明はこれに限られない。推薦装置１００とユーザ端末２００とは、一体に構成されてもよく、同じコンピュータ上に構成されていてもよい。
【０２３０】
上記実施の形態では、推薦装置１００はリクエストされたＷｅｂページに関する情報を記憶部１４０から読み取り、ユーザ端末２００に送信していたが、本発明はこれに限られない。例えば、Ｗｅｂページに関する情報を記憶し、リクエストに応じてＷｅｂページに関する情報を推薦装置１００又はユーザ端末２００に送信するＷｅｂサーバを、推薦装置１００と別体に設けてもよい。
【０２３１】
上記実施の形態では、各種データは記憶部１４０に記憶されていたが、本発明はこれに限定されない。例えば、各種データは、その全部又は一部がＬＡＮ（Local Area Network）等を介して外部のサーバ、コンピュータ等に記憶されてもよい。また、各種データを複数の場所、例えば、複数のコンピュータから構成されるクラウドシステム上に分散配置してもよい。
【０２３２】
上記実施の形態では、制御部１５０は記憶部１４０に記憶されたプログラムに基づいて動作していたが、本発明はこれに限定されない。例えば、プログラムにより実現された機能的な構成をハードウェアにより実現してもよい。
【０２３３】
上記実施の形態では、推薦対象が商品、ユーザのクラスがユーザの嗜好や趣味、利得が商品の販売価格であったが、本発明はこれに限られない。例えば、推薦対象を治療法及び医薬品、患者のクラスを患者の健康状態、利得を患者の健康状態に依存する血圧、血糖値等に関連する指標であるとして、患者の健康状態の向上を図るために推薦システム１を適用してもよい。
【０２３４】
上記実施の形態では、マルコフ連鎖によりユーザのクラスの変化を表現してＭＤＰ問題を解いていたが、本発明はこれに限られない。ユーザのクラスの変化を表現可能な数理モデルであれば、いかなる数理モデルを採用してもよい。
【０２３５】
上記実施の形態では、ＤＰを用いてＭＤＰ問題を解いていたが、本発明はこれに限られない。例えば、ＤＰを用いずに想定される政策を全て列挙し、各政策における期待総利得を算出し、期待総利得が最大の政策を最適政策として出力してもよい。
【０２３６】
上記実施の形態は例示であり、本発明はこれらに限定されるものではなく、特許請求の範囲に記載した発明の趣旨を逸脱しない範囲でさまざまな実施の形態が可能である。各実施の形態や変形例で記載した構成要素は自由に組み合わせることが可能である。また、特許請求の範囲に記載した発明と均等な発明も本発明に含まれる。
【符号の説明】
【０２３７】
１        推薦システム
１００    推薦装置
１１０    指示受付部
１２０    表示部
１３０    通信部
１４０    記憶部
１４１    遷移確率テーブル
１４２    利得テーブル
１４３    学習系列テーブル
１５０    制御部
１５１    最適政策算出部
１５１ａ  ＤＰ木作成部
１５１ｂ  ＤＰ実施部
１５２    行動決定部
１５３    確率推定部
２００    ユーザ端末
２１０    指示受付部
２２０    表示部
２３０    通信部
２４０    記憶部
２５０    制御部
【図１】
2018190409.tif 000074
【図２】
2018190409.tif 000075
【図３】
2018190409.tif 000076
【図４】
2018190409.tif 000077
【図５】
2018190409.tif 000078
【図６】
2018190409.tif 000079
【図７】
2018190409.tif 000080
【図８】
2018190409.tif 000081
【図９】
2018190409.tif 000082
【図１０】
2018190409.tif 000083
【図１１】
2018190409.tif 000084
【図１２】
2018190409.tif 000085
【図１３】
2018190409.tif 000086
【図１４】
2018190409.tif 000087
【図１５】
2018190409.tif 000088