Amazonの研究者等による論文"Adaptive, Personalized Diversity for Visual Discovery"を読んだので簡単に紹介します。

概要

商品の写真が並んでるのを眺めながら良さげなものを見つける……というスタイルのECで、飽きさせず、かつ効果的なEC体験を実現する技術に関する解説になっています。米Amazon.comではStreamがそのようなスタイルになっており、そこで個々のユーザの興味に合わせて多様な商品を提示することでCTR(Click Through Rate)を向上させています。
なおこの論文はRecommender Systems(RecSys) 2016のBest short paperです。

商品のスコアリング

CTR予測

まず、商品の属性(ブランド、色、価格などなど)を特徴量としたBayesian Linear Probit regressionでCTRを予測します。これが商品を並べる際の基本的な指標になります。

P(c|\boldsymbol{a})=\Phi(\boldsymbol{u}\cdot\boldsymbol{a})

$\Phi$は正規分布の累積分布関数、$a_j$が商品$a$の属性(すべて0/1でone-hot化されてるものとする)、$\boldsymbol{u}$が重みになり、正規分布を事前分布として持ちます(表記を少しアレンジ)。MSによる元論文によれば、事前分布の平均$\boldsymbol{m}$・分散$\boldsymbol{s}$をオンライン学習でアップデートして、商品$a$に対するクリック予測分布は重みを積分消去した

P(c|\boldsymbol{a})=\Phi\left(\frac{c\ \boldsymbol{a}\cdot\boldsymbol{m}}{\sqrt{\beta^2+\boldsymbol{a}\cdot\boldsymbol{s}}}\right)\ \ (c\in\{-1,1\})

という簡単な形で与えられます。

未評価商品の対応

これで各商品のCTRが予測できるようになるのですが、そもそも表示されたことのない商品には正例であるクリックが蓄積されないので、単に予測CTR順に並べるのではなく、各商品をスロットとみなすMulti-Armed Bandit問題として扱います。
ここでは重み$\boldsymbol{u}$を事後分布$N(\boldsymbol{m},\boldsymbol{s})$からサンプリングして(Thompson Sampling, ただ報酬であるクリック予測分布(前節)から直接サンプリングしない理由があるのかはよくわからず)、その重みを用いることで人気の商品とまだ評価が定まっていない商品を程よく混ぜてスコアリングできます。

多様なアイテムを並べる

多様性の指標

単純に前述のスコアリングを利用すると、同じような属性を持つ似たような商品が同程度のスコアになり、冗長なものになってしまいます。並べるアイテムを多様化してやることにより、良さげなものをすばやく見つけられることを筆者らは過去論文で示していて、それを適用しています。
多様性を測る指標として、

\rho(A_k,\boldsymbol{w})=\boldsymbol{w}\cdot\log\left(1+\sum_{a_i\in A_k}\boldsymbol{a}_i\right)+\sum_{a_i\in A_k}s(\boldsymbol{a}_i)

という劣モジュラ関数を導入し、その最適化問題として解いています。ここで$A_k$は多様性を評価したい$k$個の商品からなるリスト、$\boldsymbol{w}$は商品属性に対する多様性に関する重み、$\boldsymbol{a}_i$は商品$i$の属性、$s(\boldsymbol{a})$は予測CTRを表します。
この関数は集合として見たときの良さ(第一項)と個々の良さを単純に足し合わせたもの(第二項)の和になっています。第二項だけ見れば予測CTRが高い商品を集めたくなるのですが、第一項で属性ベクトルの和に対数がかかっていることによりクリックに効く属性を持っている商品ばかりを集めるだけでは損をし、商品リストの属性にばらつきをもたらす形になっているのがポイントです。
劣モジュラ最適化というと小難しい感じがするのですが、大きなお友達な人もそうでない人もこちらの説明が非常に分かりやすいです。要は一番よさげな部分集合を見つける、というNP hardな問題も、評価方法が劣モジュラ性という特性を持っていると現実的に解けるよ、ということです。

多様化のための重み付けと個人化

多様性に関わる重み$\boldsymbol{w}$をどうするかですが、2種類の手法を提案しています。

ユーザ共通重み

商品カテゴリ$j$の重みを、全ユーザ合計の閲覧数$v_j$とクリック数$c_j$を使って以下のように定義します。

w_j=\frac{c_j+\alpha}{v_j+\alpha+\beta}

これは単純なクリック率($c_j/v_j$)をパラメータ$\alpha, \beta$を持つベータ分布でスムージングしたものになっています。

個人化重み

ユーザごとに重みを変える方法です。ユーザ$u$の商品カテゴリ$j$ごとのクリックが多項分布に従うとして、その共役事前分布であるDirichlet分布でスムージングしたものを用います。

\hat{w}_{uj}=\frac{c_{uj}+\alpha_j}{\left|c_{uj}+\alpha_j\right|}

(ここで閲覧数に対するクリック率、という考え方が無くなっちゃってるのが謎ですが……)

実験

以下の3種類を、Stream上でそれぞれ100,000ユーザ以上で試し閲覧時間、商品閲覧数、CTRの対照群(カッコ内)との変化率で比較しています。

1. 劣モジュラ多様化 vs. カテゴリCTRに応じたカテゴリ選択→カテゴリ内高スコア(予測CTR)商品選択
2. 劣モジュラ多様化＋全体CTRによる重み付け vs. 人手による重み付け
3. 劣モジュラ多様化＋個人化重み付け vs. 手法2.

いずれもCTRが改善しています。閲覧数が少なくなっているのは、商品リストを延々眺めなくても興味を引く商品にたどり着いていることを示すとのこと。

所感

コンテンツとしてのECというものを考えたときには、単に獲得効率を考えるだけではなく、ユーザ体験を技術でどう向上させるか、という点が重要になり、その意味で非常に参考になりました。ただ多様化の部分では劣モジュラ関数の設計とその評価がad hocなため、単純な知見としては使いまわせないかもです(recommender system業界では議論が絶えない点であると同時に面白いところでもあるのですが)。