リクルートにおける数理最適化の活用事例と産学連携の取り組み

© Recruit Co., Ltd. All Rights Reserved
リクルートにおける数理最適化の
活用事例と産学連携の取り組み
1
株式会社リクルート
西村直樹 [email protected]
2023/9/12

View Slide

自己紹介
2
西村直樹
株式会社リクルート
データ推進室
アジリティテクノロジー部
#販促領域 #人材領域　
#入社9年目 #横浜市在住
#シニアデータサイエンティスト
#Pythonではじめる数理最適化
氏名
所属
タグ

View Slide

Contents
1. リクルートのデータ組織
2. 数理最適化の産学連携の取り組み
3. 数理最適化活用施策の紹介
3.1. ビジネス要件付きの推薦商品決定
3.2. クーポン配信対象者の決定
3.3. 商品価格の決定支援
3

View Slide

Contents
4

View Slide

リクルートのデータ組織：データ推進室
5
各事業領域のデータ戦略立案・推進を行う領域特化ユニットと
領域横断で支援を行う専門職種のユニットが交差するマトリクス型組織
データテクノロジーユニット
DPU
販促1
DSU
販促2
DSU
販促3
DSU
販促4
DSU
SaaS
DSU
HR
DSU
アジリティテクノロジー部　より高度な専門性を基に領域・横断の重要案件の支援を行う
DPM1部 DPM2部
主務組織（領域戦略の実現のための活動に責任を持つ）
DTL部
Megagon
ATL部
D3M部(Data Driven Decision Making)
データエンジニアリング部
データサイエンス・機械学習エンジニアリング部
採用・育成を含む
専門性強化に
責任を持つ

View Slide

6
機械学習による予測のタスクは各事業領域
で多く活用されるように
　
すべての技術について、どの事業領域にも
十分にひとがいる、というわけではない
　
数理最適化技術：解くべき課題を計算機で
解ける形の問題としてモデリングする部分に
ハードルがあり、予測タスクと比べると
活用実績は少ない
　
数理最適化の技術普及や案件探索のために　
実施している取り組みと活用事例について紹介
リクルートの事業領域の例
データ組織での数理最適化技術の活用

View Slide

Contents
7

View Slide

数理最適化寄附講座との産学連携
8
● 月次で社内の数理最適化関連の案件を横断的にレビューいただいた
● 案件相談会として定期的にレビューいただくことで複数の利点があった
① 数理最適化関連の案件相談
② 数理最適化セミナー
③ 社内事例共有会
● 隔週で講義形式のオンラインセミナーを実施いただいた
● 広いバックグラウンドのメンバーの案件企画のきっかけとなった
● 数理最適化関連の案件担当者が持ち回りで案件共有をした
● オブザーバーとして参加いただくことで新たなアプローチの発想が得られた

View Slide

● 個別案件としては2018年度から実務課題をテーマとした共同研究を実施
● 2020年度から月次の頻度で、各回複数領域の案件について議論
① 数理最適化関連の案件相談
▼ 大阪大学大学院情報科学研究科年報 2021年度 WEB版より
9
https://www.ist.osaka-u.ac.jp/japanese/dept/istplaza/R04/IST-Plaza2022.pdf

View Slide

● 担当者だけでなく専門家や参加者も複眼的に解決策を検討
● 客観的な観点が入るため、既存手法調査や検証がより丁寧に
10
事業領域外
分析者
案件ディレクター
専門家
(大学教員)
複眼的な検討
案件担当
分析者
複眼的な検討により
案件の成功確度が向上
利点1. 案件の成功確度の向上

View Slide

11
● ひとりが1期で担当できる案件数には限りがある
● 自身の案件に加えて他の案件の検討にも参加することで
実課題の解決策の引き出しが増える
専門家
(大学教員)
知見獲得
事業領域外
分析者
案件担当
分析者
多様な実ケーススタディに
ついての議論により知見獲得
利点2. 社内分析者の知見獲得

View Slide

12
● 検討のみ参加していた案件へ、途中から参画を希望して
もらい、活躍機会が創出されたことも
専門家
(大学教員)
案件参画
事業領域外
分析者
案件担当
分析者
技術適性のある案件への
参画機会の創出
利点3. 社内分析者の活躍機会の創出

View Slide

社内での数理最適化の技術活用
の普及と案件探索を目的として
隔週の頻度で開催
　　
応用事例紹介など、案件企画者
も対象とする回と、実装者向けに
理論的な内容を扱う回を区別して
アナウンス
　　
本セミナーがきっかけで、専門外
のメンバーが数理最適化の活用を
着想された案件も
13
② 数理最適化セミナー

