最適決定木を用いた処方的価格最適化

最適決定木を用いた処方的価格最適化
株式会社リクルート 株式会社リクルート 法政大学
筑波大学
第0回 MOAI 研究部会(zoom) 2023年8月3(木) 14:00-15:00
池田 春之介 西村 直樹 鮏川 矩義 高野 祐一

Transcript

1. 最適決定木を用いた処方的価格最適化 1 株式会社リクルート 池田 春之介 株式会社リクルート 西村 直樹 法政大学 鮏川 矩義 筑波大学 高野 祐一 第0回 MOAI 研究部会（zoom） 2023年8月3(木) 14:00-15:00
2. 自己紹介 2  氏名：高野 祐一（Yuichi TAKANO）  所属：筑波大学 システム情報系 准教授  専門分野：数理最適化・金融工学・機械学習  研究室の学生の発表 第22回情報科学技術フォーラム（FIT2023） 2023年9月6日（水）～9月8日（金）大阪公立大学（ハイブリッド開催） A-005 二重単調性の緩和制約を用いたノンパラメトリック項目反応モデル ◎竹内 崇貴（筑波大学）・鮏川 矩義（法政大学）・高野 祐一（筑波大学） A-011 複数プロジェクトへの資源配分を考慮した競争入札戦略 ◎深谷 悠人（筑波大学）・鮭川 矩義（法政大学）・高野 祐一（筑波大学） A-023 船舶到着時刻の不確実性を考慮したコンテナ事前整列問題 ◦伊熊 大貴（筑波大学）・鮏川 矩義（法政大学）・高野 祐一（筑波大学） F-036 クーポン配布のロバスト最適化 ◎上原 祐輝（筑波大学）・鮏川 矩義（法政大学）・高野 祐一（筑波大学）・Deddy Jobson・Jie Yang・Yilin Li・松本 健（メルカリ）・西村 直樹（リクルート） F-042 機械学習を利用した混合整数最適化問題のオンライン高速求解 ◎武井 柊悟（筑波大学）・鮏川 矩義（法政大学）・高野 祐一（筑波大学） F-048 データコラボレーション解析を用いた推薦システム ◦柳 智也（筑波大学）・鮏川 矩義（法政大学）・高野 祐一（筑波大学）
3. 発表の構成 1. 研究背景 2. 提案手法 3. 数値実験 4. まとめと今後の課題 3
4. 発表の構成 1. 研究背景 2. 提案手法 3. 数値実験 4. まとめと今後の課題 4
5. • 製品やサービスの価格は消費者の需要に大きな影響を与えるため， 適切な価格戦略は企業の収益と利益を増大させる • 多くの企業で重要な意思決定課題である価格最適化の問題は， マーケティング分野の中心的なテーマとして広く研究されてきた • 実際に以下のような幅広いビジネスで応用され，成功を収めている • 情報通信技術の進歩により，消費者の需要をリアルタイムに価格に 反映でき，価格戦略が売上や利益に与える影響が大きくなっている 5 背景 小売 ホテル 鉄道 電力
6. • 処方的価格最適化のフレームワークは需要予測と価格最適化の ２段階で構成される • 需要予測では，価格と需要の関係を示す回帰モデルを構築する • 価格最適化では，構築された需要予測モデルに基づいて， 目的関数（売上や利益）を最大化する価格を決定する 6 背景 ①需要予測 ②価格最適化 処方的価格最適化 価格 𝑝 需要 𝑞 最適価格 𝑝∗ 価格と需要の関係を導出 求めた関係から最適価格を計算 価格 𝑝 𝑟 = 𝑝 × 𝑞 𝑝 売上 需要 𝑞
7. • 売上最大化を目的とした複数商品の価格設定 7 問題設定 定式化 集合 決定変数 とする ただし, 売上(価格×需要数)最大化 複数商品の価格設定
8. 先行研究[1, 2]： • 処方的価格最適化問題の一般的なフレームワークを確立 • 需要を線形回帰で表現し，0-1整数二次最適化問題（BQO）に定式化 • BQOを高速で解くためのアルゴリズムを提案 課題： • 需要を高精度で推定することが売上の向上に直結するため， 線形回帰よりも高精度の回帰モデルの利用が望ましい (ex. 勾配ブースティング決定木等) • より高精度の回帰手法の適用は，解きやすい問題への定式化が難しい （全列挙する場合は，十数個の商品でも現実的な時間で解くのは困難） 8 先行研究とその課題 解きやすい問題への定式化が困難 [1] S.Ito, R.Fujimaki, “Optimization beyond prediction: Prescriptive price optimization“, In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.1833-1841, 2017 [2] S.Ito, R.Fujimaki, “Large-Scale Price Optimization via Network Flow“, 30th Conference on Neural Information Processing Systems, 2016
9. 先行研究[3]： • 需要予測モデルにバギングを用いた回帰木を適用し， 0-1整数最適化問題として定式化 • 線形緩和を用いた高速アルゴリズムを提案 課題： • 需要予測の精度と引き換えに，交差価格弾力性（商品価格の変化が 他の商品の需要へ与える影響）を無視する強い仮定に依存 9 先行研究とその課題 [3] K. J. Ferreira, B. H. A. Lee, D. Simchi-Levi, Analytics for an online retailer: Demand forecasting and price optimization, Manufacturing & service operations management 18 (2016) 69–88.
10. 高精度の回帰モデルを用いつつ，現実的な時間で最適解が求められる 処方的価格最適化モデルを提案 1. 回帰モデルに解釈性を失わずに高い汎化性能が期待できる 最適決定木[4]を適用 (①需要予測) 2. 最適決定木を用いた価格最適化問題を混合整数線形最適化問題 （MILO）として定式化 (②価格最適化) 3. 大規模な問題にも対応可能な発見的解法を提案 10 本研究の位置づけ 精度向上 売上増 先行研究 本研究 処方的価格最適化 ①需要予測 ②価格最適化 線形回帰 BQO 最適決定木 MILO [4] D. Bertsimas, J. Dunn, Machine learning under a modern optimization lens. Charlestown, MA: Dynamic Ideas LLC, 2019.
11. 発表の構成 1. 研究背景 2. 提案手法 3. 数値実験 4. まとめと今後の課題 11
12. • 葉と枝の木構造を基にした回帰・分類の手法 • 説明変数で条件分岐して，説明変数の部分領域に分割 • 枝は評価指標を最大化・最小化するように貪欲に分岐 • 回帰の場合は，葉ノードのサンプルの平均値を予測値とする 12 決定木(CART)とは 決定木による回帰のイメージ D C B A 𝑥1 𝑥2 𝜃1 𝜃2 𝜃3 2 3 B 1 C D 𝑥1 > 𝜃1 𝑥2 > 𝜃2 𝑥2 > 𝜃3 葉ノード 枝ノード 貪欲に分岐 A 平均値で予測 σ𝑖 ∈𝐴 𝑦𝑖 |𝐴| 1変数で 分割 σ𝑖 ∈𝐵 𝑦𝑖 |𝐵| σ𝑖 ∈𝐶 𝑦𝑖 |𝐶| σ𝑖 ∈𝐷 𝑦𝑖 |𝐷|
13. • 複数の決定木の予測を組み合わせることで汎化性能が向上する 13 決定木を用いた回帰手法 勾配ブースティング (ex. LightGBM, XGBoost など) バギング (ex. Random Forest など) 独立に複数の弱学習器を構築し， 多数決や平均値を出力 弱学習器の弱点を補うように 新しい弱学習器を構築し， 多数決や平均値を出力
14. • CARTでは貪欲に分岐していくのに対し，数理最適化を用いることで 木の深さを指定し評価指標に基づいてすべての分岐を同時に最適化 • 1つの決定木によって，回帰モデルが表現されるため解釈性が高い • 実験的には勾配ブースティング決定木と同等の性能が示されている 14 最適決定木[4]とは 最適決定木のイメージ（回帰） 2 3 1 𝒂1 T𝒙 > 𝜃1 𝒂2 T𝒙 > 𝜃2 𝒂3 T𝒙 > 𝜃3 葉ノード 枝ノード すべての分岐を同時に最適化 A 葉ノードに回帰モデル 𝜷𝐴 Τ𝒙 + 𝛽𝐴 𝜷𝐵 Τ𝒙 + 𝛽𝐵 𝜷𝐶 Τ𝒙 + 𝛽𝐶 𝜷𝐷 Τ 𝒙 + 𝛽𝐷 超平面分割 B C D [4] D. Bertsimas, J. Dunn, Machine learning under a modern optimization lens. Charlestown, MA: Dynamic Ideas LLC, 2019.
15. • 各商品の需要𝑞𝑚 を予測するモデルを最適決定木により構築 15 最適決定木[4]による需要予測 最適決定木の定式化 各商品の最適決定木を構築すれば 価格最適化問題に組み込み可能 価格最適化問題の定式化 [4] D. Bertsimas, J. Dunn, Machine learning under a modern optimization lens. Charlestown, MA: Dynamic Ideas LLC, 2019.
16. 最適決定木を用いた価格最適化問題 最適決定木に関する制約 (1) (2) (3) (4) (5) (6) (7) (8) (9) 16 価格決定に関する制約 定式化 𝑝𝑚 : 商品𝑚の価格 𝑞𝑚 : 商品𝑚の需要 𝑥𝑚𝑘 : 商品𝑚の𝑘番目の価格選択有無（0-1変数） 𝑧𝑚𝑡 : 商品𝑚の葉ノード𝑡への割当有無（0-1変数） 決定変数
17. 最適決定木を用いた価格最適化問題 最適決定木に関する制約 (1) (2) (3) (4) (5) (6) (7) (8) (9) 17 価格決定に関する制約 (1)：総売上最大化 (2), (3)：各商品の需要𝑞𝑚 を葉ノード𝑡の回帰モデルで予測する (4), (5)：各商品の需要𝑞𝑚 は葉ノード𝑡への分岐条件を満たす (6)：各商品の需要𝑞𝑚 を必ずどれか一つの葉ノード𝑡に割り当てる 定式化 𝑝𝑚 : 商品𝑚の価格 𝑞𝑚 : 商品𝑚の需要 𝑥𝑚𝑘 : 商品𝑚の𝑘番目の価格選択有無（0-1変数） 𝑧𝑚𝑡 : 商品𝑚の葉ノード𝑡への割当有無（0-1変数） 決定変数
18. 最適決定木を用いた価格最適化問題 最適回帰木に関する制約 (2) (3) (4) (5) (6) (7) (8) (9) 18 価格決定に関する制約 (7), (8)：商品𝑚の価格を価格候補から一つだけ選ぶ (9)：𝑥𝑚𝑘 : 商品𝑚が𝑘番目の価格となる場合に1, そうでない場合に0 𝑧𝑚𝑡 : 商品𝑚が葉ノード𝑡に割り当てられる場合に1, そうでない場合に0 定式化 𝑝𝑚 : 商品𝑚の価格 𝑞𝑚 : 商品𝑚の需要 𝑥𝑚𝑘 : 商品𝑚の𝑘番目の価格選択有無（0-1変数） 𝑧𝑚𝑡 : 商品𝑚の葉ノード𝑡への割当有無（0-1変数） 決定変数
19. 定式化の問題点 • 目的関数が決定変数の積となり，非線形の混合整数最適化問題 （MINLO）となる →商用ソルバーでも厳密解を求めるのは困難 19 解きやすい問題への変形 定式化の工夫 • 補助変数を追加することで，目的関数を線形に等価変換 (𝒖𝒎𝒌 = 𝒙𝒎𝒌 𝒒𝒎 となる連続変数を導入) 元の定式化 (MINLO) 変換後の定式化（MILO） 等価 変換 非線形 線形 代入 𝒖𝒎𝒌 = 𝒙𝒎𝒌 𝒒𝒎 の関係性を表現
20. • MILO定式化では，木の深さ4・商品数20程度ならば厳密解が導出可能 • さらに大規模な問題では，現実的な時間で最適解を得ることは困難 • 座標上昇法に基づく発見的解法を提案 20 高速解法の提案 多スタート乱択座標上昇法 以下の手順を一定回数を行い，目的関数が最大となる場合を出力解とする 1. 初期解を生成 2. ランダムに商品を選び，他の商品の価格は固定したまま 選んだ商品の価格を最適化し暫定解を更新 3. 終了条件を満たせば終了，そうでなければ2へ戻る 価格集合： [価格1, 価格2, 価格3] 商品集合: [商品1, 商品2, 商品3] 商品1 商品2 商品3 価格2 価格3 価格2 初期解： 商品1 商品2 商品3 価格2 価格3 価格2 商品1 商品2 商品3 価格2 価格1 価格2 ランダムに商品を選択 解を更新 最適化
21. 発表の構成 1. 研究背景 2. 提案手法 3. 数値実験 4. まとめと今後の課題 21
22. 使用データ • 2種類（線形回帰/最適決定木）の真の需要モデルを仮定し， 人工データを生成 1. 真の需要モデルが線形回帰の場合 22 実験設定 𝑝𝑚 , 𝑞𝑚 ℳ 𝛽𝑚′ 𝑚 ∗, 𝛽 0 𝑚 ∗ 𝜀 𝑞𝑚 = ෍ 𝑚′∈ℳ 𝛽𝑚′ 𝑚 ∗𝑝𝑚′ + 𝛽 0 𝑚 ∗ + 𝜀, ∀𝑚 ∈ ℳ 商品𝒎の真の需要モデル： ただし，𝑚 = 𝑚のとき 𝛽𝑚′ 𝑚 ∗ ∼ N −1, 1 , 𝑚 ≠ 𝑚のとき 𝛽𝑚′ 𝑚 ∗ ∼ N 1, 1 , 𝛽 0 𝑚 ∗ ∼ U 100, 200 , 𝜀 ∼ N 0, 𝜎2 として， 𝛿 = 𝜎2/𝐸[𝑞𝑚 2 ]によってノイズを調整 価格は 𝑝𝑚′ ∈ 0.80, 0.85, 0.90, 0.95, 1.00 の5種類から選択 ：商品𝑚の価格，需要 ：商品の集合 ：商品𝑚の需要モデルの商品𝑚′に対する回帰係数，切片 ：商品𝑚の需要モデルのノイズ 基準価格に対する割合
23. 使用データ 2. 真の需要モデルが最適決定木の場合 23 実験設定 商品𝒎の真の需要モデル： 𝑞𝑚 = ෍ 𝑚′∈ℳ 𝛽𝑚′ 𝑚 ∗𝑝𝑚′ + 𝛽 0 𝑚 ∗ + 𝜀, ∀𝑚 ∈ ℳ ただし， 𝛽𝑚′ 𝑚 ∗, 𝛽 0 𝑚 ∗, 𝜀の生成方法は線形回帰の場合と同様 ෍ 𝑚′∈ℳ 𝑎 𝑚′𝑡 𝑚 ∗𝑝𝑚′ ≥ 𝑏𝑡 𝑚 ∗, ∀𝑚 ∈ ℳ, ∀𝑡 ∈ 𝒯 𝐵 (𝑚) 枝ノード 𝒕 での分岐条件： 𝑎 𝑚′𝑡 𝑚 ∗ 𝑏𝑡 𝑚 ∗ 𝒯 𝐵 (𝑚) ：商品𝑚の枝ノード𝑡の分岐条件の係数 ：商品𝑚の枝ノード𝑡の分岐条件の切片 ：商品𝑚の需要モデルの枝ノードの集合 𝑎 𝑚′𝑡 𝑚 ∗は{0, 1}からランダムに選択 𝑏𝑡 𝑚 ∗は{0.85, 0.90, 0.95}からランダムに選択 各葉ノードで設定
24. 比較手法 • 既存手法（需要予測：線形回帰，最適化：MILO） • 提案手法（需要予測：最適決定木，最適化：MILO & 発見的解法） • 発見的解法の設定： - 初期解の生成数： ℳ |𝒦| ( ℳ ：商品数，|𝒦|：価格候補数) - 終了条件：10回連続で目的関数が更新されない • 実験結果は真のモデルから生成されたデータから計算した 10回分の平均値を比較 24 実験設定
25. 需要予測の実験方法 • 真の需要モデルから訓練・検証データを生成し， 訓練データに対して学習を行い，検証データで評価を行う 評価指標 • 需要予測：MAPE（平均絶対値パーセント誤差） 25 実験設定 MAPE = 1 𝑁 ෍ 𝑖=1 𝑁 ො 𝑦𝑖 − 𝑦𝑖 𝑦𝑖 真の需要 モデル 需要予測 モデル ①生成 訓練データ ②訓練 検証データ ③予測 ④評価
26. 価格最適化の実験方法 • 真の需要モデルから訓練・検証データを生成し， 訓練データに対して学習を行い，検証データで評価を行う 評価指標① • 価格戦略の性能評価： (導出した価格が実際どの程度の売上を達成できるか) 26 実験設定 真の需要 モデル 需要予測 モデル ①生成 訓練データ ②訓練 ④評価 ③最適化 ③最適化 真の需要モデルの最適売上 = 真の需要モデルでの導出価格の売上 SQI ≔ 𝑓∗ ෝ 𝒑 𝑓∗ 𝒑∗ (≤ 1) 価格最適化の 目的関数 𝑓∗(𝒑) 価格最適化での 目的関数 መ 𝑓(𝒑) 𝒑∗ = argmax 𝑓∗(𝒑) 𝒑 ෝ 𝒑 = argmax መ 𝑓(𝒑) 𝒑 ④評価
27. 価格最適化の実験方法 • 真の需要モデルから訓練・検証データを生成し， 訓練データに対して学習を行い，検証データで評価を行う 評価指標② • 売上の推定評価： (推定した売上が最適な売上とどれだけ乖離するか) 27 実験設定 真の需要 モデル 需要予測 モデル ①生成 訓練データ ②訓練 ④評価 真の需要モデルの最適売上 = 推定した需要モデルでの導出価格の売上 EAI ≔ መ 𝑓(ෝ 𝒑) 𝑓∗(𝒑∗) ④評価 ③最適化 価格最適化の 目的関数 𝑓∗(𝒑) 𝒑∗ = argmax 𝑓∗(𝒑) 𝒑 ③最適化 価格最適化での 目的関数 መ 𝑓(𝒑) ෝ 𝒑 = argmax መ 𝑓(𝒑) 𝒑
28. • 訓練データ数が十分にあれば，線形回帰で生成したデータでは 線形回帰と同程度，回帰木で生成データでは線形回帰を上回る （青字：提案手法，黒字：既存手法） 需要予測の結果 真のモデルが線形回帰の場合 真のモデルが最適決定木の場合 LR：線形回帰，ORT：最適決定木 28
29. • 訓練データ数が十分にあれば，線形回帰による生成データでは 線形回帰と同程度，回帰木による生成データでは線形回帰を上回る 厳密解法での価格最適化の結果 (1/3) 真のモデルが線形回帰の場合 真のモデルが最適決定木の場合 29 LR：線形回帰，ORT：最適決定木 SQI：価格戦略の性能評価（最適売上に対する導出価格の売上の比率) EAI：推定した売上の評価（最適売上に対する推定売上の比率）
30. • 商品数を増やした場合でも，線形回帰による生成データでは 線形回帰と同程度，回帰木による生成データでは線形回帰を上回る 厳密解法での価格最適化の結果 (2/3) 真のモデルが線形回帰の場合 真のモデルが最適決定木の場合 30 LR：線形回帰，ORT：最適決定木 SQI：価格戦略の性能評価（最適売上に対する導出価格の売上の比率) EAI：推定した売上の評価（最適売上に対する推定売上の比率）
31. • ノイズを増やした場合でも，ノイズが0.4以下の場合では同様の傾向 （ノイズ0.4は誤差が40%を表すため，実用的な範囲で有用） 厳密解法での価格最適化の結果 (3/3) 真のモデルが線形回帰の場合 真のモデルが最適決定木の場合 31 LR：線形回帰，ORT：最適決定木 SQI：価格戦略の性能評価（最適売上に対する導出価格の売上の比率) EAI：推定した売上の評価（最適売上に対する推定売上の比率）
32. 発見的解法の計算時間(秒) • 木の深さが2以上のときはMILOよりも高速に求解 (|ℳ|：商品数，𝐷∗：真の需要モデルの木の深さ) 32 発見的解法での価格最適化の結果 (1/2) ※平均値と標準誤差を記載 MILO：混合整数線形最適化，MRCA：発見的解法
33. 33 発見的解法での価格最適化の結果 (2/2) 発見的解法の解の精度 • 厳密解が求まる範囲において，ほとんどの場合で最適解と一致 (|ℳ|：商品数，𝐷∗：真の需要モデルの木の深さ) ※平均値と標準誤差を記載 MILO：混合整数線形最適化，MRCA：発見的解法
34. 本研究のまとめ • 既存手法よりも高い予測精度が期待できる最適決定木を適用した 処方的価格最適化モデルを提案 • 非線形な混合整数最適化問題（MINLO）を混合整数線形最適化問題 （MILO）に等価変換することで現実的な時間で最適解が取得可能に • 大規模な問題にも対応できる高速解法を提案 • 数値実験にて，提案手法の有用性を確認 今後の課題 • 予測モデルの推定誤差や分布の変化などの不確実性にも対応できる ロバスト最適化の検討 • 予測モデルの学習と価格最適化を同時に行う処方的価格最適化モデル の構築 • 実際のサービスでのオンライン検証 34 まとめと今後の課題
35. EOF 35