JP6145766B2 - 解探索システム、解探索プログラム - Google Patents

Description

本発明は、組み合わせ報酬最大化問題の解を高速かつ効率的に導く上で好適な解探索システム、解探索プログラムに関するものである。

従来より、期待値を最大化する解を探索する問題の代表例として、バンディット問題がある。このバンディット問題とは、貰える合計報酬の期待値を最大化することを目的とし、プレイヤーはn種類の異なる行動選択肢から一つの選択肢を選択する動作を繰り返す。各選択の後は毎回、選択した行動に依存する確率分布から選ばれた結果がプレイヤーの報酬として与えられる。

仮に複数のスロットマシーンが存在し、各スロットマシーンのレバーを引くことにより、ある確率分布の下でコイン（報酬）がもらえるものとする。このコインが出る確率分布（当選確率）がスロットマシーン毎に異なる場合であって、かつプレイヤーはその当選確率が分からない場合を考えてみる。このとき、各スロットマシーンの当選確率を知る最も一般的な方法としては、とりあえず各スロットマシーンを多数回に亘り順にプレイし、実際に最も報酬が大きかったスロットマシーンが、最も当選確率が高いものと判断する。

しかしながら、かかる方法では、実際に最も当選確率の高いスロットマシーンを特定する上で相当の回数に亘りスロットマシーンをプレイしなければならず、結果として多くの投資が必要となる。このため、各スロットマシーンにおける当選確率を調べる上で極力投資を少なくしつつ、効率的に解を探索できるアルゴリズムを考える必要が出てくることが分かる。

かかる場合には、上述のような貰える合計報酬の期待値を最大化するバンディット問題に置き換えて、これを解くことができる（例えば、非特許文献１参照。）。特にこのバンディット問題の中で、n種類の異なる行動選択肢から最良の結果の出力が期待される組み合わせを選択する、いわゆる組み合わせバンディット問題も近年において注目されている。この組み合わせバンディット問題では、複数台のスロットマシーンの中からより高配当が期待できるスロットマシーンの組み合わせを選択する場合のみならず、例えばコグニティブ無線通信においてデータ伝送量を最大化できるチャネルの最適な組み合わせの選択、インターネット広告においてクリック数を最大化できる広告の最適な組み合わせ、更には最も投資リターンの大きい金融商品のポートフォリオの選択等、様々な分野においてニーズがある。このような応用例の場合には、より一般的な組み合わせ報酬最大化問題になる。つまり、プレイヤーが多数で、それぞれのプレイヤーの選択に依存して（例えばペイオフ行列によって）各プレイヤーの報酬量が決定される。しかし、本明細書では簡単のために、各スロットマシーンが独立な場合の、組み合わせ報酬最大化問題（特に２つの組み合わせ）について例を挙げて説明する。

S.J.Kim,M.Aono,M.Hara, BioSystems 101,29-36 (2010)

しかしながら、従来において、組み合わせバンディット問題の解を自動的に探索して求めるためのアルゴリズムが特段提案されていなかった。情報量が増大の一途を辿る昨今において、大量の情報から高速かつ効率的に、組み合わせバンディット問題の解を求めるための社会的要請が高くなると考えられるが、これについて特段の解決策が提案されていないのが現状であった。

本発明は、上述した問題点に鑑みて案出されたものであり、その目的とするところは、高速かつ効率的に組み合わせバンディット問題の解を求めることが可能な解探索システム、解探索プログラムを提供することにある。

本発明を適用した解探索システムは、上述した課題を解決するために、確率分布に基づいて結果を出力する２以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索システムにおいて、上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較手段と、上記戦績優劣比較手段により比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御手段と、上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示手段とを備え、上記出力指示手段は、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている１以上の被検対象を、探索解として特定する解探索システムことを特徴とする。

本発明を適用した組み合わせ探索プログラムは、確率分布に基づいて結果を出力する２以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索プログラムにおいて、上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較ステップと、上記戦績優劣比較ステップにより比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御ステップと、上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示ステップとを有し、上記出力指示ステップでは、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている１以上被検対象を、探索解として特定することをコンピュータに実行させることを特徴とする。

上述した構成からなる本発明によれば、被検対象から出力された今までの戦績の優劣と、被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させ、この計量変数の値に応じて結果の出力を指示するか否かを決定する。そして、結果の出力の指示の繰り返しを経て最終的に最も結果の出力の指示が行われている被検対象の組み合わせを、探索すべき組み合わせとして特定する。これにより、組み合わせバンディット問題の解を自動的に探索して求めることが可能となり、情報量が増大の一途を辿る昨今において、大量の情報から高速かつ効率的に、組み合わせバンディット問題の解を求めることが可能となる。