View Slide

③ 社内事例共有会
数理最適化関連の案件に関わる複数の
事業領域のメンバーがあつまり、
各回持ち回りで案件共有
　　
ウェブ媒体などでの公開を見据えて、
領域固有知識がなくても理解できるか、
他の取りうるアプローチはあるかなど議論
　　
オブザーバーとして梅谷先生にも参加
いただいた
　　
担当領域に閉じず詳細の事例共有がされ
領域横断で取り組む案件も生まれた
14
＠IT連載　「リクルート事例で分かる数理最適化入門」
https://atmarkit.itmedia.co.jp/ait/series/28443/

View Slide

Contents
15

View Slide

背景：ビジネス要件付きの推薦商品決定
実務での商品推薦ではビジネス要件
を満たすことが求められることがある
● 商品の推薦数の上下限
● 会員への推薦数の上下限
● 推薦総数の上限
● 全体推薦効果の下限
素朴にスコアの高い順の送付/表示
では要件を満たせない場合がある
16
商品会員

View Slide

事例：全体推薦効果を一定以上担保した上での目標効果達成商品数の最大化
● 想定する推薦システムの仕様
○ 会員がウェブページに来訪すると
その時点の会員の属性と行動の情報
に応じて商品が推薦される
● ビジネス要件
○ 目標効果を達成する商品の数を最大化
○ 全体の推薦効果は一定以上を担保
○ 会員への推薦商品数の上限あり
17
商品会員
推薦を偏らせず、
目標効果を達成できる
商品数を増やしたい

View Slide

定式化：全体推薦効果を一定以上担保した上での目標効果達成商品数の最大化
定式化できたので解けば解決？
18
目標効果を達成する商品数の最大化
　
　
商品 j の効果が目標効果を超えるとき
z
j
= 1 となる
　
全体の推薦効果は L 以上
　
各会員に対する推薦商品数は N 以下
商品ｊが目標効果を達成するとき1,
そうでないとき0となる決定変数
商品 j の目標効果
全体推薦効果の下限
会員 i に商品 j
を推薦するかどうか
の決定変数
推薦商品数
会員 i へ商品 j を
推薦時の推定効果

View Slide

課題：問題規模の大きさと訪問者の不確実性
19
● 問題規模の大きさ
○ 商品数と会員数が大きい場合
には解くのが難しい
○ 整数計画問題のため解ける規模
は大きくない
● 訪問者の不確実性
○ 推薦結果だけでなく、来訪して
推薦システムの表出に触れるか
どうかも予測が難しい
○ 問題の求解後に登録する
新規会員には推薦ができない
・
・
・
・
・
・
×
数が多い
訪問
しない
新規
登録

View Slide

課題に対するアイデア
20
AがBよりも全体的に
スコアが高く、Aは
達成だがBは未達に
一般的な推薦システムと同様にスコアの降順に選択したとき、元の最適化問題
を解いた結果と近くなるようなスコアの調整係数を得たい
素朴なスコア
による推薦
調整したスコア
による推薦
0.3
0.4
調整係数
×1
0.4
0.6
Bのスコアを理想的な
結果をもとに調整する
ことで両方達成に
調整係数
×2
0.6
0.8
0.6
0.8
A
B
A
B

View Slide

調整係数算出のための二段階最適化の流れ
● 一段階目
○ 会員についてサンプリングして元の最適化問題を解く
→ 小さな問題であれば頻度高く問題を解き直すことができる
● 二段階目
○ 元の最適化問題と結果が近くなるようなスコアの調整係数を算出する
ための最適化問題を解く
→ 調整係数として扱うことで既存の推薦システムのスコアに対して
　　素朴に掛け合わせるだけで適用することができる
21
アイテム推薦における公平性考慮のための二段階最適化, 濱田賢吾, 西村直樹, 梅谷俊治,
日本オペレーションズ・リサーチ学会 2023年春季研究発表会

View Slide

一段階目：会員についてサンプリングして元の最適化問題を解く
22
目標効果を達成する商品数の最大化
　
　
商品 j の効果がサンプリング率×目標
効果を超えるときz
j
= 1 となる
　
全体の推薦効果は L×サンプリング率
以上
　
各会員に対する推薦商品数は N 以下
サンプリング率
サンプリングした
会員の集合
実用的に解ける程度の
サンプリング率にする

View Slide

