糞糞糞ネット弁慶

読んだ論文についてメモを書きます.趣味の話は http://repose.hatenablog.com

Customized Regression Model for Airbnb Dynamic Pricing (KDD 2018) 読んだ

KDD 2018 | Customized Regression Model for Airbnb Dynamic Pricing

民泊サービス Airbnb において, host (部屋を提供する人,ホスト) に対して「この値段で部屋を貸すと良い」と価格を提案する機能を実装するための技術.

  • 予約 (booking) が入るかどうかの予測を行う
  • その上で最適な価格を提示する

という二つの方法を取る.
この論文の貢献は以下の二つ.

  • 価格の決定方法を評価する指標を提案していること
  • その指標にもとづき価格を提示するモデルを学習する方法を考えたこと

なぜ需要の推定が難しいか

「価格を決定する」というのは非常に古典的な問題.一般的には需要関数を求めて面積が最大となるような価格 P を提案する.このとき,需要関数は価格のみの関数 F(P)である.
しかし, Airbnb では需要は価格だけではなく,時刻 t およびその物件を識別する ID id によって決まる F(P, t, id) である.それぞれの要因は次のような要素で構成される.

  • 時刻による違い
    • 季節性やイベントによって需要が異なる
    • 現在時刻と予約を予測したい時刻との差が短ければ短いほど予約されにくい (表示期間が短ければ短いほど予約されにくいという話?)
  • 物件による違い
    • すべての部屋がほぼ同じであるホテルとは異なり, Airbnb にある物件はすべて異なっている (一般的な物件に加え,城やツリーハウス,船がある).これだけでも需要が大きく変わってくる.
    • もし似たような物件に絞ったとしても,レビューが良いほうが需要が高いだろう
    • 近隣物件の需要が高まっているのなら,高評価の物件はより高い価格を提示しても利用率を下げることなく予約が入るだろう.

予約推定モデル

まずは予約されるかどうか推定するモデルを構築する.
特徴量には

  • 物件特徴量 : 物件の価格,部屋の種類,収容人数,ベッドルームやバスルームの数,アメニティ,場所,レビュー,過去の利用率,「今すぐ予約」が可能か,など
  • 時間的特徴量 : 季節性 (何月何日か,何曜日か),予約状況 (チェックインからチェックアウトまでの期間など),予測日から推定対象の日付までの差など
  • 需要・供給のダイナミクス : 近隣の予約可能な物件数,検索者数など

モデルは GBM を使う.ひとつの GBM を推定するのではなく,物件の密度に応じて区画を分け,adaptive sampling を行いながら別々の GBM を学習することで AUC がより良い値になった.

このモデルを需要関数代わりに使うとどうなるか

この予約推定モデルを価格の関数としてみなすことで需要関数として扱うことができる.この関数をそのまま使って収益最大化を A/B テストしてみたが失敗した.
この関数を需要関数としてそのまま使うことには以下の三つの問題があった.

  • データがスパースであること : データにおいて価格は大きく変化していない.たとえば 150 ドルの部屋に対して 50 ドル未満や 500 ドルを設定している人はいない.そのため,平均的な価格のデータばかり集まってしまう.
  • 物件がそれぞれユニークすぎること
  • 特徴量の依存性 : 予約推定モデルにおいて用いた特徴量のうち価格と相関を持つものがあるためうまく働かない.

価格提示モデル

最適な価格と提示価格の関係,オフラインでの評価指標

ここからがこの論文の一番おもしろいところ.
そもそも「最適な (optimal)価格」とは一体どういうことでしょうか.いま手元にあるデータには,「ある価格の物件に予約が入ったかどうか」しかわからず,このデータで学習をしてもただの「現状の価格推定モデル」が得られるだけです.「真に最適な価格」は神様しか知りません.
そこで,真に最適な価格 P_o が存在するとして,実際の価格 P とモデルによって提示する価格 P_{s} との関係を考えると以下のように整理できる.

  • もし物件が予約されて P_s < P だった場合,もしホストがモデルに従っていた場合には P_s - P 分だけ損をすることになる.なのので P_o \geq P でなければならない
  • もし物件が予約されずに P_s \geq P だった場合,もっと安ければより予約される確率が高まっただろう.よって P_o < P でなければならない.
  • もし物件が予約されて P_s \geq P だった場合,もしホストがモデルに従っていた場合 (値上げしていた場合) でも予約が入ったかどうかはわからない
  • もし物件が予約されずに P_s < P だった場合,ホストがモデルに従っていればより予約される確率が高かっただろう.しかし安すぎるとホストが損をしてしまう.

