タダ飯はない定理

数学の民間伝承では、デイビッド・ウォルパートとウィリアム・マクレディの「ノー・フリー・ランチ」（NFL）定理（複数形になることもある）は、「無料の昼食などない」という諺、つまり成功への近道はないということを暗示している。これは1997年の「最適化のためのノー・フリー・ランチ定理」に登場した。^{[ 1 ]}ウォルパートは以前にも機械学習（統計的推論）のためのノー・フリー・ランチ定理を導出していた。^{[ 2 ]}

2005年にウォルパートとマクレディ自身が、彼らの論文の最初の定理は「すべての可能な問題にわたってパフォーマンスを平均すると、任意の2つの最適化アルゴリズムは同等である」と述べていることを明らかにした。^{[ 3 ]}

「ノー・フリー・ランチ」（NFL）定理は、ウォルパートとマクレディが実際に証明した定理の、簡単に述べられ理解しやすい帰結です。客観的には証明された定理よりも弱く、したがってそれらを包含するものではありません。さまざまな研究者がウォルパートとマクレディの研究を実質的に拡張してきました。NFL定理が研究分野の文脈でどのように使用されるかという点では、探索と最適化におけるノー・フリー・ランチは、特に探索^{[ 4 ]と最適化[ 1 ]}の統計的同一性のためにデータを数学的に分析することを目的とした分野です。

NFLは重要な洞察をもたらすと主張する学者もいる一方で、NFLは機械学習の研究にはほとんど関係がないと主張する学者もいる。^{[ 5 ] [ 6 ] [ 7 ]}

ちょうど2日間存在し、各日が晴れか曇りのどちらかの状態しかないおもちゃの宇宙を想定してみましょう。この宇宙には、正確に4つの可能な歴史があります。

1. （晴れ、曇り）：宇宙は1日目は晴れで、2日目は曇りです。
2. （晴れ、晴れ）
3. （曇り、曇り）
4. （曇り、晴れ）

1日目が晴れであれば2日目も晴れと予測するなど、履歴#2で成功する予測戦略は、履歴#1では失敗し、その逆もまた同様です。すべての履歴が等確率である場合、どの予測戦略も同じスコアとなり、精度率は0.5になります。^{[ 8 ]}

ウォルパートとマクレディは、民俗的定理と密接に関連する2つのNFL定理を提示している。彼らの論文では、次のように述べている。

関連する結果をNFL定理と名付けたのは、アルゴリズムが特定のクラスの問題で優れたパフォーマンスを発揮する場合、必然的に残りのすべての問題のセットでパフォーマンスが低下するということを示すためです。^{[ 1 ]}

最初の定理は、最適化の進行中に目的関数が変化しないことを仮定し、2番目の定理は、目的関数が変化する可能性があることを仮定している。 ^{[ 1 ]}

この定理は、以下のように同義的に定式化することもできる。

ここで、ブラインドサーチとは、アルゴリズムの各ステップで、要素が${\displaystyle v\in V}$は、一様確率分布に従って、の要素からランダムに選択される。${\displaystyle V}$これまで選ばれていないもの。

要するに、これは、すべての関数fが等確率である場合、最適化の過程で任意のm個の値のシーケンスを観測する確率はアルゴリズムに依存しないことを意味します。Wolpert と Macready の分析フレームワークでは、パフォーマンスは観測値のシーケンスの関数であり (例えば、実時間ではない)、目的関数が一様にランダムに抽出される場合、すべてのアルゴリズムのパフォーマンスが同一分布になること、またすべてのアルゴリズムの平均パフォーマンスが同一になることが容易に導かれます。しかし、すべてのアルゴリズムの平均パフォーマンスが同一であることは定理 1 を意味しないため、通説の定理は元の定理と等価ではありません。

定理2は、時間変動目的関数に対する同様の、しかし「より微妙な」NFL結果を確立する。^{[ 1 ]}

NFL定理は、「環境が一様ランダムである」場合に何が推論できるか（機械学習におけるNFLの場合）あるいは何が見つかるか（探索におけるNFLの場合）という疑問から生まれたものではありません。むしろ、一様ランダム性は、アルゴリズムAがアルゴリズムBよりも優れた性能を発揮する環境の数と、アルゴリズムBがアルゴリズムAよりも優れた性能を発揮する環境の数を比較するためのツールとして用いられました。NFLは、（適切な重み付けをすれば）これらの環境の集合には同数の環境が存在することを示しています。

