割当問題で分布を均質化する

こんにちは，新卒 2 年目データサイエンティストのはだです．
この記事はBrainPad Advent Calendar 2024の 10 日目の記事です．

はじめに

ブレインパッドでは「新卒 1 年目は毎日業務時間 1h を使って課題図書を読んで勉強する（1 年間）」という勉強会制度があります．
例年 2 年目になった先輩が自身の経験を元に図書の入れ替えを行い、次年度の課題図書を指定＆メンターに就任する仕組みです．
書籍のトピックとしては統計，機械学習，効果検証，数理最適化などがあり，そのトピックから 6 冊が選ばれ，大体各書籍 2 ヶ月程で読んでいきながら適宜分からないところを 2 年目の先輩社員達を交えながら議論していくという活動が行われています．
詳しい内容については以前白金鉱業.FMで紹介されているので興味のある方はぜひ聴いてみてください．

その勉強会の最適化トピックとして，今年はPython ではじめる数理最適化(第 2 版)が課題図書として選ばれました．私自身，学生時代に輪読会で読んだりしていて大変お世話になっている書籍です．
本記事では勉強会で議論になった第 3 章で登場するクラス編成の最適化問題にを題材に，割当問題において割当後の各グループの特徴量分布を均質化する方法について考察してみたいと思います．

本記事での実験コードはこちらにあります．
また，書籍サポートページの該当コードはこちらです．

問題概要

まずはじめに問題設定についてざっくりと説明します．
やりたいこととしては，生徒の集合$S$，クラスの集合$C$として，各生徒$s \in S$に対してクラス$c \in C$を割り当てる問題を考えます．
割り当てるにあたって,各クラスの人数や男女比，学力が均等になるようにといった制約条件が入ります．
以降では，学力が均等になるようにという制約条件について深く考えてみます．
書籍ではまずは各クラスに割り当てられた生徒の学力試験の平均値が平均点 ±10 点になるようにという制約条件を考慮しています．
このモデルは，各生徒$s \in S$の学力試験の点数を$score_s$，生徒$s$がクラス$c$に割り当てられるかを表す決定変数を$x_{s,c}$として，以下のような実行可能解を見つける問題として定式化されます．

$$\begin{align*} \text{find} \quad & x_{s,c} \\ \text{s.t.} \quad & \overline{score} - 10 \le \sum_{s \in S} x_{s,c} \cdot score_s \le \overline{score} + 10, \quad \forall c \in C, \\ & \\ & \vdots \quad \text{(other constraints)} \\ & \\ & \sum_{c \in C} x_{s,c} = 1, \quad \forall s \in S, \\ & \left \lfloor \frac{|C|}{|S|} \right \rfloor \le \sum_{s \in S} x_{s,c} \le \left \lceil \frac{|C|}{|S|} \right \rceil, \quad \forall c \in C. \\ \end{align*}$$

ここで，$\overline{score}$は学年平均点を表す定数とします．
上記のモデルでは 1 番目の制約条件が各クラスに割り当てられた生徒の平均値が平均点 ±10 点という条件を表しています^[1]．
その他の詳細な制約条件については書籍やサポートページを参照してください．

このモデルのもとで計算を行うと各クラスの試験点数分布は以下のようになります．

概ねバランスが取れていそうに見えますがこのモデルだと平均値しか考慮できていないため分散や歪み方などがクラスによって異なっていることがわかります．
例えばクラス B は左に偏った幅の広い分布になっている一方で，クラス G はどちらかというと右に偏った幅の狭い分布になっていることがわかります．

この問題点を解決するために書籍では，まず得点ごとに生徒をソートして各クラスに順番に割り当てるという初期解を生成した後に，各種制約を満たすように初期解からの変更量を最小化するというモデリングを行っています．
このモデルは，初期解において生徒$s$をクラス$c$に割り当てる場合に 1,それ以外は 0 の値を取る定数 $X_{s,c}$を用いて以下のように定式化されます．

