「ビジネス課題を解決する技術」を読む　～5章　離散最適化で広告出稿番組を選択する②～

はじめに

森下光之助著「ビジネス課題を解決する技術～数理モデルの力を引き出す3ステップフレームワーク」は、数理モデルを活用して課題を体系的に解決する手法を提供する。本書を読む理由は，データサイエンスを製造業の現場に効果的に適用するための実践的なフレームワークを学び，チームの分析力を強化し，事業成果を最大化するためである。本書はマーケティングを題材としているが，製造業での応用を意識しながら読み進めていく。

本記事は，「5章　離散最適化で広告出稿番組を選択する」における後半部分に関する読書メモである。

改訂履歴

「追記事項(2025/07/13)」を記載(2025/7/13)。

追記事項(2025/07/13)

「ビジネス課題を解決する技術」において，離散最適化の近似解法として貪欲法が説明されていた。
2025/07/12に本記事を公開してから，貪欲法に関する記載について，@jacobtitor さんから「厳密な最適化計算が行える問題のような気がします」とのコメントを頂いた。
またXで @MickeyKubo さんが，最適化理論や凹費用の最小化について興味深いコメントを投稿されていた(参考ポスト)。
私はこれらのご意見を学びのきっかけとして受け止めており，さらなる議論やご意見を歓迎します。

本記事を読むことで得られること

本記事を読むことで得られることは，主に以下の内容である。

貪欲法による離散最適化の実行とその評価方法

はじめに
5.3　ステップ2：数理モデル構築し、未知のパラメータをデータから推定する
- 数理モデルの推定
- データを用いた予測精度の検証
5.4　ステップ3：数理最適化問題を解いて最適なアクションを導出する
- 貪欲法
- 貪欲法の検証
まとめと感想
- 参考サイト

5.3　ステップ2：数理モデル構築し、未知のパラメータをデータから推定する

数理モデルの推定

数理モデルを構築した結果，目的関数は以下のように表されることが確認できた。

$\begin{align} E[R \mid \boldsymbol{d}] = \frac{1}{n} \sum_{i=1}^n \left( 1- \prod_{j=1}^m (1 - \pi_{i, j})^{d_j} \right) \\ \\ \end{align}$

ここから個人 $i$ が番組 $j$ のCMに接触する確率 $\pi_{i, j}$ さえ求めれば，合算のユニークリーチを計算できることがわかる。この接触確率 $\pi_{i, j}$ を推定する方法を考える。

番組とCM出稿枠の関係を考える。企業 $k$ が番組 $j$ の放送枠を購入すると，番組 $j$ 内のいずれかのCM枠で毎週CMが放送される。個人ごとにこのCMに接触したかどうかのデータ $r_{i, j, k} \in \{0, 1\}$ が記録されているとすると，個人 $i$ の番組 $j$ のCM接触確率 $\pi_{i, j}$ は以下のように推定される。

$\begin{align} \hat{\pi}_{i, j} = \frac{1}{\lvert \mathcal{K}_j \rvert} \sum_{k \in \mathcal{K}_j } r_{i, j,k} \\ \\ \end{align}$

となる。ただし $\mathcal{K}_j$ は，番組 $j$ にCMを放送した企業の集合とする。

データを用いた予測精度の検証

データによって推定した接触確率を用いて計算した合算のユニークリーチの予測値と，合算のユニークリーチの実測値の散布図は，下図のようになる。

単に機械学習モデルを適用した場合よりも高い精度で合算のユニークリーチを予測できていることが確認できた。

5.4　ステップ3：数理最適化問題を解いて最適なアクションを導出する

ステップ2では，選択した番組群 $\boldsymbol{d}$ に対する合算のユニークリーチ $E[R \mid \boldsymbol{d} ]$ が未知であったが，これを推定することができた。

未知の部分が無くなった最適化問題は以下のようになる。

$\begin{align} \max _{\boldsymbol{d}} \quad & 1 - \frac{1}{n} \sum_{i=1}^n \prod_{j=1}^m (1-\hat{\pi}_{i, j})^{d_j} \\ \\ \mathrm{s.t.}\quad & \sum_{j=1}^m c_j d_j \leq b \\ \\ &d_j \in \{0, 1\} \quad \forall j=1,..., m \\ \\ \end{align}$

この最適化問題は，決定変数が $d_j \in \{0, 1\}$ である離散最適化問題である。ただし今回の問題設定では $m=113$ であり，厳密解を求めるには計算量が膨大になるそのため，貪欲法を用いて近似解を求める。

貪欲法

貪欲法は，目の前の一手一手で最適な選択を繰り返すという手法である。

目の前の一手よりも先の選択は考慮していないが，実装が容易であるため，近似解を求める手法としては多くの場面で利用される。

今回は具体例として，

予算 $b$ : 5,000万円
コスト $c_j$ : 500万円

とすると，制約条件は

$\begin{align} \sum_{j=1}^m 500 d_j \leq 5000 \Leftrightarrow \sum_{j=1}^m d_j \leq 10 \\ \\ \end{align}$

となり，113番組の中からユニークリーチを最大化する10番組を選択する問題になる。

貪欲法の検証

貪欲法によって求めた最適解が，合算のユニークリーチを効率的に獲得できているのか確認する。

貪欲法では，合算のユニークリーチを最大化する番組群が，追加順に得られている。そこで，

番組数ごとに，合算のユニークリーチを最大化する番組群を求め，その合算のユニークリーチを計算し，番組数を横軸・合算のユニークリーチを縦軸とするカーブを描く。
番組数ごとに，同じ番組数だけ出稿した企業の合算のユニークリーチの散布図を描く。

として，1. が2.よりも上回っているかどうかを確認する。

上記を描画した結果は下図の通りである。同じ番組数であれば，貪欲法による近似解は実測値を上回っているので，貪欲法によって番組群が効率的に選択できていることが確認できた。

まとめと感想

今回は，「5章　離散最適化で広告出稿番組を選択する」における後半部分についてまとめた。

今回の最適化問題は離散最適化問題であった。離散最適化問題は厳密解を求めることが難しいことが多いが，手軽に解を求める方法として，貪欲法を理解した。

貪欲法はヒューリスティックな解法であるが，ヒューリスティックな解法で得られた解は「本当にその解でよいのか？」という疑問がつきまとう。本章では，実測値のデータと比較することにより，貪欲法による解が良いことを示していた。厳密解に比べてどこまで近づいているか，ということについては答えられてはいないものの，実問題で意思決定するうえでは参考になる考え方だった。

本記事を最後まで読んでくださり，どうもありがとうございました。