二段階目：スコアの調整係数を算出するための最適化問題を解く
23
制約違反のペナルティ総和の最小化
元のスコアG
ij
× 調整係数λ
j
が
元問題で推薦されるときにはt
i
以上、
推薦されないときにはt
i
以下
うまくλ
j
で事前の推薦結果に調整
できない際はペナルティp
ij
がかかる
制約違反のペナルティ(決定変数)
会員 i に対して推薦するか
否かのスコア閾値(決定変数)
スコアの
調整係数
(決定変数)
一段階目の問題で決めた
推薦するか否かの結果
サンプリングした会員の分布が全体の会員の分布に近ければ、得られた λ
j
による補正スコアの高い順
に会員 i に対して貪欲に選択することで、元問題を解いた結果と近い結果を得ることが期待できる

View Slide

実験結果の概要
24
商
品
の
ス
コ
ア
商品
商品のスコアの分布
全スコアの総和商品の目標達成率
貪欲法 1,056(110%) 28%(48%)
提案手法 955(100%) 58%(100%)
最適割当 972(102%) 62%(107%)
各手法の数値と対提案手法比
※（）内は対提案手法比
● 提案手法対貪欲法
○ 提案手法は全体効果（全スコアの総和）は大きく減らさず、商品の目標スコア
達成率は2倍程度改善されている
● 提案手法対最適割当 (一段階目のみ解いた結果)
○ 推薦時に最適化問題を陽に解かない軽量な方法でも、実際に最適化問題を
解く場合と近い性能が達成されている
目標値
貪欲法
提案手法

View Slide

今後のテーマ：ビジネス要件付きの推薦商品決定
● 大規模な2部グラフのマッチング問題のよい問題分割
○ サービスによっては商品数の規模が大きく、会員数でサンプリング
した一段階目の最適化問題も解くのが難しい
○ 問題規模が大きくなると素朴な方法でも処理に時間がかかるため、
問題分割をして並行処理しなければならない
○ 元問題を解いた結果と近い結果が得られるような問題分割をしたい
25

View Slide

Contents
26

View Slide

背景：クーポン配信対象者の決定
多くのサービスで、新規会員の初回
利用やリピート会員の継続利用を促す
目的でのクーポンキャンペーンが実施
されている
限られたキャンペーン予算のもとで、
効果を最大化したい
27
割引クーポンのイメージ
「ギフト券の見方を知りたい（期間・対象メニューなど）」より

View Slide

事例：費用制約のもとでのクーポン配信による売上最大化
● 想定するクーポン配信システムの仕様
○ バッチ処理にて全配信候補の
会員に対してクーポンの配信、
非配信を決定
○ 候補会員全体の利用売上の最大化
○ 期待費用は一定以下
○ クーポンの種類は定額の1種類のみ
28
10,000円
非配信
1,000円
配信
5,000円
× 期待売上
会員
各会員へクーポンを配信/非配信の
ときの真の売上/費用がわかれば
　配信対象者を決定できそう

View Slide

定式化：費用制約のもとでのクーポン配信による売上最大化
29
売上推定値増分の総和の最大化
期待費用の総和は一定以下
(クーポン額面×クーポン利用確率)
クーポン配信(1)/非配信(0)
での売上推定値
キャンペーン予算
クーポン額面
配信(1)でのクーポン利用確率推定値
会員 i にクーポンを配信する
かどうかの決定変数
● ナップサック問題となるため、ρ
i
（売上推定値増分/期待費用）の
大きな会員の順に貪欲に選択すると x
i
の線形緩和問題の最適解に
定式化できたので解けば解決？

View Slide

課題：予測対象が複数存在することにより優先度付けが不安定に
30
会員 i の真値 10,000 5,000 500 10
予測パターン1 12,000 3,000 300 30
予測パターン2 20,000 17,500 250 10
誤差大
誤差小
それぞれで予測モデルを作成すると、各予測モデルは誤差が
小さくても優先度ρ
i
の誤差が大きくなってしまうことがある
誤差小誤差小
誤差大誤差大誤差大誤差小
配信の売上非配信の売上配信の費用

View Slide

既存手法: Transformed outcome
Maciej Jaskowski and Szymon Jaroszewicz. Uplift modeling for clinical trial data.
In ICML Workshop on Clinical Data Analysis, Vol. 46, pp. 79–95, 2012.
31
会員
A 300円？？
B ? 200円？
C 250円 ? ？
会員
A 300円？ 600円
B ? 200円 −400円
C 250円 ? 500円
観測データからは介入有無
での売上差は入手不可能
学習データ中の T
i
=1 の比率
左表はp=0.5で計算
売上差の不偏推定となるよ
うに、r
i
を目的変数として予
測モデルを1つ学習
配信の
売上観測値
非配信の
売上観測値
配信するかどうかの{0,1}

