ICFP programming contest 2018

無職なこともあり、とても楽しい問題だったこともあり、久々にほぼガチで参加してる会になりました。いや楽しかった。順位表が凍結された段階での最終順位は2位で、1位は絶対に無理、その後にできた変更はしょうもないので、おそらく7位とかそのあたりの、5位強みたいなところに落ちついているのでないかと想像してます。暫定2位といっても特に良いところはなく、得点を決める式のおかげで、大幅なとりこぼしが無いだけで、推定1位のウナギに対して全順序がついて負けてる形のはずで、大変くやしい。が、まあ僕的には頑張ったとは思う。

初動

パーサやシミュレータを実装して、簡単なシングルスレッドAI、下から順に塗っていって、既にあるブロックとつながっていないところに置かざるを得なくなると、 Flip する、というものを Ruby で書く。デフォルトよりは大幅によくなることを確認して、いい問題だなあ……と思いつつ、寝る。

シミュレータについて、 SML 的ななにかからコンパイルされた JS だから、単純な方法でこれ切り出せるでしょ……と思ったけど、それに時間を使う余裕は最後までなかった。それに限らず、時間的余裕は最後までなかった。

起きて、 Flip のコストがとてもでかいこと、並列化が大変嬉しいこと、を再確認して、スケジューリングは賢くなくて良い(つまり無駄な動きをしても良い)から、 Flip はできればしない、かつスケールし、できればヘッドのMoveとFillの比が良い方針を考える。

思いついたのは、やはり下からスケジュールして行くのだけど、自分の左右と真下を塗る、という方針。Move:Fill比が最大1:3で、なんとなく良さそうに思ってた。

# B がボット、 O が担当する Fill する範囲
# 右方向が Z 軸、上方向が Y 軸、奥が X 軸で進行方向

OBO
_O_

でも実装してみると最初の戦車ぽい形のやつすらダメで、理由は説明しずらいけどとにかくこの方針で Flip 無しはできないのでした。もう少しちゃんと考えてから始めるべきだった。

エレベータ

次に考えたのは、上方向から見た X-Z の平面を 3x3区間に分割して、並列に動くボットは、その空間の中で一回以上塗ることが可能などこかにアサインされる。イメージとしてはエレベータなのだけど、その 3x3 の中心を下って上がって、途中で塗って返ってくる。 3x3 の中央は、ロボットが作業用なので、まだ塗っていない領域が下の方にある場合は底の蓋をしてしまわない。

この方針でたいていの問題が Flip 無しで塗れる感じになり、 3x3 のグリッドの作りかた9種類をそれぞれ試すと、どれかは Full Division の問題を解けるようになりました。

最初に間違った方針で時間を浪費してしまったこともあり、 Lightning Division 中には全部の問題にたいしてまともな点数の結果を返すことができませんでした。見積りをあやまったな、と。

Lightning Division が終わった後も、このコードはバグバグだったので、それを修正しまくって、一通りバグが取れて、一通り FA の問題に適用し終えて提出すると、 FA に対しては全て1位が取れている感じになっていました。潜伏していた人もいたかもですが、これが Lightning Division に提出できていればなあ……と残念。

さてこのエレベータの方針は、

  • 3x3 のエレベータのどれを優先するかという判断を何もしていない
  • さらに言うなら、 3x3 のうち、他の塗れる 3x3 が増える、つまり仕事が増える順序を優先するべきなのだけど、それをやっていない

という2点の TODO がありました。 Full Division のルールを検討するまでは、これは結構面白い課題だと思ってたので、是非やりたいなーとか思っていました。ですが、構築はそれなりにうまくいっているので、まだ実装してない解体を優先しました。最終的にもこれらの TODO は手つかずのままだった。

役割が無くなったボットは、とりあえず天井まで移動して、それから次に行きたい場所をアサインする、という流れだった。そういう感じでやると、当たり前だけど x=1 z=1 にいるやつは x=5 z=1 に移動しようとして、 x=5 z=1 にいる子が x=1 z=1 に移動しようとする、いわゆるデッドロックが頻繁に起きていた。これはまあ、定期的に全員が Wait を発行している場合、ランダムなタスクの担当者を入れ替える、という雑な方法で解決した。まあこの問題は頻繁に起きることではあるけど、しかしスコアに大幅な影響を与えるほどの問題ではないであろうとそのままにした。

解体して良いかという判断

解体は、構築と違って、この座標のブロックを消して大丈夫か…という判定が自明じゃないので、そこをまずあれこれと考えました。最終的に、近似的な方針でやることにした

  • 最初に地面から幅優先探索する
  • とあるブロック X に幅優先で辿りついた時、 X に同時に辿りついた元のブロック群が、ブロック X を支えている、と仮定する
  • ブロック Y を消して良いかを考える時、 Y が支えている全てのブロックをチェックし、そのいずれかが Y によってのみ支えられている時、そのブロックは消してはいけない

例えば

ABC
D
E

だと、依存関係は

A→B→C
↑
D
↑
E

となるので、Cしか破壊できないと正しく判定される。

ABC
DE
F

だと

A→B→C
↑  ↑
D→E
↑
F

なので、Cに加えて、AとEも、どちらかなら破壊して良い。何故ならBはその両者から支えられているから。

保守的になりすぎて消せるブロックを消せないと判定するケースがあって、

ABCDE
F___G
H___I

だと、どれを消しても大丈夫なはずだけど、Cしか消せないと判定されてしまう。

Void による解体

解体可能判定が上記で決まった後も、特に良いアイデアが無かった。よって、よく覚えてないけど、おおむね構築時の 3x3 に分配するアルゴリズムを使いまわす感じの、しょうもない実装で実現した。

