TCO17 Marathon Round 1 (GraphDrawing) の反省

問題と1位の方（chokudaiさん）の解法

TCO2017R1

結果

• 力学モデル（バネ）で、長さ比に応じて力を加える。その後、貪欲法（一番悪い辺の点を、最も高得点になる場所へ移動）で解を改善。
• 45位/146位 652,515.28点。30位ぐらいの人ともかなりの点差が開いていて、敗北感ある…。

敗北までの流れ

ファーストインプレッション

• 方針
  • 力学モデル
  • 焼きなまし
  • よさげな頂点同士をマージしながら構築

• 問題の穴
  • 木の足の部分はどうでもよい。
  • 距離が近くになる点どうしは、まとめて動かしてもいいかも。
  • 三角形などサイクルの形で、辺が絶対につながらず満点が取れないケースもあるので、こういうケースでは理論上最高得点を求めて、最高得点にあわせて、目標長さの条件も緩めたほうがいいのでは。
  • MAX_RATIO / MIN_RATIOなのに注意。全部言われた長さにせよとは言ってない。全部スケールしても得点は変わらない？
  • 三角形って何個あるんでしょう。位置関係が確定する気がする。
  • 長さが整数値になることを使ったHackはなさそう。

ざっくり焼きなまし

• 近傍
  • ランダム移動、だんだん移動量を少なく
• 評価値
  • 最小値だと、差分を使いづらく、雑に書くとO(E)、良くてO(logE)ぐらいな気がしたので、とりあえず重み付きの和で対応

Submission 2 得点 248563.14
上位の得点が、70万点近くなので、恐らくハズレ方針だと思い、あきらめる。

力学モデル（バネ）

メモ

• 微分せよ。
• ズレ0のやつで、位置があうか比較する。
• インラインアセンブラがききやすい
• 論文（良い初期位置とか）
• Logをつけてみては？
• 引っ張る力を比ベース
• たぶんランダムな力とかは筋がわるそう。

試したこと

• 普通のバネで引っ張る
  • バネモデル、意外とバネ定数により、発散しやすい。
  • 枠外でも力を加えて、枠に入れたほうが高得点になる。
  • 今回は目標の長さとの比が得点にかかわるので、長さ比に比例した力を加える（普通のバネは差に比例した力を加えるので、）
  • バネの力により簡単に発散するので、バネ定数の調整と、pow()をつけた調整を試す。
    • powやlogを付けた調整は発散しやすかった。
  • 距離の短い辺が、強い力でずっと動き続けて足をひっぱる。
• 序盤は遊びを入れて、自由に動けるようにする。目標得点を0からスタートし、目標票得点内に収まるのであれば力は加えない。そして徐々に目標得点を増やしていく（拘束も強まる）
  • →これは極値にハマる可能性を大幅に減らせる有力な方針だと思ったけど、そうでもなかった。結局同じような場所でハマる。
• エネルギー最小化
  • https://cs.brown.edu/~rt/gdhandbook/chapters/force-directed.pdf のKamada and Kawaiのアルゴリズム。
  • バネエネルギーは積分すればいいので、

差ベース
// energy = integrate k*(x-a) dx from x=a to b ====> k * (a-b)^2 / 2

比ベース
// energy = integrate k*(x/a-1) dx from x=a to b ====> k * (a-b)^2 / (2*a)
// energy = integrate k*(a/x-1) dx from x=b to a ====> k * (a * log(a/b) + (b-a) )

• • 本当だったら、高速化のためKamada and Kawai多変数のニュートン法で = 0系の連立方程式を解くのだけど、まずは遅くてもいいので、エネルギー最小になる点を全探索で試すことにした。バネより結果が悪いのであきらめる。
• このタイミングでビジュアライザも作成。正しくは動いているっぽい。
• ズレなしで満点を取れるテストケースを試す
  • それでも満点がとれない。
  • どうやら初期位置が悪いと簡単なケースでは、ダメなことが分かる。
  • 逆にチートして、初期位置を知っているものとしてやると、バネでも高得点が取れる。
• 簡単なわりには低得点になるケースを探す
  • 変な三角形とか、田んぼの田とか、いろいろと手作業でいろいろと作るも見つからず。

Submission 3 得点 475556.16

恐らくバネ方針も良くないのだと思い、あきらめる。

強引な貪欲法

もう一番得点が低い辺の頂点の片方を、700*700の移動先を全部試して一番良いところに移動させる。というか、なぜこれを最初に試さない。

• 高速化する。得点ハイトマップを作成して、関数形を見る限り、そんなに山の数が多いかんじではないので、焼きなましで探していいのでは？（ドーナツを重ねてくり）

• • 250回ぐらいの焼きなましループで、最適解（=700*700）を90%ぐらいの正解率
• 得点は伸びたが、上位の70万点には程遠い。
• 貪欲→バネ→貪欲→バネを繰り返せば、極大値にハマらないのではないか？
  • ハマる

Submission 4 得点 606403.67

焼きなまし

貪欲でいいのなら、焼きなましもやっぱり行けるでしょうと思い、焼きなましの戻る

メモ

評価値

• 最小値（問題のスコアと一緒）
• 足し算
• 重み付き足し算（ペナルティはV倍とかにしないとダメ）
• 分散

近傍

• 頂点どうしの位置交換
• 悪い頂点のとなり
• 辺対称
• 大ランダム移動（たぶん大きい移動が入った時点で負け）・小近傍移動
• 速度つき近傍（慣性）
• 粗いグリッド⇒細かいグリッド

実際にやったこと

評価値

• 最小値
• 足し算
• 重み付き足し算（に比が1から離れていれば離れるほど、さらに悪くなる）
• 分散
  • O(1)で計算できるし、２番目に悪い点、３番目に悪い点も実質考慮できるので、よいかなと思ったけど、だめだった。

近傍

• 粗いグリッドに分けて、ざっくりした位置を決めたのち、徐々に細かいグリッドにしていく。2*2→4*4→8*8→…
  • 32*32を最高にスコアが落ち始めるので、あきらめる。←これはもったいなかった。32以降は別方針にするとか、2段階の解法で高得点いけた

Submission 2と同レベルの得点しかとれないので、やめる。

Beam search系

迷走する。書くほどでもないか…

反省点

部分最適（極値にハマる）理由を考察するのを第一に考える。

シンプルで統一的な解法にこだわりがち。