これらの関係を踏まえて,prec-recall の 表のように

  • a :  P_s \geq P かつ予約された
  • b :  P_s \geq P かつ予約されなかった
  • c :  P_s < P かつ予約された
  • d :  P_s < P かつ予約されなかった

として次の 5 つの指標を考える.これらの指標はオフラインでのモデルの評価に用いる.

  • Price Decrease Recall (PDR) : d / (b + d), 予約されなかった中で,安く提案できていた割合
  • Price Decrease Precision (PDP) : d / (c + d), 安く提案できていた中で,予約されなかった割合
  • Price Increase Recall (PIR) : a / (a + c), 予約された中で,高く提案できていた割合
  • Price Increase Precision (PIP) : a / (a + b), 高く提案できていた中で,予約された割合
  • Booking Regret (BR) :  \textrm{max}(0, \frac{P - P_{s}}{P}) の全予約での median

Price Decrease は「より安く提案できていたか」すなわち予約確率をより上げられていたかについて, Price Increase は「より高く提案できていたか」すなわちホストがより収益絵を得られたかについて考えている.
BR は提案によって収益が落ちていたであろう度合いを表している.
検証したところ,これらの指標の中での PDR と BR は実ビジネスでの指標と高い相関を持つことがわかった.特に,PDR は booking gain (予約数?)と相関を持ち,低い BR による価格提案はよりホストの収益を増加させていることがわかる.じゃあ PDR と BR だけを見て最適化すればいいかというとそういうわけにもいかない.なぜなら PDR と BR はトレードオフにあるからだ (安い価格を提案すると PDR は改善するが BR は悪化する).

モデル,目的関数

まず特徴量として

  • ホストによって設定された価格 P_i
  • 予約推定モデルによる確率 q_i
  • 予約推定モデルでは捉えきれなかった市場の需要を示す変数

を入れる.
ここで,目的関数として SVR での \epsilon- insensitive loss (ε許容誤差) のように幅を持たせた新しい損失を提案する.何度も言っているように,「最適な価格」というのを我々は知ることができないけれど,ビジネス的な観点から「最適な価格はこの範囲内に入るだろう」ということはわかるのでそれを損失関数に反映する.
目的関数は次の関数の最小化である.
\textrm{argmax}_{\theta} \sum_i (L(P_i, y_i) - f_{\theta}(x_i))^+ + (f_{\theta}(x_i) - U(P_i, y_i))^+
ここで y_i は i が予約されていたかどうかを示す二値変数, f_{\theta} は推定したいモデル,(x)^+ = \textrm{max}(0, x)
L, U はそれぞれ
L(P_i, y_i) = y_i \cdot P_i + (1 - y_i)\cdot c_1 P_i
U(P_i, y_i) = (1 - y_i) \cdot P_i + y_i\cdot c_2 P_i
とする.このとき  c_1 \in (0, 1),\ c_2 > 1 である定数.
これが何を意味しているかというと,

  • 予約されている時は価格の下限を P_i,上限を  c_2 P_i とし,その範囲内であれば損失を 0
  • 予約されていない時は価格の下限を c_1P_i,上限を  cP_i とし,その範囲内であれば損失を 0

という形の非対称な損失を考える.

需要に基づく価格設定

更に価格提示のためのモデルを考える.以下のような仮説を置く.

  • 同じ物件ならば予約確率と価格には相関がある.よって予約確率で価格を変化させる.
  • 予約予測モデルでは捉えられなかった需要の兆候が容易に反映できるようにする
  • 代表的な価格を中心にしてそこからの増加・減少分を学習する

