右上➚

プログラミングに関するメモをのこしていきます

"Applying Deep Learning To Airbnb Search" を読んだ

[1810.09591] Applying Deep Learning To Airbnb Search を読んだときのメモをそのまま出してみます。面白かった。 本当にメモなので、詳細は原文を読んでください。

airbnb の search ranking に deep learning を導入していく過程を論文っぽくしたもの。

おしゃれなモデリング手法の提案とかじゃなくて、現実の問題に対して NN を適用していくにあたって発見した良かったこと・悪かったことについてまとめた文章になっている。

Motivation

もともと Gradient Boosted Decision Tree でやっていて結構うまく行っていたが、gain が停滞してきたのでそれの突破口を探していた。

Model Evolution

評価指標は NDCG (Normalized Discounted Cumulative Gain) を使っている。

f:id:agtn:20181121214034p:plain

"Convolutional Neural Networks for Visual Recognition" を書いた A. Kaypathy が "don't be a hero" と言っている(複雑なモデルを扱えると思わないほうがいいよ、みたいな意味?)が、"Why can't we be heroes?" と言いながら複雑なモデルに爆進したらしい

その結果、無限に時間を持っていかれて全然うまくいかなかった。

結局、最初に production に入ったモデルはめちゃくちゃシンプルな NN だった。

a simple single hidden layer NN with 32 fully connected ReLU activations that proved booking neutral against the GBDT model.

入力や目的関数も GBDT と全く同じにしている。(booking するかしないかの L2 regression loss)

ものすごく gain があったわけではないけれど、NN が production でうごく、live traffic をちゃんとさばけるという pipeline を整えるためにこの step 自体は良かったと言っている。

やりすぎないことで先に進むことはできたが、すごくよくもなっていなかった。つぎの breakthrough は LambdaRank + NN を組み合わせたことだった。LambdaRank は Learning to Rank のアルゴリズムで、簡単にいえばロス関数に直接評価指標(ここでは NDCG)を組み込める(ここまでは learning to rank 的なアプローチはまったく取っていなかった。単にクリック率をよく予測し、それを上から出すことで NDCG を最適化していた)。

これらをやりながらも Factorization Machine と GBDT は research を続けていて、NN と comparable な成果が出せることはわかっていた。comparable な成果が出ている一方で出力される list は全然別物だったので、組み合わせたらもっと良くなるのではということで、FM や GBDT の結果を特徴量に含む NN を学習させて利用することにした。

f:id:agtn:20181121214010p:plain

この時点でもうモデルの複雑さは結構なものになっていて、機械学習の技術的負債問題が顔をだしつつあった。そこで、 ensamble などをすべて捨てて、単に DNN を大量のデータ(いままでの 10x)で学習させるというシンプルな解法に舵を切った(DNN とはいえ 2 hidden layers)。入力の次元は 195 次元、1st hidden layer = 127, 2nd = 83 というモデル。入力の特徴量はシンプルなもので、価格、アメニティ、過去の booking 数、などなど。ほぼ feature engineering をせずに入力した(これが DNN にする目的だった)。

Failed Models

失敗についても言及してくれていてすごく嬉しい。

  • ID を使ったモデルは過学習がひどくて使えなかった
    • 扱っているアイテムの都合上、ある ID に対してたくさんのデータが取れることがない
      • どれだけ人気でも年間 365 までしかコンバージョンしない
  • 詳細ページへの遷移は booking よりはるかに多いし dense なので、それを使うモデルも作ったがうまくいかなかった
    • multi task 学習で、booking prediction と long view prediction を予測させた

あとは NN は特徴量を normalize したほうがいいよねとか、特徴量の distribution を観察しましょうとか、Java 上で TensorFlow のモデル動かすの大変でしたとか、いろいろ現実っぽい話が並ぶ。 もっといろいろ言ってるけど、詳細は本文を読んだほうが良い。

画像とかじゃない領域で DNN を production にいれるにはこういうステップを経るんだなというのが伝わってくるし、この話から得るべき学びがかなりある。光景が目に浮かぶ良い文章だなと思いました。

個人のメモ・ノートを保存するサービス選び

Dropbox Paper と Google Keep を併用してメモとかを取っていた. 長期的な記録とか人に見せうるもの,長めの文章は Dropbox Paper に, 一時的なメモとかリマインダ的なものは Keep に, と使い分けていた.

Dropbox Paper すごく好きだったんだけど,

  • なんか重い気がする
  • WYSIWYG なので markdown で書いているつもりでもちょこちょこ変なことが起きる
    • バッククオートをおした時の挙動とか
  • ブラウザでしか開けない

