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

解探索システム、解探索プログラム UPDATE 外国出願あり

国内特許コード P190016291
整理番号 08135
掲載日 2019年8月23日
出願番号 特願2013-066768
公開番号 特開2014-191598
登録番号 特許第6145766号
出願日 平成25年3月27日(2013.3.27)
公開日 平成26年10月6日(2014.10.6)
登録日 平成29年5月26日(2017.5.26)
発明者
  • 金 成主
  • 青野 真士
  • 行田 悦資
  • 原 正彦
出願人
  • 国立研究開発法人理化学研究所
発明の名称 解探索システム、解探索プログラム UPDATE 外国出願あり
発明の概要 【課題】高速かつ効率的に組み合わせバンディット問題の解を求める。
【解決手段】それぞれ設定された確率分布に基づいて結果を出力する2以上の被検対象のうち最良の結果の出力が期待される被検対象5の組み合わせを探索する際に、出力された結果の蓄積に基づく今までの戦績を被検対象5毎にそれぞれ求め、各被検対象5の戦績を被検対象5全体の戦績との関係においてその優劣を比較する戦績優劣比較部1と、比較された戦績の優劣と、被検対象5から出力された直近の結果とに基づいて、計量変数を増加又は減少させるように制御することを当該被検対象5毎に行う制御部3と、計量変数が閾値を超えた被検対象5に対して結果の出力を指示する出力指示部4とを備え、上記出力指示部4は、結果の出力の指示の繰り返しを経て最終的に最も結果の出力の指示が行われている被検対象5の組み合わせを、探索すべき組み合わせとして特定する。
【選択図】図1
従来技術、競合技術の概要

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

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

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

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

産業上の利用分野

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

特許請求の範囲 【請求項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項記載の解探索プログラム。
国際特許分類(IPC)
Fターム
  • 5L049AA04
  • 5L049CC18
  • 5L049DD03
画像

※ 画像をクリックすると拡大します。

JP2013066768thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記「問合せ先」まで直接お問い合わせください。


PAGE TOP

close
close
close
close
close
close
close