本発明を適用した解探索システムの全体構成を示す図である。 計量変数について説明するための図である。 本発明を適用した解探索システムの他の全体構成例を示す図である。 本発明を適用した解探索システムを、コンピュータプログラムで実現した場合における実施例を示す図である。 被検対象の当選確率が、０．２、０．５、０．８の３つのサンプルについての組み合わせを選択するシミュレーションを行う例を示す図である。

以下、本発明を適用した解探索システムについて図面を参照しながら詳細に説明をする。

図１は、本発明を適用した解探索システム解探索システム１の全体構成を示している。この解探索システム１は、２以上の被検対象５ａ〜５ｄのうち最良の結果の出力が期待される被検対象５の組み合わせを探索するシステムである。解探索システム１は、戦績優劣比較部２と、この戦績優劣比較部２に接続された制御部３ａ〜３ｄと、制御部３ａ〜３ｄに接続された出力指示部４ａ〜４ｄとを備えている。

ちなみに、この制御部３ａ〜３ｄ、出力指示部４ａ〜４ｄは、それぞれ被検対象５の数と同等となるように設けられるものであり、図１の例では４個の被検対象５からなるため、これら制御部３、出力指示部４も４個ずつで構成される。

被検対象５は、それぞれ設定された確率分布に基づいて結果を出力する対象物である。例えば、スロットマシーンやパチンコの台のように、設定された確率分布に基づいてコインという結果物を出力するものであってもよい。また、コグニティブ無線通信は、各チャネルのデータ伝送量の大小は、その都度変化するものであるが、これについてもある時点において設定された確率分布で表現することができる。このようなコグニティブ無線通信において任意のチャネルを選択した場合に、実際の“データ伝送量”という結果物を出力する。また、インターネット広告についても、掲載すべき広告のクリック数の大小は確率分布で表すことが可能となり、“実際のクリック数”という結果物はその確率分布に基づいて算出することが可能となる。また、金融商品については、その将来的な投資リターンも確率分布で表すことができ、“実際の投資リターン”という結果物も当該確率分布に基づいて表される。

このように、被検対象５は、出力する結果を確率分布に変換することが可能なあらゆる事象、物、システム、プログラムやアルゴリズムを含む概念である。ちなみに、この被検対象５において出力される結果の確率分布は、通常の正規分布、ガウシアン分布のみならず、離散的な分布であってもよいし、２項分布で構成されていてもよい。ちなみに、この被検対象５の確率分布は、この解探索システム１のユーザにとって未知のものとなっている。ユーザは、これらの被検対象のうち、最良の結果の出力が期待される被検対象の組み合わせを探索するためにこの解探索システム１を使用することとなる。

被検対象５ａ〜５ｄは、それぞれ設定された確率分布に基づいて結果ｌを出力する。ことき、被検対象５ａから出力される結果を結果ｌ₁とし、被検対象５ｂから出力される結果を結果ｌ₂とし、被検対象５ｃから出力される結果を結果ｌ₃とし、被検対象５ｄから出力される結果を結果ｌ₄とする。出力された結果ｌ₁は、戦績優劣比較部２へと送信されると共に、制御部３ａへ送信される。出力された結果ｌ₂は、戦績優劣比較部２へと送信されると共に、制御部３ｂへ送信される。出力された結果ｌ₃は、戦績優劣比較部２へと送信されると共に、制御部３ｃへ送信される。出力された結果ｌ₄は、戦績優劣比較部２へと送信されると共に、制御部３ｄへ送信される。

戦績優劣比較部２は、被検対象５ａ〜５ｄから出力される結果ｌ₁〜ｌ₄を受信し、これを記憶する。この戦績優劣比較部２は、被検対象５ａ〜５ｄから結果ｌ₁〜ｌ₄を受信する都度、順次記憶しておくことで、結果を蓄積する。そして、この戦績優劣比較部２は、被検対象５ａ〜５ｄ毎に、出力された結果の蓄積に基づく今までの戦績をそれぞれ求める。ここでいう戦績とは、被検対象５から出力される結果がより優れているのか、或いはより劣っているのかを示すあらゆるデータを示すものである。被検対象５がスロットマシーンであれば、コインがどの程度出たかを示すものであってもよいし、被検対象５がインターネット広告であれば、クリックがどの程度行われたかを示すデータであってもよい。また、この戦績優劣比較部２は、各被検対象５の戦績を被検対象５全体の戦績との関係においてその優劣を比較する。ここで被検対象５ａについての被検対象５全体の優劣をｓ₁ ^tとし、被検対象５ｂについての被検対象５全体の優劣をｓ₂ ^tとし、被検対象５ｃについての被検対象５全体の優劣をｓ₃ ^tとし、被検対象５ｄについての被検対象５全体の優劣をｓ₄ ^tとする。これら優劣ｓ₁ ^tは、制御部３ａに、優劣ｓ₂ ^tは、制御部３ｂに、優劣ｓ₃ ^tは、制御部３ｃに、優劣ｓ₄ ^tは、制御部３ｄにそれぞれ送られる。

