焼きなまし法の真実

はじめに

著者は、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項目増えたことで、当初苦情が来そうだと思っていた読者層にとっても、少しだけ有益な記事になったかもしれないとも思います。
この場をお借りして、お礼申し上げます。

カテゴリー: 未分類

オーバーフィッティング回想録

はじめに

この記事は以下の競技プログラミングイベントの一環として書かれました。

Competitive Programming Advent Calendar 2014
http://partake.in/events/9b53847a-3a97-4aac-b754-5e681c3c7197

前置き

マラソンマッチでシステムテストの後に順位が落ちた。
……そんな経験はありませんか?

それは一般的に過学習やオーバーフィッティングと呼ばれます。

私事ですが、最近、暫定1位からのシステムテスト転落があまりに多くありました。

2014年6月4日: 2014 TCO Marathon Round 2 "RectanglesAndHoles"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15982
終了時暫定1位→システムテスト後5位に転落

2014年6月28日: EPA Cyano Modeling Challenge "CyanoHABsPredictor"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15995
終了時暫定1位→システムテスト後5位に転落

2014年7月2日: OmegaDetector
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16001
終了時暫定1位→システムテスト後2位に転落

2014年10月27日: Design of Experiments "OptimalDrug"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16168
終了時暫定1位→システムテスト後11位に転落

『ちょwww コルンさんwwwww システムテスト無視してプレイしてるでしょ!?』
『また、暫定だけ1位ねwwww』
『システムテストで落ちて良いなら、誰でも暫定1位ぐらい取れるわwwww』

そんな声が聞こえてきそうなぐらいの連続転落なので、少し振り返ろうと思います。

そもそもマラソンレッドコーダーとオーバーフィッティングとは、切っても切れない関係にあります。

オーバーフィッティングとは

まずは導入として、私にとって最初のマラソンマッチにまで振り返ります。

2011年4月5日: Contest: Marathon Match 68 "BeautifulCrossword"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14495

順位 ハンドルネーム 暫定スコア 最終スコア
1 wleite 66.67 668.77
2 colun 66.50 664.73
3 EmK 65.73 658.76
4 OgieKako 64.64 645.36
5 ainu7 64.44 645.08

暫定2位、システムテスト後2位で、転落はありませんでした。

しかし、上位5人の暫定スコアとシステムテストスコアの推移に注目して下さい。
暫定テストでは100テストケースなのに対して、システムテストでは1000テストケースですので、単純計算で10倍するだけで、ほぼ同じぐらいのスコア基準となります。

wleiteさん、EmKさん、ainu7さんの3人は、ご存知(?)、3人とも有名なマラソンレッドコーダーです。
スコア変動を見ると、66.67→668.77、65.73→658.76、64.44→645.08と、3人が3人とも、システムテストで10倍よりも少しだけ良いスコアになっています。

対して(私含めて)イエローコーダーの2人ですが、66.50→664.73、64.64→645.36という具合で2人とも10倍よりも少しだけ悪いスコアになっています。

これは実は偶然ではなく、必然です。
システムテストによって上がることはほぼ無くて、システムテストによって落ちることだけが、オーバーフィッティングが原因で時々あります。

レッドコーダーは、オーバーフィッティングを避ける手段を持っています。

原因を探ると、この時私は初参加でしたので、自前のローカル環境にて100テストケースぐらいでテストを行っていました。
このコンテストが終わった後すぐに、chokudaiさんから、ローカル環境で確認する際は、300テストケースぐらいを使っていることを教えて頂きました。

それ以降、私は基本的には、ローカル環境では1000テストケースを目安に使う様にしています。

実はマラソンマッチで良くあるヒューリスティクス系の出題では、オーバーフィッティングによる順位の変動は微々たるもので、最終順位の変動のみを見るのなら、100人ぐらい参加しているコンテストの場合で、多く変動した時でも3位落下ぐらいの変動に収まることが多いです。
そのぐらいの差しか出ないのは、ヒューリスティクス系の出題のほとんどが、LocalTests、TestExamples、FullSubmit、SystemTestsの4つで取り扱う問題が、本質的に同じであることが原因です。

それでも、FullSubmit結果を見ながら方針を選んでしまうと、パラメータ側だけに限らず、アルゴリズムそのものに、オーバーフィッティング要素が紛れ込んでいきます。
その結果が、3位程度の落下へと繋がります。

オーバーフィッティングの可能性がある環境下では、どちらに舵取りして良いのか分からない状態になりますので、それを取り除くことで、どちらに舵取りすれば良いのかが分かる様になり、結果的に最終順位(及び暫定順位も!)を大きく伸ばすことができます。
微細な差であっても、10000テストケースもテストしてハッキリと差が見えていれば、本当に些細であっても、偶然ではないことが分かります。

実際には標準偏差など統計手段を用いることで、もうちょっと具体的なことが言える様で、この辺ainu7さんが良く話題に出しています。

私はあまり詳しくないのですが、たとえば標準偏差が100のとき、100テストケース平均の標準偏差は10ぐらいで、10000テストケース平均の標準偏差は1ぐらいになるのかな?? と思っています。(テストケース数の平方根で割ることができる?)
ただこの話には、テストケースごとの最適解スコアの標準偏差の話と、同じテストケースに対するソルバの使用乱数列による獲得スコアの標準偏差の話が混じっているので、実際にはそこまで単純な話ではなく、後者を真面目に求める手間がとても大きいので、1000テストケース以上である程度の差が出てれば、感覚で判断して有用な変更だったと結論付ける様にしています。

この辺、詳しい人いましたら、ぜひご指摘ご指導頂きたい所です。

それでも起こるオーバーフィッティング

さて、それじゃあ1000テストケースぐらい用いるのだから、オーバーフィッティングとはもう無縁ですね、さよならグッバイ。
……残念ながら、そうもいきません。

さよならグッバイ、オーバーフィッティング……で済むのなら、なぜ私は今年に入って4度も、暫定1位から転落しているのでしょうか?

前フリがだいたい終わりましたので、ここから本編です。
それでも引っかかるオーバーフィッティングの脅威について、ここからコンテスト別で説明していこうと思います。

レアケース

非常に間抜けな転落をしたのが、TCO14MR2でした。

2014年6月4日: 2014 TCO Marathon Round 2 "RectanglesAndHoles"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15982
終了時暫定1位→システムテスト後5位に転落

落ちた原因は、セグメンテーションフォルトでした。
発生確率は80テストケースに1テストケース前後だった様です。

2文字書き換えれば(あるいは妥当な値じゃなくて良いのなら、1文字書き加えれば)システムテスト後もおそらく1位でした……というのは置いておいて、これもまた実力ではあります。
現に、私のローカル環境のテストではやはり1000テストケースぐらいテストしていて、セグメンテーションフォルトが大量に出ていました。
ただ、採点機構を自動化していたため、警告に気付きませんでした。
最終日の最終サブミットのみでしか出て来なかったエラー要素だったため、疲れていたこともあり、完全に見逃しました。
(最終サブミットの1つ手前のサブミットのままだったら2位ですね……1位が取りたかったので、その選択肢は無いのですが)

セグメンテーションフォルトが出るとデータベースに突っ込まれる値がnullになるのですが、全体スコア算出の際にnullを除いて計算していたことが原因でした。

と、TCO14MR2に限って言えば間抜けな話なので二度と繰り返すはずもないという話で決着するのですが、実はそう簡単に片付けて良い話でもありません。

同類の問題がTCO12MR2の際にもありました。
セグメンテーションフォルトではなかったものの、不確定反復問題だったため、無難な選択をしてみても、実際に蓋を開けてみたら不運が重なって早期ゲームオーバーになることがありました。
パーフェクトゲームを目指せる問題でしたので、99.5〜100%の点数を狙う中、時折0〜50%付近を取ってしまうテストケースが存在するというのは、とても大きな痛手となります。
この時は確か、ローカルテスト上で20000テストケースぐらい走らせて10件程度の0〜50%テストケースが存在しました。
この時のSystemTestsは3000テストケースだったので、1.5件程度の0〜50%テストケースが存在するはずですが、実際には3件発生しました。

ちなみに1位の人でも1件、2位の人でも3件、発生しています。

