no free lunch定理

昨日のエントリ
ちょwww - rindai87の日記
のしましまさんのコメントより

機械学習は,カーネルなどのモデルに大きく予測性能が依存依存します.また,no free lunch定理いうものがあり,いかなる問題に対しても他より高い予測性能を示すモデルは存在しえません.

なにっ!
聞いたこともないので調べてみる。

No Free Lunch Theorem—理想の**の探し方—
http://mikilab.doshisha.ac.jp/dia/research/report/2007/0916/007/report20070916007.html

端的に言うと

1995年にDavid H. WolpertとWilliam G. MacreadyによりNo Free Lunch定理(NFL)が発表された.
NFLとはすべての評価関数に適用できる効率のよいアルゴリズムは存在しない.
という定理である.
http://mikilab.doshisha.ac.jp/dia/research/report/2007/0916/007/report20070916007.html

ということのようだ。
さらに

ある特定の問題に関して最適化されたアルゴリズムは多く存在するが, 平均すると汎用的なアルゴリズムと大きな差は見られない
http://mikilab.doshisha.ac.jp/dia/research/report/2007/0916/007/report20070916007.html
とのこと。

ほほぅ。
ざっと見ただけなのでもう少し調べてみる必要はありそうだ。


昨日は

データの性質に合うカーネル関数を「うまく設計」することができるってことは、データの構造がある程度分かっているってことで、それなら計算コストの高い機械学習じゃなくてもよくね?って意見があるらしい。
ちょwww - rindai87の日記

と言ったが、これは少しNo Free Lunch定理とは違うところで主張したつもり。


特定の問題に特化したアルゴリズムの効率が改善されればされるほど、その問題の構造等の理解が深まっていく。
問題への理解が深まり、究極的に問題のモデルを完全に数式で記述できちゃうと、そもそも機械学習いらないじゃん?ってなる。
SVMの場合、その問題構造を完全に理解して、このカーネルを使えば完全に分離できちゃうよ、っていうのが分かってる状態って言うのは、すなわちもうそんなカーネル使ってわけのわからん高次元空間に写像してそこで線形分離しちゃったりなんかしないでも、別の手段を使えるでしょうよ、ということになるだろう。
ってなつもりで書いてみた。


あまりに極端なところを言ってるだけで、現実問題としては、少しずつ理解を深めて、問題に適したカーネルを選択したり設計したりするしかないのだけどね。


少し話が飛躍したな。
今の自分の理解では、
ちょっとまだ完全には良く分かってない問題なんだよねーって時に、
ちょいとあなた、そんな時にはこのアルゴリズムを使ってみないさいよ。
というアルゴリズムは存在しないってことがNo Free Lunch定理なのかと。
ある程度限定された条件下での話みたいだけど。


そういう意味では、

我々は進化論的計算、特に遺伝的アルゴリズム遺伝的プログラミングをさまざまな問題に応用する研究をしているが、次のような質問をよく受ける。

  1. なぜその問題に遺伝的アルゴリズムを適用したのか。
  2. そもそも遺伝的アルゴリズムというのはよい探索手法なのか。

No Free Lunch Theorem—理想の**の探し方—

すごく良く分かる。
「はいっ」って渡された論文から始まった今の研究だけど、このことについて最近良く考えてる。
しかし答えはまだ出てないなぁ、ってかあるのかな?


って言っておいて、専門家の詳しい先生が降臨してびしびし指摘してくれることを望むメソッド。