View Slide

32
定額のインセンティブ付与における予算制約を考慮したアップリフトモデリング, 松井諒生, 吉住宗朔,
西村直樹, 小林健, 中田和秀, 日本オペレーションズ・リサーチ学会 2023年春季研究発表会
会員の利用履歴 (売上>0) を学習データとして、ρ
i
を直接
目的変数として学習するような予測モデルを作成したい
配信予約確率 × 配信観測売上非配信予約確率 × 非配信観測売上
配信予約確率
ー
配信予約確率
配信売上期待値ー非配信売上期待値
∝
＝
優先度ρ
i
：=
配信費用期待値
配信観測売上
非配信予約確率
ー
配信予約確率
× 非配信観測売上

View Slide

クーポン配信の優先度算出の流れ
優先度ρi
33
● 優先度算出モデルの学習
○ 会員 i の特徴量をもとに　　　　　　　　の推定値を
推論
○ Si(Ti)>0のデータを用いて優先度
を算出
○ 優先度 r
i
を会員 i の特徴量をもとに学習
　
● 優先度算出モデルによる推論
○ 会員 i の特徴量をもとに r
i
の推定値を算出
配信観測売上
非配信予約確率
ー
配信予約確率
× 非配信観測売上
∝
特定の仮定のもとでの期待値が
ρ
i
に対する不偏推定量に

View Slide

34
提案手法
ランダム
Transformed outcome
/費用予測
全会員に付与した場合を1とする
費用の利用比率
※ Kevin Hillstrom:　MineThatData
● ECサイトでのRCTメール配信の公開データ※に対して売上ごとに
定額費用がかかる設定で検証
● 10-fold CVの結果の平均と95%信頼区間を記載
費
用
あ
た
り
の
売
上
増
分
提案手法は売上差、費用を個別に予測し
優先度付けした既存手法に比べて費用を
利用したときに売上増分が大きくなる
対象に配信できている
限られた会員に対してクーポン配信
するとき特に効果差が大きい

View Slide

今後のテーマ：クーポン配信対象者の決定
● 複数種類、定額以外などの状況での拡張
○ ５００円/1000円/1500円など多種のクーポン
○ 10%引きなどの定率のクーポン
● 長期効果（Lifetime value) の考慮
○ 短期効果を最大化する配信対象と、長期効果も加味した場合の
配信対象は異なるのでは
○ 長期効果も加味しつつ、A/Bテストは短期間で実施したい
35

View Slide

Contents
36

View Slide

背景：商品価格の決定支援
37
価格運用者
明確な方針
暗黙の方針
売上を最大化
利益率目標はX%
商品価格を市況に合わせて細かく人手で
調整するのは労力を要する
　
人手で設定するのと遜色のない商品価格を
迅速に設定したい
　
価格設定のビジネス要件には明文化された
ものもあれば暗黙知化されているものもある
価格操作範囲は...
1日の価格操作数は...
景況がいいときには...

View Slide

事例：商品カテゴリごとの暗黙の価格操作範囲の自動推定
38
価格運用者
明確な方針
暗黙の方針
売上を最大化
利益率目標はX%
価格操作範囲は...
1日の価格操作数は...
景況が良いときには...
目的関数：期待売上（最大化）
制約条件：全体利益率期待値 ≧ 目標利益率
下限 ≦ 価格 ≦ 上限
下限 ≦ 価格操作数 ≦ 上限
特定の条件での制約条件
商品カテゴリごとの価格割当問題
過去データから暗黙
の制約条件を特定
● 想定する価格提案システムの仕様
○ 全体利益率目標や価格操作範囲などのパラメータを厳密な値ではなく
何段階かの程度で価格運用者が入力する
○ 方針に沿い、手動修正が少なくなるような提案価格（利益率）リストを作成

View Slide

具体例：各カテゴリごとの商品価格操作の可視化
39
価格操作前利益率価格操作前利益率価格操作前利益率
価
格
操
作
後
利
益
率
カテゴリA カテゴリB カテゴリC
● カテゴリごとに価格操作が実行される範囲が異なる
→ 提示する価格操作の実行可能範囲を個別に設定することが必要
利益率1.0から
1.2に値上げ操作

View Slide

既存手法：数値属性相関ルール (最適確信度相関ルール)
40
支持度の最低値が与えられたもとで確信度が最大の区間を算出する
価格操作前利益率
価
格
操
作
後
利
益
率
支持度 =
確信度 =
選択区間の操作領域数
すべての区間の操作領域数
選択区間の領域数
選択区間の操作領域数
Fukuda, T., Morimoto, Y., Morishita, S., & Tokuyama, T. (1999). Mining optimized association rules for numeric
attributes. Journal of Computer and System Sciences, 58(1), 1-12.
例：最低支持度80%のときの最適区間
支持度 = 5/6 (83%) , 確信度 = 5/5