上位陣はほぼ理想点で横並びになった後、稀に存在する0点テストケースの数で順位が決まる……この0点テストケースの割合は工夫に依って減らせるものの完全に0にすることは難しく、SystemTestsに使用されるテストケース数が充分に多くないため、運ゲーになる場合があります。
こういうケースでは、FullSubmitによる暫定順位に大きなノイズが加わっている場合があります。また、SystemTestsも運次第です。開けてみなければ結果は分かりません。

高速化

実は、オーバーフィッティングしなければならない要素があります。
その1つが、高速化です。

Javaだと同じプログラムが異なるOS上で動きます。
C++でも、Javaほどではないにせよ、ある程度の環境で同じ様に動作します。

しかしながら、まったく同じではありません。
動作速度が異なります。

CPU、メモリバス速度、コンパイラバージョン、OSコア等の要因によって、動作速度が変わってきます。

そんなもの、良いCPUを積めば速くなるだけだろう?

その通りなのですけれども、違うんです。それだけじゃない。

CPUによって、得意とする命令、不得手とする命令が、異なります。

単純にどの命令も均一に速くなるだけでしたら、ローカルで高速化を施し、あとは本番環境で動かすだけです。
ところが、ローカル環境と得手/不得手が異なる場合、ローカル環境で高速化を施すこと自体が悪いオーバーフィッティングになります。

では、しなければならないオーバーフィッティングとは何でしょうか?

簡単です。本番環境にオーバーフィッティングさせることです。

これをやっているかどうかは、ExampleTests数を見れば分かります。
明らかに初心者じゃない人が、明らかに不自然な短い間隔で20連投以上していたなら、きっとそれは、本番環境のマシンの特性を調べています。
ただ、ExampleTestsの問題固有の速度計測になる場合がありますので、そういう場合は特定の問題を埋め込んで、埋め込んだ問題を計算させて時間を測定し、最後にダミー回答を返したりする場合もあります。
(入力値が大き過ぎる場合は、これが出来ない場合もあります)

配布データの延長線上に本番データが無い

さて、これまではオーバーフィッティングとは言っていたものの、機械学習以外のコンテストの場合が多かったのですが、ここでは機械学習系のコンテストを取り上げます。
ヒューリスティクス系のコンテストではオーバーフィッティングによって順位が落ちても3位以内であることが多い旨を書きましたが、機械学習系の場合はオーバーフィッティングによって1位→最下位があり得ます。

むしろここが本題と言ってよいでしょう。

オーバーフィッティングの避け方については、他の専門記事等に譲ることにします。
マラソンマッチアドベントカレンダー内でも、機械学習系の記事を載せる予定の方々がいる様ですので、そちらに譲ります。

ともかく、本記事はそういうガチのオーバーフィッティング回避テクニックに関してではなく、コンテスト特有の部分に焦点を当てたいと思っています。

ある意味で破綻していますが、程度の差こそあれ、賞金ありのコンテストでは配布データの延長線上に本番データが無いことがあります。

多くのコンテストでは、配布データとExampleTestsとは同じなのですが、FullSubmitとSystemTestsに使われるデータは異なります。

異なるだけであり、本質的には同じ……であるなら問題ないのですが、本質的に異なることが多々あります。

2014年6月28日: EPA Cyano Modeling Challenge "CyanoHABsPredictor"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15995
終了時暫定1位→システムテスト後5位に転落

上記は、周期問題であるにも関わらず、配布されたデータ(およびExampleTests)の学習期間は1年分のみでした。
FullSubmitではそれが1年半分ぐらいになり、SystemTestsではそれが2年分ぐらいになります。
SystemTestsでは有効そうな手法が、ExampleTestsでは使えず、FullSubmit以降でしか有用性の検証が行えませんでした。
実際それが有効だったから5位までしか転落せずに済んだのだと思いますが、ともかく、FullSubmitでオーバーフィッティングするしか検証方法がないコンテストというものが、稀にあります。
(この手法を使う前の順位が暫定6位ぐらいだったので、もろもろの要素から考えると、この手法を使わなかった場合の順位は8位以下だったものと思います)

このように、FullSubmit以降でなければ存在しない要素が事前に分かっている場合は、FullSubmitスコアのみを見て学習させていかなければならない場合があります。
この場合、あえてオーバーフィッティングを選ぶ選択肢があります。
もちろん、暫定1位に躍り出ても、最終順位は落ちる可能性が高くなります。
でも、その要素を使わなかった場合の順位はもっと悪い可能性が高く、FullSubmitスコアで調整することを意図的に選ぶ場合があり得ます。

次の問題に行ってみましょう。

2014年10月27日: Design of Experiments "OptimalDrug"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16168
終了時暫定1位→システムテスト後11位に転落

この問題、配布されたデータはテストデータ生成器で、FullSubmitおよびSystemTestsはリアルデータでした。
……もはや延長線上どころの騒ぎではありません。

CyanoHABsPredictorの際に、SystemTestでまで効果があった要素が、LocalTestsで検証不可能だったという、運営への不信感があります。

また、更に昔……MM73 OrdinalTraitAssociationMappingというコンテストでは、FullSubmitで故意にオーバーフィッティングしなければ4位以上に入れなかった問題もありました。

2011年7月27日: Marathon Match 73 "OrdinalTraitAssociationMapping"
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14584

流石にMM73の様なことはもう二度と繰り返されないと思いたいのですが、TopCoderMarathonMatchの機械学習系の問題の質は、不信感だらけでどれぐらいアテにして良いのか良く分からない状態です。
(※ 逆に、ヒューリスティクス系の問題の質は、どれも安定して高いです)

さて、OptimalDrugに話題を戻します。

結論から書きます。この問題は、他のTopCoder機械学習系の問題と比較して、問題の質は高い方だった様です。
様です、というのは、少なくとも参加者の中には、ただの1人も、リアルデータにのみ有効な要素を見つけ出す事ができた人がいませんでした。
すべての参加者は、非リアルデータに存在していた要素によって、最終順位が決まりました。

この根拠は、膨大な量の非リアルデータ(シードを変えればいくらでも公式のデータ生成器によって生成可能)を使って、Psyhoさんが実験を行い、その結果を掲示板に書き込んでいます。

Some stats about the system tests
http://apps.topcoder.com/forums/?module=Thread&threadID=836129&start=0

この結果を見ると、実際のSystemTestsによる順位と、公式のデータ生成器による順位との間に、強過ぎる相関があることが見て取れます。
非常に妥当な順位であったことが分かります。

このように、配られたデータが非リアルデータであり、実際のシステムテストがリアルデータで行われるとしても、非リアルデータでの検証で充分な場合もあり得るということです。

ただ、私の把握している範囲でも、配られた非リアルデータとFullSubmitでのリアルデータの間には、あり得ないデータ特性の差異がありました。
単純に誰も辿り着けなかっただけで、やはりFullSubmitでなければ検証できない要素があった可能性も、否定自体は出来ません。

追記:
この記事の公開後にyowaさんに指摘されたのですが、Psyhoさんの掲示板への書き込みデータは、非リアルデータでの全員分のシミュレーション結果ではなく、システムテスト結果点数を用いてのブートストラップらしいです。

少し極端な例で説明すると、たとえばシステムテストが3つしかなかったとします。3つをAとBとCだとします。実際のシステムテストではABCの3つのテストが行われたのですが、もしかすると出題に偏りがあり、AABとかACCとかいう出題だった可能性もある、という理論のもと、沢山シミュレーションします。
その結果として、各競技者が、何位の確率が何%で……というのが出てきます。

ここでは極端な例として3つしかシステムテストがなかった場合を示しましたが、システムテストが多ければ多いほど、このシミュレーションは妥当な結果を出します。
Psyhoさんの出した結果がSystemTestsによる順位と相関が強過ぎたのは当然の話で、PsyhoさんはSystemTestsの順位が揺らぐ確率がどのぐらいあったのかを知りたかった、ということの様です。

というわけですので、残念ながら、このコンテストにおいても配布データはアテにならなかった様で、FullSubmitのオーバーフィッティングを目指した路線は、どうやら間違いだったと断定はできない様です。

そこに賞金がある限り、使える手段はなんでも使って、SystemTests1位を狙うのがコンテストです。
オーバーフィッティングとは仲良く付き合って行かざるを得ません。

