レコメンドの最適化

#1. レコメンド
レコメンドでは学習データをもとに機械学習などでモデルを作り、ユーザxアイテムに関して予測スコアをつけて、各ユーザに関して予測スコアが高いアイテムTOP ?を見せることが多いです。しかしこの方法では人気アイテムの予測スコアが高くなり、人気のないアイテムの予測すこが小さくなるので、人気のあるアイテムばかり広告が出て、人気のないアイテムには広告が出ないという問題があります。
広告サイトでは、人気のないアイテムに対してもある程度のCVを得るため広告を出す必要がある場合が多いです。

#2. 最適化
アイテム単位で広告するユーザ数に制限を入れることにより解消することができます。
例えば人気アイテムには広告を出す最大ユーザ数を設定し、人気のアイテムには広告を出す最小ユーザ数を設定すれば良いです。

#3.例
ユーザ数 30、アイテム数 20とします。
各ユーザに関して5件アイテムをレコメンドすると考えます。

ただしすべてのアイテムに関して10人以下しか広告を出さず
アイテム0,1,2は人気アイテムなので3人以下しか広告を出さず
アイテム18,19は人気のないアイテムなので9人以上広告を出すとします。

以下
$ scores_{ui} $: ユーザu,アイテムiの予測スコアとします。

上記の条件を数式にすると

###変数
$ choices_{ui} $ : ユーザuにアイテムiの広告を出すかどうか(1 or 0)
###目的関数
$ \sum_{u} \sum_{i} scores_{ui} * choices_{ui} $
を最大化する。
###制約条件

1. $\sum_{i} choices_{ui} <= 5 (\forall u)$
2. $\sum_{u} choices_{ui} <= 10 (\forall i)$
3. $\sum_{u} choices_{ui} <= 3 (i=0,1)$
4. $\sum_{u} choices_{ui} >= 9 (i=18,19)$

となり線形計画法で解けます。

pulpで実数すると

USER =30
ITEM = 20
Users = list(range(0,USER))
Items = list(range(0,ITEM))

prob = pulp.LpProblem("test",pulp.LpMaximize)

# 変数の宣言
choices = pulp.LpVariable.dicts("Choice",(Users,Items) , 0, 1, pulp.LpInteger)

# 目的関数
prob += pulp.lpSum([scores[u][i] * choices[u][i] for u in Users for i in Items ])

# 制約条件
#1. $\sum_{i} choice_{ui} <= 5 (\forall u)$
for u in Users:
    prob += pulp.lpSum([choices[u][i] for i in Items]) <=5

#2. $\sum_{u} choice_{ui} <= 10 (\forall i)$
for i in Items:
    prob += pulp.lpSum([choices[u][i] for u in Users]) <= 10

#3. $\sum_{u} choice_{ui} <= 3 (i=0,1)$
for i in [0,1]:
    prob += pulp.lpSum([choices[u][i] for u in Users]) <= 3

#4. $\sum_{u} choice_{ui} >= 9 (i=18,19)$
for i in [18,19]:
    prob += pulp.lpSum([choices[u][i] for u in Users]) >= 9

status = prob.solve()

で解けます。

今scoresを下記のようにアイテム1,2は人気アイテムなのでスコアを増やして、スコア18,19は人気のないアイテムなのでスコアを減らします。

np.random.seed(10)
scores = np.random.rand(USER, ITEM)
scores[:,0] += 0.3
scores[:,1] += 0.3
scores[:,18] -= 0.3
scores[:,19] -= 0.3
scores = np.clip(scores, 0, 1)

サンプルソースは
https://github.com/tohmae/pulp_sample/blob/master/score_optimize.py
にあります。

上記のスコアで最適化を実行した場合、制約条件2,3,4がない場合は

	Item0	Item1	Item2	Item3	Item4	Item5	Item6	Item7	Item8	Item9	Item10	Item11	Item12	Item13	Item14	Item15	Item16	Item17	Item18	Item19
