Re:ゼロから始めるML生活

ミスよりグズを嫌え

【論文メモ:Airbnb search engine】Applying Deep Learning To Airbnb Search

f:id:nogawanogawa:20180920205727j:plain:w500

論文

[1810.09591] Applying Deep Learning To Airbnb Search

著者

Malay Haldar, Mustafa Abdool, Prashant Ramanathan, Tao Xu, Shulin Yang, Huizhong Duan, Qing Zhang, Nick Barrow-Williams, Bradley C. Turnbull, Brendan M. Collins, Thomas Legrand

背景

Airbnbのサービスは、ホスト(貸し手)とゲスト(借り手)という二面性を持つ。 ゲストはAirbnb.comのサイトで特定の地域に関して空き部屋の有無を検索することで、サービスを利用し始めることになる。 この検索という行為には数千もの候補の施設の中から一握りの施設を適切に並べることを意味する。

Aitbnbの初期の実装では、手動で作成したスコアリング関数を使用することでこの並び替えを行っていた。 その後、手動のスコアリング関数をgradient boosted decision tree (GBDT) に置き換え、非常に良い検索性能を達成した。 しかし、この手法も最終的には「長々とした良くも悪くもないお試し表記」によって収束してしまう問題がある。

検索モデルの変遷

Airbnbにおける一般的なゲストの振る舞いについて下記に示す。

f:id:nogawanogawa:20190102081537j:plain:w500

通常ユーザは複数回の検索とその結果である検索リストを確認することになる。 さらに、その中でいくつかの物件について詳細ページに遷移する。 そして、その中で気に入ったものがあると予約に至るというのが一般的な流れとなる。

下記に、これまでの検索モデルによる効果を示す。

f:id:nogawanogawa:20190102082536j:plain:w500

横軸に使用した検索モデル、縦軸には表示された物件が予約されたら1、それ以外は0として集計されたオフラインスコアであるNDCGを表している。
また、下記にコンバージョン率の増加について示す。

f:id:nogawanogawa:20190102082811j:plain:w500

横軸に使用した検索モデル、縦軸には各モデルによるコンバージョン率の増加を表している。
それぞれのモデルについて、確認していく。

Simple NN

最初のモデルでは、単純なニューラルネットワークを採用していた。 隠れ層は32ノードの1層のみ、活性化関数はReLUというモデルだった。

特徴量はGBDTのときと同じものを使用している。

Lambdarank NN

次に採用したLambdarank NNでは、評価の指標としてNDCGを採用した。 Lambdarank NNによって大きく2つの改善が見られた。

  • 物件の間での関連性の形式化
  • 順番の入れ替えによるLossの変化の考慮

下記に、Lambdarank NN の実装の一部を示している。

f:id:nogawanogawa:20190102082817j:plain:w500

Decision Tree/Factorization Machine NN

Lambdarank NNのあと、主に2点についての方針を考案した。

  • GBDTのイテレーションにおいて、学習データの構築の際に使用するサンプリング手法の置き換え
  • クエリから出力された物件リストが予約される可能性を推定するFactorization Machine (FM)を導入

これらのモデルと既存の予測モデルを比較したところ、推定の精度は大差なかったが、表示される物件は全く異なったものとなっていた。 そこで、従来のモデルとこれら2つのモデルを組み合わせることを考案した。

概要を下記に示す。

f:id:nogawanogawa:20190102082832j:plain:w500

FMによって出力された予測をNNの入力として扱い、 GBDTモデルはtreeごとにカテゴリとしての特徴とみなしてNNの入力とした。

Deep NN

推論モデルは複雑になりがちで、これらはすでに先行研究でも取り上げられている。 (いまのところ)AIrbnbのモデルでの最後の改善は、モデルの複雑化ではなく、単純に学習データを10倍にし、隠れ層を2層に増加させることだった。

構成としては

  • 合計195の特徴量をembeddingとする
    • 特徴量の例
      • 価格
      • アメニティ
      • 過去の予約回数
  • 第1層では127の全結合NN
  • 第2層では83の全結合NN
  • 活性化関数はReLU

のようになっている。

効果の測定のために、NDCGの学習について評価した図を下記に示す。

f:id:nogawanogawa:20190102082845j:plain:w500

17億のデータセットを使用し、学習の後半ではテストデータと学習データでほぼ同等の評価値に達することがわかる。