制御部３ａ〜３ｄは、それぞれ戦績優劣比較部２から、戦績の優劣に関する情報ｓ₁ ^t〜ｓ₄ ^tがそれぞれ入力されるとともに、被検対象５ａ〜５ｄから直近の結果ｌ₁〜ｌ₄がそれぞれ入力される。制御部３ａ〜３ｄは、それぞれ入力された戦績の優劣に関する情報ｓ₁ ^t〜ｓ₄ ^tと、被検対象から出力された直近の結果とに基づいて計量変数を増加又は減少させるように制御する。

図２は、この計量変数のイメージを説明するための図である。計量変数ｘ^tは、各被検対象５に対してそれぞれ個別に割り当てられたパラメータであり、被検対象５を選択するか否かの判断する上での基準となるものである。この計量変数ｘ^tが高いほど、その被検対象５を選択する可能性が高くなる。一方、この計量変数ｘ^tが低いほどその被検対象５を選択しない可能性が高くなる。

このような計量変数ｘ^tの増減を制御するのが、制御部３である。つまり制御部３ａは、結果ｌ₁と優劣ｓ₁ ^tとに基づいて計量変数ｘ₁ ^tの増減を制御し、制御部３ｂは、結果ｌ₂と優劣ｓ₂ ^tとに基づいて計量変数ｘ₂ ^tの増減を制御し、制御部３ｃは、結果ｌ₃と優劣ｓ₃ ^tとに基づいて計量変数ｘ₃ ^tの増減を制御し、制御部３ｄは、結果ｌ₄と優劣ｓ₄ ^tとに基づいて計量変数ｘ₄ ^tの増減を制御する。これら制御部３による計量変数ｘ^tの制御は、あくまで結果ｌと、優劣ｓ^tに基づくものであればいかなるものであってもよい。

出力指示部４ａ〜４ｄは、計量変数を監視し、予め設定した閾値を超えるか否かを判別する。そして、計量変数が閾値を超えた旨を判別した場合には、被検対象５に対して結果の出力を指示する。この図２の例では、閾値を超えた計量変数は、ｘ₂ ^tとｘ₄ ^tである。このため、ｘ₂ ^tを監視する出力指示部４ｂと、ｘ₄ ^tを監視する出力指示部４ｄは、被検対象５ｂ、５ｄに対して結果の出力を指示する。

このようにして、被検対象５を中心として、戦績優劣比較部２、制御部３、出力指示部４の順でいわゆるフィードバック制御が行われる。このような戦績優劣比較部２、制御部３、出力指示部４からなる解探索システム１は、例えば、アナログ回路、デジタル回路を始めとしたいかなるデバイスで具現化されるものであってもよい。ちなみに、回路として具現化される場合には、FPGA(field-programmable gate array)に基づいて、構成を設定するようにしてもよい。また、本発明はプログラムで具現化されるものであってもよい。かかる場合には、戦績優劣比較部２は、これと同様の処理を実行する戦績優劣比較ステップに、制御部３は、これと同様の処理を実行する制御ステップに、出力指示部４は、これと同様の処理を実行する出力指示ステップとして具現化されることとなる。これに加えて、このようなプログラムに基づいて動作するハードウェア（例えば、パーソナルコンピュータ、各種携帯情報端末等）を介して具現化されるものであってもよい。

次に、本発明を適用した解探索システム１による組み合わせ探索動作について説明をする。

先ず、被検対象５ａ〜５ｄのいくつかについて結果の出力が行われる。この結果の出力が指示されるのは上述した出力指示部４により出力指示が行われたものに限る。

被検対象５ａ〜５ｄから出力された結果ｌは、それぞれ戦績優劣比較部２へ送られると共に、制御部３へと送られる。戦績優劣比較部２では、この送られてきた結果ｌに基づいて具体的に以下の処理動作を行う。

以下の式（１）におけるｑ_i ^tは、それぞれの被検対象５ａ〜５ｄにおける戦績を示す指数である。この戦績指数ｑ_i ^tのｔは、この解探索システム１におけるフィードバック回数を示している。また、ｉは、図１に示す下付きの数字に対応するものであり、それぞれの被検対象５に対応するものである。つまりｉ毎に、換言すれば被検対象５毎に、この戦績指数ｑ_i ^tを求めていくこととなる。

・・・・・・・（１）

