Hatena::Grouptopcoder

横道にそれるTopCoder参加記録でもいいじゃないか

 | 

2018-01-16

2018-01-16 Weathernews Programming Competition 参加記録

22:05 | 2018-01-16 Weathernews Programming Competition 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか を含むブックマーク はてなブックマーク - 2018-01-16 Weathernews Programming Competition 参加記録 - 横道にそれるTopCoder参加記録でもいいじゃないか

まずはポエムから。

普段、試行錯誤を楽しみにコンテストに参加している身としては優勝を意識してからは本当にしんどい感じでした。基本的に勝負事に向いていないのだと思います。

潜伏という姑息な手段で形式的には勝ちましたが、shinhさんとまともにやっては勝てる気がしません。

潜伏したのは夜なべして競い合うのは辛いからという理由ですが、主催側としては出来るだけ良い結果が欲しかったと思うので申し訳ないし、shinhさんにも申し訳なかったなあと思います。

最終日は細かいチューニングは済ませてしまってあり、僅差でも抜かれてしまうと手立てがない状況でした。


それでも出来栄えとしては外注してもどこにも達成できないくらいの性能が達成できたと思います。さすが優秀なcompetitorが集まるAtCoderですね!

改善の効果は指数関数的に小さくなっているという印象でした。

200点差というのは流石に想定していませんでしたが、2,000点くらいの差で決着することは十分考えられると思っていました。

イメージですが、

もともとの1ピクセルが16bitで

出現する値の偏り 4.2bit

上、左、左上のピクセルとの関連性 4.5bit

異なる時間、周波数の画像との関連性 0.7bit (隣接ピクセルとの関連と重複する情報以外の部分)

を使って1ピクセル6.7bitになった、という感じです。

600秒という制限のなかでは、ここから1%(0.07bit)削るのはかなり大変という印象でした。


使用している技術は観測した範囲では他の参加者とあまり変わらないのかなと思います。

提出したコードはそれなりに読みやすくしたつもりなので、もし詳細気になる方は↓

https://wn2017_1.contest.atcoder.jp/submissions/1981642


私もDNN使ってみたいなと思いましたが、処理時間の関係で難しそうでした。

気をつけたのは、それでも非線形な処理を使おうということでした。

DNNなら活性化関数がそれに相当しますが、条件分岐でもいいから、あまり線形和の操作をしないこと。

S/N比の悪い情報をまぜてしまうとかえって圧縮率が悪くなってしまう。だからイメージとしては「5分前の画像と比較して動きが大きい箇所か、そうでないか」という情報を利用しようとか、そういうイメージで考えました。

実際にはそこまでヒューリスティックに処理しているわけではありませんが。


圧縮できるっていうことは、データに規則性があるということで、この世界の秩序がつまっているということで、とても魅力的なトピックだと思います。

shinhさんがPNGより随分優秀なファイルフォーマットを紹介していましたが、一度フォーマットが決まってしまうとなかなか代替が進まないのが、圧縮という分野の少し切ないところかなと思います。

貴重な機会を提供して下さったAtCoder社とウェザーニュース社に感謝しつつ、おしまい。

 |