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

ブリタニカ国際大百科事典 小項目事典

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

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

出典　ブリタニカ国際大百科事典 小項目事典