これを踏まえ次のようなモデルを作る.
P_s = P \cdot V
V = 1 + \theta_{1} (q^{\varphi_{H}^{-qD}} - \theta_2),\ D > 0
V = 1 + \theta_{1} (q^{\varphi_{L}^{-(1-q)D}} - \theta_2),\ D \leq 0
P はホストによって設定された代表的な価格,qは予約確率,D は類似した物件で作ったクラスタにおける追加の特徴量から構築した需要の度合いを正規分布で正規化したもの.
\theta_1 は価格の増減をコントロールするパラメータ,theta_2P=P_s を出す時の微調整パラメータ.\theta_1,\ \theta_2が与えられるとこの関数は q に対して単調増加する.1 < \varphi_L < \varphi_H < 2 は定数.

学習

とはいえこれだけだと値が壊れるので
 l_1 \leq \theta_1 \leq \mu_1
 l_2 \leq \theta_2 \leq \mu_2
となるような制約を加える.
また,需要が乏しい物件には
a\theta_1 + b \leq \theta_2,\ (a > 0)
という制約を加える.
あとは SGD で学習.

PDR の話のあたり,「真の値が存在しない時にどういう数字を作れば改善してるかどうか考えられるか」の話が一番おもしろかった.気力が尽きたのでP_s = SV の話のあたりはよくわかってない (例えば additional な demand signal とは何か,とか).

声優統計コーパスのバランス文を男性が読み上げた音声ファイルが公開されました

声優統計コーパスのパラレルコーパスとして,東京大学猿渡研究室によるJSUT (Japanese speech corpus of Saruwatari-lab., University of Tokyo)がありました.
このたび,nico-opendata 音声読み上げデータセットDwango Media Village によって公開されました.
nico-opendata 音声読み上げデータセットDwango Media Village の男性研究員が声優統計コーパスのバランス文 100 文を読み上げた音声ファイルです.上記ページでは統計的声質変換に関するサーベイも記述されています.声質変換についてわかっていなかったので非常に参考になりました.
また,同研究員が音学シンポジウム2018で発表を行った「畳込みニューラルネットワークを用いた音響特徴量変換とスペクトログラム高精細化による声質変換」について,発表内容,ソースコード,および,統計的声質変換を実際に行ったデモ音声が公開されています.

せっかくなのでこれを機に様々な人々が思い思いの音声コーパスを公開する時代になると面白いと思います.

Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time (WebConf 2018) 読んだ

[1711.07601] Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time
Pinterest における推薦の論文.Jure Leskovec が last author に入っているのでとりあえず読む. WWW が WebConf に名前が変わったのが悲しい.

概要

超大規模なサービスである Pinterest においてリアルタイムな推薦を実現する Pixie について説明する.

手法

Pinterest ではユーザは Board の下にそれぞれの pin を保存する.実現したいのは直近のユーザの行動によって得られた pin と重みの集合であるクエリ Q に対して適した pin を推薦したい.
基本的な方針は pin と Board を二部グラフとみなしてそのグラフ上をランダムウォークする.

ランダムウォークの基礎

クエリ が 1 つだけで重みがない場合のランダムウォークについて考えてみると,二部グラフ上の かららスタートして 回二部グラフ上をランダムに渡り歩き,それぞれの pin を訪問回数 順に並び替えて返せばいい.
この手法を次に説明するように発展させていく.

ランダムウォークにバイアスをかける

まずはただランダムに遷移するのではなく,ユーザごとにバイアスをかけることを考える.隣接ノードを uniform に選ぶのではなく,ユーザごとの特徴量に従って遷移するノードを PersonalizedNeighbor(E, U) という関数で選ぶ.この関数についてはこれ以上の説明がないので詳細は不明.

複数のクエリと重みを扱う

