https://beta.atcoder.jp/contests/wn2017_1/standings
むっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。
やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。
今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測したものなので、互いに相関があり、相関を利用しない普通の画像圧縮だけでは上位の成績にはなかなか追いつかないと思っています(後述しますが汎用画像圧縮で7位は取れていたと思います)。
次のピクセルを予測する
圧縮についてある程度の知識があれば、色んな情報から次のピクセルの値を予測して、当然予測は外れるので外れた分についてエントロピー符号、という方法を考えるかと思います。エントロピー符号はデータに偏りがあればあるほど圧縮率が上がるため、問題のドメインについての知識を利用して、データを偏らせることができれば圧縮率が高くなります。例えば、普通の画像は一般的に直前のピクセルと近い値を持っていると考えられるので、直前のピクセルと次のピクセルの差分を保存すれば値が0に近い値に偏るので良いのです。すぐ左のピクセルだけでなく、左と真上のピクセルの平均値であるとか、付近のピクセルを適当なわりあいで混ぜた数値であるとか、予測の精度を上げる方法は色々と考えられます。
今回の問題の場合、同じ波長を別の時間に観測した画像や、同じ時間に違う波長を観測した画像からもパラメータを拾ってくることができて、さらにこの予測の精度を上げることができます。これは、パラメータが複数あって一つの値を推定するので、普通にある種の機械学習と言えます。
私が使った方法は、参照画像からピクセルの値を推定して、その推定した値がさらにどれだけ現実とずれているかということを近傍のピクセルから推定する、という方法と、参照画像と近傍の両方からピクセルを推定する、という両方のアプローチを、かつ色んな参照画像に対してやってみて良かったやつ、という方法です。機械学習で忌み嫌われていると思っている ensemble 的な話です。本当は一気に推定する方法だけで行きたかったのですが、一気推定は当初の時間制限だと割とギリギリだったのと、参照画像との相関が低い画像で成績が悪い(特に全体の半分以上を占める一番大きい画像4枚で良くない)ので、最後まで残ってメンテナンスを困難にしていました。
実際のモデルは、単にパラメータ(つまり近傍や参照画像のピクセル値)を重みつけて線形和したもので、重みの推定は単なる最小二乗法でやりました。パラメータの二次以上の項を入れるのはほぼ逆効果で、まあそれは冷静に考えるとピクセルの値を2つかけ算した値に意味があるとは思えないわけですが、もう少し複雑なパラメータを入れることはありえたかと思います(例えば med(x,y) のような)。
最小二乗法は微分可能なおかげで解析解があって、お手軽高速に計算できるというのは大変良いのですが、後段のエントロピー符号的には無視しても良いはずの外れ値に優しい、という特性を持っているので大変よろしくないという認識でした。なるべく多くのピクセルをゼロ付近の極めて近いレンジの値に押し込むことによって圧縮したい、というモチベーションなので、稀に予測が大幅に外れる値がどういう値を持っているか、はたいして興味がないのです。実際ぐぐってみると、ロバストな最小二乗法というのが色々あって、やってみると良かったりもするのですが……実装が面倒だったり遅かったり、そもそもここがよくなることで得られるメリットが少なかったりとあって、放棄しました。要研究。
さてこの線形和のパラメータは画像の位置によって多少違うはず、ということで適当に大きめのブロックに分割したりしています。また、余分にパラメータを保存することを考えると、ほんの少しの差ですが、参照画像のピクセルの値によって使うパラメータを切り替えたりもしています。
予測から外れたぶんをエントロピー符号にかける
で、予測からのずれの量をエントロピー符号にかけることになります。エントロピー符号というやつは、ハフマン符号が一番有名で、例えば0012というデータを圧縮するなら、0は1と2よりよく出てくるので"0"という1ビットで表現して、1と2は"10"と"11"を使って表現しよう、というものです。ハフマン符号では各文字を整数ビットでしか符号化できませんが、算術符号やその一種のレンジコーダでは概念的に小数ビットを割り振ることができる……ような感じです。出てくる文字の確率分布で割り当てるビット数を決めるわけですが、その確率分布を動的に変えるものがadaptiveなやつで、ヘッダなどに確率分布を埋める必要がない、データの特徴の変化に対応できる、などの良いところがあります。ですが、何故か私は最終日前までadaptiveなやつを使うことを考えてなかったのでadaptiveじゃないやつを使ってます。まあadaptiveなやつはそれはそれで不利なところもあると思います、たぶん。
これ以上偏りが顕在化できない状態になったデータは、ハフマン符号でだいたい理論限界寸前まで圧縮できます。レンジコーダだとさらに進んで、まあもう理論限界だろってとこまで行きます。でこの理論限界てのがシャノンの限界というやつですね。となるとやること無さそうな気がするのですが、やれることがあります。前段で適当に予測したくらいではまだまだ偏りが顕在化しきっていないのです。
残ったデータは、まあおおむねゼロに近いところに頑張って叩き込まれてはいるのですが、部分部分で見ると、うまい具合にゼロ近辺に集まっていてくれているところと、予測器が苦戦して値がバラけまくっているところがあります。参照画像も現画像もほとんどデータが無くて動きが無いところとかは、ゼロ近辺の値に短いビット列を割り当てても良いし、逆に動きが激しいところはもう少しまんべんなくビット列を割り当てないといけません。
というわけで、画像をブロックに区切った上で近くの予想からのズレの量に応じて、使うレンジコーダを分けています。近辺の予想からのズレで使いわけるのは、近辺がズレてなければ次の値もあまりズレてないだろうという仮定があり、逆に近辺がズレているのなら次の値もゼロから遠い値の可能性が高いだろう、ということからです。これは私の理解ではLZMAが似たようなことをしているはずです。
区間で区切るのもまたこういう分類の効果を発揮してくれるというわけです。私の場合、単にゼロからのズレっぷりの平方根の和で得点をつけて、その得点が高いものほどバラけたデータに使う符号器、というようになっています。二乗和だとさっきも書いた通り外れ値に従ってしまうため、絶対値どころか平方根くらいが良いようでした。
圧縮 == 機械学習
で、なんかこういうことをやっていると、まるで機械学習なわけです。前段はいくつかの値から次のピクセルを予測する回帰をやっていて、後段は似た素性のデータには同じエントロピー符号器を選択するように、データをなんとなく分類するわけです。回帰と分類てモロに機械学習ですよね。
このコンテストの最初の頃は、「うーんこの最初二乗法で予測するとかなかなか面白いアイデアじゃないの？」とか思って、ぐぐってみると10年以上前のどうでも良さそうな論文が出てきます。まあ私が考えるようなことは普通に誰でも考えるよな、と思ってました。
そのうちに「これなんか本当に機械学習そのものじゃないの？そういえばオートエンコーダとか割と初歩的な深層学習よね」とか思いはじめてきました。で、そういうワードでぐぐってみると、色々と出てきます。そんなこんなしていて気付いたのが、FLIFというデータフォーマットで、これは実際圧縮が難しいデータに関しては私の圧縮といい勝負をするレベルの汎用圧縮でびっくりしました。それで特に感銘を受けたのが、FLIFの説明スライドでした。
http://flif.info/slides/FLIF_ICIP16/assets/player/KeynoteDHTMLPlayer.html#36
特にこの上記の KEY INSIGHT というページでは、モロに「Compression = Machine Learning」と言っていて、そうだよそう、その通りなんだよ、と思って感動しました。その次の "If you can (probabilistically) predict/classify,
then you can compress" も、まさにその通り、という感を受けました。しかし今にして思うと別に感動的でもなんでもなくて、当たり前だよなあという気がしてきてしまうんですけどね。最近の圧縮ではニューラル使うのもあるようですし。まあこの「なるほど！」→「当たり前じゃん」のプロセスを成長ということにしたいです。
機械学習といえば特徴量をプロが頑張って自力抽出、というのはオワコンで、なるべく特徴量も含めてメタな学習をするようなモデルを選ぶというのが主流という理解で、その現在での完成形の一つが深層学習という感じだと思います。FLIFでは深層学習では無いものの決定木を使って使うべき符号器を選んでるようです。
2週間ほどあれこれと人間の直感を駆使して特徴量を探しては圧縮率に一喜一憂する、という全くスケールしない(けど実は結構楽しい)作業に従事していた私としては、この知見には実になるほどなあというところで、最初からこの知識があれば、もっとadaptiveなアプローチを最初から指向していた(そしておそらく大失敗していた)ように思います。何故失敗するかというと、この手のマラソンでは最終的には一般的すぎる解より人間全力チューンが勝ちがちという経験則があるからです。ただ実際問題としてパラメータ増えすぎてコード整理や調整をしきれなかったという面があって、実際最後の方はパラメータ調整だけが実質的な伸びしろだったので、反省点とも言えます。
まとめ
楽しかった、勉強になった、しかし本当に悔しい
