n週連続 推薦システム関連の論文読んだシリーズ9週目(水曜更新): 推薦タスクをMarkov 決定過程 (MDP) として定式化し、RLアプローチを適用した最初(?)の論文を読んだ

# An MDP-Based Recommender System

published date: 5 September 2005,
authors: Guy Shani, Ronen I. Brafman, David Heckerman
url(paper): https://www.jmlr.org/papers/volume6/shani05a/shani05a.pdf
(勉強会発表者: morinota)

---

## どんなもの?

- 一般的な推薦システム(コンテンツベースや協調フィルタリングベース)は、**推薦プロセスを静的な視点で捉え**、予測問題として扱っている.
- しかし、推薦プロセスはSequentialなプロセスである.
  - ユーザのInteractionを受けて、新たな推薦アイテムリストを生成する.
  - また、ユーザの選択は、**例えば、最近気に入った本の著者の本を買うというように、Sequentialな性質を持っている**.
- 本論文では、推薦問題を**逐次決定問題(sequential decision problem)として捉えることがより適切**であり、その結果、マルコフ決定過程(MDP)が推薦システムのモデルとしてより適切であることを主張する.
  - sequential decision problem = sequentialなデータを考慮 & 強化学習、みたいなイメージ?
- MDPベースの推薦システムが実際に成功するためには、強力な初期モデルを採用し、素早く解けること、そしてメモリをあまり消費しないことが必要.
- 2005年の論文なので、"商業的に展開されている数少ない推薦システムの一つ"らしい.

## 先行研究と比べて何がすごい？

- 推薦システムにおいてMDP(Markov decision processes, マルコフ決定過程)を定義した、最初の論文.(たぶん推薦 \* 強化学習のかなり初期の論文??)
- MDPモデルと適切な初期化・解法に基づく推薦システムに対する新しいアプローチ.
  - 購入される確率は少し低いが、より高い利益を生み出す商品を薦めるなど、特定の推薦アイテムの効用を考慮することができる.
  - 「**目先の報酬は低いが、将来、より可能性の高い、あるいはより有益な報酬につながる**アイテム」を提案することがある.(=まさに短期的なクリックではなく、長期的なユーザ体験の改善みたいな...?)

## 技術や手法の肝は？

### 推薦プロセスの逐次性(Sequential Nature)

ほとんどのレコメンダーシステムは、ユーザにアイテムを提案し、ユーザはその中から1つを選択する、という順序で動作する.
次のステージでは、新しいおすすめアイテムのリストが計算され、ユーザに提示される.
このように、**ユーザの過去の評価をもとに、各段階で新しいリストを算出するという推薦プロセスの逐次性**は、推薦プロセスを逐次最適化プロセスとして再定義する事に関して理にかなっている.

推薦のプロセスには、**さらにもう一つの逐次性がある.**
すなわち、**最適なレコメンデーションは、過去に購入したアイテムだけでなく、それらのアイテムを購入した順番にも依存する**可能性がある.

### MDP

MDPとは、**逐次確率的決定問題(sequential stochastic decision problems)のモデル**である.
そのため、**自律的なエージェントが行動(action)によって周囲の環境(environment)に影響を与えるようなアプリケーション**(例えば、ナビゲーションロボットなど)に広く利用されている.
**MDP(マルコフ決定過程)の定義**は four-tuple(４つ組)：$\langle S, S, Rwd, tr \rangle$で、$S$ はstateの集合、Aはactionの集合、$Rwd$は各stateに実数値を割り当てるreward関数, $tr$ はstate transition関数である.

MDPにおける意思決定者の目標は、reward stream関数(=streamってどういう意味? 短期的でimmidiateなrewardではなく、長期的なrewardって意味?)が最大になるように行動すること.
形式的には、MDP $\pi$ の**stationary policy(定常方策?)は、stateからaction へのmapping**であり、**各stateでどのactionを実行するかを指定するもの**.(=**stateが決まれば、常に同じactionが決定するって意味**??)
このような最適な方策 $\pi$ が与えられた場合、エージェントは意思決定プロセスの各段階において、どのような state $s$ にあるかを確定し、action $a = \pi(s)$ を実行すればよい.