解体時は構築時と違って、 Void によって移動範囲が減ることは無いため、あまり大変なバグは起きることはなくて、まあほどほどのタイミングでこれは完成した。ただ 3x3 に切っていくという方針はそもそも解体にとって良い方法ではないため(特に上述の解体可能判定が正しくないため)、かなり遅いものになってしまったという感じ。

感想戦twitter で見た方法として、解体は構築の逆再生をすれば良いというのを見て、なるほどこれをやっていれば解体について使った時間の多くの人的時間を節約できたなあ……と思った。

平面 GVoid による解体

明らかに構築に比べて解体で得ている得点がイマイチだったので、解体をもう少し考えることにした。

結果、解体は GVoid でまとめてやるのがやりやすく、依存解析をすっとばせる部分がたくさんあるのもあって、むっちゃいいじゃん、となった。とはいえ、 3次元 GVoid はこの段階では「管理大変そうだなあ…」という感覚があり、2次元 GVoid で上から順に切りとっていくソルバを作った。

これはコード量はおおくはないし、このソルバ自体は前述のソルバと違って全ての問題を解く汎用性はないけど、多くの問題に関しては前述のソルバを凌駕するものとなった。こういう、問題によって違うソルバが有効になる問題は一人チームだとキツいんじゃよーと思いつつ、だがうまくいったのでよしよしと思いつつ次へ。

最高記録管理、あるいはインフラ

今回一人チームきっっつい、と思った部分はいくつもあったのですが、一番きつかった部分でした。今回の問題の場合、単一のプログラムがベストの解を出す必要はなく、複数の似たようなプログラムがそれぞれ出した解の最高の物を提出すれば良い形式で、かつ、その最高の解が必ずしも最終バージョンのプログラムによって生成されている必要はない、という形式でした。

そのため、提出できる解のうち最高のものを管理し、かつその最高のものを越えた解があればそれでアップデートする必要がありました。これは2種類のめんどくさいタスクを追加しました

  • 開発中のシミュレータはおそらく正しくないため、現段階でのシミュレータで実行してみて、たしかに一番良い結果が更新された、と判断すれば最高記録として記録する仕組みを作りました。0点を取ると死ぬ今回のルールでは、これは安全で良いアプローチだと思うのですが、問題はシミュレーション自体が大変遅いものであったということでした。おかげで、常に「なんだかもう覚えてないけど、なんかの計算結果を(おそらくムダに)検証している、という状態になりました。
  • 3D モデル X を別のモデル Y に変換する、というタスク(FR)は時間が足りなかったこともあり、単純にそれが一番効率だと考えられたこともあり、 X を完全に解体してから Y を完全に構築する、という方針で解きました(たぶん他のチームもそうやっているかと思います)。これは X を解体する最高記録を残しつつ、 Y を構築する最高記録も残して、んでその二つの最高記録をマージしなきゃだということになります。めんどくさい
  • 当時の段階では、 FR なモデル(つまり解体&構築なやつ)は、ものによってはひょっとすれば解体+構築より効率的な実装ができるかもなあ……と思っていたので、解体+構築を同時にやるようなアルゴリズムが後でできるかも、という仮定の元、2日目寝る段階では、 FR は単に FA+FD をまとめてやる物を計算して寝たのでした。よって FR 解から FA 解と FD 解を切り出してきて、一番良い FA & FD を切り出す、というような余計なタスクが発生しました

などなどやってるうちに、結構な時間が溶けました。結果として、 FA+FD よりも FR を効率的に解く方法を考えられる問題はぱっと見見つからず、 FA+FD を効率的に解けることを期待したインフラも完全に無駄になりました。

今にして思えば、アルゴリズムで作った手順が、シミュレータで間違ってることは基本的に無いため、再確認は特にせず最高記録を更新する手順にすれば良かったなあ……と思う。

まとめて 3D GVoid

この段階でもう一度リーダーボードを眺めて、構築も解体もほどほどに良い解は提出できている(Flipも無いし並列化もされている)ので、特に「こういうタイプの問題で弱い」みたいなのは無く、単に全て弱いことがわかっていました。そこで、複雑な問題は再計算する時間が無いため、単純な問題に対して単純でかつ有効な解は無いか……ということを考えました。

すると、単純な問題での解体がイマイチな点数であることに気付いたので、あれこれ考えました。あれこれ考えた結果、単純な問題は問題全体を GVoid で消してしまえるのでは……と気付きました。

で、最初に8体に分裂して、全体を消して、終了、みたいなやつを作りました。あたりまえでしたが簡単な問題については劇的な効果がありました。今にして思えばこのロジックをさらに良くして、一回で消し切れない問題に対しても 3D GVoid を使う解を生成する価値があったと思っています。

たしかこれをやってるあたりでリーダーボードが凍結されました。

GFill を使ってみたい

このあたりで、「やりたいことは無数にあるけど、期間内で実際にやれて、かつスコア的に劇的に有効な手が思い当たらんなあ…」と思ってました。その結果、 GFill 使ってないのはムダすぎるよね、と思いました。

で……ごくシンプルな 1D GFill と Fill で解ける問題だけを解くソルバを作りました。序盤の方の問題はこれで全部解けるだろ……という気分で作ったのですが、実際見てみると壊滅的で、 FA 3問くらいの最高記録を更新できただけで終わりました……

まとめ

すごく楽しかった。まじですごかった(低語彙力)。問題をぱっと見た時に、「なるほどこれ俺もできそうだ」と思うにも関わらず、いざやってみるとすごく簡単なことですらクッソ大変、というのがすごく良かった。大変明確に動くヴィジュアライザなども用意されていた。

例年と比べてもノンゼロの点数が少なかったらしい。敷居が高かったのでは、という観測もあるみたい。ごくごく個人的な感覚では、今回の問題の敷居は高くなかったと思う。常に Flip on の状態で動く解が主催から与えられているので、その中にある移動命令いくつかをつなげるだけでノンゼロの点数は簡単に得られる。単に、今までノンゼロを得ていたチームの中でほとんど実質参加してなかった層が、自明なノンゼロ解を発見できなかった、もしくは ICFPC 自体の参加者が減っている、そのあたりが理由じゃないかなあ……と思う程度には、今回の問題は弱いチームに配慮されている問題だったのではないかと思う。

