TOP > 国内特許検索 > 解探索システム、解探索プログラム > 明細書

明細書 :解探索システム、解探索プログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第6145766号 (P6145766)
公開番号 特開2014-191598 (P2014-191598A)
登録日 平成29年5月26日(2017.5.26)
発行日 平成29年6月14日(2017.6.14)
公開日 平成26年10月6日(2014.10.6)
発明の名称または考案の名称 解探索システム、解探索プログラム
国際特許分類 G06Q  50/10        (2012.01)
G06F  19/00        (2011.01)
FI G06Q 50/10
G06F 19/00 120
請求項の数または発明の数 10
全頁数 16
出願番号 特願2013-066768 (P2013-066768)
出願日 平成25年3月27日(2013.3.27)
審査請求日 平成27年11月26日(2015.11.26)
特許権者または実用新案権者 【識別番号】503359821
【氏名又は名称】国立研究開発法人理化学研究所
発明者または考案者 【氏名】金 成主
【氏名】青野 真士
【氏名】行田 悦資
【氏名】原 正彦
個別代理人の代理人 【識別番号】100120868、【弁理士】、【氏名又は名称】安彦 元
審査官 【審査官】松野 広一
参考文献・文献 米国特許出願公開第2008/0140591(US,A1)
AUER, Peter et al,Finite-time Analysis of the Multiarmed Bandit Problem,Machine learning,2002年,Vol.47,pp.235-256
VERMOREL, Joanne`s, MOHRI, Mehryar,Multi-Armed Bandit Algorithms and Empirical Evaluation,In Proceedings of the 16th European Conference on Machine Learning,2005年10月,Vol.3720,pp.437-448,URL,http://www.cs.nyu.edu/~mohri/pub/bandit.pdf
大用 庫智 外2名,非定常N本腕バンディット問題に対する人間の認知バイアスの適用,2011年度人工知能学会全国大会(第25回)論文集 [CD-ROM] 2011年度人工知能学会全国大,日本,2011年 6月 1日,pp.1-4
青野 真士 外4名,粘菌コンピュータと確率探索アルゴリズム,システム/制御/情報,日本,システム制御情報学会,2011年12月15日,Vol.55 No.12,pp.26-31
調査した分野 G06Q 10/00-99/00
G06F 19/00
G06N 3/00
G06N 5/04
特許請求の範囲 【請求項1】
確率分布に基づいて結果を出力する2以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索システムにおいて、
上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較手段と、
上記戦績優劣比較手段により比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御手段と、
上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示手段とを備え、
上記出力指示手段は、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている1以上の被検対象を、探索解として特定すること
を特徴とする解探索システム。
【請求項2】
それぞれ設定された確率分布に基づいて結果を出力する3以上の被検対象のうち最良の結果の出力が期待される被検対象の組み合わせを探索し、
上記出力指示手段は、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている被検対象の組み合わせを、探索解として特定すること
を特徴とする請求項1記載の解探索システム。
【請求項3】
上記出力指示手段による出力指示に応じて、時系列的に確率分布が変化する被検対象の組み合わせを探索する上で、2以上の当該解探索システムを用いて解探索を行うこと
を特徴とする請求項1記載の解探索システム。
【請求項4】
上記戦績優劣比較手段は、一の被検対象がより優れた結果を出力した場合及び他の被検対象がより劣る結果を出力した場合に、上記一の被検対象における今までの戦績をより優れる側に向上させ、一の被検対象がより劣った結果を出力した場合及び他の被検対象がより優れた結果を出力した場合に、上記一の被検対象における今までの戦績をより劣る側に下降させること
を特徴とする請求項1~3のうち何れか1項記載の解探索システム。
【請求項5】
上記戦績優劣比較手段は、上記各被検対象の戦績と被検対象全体の戦績の平均との差分を内部リソース値とし、
上記制御手段は、
上記内部リソース値が正で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
上記内部リソース値が正で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数をそのままにし、
上記内部リソース値が0で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
上記内部リソース値が0で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させ、
上記内部リソース値が負で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数をそのままにし、
上記内部リソース値が負で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させること
を特徴とする請求項1~4のうち何れか1項記載の解探索システム。
【請求項6】
上記制御手段は、上記被検対象毎に割り当てられる計量変数の合計が一定となるように制御すること
を特徴とする請求項1~5のうち何れか1項記載の解探索システム。
【請求項7】
確率分布に基づいて結果を出力する2以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索プログラムにおいて、
上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較ステップと、
上記戦績優劣比較ステップにより比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御ステップと、
上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示ステップとを有し、
上記出力指示ステップでは、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている1以上被検対象を、探索解として特定すること
をコンピュータに実行させることを特徴とする解探索プログラム。
【請求項8】
上記戦績優劣比較ステップでは、一の被検対象がより優れた結果を出力した場合及び他の被検対象がより劣る結果を出力した場合に、上記一の被検対象における今までの戦績をより優れる側に向上させ、一の被検対象がより劣った結果を出力した場合及び他の被検対象がより優れた結果を出力した場合に、上記一の被検対象における今までの戦績をより劣る側に下降させること
を特徴とする請求項7記載の解探索プログラム。
【請求項9】
上記戦績優劣比較ステップでは、上記各被検対象の戦績と被検対象全体の戦績の平均との差分を内部リソース値とし、
上記制御ステップでは、
上記内部リソース値が正で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
上記内部リソース値が正で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数をそのままにし、
上記内部リソース値が0で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数を増加させ、
上記内部リソース値が0で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させ、
上記内部リソース値が負で、上記被検対象から出力された直近の結果がより優れたものである場合には、上記計量変数をそのままにし、
上記内部リソース値が負で、上記被検対象から出力された直近の結果がより劣るものである場合には、上記計量変数を下降させること
を特徴とする請求項7又は8記載の解探索プログラム。
【請求項10】
上記制御ステップでは、上記被検対象毎に割り当てられる計量変数の合計が一定となるように制御すること
を特徴とする請求項7~9のうち何れか1項記載の解探索プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、組み合わせ報酬最大化問題の解を高速かつ効率的に導く上で好適な解探索システム、解探索プログラムに関するものである。
【背景技術】
【0002】
従来より、期待値を最大化する解を探索する問題の代表例として、バンディット問題がある。このバンディット問題とは、貰える合計報酬の期待値を最大化することを目的とし、プレイヤーはn種類の異なる行動選択肢から一つの選択肢を選択する動作を繰り返す。各選択の後は毎回、選択した行動に依存する確率分布から選ばれた結果がプレイヤーの報酬として与えられる。
【0003】
仮に複数のスロットマシーンが存在し、各スロットマシーンのレバーを引くことにより、ある確率分布の下でコイン(報酬)がもらえるものとする。このコインが出る確率分布(当選確率)がスロットマシーン毎に異なる場合であって、かつプレイヤーはその当選確率が分からない場合を考えてみる。このとき、各スロットマシーンの当選確率を知る最も一般的な方法としては、とりあえず各スロットマシーンを多数回に亘り順にプレイし、実際に最も報酬が大きかったスロットマシーンが、最も当選確率が高いものと判断する。
【0004】
しかしながら、かかる方法では、実際に最も当選確率の高いスロットマシーンを特定する上で相当の回数に亘りスロットマシーンをプレイしなければならず、結果として多くの投資が必要となる。このため、各スロットマシーンにおける当選確率を調べる上で極力投資を少なくしつつ、効率的に解を探索できるアルゴリズムを考える必要が出てくることが分かる。
【0005】
かかる場合には、上述のような貰える合計報酬の期待値を最大化するバンディット問題に置き換えて、これを解くことができる(例えば、非特許文献1参照。)。特にこのバンディット問題の中で、n種類の異なる行動選択肢から最良の結果の出力が期待される組み合わせを選択する、いわゆる組み合わせバンディット問題も近年において注目されている。この組み合わせバンディット問題では、複数台のスロットマシーンの中からより高配当が期待できるスロットマシーンの組み合わせを選択する場合のみならず、例えばコグニティブ無線通信においてデータ伝送量を最大化できるチャネルの最適な組み合わせの選択、インターネット広告においてクリック数を最大化できる広告の最適な組み合わせ、更には最も投資リターンの大きい金融商品のポートフォリオの選択等、様々な分野においてニーズがある。このような応用例の場合には、より一般的な組み合わせ報酬最大化問題になる。つまり、プレイヤーが多数で、それぞれのプレイヤーの選択に依存して(例えばペイオフ行列によって)各プレイヤーの報酬量が決定される。しかし、本明細書では簡単のために、各スロットマシーンが独立な場合の、組み合わせ報酬最大化問題(特に2つの組み合わせ)について例を挙げて説明する。
【先行技術文献】
【0006】

【非特許文献1】S.J.Kim,M.Aono,M.Hara, BioSystems 101,29-36 (2010)
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、従来において、組み合わせバンディット問題の解を自動的に探索して求めるためのアルゴリズムが特段提案されていなかった。情報量が増大の一途を辿る昨今において、大量の情報から高速かつ効率的に、組み合わせバンディット問題の解を求めるための社会的要請が高くなると考えられるが、これについて特段の解決策が提案されていないのが現状であった。
【0008】
本発明は、上述した問題点に鑑みて案出されたものであり、その目的とするところは、高速かつ効率的に組み合わせバンディット問題の解を求めることが可能な解探索システム、解探索プログラムを提供することにある。
【課題を解決するための手段】
【0009】
本発明を適用した解探索システムは、上述した課題を解決するために、確率分布に基づいて結果を出力する2以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索システムにおいて、上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較手段と、上記戦績優劣比較手段により比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御手段と、上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示手段とを備え、上記出力指示手段は、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている1以上の被検対象を、探索解として特定する解探索システムことを特徴とする。
【0010】
本発明を適用した組み合わせ探索プログラムは、確率分布に基づいて結果を出力する2以上の被検対象のうち最良の結果の出力が期待される被検対象を探索する解探索プログラムにおいて、上記出力された結果の蓄積に基づく今までの戦績を上記被検対象毎にそれぞれ求め、上記各被検対象の戦績を被検対象全体の戦績との関係においてその優劣を比較する戦績優劣比較ステップと、上記戦績優劣比較ステップにより比較された戦績の優劣と、上記被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象毎に行う制御ステップと、上記計量変数が閾値を超えた上記被検対象に対して結果の出力を指示する出力指示ステップとを有し、上記出力指示ステップでは、上記結果の出力の指示の繰り返しを経て最終的に最も上記結果の出力の指示が行われている1以上被検対象を、探索解として特定することをコンピュータに実行させることを特徴とする。
【発明の効果】
【0012】
上述した構成からなる本発明によれば、被検対象から出力された今までの戦績の優劣と、被検対象から出力された直近の結果とに基づいて、計量変数を増加又は減少させ、この計量変数の値に応じて結果の出力を指示するか否かを決定する。そして、結果の出力の指示の繰り返しを経て最終的に最も結果の出力の指示が行われている被検対象の組み合わせを、探索すべき組み合わせとして特定する。これにより、組み合わせバンディット問題の解を自動的に探索して求めることが可能となり、情報量が増大の一途を辿る昨今において、大量の情報から高速かつ効率的に、組み合わせバンディット問題の解を求めることが可能となる。
【図面の簡単な説明】
【0013】
【図1】本発明を適用した解探索システムの全体構成を示す図である。
【図2】計量変数について説明するための図である。
【図3】本発明を適用した解探索システムの他の全体構成例を示す図である。
【図4】本発明を適用した解探索システムを、コンピュータプログラムで実現した場合における実施例を示す図である。
【図5】被検対象の当選確率が、0.2、0.5、0.8の3つのサンプルについての組み合わせを選択するシミュレーションを行う例を示す図である。
【発明を実施するための形態】
【0014】
以下、本発明を適用した解探索システムについて図面を参照しながら詳細に説明をする。

【0015】
図1は、本発明を適用した解探索システム解探索システム1の全体構成を示している。この解探索システム1は、2以上の被検対象5a~5dのうち最良の結果の出力が期待される被検対象5の組み合わせを探索するシステムである。解探索システム1は、戦績優劣比較部2と、この戦績優劣比較部2に接続された制御部3a~3dと、制御部3a~3dに接続された出力指示部4a~4dとを備えている。

【0016】
ちなみに、この制御部3a~3d、出力指示部4a~4dは、それぞれ被検対象5の数と同等となるように設けられるものであり、図1の例では4個の被検対象5からなるため、これら制御部3、出力指示部4も4個ずつで構成される。

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

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

【0019】
被検対象5a~5dは、それぞれ設定された確率分布に基づいて結果lを出力する。ことき、被検対象5aから出力される結果を結果l1とし、被検対象5bから出力される結果を結果l2とし、被検対象5cから出力される結果を結果l3とし、被検対象5dから出力される結果を結果l4とする。出力された結果l1は、戦績優劣比較部2へと送信されると共に、制御部3aへ送信される。出力された結果l2は、戦績優劣比較部2へと送信されると共に、制御部3bへ送信される。出力された結果l3は、戦績優劣比較部2へと送信されると共に、制御部3cへ送信される。出力された結果l4は、戦績優劣比較部2へと送信されると共に、制御部3dへ送信される。

【0020】
戦績優劣比較部2は、被検対象5a~5dから出力される結果l1~l4を受信し、これを記憶する。この戦績優劣比較部2は、被検対象5a~5dから結果l1~l4を受信する都度、順次記憶しておくことで、結果を蓄積する。そして、この戦績優劣比較部2は、被検対象5a~5d毎に、出力された結果の蓄積に基づく今までの戦績をそれぞれ求める。ここでいう戦績とは、被検対象5から出力される結果がより優れているのか、或いはより劣っているのかを示すあらゆるデータを示すものである。被検対象5がスロットマシーンであれば、コインがどの程度出たかを示すものであってもよいし、被検対象5がインターネット広告であれば、クリックがどの程度行われたかを示すデータであってもよい。また、この戦績優劣比較部2は、各被検対象5の戦績を被検対象5全体の戦績との関係においてその優劣を比較する。ここで被検対象5aについての被検対象5全体の優劣をs1tとし、被検対象5bについての被検対象5全体の優劣をs2tとし、被検対象5cについての被検対象5全体の優劣をs3tとし、被検対象5dについての被検対象5全体の優劣をs4tとする。これら優劣s1tは、制御部3aに、優劣s2tは、制御部3bに、優劣s3tは、制御部3cに、優劣s4tは、制御部3dにそれぞれ送られる。

【0021】
制御部3a~3dは、それぞれ戦績優劣比較部2から、戦績の優劣に関する情報s1t~s4tがそれぞれ入力されるとともに、被検対象5a~5dから直近の結果l1~l4がそれぞれ入力される。制御部3a~3dは、それぞれ入力された戦績の優劣に関する情報s1t~s4tと、被検対象から出力された直近の結果とに基づいて計量変数を増加又は減少させるように制御する。

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

【0023】
このような計量変数xtの増減を制御するのが、制御部3である。つまり制御部3aは、結果l1と優劣s1tとに基づいて計量変数x1tの増減を制御し、制御部3bは、結果l2と優劣s2tとに基づいて計量変数x2tの増減を制御し、制御部3cは、結果l3と優劣s3tとに基づいて計量変数x3tの増減を制御し、制御部3dは、結果l4と優劣s4tとに基づいて計量変数x4tの増減を制御する。これら制御部3による計量変数xtの制御は、あくまで結果lと、優劣stに基づくものであればいかなるものであってもよい。

【0024】
出力指示部4a~4dは、計量変数を監視し、予め設定した閾値を超えるか否かを判別する。そして、計量変数が閾値を超えた旨を判別した場合には、被検対象5に対して結果の出力を指示する。この図2の例では、閾値を超えた計量変数は、x2tとx4tである。このため、x2tを監視する出力指示部4bと、x4tを監視する出力指示部4dは、被検対象5b、5dに対して結果の出力を指示する。

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

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

【0027】
先ず、被検対象5a~5dのいくつかについて結果の出力が行われる。この結果の出力が指示されるのは上述した出力指示部4により出力指示が行われたものに限る。

【0028】
被検対象5a~5dから出力された結果lは、それぞれ戦績優劣比較部2へ送られると共に、制御部3へと送られる。戦績優劣比較部2では、この送られてきた結果lに基づいて具体的に以下の処理動作を行う。

【0029】
以下の式(1)におけるqitは、それぞれの被検対象5a~5dにおける戦績を示す指数である。この戦績指数qitのtは、この解探索システム1におけるフィードバック回数を示している。また、iは、図1に示す下付きの数字に対応するものであり、それぞれの被検対象5に対応するものである。つまりi毎に、換言すれば被検対象5毎に、この戦績指数qitを求めていくこととなる。

【0030】
【数1】
JP0006145766B2_000002t.gif
・・・・・・・(1)

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

【0032】
このΣ以降の項において、μは係数である。またρi、ρjは、より優れた結果を出力
した場合を意味している。ここでρiは、これから戦績指数qitを求めようとする被検対象5が、より優れた結果を出力した場合に“1”となり、より劣る結果を出力した場合には、“0”となる。ρjは、jに相当する他の被検対象5が、より優れた結果を出力した場合に“1”となり、より劣る結果を出力した場合には、“0”となる。本明細では、例として、2つの組み合わせを選択するためのシステムであることからρは2変数となっている。

【0033】
表1は、ρ、πの取り得る値を示している。

【0034】
【表1】
JP0006145766B2_000003t.gif

【0035】
式(1)の括弧内は、ρi・ρjのように乗算で表されることから、ρiとρjの双方が1である場合のみプラスになる。

【0036】
また、πは、i、j以外の他の被検対象5が、より劣った結果を出力した場合に“1”となり、より優れた結果を出力した場合に“0”となる。

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

【0038】
このように、本発明では、qitを求める一の被検対象5が、より優れた結果を出力した場合及び他の被検対象がより劣る結果を出力した場合に、当該一の被検対象5における今までの戦績qitをより優れる側に向上させる。また、qitを求める一の被検対象5が、より劣った結果を出力した場合及び他の被検対象がより優れた結果を出力した場合に、当該一の被検対象5における今までの戦績qitを変化させない。戦績優劣比較部2は、このような制御を行うものであってもよく、上述した(1)式に基づく制御を行う場合に限定されるものではない。

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

【0040】
戦績優劣比較部2は、このようにして、各被検対象5a~5dについてそれぞれ戦績指数q1t~q4tを求めた後、その戦績指数q1t~q4tを被検対象全体5の戦績との関係においてその優劣を比較する。そして、この優劣の比較結果としての内部リソース値sitをそれぞれ出力する。

【0041】
かかる場合に、(2)式に基づいてその優劣を比較するようにしてもよい。

【0042】
【数2】
JP0006145766B2_000004t.gif
・・・・・・・(2)

【0043】
式(2)は、一の被検対象5の戦績qit-1と被検対象5全体の戦績qkt-1の平均との差分を、内部リソース値sitとしている。例えば、被検対象5aについての内部リソース値s1tを求める場合には、その戦績q1t-1と、全被検対象の戦績q1t-1、q2t-1、q3t-1、q4t-1の平均との差分を求める。ちなみに、(2)式の右項においてx0tはあくまで調整値であり、必須のものではない。 この(2)式に基づいて、内部リソース値sitを判断する場合に限定されるものではない。内部リソース値sitは、それに対応する一の被検対象5の戦績qit-1が、他の被検対象5との間で相対的に優れているか否かを示すものであれば、いかなる計算式で、或いはいかなる方法で、これを評価するようにしてもよい。戦績優劣比較部2は、これら計算したs1t~s4tをそれぞれ、制御部3a~3dへ出力する。

【0044】
制御部3a~3dは、これらs1t~s4t並びに被検対象5a~5dから直近の結果l1t~l4tがそれぞれ入力された場合に、例えば、以下の制御を行う。

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

【0046】
【表2】
JP0006145766B2_000005t.gif

【0047】
この表2によれば、制御部3は、内部リソース値sitと、被検対象5から出力された直近の結果litとより形成されるマトリクスに基づいて、制御方法を決定する。ここでlit=-1は、より優れた結果が出力された場合を意味している。また、lit=1は、より劣った結果が出力された場合を意味している。ちなみに、このlitの優劣の基準についてもいかなるものであってもよい。

【0048】
また、表中の数値(-1、0、1)の意味については、先ず“-1”は、計量変数xを成長速度を減少させるように制御する。また、“0”は、計量変数xtの成長速度を特に増減させないことを意味し、“1”は、計量変数xtの成長速度を増加させるように制御する。

【0049】
ちなみに以下の例では、x0tは、xiの値によって決まるものと仮定している。

【0050】
制御部3は、この表2に基づいて具体的に以下の制御を行う。

【0051】
内部リソース値sitが正で、被検対象5から出力された直近の結果litがより優れたものである場合(=-1)には、“1”であることから計量変数xtの成長速度を増加させる。内部リソース値sitが正で、被検対象5から出力された直近の結果litがより劣るものである場合(=1)には、“0”であることから計量変数xtの成長速度を増加させることなくそのままにする。内部リソース値sitが0で、被検対象5から出力された直近の結果litがより優れたものである場合(=-1)には、“1”であることから計量変数計量変数xtの成長速度を増加させる。内部リソース値sitが0で、被検対象5から出力された直近の結果litがより劣るものである場合(=1)には、“-1”であることから計量変数計量変数xtの成長速度を減少させる。内部リソース値sitが負で、被検対象5から出力された直近の結果litがより優れたものである場合(=-1)には、“0”であることから計量変数計量変数xtの成長速度をそのままにし、内部リソース値sitが負で、被検対象5から出力された直近の結果litがより劣るものである場合(=1)には、“-1”であることから計量変数計量変数xtの成長速度を減少させる。

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

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

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

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

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

【0057】
ちなみに、解探索システム1により解を求める上で、被検対象5a~5d毎に割り当てられる計量変数x1~x4と、x0tとの合計が一定となるように制御することで、より探索精度を高めることが可能となる。即ち、x0t+x1+x2+x3+x4=一定、としておくことにより、計量変数xtが全体的に大きくなってしまい、閾値との間でバランスが取れなくなるのを防止することができ、これが探索精度の向上につながることとなる。

【0058】
0tは、他の計量変数xiの値により影響を受ける変数である。上述した処理動作を繰り返し進めていく結果、上述した(2)式において、当初はx0tの項が支配的になり、qit-1以後の項(一の被検対象5の戦績qit-1と被検対象5全体の戦績qkt-1の平均との差分)については、あまりこのsitを決定する上で大きな影響を与えるものではない。その結果、このsitは、戦績qit-1と戦績qkt-1の平均との差分に影響を受けることなく、自由度が高くなり、その分ランダムな値を取りやすくなる。その結果、ランダムな値を取りやすくなるsitを介して様々な出力指示4a~4dが行われ、様々な解を探索することが可能となる。

【0059】
これに対して、tが大きくなるにつれ、換言すればフィードバック回数が多くなるにつれ、徐々にqit-1以後の項(一の被検対象5の戦績qit-1と被検対象5全体の戦績qkt-1の平均との差分)が大きくなる。その結果、このsitを決定する上で、sitよりも、戦績qit-1と戦績qkt-1の平均との差分値が支配的になってくる。そして、次回に出力指示4a~4dが行われるものについては、戦績qit-1と戦績qkt-1の平均との差分値がより影響を受けるものとなる。

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

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

【0062】
なお、本発明は、上述した実施の形態に限定されるものではない。例えば、図3に示すように、2以上の解探索システム1を用いて、被検対象5を探索するようにしてもよい。図3では、2つの解探索システム1a、解探索システム1bを用いて被検対象5a~5dを探索する場合について示している。ちなみに、この2つの解探索システム1a、解探索システム1bは、互いの同一の被検対象5a~5dのグループの探索を行う。換言すれば図中において解探索システム1b側の点線で示されている被検対象5a~5dは、解探索システム1a側の実線で示されている被検対象5a~5dと同一のものである。

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

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

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

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

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

【0068】
更にこのケースでは、解探索システム1a、解探索システム1b間が互いに連関していてもよい。つまり、解探索システム1aが特定の被検対象5aを選択した場合、解探索システム1bは、被検対象5cを選択するように互いに連関するように設定されていてもよい。これにより、例えば株等の投資対象を被検対象5に当てはめる場合において、一の解探索システム1aが、他の解探索システム1bとの間で互いに連関して意思決定を行う場合が多い場合(例えば、A氏がT社の株を買った場合に、B氏は、T社と業務上の関連性が高いU社の株を買う場合)において、その探索精度を向上させることが可能となる。なお、この解探索システム1aによる出力指示、解探索システム1bの出力指示の相関性はいかなるものであってもよい。

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

【0070】
なお、上述した実施形態では、2個の解探索システム1a、解探索システム1bを用いる場合を例にとり説明をしたが、これに限定されるものではなく2以上であればいかなる数で構成されていてもよい。
【実施例1】
【0071】
図3は、本発明を適用した解探索システム1を、コンピュータプログラムで実現した場合における実施例を示している。コンピュータプログラムで実現するため、戦績優劣比較部2は、これと同様の処理を実行する戦績優劣比較ステップに、制御部3は、これと同様の処理を実行する制御ステップに、出力指示部4は、これと同様の処理を実行する出力指示ステップとして具現化したプログラムを作成した。
【実施例1】
【0072】
被検対象5は、予め設定された確率の下で当選するか落選するかが決まる装置であり、例えばスロットマシーン等を想定している。この被検対象5-1の当選確率=0.35、被検対象5-2の当選確率=0.45、被検対象5-3の当選確率=0.55、被検対象5-4の当選確率=0.65とされている。また5-0は、x0tである。
【実施例1】
【0073】
このうち、当選確率の高い2つの被検対象5の組み合わせ(即ち、被検対象5-3、5-4)を探索解として求めることを行う。
【実施例1】
【0074】
図3の横軸tはフィードバック回数である。また、戦績指数qiは、(1)式に基づいて被検対象5毎に求めている。優劣Siは、(2)式に基づいて被検対象5毎に求めている。aiは、表2から導き出される-1、0、1の何れかの数値である。
【実施例1】
【0075】
またviは、aiに基づいて計量変数を増やす方向に推進させるのか、或いは減らす方向に推進させるのかを決めるパラメータである。仮にaiが計量変数を増減させる際の加速度であるとすえれば、このviは、計量変数の増減速度である。aiは、viの1回微分で表すことができる。更に、計量変数xiは、実際に計量変数の増減速度viに基づいて増減させられた実際のパラメータ値である。ここで閾値は0としている。
【実施例1】
【0076】
このようなプログラムによる結果より、フィードバック回数が増加するにつれて、計量変数xiは、殆ど被検対象5-3、5-4のみが大きくなってそのまま出力指示部4によって出力指示が行われることが繰り返されるのがわかる。
【実施例1】
【0077】
このように本発明を適用したコンピュータプログラムにより、組み合わせバンディット問題を自動的に求めることができることを検証することができた。
【実施例1】
【0078】
図4は、他の実施例ではあるが、それぞれ被検対象5の当選確率が、0.2、0.5、0.8の3つのサンプルについて、本発明を適用したコンピュータプログラムにより、より当選確率の高い組み合わせを選択するシミュレーションを行った結果である。実線が本発明に相当する。比較例1は、ソフトマックスアルゴリズムを組み合わせ報酬最大化問題に拡張したものである。また比較例2は、イプシロングリーディアルゴリズムを組み合わせ報酬最大化問題に拡張したものである。 その結果、本発明を適用したコンピュータプログラムは、フィードバック回数が増加するにつれて、他の比較例よりも正答率が高くなるのが分かる。
【符号の説明】
【0079】
1 解探索システム
2 戦績優劣比較部
3 制御部
4 出力指示部
5 被検対象
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4