ホーム › 未分類 › 焼きなまし法の真実

焼きなまし法の真実

Posted on by colun カテゴリー: 未分類 — コメントはありません ↓

はじめに

著者は、TopCoder Marathon Matchesで世界大会決勝へとアメリカに3度招待された。
その3度ともが、予選では強文脈ゲームによる通過であり、焼きなまし法の使えない問題分類だった。
近年、文脈のない探索の出題が増えてきており、焼きなまし法が正解方針であることが多くなっている。
焼きなまし法へと苦手意識を持った著者であったが、出題の傾向がそうであるのなら避けて通れるものでもなく、焼きなまし法の出題であっても単純な殴り合いで1位をもぎ取れるまでになりたいと2年前に決意して、七転八倒を繰り返しながら現在に至る。

その間、ainu7さんやKomakiさんの力に依る所が大きいが、Kaggleという機械学習系の問題を多く取り扱っている定期コンテストサイトにおいて、毎年クリスマスを挟んで開催されているSantaコンテストで、焼きなまし法の出題に対してチーム戦で1位を取った。このコンテストで1位を取ったことはかなり凄いことで、TopCoderOpenのMarathonMatches部門で優勝するのに匹敵するぐらいすごいことだと個人的には思っている。（実際、総参加人数はTopCoderOpenより多い）
著者はすごくなくて、チームを一緒に組んだainu7さんやKomakiさんが、ただただひたすらに凄いのである。彼らから直接的に焼きなまし法について教わることは少なかったが、一緒にチームで戦う中で間接的には多大過ぎるヒントを頂いており、直接的に教わる以上の影響を受けており、それがなければ正直ここまで辿りつけなかったと思う。

その後も七転八倒しながら焼きなまし法をコンテストなどで使いながら、理論を一から学び直していく中で、いくらかの知見を整理できたと思う。

現在、まだ単純な殴り合いで1位をもぎ取れるところまでは至っていないが、現在までに数々のノウハウを得、2年前では考えられなかったほどに焼きなまし法へのイメージが変わった。
この情報を共有し、焼きなまし法で迷ってる方々の意識の是正につながればこれ幸いである。

この記事は、読者がすでに焼きなまし法をある程度知っているということを前提とする。

焼きなまし法はベター山登りなのか？

良い方向へのみ遷移を繰り返していると、局所解に陥る。これは分かりやすい。
時々悪い方向へも遷移を行っていれば、局所解を抜けだして別の局所解に辿り着くかもしれない。その別の局所解は、元の局所解より良いかもしれない。これも分かりやすい。
そうしたことから、焼きなましは山登り法よりはいくらかマシな様に思っていた。

これは、著者が焼きなまし法を初めて使った時から実に15年近く勘違いしていた、間違った焼きなまし法の理解である。
この理解は、単なるベター山登り法でしかない。
いくつかの局所解を避けて、たまたま辿り着くいくぶんましな局所解で満足する方法である。

本当の焼きなまし法は、もっと大局的に厳密解の一歩手前まで肉迫することができる。
2年前に想像していたよりずっとずっと高温からスタートし、そして局所解になってすらいない様な中途半端なところを行ったり来たりしながら、温度が下がっていくことで移動可能な範囲が狭まっていくが、その間、より大局解に近い領域を高確率で選び続ける。
この後の話で、その感覚を、少しでも多く共有できれば、これ幸いである。

探索空間は本当に高次元なのか？

1次元なら全探索も試せるだろう。2次元でも全探索が試せるかもしれない。
5次元ならどうだろうか？　100次元だったらどうだろうか？　100万次元だったらどうだろうか？
焼きなましの適用範囲は、出題に依って違うが、100〜1億次元以上を想定する場合が多そうだ。
そもそも、次元数がいくつなのかを明確化しづらい、組み合わせ問題の様なものもある。
しかしあれも、広義では次元がある中での探索をしている様なものとみなせる。

さて、仮に100万次元の探索問題があるとする。
これは本当に1つの100万次元問題なのか？　それとも、5次元の探索問題が20万個並んでいるだけなのか？
実際のところ、どちらでもなく、互いに少しずつ重複し合った5次元の探索問題が100万個並んでいる様なイメージが正しい場合が多い様に思う。
5次元が100万個だったら、全部で500万次元じゃないか？　計算が合わないだろう？　だから、それらが制約になっていて、探索の難易度が上がるのである。しかし真に1つの100万次元の問題よりは、ずっと簡単なはずなのである。効率的に解く方法が存在し、焼きなまし法ではそれが可能だからこそ、強い。

