Obey Your MATHEMATICS.

機械学習関連の純粋数学や実験など

【Recsys2016】Adaptive, Personalized Diversity for Visual Discovery (AmazonStream)に関するメモ

この記事は次の論文:

Adaptive, Personalized Diversity for Visual Discovery

Choon Hui Teo Amazon, Palo Alto, CA, USA
Houssam Nassif Amazon, Seattle, WA, USA
Daniel Hill Amazon, Palo Alto, CA, USA
Sriram Srinivasan UC Santa Cruz, Santa Cruz, CA, USA
Mitchell Goodman Amazon, Seattle, WA, USA
Vijai Mohan Amazon, Seattle, WA, USA
S.V.N. Vishwanathan Amazon & UC Santa Cruz, Palo Alto, CA, USA


についての個人的なメモです。*1

§1. 概要と背景

この論文は、Recsys2016 のショートペーパー部門の受賞論文。*2

AmazonStreamと呼ばれるサービス(日本にはないっぽい?)を題材*3にして、推薦システムにつきまとう推薦アイテムの種類の偏りを劣モジュラ関数最適化問題に焼き直して上手くやったと言うもの。多様性を持たせた推薦システムの構築。

好きなお店にウィンドウ・ショッピングしていく感覚でアイテムをユーザーに推薦したい ---> 豊かなユーザー体験へ。

ステップは次の3つに分けられる
◯CTR予測モデル
◯多様性問題の定式化
◯ユーザーのモデリング(?)

§2. CTRのモデリングについて-その1-

基本的に次のMicrosoftの論文と同じ。

Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine - Microsoft Research

↑この論文には次のような背景があるらしく、なんか楽しい

Recognising the importance of CTR estimation for online advertising, management at Bing/adCenter decided to run a competition to entice people across the company to develop the most accurate and scalable CTR predictor. The algorithm described in this publication tied for first place in the first competition and won the subsequent competition based on prediction accuracy. As a consequence, it was chosen to replace Bing’s previous CTR prediction algorithm, a transition that was completed in the summer of 2009.

結構古い(2009年)のですが、まだまだ現役なのもまた良い。



ユーザー&アイテムの特徴量をconcatenateした特徴量ベクトルを {  { \bf x} = (x_i), \ \ x_i \in \{0, 1 \}   }, そしてclick or notを表すターゲットとなる値を{ y \in \{ -1, 1 \} } とする。(特徴量ベクトルは何故か全部カテゴリカル。)

この時クリック確率を表す確率分布を

{ p(y|x):= \Phi \left(  \dfrac{y }{\beta} {\bf  w^T x }  \right)}

{  \Phi(t) := \displaystyle \int^t_{-\infty} \dfrac{1}{\sqrt{2\pi}} \exp\left( -\dfrac{x^2}{2} \right) dx }

で定める。ここで{ {\bf w } }が最適化すべきパラメータで、ベイズ的に扱うために正規分布を事前分布を置き予測分布がclosed formで書けるようにする、が、事後分布は解析的には解けない。それを推定するためのオンライン学習アルゴリズム
www.microsoft.com

ここにあるのでそれを利用している。

そのトリックにより、サンプルが生成される度にオンラインで事前分布のパラメータを更新していく形で最適化をしていく。

§3. CTRのモデリングについて-その2-

前セクションの単純なCTRモデルの問題点↓

Our catalog consists of hundreds of thousands of items with thousands of items added or purged daily. The ex- pected click probability may unduly favor popular items over underexposed or recently added items. This is because un- derexposed items will likely be associated with undertrained model weights that potentially underestimate the true click probability.

新規アイテムの訓練データも欲しい、と言う事でThompson samplingしてランダムに新しいアイテムも晒す。*4

§4. 多様性問題の定式化

CTRモデリングによって、各ユーザーに対してアイテムのスコアリストが得られる。
k個をユーザーに表示するとして、スコア順に並べ替え大きい順にk個取ってしまうと種類が偏る-->多様性をもたせたい。



アイテムの特徴量ベクトルの集合を{ \mathcal{A} := \{ \bf a_1, a_2, a_3,... \}  (a_i \in \mathbb{R}^d ) }とする。

ここで、{ \mathcal{A} }上の劣モジュラ関数 {\rho : 2^\mathcal{A} \rightarrow \mathbb{R}} を次のように定義する:

{  \rho(A,{\bf u}) := \displaystyle \left<{\bf w}_u, \log\left( 1 + \sum_{ {\bf a } \in A}{\bf a }  \right)  \right> + \sum_{ {\bf a } \in A} s({\bf a } ) }

ここで第一項は {\mathbb{R}^d  } 上の標準内積{s} はCTRスコアを出力する関数。また、{ {\bf w}_u }{\mathbb{R}^d  } に埋め込まれたユーザーベクトル(これは次のセクションで。)

そして最適なk個のアイテムリストは次のように与えられる:

{  A^*_k({\bf w}_u)  := \displaystyle \underset{A \in 2^\mathcal{A}, |A|=k}{argmax}   \ \ \rho(A,{\bf w}_u)}

対数を噛ませる事で、一方向だけの成分を伸ばすことで最大化されていくのを防いでいる。これにより多様性が得られる。

§5. ユーザーのモデリング

この論文では、アイテムの特徴量はすべてカテゴリ値になっている事に注意する。
ユーザー {u} のクリック回数を {m_u} 、カテゴリー毎のクリック回数を表すベクトルを { {\bf c_u} }とする。

各クリックはユーザー毎に多項分布に従い、多項分布のパラメータはユーザー毎に、共通のディリクレ分布から生成されているとしてモデリングする。

{ {\bf w}_u \sim Dirichlet ({\bf \alpha} ) }

{ {\bf c}_u \sim Multinomial ({\bf w}_u) }

ここで{ {\bf \alpha} } はディリクレ分布のパラメータ。


事後分布もディリクレ分布であり、期待値{ \hat{{\bf w}}_u}はexplicitに書くことが出来る:

{  \hat{{\bf w}}_u \ = \ \left({\bf c}_u +{\bf \alpha} \right) \| {\bf c}_u +{\bf \alpha} \|^{-1}_1  }

§6. 所感

◯カテゴリ値にこだわる意味がよく分からない。

◯劣モジュラに出てくるユーザーの特徴量ですが、結局LDAっぽい事やっているだけで、もっとPersonalize出来るのでは。

◯ユーザー毎に劣モジュラ最大化を解くの、相当しんどいのでは。

◯劣モジュラにこだわらなくても、アイテムのベクトル化が上手く行っていれば、内積を使って上手くフィルタリングできそうな気がする。(劣モジュラ無知勢なので逃げたい)

*1:4月から推薦システム絡みの機械学習をすることになりそうなので、それ関係の記事が増えるかと思います。

*2:人 工 知 能 32巻1号(2017年1月)の神嶌先生の記事参照

*3:ウィンドウ・ショッピングをECでやる感じのサービス?

*4:この辺は次元圧縮してアイテムをモデリングすればやらなくても良さそう。