### 推薦システムにおけるMDPを定義する

MDPを定義するためには、状態(state)、行動(action)、遷移関数(transition function)、報酬関数(reward function)のセットを提供する必要がある.

#### state:

- アイテム（例えば、本、CD）の k-tuples(interaction履歴?)に対応.
- そのうちのいくつかの接頭辞は、アイテムの欠落に対応するNULL値を含むことができる.(ユーザのinteractionがk個に満たないケース)

#### action:

- アイテムの推薦に対応.
- 複数の推奨アイテムリストを検討することも可能だが、本論文ではシンプルに、一つの推薦アイテムを検討している.

#### reward:

- プロダクトが定義する interaction (ex. 商品を売る, ウェブページを見せる, etc.)の効用を符号化したもの.
- state は interaction したアイテムのリストを符号化するため、reward は現在の state を定義する最後のアイテムにのみ依存する.
- ex) state $(x1, x2, x3)$の reward は、アイテム$x3$ への interaction からサイトが生み出す報酬.
- 本論文では、reward　として net profit(アイテムの購入による純利益?)を使用している.

#### state transition:

- 各action(アイテム推薦)後のstateは、その推薦に対するユーザのresponceによって決まる.
- アイテム $x'$ を推薦した場合、ユーザには次の3つの選択肢がある.
  - この推薦を受け入れることで、state $(x1, x2, x3)$ から $(x2, x3, x')$に移行する.
  - $x'$とは別の、非推薦アイテム$x''$を選択することで、state $(x1, x2, x3)$ から $(x2, x3, x'')$に移行する.
  - 何もしない(ex. ユーザーがセッションを終了する)事で、そのままの state を維持する.

したがって、本MDPモデルにおける**state transitionの確率的要素は、ユーザの実際の選択**である.

上のケースのtransition functionは以下:

$$
tr^{1}_{MDP} (<x_1, x_2, x_3>, x', <x_2, x_3, x''>)
\tag{13}
$$

これは、state $<x1, x2, x3>$ でアイテム $x'$ が推薦されてる場合に、ユーザがアイテム $x''$ を選択する確率.
ここで、k=1のsingle item recommendationsを表すために、$tr^{1}_{MDP}$と表記している.

### transition function の初期化方法の工夫

**transition functionの適切な初期化**は、推薦システムのMDPにおける重要な実装課題である.
従来のモデルベースの強化学習アルゴリズムが、遷移関数の適切な値(i.e. 最適な方策と言ってもいい?今回の場合はtransition function)をオンラインで学習するのとは異なり、**推薦システムの場合、最初に展開するときにかなり正確である必要がある.**

## どうやって有効だと検証した?

実際に導入した推薦システムから収集したデータに基づき、オンライン評価を行う.
本研究の主要なテーゼは、**（1）推薦を逐次最適化問題として捉えるべきであり、（2）MDPはこの見解に適したモデルを提供する**、というものである.
MDPに基づく推薦システム（MDPと表記）と、予測モデルに基づく推薦システム(MCと表記)、および他の変種との性能を比較した.

### Utility Performance

以下の**4つのポリシー**の性能を比較した.

- Optimal: MDPに最適なポリシーに基づいたアイテムを推薦する.
- Greedy: $Pr(x|h)\cdot R(x)$ を最大化するアイテムを推薦する(ここで、$Pr(x|h)$はユーザーの履歴hが与えられた場合にアイテムxを購入する確率、$R(x)$ はサイトにとってのxの価値（例えば純利益）である).
- Most likely: 最も可能性が高い - $Pr(x|h)$ を最大化するアイテムを推薦する.
- Lift: $Pr(x|h)/Pr(x)$ を最大化するアイテムを推薦する. ここで、Pr(x)はアイテムxを購入する事前確率である.

異なるポリシーを評価するために、ユーザとシステムとのInteractionのシミュレーションを実行した.
シミュレーション中、システムは推薦アイテムのリストRを生成し、そこから模擬ユーザが次のアイテムを選択する.
(遷移確率質量の)分布$tr(s,R,s \cdot x)$-**現在のstate sと推薦リストRが与えられたときに、次の選択アイテムがxである確率**-を用いて、ユーザによるx購入のシミュレーションをした.

結果は表3.

![](https://camo.qiitausercontent.com/f610bd9090abc21067eaa0187392187641d7ba19/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f313639373237392f34643635366363332d623465362d303833662d633764322d6436643532313764666332662e706e67)

各方策の計算値は、全state で平均した discounted profit の合計.
当然ながら、optimal policy(MDP)は最も高い値をもたらす.
しかし、**その差は小さく、予測モデルだけでも非常に良い結果が得られると思われる**.

次に、MDPベースのシステムとMCベースのシステムの性能を比較する実験を行った.(A/Bテスト)
この実験では、サイトに入る各ユーザに、ランダムに生成されたカートIDが割り当てられた.
このcart-idの最終ビットに基づき、MDPまたはMCからユーザにレコメンドが提供された.(要するにA/Bテスト!!)

**MDPレコメンダーの性能向上は**、片側並べ替え検定でp = 0.08と**統計的に有意であった**ことがわかった.
これは、**MDPがより多くのアイテム購入を生み出しているか、より高価な商品の売上を生み出しているかの2つの可能性がある**.

### Computational Analysis

ここでは、**MDPベースとPredictorレコメンダーシステムの計算コスト**を比較する.

まず、**推薦にかかる時間**について.
**レコメンデーション時間は、一般的に計算コストの中で最も重要なもの**である.
表5は、レコメンダーシステムが1秒間に生成するレコメンド数を示している.

![](https://camo.qiitausercontent.com/5b1a28c07d0bec4c890387d13b3ba7707eecbc79/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f313639373237392f62356664336662392d306435392d366663622d636332392d3862303162363236396161622e706e67)

その結果、MDPモデルの方が高速であることがわかった.
この結果は、**MDPモデルで、オンラインでほとんど計算をしないこと**に起因している.

**より高速な推薦のために支払われる代償は、より大きなmemory footprintである**.
表6に、モデルの構築と保存に必要なメモリ量をメガバイトで示す.
MDPモデルはPredictorモデルより多くのメモリを必要とする.

![](https://camo.qiitausercontent.com/3010cad67ed8f8a57ce8d6ad46fdb948f9d1d831/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f313639373237392f39616437383637372d336664302d333131652d336163332d3464303833353661646430322e706e67)

最後に、新しいモデルを構築するのに必要な時間を考慮する.
モデル構築は、サイトのパフォーマンスに影響を与えないマシンで、長い時間間隔(せいぜい週に1回程度)で実行されるオフラインタスクであるため、この計算コストは、レコメンダーシステムを選択する際に最も重要ではないパラメータと言えるかもしれない.
とはいえ、表4にあるように、**MDPモデルは構築時間が最も短い**.(=MDPはオンライン更新的な事だから??)

![](https://camo.qiitausercontent.com/138a37d9e862ec0e06293e08672694af2fc12abf/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f313639373237392f30366332383539662d336531652d333263612d663661612d6232613130323964333633632e706e67)

MDPベースのモデルは**より多くのメモリを使用する代償として最速のレコメンデーションを提供し、より速くモデルを構築する**

## 議論はある？

- データから重み付け関数や混合重みを学習することで、キャリブレーションを向上させることができるはずである.
- 予測モデルは、明示的に指定できるアイテム間の関係も利用する必要がある.(ex. アイテムカテゴリ, 著者名, etc.)
- 最後に、年齢や性別など、ユーザーに関する情報をモデルに取り込む必要がある.

## 次に読むべき論文は？

- DQN をニュース推薦に応用した論文 [DRN: A Deep Reinforcement Learning Framework for News Recommendation](https://dl.acm.org/doi/pdf/10.1145/3178876.3185994)

## お気持ち実装