Uplift Modeling with Multiple Treatments and General Response Types

[usaito]

0. 論文概要

Yan Zhao, Xiao Fang, and David Simchi-Levi. Uplift Modeling with Multiple Treatments and General Response Types. In proceeding of the SIAM International Conference on Data Mining (SDM17), 2017.

** 図表は全て本論文からの引用です.

1. 要約

• 多種介入が存在する場合のuplift modelingを定式化し, その状況における評価指標を提案.
• 提案した評価指標を学習過程で最大化するようなForest likeのアルゴリズムを提案.
• 提案手法によって介入施策を個別化することでより望ましい目的変数を導けることを実験で実証.

2. 背景

• Uplift modelingでこれまで提案されているのは, 基本的に介入する or しないの2種介入の状況に対応するアルゴリズム
• 多種介入に対応するアルゴリズムも少数存在するがそれらは, binary outcomeにしか用いることができないという制約を持つ
• よって, より現実的な状況に対応するために多種介入かつ目的変数が連続変数である場合にも適用できるアルゴリズムが必要である. これがあれば, 例えば, 複数の広告クリエイティブを最大化することでユーザーの商品購入金額を最大化するような問題設定で, 介入施策を最適化できるようになる.

3. 手法

定式化

まず, 多種介入が存在するuplift modelingを定式化する. この問題設定では, 以下のように各データについて以下の3つの変数がデータセットとして用いることができる.

ここで, xは特徴量ベクトル, tはデータが受けた介入を表すカテゴリカル変数, yが観測された目的変数である. uplift modelingでは, RCT (A/B test) によってデータが得られる状況を想定するので, tとxは独立である.

今回求めたいのは, 以下の値を最大化するような, uplift model hである. ここでhは, 特徴量ベクトルを入力とし, どの介入をすべきかを返してくれるような写像である.

上の値を最大化するようなhは, 以下のように定義することができる. つまり, 各データについて, tで条件付けた時の目的変数の期待値が最大になるようなtを返せば良い.

評価指標

最適なhを求めるアルゴリズムの話に入る前に, まず, hの性能を評価するためのmetricを提案する. ここで問題なのが, テストデータについても, 各データについてデータが集められた際に受けた介入に紐づく目的変数しか得られていないということである. （この辺はRubin Causal Modelで記述すれば見通しが良いのだが, この論文ではそうしていない）

しかし, いま性能を評価したいモデルhと, テストデータが受けた介入tが一致する時の目的変数を（重み付けて）平均すれば, 欲しいmetricに対してunbiasedな推定量を得ることができる. （Zの実現値を平均すれば良い）

もちろんこれ自体評価指標として用いることができるが, 本論文のメインパートではこの値を最大化するようなアルゴリズムを提案している.

アルゴリズム

さて, 先ほど提案した評価指標に対する不偏推定量を最大化するようなtree-basedのアルゴリズムであるCTSが本論文の目玉. まず, ある介入が割り当てられた親ノードφを子ノードφ_lとφ_rに分割して, それぞれに違う介入を割り当てることを考え, 分割するごとに介入を個別化するようなアルゴリズムを想定する. この時最適な分割は, 目的変数が最も増加する分割として以下のように定義できる.

左ノードと右ノードの密度で重み付けした目的変数の期待値の和が最大になるような分割を最適としている. しかし, 先ほどと同じように, s_Nで表されるトレーニングデータに含まれているのは実際にデータが受けた介入に対応する目的変数だけであり, データから最適な分割を求めることは不可能である.

ここで, 先ほど評価指標として導いた不偏推定量が役に立つ. 先の不偏推定量を用いることで, 任意の分割から導かれるであろう目的変数を不偏推定することができるので, サンプルから推定されるそれに基づいて逐次分割していけば良いというのが提案手法CTSの主たるアイデアである. 実際のsplit criterionは以下のようなものである.

where

ここで, (3.8)に出てきているn_regは正則化であり, 子ノードにある介入を割り当てた時の目的変数を推定する時に, 親ノードの情報もある程度用いるような正則化になっている.

アルゴリズムの全体像は以下の通り. 最終的にバギングすることで過学習を防ぐ. あるテストデータについて, そのデータが属するリーフの目的変数を最大化する介入を予測方策として返す.

4. 実験

人工データ

まず, 人工データを使ってCTSの性能を評価する. SMAは, 既存の機械学習アルゴリズムの組み合わせで介入を求める手法であり, 本論文では, baselineとしている. 人工データを使うことで, テストデータに対して予測した時の性能を推定する必要はなく, 真の値を用いて評価することが可能.

ここでは, 以下の4つの介入が存在するデータを用いる.

結果は次の通り. トレーニングデータの数を増やすにつれてCTSが大きくbaselineを上回っている.

実データ1

次に, ある航空会社の座席予約に関するデータを使った実験を行う. ここでは, あるチケットについてそれを€5で販売するか, €7で販売するかをユーザーごとに最適化することで期待購入金額を最大化する問題を解く.
Figure 3は各アルゴリズムと, 価格帯を固定した時に導かれる期待購入金額がプロットされている. これらの値は, 実データであるため推定された値であることに注意.

CTSが大きく他を上回る性能を見せた.

実データ2

次に4つの価格帯を用いることが可能な問題へと拡張する. （目的変数の値が大きく異なるのでおそらく違う案件を用いた実験だと考えられる）

この実験でも, いずれかの価格帯に固定したり, baselineを用いるよりも, 提案手法を用いることで最大の売り上げを得ることができた.

5. コメント

• 徐々に介入を個別化していくようなsplit criterionの設計が面白い発想だった
• 実は同じ著者による後続研究でCTSは, 真に最適なmodelへと収束することが示されるらしい
• 人工データ実験でかなりデータが小さいところではbaselineに負けているのが気になる

6. 関連論文ピックアップ

CTSの理論解析

• Yan Zhao, Xiao Fang, and David Simchi-Levi. A Practically Competitive and Provably Consistent Algorithm for Uplift Modeling. In 2017 IEEE International Conference on Data Mining (ICDM). New Orleans, 2017.