Top > Search of Japanese Patents > SOLUTION SEARCH SYSTEM AND METHOD, AND SOLUTION SEARCH PROGRAM

SOLUTION SEARCH SYSTEM AND METHOD, AND SOLUTION SEARCH PROGRAM NEW_EN foreign

Patent code P190016291
File No. 08135
Posted date Aug 23, 2019
Application number P2013-066768
Publication number P2014-191598A
Patent number P6145766
Date of filing Mar 27, 2013
Date of publication of application Oct 6, 2014
Date of registration May 26, 2017
Inventor
  • (In Japanese)金 成主
  • (In Japanese)青野 真士
  • (In Japanese)行田 悦資
  • (In Japanese)原 正彦
Applicant
  • (In Japanese)国立研究開発法人理化学研究所
Title SOLUTION SEARCH SYSTEM AND METHOD, AND SOLUTION SEARCH PROGRAM NEW_EN foreign
Abstract Efficient Method for Decision-Making Based on Trial and Error
In order to conduct a process of trial and error efficiently, it is important to maintain a balance between focusing on information obtained from past trials and searching for better new options. Through the study of information processing principles used by unicellular organisms, we have discovered that even non-intelligent substances are capable of realizing efficient decision-making as long as they have the property of preserving volume. This method, named the "tug-of-war principle", is found to perform better in terms of efficiency and adaptability than conventional decision-making algorithms.
Outline of related art and contending technology (In Japanese)従来より、期待値を最大化する解を探索する問題の代表例として、バンディット問題がある。このバンディット問題とは、貰える合計報酬の期待値を最大化することを目的とし、プレイヤーはn種類の異なる行動選択肢から一つの選択肢を選択する動作を繰り返す。各選択の後は毎回、選択した行動に依存する確率分布から選ばれた結果がプレイヤーの報酬として与えられる。

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

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

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

※Click image to enlarge.

thum_JPA 426191598_i_000002.jpg
State of application right Registered
(In Japanese)ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記「問合せ先」まで直接お問い合わせください。


PAGE TOP

close
close
close
close
close
close
close