华为在《AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction》提出了AutoFIS

摘要

学习特征交叉对于CTR预估来说非常重要。在大多数已经存在的深度学习模型中，特征交叉是人工设计或者简单枚举的。然而，枚举所有的特征交叉会带来很大的内容和计算开销。更糟的是，无用的交叉会在训练过程中引入噪声和复杂度[28]。在本工作中，我们提出了一个two-stage算法称为Automiaitc Feature Interaction Selection（AutoFIS）。AutoFIS可以为FM自动标识出重要的特征交叉，有一定计算开销。在search stage中，通过替代搜索候选特征交叉的离散集合，我们会通过引入结构参数将从离线变成连续进行选择。通过在结构参数上实现一个regularized optimizer，模型可以在训练过程中自动标识并移除冗余的特征交叉。在retrain stage，我们会保存结构参数，将它们作为一个attention unit来进一步增强效果。在三个大规模数据集上的离线实验表明，AutoFIS可以极大提升多个FM-based模型。AutoFIS被成功部署在Huawei APP store推荐服务中，10天数据看，可以在CTR/CVR上分别提升20.3%和20.1%。

3.方法

在本节中，我们描述了提出的AutoFIS，它可以自动选择在FM中重要的特征交叉。

3.1 FM（Base Model）

首先，我们定义FM：

定义3.1: FM是这样的模型：来自不同features的多个embeddings的交叉会通过一些内积/neural network的操作来建模成一个实数（real number）。

图1

我们采用FM、DeepFM、IPNN作为实例来公式化我们的算法，并探索在多个数据集上的效果。图1表示了：FM、DeepFM和IPNN模型的结构。FM包含了一个feature embedding layer和一个feature interaction layer。除了这两个layers外，DeepFM和IPNN模型会包含一个额外的layer：MLP layer。在DeepFM和IPNN间的不同之处是：feature interaction layer和MLP layer会在DeepFM中并列工作，而在IPNN中则是顺序的。

在后续章节上，我们将简要描述FM中的feature embedding layer和feature interaction layer。为了与DeepFM和IPNN模型一起工作，MLP layer和output layer也会被公式化。接着，我们提出的AutoFIS是如何在feature interaction layers上工作的会被详述，例如：基于结构参数选择重要的特征交叉。

Feature Embedding Layer。在大多数CTR预估任务中，数据会以multi-field categorical的形式采集。一个典型的数据预处理，会通过one-hot或multi-hot encoding会将每个数据样本转化成一个高维稀疏向量。当一个field是多变量时，会被表示成一个multi-hot encoding vector。一个数据样本可以表示成：

\[x = [x_1, x_2, \cdots, x_m]\]

其中，m是fields数目，\(x_i\)是第i个field的one-hot或multi-hot encoding vector。一个feature embedding layer被用于将一个encoding vector转换成一个低维向量：

\[e_i = V_i x_i\]

…(1)

其中：\(V_i \in R^{d \times n}\)是一个matrix，\(n_i\)是在第i个field中的。

• 如果\(x_i\)是一个具有第j个元素\(x_i[j]=1\)的one-hot vector，那么\(x_i\)的representation是\(V_i^j\)
• 如果\(x_i\)是一个multi-hot vector，对于\(j=i_1, i_2, \cdots, i_k\)，具有\(x_i[j]=1\)，那么这些元素的embeddings是\(\lbrace V_i^{i1}, V_i^{i2}, \cdots, V_i^{ik}\rbrace\)，接着\(x_i\)的representation是这些embeddings的sum或average。

feature embedding layer的output是多个embedding vectors的concatenation：

\[E= [e_1, e_2, \cdots, e_m]\]

Feature Interction Layer

在将features转换成低维空间之后，feature interactions可以使用feature interaction layer被建模到这样的一个空间。首先，pairwise feature interactions的inner product会被计算如下：

\[[\langle e_1, e_2 \rangle, \langlee_1, e_3 \rangle, \cdots, \langle e_{m-1}, e_m \rangle]\]

…(2)

其中：

• \(e_i\)是第i个field的feature embedding，
• \(\langle \cdot, \cdot \langle\)是两个vectors的inner product

在该layer中的pair-wise feature interactions的数目是\(C_m^2\)：

\[l_{fm} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \langle e_i, e_j \rangle\]

…(3)

这里，所有的feature interactions会等贡献地被传给下一layer。如第1节和第4节，不是所有的特征交叉都有相等的预见性，无效交叉可能会影响效果退化。因此，我们提出了AutoFIS算法来有效选择重要的特征交叉。

为了研究我们的方法是否可以被用来识别重要的高阶交叉，我们将具有3rd-order交叉（例如：三个fields的组合）的feature interaction layer定义为：

\[l_{rm}^{3rd} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \langlee_i, e_j \rangle + \sum\limits_{i=1}^m \sum\limits_{j<i}^m \sum\limits_{t>j}^m \langle e_i, e_j, e_t \rangle\]

…(4)

MLP Layer。MLP Layer会包含许多具有activation functions的FC layers，它会学到features的关系和组合。一个这样的layer的output是：

\[a^{(l+1)} = relu(W^{(l)} a^{(l)} + b^{(l)})\]

…(5)

其中：

• \(a^{(l)}, W^{(l)}, b^{(l)}\)分别是第l层的input、model weight、bias。
• \(relu(z) =max(0, z)\)：为Activation
• \(a^{(0)}\)是input layer
• \(MLP(a^{(0)}) = a^{(h)}\)：其中h是MLP layer MLP的depth

Output Layer

FM模型没有MLP layer，并直接将feature interaction layer与prediction layer连接：

\[\hat{y}_{FM} = sigmoid(l_{fm}) = \frac{1}{1 + exp(-l_{fm})}\]

…(6)

其中，\(\hat{y}_{FM}\)是predicted CTR。

DeepFM会将feature interaction layer与MLP layers并行进行组合：

\[\hat{y}_{DeepFM} = sigmoid(l_{fm} + MLP(E))\]

…(7)

当在IPNN中时，MLP layer会跟在feature interaction layer之后：

\[\hat{y}_{IPNN} = sigmoid(MLP([E, l_{fm}]))\]

…(8)

注意，IPNN的MLP layer可以对不同feature interactions进行reweighting，来捕获它们的相对重要性。这也是为啥IPNN要比FM和DeepFM具有更高能力的原因。然而，有了IPNN的公式，我们不能检索对应于每个feature interaction的相对贡献的准确值。因此，在IPNN中的feature interactions会带来噪声和计算开销。下面，我们展示了AutoFIS是如何改进IPNN的。

Objective Function

FM、DeepFM、IPNN会共享相同的objective function，例如：最小化predicted values和labels间的cross-entropy：

\[L(y, \hat{y}_M) = - y log\hat{y}_M - (1-y) log(1 - \hat{y}_M)\]

…(9)

其中：

• \(y \in \lbrace 0, 1 \rbrace\)是label
• \(\hat{y}_M \in [0, 1]\)是y=1的预估概率。

3.2 AutoFIS