View Slide

課題：推定操作範囲の過去データに対する過剰適合
41
● 価格操作前利益率区間ごとに独立に最適区間を推定した場合
サンプルサイズが少ない部分が極端な範囲をとる（過剰適合）
● 得られた範囲について解釈が難しい（暗黙知の理解の観点）
→ そのまま価格設定範囲の制約条件として利用するのは適さない
最低支持度90%の最適区間の例
価
格
操
作
後
利
益
率
価
格
操
作
後
利
益
率
操作前利益率区間：0.1 操作前利益率区間：0.01
1.0は0.9よりも
下限が低い？

View Slide

42
価格操作範囲の特性を運用者へのインタビューをもとにした知見により修正
価
格
操
作
後
利
益
率
価格操作範囲の特性
① 価格操作上下限の単調性
　（操作前利益率が高いほど上下限は高い）
　
② 価格操作上限の凹性
（上限増加幅は操作前利益率が高くなるにつれ減少）
　
③ 価格操作下限の凸性
（下限増加幅は操作前利益率が高くなるにつれ増加）
①＋②
①＋③
レベニューマネジメントにおける暗黙知を考慮した最適化モデルの自動構成, 西村直樹, 池田春之介,
木村隆介,　梅谷俊治, 第23回情報論的学習理論ワークショップ(IBIS2020)

View Slide

定式化：価格操作の特性を考慮した範囲修正
43
操作領域数が多い操作前利益率範囲 r の上下限に重みをつけ、単調性・
凹性・凸性の制約のもとで誤差が最小となるよう操作範囲を修正
操作前利益率範囲 r
の操作領域数
操作前利益率範囲 r
の操作後利益率上限の
修正値・算出値〃下限の
修正値・算出値
上下限の算出値との重み付き2乗誤差最小化
価格操作上限の単調性
価格操作下限の単調性
価格操作上限の凹性
価格操作下限の凸性
価格操作上限の推定値は下限の推定値より大
①
②
③
43

View Slide

44
算出値（補正なし） ①単調性補正 ②③凹性凸性補正
操作前
利益率
区間
0.01
操作前
利益率
区間
0.1
①②③単調性凹性凸性補正
● 提案手法の範囲修正モデルにより操作範囲は以下のように修正された
● 5-fold CVによる範囲誤差は①②③の修正を加えた場合が最も良い

View Slide

今後のテーマ：商品価格の決定支援
45
● 最適化結果をよくするような予測モデルの学習
○ 価格などを入力とした売上予測モデルの学習と、売上予測を入力
とした最適化を別に実施するのでなく、最適化結果を良くするよう
な予測モデルを直接学習したい
● ビジネス観点の評価方法の確立
○ 価格付けは商品推薦などのタスクと異なりユーザーごとに価格を
変えたA/Bテストが難しい
○ システムで決定した提案価格が運用者によって必ず適用される
とは限らない

View Slide

その他の事例
46
● キッチンモニターでの調理順提案
○ 調理遅れ時間の総和の最小化
○ 注文された料理は調理される
　
● TVCMの出稿割当の決定
○ 全対象CMの視聴者の最大化
○ 各CMへの視聴者数を担保
　
● フリーペーパーの配送計画
○ 総移動距離の最小化
○ ドライバーやトラック積載量の
制約条件を遵守
＠IT連載　「リクルート事例で分かる数理最適化入門」
https://atmarkit.itmedia.co.jp/ait/series/28443/

View Slide

おわりに
47
● 数理最適化関連のリクルートの産学連携の取り組みと事例を紹介
● 今後のテーマとした課題について興味をもっていただいた方や、
一緒に取り組んでくださる方がいれば、ぜひお声掛けください

View Slide

リクルートにおける数理最適化の活用事例と産学連携の取り組み

リクルートにおける数理最適化の活用事例と産学連携の取り組み

Recruit
PRO

More Decks by Recruit

Other Decks in Business

Featured

Transcript

リクルートにおける数理最適化の 活用事例と産学連携の取り組み

リクルートにおける数理最適化の 活用事例と産学連携の取り組み

Recruit PRO

More Decks by Recruit

Other Decks in Business

Featured

Transcript

リクルートにおける数理最適化の活用事例と産学連携の取り組み

リクルートにおける数理最適化の活用事例と産学連携の取り組み

Recruit
PRO