(57)【特許請求の範囲】
【請求項１】
所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に前記確認作業または実空間において前記多次元の各要素がとった値の組み合わせを示すインプット情報と、その時に前記インプット情報が示す前記組み合わせに対して得られた前記所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部と、
所定の終了条件を満たすまで、前記要素の組み合わせ毎に定義される指標であって、前記実績データから算出される、前記実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における前記所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す探索部とを備える
ことを特徴とする組み合わせ探索システム。
【請求項２】
前記探索部は、
前記探索空間に含まれる一部の組み合わせに対して算出される前記情報の重要度に基づいて、次の確認作業で用いる組み合わせを絞り込む大域決定部を含む
請求項１に記載の組み合わせ探索システム。
【請求項３】
前記大域決定部は、前記一部の組み合わせとして、前記実績データに含まれる前記インプット情報が示す前記要素の組み合わせに対して、前記情報の重要度を算出する
請求項２に記載の組み合わせ探索システム。
【請求項４】
前記大域決定部は、前記情報の重要度を基に、前記一部の組み合わせの中から１または複数の組み合わせを採択することにより、次の確認作業で用いる組み合わせを絞り込む
請求項２または請求項３に記載の組み合わせ探索システム。
【請求項５】
前記大域決定部は、前記情報の重要度に比例した確率で、前記一部の組み合わせの中から、次の確認作業で用いる組み合わせの探索起点とする１の組み合わせを採択することにより、次の確認作業で用いる組み合わせを絞り込む
請求項２から請求項４のうちのいずれかに記載の組み合わせ探索システム。
【請求項６】
前記探索部は、
前記大域決定部によって採択された組み合わせを起点として前記探索空間の部分空間を探索して、次の確認作業で用いる組み合わせを決定する詳細決定部を含む
請求項４または請求項５に記載の組み合わせ探索システム。
【請求項７】
前記探索部は、一定の確率で、前記探索空間の中からランダムに採択された組み合わせを、次の確認作業で用いる組み合わせとして決定する
請求項１から請求項６のうちのいずれかに記載の組み合わせ探索システム。
【請求項８】
所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に前記確認作業または実空間において前記多次元の各要素がとった値の組み合わせを示すインプット情報と、その時に前記インプット情報が示す前記組み合わせに対して得られた前記所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能な情報処理装置であって、
所定の終了条件を満たすまで、前記要素の組み合わせ毎に定義される指標であって、前記実績データから算出される、前記実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における前記所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す探索部を備える
ことを特徴とする情報処理装置。
【請求項９】
所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に前記確認作業または実空間において前記多次元の各要素がとった値の組み合わせを示すインプット情報と、その時に前記インプット情報が示す前記組み合わせに対して得られた前記所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能な情報処理装置が、所定の終了条件を満たすまで、前記要素の組み合わせ毎に定義される指標であって、前記実績データから算出される、前記実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における前記所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す
ことを特徴とする組み合わせ探索方法。
【請求項１０】
所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に前記確認作業または実空間において前記多次元の各要素がとった値の組み合わせを示すインプット情報と、その時に前記インプット情報が示す前記組み合わせに対して得られた前記所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能なコンピュータに、
所定の終了条件を満たすまで、前記要素の組み合わせ毎に定義される指標であって、前記実績データから算出される、前記実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における前記所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返し実行させる
ための組み合わせ探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定のパラメータを最適化する多次元の組み合わせを探索する組み合わせ探索システム、情報処理装置、組み合わせ探索方法および組み合わせ探索プログラムに関する。
【背景技術】
【０００２】
材料開発の迅速化、低コスト化のために、少ない実験回数で優れた特性を持つ材料を探索する技術が求められている。しかし、そのような優れた特性を持つ材料の多くは複数の元素の組み合わせからなり、例えば多元合金の素材における組成比のように生成条件は多岐にわたる。そのような材料の生成条件の最適化は、多次元組み合わせ問題である。多次元の組み合わせ問題では、組み合わせが取りうるパターンの数は条件の数（例えば、多元合金の組成比であれば、合成されうる元素数）に応じて指数関数的に増加する。そのため、経験や直感等の人間的な予想だけでは最適化が困難であり、数理的なアプローチが重要となる。【０００３】
昨今のコンピュータ技術の発達に伴い、実際に材料を作らずとも、第一原理計算や分子動力学法等を用いて、ある程度の精度で物理量を予測することが可能となった。しかし、例えば、四元合金の素材の組成比を１％程度の精度で最適化する問題を考えた場合、組み合わせのパターン数は約１億になる。このような多次元の組み合わせ問題では、計算手法を利用して最適化したい物理量を予測できたとしても、全探索を行うことは困難である。【０００４】
多次元の組み合わせ問題を最適化する手法の１つとして、過去の実験結果を基に、実験条件と最適化したい特性との相関を学習し、任意の条件に対してどれくらいの特性が得られるかを予測することで、実験条件の候補を絞り込むことが考えられる。上記の例でいえば、実験条件とされる多次元合金の素材の組成比と、その実験条件で得られた物理的な特性（磁性、熱電特性等）との相関を学習し、特性が未知の組成比においてどれくらいの特性が得られるかを予測して、次の実験条件を、好適な結果が得られるような組み合わせ（組成比）に限定することで、効率的な材料探索が可能になる。【０００５】
相関の学習方法としては、機械学習技術やＡＩ（Artificial Intelligence ）で用いられる数理的な手法が注目されている。【０００６】
数理的な手法を利用した組み合わせ問題の最適化方法の一例が、例えば、非特許文献１および特許文献１、２、３に記載されている。【０００７】
例えば、非特許文献１には、ガウス回帰と期待値最大化とによる最適化方法が記載されている。また、特許文献１には、モンテカルロ法を用いた最適化方法が記載されている。また、特許文献２には、粒子群最適化法による方法が記載されている。また、特許文献３には、確率的なシステムの注目指標を最小化することによる最適化方法が記載されている。【０００８】
また、例えば、実験を伴う多次元の組み合わせ問題の最適化方法の例として、非特許文献２には、組み合わせを遺伝子で表現し、実験結果が悪いものを淘汰し、優れた遺伝子同士を交叉させることで次に測定するべき組み合わせを与える方法が記載されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００９−１４６０７２号公報
【特許文献２】国際公開第２０１３／００８３４５号
【特許文献３】国際公開第２０１６／１９４０５１号
【非特許文献】
【００１０】
【非特許文献１】石井一夫、「翻訳  マテリアルズインフォマティクス  探索と設計」、２０１７年、ｐ．４３−６９
【非特許文献２】D. M. Deaven and K. M. Ho, "Molecular Geometry Optimization with a Genetic Algorithm", Phys. Rev. Lett. 75, Jul 1995.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
例えば、上記の各文献に記載された方法を利用して、所望の特性に対して多次元の素材の組成比の最適化を行うことを考える。【００１２】
組成比の最適化では、主に２つの事が求められる。すなわち、（１）どの組み合わせを優先して測定すべきかの決定を高速に行うこと、および（２）最適化対象とした特性が複数の異なる組み合わせにおいてピークを持つような場合であっても、それら複数のピークに対応した組み合わせが求められることである。【００１３】
上記（１）に関し、例えば、非特許文献１に記載の方法は、ガウス回帰によって得られる期待値と分散の関係を示す関数を用いて、結果が未知の全ての組み合わせに対して優先度を計算し、最も優先度の高い組み合わせを次の実験候補に決定する。しかし、組み合わせ数が膨大になる多次元系においては、全ての組み合わせで優先度を計算するのは困難である。【００１４】
また、特許文献１に記載の方法は、回帰木を使った高速化をなしているが、回帰木の設計や計算コストが条件の数の指数関数に依存することに変わりなく、また、それを解決する方法について何ら考慮していない。【００１５】
また、特許文献２に記載の方法は、昆虫や魚の群知能をモデル化することで高速化を図っている。具体的には、組み合わせの条件数に応じた多次元ベクトルが張る多次元空間上に複数のエージェントを配置し、それらエージェントのいる位置の各々において実験を行う。実験の結果、優れた特性が得られたエージェントのいる方向に他のエージェントを移動させる処理を繰り返す。これにより、より優れた特性を持つ組み合わせの探索を高速化する。しかし、この方法は、高速である一方、エージェントの重複を陽に扱うことが困難であり、特定の組み合わせにエージェントが集中した場合、効率が大幅に落ちるという問題がある。【００１６】
また、特許文献３に記載の方法は、過去の実験結果から多次元空間上での特性の勾配を推定し、より特性が向上しそうな組み合わせに絞って優先度を計算し、得られた優先度を基に最適解を探索する。しかし、この方法は、優先度を算出する組み合わせを絞ることで高速化を図っているが、勾配を推定してピークを上っていく単純な山登り法では、局所解を抜け出すのが困難である。【００１７】
非特許文献２に記載の方法は、組み合わせを遺伝子で表現し、実験結果が悪いものを淘汰し、優れた遺伝子同士を交叉させることで次に測定するべき組み合わせを与えることで、組み合わせの最適化を行う。この方法は、遺伝アルゴリズムとも呼ばれ、適用できる問題の幅が広く、また、組み合わせの決定の計算コストが問題の次元によらず高速である。しかし、この方法は、実験結果の悪いものが淘汰されるため、組み合わせの多様性を管理するのが困難であり、探索範囲が狭くなったり、局所解に陥りやすいという問題がある。また、非特許文献２に記載の方法は組み合わせの重複が管理できずに実験コストが増加するという問題がある。なお、非特許文献１に記載された方法を利用して組み合わせ毎の予測値や分散を得ることで組み合わせの多様性を管理することは可能だが、分散が小さい組み合わせについても交叉を行うのに十分な遺伝子の個体数が必要であるため計算効率がさほど上がらない、回帰の計算コストが高く遺伝アルゴリズムが持つ高速性を損ねてしまうという問題がある。【００１８】
上記（２）に関し、多次元の組み合わせの最適化問題においては、最も優れた結果を示す組み合わせ以外の組み合わせも必要になることがある。例えば、多次元の素材の組成比の最適化問題の場合、素材のコスト、環境配慮等の影響から、幾分か特性を犠牲にしてでも、低コスト、無害な素材を使いたい場合がある。また、単純に、同程度の優れた結果を示す組み合わせが複数存在する場合もある。【００１９】
しかし、上記の方法はいずれも、最も優れた特性を持つ組み合わせを探索するための手法となっており、それ以外に優れた特性を持つ組み合わせを高速に（例えば、全探索よりも効率的に）探索することは考慮されていない。【００２０】
本発明は、上述した課題に鑑みてなされたものであり、所定のパラメータを最適化する多次元の組み合わせ問題において、複数のピークを有する場合であっても、適切な解を効率よくかつ安定して探索することができる組み合わせ探索システム、情報処理装置、組み合わせ探索方法および組み合わせ探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明による組み合わせ探索システムは、所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去の確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部と、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す探索部とを備えることを特徴とする。【００２２】
また、本発明による情報処理装置は、所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能な情報処理装置であって、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す探索部を備えることを特徴とする。【００２３】
また、本発明による組み合わせ探索方法は、所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能な情報処理装置が、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返すことを特徴とする。【００２４】
また、本発明による組み合わせ探索プログラムは、所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能なコンピュータに、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返し実行させることを特徴とする。
【発明の効果】
【００２５】
本発明によれば、所定のパラメータを最適化する多次元の組み合わせ問題において、複数のピークを有する場合であっても、適切な解を効率よくかつ安定して探索することができる。
【図面の簡単な説明】
【００２６】
【図１】第１の実施形態の組み合わせ探索システムの構成例を示すブロック図である。
【図２】第１の実施形態の組み合わせ探索システムの動作例を示すフローチャートである。
【図３】第１の実施形態の組み合わせ探索システムのより詳細な動作例を示すフローチャートである。
【図４】１次元関数に対する情報の重要度の一例を示す説明図である。
【図５】第１の例である二元の組み合わせの最適化問題の関数Ｆ（ｘ，ｙ）の出力を示すグラフである。
【図６】関数Ｆに対するパラメータｘ，ｙの組み合わせの探索結果の例を示す模式図である。
【図７】関数Ｆに対するパラメータｘ，ｙの組み合わせの探索結果の例を示す模式図である。
【図８】関数Ｆに対するパラメータｘ，ｙの組み合わせの探索結果の例を示す模式図である。
【図９】関数Ｆに対するパラメータｘ，ｙの組み合わせの探索結果の例を示す模式図である。
【図１０】本発明による二段階探索手法と他の手法とのコストの比較結果を示す説明図である。
【図１１】第２の例での実験結果を示すグラフである。
【図１２】第２の例におけるFeの合成比率毎の実験回数の分布を示すグラフである。
【図１３】本発明の各実施形態にかかるコンピュータの構成例を示す概略ブロック図である。
【図１４】本発明の組み合わせ探索システムの概略を示すブロック図である。
【図１５】本発明の組み合わせ探索システムの他の例を示すブロック図である。
【発明を実施するための形態】
【００２７】
［実施形態１］
以下、図面を参照して本発明の実施形態について説明する。図１は、第１の実施形態にかかる組み合わせ探索システムの構成例を示すブロック図である。図１に示す組み合わせ探索システムは、記憶部１０と、探索部２０と、実験部３０とを備える。
【００２８】
記憶部１０は、多次元の素材の組成比の１つ以上の組み合わせの各々に対して行った、最適化したい特性に関する実験結果を示す情報（実績データ）を記憶する。記憶部１０は、実験を行った材料の情報（多次元の素材の組成比）と、その材料から実験により得られた特性とを対応づけた情報を少なくとも１つ以上記憶する。以下、実験に用いる材料の多次元の素材の組成比を、実験のインプット情報または単にインプットといい、該材料から実験により得られた特性を、実験のアウトプット情報または単にアウトプットという場合がある。
【００２９】
探索部２０は、実験結果または探索結果が所定の終了条件を満たすまで、次に実験を行う１の組み合わせを、組み合わされる各条件（各要素）に対応する成分からなる多次元ベクトルが張る多次元空間である探索空間内から探索して決定する探索決定処理を繰り返し行う。
【００３０】
本実施形態の探索部２０は、戦略決定部２１と、終了判定部２２と、二段階決定部２３と、乱択部２４とを含む。なお、探索部２０は、終了判定部２２において所定の終了条件を満たすと判定されるまで、戦略決定部２１によって決定された探索戦略に応じて二段階決定部２３または乱択部２４による探索決定処理を繰り返し行う。
【００３１】
戦略決定部２１は、ピーク探索の戦略を決定する。以下に示す例では、ピーク探索の戦略として、以下に示す二段階探索手法と、ランダムに組み合わせを選択する乱択手法のいずれかを決定する。ただし、戦略決定部２１は、適度にばらつきのある複数の組み合わせに対する実験結果が得られている場合等は省略することも可能である。または、戦略決定部２１を、最初に数回ランダムに組み合わせを決定するランダム決定機（図示せず）によって代替してもよい。なお、戦略決定部２１が省略またはランダム決定機により代替された場合、乱択部２４も省略される。
【００３２】
終了判定部２２は、これまでの探索の経過や実験結果を基に、探索が終了条件を満たすか否かを判定し、終了条件を満たした場合に、探索部２０における探索決定処理を終わらせる。
【００３３】
なお、本実施形態では、１回の探索決定処理で次に実験を行う１の組み合わせが決定される度に、後述される実験部３０により実験が行われ、その結果が記憶部１０に追加されるものとする。追加された実験結果は、次の探索決定処理でこれまでの実験結果の１つとして参照される。
【００３４】
二段階決定部２３および乱択部２４はそれぞれ、過去の実験におけるインプットとアウトプットを保持する記憶部１０の情報を基に、次の実験におけるインプットを決定する決定機である。ただし、二段階決定部２３は、二段階探索手法を用いて次の実験におけるインプットを決定し、乱択部２４は、乱択手法を用いて次の実験におけるインプットを決定する。
【００３５】
なお、本実施形態では実績データの取得方法として実験を例示しているが、実績データは、所定の確認作業により得られるものであればよい。確認作業としては、実験以外にも、所定の精度を満たす数値計算（計算シミュレータ等）等が挙げられる。また、実験には、組み合わせが示す事象等を実空間もしくはその疑似空間上に生じさせてその時に生じた現象を取得すること等、あらゆる検証動作が含まれる。したがって、上記の実験部３０は、所定の確認作業を行うためのあらゆる装置と代替可能である。その場合、次の実験におけるインプットは、次の確認作業で用いるインプットと置き換えればよい。また、インプットには離散的なパラメータや次元圧縮等の前処理を施したものを加えることも可能である。インプットとアウトプットの具体例を以下に列挙する。
【００３６】
・合金の材料の組成比（インプット）と、合金の磁気、電気、熱等の物理的特性（アウトプット）
・合金の材料の組成比（インプット）と、合金の磁気、電気、熱等の物理的特性のシミュレーションによる予測値（アウトプット）
・材料の形状（インプット）と、計算シミュレーションから得られる材料の熱、磁気等の物理的特性（アウトプット）
・材料の形状（インプット）と、計算シミュレーションから得られる材料の熱、磁気等の物理的特性のシミュレーションによる予測値（アウトプット）
・ｔ−ＳＮＥ（t-distributed stochastic neighbor embedding ）等の手法により次元削減された回路の画像情報（インプット）と電気的特性（アウトプット）
・ナップザック問題における品物の組み合わせ（インプット）と、品物の価値（アウトプット）を初めとした組み合わせ問題における種々の組み合わせとその価値
【００３７】
二段階決定部２３は、予測部２３１と、大域決定部２３２と、詳細決定部２３３とを有する。
【００３８】
予測部２３１は、記憶部１０に記憶されている情報に基づいて、任意の組み合わせ（インプット）に対して、最適化したい特性の値（アウトプット）を予測する。予測部２３１は、例えば、カーネル近似やガウス回帰等公知の方法を利用できる。また、機械学習技術やＡＩ等に用いられる公知の学習方法により学習された推定モデルを利用することも可能である。
【００３９】
大域決定部２３２は、過去の実験結果および予測部２３１による予測結果を基に、次の実験におけるインプット（組み合わせ）の探索起点を大域的に決定する。以下、大域決定部２３２が決定した探索起点を、大域候補点と呼ぶ場合がある。
【００４０】
大域決定部２３２は、大域候補点の決定に際し、過去の実験結果から、インプット（組み合わせ）に対してそれぞれの情報の重要度を求め、それを利用する。これにより、大域候補点を高速に（少なくとも、総当たり計算よりも計算コストを抑えて）決定する。
【００４１】
本実施形態では、各組み合わせに対する情報の重要度として、「過去の実験結果から予測される、実験を増やす、すなわちその組み合わせに対する所定のパラメータの値（本例の場合、所定の特性値）の測定回数が増えることによる探索空間内における当該値の不確かさの減り代」に少なくとも基づく指標を用いる。ここで、所定のパラメータの値の不確かさは、任意の予測関数で与えられる、実験値の誤差から作られる期待値に対する不確かさ（Error ）であってもよい。より具体的に、過去の実験で用いたインプットとアウトプットに対する、カーネル近似やガウス回帰等の回帰分析を施すことで得られるアウトプットの予測値の不確かさであってもよい。
【００４２】
例えば、ある組み合わせに対する情報の重要度は、過去の実験結果から回帰によって得られる期待値に対する不確かさがその組み合わせの測定を追加することによってどれだけ減るかを示す「減り代」に対して、単調増加する指標や正の相関をもつ指標であってもよい。また、ある組み合わせに対する情報の重要度は、過去の実験結果から予測される当該組み合わせに対する所定のパラメータの値（期待値）と、当該組み合わせに対する測定を追加した場合に過去の実験結果から予測される当該組み合わせに対する所定のパラメータの値（期待値）の不確かさの減り代とに基づく指標であってもよい。期待値も加味することで、優れた特性が得られそうもない組み合わせの重要度を下げる等の調整を行うことができる。
【００４３】
ここで、探索空間内での予測値の不確かさを示す指標として分散（またはその総和）を用いてもよい。その場合、情報の重要度は、過去の実験結果から予測される、その組み合わせに対する実験を増やすことによる探索空間内での所定のパラメータの値（期待値）の分散（またはその総和）の減り代に基づく値としてもよい。なお、本実施形態における「情報の重要度」は、実験への「投資優先度」とみなすこともできる。分散以外にも、過去の実験結果から得られる、その組み合わせに対する期待値と不確かさとを掛け合わせて得られる指標を用いてもよい。期待値と不確かさの乗算を用いることで、探索空間において不確かさが低い点や期待値が低い点に対する重要度を下げることができる。
【００４４】
大域決定部２３２は、例えば、過去に測定したインプット毎に、探索空間全体での誤差の総和の減少値を指標とした、情報の重要度を求め、その情報の重要度に比例した確率で過去に実験したインプットを１つ採択することにより、大域候補点を決定してもよい。
【００４５】
詳細決定部２３３は、大域決定部２３２により決定された大域候補点を基に、次に実験候補とする１の組み合わせを決定する。
【００４６】
詳細決定部２３３は、例えば、大域候補点を起点とした局所的な最適化手法により、次に実験候補とする１の組み合わせを決定してもよい。具体例として、詳細決定部２３３は、大域候補点とされた組み合わせに対してランダムノイズを足すことで、次に実験する組み合わせの候補を複数生成し、それらの候補の中から情報の重要度が最も高い候補を次の組み合わせとして採択してもよい。また、例えば、詳細決定部２３３は、大域候補点を起点とする山登り法等を利用して局所的な最適解を求め、それを次の組み合わせとしてもよい。このとき、詳細決定部２３３は、情報の重要度以外の指標（例えば、予測値）を用いることも可能である。
【００４７】
本実施形態では、このような、まず実績データを基に高速かつ大域的に、次の組み合わせの探索起点とする１の組み合わせを求め、その後、大域的に求めた１の組み合わせを基にして局所的に最適解を求める手法を、二段階探索手法と呼ぶ。特に、大域的に１の組み合わせを求める際や局所最適解を求める際に、過去のデータから組み合わせ毎の情報の重要度を定量的にかつ算出対象を限定して求めることで、より良いアウトプットが得られる可能性が高い組み合わせを高速に推測する。
【００４８】
実験部３０は、探索部２０によって決定された組み合わせに対して実験を行う。なお、実験部３０による実験の結果は記憶部１０に登録（追加）される。
【００４９】
次に、本実施形態の動作を説明する。図２は、本実施形態の組み合わせ探索システムの動作例を示すフローチャートである。図２に示す動作は、次の実験の組み合わせ（インプット）を決定する組み合わせ決定フェーズ（ステップＳ１１〜ステップＳ１５）と、決定された組み合わせで実験を行いその結果を取得する実験フェーズ（ステップＳ１６）と、終了条件を判定する判定フェーズ（ステップＳ１７）とに大別される。
【００５０】
決定フェーズでは、探索部２０に記憶部１０のデータを入力し、探索部２０が、入力されたデータに基づいて次の実験のインプットを決定する。実験フェーズでは、実験部３０が、探索部２０により決定されたインプットに対して実験を行い、その実験のアウトプットを記憶部１０に追加する。判定フェーズでは、これまでの結果が終了条件を満たしているかを確認し、条件を満たしていない場合は探索部２０に再び記憶部１０のデータを入力してインプットの決定処理に戻る。終了条件は、本システムのユーザにより問題に応じて定められる。一例としては、ピークの高さ（確認された特性の高さ）、ピークの数（適切な解とされる組み合わせの数）、誤差（予測値の不確かさ）、実験回数が所定の値に達した等がある。なお、図１では図示省略しているが、探索部２０を備える情報処理装置等が、次の実験のインプットを示す情報を出力する出力部や、記憶部１０に新たな実績データを追加するための入力部をさらに備えていてもよい。
【００５１】
以下、図２を参照してこれらのフェーズを含む本実施形態の動作をより詳細に説明する。図２に示す例では、まず、記憶部１０のデータが探索部２０に入力され、次の実験対象とされる組み合わせの決定指示が行われる（ステップＳ１１）。
【００５２】
次の実験対象とされる組み合わせの決定指示が行われると、まず、戦略決定部２１が、今回の探索決定処理におけるピークの探索戦略を決定する（ステップＳ１２）。戦略決定部２１は、例えば、ピークの探索戦略として二段階探索手法を用いるか乱択手法を用いるかを決定してもよい。
【００５３】
ピークの探索戦略として乱択手法が採用された場合、探索部２０の乱択部２４が、次の実験の組み合わせをランダムで生成する（ステップＳ１３）。一方、ピークの探索戦略として二段階探索手法が採用された場合、ステップＳ１４に進む。
【００５４】
ステップＳ１４では、大域決定部２３２が、過去の実験結果を基に、大域的に、次の実験の組み合わせの探索起点となる組み合わせを探索して、大域候補点を決定する。ここで、「大域的に探索する」とは、インプットが張る空間（探索空間）全体を探索範囲として探索することを意味する。上記の例では、情報の重要度を採択確率として利用して探索することが「大域的」に相当する。
【００５５】
次いで、詳細決定部２３３が、決定された大域候補点を基に、局所的に、次の実験の組み合わせの候補を探索して、１の組み合わせを決定する（ステップＳ１５）。ここで、「局所的に探索する」とは、インプットが張る空間（探索空間）の一部（例えば、起点からの近傍領域）のみを探索範囲として探索することを意味する。上記の例では、大域候補点に所定のランダムノイズを足したものを候補にして探索することが「局所的」に相当する。
【００５６】
次の実験の組み合わせが決定すると、実験部３０が、実験を行ってその結果を記憶部１０に追加する（ステップＳ１６）。
【００５７】
最後に、終了判定部２２が、終了判定を行う（ステップＳ１７）。所定の終了条件を満たした場合（ステップＳ１７のＹｅｓ）、探索決定処理を終了する。一方、所定の終了条件を満たしていない場合（ステップＳ１７のＮｏ）、ステップＳ１１に戻り、次の実験の組み合わせを決定するための探索決定処理を行う。
【００５８】
図３は、図２に示す動作例のより詳細なフローチャートである。本実施形態の組み合わせ探索システムは、例えば、図３に示すような動作を行ってもよい。
【００５９】
図３に示す例では、まず、探索部２０に記憶部１０に記憶されている実験結果が標本データとして入力され、次の実験対象とされる組み合わせの決定指示が行われる（ステップＳ１０１）。なお、最初は、実験結果が１つまたは０であってもよい。なお、０の場合は、ステップＳ１０２〜ステップＳ１０３の処理を飛ばしてステップＳ１０４に進めばよい。
【００６０】
決定指示が行われると、戦略決定部２１は、一様乱数を生成する（ステップＳ１０２）。そして、生成された乱数が特定の値ｐ以下であった場合（ステップＳ１０３）、ステップＳ１０４に進み、それ以外の場合ステップＳ１０５に進む。なお、ステップＳ１０４が、上記の乱択手法による探索決定処理に相当し、ステップＳ１０５〜ステップＳ１０９が上記の二段階探索手法による探索決定処理に相当する。
【００６１】
ここで、ｐは０から１の値をとることが可能であり、０＜ｐ＜０．５程度が好ましい。ｐが大きいほど、乱択手法が採用されやすくなるため、ピークの発見に要する実験回数が減る一方で、ピークの高さを決定するのに要する実験回数が増える。なお、ｐ＝０．５（１−ｎ／Ｎ）のように、ｐを徐々に減らすことも可能である。ここで、ｎはこれまでに行われた実験の数、Ｎはユーザが決めた実験回数の上限値である。ｐをこれまでに行われた実験の数に応じて減らすことで、新しいピークを探すことの重要度を動的に変えることができる。
【００６２】
ステップＳ１０４では、乱択部２４が、次の実験の組み合わせをランダムで生成する。なお、乱択部２４は、ランダムで組み合わせを生成する代わりに、ランダムで作った組み合わせを複数用意し、後述する方法で得られる不確かさＡが最も大きい組み合わせを採択することで、未知の組み合わせを効率的に探索させることも可能である。
【００６３】
なお、ステップＳ１０１〜ステップＳ１０４の処理は、上述したように、最初に複数回ランダムな組み合わせで実験を行う等の手段で代替することも可能である。
【００６４】
ステップＳ１０５〜ステップＳ１０６では、大域決定部２３２が、過去の実験から推測される組み合わせ毎の、目的変数とされる測定値の期待値Ｅおよび不確かさＡを基に、大域候補点とする組み合わせ毎を１つ決定する。本例では、大域決定部２３２は、追加で実験を行うことでピークに関するより多くの情報を得られる組み合わせを、大域候補点に決定する。
【００６５】
大域決定部２３２は、まず、既知の組み合わせに対して、予測部２３１を用いて情報の重要度を算出する（ステップＳ１０５）。ここでは、大域決定部２３２は、予測部２３１を用いて、過去の実験からインプットに対するアウトプットの期待値Ｅおよび不確かさＡを推測させる。なお、取り得る全てのインプットに対して期待値Ｅおよび不確かさＡを計算することは、計算コスト的に困難であるため、以下では過去の実験で用いたインプットに対してのみ期待値Ｅおよび不確かさＡを計算する。そして、大域決定部２３２は、算出された期待値Ｅおよび不確かさＡを基に、情報の重要度を求めることで、より良いアウトプットが得られる可能性が高いインプットを大域的に推測する。
【００６６】
このような重要度を用いることで、複数のピークを探索できるようにする。例えば、アウトプットの最大値を更新できる確率が高い、すなわち単純に期待値Ｅおよび不確かさＡが高いインプットのみを採択する方法の場合、探索されるピークが１つに固定される。これに対して、大域決定部２３２は、実験結果から推測される、追加で実験を行うことでピークに関するより多くの情報を得られるインプット、すなわち取り得るインプット全域でのばらつき（分散）の減り代が大きいインプットを採択することで、探索されるピークが１つに固定されないようにする。なお、計算コストが許す範囲内で、過去の実験で用いたインプット以外のインプット（例えば、探索空間内でこれまでに実験結果が得られていない領域から選択されたいくつかのインプット）に対しても、期待値Ｅおよび不確かさＡを求めることも可能である。
【００６７】
任意のインプットに対するアウトプットの期待値Ｅおよび不確かさＡは、予測部２３１により計算される。予測部２３１は公知の方法を用いることができる。
【００６８】
例えば、標本データにおいてｉで識別されるインプットＸｉに対して、カーネル回帰で期待値Ｅｉおよび不確かさＡｉを求める場合、次の式（１）を用いてもよい。ここで、標本データは、アウトプットが既知のインプットからなるデータの集合をいう。ｉは、例えば、実験番号であってもよい。なお、実験結果が未知のインプットＸｉに対してＥｉおよびＡｉを求める場合はこの限りではない。その場合も、実験結果が未知のインプットＸｉを式（１）に代入して、ＥｉおよびＡｉを求められる。ここで、Ｘは｛ｘ１，ｘ２，ｘ３，・・・｝のように２以上の互いに独立した成分からなる多次元ベクトルである。
【００６９】
【数１】
0006915743.tif 000002
【００７０】
ここで、Ｒｉは、Ｘｉに対して得られたアウトプット（測定値）である。また、Ｋはカーネル関数である。カーネル関数には、ガウスカーネル、多項式カーネル等の公知のものを使うことができる。カーネル関数Ｋ（）の入力であるＸｉ−Ｘｊは、インプットＸｉとインプットＸｊ間の距離を表す。距離としては、ユークリッド距離、マンハッタン距離等を用いることができる。ここで、インプットＸｊは、標本データに含まれるいずれかのインプットを表す。したがって、ｊは１〜標本データ数の間の値を取る。
【００７１】
インプットＸｉにおける情報の重要度Ｚｉは、（１）Ａｉが０またはＥｉが０であるときに０に収束すること、および（２）任意のｉ，ｊに対してＡｉ≦ＡｊかつＥｉ≦ＥｊであるならＺｉ≦Ｚｊであることを満たす関数で与えられてもよい。なお、予測値が負の値を取り得る場合は、上記の条件（１）におけるＡｉに対する「０」を今までの実験結果で得られた最小の値で代替することができる。
【００７２】
Ｚｉの望ましい例の一つとして、「インプットＸｉに対する実験を追加で行うことによる、探索空間全域での予測値の不確かさの減り代の増加に対して増加傾向を示す等正の相関をもつ指標」が挙げられる。この場合、重要度Ｚｉは、次のように計算できる。
【００７３】
上記の式（１）で示したカーネル近似を用いる場合、探索空間内での予測値の不確かさＵは、標本データの分散の総和で評価することができる。すなわち、以下の式（２）を用いて評価できる。
【００７４】
【数２】
0006915743.tif 000003
【００７５】
このとき、インプットＸｉに対して追加で実験を行うことによる、探索空間全域での分散の総和の減り代Ｄｉは、式（３）で与えられる。
【００７６】
【数３】
0006915743.tif 000004
【００７７】
インプットＸｉの情報の重要度Ｚｉとしては、Ｄｉをそのまま用いてもよいし、Ｄｉの代わりに、Ｄｉの平方根をとったものや、Ａｉの次数を５／２以外にしたものを用いることも可能である。なお、これらはいずれも上記の条件（１）および（２）を満たしている。
【００７８】
図４は、１次元関数に対する情報の重要度の一例を示す説明図である。図４（ａ）は、予測対象（１次元の要素）に対する真値（実際の関数）を示している。なお、図４（ａ）において×印はこれまでの実験で得られた結果を表している。また、図４（ｂ）は、予測対象に対して本実施形態で得られる「情報の重要度」の例を示している。また、図４（ｃ）は、比較例として、非特許文献１の手法で得られる優先度の例を示している。図４に示すように、図４（ｃ）では過去の実験で高い特性が得られた左側の山（第１のピーク）付近の優先度が高く、右側の山（すなわち第２のピーク）付近の優先度が著しく低くなっているのに対し、本実施形態の情報の重要度を示す図４（ｂ）では、２つの山付近でバランスよく、高い値が取られている。
【００７９】
なお、ガウス回帰を用いて、インプットＸｉに対する期待値Ｅｉおよび不確かさＡｉを求める場合、インプットＸｉに対して直接、ガウス回帰を適用すると、Ａｉ＝０となってしまう。その場合、予測部２３１は、インプットＸｉの各成分に微小な乱数を加えて、インプットＸｉを、ガウス回帰のデータ（標本のデータ）から外して走査を行えばよい。これにより、非０のＡｉを得ることができる。なお、微小な乱数の例としては、０．０２〜０．１Ｌ程度の乱数が挙げられる。ここで、Ｌは、各成分の取り得る値の広さ（値域幅）を表す。
【００８０】
このようにして得られる情報の重要度Ｚｉに基づいて、大域決定部２３２は、Ｚｉを求めたインプット群（インプットＸｉ、ｉ＝１〜Ｎ等）から大域候補点とする１つのインプットを決定する（ステップＳ１０６）。その際、大域決定部２３２は、各組み合わせ（インプットＸｉ）の採択確率を、情報の重要度Ｚｉに比例するようにする。
【００８１】
なお、大域決定部２３２は、最適化の対象である特性値またはその予測値（上記の期待値Ｅｉ）が小さいインプットＸｉについて、その近傍を含めて追加の探索を求めないのであれば、その情報の重要度Ｚｉを０または無効にする等して、大域候補点の選択肢から除外してもよい。例えば、大域決定部２３２は、期待値Ｅｉに対して閾値（大域候補点とする期待値の下限値Ｅ０）を定め、Ｅｉ＜Ｅ０を満たすＸｉを選択肢から除外してもよい。
【００８２】
また、大域決定部２３２は、特定の組み合わせに対する実験回数Ｎｉや不確かさＡｉについても閾値（大域候補点とする上限値Ｎ０やＡ０）を定め、それらが閾値を上回った場合、すなわちＮｉ＞Ｎ０やＡｉ＞Ａ０の場合に、そのＸｉを選択肢から除外してもよい。
【００８３】
このような除外処理を加えることにより、ピークの高さ測定の精度を落とす代わりに、探索を高速化させることができる。なお、上記の除外処理は、後述する詳細決定部２３３も行うことが可能である。
【００８４】
大域決定部２３２が、情報の重要度Ｚｉが最大のものではなく、Ｚｉに比例した乱択により大域候補点を決定することにより、測定ノイズへの耐性が得られ、特定のピークについてのみ探索を行うことを避けることができる。
【００８５】
大域候補点が決定すると、詳細決定部２３３は、大域候補点にランダムベクトルを加えて、次の実験のインプット（組み合わせ）の候補を生成する（ステップＳ１０７）。詳細決定部２３３は、例えば、大域候補点とされたインプットの各成分に対し、０．１Ｌ程度の乱数を加えることで、次の実験のインプット候補Ｘｉ’を複数生成する。
【００８６】
そして、詳細決定部２３３は、生成したインプット候補Ｘｉ’の各々に対して情報の重要度Ｚｉ’を求め、最も情報の重要度Ｚｉ’の高いインプット候補Ｘｉ’を次に実験するべきインプットに決定する（ステップＳ１０８、ステップＳ１０９）。ここで、インプット候補Ｘｉ’に対する情報の重要度Ｚｉ’は、これまでの実験結果に基づくカーネル回帰やガウス回帰を用いて計算できる。詳細決定部２３３も、次に実験する組み合わせを、大域候補点の近傍に絞ることで、全ての組み合わせ候補に対する情報の重要度を算出する必要がなくなるため、計算コストを落とすことができる。なお、詳細決定部２３３は、上述したアルゴリズムの代わりに、大域候補点にランダムベクトルを加えたものをそのまま使ったり、大域候補点にランダムベクトルを加えたものの中からランダムに選んだり、最も不確かさＡｉの高いインプット候補を選んだりするアルゴリズムを用いることもできる。予測精度は落ちる代わりに、計算コストを減らすことができる。なお、この他にも、詳細決定部２３３における選択アルゴリズムは、大域候補点にランダムベクトルを加えたものの中から期待値Ｅｉが最も高いインプット候補を採用することも可能である。
【００８７】
次に実験する組み合わせが決定されると、探索部２０はその情報を出力する（ステップＳ１１０）。
【００８８】
実験部３０は、次に実験する組み合わせの情報が入力されると、その組み合わせを用いて実験を行い、その結果を記憶部１０に追加する（ステップＳ１１１）。
【００８９】
決定した組み合わせに対する実験結果が得られると、終了判定部２２が、これまでに得られた実験結果またはこれまでの探索経過が探索の終了条件を満たすか否かを判定する（ステップＳ１１２）。探索の終了条件を満たした場合（ステップＳ１１２のＹｅｓ）、そのまま処理を終了する。一方、探索の終了条件を満たしていない場合（ステップＳ１１２のＮｏ）、ステップＳ１１１に戻る。
【００９０】
以上のように、本実施形態によれば、どの組み合わせを優先して測定すべきかの決定を高速に行いつつも、最適化対象とした特性が複数の異なる組み合わせにおいてピークを持つ場合であっても、適切な解とされる組み合わせを高速にかつ安定して求めることができる。ここで、適切な解とは、探索の終了条件によるが、例えば、当該解を得るまでのコストとの両立において所定の網羅性を満たす解であったり、２以上のピークに対応する解等が挙げられる。
【００９１】
なお、上記では、１回の探索決定処理で１つの組み合わせを決定し、組み合わせが１つ決定される毎に実験結果を求める処理を繰り返し行うことにより、最適化を行う方法を示したが、例えば、１回の探索決定処理で複数の組み合わせを決定し、それらに対して各々実験を行い、その結果が反映されたら再び探索決定処理に戻るといった方法も可能である。その場合、例えば、大域決定部２３２が、重要度を採択確率に用いて２以上の大域候補点を決定してもよいし、詳細決定部２３３が、決定された大域候補点に対して重要度に基づいて２以上の組み合わせを決定してもよいし、それらを組み合わせることも可能である。
【００９２】
以下、具体的な例を用いて本実施形態の効果を示す。以下では、本発明の適用範囲とされる組み合わせ問題として、多次元の素材の組成比を解く問題を例示するが、それ以外にも、予測部２３１を用いて結果が予測できる問題、すなわち過去の実績から未知の組み合わせに対する結果が予測できる問題であれば、同様に適用可能である。
【００９３】
［例１］
図５（ａ）は、第１の例である二元の組み合わせの最適化問題の関数Ｆ（ｘ，ｙ）の出力を示すグラフである。関数Ｆは二次元空間上で定義され、図５（ａ）に示すように、２つのパラメータｘ，ｙに応じて出力が変化する。図５（ｂ）は、図５（ａ）で示される複数のピークを模式的に示す模式図である。ここで、関数Ｆは、２つのパラメータｘ，ｙに対して式（４）のように定義される。
【００９４】
【数４】
0006915743.tif 000005
【００９５】
図５（ａ）および図５（ｂ）に示すように、本例の関数Ｆ（ｘ，ｙ）は、（30，30）に負のピークを有するとともに、（20，20）、（40，70）および（100 ，50）に正のピークを有する。以下、図５（ｂ）に示すように、（30，30）の負のピークをＰ０、（20，20）、（40，70）および（100 ，50）の正のピークをそれぞれＰ１、Ｐ２およびＰ３と記す。本例では、ピークＰ０が、ピークＰ１の発見を妨害している。更に、ピークＰ３は、ピーク幅が広く、局所解として機能する。
【００９６】
このような場合において、Ｆ（ｘ，ｙ）が大きい値を持つｘ，ｙの組み合わせを探すことを考える。
【００９７】
なお、図５に示す関数Ｆ（ｘ，ｙ）は、仮想的なものであるが、材料の素材の組成比の組み合わせ問題においても、このような複数の正のピークや、材料の破壊、酸化等に起因する負のピークが存在する場合がある。
【００９８】
図６〜図９はそれぞれ異なる最適化手法で関数Ｆに対してパラメータｘ，ｙの組み合わせを探索した結果を示す模式図である。図中において、太線の丸が、実験をすべき組み合わせとして出力された点（出力点）を表している。出力点が正のピークを示す黒丸の中に存在していれば、そのピークを発見できたことになる。なお、図６〜図９では、実験（本例の場合、測定値の算出）は、１００回ずつ行われている。
【００９９】
図６は、非特許文献１に記載の方法で、関数Ｆ（ｘ，ｙ）を最適化する組み合わせ（ｘ，ｙ）を探索した結果を示す。図６に示すように、当該方法では、ピークＰ３は発見できたが、他のピークが発見できていない。このように、非特許文献１に記載の方法では、局所解であるピークＰ３に捉われてしまい、他のピークが探索されないことがわかる。
【０１００】
図７は、戦略決定部２１により乱択手法と二段階探索手法を組み合わせた上記の方法により、ｘ，ｙの組み合わせを探索した結果を示す模式図である。図７に示すように、当該方法では、全てのピークが発見できたことがわかる。
【０１０１】
図８は、乱択手法を省略して、二段階探索手法のみを用いた場合の探索結果を示す模式図である。図８に示すように、当該方法では、ピークＰ２とピークＰ３は発見できたが、ピークＰ１が発見できなかったことがわかる。これは、ピークＰ０の谷を越えられずに、ピークＰ１付近での実験回数が少なくなり、結果としてピークＰ１付近の点が大域候補点として選択されにくくなったことが原因と推定される。
【０１０２】
図９は、大域決定部２３２において情報の重要度が最も高いインプットを大域候補点に選択して二段階探索手法を行った場合の探索結果を示す模式図である。当該方法では、先に発見したピークＰ２近傍での探索を優先しすぎており、ピークＰ１を発見できていない。
【０１０３】
なお、上記関数Ｆ（）による検証はしていないが、特許文献２に記載の方法の場合、複数のエージェントを用いることでピークＰ２およびピークＰ３は発見できても、ピークＰ０の谷を越えられずに、ピークＰ１を発見するのは困難であると考えられる。それだけでなく、エージェントが同じピークを複数回実験することによる効率の低下が起こると予想される。
【０１０４】
特許文献３に記載の方法の場合、過去の実験結果から統計量を予想するので、実験の重複はある程度避けられることが予想される。しかし、山登り法で組み合わせを最適化するため、特許文献２に記載の方法と同様、ピークＰ０の谷を越えられずに、ピークＰ１を発見するのは困難であると考えられる。
【０１０５】
また、非特許文献２に記載の方法の場合、組み合わせ決定までの計算コストを抑えることができるが、優れた組み合わせ同士を交叉させることで次に測定するべき組み合わせを与えるので組み合わせの多様性を管理しきれず、局所解であるピークＰ３に捉われてしまい、他のピークが探索されないことが予想される。
【０１０６】
また、図１０は、本発明による二段階探索手法と、他の手法（全探索および非特許文献１に記載の手法）とのコストの比較結果を示す説明図である。なお、図１０に示すコストは、局所解へのトラップと谷による探索の妨害を無視した。ここで、組み合わせ決定コストは、具体的には、過去の実験結果から次に実験する１の組み合わせを決定するのに必要な計算量である。また、１ピーク発見コストは、１個のピークを発見するのに必要な実験回数である。また、Ｋピーク発見コストは、Ｋ個のピークを発見するのに必要な実験回数である。
【０１０７】
図１０において、ｄはパラメータの数、すなわち組み合わせの次元数である。ｆは、組み合わせの各パラメータの自由度である。Ｐは、標本データの数である。ｗはピークの幅、ｍは各ピークの頂点を決定するのに必要な実験回数、Ｍはピーク１つを構成する組み合わせの実験優先度（情報の重要度）を０にするのに必要な実験回数である。図１０における各コストの値は、ｄ＝２、ｆ＝１００、ｗ〜１０、ｍ〜１０、Ｍ〜４０として求めた。
【０１０８】
図１０に示すように、本発明による二段階探索手法を利用すれば、Ｋピーク発見コストを小さくすることができるので、特に１回の実験に時間がかかるような問題に対して効果的である。また、図１０に示すコストより、本発明による二段階探索手法は、これまでの手法では扱うことができなかった高次元（特に５次元以上）であっても適用することができる。例えば、図１０における各方法のコスト演算式にｄ＝５、ｆ＝１００、ｗ〜１０、ｍ〜１０、Ｍ〜４０を代入すると、非特許文献１の手法では計算コストが１０の１０乗のオーダになってしまうが、本発明の手法では１０の５乗程度にオーダを抑えることができる。
【０１０９】
［例２］
次に、本発明の最適化手法を用いた、スピン分極率を目的変数とするホイスラー合金（Fe2-xCoxCr1-yMnySi1-z-aAlzGea ）の各素材の合成比率の最適化結果を示す。ここで、組み合わせのパラメータは、ホイスラー合金における、Coの比率ｘ、Mnの比率ｙ、Alの比率ｚ、Geの比率ａの計４つである。
【０１１０】
図１１は、第２の例での実験結果を示すグラフである。図１１には、図３に示す方法で決定された実験番号で識別されるインプット（組成比）の各々に対して逐次実験（数値計算）を行って得られたスピン分極率の変動が示されている。本例では、最初にランダムに決定した１の組み合わせに対して行った実験結果を示す情報が記憶部１０に記憶された状態から、図３に示す方法を用いて上記４つのパラメータの組み合わせからなるインプットを逐次的に決定させ、１つのインプットが決定する度に当該インプットが示す素材に対して実験（数値計算）を行い、その結果を記憶部１０に反映した。インプットの決定および実験は、終了条件である１００回を満たすまで行われた。
【０１１１】
なお、実験結果より、スピン分極が高い領域（図１１において破線で囲った実験結果の組み合わせが位置する領域）は、Co2Cr0.6Mn0.5Al 、Fe0.6Co1.4Cr0.3Mn0.7Si0.3Al0.6Ge0.1 、Fe1.2Co0.8MnSi0.3Al0.4Ge0.3 の３箇所に点在していた。これをパラメータの組み合わせで示すと、（ｘ，ｙ，ｚ，ａ）＝（2.0 ，0.5 ，1.0 ，0 ）、（1.4 ，0.7 ，0.6 ，0.1 ）、（0.8 ，1.0 ，0.4 ，0.3 ）である。なお、最初に発見されたピークは、（1.4 ，0.7 ，0.6 ，0.1 ）である。
【０１１２】
図１２は、第２の例におけるFeの合成比率毎の実験回数の分布を示すグラフである。非特許文献１に記載の方法等では、最初に見つけたピーク近傍の組成比（Fe60% ）ばかりを測定し、他のピークの存在を見落としてしまうところを、上記の方法では複数のピークを発見できている。
【０１１３】
［その他］
例えば、本実施形態の組み合わせ探索方法は、材料以外の任意の多次元関数の最適化に用いることができる。特に、不連続な変化やピーク近傍に谷があるような問題（例えば、過学習）においては、山登り法やエージェントを移動させる方法では谷を超えることが困難であるのに対し、本実施形態の組み合わせ探索方法は適切な乱択が含まれているため、不連続な変化やピーク近傍に谷があるような問題も最適化することが可能である。ここで、適切な乱択には、乱択部２４による乱択だけでなく、大域決定部２３２による情報の重要度を採択確率として用いた乱択も含まれる。
【０１１４】
また、本実施形態の組み合わせ探索方法は、インプットやアウトプットが離散的な値を取る問題にも用いることができる。例えば、交通インフラの最適化問題について考える。道路を建設する場所をインプット、道路によってもたらされる物流をアウトプットとしたとき、インプットおよびアウトプットは離散的な値をとる。本実施形態の組み合わせ探索方法は、過去のインプットとアウトプットの組から未知のインプットに対するアウトプットの予想が可能であれば（カーネル近似、ガウス回帰といった公知の方法を用いることができる）、こうした問題に対しても高速、かつ安定な最適化を行うことができる。離散的なインプットに対する最適化手法として知られる遺伝アルゴリズムに比べ、本実施形態の組み合わせ探索方法は局所解に捉われにくく、また、実験の重複を容易に避けることができる。
【０１１５】
また、本実施形態の組み合わせ探索方法は、アウトプットに誤差を伴うような問題にも用いることができる。例えば、ポーカーを行うＡＩにおいて、各々のカードの価値をあらかじめ設定し、価値の高い手札を残すようにすることを考える。より強いＡＩを作るには、カードの価値のセットをインプットとし、そのＡＩを実際に戦わせたときの最終的な儲けをアウトプットとした多次元最適化問題を解く必要がある。この場合、アウトプットには統計的な誤差が付与される。誤差を考慮しない手法（例えば、非特許文献１、特許文献１〜３に記載の方法等）の場合、偶然高いアウトプットが得られたインプット周辺に実験が集中してしまうが、本手法の場合、戦略決定部２１や大域決定部２３２による実験の分散により、アウトプットのノイズを回避することができる。
【０１１６】
また、図１３は、本発明の各実施形態にかかるコンピュータの構成例を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１と、主記憶装置１００２と、補助記憶装置１００３と、インタフェース１００４と、ディスプレイ装置１００５と、入力デバイス１００６とを備える。
【０１１７】
上述した実施形態の組み合わせ探索システムが備える装置等は、コンピュータ１０００に実装されてもよい。その場合、各装置の動作は、プログラムの形式で補助記憶装置１００３に記憶されていてもよい。ＣＰＵ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、そのプログラムに従って各実施形態における所定の処理を実施する。なお、ＣＰＵ１００１は、プログラムに従って動作する情報処理装置の一例であり、ＣＰＵ（Central Processing Unit ）以外にも、例えば、ＭＰＵ（Micro Processing Unit ）やＭＣＵ（Memory Control Unit ）やＧＰＵ（Graphics Processing Unit）等を備えていてもよい。
【０１１８】
補助記憶装置１００３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例として、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００がそのプログラムを主記憶装置１００２に展開し、各実施形態における所定の処理を実行してもよい。
【０１１９】
また、プログラムは、上記の実施形態における所定の処理の一部を実現するためのものであってもよい。さらに、プログラムは、補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで各実施形態における所定の処理を実現する差分プログラムであってもよい。
【０１２０】
インタフェース１００４は、他の装置との間で情報の送受信を行う。また、ディスプレイ装置１００５は、ユーザに情報を提示する。また、入力デバイス１００６は、ユーザからの情報の入力を受け付ける。
【０１２１】
また、実施形態における処理内容によっては、コンピュータ１０００の一部の要素は省略可能である。例えば、コンピュータ１０００がユーザに情報を提示しないのであれば、ディスプレイ装置１００５は省略可能である。例えば、コンピュータ１０００がユーザから情報入力を受け付けないのであれば、入力デバイス１００６は省略可能である。
【０１２２】
また、上記の実施形態の各構成要素の一部または全部は、汎用または専用の回路（Circuitry）、プロセッサ等やこれらの組み合わせによって実施される。これらは単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。また、上記の実施形態の各構成要素の一部又は全部は、上述した回路等とプログラムとの組み合わせによって実現されてもよい。
【０１２３】
上記の実施形態の各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【０１２４】
次に、本発明の概要を説明する。図１４は、本発明の組み合わせ探索システムの概略を示すブロック図である。図１４に示す組み合わせ探索システム６００は、記憶部６１と探索部６２とを含む。
【０１２５】
記憶部６１（例えば、記憶部１０）は、所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する。
【０１２６】
探索部６２（例えば、探索部２０）は、所定の終了条件を満たすまで、多次元の各要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す。
【０１２７】
このような構成により、複数のピークを有する場合であっても、適切な解を効率よくかつ安定して探索することができる。
【０１２８】
また、図１５は、本発明の組み合わせ探索システムの他の例を示すブロック図である。図１５に示すように、本発明の組み合わせ探索システム６００において、探索部６２は、大域決定部６２１と、詳細決定部６２２とを含んでいてもよい。
【０１２９】
大域決定部６２１（例えば、大域決定部２３２）は、探索空間に含まれる一部の組み合わせに対して算出される情報の重要度に基づいて、次の確認作業で用いる組み合わせを絞り込む。大域決定部６２１は、例えば、情報の重要度を基に、上記の一部の組み合わせの中から１または複数の組み合わせを採択することにより、次の確認作業で用いる組み合わせを絞り込んでもよい。
【０１３０】
詳細決定部６２２（例えば、詳細決定部２３３）は、大域決定部６２１による絞り込み結果に基づいて、次の確認作業で用いる組み合わせを決定する。詳細決定部６２２は、例えば、大域決定部６２１によって採択された組み合わせを起点として探索空間の部分空間を探索して、次の確認作業で用いる組み合わせを決定してもよい。
【０１３１】
大域決定部６２１による絞り込みを行った上で、詳細決定部６２２が次の確認作業で用いる組み合わせを決定する構成とすることにより、例えば、複数のピークに対応する解を高速に求めることができる。
【０１３２】
なお、上記の実施形態は以下の付記のようにも記載できる。
【０１３３】
（付記１）所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部と、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す探索部とを備えることを特徴とする組み合わせ探索システム。
【０１３４】
（付記２）探索部は、探索空間に含まれる一部の組み合わせに対して算出される情報の重要度に基づいて、次の確認作業で用いる組み合わせを絞り込む大域決定部を含む付記１に記載の組み合わせ探索システム。
【０１３５】
（付記３）大域決定部は、一部の組み合わせとして、実績データに含まれるインプット情報が示す要素の組み合わせに対して、情報の重要度を算出する付記２に記載の組み合わせ探索システム。
【０１３６】
（付記４）大域決定部は、情報の重要度を基に、一部の組み合わせの中から１または複数の組み合わせを採択することにより、次の確認作業で用いる組み合わせを絞り込む付記２または付記３に記載の組み合わせ探索システム。
【０１３７】
（付記５）大域決定部は、情報の重要度に比例した確率で、一部の組み合わせの中から、次の確認作業で用いる組み合わせの探索起点とする１の組み合わせを採択することにより、次の確認作業で用いる組み合わせを絞り込む付記２から付記４のうちのいずれかに記載の組み合わせ探索システム。
【０１３８】
（付記６）探索部は、大域決定部によって採択された組み合わせを起点として探索空間の部分空間を探索して、次の確認作業で用いる組み合わせを決定する詳細決定部を含む付記４または付記５に記載の組み合わせ探索システム。
【０１３９】
（付記７）探索部は、一定の確率で、探索空間の中からランダムに採択された組み合わせを、次の確認作業で用いる組み合わせとして決定する付記１から付記６のうちのいずれかに記載の組み合わせ探索システム。
【０１４０】
（付記８）情報の重要度は、実績データから算出される、実績データに組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの予測値の不確かさの減り代に基づく指標である付記１から付記７のうちのいずれかに記載の組み合わせ探索システム。
【０１４１】
（付記９）情報の重要度は、実績データから回帰分析により算出されるその組み合わせに対する所定のパラメータの期待値と期待値の不確かさとに基づいて算出される、探索空間全体での期待値の分散の減り代に基づく指標である付記１から付記７のうちのいずれかに記載の組み合わせ探索システム。
【０１４２】
（付記１０）ある組み合わせｉに対する情報の重要度をＺｉ、実績データから回帰分析により算出されるその組み合わせに対する所定のパラメータの期待値をＥｉ、期待値の不確かさをＡｉとした場合に、任意の組み合わせに対する情報の重要度が、Ｅｉが最小値またはＡｉが０であるときに０に収束すること、および任意のｉ，ｊに対してＡｉ≦ＡｊかつＥｉ≦ＥｊであるならＺｉ≦Ｚｊであることを満たす関数で与えられる付記１から付記９のうちのいずれかに記載の組み合わせ探索システム。
【０１４３】
（付記１１）次の確認作業で用いる組み合わせを示す情報を出力する出力部と、記憶部に新たな実績データを追加するための入力部とを備える付記１から付記１０のうちのいずれかに記載の組み合わせ探索システム。
【０１４４】
（付記１２）確認作業を行うための所定の装置を備え、出力部は、所定の装置に、次の確認作業で用いる組み合わせを示す情報とともに、組み合わせを用いた確認作業の指示を行い、入力部は、所定の装置から確認作業の結果を示す情報を受け付けると、記憶部に新たな実績データを追加する付記１１に記載の組み合わせ探索システム。
【０１４５】
（付記１３）所定の終了条件が、確認された所定のパラメータの値、解とされる組み合わせの数、不確かさ、確認作業の回数の少なくともいずれかを用いて規定されている付記１から付記１２のいずれかに記載の組み合わせ探索システム。
【０１４６】
（付記１４）多次元の組み合わせ問題が、所定の特性に対する材料合成の条件パラメータの組み合わせ問題、多次元関数の出力値に対する入力パラメータの組み合わせ問題、離散的な値をとる要素を含む多次元の組み合わせ問題、測定値にノイズが含まれるパラメータに対する多次元の組み合わせ問題、および所定の特定に対する次元削減されたデータの組み合わせ問題のいずれかである付記１から付記１３のいずれかに記載の組み合わせ探索システム。
【０１４７】
（付記１５）所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能な情報処理装置であって、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返す探索部を備えることを特徴とする情報処理装置。
【０１４８】
（付記１６）所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能な情報処理装置が、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返すことを特徴とする組み合わせ探索方法。
【０１４９】
（付記１７）所定の確認作業を伴う所定のパラメータに対する多次元の組み合わせ問題における実績データであって、過去に確認作業または実空間において多次元の各要素がとった値の組み合わせを示すインプット情報と、その時にインプット情報が示す組み合わせに対して得られた所定のパラメータの値を示すアウトプット情報とを対応づけた情報を記憶する記憶部にアクセス可能なコンピュータに、所定の終了条件を満たすまで、要素の組み合わせ毎に定義される指標であって、実績データから算出される、実績データにその組み合わせに対する新たなアウトプット情報が追加されることによる探索空間全体における所定のパラメータの値の不確かさの変化量を基に定義される指標である情報の重要度に基づいて、次の確認作業で用いる組み合わせを少なくとも１つ決定する処理を繰り返し実行させるための組み合わせ探索プログラム。
【０１５０】
以上、本実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１５１】
この出願は、２０１８年３月２３日に出願された日本特許出願２０１８−０５５４９４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用の可能性】
【０１５２】
本発明は、複数のピークを有する多次元の組み合わせ問題だけでなく、実験等結果を得るまでにある程度高いコストを伴う多次元の組み合わせ問題やアウトプットに誤差を伴う多次元の組み合わせ問題に対して最適化を行う用途に好適に適用可能である。
【符号の説明】
【０１５３】
１０  記憶部
２０  探索部
２１  戦略決定部
２２  終了判定部
２３  二段階決定部
２３１  予測部
２３２  大域決定部
２３３  詳細決定部
２４  乱択部
３０  実験部
６００  組み合わせ探索システム
６１  記憶部
６２  探索部
６２１  大域決定部
６２２  詳細決定部
１０００  コンピュータ
１００１  ＣＰＵ
１００２  主記憶装置
１００３  補助記憶装置
１００４  インタフェース
１００５  ディスプレイ装置
１００６  入力デバイス
【図１】
0006915743.tif 000006
【図２】
0006915743.tif 000007
【図３】
0006915743.tif 000008
【図４】
0006915743.tif 000009
【図５】
0006915743.tif 000010
【図６】
0006915743.tif 000011
【図７】
0006915743.tif 000012
【図８】
0006915743.tif 000013
【図９】
0006915743.tif 000014
【図１０】
0006915743.tif 000015
【図１１】
0006915743.tif 000016
【図１２】
0006915743.tif 000017
【図１３】
0006915743.tif 000018
【図１４】
0006915743.tif 000019
【図１５】
0006915743.tif 000020