というのが使いにくく感じてしまった. 基本的にグループで使うものだと思うので,僕は使わない機能がいっぱいあるなぁという感じもした.

Keep は Keep で好きだし,使い分ければそんなに嫌なこともなかったので続投したい. その上で,長期的に残しておきたいメモやノートを書くサービスを探してみた.

ほしい要件

  • markdown で書ける
  • 端末間同期
  • 画像を D&D で貼れる & 保存できる
  • グループ分け.ディレクトリを切るくらいの機能で十分
  • Archive
  • 検索
  • ブラウザ以外のアプリケーションとして閲覧できる
    • 別に Electron でもなんでも良いけど,ブラウザとは独立したアプリケーションとして動いて欲しい
  • mobile app
  • 細かい一時的なメモを取るのは keep.google.com でやる
  • ToDo もいらない

比較

Dropbox Paper

Pros

  • サービスの大きさ・信頼性
  • markdown + WYSIWYG なエディタであること
  • 人にパッと見せられるくらいキレイにメモがとれる
  • presentation mode(個人で使ってたらあんまりいらないかも)

Cons

  • 重い...
  • WYSIWYG であること
  • ブラウザでしか開けない
  • markdown で書いているのに markdown として export すると微妙に modify されている...

Google Keep

Pros

  • さくさく
  • シンプル
  • リマインダとの連携とか

Cons

  • 長期的に残しておきたいドキュメントとかノートを書くためのものではない
  • markdown で書けない

evernote

お金は払う前提で考える

Pros

  • 圧倒的コミュニティ.連携の広さとか tips が転がりまくっている.
  • web clip とかちょっとした pdf や画像をポンポンぶち込んでおける
  • 短いメモみたいなものも躊躇なくいれておけそう

Cons

  • markdown が使えない問題がでかい
  • 長めの文章を書く感じじゃなさそう
  • 機能が多すぎてごちゃつきそうというイメージもある

Boostnote

OSS になっているエディタで,dropbox みたいな外部クラウドストレージを使って同期をはかるやつ.

Pros

  • UI
  • 要件はほぼ満たしている
  • 外部ストレージを使っているので,サービス停止のリスクは外部ストレージに依存する
    • dropbox / google drive / one drive とか代替も結構あるのでサービス停止を気にする必要がなさそう

Cons

  • Dropbox などのストレージを圧迫する
  • Boostnote 独自のフォーマット(フォーマットとしては cson だけど)で保存されるので,別に外部ストレージにそのまま md が吐かれるとかではない
    • markdown として export はできる

Inkdrop

Pros

  • UI
  • 要件は満たしている
  • status と tag 機能は便利そう.
  • 一番普通に整理が出来る構造になっている気がする
  • Data Access API が使える

Cons

  • 個人開発なのでサービス停止がこわい
    • とはいえ markdown なので移行は容易い

結論

要件を満たしているといえるのは Inkdrop と Boostnote くらいだろうか. Boostnote よりも Inkdrop のほうが first impression では好みだった. とりあえず 60 日 free なので Inkdrop を使ってみる. 今この文章も Inkdrop 上で書いている.普通に markdown を書けばいいのでまあ書くのは楽.

golang でテストのために時間を操作するライブラリ timejump

現在時刻に依存するコードをテストするとき,golangtime.Now を普通に使っているとモックできずうまくテストが書けないという問題があります. 時間の操作は time パッケージをそのまま使えば良いのですが,time.Now だけはモックできるようにしたいところです.

解決方法としては,グローバル変数var NowFunc func() time.Time を置いておいて,テスト時に入れ替えるという方法があり,ORM である gorm などが実際にこれを行っています.

gorm/utils.go at 2a1463811ee1dc85d168fd639a2d4251d030e6e5 · jinzhu/gorm · GitHub

例:

var NowFunc = time.Now

func Do() string {
    return NowFunc().String()
}

func TestDo(t *testing.T) {
    now := time.Date(2009, time.November, 10, 23, 0, 0, 0, time.UTC)
    NowFunc = func() time.Time {
        return now
    }
    got := Do()
    if got != now.String() {
        t.Fail()
    }
}

golang の使用上,Ruby の timecop のようなことは出来ないので,こういう工夫をするしかありません.

なんとなくグローバル変数をテストのために置いて書き換えるのが嫌なのと,なんにも考えずに t.Parallel() を置けなくなるのがちょっと嫌だなと思っていました. また,時間経過をシミュレーションしたい場合は,そういう NowFunc を毎回書く必要があり,結構面倒です. あとパッケージをまたぐと厄介だし毎回書くのも嫌.