• シンプルで統一的な解法でないと高得点が取れないと、その後複雑な解法にした際も、最終的には点が伸ばせないと考える癖がある気がする。
• それ自体はいいのだけど、どうもシンプルな解法をいろいろ試すものの、それぞれの解法への考察が雑になり、点が伸ばせる解法を、謝って枝刈りしてしまっている気がする。
• 悪いところを考察したうえであれば、例外的な対処も入れて良い。部分的対応をどんどん入れていってよい。
  • 力学解法でも、焼きなましでも、高得点は取れてたっぽい。
  • 悪そうな解法でも、部分的にでも良いところを探すようにする。
  • ちゃんとした物理に従う必要はないですよ。
    • バネモデルで、たまにワープさせたって構わない
    • バネモデルで、全部のやつに同時に力を加えなくたって構わない。（一番悪いやつだけとか）

評価関数を状況に応じて変える

（分かってるつもりなのですが…）

• 例えば、焼きなましのグリッド解法は、高得点を取ってる人はいるので、良い方針だったはずなのだけど、2*2のときも、700*700のときも、似たような評価関数を使っているのは、大変良くない。
• そもそも、段階ごとの目的に意識がいってない気がする。粗いグリッドのときは、「正しいセルに振り分ける」のが目的、細かいグリッドのときは「高得点取れるようにする」なのに、評価関数が1つというのは良くない。それぞれの段階での目的をはっきりさせて、評価関数をつくろう。
• これは焼きなましに限らない。Beam Searchの前半と後半で評価値を変えたりもするし、目的ベースで、柔軟にかえる

頭の悪さは、ビジュアライザとランダムテストで補おう

• 極値にハマる、単純なケースを、自分でテストケースを作るものの、見つけられなかった。
  • ランダムで単純なテストケースを大量に作って、試せばいいだけ
  • せっかくビジュアライザもあるんだから、考察も簡単にできるのだし

スコアに大きな影響を与えるものを、必ずしもアルゴリズムの最初に確定する必要はない。

• 今回は短い辺が、低得点の原因になるけど、その場所を先に確定させると高得点にはならない。
• 短い辺は確かにボトルネックになるけど、アルゴリズムの後半でGreedyとかやれば必ず治せる。
• 似たようなテクニックとして、「後で決めても辻褄が合っていればよい。(Peg Jumpingとか)」というのもある。

このブログは、マラソン開催中に非公開で書くべし

• 絶対にマラソン中に書いたほうが効率がよい。
• 他の人の解答をまだあまり検討していない⇒復習としては最悪！

ビームスタックサーチについての勉強メモ

マラソンマッチ界隈でよく知られている通称chokudaiサーチ、それと似ていると言われてるビームスタックサーチ(beam-stack search)について、ちょっと調べてみました。論文はこちらです。
R Zhou, EA Hansen (2005) Beam-Stack Search: Integrating Backtracking with Beam Search, 15th International Conference on Automated Planning and Scheduling

でも、いまだ分からないところも多いので、まとめました。誤解してそうなので、間違いを指摘してもらえると助かります！論文と照らし合わせながら読んでもらえると良いと思います。

この記事を読むのには以下の知識が必要です。

• ビームサーチ
• 全探索（深さ優先探索など）
• A*アルゴリズム等で出てくる、ヒューリスティック関数の意味

ビームスタックサーチの概要

前提

• 許容的なヒューリスティック関数、つまり、最小値を求めるときは、現在の状態～未来で取りうるコストの下限が必要。最大値を求めるときは上限。（Admissible heuristics)
• 最適解を求めるのが目的。枝刈りは行われるが、基本は全部のパスを通ろうとするので、最適解があれば、必ず見つけられる。(Completeness)

特殊なケース

• ビーム幅が十分に大きいときは、分枝限定法-幅優先探索と同じ。バックトラッキングは行われない。
• ビーム幅が1のときは、分枝限定法-深さ優先探索と同じ。（ちなみに、ビームサーチだと、ビーム幅1は貪欲法と同じ。）

疑似コード

上記の論文に載っているビームスタックサーチの疑似コードの引用である。24～28行目の変数relayの部分は、拡張バージョンdivide and conquer beam-stack searchの部分なので、今回は無視する。

ビームスタックサーチの流れ

ビーム幅2で、ビームスタックサーチを使って、最小値を求める場合を考える。（注意：まだ不明な点があるので、グラフをわざと簡単な木にしてます）

各ノードnを状態とし、それぞれのノード内の数字は評価値を表す（f-costと呼ぶ。ノード番号では無い！）。評価関数f(n) は
f(n) = g(n) + h(n)

• g(n)は、スタートノードからノードnまでのコスト
• h(n)は、許容的なヒューリスティック関数、ノードnからゴールノードまでのコストの下限（絶対に過大評価しない値）

スタートノード（f-costが0）から、最小値を求めていく。

Layerごとに、

• f-costでソートする。
• fmin・fmaxという範囲を示すペアの値を持つ。初期値は fmin=0, fmax=U。(Uは現在までの最適解。Uの初期値は+∞で良い)。

fmin・fmaxのペアをレイヤーの小さい順からスタックにpushしていったものを、ビームスタック(beam stack)と呼ぶ。

スタートノードから、ビームサーチをしていく（8行目）。注意点は、f-costが[fmin,fmax)に入るノードだけを探索するところ21行目?。ビーム幅が2なので、上位2つ（低いコスト）しか入れない。ビーム幅から漏れたノードの評価値が新たにfmaxとなる（3行目）。つまり範囲が狭まる。

ゴールノードにたどりついたので、最小値を更新し、U=6となる。もし、fmax>Uとなった場合は、そのLayerはEmpty Layerとなる。Empty Layerが、ビームスタックのtopに来たら除去される。つまり深いLayerから探索から外れていく（46～48行目）。

（ここが全く分かってない可能性あり！）最深層までたどり着いたら、最深層のfminとfmaxが更新される。fminが今までのfmax、fmaxがUになる（50～51行目）。

ここはfmaxはそのまま。評価値5のノードは辿っておらず、ビーム幅2からあぶれたわけではない。

深さ優先探索順に新しい訪問先を辿っていく

別のゴールノードにたどり着いたので、最小値を更新し、U=5となる。常に後で見つかった解のほうが、良い最適解になるのに注意する(44～45行目)。これでビームスタックが空になったので、終了（49行目）。