個人的には、 Full Division で追加されたルールは全て必要なかった。今思えば、全ての追加ルールが、単純にゲームをシンプルにする方向に変わった気がする。当初の問題で、勝てたかっていうと今よりもっとひどい負け方をしていると予想されるのだけど、ただどっちが楽しめたかっていうと、 GVoid/GFill の無いルールだったんじゃないかな。というか、最初に考えたエレベータ方針をもっときっちり詰めたかったな。

いやでもまじで当たり回だったとおもってますマジで

転職について

6月14日がグーグル最終日でした。8月からPFNに混ぜてもらう予定です。退職や入社も重要イベントなんでしょうけど、転職活動それ自体が大変に楽しい体験だったので、入社したからって突然次の会社についての知見にあふれているわけでもなし、このタイミングでなんか書こうと思いました。どうせ暇だし。

前回との差分

http://shinh.hatenablog.com/entry/2016/03/11/142748 が前回までのあらすじ。このちょっと後で、「ニューラルトランスレートすげー」とか思って Google Translate のチームに入れてもらって、自然言語/機械学習研究入門+プロダクショナイズ+TensorFlowまわりのあれこれおもしれーとか、その他いろいろをやってた、というのが現在との差分です。

機械翻訳というのは、他の機械学習応用分野と同じく、ニューラルさんによってすさまじく簡略化されてしまったとのことです。とはいえ、機械学習初心者が10年選手に囲まれている状態で、学ぶこともすごく多くて、咀嚼するより早く新しい話題が現れている感じで、まだまだやってみたいことあるな、という感じでした。

でもやめるという話

じゃあなんでやめるかというと、飽きたのでした。グーグルでは色々新しいことが起きてて、そういうのは楽しいわけです。最近だと Swift for TensorFlow とかすげー楽しいと思いました。グーグルの外だと X 社の A と Y 社の B と Z 社の C を組み合わせて……みたいな感じでやってることを全部自社で持ってるみたいなこと多いですしね。

じゃあ何に飽きたかというと、プロジェクトとかじゃなくて、環境に飽きたということかな、と思います。

グーグルというのはやはりすごい会社で、個々の技術的な判断もそうですが、プロセスなんかもすごく合理的にうまく回ってると思います。そしてそのプロセスを改善するメタなプロセスもうまく回ってる。例えば不満があるとしても、不満を集めてきて修正する方のレイヤが割とうまく動いてるので、同じ不満をずっと持ってる、ということになりにくい。

プロダクトとかも、全体で見ると成功しているプロダクトがとても多くて、なんかあのプロダクトは地味かな?とか思ってるようなものでも、話を聞いてみると他の会社だと大成功レベルでうまくいってるような感じだったりして。成功してるおかげで投資がなされて面白プロジェクトが次々に出てくるし、自分自身はぱっとしないことやってても高い水準の給料が出る。

で、それらはすごくいいことなんだけど、なんかそういう良い環境に飽きてしまった。飽きたってのは単純な話で、単純な話だけに対処法が特に無い。しかも良い環境であることに飽きたという感じなので、どうしようもない。居心地いいからと言って11年もいたのは長過ぎでした。

というわけでグーグルはいい会社だと思います(言わされてるわけじゃないよ!)。辞める私が言うのもなんですが、おすすめ。

就職活動楽しかったという話

書きたかったのはこっちでした。人生初と言っていい就職活動がとても楽しかったんです、悩ましくもあったけど。

他の会社が何をやっているか、自分にあう仕事があるかなど、ハタから見ててもよくわからないので、気になる企業はサイトに書いてある連絡先から応募していきました。あと普段無視してるようなエージェントや会社の人事からのメールにも返事して、色々と対応していただきました。たくさん受けても一社以外行けないわけで、冷やかしみたいで失礼かなぁ……とも思ったのですが、まぁそんなしょっちゅうすることじゃないので許してもらおう……と考えることにしました。

知人がいる会社もあったので、そういう人に口を聞いてもらうという手もあるのかもしれなかったのですが、なんだか断りにくくなりそうなのでやめておきました。採用プロセスを実際に見た方が、未来の同僚がどういう方法で採用されるかを推測できるというメリットもあるな、とも思いました。かわりに、知人がいる会社では最初の面接時に「ご飯でもどう?」と声をかけてみたりもしてみました。

で、面接に行ってみるとすごく楽しいのでした。普通にオフィス見学に遊びに行っているのと違って、会社でやってることについて細かく説明をしてもらって、私が入社するとするとどういう仕事がありそうか、などに突っ込んで聞けるので。そういう突っ込んだ話をしていると、とても勉強になる。グーグルの X に対応するものは Y でこういうふうに使っているんだなぁ、とか、グーグルだと基本 B2C だけど B2B だとこういう感覚なんだなぁ、とか。

聞く話は大変面白そうな話が多くて、なんだそれ面白そう俺も混ぜろ、と思って毎度面接の後は「よしここにするかー」みたいに思ってるというような状態になりました。まぁ流されやすいのもあると思いますが。最初の頃は「グーグルには満足してるけど、もし面白そうな話が一つくらいあれば……」くらいの気持ちだったんですけど、これだけ面白い話があるなら、「どこかには転職するだろうな……飽きたし。あと転職活動に費した労力がもったいないし(サンクコスト)」、という気分になっていきました。

