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_2$ は $P=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 で学習．