私見と疑問点

アルゴリズムの観点から

• 疑似コードで、どうやってバックトラッキング（深さ優先探索）を実行しているのか？
  • 普通は深さ優先探索をするには、再帰にするか、stackにpush・popをするか、どちらかだけど、8～37行目を見る限り、popはしていないし、再帰呼び出しもない。
  • 関数searchは毎回スタートから行われているので、新たに訪問するノードの順が、深さ優先探索順になるだけかもしれない。
    • ただ、そうだとすると、毎回スタートから同じノードを何度もたどり、計算量がひどいことになりそうな…。
• 以下の例は大丈夫なのか？f-cost3のノードを訪問する前に、f-cost4と5のノードを訪問するので、fmaxが6になり(3行目)、その後すぐfminが6になるので、f-cost3のノードを訪れずに終わってしまいそう。

• wikipediaでビームサーチを見たら、そこでもヒューリスティック関数の例がでていたし、先行する論文のいくつかもそうだった。もしかして、それが普通？
• ビームスタックサーチを分枝限定法（branch and bound）と呼ぶのは大げさな感じが…。ただの枝刈りでは…。でも、英語版wikipedia見ると、ヒューリスティック関数で枝刈りするだけでも、そう呼べるみたい。

マラソンマッチの観点から

• 許容的なヒューリスティック関数が必要だとすると、使用箇所は限定されそう。
  • 最短距離のようにコストが増えていくだけなら、許容的なヒューリスティック関数を常に0とみなしても、よさげですが。自由に値をとりうる評価関数だと、枝刈りが行われず、ビームスタックサーチは、ただの探索になってしまいます。
• マラソンマッチの探索上手な人だと、そもそも、幅優先だか深さ優先だか最良優先だかあまり区別のつかないような、自由な探索を書く人も多く、まさにビームスタックサーチは、その中に含まれそう。
• ビームスタックサーチとほぼ同じと言われてたchokudaiサーチとは、アルゴリズムも目的も全然違うっぽい。

Kaggle体験記（TopCoder機械学習マラソンとの違いなど）

tanzakuさん、今年もありがとうございます！ Competitive Programming （その2） Advent Calendar 2016 - Adventarの25日目！

はじめに

Kaggle（https://www.kaggle.com/）も、TopCoder機械学習マラソン（TopCoder）も、広義の競技プログラミング！ ということで、今回Kaggleに軽めに参加してみました。これらの違いについて取りあげようと思います。機械学習そのものについては取り上げてません。あしからず。

Kaggleの特徴（TopCoderと異なる点）

予測データのみを提出すれば良い。

• TopCoderは、マッチにより、予測する実行コードを提出する形式か、予測したデータを提出する形式か違ってきますが、Kaggleは、ほぼ予測データのみ提出です（例外はある）。そういうわけで、ライブラリや計算資源を好きなだけ使えます。

参加しやすい

• ページのレイアウトが分かりやすく、いたれりつくせりで、TopCoderのように管理がされなくなったりということもなさげで（過去問が動かないとか）、全体的に、ちゃんとしてます。
• とりあえず提出できるサンプルデータも用意されてるので、最初の１歩は踏み出しやすいです。
• 運営の方から、「新たな検索機能を追加したので、感想をきかせてね」といった連絡がリアルタイムで送られてきて、驚きました。積極的に改善しようという姿勢がうかがえます。

マッチの開催中でも、フォーラム内でなら、解法を議論してよい。

• 解法そのものについて直接言及しているのもあります（こうすると、何点までは行けるとか）
• データのビジュアライズなど、面倒そうなことをやってくれてる親切な人もいます。
• ただ、上位の人は、下位の人向けへのヒントをとどめて、本当に上位にいけそうなアイディアを公開するのは控えているようです。

マッチの開催中でも、コードを公開することができる。

• 後から始めたほうが情報が入る分有利で、公平でないとか、そういう議論もあるようです。
  • そんな人はTopCoder。TopCoderは議論禁止・コード公開禁止、また、コード提出の場合は計算資源も全員いっしょなので、そういう意味で公平な競争がしたい人にはおすすめ。
    • ただ、TopCoderのようにコード提出形式のもはじまったようです。
    • 上位の情報は書いてないので、上位の人たちは、別にこのままのルールでも、公平な競争ができてると感じているかも。でも、中位以下の人のモチベーションがどうなるか気になります。

書いたコードを、Kaggleのブラウザ上で実行できる。

• TopCoderでもできなくはないけど、ファイルも取り扱えたり。folkもできたり、高機能。多くのライブラリも使えます。Dockerのおかげ？
• 計算資源がしょぼいのを除けば、ブラウザ上だけでなんでもできそう。すごい。

最終提出データを2種類選択できる。

• TopCoderだと1番最後に提出した1つになるので、万が一間違ったものを提出したことを考えると、時間ギリギリで提出するのは無謀。
• 1つは過学習したやつ、1つはクロスバリデーションしっかりやった無難なやつといった、作戦もありそうです。

参加者のレベル

• 語れる立場にありません（泣）。マシな結果を出してからにします。ただ、最近はTopCoder→Kaggleへ参戦して結果を出しているトップクラスの方や（colunさん・Komakiさん・marek.cyganさん・iwiさんなど）、またKaggleからTopCoderへ参戦してる方もいます（fugusukiさんなど）ので、強い人はどこでも強いということだけは言えるでしょう。

Kaggle体験記じゃ

今回、参加したのはこれ。
www.kaggle.com
作業過程20時間をすべて録画していたので、時刻つきで、見直してみました。流れは分かるかと。

• (00:00:00) なんでもいいので、最低限の解答を提出しよう。自分は大風呂敷を広げて暴走する悪癖があるので、まず簡単な解をめざす！
• (00:31:54) Kernelsってところで、他の人のコードが見れて、ショック！folkって書いてあるってことは、これを使っていいのか？同じぐらいの得点の人もたくさんいるし、ぱくってそう…。

• (00:43:49) そのまま実行できるの？どれぐらい時間かかるんだろう…。

• (00:52:37) 提出できるし、Dockerすごい。まぁ、パクってるけど、最低限の解答ということにする。

• (02:36:56) 罪悪感をかんじてきたので、せめて自分で実行する。Linuxのほうがインストールが簡単そうだけど、家にLinuxがないので、Amazon Web Service(AWS) EC2で、無料のUbuntuインスタンスを借りてみる。