これは、「環境」が正確に何であるかという多くの定義に当てはまります。特に、学習アルゴリズムAが（平均的に）Bを上回る事前分布（適切な重み付けをしたもの）は、その逆の場合と同数存在します。NFLにおいて最も重要なのは、このような事前分布の集合に関する記述であり、すべての環境に等しい確率を割り当てる単一の特定の事前分布において、2つのアルゴリズムが同等の性能を発揮するという事実ではありません。

NFLは一連の問題の根本的な限界を理解する上で重要ですが、実際に発生する可能性のある問題の個々のインスタンスについては何も述べていません。つまり、NFLは数学的な記述に含まれることを述べているだけで、それ以上のものではありません。たとえば、アルゴリズムが事前に固定され、固定されたアルゴリズムの最悪ケースの問題が事後的に選択される状況に適用されます。したがって、実際に「良い」問題がある場合、または特定の問題インスタンスに対して「良い」学習アルゴリズムを選択できる場合、NFLはこの特定の問題インスタンスに関する制限については何も述べていません。NFLは、学習アルゴリズムや探索ヒューリスティクスの一般化を示唆する他の論文の結果と矛盾しているように見えるかもしれませんが、NFLの正確な数学的論理と直感的な解釈の違いを理解することが重要です。 ^{[ 9 ]}

NFLの直感に反する意味合いの1つを説明するために、2つの教師あり学習アルゴリズムCとDを固定するとします。次に、目標関数fをサンプリングして、入力と出力のペアのセットdを生成します。問題は、dの外側にある点に関連付けられる出力を予測するために、dに対してCとDのどちらをトレーニングするかをどのように選択すべきかということです。

科学や統計学のほぼすべての分野で、CとDのどちらを選ぶかという問いに答えるためには、dに対してこれら2つのアルゴリズムを用いて交差検証を行うのが一般的です。言い換えれば、dからCまたはDのどちらを用いて一般化するかを決定するために、d内でテストした際にどちらのアルゴリズムがサンプル外のパフォーマンスが優れているかを確認します。

CとDは固定されているため、この2つから選択するために交差検証を用いる方法は、それ自体がアルゴリズム、つまり任意のデータセットから一般化する方法である。このアルゴリズムをAと呼ぶ。（Aは、科学的方法そのものの簡略化されたモデルであると言えるだろう。）

また、交差検証を回避して選択することもできます。つまり、dの範囲内でサンプル外のパフォーマンスが悪い方を基準に、C と D のどちらかを選択できます。ここでも、C と D は固定されているため、この交差検証の回避自体がアルゴリズムとなります。このアルゴリズムを B と呼びましょう。

NFLは（大まかに言えば）AがBに勝つのと同じ数の目標関数（および関連するデータセットd）でBがAに勝たなければならないと述べている。この非常に具体的な意味では、科学的方法は「反」科学的方法に勝つのと同じくらい簡単に負けることになる。^{[ 10 ]}

NFLは、目標関数がすべての可能な関数の均一分布から選択される場合にのみ適用されます。そうでない場合、つまり特定の目標関数が他の目標関数よりも選択される可能性が高い場合、AはBよりも全体的に優れたパフォーマンスを発揮する可能性があります。NFLの貢献は、適切なアルゴリズムを選択するには、そのアルゴリズムが使用される目標関数の種類について仮定を置く必要があることを示している点にあります。仮定がなければ、科学的方法のような「メタアルゴリズム」は、ランダム選択よりも優れたパフォーマンスを発揮しません。

NFLが重要な洞察をもたらすと主張する学者もいる一方で、NFLは機械学習の研究にはほとんど関係がないと主張する学者もいる。^{[ 5 ] [ 6 ] [ 7 ]}例えば、コルモゴロフ複雑度の低いシーケンスの方が複雑度の高いシーケンスよりも起こりやすい場合、オッカムの剃刀が正しいとすれば、（現実世界で観察されるように）交差検証などのアルゴリズムは、（ランダム選択や反交差検証と比較して）実際の問題で平均的に優れたパフォーマンスを発揮する。^{[ 11 ]}

しかし、コルモゴロフ複雑性に基づく議論を用いて現実世界の特性を確立するには、計算不可能であり、任意の加法定数を除いて定義されていないため、形式的に大きな課題があります。これらの課題を部分的に認識して、最近では、「メタ帰納法」を使用することで、チューリングマシンを呼び出しずにノーフリーランチ定理を回避する方法があると主張されています。^{[ 12 ] [ 13 ]}さらに、機械学習モデルのコルモゴロフ複雑性は、データラベルの圧縮によって上限を設定でき、コルモゴロフ複雑性を介して非空虚なクロスドメイン一般化の境界を生成することが可能です。^{[ 7 ]}

• タダ飯はない定理
• 定理を説明する図