複数社から楽しそうな話を聞けたのは本当に嬉しい誤算でした。感じたこととして

  • 人々が普通に楽しそう。10年前だと「エンジニア中心の会社です!」みたいな広告がなされてた気がするんだけど、もうそんなことは割と自明になってしまっている
  • 小さい会社が普通にテクニカルな意味で(私の興味基準で)すさまじく面白そうなことをやっている
  • お金も割とちゃんと出そう

体感ですが、10年前だと上のうち1つ満たす会社はあるけど、5年前くらい前までは2つ満たすのも難しかったのでは、と感じました。なんかいい時代になってるんじゃないかな、と思いました。AI系の会社に関してはAIバブルのおかげとかもありそうですが。

一方で、「どこも楽しそー」となってしまうと、候補を減らしていくのが大変でした。各社、楽しい議論を時間を割いて一緒にしていただいていただけに、断るのがとても心苦しくて。

最後、数社でどうしたもんか……と、今までこんなに悩んだことあったかなーというくらい考えました。結局なんで PFN のオファーを受けようと思ったかというと、いろいろあるけど、 PFN が一番うまくいかなさそうな気がしてきたからでした。良く言うとゴールが高いということもあるかと思います。うまくいかなさそうというか、「この会社どうなるんだろ?」と素直に疑問というか、良く言うとわくわくするという感じかもしれないです。

PFN より規模の小さい会社もいくつか候補にあって、割と高確率でうまくいくと思っていたので、会社が成功すると株とかで一攫千金!みたいなのはとても魅力的だったし、「もったいないことしたかなー」とも思っています。まぁでもグーグルで一番楽しかったプロジェクトはうまくいかないと思いつつ入って、実際にうまくいかなかったやつなんですよねえ(不吉)。

あとなんか、よく言われることですけど、採用とかはどっちから見ても縁というかタイミングというかですね。もう数年前だったら、もう数年後だったら、それぞれ違うところに行ってた気がします。実際、今回も他の会社のオファー受けかけたりもしましたし。なんにせよもう少し頻繁に転職とか考え(る|られる)べきだな、と思いました。

最後に、今回応募させてもらった会社の対応してくださった方々にとても感謝しています。色々と今まで考えてもなかった視点を持てたように思います。ありがとうございました。

まとめ

  • グーグルいい会社だけど11年は長すぎた
  • 転職活動楽しかった。おすすめ
  • 8月まで暇なんで遊んでください

MJIT で dlopen 使わずに ELF オブジェクトを直接ロードする話

MJIT というのが Ruby に入ったのは聞いていて、すごいことするな、と思ってたんですが、実際に Ruby Kaigi で話を聞けて少し遊んでみたくなったのでした。そういえば https://turingcomplete.fm/5 の時に「MJITについてどう思うか聞いておいて下さい」とかリクエストしておいたのに聞いてくれなかったのであった。

https://k0kubun.hatenablog.com/entry/ruby26-jit

すごいことするな、と思ったのはその手法で、 C 生成して dlopen という、よく雑談とかで言う話ではあるけど、実際広く使われる用途で使われたのは見たことが無かった(ICFPCとかでは見たことがある)ので、すごいなと。

一方で、 dlopen たくさんすると、いくつかの意味でオーバヘッドがかかると思われるため、あとでマイクロベンチに出ないところで大変だったりするだろうなぁ……特にメモリのローカリティ的な、とか思いつつ聞いていると、やはりメモリのキャッシュヒット率が減りはじめると悪い影響が……という話になりました。一つ一つの C レベル関数は恐らく小さいのではないかな、と思っていたので、コードサイズにして例えば 100-1000 バイトくらいの関数のために、 dlopen すると少なくとも必要であろう r-x の .text ページと GOT のための r-- (or rw-) のせいで 8192 バイトを使うことになるのではないかなぁ……と思っていたのでした。

Ruby Kaigi 中に質問したのですが、「一つの関数ごとに最低 8 or 12kB 使うかな……」と思っていたところに「2MB/method!」みたいなスライドを見て、なんじゃそれと思ったからでした。あとで スライド をよく眺めると、 .text と .rodata の間のいじれないやつもカウントしてただけと気付きました。 2MB の仮想アドレスを取っちゃうのもどうなんだって話はあるかもしれないですが、それより3つのページに分割されるのが本質的な問題だと思います。かつ、 MJIT の吐いてるコードを見る限り .data と .rodata は使わなさげなので、実際に触るページは .text 用のやつと .got のやつで2枚だけでないかと思います。

さて、この問題についての正しい解決策は、適切な単位で複数のメソッドをまとめてコンパイルする、というものじゃないかと思います。でかつそれは提案されていた手法なので良いと思います。とはいえ .got のために .so 一つごとに無駄に 4kB 使うというのもなぁ……などとも思います。で、 .got と .text をまとめて同じページに突っ込んでくれそうなリンカオプション無いか……と探したり(なかった)、そもそも RELRO て .got を RX にすることできるの……とローダ眺めたり(できなかった)しました。

なーんていうことを考えてから、とりあえずムダをはぶくだけなら .so をローダに読ませるのではなくて、 .o を自力で適当にロードすればいいよね、ということで、そういうものをでっちあげました。

https://github.com/shinh/ruby/tree/objfcn

まあ……使いやすいものではないと思います。本質的に MJIT のような .so を読む以外の手法で書かれた JIT エンジンにある問題ですが、やはりデバッグは大変ですし、自分でちゃんと空いたメモリを解放するとかも面倒ですし(現状1GB固定アロケートするモードと遅い方法)、まあそんなこんな……

ただ、 C コード吐いてコンパイルしてロードする、って方針が変わらないのであれば、ロードに関しては最速な方法だと思うので、もっと適切な方法であろう、複数のコードをまとめてコンパイルする、という方法で理論限界に近付いてるかどうかは、私のコードと比較すれば評価できるのではないかと思っています。

あと最初にがーと書いたコードは2つクラッシュするバグがあって、それぞれなるほどなあと思ったので書いておきます。