User0	1	0	0	1	0	0	0	1	0	0	0	1	0	0	1	0	0	0	0	0
User1	1	0	0	1	0	0	0	0	0	0	1	0	1	0	0	0	0	1	0	0
User2	0	1	0	1	0	0	0	1	0	0	0	0	0	0	0	1	1	0	0	0
User3	1	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1	1	0	0
User4	1	1	1	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	0	0
User5	1	1	0	0	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0
User6	0	1	0	1	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	1
User7	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	1	0	0	0	0
User8	0	0	0	0	0	0	0	0	1	0	1	1	0	1	0	0	1	0	0	0
User9	1	1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	1	0	0
User10	1	1	0	0	0	0	0	0	0	0	0	1	1	0	1	0	0	0	0	0
User11	0	1	0	0	1	0	0	1	0	0	0	1	1	0	0	0	0	0	0	0
User12	0	0	1	0	0	1	0	0	1	0	0	0	1	0	1	0	0	0	0	0
User13	0	0	0	1	0	0	0	1	1	0	1	0	1	0	0	0	0	0	0	0
User14	0	0	1	1	0	0	1	0	0	0	0	0	0	0	1	1	0	0	0	0
User15	1	0	1	0	0	0	0	0	0	0	0	0	1	0	1	1	0	0	0	0
User16	1	0	0	1	0	0	0	1	0	0	0	0	0	1	0	1	0	0	0	0
User17	0	1	0	1	0	0	0	0	0	1	0	0	0	1	0	0	0	1	0	0
User18	0	0	1	1	0	0	1	0	0	1	0	0	0	0	0	0	0	1	0	0
User19	1	0	0	1	1	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0
User20	0	1	0	0	1	0	0	0	0	1	1	0	0	0	0	0	0	1	0	0
User21	0	0	0	0	1	1	0	0	0	0	0	1	0	1	0	1	0	0	0	0
User22	1	0	0	1	0	0	0	0	0	0	1	1	0	0	0	0	0	1	0	0
User23	0	0	0	1	1	0	0	1	0	1	0	0	0	0	0	1	0	0	0	0
User24	0	0	0	0	1	1	0	0	0	1	0	0	0	1	0	0	1	0	0	0
User25	0	0	0	0	0	1	0	0	0	0	1	0	0	1	1	0	0	1	0	0
User26	0	1	1	0	1	0	0	0	0	0	0	1	0	1	0	0	0	0	0	0
User27	0	0	0	0	0	0	1	0	0	0	1	1	0	0	1	0	1	0	0	0
User28	0	1	0	0	0	1	0	0	0	0	0	1	1	0	0	0	1	0	0	0
User29	1	1	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	1	0	0

制約条件2,3,4を入れた場合は

	Item0	Item1	Item2	Item3	Item4	Item5	Item6	Item7	Item8	Item9	Item10	Item11	Item12	Item13	Item14	Item15	Item16	Item17	Item18	Item19
User0	0	0	0	0	0	0	0	1	0	0	0	1	0	0	1	0	0	0	1	1
User1	0	0	0	0	0	0	0	0	1	0	1	0	1	0	0	0	0	1	0	1
User2	0	0	0	1	0	0	0	1	0	0	0	0	0	0	0	1	1	0	1	0
User3	1	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1	1	1	0
User4	1	0	1	0	0	0	0	0	0	1	0	0	0	1	0	0	1	0	0	0
User5	0	1	0	0	1	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0
User6	0	1	0	1	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	1
User7	0	0	0	1	0	1	0	0	1	0	0	0	0	1	0	1	0	0	0	0
User8	0	0	0	0	0	0	0	0	1	0	1	1	0	1	0	0	1	0	0	0
User9	0	0	0	0	1	1	0	0	0	0	0	1	0	0	0	0	1	1	0	0
User10	0	0	0	1	0	0	1	0	0	0	0	1	1	0	1	0	0	0	0	0
User11	0	0	0	0	1	0	0	1	0	0	0	1	1	0	0	0	0	0	0	1
User12	0	0	0	0	0	1	0	0	1	0	0	0	1	0	1	0	0	0	1	0
User13	0	0	0	1	0	0	0	1	1	0	1	0	1	0	0	0	0	0	0	0
User14	0	0	1	1	0	0	1	0	0	0	0	0	0	0	1	1	0	0	0	0
User15	0	0	1	0	1	0	0	0	0	0	0	0	1	0	1	1	0	0	0	0
User16	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	1	0	0	0	1
User17	0	0	0	1	0	0	0	0	0	1	0	0	0	1	0	0	0	1	1	0
User18	0	0	1	0	0	0	1	0	0	1	0	0	0	0	0	0	0	1	0	1
User19	0	0	1	1	1	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0
User20	0	0	0	0	1	0	0	0	0	1	1	0	0	0	0	1	0	1	0	0
User21	0	0	0	0	0	1	0	0	0	0	0	1	0	1	0	1	0	0	0	1
User22	0	0	0	1	0	0	0	0	0	0	1	1	0	0	0	0	0	1	1	0
User23	0	0	0	1	1	0	0	1	0	1	0	0	0	0	0	1	0	0	0	0
User24	0	0	0	0	1	1	0	0	0	1	0	0	0	1	0	0	1	0	0	0
User25	0	0	0	0	0	1	0	0	0	0	1	0	0	1	1	0	0	1	0	0
User26	0	0	1	0	1	0	0	0	0	0	0	1	0	1	0	0	0	0	0	1
User27	0	0	0	0	0	0	0	0	0	0	1	1	0	0	1	0	1	0	1	0
User28	0	0	0	0	0	1	0	0	0	0	0	1	1	0	0	0	1	0	1	0
User29	0	1	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	1	0	1

となり制約条件2,3,4を入れた方がアイテム1,2の広告数が減って、アイテム18,19の広告数が増えることがわかります。

線形計画法でレコメンドの最適化ができました。