AutoFIS会自动选择有用的特征交叉，它可以补用于任意FM模型的feature interaction layer。在本节中，我们会详述它是如何工作的。AutoFIS可以分成两个阶段：search stage和re-train stage。在search stage中，AutoFIS会检测有用的特征交叉；而在re-train stage中，具有选中的feature interactions的模型会被重新训练。

Search Stage

为了让该算法更好地呈现，我们引入gate操作来控制是否选择一个feature interaction：一个open gate对应于选中一个feature interaction，而一个closed gate会导致一个dropped interaction。对应于所有二阶特征交叉的gates的总数是：\(C_m^2\)。以brute-force方式寻找open gates的最优集合非常挑战，因为我们会面对一个非常大的搜索空间（\(2^{C_m^2}\)）。在本工作中，我们会从一个不同的视角去处理该问题：作为在open gates的一个离散集合上进行搜索的替代，我们会通过引入结构参数\(\alpha\)可以选择连续方式，以便每个feature interaction的相对重要性可以通过梯度下降进行学习。提出的AutoFIS的总览如图2所示。

图2 AutoFIS总览

这种通过梯度学习的结构选择scheme受DARTS【20】的启发，在DARTS中，目标是从在CNN结构中的候选操作集合中选择一个操作（operation）。

特别说明的是，我们会将在FM中的interaction layer重新公式化为：

\[l_{AutoFIS} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \alpha_{(i,j)} \langle e_i, e_j \rangle\]

…(10)

其中：

\(\alpha = \lbrace \alpha_{(1,2)}, \cdots, \alpha_{(m-1,m)} \rbrace\)是结构参数。在AutoFIS的search stage，\(\alpha_{(i,j)}\)值会以这样的方式学习：\(\alpha_{(i,j)}\)可以表示每个feature interaction到final prediction的相对贡献。接着，我们可以通过设置那些不重要的gates关闭决定每个feature interaction的gate状态。

Batch Normalization

从整体neural network的角度看，一个feature interaction的贡献可以通过\(\alpha_{(i,j)} \cdot \langle e_i, e_j \rangle\)来进行测算。相同的贡献可以通过对该项rescaling成\((\frac{\alpha_{(i,j)}}{\eta}) \cdot (\eta \cdot \langle e_i, e_j\rangle )\)，其中\(\eta\)是一个真实值。

由于\(\langle e_i, e_j \rangle\)的值可以与\(\alpha_{(i,j)}\)联合学习，它们的scale组合会导致对\(\alpha_{(i,j)}\)的不稳定估计，比如：\(\alpha_{(i,j)}\)不再表示\(<e_i, e_j>\)相对重要性。为了解决该问题，我们在\(\langle e_i, e_j \rangle\)上使用Batch Normalization来取除它的scale问题。BN已经作为一个标准方法被用来训练DNN来达成快速收敛和更好的效果。

原始的BN会使用一个mini-batch的统计信息来对activated output进行归一化。特别的，

\[\hat{z} = \frac{z_{in} - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} \\ z_{out} = \theta \cdot \hat{z} + \beta\]

…(11)

其中：

• \(z_{in}, \hat{z}, \hat{z_{out}}\)是input、BN的归一化值、BN的output值
• \(\mu_B, \sigma_B\)是\(z_{in}\)在一个mini-batch B上的均值和标准差；
• \(\theta, \beta\)分别是BN的trainable scale和shift参数
• \(\epsilon\)是数值稳定性的一个常数

为了得到\(\alpha_{(i,j)}\)的稳定估计，我们分别将scale和shift参数设置为1和0. 在每个feature interaction \(<e_i, e_j>\)上的BN操作可以被计算成：

\[\langle e_i, e_j\rangle_{BN} = \frac{\langle e_i, e_j\rangle - \mu_B(\langle e_i, e_j \rangle)}{\sqrt{\sigma^2_B(\langle e_i, e_j\rangle)} + \epsilon}\]

…(12)

其中：

• \(\mu_B\)和\(\sigma_B\)是在mini-batch B中的\(\langle e_i, e_j \rangle\)的均值和标准差。

GRDA Optimizer

GRDA optimizer的目标是：获得一个sparse DNN。为了在每个gradident step t上使用数据\(Z_t\)来更新\(\alpha\)，我们使用以下的等式：

\[\alpha_{t+1} = \underset{argmin}{\alpha} \lbrace \alpha^T(-\alpha_0 + \gamma \sum\limits_{i=0}^t \nabla L(\alpha_t; Z_{i+1}) + g(t, \gamma) \| \alpha \|_1 + 1/2\| \alpha \|_2^2 \rbrace\]

其中：

• \(g(t,\gamma) = c\gamma^{1/2} (t\gamma)^u\),
• \(\gamma\)是learning rate
• c和\(\mu\)是可调超参数，用于对accuracy和sparsity做tradeoff

在搜索阶段，我们使用GRDA optimizer来学习结构参数\(\alpha\)，并获得一个sparse解。这些不重要的特征交叉（例如：具有零值的\(\alpha_{i,j}\)值）会被自动丢弃。其它参数可以通过Adam optimzier进行学习。

One-level优化

为了在AutoFIS的search stage上学习结构参数\(\alpha_{i,j}\)，我们提出\(\alpha\)与其它所有network权重v进行联合最优化（比如：等式3中的w，和等式5中的\(W^{(l)}\)和\(b^{(l)}\)）。这与DARTS不同。DARTS会将\(\alpha\)看成是更高lebel的决策变量，将network weights看成是更低level的变量，接着使用一个bi-level最优化算法来对它们进行最优化。在DARTS中，假设：当只有network weights被合理学习时，以使\(\alpha\)可以“做出合适决策”，模型可以选择operation。在AutoFIS公式的上下文中，这意味着，我们可以决定：在network weights被合理训练时，一个gate是否会是open或closed，这会导致我们会回到对\(2^{C_m^2}\)个模型完全训练的问题。为了避免这个问题，DARTS提出，只在一个gradient descent step上对network weights的最优值进行逼近，并迭代训练\(\alpha\)和\(v\)。

我们会讨论这种近似的不准确性可能对效果有损。因此，通过对bi-level optimization进行替代，我们提出使用one-level optimization对\(\alpha\)和\(v\)进行联合优化。特别的，参数\(\alpha\)和\(v\)会与gradient descent一起更新：

\[\partial_v L_{train}(v_{t-1}, \alpha_{t-1}) = \partial_{\alpha} L_{train}(v_{t-1}, \alpha_{t-1})\]

…(14)

在该setting中，\(\alpha\)和\(v\)可以探索它们的设计空间直到收敛，\(\alpha\)可以被学习用来作为独立feature interactions的贡献。在第4节中，我们展示了one-level optimization要优于two-level optimization。

Re-train Stage

在search stage的训练之后，一些不重要的交叉会根据架构参数\(\alpha^*\)被自动抛弃。我们使用\(G_{(i,j)}\)来表示特征交叉\(\langle e_i, e_j \rangle\)的gate status，当\(\alpha_{(i,j)}^*=0\)时会\(G_{(i,j)}\)将并设置为0；否则，我们设置为1. 在retrain阶段，这些不重要的feature interactions的gate status被确定永久关闭。

在移除这些不重要的交叉后，我们会使用在模型中保存的\(\alpha\)来对新模型进行retrain。特别的，我们会将等式(3)的feature interaction layer进行替换：

\[l_{rm}^{re} = \langle w,x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>1}^m \alpha_{(i,j)} G_{(i,j)} \langle e_i, e_j \rangle\]