失敗談

ここまで来る過程で様々な失敗も経ており、成功したモデルよりも失敗したモデルのほうが多いくらいである。 世間一般でうまくいくと言われるモデルに対しても、いざ導入してみると全く効果が出ないこともしばしばである。 ここでは失敗したモデルについて、いくつか紹介していく。

Listing ID

Listing ID (物件のID)をEmbeddingのインデックスとして使用し、物件固有の特徴が反映されたEmbeddingのベクトル表現を学習するというアイデアがある。 実際に、自然言語処理やレコメンデーションシステムではカテゴリーの傾向を学習しており、うまくいくと考えていた。

実際にやってみると期待とは異なり、Listing IDでは過学習してしまうことがわかった。 学習曲線について下記に示す。

f:id:nogawanogawa:20190102082930j:plain:w500

NDCGにおいて、トレーニングセットについては急速に精度が向上しているのに対して、テストセットについてはあまり精度の向上が見られないこ とがわかる。 このように、Airbnbの特殊な環境下ではこの手法では効果が見られないことがわかった。

原因としては、Airbnb特殊な環境が考えられる。 Listing IDが適切な値に収束するようにするためには、それぞれの物件に対して十分な量のデータが必要になる。 文章中の単語や動画配信のレコメンデーションなどについてこれを使用する場合には、回数の制約がない。 一方でAirbnbは、現実に存在する物件に関するビジネスであり、年間でも最大で365回しか予約されることはない。 一方で予約されない物件では、ずっと小さい予約回数になることもありうる。

このようなビジネスの制約の違いにより、各物件に紐付いたデータ量が不足し、物件に対してオーバーフィッティグしてしまい、うまくいかなかったと考えられる。

Multi-task learning

物件の利用自体には制約があるものの、物件の詳細ページに関する閲覧に関しては制約はない。

下記に物件ごとの閲覧の分布を示す。

f:id:nogawanogawa:20190102082946j:plain:w450

閲覧に比べ、実際の予約の分布はずっとまばらとなってしまうため、連続的ではなく予測が難しい。

そこで、長時間の閲覧の回数が予約につながると仮定し、この仮説を検証するために、一つのモデルを構築した。 このモデルでは、2つの出力層を使用することで物件が予約される確率と長時間の物件詳細ページの閲覧を一度に予測する。 損失関数としては予約されるかと、長時間の閲覧があるかどうかを目的関数とする。

ネットワークの構成を下記に示す。

f:id:nogawanogawa:20190102083030j:plain:w500

閲覧と予約を同じ隠れ層を共有する構成となっている。 ポイントとしては、Listing IDが隠れ層の入力として共有されている点で、これにより閲覧の情報を予約の推定に反映し、同時にオーバーフィッティングを回避することを期待していた。

ところが、実際にやってみると、長時間の閲覧は劇的に増加したものの、予約は一向に増加しなかった。 この原因としても、やはりAirbnb独特の特徴が原因と考えられる。 長時間の閲覧は、高額な物件や説明文が長い物件、極端に独特な物件に見られていた。 長時間の閲覧は、予約とは直行する成分と考えられ、これらから予約の確率を推定するとは難しいと判断した。

特徴エンジニアリング

GBDT pipelineから、特徴エンジニアリングを行う。 特徴エンジニアリングの典型としては、計算比率、ウィンドウによる平滑化、その他要素がある。 これまで、特徴エンジニアリングの手法は多数発表されてきているが、どれが最も適切かは未だわかっていない。

今回のモデルに有効な手法を検討する。

正規化

はじめ、すべての特徴を使用して学習を行ったところ、学習の中盤で損失関数が停滞してしまった。 これは適切に特徴量を正規化できていないためである。

厳格な数値による特徴量の表現は、相対的な並べ替えが行われている限り、あまり意味がない。 一方で、NNは入力となる数値に対して反応してしまう。 異常な数値が入力となってしまう場合には、永続的に活性化関数が機能停止してしまう。

このような不具合を避けるために、特徴量を{-1, 1}の範囲に制限し、平均を0になるように正規化する。 これは2種類の変形のどちらかによって実現される。

分散

制限された範囲に数値を収めることに加え、分散を平滑化する。 この理由は、下記の3点のようなことが挙げられる。

バグの局所化