5次元であれば、たとえばこの軸が真偽値（Boolean … つまり、True or False）であるならば、32種類しか存在せず、全探索が容易である。32種類を100万個について個別に求めるだけならば、3200万個の評価をすれば良いだけなので、これも計算できてしまう。ただし実際には重複分が制約になっていて、その方法では解は求まらない。そもそも100万ある次元の、それぞれどの5次元ずつが関連付いているのかを整理して解くというプロセスが、別の問題として発生し、こちらを解くことがそもそもからして難しい。

こうした場合に、焼きなまし法を使うと楽に解ける。個別の5次元ぐらいの軸の関連性とかも、考える必要がなく、内部的によろしくやってくれる。

たとえば完全に独立なAとBの探索を、一度に行う場合を考えよう。

Sc((A, B)) = ScA(A) + ScB(B)

これを最適化せよ、という問題だ。AとBが完全に分離できているのなら、AとBと個別に問題を解く方が通常は遥かに簡単である。
これは、全探索の場合は、一緒に解くと

O(Cost(Optimize(Sc((A, B))))) = O(Cost(Optimize(ScA(A))) * Cost(Optimize(ScB(B))))

とかになるからである。（表記法がこれで正しいかどうか不明）
個別に解いて良いのならば

O(Cost(Optimize(ScA(A))) + Cost(Optimize(ScB(B))))

のコストで済んでしまう。なんとしても一緒には解きたくないのである。

焼きなまし法の場合のコストは、ごちゃ混ぜで解いても後者になる。ここが、焼きなまし法が非常に強い理由である。

理由を示そう。実はすでに示した下記の式が理由になっている。

Sc((A, B)) = ScA(A) + ScB(B)

ただ、これだけでは分からないと思うので、遷移を考えよう。

(A, B)→(A’, B)→(A’, B’)→(A’, B”)→(A’, B”’)→(A”, B”’)→(A”’, B”’)

という具合に遷移したとしよう。（※AとBの両方をまたぐ様な遷移が存在しないと仮定する）

AとBは完全に独立で互いに影響を及ぼさないので

A→A’→A”→A”’

B→B’→B”→B”’

というのがそれぞれ別々に変化したに等しい。
これらが本当に独立に変化しているのならば、Optimize(ScA(A))とOptimize(ScB(B))とをそれぞれ同時進行で別々に解いているに等しく、Optimize(Sc((A, B)))を正面切って解くことを回避できていると言える。

Sc((A, B)) = ScA(A) + ScB(B)

何度も出してきたが、上記式が成立しているので、当然下記も成り立つ。

ΔSc((A’, B’)←(A, B)) = ΔScA(A’←A) + ΔScB(B’←B)

ΔScX(X←X)は常に0なので、温度変化の試行回数ぐらいしか互いに影響を及ぼしておらず、それは無視できるので、問題が混ざったままで解いても、別々に解いてる効率が得られる。

このことが成り立つためには、採択確率として何気なく使っている以下の式がとても重要である。

min(1.0, exp(ΔSc / T))

この式あればこそ、単純なスコア差でのみ採択確率が変化する。AとBが一緒に変化することさえなければ、問題は混ざったままであっても、分割して解いてるに等しくなる。

AとBの両方をまたぐような遷移が存在しないことを仮定していたが、これは1次元ずつの最小単位の変化を繰り返すなどで実現が可能である。複数次元の同時変化は、上記前提を崩してしまうので注意が必要となる。

採択確率式の正当性

exp(ΔSc / T)

我々は上記の確率式を当たり前の様に使う。
それはあたかも宗教の様に、「これが良いと言われたからこれが良いのだ」的に信じるものは救われる。

実は焼きなましがうまくいくために採択確率式が満たすべき条件が2つあって、この2つの両方を満たす採択確率式は非常に限られる。
片方が、すでに前章で論じた問題であり、それは「スコア差のみが採択確率を決める」ことである。

もう片方の条件は、メトロポリス・ヘイスティングス法に起因する理由で、採択確率に関して、以下の式を満たす必要がある。

min(1.0, p_to / p_from)

なお、焼きなまし法においては、

p = K*exp(Sc/T)