…(15)

注意，这里\(\alpha_{(i,j)}\)不再作为一个indicator来决定是否一个交叉该包含在模型内（比如：在search stage）。作为替代，它会当成是结构的一个attention unit来学习保持特征交叉的相对重要性。在该stage中，我们不必选择feature interactions。因此，所有参数会通过Adam optimizaer来学习。

4.实验

略

• 1.https://arxiv.org/pdf/2003.11235.pdf

阿里在《Personalized Re-ranking for Recommendation》中提出了PRM算法：

1.介绍

ranking对推荐系统很重要。由ranking算法给出的ranked list的quality对于用户满意度以及推荐系统收益来说具有很大影响。大量的ranking算法被提出来优化ranking的效果。在推荐系统中，ranking通常只考虑user-item pair features，并没有考虑在list中的其它items，特别是那些在旁边的items【8，35】。尽管pairwise和listwise的L2R方法尝试通过将item-pair或者item-list作为input来解决该问题，他们只关注于最优化loss function以便更好地利用labels，例如：click-through data。他们不会显式建模在feature space中的items间的相互影响。

一些工作【1，34，37】尝试显式建模在items间的相互影响，来对之前ranking算法给出的initial list进行refine，这被称为“re-ranking”。主要思想是，通过对intra-item patterns进行编码到feature space的方式来构建scoring function。进行feature vectors编码的SOTA方法有：RNN-based（比如：GlobalRerank，或者DLCM）。他们会将initial list来顺序feed给RNN-based结构，在每个time step输出encoded vector。然而，RNN-based方法对于建模在list间的交互来说具有局限性。之前编码的item的特征信息会随着编码距离降低。受transformer的启发，我们提出使用transformer架构来建模items间的相互影响。transformer结构使用self-attention机制，其中：任意两个items可以直接相互交叉，不会随着编码距离降级。同时，由于并行化，Transformer的encoding过程要比RNN-based方法更高效。

除了items间的交互外，对于交叉的个性化encoding功能，也要在推荐系统中的re-ranking中被考虑。推荐系统的re-ranking是user-specific的，依赖于用户偏好和意图。对于一个对价格很敏感的用户，“price”特征间的交叉对于re-ranking model来说很重要。例如，当用户关于价格对比时，具有不同价格的相似items趋向于在list中会更集中。当用户没有明显的购买意图时，在推荐列表中的items趋向于更分散。因此，我们会引入一个个性化模块到Transformer结构来表示在item交互上的用户偏好和意图。在list中的items与user间的交互，可以在PRM中被并行捕获。

该paper的主要贡献如下：

• 问题。我们提出一个个性化re-ranking问题：并且首次显式地引入个性化信息到reranking任务中。实验结果表明，在list representation中引入用户表示（users’ representation）的效果。
• 模型: 我们使用Transformer并且带上个性化embedding来计算initial input ranking list的representations，并输出re-ranking score。对比起RNN-based方法，self-attention机制允许我们以一个高效地方式来建模user-specific在任意两个items间的交互影响。
• 评估：我们在离线和在线实验上，展示了我们的方法极大地胜过SOTA方法。online A/B测试表明了它能达到更高的CTR和收益。

2.相关工作

略

3.Reranking模型公式化

在本节中，我们首先给出一些关于l2r的前置知识，以及推荐系统的reranking方法。接着，我们将问题进行公式化来求解。概念如表1所示。

Learning to Rank（也称为LTR）方法在IR和推荐的排序中被广泛使用，用来生成一个有序列表。LTR方法会基于items的feature vector学习一个全局的scoring function。有了这个全局函数，LTR方法会通过对candidate set中的每个item进行打分输出一个有序列表。该全局scoring function通常通过最小化以下的loss function L来学到：

\[L = \sum\limits_{r \in R} l (\lbrace y_i, P(y_i | x_i;\theta) | i \in I_r \rbrace)\]

…(1)

这里：

• R：推荐的所有用户请求的集合。
• \(I_r\)：对于请求 \(r \in R\)的items的候选集合。
• \(x_i\)：表示item i的feature space。
• \(P(y_i \mid x_i; \theta)\)是在给定参数\(\theta\)的ranking model对item i的预估点击概率。
• l是由\(y_i\)和\(P(y_i \mid x_i; \theta)\)计算的loss

然而，\(x_i\)对于学习一个好的scoring function来说是不够的。我们发现：对推荐系统来说ranking需要考虑以下额外信息：

• a) 在item pairs间的相互影响（mutual influence）
• b) users和items间的交叉（interaction）

对于请求r，在item pairs间的相互影响，可以通过由给定的已经存在的LTR model中，直接从intial list \(S_r = [i_1, i_2, \cdots, i_n]\)中直接学到。【1，37，2，3】提出了更好的方法使用item-pairs间的互信息（mutual information）。然而，少量工作则会考虑在users和items间的交叉。在本paper中，我们引入一个个性化matrix PV来学习user-specific encoding function，它可以建模在item-pairs间的个性化相互影响。该模型的loss function可以公式化为等式2.

\[L = \sum\limits_{r \in R} l (\lbrace y_i, P(y_i | X, PV; \hat{\theta}) | i \in S_r \rbrace)\]

…(2)

其中：

• \(S_r\)：是在给定前面的ranking model时的intial list
• \(\hat{\theta}\)：是我们的re-ranking model的参数
• X：是在list中所有items的fearture matrix

4.个性化reranking model

在本节中，我们首先给定：我们提出的个性化reranking Model(PRM)的一个总览。接着，我们引入：我们模型的每个组件。

4.1 模型结构

PRM的结构如图1所示。模型包含了三个部分：

• input layer
• encoding layer
• output layer

它会将由前面ranking模型生成的关于items的initial list作为input，并输出一个rerank后的list。

图1 PRM（个性化reranking model）的详细网络结构以及它的子模块

4.2 Input layer

input layer的目标是：为在intial list中所有items准备综合representations，并将它feed到encoding layer。首先，我们有：

• 一个固定长度的intial sequential list \(S=[i_1, i_2, \cdots, i_n]\)，它由之前的ranking方法给出。
• 有一个raw feature matrix \(X \in R^{n \times d_{feature}}\)，与之前的ranking方法相同。X中的每一行表示对于每个item \(i \in S\)的raw feature vector \(x_i\)

个性化向量（Personalized Vector（PV））

两个items的feature vectors的encoding可以建模两者间的相互影响，但这种influences对于用户来说影响有多深是未知的。需要学习一个user-specific encoding function。尽管整个initial list的representation可以部分影响用户的偏好，但对于一个强大的personalized encoding function来说是不够的。如图1(b)所示，我们：