クエリとして複数の pin とそれぞれの重みを扱う (重みはその pin に対してユーザがどういう行動をとったか,およびその行動が発生してからの経過時間にもとづいて決まるらしいが詳細な説明無し).
基本的には各クエリごとにランダムウォークを行い,クエリごとの pin の訪問回数 を保存する.
ここで重要なのは,各クエリにおいてランダムウォークの回数 を変えて とすることである.クエリの次数が大きければ大きいほどランダムウォークの回数は多くする.
と思ったらより効率的にするために early stopping を導入する.これは最低 個の pin に最低 回訪問したらランダムウォークを打ち切るというもの.これによって精度はそのままに計算時間が倍の速さになった.
(early stopping するなら重みの形はどうでもいいのだろう)

Multi-hit Booster

ただ足し合わせるのではなく, として複数のクエリから訪問されている pin を重く評価する.

グラフの枝刈り

グラフはそのままだと非常に大きいので枝刈りする.方針としては二つ.

雑多な Board を削除する

pin の説明文に対して LDA を適用して topic distribution を計算して topic vector とする.その後,それぞれの Board に直近で追加された複数の pin の topic vector の entropy を Board の entropy とし,これが大きい Board をグラフから削除する.

人気の pin を削除する

人気の pin を削除する.がただ削除するのではない.その pin の topic vector と Board の vector とのコサイン類似度を取って類似しているもののみ残す.

この枝刈りによってグラフの大きさを 1/6 にし,推薦の類似度を 58% 改善した.

ML Ops Study #2 参加した

ML Ops Study #2 - connpass
申し込んだら当たったので参加した.皆さんみたいにちゃんとした機械学習や深層学習がしてみたかった.

機械学習プロジェクトを頑健にする施策: ワークフロー、仮想化、品質向上、知識移譲 etc

機械学習プロジェクトを頑健にする施策 ML Ops Study #2 // Speaker Deck

  • 機械学習プロダクトは脆い.原因とその対策.
    • 実験スクリプトが動かない
    • 実験スクリプトが理解できない,実験した人がいなくなる
      • ソフトウェアエンジニアリングをちゃんとする
      • ソフトウェアエンジニアが書いてリサーチャーがレビューする
      • コードの整理は実験をした本人がやる
        • この話,金融機関における数理モデル研究から実用化に至るノウハウなどが(もしあるのならば)参考になるのではないかと思った
      • テストもちゃんと書く

質疑で「リサーチャーは Jupyter notebook が精一杯だったりする.リサーチャーがソフトウェアエンジニアの,ソフトウェアエンジニアがリサーチャーの素養がある程度ないと難しいのではないか」みたいな質問があり, Cookpad 社は両方素養がある人ばかりなのでコードレビューも問題無いという返答があった.Jupyter notebook ですらまともに使うことができない低レベルの人間なのでとても参考になった.
Github や Qiita に公開されている機械学習系のコードは品質がひどくて動かない事が多い」という話で自分を除く皆さんが笑顔になっていた.

ドローン点検・測量を機械学習を使って圧倒的に簡単にしました

  • SONYZMP が組んだエアロセンスではドローンによる測量をやっている
  • ドローンの GPS は誤差が酷いのでマーカーを併せて使うことが一般的だが
    • マーカーの正確な位置を手で測量しなきゃならない
    • 画像中のマーカーを手で特定しなきゃならない
  • そこでマーカーを独自開発する
    • 高精度 GPS と高さ計測をマーカー自身で実現
    • その上でドローンから空撮した画像中からマーカーを自動検出 (opencv による候補抽出 + tf 実装の VGG でマーカーかどうか分類) する
      • どうして一つのモデルで全部やらないかの質疑が聞き取れなかった
  • 結果手作業を 60% 削減できた

Kelner: 爆速で構築できる機械学習モデルサーバー

What is Kelner? | Kelner
学習済み機械学習モデルを用いた予測を簡単に REST API として公開するためのフレームワーク
機械学習といっても Keras と Tensorflow にのみ対応しており scikit-learn には未対応.よくわかっていないけれど kelner_model.KelnerModel を継承した SKLearnModel とか実装すればいいのだろうか.

このあたりで追加した頭痛薬が効かなくて帰った.

声優統計コーパスの利用事例暫定まとめ

日本声優統計学会 にて声優統計コーパスを公開してほぼ一年.個人団体を問わず問い合わせのメールを頂いている.