である。（Scは便宜上、big is betterということで、ヨロシク）
したがって採択確率は実際には下記だったのだ。

min(1.0, (Kexp(Sc_to/T)) / (Kexp(Sc_from/T)))

場合によっては途中でオーバーフローしそうなので、これを実際に計算させるのはやめたほうが良いが、定数Kが互いに消えて、exp内を統合すれば

min(1.0, exp(ΔSc / T))

と等価であることはすぐに分かると思う。（この段階になれば、オーバーフローしても問題なく振る舞う）

メトロポリス・ヘイスティングス法がうまくいく条件

2つの地点A, Bが存在するとき、以下の条件を満たすと、メトロポリス・ヘイスティングス法はうまく動く（無限回遷移させた時に、地点Xにいる確率はp_Xにほぼ等しくなる）とされている。

p_A * (q_BA * a_BA) = p_B * (q_AB * a_AB)

ここで、q_BAはA地点からB地点への遷移が提案される確率であり、a_BAはA地点からB地点への提案された遷移が採択される確率である。すなわち、(q_BA * a_BA)は、A地点からB地点へと遷移する確率と言い換えることができる。

本当は順番が逆で、遷移確率が先に存在し、それが提案確率とずれるために、採択確率を用いてバランスを取るという論法になっている。

さてここで、採択確率式は

a_BA = min(1, p_B / p_A)
a_AB = min(1, p_A / p_B)

とするのが、一般的なメトロポリス・ヘイスティングス法である。

この時、すなわち、

q_BA = q_AB

となる前提が存在する。

この提案確率の前提が崩れない様な、近傍提案を書く必要がある。
もし空間の端などで近傍提案を書くときは、空間の外側も近傍提案は行ってあげたうえで、必ず棄却する様にするなどしてあげた方が、この提案確率の前提を崩さずに済むことになる。（それと等価の処理を別の方法で書けるのなら、それでも良い）

なお、採択確率式は、以下であっても条件を満たす。
（真偽値軸でのギブスサンプリングが、正にこの式になる）

a_BA = p_B / (p_A + p_B)
a_AB = p_A / (p_A + p_B)

基本的にはどんどん遷移していった方が良い、という思想から、通常のメトロポリス・ヘイスティングス法の方の採択確率が好まれる。

ギブスサンプリング版採択確率式が焼きなまし法としても問題ないかどうかは、著者はまだ未検証だが、もし問題ない場合は、列挙コストが少なく遷移コスト（新しい状態への更新コスト）が高い場合に有効かもしれないなと、個人的には思っている。
ただ、ギブスサンプリング版採択確率式が使われているのを見たことがないため、一般的にメトロポリス・ヘイスティングス法版が好まれていることは間違いなさそうだ。

もし、どうしても提案確率側をいじる場合には、採択確率の方を調整することでも、遷移確率全体のバランス調整が可能になるということを、頭の片隅に入れておいた方が良いかもしれない。（あまりに上級過ぎて、著者も通常は検討すらしなさそうです…）

メトロポリス・ヘイスティングス法と温度

min(1.0, p_to / p_from)

上記式の必然性については、前章で説明した。

上記式を用いることによって、無限回遷移させた場合に、すべての地点において、存在している確率がpにほぼ等しくなる。
が、実際には無限回遷移はできず、そのため移動経路が確率がほぼ0の面で遮られていたら、そこから抜け出すことができない。
この確率がほぼ0の面のことを、この記事では仮に「壁」と表現することにする。
壁は、領域を2つ以上に分断する。

壁が一切存在しない様な温度が存在すると過程する。温度が無限大であれば、採択確率は常に1になるので、壁は存在しない。実際には、無限大よりはずっとずっと低い温度でも壁が存在しない温度は存在するはずである。
そこから温度が十分にゆっくりと下がっていく時、どこかのある地点で壁が発生し、壁は領域を2つ以上に分断する。
しかし、この時に、片方の領域から見た場合に壁になっていても、もう片方の領域から見ると壁になりかけではあるが不完全であるという状況が生じうる。その差は、現在とどまっている領域周辺のpに依る。
つまり、確率がより高い場所（＝よりスコアが良い場所）にいた方が、壁は温度変化に対して早く具現化する。
確率がより高い場所からだと壁にはばまれているが、確率がより低い場所からだと壁にはばまれておらず、確率がより高い場所へと抜ける可能性が残されている。
また、そもそもからして、そういう温度に到達したタイミングにおいて、確率がより高い位置にいる可能性のほうが高い。
これが無限回の議論になると、結果は「必ず」になる。