そこで,Ruby の timecop のように現在時刻をいじくり回せるようにするライブラリを作ってみました.

github.com

godoc.org

使用する際は time.Now をすべて timejump.Now に置き換える必要があります.( Ruby と違って time.Now を直接上書きできないので...) 普段は timejump.Nowtime.Nowif !active { ... } が一段挟まるだけなのでパフォーマンスに影響はほとんどないはずです.

テスト時は,timejump.Now の挙動を変えたいテストの頭で

func TestDo(t *testing.T) {
    timejump.Activate()
    defer timejump.Deactivate()
    ...
}

とします.

timejump.Activate区間はロックをとっているので,テストを並列で走らせても並列に走らなくなります.

timejump.Stop() で時間停止,timejump.Jump で時間移動,timejump.Moveタイムゾーンの移動,timejump.Scale で時間の経過速度をいじれます.

時間を止めたいだけの場合はグローバル変数NowFunc を持っておいて t.Parallel を間違って置かないように気をつけるほうが正直楽だとは思いますが,時間経過をテストしたい場合にはちょっと楽になるはずです.

もともとあるパッケージのテストをするために書いたパッケージだったのですが,目的だったテストを書く前にテストしたいパッケージが御役御免になってしまったので,timejump も御役御免になってしまいました. いつか使う日が来る気がするので,ここに寝かせておきます.

ISUCON 7 本戦出場してきました 「都営三田線東急目黒線直通急行日吉行」

ISUCON 7 お疲れ様でした!

僕らのチーム,「都営三田線東急目黒線直通急行日吉行」は学生枠 2 位,全体で 10 位という結果でした.

予選の結果が異常によかったので完全に調子に乗っていたんですが,本戦はやっぱり難しかったですね... 本戦でも社会人上位勢と戦えるくらいのスコアを出すのと学生枠優勝が目標だったのでやっぱりくやしい.

やったこと

結局テンパりすぎてスコア記録を残せていないので,なんとなく記憶を頼りに...

Go 実装でいきました.

  • room 名から ws をつなぎに行くホストが一台に固定されるように
    • 同じルームの action は全部同じホストにいくように
    • これでオンメモリに出来るようにした(結局ほとんどオンメモリにデータは持たなかった)
  • ルーム名から適当なハッシュ値を計算してふるようにしていたけれど,ルームによってアクセス頻度とかがちがうっぽい?ことに気がつく
    • 3 台に振ってるはずなのに,CPU 使用率を見ると 2 台しか使われていないとか
    • 負荷分散が運ゲーになっていて改善の結果が見にくかったので,とりあえず 1 台しか使わないように
  • ホストごとの接続数を redis に入れて,空いていそうなところに振り分けるように
    • 前段のサーバに nginx + app + redis を入れて,そこの redis に room -> host の対応情報を入れた
    • CPU 使用率で振り分けたほうが良かったかもしれない
  • schedule の計算過程を最適化出来る気がしなかったので,結果をキャッシュしようと試みる
    • どうやっても事後検証をパスできなかったので捨てることに...
  • 部屋ごとにロックをとってすべての操作を直列にした
    • トランザクションとかが複雑すぎていじれる気がしなかったので,一旦直列にして考えることを減らそうとした
    • rollback 考えなくて良くなったのでこれ自体は良かった気がする
  • @izumin5210 が adding/buying を redis にいれたり,過去の adding をまとめてくれた
    • ここは完全におまかせしてしまった
    • 最終的にまともに効いたのはこれだけだったのでは
  • 終盤はベンチマーカに弾かれる原因をひたすら探していた
    • 安全側に倒そうということで,色んな所でひたすらロックを取るようにしてなんとかパスした

という感じで,最高スコアが 17000 くらい,最終スコアが 16700 で終了しました.

反省

  • チーム名が長すぎた
    • 名札のチーム名部分のフォントが他のチームより小さかった気がする(ご迷惑おかけしていたらすみません...)
    • 手書きで書くのがつらすぎる
    • 来年は気をつけます
  • テストがせっかく用意されていたのにまったく使わなかった
    • テスト使っていたらもうちょっと計算過程の最適化にも手を出せたかもしれない
  • なにも操作がなくても 500ms ごとに status を計算していたところの最適化を入れきることができなかった
    • この計算は room ごとに一回やれば良いはずなのにコネクション一個につき一回計算していた
    • room ごとにひたすら status を計算し続ける goroutine を起動してそこから返す実装を書いていたが,終盤の fail 祭りにびびっていれられなかった...
    • 意味があったかどうかはよくわからない.
  • CPU profile をみて,bigint の計算がやばいことはわかっていたのに,手が出せなかった
    • この複雑さは結果をキャッシュしろってことだな!って勝手に思い込んでいたけど,結果のキャッシュも複雑で無理だった
    • 他のチームの方の話を聞く限り,そんなに無茶な最適化じゃなくても地道に最適化していたらそれなりにスコアに効いたのかもと思った(これはやってみないとわからないけど)

