(57)【要約】【課題】バンディットアルゴリズムにおけるリグレットを低減する。【解決手段】選択システム（１）の取得手段（１０１）は、所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の確率に関する確率情報を取得する。選択手段（１０２）は、各選択肢の確率情報に基づいて、所定の基準で選択肢を選択する。選択手段（１０２）は、当該選択肢だけではなく、所定の基準では選択されない選択肢も選択する。更新手段（１０３）は、選択手段（１０２）が選択した各選択肢により得られた事象に基づいて、確率情報を更新する。【選択図】図９
2020009283.tif 000002
【特許請求の範囲】
【請求項１】
所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の前記確率に関する確率情報を取得する取得手段と、
各選択肢の前記確率情報に基づいて、所定の基準で選択肢を選択する手段であって、当該選択肢だけではなく、前記所定の基準では選択されない選択肢も選択する選択手段と、
前記選択手段が選択した各選択肢により得られた事象に基づいて、前記確率情報を更新する更新手段と、
を含むことを特徴とする選択システム。
【請求項２】
前記選択手段は、前記所定の基準で選択する選択肢の割合を、前記所定の基準では選択されない選択肢の割合よりも多くする、
ことを特徴とする請求項１に記載の選択システム。
【請求項３】
前記確率情報は、前記確率を示す確率分布であり、
前記選択手段は、各選択肢の前記確率分布に基づいて、前記所定の基準で選択肢を選択する、
ことを特徴とする請求項１又は２に記載の選択システム。
【請求項４】
前記確率分布は、ベータ分布であり、
前記所定の基準は、トンプソンサンプリング法における基準であり、
前記選択手段は、各選択肢のベータ分布に基づいて、トンプソンサンプリング法で選択肢を選択し、当該選択肢だけではなく、トンプソンサンプリング法では選択されない選択肢も選択する、
ことを特徴とする請求項３に記載の選択システム。
【請求項５】
前記選択手段は、所定のパラメータに応じた割合で、前記所定の基準では選択されない選択肢を選択する、
ことを特徴とする請求項１〜４の何れかに記載の選択システム。
【請求項６】
前記選択手段は、各選択肢により得られた事象の時系列的な変化に基づいて、前記所定の基準では選択されない選択肢を選択する割合を決定する、
ことを特徴とする請求項１〜５の何れかに記載の選択システム。
【請求項７】
前記更新手段は、各選択肢により得られた事象のうち、新しい事象ほど重み付けを高くして、前記確率情報を更新する、
ことを特徴とする請求項１〜６の何れかに記載の選択システム。
【請求項８】
前記更新手段は、各選択肢により得られた事象のうち、直近の一部の期間における事象に基づいて、前記確率情報を更新する、
ことを特徴とする請求項１〜７の何れかに記載の選択システム。
【請求項９】
各選択肢は、複数のユーザの各々に提示されるコンテンツであって、
前記所定の事象は、前記コンテンツが提示されたユーザが当該コンテンツを選択することであり、
前記更新手段は、前記選択手段が選択した各コンテンツが提示されたユーザの行動に基づいて、前記確率情報を更新する、
ことを特徴とする請求項１〜８の何れかに記載の選択システム。
【請求項１０】
所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の前記確率に関する確率情報を取得する取得ステップと、
各選択肢の前記確率情報に基づいて、所定の基準で選択肢を選択するステップであって、当該選択肢だけではなく、前記所定の基準では選択されない選択肢も選択する選択ステップと、
前記選択ステップが選択した各選択肢により得られた事象に基づいて、前記確率情報を更新する更新ステップと、
を含むことを特徴とする選択方法。
【請求項１１】
所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の前記確率に関する確率情報を取得する取得手段、
各選択肢の前記確率情報に基づいて、所定の基準で選択肢を選択する手段であって、当該選択肢だけではなく、前記所定の基準では選択されない選択肢も選択する選択手段、
前記選択手段が選択した各選択肢により得られた事象に基づいて、前記確率情報を更新する更新手段、
としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、選択システム、選択方法、及びプログラムに関する。
【背景技術】
【０００２】
従来、複数の選択肢の中から、所定の事象を得る確率が高い又は低い選択肢を選択する技術が知られている。例えば、特許文献１には、複数の広告（選択肢の一例）の中からクリック率（所定の事象を得る確率の一例）が高い広告を選択する技術において、クリック率の高い広告を特定する探求と、探求結果を利用して広告を選択する活用と、を行うバンディットアルゴリズムが記載されている。また例えば、非特許文献１には、バンディットアルゴリズムの一例として、確率分布の一例であるベータ分布を利用して選択肢を選択するトンプソンサンプリング法が記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１６−１２２２４１号公報
【非特許文献】
【０００４】
【非特許文献１】Analysis of Thompson Sampling for the Multi-armed Bandit Problem、http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００５】
所定の事象を得る確率は、固定値ではなく、時間経過に応じて変化することがある。例えば、特許文献１において、広告Ｘは、最初はクリック率が非常に高いが、時間経過に応じて徐々にクリック率が低くなり、広告Ｙは、最初はクリック率が非常に低いが、時間経過に応じて徐々にクリック率が高くなる、といった事象が発生する。
【０００６】
例えば、非特許文献１のトンプソンサンプリングによれば、序盤の探求によって、クリック率が非常に高いことを示す広告Ｘのベータ分布と、クリック率が非常に低いことを示す広告Ｙのベータ分布と、が取得される。このため、序盤のうちは、広告Ｘが１００％選択され、広告Ｙは全く選択されない状態となる。その後、時間経過に応じて広告Ｘのクリック率が徐々に下がるので、広告Ｘのベータ分布は、広告Ｙのベータ分布に徐々に近づいていく。
【０００７】
一方、広告Ｙは全く選択されず、ベータ分布が変化しないので、広告Ｙの実際のクリック率が広告Ｘを超えたとしても、ベータ分布上は、その事実を特定することができず、広告Ｙは選択されない。広告Ｙは、広告Ｘのベータ分布が同程度まで落ち込んだ場合にようやく選択され始めるので、広告Ｙの実際のクリック率が広告Ｘを超えたことを特定するのが遅れてしまい、多くのリグレットが発生する。
【０００８】
本発明は上記課題に鑑みてなされたものであって、その目的は、バンディットアルゴリズムにおけるリグレットを低減することが可能な選択システム、選択方法、及びプログラムを提供することである。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明に係る選択システムは、所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の前記確率に関する確率情報を取得する取得手段と、各選択肢の前記確率情報に基づいて、所定の基準で選択肢を選択する手段であって、当該選択肢だけではなく、前記所定の基準では選択されない選択肢も選択する選択手段と、前記選択手段が選択した各選択肢により得られた事象に基づいて、前記確率情報を更新する更新手段と、を含むことを特徴とする。
【００１０】
本発明に係る選択方法は、所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の前記確率に関する確率情報を取得する取得ステップと、各選択肢の前記確率情報に基づいて、所定の基準で選択肢を選択するステップであって、当該選択肢だけではなく、前記所定の基準では選択されない選択肢も選択する選択ステップと、前記選択ステップが選択した各選択肢により得られた事象に基づいて、前記確率情報を更新する更新ステップと、を含むことを特徴とする。
【００１１】
本発明に係るプログラムは、所定の事象を得る確率が時間経過に応じて変化する複数の選択肢の各々の前記確率に関する確率情報を取得する取得手段、各選択肢の前記確率情報に基づいて、所定の基準で選択肢を選択する手段であって、当該選択肢だけではなく、前記所定の基準では選択されない選択肢も選択する選択手段、前記選択手段が選択した各選択肢により得られた事象に基づいて、前記確率情報を更新する更新手段、としてコンピュータを機能させる。
【００１２】
また、本発明の一態様では、前記選択手段は、前記所定の基準で選択する選択肢の割合を、前記所定の基準では選択されない選択肢の割合よりも多くする、ことを特徴とする。
【００１３】
また、本発明の一態様では、前記確率情報は、前記確率を示す確率分布であり、前記選択手段は、各選択肢の前記確率分布に基づいて、前記所定の基準で選択肢を選択する、ことを特徴とする。
【００１４】
また、本発明の一態様では、前記確率分布は、ベータ分布であり、前記所定の基準は、トンプソンサンプリング法における基準であり、前記選択手段は、各選択肢のベータ分布に基づいて、トンプソンサンプリング法で選択肢を選択し、当該選択肢だけではなく、トンプソンサンプリング法では選択されない選択肢も選択する、ことを特徴とする。
【００１５】
また、本発明の一態様では、前記選択手段は、所定のパラメータに応じた割合で、前記所定の基準では選択されない選択肢を選択する、ことを特徴とする。
【００１６】
また、本発明の一態様では、前記選択手段は、各選択肢により得られた事象の時系列的な変化に基づいて、前記所定の基準では選択されない選択肢を選択する割合を決定する、ことを特徴とする。
【００１７】
また、本発明の一態様では、前記更新手段は、各選択肢により得られた事象のうち、新しい事象ほど重み付けを高くして、前記確率情報を更新する、ことを特徴とする。
【００１８】
また、本発明の一態様では、前記更新手段は、各選択肢により得られた事象のうち、直近の一部の期間における事象に基づいて、前記確率情報を更新する、ことを特徴とする。
【００１９】
また、本発明の一態様では、各選択肢は、複数のユーザの各々に提示されるコンテンツであって、前記所定の事象は、前記コンテンツが提示されたユーザが当該コンテンツを選択することであり、前記更新手段は、前記選択手段が選択した各コンテンツが提示されたユーザの行動に基づいて、前記確率情報を更新する、ことを特徴とする。
【発明の効果】
【００２０】
本発明によれば、バンディットアルゴリズムにおけるリグレットを低減することが可能になる。
【図面の簡単な説明】
【００２１】
【図１】選択システムの全体構成を示す図である。
【図２】従来のバンディットアルゴリズムが想定するクリック率を示す図である。
【図３】本実施形態に係るバンディットアルゴリズムが想定するクリック率を示す図である。
【図４】ＡＢテストにおけるテスト期間の様子を示す図である。
【図５】従来のバンディットアルゴリズムが実行される様子を示す図である。
【図６】従来のバンディットアリゴリズムにおける確率分布の変化を示す図である。
【図７】ダイナミックバンディットアルゴリズムが実行される様子を示す図である。
【図８】ダイナミックバンディットアリゴリズムにおける確率分布の変化を示す図である。
【図９】選択システム１で実現される機能の一例を示す機能ブロック図である。
【図１０】コンテンツデータベースＤＢのデータ格納例を示す図である。
【図１１】選択システム１で実行される処理を説明する図である。
【発明を実施するための形態】
【００２２】
［１．選択システムの全体構成］
以下、本発明に関わる選択システムの実施形態の例を説明する。図１は、選択システムの全体構成を示す図である。図１に示すように、選択システム１は、サーバ１０と、ユーザ端末２０と、を含み、これらはネットワークＮを介してデータ送受信可能に接続される。なお、図１では、サーバ１０とユーザ端末２０との各々を１台ずつ示しているが、これらは複数台あってもよい。
【００２３】
サーバ１０は、サーバコンピュータである。サーバ１０は、制御部１１、記憶部１２、及び通信部１３を含む。制御部１１は、少なくとも１つのプロセッサを含む。制御部１１は、記憶部１２に記憶されたプログラムやデータに従って処理を実行する。記憶部１２は、主記憶部及び補助記憶部を含む。例えば、主記憶部はＲＡＭなどの揮発性メモリであり、補助記憶部は、ハードディスクやフラッシュメモリなどの不揮発性メモリである。通信部１３は、有線通信又は無線通信用の通信インタフェースであり、例えば、ネットワークを介してデータ通信を行う。
【００２４】
ユーザ端末２０は、ユーザが操作するコンピュータであり、例えば、パーソナルコンピュータ、携帯情報端末（タブレット型コンピュータを含む）、又は携帯電話機（スマートフォンを含む）等である。ユーザ端末２０は、制御部２１、記憶部２２、通信部２３、操作部２４、及び表示部２５を含む。制御部２１、記憶部２２、及び通信部２３のハードウェア構成は、それぞれ制御部１１、記憶部１２、及び通信部１３と同様のため、説明を省略する。
【００２５】
操作部２４は、入力デバイスであり、例えば、タッチパネルやマウス等のポインティングデバイスやキーボード等を含む。操作部２４は、操作内容を制御部２１に伝達する。表示部２５は、例えば、液晶表示部又は有機ＥＬ表示部等である。
【００２６】
なお、記憶部１２，２２に記憶されるものとして説明するプログラム及びデータは、ネットワークを介してサーバ１０又はユーザ端末２０に供給されるようにしてもよい。また、サーバ１０及びユーザ端末２０のハードウェア構成は、上記の例に限られず、種々のハードウェアを適用可能である。例えば、サーバ１０及びユーザ端末２０は、コンピュータ読み取り可能な情報記憶媒体を読み取る読取装置（例えば、光ディスクドライブやメモリカードスロット）や外部機器と直接的に接続するための入出力インタフェース（例えば、ＵＳＢ端子）を含んでもよい。情報記憶媒体に記憶されたプログラムやデータが読取装置又は入出力インタフェースを介して、サーバ１０又はユーザ端末２０に供給されるようにしてもよい。
【００２７】
［２．選択システムの概要］
選択システム１は、バンディットアルゴリズムを利用して、所定の事象を得る確率が時間経過に応じて変化する複数の選択肢のうち、少なくとも１つの選択肢を選択する。
【００２８】
事象とは、選択肢が選択されたことによって発生する現象、出来事、結果、又は効果である。選択肢が選択された場合には、複数の事象の各々が、当該事象に応じた確率で発生する。事象は、バンディット問題における報酬（パフォーマンス）であり、報酬の発生の有無、又は、報酬の程度である。本実施形態では、所定の事象が報酬のような良い事象である場合を説明するが、所定の事象は、事故、失敗、又は障害のような悪い事象であってもよい。即ち、良い事象を得るためにバンディットアルゴリズムが利用されてもよいし、悪い事象を防ぐためにバンディットアルゴリズムが利用されてもよい。
【００２９】
別の言い方をすれば、所定の事象は、バンディットアルゴリズムの利用者が得たい事象ではなく、利用者が得たくない事象であってもよい。所定の事象が良い事象である場合には、バンディットアルゴリズムは、所定の事象を得る確率の高い選択肢を選択し、所定の事象が悪い事象である場合には、バンディットアルゴリズムは、所定の事象を得る確率の低い選択肢を選択する。
【００３０】
確率とは、事象が起こる度合である。即ち、確率は、選択肢が選択された合計回数に対して、事象が起こる度合である。別の言い方をすれば、確率は、割合、比率、又は蓋然性ということもできる。確率は、時間が経過すると変化する。確率は、時間経過に応じて上がってもよいし下がってもよい。確率は、自然界の現象に応じて変化したり、ユーザの嗜好に応じて変化したりする。
【００３１】
選択肢とは、バンディット問題における腕である。別の言い方をすれば、選択肢は、候補である。選択肢は、選択システム１の用途に応じた選択肢を用意すればよい。選択システム１は、種々の用途で利用可能であり、例えば、ウェブサイトの運営、広告若しくはクーポンの配信、電子メールの配信、治験、ゲーム木探索、又はオンライン経路制御等に利用可能である。
【００３２】
選択システム１をウェブサイトの運営に利用する場合には、選択肢は、ウェブサイトの内容である。ウェブサイトの内容は、ウェブサイトの構成であり、例えば、コンテンツの種類、レイアウト、デザイン、又は色である。コンテンツは、電子的に提供される情報であればよく、例えば、画像、動画、楽曲、音声、テキスト、又はアプリケーションである。例えば、ユーザがウェブサイト内のコンテンツ又はリンクを選択することは、所定の事象の一例である。また例えば、ユーザがウェブサイトに掲載されたコンテンツを利用することは、所定の事象の一例である。利用とは、コンテンツのダウンロード、再生、又は視聴である。
【００３３】
選択システム１を広告又はクーポンの配信に利用する場合には、選択肢は、広告又はクーポンである。広告又はクーポンは、コンテンツの一例でもある。例えば、ユーザが広告又はクーポンを選択することは、所定の事象の一例である。また例えば、ユーザが広告又はクーポンに掲載された商品又はサービスを、購入、予約、又は契約することは、所定の事象の一例である。
【００３４】
選択システム１を電子メールの配信に利用する場合には、選択肢は、件名、本文、レイアウト、デザイン、画像、動画、又は添付ファイルである。例えば、ユーザが電子メール中のリンクを選択することは、所定の事象の一例である。また例えば、ユーザが添付ファイルを開くことは、所定の事象の一例である。また例えば、ユーザが電子メールに返信することは、所定の事象の一例である。また例えば、ユーザが電子メールを閲覧することは所定の事象の一例である。
【００３５】
選択システム１を治験に利用する場合には、選択肢は、薬である。例えば、検査項目の数値が回復することは、所定の事象の一例である。また例えば、ユーザから良好な所感を得られることは、所定の事象の一例である。
【００３６】
選択システム１をゲーム木探索に利用する場合には、選択肢は、ゲームにおける手又はコマンドである。ゲームは、種々のタイプのゲームを適用可能であり、例えば、将棋、囲碁、又はチェス等である。例えば、局面の優劣を示す評価値が上昇することは、所定の事象の一例である。また例えば、得点を稼ぐゲームであれば、得点が増加することは、所定の事象の一例である。
【００３７】
選択システム１をオンライン経路制御に利用する場合には、選択肢は、データを送信する場合のネットワーク上のルートである。例えば、データ遅延累積が小さくなることは、所定の事象の一例である。また例えば、ネットワーク機器の処理負荷又はネットワークの通信負荷が小さくなることは、所定の事象の一例である。
【００３８】
本実施形態では、選択システム１をウェブサイトの運営に利用し、各選択肢の一例として、複数のユーザの各々に提示されるコンテンツを説明する。このため、コンテンツが提示されたユーザが当該コンテンツを選択することが所定の事象に相当し、クリック率は、所定の事象を得る確率に相当する。例えば、選択システム１は、バンディットアルゴリズムを利用して、クリック率が高いコンテンツを選択する。
【００３９】
なお、本実施形態では、ユーザがコンテンツを選択する確率（選択率）を、クリック率と記載するが、ユーザは、クリック以外の操作によってコンテンツを選択してもよい。例えば、ユーザは、タップ、長押し、ダブルタップ、スワイプ、フリック、又はダブルクリックといった操作によって、コンテンツを選択したよい。即ち、クリック率は、コンテンツの選択率を意味し、コンテンツを選択するための操作は、クリックに限定されない。
【００４０】
また、本実施形態では、説明の簡略化のために、コンテンツの数を２つとして説明するが、コンテンツは、３つ以上であってもよい。即ち、多腕バンディット問題における腕の数を２つとして説明するが、腕の数は、３つ以上であってもよい。以降、本実施形態に係るバンディットアルゴリズムを、従来のバンディットアルゴリズムと対比して説明する。
【００４１】
図２は、従来のバンディットアルゴリズムが想定するクリック率を示す図である。図２の縦軸は、クリック率を示し、横軸は、時間を示す。図２に示すように、コンテンツＡは、クリック率ＣＴＲ１が６０％であり、コンテンツＢは、クリック率ＣＴＲ２が２０％である。
【００４２】
従来のバンディットアルゴリズムでは、時間経過に関係なく、各コンテンツのクリック率が固定値の場合を想定している。このため、探索によって、コンテンツＡのクリック率ＣＴＲ１がコンテンツＢのクリック率ＣＴＲ２よりも高いことが特定されると、それ以降は、コンテンツＡが１００％選択され、コンテンツＢは全く選択されない状態となる。
【００４３】
しかしながら、実際には、トレンド（ユーザの嗜好）が変化するので、コンテンツのクリック率は、時間経過に応じて変化する。例えば、ハロウィンの時期には、カボチャのイラストが描かれたコンテンツが好まれたり、オレンジと黒を基調としたコンテンツが好まれたりする。このため、これらのコンテンツのクリック率は、ハロウィンの時期は高いが、ハロウィンが過ぎると低くなる。
【００４４】
また例えば、クリスマスの時期には、サンタクロースのイラストが描かれたコンテンツが好まれたり、赤と緑を基調としたコンテンツが好まれたりする。これらのコンテンツのクリック率は、ハロウィンの時期は低いが、ハロウィンが経過してクリスマスが近づくにつれて高くなる。本実施形態のバンディットアルゴリズムでは、上記のように、コンテンツのクリック率が時間経過に応じて変化する場合を想定している。
【００４５】
図３は、本実施形態に係るバンディットアルゴリズムが想定するクリック率を示す図である。図３に示すように、コンテンツＡ（例えば、ハロウィンの時期に好まれるデザインのコンテンツ）は、ｔ＝０の時点（例えば、１０月）では、クリック率ＣＴＲ１が６０％であり、時間経過に応じて徐々にクリック率ＣＴＲ１が下がる。コンテンツＢ（例えば、クリスマスの時期に好まれるデザインのコンテンツ）は、ｔ＝０の時点では、クリック率ＣＴＲ２が２０％であり、時間経過に応じて徐々にクリック率ＣＴＲ２が上がる。ここでは、説明の簡略化のために、コンテンツＡのクリック率ＣＴＲ１と、コンテンツＢのクリック率ＣＴＲ２と、が反比例する場合を説明する。
【００４６】
なお、図３では、コンテンツＢのクリック率ＣＴＲ２が、コンテンツＡのクリック率ＣＴＲ１に追いつく時点をｔ１とする。ｔ＝０〜ｔ１の期間Ｔ１において、コンテンツＡのクリック率ＣＴＲ１は、コンテンツＢのクリック率ＣＴＲ２よりも高い。時点ｔ１以降の期間Ｔ２において、コンテンツＢのクリック率ＣＴＲ２は、コンテンツＡのクリック率ＣＴＲ１よりも高い。
【００４７】
もし仮に、サーバ１０が、全期間においてクリック率が高い方のコンテンツを選択すると、バンディット問題におけるリグレットは発生しない。図３の例であれば、期間Ｔ１においてコンテンツＡを１００％選択し、期間Ｔ２においてコンテンツＢを１００％選択すると、リグレットが発生せず、理想的なクリック数を得る。このため、リグレットを抑えるためには、コンテンツＢのクリック率ＣＴＲ２がコンテンツＡのクリック率ＣＴＲ１よりも高くなる時点ｔ１を見極めることが重要である。
【００４８】
この点、クリック率の高いコンテンツを選択する方法として、バンディットアルゴリズム以外に、ＡＢテストと呼ばれる手法が知られている。ＡＢテストは、所定のテスト期間において、コンテンツをランダムに選択してクリック率を計測し、テスト期間の終了後において、テスト期間中に最もクリック率が高かったコンテンツを１００％選択する手法である。
【００４９】
図４は、ＡＢテストにおけるテスト期間の様子を示す図である。図４の上のグラフは、テスト期間において、コンテンツＡが選択される割合ＲＡと、コンテンツＢが選択される割合ＲＢとを示す。図４の下のグラフは、テスト期間における実際の総クリック数ＲＣと、理想的な総クリック数ＩＣと、を示す。
【００５０】
実際の総クリック数ＲＣは、コンテンツＡが実際に選択された数と、コンテンツＢが実際に選択された数と、の合計値である。実際の総クリック数ＲＣが高いほど、バンディット問題における報酬の合計値が高いことを意味する。
【００５１】
理想的な総クリック数ＩＣは、リグレットが発生しない場合の総クリック数である。即ち、理想的な総クリック数ＩＣは、全期間において、クリック率が最も高いコンテンツを選び続けた場合の総クリック数である。ここでは、期間Ｔ１においてコンテンツＡを１００％選択し、期間Ｔ２においてコンテンツＢを１００％選択した場合に、理想的な総クリック数ＩＣを得る。リグレットは、理想的な総クリック数ＩＣと、実際の総クリック数ＲＣと、の差の積分値となる。
【００５２】
図４の上のグラフに示すように、テスト期間では、コンテンツＡ，Ｂの各々がランダムに選択されるので、割合ＲＡ，ＲＢは、それぞれ５０％となる。ここでは、コンテンツＡのクリック率ＣＴＲ１と、コンテンツＢのクリック率ＣＴＲ２と、は反比例するので、割合ＲＡ，ＲＢがそれぞれ５０％であれば、図４の下のグラフに示すように、テスト期間における実際の総クリック数ＲＣは一定値になるので、多くのリグレットが発生する。
【００５３】
より具体的には、期間Ｔ１では、クリック率が高いコンテンツＡが選択される割合が少ないことによるリグレット（即ち、クリック率が低いコンテンツＢが選択される割合が高いことによるリグレット）が発生する。一方、期間Ｔ２では、クリック率が高いコンテンツＢが選択される割合が少ないことによるリグレット（即ち、クリック率が低いコンテンツＡが選択される割合が高いことによるリグレット）が発生する。
【００５４】
以上のように、ＡＢテストでは、テスト期間中に多くのリグレットが発生する。更に、ＡＢテストでは、テスト期間の終了後には、コンテンツＡ，Ｂの何れか一方のみが選択されるため、その後のクリック率の変化に対応することもできない。
【００５５】
図５は、従来のバンディットアルゴリズムが実行される様子を示す図であり、図６は、従来のバンディットアリゴリズムにおける確率分布の変化を示す図である。図５の上のグラフは、コンテンツＡが選択される割合ＲＡと、コンテンツＢが選択される割合ＲＢと、を示す。図５の下のグラフは、実際の総クリック数ＲＣと、理想的な総クリック数ＩＣと、を示す。図６に示す確率分布は、従来のバンディットアルゴリズムが選択したコンテンツによって計測されたクリック率を示す確率分布である。
【００５６】
なお、ここでは、従来のバンディットアルゴリズムの一例として、トンプソンサンプリング法を説明する。トンプソンサンプリング法では、確率分布の一例であるベータ分布を利用してコンテンツが選択される。例えば、コンテンツＡの確率分布から生成した乱数と、コンテンツＢの確率分布から生成した乱数と、によってコンテンツが選択されてもよいし、コンテンツＡの確率分布の最頻値と、コンテンツＢの確率分布の最頻値と、によってコンテンツが選択されてもよい。なお、最頻値ではなく、平均値又は中央値が用いられてもよい。コンテンツＡが選択される割合ＲＡは、コンテンツＡのベータ分布Ｐ１が示すクリック率が高いほど高くなり、コンテンツＡが選択される割合ＲＢは、コンテンツＢのベータ分布Ｐ２が示すクリック率が高いほど高くなる。
【００５７】
時刻ｔ＝０の時点では、コンテンツＡ，Ｂのクリック率の情報がなく、ベータ分布Ｐ１，Ｐ２は同じ状態になるので、図５に示すように、割合ＲＡ，ＲＢは、それぞれ５０％となり、しばらくの間、当該割合で探索が実行される。その後、探索結果に基づいて、コンテンツＡのベータ分布Ｐ１と、コンテンツＢのベータ分布Ｐ２と、が更新される。ベータ分布Ｐ１，Ｐ２の更新により、探索後すぐに、コンテンツＡのクリック率ＣＴＲ１が、コンテンツＢのクリック率ＣＴＲ２よりも極めて高いことが特定されるので、コンテンツＡが１００％選択され、コンテンツＢは全く選択されない状態となる。
【００５８】
コンテンツＡのクリック率ＣＴＲ１は、時間経過に応じて徐々に下がるので、図６に示すように、コンテンツＡのベータ分布Ｐ１の最頻値は、徐々に低下する。また、コンテンツＡは、１００％選択されており、多くの観測事象がベータ分布Ｐ１に反映されるため、ピークが高くなる。
【００５９】
一方、コンテンツＢは、全く選択されていないので、ベータ分布Ｐ２は変わらない。このため、コンテンツＢの実際のクリック率ＣＴＲ２が徐々に上がっていたとしても、ベータ分布Ｐ２上では、その事実を特定することができないので、図５に示すように、時点ｔ１を過ぎたとしても、コンテンツＡが１００％選択され、コンテンツＢは全く選択されない状態となる。
【００６０】
その後、コンテンツＡのベータ分布Ｐ１がコンテンツＢのベータ分布Ｐ２に近づくと、最頻値の相対的な差が小さくなるので、コンテンツＢが選択され始める。図５では、コンテンツＢが選択され始める時点をｔ２とする。図５に示すように、時点ｔ２は、時点ｔ１よりもかなり後である。このため、時点ｔ２になると、コンテンツＢのクリック率ＣＴＲ２は、既にコンテンツＡのクリック率ＣＴＲ１よりもかなり高い。
【００６１】
コンテンツＢが選択され始めると、ベータ分布Ｐ２上で、コンテンツＢのクリック率ＣＴＲ２が高いことが特定されるので、図６に示すように、コンテンツＢのベータ分布Ｐ２の最頻値は、急激に上昇する。それに伴い、図５の上のグラフに示すように、時点ｔ２以降において、コンテンツＢが選択される割合ＲＢは、急激に上昇する。その後、時点ｔ３になると、コンテンツＢが１００％選択され、コンテンツＡは全く選択されない状態となる。
【００６２】
以上のように、従来のバンディットアルゴリズムでは、時点ｔ２になるまでは、コンテンツＡが１００％選択されるので、コンテンツＢのクリック率ＣＴＲ２がコンテンツＡのクリック率ＣＴＲ１よりも高いという事実を特定するのが遅れてしまう。このため、時点ｔ１以降において、クリック率が低いコンテンツＡを選択し続けてしまい、多くのリグレットが発生する。
【００６３】
そこで、本実施形態のバンディットアルゴリズムでは、所定のパラメータεに応じた割合で、トンプソンサンプリング法では選択されないコンテンツを選択し、当該コンテンツのクリック率の変化を迅速に特定するようにしている。即ち、本実施形態のバンディットアルゴリズムは、トンプソンサンプリング法に基づくコンテンツの選択を１００％行うのではなく、パラメータεに応じた割合で探索を実行し、クリック率の変化をいち早く検出する。以降、本実施形態のバンディットアルゴリズムを、ダイナミックバンディットアルゴリズムと記載する。
【００６４】
例えば、トンプソンサンプリング法によりコンテンツＡが選択される割合をＲＡＴ（図５のＲＡ）とし、トンプソンサンプリング法によりコンテンツＢが選択される割合をＲＢＴ（図５のＲＢ）とすると、ダイナミックバンディットアルゴリズムによれば、コンテンツＡが選択される割合ＲＡと、コンテンツＢが選択される割合ＲＢと、は下記の通りとなる。
【００６５】
・割合ＲＡＴ＞ＲＢＴの場合
ＲＡ＝（１−ε）＊ＲＡＴ
ＲＢ＝（１−ε）＊ＲＢＴ＋ε
【００６６】
・割合ＲＢＴ＞ＲＡＴの場合
ＲＡ＝（１−ε）＊ＲＡＴ＋ε
ＲＢ＝（１−ε）＊ＲＢＴ
【００６７】
・割合ＲＢＴ＝ＲＡＴの場合
ＲＡ＝（１−ε）＊ＲＡＴ＋ε／２
ＲＢ＝（１−ε）＊ＲＢＴ＋ε／２
【００６８】
なお、上記の割合ＲＡ，ＲＢは、一例であり、ダイナミックバンディットアルゴリズムは、トンプソンサンプリング法では選択されないコンテンツ（又は選択されにくいコンテンツ）をパラメータεに応じた割合で選択すればよい。
【００６９】
また、本実施形態では、パラメータεが固定値である場合を説明するが、後述する変形例のように、パラメータεは、可変値であってもよい。ただし、パラメータεの値が高すぎると、多くの探索が行われてリグレットの原因となるので、パラメータεは、低めに設定した方がよく、本実施形態では０．０１とする。即ち、ダイナミックバンディットアルゴリズムは、９９％の割合でトンプソンサンプリングに基づくコンテンツの選択を行い、１％の割合で探索を実行する。この点は、バンディットアルゴリズムの一例であるイプシロングリーディ法と同じである。なお、パラメータεは、０．０１に限られず、０．０１よりも小さくてもよいし大きくてもよい。例えば、パラメータεは、０よりも大きく、０．５よりも小さい任意の数値を設定してもよい。
【００７０】
図７は、ダイナミックバンディットアルゴリズムが実行される様子を示す図であり、図８は、ダイナミックバンディットアリゴリズムにおける確率分布の変化を示す図である。図７の上のグラフは、コンテンツＡが選択される割合ＲＡと、コンテンツＢが選択される割合ＲＢとを示す。図７の下のグラフは、実際の総クリック数ＲＣと、理想的な総クリック数ＩＣと、を示す。図８に示す確率分布は、ダイナミックバンディットアルゴリズムが選択したコンテンツによって計測されたクリック率を示す確率分布である。
【００７１】
図７に示すように、ｔ＝０の時点では、コンテンツＡ，Ｂのクリック率の情報がないため、割合ＲＡ，ＲＢは、それぞれ５０％となり、探索が実行される。この点は、従来のバンディットアルゴリズムと同様である。その後すぐに、コンテンツＡのクリック率が高いことが特定されるので、コンテンツＡが略１００％選択され、コンテンツＢはほとんど選択されない状態となる。
【００７２】
即ち、トンプソンサンプリング法だけであれば、コンテンツＡが１００％選択され（ＲＡＴ＝１）、コンテンツＢは全く選択されないが（ＲＢＴ＝０）、ダイナミックバンディットアルゴリズムによれば、上記の数式の通り、コンテンツＢは、全く選択されないのではなく、パラメータεの割合で選択される。本実施形態では、パラメータεは０．０１なので、コンテンツＢは、１％の割合で選択される。
【００７３】
コンテンツＡのクリック率ＣＴＲ１は、時間経過に応じて徐々に下がるので、図８に示すように、コンテンツＡのベータ分布Ｐ１の最頻値は、徐々に低下する。一方、コンテンツＢは、全く選択されないわけではなく、１％の割合で選択されているので、ベータ分布Ｐ２の最頻値が徐々に上昇する。即ち、従来のバンディットアルゴリズムでは、コンテンツＢは、全く選択されないので、ベータ分布Ｐ２が変化しないので、コンテンツＢのクリック率が高まっている事実を検知できなかったが、ダイナミックバンディットアルゴリズムでは、コンテンツＢが僅かながら選択されるので、当該事実を検知可能となる。
【００７４】
コンテンツＢのベータ分布Ｐ２の変化により、コンテンツＢのクリック率ＣＴＲ２が時間経過に応じて徐々に上がっていることが特定されるので、図７に示すように、コンテンツＢの割合ＲＢは、早い段階で上がり始める。即ち、コンテンツＡのベータ分布Ｐ１とコンテンツＢのベータ分布Ｐ２との差が徐々に縮まるので、トンプソンサンプリング法によりコンテンツＢが選択される割合ＲＢＴは、早い段階で０ではなくなる。その後、コンテンツＡのクリック率ＣＴＲ１とコンテンツＢのクリック率ＣＴＲ２との差が徐々に縮まるにつれて、コンテンツＡの割合ＲＡとコンテンツＢの割合ＲＢとの差も徐々に縮まる。図７の例では、時点ｔ１付近において、割合ＲＡ，ＲＢは、それぞれ５０％ずつとなる。
【００７５】
その後、図８に示すように、コンテンツＢのベータ分布Ｐ２の最頻値は、コンテンツＡのベータ分布Ｐ１の最頻値よりも高くなるので、図７に示すように、割合ＲＢは、割合ＲＡよりも高くなる。コンテンツＢのクリック率ＣＴＲ２とコンテンツＡのクリック率ＣＴＲ１との差が徐々に広がるにつれて、コンテンツＢの割合ＲＢとコンテンツＡの割合ＲＡとの差も徐々に広がる。図７に示すように、最終的には、コンテンツＢの割合ＲＢが略１００％になり、コンテンツＡの割合ＲＡは略０％になる。
【００７６】
図７に示すように、ダイナミックバンディットアルゴリズムによれば、コンテンツＢのクリック率の変化を迅速に検出することで、実際のクリック数ＲＣを理想的なクリック数ＩＣに近づけることができる。また、パラメータεを低く設定することで、クリック率が低い方のコンテンツを選択する割合を極力減らすこともできる。
【００７７】
以上のように、ダイナミックバンディットアルゴリズムでは、トンプソンサンプリング法で選択されないコンテンツをパラメータεの割合で選択し、当該コンテンツのクリック率の変化を迅速に検知する（別の言い方をすれば、当該コンテンツのクリック率の将来的な変化を予測する）ことで、従来の手法に比べてリグレットを低減している。以降、選択システム１の詳細を説明する。
【００７８】
［３．選択システムで実現される機能］
図９は、選択システム１で実現される機能の一例を示す機能ブロック図である。図９に示すように、選択システム１では、データ記憶部１００、取得部１０１、選択部１０２、及び更新部１０３が実現される。本実施形態では、これら各機能がサーバ１０により実現される場合を説明する。
【００７９】
［３−１．データ記憶部］
データ記憶部１００は、記憶部１２を主として実現される。データ記憶部１００は、ダイナミックバンディットアルゴリズムを実装するために必要なデータを記憶する。例えば、データ記憶部１００は、パラメータεを記憶する。また例えば、データ記憶部１００は、コンテンツデータベースＤＢを記憶する。
【００８０】
図１０は、コンテンツデータベースＤＢのデータ格納例を示す図である。図１０に示すように、コンテンツデータベースＤＢは、コンテンツに関する各種情報を格納するデータベースである。例えば、コンテンツデータベースＤＢには、コンテンツを一意に識別するコンテンツＩＤ、コンテンツの実データへのパス名、クリック数、及び非クリック数が格納される。
【００８１】
クリック数は、コンテンツが選択された合計回数である。即ち、クリック数は、コンテンツが提示されたユーザが当該コンテンツを選択した合計回数である。非クリック数は、コンテンツが選択されなかった回数である。即ち、非クリック数は、コンテンツが提示されたユーザが当該コンテンツを選択しなかった回数である。
【００８２】
クリック数と非クリック数とは、過去の全期間における合計回数であってもよいし、直近の一部の期間における合計回数であってもよい。一部の期間とする場合には、数分〜数時間程度であってもよいし、１日〜数か月程度であってもよい。本実施形態では、クリック数と非クリック数は、後述する取得部１０１がベータ分布を取得するために参照される。
【００８３】
なお、データ記憶部１００に記憶されるデータは、上記の例に限られない。例えば、データ記憶部１００は、各コンテンツに対するユーザの行動履歴を示すデータベースを記憶してもよい。このデータベースには、コンテンツが提示されたユーザの行動内容と行動日時とが格納される。行動は、コンテンツに対するユーザの行動であり、例えば、選択、購入、予約、又は契約である。
【００８４】
［３−２．取得部］
取得部１０１は、制御部１１を主として実現される。取得部１０１は、クリック率が時間経過に応じて変化する複数のコンテンツの各々のクリック率に関する確率情報を取得する。
【００８５】
確率情報は、クリック率が反映された情報であればよく、例えば、クリック率を示す確率分布、確率分布を生成するためのパラメータ、過去のクリック率の平均値、又はクリック率の推移である。なお、平均値は、過去の全期間又は一部の期間において計測された確率の単純平均値が用いられてもよいし、加重平均値が用いられてもよい。加重平均値が用いられる場合には、新しい確率ほど重み付けを高くし、古い確率ほど重み付けを低くしてもよい。
【００８６】
本実施形態では、確率情報の一例として、クリック率を示す確率分布を説明する。本実施形態では、確率分布の一例としてベータ分布を説明するが、ベルヌーイ分布、ポアソン分布、又は多項分布といった種々の確率分布を適用可能である。なお、ベータ分布は、連続型の確率分布であり、第１種ベータ分布が用いられてもよいし、第２種ベータ分布が用いられてもよい。ベータ分布の確率密度関数は、パラメータα，βに基づいて定義される。
【００８７】
パラメータαは、所定の事象が得られたことを確率密度関数に反映させる（ポジティブフィードバック）ためのパラメータであり、所定の事象を得た場合に増加する。本実施形態では、コンテンツが選択されることが所定の事象を得ることに相当するので、パラメータαは、コンテンツが選択された場合に増加する。コンテンツの選択数をそのままパラメータαとしてもよいし、コンテンツの選択数を所与の数式に代入して得られる値をパラメータαとしてもよい。
【００８８】
パラメータβは、所定の事象が得られなかったことを確率密度関数に反映させる（ネガティブフィードバック）ためのパラメータであり、所定の事象が得られなかった場合に増加する。本実施形態では、コンテンツが選択されないことが所定の事象を得られないことに相当するので、パラメータβは、コンテンツが選択されなかった場合に増加する。コンテンツが選択されなかった回数をそのままパラメータβとしてもよいし、当該回数を所与の数式に代入して得られる値をパラメータβとしてもよい。
【００８９】
本実施形態では、２つのコンテンツＡ，Ｂについて説明するので、コンテンツＡのベータ分布Ｐ１のパラメータをα１，β１と記載し、コンテンツＢのベータ分布Ｐ２のパラメータをα２，β２と記載する。なお、これらを特に区別する必要のないときは、単にα，βと記載する。パラメータα，βは、初期値が代入され、後述する更新部１０３によって更新される。初期値は、０よりも大きい任意の値であればよく、例えば、０．５〜５程度の値であってもよいし、他の値であってもよい。
【００９０】
なお、ベータ分布の取得方法自体は、種々の手法を適用可能であり、例えば、トンプソンサンプリング法におけるベータ分布の取得方法を適用可能である。例えば、取得部１０１は、コンテンツデータベースＤＢに基づいて、ベータ分布を生成する。取得部１０１は、各コンテンツのクリック数に基づいて、当該コンテンツのパラメータαを取得し、各コンテンツの非クリック数に基づいて、当該コンテンツのパラメータβを取得する。
【００９１】
本実施形態では、説明の簡略化のために、取得部１０１は、各コンテンツのクリック数を、そのまま当該コンテンツのパラメータαとし、各コンテンツの非クリック数を、そのまま当該コンテンツのパラメータβを取得する。取得部１０１は、パラメータα，βに基づいて、ベータ分布を取得する。ベータ分布は、パラメータαがパラメータβに比べて高いほど、最頻値が１に近くなりクリック率が高い分布を示し、パラメータβがパラメータαに比べて高いほど、最頻値が０に近くなりクリック率が低い分布を示す。
【００９２】
なお、取得部１０１は、各コンテンツのクリック数を計算式に代入して得られる値を、当該コンテンツのパラメータαとし、各コンテンツの非クリック数を計算式に代入して得られる値を、当該コンテンツのパラメータβとしてもよい。この場合、クリック数が多いほどパラメータαが高くなり、非クリック数が多いほどパラメータβが高くなるように計算式を定めておけばよい。例えば、この計算式は、過去の全期間又は一部の期間の平均値を求める計算式であってもよい。平均値としては、単純平均であってもよいし、加重平均であってもよい。
【００９３】
また、本実施形態では、取得部１０１がベータ分布を生成する場合を説明するが、ベータ分布が予め生成されてデータ記憶部１００に記憶されていてもよい。この場合、取得部１０１は、データ記憶部１００からベータ分布を取得する。ベータ分布は、サーバ１０により予め生成されてもよいし、他のコンピュータにより予め生成されてもよい。また、ベータ分布は、サーバ１０以外の他のコンピュータに記憶されていてもよい。この場合、取得部１０１は、当該他のコンピュータからベータ分布を取得する。
【００９４】
［３−３．選択部］
選択部１０２は、制御部１１を主として実現される。選択部１０２は、複数のコンテンツの中から少なくとも１つのコンテンツを選択する。選択部１０２は、一度に１つのコンテンツを選択してもよいし、一度に複数のコンテンツを選択してもよい。本実施形態では、説明の簡略化のために、選択部１０２が一度に１つのコンテンツを選択する場合を説明する。
【００９５】
選択部１０２は、各コンテンツのベータ分布（確率情報・確率分布の一例）に基づいて、所定の基準でコンテンツを選択する。ただし、選択部１０２は、当該コンテンツだけではなく、所定の基準では選択されないコンテンツも選択する。即ち、選択部１０２は、ある機会では、所定の基準でコンテンツを選択し、別の機会では、所定の基準では選択されないコンテンツを選択する。
【００９６】
所定の基準とは、コンテンツを選択するために定められた基準である。基準自体は、種々のバンディットアルゴリズムで用いられている基準を適用可能である。このため、所定の基準で選択されるコンテンツは、従来のバンディットアルゴリズムで選択されるコンテンツということができる。例えば、所定の基準は、トンプソンサンプリング法、ソフトマックス法、ＵＣＢ（Upper Confidence Bounds）法、ＥＸＰ３法、又はベイズ確率を使用したアルゴリズムで利用されている基準であってもよい。
【００９７】
所定の基準では選択されないコンテンツは、所定の基準で選択されるコンテンツ以外のコンテンツである。別の言い方をすれば、所定の基準では選択されないコンテンツは、従来のバンディットアルゴリズムでは選択されないコンテンツであり、本来であれば選択されないコンテンツである。例えば、所定の基準では選択されないコンテンツは、ベータ分布に基づいた場合には選択されないコンテンツである。
【００９８】
本実施形態では、ユーザがコンテンツを選択することが所定の事象に相当し、所定の事象が先述した得たい事象なので、所定の基準で選択されるコンテンツは、クリック率（所定の事象を得る確率）が相対的に高いコンテンツであり、所定の基準で選択されないコンテンツは、クリック率が相対的に低いコンテンツである。一方、所定の事象が先述した得たくない事象の場合には、所定の基準で選択されるコンテンツは、所定の事象を得る確率が相対的に低いコンテンツであり、所定の基準で選択されないコンテンツは、当該確率が相対的に高いコンテンツである。
【００９９】
選択部１０２は、所定の基準でコンテンツを選択するか、所定の基準では選択されないコンテンツを選択するか、をランダムに決定してもよいが、本実施形態では、選択部１０２は、所定のパラメータεに応じた割合で、所定の基準では選択されないコンテンツを選択する。パラメータεに応じた割合とは、εの値であってもよいし、εの値を計算式に代入して得られる値であってもよい。
【０１００】
本実施形態では、選択部１０２は、パラメータεに基づいて、所定の基準でコンテンツを選択するか、所定の基準では選択されないコンテンツを選択するか、を決定する。パラメータεは、低い値（例えば、０．０１）が設定されるので、選択部１０２は、所定の基準で選択するコンテンツの割合を、所定の基準では選択されないコンテンツの割合よりも多くする。別の言い方をすれば、選択部１０２は、所定の基準では選択されないコンテンツの割合を、所定の基準で選択するコンテンツの割合よりも少なくする。
【０１０１】
なお、本実施形態では、所定の基準の一例として、トンプソンサンプリング法における基準を説明する。このため、選択部１０２は、各コンテンツのベータ分布に基づいて、トンプソンサンプリング法でコンテンツを選択し、当該コンテンツだけではなく、トンプソンサンプリング法では選択されないコンテンツも選択する。
【０１０２】
例えば、選択部１０２は、所定の基準でコンテンツを選択すると決定した場合、取得部１０１が取得したベータ分布に基づいて、トンプソンサンプリング法における基準でコンテンツを選択する。選択部１０２は、各コンテンツのベータ分布に基づいて乱数を発生させ、乱数が最も高いコンテンツを選択する。乱数は、ベータ分布の最頻値が高いほど、発生可能な最高値が高くなり、ベータ分布の最頻値が低いほど、発生可能な最高値が低くなる。
【０１０３】
なお、トンプソンサンプリング法におけるコンテンツの選択方法は、上記の例に限られない。ベータ分布が示すクリック率が高いほど選択される割合が高くなり、ベータ分布が示すクリック率が低いほど選択される割合が低くなればよい。例えば、選択部１０２は、各コンテンツの最頻値の比率に基づいて、当該コンテンツが選択される割合を決定してもよい。
【０１０４】
例えば、コンテンツＡのベータ分布の最頻値をＦＡとし、コンテンツＢのベータ分布の最頻値をＦＢとした場合に、選択部１０２は、コンテンツＡの割合を「ＦＡ／（ＦＡ＋ＦＢ）」とし、コンテンツＢの割合を「ＦＢ／（ＦＡ＋ＦＢ）」としてもよい。他にも例えば、選択部１０２は、ベータ分布の最頻値が高い方を１００％選択し、ベータ分布の最頻値が低い方を選択しないようにしてもよい。
【０１０５】
また例えば、選択部１０２は、所定の基準選択されないコンテンツを選択すると決定した場合、トンプソンサンプリング法における基準とは異なる基準でコンテンツを選択すればよい。例えば、選択部１０２は、ランダムにコンテンツを選択してもよい。また例えば、選択部１０２は、トンプソンサンプリング法で選択されるコンテンツを特定し、当該コンテンツ以外のコンテンツを選択してもよい。また例えば、選択部１０２は、確率分布が示す最頻値が最も低いコンテンツを選択してもよい。本実施形態では、選択部１０２は、トンプソンサンプリング法で選択されるコンテンツ以外のコンテンツを選択する。
【０１０６】
なお、選択部１０２がコンテンツを選択する機会は、繰り返し訪れるものとする。コンテンツを選択する機会は、定期的に訪れてもよいし、不定期的に訪れてもよい。定期的にコンテンツが選択される場合には、選択部１０２は、一定期間が経過するたびにコンテンツを選択する。非定期的にコンテンツが選択される場合には、選択部１０２は、ランダムに定まるタイミングでコンテンツを選択してもよいし、ユーザ端末２０からアクセスを受け付けた場合にコンテンツを選択してもよい。本実施形態では、選択部１０２は、ユーザ端末２０からアクセスを受け付けた場合にコンテンツを選択する。
【０１０７】
［３−４．更新部］
更新部１０３は、制御部１１を主として実現される。更新部１０３は、選択部１０２が選択した各コンテンツにより得られた事象に基づいて、ベータ分布を更新する。更新とは、得られた事象をベータ分布に反映させることである。
【０１０８】
更新部１０３は、ベータ分布を直接的に更新してもよいし、間接的に更新してもよい。即ち、更新部１０３は、ベータ分布の確率密度関数が示す曲線自体を更新してもよいし、ベータ分布を取得するための情報を更新してもよい。本実施形態では、更新部１０３は、ベータ分布を取得するためのクリック数と非クリック数とを更新する場合を説明するが、パラメータα，βを更新してもよい。
【０１０９】
また、本実施形態では、ユーザの行動が事象に相当するので、更新部１０３は、選択部１０２が選択した各コンテンツが提示されたユーザの行動に基づいて、ベータ分布を更新する。コンテンツが提示されたユーザの行動とは、コンテンツが提示された状態でユーザが取った行動であり、コンテンツに対するユーザの行動である。更新部１０３は、ユーザ端末２０からユーザの行動を取得し、当該行動に基づいて、ベータ分布を更新する。
【０１１０】
例えば、サーバ１０は、ユーザ端末２０からのアクセスを受け付けた場合に、選択部１０２が選択したコンテンツをユーザ端末２０に送信する。ユーザ端末２０は、コンテンツを表示部２５に表示させ、操作部２４の検出信号に基づいて、ユーザがコンテンツを選択したかを判定する。ユーザ端末２０は、ユーザがコンテンツを選択した場合に、ユーザＩＤとともに、コンテンツが選択されたことを示す通知をサーバ１０に送信する。
【０１１１】
更新部１０３は、当該通知を受け取った場合に、クリック数を増加させる。一方、更新部１０３は、ユーザ端末２０から当該通知を一定期間受信しなかったり、当該通知を受信することなくユーザ端末２０とのセッションが切断されたりした場合には、非クリック数を増加させる。
【０１１２】
なお、更新部１０３は、定期的にベータ分布を更新してもよいし、不定期的にベータ分布を更新してもよい。定期的にベータ分布を更新する場合には、更新部１０３は、所定の間隔ごとに、ベータ分布を更新する。当該間隔は、予め定められた値であればよく、例えば、数分〜数時間であってもよいし、１日〜数か月であってもよい。不定期的にベータ分布を更新する場合には、更新部１０３は、コンテンツを提供するたびにベータ分布を更新してもよいし、コンテンツを提供した回数が一定回数を超えるたびにベータ分布を更新してもよい。
【０１１３】
［４．選択システムで実行される処理］
図１１は、選択システム１で実行される処理を説明する図である。図１１に示す処理は、制御部１１が記憶部１２に記憶されたプログラムに従って動作し、制御部２１が記憶部２２に記憶されたプログラムに従って動作することによって実行される。下記に説明する処理は、図９に示す機能ブロックにより実行される処理の一例である。
【０１１４】
図１１に示すように、まず、ユーザ端末２０において、制御部２１は、サーバ１０にアクセス要求を送信する（Ｓ１００）。アクセス要求は、任意のタイミングで送信されるようにすればよく、例えば、ユーザがサーバ１０のＵＲＬを指定した場合に送信されてもよいし、ユーザ端末２０で所定のアプリケーションが起動した場合に送信されてもよい。
【０１１５】
サーバ１０においては、アクセス要求を受信すると、制御部１１は、コンテンツデータベースＤＢに基づいて、ベータ分布のパラメータα，βを取得する（Ｓ１０１）。Ｓ１０１においては、制御部１１は、コンテンツデータベースＤＢを参照し、コンテンツＡが選択された回数をパラメータα１とし、コンテンツＡが選択されなかった回数をパラメータβ１とする。制御部１１は、コンテンツデータベースＤＢを参照し、コンテンツＢが選択された回数をパラメータα２とし、コンテンツＢが選択されなかった回数をパラメータβ２とする。
【０１１６】
制御部１１は、Ｓ１０１で取得したパラメータα，βに基づいて、各コンテンツのベータ分布を取得する（Ｓ１０２）。Ｓ１０２においては、制御部１１は、パラメータα１，β１に基づいて、コンテンツＡのベータ分布Ｐ１を取得し、パラメータα２，β２に基づいて、コンテンツＢのベータ分布Ｐ２を取得する。なお、ベータ分布の確率密度関数の数式は、予め記憶部１２に定義されているものとする。
【０１１７】
制御部１１は、Ｓ１０２で取得した各コンテンツのベータ分布に基づいて、トンプソンサンプリング法でコンテンツを特定する（Ｓ１０３）。Ｓ１０３においては、制御部１１は、ベータ分布Ｐ１の最頻値に基づく乱数がベータ分布Ｐ２の最頻値に基づく乱数よりも大きい場合には、コンテンツＡを特定し、ベータ分布Ｐ２の最頻値に基づく乱数がベータ分布Ｐ１の最頻値に基づく乱数よりも大きい場合には、コンテンツＢを特定する。乱数が同じ場合には、乱数が再度取得されてもよいし、コンテンツＡ又はＢがランダムに選択されてもよい。
【０１１８】
なお、ここでは、サーバ１０がユーザ端末２０からアクセス要求を受け付けた場合に、Ｓ１０１〜１０３の処理が実行され、トンプソンサンプリング法で選択されるコンテンツが特定される場合を説明したが、サーバ１０は、当該コンテンツを予め特定しておき、当該コンテンツのコンテンツＩＤを記憶部１２に記録しておいてもよい。この場合、サーバ１０は、Ｓ１０１〜Ｓ１０３の処理を省略してもよい。
【０１１９】
制御部１１は、パラメータεに基づいて、トンプソンサンプリング法でコンテンツを選択するかを決定する（Ｓ１０４）。Ｓ１０４においては、制御部１１は、（１−ε）の確率で、トンプソンサンプリング法でコンテンツを選択すると決定し、εの確率で、トンプソンサンプリング法では選択されないコンテンツを選択すると決定する。別の言い方をすれば、制御部１１は、イプシロングリーディ法に基づいて、トンプソンサンプリング法に基づく活用を行うか、トンプソンサンプリング法に基づかずに探求を行うか、を決定する。
【０１２０】
トンプソンサンプリング法でコンテンツを選択すると決定された場合（Ｓ１０４；Ｙ）、制御部１１は、コンテンツデータベースＤＢに基づいて、ユーザ端末２０に対し、Ｓ１０３で特定したコンテンツを選択して送信する（Ｓ１０５）。Ｓ１０５においては、制御部１１は、コンテンツデータベースＤＢを参照し、Ｓ１０３で特定したコンテンツの実データを取得して送信する。
【０１２１】
一方、トンプソンサンプリング法では選択されないコンテンツを選択すると決定された場合（Ｓ１０４；Ｎ）、制御部１１は、コンテンツデータベースＤＢに基づいて、ユーザ端末２０に対し、Ｓ１０３で特定したコンテンツではない方のコンテンツを選択して送信する（Ｓ１０６）。Ｓ１０６においては、制御部１１は、コンテンツデータベースＤＢを参照し、Ｓ１０３で特定したコンテンツではない方のコンテンツの実データを取得して送信する。
【０１２２】
ユーザ端末２０においては、コンテンツを受信すると、制御部２１は、当該コンテンツを表示部２５に表示させる（Ｓ１０７）。Ｓ１０７においては、制御部２１は、受信したコンテンツを選択可能な状態で表示部２５に表示させる。以降、コンテンツを選択するための操作が受け付けられる。
【０１２３】
制御部２１は、操作部２４の検出信号に基づいて、コンテンツが選択されたかを判定する（Ｓ１０８）。コンテンツが選択されたと判定された場合（Ｓ１０８；Ｙ）、制御部２１は、サーバ１０に対し、コンテンツが選択されたことを示す通知を送信する（Ｓ１０９）。一方、コンテンツが選択されたと判定されない場合（Ｓ１０８；Ｎ）、通知は送信されない。
【０１２４】
サーバ１０においては、制御部１１は、通知を受信したかを判定する（Ｓ１１０）。通知を受信したと判定された場合（Ｓ１１０；Ｙ）、制御部１１は、コンテンツデータベースＤＢに格納された、コンテンツのクリック数を増加させ（Ｓ１１１）、本処理は終了する。Ｓ１１１において増加されたクリック数は、次回の本処理で参照される。
【０１２５】
一方、通知を受信しないと判定された場合（Ｓ１１０；Ｎ）、制御部１１は、コンテンツデータベースＤＢに格納された、コンテンツの非クリック数を増加させ（Ｓ１１２）、本処理は終了する。Ｓ１１２において増加された回数は、次回の本処理で参照される。
【０１２６】
以上説明した選択システム１によれば、トンプソンサンプリング法で選択されるコンテンツだけではなく、トンプソンサンプリング法では選択されないコンテンツも選択し、コンテンツに対するユーザの行動に基づいてベータ分布を更新することにより、トンプソンサンプリング法では選択されないコンテンツのクリック率の変化がベータ分布に反映されるので、当該コンテンツのクリック率の変化を迅速に特定し、バンディットアルゴリズムにおけるリグレットを低減することができる。例えば、トンプソンサンプリング法で選択されるコンテンツを予め特定しておき、サーバ１０がユーザ端末２０からのアクセス要求を受け付けた場合にＳ１０１〜Ｓ１０３の処理を省略する場合には、サーバ１０の処理負荷を軽減することができ、コンテンツを提示する処理を高速化することができる。
【０１２７】
また、トンプソンサンプリング法で選択するコンテンツの割合を、トンプソンサンプリング法では選択されないコンテンツの割合よりも多くすることで、クリック率が低いコンテンツのクリック率の変化を監視しつつ、クリック率が高いコンテンツをより多く選択し、バンディットアルゴリズムにおけるリグレットをより効果的に低減することができる。
【０１２８】
また、確率情報として確率分布を利用し、確率分布に基づいて、コンテンツを選択することで、クリック率が高いコンテンツを精度よく選択し、バンディットアルゴリズムにおけるリグレットをより効果的に低減することができる。
【０１２９】
また、確率分布としてベータ分布を利用し、所定の基準としてトンプソンサンプリング法における基準を利用することで、クリック率の高いコンテンツを精度よく選択し、バンディットアルゴリズムにおけるリグレットをより効果的に低減することができる。
【０１３０】
また、パラメータεに応じた割合で、トンプソンサンプリング法では選択されないコンテンツを選択することで、探求のためにクリック率が低いコンテンツが選択されすぎてしまうことを防止し、クリック率が高いコンテンツを精度よく選択し、バンディットアルゴリズムにおけるリグレットをより効果的に低減することができる。
【０１３１】
また、選択肢としてコンテンツを適用し、ユーザがコンテンツを選択することを所定の事象とすることで、コンテンツのクリック率を効果的に上げることができる。
【０１３２】
［５．変形例］
なお、本発明は、以上に説明した実施形態に限定されるものではない。本発明の趣旨を逸脱しない範囲で、適宜変更可能である。
【０１３３】
（１）例えば、実施形態では、パラメータεを固定値としたが、パラメータεは、可変値であってもよい。例えば、トレンド（ユーザの嗜好）の変化が大きい場合には、それまでの結果で推定したクリック率の精度は低いので、ダイナミックバンディットアルゴリズムは、パラメータεを大きくして探求を高頻度で行ってもよい。
【０１３４】
選択部１０２は、各コンテンツにより得られた事象の時系列的な変化に基づいて、トンプソンサンプリング法では選択されないコンテンツを選択する割合を決定する。事象の時系列的な変化とは、事象の変化の大きさである。ここでは、ユーザがコンテンツを選択することが事象に相当するので、クリック率の変化が、事象の時系列的な変化に相当する。
【０１３５】
本変形例では、コンテンツデータベースＤＢに、各コンテンツのクリック率が時系列的に格納されるものとする。例えば、サーバ１０は、一定期間ごとに、各コンテンツのクリック数を、当該コンテンツのクリック数と非クリック数の合計数で割った値をクリック率として算出し、コンテンツデータベースに格納する。他にも例えば、サーバ１０は、一定期間ごとに、各コンテンツのクリック数と非クリック数とをコンテンツデータベースＤＢに格納し、各期間のクリック率を計算してもよい。
【０１３６】
選択部１０２は、コンテンツデータベースＤＢに時系列的に格納されたクリック率を参照し、クリック率の変化量を取得する。選択部１０２は、クリック率の変化量が多いほど、トンプソンサンプリング法では選択されないコンテンツを選択する割合を高くし、クリック率の変化量が少ないほど、トンプソンサンプリング法では選択されないコンテンツを選択する割合を低くする。別の言い方をすれば、選択部１０２は、クリック率の変化量が少ないほど、トンプソンサンプリング法でコンテンツを選択する割合を高くし、クリック率の変化量が少ないほど、トンプソンサンプリング法でコンテンツを選択する割合を低くする。例えば、選択部１０２は、クリック率の変化量が多いほどパラメータεを高くし、クリック率の変化量が少ないほどパラメータεを低くする。
【０１３７】
変形例（１）によれば、各コンテンツにより得られた事象の時系列的な変化に基づいて、トンプソンサンプリング法では選択されないコンテンツを選択する割合を決定することで、トレンドの変化に対応し、リグレットを効果的に軽減することができる。
【０１３８】
（２）また例えば、実施形態のように時間経過に応じてクリック率が変化する場合、昔に計測されたクリック率よりも、最近計測されたクリック率の方が、直近のトレンドが反映されているので、直近のユーザの行動に重きを置くようにしてもよい。
【０１３９】
本変形例の更新部１０３は、各コンテンツにより得られた事象のうち、新しい事象ほど重み付けを高くして、ベータ分布を更新する。即ち、更新部１０３は、各コンテンツにより得られた事象のうち、古い事象ほど重み付けを低くして、ベータ分布を更新する。
【０１４０】
ここでは、ユーザがコンテンツを選択することが事象に相当し、パラメータα，βを更新することがベータ分布を更新することに相当するので、更新部１０３は、パラメータα，βを更新する場合に、最近の行動の重み付けを高くし、昔の行動の重み付けを低くする。例えば、更新部１０３は、パラメータα，βを計算するための計算式の係数を、新しい行動ほど高くして古い行動ほど低くする。
【０１４１】
変形例（２）によれば、各コンテンツにより得られた事象のうち、新しい事象ほど重み付けを高くしてベータ分布を更新することで、直近のトレンドをベータ分布に強く反映し、リグレットを効果的に軽減することができる。
【０１４２】
（３）また例えば、変形例（２）で説明した方法以外にも、直近のトレンドに重きを置くために、更新部１０３は、各コンテンツにより得られた事象のうち、直近の一部の期間における事象に基づいて、ベータ分布を更新してもよい。即ち、更新部１０３は、直近の一部の期間よりも前の期間における事象は参照せず、直近の一部の期間における事象に基づいて、ベータ分布を更新してもよい。直近の一部の期間は、現時点に近い期間であればよく、例えば、数分〜数時間であってもよいし、１日〜数か月程度であってもよい。
【０１４３】
変形例（３）によれば、各コンテンツにより得られた事象のうち、直近の一部の期間における事象に基づいてベータ分布を更新することで、直近のトレンドをベータ分布に強く反映し、リグレットを効果的に軽減することができる。
【０１４４】
（４）また例えば、上記変形例のうちの２つ以上を組み合わせてもよい。
【０１４５】
また例えば、選択部１０２は、特にパラメータεを利用せずに、トンプソンサンプリング法では選択されないコンテンツを選択してもよい。例えば、ある一定期間の間に、トンプソンサンプリング法では選択されないコンテンツを選択する選択数を定めておき、選択部１０２は、当該期間において、当該選択数だけ、トンプソンサンプリング法では選択されないコンテンツを選択してもよい。また例えば、選択部１０２は、各コンテンツのパラメータα，βを補正し、クリック率が相対的に低い方のコンテンツが選択されやすくするようにしてもよい。この場合、選択部１０２は、クリック率が相対的に高いコンテンツのパラメータαを下げてパラメータβを上げてもよいし、クリック率が相対的に低いコンテンツのパラメータαを上げてパラメータβを下げてもよい。
【０１４６】
また例えば、選択部１０２は、各コンテンツを選択する割合ＲＡ，ＲＢを予め計算し、割合ＲＡ，ＲＢをコンテンツデータベースＤＢに格納しておいてもよい。この場合、選択部１０２は、ユーザ端末２０がサーバ１０にアクセスした場合に、コンテンツデータベースＤＢに格納された割合ＲＡ，ＲＢに基づいて、コンテンツを選択してもよい。即ち、選択部１０２は、予め計算された割合ＲＡ，ＲＢに基づいて、コンテンツを選択してもよい。予め割合ＲＡ，ＲＢを計算しておくことで、ユーザ端末２０からのアクセス要求を受け付けるたびにベータ分布を取得したりトンプソンサンプリング法でコンテンツを選択したりする処理を省くことができるので、サーバ１０の処理負荷を軽減し、コンテンツを提示する処理を高速化することができる。
【０１４７】
また例えば、コンテンツを２つとして説明したが、選択部１０２は、３つ以上のコンテンツの中からコンテンツを選択してもよい。例えば、実施形態で説明したコンテンツＡ，Ｂに加えて、最初はクリック率が低いが時間経過に応じて徐々に上がるコンテンツＣの３つが存在したとすると、序盤において、選択部１０２は、（１−ε）の確率でコンテンツＡを選択し、εの確率でコンテンツＢ又はＣの何れかをランダムに選択してもよい。コンテンツが４つ以上の場合も同様に、選択部１０２は、トンプソンサンプリング法で選択されるコンテンツだけでなく、トンプソンサンプリング法では選択されないコンテンツも選択するようにすればよい。
【０１４８】
また例えば、データ記憶部１００は、選択システム１に含まれている必要はなく、データベースサーバによって実現されてもよい。また例えば、サーバ１０で実現されるものとして説明した機能は、サーバ１０とユーザ端末２０との間で分担されるようにしてもよい。例えば、取得部１０１がユーザ端末２０で実現されてもよい。この場合、取得部１０１は、制御部２１を主として実現される。ユーザ端末２０の取得部１０１は、各コンテンツのクリック率に基づいてベータ分布を取得する。また例えば、選択部１０２がユーザ端末２０で実現されてもよい。この場合、選択部１０２は、制御部２１を主として実現される。ユーザ端末２０の選択部１０２は、サーバ１０からコンテンツデータベースＤＢの内容を取得し、コンテンツを選択する。また例えば、更新部１０３がユーザ端末２０で実現されてもよい。この場合、更新部１０３は、サーバ１０に対してクリック数又は非クリック数の更新指示を送信する。また例えば、取得部１０１、選択部１０２、及び更新部１０３の各々は、サーバ１０及びユーザ端末２０以外のコンピュータで実現されるようにしてもよい。
【符号の説明】
【０１４９】
１  選択システム、１０  サーバ、２０  ユーザ端末、１１，２１  制御部、１２，２２  記憶部、１３，２３  通信部、２４  操作部、２５  表示部、Ａ，Ｂ，Ｃ  コンテンツ、Ｎ  ネットワーク、ＤＢ  コンテンツデータベース、ＩＣ  総クリック数、Ｐ１，Ｐ２  ベータ分布、ＲＡ，ＲＢ，ＲＡＴ，ＲＢＴ  割合、ＲＣ  総クリック数、Ｔ１，Ｔ２  期間、１００  データ記憶部、１０１  取得部、１０２  選択部、１０３  更新部、ＣＴＲ１，ＣＴＲ２  クリック率。
【図１】
2020009283.tif 000003
【図２】
2020009283.tif 000004
【図３】
2020009283.tif 000005
【図４】
2020009283.tif 000006
【図５】
2020009283.tif 000007
【図６】
2020009283.tif 000008
【図７】
2020009283.tif 000009
【図８】
2020009283.tif 000010
【図９】
2020009283.tif 000011
【図１０】
2020009283.tif 000012
【図１１】
2020009283.tif 000013