$$\begin{align*} \text{min.} \quad & \sum_{s \in S} \sum_{c \in C} X_{s,c}\cdot x_{s,c} \\ \text{s.t.} \quad & \overline{score} - 10 \le \sum_{s \in S} X_{s,c} \cdot score_s \le \overline{score} + 10, \quad \forall c \in C, \\ & \\ & \vdots \quad \text{(other constraints)} \\ & \\ & \sum_{c \in C} x_{s,c} = 1, \quad \forall s \in S, \\ & \left \lfloor \frac{|C|}{|S|} \right \rfloor \le \sum_{s \in S} x_{s,c} \le \left \lceil \frac{|C|}{|S|} \right \rceil, \quad \forall c \in C. \\ \end{align*}$$

このモデルを実行すると以下のような結果が得られます．

分布を見ると先ほどよりもそれぞれのクラスの得点分布が均質化されていそうです．
実際にこれらの分布の違いを定量化するために，各クラスの学力分布に対して平均，分散，歪度，尖度を計算して，それぞれの最大値-最小値を計算してみます．
まず先ほどのナイーブモデルの結果は以下のようになります．

統計量	最大値-最小値
平均	16.205128
標準偏差	30.279656
歪度	1.269706
尖度	3.329349

続いて初期解を用いたモデルの結果は以下のようになります．

統計量	最大値-最小値
平均	15.425000
標準偏差	14.844661
歪度	1.171639
尖度	1.232404

結果を見ると，各クラスの平均値の違いは制約条件で考慮されていることもあり同じくらいですが，分散が大幅に均質化されていることがわかります．

別解法

書籍では上述のルールベースで生成した初期解を用いた解法を紹介していますが，本記事では分布の均質化を目的関数に直接組み込んだ別アプローチを考えてみたいと思います．
まずはシンプルに各点数 $p \in P=\{\min(Score_s), \dots, \max(Score_s)\}$において，各クラスの分布の値が等しくなるようにする目的関数が思い付きます．
ここで $S_p = \{ s \in S | score_s = p \}$として，得点が$p$の生徒の集合を表すものとします．
このアプローチのイメージは下図のように，オレンジ色の各クラスの得点$p$の人数$\sum_{s \in S_p} x_{s,c}\ (c \in C)$の違いが小さくなるようにする目的関数を考えて，それを全ての得点$p \in P$に対して足し合わせることで，分布の均質化を行います．

このアプローチは以下のように定式化できます．

$$\begin{align*} \text{min.} \quad & \sum_{p \in P} z_p \\ \text{s.t.} \quad & - z_p \le \sum_{s \in S_p} x_{s,c} - \frac{|C|}{|S_p|} \le z_p, \quad \forall c \in C, \forall p \in P,\\ & \\ & \vdots \quad \text{(other constraints)} \\ & \\ & \sum_{c \in C} x_{s,c} = 1, \quad \forall s \in S, \\ & \left \lfloor \frac{|C|}{|S|} \right \rfloor \le \sum_{s \in S} x_{s,c} \le \left \lceil \frac{|C|}{|S|} \right \rceil, \quad \forall c \in C. \\ \end{align*}$$

ここでは 1 番目の制約条件と目的関数自体が分布を均質化することを意図しているので，書籍モデルとは異なり制約条件として平均点 ±10 点制約を入れていないことに注意して下さい．
この定式化で求解すると以下のような結果が得られます．

統計量	最大値-最小値
平均	70.440385
標準偏差	36.749729
歪度	1.376016
尖度	1.524052

これは一番最初のモデルと比べてもダメダメな結果になってしまいました．
そもそも平均値の乖離が 20 を超してしまいました(お前が外したからだろという感じですが)

以上の結果の原因を考察するために 300 点〜304 点までの生徒が 3 人ずついて，2 クラスに分けるようなシンプルな状況を考えます．
このような設定ではなんとなく下図のような分布になってほしい気持ちになります．

理想的な解

上のモデルにおける最適化にいて考えると，各得点(300,301,...,304)に対して一方のグループに 1 人，他方に 2 人を割り当てるという解が最適解となります．
これは上の理想的な解も最適解として出力され得ることを意味します．
一方で，このモデルでは 300,301,302 点でクラス A に 2 人割り当てて，303,304 点でクラス B に 2 人割り当てるという下の図のような均質的な出ない分布の解も最適解となってしまいます．

偏った解

つまるところ，このモデルでは点数ごとにしか均等に割り振ることを考慮できていないことが問題であると考えられます．