一つ目は mmap を前もってする際に PLT/GOT のために生成するコードのサイズを計算に入れてない、というものでした。これは tinycc の時もどうしたもんかと思った記憶がありました……

二つ目はセクションヘッダに指定されてるアラインメントを適切に取っていない、というものでした。具体的には SSE 命令で data 領域を読んだりするコードの SSE アラインメントが壊れてる、という話でした。なんか低レイヤなとこいじってると SSE アラインメントは必ずバグりますね。スタックがアライン取れてない状態で printf 呼んで死んだりとか……

とりとめもないですが、こんな方法を MRI で採用すべきとは思ってないのですが、ただこの手法の JIT エンジンの持つ、いくつかあるオーバーヘッド源の一つであろう、メモリがページ境界で分断されてしまってローカリティが良くない、というやつがどのくらい悪さをしてるかの評価程度には使えるのではないかと思っています。

clearstackの話

https://turingcomplete.fm/19#t=26:39 で僕のやったことに言及してくれて、「使ったスタックを消すなにかを浜地が作ったが、それは全く公開されていない」という趣旨の事が言われていました。でも実際のところなんか書いたけど、単に誰も興味を持たなかったというだけのことでした。

http://shinh.hatenablog.com/entry/20130728/1374990526

実際はclang pluginで、かつすごく適当にでっち上げただけで、効率は完全度外視だし正しく動いてるんだかもよくわからない、って感じでした。クラッシュはしなかったくらいの何か。当時の記述はすごい適当ぽいので、2点書いておきます。

当時のモチベーション

保守的GCが「やや病的なケースでポインタに見える整数値の参照先を残してしまう」てのはよく聞くわけですが、Rubyのバグかなんかで見たのは違うケースで、実際に過去にポインタだったが、もう使ってないマシンスタックに残ってるものが解放されない、というような話でした。

具体的にCレベルで考えると、VMのループてのはおおむね

switch (op) {
  case OP_X: {
    VALUE x = ...
    なんかする...
  }
  case OP_Y: {
    VALUE y = ...
    なんかする...
  }
}

とかそういう感じになっているわけです。ここで VALUE てのは tagged-pointer ですが、まあ要はポインタです。 VALUE x とか VALUE y ですが、少なくとも当時の GCC は x と y を同じスタックに割り付けるということはせず、かつ VM ループを処理する関数が結構複雑な関数だったこともあり、かなりのローカル変数がレジスタだけでは処理できるずスタックに割り付けられていたと記憶してます。実際手元で vm_exec_core を見てみると

0000000000015050 <vm_exec_core>:
   15050:       41 57                   push   %r15
   15052:       41 56                   push   %r14
   15054:       41 55                   push   %r13
   15056:       41 54                   push   %r12
   15058:       55                      push   %rbp
   15059:       53                      push   %rbx
   1505a:       48 8d 1d 00 00 00 00    lea    0x0(%rip),%rbx        # 15061 <vm
_exec_core+0x11>
   15061:       48 81 ec 28 01 00 00    sub    $0x128,%rsp

とか言ってまして、296B のマシンスタックを確保しているわけです。

でもまあスタックが上がったり下がったりしてれば、そのうちマシンスタックは適宜再利用されて、たまたま残ってた VALUE とかも消えたりすると思うんですが、その時問題になってたと記憶しているのは

def init_server
  ... なんだか複雑な処理をして初期化をして、 serving に必要なデータを集めてきて、
  ... データの大部分は捨てるが serving に必要なものだけを残す
end

def execute_server(sock, data)
  while true  # 二度と戻らない
    ... serving する
  end
end

def run_server(data)
  sock = ...ソケットとか作る
  execute_server(sock, data)
end

data = init_server
run_server(data)

みたいな、単純化するとこういうケース。 init_server はなんだか複雑な処理をするので、マシンスタック上に不要になってるはずのポインタを残し、 run_server は init_server とは別のマシンスタック領域を使ったためにそのポインタが残っていて、それで execute_server 呼んじゃうので、 init_server のためのマシンスタックは未来永劫初期化されない、というような。

当時はやや場当たり的に、Rubyのこの部分を別の関数に分離したらよくなったよ、とかそういうことが報告されていました。現段階でどうなってるかは知らないです。

Boehm GC

は、この手のスタックに残ったポインタを定期的に適当なヒューリスティクスと乱数的なタイミングで消すってことをやっていたと思います。たぶんこれ

https://github.com/ivmai/bdwgc/blob/master/misc.c#L332

スタックが頻繁に上がり下がりしてるようなプログラムではすごく有効なはずで、なるほど GC というのはミューテータのアクセスパターンにひどく依存する難しいものだなぁと思った記憶があります。ミューテータ依存というと、他にはコンパイラとかも GC 泣かせだと聞いたことがあります。最初にがばっとメモリ確保して、その部分はあまり解放しないけどその後も確保と解放が続くとかなんとか。まあそれは世代別が緩和しそうな話ですね。

もとの話に戻して適当なタイミングでスタックを綺麗にする緩和は、当然ながら現在のスタックポインタより深いところにあるスタックは消しちゃいけないので、さっきの Ruby の例のように、マシンスタックの金輪際書き換えが起きない部分に残ってるポインタライクなものに対しては無力なのです。

いう2点がモチベーションだったと思います。

ビット演算クイズを解いた時の話

http://herumi.in.coocan.jp/diary/1804.html#13

を解いた時の話。光成さんは実験的に解かれたようだったんですが、割と理詰めで解けたので、思考過程をダンプしてみます。元のコードは

