NFL定理をめぐるDembski
フィットネス関数とアルゴリズムが独立であれば、進化型アルゴリズム（遺伝的アルゴリズム）のパフォーマンスは、ランダムサーチを超えないというNFL定理。
インテリジェントデザイン理論家Dr. William Dembskiは、これが生物進化の不可能性を証明していると喜び、"No Free Lunch"という本を書いた。それは、間違いだと、定理をつくったD.H.Wolpertに批判され、Dembskiはそのときは撤退したようである。
Dembski (2002)
インテリジェントデザインの数学担当のWilliam Dembskiは"No Free Luch"(2002)において、
The No Free Lunch (NFL) theorems (Wolpert and Macready 1997) prove that evolutionary algorithms, when averaged across fitness functions, cannot outperform blind search. This means that an evolutionary algorithm can find a specified target only if complex specified information already resides in the fitness function. Evolutionary algorithms cannot account for the complex specified information we see in life; that information has to come from design.
No Free Lunch(NFL)定理(Wolpert and Macready 1997)は、フィットネス関数が平均化されている場合、進化アルゴリズムはブラインドサーチを超えられないことを示した。これは、進化アルゴリズムが設定されたターゲットを見つけられるのは、フィットネス関数に設定された情報が含まれている場合のみだということを意味する。進化アルゴリズムは、我々がみる生物のような複雑に設定された情報を説明できない。と言った。
進化型アルゴリズム(遺伝的アルゴリズム)の話を生物進化にすりかえるトリッキーな物言いではあるが、とりあえず進化論を攻撃。
H. Allen Orr (2005)による批判
ロチェスター大学教授(生物学)Dr. H. Allen Orrは、The New Yorker(批評・随筆・投資レポート・フィクションなどを掲載する米国の週刊誌 wiki)に掲載した記事で、DembskiのNFL定理の誤用を批判した。
Another problem with Dembski’s arguments concerns the N.F.L. theorems. Recent work shows that these theorems don’t hold in the case of co-evolution, when two or more species evolve in response to one another. And most evolution is surely co-evolution. Organisms do not spend most of their time adapting to rocks; they are perpetually challenged by, and adapting to, a rapidly changing suite of viruses, parasites, predators, and prey. A theorem that doesn’t apply to these situations is a theorem whose relevance to biology is unclear. As it happens, David Wolpert, one of the authors of the N.F.L. theorems, recently denounced Dembski’s use of those theorems as “fatally informal and imprecise.” Dembski’s apparent response has been a tactical retreat. In 2002, Dembski triumphantly proclaimed, “The No Free Lunch theorems dash any hope of generating specified complexity via evolutionary algorithms.” Now he says, “I certainly never argued that the N.F.L. theorems provide a direct refutation of Darwinism.”
Dembskiの議論のもうひとつの問題点はN.F.L定理に関するものだ。最近の研究で、2つもしくはそれ以上の種が相互作用する共進化(co-evolution)には、これらの定理は適用できないことがわかった。ほとんどの進化は間違いなく共進化だ。生物は適応にほとんど時間を費やさない。急速に変化するウィルス、寄生生物、捕食者および獲物に絶え間なく挑戦され、これに適応している。このような状況に適用できない定理の、生物学における妥当性は不明だ。たまたま、N.F.L.定理の作者のひとりであるDavid Wolpertは、最近、Dembskiの定理の使い方は、致命的に公式にあっておらず(fatally informal)、不正確だと批判している。これに対するDembskiの見かけの対応は戦術的後退。2002年にDembskiは「No Free Luncj定理は進化論のアルゴリズムで、設計された複雑さ(Specified Complexity)を生成できるという望みを打ち砕く。」と勝ち誇って宣言した。今は「私は、N.F.L.定理がダーウィン説を直接論破するものだとは決して言っていない」と、言っている。
この批判は、定理を作ったWolpertによる批判をそのまま引用した記述となっている。
Dembski (2005)の反論
Dr. William Dembskiは自らのブログ(Uncommon Decent)でただちに反論した。
Orr tries to get around the force of displacement by remarking that the NFL theorems don’t hold in the case of co-evolution (fitness landscapes that vary over time as organisms/population agents evolve). Actually, I dealt with co-evolution in section 4.10 of my book No Free Lunch, and argued there that co-evolution does not overcome the displacement problem. In his 2002 Boston Review critique of that book, Orr claimed that I hadn’t even addressed the issue of co-evolution when I had devoted a whole section to it. More importantly, the No Free Lunch theorem that I prove in my paper “Searching Large Spaces” does in fact hold for co-evolutionary scenarios, as does the displacement theorem that I prove there.
NFL定理が共進化(生物/生物集団が進化するのに従って時間がたつにつれて異なるフィットネス状況)の場合で成立しないと言って、Orrは"Displacement"の力を回避しようとしている。実際、私の本"No Free Lunch"の4.10で、共進化に触れ、そこで、共進化が"Displacement問題"を解決しないと論じた。
2002年の、本に対するBoston Reviewの批評で、Orrは、私が一節をまるまる使って論じていたにもかかわらず、私が共進化の問題を記述してさえいなかったと主張した。さらに重要なことは、私が論文“Searching Large Spaces”で証明したことだが、No Free Lunch定理は、そこで私が証明した"Displacement定理"と同じく、共進化シナリオに対しても有効だ。
NFL定理ではなく"Displacement"が重要で、それは前から言っているという反論。だったら、本のタイトル"No Free Lunch"はなんだったんだということになるのだが。
で、この"Displacement"とは何かと言うと、Dembski "No Free Lunch"によれば
the problem of finding a given target has been displaced to the new problem of finding the information j capable of location that target. Our original problem was finding a certain target within phase space. Out new problem is finding a certain j within the information resource space J.
与えられた目標を見つける問題は、目標としている場所がわかる情報jを見つける新しい問題に置き換わった。我々のもとの問題は、ある目標を位相空間内で見つけることだった。そして、新しい問題はあるjを情報リソース空間Jの中に見つけることだ。
これは、「宝物が埋まっている島があったとき、島をくまなく探すのではなく、世界地図からその島を探す」という問題の置き換えらし[
Mark Perakh 2004
]。
Mark PerakhによるDisplacement批判
このDIsplacementについては、これより前の2004年に、Mark Perakhによって批判されている。
What Dembski seems to ignore is the crucial point that I have stressed several times: the NFL theorems legitimately compare the performance of any two algorithms, but what they compare is performance averaged over all possible fitness landscapes. This is an intersting theoretical conclusion and a tool for investigating the mutual relationship between fitness functions and search algorithms. It has no relevance for problems of practical interest encountered in real life, where we are interested in finding out whether or not a given algorithm outperforms a random search if applied to a specific class of fitness landscapes.
Dembskiが無視しようとしているのは、私が何度も強調した重要な点だ。「NFL定理は合理的に2つのアルゴリズムのパフォーマンスを比較するが、比較するものは考えうるすべてのフィットネス状況について平均されたパフォーマンスだ。これは興味深い理論的結論であり、フィットネス関数とサーチアルゴリズムの相互の関係を調べる道具となる。しかし、フィットネス状況の特定のクラスに適用する場合、与えられたアルゴリズムがランダムサーチを超えるパフォーマンスを出すかどうか調べたくなるような、実用的に現実で直面している関心の問題とは何の関係もない。
あらゆる問題について平均した期待値ではランダムサーチを超えられないが、特定問題については別だろうというのがMark Perakhの説明。これを認めるとDembskiの論は何の意味も持たなくなるので、無視を決め込んでいるようだ。
最終更新：2013年11月17日 22:14
