ノーフリーランチの定理

2つのノーフリーランチの定理

ノーフリーランチの定理と呼ばれるものは、大きく分けて2つあります。ひとつは探索・最適化についての定理(Wolpert and Macready 1997)、もうひとつは教師あり機械学習についての定理(Wolpert 1996)です。どちらも、特定の前提を置かずに比べると、どのアルゴリズムにも無条件の優位は無いことを述べています。

探索・最適化についての定理

中心となる主張は次のとおりです。コスト関数の極値(最大値や最小値)を探索するすべてのアルゴリズムは、あらゆる可能なコスト関数について平均すると、まったく同じ性能になります。この定理は、探索空間が有限であり、アルゴリズムが同じ点を再び評価しない場合を対象にしています。

Wolpert と Macready は、これを次のようにも言い換えています。あるアルゴリズムAが一部のコスト関数でアルゴリズムBより優れているなら、大まかに言えば、Bの方がAより優れているコスト関数がちょうど同じ数だけ別に存在します。

帰結: 性能向上は別の問題で相殺される

この定理から、どんな探索・最適化アルゴリズムについても、ある種類の問題で性能が上がった分は、別の種類の問題での性能低下によって正確に支払われることになります。すべての問題で他より優れた、万能のアルゴリズムは存在しないということです。

原論文では、この結果を出発点として、探索問題の幾何的な性質や情報理論的な側面の分析、個々の探索アルゴリズムの性能を評価するための数学的な基準の導出、ミニマックスの観点、途中までの探索の様子から同じコスト関数での今後のふるまいを予測することの妥当性、時間とともに変わるコスト関数などにも議論を広げています。最後に、生物に着想を得た探索手法をどこまで正当化できるかについても論じています。

教師あり機械学習についての定理

ここまでの探索・最適化についての記述は、Wolpert and Macready(1997)の原論文の要旨を直接引用したものです。これに対し、教師あり機械学習についての定理は、この2つの定理を整理したno-free-lunch.org(Martin Sewellによる文献整理ページ)の要約に基づきます。同ページによれば、Wolpert (1996) は、ノイズの無い状況で、損失関数を誤分類率とし、訓練データに含まれない事例での誤差に関心があるときには、学習アルゴリズムどうしにアプリオリな(事前に言える)優劣は無いことを示しました。どれだけうまくいくかは、学習アルゴリズムが、データが与えられたときの目的関数の実際の事後分布とどれだけ合っているかによって決まります。

試験との関わり

ノーフリーランチの定理はシラバス2024のキーワードに含まれます。2つの定理があること、平均すると性能が同じになるという主張、そこから万能のアルゴリズムは無いと言えることを押さえておきましょう。