大学の講義「人工知能」の課題でノーフリーランチ定理についての課題が出たので、ついでにブログにも載せておきます。
ノーフリーランチ定理とその解釈
題名に「万能なアルゴリズムは存在しない」と書きましたが、もう少し厳密に言うとこのようになります。
コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる。（ 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)$となります。
| ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ | ・・・ |
| ・・・ | (-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$に依存しない。故にノーフリーランチ定理は示された。