将raw feature matrix \(X \in R^{n \times d_{feature}}\)与一个个性化矩阵\(PV \in R^{d \times d_{pv}}\)进行concat，以便获得intermediate embedding矩阵\(E' \in R^{n \times (d_{feature} + d_{pv})}\)，如等式（3）所示。PV通过一个预训练模型生成，它会在以下章节中介绍。PV的效果增益会在evaluation部分介绍。

\[E' = \left[\begin{array} x_{i_1}; pv_{i_1} \\ x_{i_2}; pv_{i_2} \\ \cdots \\ x_{i_n}; pv_{i_n} \end{array} \right]\]

…(3)

Position Embedding(PE)

为了利用在initial list中的顺序信息，我们会注入一个position embedding： \(PE \in R^{n \times (d_{feature} + d_{pv}})\)到input embedding中。接着，使用等式(4)计算encoding layer的embedding matrix。在本paper中，一个可学习的PE会被使用，我们发现它的效果要比【24】中使用的固定的position embedding效果稍好些。

\[E'' = \left[ \begin{array} x_{i_1}; pv_{i_1} \\ x_{i_2}; pv_{i_2} \\ \cdots \\ x_{i_n}; pv_{i_n} \end{array} \right] + \left[\begin{array} pe_{i_1} \\ pe_{i_2} \\ \cdots \\ pe_{i_n} \end{array} \right]\]

…(4)

最后，我们会使用一个简单的feed-forward network来将feature matrix \(E'' \in R^{n \times (d_{feature} + d_{pv})}\)转换成\(E \in R^{n \times d}\)，其中d是encoding layer的每个input vector的隐维度（latent dimensionality）。E可以公式化为等式5。

\[E = EW^E + b^E\]

…(5)

其中:

• \(W^E \in R^{(d_{feature} + d_{pv}) \times d}\)是投影矩阵
• \(b^E\)是d维向量

4.3 Encoding Layer

图1(a)中的encoding layer的目标是：将item-pairs的相互影响与其它额外信息进行集成，包括：用户偏好、initial list S的ranking顺序等。为了达到该目标，我们采用Transformer-like encoder，因为Transformer已经被证明在许多NLP任务中很有效，特别的是在机器翻译中具有强大的encoding和decoding能力。Transformer中的self-attention机制非常适合在我们的re-ranking任务中，因为它会直接建模任意两个items间的相互影响，并且忽略它们间的实际距离。没有了距离衰减（distance decay），Transformer可以捕获那些在initial list中相互相隔较远的items间的更多交互。如图1(b)所示，我们的encoding module包含了Transformer encoder的\(N_x\)个块。每个块（图1(a)）包含了一个attention layer和一个Feed-Froward Network（FFN） layer。

Attention Layer

attention function如等式（6）所示：

\[Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d}}) V\]

…（6）

其中，矩阵Q, K, V分别表示queries、keys和values。d是矩阵K的维度，为了避免inner product 的大值。softmax被用来将inner product 的值转化成value vector V的adding weight。在本paper中，我们使用self-attention，其中：Q, K, V来自相同的矩阵进行投影。

为了建模复杂的mutual influences，我们使用multi-head attention，如等式7所示：