数値の範囲を逐一確認することは特徴の種類が多くなるに連れて難しくなる。 平滑化によって典型的な分布を使用すれば、外れ値の検出が容易になる。

一般化

このプロダクトに携わる経験則として、NNのLayerの出力は分散の観点では徐々に平滑化されている。 出力層の分布を下記に示す。

f:id:nogawanogawa:20190102083052j:plain:w250

また、隠れ層の出力(第2層、第1層)を下記に二種類示す。

f:id:nogawanogawa:20190102083002j:plain:w500

f:id:nogawanogawa:20190102083012j:plain

何百もの特徴量を使用してモデルを学習させる際に、これらの組み合わせのパターンはとてつもなく大きく、 それが不具合を起こしかねない。 下位層での平滑化は上位層で把握できていない値を正しく保管することに役立つ。 そのため、入力層での平滑化が有効と考えられる。

実際、テストセットで物件の価格を2倍〜4倍にしてみても、モデルは安定しており、正常に機能していると考えている。 大体の特徴量は一度の正規化でなめらかな分布になったが、一部そうでないものについては特殊な処理が必要になった。 その例として、物件の緯度経度の地理情報がある。

下記に緯度経度をそのままマッピングした図を示す。

f:id:nogawanogawa:20190119113127j:plain:w500

この分布を平滑化するためには、生の値を使用せず中心とそのオフセットを使用する必要がある。 中心からの分布を示した図を下記に示す。

f:id:nogawanogawa:20190119113141j:plain:w500

左図はそのままプロットしたものあるが、これでは、まだ中心から極端に遠すぎる物件が存在する。 そのため対数をとったものが右図である。 これで、平滑な分布に変形する事ができた。 これを使用して分布を示したものが下記の様になる。

f:id:nogawanogawa:20190119113152j:plain:w500

特徴量の完全性確認

分布の滑らかさがなく、モデルがうまく機能しない場合もある。 例としては、物件の占有率があげられる。 占有率を示した図を下記左図に示す。

f:id:nogawanogawa:20190119113206j:plain:w600

通常物件は最小限の滞在が行われるが、時々何ヶ月も滞在することもある。 しかし、占有率は連泊を想定しない特徴量として取り扱っており、これが状況を複雑化させている。

そこで、平均滞在期間を特徴量として加えることとした。 平均滞在期間の分布を示したものが右図となっている。 これらを組み合わせることで、いびつな分布にも効果的であると考える。

カテゴリーに関する濃度

ゲストの街に関する嗜好は重要なシグナルの一つと捉えることが出来る。 このシグナルは重く取り扱われ、近隣の物件や街も重要に扱われることが望ましい。

単純なNNではこれらの情報は他と同じ一つの特徴として扱われる。 そこで、新しくカテゴリに関する特徴量を設計した。 こちらは、地域と対応する整数値(ハッシュ値)をペアとして取扱い、ハッシュ値間の連関を学習するように設計されている。

これによる効果を下記に示す。

f:id:nogawanogawa:20190119113221j:plain:w500

サンフランシスコだけでなく、南や西岸に対しても強調され、地理的な情報について期待通り学習できるようになっている。

システム

学習とスコアリングの計算処理的性能を向上させる点について考える。 流れとしては下記のようになり、これらはAWS上で稼働している。

  1. ユーザーはJavaサーバへアクセス
  2. Javaサーバーから生成されたログをThriftに格納
  3. 学習はSparkによって分散処理
    • 学習のモデルにはTensorFlowを採用
  4. 学習されたモデルがJavaサーバーへ反映される

Protocol Buffer とデータ・セット

CSV形式の学習データを使用して学習を行う。 初期の頃は、機械学習による並べかえを行っていなかったため、GPU使用率は25%未満となっていた。 多いところで、データのパースやfeed_dictへのコピーが主である。

Protocol Bufferとして学習データを生成し、それらを使用して学習を行うようにパイプラインを変更したところ、17倍の性能向上が見られ、GPU稼働率も90%程度まで達した。

静的特徴のリファクタリング

位置やアメニティなど、特徴自体はなかなか変更されるものではない。 これらすべてを毎回学習していることは非効率である。

このような不要なディスクアクセスを回避すべく、(準)不変な特徴については学習されないembeddingとして設定する。 嗜好の変化とこのやり方はトレードオフの関係にあるが、CPU <=> GPU間のデータ転送を削減することが出来る。 この削減した分だけ、別の有用な特徴を考慮することも出来る。