int calc(int a, int b, int s) {
    const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
    assert(0 <= s && s <= 16 && && 0 <= b && b < a && a < Q * 4);
    int n = 0;
    for (;;) {
        if (a < Q2) {  // A
            n = n * 2;
        } else if (b >= Q2) {  // B
            n = n * 2 + 1;
            a -= Q2;
            b -= Q2;
        } else if (b >= Q && a < Q3) {  // C
            a -= Q;
            b -= Q;
        } else {  // D
            break;
        }
        a = a * 2 + 1;
        b = b * 2;
    }
    return n;
}

という感じ。

ビット演算はゴルフと似たところがあって、まず「このコードはもっとシンプルにできる」と信じ込む必要があって、これが結構難しいと思います。今回はクイズという形で出題されたのでこの点はクリアされてて、シンプルになるという確信が無いのにたどりつかれた光成さんはすごいなあ……と思います。

しょうもない書き換え

とりあえず真ん中の4分岐 (以降上から ABCD と呼ぶ) を減らしたい。とりあえず上2つを削るとすると…と考えて

int calc(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    if (a < Q2 || b >= Q2) {
      n = n * 2 + ((a & Q2) >> (s + 1));
      a -= a & Q2;
      b -= a & Q2;
    } else if (b >= Q && a < Q3) {
      a -= Q;
      b -= Q;
    } else {
      break;
    }
    a = a * 2 + 1;
    b = b * 2;
  }
  return n;
}

という感じになった。2つの分岐を一緒に扱って、 a & Q2 が 0 なら分岐A、 0 で無ければ B という感じで分けてみた。とかやってると3つ目の分岐も結局 a, b の値域がちょうどいいところ (Q = 1 << s の倍数の地点) で分岐してるわけで、整理してみるべきだな、と思う。

分岐を整理する

a も b も常に 0 以上でかつ Q*4 以上になることはない。分岐は Q より小さいか、 Q*2 より小さいか、 Q*3 より小さいか、だけで行なわれてるので、分岐に対して a と b が持ちうる状態はそれぞれ4つ。 a/Q を an として b/Q を bn として、分岐 ABCD のどれを選ぶべきかを整理すると

bn\an 0 1 2 3
 0    A A D D
 1    N A C D
 2    N N B B
 3    N N N B

となる。 N というのはありえない組み合わせで、これは常に b < a であることから。まず D の分岐はループを止めるという特殊な動作をするので、先に処理してやる。この条件は少し考えると

  if (an - bn >= 2)
    break;

でうまくあらわせる。 D を忘れてよいという気持ちで上の表を眺めると、分岐 ABC はもっとシンプルに a と b がそれぞれ Q*2 より小さいかだけで表現できる。 a/Q/2 を ab として b/Q/2 を bb とすると

bb\ab 0 1
 0    A C
 1    N B

これだけの話だ。 ABC それぞれの分岐で起きるべき変化で共通でないものは

  • A: n = n * 2
  • B: n = n * 2 + 1 ; a -= Q * 2 ; b -= Q * 2
  • C: a -= Q ; b -= Q

n から考えていくと、 n を 2 倍しなければならないのは A, B のケースでこれは (ab ^ bb ^ 1) で表現できる。その後 n に 1 を足さなければならないのは B だけで、これは単に bb で良い。というわけで n は以下のように分岐なく処理できる。

  n <<= ab ^ bb ^ 1;
  n |= bb;

a, b は A, B, C の時にそれぞれ 0, Q * 2, Q を引けば良い。なんとでもなるけど Q << bb で B の時だけ Q * 2 にすることができて、 (Q << bb) * ab とかすれば A の時だけ 0 にすることができる。というわけで a, b の変化は

  int sub = (Q << bb) * ab;
  a -= sub;
  b -= sub;

などとシンプルになった。以上まとめると

int calc_mine1(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    int an = a >> s;
    int bn = b >> s;
    int ab = an >> 1;
    int bb = bn >> 1;

    if (an - bn >= 2)
      break;

    n <<= ab ^ bb ^ 1;
    n |= bb;
    int sub = (Q << bb) * ab;
    a -= sub;
    b -= sub;
    a = a * 2 + 1;
    b = b * 2;
  }
  return n;
}

ループ内の分岐は無くなったけど、まだこの計算の本質がなんなのかとかがわかるような形ではない。もうちょっとシンプルにしないとなあと考える。

状態遷移を把握する(より道気味)

an, bn の組み合わせが10種類あって、うち3種類はループから脱出するけど、残り7種類はもう一回以上ループすることになる。それぞれの状態から、次の an, bn が何になるかを考えてみる。というのは、 an, bn になされてる演算は Q か Q*2 を引いてから2倍なり2倍プラス1する、ってものなので、割とシンプルな状態遷移をするはずなんです。

分岐 A は a, b を2倍なり2倍プラス1するだけなので、遷移前の an か bn が 0 なら次の an/bn は 0 か 1 になり、遷移前の an/bn が 1 なら次の an/bn は 2 か 3 になる。

分岐 B は2倍する前に Q*2 を引くので、 an/bn が 2, 3 ならそれぞれ 0, 1 に変換してから、分岐 A と同じ遷移をする。

分岐 C は an == 2 かつ bn == 1 の時だけ。まず Q を引くので、 an == 1 かつ bn == 0 になってから 2 倍なので、 an は 2, 3 のどちらか、 bn は 0, 1 のどちらかになる。

まとめると

  • <元のan>, <元のbn> => <次のanの候補>, <次のbnの候補>
  • 0, 0 => (0, 1), (0, 1) (A)
  • 1, 0 => (2, 3), (0, 1) (A)
  • 1, 1 => (2, 3), (2, 3) (A)
  • 2, 2 => (0, 1), (0, 1) (B)
  • 3, 2 => (2, 3), (0, 1) (B)
  • 3, 3 => (2, 3), (2, 3) (B)
  • 2, 1 => (2, 3), (0, 1) (C)