さて、この壁であるが、温度に依って発生する。壁がどこにどのように存在しているのかは分からないが、温度に依って発生する壁は、その温度順に並べて考えることができる。実際ソートできるわけではないが、結果的に温度順に処理していけることを仮定することができる。

つまり、以下の様な話を想定できる。
最初はすべての領域に自由に移動することができる。
どこかのタイミングで最初の壁Aが出現する。分断される領域のうちで、最も確率の高い領域を選べる。
次に更にどこかのタイミングで壁Bが出現する。これも分断される領域のうちで、最も確率の高い領域を選べる。
更に壁Cが、壁Dが、壁Eが、、、以下、温度が0になるまで無限に繰り返す。

これらの、温度によって発生する壁による領域の選択を繰り返していくのが焼きなまし法である。
なんとなくだけれども筆者は、焼きなまし法を、ランダムウォークによる二分探索の様にイメージしている。
もちろん、遷移回数は無限回ではないために、壁Cを処理している最中に壁Dも出現するかもしれず、また無限回ではないために最良ではない領域を選択してしまう可能性もある。しかし、全体としてはある程度うまくいくことが期待できる。

これは自戒ですが、数学的な根拠が少しでもずれると、そのずれ具合によって、この前提は段々と崩れていきます。
試行回数が十分大きくない場合は、少しぐらい数学的根拠がずれていても、だいたい上手くいくので、気が付きません。
しかしながら、試行回数が十分過ぎるほど大きくなったそのときに、これらの数学的根拠が満たされているかどうかが、極めて大きく効いてくることになります。
逆に言えば、遷移回数が極端に少ない場合は、この前提を崩してでも、他を取りに行った方が良い場合もあり得ます。
しかしこれが落とし穴で、コンテストにおいて序盤は遷移回数が極端に少なくても、何らかの事情で急激に遷移回数が稼げる様になる場合もあります。そうした際に、数学的根拠を見なおした方が良い場合も、あるかもしれません。

おまけ1 … 遷移先候補をどう提案するか？

おまけ章は、元々の記事には存在していませんでした。査読をお願いした際に、一般読者が特に知りたいと思っていることだと助言を頂きましたので、可能な範囲で付け足しを行いました。
そのため、検証が圧倒的に不足しており、部分的には理論を根拠としつつも、著者が今後のコンテストで検証していく予定の部分ということでご理解をお願いしたいと思います。

焼きなまし法では、次に遷移する先の候補を作成する。
この遷移先候補は近傍とも呼べる場合が多い。
この遷移先候補を1つ作ることを、メトロポリス・ヘイスティングス法では提案と言い、ここまでで述べた様に提案確率の条件を気にする必要がある。

ところで、原型となるメトロポリス・ヘイスティングス法では複数次元を同時に変化させる。これは、探索空間の広がる方向が複数の次元にまたがる方向へと広がっていた場合に、1次元ずつの遷移が不利なためであると考えられる。これは、実際に1次元ずつの遷移を行うギブスサンプリングの弱点でもある。

遷移先候補が元の位置から遠くなれば遠くなるほど、棄却確率は高くなる。
ここで、遷移半径は1σぐらいが適していると、「パターン認識と機械学習（下巻、Metropolis-Hastingsアルゴリズム）」にはある。次元によってσが異なる場合はσ_minで妥協する様な話が書かれているが、ともかく。
σ_minの半分にした場合に必要な遷移回数がどうなるかというと、2倍ではなく4倍である。ランダムウォークをしているので、2乗になる。（正規分布をn個足したとき、平均はn倍になるが、標準偏差は√n倍にしかならない。標準偏差をn倍にするためには、n^2倍にしなければならない）

コンテストでは「集合間での所属の移動」や「順序の入れ替え」等が次元相当である場合も多く、この場合に1つの次元で移動可能な遷移半径は限られる。
遷移半径は2次元同時移動で√2倍、3次元同時移動で√3倍、4次元同時移動で√4倍……
（集合の移動をユークリッドだと想定して良いかどうかは疑問が残るが、各次元ともにプラス効果もマイナス効果もあって、その合計値がスコアであることを考えると、プラスとマイナスが打ち消し合う時の標準偏差を論じることになり、√がかかるはずなので、ノルムにユークリッドを用いるのは、そこそこ妥当だと考えられる）