しかしよく考えたら Google Analytics の設定をまともに書いていなかったせいでどれぐらいダウンロードされたのか全く計測できていない.せめて,検索して見つけた範囲で利用されているブログ記事を集めた.

声優統計コーパスを使ってみる - 驚異のアニヲタ社会復帰への道
声優統計コーパスをアライメントしてみる | Hiho's Blog
日本声優統計学会の公開データを使って声優さんの声認識 – 京都の技術者ロードローラーさんのブログ
声優統計コーパスを使ったWaveNet音声合成/歌声合成に挑戦します - Monthly Hacker's Blog
声優統計のデータを使った、簡単なGMM声質変換のデモノートブック - Jupyter Notebook

@__dhgrs__さんからの指摘にもあるように,公式でアラインメントを提供すべきなのだろうと思っているけれどなかなか時間がない.今回言及した記事でも行われていたり,この方も行っていたりとあるにはあるのだけど,なかなか追いきれていないのと音声周りの知見がやはりまだ無いままなのでどうやるのが良さそうなのかよくわかっていない.

Shinnosuke Takamichi (高道 慎之介) - JSUT
また,これはブログ記事ではないけれど,東大猿渡研究室の高道助教によって作成されたコーパスに voiceactress100 として声優統計コーパスと互換のある音声が含まれている.
このコーパス[1711.00354] JSUT corpus: free large-scale Japanese speech corpus for end-to-end speech synthesis という形で論文にもなっている. Reference に [11] y_benjo and MagnesiumRibbon とあるのがいい.

その他,このように利用しているなどあったら教えて欲しい.とても嬉しい.

Dynamic Word Embeddings for Evolving Semantic Discovery (WSDM 2018) 読んだ

概要

[1703.00607] Dynamic Word Embeddings for Evolving Semantic Discovery
word embedding の時系列変化が見たい(これどこかの論文でも見た気がする).
例えば, apple という単語は昔は果物が連想されるだけだったが,今ではテクノロジー企業も連想されるだろう.
例えば, trump という人名だって「不動産」 -> 「テレビ」 -> 「共和党」と連想するものが時間と共に変化するだろう.
そういうのが見たい.

問題は,従来の embedding の方法は学習時に回転を考慮しないため,異なる時点での embedding を対応付けることができない.そこで,従来手法では,

  • 各時点での embedding を学習する
  • 時点ごとの embedding を対応付ける alignment を解く

という二段階のアプローチを行っていた.
この論文の手法は,全時点での embedding を解きながら embedding の時間変化に伴う滑らかさを正則化項として追加することで alignment を分割して説かなくて済む.

手法

ある時点での embedding については skip-gram や CBoW ではなく, PPMI (positive pointwise mutual information) 行列を行列分解することで獲得する.
結論から先に書くと,時点 における PPMI matrix を とし,分解後行列を とすると,最小化すべき目的関数は

となる.一項目は embedding そのものの誤差の最小化,二項目は embedding の正則化,三項目が時点間での滑らかさのコスト関数.で時点間の embedding がどれだけ近いかをコントロールする.
これにより,全ての embedding が全時点を考慮した状態で推定が可能となる,と著者らは主張している.
非常にシンプルな話.
勾配まで論文中に示してあるので実装も簡単にできそう.

結果

embedding を t-sne で可視化しつつある単語の変化の跡 (trajectory) を見る.27年分のデータで実験

  • apple が「果物」から「技術」に移動している.94年にスパイクが発生しているのは IBM との騒動があったため.
  • amazon は「森林」から「e-コマース」に移動し,「タブレット」など経て最終的には Netflix などのコンテンツ配信領域に落ち着いている.
  • obama は「学生」「市民」という領域から「議員」に移動し,最後には「大統領」に
  • trump は「オーナー」「不動産」から「大統領」に

Neural Factorization Machines for Sparse Predictive Analytics (SIGIR 2017) 読んだ & Chainer で実装した

[1708.05027] Neural Factorization Machines for Sparse Predictive Analytics

