ノーフリーランチ定理(読み)ノーフリーランチていり(英語表記)no-free-lunch theorem

ブリタニカ国際大百科事典 小項目事典 「ノーフリーランチ定理」の意味・わかりやすい解説

ノーフリーランチ定理
ノーフリーランチていり
no-free-lunch theorem

あらゆるコスト関数に対する探索量の平均は,どの探索アルゴリズムも同じである,と結論する定理。コスト関数とは,引数に対してコスト(損失あるいはペナルティ)を与える関数一般をさす。「有限集合から有限集合への関数として与えられるコスト関数を最適化(最小化あるいは最大化)する変数値を求めよ」という問題に対し,「探索アルゴリズムが同じ変数値の組み合わせを一度しか探索しない(→ヒューリスティック探索)」,「探索アルゴリズムがコスト関数に関する先験的知識をまったくもっていない」などの仮定をしたときに結論づけられる。アメリカ合衆国の物理学者デービッド・ウォルパートとウィリアム・マクレディが 1995年に発表した。この定理は,あらゆる問題に対して万能の探索アルゴリズムが存在しないので,同じ変数値の組み合わせを一度しか探索しないようにアルゴリズムを作成すること以外は,先験的知識を利用せずにアルゴリズム自体に工夫をしても性能改善は起こらないことを示唆している。ウォルパートとマクレディは探索問題だけでなく,機械学習をはじめとする広い範囲の最適化問題でも同様の定理が成立することを示した。観点を変えれば,探索問題や最適化問題を解くとき,探索アルゴリズムの性能を向上させたければ,コスト関数や,問題領域などにかかわる先験的知識を利用することが必要だといえる。

出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報

今日のキーワード

部分連合

与野党が協議して、政策ごとに野党が特定の法案成立などで協力すること。パーシャル連合。[補説]閣僚は出さないが与党としてふるまう閣外協力より、与党への協力度は低い。...

部分連合の用語解説を読む

コトバンク for iPhone

コトバンク for Android