阿里在《Diversified Interactive Recommendation with Implicit Feedback》提出了D2CB。
摘要
交互式推荐系统（Interactive recommender systems）允许用户与推荐系统间的交互，吸引了许多研究关注。之前的许多方法主要关注于优化推荐的accuracy。然而，他们通常会忽略推荐结果的多样性（diversity），因而，通常会产生不令人满意的用户体验。在本paper中，我们提出了一个新的diversified recommendation model，命名为“Diversified Contextual Combinatorial Bandit (DC2B)”，它会使用用户的隐式反馈来进行交互推荐。特别的，DC2B会在推荐过程中采用DPP来提升推荐结果的多样性。为了学到模型参数，提出了一个Thompson sampling类型的算法，它基于 variational Bayesian inference来实现。另外，理论上的regret分析也提供了对DC2B的效果保证。在真实数据集上的大量实验表明，提出的方法可以对推荐的accuracy和diversity进行balance。
介绍
常见的推荐系统通常是以非交互的方式开发，并从日志中的用户行为数据中进行学习。这种系统的一个缺点是，不能及时捕获用户偏好的变化。因而发展为允许交互的交互推荐系统。在文献中，contextual bandit learning已经表明是交互推荐问题的一个满意解法(Li et al. 2010; Zhao, Zhang, and Wang 2013; Tang et al. 2015; Wang, Wu, and Wang 2017; Qi et al. 2018)。在这些方法中，推荐系统给一个用户顺序推荐items的一个集合，并采用用户的立即反馈（immediate feedback）来提升推荐策略（recommendation policy）.
实际上，用户的隐式反馈（implicit feedback）（例如：点击历史）通常会用来构建推荐系统，由于隐式反馈是以用户为主心的（user centric），可以很容易收集到。然而，implicit feedback通常会带来偏差信号，会让推荐问题变得更具挑战。这种bias来自到：implicit feedback只能捕捉正向用户偏好（例如：观察到的user-item交互），所有的负向用户偏好会错过。尽管在该user和一个item间的无交互（non-interaction）通常会看成是负向用户偏好，但它不能显式表示用户不喜欢该item，因为无交互可能是因为该item没有被曝光给用户所造成。
另外，之前的交互式推荐方法主要关注于优化推荐accuracy。他们通常会忽略其它推荐结果的重要特性，例如：推荐的item set的多样性。因此，通过这些方法生成的推荐列表的items会非常相似，推荐结果可能只cover了很小部分的items。这会造成次优的用户体验，因而会减小推荐系统的商业价值。直观上，要达到高accuracy和diversity是非常具有挑战的。只关注diversity的方法会让accuracy受损。由于对于不流行items缺少数据，在推荐中考虑这些items会导致在推荐效果上的减弱（Adomavicius 2011）。因此，多样化推荐方法的主要目标是，在accuracy和diversity间的tradeoff进行最优化，这通常指的是“accuracy-diversity dilemma”。
在本paper中，我们提出了一种新的bandit learning framework，它基于用户的implicit feedback进行交互式推荐系统，它会尝试在推荐结果中对accuracy和diversity间努力达到一个balance。为了解决由implicit feedback引起的bias问题，我们会从两方面建模用户与推荐系统间的交互：
- i) 多样化Item的曝光（Exposure）：推荐系统会选择一个相关并且多样的items集合曝光给用户
- ii) User Engagement：用户实际中会与一些曝光的items进行engage（比如：点击一些items）
特别的，DPP会用来选择一个多样性items集合曝光给用户，考虑上所选中items集合的qualities和diversity。DPP的优点是，显式建模一个item set被选中给用户的概率，因而可以帮助解决由implicit feedback造成的bias问题。另外，items的contextual features可以用来建模在推荐items上观察到的user engagements。
总结下，在本paper中的主要贡献如下：
- 1) 我们提出了一种新的bandit learning方法：DC2B，来提升交互式推荐系统的推荐多样性
- 2) 我们提出了在Thompson sampling framework的variantional Bayesian inference来学习模型参数
- 3) 我们也为DC2B提供了理论性regret analysis
- 4) 实验表明有效
2.相关工作
交互式推荐
3.问题公式化
我们采用contextual bandit来构建多样性交互推荐系统。该推荐系统被看成是一个agent，每个item被看成是一个arm。假设：
- \(A = \lbrace a_i \rbrace_{i=1}^N\)表示是N arms的集合（例如：items）
我们假设：每个arm \(a_i\)具有一个contextual feature vector \(x_i\):
\[x_i \in R^{1 \times d}\]它会对side information进行归纳，所有arms的features X表示为：
\[X \in R^{N \times d}\]在每次尝试时，推荐agent会首先从A中选择一个关于arms的子集S，同时考虑上被选中arms的qualities和diversity。S通常称为是一个“super arm”。这里，我们经验性将一个arm \(a_i\)的quality \(r_i\)定义如下：
\[r_i = exp(\theta x_i^T)\]…(1)
其中：
- \(\theta\)是bandit参数，它描述了用户偏好（user preferences）
选中的super arm S的diversity可以通过intra-list distance metric（Zhang&Hurley 2008）进行measure。一旦一个多样性的super arm S根据一个policy \(\pi\)被选中并展示给用户，该用户在展示items的engagements（例如：在items上的点击）会用来作为推荐agent的rewards，用来最优化它的推荐policy。通过与用户交互，推荐agent的目标是：调整它的super arm选择策略来最大化它的随时间的累积回报（cumulative reward over time）。
3.1 多样化Item曝光
DPP是一个优雅的概率模型，它可以建模在许多机器学习问题中的多样性。在本文中，我们利用DPP来建模一个相关且多样的super arm S的选择概率。正式的，一个在候选arms A集合上的DPP P，是一个在\(2^A\)上的概率测量，它可以描述A的所有子集的概率。如果P在空集合\(\emptyset\)上分配非零概率，则存在一个真实、半正定kernal matrix \(L \in R^{N \times N}\)，这样，super arm S的概率\(p(S)\)可以定义如下：
\[p(S) = \frac{det(L_{[S]})}{det(L+I)}\]…(2)
其中：
- I是单位矩阵
- \(L_{[S]} \equiv [L_{ij}]_{a_i, a_j \in S}\)是L的子矩阵。如(Kulesza 2012)所示，L可以被写成一个Gram matrix，\(L = V V^T\)，其中V的行是表示arms的vectors。
根据【Chen 2018; wilhelm 2018】，我们经验性地设置 \(V_i = (r_i)^{\alpha} x_i\)，其中\(\alpha > 0\)是一个参数，它控制着item qualities的影响。接着，L的元素被定义成：\(L_{ij} = (r_i r_j)^{\alpha} x_i x_j^T\)。如果\(x_i\)是归一化的，例如：\(\| x_i \|_2 = 1\)，则在\(a_i\)和\(a_j\)间的Cosine相似度可以通过\(C_{ij} = x_i x_j^T\)进行计算。我们可以将L重写为：
\[L = Diag \lbrace exp(\alpha \bar{r})\rbrace \cdot C \cdot Diag \lbrace exp(\alpha \bar{r}) \rbrace\]…(3)
其中，\(Diag(\bar{r})\)是一个对角矩阵，它的第i个对角元素是：\(\bar{r}_i = \theta x_i^T\)，C是相似度矩阵。接着，super arm S的log概率为：
\[log p(S) \propto 2 \alpha \sum\limits_{a_i \in S} \bar{r}_i + log det(C_{[S]})\]…(4)
其中，当在S中的arms的features是正交时，最后一项是最大的，它可以帮助提升推荐的diversity【Chen 2018】。另外，等式(4)也表明参数\(\alpha\)可以帮助对推荐的相关性和多样性进行balance。
3.2 User Engagements
用户在展示items上的engagements通过它的implicit feedback（比如：在items上的点击）进行表示，它通常可以通过一个二元变量的集合进行描述。如果用户在arm \(a_i\)上具有engagments，则我们设置为\(y_i=1\)；否则设\(y_i=0\)。一旦一个arm \(a_i \in S\)已经展示给用户，我们假设：用户在\(a_i\)上的engagements只由它的quality来决定。从而，观测到的user在\(a_i\)上的engagements（例如：\(y_i=1\)）的概率\(p_i\)可以定义如下：
\[p_i \triangleq \rho (\theta x_i^T) = \frac{exp(\theta x_i^T)}{1+exp(\theta x_i^T)} = \frac{r_i}{1 + r_i}\]…(5)
这可以被解释成：当一个arm \(a_i\)被提供给该用户时，在该arm或一个virtual arm \(a_0\)上的user engages具有一个相关分（relevance score）1。基于该假设，我们可以定义observed user engagements的联合概率 \(Y = \lbrace y_i \mid a_i \in S \rbrace\)如下：
\[p(Y, S, \theta) = p(\theta) p(S | \theta) p(Y | S, \theta) \\ = p(\theta) \frac{det(L_{[S]})}{det(L+I)} \prod\limits_{a_i \in S} p_i^{y_i} (1 - p_i)^{1-y_i}\]…(6)
其中：
- \(p(\theta)\)会预先分配给bandit参数。另外，我们假设\(p(\theta)\)服从一个高斯分布\(N(m, \Sigma)\)，其中\(m, \Sigma\)是有边界的。该假设通常会被用于实际情况中。
4.参数推断（Parameter Inference）
一旦一个新的observation (S, Y)提供，我们会采用variational Bayesian inference【Blei 2017】来开发一个闭合形式近似\(\theta\)的后验概率。根据(Blei 2017)，\(\theta\)的近似后验\(q(\theta)\)可以表示成：
\[log q^*(\theta) = E_{param \neq \theta} [log \ p(Y, S, \theta)] + const\]再者，基于线性代数的知识，我们有：
\[det(L_{[S]}) = \prod_{a_i \in S ^{r_i^{2\alpha}}} det(X_{[S]} X_{[S]}^T)\]以及
\[det(L+I) = exp(tr(log(L+I)))\]接着，我们可以有以下的似然函数：
\[log p(Y, S | \theta) = \sum_{a_i \in S} (\phi_i + 2\alpha log r_i) + log det(X_{[S]} X_{[S]}^T) - \sum\limits_{j=1}^N log (1 + r_j^{2 \alpha} x_j x_j^T)\]…(7)
其中：
- \[\phi_i = y_i log p_i + (1+y_i) log(1 + p_i)\]
在等式(7)中，似然函数是一个logistic function，它与在\(\theta\)上的高斯先验是共轭的。为了解决该问题，以下在logistic function上的高斯下界（lower bound）被用来近似似然（jaakkola 1997）：
\[\rho(x) \geq \rho(\epsilon) e^{\frac{x-\epsilon}{2} - \lambda (\epsilon)(x^2 - \epsilon^2)}\]其中：
- \[\lambda(\epsilon) = \frac{1}{2 \epsilon} ( \rho(\epsilon) - \frac{1}{2})\]
- \(\epsilon\)是一个辅助变量，需要进行调整使得bound在\(x = \pm \epsilon\)附近。
再者，通过假设：
- \[\| \theta \|_2 \leq A\]
- \[\| x_j \|_2 \leq B\]
我们有：
\[- log[1 + exp(2 \alpha \theta x_j^T) x_j x_j^T] \geq - exp(2 \alpha \theta x_j^T) x_j x_j^T \geq -exp(2 \alpha A B) B^2\]由于我们假设m和\(\Sigma\)是有界的，因而推断\(\theta\)是有界是合理的。通过对\(x_j\)进行归一化，我们可以做出\(x_j\)也是有界的。接着，我们有似然函数的下界，如等式（7）所示：
\[log p(Y, S | \theta) \geq const. + \sum\limits_{a_i \in S} [\frac{2y_i - 1 + 4 \alpha) \theta x_i^T}{2} - \lambda(\epsilon_i)(\theta (x_i^T x_i) \theta^T) + \phi(\epsilon_i)]\]…(8)
其中，\(\phi(\epsilon_i) = log \rho(\epsilon_i) - \frac{\epsilon_i}{2} + \lambda(\epsilon_i) \epsilon_i^2\)。\(\theta\)的最优variational分布如下：
\[log q^*(\theta) \approx E[ log h(\theta, \epsilon)] + E[log p(\theta)] + const\]由于模型的共轭性，我们可以知道：\(q(\theta)\)会遵循高斯分布\(N(m_{post}, \Sigma_{post})\)，其中均值和方差如下：
\[\sum_{post}^{-1} = \sum^{-1} + 2 \sum\limits_{a_i \in S} \lambda(\epsilon_i) x_i^T x_i \\ m_{post} = \sum_{post} [\sum^{-1} m + \sum\limits{a_i \in S}(y_i + 2 \alpha - \frac{1}{2}) x_i]\]…(9)(10)
由于没有先验分配给\(\epsilon_i\)，\(\epsilon_i\)的最优值可以通过最大化期望似然函数来生成：\(l(\epsilon_i) = E[log p(Y, S \mid \theta, \epsilon_i)])\)。对\(l(\epsilon_i)\)根据\(\epsilon_i\)进行求导并将它设置为0，可以获得\(\epsilon_i\)的最优值：
\[\epsilon_i = \sqrt(x_i (\sum_{post} + m_{post}^T m_{post}) x_i^T)\]…(11)
我们采用Thompson sampling(TS)更新模型参数来对exploration和exploitation进行balance。TS算法的详情见算法1.
算法1
在标准TS方法中，它需要从模型参数\(\theta\)中进行抽样。由于logistic似然函数与高斯先验不共轭，我们提出从近似后验分布\(q(\theta)\)中进行抽样。一旦完成了\(\theta\)的抽样，DPP kernel matrix L就固定了，我们可以通过最大化\(f_{\theta}(S) = \prod_{a_i \in S} p_i det(L_{\mid S \mid})\)来选择最优的super arm S。我们采用fast gready MAP inference算法（Chen 2018）来获得最优的super arm。greedy算法的详情如算法2所示。
算法2
4.Regret分析
我们考虑一个模型，它涉及：
- 一个actions的集合S
- 一个函数集合 \(F = \lbrace f_{\theta}: S \rightarrow \mid \theta \in \Theta \rbrace\)，它通过一个随机变量\(\theta\)进行索引，它属于一个索引集合\(\Theta\)。
在每个时间t时，一个随机子集\(S_t \subseteq S\)会被展示，一个action \(S_t \in S_t\)会被选中，之后会获得reward \(R_t\)。我们定义了reward function如下：
\[E[R_t] \triangleq f_{\theta}(S_t) = \prod_{a_i \in S_t} p_i det(L_{[S_t]}) = \prod_{a_i \in S_t} p_i r_i^{2\alpha} det(X_{[S_t]} X_{[S_t]}^T\]并且定义了在第t次试验时的reward：
\[R_t = f_{\theta}(S_t) + \epsilon_t\]因此，我们有\(E[\epsilon_t] = 0\)。另外，我们假设：
\[\forall f_{\theta} \in F, \forall S_t \in S, f_{\theta} (S_t) \in [0, C]\]对于一个推荐policy \(\pi\)，我们可以定义Bayesian risk bound如下：
\[Regret(T, \pi) = \sum\limits_{t=1}^T E[max_{s \in S_t} f_{\theta}(s) - f_{\theta}(S_t)]\]…(12)
为了执行regret analysis，我们首先介绍以下两个辅助定理，它根据【Russo 2014】的观点9和观点10被证明。不同之处是，这种方法的变量是一个arms集合\(S_t\)，它替代了单个arm a，证明相似，出于篇幅此处省去。我们根据定理7设置\(\sigma=1\)，它表明\(f_{\theta}\)满足假设2.
引理1: 对于所有\(T \in N, \alpha_0 > 0, \sigma \leq 1/2T\)，有：
\[Regret(T, \pi^{TS}) \leq 4 \sqrt{dim_M(F, T^{-1}) \beta_T^*(F, \alpha_0, \sigma)T} + 1 + [dim_M(F, T^{-1}) + 1] C\]其中：
。。。
5.实验
实验设定
数据集：该实验会在以下数据集上执行：Movielens-100K, Movielens-1M, Anime.
Setup和Metrics
对于交互式推荐方法，最合适的是使用一个具有实时的用户交互的在线实验setting进行评估。然而，通常在学术研究中不可能具有这样的environment。因而，根据（Zhao 2017），我们假设，用户在items上的ratings记录在我们的实验数据集中，它们是无偏 的，这些记录可以被 看成是无偏的用户反馈（unbiased user feedback）。无偏离线评估策略（Li 2011）被 用于评估推荐方法。在实验中，我们随机将每个dataset划分成两个非重合的集合，通过随机采样了80%的用户用于训练，并使用剩余20%的用户用于测试。接着，我们会基于训练数据采用BPRMF来学习items的embeddings，它会被用来做为arms的contextual features。经验性的，我们会将item embeddings的维度设置为10。由于用户通常对少量的top-ranked推荐items感兴趣，我们会采用Precision@N来评估推荐accuracy（SHi 2014），通过在 \(\lfloor N/ \mid S \mid \rfloor\)次试验（trials）的推荐items进行聚合，并计算precision。特别的，N设置 为10， 30， 50。我们也会评估每个方法在所有推荐实验 中的平均推荐diversity，通过ILD metric（intra-list distance）：
\[\frac{1}{T} \sum\limits_{t=1}^T [ \frac{2}{|S_t| (|S_t| -1)} \sum\limits_{a_i \in S_t} \sum\limits_{a_j \in S_{t,i \neq j} } ( 1- sim_{ij})]\]其中：
- \(S_t\)：是在trail t的推荐item set
- \(\mid S_t \mid\)：表示\(S_t\)的size
- T：是推荐实验的总数目
- \(sim_{ij}\)：表示在\(a_i\)和\(a_j\)中的相似度
由于一个item可能会属于多个item类目，我们会通过使用两个items的类目的jaccard相似度来定义成item相似度\(sim_{ij}\)。对于这些accuracy和diversity metrics来说，我们首先会计算每个user的value，接着会上报在所有users上的平均值。根据CHeng 2017，我们会采用F-measure来评估不同方法在accuracy和diversity的tradeoff上的表现，其中：
\[F-measure = 2 * accuracy * diversity / (accuracy + diversity)\]由于训练users与测试users是非重合的，为warm-start settings设计的推荐算法并不适合作为baselines。在本paper中，我们会将DC2B与以下推荐方法进行对比：
- 1）LogRank：在该方法中，我们会定义每个arm \(a_i\)的quality score为：\(r_i = 1/(1+ exp(-\bar{u}x_i^T))\)，其中：\(\bar{u}\)是从训练数据中学到user embeddings的平均。接着，会选中\(\mid S_t \mid\)个具有最高quality scores的arms作为一个super arm \(S_t\)来进行第t次trail的推荐
- 2) MMR：该方法采用MMR策略来提升推荐多样性。在第t次trial时，该方法会顺序选择一个具有最大MMR score的arm到\(S_t\)中。MMR score的定义如下：\(\bar{r}_i = \alpha r_i - \frac{(1-\alpha)}{\mid S_t \mid} \sum_{j \in S_t} sim(x_i, x_j)\)，其中：\(r_i\)是在LogRank方法中定义的arm quality，\(sim(x_i, x_j)\)是在\(x_i\)和\(x_j\)间的cosine相似度
- 3）e-greedy：该方法会以\(\epsilon\)的概率随机添加一个可提供的arm到\(S_t\)中，以\(1-\epsilon\)的概率添加具有最高quality的arm到\(S_t\)中，item quality的定义与LogRank方法相同
- 4) \(DPP^{map}\)（CHen 2018）：该非交互式方法会使用DPP来提升推荐多样性。item quanlity的定义与在LogRank中的相同
- 5) \(C^2 UCB\)（Qin 2014）：该方法会集成LinUCB框架，使用一个entropy regularizer来为交互式推荐提升diversity
- 6) EC-Bandit（Qi 2018）：该bandit方法基于Thompson sampling框架，并为使用用户隐式负反馈的交互式推荐进行开发。在本方法中，用户需要与 recommender交互 \(S_t\)次，并在第t次实验生成推荐item集合
对于所有方法，我们经验性地将每次实验的\(S_t\)的size设置为10。一个validation set会从training data中采用来选择超参数。每个方法的最佳参数设置如下。
- MMR的\(\alpha\)会设置为0.9
- e-greedy的\(\epsilon\)会设置为0.1
- \(DPP^{map}\)的\(\theta\)会设置为0.6
- 在\(C^2UCB\)中，我们会设置\(\lambda_0 = 100, \lambda=0.1, \sigma = 1\)
- 在EC-Bandit中，我们会设置参数\(\lambda=1\)
- 对于DC2B，我们经验性地将\(alpha=3, \lambda=1\)
效果对比
不同算法的推荐的accuracy和diversity如表2所示。在表2中，提出的DC2B方法，在ML-1M和Anime datasets上会达到最佳的推荐accuracy（例如：Precision@N），在ML-100K dataset上达到第二好的accuracy。例如，在Anime dataset上，DC2B的效果要极大胜过C2UCB和EC-Bandit：59.35%和107.11%，。。。
略