戦績指数ｑ_i ^tは、フィードバックの回数ｔが増加するにつれて順次更新される。そして、この戦績指数ｑ_i ^tは、その前のフィードバック回数ｔ−１において求めた戦績指数ｑ_i ^t-1に加えて、Σ以降の項を足すことで表示される。また、この（１）式においてα
は忘却パラメータであり、必要に応じて設定される。

このΣ以降の項において、μは係数である。またρ_i、ρ_jは、より優れた結果を出力
した場合を意味している。ここでρ_iは、これから戦績指数ｑ_i ^tを求めようとする被検対象５が、より優れた結果を出力した場合に“１”となり、より劣る結果を出力した場合には、“０”となる。ρ_jは、ｊに相当する他の被検対象５が、より優れた結果を出力した場合に“１”となり、より劣る結果を出力した場合には、“０”となる。本明細では、例として、２つの組み合わせを選択するためのシステムであることからρは２変数となっている。

表１は、ρ、πの取り得る値を示している。

式（１）の括弧内は、ρ_i・ρ_jのように乗算で表されることから、ρ_iとρ_jの双方が１である場合のみプラスになる。

また、πは、ｉ、ｊ以外の他の被検対象５が、より劣った結果を出力した場合に“１”となり、より優れた結果を出力した場合に“０”となる。

即ち、この（１）式の括弧内は、そのｑ_i ^tを求める被検対象５が、より優れた結果を出力した場合と、当該ｑ_i ^tを求める被検対象５以外の他の被検対象５が、より劣った結果を出力した場合に、その数値が上昇することになっている。仮に被検対象５がスロットマシーンである場合には、当該ｑ_i ^tを求めるスロットマシーンが当選した場合には、（１）式の括弧内の数値を上昇させ、当該ｑ_i ^tを求めるスロットマシーンが落選した場合には、（１）式の括弧内の数値を変化させない。また、当該ｑ_i ^tを求めるスロットマシーン以外が当選した場合には、（１）式の括弧内の数値を変化させず、当該ｑ_i ^tを求めるスロットマシーン以外が落選した場合には、（１）式の括弧内の数値を上昇させる。そして、（１）式の括弧内の数値が上昇するにつれて戦績指数ｑ_i ^tが上昇し、より優れた戦績になる。

このように、本発明では、ｑ_i ^tを求める一の被検対象５が、より優れた結果を出力した場合及び他の被検対象がより劣る結果を出力した場合に、当該一の被検対象５における今までの戦績ｑ_i ^tをより優れる側に向上させる。また、ｑ_i ^tを求める一の被検対象５が、より劣った結果を出力した場合及び他の被検対象がより優れた結果を出力した場合に、当該一の被検対象５における今までの戦績ｑ_i ^tを変化させない。戦績優劣比較部２は、このような制御を行うものであってもよく、上述した（１）式に基づく制御を行う場合に限定されるものではない。

また、何れの出力結果が優れており、何れの出力結果が劣っているかについては、いかなる基準の下で判断するようにしてもよい。上述したスロットマシーンの例では、コインが出るか否かで優劣を決める場合に限定されるものではなく、コインの枚数や種別に応じて優劣を決めるようにしてもよい。また、この優劣についても、優れているか、或いは劣っているかの２段階で設定される場合に限定されるものではなく、３段階以上で優劣を評価するようにしてもよい。ちなみに、３段階以上で優劣をランク分けする場合においても、一の被検対象５がより上位ランクであるほどｑ_i ^tを上昇させ、他の被検対象５がより下位ランクであるほどｑ_i ^tを下降させるように調整を行う。

戦績優劣比較部２は、このようにして、各被検対象５ａ〜５ｄについてそれぞれ戦績指数ｑ₁ ^t〜ｑ₄ ^tを求めた後、その戦績指数ｑ₁ ^t〜ｑ₄ ^tを被検対象全体５の戦績との関係においてその優劣を比較する。そして、この優劣の比較結果としての内部リソース値ｓ_i ^tをそれぞれ出力する。

かかる場合に、（２）式に基づいてその優劣を比較するようにしてもよい。

・・・・・・・（２）

式（２）は、一の被検対象５の戦績ｑ_i ^t-1と被検対象５全体の戦績ｑ_k ^t-1の平均との差分を、内部リソース値ｓ_i ^tとしている。例えば、被検対象５ａについての内部リソース値ｓ₁ ^tを求める場合には、その戦績ｑ₁ ^t-1と、全被検対象の戦績ｑ₁ ^t-1、ｑ₂ ^t-1、ｑ₃ ^t-1、ｑ₄ ^t-1の平均との差分を求める。ちなみに、（２）式の右項においてｘ₀ ^tはあくまで調整値であり、必須のものではない。 この（２）式に基づいて、内部リソース値ｓ_i ^tを判断する場合に限定されるものではない。内部リソース値ｓ_i ^tは、それに対応する一の被検対象５の戦績ｑ_i ^t-1が、他の被検対象５との間で相対的に優れているか否かを示すものであれば、いかなる計算式で、或いはいかなる方法で、これを評価するようにしてもよい。戦績優劣比較部２は、これら計算したｓ₁ ^t〜ｓ₄ ^tをそれぞれ、制御部３ａ〜３ｄへ出力する。

