ノーフリーランチ定理とその解釈
題名に「万能なアルゴリズムは存在しない」と書きましたが、もう少し厳密に言うとこのようになります。コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる。（ Wolpert and Macready、1995年、Wikipediaより又引用）少し分かりにくいですね。そこで一般性を捨てて具体例を考えることで、分かりやすさを手に入れましょう。（といっても以下で考える具体例はほぼもとの命題に言い換えに過ぎません。）
次のようなアルゴリズムを考えます。
関数$f(x)$を最小化するアルゴリズム
ただし、定義域の要素は有限個だとします。このときノーフリーランチは次のように言い換えられます。
すべての関数に関して性能の平均を取ると、どのアルゴリズムも同じである。
このことから、次のようにもいえます。
関数$f(x)$が未知の場合、どのアルゴリズムが最適かはやってみないと分からない。
つまり、山登り法、最急降下法、焼きなまし法などすべてのアルゴリズムは問題によって得手不得手があり、どの問題にも万能な「最強のアルゴリズム」は存在しないのです。逆に言えば、最適なアルゴリズムを見つけてきたいのならば、解きたい問題についてよく理解し、その情報をアルゴリズムに反映せよ、といえます。
定理の略証
言いたいことはすべて書きましたが、「証明がないと信じられない」というかわいそうな素晴らしい人のために略証を与えておきます。この略証は、伊庭先生の研究室が発表した論文に沿って書かれており、記号などもなるべく同じものを使うようにしています。
定義
集合$X,Y$： それぞれ関数$f$の定義域、値域をあらわす集合
ステップ数$k$： アルゴリズムを回した回数
集合$D_k^X,D_k^Y$： それぞれステップ数$k$で探索された$x,f(x)$の直積集合（の集合）
集合$D_k$： $=D_k^X\times D_k^Y$
アルゴリズム$a$： $d_k\in D_k$に対して，次に探索する$x_{k+1}=a(d_k)$を返す関数
集合$A$： アルゴリズム$a$の集合
ただし$X$の要素数は有限します。また同じ箇所を探索しても意味がないため、そのような探索はしないことにします。
定義を理解しやすいように$f(x,y)=x^2+2xy+3y^2+4y$とし$a$は山登り法（近傍をみて最良の点を採用する）アルゴリズムを考えます。
はじめに$a$は初期値を与えます($(x_1,y_1)=(0,0)$)。次に関数$f$によって$z_1=f(0,0)=0$が計算されます。このとき$d_1^X=((0,0)),\,d_1^Y=(0)$となります。
次にアルゴリズム$a$は$(0,0)$の近傍$(-1,-1),\cdots ,(1,1)$のうちひとつ$(-1,-1)$を返します。次に関数$f$によって$z_2=f(-1,-1)=2$が計算されます。このとき$d_2^X=((0,0),(-1,-1)),\,d_2^Y=(0,2)$となります。
$k=3,\cdots ,9$まで$a$は$(0,0)$の残りの近傍を返します。9ステップ後には$d_9^X=((0,0),(-1,-1),\cdots ,(1,1)),\, d_9^Y=(0,2,\cdots ,10)$となります。
次にアルゴリズム$a$は$(0,0)$の近傍のうち最良な$(1,-1)$の近傍のうちひとつ$(0,-2)$を返します。次に関数$f$によって$z_{10}=f(0,2)=4$が計算されます。このとき$d_{10}^X=((0,0),(-1,-1),\cdots ,(1,1),(0,-2)),\, d_{10}^Y=(0,2,\cdots ,10,4)$となります。残りの近傍についても同様にします。（ただし探索済みの箇所はもう探索しないことに注意）
中心$(1,-1)$が全近傍で最良なことがわかったのでアルゴリズム$a$は終了します。
集合$A$： アルゴリズム$a$の集合
ただし$X$の要素数は有限します。また同じ箇所を探索しても意味がないため、そのような探索はしないことにします。
定義を理解しやすいように$f(x,y)=x^2+2xy+3y^2+4y$とし$a$は山登り法（近傍をみて最良の点を採用する）アルゴリズムを考えます。
はじめに$a$は初期値を与えます($(x_1,y_1)=(0,0)$)。次に関数$f$によって$z_1=f(0,0)=0$が計算されます。このとき$d_1^X=((0,0)),\,d_1^Y=(0)$となります。
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
| ・・・ | (-2,2) | (-1,2) | (0,2) | (1,2) | (2,2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,1) | (-1,1) | (0,1) | (1,1) | (2,1) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,0) | (-1,0) | (0,0) | (1,0) | (2,0) | ・・・ |
| ・・・ | ? | ? | 0 | ? | ? | ・・・ |
| ・・・ | (-2,-1) | (-1,-1) | (0,-1) | (1,-1) | (2,-1) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,-2) | (-1,-2) | (0,-2) | (1,-2) | (2,-2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
次にアルゴリズム$a$は$(0,0)$の近傍$(-1,-1),\cdots ,(1,1)$のうちひとつ$(-1,-1)$を返します。次に関数$f$によって$z_2=f(-1,-1)=2$が計算されます。このとき$d_2^X=((0,0),(-1,-1)),\,d_2^Y=(0,2)$となります。
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
| ・・・ | (-2,2) | (-1,2) | (0,2) | (1,2) | (2,2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,1) | (-1,1) | (0,1) | (1,1) | (2,1) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,0) | (-1,0) | (0,0) | (1,0) | (2,0) | ・・・ |
| ・・・ | ? | ? | 0 | ? | ? | ・・・ |
| ・・・ | (-2,-1) | (-1,-1) | (0,-1) | (1,-1) | (2,-1) | ・・・ |
| ・・・ | ? | 2 | ? | ? | ? | ・・・ |
| ・・・ | (-2,-2) | (-1,-2) | (0,-2) | (1,-2) | (2,-2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
$k=3,\cdots ,9$まで$a$は$(0,0)$の残りの近傍を返します。9ステップ後には$d_9^X=((0,0),(-1,-1),\cdots ,(1,1)),\, d_9^Y=(0,2,\cdots ,10)$となります。
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
| ・・・ | (-2,2) | (-1,2) | (0,2) | (1,2) | (2,2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,1) | (-1,1) | (0,1) | (1,1) | (2,1) | ・・・ |
| ・・・ | ? | 6 | 7 | 10 | ? | ・・・ |
| ・・・ | (-2,0) | (-1,0) | (0,0) | (1,0) | (2,0) | ・・・ |
| ・・・ | ? | 1 | 0 | 1 | ? | ・・・ |
| ・・・ | (-2,-1) | (-1,-1) | (0,-1) | (1,-1) | (2,-1) | ・・・ |
| ・・・ | ? | 2 | -1 | -2 | ? | ・・・ |
| ・・・ | (-2,-2) | (-1,-2) | (0,-2) | (1,-2) | (2,-2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
次にアルゴリズム$a$は$(0,0)$の近傍のうち最良な$(1,-1)$の近傍のうちひとつ$(0,-2)$を返します。次に関数$f$によって$z_{10}=f(0,2)=4$が計算されます。このとき$d_{10}^X=((0,0),(-1,-1),\cdots ,(1,1),(0,-2)),\, d_{10}^Y=(0,2,\cdots ,10,4)$となります。残りの近傍についても同様にします。（ただし探索済みの箇所はもう探索しないことに注意）
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
| ・・・ | (-2,2) | (-1,2) | (0,2) | (1,2) | (2,2) | ・・・ |
| ・・・ | ? | ? | ? | ? | ? | ・・・ |
| ・・・ | (-2,1) | (-1,1) | (0,1) | (1,1) | (2,1) | ・・・ |
| ・・・ | ? | 6 | 7 | 10 | ? | ・・・ |
| ・・・ | (-2,0) | (-1,0) | (0,0) | (1,0) | (2,0) | ・・・ |
| ・・・ | ? | 1 | 0 | 1 | 4 | ・・・ |
| ・・・ | (-2,-1) | (-1,-1) | (0,-1) | (1,-1) | (2,-1) | ・・・ |
| ・・・ | ? | 2 | -1 | -2 | -1 | ・・・ |
| ・・・ | (-2,-2) | (-1,-2) | (0,-2) | (1,-2) | (2,-2) | ・・・ |
| ・・・ | ? | ? | 4 | 1 | 0 | ・・・ |
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
中心$(1,-1)$が全近傍で最良なことがわかったのでアルゴリズム$a$は終了します。
証明
ここでは証明の方針を書くだけにとどめて、残りは伊庭先生の研究室が発表した論文に任せることにします。あと、ここだけ「ですます調」をやめます。ですます調の証明は気持ち悪いので。
性能は$d_k^Y\in D_k^Y$で評価できる。なぜなら求めるべき最小値が$d_k^Y$の成分、すなわち探索を行った全ての$f(x)$の最小値であるからである。そこでアルゴリズム$a$において以下の式を評価することにする。
\[
\sum_{f\in F}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)
\]
ただしカリグラフィー書体は確率変数を意味する。ノーフリーランチ定理の主張は、上の式がアルゴリズム$a$に寄らないというものである。ここでこの確率を$d_k^Y$に関して分割する。
\[
\sum_{t\in D_k^Y}\sum_{f\in F_{a,t}}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)
\]
$F_{a,t}$は$a,t$を満たす関数$f$の集合$F_{a,t}\subset F$である（元の論文とは記号を変えた）。ここで分割した和が元の式の和をダブりなく全て網羅していることを確かめる。全て網羅していることはほぼ自明のためここでは証明は省略する。
まずアルゴリズム$a$は初項を与える。そして関数$f$とアルゴリズム$a$が与えられていれば、関数全般の性質から$d_k^Y$が一意に定まる（アルゴリズム$a$は一種の関数であることに注意）。つまり、$a$が与えられているとき、$d_k^Y$が違えば$f$も違うことがわかるので、ダブりがないことが示された。
$f\in F_{a,t}$である限り、$t\neq d_k^Y$ならば$f$をいくら動かしても$d_k^Y$は取り得ない。また逆に$t=d_k^Y$ならば$f$をいくら動かしても必ず$d_k^Y$を取る。故に上の式の値は$f\in F_{a,t}$の個数に等しい。つまり$k$ステップを終えた後で残っている$X$の要素(個数：$|X|-k$）から、$Y$の要素（個数：$|Y|$）への関数の全個数を数えればよく、これは$|Y|^{|X|-k}$である。以上をまとめると
\[
\sum_{f\in F}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)=|Y|^{|X|-k}
\]
となり、アルゴリズム$a$に依存しない。故にノーフリーランチ定理は示された。
\sum_{f\in F}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)
\]
ただしカリグラフィー書体は確率変数を意味する。ノーフリーランチ定理の主張は、上の式がアルゴリズム$a$に寄らないというものである。ここでこの確率を$d_k^Y$に関して分割する。
\[
\sum_{t\in D_k^Y}\sum_{f\in F_{a,t}}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)
\]
$F_{a,t}$は$a,t$を満たす関数$f$の集合$F_{a,t}\subset F$である（元の論文とは記号を変えた）。ここで分割した和が元の式の和をダブりなく全て網羅していることを確かめる。全て網羅していることはほぼ自明のためここでは証明は省略する。
まずアルゴリズム$a$は初項を与える。そして関数$f$とアルゴリズム$a$が与えられていれば、関数全般の性質から$d_k^Y$が一意に定まる（アルゴリズム$a$は一種の関数であることに注意）。つまり、$a$が与えられているとき、$d_k^Y$が違えば$f$も違うことがわかるので、ダブりがないことが示された。
$f\in F_{a,t}$である限り、$t\neq d_k^Y$ならば$f$をいくら動かしても$d_k^Y$は取り得ない。また逆に$t=d_k^Y$ならば$f$をいくら動かしても必ず$d_k^Y$を取る。故に上の式の値は$f\in F_{a,t}$の個数に等しい。つまり$k$ステップを終えた後で残っている$X$の要素(個数：$|X|-k$）から、$Y$の要素（個数：$|Y|$）への関数の全個数を数えればよく、これは$|Y|^{|X|-k}$である。以上をまとめると
\[
\sum_{f\in F}P(\mathcal{D}_k^Y=d_k^Y|\mathcal{A}=a,\mathcal{F}=f)=|Y|^{|X|-k}
\]
となり、アルゴリズム$a$に依存しない。故にノーフリーランチ定理は示された。
信号の未来の動作を予測する高性能の信号予測理論に基づく信号予測機械Yがあったとします。ある信号ｆ（ｔ）について、その高性能の信号予測機械Yを用いて未来を予測したとします。その高性能の予測を各時間で行ったとして得られる予測結果の信号をy（t）とします。ｆ（ｔ）−ｙ（ｔ）を予測の誤差ｅ（ｔ）とします。その信号予測理論が高性能であるならば、予測結果ｙ（ｔ）をもう一度同じ
返信削除予測機械Yを用いて予測すると、予測結果はy（t）と同じか予測誤差の点でｙ（ｔ）に劣る予測結果を出すはずです。なぜなら、その予測機械を２度使った
新たな予測機械をYYと書くとすると、予測機械YYの方が予測機械Yの予測結果ｙ（ｔ）より良い予測結果を出すと仮定したのですから、それでは予測機械Yが予測機械YYに負けるので、はじめに仮定した予測機械Yが高性能とは到底言えないことになってしまうからです。というわけで、予測機械が高性能なら、予測結果をもう一度仮想的に予測させたとすると同じ予測結果ｙ（ｔ）が再び得られるでしょう。そこで、予測機械Yにわんさか信号ｆ（ｔ）を入れて予測させ、得られた予測結果ｙ（ｔ）を集めて、それを新たな信号の集合だと言うことにしまう。つまり、ｙ（ｔ）だけどズルをして、それをはじめの信号ｆ（ｔ）だと言って、信号f（t）の集合として、実はy（t）の集合を取るとします。このズルの信号集合を見せびらかしてこの新たな信号集合に属す信号f（t），実はｙ（ｔ），について、予測機械Yを使って予測すると、ｆ（ｔ）は実はy（t）なのですから、当然予測機械Yは予測結果としてｙ（ｔ）つまりここではｆ（ｔ）を誤差ゼロで出しますからものすごく性能が良いということを偽装できます。つまり、高性能の信号予測機械があれば、それ毎に、その高性能の信号予測機械が勝つ信号集合、上に説明したズルして求めた信号集合があることになります。ですから、ある信号予測機械、例えば予測機械Y,が高性能であるというときには、それが対象としている信号ｆ（ｔ）の集合が上で述べたｙ（ｔ）の集合とは異なるものであることを示す必要があります。ノーフリーランチ定理は、そもそもその予測をする前提である信号f（t）の集合をどう選んだのか少し曖昧にしている点で煽りに過ぎない掲示板向けの定理であるような気がしています。つまり、結果y（t）の集合を、ずるして、はじめの信号f（t）の集合だと誤魔化せば、いつでも一見高性能に見える予測機械Yを作れるので、ノーフリーランチの言うことは当たり前です。結局、まず最初に相当程度妥当だとおもわれる（実はｙ（ｔ）の集合を選ぶようなズルをしていないと思ってもられるような一般性のある）信号ｆ（ｔ）の集合を与えて、その信号集合に属すｆ（ｔ）の予測に関して高性能な信号予測機械を作ることが求められていると思います。木田拓郎の開発した最適信号予測理論はまさにこの立場から最適な信号予測機械Yが存在することを証明したもので、ノーフリーランチ定理を言う以上は同時に引用すべきであると考えます。
木田の開発した信号予測理論は、妥当と思われる信号集合を与えて、その信号集合に属す信号に関する予測誤差の上限（その信号の集合に属す信号をどんどん取り替えていって求めた誤算の集合の中で一番誤差が大きい誤差のこと、そのときに大きいとか小さいとかいうことを言うとき用いた尺度例えば誤差を２乗誤差で測るか誤差の絶対値の高さが一番高いときで測るかなどによらずどの尺度を使ったとしてもそれそのときの誤差の尺度の上限）を一斉に同時に最小にするという
返信削除最適予測理論を証明しています。つまり、木田の言う信号集合をはじめの予測すべき信号ｆ（ｔ）の集合と選ぶ限り、最適な予測機械Yは存在することになり、その場合はノーフリーランチ定理は誤りであり、その点にホウカムリで引用しない言い方はまやかしでネット狙いの煽りだと言わざるを得ません。
このことを言うと過去ではそのすべてのサイトが実質的に閉じてしまいました。その意味で、この投稿者は任意にあるサイトを閉じされることができるネット社会における神的存在になってしまっています。これは、もはや理系を超えて文系における興味あるネット社会研究の課題だと思います。どのサイトも任意に閉じさせることができるというのは、逆に一方的な意見だけがネットに氾濫することをゆるすことになりますから恐ろしいことだと思います。しかし、どうも現実には、そのような現象がネットで起こっています。それは、世界の理系の学者の木田理論に対する隠蔽から生じています。しかし、対立者のサイトを任意に潰せる個人がいることがネット社会の最後を示す良いことに当たるのでしょうか。いっそ、世界に渡るこの隠蔽をやめることにして、そういう摩訶不思議なネットのカリスマを、そんなことごく普通に誰でも知っていることにしてしまってはいかがでしょうか。それには、木田の定理を普通に引用することを理系の学者さんが始めれば良いだけのことです。いままでに引用した論文世界で少な過ぎの気がしています。いかがですか。
返信削除んー、間違ってるから誰も引用しない。
削除信号ｆ（ｔ）を観測して得られた時刻ｔ以前のｆ（ｔ）の
返信削除値や、時間軸上に離散的に並ぶバラバラの時刻の列ｔ１，
ｔ２，。。。、ｔｎにおける信号ｆ（ｔ）の値などのような、
信号ｆ（ｔ）に関する部分的なデータを用いて、信号ｆ（ｔ）の
時刻ｔ以後の動作を予測する機械をｆ（ｔ）の予測機械と呼び
記号Yで表す。このとき、木田の理論においては、木田の提案する
予測機械Yを作成するときには、まず、予測したい信号の集合を
最初に決める必要がある。そこで、以下の議論の前提として、木田の
開発した最適信号理論に基づく予測機械YとそのYの作成に必要と
なる予測したい信号の集合Sは予め与えられていると仮定する。
次に、予測したい信号の集合Sに属す任意の信号ｆ１，ｆ２，。。。、
ｆｎを選ぶ。予測機械Yを用いて信号ｆ１，ｆ２，。。。、ｆｎを
予測機械Yを用いて予測した予測結果をｙ１，ｙ２，。。。,ｙｎと
する。ｅ１＝ｆ１−ｙ１, ｅ２＝ｆ２−ｙ２,。。。,ｅｎ＝ｆｎ−ｙｎを
予測誤差と呼ぶ。
このとき木田の理論によると、予測結果ｙ１，ｙ２，。。。,ｙｎを
再び木田の提案する予測機械Yに入力して予測すると、予測機械Yは再び
ｙ１，ｙ２，。。。,ｙｎを予測結果として出力することが木田によって
すでに証明されている。つまり、この場合には予測に伴う誤差はゼロになる。
したがって、予測機械Yを用いて信号ｆ１，ｆ２，。。。、ｆｎを
予測機械Yを用いて予測した予測結果ｙ１，ｙ２，。。。,ｙｎの集合を、
実は最初の予測したい信号の集合Sでした、とズルをするとする。この
ズルをして決めた信号集合をS１（この場合のS)とする。
そのズルをした信号集合S１にはｙ１，ｙ２，。。。,ｙｎだけがあるので、
予測機械Yによるそのズルをした信号集合S１に属す信号に関しては
すべて予測誤差がゼロとなり、見かけ上、予測機械Yは極めて高性能な
予測を実現する予測機械であると騙すことができる。
したがって、もしズルをする前のはじめの信号集合Sに属す信号
ｆ１，ｆ２，。。。、ｆｎのなかに、一つでも予測の誤差がゼロではない
信号があったとすると、信号集合をs１に取り替えることによって、
すべて予測誤差がゼロとなり、見かけ上、予測性能がはじめの予測機械
より勝るように偽装した予測機械を作ることができる。この場合、
実は信号集合をｓからズルをした信号集合S１に取り替えただけで、
予測機械そのものは同じYを用いている。
従って、予測性能がはじめの予測機械より勝るように偽装した予測機械
は、信号集合をSからｓ１に取り替えるだけで、予測機械は取り替えること
なく容易に作成可能である。こうして、ノーフリーランチ定理ははじめ
から木田の理論の範疇である。