インテリジェントデザイン理論家Dr. William Dembskiは、遺伝的アルゴリズムについてのNFL定理を使って、進化シミュレーションがこっそり情報を持ち込んでいて、進化できるかのような結論を出しているのだと数学的に証明しようとしている。が、いまのところNFL定理を間違って使っていて、正しい証明をしたことはない。そして、Dr. William Dembskiは、2007年に、再度チャレンジをした。これを、数学者E. Tellgrenが斬っている。
William Dembski has been one of the most influential contributors to the Intelligent Design (ID) movement. Among other things, his work has added the terms specified information, specified complexity, and complex specified information to the basic vocabulary of the ID movement. These terms are all directly related to the logarithms of special types of probabilities, e.g. the probability of a pattern of interest given that it was produced in some way that excludes the foresight and guidance of an intelligent agent.
William Dembskiはインテリジェントデザイン運動の最有力の貢献者のひとりである。とりわけ彼の成果は、指定された情報や指定された複雑さや複雑で指定された情報はインテイジェントデザイン運動の基礎用語を加えたことである。これらの用語はすべて、関心対象のパターンの、インテリジェントエージェントによる予見および指導を除外した形で生成確率のような、確率の特殊形式の対数表現である。
In a recent draft manuscript, Dembski and his coauthor Marks extend the vocabulary with three new terms [1]: endogenous information, exogenous information, and active information. They consider as given a search space and a fixed subset, called a target, that makes up some fraction ps of the search space. An issue of interest to them is how to measure how well a search algorithm [2] exploits the structure of the search problem. Two possible candidates are the probability p that a search algorithm is successful and the ratio p/ps. Readers of Dembski's previous writings will not be surprised to discover that Marks and Dembski prefer to log-transform their probabilities and rename them 'information'. In equations, their definitions are
最近の草稿で、Dembskiと共著者Marksは新たに3つの用語を加えた[1]。すなわち、endogenous infromation(内在情報)とexogenous infromation(外生情報)とActive Infromation(能動情報)である。所与の探索空間と、探索空間のpsを構成するターゲットと呼ぶ固定された部分集合として考えられている。彼らにとっての関心事は、探索アルゴリズムが探索問題の構造をどれだけうまく活用しているかを計測する方法である。その考えられる候補は2つで、探索アルゴリズムが成功する確率pと、その比p/psである。Dembskiの前の文献を読んだことがないと、Marks and Dembskiが確率を対数形式に書いて、これを情報と呼ぶことに驚くかもしれない。方程式上の定義は以下のとおり：
endogenous information = -log(ps),
exogenous information = -log2(p),
active information = -log2(ps/p).
(More generally, it is indicated that ps can be replaced by the probability that some reference algorithm finds the target. Since the draft manuscript focuses on the case when ps is the fraction of points in the target, I will do the same.) It sounds a little less strange to say that active information has to come from a programmer than it does to say the same of a probability value larger than ps. We are more prone to reify something called 'information' and expect it to come from somewhere in particular than to doing the same for a probability or a probability ratio. For a given search problem, the three types of information typically have a rather mundane origin. They typically arise from the formulation of the search problem. If the formulation of the search problem is informative enough to enable us to estimate the size of the target, then it usually also implies something about which regions of the search space that are likely to be in the target and which search algorithms are most efficient. Of course, Marks and Dembski are not only concerned with the mere mathematical existence of successful search algorithms, they also want to imply something about how such search algorithms are implemented or realized. Naturally, for those search algorithms that are implemented in man-made computers, human programmers tend to play a central role. Even in this case, however, a large ratio p/ps cannot be entirely attributed to the intrinsic creativity and cleverness of a human programmer. In practice, programmers learn from each other and from experience, and many algorithms are directly inspired by observations of nature. Examples include simulated annealing, genetic algorithms, swarm optimization, etc. To the extent that search problems, targets and large ratios p/ps also arise in nature (e.g. minimization of free energy in thermodynamic systems or maximization of reproductive success in evolving biological populations), a different answer seems to be required. For one thing it is implausible to think that a human programmer had the means and opportunity to be involved. Additionally, any process that is capable of reaching a long-lived equilibrium or stationary state can be viewed as optimizing something (e.g. minimizing a function that describes the rate of change squared or the distance to the equilbrium state).
（より一般的には、psは何らかの参照アルゴリズムがターゲットを探索する確率と置き換えることできることが示せる。草稿が、psがターゲットの中の点であるケースに注目しているので、私も同様にするだろう。）能動情報がプログラマに起因するものだと言う方が、psよりも大きい値の確率と同じというよりも奇異ではないかもしれない。情報と呼ばれるものを具体化し、特定の場所から来ると期待する方が、確率や確率比に対して同様なことをするより考えやすいだろう。所与の探索問題では、3つのタイプの情報の起源は、一般的にありふれている。それらの情報は典型的には、探索問題の構造を起源とする。もし、探索問題の構造が、ターゲットの大きさを推定できるに足る情報を持っていれば、それは、探索空間のどの領域がターゲットにあるかとか、どの探索アルゴリズムが最も効率が高いかについて何らかの示唆を与える。もちろん、Marks and Dembskiは、成功する探索アルゴリズムの数学的存在のみ関わっているわけではなく、そのような探索アルゴリズムがどのように実装あるいは実現されるかについて、何らかの示唆を得たがっている。人間が作ったコンピュータに実装された探索アルゴリズムに対しては、人間のプログラマが中心的役割を担うことが多い。そのような例でも、しかしながら、p/psの大きな比は内在的創造性や人間のプログラマの賢さだけで実現されるものだとは言えない。実際には、プログラマたちは互いに学びあい、経験から学び、多くのアルゴリズムは自然界の観察に直にインスパイヤされている。その例には、シミュレーテッドアニーリングや遺伝的アルゴリズムは群最適化などがある。自然界に起こる探索問題やターゲットや大きなp/psの大きな比を拡張するには（熱力学系における自由エネルギーの最小化や進化する生物集団における生殖成功の最大化など）、違った答えが必要と思われる。人間のプログラマに手段と機会が含まれていたと考えるのは、信じがたい。さらに、長期平衡状態や静的状態に到達することが可能な過程は、最適化されたものと見ることができる（変化率の二乗あるいは平衡状態までの距離を記述する関数を最小化するなど）。
Because of the use of information terminology and the appeal to the Maximum Entropy (MaxEnt) principle, it is interesting to compare Marks and Dembski's work to older work within the MaxEnt tradition. It has been shown that the MaxEnt principle can be used as a framework to derive the optimal way to distribute search efforts over different cells of a search space [3]. Although the motivation and assumptions behind that work are different, it is similar in that it led to definitions of quantities measuring the amount of prior knowledge about the target and the amount of knowledge utilized during the search. These measures are, in different ways, both more general and more restricted than Marks and Dembski's measures. They are much more general because there is no restriction to uniform probability and complete lack of knowledge about the target location. They are more restricted in that they presuppose that the target consists of a single point. In the special case of uniform probability and a single-point target, they differ only by trivial additive constants from the endogenous and exogenous information. However, the older measures are directly related to optimal distribution of search efforts and therefore have a clearer meaning and significance. In comparison, it is less clear which questions Marks and Dembski's three quantities can answer.
情報用語の使用および最大エントロピー原則へのアピールにより、Marks and Dembskiの成果を、最大エントロピー原則の過去の文献と比較するの面白い。最大エントロピー原則は、最適に探索空間の異なるセルへの探索の分配を導出するフレームワークとして使える[3]。Marks and Dembskiの成果の背後にある動機と仮定は違っているが、その仕事の背後の動機と見せかけが異なるが、それがターゲットについて事前知識量および探索中に利用される知識量を測定する指標の定義を導出するという点で類似している。これらの測定指標は違った意味で、Marks and Dembskiの指標よりも、一般的であり、かつ制限的である。それらは、一様確率について制限がなく、ターゲットの位置についての知識がまったくないので、はるかに一般的である。ターゲットが1点であることを前提にするという点で、より制限的である。一様確率およびターゲットが1点であるという特殊例では、内在情報と外生情報のトリビアルな付加定数だけの違いになる。しかし、従来の指標は探索の最適分配に直に関連しており、従って、より明確な意味と重要性を持つ。これに対して、Marks and Dembskiの3つの量が答えることのできるものは不明確である。
On another note, Marks and Dembski are mistaken when they refer to Wolpert and Macready's original No-Free-Lunch (NFL) theorem as if it were directly applicable also to the situation they are analyzing. In the current version of their draft, Marks and Dembski stipulate that (a) the target makes up some fixed fraction ps of the search space and (b) no other assumptions about the search problem are to be made. The NFL scenario analyzed by Wolpert and Macready [4] differs in that stipulation (a) is not made. When one makes use of the Principle of Insufficient Reason or the MaxEnt principle to determine a Bayesian prior, it is important to be clear about what, precisely, it is that is totally unknown. In the NFL scenario it is a cost/objective/fitness function f defined on the search space that is taken to be totally unknown. Performance is evaluated as an average over all mathematically possible functions. If one wishes to define a target it must be defined in terms of the totally unknown function f, e.g. as the region {x | f(x) > c} of the search space with function values larger than some threshold c for what is satisficingly good. For some functions such a target is very small, for other functions it is very large (an example is the function which assigns the maximum value to every search space point). Because all functions contribute, the NFL-averaged performance will include contributions targets of varying sizes, in contrast to the scenario analyzed by Marks and Dembski. Arriving at the target in the NFL scenario is not prohibitively hard, not even for random i.i.d. sampling [5].
もうひとつ注意する点は、Marks and Dembskiが、Wolpert and MacreadyのオリジナルのNo-Free-Lunch (NFL)定理を、彼らが分析している状況に直に適用可能だとしていることが、間違いだということである。現時点の草稿で、Marks and Dembskiは (a)ターゲットが探索空間の固定された部分psを構成していて、(b) 探索問題について他に作りうる仮定がないと規定している。Wolpert and Macready [4]が分析したNFLシナリオは規定(a)がないという点で違っている。理由不十分原理や最大エントロピー原則を使って、ベイジアンを予め定めようとするなら、何をまったく未知を正確に明確化することが重要である。NFLシナリオでは、コスト/目的/フィットネス関数fが、まったく未知の探索空間の上で定義される。数学的にありうるすべての関数の平均としてパフォーマンスが評価される。ターゲットを定義したいなら、完全に未知の関数f（たとえば、探索空間の領域{x | f(x) > c}と、関数値がそれ以上なら良いとする閾値cを定義しなければならない。ある関数はターゲットが非常に小さく、他の関数は非常に大きい（たとえば、探索空間のすべての点で最大値をとる関数）。Marks and Dembskiが分析したシナリオと違って、あらゆる関数が寄与するので、パフォーマンスのNFL平均は、大きさが変化するターゲットの寄与分も含まれる。NFLシナリオのターゲットに到達するのは、非常に困難というわけでもないし、それはランダムi.i.d.サンプリングにとっても同様である[5]。
In some ways the mistake is not very serious. They don't really need the original NFL results for their own conclusions. Moreover, a generalization of the NFL theorem to the situation when the function is known to belong to a special class of functions (which is closed under permutation of the search space) is applicable to their own scenario [6]. If the function to be sampled is known to assign satisficing values to a fraction ps of the search space, but is otherwise totally unknown, then both stipulations (a) and (b) are respected and the generalized NFL theorem is applicable.
いくつかの点で、間違いはあまり深刻ではない。Marks and Dembskiの結論のためには、オリジナルのNFLの結果は本当は必要ではない。さらに、関数が特別なクラスの関数（探索空間の順列のもとに閉じている）に属していることがわかっているときに対して、NLF定理の一般化は、彼らのシナリオに適用可能である[6]。サンプルされる関数が探索空間の部分sを満たす値を持つことが既知ではなく、まったく未知であれば、規定(a)と(b)は考慮され、一般化NFL定理は適用可能となる。
What makes the difference between the NFL scenario and Marks and Dembski's stipulations significant is the far-reaching conclusions inspired by the latter. They write [1]:
NFLシナリオとMarks and Dembskiの規定の違いによって生じる重大な違いは、後者によってインスパイアされる広範囲の結論である。彼らは次のように書いている[1]：
"To have integrity, all search algorithms, especially computer simulations of evolutionary search, should make explicit (1) a numerical measure of the difficulty of the problem to be solved, i.e., the endogenous information, and (2) a numerical measure of the amount of problem-specific information resident in the search algorithm, i.e., the active information."
完全性を実現するために、特に進化探索のコンピュータシミュレーションは、(1) 解くべき問題の難しさの数値的指標、たとえば内在情報と、(2) 探索アルゴリズムにある問題依存の情報量の指標、たとえば能動情報の数値指標をあらわに算出すべきである。
While there is nothing unreasonable about the general idea of quantifying problem difficulty and problem-specific information, the particular assumptions Marks and Dembski rely on are neither realistic enough nor general enough to become some sort of integrity requirement. The assumptions (a) and (b) correspond to the NFL scenario with an extra restriction of the function to be sampled. Why is the NFL scenario with this extra knowledge a privileged set of assumptions? Why give knowledge of the target size special treatment compared to, say, knowledge about the smoothness of the function? In reply to criticism of Dembski's older work on the basis that real-world fitness functions exhibit clustering of similar values, Marks and Dembski claim that taking such knowledge into account is to commit the crime of smuggling in unwarranted assumptions [7]. Given that, it seems that they are equally guilty in smuggling in an unwarranted assumption about the target size. Without the target size assumption (a) smuggled in, the NFL scenario is so benign that any search algorithm, random i.i.d. sampling included, is reasonably effective [5]. A characteristic of hard search problems is that the difficulty grows fast with the size of the search space. In contrast, the NFL-averaged performance is (almost completely) independent of the size of the search space. If this is counter-intuitive, it is only because the original NFL theorem is a formal version of the problem of induction, whereas the real-world search problems we build our experience and intution on seem to come from domains that enable inductive learning and generalizations.
問題の難しさと問題依存情報を定量化するという一般的な考え方には何ら不合理なことはない。しかし、Marks and Dembskiが頼る特定の仮定は、完全性条件となるには、現実性と一般性ともに不足である。NFLシナリオに対応する仮定(a)と(b)はサンプルされる関数の余分な制限を持たせている。この余分な知識を加えたNFLシナリオが、仮定の特権的なセットなのか？何故、ターゲットサイズの情報を与えることが、関数のなめらかさについて情報に比べて、特別な扱いとなるのか？現実世界のフィットネス関数は似たような値のクラスタリングなることに基礎をおく、Dembskiの過去の文献への批判にこたえて、Marks and Dembskiは、そのような情報を入れることは、保証されない仮定をこっそり持ち込む犯罪を犯すことだと主張している[7]。そうだとするなら、彼らもまた、ターゲットサイズについての保証されない仮定をこっそり持ち込むという同じ罪を犯している。ターゲットサイズについての仮定(a)を持ち込まないなら、NFLシナリオは、どのような探索アルゴリズム（ランダムi.i.dサンプリングを含む）も、かなり効果的だという穏健なものになる[5]。難しい探索問題の特徴は、探索空間のサイズとともに難しくなることである。これに対して、NFL平均パフォーマンスは（ほぼ完全に）探索空間のサイズに依存しない。これが直観に反しているのは、NFL定理が帰納問題の公式バージョンであるのに対して、我々が経験と直観を構築する現実世界の探索問題が、帰納的学習と一般化を可能とするドメインから産物であるからだ。
Acknowledgement:
Thanks to Pete Dunkelberg for commenting on earlier versions.
References and notes:
[1]
R. Marks and W. Dembski. Conservation of Information in Search: Measuring the Cost of Success,
[2] Note that, following Wolpert and Macready and others, a search algorithm in this context is just a sampling distribution of the type P(next sampling point | data about previously sampled points). This differs a bit from the more common notion of an algorithm as a list of instructions, input to a Turing machine, or an implementation in a programming language.
[3]
E. T. Jaynes. Entropy and Search-Theory, 1985.
(Note that Jaynes frequently referred to MaxEnt Bayesianism as 'information theory' and to work within this tradition as 'information-theoretic'. This is different from both Shannon's information theory and algorithmic information theory.)
[4] D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82, 1997.
[5]
T. M. English. Optimization is easy and learning is hard in the typical function. In Proceedings of the 2000 Congress on Evolutionary Computation CEC00, p. 924-931, July 2000. IEEE Press.