制御部３ａ〜３ｄは、これらｓ₁ ^t〜ｓ₄ ^t並びに被検対象５ａ〜５ｄから直近の結果ｌ₁ ^t〜ｌ₄ ^tがそれぞれ入力された場合に、例えば、以下の制御を行う。

表２は、この制御部３による制御を行う上で参酌するテーブルの例を示している。

この表２によれば、制御部３は、内部リソース値ｓ_i ^tと、被検対象５から出力された直近の結果ｌ_i ^tとより形成されるマトリクスに基づいて、制御方法を決定する。ここでｌ_i ^t＝−１は、より優れた結果が出力された場合を意味している。また、ｌ_i ^t＝１は、より劣った結果が出力された場合を意味している。ちなみに、このｌ_i ^tの優劣の基準についてもいかなるものであってもよい。

また、表中の数値（−１、０、１）の意味については、先ず“−１”は、計量変数ｘを成長速度を減少させるように制御する。また、“０”は、計量変数ｘ^tの成長速度を特に増減させないことを意味し、“１”は、計量変数ｘ^tの成長速度を増加させるように制御する。

ちなみに以下の例では、ｘ₀ ^tは、ｘ_iの値によって決まるものと仮定している。

制御部３は、この表２に基づいて具体的に以下の制御を行う。

内部リソース値ｓ_i ^tが正で、被検対象５から出力された直近の結果ｌ_i ^tがより優れたものである場合（＝−１）には、“１”であることから計量変数ｘ^tの成長速度を増加させる。内部リソース値ｓ_i ^tが正で、被検対象５から出力された直近の結果ｌ_i ^tがより劣るものである場合（＝１）には、“０”であることから計量変数ｘ^tの成長速度を増加させることなくそのままにする。内部リソース値ｓ_i ^tが０で、被検対象５から出力された直近の結果ｌ_i ^tがより優れたものである場合（＝−１）には、“１”であることから計量変数計量変数ｘ^tの成長速度を増加させる。内部リソース値ｓ_i ^tが０で、被検対象５から出力された直近の結果ｌ_i ^tがより劣るものである場合（＝１）には、“−１”であることから計量変数計量変数ｘ^tの成長速度を減少させる。内部リソース値ｓ_i ^tが負で、被検対象５から出力された直近の結果ｌ_i ^tがより優れたものである場合（＝−１）には、“０”であることから計量変数計量変数ｘ^tの成長速度をそのままにし、内部リソース値ｓ_i ^tが負で、被検対象５から出力された直近の結果ｌ_i ^tがより劣るものである場合（＝１）には、“−１”であることから計量変数計量変数ｘ^tの成長速度を減少させる。

このようにして制御部３は、戦績優劣比較部２により比較された戦績の優劣に基づく内部リソース値ｓ_i ^tと、被検対象５から出力された直近の結果ｌ_i ^tとに基づいて、計量変数ｘ^tを増加又は減少させるように制御する。ちなみに表２中の数値はあくまで一例であり、内部リソース値ｓ_i ^tと直近の結果ｌ_i ^tとに基づくものであればいかなる数値であってもよい。

また、上述した例では、内部リソース値ｓ_i ^tを３段階で表示し、直近の結果ｌ_i ^tを２段階で表示し、合計２×３のマトリックスで表示しているが、これに限定されるものではなく、ｓ_i ^t、ｌ_i ^tともに最低２段階であれば何段階でランク分けするようにしてもよい。

さらに、この制御部３は、このようなマトリックス表で制御方法を規定する場合に限定されるものではなく、内部リソース値ｓ_i ^tと直近の結果ｌ_i ^tとに基づくものであれば他のいかなる方法に基づいて計量変数ｘ^tの増減を制御するようにしてもよい。具体的には、内部リソース値ｓ_i ^tと直近の結果ｌ_i ^tとを変数とした所定の演算式に従って制御方法を決めるようにしてもよい。

このようにして制御部により計量変数ｘ^tの増減を制御する結果、図２に示すように、ある被検対象５に対する計量変数ｘ^tは閾値未満であり、ある被検対象５に対する計量変数ｘ^tは閾値以上となる。出力指示部４は、これら軽量パラメータｘ^tをそれぞれ閾値との関係で比較し、閾値を超えた計量変数ｘ^tに応じた被検対象５に対してのみ、結果の出力を指示する。結果の出力を指示された被検対象５は、新たなる結果をそれぞれの確率分布に基づいて出力することとなる。