予選のときも練習のときも,「遅いのはわかっているけど複雑そうでやりたくない」部分を触らないとだめっていう教訓は得ていたはずなんだけど,結局そこでやられてしまったのが一番くやしいですね...

来年は学生枠ではなくなるのですが,社会人枠でも本戦にでて勝ちたいです!

去年に引き続き本戦に出られたのはほんとうに良かったし,またまた勉強になる良い経験でした!運営の皆様お疲れ様でした & ありがとうございました!

ISUCON7予選1日目に「都営三田線」で参加して通過できた話

ISUCON7 予選お疲れ様でした! タイトルどおりですが,「都営三田線東急目黒線直通急行日吉行」という学生チームで参加し,1日目3位枠で通過することができました. チーム編成は,去年2人チームで参加したときの相方である 0gajun と,僕の内定先の同期の izumin の 3 人チームでした.

何をやったかとかスコアの変遷は別で記録したいと思います(僕一人で把握しきれていないので)が,とりあえずリポジトリはここです.

github.com

追記: タイムラインと詳細はこっちに書きました

www.wantedly.com

f:id:agtn:20171023153909p:plain

去年2人で参加した時は学生枠で予選通過はできたものの,一般枠との圧倒的なスコア差にだいぶ打ちひしがれていました. もともと,「0gajun がインフラ,僕がインフラ寄りのアプリ」というチームだったので,アプリ側をがつがついじれる izumin が加わったことで,チームバランスが良くなった + 手数が圧倒的に増えたと思います.

去年とくらべてメンバーも増えたし学生とはいえ一年間で成長している(はず)というのもあったので,夢として「学生枠だけど一般枠と戦えるスコアを出したい」というのがありました. 結果,予選1日目上位3チーム枠で本戦出場を決められて本当にうれしかったです.2日目の上位が圧倒的なスコアだったのでちょっと凹みましたが,全体でも 10 位くらいだったと思うので,目標は達成できたと思います. また,無理やり ISUCON 特化な高速化を入れたりすることなく良いスコアを出せたと思うので,そこも良かったなと思っています. 本戦でも良いスコアが出せるように頑張るぞー!

最後に,ISUCON 運営の皆様,本当にお疲れ様でした & ありがとうございました! 予選から複数台構成で面食らいましたが,複数台は難しい分,楽しさも増すし勉強になることもたくさんありました! 本戦も楽しみにしています!

go generate する時のバイナリのバージョンを固定したい

https://github.com/golang/mockmockgen というコマンドを提供しています. これは,interface から mock を自動生成するコマンドで go generate と合わせて使うと interface に追従する mock がとても簡単に作れます.

他にも yacc とかリソースをバイナリに埋め込むとか,色々便利ツールがあり,go generate でコード生成をするのは golang のアプリケーションではよくあることだと思います.

しかし,golangvendor/ の仕組みは基本的に package として使うことを考えて作られているので,プロジェクトごとに mockgen などの生成コマンドのバージョンを固定するためには使えません.

ここで,go generate で使うバイナリのバージョンが固定されていないと起こりうる問題として

  • 生成されたコードに毎回 diff が出る
    • 気軽に git add . 出来ないし,コミット漏れや無駄コミットにつながる
  • バージョンAのコマンドとバージョンBのコマンドによって生成されたコードが混ざる
  • ライブラリのバージョンと生成コマンドのバージョンが一致しないためバグる
    • github.com/golang/mock/mockgengithub.com/golang/mock/gomock というライブラリとセットで使うので,gomock package と mockgen バイナリのバージョンは揃えたい

などがあります.

これ結構嫌な問題だと思ったのですが,パッとぐぐってみてもあまり困っている声を聞かないので普通どうやって解決しているのか気になっています. (もしかして僕が知らないだけで普通に解決されている問題だったりするのだろうか…)

とりあえず vendor 以下の package をビルドしたり固定されたバージョンのバイナリをぱぱっと実行するために

github.com

を作ってみました.

shell script で書けそうな単純な仕事しかしていませんが,go で実装されています.

bindor build github.com/golang/mock/mockgen./.bindor/mockgen というバイナリが出来ます. bindor exec command args... とやると PATH=./.bindor:$PATH した環境下で command args... を実行します.

$ glide get github.com/golang/mock
$ bindor build github.com/golang/mock/mockgen
$ bindor exec which mockgen
/path/to/current/.bindor/mockgen