前述までの延長線上で更に考える。ある温度から温度が2倍になったとき、適切な遷移半径も2倍になっていることが分かる。

適切な遷移半径から遷移半径を半分にした時、必要な遷移回数は4倍になる。
しかし、遷移半径を無理やり2倍にするためには、4倍の次元を同時変化させる必要が生じる。これには多くの場合、4倍の計算コストを要する。
これは見事に釣り合いが取れていて、前章「探索空間は本当に高次元なのか？」で述べた無相関の次元を同時に遷移させる場合のデメリットを考えると、遷移は常にほぼ最小単位で行うことが無難であるとの結論に達する。

ただし、複数の次元を同時に遷移させることで、前述を覆す高速化のメリットが得られる場合は、この限りではない。
そうした場合、いくつかの高速な遷移候補の提案方法が得られる場合も多い。ただし、温度に対して遷移半径が大きすぎる提案方法は、1σより広い遷移を行おうとしていることになるため、「パターン認識と機械学習（下巻、Metropolis-Hastingsアルゴリズム）」にもある通り、望ましくない。
1σの時の採択確率期待値は、正規分布の確率密度関数より導出可能で、これと比べて採択確率が大幅に下がった遷移候補提案方法はフェードアウトさせていくという方法を、現在検討している。（未検証）
もちろん、そういうことを行えば提案確率の左右対称性が結果的に狂うことにもなるが、ゆっくりと変化していくのであれば、影響は小さいと考える。

おまけ2 … 温度管理について

温度Tは、十分に高いだろう開始温度から、ゆっくりと下げていくことが前提となります。
しかしながら、遷移回数が十分に大きくない場合、開始温度は低いほうがパフォーマンスが出る場合も少なくありません。
何らかの事情で遷移回数が稼げるようになった場合は、開始温度を再検討する必要が生まれます。

次に、温度の下げ方についてですが、これは最終的に十分温度が下がって、途中で温度が上がるようなことがなければ、どの様に下げても、無限回の遷移があれば、うまくいくはずです。

しかしながら実際には無限回の遷移はないので、効果的な温度スケジュールを模索することになります。

著者は以下の様な温度スケジュールを好んで使っています。

T0 = 初期温度
n = 予定している全遷移回数
i = 現在の遷移回数カウンタ
progress = (i+0.5)/n
remain = (1.0 – progress)
T = T0 * pow(remain, paramA) * exp2(-progress*paramB)

ここで、最初はparamA=1, paramB=4ぐらいにしてあげると、T0に対してパフォーマンスの変動が鈍感になり、T0およびアルゴリズム側の調整もやりやすくなります。
（※paramA=1の場合、powは不要になる）

最終的にparamB=1付近でT0を調整した時に、全体パフォーマンスが無難に良い場合が経験上は多くあります。
ただ、場合によってはparamAとparamBの両方を調整した方がパフォーマンスが出る場合もあります。

終わりに

書き終えて読み返してみると、非常に苦情が来そうな記事である。
話がいちいち遠回り過ぎて、どうでも良さそうな部分に多くの文量が割かれていると感じる方も多いかもしれない。

しかしながら、この内容はまぎれもなく、2年前の著者が知りたかった内容であり、この内容を2年前に読んでいたなら、焼きなまし法を使えるようになるのに、こんなにも悪戦苦闘しなくて良かったと思える内容である。

本当は、非常に初歩的な基礎理論の根底に潜む普遍の考え方こそ、足場を固めてくれて、そこから自由な発想で踏み出すことができる。
自由であるということはどんな案も出せるということではなく、しっかりした指針が全て揃っているからこそ、通常では思いつかない様なことであっても、指針に外れていないことに気付き、実現してみようと一歩を踏み出せるのだと思う。

謝辞

この記事を公開するにあたって、少しでも皆様に分かりやすい記事としてお届けするため、@nico_shindanninさんに査読をお願いしました。
@nico_shindanninさんからは多くのご指摘を頂き、著者の力不足によりそれらすべての修正はできませんでしたが、初稿から比べてかなり読みやすくなったと思います。
また、おまけが2項目増えたことで、当初苦情が来そうだと思っていた読者層にとっても、少しだけ有益な記事になったかもしれないとも思います。
この場をお借りして、お礼申し上げます。

コメントを残す

メールアドレスが公開されることはありません。