JAVA NN ライブラリ

2017年初頭現在、学習したモデルをJava Stackで使用する効率よい方法が存在しなかった。 "検索"というレスポンスが重要視される機能なので、我々はJavaにおけるネットワークスコアリングライブラリを開発した。

ハイパーパラメータ

Drop out

我々の実装では、はじめ正規化と対応しており、有効であった。 しかし、異なる特徴ごとにドロップアウトが発生し、オフライン指標において悪影響を及ぼすようになってしまった。

そこで、学習データが欠損している場合に、無作為にデータの水増しを行った。 手作業で補足データを作成もしたが、オフライン評価で1%未満の向上しか見られず、オンライン評価では目覚ましい改善は見られなかった。

初期化

はじめ、ネットワークの初期化はすべて0にしていたが、その後{-1, 1} の範囲でランダムに選択するXavier initializationに変更した。

Optimizer

取り組んでいる中で、Adam Optimizerでは性能の改善が難しいことがわかった。 そのため変形Lazy Adam Optimizerを採用した

Batch サイズ

先行研究等も参考にして、今の所Batchサイズは200に落ち着いた。

特徴量の重要度

特徴量ごとに重要度を求めることはモデルの反復において重要なファクターとなる。

スコアの内訳

NNの世界では、個々の特徴を切り分けて考えることは、混乱を招くだけである。 初期の実装では、出力に対して、入力のどの特徴がどれだけ影響を与えているかを分析した。 これをやってみた結果、そもそもの考えが間違っていることに気がついた。

非線形の活性化関数を使用する以上、きれいにこれらを切り分けることは不可能である。

風化テスト

風化テストも単純な重要度を捉える指標である。 しかし、NNではノイズにた特徴量を途中で欠落してしまう。 特徴を数多く冗長に設定している関係上、一つの特徴量の変化に出力がそれほど影響を及ぼさないことになってしまう。 その結果、テセウスパラドックスに陥ってしまい、正しい重要度を推定することは難しい。

並べ替えテスト

表示する物件を並べ替えて重要度を測定することも考えた。 その結果、物件内の部屋数が最も影響を与えるという結果になり、あまり意味のある結果は得られなかった。

そもそも、各特徴を独立として考えているため、考え方として間違っている。

先頭-末尾に関する分析

推定された物件の先頭と末尾に関する分析を使用して、特徴の重要度を考える。 下記に例を示す。

f:id:nogawanogawa:20190119113231j:plain:w500

先頭で表示される物件については低価格に寄っていて、モデルは価格に敏感であることがわかる。 一方でレビューの個数は、先頭・末尾で殆ど変わらず、あまり関係ないことがわかる。

このように、相対的にであれば特徴量を分析することが可能であることがわかった。

振り返り

これまでのDNNの取り組みの成果の概要を下に示す。

f:id:nogawanogawa:20190119113241j:plain:w400

はじめは、GBDTモデルをNNに置き換えることで、非常に大きな最適化の恩恵を享受出来た。 その後、改善が見られない期間が続いたが、結果として全体を別のモデルに置き換えるのではなく、部分的に導入していく方法に行き着いた。 その過程で、システム全体を見直すこともでき、部分的なコントロールできる小さな問題に細分化することで改善することができた。

はじめは単なる特徴量の選定であったが、DNN導入後はネットワーク全体を含めた最適化を行っていった。 これにより、より高い抽象度でものを考えることができ、目的にむけどう改善するか、どうユーザーに見せていくかまで考慮できるようになった。 それでもまだ導入して2年しか経っておらず、始まったばかりである。 ぜひ他の方もDNN導入の検討をおすすめする。

感想

普通の論文とは流れが違う論文で、技術論文としてはちょっと”???”って感じの書き方でした。 そんなわけで、論文を読むにあたってこちらの記事も参考にさせていただきました。

qiita.com

非常にわかりやすかったです。ありがとうございました。

論文の書き方についてはお手本にしてほしくない論文ですが、内容は非常に興味深く、勉強になりました。

理解しきれなかった部分はおそらく、検索エンジン特有の背景知識が抜けているためだと思うので、その辺勉強してからもう一度読んでみたいと思います。(覚えてたら。。。)