Help us understand the problem. What is going on with this article?

レコメンドの最適化

1. レコメンド

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

2. 最適化

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

3.例

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

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

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

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

voyager
persol
PERSOL(パーソル)グループは、人材派遣、人材紹介、求人広告をはじめとし、ITアウトソーシング、設計開発にいたるまで、国内外70社を超える幅広い企業群で構成されています。
https://www.persol-group.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした