2012年に読んだ面白論文紹介場所 参加記事です。３本立てです。
☆ 「博士の愛した数当て」
☆ 「It's not Automatic.」
☆ 「47」
まず１本目は、STACS'12 から "Playing Mastermind With Constant-Size Memory"。
ぼくの記憶は １ターンしか もたない
ヒット＆ブローあるいはマスターマインドというゲームがあります。 私が遊んだことがあるバージョンは
こういうルールでした。できるだけ少ない回数で当てることができたら、かっこいい。
さて、これの一般化バージョンを考えます。 「0-9までの数をN桁並べた数を思い浮かべる（以下同様）」。 Nを大きくしていくと答えのパターンは 10N 通りと急速に大きくなって当てるのが難しくなりそうですが… これをどれだけ速く解けるかということについては 放浪の数学者エルデシュ が取り組んだ結果があって、何も考えずに適当に ランダムに N/log(N)に比例する回数回 質問すれば、確率的考えてに、答えが１つに絞れるのだそうです。 これは意外と少ない。そしてオーダー的に、この O(N/log(N)) というオーダーは最低限必要とのこと。
……と、ここまでが前置き。
エルデシュの方法を実行するには、答えを１つに絞るために、N/log(N) 回の問答の内容（自分が何を聞いたら相手が何と返したか）を覚えておかないといけません。 でも、もし、自分の記憶が１ターン分しか保たない、 つまり、一番最後にやった問答のことだけしか覚えていられないとしたら？ それでもあなたは、ヒット＆ブローを当てることができるのでしょうか？
できる。 しかも普通と何ら変わらない N/log(N) 回のオーダでできる、 という感動的な結果がこの論文で示されます。
この論文を読んでいて、私は３回驚きました。
論文ではまずアイデアの骨子を伝えるために、 1ターンではなく2ターン記憶が繋がる場合を考えています。 この方法が、聞いた瞬間に「チートじゃん！！」と叫んでしまった驚きの１つ目。
考えてもみてください。 「たった2回の問答しか覚えられない」というと、とても短い記憶で苦しんでいるように聞こえますが、 1回の問答を覚えられるということは、自分がそのとき何を聞いたか、N桁の長い数を完全に暗記できるのですよ、 この人は。
これは実は大変な記憶力です。1回1回の問い合わせの答えはヒットとブローの数を表す自然数で、 最大で N なので、つまり log N ビットで表現できます。（自分の質問は、例えば決まった疑似乱数で 計算することにすれば毎回再計算できるので覚えなくてよく、相手の答えさえ思い出せれば構わないということです。） そして、エルデシュの結果によれば、N/log N 回問い合わせることができれば事足ります。 つまり掛け算して N ビットの記憶ができる人は、実は全ての必要な問答を記憶できているのです。
従って、2ターン記憶が保つ人の作戦は、こうなります。
ここまでだと「そんなのありかよ！wwwwwww」で終わってしまうのですが、 ここからがこの論文の本気です。1ターンしか記憶が保たない場合にどうするか。 自分の記憶のための復唱に問い合わせを使ってしまうと、今度は、それしかできません。 情報を集めるのに必要なランダムな問い合わせができないのです。逆に、 １回でもランダムに問うと、それまでに集めた情報を全て忘れてしまいます。
詳細はぜひ論文を読んで欲しいのですが、 問い合わせ列の領域を細かく分割して、ランダムクエリ用と記憶用に使う部分を 平方分割 ではないけどそんな感じに √N 桁毎に分割してじわじわ攻めていくと、 記憶と確定を最後まで同時に達成しきることができるという。 謎の精度計算とビット埋め込みテクノロジー。これは本当に感動的です。
そして、そもそもなんでこんなことを考えるのか？ の説明が第３の驚きでした。
「数当てゲームをたった１回の記憶で当てる手法を考えた」 と表現してしまうと私などは 「この人ひまだったんだなあ」 といった感想を抱いてしまうのですが、なんと、 この問題にはちゃんと真っ当な応用が念頭にあるらしい。
何に使うかというと、 焼きなまし法 などの確率的最適化アルゴリズムの実行時間評価。 最適化しようとしている対象の関数の正確な挙動はわからないけれど、 乱数ジャンプをうまく使っていい解を見つけ出していく… というタイプのアルゴリズムに対する考察をするにあたって、 記憶限定マスターマインドが重要になってくるのだそうです。
その手のアルゴリズムが最適解を見つけるまでに必要な繰り返し回数の下限を見積もる指標として "Black Box Complexity" という概念があるそうで、これは、 焼きなまし等の「どんな問題に対しても適用できる汎用手法」で出せるパフォーマンスの限界を、 「問題の構造に特化した確率探索アルゴリズムだったらどのくらいの回数で最適解を出せるか」 で見積もろうというものだそうな。
ところが…マスターマインドを焼きなましっぽい手法で当てようとすると クーポン収集問題的に考えて O(N × log N) 回の問答を繰り返す必要があるのですが、 ここまで述べてきたように、エルデシュの結果によるとこの問題はマスターマインドに特化した手法を使えば O(N / log N) 回で解けてしまう。つまり Black Box Complexity の評価は粗すぎるのでは…？ という批判があって、それに対して、「いや、エルデシュの方法は N/log N 回の履歴全部を記憶していないと実行できない。対して焼き鈍しは普通、直前の状態とせいぜい "温度" パラメタだけから次の状態を求めることを繰り返して最適解を見つける。つまり直前の状態しか覚えられない場合のBlack Box Complexityを考えて評価に使うべき。 そうすればO(N × log N)回という下限評価がきっと出てくるはず…！」 という期待を込めた予想がなされていたそうなのです。 ですが、今回の論文が驚異の記憶詰め込み術を用いて１ターンの記憶でもO(N/log N)回を達成し、 綺麗に予想を打ち砕いてしまった、と。かっこいいですね。
論文紹介２本目。次も同じく STACS'12 から "The Field of Reals is not $-Automatic" の紹介です。
足し算と掛け算を使って記述できる自然数に関する論理式の真偽判定を機械的に完全にすることはできない (※厳密な表現はなにか本読んでください) という結果に対して、一方で
という事実も知られています。 実数は自然数を含んでいることを考えると、前者は特に不思議に思われるかもしれませんが、 直感的な大ざっぱな理解としては実数の中で「この数は自然数である」という述語を定義するのが難しいので、 実数の中で自然数論を展開するのは難しいのでセーフ、という感じ。
この２つの結果は、どちらも、 "Quantifier Elimination" という技法を使って証明されています。 Quantifier Elimination については YouTube に 【ぉーん】接点ｔの問題を一瞬で解く【ＱＥ入門】 Quantifier Elimination という異常な動画があがっていて素晴らしいので、そちらをご参照ください。
さて、２つの結果のうち後者、足し算のみの自然数論なら行ける、という方については、 正規表現の実装などに使われる オートマトン を使った別の証明も知られています。 流れとしては、 「論理式が成り立つ」という条件を上手く言い換えて、 「このオートマトンにマッチする文字列は存在しない」という形に変形します。 そしてこの条件は機械的に検査可能です。
となると、はて、実数に関する決定可能性も、Quantifier Elimination だけではなく、 オートマトンを使った証明もできるのかな？ と考えるのが自然でしょう。
できません。 というのがこの論文で証明されていることです。
正規表現しちへんげ でも触れましたが、オートマトンで表現できる、というのは、要するに「メモリを定数しか使わないで表現できる」 ということです。
で、「自然数の足し算」というのは筆算で下の桁から計算していく様子などを考えるとわかりますが、 一桁分のメモリだけ持っておけば計算できるので、実にオートマトン的です。オートマトンチックです。 Automatic です。対して、掛け算はそうでもありません。なので、足し算だけの自然数論なら、 全体をオートマトンで表せるのです。
実数だとどうでしょう。0.999999 = 1 問題などの細かいところで色々注意と技が必要ではあるのでこの段落の以下の説明はかなり不正確ですが、 まあ大雑把に言うと、実数でも、 足し算の筆算は基本的に桁を揃えればあとは順々に桁を見ていくだけなので、 オートマトンチックにどうにかなります。
掛け算は…普通の数の表記法だと難しそうですが、何も普通の数の表記法だけにこだわる必要はありません。 例えば、元の数の log をとって10進数表記することにすると、log(xy) = log x + log y なので、 掛け算は足し算に変化し、オートマトンで表現できるようになります。 問題はこっちの表記法だと今度は足し算が難しいことで、つまり問題はこうなります。 「足し算と掛け算がどっちもオートマトンチックにできるような実数の表現方法はあるか？」
ない のです。
証明は、もしオートマトン的な表現ができたとすると、 実数の中で「等差数列」に近い物が扱えてしまい、等差数列というのはつまりだいたい自然数です。 オワタ＼(^o^)／
３本目の紹介です。23:00にこの記事を公開するつもりだったのですが、 気づいたら24:00を回ってしまったし眠いので簡単に紹介だけ。
自分的には上記の２本がズバ抜けて面白かったので迷ったのですが、 "The Ford–Johnson algorithm still unbeaten for less than 47 elements" が去年読んだ中では次に印象に残っているかなあと思います。 "still unbeaten" の辺りの響きがかっこいい。
どういう論文かというと、 ソートは最小何手でできるか（よく知られている下限である log_2(n!) にどこまで近づけるか） っていうのを機械で探索する話。
という結果が知られているところに、
ということをまた計算機をブンブン回して確かめたという報告論文です。
理論的な計算量の話を、あたかも自然現象をシミュレーションで再現して観察するかのように、 マシンの力を振り回してとりあえずアルゴリズムをひたすら試してみて観察すると何か道が開けるのではないか？ という方向を提案する Experimental complexity theory というスライドを読んでちょうど感心していたところだったので、 具体的にこういうことをやってみている論文を読んで非常に楽しめた次第でした。