• スクリプトで使われてるパッケージ（NumPy, scipy, pandas, scikit-learn）を、全部インストールしたつもりなのに、動かず、ハマる。python 2で動くのか疑心暗鬼に。原因は、間違ってpython等を古いバージョンに戻したため、バージョンの整合性のせいで動かず、一からインストールしなおしたら、治った。 python 2で普通に全部動く。（2016年12月時点の話ですが、xgboostのインストールで、赤字の部分は古い情報も見かけるので注意。）

#xgboost
git clone --recursive https://github.com/dmlc/xgboost.git
cd xgboost; make; cd python-package; sudo python setup.py install; cd ~

• でも、やっぱり別のエラーがでる…。スクリプトの文字コードにスペイン語が入ってるのにも関わらず、秀丸はSHIFT-JISと誤認識して、文字化けしてた。おーい…。絶対UTFで。
• (08:30:59) 今度はMemoryエラー。単に無料インスタンスではメモリ不足のよう。有料で1番安いインスタンスを借りなおし、インストール用のbashスクリプトをちゃんと整備。

• (10:37:38) 動くようになる。ただし、単に自分でスクリプトを実行しただけでなので、スコアは同じ。この時点で、527位/1700ぐらい。
• (11:30:22) スクリプトの中身とxgboostのパラメータなどを理解しようとする。
• (12:30:57) データセット・スコアの理解につとめる
• (13:27:10) フォーラムをみる。 Lagと呼ばれる特徴量を追加すると0.03点いけるらしいのでやってみる。*1

• (16:04:55) 簡易版のLagを入れてみると、実際0.03にかなり近い得点にいけた！てきと～なことこの上ないけど、上位10%まであと少し。ただ、終了まで3時間しかない…。

• ちゃんとLagを入れてみるが、点が下がる。実装ミスかもしれないけど、AWS上だとIDEはさすがに使えないので、デバッグしづらい…
• 5分程度しか計算してないので、短すぎかも？
• (18:09:16)もう高いEC2インスタンスC4.8XLarge借りちゃえ。1時間$3ぐらいだし、もう1時間30分しかないので、問題ないでしょう。

• うわー、それでも結果伸びない。他人のを借りてきただけど、いろいろちゃんとセットアップしないので、結局損。xgboostしか使ってないのは、そこまで大問題ではないと思うけど、特徴量選択の自動化・ハイパーパラメータ調整・クロスバリデーションも何もやってない。眠い。天啓による調整に頼る（ダメ）。
• 最後、結構時間ギリギリ（打ち切れるように改良してないのもだめだし、そもそもギリギリまでやってるのがダメ）
• なんとか間に合って
• (19:38:59) あぁぁぁぁ、あせって間違ってデータではなく、pythonスクリプトを提出してることに気づく。つい、TopCoderの癖が…。バカすぎる…。

• マッチ終了
• (19:42:19) Post Deadlineと表示される。提出遅れには厳粛に対応、しかし、遅れた結果はしっかり見せる、優しいのか鬼なのか分からないけど、ちゃんとしてる仕様。

• 最終結果は、215位/1784(上位13%)でした。TopCoderのように、レート下がるってことはなさげなので、下位に沈んだら放棄する人も多いのかも。
• 徹夜したので、次の日は即寝落ち。

• 2日後、高額なインスタンスにつなげっぱなしだったのに気づく！
• 結果

• …わしはバカすぎじゃ。

Kaggle体験記まとめ

• 普段からLinuxを使っている人や、AWS EC2やS3を使っている人であれば、もっとすんなり行くと思います。
• 今回は全部AWS EC2上のUbuntu上で行いましたが、自分のPCにも開発環境を用意したほうがいいと思います。IDEが使えないのが痛い…。
• Kaggleの流れを知りたいのであれば、最初の1回は今回のように他の人のスクリプトを足がかりにスタートするのは悪くないと思います。
• ただ、成功例をたどるだけでは、勉強にはならなそう（短時間のわりに良いスコアは得られるかもしれませんが）。試行錯誤したり、アルゴリズムを導入・改良したり、自動化など環境をより便利にしたりってところは、自分でやったほうが、長期的にみると、スコア的にも勉強の観点からも得だと思います。
• Forumでの解法の事後公開やディスカッションもとても盛んなので、読みましょう。そのあとの復習が大事。
• 日本人のKaggle参加者の参戦記もたくさん落ちているので、ぜひ読みましょう。

おわりに

来年こそはKaggleもがんばりたい…といいたいところですが、本職が大変になりそうなので、ぜひ、これをみた皆さんは、わしの分まで、Kaggleをやるのじゃぞ！

*1:（同じお客様IDの過去5年間のデータを探し、それも特徴量に加えるという方法です。過去の記事　ランダムフォレストのつかいかた - じじいのプログラミング -> 同種の説明変数を追加する。 -> （1）同種のデータとのかかわりを表す変数を追加する ぽいやつ）

競技プログラミングの2015年の結果、2016年の目標

2015年の結果

SRMに56.6%以上参加	20点	達成
SRMに56.6%以上参加したうえでRating1800以上	20点	失敗
TCO15 SRM Round 3	20点	失敗
マラソンマッチ レッドコーダー	80点	失敗
TCO15 マラソン予選10位以内 1回ごとに	20点	失敗
TCO15 マラソンワールドファイナル出場	300点	失敗
Google Code Jam Round 3	10点	失敗
プロコンTシャツゲット1枚ごとに	5点	2枚
プロコン賞金10万円ごとに	10点	失敗
プロコンでオンサイト決勝出場	50点	失敗
ニコ生放送200枠分（=100時間）	10点	失敗
海外でプロコンオフ会をやる	10点	達成
Codeforcesで栗原市ランキングいり	10点	失敗

2015年の結果 40点でした…。(なお、2014年は60点でした)

2015年の反省

マラソンマッチ レッドコーダー	80点	失敗
TCO15 マラソン予選10位以内 1回ごとに	20点	失敗
TCO15 マラソンワールドファイナル出場	300点	失敗

まずは、ここらへん。TCO15 Marathon Match Round 1の最終提出が間に合わず（もちろん自分が悪い）、レーティング激減して、気持ちが切れてしまった感じがあります…。あと、そもそも時間が作れなかったというのもありました（特に2015年上半期）。
また、自分の場合は、安定した結果を出すために、マッチに参加するよりも、突っ込んだ復習が大事な気がしているのですが、復習のモチベ維持もできていなかった気がします。