続いてこのモデルを改良して，累積分布を各点数ごとに均等にするようにしてみます．
つまり，得点$p$以下の生徒の集合を$S_\le p = \{ s \in S | score_s \le p \}$として以下のような定式化を考えます．

$$\begin{align*} \text{min.} \quad & \sum_{p \in P} z_p \\ \text{s.t.} \quad & - z_p \le \sum_{s \in S_\le p} x_{s,c} - \frac{|C|}{|S_\le p|} \le z_p, \quad \forall c \in C, \forall p \in P,\\ & \\ & \vdots \quad \text{(other constraints)} \\ & \\ & \sum_{c \in C} x_{s,c} = 1, \quad \forall s \in S, \\ & \left \lfloor \frac{|C|}{|S|} \right \rfloor \le \sum_{s \in S} x_{s,c} \le \left \lceil \frac{|C|}{|S|} \right \rceil, \quad \forall c \in C. \\ \end{align*}$$

このモデルの場合は，累積分布を考えるため得点を跨いだ均質化を考慮することができ，先ほどの例での偏った解は最適解とはならずに理想的な解のみが最適解となります．
イメージとしては下図のように，各得点$p$に対して，各クラスに割り当てられた得点$p$以下の生徒人数が均等になるようにするという感じです．

では，実際にこのモデルで計算を実行してみると以下のような結果が得られます．

統計量	最大値-最小値
平均	5.757051
標準偏差	4.606729
歪度	0.871509
尖度	1.074960

明示的に平均値 ±10 点の制約を入れていなくても平均値が均質化されていることがわかります．
さらに分散，歪度，尖度に関してもうまく均質化されていることが分かります．

まとめ

この記事では，Python ではじめる数理最適化第 3 章を題材に割当問題において割り当てられたグループの分布を均質化するためのモデリングについて考察を行いました．
この方法は，因果推論の文脈で共変量の分布が等しくなるような割り当てを考える状況でも使えそうな気がしつつも，先行事例はちゃんと調べられていないです．．．(最適輸送使って分布を均質化するとかはありそうですが)

また少し雑談をすると，書籍での予め分布が均質化されるような割り当てを考えておいて，その割り当てをなるべく崩さないように調整するという発想の転換とも言えるこのアプローチは初見で思いつくのはなかなか難しそうです．
私も初めて書籍を読んだ時は「分布間距離を考えて頑張るのか？」などと読みながら思っていましたが，この方法を読んでなるほどと思った記憶があります．
実際に新卒勉強会においてもこのアプローチをどうしたら思いつくのかという質問が出ていました．
一方で，入社後にデータサイエンティストとして実務の最適化問題を考えるようになり，このような全部を最適化問題の枠組みの中で頑張らずにある程度，外部の情報を利用して問題を解くというアプローチは常套手段なのだなと思うようになりました．（今回であれば目的関数で分布の均質化を頑張るのではなくシンプルなルールベースの初期解の情報を利用している）

同じような話として広告予算配分などの機械学習モデルの予測をもとにして最適化問題を解く際にもこの手の考え方は役に立ちます．
単純に予測モデルの出力を鵜呑みにして問題を解いてしまうと，最適解として予測モデルの外挿領域の信頼できない結果が出てしまうということは往々にしてあります．
意思決定者としても前回の計画と最適化による計画が劇的に異なる場合，その結果を採用することは難しいです．
そのような状況に対しては過去実績をもとにして，実績からの乖離があまりに大きいようであればペナルティを与えて最適化問題を解くといった対処法が考えられます．
この方法も最適化問題の外側の過去実績という外部情報を利用して問題を解くという意味で書籍のアプローチと似ているなと感じています．
こちらの広告予算配分の話は弊社の魚井さんが昨年の OptimizationNight で発表した資料に詳しく記載されているので，興味のある方はぜひご覧下さい．

以上雑多な話をしてしまいましたが，ここまで記事をお読みいただきありがとうございました．

脚注

1. こちらの制約条件は極端な入力データが入ってきた際に実行不能になることを避けるためにソフト制約として書き換えて，各クラス平均点の学年平均からの乖離を最小化する定式化をするなども考えられそうです．