佐藤さんの 最適輸送の理論とアルゴリズム (機械学習プロフェッショナルシリーズ) を読んだ。素晴らしかった。
この本に書いてあった 最適輸送 を使って、スタッフの力量を考慮したタスクの割付け方法を考えたい。
問題設定
厳密に述べない。雰囲気でわかると思うそれに委ねる。
例えば 3 人のスタッフがいるとする。それぞれ $s_0, s_1, s_2$ と名付ける。
また目の前に 10 の異なるタスクがあるとする。例えば「XXを組み立てる」「〇〇を梱包する」といったものをイメージしてくれればよい。これをそれぞれ $t_0, t_1, \dots, t_8, t_9$ と名付ける。
タスクをスタッフに割付ける とは、以下のようにスタッフ $s$ に対してタスク $t$ を対応付けることを意味する。「XXの組み立てを近藤さんにお願いしよう」といった具合。
| スタッフ | 割付けられたタスク |
|---|---|
| $s_0$ | $t_0$, $t_1$, $t_2$ |
| $s_1$ | $t_3$, $t_4$, $t_5$ |
| $s_2$ | $t_6$, $t_7$, $t_8$, $t_9$ |
さて、上の割付けは、実はスタッフの力量を 考慮しない 例であった。つまり、いずれのスタッフもいずれのタスクを担当することができる。それ故、 全員がなるべく負荷が均等になるようにタスクが割付けされている。
では スタッフの力量を考慮するとはどういうことか。
ここでは以下の2つの観点で考える。
(1) スタッフのキャパシティ
例えば新人スタッフとベテランスタッフで、タスクをこなす速度が異なるので、ベテランスタッフに相対的に多くのタスクを割り付けたい、といったかんじ。ここではこのスタッフの処理できる大きさの度合いをキャパシティと表現する。
スタッフのキャパシティは、以下のように数字で表現できる。数字が大きいほどキャパシティが大きい、と、直感的に理解してほしい。
| スタッフ | キャパシティ |
|---|---|
| $s_0$ | 1 |
| $s_1$ | 2 |
| $s_2$ | 4 |
このとき、タスクの割付けは以下のようであるのが望ましい。つまり $s_2$ が他のスタッフに比べて多くのタスクを持つかんじ。
| スタッフ | 割付けられたタスク |
|---|---|
| $s_0$ | $t_0$ |
| $s_1$ | $t_1$, $t_2$, $t_3$ |
| $s_2$ | $t_4$, $t_5$, $t_6$, $t_7$, $t_8$, $t_9$ |
(2) スタッフそれぞれのタスクの向き・不向き
たとえば、あるスタッフは組み立てに関しては他のスタッフよりも圧倒的に上手いが、梱包作業についてはめっきりだめ、みたいなこと。
これも以下のように表で表現しよう。ここでは 数字が大きいほどそのタスクが苦手 とする。
| 向き不向き | $t_0$ | $t_1$ | $t_2$ | $t_3$ | $t_4$ | $t_5$ | $t_6$ | $t_7$ | $t_8$ | $t_9$ |
|---|---|---|---|---|---|---|---|---|---|---|
| $s_0$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| $s_1$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| $s_2$ | 1 | 1 | 1 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
この表に基づくと、$s_2$ は $t_3, t_4, \dots, t_9$ のタスクが向いていない。したがって $s_2$ には $t_0, t_1, t_2$ のいずれかのタスクを割り当てるのがよかろう。
以下は、 (1) の例で示したキャパシティで、さらに上の表に基づく向き・不向きが定義されている場合の割付け例。
| スタッフ | 割付けられたタスク |
|---|---|
| $s_0$ | $t_3$ |
| $s_1$ | $t_4$, $t_5$, $t_6$ |
| $s_2$ | $t_0$, $t_1$, $t_2$, $t_7$, $t_8$, $t_9$ |
ここで $s_2$ に $t_7$, $t_8$, $t_9$ が割付けされていることにも注目したい。力量的には、 $s_2$ は仕方なく苦手な $t_7$, $t_8$, $t_9$ も割付けされることになる。
さて、以下のようにスタッフのキャパシティと向き不向きが定義されているとする。 この条件に基づいて、上のようなかんじの良さげな割付けを、自動的に行えるようにしたい。 これが問題。
| スタッフ | キャパシティ |
|---|---|
| $s_0$ | 3 |
| $s_1$ | 7 |
| $s_2$ | 6 |
| 向き不向き | $t_0$ | $t_1$ | $t_2$ | $t_3$ | $t_4$ | $t_5$ | $t_6$ | $t_7$ | $t_8$ | $t_9$ |
|---|---|---|---|---|---|---|---|---|---|---|
| $s_0$ | 3 | 7 | 2 | 6 | 1 | 8 | 4 | 9 | 5 | 10 |
| $s_1$ | 6 | 2 | 8 | 4 | 10 | 3 | 7 | 1 | 9 | 5 |
| $s_2$ | 9 | 5 | 1 | 7 | 3 | 10 | 6 | 2 | 8 | 4 |
最適輸送として問題を定式化する
以下の佐藤さんのスライドを参照されたし。これに基づいて、今回の問題が最適輸送としてどのように定式化されるかを説明する。
以下、いい加減な説明になる。
直感的に言えば、スタッフのキャパシティが「輸送元のヒストグラム(確率分布)」に、向き不向きが「輸送のコスト」に、そして割り付けたいタスクが「輸送先のヒストグラム(確率分布)」にそれぞれ対応する。
「輸送元のヒストグラムの山を、輸送先のヒストグラムの山に、コストをかけて輸送する」というのが「スタッフのキャパシティを、タスクそれぞれに分配する」というかんじで対応させる。
輸送先のヒストグラムの山は、一般に複数の輸送元の山から構成されることになる。この構成要素の中の割合が最も大きいスタッフを、そのタスクのアサイニーとする。
ちゃんと定式化する。
輸送元の確率分布 $\alpha$ を
$$
\alpha = \sum_{s \in S} a_s \delta_{s},
$$
ただし、 $\delta$ はディラックのデルタ、また $S \subset \mathbb{N}$ はスタッフの集合、 $a_s$ は正規化したキャパシティとする。正規化したキャパシティとは、それぞれのキャパシティの値を合計で割ることを意味する。
おんなじかんじで、輸送先の確率分布 $\beta$ を
$$
\beta = \frac{1}{|T|} \sum_{t \in T} \delta_{t},
$$
ただし、 $\delta$ はディラックのデルタ、また $T \subset \mathbb{N}$ をタスクの集合とする。一様分布になっているのは、タスクそれぞれのキャパシティとか難しさとかを今は考えていないから。
(書いてて思ったけれども、ここの分布を変えれば、タスクそのものの難しさ、みたいなものも表現できるのか。面白いな。)
コスト関数 $C: S \times T \rightarrow \mathbb{R}$ は、向き不向きのマトリクスそのもの。
輸送行列を $P = (P_{st}) \in \mathbb{R}^{|S| \times |T|}$ とすれば、この問題は以下のように表現できる。
\begin{align}
& \min_{P \in \mathbb{R}^{|S| \times |T|}} \sum_{(s, t) \in S \times T} C(s, t) P_{s t} \\
\text{s.t.} \quad & P_{st} \geq 0, \quad \forall (s, t) \in S \times T, \\
& \sum_{t \in T} P_{st} = a_s, \quad \forall s \in S, \\
& \sum_{s \in S} P_{st} = \frac{1}{|T|}, \quad \forall t \in T.
\end{align}
問題を解く
POT という最適輸送問題のソルバーを使う。使い方は超簡単だった。
$ pip install POT
結果をプリントするヘルパー関数
def print_result(transport_matrix):
s_to_tlist = {i: [] for i in range(len(transport_matrix))}
for task, staffs in enumerate(transport_matrix.T):
assigned_staff = np.argmax(staffs)
s_to_tlist[assigned_staff].append(task)
for staff, task_list in s_to_tlist.items():
_task_list = [f"t{i}" for i in task_list]
print(f"s{staff}: {_task_list}")
最適な輸送行列を求める関数
def assign_staff(capacity, skill_matrix):
# alpha は全部足して 1 にできるように、全部の和で割り算しておく
alpha = np.array([i / sum(capacity) for i in capacity])
# コスト行列は向き不向きの表そのもの
cost_matrix = np.array(skill_matrix)
# beta は、すべて平等な重み
task_num = len(cost_matrix.T)
beta = np.array([1 / task_num for _ in range(task_num)])
# 最適な輸送行列を求める
transport_matrix = ot.emd(alpha, beta, cost_matrix)
# print
print_result(transport_matrix)
まず一番最初の力量を考慮 しない 例から。
capacity = [1, 1, 1]
skill_matrix = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
assign_staff(capacity, skill_matrix)
結果。いいかんじに分散されてる。
s0: ['t2', 't3', 't4']
s1: ['t0', 't1', 't5']
s2: ['t6', 't7', 't8', 't9']
次に、キャパシティだけ違う例。
capacity = [1, 2, 4]
skill_matrix = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
assign_staff(capacity, skill_matrix)
結果。いいかんじにキャパシティを考慮した状態になっている。
s0: ['t2']
s1: ['t1', 't3', 't7']
s2: ['t0', 't4', 't5', 't6', 't8', 't9']
次に、キャパシティと向き不向きを考慮した例。
capacity = [1, 2, 4]
skill_matrix = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 10, 10, 10, 10, 10, 10, 10],
]
assign_staff(capacity, skill_matrix)
結果。 $s_2$ のスタッフが $t_0, t_1, t_2$ を取ってる。いいかんじ。
s0: ['t5']
s1: ['t3', 't6', 't7']
s2: ['t0', 't1', 't2', 't4', 't8', 't9']
最後の例。デタラメな直感的にどういう結果になってるかわからない例。
capacity = [3, 7, 6]
skill_matrix = [
[3, 7, 2, 6, 1, 8, 4, 9, 5, 10],
[6, 2, 8, 4, 10, 3, 7, 1, 9, 5],
[9, 5, 1, 7, 3, 10, 6, 2, 8, 4]
]
assign_staff(capacity, skill_matrix)
結果。キャパシティ的に $s_0$ より $s_1, s_2$ のほうがタスクの量が多い。またすべてのチョイスが 6 以下のコストになっているかんじ。いいかんじに見える。
s0: ['t0', 't8']
s1: ['t1', 't3', 't5', 't7']
s2: ['t2', 't4', 't6', 't9']
これをちゃんと評価する方法はまた別で。
終わり。