2016年はもっと時間がなさそうで、未来は暗い気がしますが、参加するマラソンマッチを絞って、出たやつについては丁寧にやっていこうと思います。

プロコン賞金10万円ごとに

10点

失敗

主に機械学習マッチでチャンスがあると思っていたのですが、そもそもあまり参加ができませんでした。少なくとも解答がでた場合は、結果が悪くても提出するようにはしているのですが、解答まで至らなかったマッチが２つありました…（地震と前立腺がん）。こっちは短時間で準備するノウハウはつかんできた気がするので、今後、通常マラソンよりは結果が出せそうな気はします。

SRMに56.6%以上参加したうえでRating1800以上

20点

失敗

2015年は初めて一時的にRating 1800を越え、最終戦まで1800を越えるチャンスはあったのですが、逃してしまいました。Mediumが解けないのはしょうがないにしても、Easyで落とすケースが目立ちました。というか、Easyが昔ほど簡単ではありません。
まずEasyの出てない回の問題もたまってきたので、Easy問題を練習で解いてEasy安定に努めたいと思います。これなら、時間はそんなにかからないはず。

Google Code Jam Round 3

10点

失敗

大会では、もうちょっとうまくやれた気がします。Code Jam Round 3は決して不可能ではない目標なのですが、ピンチになって難しい問題を解かないとダメな状況になるとほぼ失敗するので、ピンチになってもあせらずに簡単な問題を確実に解いていくようにしたいです。

ニコ生放送200枠分（=100時間）

10点

失敗

結果、放送したのは120枠分（＝60時間）程度でした。現状だと100時間はかなり難しいですが、できる範囲で継続してやっていきます。

海外でプロコンオフ会をやる

10点

達成

シンガポールでオフ会をするのは予想以上に大変でした…。「人を集める方法」「人に連絡する方法」「場所探し」「参加費」「何をすればいいのか」、すべてが難しかったです。かなりの時間を使った気がしますが、達成できてよかったです。ただ、これをやらなければ、他に時間をつかえた気もします。

あと、数少ない良かった点としては、「目標を常に覚えていた」ことでしょう。目標がなければ、もっと無為に過ごしていたと思われるので、それよりはマシ。2016年も目標を忘れない！

2016年の得点表と目標

正直なところ、2016年は2015年より忙しくなる要素しかないので、目標は2014年の水準、60点以上にします。あと、Codeforces, Facebook Hacker Cup, Kaggleとバリエーションを増やしました。（これらを増やしても2015年は40点です。）

SRMに50%以上参加	20点
SRMに50%以上参加したうえでRating1800以上	20点
TCO16 SRM Round 3	20点
マラソンマッチ レッドコーダー	80点
マラソンマッチ Rating 2000以上	40点
マラソンマッチ Rating 1800以上	20点
TCO16 マラソン予選10位以内 1回ごとに	30点
TCO16 マラソンワールドファイナル出場	300点
Codeforces Highest Rating 2200以上（薄い橙）	50点
Codeforces Highest Rating 1900以上（紫）	10点
Google Code Jam Round 3	10点
Facebook Hacker Cup Round 2	5点
Facebook Hacker Cup Round 3	20点
プロコンTシャツゲット1枚ごとに	5点
プロコン賞金10万円ごとに	10点
プロコンでオンサイト決勝出場	50点
Kaggle 上位25%	5点
Kaggle 上位10%	10点
ニコ生放送200枠分（=100時間）	10点
海外でプロコンオフ会をやる	10点
Codeforcesで栗原市ランキングいり	10点

なお、得点表は、難度だけではなく、自分がやりたいかどうかも含めて決めています。

ところで…

ほっほー。

2015年の目標を振り返ってみたところ、40点のところをみたら、

30～59

怠惰・堕落(FUJIYAMAに乗る)

と、書いてあったのじゃ。絶対にこんな低い点は取らないと思って、てきとーに書いたのに…。しかも、不幸は重なるもので、甲府に行く用事ができてしまったので、ついでに行ってきたのじゃ…。

頭がおかしいアトラクションだらけですね。わしは死にたくないのじゃ。

でも勇気を振り絞って、以下の乗り物に乗ってきたのじゃ。天にも届くようなスロープに、背後にそびえる富士山が、一層の恐怖をかきたてるのじゃ。変な生き物もいたし、地獄だったのじゃ。さすがFUJIYAMA！

…では、さらばじゃ。ほっほー()

累積和を使う動的計画法

この記事はCompetitve Programming Advent Calendar 2015の23日目の記事です。tanzakuさんに感謝
www.adventar.org

今回は、累積和を使う動的計画法についてです。TopCoderのDiv2上位ぐらいの人向けの難易度です。

問題

AtCoder Typical DP Conestの問題です。
F: 準急 - Typical DP Contest | AtCoder

Problem Statement
ある路線には駅 1 から駅 N までの N 個の駅がある。すぬけ君は、この路線に準急を走らせることにした。
準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。
連続する K個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。
準急の停車駅の組み合わせとして何通り考えられるか、mod 1,000,000,007 で求めよ。


Constraints
2≤K≤N≤1000000

最初の方針（ただし、計算時間が間に合わない）

まず答えがでる実例N=9, K=5で手計算すると、以下のように112通りになります。図は矢印にそって足していくだけです。駅1と駅9は絶対に停まるのには注意してください。

• 状態は、
  • 何駅目まで来たか
  • 現在何駅連続で停まっているか
• 遷移は
  • 次の駅に停まる→連続で停まった回数が+1
  • 次の駅に停まらない→連続で停まった回数が0に戻る

となるので、動的計画法で
dp[何駅目まで来たか][現在何駅連続で停まっているか]
とすれば、コードは以下のようになります。

#include <iostream>
using namespace std;

long long dp[123][123];

