ノーフリーランチ定理（No Free Lunch theorem）とは？：AI・機械学習の用語辞典

用語「ノーフリーランチ定理（No Free Lunch theorem）」について説明。全ての問題において優れた性能を発揮できる“万能”の「教師ありの機械学習モデル」や「探索／最適化のアルゴリズム」など（＝無料のランチ）は理論上、存在しないことを指す。

[一色政彦，デジタルアドバンテージ]

連載目次

用語解説

　機械学習におけるノーフリーランチ定理（No Free Lunch theorem：「無料のランチはない」定理）とは、あらゆる問題を効率よく解けるような“万能”の「教師ありの機械学習モデル」や「探索／最適化のアルゴリズム」などは存在しない（理論上、実現不可能）、ということを主張する定理である。

図1　ノーフリーランチ定理のイメージ（後述の「言葉の歴史」を参照）

　教師ありの機械学習モデルに対するノーフリーランチ定理は、数学者のDavid H. Wolpert氏が1996年の論文の中で提示した。また、探索／最適化のアルゴリズムに対するノーフリーランチ定理は、David H. Wolpert氏とWilliam G. Macready氏が1997年の論文で提示している（※特にこちらの論文が有名）。2000年前後には多くの研究者が、この他にもさまざまな形でノーフリーランチ定理を証明／実証している（参考：「No Free Lunch Theorems」）。

　1997年の論文の一節を引用すると、

We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.
「もしアルゴリズムが、ある特定領域の問題において優れた性能を発揮しているのなら、それ以外の残り全ての問題群においては性能が低下する代償を支払う必要がある」ということを示す一連の結果を、我々は「NFL（ノーフリーランチ）定理」と呼んでいる。［筆者による翻訳］

と説明されている（※引用文献：「David H. Wolpert and William G. Macready, "No Free Lunch Theorems for Optimization" IEEE Transactions on Evolutionary Computation Vol.1 No.1 pp.67-83,1997.」。69ページ目の「III. THE NFL THEOREMS」から一文を引用）。

　ノーフリーランチ定理の数学的な意味や証明については本稿では割愛する。

　「ノーフリーランチ」という用語の成り立ちについても簡単に紹介しておこう。

「ノーフリーランチ」という言葉の歴史

　“No free lunch”という言葉は、「無料で何かを手に入れるのは不可能だ」という考えを伝えるための一般的な英語の格言であり、

“There ain't no such thing as a free lunch.”（略語：TANSTAAFL、「タンスターフル」と読む、日本語訳：タダより高いものはない）

という有名なフレーズから来ている。この“free lunch”（無料のランチ）は、19世紀の西部開拓時代（1860年以降）〜1920年代（※最初に言い始めた人は不明で、始まりの年代も詳細不明。少なくとも1891年以前から使われている用語。詳しくは、後述の「ここまでの歴史」のリンク先を参照）、アメリカのバーでお酒を飲む客を誘い込むために慣習的に提供されていた「無料ランチ」に起源がある。例えるなら、名古屋でモーニングコーヒーを飲みに行くと、トーストされたパンやゆで卵などが無料で付いてくるが、そんな感じだろう（むしろパンと卵を目的に、毎朝、コーヒーを飲みに行くようになるわけだが……）。

　当時のアメリカのバーで、昼食として塩辛いハムやチーズ、クラッカーなどが無料で提供されると、客は結局、ビールを何杯も飲むことになる。「無料のランチ」を食べたいだけ注文すると、その分だけ、酒量も増えてしまい、最終的には高額なランチ代となってしまうのだ。このことから、“There ain't no such thing as a free lunch.”（タダよりも高いものはない）という戒めが、バーの利用者の間で言われるようになった。

　この戒めは、1930年〜1950年代になると格言として生き残り、さまざまな場面で使われるようになった（※ここまでの歴史については、この記事「There ain't no such thing as a free lunch - Wikiwand」が詳しい）。

　その後、このフレーズと略語が、1966年に出版されたRobert Heinlein氏のSF小説『The Moon Is a Harsh Mistress』（邦題：『月は無慈悲な夜の女王』）や、1975年に出版された経済学者Milton Friedman氏の本『There's No Such Thing As a Free Lunch』などで使われて、さらに有名となり格言として普及した（※参考：「ON LANGUAGE; Words Out in the Cold - The New York Times」）。それからさまざまな分野でこの用語が使われるようになり、機械学習の分野でも上記のように「ノーフリーランチ定理」という用語が定着しているというわけである。機械学習を実践する人は必ず知っておかなければならない用語となっている。

「AI・機械学習の用語辞典」