(※ただ、OptimalDrugに限って言えば、妥当であってはならないデータ特性を採用してしまいましたので、反省が残ります。もう少し運営を信頼すべきでした

システムテストの偏り

SystemTestsの件数をチェックしましょう。
それが40件ぐらいしかないのだとすると、運ゲー度が増します。

2014年7月2日: OmegaDetector
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16001
終了時暫定1位→システムテスト後2位に転落

上記の出題は、バーコードの画像認識ゲームでした。

画像認識であることもあり、問題の性質上、スコアの標準偏差は高い状態にあります。
しかし、FullSubmitが100件、SystemTestsが222件ある、そう安心していました。

2日半程度しか参加していないコンテストなのでそこまでこだわりは強くないのですが、試合終了後しばらくしてから一応見直しをしました。

まず、Test Case 33〜39ですが、Psyhoさんが0点を連発している傍ら、僕は2300点前後を連発しています。
Test Case 49〜53ですが、Psyhoさんが0点を連発している傍ら、僕は1400点前後を連発しています。
そしてTest Case 177〜184ですが、Psyhoさんが1400点前後もしくは2300点前後を連発している傍ら、僕は0点を連発しています。

お気付きでしょうか? 0点を取るテストケースの偏りが、偶然では片付かないほど偏っているのです。

ひとまず、どれだけデータに偏りがあろうとも、そこまで含めてのコンテストなので、それも実力のうちです。
それは間違いないのですが、本記事の目的はオーバーフィッティングを回想し、同じ轍を踏まないことです。

おそらく8問程度はほぼ同じ画像……下手すると16問ぐらいほぼ同じ画像だった可能性があります。
全部で200問以上あるんだから8〜16問程度似た画像でも問題ない? 果たしてそうでしょうか?
テストケース間の相関が高い時、同じ解法プログラムでのスコアの標準偏差は高くなります。
つまり、順位はひっくり返り易くなります。
あるいは、FullSubmitによる暫定順位の時点で、偶然ひっくり返ったランキングが出易くなります。

そして、SystemTestsに8件のほぼ同じ画像があったとした時、その内訳を気にするべきです。

以下は問題文だか、あるいは問題文と同等の価値を持つ、掲示板への主催者サイドの書き込みです。

「ダウンロード可能な学習データ10件は、人の手によって、慎重に選ばれました」

学習データはランダムにではなく、人の手によって、意図を持って選ばれています。

こうして考えた時、内訳は果たして以下のどれだったのでしょうか?

A. 学習データ0件、FullSubmit0件、SystemTests8件
B. 学習データ0件、FullSubmit4件、SystemTests8件
C. 学習データ1件、FullSubmit0件、SystemTests8件
D. 学習データ1件、FullSubmit4件、SystemTests8件

思うに、少なくともCまたはDです。
なぜなら、SystemTestsに8件以上も含まれている系統画像があったら、1つは配布学習データに加えると判断するのは妥当です。
更に私の提出したプログラムは、与えられた学習データのとある1つの画像に対してだけ、0点を出します。

意図的に選ばれたとする出題者発言から、私は、それが最も極端な例であると推理しました。
最も極端な例であれば、他の例は基本的にはそこまでは極端ではないので、読み取れないでも問題ありません。

しかしながら、極端な例であれば、ほとんど同じ……少しだけ撮る角度や明るさを変えた画像が、SystemTestsにおいて複数用意されている……そういう可能性を、考える必要がありました。

次回からは、その可能性を考慮に入れて取り組むことになりそうです。

採点バグ

最後になりますが、マラソンマッチの採点サーバーにはバグがある場合がある様です。
毎回あるバグなのかどうかは分かりません。むしろ1回しか出会った事がありません。

採点処理は単純ではないため、毎回別の採点プログラムを使用している可能性があり、問題固有のバグだった可能性が高いです。

2014年8月21日: ChildStuntedness
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=16065
終了時暫定53位→システムテスト後59位に転落
(ただし59位は最下位であり、0点の順位。32人が0点で最下位)

0点落ちには著名レッドコーダーのwleiteさんも居るため、簡易的に説明する際にはこれを免罪符に挙げますが、実は問題はこれではありません。
0点の原因は、正直良く分かりません。wleiteさんに関してはTLEの可能性が高く、私にもTLEの可能性はあります。

TLE自体は仕様であり、TLEで0点は別に構わないのです。

問題は以下の2つの示す暫定スコアの差異です。

順位表:
http://community.topcoder.com/longcontest/stats/?&sr=51&nr=50&module=ViewOverview&rd=16065

順位 ハンドルネーム 暫定順位 暫定スコア 最終スコア
59位 colun 53位 128,828.09点 0.00点

サブミット履歴:
http://community.topcoder.com/longcontest/?module=ViewSubmissionHistory&rd=16065&pm=13367&cr=22689976

サブミット番号 日時 暫定スコア 言語
5サブミット目 08.16.2014 22:55:43 0.00点 C++
4サブミット目 08.15.2014 07:38:43 0.00点 C++
3サブミット目 08.15.2014 02:59:01 128828.09点 C++
2サブミット目 08.14.2014 17:21:16 190020.06点 C++
1サブミット目 08.14.2014 15:13:01 103856.49点 C++

最新サブミットである5サブミット目が0.00点であるにも関わらず、暫定スコアは128,828.09点のままでした。

当時の状況としては、以下でした。

FullSubmitを送信
→Queue Statusからはすぐに取り除かれる
→しかしメールで結果が来ない
→ちょうど24時間ぴったり経った頃に、メールが届く
→しかしメールの内容は、送ってもいないExampleTests

私のメールボックスには、ExampleTest13の結果メールが3通分あります。
(1通目はExampleTest13、2通目はFullSubmit4の24時間後、3通目はFullSubmit5の24時間後)

それで、こんな面白い状況を放っておくわけにもいかない……と思い、そのままゲームを離脱、レッドコーダーからイエローコーダー転落と相成りました。
(レーティング変動のキャップが150だと思い込んでいて、0点提出してもレッドからは落ちないと思い込んでいたのが、安易に好奇心に負けた理由です)

話をはしょって勉強会でちょっとその話をした所、「TopCoderへと異議申し立て、直談判とかしないんですか?」とかいうことを言われましたが、するはずがありません。
レーティングなんてどうでもよくて、僕は上記状況における好奇心に負けました。
なので、0点であること、その点数によって最下位であること、また最下位であるからレーティングがキャップまで落ちることは、とても正当なことです。
どこにも異議申し立てを行う要素などあるはずがありません。
レーティングを大切にする場合のこれに対する正しい対処は、試合が終わる前に、メールまたは掲示板に、この旨を主催者側へと連絡すれば良いのです。
明らかなトラブルで、問題自体に触れない内容なので、この場合はおそらく掲示板への書き込みで問題ないと思います。

しかし僕は、それをしませんでした。好奇心に負けたのです。
対処しないでほしかった。
このまま終局した時に、3サブミット目がアクティブとしてシステムテストに使われるのか、それともやはり最終サブミットである5サブミット目がシステムテストに使われるのか、それを知りたかった。
結果、知識欲は満たされました。
だからこれはこれで良い。

ただ、落ちる前の私のレーティングでさえ、某所から苦情が来ます。
colunさんのあのレーティングは詐欺だ、と。(※リップサービスの可能性はあります)
確かにTCO予選だけ出場してればもっと上がりそうだなと思います。予想としてはちゃんと時間を取った上でのヒューリスティクス系の問題に限って言うなら2500前後は難しくないでしょう。
ただ、レーティング付きの賞金ありコンテストが開かれれば登録して調査のためにサブミットしてみることもあるでしょうし、途中で投げ出せば0点のまま終わることもあるでしょう。

レーティング付きの賞金ありコンテストが存在し、かつ仕事の合間に賞金狙いで参加している以上は、それは仕方がないことです。(今回紹介した暫定1位転落で、不本意だったのはTCO14MR2のみです)
その辺まで含めて、実力であり、今のレーティングは正当なものなのかもしれません。

ただまぁ、流石にイエローコーダー落ちは落ち過ぎなので、これはそのうちどうにかしたいと思っています。

また、投げ出さずとも、機械学習系のコンテストはヒューリスティクス系ほどには強くないです。それらが同じレーティングとして評価されるという点は若干不自然に思っています。
師匠(大学院の某教授)からは、ヒューリスティクスも機械学習も本質的に違うはずがないから、単に勉強不足なだけだろうとお叱りを受けたりもしています。
その辺の検証も含めて、たとえレーティングが下がっても、今後機械学習系のコンテストには積極的に参加していく予定です。

終わりに

今回はあまり需要のない所をアドベントカレンダー記事にしたかもしれません。

ただ、なんとなく普段のツイッターで、需要のある所は定期的につぶやき続けている様な気がしますので、今回は地味な内容を取り上げてみました。

今回のイベントにと誘って頂いたtomerunさんに感謝しつつ、本記事を締めくくろうと思います。

カテゴリー: 未分類

TopCoderのスタックサイズの増やし方・改

参考記事

TopCoderのスタックサイズの増やし方 – 赤コーダーになりたい

本文

kusanoさんに情報提供した際に、「スタック書き換えるからスタック上の関数スコープ変数とか全部使えなくなるよ(意訳)」みたいなことを言ったものだから、その通りの内容で記事を書いて頂く結果になりました。

しかし、よくよく考えれば、rsp以外にもrbpがある。
gccでは関数スコープ変数で可変長配列が可能なので、関数スコープ変数へのアクセスがrbpであることが保証されるはず……と思ったのですが、可変長配列が使われていない場合は-O2オプションでrbpが使われることが保証されない様でした。
だったら可変長配列を強制すれば良いのではないか、と思いまして。
allocaを入れることで、この問題は解決しました。

#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));

#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

上記の様なマクロをあらかじめ定義しておいて……

class PairGame{public:
int maxSum( int a, int b, int c, int d )
{
    BEGIN_STACK_EXTEND(128*1024*1024);

    //  メインの処理
    f1(a, b, 1234567, 1234567);
    int r = f2(c, d);

    END_STACK_EXTEND;
    return r;
}};

とするだけで、問題なくいけました。

捕捉(追記)

インライン展開等によって、しばらくは書き換え前のスタックが使われる場合があることが確認されています。
ただ、その場合であっても、階層が深くなる場合、どこかのタイミングで書き換え後のスタックが使われる様になることが確認されています。

また、現時点では確認した全ての状況で上記マクロで問題なく動いていますが、上記マクロで問題なく動かないケースがあるかもしれません。
そういうケースが見つかった場合は、問題番号と不具合の生じたコードとどういう不具合であるかを、colunまでご一報頂ければ幸いです。

蛇足

今回はコンテストプログラミングの話題なのでkusanoさんの記事では触れてもらえませんでしたが、例外処理(try catch finally等)を使う場合は、セグメントレジスタの書き換えも必要だった気がします。(うろ覚え)(たしかSSではなくFSだったと思いますが…Windows環境だけだったかも? 分かりません。記憶ではFS[0]とFS[1]が……ぶつぶつ)

カテゴリー: 未分類

fluentdの勉強会行って来た

帰ったらブログ書いてね、って発表者が言ってたので、律儀に書く。

Fluentd meetup in Fukuoka
http://www.zusaar.com/event/501053

fluentdってのは、ログ取りのためのプロダクト。
ログ取りには必ず目的がある。それは、取ったログを元に何かを把握するってこと。
通常、以下の様な流れになる。

情報源→収集→貯蔵→処理→可視化→報告書

さて、この中でfluentdがやってるのは収集の部分。
他の部分に関しては、他のツールがあるだろうから、ノータッチ。

まぁ一口に収集って言っても、世の中には色々な情報源がありますから、
情報源ごとに情報を切り出すコード書かなきゃいけないよねー ってのはfluentdがあってもなくても同じ。
誰かが書いたコードを拾ってこれたら良いねー、、、ってのも、fluentdがあってもなくても同じ。
じゃあfluentd無くて良いじゃん? んなこたない。

違うんですよ。違うんです。
確かに情報源から情報を切り出すコードは個別に書かなきゃいけない。
でも、切り出した後の情報って、どうなるんです? 切り出して終わりじゃないよね?
切り出した後の情報には、その後のだいたい共通になるプロセスがあるんですよ。
それをパッケージ化致しやしょう、ってのがfluentd。

ん、違う? そうですよね、それだけがfluentdではない。
結局、切り出した情報を保存したい先ってのも、その時々でケースバイケースなんです。
だから、MySQLに突っ込みたいときは、MySQLに突っ込むコードを自分で書くか、どこかから拾ってこなきゃいけない。
だから、MongoDBに突っ込みたいときは、MongoDBに突っ込むコードを自分で書くか、どこかから拾ってこなきゃいけない。
だから、ツイッターに突っ込みたいときは、ツイッターに突っ込むコードを自分で書くか、どこかから拾ってこなきゃいけない。

……ええと、それもプラグインとして扱いやしょう!

情報源がN個あって、突っ込み先がM個ある時に、実装がN×M個もあったら大変だよね。
実装はN+M個にしようよ。間にfluentdを挟んでさ!
(NとMが100ずつなら、N×Mは10000になってしまうけど、N+Mなら200で済む!)

っていう、コード再利用の仕組みがfluentdなわけです。
プラグインを個人個人で公開するための場所も用意されているので、自分の書いたコードを他人に再利用してもらうのも簡単だよねー
っていう風に、使う側と作る側の両方をつなぐ再利用の仕組みがfluentdなわけです。

再利用し易いために、ログをJSON形式でやり取りしているのかもしれません。

そんなコードの再利用性を高めた先で出来る様になったことっていうのは、個別の収集コードを書いてた頃よりもずっとずっと豪華な機能達ですよ、と。
そんな豪華な環境に皆が集まって来た結果として、情報源からの情報切り出しプラグインも、貯蔵先へのデータ突っ込みプラグインも、かなりの種類が揃っている。
かなり細かな部分まで、既存のコードがあるから、新しいの書かなくて良いよ、そんな環境が整ってしまった。

こっちの水は甘いから、飲んでみろ!

……以上、fluentdの勉強会の参加リポートでした。

カテゴリー: 未分類

プログラミングコンテストのビジョン

==前書き==

知人とのお酒の席でこの話をしたら、知り合いに紹介するのに今話した内容を文章で欲しいと言われた。
なのでブログに貼付けておくことにする。

==本文==

長期間(最低12時間〜最頻で2週間程度〜最長で3年ぐらい)で競うプログラミングコンテストでは、プログラミングの能力で1位を決めたりはしない。
ゲーム理論やグラフ理論といった、もっとプログラミングが関係のない所で、1位が決まる。
観戦のみであれば尚更、プログラミングコンテストを楽しむのに、プログラミングの能力は必要ない。
本当の一般人であっても……1億人を超える日本人のほとんどが観客として楽しめる様な、そんなプログラミングコンテストを僕は目指している。

高専プロコンは20年以上の歴史を重ねて来た。
目で見て理解し易いロボコンの大衆への浸透率が高かったことに対して、目で見て理解し辛いプロコンは大衆にまだ浸透できていない。
これを重くみた高専プロコン運営は、試行錯誤を重ね、少しでも一般観衆が見て分かり易いコンテストを作ることを心がけて来た。
そんな文化の中で僕は育った。

近年の高専プロコンでは、この辺が改善されてきている。
観衆が見て分かり易くするためには、問題の視覚化がポイントだった。
コンピュータの中で計算上で起こっているはずのことを、体感し易い様にいかに可視化するのかという話だ。
そこはコンテスト運営がいくらでも工夫可能な部分だ。
野球やサッカーやゴルフの様な、あるいはアイススケートに匹敵する様な視覚効果をもたらすことができる。
ボクシングやK1の様な分かり易さを観客に提供することもできる。
また、プロコン自体の性質上、囲碁や将棋の様な深い思考を観客に提供することもできる。
クイズ番組や教育番組の様に、観客と一緒になって考えていくこともできる。
また、あらゆるスポーツの様に、スター選手という偶像を作り出し、それを観客に提供することもできる。
初心者にも分かり易いことを解説するスター選手もいれば、上級者向けの難しい解説をまじえるスター選手も出てくるだろう。

プログラミングを売りたいのではない。
僕が売りたいのは、論理的な戦略立案能力だ。
それを実現するために実動部分ではプログラミング能力が要る。
しかし観戦する分には必須ではない。

問題文を読むだけでは問題への理解は足りず、コンピュータに計算させることでデータを増やせる。
そのデータをもとにして、よりよい戦略を立て、それを実現していく。
企業活動……ビジネスそのものと非常に類似点は多い。
コンテストでは問題をやや単純化しているため、実際にはビジネスの方が複雑だとは思う。
単純化した仕組みの中でうまくいく戦略を立てられなければ、複雑化した現実社会の中で戦略を立てることはより難しい。
要は、ゲーム戦略、企業戦略、経済戦略、恋愛戦略……そうしたもののシミュレーションを通した戦略立案コンテストなのだ。

ここ数年、プログラミングコンテストが乱立している。それはとても良いことだと思う。
しかし乱立している理由は、企業が優秀なプログラマを招き入れるためである。
求人のためのプログラミングコンテストなのだ。それはそれで悪い流れではない。
しかし僕は、大衆のプログラミングコンテストを目指していきたい。 seo links . Tripticlideskruc .

カテゴリー: 未分類

マラソンマッチの取り組み方

目次

はじめに

皆さんこんにちは。

この記事は、下記のイベントの一環として書かれたものです。

Competitive Programming Advent Calendar
http://partake.in/events/ee35b200-e151-44c1-b123-482d0a7447b5

マラソンマッチ上位者と言えば @chokudai さんや @wata_orz さんが有名ですが、二人に比べれば多少劣るものの、私もマラソンレッドコーダー保持者の一人です。
マラソンレッドコーダー保持者は今の所、日本に5人6人しかいない様です。

実は、私の実力を客観的に見ると、マラソンマッチのレーティングで言うと1500〜1700ぐらいが妥当な線だという自覚があります(私より明らかに実力が上の方々が1700付近でとどまっていますので)。
ところがどういうわけか、2200以上のレッドコーダーを保持できています。
そして、今後も定期的にマラソンマッチに参加するつもりですが、レッドコーダーを保持し続けるのは難しくないように感じています。

私より実力が上なのに1700付近の方々と、私と、一体何が違うのでしょうか?
1つはマラソンにかけられる時間量かもしれません。
でも時間がたっぷりあれば、本当にマラソン上位は取れるのでしょうか?

頭脳勝負なら勝てない方々に、頭脳だけの勝負じゃないから、マラソンで勝負になるわけです。
SRMが頭の回転の速さや知識量や練習量を競うものであるのに対して、マラソンは総合力で競います。
マネジメントスキルなどによって、頭の善し悪しを補って戦う事ができます。
また、SRMの様な単純な繰り返しトレーニングでは、レーティングが思う様に伸びないはずです。(たぶん)
ハッキリ言って、SRMは若い方が有利ですが、マラソンマッチは年老いても不利になりません。シニア向けの競技です。
こうした性質は、マラソンマッチの最大の魅力であると言えます。

本記事では、マラソンマッチに対してどのように取り組めば成果を出せるのかということについて、主に説明をしていきたいと思います。

また、この記事を読むことによって、社会人プログラマの方々が、「会社で身につけてきたノウハウと同じじゃないか。自分だってマラソンマッチで上位が狙えるんじゃないか?」という実感を持って頂けたら、嬉しく思います。

なお、本記事には、一部の技術的背景などについての説明不足が多々存在します。
私が今回論じたいのは取り組み方についてなので、その辺をご理解頂いた上で、分からない部分は調べつつ読んで頂けたらと思います。

マラソンのノウハウは、たった3つ

私が思うに、たった3つです。以下に挙げます。

1.問題をしっかり把握する
2.判断基準を明確にする
3.反復期間を短くする

あれ? なんか、会社でやってることと似てませんか?

1.問題をしっかり把握する

開発するときも、問題をしっかり把握することは重要ですよね。
最初にお客様相手にしっかりとヒアリングを行うと思います。
ヒアリングでつまずくと、その後の開発が台無しになりかねません。
何を解決すべきなのかを、しっかり要件として定義し、把握する必要があります。
ドメイン駆動設計では、ドメイン言語を用いて、システムの専門家もドメイン(問題)に対しての理解を深めていきますよね。

貴方が開発者ではなく、トラブルシューティング部隊に所属していたとしても、問題をしっかり把握することがどれだけ大切なことかについて、既に分かっていることと思います。
不具合の症状は何であるのか? その症状に対して、お客様はなぜ困っているのか?
バグの修正だけが本当に問題の解決であるのか? 何が満たされれば、問題の解決と定義できるのか?
不具合の再現する条件はなんだろうか? 正常に動いていた時は、今と何が違ったのか?
そんな感じで、資料を最初に集め、調査を進めていくことと思います。また、お客様に、何が満たされれば解決であるのかについて、訊ねることもあるでしょう。

これらは全て、問題に対しての理解を深める行為です。
マラソンでも、これが最初に要求されます。

もちろん、問題文は最初に読みます。でも、それだけを言っているわけではありません。
問題文を読んだだけの段階では、問題への理解は不完全なものです。
その不完全な理解を、少しずつ完全なものに近付けていく必要があります。
ここにどれだけの時間を費やせるかが、間違わずに正しい方針を選べるかにかかっています。
正しい方針は、正しい設計へと繋がっていき、下流工程の大幅な工数削減へと繋がります。
(ここをサボると、下流工程が増えて、2週間では上位を目指せなくなります)

ノウハウとして3つあげましたが、3つの中でも本項はダントツに分量が多いです。
それは、3つの中でダントツに本項の重要度が高いことを示しています。

それでは1つ1つ見て行きましょう。

問題をちゃんと読む

問題を読むだけでは不完全ですが、問題を読まなければ始まりません。
出題は英語です。マラソンマッチは2週間程度の期間が与えられていますので、丸1日を英文読みに費やしても、バチは当らないのではないかと思います。

英和翻訳サイトは、Yahoo翻訳やGoogle翻訳などがオススメです。
この2つは翻訳方式として全く異なるものを採用しているので、翻訳させる英文によって、得手不得手が分かれることも多いです。
片方でちゃんと翻訳されない場合は、もう片方も使ってみてはいかがでしょうか。

私の場合、マラソンマッチを始めたばかりの頃は、プライベートwikiに英語のマラソン文を貼付けて、それを1行1行、翻訳サイトを使いながらの半手動翻訳していき、wiki上に日本語の問題文が完成してから、マラソンを開始していました。英語が苦手だった私でも、だいたい半日ぐらいあれば、翻訳できていました。

テスタを読む

マラソンマッチでは、テスタのソースコードが公開されています。
試合によって、グラフィカルな表示を行うテスタが付属する場合があり、その時はテスタではなく、ビジュアライザと呼ばれます。
テスタであってもビジュアライザであっても、ソースコードは公開されていますから、ソースコードを必ず読む事をおすすめ致します。

テスタのソースコードに書かれている問題生成手順が、多くの場合、本番でも使われます。
「ランダムに生成」と書かれている部分であっても、ソースコードを読めば、ランダムの分布のニュアンスが分かる場合もあります。問題文から読み取れなかった部分であっても、ソースコードを読めば一目瞭然なことは多いのです。
問題文の英語の細かなニュアンスが分からない場合も、テスタのソースコードが解決に繋がることは多々あります。
テスタのソースコードを読むことで、問題の定義について、分からないことがなくなるのではないでしょうか。

(賞金ありコンテストの一部では、稀に問題生成手順が隠蔽されることがあります)

なお、探索問題の場合、問題入力と解出力のみから点数を計算する方法がテスタに埋め込まれている場合があります。
これをほぼそのまま流用することで、探索問題の評価関数は完成したも同然の場合が少なからずあります。
(実際には、MM70等、速度面を大幅に調整する必要がある場合もあります)

問題を理解するために回答プログラムを書く

問題をいかに解いて、より高得点を取るかということは、この段階ではあまり重要ではありません。
それよりも、出題された問題の傾向などを解析するプログラムを、回答プログラムとして作っていきます。

たとえばMM68(美しいクロスワード)ではクロスワードに使うことができる単語一覧が問題入力として与えられます。
これに対して、aで始まる単語がいくつあるか、bで始まる単語がいくつあるか、、、zで始まる単語がいくつあるか?
それから、aで終わる単語はいくつ? bで終わる単語はいくつ? と、それらを統計して表示するプログラムを書くなどしました。

問題の解としては、この段階では空っぽを返して良いのです。点数は重要ではありません。

そうそう、マラソンマッチでは標準出力はテスタとの通信を行うために使われるので、リポート出力には標準エラー出力を使うと良いかと思います。
もしくは、問題番号をどこかから抜く様にするなどしておいて、問題番号.txtや、問題番号.htmlのファイルを生成して、そこに書き込んでも良いでしょう。(問題番号を抜く方法については、後述します)

ビジュアライザの自作

付属のテスタがビジュアライザ機能を持っている場合であっても、ビジュアライザが不十分な場合が多々あります。
そういう場合に、ビジュアライザを自作するという方法が有効な場合があります。
といっても、そんなに時間が取れない場合も多いので、htmlリポート機能を付けたり、あるいは既存のビジュアライザに表示を付け足して使うという方法もあります。

実際、ビジュアライザはとても重要です。
問題文とテスタソースコードを全て読み終えて、問題の方程式が全て頭の中に入ったとしても、それらの方程式からなる問題空間がどういう形をしているのかについて、実感が湧く段階には、なかなか至ることができません。

付属のビジュアライザを通して実感を得手も、実感が充分かどうかは分かりません。
何より、他のライバル達は、同じ段階の実感を得ているのです。
同じ段階の実感を得ているもの同士が戦えば、より能力が高い方が勝ってしまいます。
それは、低い能力を補って戦うマラソンマッチ本来の戦い方ではありません。

能力が低くても有利に戦える第一歩目が、ビジュアライザの自作(もしくは改造)です。
何を表示すれば、問題空間に対しての理解がより深まるのか? それをよく考えることです。
そうして、ビジュアライザへと少しずつ表示を追加していきます。場合によっては、新しい表示項目のために、古くて理解し終えた表示を消すこともあるかと思います。

ビジュアライザへの表示の追加は、それ以降のあらゆる段階で行う可能性があります。
ビジュアライザに表示の追加を行うことで考えるための情報が増える場合は、迷わずそれを実行して、問題空間に対しての理解を少しずつでも確実に深めていってください。

なお、ビジュアライザ自作に関しては、私よりも診断人( @nico_shindannin )さんの方がより前衛的な取り組みをしています。
回答状況を効果的に表示するだけではなく、ビジュアライザ上で、回答の一部を修正したら点数がどのように変化するのかということを、逐次、GUI操作に合わせてシミュレートするプログラムです。
こういうプログラムを運用できれば、更に問題空間への理解は深まることでしょう。

2.判断基準を明確にする

会社では、上流工程が終わったら、下流の開発に入って行くことと思います。
ところで、マラソンマッチの進捗具合について、どのように評価しますか?
そもそも、マラソンマッチ全体の工数をどうやって見積もりますか?

マラソンマッチでは、期間が定められています。
その期間に間に合わなかった分については、間に合わなかった成果物が最終評価となります。

どうせ時間の全てをマラソンに費やすのだから、工数なんて見積もるだけ無駄無駄?
果たして本当にそうでしょうか?
それでは闇の中でがむしゃらに走っているのと同じではないですか?
典型的なデスマーチなのではないでしょうか?

本項では、AとBの2つの実装がある場合に、どちらがより優れた方法であるのかということを、明確に比較する方法について述べます。
その延長線上として、何位を目指すためにはどのぐらいの工数がかかるのかということについて、大雑把な見積もりを立てる指針を示します。

もしかしたら初期段階では、1位を目指すための工数は見積もれないかもしれません。
それでも多くの場合、この工数の作業をすれば、どのぐらいの順位になるのかの予測が立つことがほとんどです。
その方式の延長線上の方法で、目標順位に届くのか?
届かないのだとすると、根本的な考え方を改めなければならないのだろうか?
そういうことを考える指針になればと思います。

貴方が開発者ではなく、トラブルシューティング部隊に所属していたとすると、本項で行っていることにより近いものを経験済みかもしれません。

問題が起こっているサーバー上などに計測プログラムを導入することがあるのではないでしょうか?
計測プログラムを導入する目的はなんでしょうか?
1つ目は、サーバーで何が起きているのかを調べるためですよね。このこと自体は問題の把握につながります。
しかし計測プログラムの導入は、問題がどの程度解決に近くなったかを数値的に把握するための基準の構築でもあるのではないでしょうか?
その部分が、本項で目指す所に近いものがあります。

テスト環境の構築

付属のテスタをボタン1つで実行可能な環境を構築しましょう。
たいてい、バッチを組むことになると思います。

調査段階では、テストケースは4つぐらいしか使わない、という場合も多いです。
それは、1つ1つのテストケースの問題を解くプロセスを追って行く必要があるからです。

中盤以降では、TopCoderサーバーでの暫定スコアが気になる様になります。
実は、TopCoderサーバーの暫定スコアを基準に解法の改善を行ってはいけません。
暫定スコアで使用される問題と本番で使用される問題は、イコールではないからです。

何らかのテストケースで評価し、その評価に基づいて解法を改善していく時、用いたテストケースに対しての過剰最適化が発生します。
それは、本番評価に対する改悪である場合が多く発生し得ます。

過剰最適化は、テストケース数を増やすことで緩和することが可能です。

さて、多くの場合に、暫定スコアは100問程度で算出されます。
そして本番スコアは1000問程度で算出されます。
(試合によって違うことがあるので、よく確認して下さい)

指数的な中間地点である300問ぐらいが、ローカル環境での評価に用いたいテストケース数の目安となります。
もちろん、3000問ぐらいのテストケースが使えたなら、それに越した事はありません。

1万問のテストケースを使うのは、ちょっとやり過ぎかなぁという印象です。

なお、CPUが4コア(ハイパースレッディングなし)の場合、テストを同時に動かすプロセス数は3つ程度に留めましょう。(スレッドの連続実行の安定性を保つためです)
また、予め本番環境のCPU性能を確かめておいて、テスト環境ではそれに合わせて制限時間を調整すべきです。(たとえばうちのPCの場合、本番環境の2倍以上の性能が出ている様なので、ローカルテスト環境では制限時間に0.4をかけて実行しています)

部分問題の基準構築

1万問のテストケースはやり過ぎだと書きましたが、そうではない場合があります。

問題のパラメータ範囲によって、問題空間の性質が大きくことなる場合が存在します。
たとえばMM71(上質な多角形)では、空間中の点の数が50から5000となっていました。
点の数が50の場合と5000の場合とでは、用いることのできる解法に差が生じます。

もしもこの問題が50〜5000までの均等分布であったなら、50〜500付近のテストケースは割合的に1割しかないので、ほとんど無視できたでしょう。
しかしMM71では、50〜500の割合と500〜5000の割合が等しくなるように問題生成されることが問題文に明記されていましたので、両方の対応を行う必要が生じました。

こういう場合、解くアルゴリズムを別々に用意することもあります。

こうして独立するアルゴリズムを別々に用いる場合、それぞれの評価も独立して行われるべきです。

では、テストケース数は、どうすれば良いのでしょうか?
全体テストケース数が300のとき、部分問題のテストケース数は半分の150でしょうか?

では、100個の部分問題に分けることができた場合、各部分問題のテストケース数は3つずつになるのでしょうか?

ここでもまた、過剰最適化の問題が発生することになります。
過剰最適化を回避するためには、部分問題でもそれなりのテストケース数を用意する必要があります。

私はMM69 ( TCO11 Round 1) において、問題空間を27個に分割しました。
同一のアルゴリズムを用いますが、各々に違う初期パラメータを与えることを決定しました。

このとき、各部分問題空間において、300個ずつのテストケースを使いました。
すなわち、8100のテストケースを用いました。
アルゴリズム調整の段階で用いたテストケース400個と、部分問題に対するテストケースには重複がないので、計8500個のテストケースを導入したことになります。
走らせた総テスト回数は、60万回を超えました。

点数モデルの脳内構築

貴方の解は、次の改良を加えたときに、どの程度の点数がアップし、順位的にはどの辺になりますか?
この問いかけに、可能な限り明確な答えを用意できる様にしましょう。

初参加で2位を取ったMM68でも、2度目の参加で1位を取ったMM69(TCO11 Round 1)でも、私は最初の本格的なサブミットを行う前の時点で、かなり上の方の順位を取れることが分かっていました。

パターンとしては3つあります。
1つ目は、本番環境では制限時間内に収まらない解法を、ローカルテスト環境で評価した結果として、何点を獲得可能なのか事前に分かっている状態で高速化を検討している時。
2つ目は、問題に書かれた得点算出式から、どういう解を提出すれば、全体の何割程度の点数が取れるのかが、明白である場合。
3つ目は、何度か重ねた改良結果の点数の上昇具合から、今回の改良がどの程度の点数を上昇させるかの予測が勘で分かる場合。(多くの場合、「これでは足りない!」と予測される改良を、改良候補から除外するのに便利です。この辺については、反復の項でも説明します)

3.反復期間を短くする

前述までの内容で、「どう解くのかをどういう手順で考えれば良いか?」「それを解いた時にどのぐらいの順位になるのかをどう見積もるのか?」について、分かるようになったことと思います。
(前項まででも、具体的なアルゴリズムについては一切述べてないので、そこは各自で勉強してくださいね)

最後に、それらを踏まえてどのように反復を繰り返していくのかについて述べます。

周辺技術の調査

問題空間への理解が深まって来たら、その解法について、自然と思い浮かぶのではないでしょうか?
その解法は、時間内に計算が終わりそうですか?

ぶっちゃけ、ギリギリのラインについては、やってみなきゃ分からない所も多いです。
しかし、明らかに時間内に処理が終了しない解法は、しっかりと把握しておくべきかと思います。

多くの場合にアルゴリズムの計算量(オーダー)の話になることが多いです。
最悪の計算量は無視して、平均の計算量で判断した方が良いかと思います。
(最悪の計算量は、少し工夫を加えることで、平均の計算量と同一にできる場合が多々ある様です)

ネットを検索したり、関連の書籍を図書館から借りて来るなどして、先人の知恵を借りつつ、試合内容に合う様に使うにはどうすれば良いかを考えましょう。(その過程で勉強することは、次回やその更に先のマラソンマッチでも役に立つはずです)

なお、定番探索で解ける問題も数多く存在します。

定番の探索法については、他の人の記事を探してみてください。

プロトタイピング

ようやく実装に入ります。
試合期間は2週間ですが、だいたい1回の反復は4時間以内に収まることを目標にすべきです。

新しい案を試したら、どのぐらいの順位が狙えるのか?
前述の点数予測だけでは細かく分からない場合に実施するのが、プロトタイピングです。

与えられた時間は4時間程度と仮定しましょう。
4時間で、そのプログラムの点数算出に最も関連する部分だけを実装するのです。
できませんか?

できなかったら、もっと実装案を簡略化してください。
大枠の点数の方向性が失われない範囲で実装案を簡略化していきます。
プロトタイピング段階では、処理時間は別に100倍ぐらいは普通にかかっても良いものとします。
本番環境で反復をしなくても良いのです。そのために、ローカルにテスト環境を構築しているのですから。
あるいは、部分問題についてのみの解法であっても構いません。
(点の数が50〜500なら時間内に計算可能。しかし点の数が5000になると一生待っても結果が出ない……とかであっても構いません)

そういう風に、条件を緩和することで、視野の外だった解法が視野の内側に入ってくることが多々あります。
それらの中で、将来性が高そうなものから順に、実装してみましょう。

なお、プロトタイピングではあまり速度にこだわった実装は行わなくて構いません。
後述の高速化の手順を実施する際に、オーダーミスは必ず浮き彫りになって改善することになります。
また、定数倍的な遅いコードも、高速化の後半で改善することになるので、あまり神経質にならなくて良いのです。

解法の構成

解法って、1アイデアで解けるものでしょうか?
実は、色々な解法を試すにしても、どの解法を使っても基本構成は同じだよね……というパターンになることが多々あります。

それらは早い段階で意識しておきましょう。

構成が固まれば、プログラム全体の差し替えではなく、一部分の差し替えで色々な解法を試すことができる様になります。

寄せて行くノウハウ

さて、上位は狙えそうでしょうか?
簡単に狙えそうにない間は、プロトタイピングを延々繰り返していくことになります。

狙えそうになってきたら、本当に狙えそうかどうかをきちんと評価して、これで勝てると思ったら、後は寄せていくだけです。

寄せは2種類あります。

速度面の寄せと、精度面の寄せです。

速度面の寄せとは、制限時間をオーバーしてしまうけど、そこから予測される順位に満足している場合に行う高速化です。
高速化については付録の別項を設けましたので、そちらを参考にして下さい。

単純な高速化では、とても制限時間内に収まらなさそうな場合は、精度と速度のトレードオフを実施するためのプロトタイピングを行って下さい。

精度面の寄せの場合、大筋では今の解法で良いけど、もうちょっと点数を伸ばしたいという感じでしょうか。
解法の改良については、前述のプロトタイピングでなんとかしてください。
局所解に陥らない様にする様な工夫の多くは追加計算時間を要しますので、プロトタイピングを試した後に、速度面の寄せに入るパターンは良く在ります。

初期パラメータの最適化については、問題空間の分割と、部分問題のテスト環境構築を参考にして下さい。

以上で、マラソンマッチで直面するあらゆる状況に対しての、考え方の指針を網羅できたのではないかと思います。
あとは付録なども参考にしつつ頑張って下さい。

付録 テクニック的なこと

高速化について

ここで取り上げる「高速化」というのは、改良前後のプログラムの結果が完全に一致するものを指します。

貴方のプログラムは、どこを改良すれば、速くなりますか?
試行錯誤してみますか?
よく考えて改良したつもりでも、全然処理時間が縮まらないことはないでしょうか?

まずは、そんなあいまいな方法で高速化に取り組むこと自体が間違いであることを知って下さい。
貴方が高速化しようとしている部分は、1テストケース辺り、0.001秒しかかかっていない箇所かもしれない。
そんな場所をいくら高速化しても、無駄です。

プロファイラを使いましょう。
入手方法や使い方等は、ネットで調べて下さい。

プロファイラを使えば、必ず、その時に最も処理時間がかかっている処理にぶち当ります。
処理に時間がかかっている箇所というのは集中しているもので、それが最頻ループの最下層にあたることが経験的に分かっています。
最頻ループのオーダーを下げる方法を考えて行くことになるでしょう。

序盤は、そういうオーダーミスを直したり、分岐を減らすパターンが多いと思います。
中盤は、コンテナの使い方とメモリの確保と解放を減らしていくことになると思います。
後半になってようやく、割り算を掛け算になおしたり、平方根演算の除去を行ったりすることになります。

ローカルテスト実行時に追加情報を与える

テスト実行時に、解法プログラムに対して、問題番号や問題生成時に使ったパラメータ等を渡す様にします。
バッチで指定したり、あるいはテスタのコードを書き換えることで、これらは可能になります。

問題番号はリポートファイルのファイル名に使うことができます。
問題生成時のパラメータは、問題解決に役立つかもしれません。あるいはリポートへの埋め込みとか。
問題生成時のパラメータは本番時には用いることができませんが、問題空間の解析等を行っている段階では、それらが有用なことが多々あります。

それから……制限時間に関して、本番環境とテスト環境とでプログラムをいじるのは、間違いの元になります。
そこで、制限時間はグローバル変数などで定義しておいて、ローカル環境ではmain関数(プログラムのエントリポイント)付近で、グローバル変数を書き換える様な方法があります。

また、C++等では条件コンパイルを用いる方法もあります。

枝刈りを観測的に行う方法

探索を行っていると、処理時間がかなりオーバーしてしまうことが多々あります。
そういう時に、枝刈りが効果的な場合があります。
枝刈りで精度が落ちることはありますが、それでも速度が大幅に改善されて上位が狙えることもあります。

ところで、精度にほとんど影響を与えない枝刈りって、どうやれば良いんでしょうか?
わりと万能な方法というのは、ネット上を探せばいくらか見つかるかもしれません。

しかしマラソンマッチの場合、問題空間はもう決まっているのですから、その問題空間でだけ使える様な枝刈りを行っても良いはずです。
それを見つけるための、そこそこ万能的な手順があります。

葉ノードまで探索した際に、使い物にならない解だった原因は何でしょうか?
それを、葉ノードで使い物にならない解が分かった時点で、調べます。
(使い物にならない解の定義は、現在の最適解と比べて大幅に劣るもの……などとします)

原因をいくつかの種類に大別しておき、それぞれに対応したカウンタを1つ進める様にします。

複数の要因が重なっている場合は、それら複数要因が重なった場合だけに増やすカウンタを用意し、その条件が当てはまる時には他の個別の要因のカウンタは増やさないことにします。

なお、これらのカウンタは、使い物になる解の場合のカウンタも、同様に用意しておきます。

とても時間のかかる探査を行ったプログラムは、最後に、各カウンタの値を出力します。
何が要因で、使い物にならない解が探索されやすいかが、これで分かるのではないでしょうか?

また、探索時に各ノードは親ノードに対して、使い物になる解が1つでもあったのか否かを報告する様にします。
すると、葉ノードではなく中間ノードでも、上記の計測が可能になります。

そうやって得られた情報を元にして、枝刈り条件を考えてみてはいかがでしょうか?

より複雑な点数モデル

MM71では、各テストケースの点数そのものではなく、各テストケースごとの全体順位の位置が、暫定スコア及び本番スコアでの点数として採用されました。(そのテストケースで1位なら1点、最下位なら0点、真ん中なら0.5点、のような感じです)
MM70及びMM72では、各テストケースごとの全体の最高点を基準としてスケーリングされた点数が、暫定スコア及び本番スコアでの点数として採用されました。(MM70の方は少し特殊なゲーム展開になりましたので、以降、MM72方式と表記します)
MM74では、全体の最高点を基準としてスケーリングされた後に4乗された点数が、暫定スコア及び本番スコアでの点数として採用されました。

MM71方式はちょっと複雑で、初期から参加してこまめに周囲の動向を確認できていなければ、脳内点数モデルを構築するのは難しいです。
かく言う私も、MM71の時は点数予測を大きく見誤りました。

と言っても、各参加者の過去の点数が、現在の分布基準で算出されたものではないということに気付けなかったのが大きな敗因です。
複雑な点数モデルでは、最新の回答は、常に最新の状況によって更新され続けます。
各参加者の過去の点数が、現在の状況によって更新されるものなのか、そうでないのかは、確認しておくべきかと思います。

さて、ちゃんと前提条件が把握できていたとすると、MM71の方式であっても点数予測を行うことは可能です。
私の知る方法としては、現段階の自分の最良解と0点解の提出の比較を行う方法や、部分問題ごとの分割送信での比較などがあげられます。
順位に依存して点数が決まるということは、こちらの回答がAからBへと切り替わった時に、回答Aと回答Bの中間に位置する回答を行っている人達の点数は変動します。
これを利用します。

最適解と0点解を切り替えても、点数の変動が起こらない方々……その方々は、雲の上の人達なので、測定不能です。
点数の変動が起こる方々は、テストケースによっては、こちらの方が上回っているということになります。
全体の競技者人数から、1人の順位の前後が入れ替わった場合に、何点が変動するかは、容易に計算可能です。
その変動が何割のテストケースに対して起こったのかを、各参加者ごとの点数変動から推論することが可能です。

次に、この調査に部分問題解を使うことで、上記をより細かく調査することが可能になります。
特定の部分問題ではちゃんと回答し、それ以外では0点の回答をするプログラムを送ります。
このとき、部分問題に該当するものが、全体の何割程度であるのか、問題生成の分布から計算可能である必要性があります。

それで、自分の部分問題ごとのおおよその順位を知る事ができる様になります。
どの部分問題を改良することで、全体の順位が上がり易いのかが、分かる様になります。

MM72方式及びMM74方式では、テストケースごとの順位制ではないので、少し状況が変わってきます。
点数の切り換えで点数の変動を見るのは、自分だけが最高得点を取っているテストケースが存在する場合にしか使えません。
しかし、部分問題提出法は、依然として有効です。

MM71よりも点数算出方法が明快なので、この辺は自分で考えながらやってください。

なお、MM74方式ではMM72方式に対して4乗の計算が加わります。
これがどういうことかというと、最適解の70%しか取れていない解は、25%程度の点数しか取れないということになります。

つまり、全ての各テストケースで70%ずつを取ると、総計結果としては25%になります。
ところが、半分のテストケースで100%の点数を取り、残りの半分のテストケースで0%を取ると、総計結果としては50%になるのです。
こうした問題では、部分問題ごとに確実に100%近い点数を目指す方が有効な場合もあります。
また、試合の途中段階において、一度、部分問題解を提出しておいて、自分の回答はどの部分問題解が得意で、どの部分問題解は不得意なのかということを、調べておくのが望ましいでしょう。

なお、マラソンマッチでは、1度サブミットすると2時間待たなければ次のサブミットができません。
現に、こういう方法があることを事前に知っている私は、MM74の問題文を読んだのが試合終了2日半前だったため、上記方法を試す事ができず、部分問題の得手不得手を測り間違えて、最後の5時間ぐらいを迷走してしまいました。
(部分問題が2つに分けられる場合、3回のサブミットが必要なので、6時間……更に最終サブミットが必要なので、試合終了8時間前の時点では既に使えない手段になってしまっています)

時間に余裕を持って、自分の現在位置を把握する様にしましょう。

最後に

書きたいことは山ほどあって、それらをがむしゃらに書いた所、こんな長くて締まりのない内容になってしまいました。

本内容は、主に、社会人がエンジニアとして働く上で、自然と身に付いているだろう事柄に対して、焦点を当てて書きました。

従って、社会人プログラマの皆さんに対して、「ほら貴方も、上位が狙えるんじゃない?」ということを全面に押し出しては書きましたが、逆に社会人の方々にとっては当たり前すぎる内容しか書けていないかもしれません。

逆に、あまり対象としたつもりのない学生の競技プログラマの方々に対して、重要なヒントを提供している内容になっているかもしれません。

今の競技プログラマ人口は、学生の方が圧倒的に多く、社会人人口は少なめだと感じています。
実際、社会人になった後にSRMに入門しても、あまり高い成果は望めないのではないかと感じている面もあります。
しかし、プログラミングを競うというのは、面白いものがあります。
実際にはプログラミング自体ではなく、数学的な考え方やマネジメントスキルが大半を占めますが、それでも競争社会というものが私は大好きです。

SRMは社会人向けではないかもしれません。
しかし、マラソンマッチは社会人にとても向いている競技だと感じています。

社会人の競技プログラミングが、もっと市民権を得ることを、切に願っております。 server Longregbiguates .

カテゴリー: 未分類

iPhoneサイトについて

iPhoneサイトって、iPhoneのブラウザに、そういうサイトを作る仕組みがあるのだとばかり思っていましたが、少し違う様ですね。

汎用的なHTML, CSS, JavaScriptと、ほんのちょっとのWebKit拡張を使って、iPhoneっぽい見た目のサイトを作っているだけの様です。
WebKit拡張って言ってるのは、背景を単色塗りつぶしじゃなくグラデーションつけたり、、、とか、そういう機能なので、基本的にはiPhoneサイトは、iPhoneっぽい見た目と操作性を模しているだけのサイトということの様です。 dom information Kerotordiawork

カテゴリー: 未分類

flashのソケットポリシーファイル

http://gimite.net/pukiwiki/index.php?Flash%A4%CE%A5%BD%A5%B1%A5%C3%A5%C8%A5%DD%A5%EA%A5%B7%A1%BC%A5%D5%A5%A1%A5%A4%A5%EB

ここを参考に、設置を行った。
ところが、xinetdでの設置の際に、つまった箇所があったので、メモしておく。

xinetdで設置はできているはずなのに、なぜかつなげなかったのである。

/etc/hosts.allow が原因だった。

in.flashpolicyd.pl: ALL

みたいな行を追加して、まともに動く様になった。

# 入れたのは下記のページからダウンロードできるperl版です。
http://www.adobe.com/jp/devnet/flashplayer/articles/socket_policy_files.html
# エラー出力もソケット出力に流れてしまう様だったので、エラー出力へのガイド出力はコメントアウトして使ってます。 Comprifeedphafour .

カテゴリー: 未分類