はじめに
こんにちは、事業会社で働いているデータサイエンティストです。
これは、レコメンドエンジンの推定結果を用いて、限られた資源をいかにユーザーに最適配分するかを説明する記事の第2回です。
前回の記事はこちらです：
今回の記事では、前回の記事で推定したモデルを活用し、ユーザーと映画を制約条件のもとでどのようにマッチングするかを実際のコードとともに紹介します。
具体的には、
- 一人のユーザーは 最大5本の映画しか観ない
- 一つの映画は 最大5人のユーザーまでしか受け付けない
といった制約を設け、その上でレコメンドモデルが推定した「ユーザーの好み」をもとに、数理最適化を用いて最適な割り当てを設計していきます。
さらに、
「数理最適化って本当に効いているの？ランダムなマッチングと大差ないのでは？」
という疑問に応えるために、シミュレーションを実施。結果として、数理最適化パッケージがしっかりと高い性能を発揮していることを示します。
それでは、さっそく本文に入っていきましょう。なお、本記事のコード内で使用する変数やデータは、前回の記事で定義したものをそのまま引き継いでいます。
また、本記事は実装寄りの記事のため、専門的な内容に言及しても特に文献を引用しない予定です。ご了承ください！また別の記事で詳細を話します。
数理最適化の定式化
詳細は少しおさらいすると、前回の記事で、ユーザー $i$ の映画 $j$ に対する選好度を
$$
評価スコア_{ij} = \phi_{j} + \sum_{d=1}^{\infty}\left( \gamma_{i,d} \cdot \zeta_{j,d} \cdot \delta_{d} \right)
$$
で定式化しました。
これは、映画ごとの人気度項 $\phi_j$ に加えて、ユーザーと映画の無限次元潜在ベクトル $(\gamma_{i,d}, \zeta_{j,d})$ の内積を、次元ごとの重み $\delta_d$ で調整したものになっています。
本記事では、映画自体の人気度を無視して、純粋なユーザーと映画の相性を示すバージョンを利用します：
$$
評価スコア_{ij} = \sum_{d=1}^{\infty}\left( \gamma_{i,d} \cdot \zeta_{j,d} \cdot \delta_{d} \right)
$$
次に、このスコアを最大化するように、ユーザーと映画のマッチングを行います。
すなわち、$評価スコア_{ij}$ に基づいて、各ユーザーが割り当てられた映画から得られる満足度の総和を最大化することが今回の目的です。
「ユーザーにスコアがマイナスの映画を見せなければよく、他の映画を全部見せればいいのでは？」という考えもあります。しかし今回のシナリオでは、
- 一人のユーザーは 最大5本の映画しか観ない
- 一つの映画は 最大5人のユーザーまでしか受け付けない
という制約があるため、単純に「見せたい映画を全部見せる」ことはできません。
このような条件のもとで、どのユーザーにどの映画を割り当てるかを最適に決めるために、数理最適化が登場するわけです！
まずは、マッチング結果を示す 決定変数 $x_{i,j}$ を定義しましょう。
ここで、$x_{i,j} = 1$ なら「ユーザー $i$ に映画 $j$ をマッチングさせる」、$x_{i,j} = 0$ なら「マッチングさせないない」と解釈します。
今回のシナリオの2つの条件のもとで、
- 一人のユーザーは 最大5本の映画しか観ない
- 一つの映画は 最大5人のユーザーまでしか受け付けない
どのようにして $x_{i,j} = 1$ の割り当てを決定し、マッチング結果の $評価スコア_{ij}$ の総和を最大化するかが、今回の最適化の目的です。
数学的には最適化問題は次のように表されます。
$$
\begin{aligned}
\text{Maximize} \quad & \sum_{i\inユーザー} \sum_{j\in映画} 評価スコア_{ij} \cdot x_{i, j}
\end{aligned}
$$
$$
\begin{aligned}
\text{subject to} \quad
\sum_{i\inユーザー} x_{i, j} \leq 5, \quad \forall j \in 映画,
\end{aligned}
$$
$$
\begin{aligned}
& \text{and} \quad \sum_{j\in映画} x_{i, j} \leq 5, \quad \forall i \in ユーザー
\end{aligned}
$$
$$
\begin{aligned}
\text{and} \quad x_{i, j} \in {0,1}, \quad \forall i \in ユーザー;\space j \in 映画
\end{aligned}
$$
ompr による実装
ここでは、まず対象となるユーザーと映画を選択し（全体を対象にすると計算時間がかかるため💦）、次に選択したユーザーと映画のすべての組み合わせに対して、$評価スコア$ を計算します：
weighted_user_latent <- m_summary |>
dplyr::filter(stringr::str_detect(variable, "^weighted_user_latent\\[")) |>
dplyr::pull(mean) |>
matrix(ncol = 20)
weighted_movie_latent <- m_summary |>
dplyr::filter(stringr::str_detect(variable, "^weighted_movie_latent\\[")) |>
dplyr::pull(mean) |>
matrix(ncol = 20)
# 最初の100ユーザーと100映画の評価スコアを計算
inner_product_result <- purrr::map(
1:100,
\(i){
purrr::map(
1:100,
\(j){
tibble::tibble(
user_id = i,
movie_id = j,
score = as.numeric(weighted_user_latent[i,] %*% weighted_movie_latent[j,])
)
}
)
},
.progress = TRUE
) |>
dplyr::bind_rows()
続いて、$評価スコア$ の行列と、R言語の数理最適化パッケージ ompr が利用するユーザー数と映画数の変数を作成します：
score_matrix <- inner_product_result |>
dplyr::pull(score) |>
matrix(ncol = 100, byrow = TRUE)
user_cnt <- nrow(score_matrix)
movie_cnt <- ncol(score_matrix)
最後に、さまざまなソルバー（数理最適化問題を解いてくれるツール）に対応するR言語の数理最適化パッケージ ompr
を利用して、数理最適化問題を定義して、解を求めます：
library(ROI.plugin.glpk)
# まず、ggplot2::ggplotのように、最適化問題を初期化する
result <- ompr::MIPModel() |>
# バイナリの決定変数 x[u, m] を定義
ompr::add_variable(x[u, m],
u = 1:user_cnt,
m = 1:movie_cnt,
type = "binary") |>
# 目的関数：ユーザーと映画の評価スコアの総和を最大化
ompr::set_objective(
ompr::sum_expr(
score_matrix[u, m] * x[u, m],
u = 1:user_cnt,
m = 1:movie_cnt
),
sense = "max") |>
# ユーザーごとの映画上限（最大5本）
ompr::add_constraint(ompr::sum_expr(x[u, m], m = 1:movie_cnt) <= 5, u = 1:user_cnt) |>
# 映画ごとのユーザー上限（最大5人）
ompr::add_constraint(ompr::sum_expr(x[u, m], u = 1:user_cnt) <= 5, m = 1:movie_cnt) |>
# GLPKソルバーで最適化
ompr::solve_model(ompr.roi::with_ROI(solver = "glpk", verbose = TRUE)) |>
# 解の取得
ompr::get_solution(x[u, m]) |>
tibble::tibble() |>
# バイナリ変数が1に近い場合、マッチング成立と判断
dplyr::filter(value > 0.5) |>
dplyr::select(user_id = u, movie_id = m) |>
# 実際の評価スコアを付与するため LEFT JOIN
dplyr::left_join(inner_product_result, by = c("user_id", "movie_id"))
これで最適化できました！
結果がきちんと制約条件を満たしているかを確認しましょう：
> result |> dplyr::mutate(one = 1) |> dplyr::summarise(s = sum(one), .by = user_id) |> dplyr::arrange(dplyr::desc(s))
# A tibble: 100 × 2
user_id s
<int> <dbl>
1 5 5
2 43 5
3 65 5
4 70 5
5 95 5
6 41 5
7 46 5
8 73 5
9 76 5
10 98 5
# ℹ 90 more rows
# ℹ Use `print(n = ...)` to see more rows
> result |> dplyr::mutate(one = 1) |> dplyr::summarise(s = sum(one), .by = movie_id) |> dplyr::arrange(dplyr::desc(s))
# A tibble: 99 × 2
movie_id s
<int> <dbl>
1 1 5
2 2 5
3 3 5
4 4 5
5 5 5
6 6 5
7 7 5
8 8 5
9 9 5
10 10 5
# ℹ 89 more rows
# ℹ Use `print(n = ...)` to see more rows
> result |> dplyr::mutate(one = 1) |> dplyr::summarise(s = sum(one), .by = user_id) |> dplyr::arrange(s)
# A tibble: 100 × 2
user_id s
<int> <dbl>
1 13 1
2 64 1
3 59 2
4 68 2
5 48 3
6 8 4
7 5 5
8 43 5
9 65 5
10 70 5
# ℹ 90 more rows
# ℹ Use `print(n = ...)` to see more rows
> result |> dplyr::mutate(one = 1) |> dplyr::summarise(s = sum(one), .by = movie_id) |> dplyr::arrange(s)
# A tibble: 99 × 2
movie_id s
<int> <dbl>
1 36 2
2 43 2
3 59 2
4 42 3
5 66 4
6 1 5
7 2 5
8 3 5
9 4 5
10 5 5
# ℹ 89 more rows
# ℹ Use `print(n = ...)` to see more rows
今回の最適化の結果、5本以上の映画とマッチングされたユーザーも、5人以上のユーザーを割り当てられた映画も存在しません。ただし、1本の映画しかマッチングできなかったユーザーや、2人のユーザーしか割り当てられなかった映画は存在します。
性能確認
ここでは、最適化モデルの性能を確認してみましょう！
考え方はシンプルです。もし ompr が本当に $評価スコア$ を参照してマッチングしているのであれば、ランダムな偽物スコアで「最適化（笑）」した結果よりも、本当の最適化結果の $評価スコア$ の総和の方が高くなるはずです。そうでなければ、結局ランダムに意思決定しているだけになってしまいますwww
具体的な手順は以下の通りです：
- ランダムな偽物スコアを生成する
-
omprを用いて本物同様の「最適化（笑）」を実施 - 得られた「偽物マッチング結果」がもたらす $評価スコア$ の総和を計算
これにより、偽物マッチング結果の $評価スコア$ 総和の分布を得られます。最後に、この分布と本当の $評価スコア$ 総和を比較して、最適化の効果を評価します。
統計学に少し踏み込んだ話になりますが、偽のデータからある数値（ここでは $評価スコア$ の総和）の分布を生成し、実際の値と比較するという手法は、まさに頻度論統計学の根幹にある考え方です。
本記事の内容に即して言えば、以下のシミュレーションは次の帰無仮説を、実際のデータを用いて検証しようとしているのです：
$$
H_{0}: \text{omprの数理最適化はランダムなマッチングと同等である}
$$
具体的にはこのように実装します：
future::plan(future::multisession)
random_results <- furrr::future_map_dbl(
1:1000,
\(x){
library(ROI.plugin.glpk)
this_score_matrix <- rnorm(user_cnt * movie_cnt) |>
matrix(ncol = movie_cnt)
result <- ompr::MIPModel() |>
ompr::add_variable(x[u, m],
u = 1:user_cnt,
m = 1:movie_cnt,
type = "binary") |>
ompr::set_objective(
ompr::sum_expr(
this_score_matrix[u, m] * x[u, m],
u = 1:user_cnt,
m = 1:movie_cnt
),
sense = "max") |>
ompr::add_constraint(ompr::sum_expr(x[u, m], m = 1:movie_cnt) <= 5, u = 1:user_cnt) |>
ompr::add_constraint(ompr::sum_expr(x[u, m], u = 1:user_cnt) <= 5, m = 1:movie_cnt) |>
ompr::solve_model(ompr.roi::with_ROI(solver = "glpk", verbose = TRUE)) |>
ompr::get_solution(x[u, m]) |>
tibble::tibble() |>
dplyr::filter(value > 0.5) |>
dplyr::select(user_id = u, movie_id = m) |>
dplyr::left_join(inner_product_result, by = c("user_id", "movie_id")) |>
dplyr::pull(score) |>
sum()
},
.progress = TRUE,
.options = furrr::furrr_options(seed = 12345)
)
結果を可視化してみると：
tibble::tibble(
random_allocation = random_results
) |>
ggplot2::ggplot() +
ggplot2::geom_histogram(ggplot2::aes(x = random_allocation), fill = ggplot2::alpha("blue", 0.3)) +
ggplot2::geom_vline(xintercept = sum(result$score), color = "red", linewidth = 1.2, linetype = "dashed") +
ggplot2::annotate("text", x = sum(result$score), y = Inf, label = "本物", vjust = 2, color = "blue", family = "HiraKakuPro-W3") +
ggplot2::labs(
x = "評価スコアの総和",
y = "分布",
title = "本物結果と偽物マッチング結果分布の比較"
) +
ggplot2::theme_gray(base_family = "HiraKakuPro-W3")
「偽物マッチング結果」で得られる $評価スコア$ の総和がせいぜい ±50 の範囲に収まるのに対し、本物の $評価スコア$ を用いた場合には、その総和がほぼ 400 に達します。もはや P 値を確認するまでもありません。本物データを使ったマッチングはランダム結果を圧倒的に上回り、性能に疑いの余地は一切ないと言えるでしょう。よって、ompr は期待通りに数理最適化を実施してくれたと判断しても問題ないでしょう。
留意点
ここで一つ注意しておきたいのが、ユーザー間での $評価スコア$ の比較可能性です。
ミクロ経済学の理論では、効用や満足度を測る指標（ここでいう $評価スコア$）を個人間で直接比較することはできない、とかなり以前から指摘されています。例えば、ユーザー1の「10ポイント」は本当にユーザー2の「5ポイント」の2倍の価値として扱ってよいのでしょうか？
本記事では便宜上「比較可能である」と仮定し、数理最適化アルゴリズムでリソース配分の最適化を実施しました。しかしもしこの比較可能性を否定するのであれば、そもそも数理最適化を行う意味がなく、単なる数値遊びにすぎなくなってしまいます。実際、ミクロ経済学ではこの問題に対応するため、補償変分や等価変分といった概念を用いて効用・満足度を金銭換算する研究が積み重ねられてきました。
もちろん、ビジネスの現場で本記事のような数理最適化を応用する場合、レコメンドエンジンのモデリングを工夫し、スコアが金銭換算可能になるように設計するのも一つの方法です。ですが、私としては まず AB テストを実施する のが現実的だと思います。スコアの個人間比較に理論的な制約があることは理解しつつも、AB テストで全体のユーザー満足度の向上が確認できれば、それで十分実用的だと考えられます。
結論
いかがでしたか？
本記事では、レコメンドエンジンの推定結果を活用し、限られたリソース（映画）をユーザーに最適配分するための数理最適化アプローチを解説しました。
- 問題の定式化：ユーザーと映画のマッチングを二値変数で表現し、ユーザーの満足度総和を最大化する目的関数を設定しました。
-
実装：
omprパッケージを用いることで、複数の制約条件下でも効率的に最適解を導き出せることを示しました。 - 性能評価：ランダムなスコアを用いたシミュレーション結果と、レコメンドモデルのスコアを用いた本物の最適化結果を比較しました。その結果、本物の最適化がランダムなマッチングを圧倒的に上回る性能を発揮することが証明されました。これは、数理最適化が単なる「数値遊び」ではなく、実際にユーザー満足度を最大化する上で極めて有効な手段であることを示しています。
最後に、ユーザー間のスコアの比較可能性という経済学的な観点にも触れました。これは理論上重要な課題ですが、現実のビジネスにおいては、本記事のような数理最適化の適用後、ABテストを通じて実際のユーザー満足度の向上を確認することが、最も現実的かつ有効なアプローチだと言えるでしょう。
レコメンドエンジンは、ユーザーの好みを予測するだけでなく、「限られた資源をどう配分するか」というビジネス上の意思決定に直接活用できる強力なツールです。ぜひレコメンドエンジンを資源配分の場面にも応用し、ミクロ経済学でいうソーシャルプランナーを目指してみてください。
ミクロ経済学（そして現代マクロ経済学）で登場するソーシャルプランナーは、単なる理論上の存在ではなく、実際に実現可能であり、社会の改善にもつながります。民間でデータサイエンティストをやるのは、とても刺激的で面白いですよ！
最後に、私たちと一緒に働きたい方はぜひ下記のリンクもご確認ください：