みんなが好きな Factorization Machines (FM) とニューラルネットワークを組み合わせて Neural Factorization Machines (NFM) を提案する.
FM とその派生手法がいくら変数間の交互作用を表現するモデルであったとしても,しかしそれは線形モデルのままであり,表現力に乏しい,というのがモチベーション.

FM

FM は という形で予測を行う.三項目で各特徴量をで低次元表現しつつその積で交互作用を扱う,というのが FM の特徴.

NFM

NFM では として, ニューラルネットワークにすることで交互作用を考慮しつつ非線形性を表現する.

ネットワークは

  • Embedding Layer
  • Bi-Interaction Layer
  • Hidden Layer
  • Prediction Layer

の四つから構成される.三つ目は複数階層のニューラルネットワーク,四つ目はただの 1 次元に落とす操作なので前二つについて書く.

Embedding Layer

FM や NFM が扱うのはたいていスパースなので,値がある次元をそれぞれ低次元に Embedding する.例えば, D 次元の入力のうち N 個だけが値を持っているとする時,K 次元に埋め込むとすると K 次元のベクトルが N 本作られる.またこの時,各次元の値を埋め込んだベクトルに掛けることを忘れないようにする.

Bi-Interaction Layer

続いて交互作用を考える. Embedding Layer から届くのは K 次元の N 本のベクトルなので,これを K 次元の一本のベクトルに変換したい.何も考えずにやると average pooling とか max pooling とかやる(例えば Learning Hierarchical Representation Model for Next Basket Recommendation (SIGIR 2015) 読んだ - 糞ネット弁慶 など.論文でも言及済)わけですが,ここでは陽に交互作用を考える.
すなわち, とする.ここで は埋め込みベクトルに元の特徴量をかけた K 次元のベクトルで, はベクトルの要素ごとの積.
これは としても計算ができる.

あとは batch normalization や dropout や residual unit なんかを Hidden Layer で入れることでモダンな感じになる.

実装

Chainer でやった.コードはこの gist にアップロードした.
ファイルは libsvm format で入力すると動作する.ひとまず classification がやりたかったので最後に sigmoid に通している.

「埋め込みを行いつつ元の値を掛ける」という操作をどうやっていいのかわからなかったので

  • 入力を「発火している特徴量の id を並べ,それ以外は -1 で padding したリスト」と「そのリストの各要素に対応する元の特徴量の値」に分ける
  • 特に後者は埋め込み後に掛ける必要があるので埋め込み次元に引き伸ばす

という方針でやる.

例えば特徴量が {0: 0.1, 3: 3, 7: 1} であり,特徴量の最大次元が10であり,3次元に埋め込む場合は

raw_fv = {0: 0.1, 3: 3, 7: 1}
# こんな感じで入力を書く
active_feature_ids = chainer.Variable(np.array([0, 3, 7, -1, -1, -1, -1, -1, -1, -1], dtype=np.int32))
feature_weights = chainer.Variable(np.array([[0.1, 0.1, 0.1], [3, 3, 3], [1, 1, 1], [0, 0, 0], ...], dtype=np.float32))

# 中略
# chainer の predict にて
# 'EMB': L.EmbedID(10, 3, ignore_label=-1) として layer を定義しておく

# まずは埋め込む
emb = self.EMB(active_feature_ids)

# 埋め込んだベクトルに元の特徴量の値をかける
emb = emb * feature_weights

# 組み合わせを考える
pairwise = F.square(F.sum(emb, axis=1)) - F.sum(F.square(emb), axis=1)
pairwise *= 0.5

# あとは何層か重ねる
pairwise = F.relu(self.l_pairwise_1(pairwise))
pairwise = F.relu(self.l_pairwise_2(pairwise))
pairwise = F.relu(self.l_pairwise_3(pairwise))

という感じで書いている.もっと綺麗に書く方法があると思うが書き慣れていないのでよくわかっていない.
これに加えてニューラルでない線形和の部分も chainer で推定させるために愚直にスパースな特徴ベクトルも渡している.綺麗に書きたい.

movielens のデータではそれらしく動いているのであとでちゃんと検証する.