本発明を適用した解探索システム１では、これらの動作を繰り返し実行する。その結果、出力指示部４により出力指示が出される被検対象５の組み合わせが徐々に一定化されてくる。最終的には、この出力指示が出される被検対象５は、一定のものに収束される。この収束されてくる被検対象５の組み合わせが、解探索システム１により選択されてくる解となる。

ちなみに、解探索システム１により解を求める上で、被検対象５ａ〜５ｄ毎に割り当てられる計量変数ｘ₁〜ｘ₄と、ｘ₀ ^tとの合計が一定となるように制御することで、より探索精度を高めることが可能となる。即ち、ｘ₀ ^t＋ｘ₁＋ｘ₂＋ｘ₃＋ｘ₄＝一定、としておくことにより、計量変数ｘ^tが全体的に大きくなってしまい、閾値との間でバランスが取れなくなるのを防止することができ、これが探索精度の向上につながることとなる。

ｘ₀ ^tは、他の計量変数ｘ_iの値により影響を受ける変数である。上述した処理動作を繰り返し進めていく結果、上述した（２）式において、当初はｘ₀ ^tの項が支配的になり、q_i ^t-1以後の項（一の被検対象５の戦績ｑ_i ^t-1と被検対象５全体の戦績ｑ_k ^t-1の平均との差分）については、あまりこのｓ_i ^tを決定する上で大きな影響を与えるものではない。その結果、このｓ_i ^tは、戦績ｑ_i ^t-1と戦績ｑ_k ^t-1の平均との差分に影響を受けることなく、自由度が高くなり、その分ランダムな値を取りやすくなる。その結果、ランダムな値を取りやすくなるｓ_i ^tを介して様々な出力指示４ａ〜４ｄが行われ、様々な解を探索することが可能となる。

これに対して、ｔが大きくなるにつれ、換言すればフィードバック回数が多くなるにつれ、徐々にq_i ^t-1以後の項（一の被検対象５の戦績ｑ_i ^t-1と被検対象５全体の戦績ｑ_k ^t-1の平均との差分）が大きくなる。その結果、このｓ_i ^tを決定する上で、ｓ_i ^tよりも、戦績ｑ_i ^t-1と戦績ｑ_k ^t-1の平均との差分値が支配的になってくる。そして、次回に出力指示４ａ〜４ｄが行われるものについては、戦績ｑ_i ^t-1と戦績ｑ_k ^t-1の平均との差分値がより影響を受けるものとなる。

このようにして最終的に出力指示が行われるものは、戦績ｑ_i ^t-1と戦績ｑ_k ^t-1の平均との差分値による影響を受けるものに収束されてくる。

上述した構成からなる本発明によれば、被検対象５から出力された今までの戦績の優劣と、被検対象５から出力された直近の結果とに基づいて、計量変数を増加又は減少させ、この計量変数の値に応じて結果の出力を指示するか否かを決定する。そして、結果の出力の指示の繰り返しを経て最終的に最も結果の出力の指示が行われている被検対象５の組み合わせを、探索すべき組み合わせとして特定する。これにより、組み合わせバンディット問題の解を自動的に探索して求めることが可能となり、情報量が増大の一途を辿る昨今において、大量の情報から高速かつ効率的に、組み合わせバンディット問題の解を求めることが可能となる。

なお、本発明は、上述した実施の形態に限定されるものではない。例えば、図３に示すように、２以上の解探索システム１を用いて、被検対象５を探索するようにしてもよい。図３では、２つの解探索システム１ａ、解探索システム１ｂを用いて被検対象５ａ〜５ｄを探索する場合について示している。ちなみに、この２つの解探索システム１ａ、解探索システム１ｂは、互いの同一の被検対象５ａ〜５ｄのグループの探索を行う。換言すれば図中において解探索システム１ｂ側の点線で示されている被検対象５ａ〜５ｄは、解探索システム１ａ側の実線で示されている被検対象５ａ〜５ｄと同一のものである。

このケースでは、被検対象５の数は、２以上であればよい。つまり最低２つの被検対象５のうち、最良の結果の出力が期待される１の被検対象５を選択するものであってもよい。かかる点において、このケースでは、２以上の被検対象５の組み合わせを探索する場合に限定されるものではなく、１の被検対象５を解として探索するものであってもよい。