int main()
{
	int N,K;
	cin >> N >> K;

	long long  MOD = 1000000007;

	dp[1][1]=1;
	for (int n = 1; n <= N-1; ++n)
	{
		for(int k = 0; k <= K-1; ++k)
		{
			dp[n+1][k+1] += dp[n][k];  // 駅にとまる
			dp[n+1][k+1] %= MOD;
			dp[n+1][0]   += dp[n][k];  // 駅にとまらない
			dp[n+1][0]   %= MOD;
		}
	}

	long long ans = 0;
	for(int k = 1; k <= K-1; ++k )
	{
		ans += dp[N][k];
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}

しかし、この問題ではNもKが1000000まで取りえます。計算時間もメモリも間に合いません。

累積和で状態数を減らす

動的計画法の計算量は、ざっくりいうと、以下のように状態数×（１状態あたりの）遷移数になります*1。

つまり、計算量減らして高速化するには、

1. 状態数を減らす
2. 遷移数を減らす

のが基本です。今回は、状態数が多いので、状態数を減らしましょう。1連続停車～K-1連続停車までを1つの状態にします*2

駅に停まらないケース（青線）は、矢印元と矢印先が同じ状態なので、そのまままとめられます。簡単。

ただし、駅に停まるケース（赤線）はどうでしょう？１番上のK-1回連続（先の例だと4連続）のケースは、駅にこれ以上停まれないので失われています。この部分は差し引かないとダメですが、状態をまとめてしまってはK-1連続停車の回数がわかりません。この部分をどうやって求めるかが、累積和を使った動的計画法のポイントです。

最初の図をよく見ると、回数が斜め方向に同じになることがわかります。改めて考えてみると、n駅でK-1連続停車した回数は、n-(K-1)駅で0連続停車した回数といっしょです。

0連続停車した回数は分かるので、これで計算できます。例えば駅5の1連続～K-1回連続は、4+4-1=7と求められます。

これで計算量はO(N)まで落とせます。コードは以下のようになります。

#include <iostream>
using namespace std;

long long dp[1234567];  // dp[n] = n駅まできて、現在0連続停車
long long sum[1234567]; // sum[n] = n駅まできて、現在1～K-1連続停車

int main()
{
	int N,K;
	cin >> N >> K;

	long long  MOD = 1000000007;

	dp[0]=1;
	sum[1]=1;
	for (int n = 1; n <= N-1; ++n)
	{
		dp[n+1]=sum[n]+dp[n];
		dp[n+1]%=MOD;
		sum[n+1]=sum[n]+dp[n];
		sum[n+1] %= MOD;
		if(n+1>=K)
		{
			sum[n+1]=sum[n+1]-dp[n+1-K]+MOD;
			sum[n+1] %= MOD;
		}
	}

	cout << sum[N] << endl;

	return 0;
}

まとめ

動的計画法の高速化には、状態数を減らすのが方法の１つです。累積和を使って減らすことができます。累積和の部分と累積和ではない部分の関係をどう立式するかで、アイディアが必要になってきます。
ただ、今回の方針は一例にすぎず、同じ問題でも多数のやり方があります。ぜひ「Typical DP 準急」で検索して、他の方針との違いも見てみてください。

応用問題として、ちゃっかりこの問題をあげておきます。累積和だけではありませんが、チャレンジしてみてください。
Contest Page | CodeChef

あす24日クリスマスイブは、競技プログラミングアドベントカレンダー創始者のtanzakuさんと、実際に役立った例を紹介してくださるuvarimeronさんです。楽しみですね。それでは、楽しいクリスマスを！

*1:本当は１遷移あたりの計算量も掛けないといけませんが、O(1)の問題のほうが多いでざっくり

*2:着想は、自分の場合は、１連続停車～K-1連続停車まで、だいたい同じような遷移をしているところから思いつきました。

MSXの思い出 - 別冊テープログイン MOCKY

MSXアドベントカレンダー8日目の記事です。主催者のmsiroさん、ありがとうございます！
www.adventar.org

1985年の別冊テープログインに載っていた、MOCKYというゲームを紹介しようと思います。

Tagoo : MSXソフトウエア検索 : 別冊テープログインMSX GAME BOOK

このゲームは風船をつくり

敵をおびき寄せ

敵がからまったら

敵をくくりつけて

敵を空に飛ばして倒すゲームでした

２人プレイもできます

片方のプレイヤーが敵にやられて全滅しても

やられたプレイヤーはお化けになり、ゲームが続けられます

お化けになったプレイヤーは風船を壊すことができます

風船を割れるので、邪魔することができます

しかし、実はお邪魔プレイだけではありません

このゲーム、実は風船が同時に2個しか作れず、変なところに風船を作るとピンチになります

そこでお化けが、いらない風船を割ってあげると

風船を新たにつくることができ

追い詰められてしまっていても、協力して、無事敵を倒せます！

まとめると、

• 死んだあともプレイできる。
• プレイヤー１とプレイヤー２が違う役割となる
• 死んだ後に、邪魔プレイと協力プレイの選択ができる
  • ゲームをやり直したければ、邪魔プレイ。
  • 性能の差をいかして、協力プレイ

という工夫がありました。その後、ボンバーマンのみそボンなど同じコンセプトのものは現れますが、画期的なゲームデザインでした。

明日9日目はsunflatさんのVPOKEについての記事です。楽しみですね！ではでは！

ボツネタ集（だいたいランダムフォレスト）

どうでもよいまえがき
今回の記事を最後に、機械学習関係の記事は、しばらくお休みにします！

• 我流すぎて、機械学習の知識が不足していて、記事を書くのに妙に時間がかかる。
• 最近、機械学習マッチで結果を出してないので、その中で記事を書いても、自分の中で説得力がいまいち。

というわけでしばらくの間は、機械学習について、以下のことに専念します。

• 本とか論文とか読んでインプット
• 機械学習マッチで結果を出す

ただ、記事を書こうと思ってたボツネタがあるので、勢いで書きました。雑です。メモ書き程度だと思ってもらえば。

それではスタートじゃ！！！！

ボツネタ1 : ID分解

世の中のIDというものは、複数の情報を持っていることがあります。これを別の特徴量として追加します。数学も機械も関係ない、セコいテクニックですが、意外と実戦的かもしれません。

まず、データを眺めてください。

自分だったら、x0のidの赤で囲われた桁を、別な特徴量として追加します。紫で囲った部分も念のため追加するかもしれません。なぜでしょう？

なぜかというと、いろいろと法則に気づくからです。

• 紫の最初の5桁は、startdayが同じとき、常に同じ値になります。日時にかかわる値だと推測できます。ただ、この5桁とstartdayの大小関係違うので、一応特徴量として追加します。
• 赤の桁は、完全に独立した値です。0～2の値しかとりません。とてもあやしいので、特徴量として追加します。
• 下2桁と3桁は常に31なので不要です。
• 下1桁はcyclesと常に同じ値なので不要です

まぁ、ただ注意点は、

• 分解前の元のIDを削るのは、特に慎重になったほうがいいです。気づいてない重要な情報があるかもしれないので。とりあえずは分解したのを追加するだけにとどめておきましょう。
• つねに同じ値というのも、必ず全部のデータで常に同じ値になってるか確認しましょう。まれに違うことがあって、それが重要度の高い特徴量になってたら。大惨事です。

データを数値でも眺めるのは本当に重要です。機械学習する前に、必ず見るようにしましょう。まぁ、こういうのすら自動化するのが最高ですけどね。

ボツネタ2 : ランダムフォレスト実装例の簡単なバリエーションについて

過去の記事で、ランダムフォレストといってもバリエーションがいろいろあるといって逃げっぱなしなので、「ちょっとは説明しないと…」という罪悪感をかんじていました。

• 効果 : ★が大きいほど、効果が高そう…といいたいですが、完全に自分の経験上なので、信ぴょう性はあまりないです。
• 謎度 : ★が大きいほど、めったにみかけないもので、謎度を高くしてます。

C++の実装例を使って、ちょっと説明します。改良はみんなの宿題！

ルートバッグ1.5倍

効果 ★
謎度 ★★★★★
TopCoderのPsyhoさんのコードをみて知ったテクの中でも、もっとも謎なものです。

ブートストラッピングでは、ルートバッグのサイズは元のデータは0.632倍が使われています。
bootstrap - What is the .632+ rule in bootstrapping? - Cross Validated
実装例のrootBagSizeRatioの部分です。
115行目

const int rootBagSize = static_cast<int>(numData * rootBagSizeRatio); // ルートに入るデータの数
root.bags.resize(rootBagSize);

#if INCMSE
vector <int> freq(numData); // データ番号別の、ルートに選ばれた個数
#endif // INCMSE

// ブートストラップサンプリング
for (int i = 0; i < rootBagSize; i++)
{
    // ここで、同じIDが選ばれる可能性があるが、問題なし。
    int row = randxor.random() % numData;
    root.bags[i] = row;
#if INCMSE
    freq[row]++;
#endif // INCMSE
}

rootBagSizeRatioの部分は、調整するにしても、普通は1以下の値を入れようと考えますが、Psyhoさんはここで1.5倍のように、1を超える値を入れてくることもあります。いったいどういう意味があるのか分かりませんが…。
なお、

• 1.5倍を入れるようにした場合でも、OOBデータもわずかに残ります。重複も許してるので。
• このままだと計算時間も長くなるので、防ぐために特徴量毎にweightという変数を用意し、何回でてきたかをとっておけば、計算時間は長くなりません。ソースコードの改良は読者の宿題！！

領域を分けるとき、全部の境界を試す

効果 ★★★
謎度

Rのランダムフォレスト実装であるので、そちらが標準だと思います。

ある特徴量の、全部の境界を試してます。自分の実装例では以下のように、numRandomPositions個しか試していません。
224行目

for (int j = 0; j<numRandomPositions; j++)	 // どの位置で分けるか
{
    const int positionID = randxor.random() % SZ(node.bags);
    const FeatureType splitValue = features[node.bags[positionID]][featureID];

ただ、多く分けるほうが必ず良いというわけでもありません。特に、少ない特徴量で似たような木ができる現象の要因になることも。計算時間も長いです。

上記の実装を全部の境界で切るようにしたいなら、

for (int j = 0; j<SZ(node.bags); j++)	 // どの位置で分けるか
{
    const int positionID = j;

とすれば、機能としてはRの実装と一緒になりますが、速度としてはお話にならないです、ダメ！前回の日記で述べた式

  {Σ[i∈P](Yi-E[P])^2}                          - {Σ[i∈L](Yi-E[L])^2}                          - {Σ[i∈R](Yi-E[R])^2}
= {Σ[i∈P]Yi^2} - 2E[P]{Σ[i∈P]Yi} + |P|E[P]^2 - {Σ[i∈L]Yi^2} + 2E[L]{Σ[i∈L]Yi} - |L|E[L]^2 - {Σ[i∈R]Yi^2} + 2E[R]{Σ[i∈R]Yi} - |R|E[R]^2  ... 2乗を展開した
=                - 2E[P]{Σ[i∈P]Yi} + |P|E[P]^2                  + 2E[L]{Σ[i∈L]Yi} - |L|E[L]^2                  + 2E[R]{Σ[i∈R]Yi} - |R|E[R]^2  ... {Σ[i∈P]Yi^2} = {Σ[i∈L]Yi^2} + {Σ[i∈R]Yi^2} で消した。
=                - 2E[P]S[P]         + |P|E[P]^2                  + 2E[L]S[L]         - |L|E[L]^2                  + 2E[R]S[R]         - |R|E[R]^2　... 総和Sであらわした
=                - 2S[P]^2/|P|       + S[P]^2/|P|                 + 2S[L]^2/|L|       - S[L]^2/|L|                 + 2S[R]^2/|R|       - S[R]^2/|R| ... E[A] = S[A]/|A|で平均Eを消した
=                -  S[P]^2/|P|                                    +  S[L]^2/|L|                                    +  S[R]^2/|R|                    ... 足し算

これで評価するようにすれば、xが小さいほうから高速に全ての分け方を試せます（予めqsortを使います）。まぁ、説明不足なので、本家のソースコードregTree.cの関数findBestSplitを熟読して、実装しましょう。読者の宿題！
なお、後述する平均2乗誤差、3乗誤差や1.5乗誤差を変えるというのをやると、以上の数式展開が使えず、速くできません。

領域を分けるとき、任意の場所で分けられるようにする。

効果 ？？？
謎度 ★★★
一度も試したことはありません。上記の例ではデータのある場所で分けていますが、現在のノードに入ってるデータの、特徴量xの最大と最小を求めておき、(max-min)*rand + min の位置で切るといった感じの実装で、任意の場所で分けることができます。これをやるとxの値の差で選ばれる確率が変わるようになるので、いろいろと問題が起きそうな気もしますが…。

領域を分けるとき、マージン最大化っぽいことをする

効果 ★★
謎度
過去の日記で、yowaさんからコメントをいただきました。Rの実装でもやっているので、謎ではありません。
ランダムフォレストのつくりかた（C++の実装例つき） - じじいのプログラミング

おそらく日記をみて、「せっかく赤色と青色の領域を分けるのに、なぜ、わざわざギリギリの点上で分けるのか。中間で分けた方がいいのではないか」と思った人もいるのではないかと思います。それです。

改良前
278行目

node.value = bestValue;

改良後はこんなかんじになるでしょうか。

FeatureType nextValue = -BIG;

for (int i = 0; i < SZ(node.bags); ++i)
{
    if( features[node.bags[i]][bestFeatureID] < bestValue)
    {
        nextValue = max(nextValue, features[node.bags[i]][bestFeatureID]);
    }
}
node.value = (bestValue + nextValue) / 2.0;
if (!(node.value > nextValue)) node.value = bestValue;

あまり効果があった経験はないのですが、計算のオーダーが増えるわけでもないので、いれていいと思います。

木の深さに応じ、特徴量を選ぶ数numRandomFeaturesを変える

効果 ★★★
謎度 ★★★

以下のnumRandomFeaturesは、通常は固定ですが、これを木の深さに応じて変えます。

198行目

for (int i = 0; i<numRandomFeatures; i++)
{
    // x0,x1,x2...の、どの軸で分けるかを決める
    int featureID = randxor.random() % numFeatures;

実装は読者の宿題！まぁ、これは簡単でしょう。木の深さを表す変数をノードにもたせておき、numRandomFeatures[depth]みたいにすればよろしい。

これは割と効果があります。特に、後述する似た木ができる現象を避けるのに使えます。つまり、木の浅いところではnumRandomFeaturesの値を少なく、深いところではnumRandomFeaturesを大きめにすると良いです。

MSE以外の誤差を使用する

効果 ★★
謎度 ★★★

311行目

double lossFunction(double y, double mean) const
{
    return (y - mean)*(y - mean);
}

ここを、絶対値の3乗誤差、絶対値の1.5乗誤差、絶対値などに置き換える方法です。

ボツネタ3 : ランダムフォレストで似た木ばかりができると予測性能が落ちる

ランダムフォレストで、同じような木がたくさんできてしまうと、極端に予測性能が落ちることがあります。以下のような条件のとき要注意です。

• 特徴量が少ない（10個以下）
• 特徴量に比べて、ノード分割の際に選ぶ数numRandomFeatures（RのmTry）が多い。（目安は、回帰 特徴量の数/3、分類 特徴量の数^0.5）
• 切る場所を試す数numRandomPositionsが大きい（Rだと全部で切るので、多い）

木をたくさん増やすことである程度解消できますが、限度があります。ちゃんとパラメータを調整して、避けましょう。

以下の図は、特徴量が7個しかないケースで、予測性能が極端に落ちたときの、決定木10本をビジュアライズしたものです。

• 上側がルートです。
• 帯の長さが、ノードの属するデータの個数に当たります。
• 帯の色が、ノードをどの特徴量xで分割したかにあたります。計7色。

これを見ると、一見カラフルで、いろんな木ができてますが、上部の色はだいたい、茶色か水色か黄緑しか来ていないことが分かります。

念のため、上記の画像を出力するコードも貼っておきます。htmlで出力する手抜きなやつですが…。

    void visualize(int id)
    {
        char path[1001];
        sprintf(path,"../visual/VisualTree.html");
        FILE *fp = fopen(path, id==0 ? "w" : "a");

        vector <string> colors = 
        {
            "Red",
            "Maroon",
            "Yellow",
            "Olive",
            "Lime",
            "Aqua",
            "Teal",
            "Blue",
            "Green",
        };

        if (fp)
        {
            fprintf(fp,"<canvas id=\"sample%d\" width=\"15000\" height=\"300\">\n",id);
            fprintf(fp,"<p></p>\n");
            fprintf(fp,"</canvas>\n");
            fprintf(fp,"<script>\n");
            fprintf(fp,"var canvas = document.getElementById('sample%d');\n",id);
            fprintf(fp,"var context = canvas.getContext('2d');\n");

            float xRatio = 0.5f;

            queue < pair <int, int> > q; // ノード番号, 左座標
            q.push(make_pair(0,0));
            while(!q.empty())
            {
                pair <int,int> now = q.front();
                q.pop();

                const TreeNode& nd = m_nodes[now.first];


                fprintf(fp,"context.fillStyle = \"%s\";\n", colors[(nd.featureID+SZ(colors))%SZ(colors)].c_str());
                fprintf(fp,"context.fillRect(%d,%d,%d,%d);\n", now.second, 10*nd.level, (int)(SZ(nd.bags)*xRatio), 10);

                if(!nd.leaf)
                {
                    q.push(make_pair(nd.left,now.second));
                    q.push(make_pair(nd.right,now.second+(int)(SZ(m_nodes[nd.left].bags)*xRatio)));
                }
            }
            fprintf(fp,"</script>\n");
            fclose(fp);
        }
    }

ボツネタにすらまとめられなかったボツネタ

カテゴリカル変数ごとに、他の特徴量xや目的変数の統計データを求めて、新たな特徴量として追加する。

機械学習は、基本不等式で分けるので、カテゴリカル変数（列挙型）はやっかい。そのままは使えない。ただ集計して特徴量を足すのに使いやすい。カテゴリカル変数x1をだとしたら、x1の値ごとに、他の特徴量x2,x3..やyを集計して（足す・割る・割合を求める・最大・最小）、新たな特徴量を追加する話。なぜボツにしたかというと、
ランダムフォレストのつかいかた - じじいのプログラミング
の「同種のデータとのかかわりを表す変数を追加する」とネタがかぶってるから。ただ、あの記事ではカテゴリカル変数とは言わなかったので、改めて書くか迷った。ただ非常に効果があるテクニックなので、みなさん使ってほしいです。

ブースティングのC++の実装例

C++の実装例で決定木の部分は実装してるので、てきとーなブースティング（木0の予測外れ分を木1のyとツッコむ）というのを実装するのは割と簡単。ただ、まじめなブースティングは、木の重みづけの部分とかも含めて理論になってるっぽく、そこは理解してないので、やめた。また、実戦で使ったことがないのも不安なので、やめた。

以上です。では、さようなら～。ほっほー。