\[S' = MH(E) = Concat(head_1, \cdots, head_h) W^0 \\ head_i = Attention(EW^Q, EW^K, EW^V)\]

…(7)

其中：

• \(W^Q, W^K, W^V \in R^{d \times d}\)。\(W^O \in R^{hd \times d_{model}}\)是投影矩阵。h是headers的数目。h的不同值的影响，会在下部分进行研究

Feed-Forward Network

该position-wise FFN主要是使用非线性和在input vectors的不同维度间的交叉来增强模型

对Encoding Layer进行Stacking

在position-wise FFN后，这里我们接着使用attention module作为Transformer encoder的一个block。通过将多个blocks进行stacking，我们可以获得更复杂和高阶的mutual information

4.4 Output Layer

output layer的function主要目的是，为在图1(b)中的每个item \(i=i_1, \cdots, i_n\)生成一个score（标记为Score(i)）。我们会使用一个linear layer，后接一个softmax layer来实现。softmax layer的输出为：每个item的点击概率，它被标记为\(P(y_i \mid X, PV; \hat{\theta})\)。我们使用\(P(y_i \mid X, PV; \hat{\theta})\)作为Score(i)来对items在one-step中进行rerank。Score(i)公式为：

\[Score(i) = P(y_i \mid X, PV; \hat{\theta}) = softmax(F^{N_x} W^F + b^F), b \in S_r\]

…(8)

其中：

• \(F^{(N_x)}\)是Transformer encoder的\(N_x\)块（blocks）的output。
• \(W^F\)是可学习的投影矩阵
• \(b^F\)是bias项
• n：在initial list中的items数目

在训练过程中，我们会使用click through数据作为label，并最小化以下的loss function：

\[L = - \sum\limits_{r \in R} \sum\limits_{i \in S_r} y_i log(p(y_i | X, PV; \hat{\theta}))\]

…(9)

4.5 Personalized Module

在本节中，我们会介绍该方法来计算个性化矩阵（personlized matrix: PV），它表示user与items间的交互。直接方法是：使用PRM model以end-to-end的方式通过reranking loss来学习PV。然而，如第3节所示，reranking task任务是：对之前的ranking方法的output进行refine。在reranking task上学到的task-specific representation会缺乏用户的泛化偏好（generic perferences）。因此，我们会利用一个pre-trained neural network来生产用户的personalized embeddings PV，它接着会被用于PRM model中的额外features。预训练的neural network从平台的整体click-through logs学习到。图1(c)展示了在我们paper中使用的per-trained model的结构。sigmoid layer会输出user u在item i在给定用户所有行为历史\(H_u\)以及用户的side information下的点击概率\((P(y_i \mid H_u, u; \theta'))\)。用户的side information包括：gender、age、purchasing level等。该model的loss通过一个point-wise cross entropy function来计算，如等式（4）所示：

\[L = \sum\limits_{i \in D} (y_i log (P(y_i | H_u, u; \theta'))) + (1 - y_i) log(1 - P(y_i | H_u, u; \theta'))\]

…(10)

其中:

• D是user u在该平台上展示的items集合。
• \(\theta'\)：是pre-trained model的参数矩阵
• \(y_i\)是在item i上的label（点 or 不点）

受[13]的启发，我们在sigmoid layer之前采用hidden vector作为personalized vector \(pv_i\)（图1(c)）feed给我们的PRM model。

图1(c)展示了pre-trained model的一个可能架构，其它模型(如：FM、DeepFM、DCN等)也可以作为选择用于生成PV。

5.实验

5.3 Evaluation Metrics

对于离线评估，我们使用Precision和MAP来对比不同的方法。更特别的，我们使用:

• Precision@5，Precision@10作为precision
• MAP@5，MAP@10, MAP@30作为MAP

。。。

略

• 1.https://arxiv.org/pdf/1904.06813.pdf

在《Learning a Deep Listwise Context Model for Ranking Refinement》提出了DLCM.

4.DEEP LISTWISE CONTEXT MODE

在该paper中，我们提出了一个DNN模型，它会包含local ranking context到LTR框架中。该模型的整体思想是：使用一个RNN网络为每个query对应的top retrieved documents进行编码，并且基于编码后的local context model来对ranked list进行refine。我们将该模型称为DLCM（Deep Listwise Context Model）。

使用DLCM的document ranking的pipeline包括三个steps。

• 第一个step是：一个初始检索（initial retrieval），它使用标准的LTR算法。在该step中，每个query-document pair(q, d)是可以被转化成一个feature vector \(x_{(q,d)}\)以及一个size=n的ranked list \(R_q^n\)，它会基于一个全局的ranking function f为query q生成。
• 第二个step是：一个编码过程，它使用一个GRU的RNN对top retrieved documents的feature vectors \(X_q^n\)进行编码。RNN会一个接一个地方式从最低位置到最高位置获取documents，并生成一个latent vector \(s_n\)来表示编码后的local context model： \(I(R_q^n, X_q^n)\)。
• 第三个step是：一个re-ranking过程，其中，top documents会使用一个local ranking function \(\phi\)（它基于\(s_n\)以及RNN的hidden outputs \(o\)）来进行rerank。DLCM的整体结构如图1所示。

图1

4.1 Input Document Representations

第3节所示，大多数L2R算法使用一个feature vector来表示每个query-document pair。在我们提出的框架中，DLCM使用相同的feature vectors。我们在模型输出侧不会包括其它额外的features。

直接将原始的feature vectors进行feed到我们的模型中，并不是使用NN的完整能力的最好方法。另一方法，原始features的维度会受限，并使用低维表示会限制neural encoders的表达能力。另一方面，高级feature抽象对于neural models的健壮性来说是有益的，特别是当原始input features有噪声时。受Wide&Deep模型的启发，我们使用一个two-step方法来获得DLCM的高级input表示。我们首先使用一个two-layer feed-forward network来学习原始features的抽象：

\[z_i^{(0)} = x_{(q,d_i)} \\ z_i^{(l)} = elu(W_z^{(l-1)} \cdot z_i^{(l-1)} + b_z^{(l-1)}, l=1, 2)\]

其中：

• \(W_z^{(l)}\)和\(b_z^{(l)}\)是在第l个layer的weight matrix和bias。
• elu是非线性激活函数，当x>=0时，它等于x；否则为 \(e^x - 1\)。我们接着将\(z_i^{(2)}\)与原始的feature vector \(x_{(qq, d_i)}\)进行concatenate来形成一个新的input vector \(x_{(q, d_i)}'\)

假设：\(\alpha\)和\(\beta\)是\(x_{(q,d_i)}\)和\(z_i^{(2)}\)的维度。当\(beta\)等于零时，我们不会进行区分，因为\(x'(q,d_i)\)可以被缩减为\(x_{(q, d_i)}\)。

4.2 编码Listwise Local Context

给定由一个global ranking function f给出的top n个检索结果，以及它们的feature vectors \(X_q^n = \lbrace x_{(q,d_i)} \mid d_i \in R_q^n\rbrace\)，DLCM中的local context model I会使用一个RNN来实现。RNN是一种deep network，在顺序数据建模中常用。一个标准的RNN包括一个输入序列，一个输出序列，以及一个state vector。由于我们会一个接一个地feed input实例（每个实例会使用一个feature vector进行表示），RNN会根据当前input进行更新它的state vector，并在每个step生成一个新的output vector。最终的state vector可以被看成是一个关于所有信息的编码（会feed到该网络中）。

在DLCM中，我们使用GRU的RNN。GRU network是一个由Cho[10]提出的技术，用于解决RNN中的梯度消失问题。它的基本思想是：使用一个update gate和一个reset gate来控制网络的states的更新。正式的，假设\(x_t \in R^{\alpha}\)是在第t个step的input vector，\(\alpha\)是\(x_t\)的维度。output vector（也是在GRU中的activation vector）\(o_t \in R^{\alpha}\)，network state \(s_t \in R^{\alpha}\)会被计算为：

\[o_t = (1-u_t) \odot o_{t-1} + u_t \odot s_t \\ u_t = \sigma(W_u^x \cdot x_t + W_u^s \cdot o_{t-1}) \\ s_t = tanh(W^x \cdot x_t + W^s \cdot (r_t \odot o_{t-1})) \\ r_t = \sigma(W_r^x \cdot x_t + W_r^s \cdot o_{t-1})\]

…(4)

其中：

• \(\odot\)是element-wise product
• \(\sigma(x) = \frac{1}{1+e^{-x}}\)是一个sigmoid function
• \(u_t \in R^{\alpha}\)是update gate
• \(r_t \in R^{\alpha}\)是reset gate
• 所有的weight矩阵\(W^x, W^s, W_u^x, W_u^s, W_r^x, W_r^s \in R^{\alpha \times \alpha}\)是在训练过程中学到的
• encoded context 模型\(I(R_q^n, X_q^n)\)是final network state \(s_n\)

在DLCM中使用GRU的RNN天然满足一个local context model的两个需求。RNN的inputs是一个vectors序列，它可以是从LTR系统中是scalar features。由于RNN会天然地学习将current input与在network state中编码的previous input进行结合，我们不会需要人工定义heuristics来建模local ranking context。同时，RNN的结果使得它能够捕获在encoding process中的位置效果。当我们使用input data一个接一个地输入到network中时，current input会趋向于比之前的inputs具有对当前network state更多的影响。

由于我们会输入排完序的top结果（从最低到最高position），在高位置的documents会对最终network state具有更多的影响。

图一的单向RNN部分，另一个可选方法是，我们也会测试双向RNN。尽管它被认为是在NLP中的高级能力，我们观察到在检索实验中没有提升。这表明，反方向的编码信息没啥用。实际上，如果我们只使用反向方式的uni-directional RNN，DLCM的效果会更差。

4.3 Local context的reranking

DLCM的最后一个step是，，它通过使用一个local ranking function \(\phi\)对documents进行排序来生成一个新的ranked list。当预测一个ranking score时，function \(\phi\)同时会考虑RNN的hidden outputs，以及关于local ranking context的编码后的latent表示：假设：\(o_{n+1-i}\)是document \(d_i \in R_q^n\)的output表示，我们将local ranking function \(\phi\)定义为：

\[\phi(o_{n+1-i, s_n}) = v_{\phi} \cdot ( o_{n+1-i} \cdot tanh(W_{\phi}\cdot s_n + b_{\phi}))\]

…(5)

其中：

• \(W_{\phi} \in R^{\alpha \times k \times \alpha}, b_{\phi} \in R^{\alpha \times k}, V_{\phi} \in R^k\)，
• k是超参数，它控制着hidden units的数目。

我们的local ranking function的定义是，与RNN中广泛使用的attention function相似。在许多机器学习应用中（例如：机器翻译），一个RNN decoder需要对不同steps的input data的不同部分进行attention。例如，我们需要关注一个句子的不同部分，当我们生成一个接一个的翻译时。attention function常被用于计算在input data上的一个attention分布，并生成一个attention vector来指导一个RNN的decode过程。在DLCM中，我们直接使用\(\phi\)的output值来对input文档进行排序。

我们尝试其它设置：比如：将o使用x进行替代，并使用一个3-layer的FFN来实现\(\phi\)，或者一个neural tensor network。然而，它们的效果会更差，或者不明显，因此，我们只汇报了等式5.

4.4 Loss function

为了训练DLCM，我们实现了两个已存在的listwise loss function（ListMLE【36】和SoftRank【34】），也提出了一个新的listwise loss function称为Attention Rank。

ListMLE是一个listwise loss function，它会将LTR公式化成一个最小化likelihood loss的问题。它将ranking看成是一个顺序选择过程，并将概率定义为：从\(\phi_{m}^n=\lbrace d_j \mid j \in [m, n] \rbrace\)选择文档：

\[P(d_i | \pi_m^n) = \frac{e^{S_i}}{\sum_{j=m}^n e^{S_j}}\]

其中：

• \(S_i\)和\(S_j\)是\(d_i\)的\(d_j\)的ranking scores

如果我们从一个ranked list \(R_q^n\)的top开始进行选择，并在每个step后从candidate set中移除选中的document，在给定ranking scores S下，我们具有\(R_q^n\)的概率：

\[P(R_q^n | S) = \prod_{i=1}^n P(d_i | \pi_i^n) = \prod_{i=1}^n \frac{e^{S_i}}{\sum_{j=1}^n e^{S_j}}\]

假设：\(R_q^*\)是对于query q最可能的ranked list，接着ListMLE loss会定义为：在给定S下\(R_q^*\)的log似然的较小者。

SoftRank：

首先在[34]中提出，是一个listwise loss function，它直接最优化关于信息检索（比如：NDCG）的ranking metrics。假设：\(S_i\)和\(S_j\)是document \(d_i\)和\(d_j\)对于query \(q_i\)的ranking scores。SoftRank function假设：文档\(d_i\)的”real” score \(S_i'\)从一个Gaussian分布中抽出，定义为：\(N(S_i, \sigma_s^2)\)，其中，\(\sigma_s\)是一个共享平滑variance。给定该假设，\(d_i\)高于\(d_j\)的概率为：

\[\pi_{ij} = Pr(S_i' - S_j' > 0) = \int_0^{\inf} N(S | S_i - S_j, 2 \sigma_s^2) dS\]

…(8)

其中，\(P_j^{(1)}(r)\)是\(d_j\)的初始rank分布，当\(d_j\)是在ranked list中的唯一文档时，接着\(p_j^{(i)}(r)\)会在添加第i个文档后被计算：

\[p_j^{(i)}(r) = p_j^{(i-1)}(r-1) \pi_{ij} + p_j^{(i-1)}(r)(1 - \pi_{ij})\]

其中，有了最终的rank分布\(p_j^{(n)}(r)\)以及所有n个documents的label，我们可以计算在每个rank上的期望相关值，并定义一个loss function作为一个期望metric score的减法。

在本paper中，我们使用NDCG作为SoftRank的objective metric。在SoftRank中的唯一超参数是共享的smoothing variance \(\sigma_s\)。我们尝试0.1, 1.0，并观察对应的效果没有变化。这里我们统一使用0.1.

Attention Rank

受attention-based NN的影响，我们提出了一个Attention Rank loss function，它会对一个ranked list的评估公式化为一个attention分配过程。假设：在文档中包含的信息是相互排斥的，一个ranked list的总信息增益是每个文档的增益的累积。如果我们进一步假设：

一个文档的相关评估得分，直接受它的信息增益的影响，最好的策略是：在有限时间内，通过分配更多attention给最好的结果、更低的attention给fair结果、以及不给不相关的结果分配attention，来最大化它的总信息增益。Attention Rank的思想是：使用我们模型的ranking scores来计算一个attention分布，并使用attention策略（通过相关评估计算）来计算它。假设：relevance label \(y_{(q,d_i)}\)表示对于query q的文档\(d_i\)的信息增益。在一个ranked list \(R_q^n\)上的最好的attention分配策略定义如下：

\[a_i^y = \frac{\phi(y(q,d_i))}{\sum\limits_{d_k \in R_q^n} \phi(y(q, d_k))}\]

其中：

• \(\phi(x)\)是一个修正的指数函数，当x>0时为\(e^x\)，否则为0.

相似的，我们会计算我们的模型\(a_i^S\)的attention分布，它使用ranking score \(S_i\)，并使用cross entropy来计算attention策略与最好的attention策略间的loss：

\[l(R_q^n) = - \sum\limits_{d_i \in R_q^n} (a_i^y log(a_i^S) + (1-a_i^y)log(1-a_i^S))\]

…(11)

Attention Rank不会直接预测文档的relevance labels，但会关注在ranked list中的每个结果的relative importance。因为，一个在不相关结果中的list中的fair document，会比在好结果中的list中的一个好文档会接受更多的attention。由于它会基于ranked lists来计算ranking loss，Attention Rank是一个listwise function，它不是一个 pointwise function。Attention Rank的主要优化是：它的简单和高效。通过使用修正的指数函数\(\phi(x)\)，我们可以显式分配更多的精力来最优化在训练过程中的高相关结果。使用Attention Rank的DLCM的训练，要比使用ListMLE和SoftRank的更快2倍和20倍。因而，它可以直接被用于无偏的LTR框架中。

• 1.https://dl.acm.org/doi/pdf/10.1145/3209978.3209985

阿里在《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%，。。。

略

参考

• 1.https://ojs.aaai.org/index.php/AAAI/article/view/5931

摘要

隐式反馈（比如：用户点击）尽管在在线信息服务中非常丰富，但在用户评估系统输出方面并没有提供实质帮助。如果没有合理地进行建模，会误导模型估计，特别是在bandit learning setting中（feedback会即时获取）。在本工作中，我们会执行使用implicit feedback的contextual bandit learning，它会建模feedback作为用户结果查看（result examination）、以及相关评估（relavance evaluation）的一部分。由于用户的查看行为是观察不到的，我们会引入隐变量（latent variables）来建模它。我们会在变分贝叶斯推断（variational Bayesian inference）之上执行Thompson sampling来进行arm selection以及模型更新。我们算法的upper regert bound analysis表明了在一个bandit setting中从implicit feedback中学习的可行性。

1.介绍

contextual bandit算法为现代信息服务系统提供了一种有效解决方案，可以自适应地发现items和users间的良好匹配。这类算法会使用关于user和item的side information顺序选择items提供服务给用户，并能基于用户立即反馈（immediate user feedback）来调节选择策略（selection policy），从而最大化用户的long-term满意度。他们被广泛部署在实际系统中：内容推荐【20，5，26】和展示广告【6，22】。

然而，user feedback的最多形式是implicit feedback（比如：clicks），而它是有偏的，并且对于系统输出的用户评估是不完整的。例如：一个用户跳过一个推荐item，并不因为是他不喜欢该item，有可能是因为他没有查看（examine）那个展示位置（例如：position bias）。不幸的是，在contextual bandit应用中一个常见惯例是：简单地将未点击（no click）看成是负反馈（negative feedback）的一种形式。这会对模型更新引入不一致性（inconsistency），由于跳过的items并非真正不相关，因而它不可避免地会导致随时间的bandit算法的次优结果。

在本工作中，我们会关注使用user click feedback来学习contextual bandits、并建模这样的implicit feedback，作为用户结果查看（result examination）和相关度评估（relevance judgment）的一个部分。 查看假设(Examination hypothesis)【8】在点击建模型上是一个基础假设，会假设：在一个系统上的一个用户点击的返回结果，当且仅当结果被用户查看（examination）时，它与在该时刻的用户信息是相关的。由于一个用户的查看行为是不可观测的（unobserved），我们会建模它作为一个隐变量，并在一个概率模型中实现该查看假设。我们会通过在相应的contextual features上的logistic functions中定义结果查看（result examination）和相关评判（relevance judgement）的条件概率。为了执行模型更新，我们会采用一个变分贝叶斯方法来开发一个闭式（closed form）近似即时模型参数的后验分布。 该近似也会为在bandit learning中使用Thompson sampling策略进行arm selection来铺路。我们的有限时间分析表明，尽管在参数估计中由于引入隐式变量增加了复杂度，我们的Thompson sampling policy会基于真实后验 ，从而保证能达到一个具有高概率的sub-linear Bayesian regert。我们也会演示，基于近似后验的Thompson sampling的regret是良性有界的（well-bounded）. 另外，我们会证明：当某人在点击反馈中建模结果查看（result examination）失败时，一个线性递增的regret是可能的，因为在负反馈中模型不能区分查看驱动的跳过（examination driven skips）还是不相关驱动的跳过（relevance driven skips）。

我们会在中国的MOOC个性化教育平台上测试该算法。为了在该平台上个性化学生的学习体验，当学生正观察视频时，我们会在课程视频顶部以banner的形式推荐类似测试的问题（quiz-like quenstions）。该算法需要决定，在一个视频中在哪里向一个特定用户展示哪个问题。如果学生觉得展示的问题对他理解课程有用，他可能会点击该banner并阅读问题以及更多关于该问题的在线内容。因此，我们的目标是在选中问题上最大化CTR。该应用有多个特性，会放大bias以及点击反馈的不完整性。

• 首先，基于用户体验的考虑，为了最小化讨厌度，一个banner的展示时间会限定在几秒内。
• 第二，由于该feature对于该平台来说是新引入的，许多用户可能不会意识到：他们会在该问题上点击，并且阅读更多相关内容。

作为结果，在一个问题上没有点击，并不能表示不相关。我们会在4个月周期内测试该算法，其中：总共有69个问题会用到该算法上来选择超过20个主要的视频，超过10w的学习观看session。基于无偏离线评估策略，对比起标准的contextual bandits，我们的算法会达到一个8.9%的CTR提升，它不会建模用户的查看行为（examination behavior）。

2.相关工作

略

3.问题设定

我们考虑一个contextual bandit问题，它具有有限但可能较大的arms。我们将：

• arm set：表示为A
• candidate arms子集：在每个trial t=1, …, T上，learner会观察到candidate arms的子集\(A_t \subset A\)，其中，每个arm a与一个context vector \(x^a\)有关，会对arm的side information进行归纳。
• 一旦arm \(a_t \in A_t\)根据一些policy \(\pi\)被选中后，对应的隐式二元反馈\(C_{a_t}\) （例如：user click），会由learner给出作为reward。

learner的目标是：判断它的arm selection策略来最大化它随时间的累积收益（cumulative reward）。使得该问题唯一和挑战的是：\(C_{a_t}\)不会真正影响用户关于选中arm \(a_t\)的评估。基于查看假设【13，8】:

• 当\(C_{a_t}=1\)时，选中的\(a_t\)必须与用户在time t需要的信息相关；
• 但当\(C_{a_t}=0\)时，\(a_t\)必须相关，但用户不会查看它

不幸的是，产生的查看条件对learner来说是不可观察的。

我们会通过一个二元隐变量\(E_{a_t}\)来建模一个用户的结果查看（result examination），并假设：arm a的context vector \(x_t^a\)可以被分解成：

\[(x_{C,t}^a, x_{E,t}^a)\]

• 其中：\(x_{C,t}^a\)和\(x_{E,t}^a\)分别是\(d_C\)和\(d_E\)。

相应的，用户的结果查看和相关判断决策被假设成：通过一个\((x_{C,t}^a, x_{E,t}^a)\)猜想、以及相应的bandit参数为\(\theta^* = (\theta_C^*, \theta_E^*)\)来进行管理。在本文其余部分，当没有二义性引入时，我们会drop掉index a以简化概念。作为结果，我们对在arm \(a_t\)的一个observed click \(C_t\)上做出以下的生成假设：

\[\begin{align} P(C_t = 1 | E_t = 0, x_{C,t}) & = 0 \\ P(C_t = 1 | E_t = 1, x_{C,t}) & = \rho(x_{C,t}^T \theta_C^*) \\ P(E_t = 1 | x_{E,t}) & = \rho(x_{E,t}^T \theta_E^*) \end{align}\]

其中：

• \[\rho(x) = \frac{1}{1 + e^{-x}}\]

基于该假设，我们有：

\[E[C_t \mid x_t] = \rho(x_{C,t}^T \theta_C^*) \rho(x_{E,t}^T \theta_E^*)\]

作为结果，观察到的click feedback \(C_t\)是来自该生成过程的一个样本。我们定义\(f_{\theta}(x) := E[C \mid x, \theta] = \rho(x_C^T \theta_C) \rho(x_E^T \theta_E)\)。到达time T一个policy \(\pi\)的accumulated regret的定义如下：

\[Regret(T, \pi, \theta^*) = \sum\limits_{t=1}^T \underset{\alpha \in A_t}{max} \ f_{\theta^*} (x^a) - f_{\theta^*}(x^{a_t})\]

其中：

• \(x^{a_t} := (x_C^{a_t}, x_E^{a_t})\)是arm \(a_t \in A_t\)的context vector，该arm会在time t时基于历史 \(H_t := \lbrace (A_i, x_i, C_i) \rbrace_{i=1}^{t-1}\)由policy \(\pi\) 中。

Bayesian regret的定义为\(E[Regret(T, \pi, \theta^*)]\)，其中采用的期望根据在\(\theta^*\)上的先验分布采用的，它可以被写成：

\[BayesRegret(T, \pi) = \sum\limits_{t=1}^T E[\underset{a \in A_t}{max} f_{\theta^*}(x^a) - f_{\theta^*}(x^{a_t})]\]

在我们的在线学习环境中，我们的目标是：发现policy \(\pi\)，并最小化在T上的accumulated regret。

4.算法

learner需要基于从click feedback \(\lbrace x_i, C_i \rbrace_{i=1}^t\)获得的随时间的互交，估计bandit参数 \(\theta_C^*\)和\(\theta_E^*\)。理想情况下，该估计可以根据bandit model参数通过最大化data likelihood来获得。然而，在我们的bandit learning setting中查看（examination）的加入作为一个隐变量，对于参数估计和arm selection来说会造成严重挑战。由于相应最优化问题的非凸性，传统的最小二乘估计、极大似然估计可以被轻易获取，更不必说计算效率。更糟的是，两个流行的bandit learning范式，UCB principle和Thompson sampling，都需要一个关于bandit参数及不确定性的精准估计。在本节中，我们提出一个有效的新解法来解决这两个挑战，它会利用variational Bayesian inference技术来近似学习即时参数，同时桥接参数估计（parameter estimaiton）和(arm selection policy)设计。

4.1 Variational Bayesian进行参数估计

为了完成在第3节中定义的生成过程，我们进一步假设\(\theta_C\)和\(\theta_E\)分别遵循高斯分布 \(N(\hat{\theta}_C, \sum_C)\)以及\(N(\hat{\theta}_E, \sum_E)\)。当一个新获得的observation \((x_C, x_E, C)\)变得可提供时，我们会对开发一个闭式近似后验感兴趣。通过在log space中使用Bayes’ rule，我们有：

\[\begin{align} log P(\theta_C, \theta_E | x_C, x_E, C) \\ &= log P(C | \theta_C, \theta_E, x_C, x_E) + log P(\theta_C, \theta_E) + log const \\ &= C log \rho(x_C^T \theta_C) \rho(x_E^T \theta_E) + (1 - C) log(1 - \rho(x_C^T \theta_C) \rho(x_E^T \theta_E)) \\ &= - \frac{1}{2} (\theta_C - \hat{\theta}_C)^T \sum_C^{-1} (\theta_C - \hat{\theta}_C) - \frac{1}{2} (\theta_E - \hat{\theta}_E)^T \sum_E^{-1} (\theta_E - \hat{\theta}_E) + log const \end{align}\]

关键思想是：我们会为似然函数开发一个\(\theta_C\)和\(\theta_E\)的二次型（quadratic form）的variational lower bound。由于 \(log \rho(x) - \frac{x}{2}\)的convexity，对应于\(x^2\)，以及logx的Jensen’s不等式，所需形式的一个lower bound是可以达到的。当C=1时，通过等式(16)，我们有：

\[l_{C=1}(x_C, x_E, \theta) := log( \rho(x_C^T \theta_C) \rho(x_E^T \theta_E)) \geq g(x_C^T\theta, \epsilon_C) + g(x_E^T \theta, \epsilon_E)\]

…(1)

其中：

• \(g(x, \epsilon) := \frac{x}{2} - \frac{\epsilon}{2} + log \rho(\epsilon) - \lambda(\epsilon)(x^2 - \epsilon^2), \lambda(\epsilon) = \frac{tanh \frac{epsilon}{2}}{4 \epsilon}, x, \epsilon \in R\)。更特别的是，\(g(x, \epsilon)\)是一个度为2的对应于x的多项式。当C=0时，通过等式（17），我们有：

\[l_{C=0} (x_C, x_E, \theta) := log( 1-\rho(x_C^T \theta_C) \rho(x_E^T \theta_E)) \\ \geq H(q) + qg(-x_C^T \theta, \epsilon) + qg(x_E^T \theta, \epsilon_{E,1}) + (1 - q) g(-x_E^T\theta, \epsilon_{E,2})\]

…(2)

其中，\(H(q) := - qlog q - (1 - q) log(1-q)\)。一旦在quadratic form中的lower bound确定后，我们可以使用一个Gaussian分布来近似我们的target后验，它的均值和covariance matrix由以下等式确定：

\[\begin{align} \sum_{C, post}^{-1} & = \sum_C^{-1} + 2q ^{1-C} \lambda (\epsilon) x_C x_C^T \\ \hat{\theta}_{C, post} & = \sum_{C,post} (\sum_{C}^{-1} \hat{\theta}_C + \frac{1}{2} (-q)^{1-C} x_C) \\ \sum_{E,post}^{-1} & = \sum_{E}^{-1} + 2 \lambda(\epsilon_E) x_E x_E^T \\ \hat{\theta}_{E,post} & = \sum_{E,post} (\sum_E^{-1} \hat{\theta}_E + \frac{1}{2}(2q-1)^{1-C} x_E) \end{align}\]

…(3)(4)(5)(6)

其中，下标“post”表示在高斯分布中的参数，它逼近期望的后验。连续的观测可以被顺序包含到近似后验。还剩一件事件需要决策，例如：变化参数\((\epsilon_C, \epsilon_E, q)\)的选择。一个选这些值的常用准则是，在observations上的似然是最大化的，与【12】相似的选择，我们会选择这些变分参数的闭式更新公式：

\[\epsilon_C = \sqrt{E_{\theta_C} [x_C^T \theta_C]^2} \\ \epsilon_E = \sqrt{E_{\theta_E} [x_E^T \theta_E]^2} \\ q = \frac{exp(g(x_C^T \theta_C, \epsilon_C) + g(x_E^T\theta_E, \epsilon_E) - g(-x_E^T \theta_E, \epsilon_E))}{ 1 + exp(g(x_C^T \theta_C, \epsilon_C) + g(x_E^T \theta_E, \epsilon_E) - g(-x_E^T \theta_E, \epsilon_E))}\]

其中，所有期望都在近似后验下采用。经验上，我们发现，近似后验和变分参数的迭代式更新收敛相当快，以致于它通常只需要少量迭代就可以获得一个满意的局部最大值。

4.2 使用近似lower bound的Thompson sampling

Thompson sampling, 通常称为“概率匹配（probability matching）”，会被广泛用于bandit learning中来平衡exploration和exploitation，并且它展示了极大的经验效率。Thompson sampling需要一个模型参数的分布来采样。在标准的Thompson sampling中，我们需要从模型参数的真实后验中进行采样。但由于logistic regression不会具有一个共轭先验（conjugate prior），在我们的问题中定义的模型不会具有一个准确的后验。我们决定，根据从等式（3）到等式（6）从近似后验中抽样。之后，我们会表明：这是一个非常紧凑的后验近似。一旦\((\bar{\theta}_C, \bar{\theta}_E)\)的采样完成，我们可以选择相应的arm \(a_t \in A_t\)，它会最大化\(\rho(x_C^T \bar{\theta}_C) \rho(x_E^T \bar{\theta}_E\)。我们将生成的bandit算法命名为examination-click bandit，或者E-C bandit，如算法1所示。

算法1 E-C Bandit

5.Regret Analysis

略

6.实验

略

7.结论

• 1.https://keg.cs.tsinghua.edu.cn/jietang/publications/NIPS18-Qi-et-al-Bandit-Learning-with-Implicit-Feedback.pdf