またこのケースにおいて被検対象５は、予め確率分布が設定されているものに限定されるものではなく、確率分布が時系列的に、つまり時間の経過に応じて変化するものであってもよい。しかも、その被検対象５における時系列的な確率分布の変化が、出力指示部４ａ〜４ｄによる出力指示に対応するものであってもよい。即ち、出力指示部４ｂからの出力指示があった場合、これに対応する被検対象５ｂのみが、当該出力指示に応じて自らの確率分布を変化させ、その変化させた確率分布に基づいて結果を出力する。

更に、各被検対象５による各確率分布の変化は、他の被検対象５による出力と独立ではなく、何らかの相関性を持たせるようにしてもよい。即ち、一の被検対象５ａがより高い確率で当たりを出す確率分布とする場合に、他の一の被検対象５ｂはこれと相関性の高い確率分布を設定するようにしてもよく、更なる他の一の被検対象５ｂは、これと負の相関をもつ確率分布を設定する等してもよい。これらの相関はいかなるもので表現されていてもよい。

このケースでは、２つの解探索システム１ａ、解探索システム１ｂを用いて、上述と同様に解探索を行っていく。出力指示が行われる都度、これに応じて被検対象５の確率分布が時系列的に変化し、しかもその確率分布の変化が、複数の被検対象５との間で独立ではなく互いに相関性を持っている。これらの処理を繰り返し実行することにより、上述と同様に被検対象５の選択が収束され、これが探索解となる。

このケースでは、例えば株等の投資対象を被検対象５に当てはめて考えることもできる。株価は、上昇、下降が、他の株価と相関性を持つことが多々ある。また、出力指示部４により出力指示された場合は、株を買った場合（或いは空売りした場合）と考えることもできるが、仮に解探索システム１ａのみならず、解探索システム１ｂが株を同じ購入した場合には、これに応じて株価が上昇する。これは、上述した出力指示に応じて被検対象５の確率分布が変化することと同様である。

更にこのケースでは、解探索システム１ａ、解探索システム１ｂ間が互いに連関していてもよい。つまり、解探索システム１ａが特定の被検対象５ａを選択した場合、解探索システム１ｂは、被検対象５ｃを選択するように互いに連関するように設定されていてもよい。これにより、例えば株等の投資対象を被検対象５に当てはめる場合において、一の解探索システム１ａが、他の解探索システム１ｂとの間で互いに連関して意思決定を行う場合が多い場合（例えば、Ａ氏がＴ社の株を買った場合に、Ｂ氏は、Ｔ社と業務上の関連性が高いＵ社の株を買う場合）において、その探索精度を向上させることが可能となる。なお、この解探索システム１ａによる出力指示、解探索システム１ｂの出力指示の相関性はいかなるものであってもよい。

また解探索システム１ａ、解探索システム１ｂ間の連関は、互いの制御部３同士が直接的に相互作用するものであってもよい。かかる場合には、上述した解探索システム１ａにおいて計量変数を決める上での演算式を、他の解探索システム１ｂ側にも直接導入することで相関性を持たせるようにしてもよい。

なお、上述した実施形態では、２個の解探索システム１ａ、解探索システム１ｂを用いる場合を例にとり説明をしたが、これに限定されるものではなく２以上であればいかなる数で構成されていてもよい。

図３は、本発明を適用した解探索システム１を、コンピュータプログラムで実現した場合における実施例を示している。コンピュータプログラムで実現するため、戦績優劣比較部２は、これと同様の処理を実行する戦績優劣比較ステップに、制御部３は、これと同様の処理を実行する制御ステップに、出力指示部４は、これと同様の処理を実行する出力指示ステップとして具現化したプログラムを作成した。

被検対象５は、予め設定された確率の下で当選するか落選するかが決まる装置であり、例えばスロットマシーン等を想定している。この被検対象５−１の当選確率＝０．３５、被検対象５−２の当選確率＝０．４５、被検対象５−３の当選確率＝０．５５、被検対象５−４の当選確率＝０．６５とされている。また５−０は、ｘ₀ ^tである。

このうち、当選確率の高い２つの被検対象５の組み合わせ（即ち、被検対象５−３、５−４）を探索解として求めることを行う。

図３の横軸ｔはフィードバック回数である。また、戦績指数ｑ_iは、（１）式に基づいて被検対象５毎に求めている。優劣Ｓ_iは、（２）式に基づいて被検対象５毎に求めている。ａ_iは、表２から導き出される−１、０、１の何れかの数値である。

またｖ_iは、ａ_iに基づいて計量変数を増やす方向に推進させるのか、或いは減らす方向に推進させるのかを決めるパラメータである。仮にａ_iが計量変数を増減させる際の加速度であるとすえれば、このｖ_iは、計量変数の増減速度である。ａ_iは、ｖ_iの１回微分で表すことができる。更に、計量変数ｘ_iは、実際に計量変数の増減速度ｖ_iに基づいて増減させられた実際のパラメータ値である。ここで閾値は０としている。

