レコメンドの最適化

#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の広告数が増えることがわかります。

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