うーん、だからどうした?と思うのですが、 (2, 3), (0, 1) に遷移した場合、 C の分岐に入るかループ終了の2択で、かつ C の分岐は (2, 3), (0, 1) に遷移するので、一度 C に入ると出てこない、ということがわかります。

さらに都合が良いことに、 C は返り値であるところの n を変更しないので、なんのことはない、 C は D 同様即座にループを出て良いということがわかります。となると分岐のテーブルは

bn\an 0 1 2 3
 0    A A D D
 1    N A D D
 2    N N B B
 3    N N N B

で良いことがわかって、これは ab/bb だけで十分に表現できるので

bb\ab 0 1
 0    A D
 1    N B

と最初からこれだけやれば良いとわかります。

分岐Cを消す

以前のコードから C の分岐用のコードを消していきます。まずループ終了条件

 if (an - bn >= 2)
   break;

は、 ab != bb の時に終了すれば良いので、例えば

  if (ab ^ bb)
    break;

となり

  n <<= ab ^ bb ^ 1;
  n |= bb;

は、 n は 常に 2 倍すれば良く、2行目はそのままで

  n <<= 1;
  n |= bb;

となり、 a, b については

 int sub = (Q << bb) * ab;
 a -= sub;
 b -= sub;

だったのですが、単に B の分岐の時だけ Q * 2 を引く、としたいだけなので

 int sub = (Q << 1) * ab;
 a -= sub;
 b -= sub;

とすれば良いです。まとめると

int calc_mine2(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    int ab = a >> s + 1;
    int bb = b >> s + 1;

    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
    int sub = (Q << 1) * ab;
    a -= sub;
    b -= sub;
    a = a * 2 + 1;
    b = b * 2;
  }
  return n;
}

a, b に起きていることを考える

 int sub = (Q << 1) * ab;
 a -= sub;
 b -= sub;

について考えると、 B の分岐の時だけ Q * 2 を引いていて、 B の分岐というのは a, b が共に Q * 2 以上の時であり、そうでない時、つまり A の分岐というのは a, b が共に Q * 2 より小さい時です。

となるとここでやってる処理というのは、 Q * 2 が 1 << (s + 1) であることを思い出すと、 Q * 2 - 1 でマスクを取る、つまり下位 s bits より上の bit を捨てているだけです。つまり

  const int QM = (1 << s + 1) - 1;
  a &= QM;
  b &= QM;

まとめると

int calc_mine3(int a, int b, int s) {
  const int QM = (1 << s + 1) - 1;
  int n = 0;
  for (;;) {
    int ab = a >> s + 1;
    int bb = b >> s + 1;
    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
    a &= QM;
    b &= QM;
    a = a << 1 | 1;
    b = b << 1;
  }
  return n;
}

というようなコードです。

ループいらなくね?

上のコード、 a と b に対して、 s + 1 bit 目の値によって分岐して、 s + 1 bit 目を捨てて、 2 倍してる。要するに上のビットから順にチェックしていってるだけなんで、 a, b をいじくる必要は全くないです。例えば

int calc_mine4(int a, int b, int s) {
  int n = 0;
  for (s++;; s--) {
    int ab = (a >> s) & 1;
    int bb = (b >> s) & 1;
    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
  }
  return n;
}

としても良い。 ab ^ bb は a > b という条件から、必ずどこかのビットで 1 になるはずなんで、終了条件はこれで良いです。で、こうなっちゃうと「n は ab と bb が共通してる限りビットを上から立てていって、 ab と bb が異なった時点で終了」というものなので、 ab と bb が異なる地点を探して、そのぶん a を右シフトすれば望みのものが得られる……ということで

int calc_mine(int a, int b, int s) {
  return a >> (32 - __builtin_clz(a ^ b));
}

となります。 __builtin_clz は左から0の数を数えるやつです。

お天気プロコンと圧縮アルゴリズムについて

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なアプローチを最初から指向していた(そしておそらく大失敗していた)ように思います。何故失敗するかというと、この手のマラソンでは最終的には一般的すぎる解より人間全力チューンが勝ちがちという経験則があるからです。ただ実際問題としてパラメータ増えすぎてコード整理や調整をしきれなかったという面があって、実際最後の方はパラメータ調整だけが実質的な伸びしろだったので、反省点とも言えます。

まとめ

楽しかった、勉強になった、しかし本当に悔しい

Deep Learning Acceleration 勉強会

https://connpass.com/event/64632/

すごく面白かった。最近こういう会に行って感心することは多いのだけど、しかしなんか書きたいと思うレベルになかなか来ない、まあそれなりに年喰ったしな、とか思ってたんですが。低レイヤとか、自分がある程度既に知ってるところの話を聞くのも楽しいけど、自分が最近勉強してて理解しはじめたことの話を見聞きする方が楽しいよねえということかと思いました。まさににわかほど語りたがる現象で、実際懇親会とかで間違ってること結構言ってそうな気がする。

ジャンルとして、他のCSのジャンルとかと違って、深層学習はとにかく論理的に確定できない話が多くて、あの論文はあやしいなあ、あれは説得力あるなあ、というような、口コミベースの情報が回してる面が、良くも悪くもあるのかなあ、という印象を持っています。

つーわけで口コミレベルの適当なことを、以下、書きます。(定型句)間違ってることが普通にいっぱいあると思います。(定型句)所属企業とは関係なく勝手に書いてます。定型句と書いたけどグーグルとしての感想では本当にないです。ちなみに僕はRNNしかいじったことないです

モデルアーキテクチャ観点からの高速化