このようなプログラムによる結果より、フィードバック回数が増加するにつれて、計量変数ｘ_iは、殆ど被検対象５−３、５−４のみが大きくなってそのまま出力指示部４によって出力指示が行われることが繰り返されるのがわかる。

このように本発明を適用したコンピュータプログラムにより、組み合わせバンディット問題を自動的に求めることができることを検証することができた。

図４は、他の実施例ではあるが、それぞれ被検対象５の当選確率が、０．２、０．５、０．８の３つのサンプルについて、本発明を適用したコンピュータプログラムにより、より当選確率の高い組み合わせを選択するシミュレーションを行った結果である。実線が本発明に相当する。比較例１は、ソフトマックスアルゴリズムを組み合わせ報酬最大化問題に拡張したものである。また比較例２は、イプシロングリーディアルゴリズムを組み合わせ報酬最大化問題に拡張したものである。 その結果、本発明を適用したコンピュータプログラムは、フィードバック回数が増加するにつれて、他の比較例よりも正答率が高くなるのが分かる。

１ 解探索システム
２ 戦績優劣比較部
３ 制御部
４ 出力指示部
５ 被検対象

Claims (10)

1. 確率分布に基づいて結果を出力する２以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索システムにおいて、
   上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較手段と、
   上記戦績優劣比較手段により比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御手段と、
   上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示手段とを備え、
   上記出力指示手段は、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている１以上の被検対象を、探索解として特定すること
   を特徴とする解探索システム。
2. それぞれ設定された確率分布に基づいて結果を出力する３以上の被検対象のうち最良の結果の出力が期待される被検対象の組み合わせを探索し、
   上記出力指示手段は、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている被検対象の組み合わせを、探索解として特定すること
   を特徴とする請求項１記載の解探索システム。
3. 上記出力指示手段による出力指示に応じて、時系列的に確率分布が変化する被検対象の組み合わせを探索する上で、２以上の当該解探索システムを用いて解探索を行うこと
   を特徴とする請求項１記載の解探索システム。
4. 上記戦績優劣比較手段は、一の被検対象がより優れた結果を出力した場合及び他の被検対象がより劣る結果を出力した場合に、上記一の被検対象における今までの戦績をより優れる側に向上させ、一の被検対象がより劣った結果を出力した場合及び他の被検対象がより優れた結果を出力した場合に、上記一の被検対象における今までの戦績をより劣る側に下降させること
   を特徴とする請求項１〜３のうち何れか１項記載の解探索システム。
5. 上記戦績優劣比較手段は、上記各被検対象の戦績と被検対象全体の戦績の平均との差分を内部リソース値とし、
   上記制御手段は、
   上記内部リソース値が正で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
   上記内部リソース値が正で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数をそのままにし、
   上記内部リソース値が０で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
   上記内部リソース値が０で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させ、
   上記内部リソース値が負で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数をそのままにし、
   上記内部リソース値が負で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させること
   を特徴とする請求項１〜４のうち何れか１項記載の解探索システム。
6. 上記制御手段は、上記被検対象毎に割り当てられる計量変数の合計が一定となるように制御すること
   を特徴とする請求項１〜５のうち何れか１項記載の解探索システム。
7. 確率分布に基づいて結果を出力する２以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索プログラムにおいて、
   上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較ステップと、
   上記戦績優劣比較ステップにより比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御ステップと、
   上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示ステップとを有し、
   上記出力指示ステップでは、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている１以上被検対象を、探索解として特定すること
   をコンピュータに実行させることを特徴とする解探索プログラム。
8. 上記戦績優劣比較ステップでは、一の被検対象がより優れた結果を出力した場合及び他の被検対象がより劣る結果を出力した場合に、上記一の被検対象における今までの戦績をより優れる側に向上させ、一の被検対象がより劣った結果を出力した場合及び他の被検対象がより優れた結果を出力した場合に、上記一の被検対象における今までの戦績をより劣る側に下降させること
   を特徴とする請求項７記載の解探索プログラム。
9. 上記戦績優劣比較ステップでは、上記各被検対象の戦績と被検対象全体の戦績の平均との差分を内部リソース値とし、
   上記制御ステップでは、
   上記内部リソース値が正で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
   上記内部リソース値が正で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数をそのままにし、
   上記内部リソース値が０で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
   上記内部リソース値が０で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させ、
   上記内部リソース値が負で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数をそのままにし、
   上記内部リソース値が負で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させること
   を特徴とする請求項７又は８記載の解探索プログラム。
10. 上記制御ステップでは、上記被検対象毎に割り当てられる計量変数の合計が一定となるように制御すること
    を特徴とする請求項７〜９のうち何れか１項記載の解探索プログラム。

Images