OptimizationNightで発表した内容です。
Optimization-Night機械学習と数理最適化の融合を考える～広告予算配分を例に～
View Slide
自己紹介• 名前：魚井英生• 所属：ブレインパッド• 役職：シニアリードデータサイエンティスト• ブレインパッド社における役割：数理最適化、機械学習を組み込んだアプリケーション開発プロジェクトのリーダー。• これまでの経験配送計画の最適化生産計画の最適化広告予算の最適化実験配合の最適化需要予測＋発注の最適化ユーザーのスコアリングシステムなどなど。• 趣味：卓球
目次1. はじめに～機械学習と数理最適化の融合の分類について考えてみた～2. 広告予算の配分計画（基礎編）3. 広告予算の配分計画（応用編）4. まとめ
1. はじめに～機械学習と数理最適化の融合の分類を考えてみた～
機械学習（予測）と最適化（意思決定）の活用の大切さ機最明日70％の確率で雨が降ります。機械学習（予測）だけでは、「で、どうする？」で終わる。事故率 移動時間車 20 20歩き 20 60事故率 移動時間車 60 30歩き 20 60降水確率20％のとき 降水確率70％のとき車と歩きのどちらを選択するべきかを事故率と移動時間の関係から、最適化を通じて、意思決定できる。事故を避けたいなら、歩き。移動時間を短くしたいなら、車。＋
実務例1～需要予測に基づいた、発注計画～製品の出荷量を予測して、必要分を発注します。これにより卸倉庫の在庫量を削減します。機最＋卸倉庫メーカーA小売A商品xの1日後、2日後の出荷量を予測。商品x発注リードタイムが7日なので前もって発注。卸倉庫＜特徴量＞・商品xの前年同月実績・商品xのカテゴリ・予測される日の曜日＜制約＞・商品xの発注リードタイム・倉庫のキャパシティ・１回の発注の最大量
実務例2～消費量予測に基づいた、在庫配送計画～機最＋軒先の在庫の減り具合を予測して、必要な量を良いタイミングで配送します。軒先A 軒先B軒先A消費量予測配送ルートの作成＜特徴量＞・軒先Aの前年同月消費量・軒先Aのカテゴリ・予測される日の曜日＜制約＞・時間指定・トラックのキャパシティ・トラックの車格制限
一見、機械学習と数理最適化の融合に見えるが、• 予測問題と最適化問題を分割できる• 予測値が機械学習器である必要がない• 予測ロジックが最適化問題の定式化に一切影響を与えない• 機械学習の汎化誤差の最小化と、最適化の目的関数の最大化が独立の解ける。疎な融合問題
定式化で見る、疎な融合問題発注計画、在庫配送ともに、予測値しか定式化に現れない。商品pの日tの在庫量 商品pの日tの需要量（発注：出荷量配送：消費量）商品pの日tの補給量（発注：入庫量配送：供給量）予測値が機械学習である必要がない
実務例3～広告効果予測に基づく、予算配分計画～過去実績から広告効果を予測して、未来の予算配分を最適化します。機最＋費用リターン費用リターンリターン費用広告A広告A広告B＜特徴量＞・広告Aの前年同月リターン・広告Aのカテゴリ・予測される月＜制約＞・全体予算のキャパシティ・広告カテゴリのキャパシティ
実務例4～特性値予測に基づく、実験計画～過去実績から特性値効果を予測して、次の実験の配合を最適化します。機最＋原料配合特性原料配合特性＜特徴量＞・各原料の配合比・原料Aのカテゴリ・原料Aの保持する成分＜制約＞・原材料全体の原価のキャパシティ・原材料の配合比率の上下限
これらの例は、機械学習と数理最適化の融合か？• 予測問題と最適化問題を分割できない• 機械学習器の選択が、最適化問題の定式化に大きな影響を与える。密な融合問題
定式化で見る、密な融合問題機械学習器自体が、定式化に現れる。機械学習器の選択が定式化に大きく影響する。線形モデル→線形計画問題勾配ブースティング→ブラックボックス最適化問題
融合問題の分類まとめ1. 疎な融合問題 2. 密な融合問題集合分割、被覆問題最適化の難しさ過去の知見十分にある。・どのソルバーどのモデリングに適しているか・どの程度の規模まで解けるか不十分。・どのソルバーがどういった観点で良いか、まだわからない。・どの程度の規模まで解けるか現実問題の例配送計画、生産計画、シフト計画、発注計画広告予算計画、ダイナミックプライシング実験配合計画、商品の条件補正疎な問題は過去の知見が十分あるが、密な問題はこれから。最適化に対する機械学習の役割ブラックボックス最適化入力データ 目的関数、制約条件
2. 広告予算の配分計画（基礎編）
広告予算の配分計画問題とは？費用とリターンの関係から、来月、再来月の予算配分を決めます。2022年の実績を使って、2023年の予算計画を立てるにはどうすれば良いでしょうか？同じ費用でも、効果が月によって違う。正しく効果を見積もるにはどうすれば良いか？要因分解と言えば、機械学習！費用リターン2022年10月2022年11月2022年12月2022年9月2022年8月12月はイベントを打っていたので、同じ費用でも11月より大きい。100万 200万 300万
勾配ブースティングによる単調制約と交互作用を入れた要因分解費用に対して、リターンが減少することは考えにくいため、単調制約を入れた勾配ブースティングを用いることで、交互作用を入れてかつ費用の増加に対して、リターンが増加するようにできます。広告メニュー 日付 費用 カテゴリ（大） 月 祝日数 イベントフラグ 前年同月リターン 当月リターンA 2022年10月 200 ディスプレイ 10 2 0 230 250A 2022年11月 300 ディスプレイ 11 3 0 220 230A 2022年12月 500 ディスプレイ 12 5 1 450 470説明変数（意思決定）説明変数（外部要因）目的変数交互作用・・・イベントがあるときに費用とリターンの関係といった組み合わせ効果単調制約・・・費用が上がると、リターンが上がるといった効果
線形モデルだと交互作用効果を取り入れられない後続の最適化を意識するあまり、線形方程式で学習してしまうと、「イベントありでかつ前年リターンが250以上の場合の費用対効果」といった組み合わせ効果（交互作用効果）を取り入れられない。広告メニュー 日付 費用 カテゴリ（大） 月 祝日数 イベントフラグ 前年同月リターン 当月リターンA 2022年10月 200 ディスプレイ 10 2 0 230 250A 2022年11月 300 ディスプレイ 11 3 0 220 230A 2022年12月 500 ディスプレイ 12 5 1 450 470説明変数（意思決定）説明変数（外部要因）目的変数Y = a1 * x1 + a2 * x2 + ・・・線形ソルバーで解こうと意識しすぎるあまり、線形回帰してしまう（交互作用が得られない）。
Shapley-Valueによる要因分解学習した勾配ブースティングに対して、shapley-valueを見ることで、費用に対する効果を分解できます。同じ費用でも、shap値で見ると、上手く要因分解できれば効果が等しくなります。費用リターン2022年10月2022年11月2022年12月2022年9月2022年8月費用リターンのshap値2022年10月2022年11月2022年12月2022年9月2022年8月外部要因で分解され、ギャップが埋まる。（上手くいけば）
最適化に進む～予測値の列挙による、費用対効果曲線の作成～予算配分したい月に対して、予測値を列挙することで、費用対効果曲線を描くことができます。この費用対効果曲線は、配分したい月の要因を取り込んだ上で描くことができます。リターン費用2023年1月（イベントなし）広告メニュー日付 費用 イベントフラグ前年度リターンA 2023年1月 100 0 230A 2023年1月 110 0 230A 2023年1月 120 0 320配分月に対するデータマート予測値を列挙交互作用を含めた外部要因を取り込んで、費用対効果曲線の作成・・・
費用対効果曲線の外装補正勾配ブースティングは決定木をベースにしているため、費用の増加に対して、リターンがストップします。これに対処するために、逓減曲線でフィッティングすることで、外装領域に対して増加分を得るこができます。リターン費用実施したことがない領域は効果がストップする。階段な効果の増加と、外装領域における効果の一定化を避けることができる。マーケターの間隔とも合致。
混合整数計画（区分線形近似）による定式化配分月に対して、予測カーブが得られた後は、区分線形近似を用いることで、混合整数計画問題として定式化できます。このように、ブラックボックス最適化問題を回避することができます。リターン費用z_k z_{k+1}y_kどれか1つの刻み点が採用される（Type1-SOS制約）広告pの月tにおける費用＜決定変数＞：広告Aの月tに刻み幅kを採用する場合に1＜従属変数＞＜必須制約＞広告pの月tにおけるリターン
3. 広告予算の配分計画（応用編）
機械学習の予測を100％信用できない外部要因を取り込めているとはいえ、データ化れていない外部要因があるため、費用対効果曲線を100％信用できない。リターン費用広告A広告B予測精度が100％に到達することは現実的に不可能。どこまで信じられるか。最適化結果過去実績・・・マーケターからすると受け入れがたい、、広告C
機械学習と数理最適化の両サイドから追及する外部要因を増やして、精度を高めることは１つの方法ではありますが、現実的にありとあらゆる外部要因を集めることは現実的ではありません。そこで過去の実績に着目します。1. データを増やして精度を高める。（機械学習）2. 過去実績との逸脱をペナルティとする。（最適化）＋広告メニュー日付 費用イベントフラグ当月リターンコロナフラグA2023年1月100 0 230 1A2023年1月200 0 230 1A2023年1月300 0 320 1外部要因を足していく。（キリがない、、）1000広告Aの配分比率の分布1000広告Bの配分比率の分布最適化の決定（ペナルティ0）最適化の決定（ペナルティ10）
配分比率以外の評価指標、配分の傾きに注目する配分比率以外にも、配分の傾きに注目することも重要です。傾きは、費用対効果の効率性の指標です。広告Aリターン/費用のの分布リターン広告A実績の傾きの範囲費用効率が良すぎる（悪すぎる）結果を防ぐ
混合整数計画による、評価指標の四分位範囲から逸脱を表現する定式化指標の値が四分位範囲を逸脱したかどうかのバイナリ変数と、逸脱値を表す非負の連続変数を用いることで定式化することができます。有効範囲指標lの下限から値が逸脱した場合、その逸脱値がnlに入る。有効範囲指標lの上限から値が逸脱した場合、その逸脱値がpuに入る。• 𝑉𝑙𝑝,𝑡・・・広告pの期tの指標lの値。• 𝑛𝑙𝑙𝑝,𝑡 ・・・広告pの期tの有効範囲lの下限の下振れ値。• 𝑝𝑙𝑙𝑝,𝑡 ・・・広告pの期tの有効範囲lの下限の上振れ値。• 𝑧𝑙𝑙𝑝,𝑡 ・・・広告pの期tの有効範囲lの下限のよりも下振れる場合に1。• 𝑝𝑢𝑙𝑝,𝑡 ・・・広告pの期tの有効範囲lの上限の下振れ値。• 𝑛𝑢𝑙𝑝,𝑡 ・・・広告pの期tの有効範囲lの上限の上振れ値。• 𝑧𝑢𝑙𝑝,𝑡 ・・・広告pの期tの有効範囲lの上限のよりも上振れる場合に1。
【参考】分岐する制約が多い場合は、ヒューリスティックスソルバーが見やすい。分岐が多い制約は混合整数計画だとBigMが多様されてわかりづらいので、ヒューリスティックスベースのソルバーの方が書きやすい。1. 混合整数計画ソルバー（ex. pulp）2. ヒューリスティックスソルバー（ex. LocalSolver）penalty_lower = iif(V – lower < 0, abs(V - lower), 0)penalty_upper = iif(V – upper > 0, abs(V-upper), 0)三項演算子を使うことで、BigM法を使わずに直感的に制約条件の反映が可能。pu = LpVariable(name=f"portfolio_ratio_p_upper_{period}_{ad_id}",cat=LpContinuous,lowBound=0,)nu = LpVariable(name=f"portfolio_ratio_n_upper_{period}_{ad_id}",cat=LpContinuous,lowBound=0,)zu = LpVariable(name=f"portfolio_ratio_b_upper_{period}_{ad_id}", cat=LpBinary)constr1 = LpConstraint(e=pu - nu - (cost - upper * total_period_cost),sense=self._sense_map["="],rhs=0,name=f"portfolio_ratio_upper_def1_{period}_{ad_id}",)・・
辞書式最適化による優先度付きの多目的最適化目的関数が増えてきた場合には、辞書式最適化を用いることで、優先度を付与した上で多目的の最適化が可能。（パレート解を列挙する必要がない。）1が変わらないなら、2を最適化2が変わらないなら、3を最適化・・・優先度ごとに最適化が可能。目的 優先度配分比率の過去実績との逸脱を最小化 1配分効率（傾き）の過去実績との逸脱を最小化 2リターンを最大化 3
インターフェースによる工夫によって、計画の出し分けを可能に目的関数の優先度付けを行えるようにすることで、楽観的、悲観的な最適化結果を出し分けることが可能になりました。それらの結果を比較し、最終的にはマーケター（人手）による意思決定を推奨しました。楽観的な計画（機械学習を信じた計画） 保守的な計画（機械学習を信じすぎない計画）マーケター楽観的な計画・・・リターンの最大限の余地を知れる。保守的な計画・・・現実的に実行できる。感覚と合致する。目的 優先度配分比率の過去実績との逸脱を最小化 3配分効率の過去実績との逸脱を最小化 2リターンを最大化 1目的 優先度配分比率の過去実績との逸脱を最小化 1配分効率の過去実績との逸脱を最小化 2リターンを最大化 3最後は人手で判断
4. まとめ
まとめ1. 数理最適化と機械学習の融合を疎と密に分けて分類してみた。疎な融合問題は、機械学習が与える影響は少ないが、最適化問題自体が難しい。一方で密な融合問題は、最適化問題は簡単だが、機械学習器の選択が定式化に影響を大きく及ぼす。2. 密な融合の一例として広告予算の最適化問題を例に出した。勾配ブースティングを用いることで、要因分解を行うことができる。また、最適化問題を解きやすくするために、正面からブラックボックス最適化問題を解くのではなく、費用に単調制約を課した上で予測値を列挙することで、古典的な混合整数計画問題として定式化できることを示した。3. 機械学習とはいえ、データには表れていない外部要因があるため、効果曲線を100％信じ切って最適化を行うには、例え最適化問題が正しく解けていたとしても、効果曲線自体に不備がある可能性をぬぐい切れないため、数理最適化でペナルティ関数を定義することで、現実的に実行可能な範囲内で最適化結果を出すことができることを示した。また、インターフェースの工夫によって、楽観的、保守的な結果を出し分けられることを示した。計画を目的に応じて出し分けられるようにし、最後は人手で意思決定することで、実務に接続できるようにした。
機械学習×数理最適化×インターフェースの補完関係の大切さ機械学習 数理最適化交互作用を取り込んだ上で要因分解できる。機械学習で作り切れない特徴量による予測誤差を、数理最適化のペナルティ関数で補完。インターフェース制約条件のON/OFFおよび、目的関数の優先度付けを実行前に設定できる。真正面から難しい問題に取り組むのも良いが、各モジュールの補完関係を駆使することが重要に思います。
ae14watanabe
cardososampaio
nkmr_rl
ynakano
ssii
wakamatsu_takumu
furukawayasuto
miura55
milescranmer
lcolladotor
icoxfog417
erikaheidi
shpigford
addyosmani
orderedlist
kastner
philhawksworth
morganepeng
jnunemaker
chriscoyier
akosma
jlugia