僕はこれとても興味があったドメインだったので、早速すごい俺得と思いながら聞いてました。 factorization, squeeze, pruning とかの話の一部は自分でも試したことがあったのですが、自分のやった範囲ではうまくいかなかったという感想です。僕なりの考えを箇条書きにすると

  • このジャンル、まずトレードオフを明確にするべき(こういうのはハードウェアとかの人の方が得意であると思う)
  • 少なくとも、クォリティ、学習スループット、推論レイテンシ、の3値があることは考えるべきで、どれか1つを狙うアプローチを他と混同すべきでない
  • もちろん上記3つ以外にもいろいろ考えることがある。例えばパラメータサイズは学習推論両方のメモリ使用量に効く、とか
  • あとこの発表はメインのターゲットはCNNだったと思う。CNNは正直よく知らないので間違ってたらホントすいません
  • conv WxH を factorization で別のに落とす、てのは意味的に別モデルを作ってる感があって、他のFCやらRNNでやるfactorizationは同じモデルだと思う
  • RNNだとfactorizationは悪くなるという印象。パラメータの数も減るし学習も早くなるのだけど、少なくともRNNだとembeddingの後の次元はほぼ完全に自由に決められるので全体の次元を落とすことは簡単で、それで同じパラメータ数で比べると余計なことしない方が計算量的に有利だった
  • なんかこの手の論文見てると正直、単にデータに対してパラメータ数過剰な状況で学習したモデルをベースラインとして、それに対して工夫するとクォリティ落とさずにパラメータ数減らせましたよ、というのがあると思った印象があります。そういうもののいくつは特に工夫しなくても単にオリジナルのモデルの次元を落とすだけでもっと効率良くパラメータを減らせるものがある印象
  • ただCNNてそんなに簡単にパラメータの数調整できるのか知らないので(画像サイズとかに依存するのかなと思いつつも単に平均色出してりゃいいんじゃねえのという感もあり)知らんす
  • この手のやつでは distillation の汎用性が高いという印象
  • 正解データも一緒に入れるという話があるのだなあと知りました。過学習しそうというイメージがある

Convolutionの数理とアルゴリズム

なんかこの人すごい人だなあとなんとなく思ってたけど、なんかその思いが強くなった。数学強い人無条件に尊敬しちゃうよね。。。大学で数学で絶望していった時の感じ

まあまあマジメに聞いてたつもりだけど、正直きちんとわかってなかった。FFTに関しては、まあその場ではわかってないのだけど、「これはFFTするとこうやってオーダーが落ちますー」なるほどー、というのを数回やってるので、「もうなんかかけ算が足し算に変わるんやろわかったわ」、くらいでゴマかせました。中国なんとかは聞いたことあるけどはてさて、という感じだった

ウェブブラウザ向け深層学習モデル高速実行フレームワーク「WebDNN」

これはもう本当にプロジェクトのモチベーションが完全に正しいと思ってます。トレーニングしたグラフとモデルをさっさとデモできる環境がある、てのは完全に正しいモチベーションだと思う。

しっかしこんなのいくつかあるDNNプラットフォームの最大公約数を探してどうこうするのたいへんだよなあ(つまりTFで書こうがChainerで書こうが同じグラフIRに落ちてるという理解)…と。ぼんやり僕が唯一知ってるTFまわりをながめてると、 tf.while_loop の対応が無さそうだなあ、と思って聞くと、無いのは TF の設計思想のせいであると。すいませんという感じであった…

そういえば、最適化の方について結構語られてたけど、後で雑談した時は、もっとフロントエンド側に力を入れるべきというようなことをおっしゃっていたように思って、それもまた正しいなぁとか思いました。多少は遅くてもいいから、あまりいじらずに動く方が嬉しい、というか。

Using Raspberry Pi GPU for DNN

このひとゴルフ以外の話もすんですねえ…と思いました。しかしスキの無い簡潔十分な発表。僕が遊んだことがあるものでは、CellのSPEに近そうだなあとか思いました。

しかしラズパイの重要性をわかってない僕にとっては、うーんゴルフがんばったんだろうなーくらいの感しかなくてすいません。まあこの業務たまにやるぶんには楽しそう

TensorFlow XLAの可能性

この発表が僕的には目玉でした…というかXLAてのは正直社内でもかなりよくわからんので、誰かざっくり解説書かないかなーと思ってたら発表者の方が別の資料で説明を書かれていたというのもあり。

とはいえさすがに一応知らない話はあまし無かったような気がする。TF時代に入れたけどXLAになると使えなくなったりするのがあったりするのが微妙ではありますね。

今まではTFグラフをStreamExecutorていうタスクランナーで動かしてた。visitorパターン的な感覚で巡回してOp::Compute関数を実行してまわる感じ。

XLAだとグラフの一部なりグラフ全体なりをvisitorパターン的に巡回して、今度はOp::Compile関数を実行してコンパイルして、ノード群をコンパイルしたものに変えた上でStreamExecutorで実行する、て感じだと思う。

Googleが開発したニューラルネット専用LSITensor Processing Unit」

一応つきあったことがあるというか現在進行形なので、言いにくいなあとかなんとか。とりあえず何喋っていいかはっきりしたのはありがたかった。

ChainerMN による分散深層学習

個人的な感覚だけで喋るなら、非同期学習オワコンは割と観測範囲の強そうな人たちが同期でいい感があると言ってる感があります。もっと言うならなるべくなら分散すらしたくないという雰囲気もあるような気がする。

後で話していたのですけど、分散すると弊社の場合、コンテナがある程度制御してるとはいえ、同じマシンで動いてる他のタスクの影響がどうしても出てしまって、同期+分散は遅いやつに性能がひっぱられがち、ということはあるとも思います。

TFが遅いとディスられてて、最初は使いかたが難しいせいかな?と思ったけど、まあそもそもTFのオープンソース版インターコネクトとマトモな感じじゃないよね、て話を思い出しました(たぶんgrpcを使っていて、この用途ではオーバーヘッドが許せる量が無いと思う)。

まとめ

まあとにかく勉強になった。なんか翻訳チームにうつってから1年ちょいたって、さすがに右も左もわからんということもない感じではあるけど、まだまだにわかほど語りたがる感じの状態です。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h