という感じです.

//go:generate bindor mockgen としてもいいですが,bindor exec go generate とすればソースコードを書き換えなくても .bindor 以下のバイナリを使うようになるはずです.

bindor 自体にバージョンを固定する仕組みは入れていません.glide とかがやってくれている仕事を分散させても管理が面倒になるだけでメリットがなさそうだし,ライブラリとしても使う package の場合はどうせ glide で管理するので,vendor 以下のディレクトリの奪い合いになってしまいます.

というわけでバイナリを vendoring する bindor を作った話でした.もっといい解決方法があったら教えてください.

Rust で Unix のシグナルを channel 経由でキャッチする

Rust でシグナルハンドリングをする必要があったのですが,あまり自分の用途にあるライブラリがなかったので作りました. 僕が Windows のことをほとんどわからないので,Windows 未対応です.

github.com

docs.rs

https://crates.io/crates/signal-notify

golangsignal.Notify に寄せた API になっていて,標準ライブラリの std::sync::mpsc::{Sender, Receiver} 経由でシグナルを待ち受けることができます.

extern crate signal_notify;
use signal_notify::{notify, Signal};
use std::sync::mpsc::Receiver;

fn main() {
    let rx: Receiver<Signal> = notify(&[Signal::INT, Signal::USR1]);
    for sig in rx.iter() {
        match sig {
            Signal::INT => {
                println!("Interrupted!");
                break;
            }
            Signal::USR1 => println!("Got SIGUSR1!"),
        }
    }
}

Rust で Unix シグナルを取るライブラリとしては GitHub - BurntSushi/chan-signal: Respond to OS signals with channels. というのが有名です. こちらは標準ライブラリの mpsc::channel ではなく,chan クレイトの channel を使っています. chan クレイトはケースによってはかなり便利で,

  1. 複数の consumer を作れる (receiver.clone() ができる)
  2. chan_select! マクロによって golangselect 的なことができる

という利点があります.

一方で複数 consumer にする必要がない & chan_select! が必要ないケースでは,シグナルハンドリングのためだけに chan にも依存するのもなんとなくはばかられるという気持ちがありました. また,自分の目的として「SIGWINCHSIGIO が取りたい」というのがあったのですが,chan-signal の仕組みだとデフォルトで無視されるシグナルをキャッチできない(macOS だけ)という問題もありました. 報告するときに方法を考えていたのですが,あまり自信がなかったのとほとんど完全に仕組みを書きなおす形になりそうだったので,自分の手元で std::sync::mpsc を使って実験してみたという経緯です.

仕組み

  1. 初期化時にパイプを作る
  2. シグナルごとに通知すべき Sender を覚えておく
  3. シグナルごとに sigaction でハンドラをセットする
    • シグナルが来たらそれをパイプに write(2) する
  4. シグナル待受&通知用のスレッドを起動する
    • パイプからシグナル番号を読んで,適切な Sendersend する

という仕組みで動いています. 自信がなかったのは,「シグナルハンドラでやっていいこと一覧」をちゃんと把握していないという点です. 一応 sigaction の man を見ると write は読んでもいい関数一覧にいる気がするし,実際動いてはいるのでセーフだろうと判断しました. (もしアウトだったら教えてください)

ちなみに chan-signal の方は,

  1. シグナルごとに通知すべき Sender を覚えておく
  2. 監視用スレッドを起動し,メインスレッドでは pthread_sigmask を使ってシグナルをブロックする
    • シグナルがすべて監視用スレッドに渡るようにする
  3. 監視用スレッドで sigwait して適切な Sendersend する

という仕組みで動いているようです. sigwait は指定したシグナルが投げられるまでブロックします. ただし,macOSsigwait の man を見ると,

Processes which call sigwait() on ignored signals will wait indefinitely. Ignored signals are dropped immediately by the system, before delivery to a waiting process.

とあって,無視されるシグナルを sigwait で待っても補足できないようです. Linux の man を見るとそんなことは書いていないし,普通に動くっぽいです.

今の実装だと,シグナルを受け取る Receiver がすべて閉じても,監視スレッドは動き続けるしハンドラも残り続けるので,これはなんとかしたいなぁと思っています. アプリケーションの実行時間のうち,ある期間だけシグナルをとってそれ以外はスルーしたいというケースもそんなにないかなというのと,内部的な変更にしかならないので API が変わらないというのがあるので,この状態でとりあえず public にしました.

CLI を書いていると意外と普通に SIGINT は取りたくなることがあると思うので,ぜひ使ってみてください. issue 報告等お待ちしています.