MM 90

hotpepsi @hotpepsi

診断人さんのおかげで名前がわかったので、明日からTopCoder Duelつくるのじゃ

agw @masashinakata

@hotpepsi . 　　　　　　　　　　| ﾈｴｼｼｮｳ､ 　　　　　　　　　　　|　　　ﾘｸｴｽﾄｲｲ? 　　　　　　　 　　　 ﾉ,,∧ 　　　　　　　　　 ／/･ω･`) 　　　　　　　　／　/⊂ノ 　　　　　　　　＼ /ーJ ￣￣￣￣￣￣￣￣￣

agw @masashinakata

Topcoder Data Science Marathon Match: Prostate Cancer Foundation - Computational Oncology - YouTube: youtube.com/watch?v=0-XuFp…

拡大

agw @masashinakata

1:35のところで、"At it's core, this is an image analysis data science challenge…"と言及しているので、画像解析絡みの様子。しかし、賞金総額$25,500.00の$500.00ってなんぞw

agw @masashinakata

うん、やっぱそうみたいだ: Topcoder Marathon Match – Computational Oncology & Data Science – Update & Video – topcoder: topcoder.com/blog/topcoder-…

msiro @msiro08

次のMarathon Match、画像解析と聞いては全力で参加せざるを得ない。さようならSamurAI Coding・・・（もしかすると戻ってくるかも知れないけど）

コルン＠KaggleSanta2015 @colun_0eitm7gt

本アカウントはサンタマラソン2015( kaggle.com/c/santas-stole… )の考察用です。この最初のツイートより前に、既に非公開設定されていて、フォロワー／フォローイングともに０の状態でコンテスト終了まで運用されます。コンテスト終了後に鍵解除の予定です。

hotpepsi @hotpepsi

@masashinakata ﾅﾅﾅﾅﾝﾃﾞｼｮｳ

コルン＠KaggleSanta2015 @colun_0eitm7gt

サンタマラソンはまだ2回目ですが、去年も今年も焼き鈍しの問題です。現在の私は12,482,848,741.22050点で22位ですが、今焼き鈍し中の解が12,454,500,000点付近を出す可能性があり、それは現在の順位表だと11位です。

コルン＠KaggleSanta2015 @colun_0eitm7gt

現在焼き鈍し中の解で120G回の遷移試行を行ったものになる予定で、これには36コアマシンで約12時間焼きなます必要があります。最終的に168時間ぐらい焼きなます可能性がありますが、それは本当の最終週に行うことであって、現段階でやるべきことではありません。

コルン＠KaggleSanta2015 @colun_0eitm7gt

ただ、最終段階での焼き鈍しと大きくかけ離れた、例えば32M回程度（手元PCで約1分）の焼き鈍しだと、周辺状況が大きく変わってきますので、あまり参考にならなくて、120G回程度とりあえず焼き鈍してみるというのはガラッと風景が変わります。

コルン＠KaggleSanta2015 @colun_0eitm7gt

（※単位はG(1000x1000x1000)とM(1000x1000)なので、遷移試行回数に1000倍以上の開きがあります）

コルン＠KaggleSanta2015 @colun_0eitm7gt

で、試行回数だけ増やしても、ここから更に急激に良くなるというのが見込めなさそうです。しかしながら、11位のままというのも非常に悔しいものです。これを許してしまうのは、今後一生そうであることを許してしまうということであって、上に10人も……寛容な僕でも到底許せるものではありません。

コルン＠KaggleSanta2015 @colun_0eitm7gt

まあ、チームは除くとした場合であっても、やはり上に5人いますから、やはり簡単に許して良いものではないです。

コルン＠KaggleSanta2015 @colun_0eitm7gt

そもそもよほど上位まで行かない限りは、チームあんまり関係ないし。

コルン＠KaggleSanta2015 @colun_0eitm7gt

12,467,012,119.48510点で14位でした。予想が12,454,500,000点付近とのことだったので、かなり差が出ていますね。なかなか思うように行かない。

コルン＠KaggleSanta2015 @colun_0eitm7gt

教科書に載っている焼きなましの遷移確率式を使った場合、a→bもb→cも悪くなる（遷移確率100%ではない）のなら、a→b→cの連続遷移確率とa→cの遷移確率は等しくなる。

コルン＠KaggleSanta2015 @colun_0eitm7gt

これに基づけば、今までa→bの遷移しか定義してこなかった所にa→cの遷移を拡張しても、そこまで問題ないだろうと期待できる。 実際にはいくつか問題があって、１つ目は遷移確率以外に、近傍列挙確率が存在して、そんな綺麗な式にはならないということ。

コルン＠KaggleSanta2015 @colun_0eitm7gt

逆に、a→cを定義するとどんなメリットがあるのかというと、b→cが100%遷移の時に、a→b→cと通るよりも、直接a→cと通った方が良いということ。

コルン＠KaggleSanta2015 @colun_0eitm7gt

ある意味で、遷移確率は距離の特性を持っていて、どこかを経由しての遷移確率は、常に、直接の遷移確率よりも小さくなることがない。

コルン＠KaggleSanta2015 @colun_0eitm7gt

もちろん、教科書にある遷移確率を使った場合の話ね。

コルン＠KaggleSanta2015 @colun_0eitm7gt

で、この時に、迂回距離が伸びる原因は、途中の山と谷の繰り返しなわけですよ。なので、山と谷の繰り返しがあまり存在しない様な迂回路が定義できるのなら、どうにかなる計算。

コルン＠KaggleSanta2015 @colun_0eitm7gt

現在基本的に「隣の配送経路への付け替え」と「自配送経路の配送順の変更」のみを遷移として定義しています。配送経路はだいたい北極から南極への直線になるので、これで一応だいたいうまく行きます。。。が、ところどころねじれているので、うまくいかないのですね。それをどうにかしましょ。。。

コルン＠KaggleSanta2015 @colun_0eitm7gt

理想的には「全部の配送経路への付け替え」を定義してあげたい所だけれども、これは２つの理由で問題がある。１つ目は無駄な遷移がむちゃくちゃ多くなること。ただこれは、遠い配送経路の列挙確率を下げてあげれば、ある程度はどうにかなります。

コルン＠KaggleSanta2015 @colun_0eitm7gt

もう１つは二の次なのですが、マルチスレッド化しているのでデッドロックの問題。現在の実装がどうなっているかというと、配送経路はだいたい１５００前後あるのだけれども、これらを環状にリンクしていて、２つの配送経路をロックする際は、リンク元を先にロックして、その後でリンク先をロックする。