返回介绍

数学基础

统计学习

深度学习

工具

Scala

九、DR [2020](用于检索)

发布于 2023-07-17 23:38:24 字数 29073 浏览 0 评论 0 收藏 0

  1. 推荐系统数十年来在各种商业应用中都取得了巨大的成功。推荐系统的目标是基于用户特征和历史行为从庞大的语料库中检索相关候选item 。在移动互联网时代,来自内容提供商content provider 的候选item 数量、以及活跃用户数量都迅速增长到数千万甚至数亿,这使得设计准确的推荐系统accurate recommendation system 变得更加具有挑战性。算法的可扩展性scalability 和效率efficiency 是现代推荐系统面临的主要挑战。大规模推荐的核心问题之一是准确accurately 、高效地efficiently 检索出最相关的候选item ,最好是在亚线性sub-linear 时间内。

    推荐系统早期的成功技术之一是协同过滤collaborative filtering: CF,它基于相似用户可能更喜欢相似item 的简单想法进行预测。基于item 的协同过滤item-based collaborative filtering: Item-CF 通过考虑itemitem 之间的相似性扩展了这一思想,后来为Amazon 的推荐系统奠定了基础。

    最近,基于向量的推荐vector-based recommendation 算法已经被广泛采用。主要思想是将用户和 item 嵌入到相同的潜在向量空间latent vector space 中,用向量的内积来表示用户和 item 之间的偏好。向量embedding 方法的典型代表有:矩阵分解matrix factorization: MF 、因子分解机factorization machines: FMDeepFMField-aware FM: FFM 等等。

    然而,当item 数量很大时,对所有item 计算内积的计算复杂度是不可行的。因此,当语料库较大时,通常使用最大内积搜索maximum inner product search: MIPS、或者近似最近邻approximate nearest neighbor: ANN 算法来检索item 。高效的 MIPSANN 算法包括基于树tree-based 的算法、局部敏感哈希locality sensitive hashing: LSH 、乘积量化product quantization: PQhierarchical navigable small world graphs: HNSW 等方法。

    尽管在实际应用中取得了成功,但是基于向量的算法有两个主要缺陷:

    • 学习向量representation 和学习良好的 MIPS 结构,二者目标并不完全一致。
    • 用户embeddingitem embedding 内积的形式限制了模型的能力capability

    为了打破这些限制,人们已经提出了基于树tree-based 的模型。这些方法使用树作为索引indices ,并将每个item 映射为树的一个叶节点。模型参数和树结构的学习目标可以很好地对齐aligned ,从而提高准确性accuracy 。然而,树结构本身是很难学习的:叶子level 的可用数据可能很少,并且可能无法提供足够的信号来学习在该 level 上表现良好的树。

    论文 《Deep Retrieval: An End-to-End Learnable Structure Model for Large-Scale Recommendations》 提出了一种端到端的可训练结构模型trainable structure model -- Deep Retrieval: DR

    受到 《Learning k-way d-dimensional discrete codes for compact embedding representations》 的启发,我们提出使用如下图所示的 $ D\times K $ 矩阵来索引indexing 。每个item 由一个或者多个长度为 $ D $ 、取值范围在 $ \{1,2,\cdots,K\} $ 的编码code (或者也称路径path )来索引indexing

    如下图所示为一个宽度为 $ K=100 $ 、深度为 $ D=3 $ 的结构。假设和巧克力相关的一个item 由长度 $ D $ 的向量 [36, 27, 20] (称作code 或者 path )进行编码。该路径表示该item 已经分配了 $ K\times D $ 的 (1,36), (2,27), (3,20) 索引indices 。图中,相同颜色的箭头形成一条路径,不同的路径可以通过在某一层layer共享相同的索引从而彼此相交。

    一共有 $ K^D $ 条可能的路径,并且每条路径可以解释为一族 clusteritem:每条路径可以包含多个item、每个item 也可以属于多条路径。

    如果添加一个虚拟的 root 节点,那么 DR 就成为一棵高度为 $ D $ 的树。和 TDM 不同的是:DR 中每个 level 都有 $ K $ 个节点,父节点可以有多个子节点,父节点之间可以共享子节点,叶子节点不是代表一个 item 而是代表一组 item

    DR 有两个的优点:

    • 在训练中,可以使用 expectation-maximization: EM 类型的算法将 item path 和结构模型structure model的神经网络参数一起学习。因此,整个训练过程是端到端的,可以轻松部署到深度学习平台上。

      结构模型包含 $ D $ 层layer、每层有 $ K $ 个节点。关于结构模型我们在下面重点描述。

    • 就模型能力model capability 方面,多对多multiple-to-multiple 编码方案使得 DR 能够学习用户和 item 之间更复杂的关系。实验表明了学习这种复杂关系的好处。

  2. DR 将所有候选item 编码为离散的潜在空间。这些候选item 的潜在码 latent code 是模型参数,将和其它神经网络参数一起学习从而最大化相同的目标函数。

    在模型学习之后,我们对latent code 进行 beam search ,从而检索最佳候选item 。实验表明,DR 具有亚线性的计算复杂度,并且可以达到和暴力搜索基线brute-force baseline 几乎相同的准确性accuracy

9.1 模型

9.1.1 结构模型

  1. 这里我们详细介绍 DR 中的结构模型structure model

    • 首先,在给定模型参数 $ \theta $ 的情况下,我们构建用户 $ \mathbf{\vec x}_i $ (即用户输入特征向量)选择路径 $ \mathbf{\vec c}_i $ 的概率,并给出训练目标。

      $ \mathbf{\vec c}_i $ 是一个长度为 $ D $ 的向量,每个元素 $ c_{i,d}\in \mathbb K $ 。

    • 然后,我们引入一个多路径机制multi-path mechanism ,使得模型能够捕获item 的多方面属性multi-aspect properties

    • 在推断阶段,我们引入一种 beam search 算法,根据用户 embedding 选择候选路径。

  2. 结构目标函数Structure Objective Function :结构模型structure model 包含 $ D $ 层layer,每层有 $ K $ 个节点。

    • 每层是一个带跳跃连接 skip connectionsoftmax 输出的多层感知机multi-layer perceptron: MLP
    • 每层输入一个 input vector,并基于参数 $ \theta $ 输出在 $ \{1,2,\cdots,K\} $ 上的概率分布。

    令 $ \mathbb V = \{1,2,\cdots,V\} $ 为所有 item 的索引集合, $ \mathbb K=\{1,2\cdots,K\} $ 为单个code 取值集合, 令 $ \pi: \mathbb V \rightarrow \underbrace{\mathbb K\times\cdots\times\mathbb K}_{ D } $ 为 item 到路径的映射。这里我们假设 $ \pi $ 是已知的(即给定item,对应的路径是已知的),并将在后文介绍共同学习 $ \pi $ 和 $ \theta $ 的算法。

    给定一对训练样本 $ \left(\mathbf{\vec x},y\right) $ ,它表示在用户 $ \mathbf{\vec x} $ 和 item $ y $ 之间的一个positive 交互(如点击、转化、喜欢like 等等),以及给定item $ y $ 关联的路径 $ \mathbf{\vec c}=(c_1,c_2,\cdots,c_D) $ ,其中 $ c_d\in \mathbb K $ ,概率 $ p(\mathbf{\vec c}\mid \mathbf{\vec x},\theta) $ 是按照如下方式逐层构建的(如下图(b)所示)。

    • 第一层以用户embedding $ \text{emb}(\mathbf{\vec x}) $ 作为输入,基于参数 $ \theta_1 $ 输出在所有 $ K $ 个节点上的概率分布 $ p(c\mid \mathbf{\vec x},\theta_1), c=1,2,\cdots,K $ 。

      即:已知用户 embedding 的条件下,第一层选择 $ c_1 $ 的概率。

    • 从第二层开始,我们将用户 embedding $ \text{emb}(\mathbf{\vec x}) $ 和所有先前层的 embedding $ \text{emb}(c_{d-1}) $ (称作 path embedding)拼接起来作为 MLP 的输入,并基于参数 $ \theta_d $ 输出 layer d 上 $ K $ 个节点的概率 $ p(c \mid \mathbf{\vec x},c_1,\cdots,c_{d-1},\theta_d),c=1,2,\cdots,K $ 。

      即:已知用户 embedding 、以及前 $ d-1 $ 层选择 $ (c_1,\cdots,c_{d-1}) $ 的条件下,第 $ d $ 层选择 $ c_d $ 的概率。

    • 概率 $ p(\mathbf{\vec c}\mid \mathbf{\vec x},\theta) $ 是所有层的概率的乘积:

      $ p(\mathbf{\vec c}\mid \mathbf{\vec x},\theta) = \prod_{d=1}^D p(c_d\mid \mathbf{\vec x},c_1,\cdots,c_{d-1},\theta_d) $

    给定 $ N $ 个训练样本的集合 $ \left\{(\mathbf{\vec x}_i,y_i)\right\}_{i=1}^N $ ,我们最大化结构模型structure model 的对数似然函数:

    $ \mathcal Q_{\text{str}}(\theta,\pi) = \sum_{i=1}^N \log p(\mathbf{\vec c}_i=\pi(y_i)\mid \mathbf{\vec x}_i,\theta) = \sum_{i=1}^N\sum_{d=1}^D\log p(c_{i,d}\mid \mathbf{\vec x}_i,c_{i,1},\cdots,c_{i,d-1},\theta_d) $

    注意:

    • 这里的目标函数只有positive 交互,而没有 negative 交互。但是通过 softmax 函数可以引入负样本信息。
    • 这里没有使用 item 的特征,仅仅将 item 作为一个 label

    感觉这是一种聚类算法,基于路径来将不同的 item 进行聚类,召回时仅需要召回相应的路径即可。

    layer d 的输入向量的尺寸是 embedding 向量尺寸乘以 $ d $ (因为 $ d $ 个 embedding 向量的拼接),输出向量尺寸是 $ K $ ,因此 layer d 的参数数量为 $ \Theta(Kd) $ 。参数 $ \theta $ 包含所有层的参数 $ \{\theta_d\}_{d=1}^D $ ,以及path embedding 。整个模型中的参数数量大概在 $ \Theta(KD^2) $ 的量级,这明显小于所有可能的路径的数量 $ K^D $ (当 $ D\ge 2 $ 时)。

    这个结构模型和典型的 DNN 推荐模型不同,该模型更偏向于 GNN 图神经网络。

  3. 多路径结构目标Multi-path Structure Objective:在tree-based 深度模型以及我们之前介绍的结构模型structure model 中,每个 item 只属于一个 cluster,这限制了模型在真实数据中表达多方面信息multi-aspect information 的能力。

    例如,一个与烤串kebab 相关的 item 应该属于一个与食物food相关的 cluster。一个和鲜花flower 相关的 item应该属于和礼物gift 有关的 cluster。然而,与巧克力chocolate 或者蛋糕 cake 相关的 item 应该同时属于食物和礼物两个 cluster,以便推荐给对食物或礼物感兴趣的用户。

    在现实世界的推荐系统中,一个 cluster 可能没有明确的含义,比如食物或礼物,但是这个示例促使我们将每个 item 分配给多个 cluster 。在 DR 中,我们允许每个item $ y_i $ 被分配到 $ J $ 个不同的路径 $ \{\mathbf{\vec c}_{i,1},\cdots,\mathbf{\vec c}_{i,J}\} $ 。 令 $ \pi: \mathbb V\rightarrow \underbrace{\mathbb K\times\cdots\times\mathbb K}_{ D\times J } $ 为 itemmultiple paths的映射,则 multiple path 结构目标定义为:

    $ \mathcal Q_{\text{str}}(\theta,\pi) = \sum_{i=1}^N \log \left(\sum_{j=1}^Jp(\mathbf{\vec c}_{i,j}=\pi_j(y_i)\mid \mathbf{\vec x}_i,\theta)\right) $

    这里将多个路径的概率相加,是否取 max 可能更有意义?取 sum 表示用户对单个 item 背后的多个概念偏好的总和,取 max 表示用户对单个 item 背后的多个概念偏好的最大值。

  4. 针对推断的 beam search :在推断阶段,给定用户 embedding 为输入,我们希望从结构模型中检索 item 。为此,我们利用 beam search 算法来检索多个path,并将检索到的path 中的 item 合并。

    • 首先,在第一层挑选 top B 节点。
    • 然后,在前一层所有节点的后续节点successors 中挑选 top B 节点。
    • 最后一层输出最终的 $ B $ 个节点。

    算法如下所示。在每一层中,从 $ K\times B $ 个候选节点中选择 top B 节点的算法复杂度为 $ O(KB\log B) $ 。总的算法复杂度为 $ O(DKB\log B) $ ,它相对于 item 的数量是亚线性 sub-linear 的。

  5. beam search 算法:

    • 输入:

      • 用户特征 $ \mathbf{\vec x} $
      • 参数 $ \theta $ 的结构模型
      • beam size $ B $
    • 输出: $ B $ 条路径的集合 $ \mathbb C_D $ 。

    • 算法步骤:

      • 基于 $ \{p(c_1\mid \mathbf{\vec x},\theta):c_1\in \{1,\cdots,K\}\} $ 中的 top B 项挑选 $ \mathbb C_1=\{c_{1,1},\cdots,c_{1,B}\} $ 。

      • 迭代, $ \text{ for } d= 2,\cdots, D $ :

        基于以下顺序,从 $ \mathbb C_{d-1} $ 集合中节点的所有后继successors 中挑选 top B 项:

        $ \{p(c_1,\cdots,c_{d-1}\mid \mathbf{\vec x},\theta)p(c_d\mid \mathbf{\vec x},c_1,\cdots,c_{d-1},\theta):(c_1,\cdots,c_{d-1})\in \mathbb C_{d-1}, c_d\in \{1,2,\cdots,K\}\} $

        然后得到集合:

        $ \mathbb C_d=\{(c_{1,1},\cdots,c_{d,1}),\cdots,(c_{1,B},\cdots,c_{d,B})\} $

        因为 $ \mathbb C_{d-1} $ 一共 $ B $ 项,每项有 $ K $ 个后继,所以需要从 $ KB $ 项中挑选 top B 项。如果采用最大堆,则算法复杂度为 $ O(KB\times \log B) $ 。

      • 返回 $ \mathbb C_D $ 。

9.1.2 学习

  1. 前面我们介绍了 DR 中的结构模型structure model 和要优化的结构目标structure objective 。目标函数相对于参数是完全连续的,因此可以通过任何基于梯度的优化器进行优化。但是,目标函数涉及从 itempath $ \pi $ 的映射,这是离散的,无法通过基于梯度的优化器来优化。

    这种映射充当item 的 "clustering" ,这促使我们使用 EM 风格的算法来联合优化离散的映射和连续的参数。在本节中,我们将详细描述 EM 算法,并引入惩罚项来防止过拟合。

  2. 针对联合训练的 EM 算法EM Algorithm for Joint Training :给定训练集中的一个 user-itempair 对 $ (\mathbf{\vec x}_i,y_i) $ ,令 item 关联的 path 为 $ \left(\left\{\pi_1(y_i),\cdots,\pi_J(y_i)\right\}\right) $ 为 EM 算法中的潜在数据 latent data 。连同连续参数 $ \theta $ ,目标函数由下式给出:

    $ \mathcal Q_{\text{str}}(\theta,\pi) = \sum_{i=1}^N \log \left(\sum_{j=1}^Jp(\mathbf{\vec c}_{i,j}=\pi_j(y_i)\mid \mathbf{\vec x}_i,\theta)\right)\\ = \sum_{v=1}^V\left(\sum_{i:y_i=v}\log\left(\sum_{j=1}^Jp(\mathbf{\vec c}_{i,j}=\pi_j(v)\mid \mathbf{\vec x}_i,\theta)\right)\right) $

    其中第二个等式是将训练集中 item = v 的所有 item 聚集在一起。

    我们在所有可能的映射 $ \pi $ 上最大化目标函数。然而,存在 $ K^D $ 条可能的 path,因此我们无法在所有的 $ \pi_j(v) $ 上最大化目标函数。相反,我们仅使用 beam search 来记录 top path 的值,而剩下的path 为零分。

    不幸的是,由于上式中存在 $ \log (0) $ ,这使得函数的数值不稳定。为了解决这个问题,我们使用上限 $ \sum_{i=1}^N \log p_i\le N\left(\log \sum_{i=1}^N p_i - \log N\right) $ 来近似目标函数,从而得到:

    $ \mathcal Q_{\text{str}}(\theta,\pi)\le \overline {\mathcal Q}_{\text{str}}(\theta,\pi)= \sum_{v=1}^V\left(N_v \log\left(\sum_{j=1}^J\sum_{i:y_i=v}p(\mathbf{\vec c}_{i,j}=\pi_j(v)\mid \mathbf{\vec x}_i,\theta)\right)-\log N_v\right) $

    其中: $ N_v = \sum_{i=1}^N \mathbb I[i:y_i = v] $ 为 item $ v $ 出现在训练集中的次数,它独立于映射 $ \pi $ 。

    因为 $ \overline {\mathcal Q}_{\text{str}}(\theta,\pi) $ 是我们最大化的真实目标 $ \mathcal Q_{\text{str}}(\theta,\pi) $ 的上限,因此无法保证前者的最大化来得到后者的最大化。但是,在实践中我们发现这种近似的做法表现良好。

    要使得 $ \overline {\mathcal Q}_{\text{str}}(\theta,\pi) $ 最大,则我们需要使得每个 item $ v $ 的项 $ \sum_{j=1}^J\sum_{i:y_i=v}p(\mathbf{\vec c}_{i,j}=\pi_j(v)\mid \mathbf{\vec x}_i,\theta) $ 最大。为简单起见,我们记得分score $ s[v,\mathbf{\vec c}] = \sum_{i:y_i=v}p(\mathbf{\vec c}=\pi(v)\mid \mathbf{\vec x}_i,\theta) $ 。在实践中不可能保留所有的得分,因为路径 $ \mathbf{\vec c} $ 的可能的数量是指数级的,所以我们通过 beam search 来仅仅保留得分最大的 $ S $ 条path 的子集。

    $ s[v,\mathbf{\vec c}] $ 的物理意义为:所有目标 item 为 $ v $ 的、路径为 $ \pi $ 的概率之和。这里有两点注意:

    • 路径为 $ \pi $ 的、目标 item 为 $ v $ 的路径概率之间可能不相等,因为用户特征 $ \mathbf{\vec x}_i $ 可能不同。
    • 同一个用户、目标 item 为 $ v $ 的路径概率之间也可能不等,因为存在 $ J $ 条不同的路径 $ \pi_j $ 。

    M-step,我们简单地在每个 $ \pi_j(v) $ 上最大化 $ \sum_{j=1}^Js[v,\pi_j(v)] $ ,这相当于在来自 beam searchtop path $ \mathbf{\vec c} $ 中挑选 $ J $ 个最高的 $ s[v,\mathbf{\vec c}] $ 分。

  3. 结构学习structure learningEM 算法:

    • 输入:

      • 训练集 $ \left\{\mathbf{\vec x}_i,y_i\right\}_{i=1}^N $
      • 预定义的 epoch 数量 $ T $
    • 输出: $ J $ 条路径 $ \left\{\pi^{(T)}_1(v),\cdots,\pi^{(T)}_J(v)\right\}_{v=1}^V $

    • 算法步骤:

      • 随机初始化 $ \pi_j^{(0)} $ 和 $ \theta $ 。

      • 迭代, $ \text{ for } t=1\cdots T $ :

        • 固定 $ \pi_j^{(t-1)} $ ,使用基于梯度的优化器优化参数 $ \theta $ ,以最大化结构目标函数 structure objective $ \mathcal Q_{\text{str}}\left(\theta,\pi^{(t-1)}\right) $ 。

        • $ \text{ for } v=1\cdots V $ :

          • 针对 beam search 得到的 top path $ \mathbf{\vec c} $ 计算得分 $ s[v,\mathbf{\vec c}] $ 。
          • 令 $ \left\{\pi^{(t)}_1(v),\cdots,\pi^{(t)}_J(v)\right\} $ 为 $ s[v,\mathbf{\vec c}] $ 中的 top $ J $ 个得分。
      • 返回 $ J $ 条路径 $ \left\{\pi^{(T)}_1(v),\cdots,\pi^{(T)}_J(v)\right\}_{v=1}^V $

  4. path size 的惩罚 Penalization on Size of Paths: 如果我们不对上述 EM 算法进行任何惩罚,那么很可能发生过拟合。

    假设结构模型structure model发生过拟合,并且对于任何输入,特定的 path (0,0,0) 都有非常高的概率。那么在 M-step 中,所有的 item 都将分配给路径 (0,0,0) ,使得模型无法对item 进行 cluster

    即单条路径上路径上分配了所有的 item

    为了防止过拟合,我们对 path size 引入了一个罚项。引入惩罚的 $ \mathcal Q $ 函数定义为:

    $ \mathcal Q_{\text{pen}}(\theta,\pi) =\overline {\mathcal Q}_{\text{str}}(\theta,\pi) -\alpha\times \sum_{\mathbf{\vec c}\in \mathbb R^D,\;c_i\in \mathbb K}f(|\mathbf{\vec c}|)\\ = \sum_{v=1}^V\left(N_v \log\left(\sum_{j=1}^Js[v,\pi_j(v)]\right)-\log N_v\right)-\alpha\times \sum_{\mathbf{\vec c}\in \mathbb R^D,\;c_i\in \mathbb K}f(|\mathbf{\vec c}|) $

    其中:

    • $ \alpha \gt 0 $ 为惩罚因子。
    • $ |\mathbf{\vec c}| $ 表示路径 $ \mathbf{\vec c} $ 中的item 数量。
    • $ f(\cdot) $ 为一个递增的凸函数。二次函数 $ f(|\mathbf{\vec c}|) = |\mathbf{\vec c}|^2/2 $ 控制 path 的平均 size 。更高阶的多项式在更大的path 上惩罚更多。在我们的实验中,我们使用 $ f(|\mathbf{\vec c}|) = |\mathbf{\vec c}|^4/4 $ 。

    值得一提的是,罚项仅适用于 M-step,而不适用于训练连续参数 $ \theta $ 。

  5. 针对路径分配的坐标下降算法coordinate descent algorithm for path assignment:在所有路径分配path assignment 上联合优化带惩罚的目标函数 $ \mathcal Q_{\text{pen}}(\theta,\pi) $ 是困难的,因为罚项不能被分解为每个 item 项的求和。所以我们在 M-step 中使用坐标下降coordinate descent 算法。当优化item $ v $ 的路径分配 $ \pi_j(v) $ 时,我们固定所有其它item 的路径分配。

    注意,项 $ -\log N_v $ 和 $ \pi_j(v) $ 无关,因此可以删掉。对每个item $ v $ ,部分的 partial 目标函数可以重写为:

    $ \arg\max_{\{\pi_j(v)\}_{j=1}^J} N_v \log\left(\sum_{j=1}^Js[v,\pi_j(v)]\right) -\alpha\times \sum_{j=1}^Jf(|\pi_j(v)|) $

    因为不同 item 的目标函数之间是相互独立的,因此可以拆分为每个 item 的目标函数最大化。

    坐标下降算法如下,其时间复杂度为 $ O(VJS) $ ,其中 $ S $ 为候选路径的 pool size 。在实践中,35 次迭代足以确保算法收敛。

  6. coordinate descent algorithm for penalized path assignment 算法:

    • 输入:

      • 评分函数 $ \log s[v,\mathbf{\vec c}] $
      • 迭代次数 $ T $
    • 输出:路径分配 $ \left\{\pi_j^{(T)}(v)\right\}_{j=1}^J $

    • 算法步骤:

      • 对所有路径 $ \mathbf{\vec c} $ 初始化 $ |\mathbf{\vec c}| = 0 $ 。

      • 迭代, $ \text { for } t =1,\cdots,T $ :

        对每个item $ v $ 迭代:

        • sum 设置为 0

          sum 存放 $ J $ 条路径的累计评分 $ \sum_{j=1}^Js[v,\pi_j(v)] $ 。

        • 迭代, $ \text{ for } j=1,\cdots,J $ :

          • 如果 $ t\gt 1 $ ,则更新 $ \left|\pi_j^{(t-1)}(v)\right|\leftarrow \left|\pi_j^{(t-1)}(v)\right|-1 $ 。

          • item $ v $ 的所有候选路径 $ \mathbf{\vec c} $ ,且 $ \mathbf{\vec c}\notin \left\{\pi_l^{(t)}(v)\right\}_{l=1}^{j-1} $ ,计算penalized score

            $ \tilde s[v,\mathbf{\vec c}] = \log (s[v,\mathbf{\vec c}]+\text{sum}) -\alpha\times (f(|\mathbf{\vec c}|+1) - f(|\mathbf{\vec c}|)) $
          • 更新:

            $ \pi_j^{(t)}(v)\leftarrow \arg\max_{\mathbf{\vec c}} \tilde s[v,\mathbf{\vec c}]\\ \text{sum}\leftarrow \text{sum}+s\left[v,\pi_j^{(t)}(v)\right]\\ \left|\pi_j^{(t)}(v)\right|\leftarrow \left|\pi_j^{(t)}(v)\right| +1 $
      • 输出 $ \left\{\pi_j^{(T)}(v)\right\}_{j=1}^J $

  7. softmax 模型的多任务学习和排序 Multi-task Learning and Reranking with Softmax Models :基于我们在本文中进行的实验,我们发现联合训练 DRsoftmax 分类模型大大提高了性能。

    softmax 分类模型:给定用户特征 $ \mathbf{\vec x} $ ,用户选择 item $ y $ 的概率为:

    $ p(y\mid \mathbf{\vec x}) = \frac{\exp\left(\mathbf{\vec x}\cdot \mathbf{\vec w}_y\right)}{\sum_{v\in \mathbb V }\exp\left(\mathbf{\vec x}\cdot \mathbf{\vec w}_v\right)} $

    其中 $ \mathbf{\vec w}_v $ 为item $ v $ 的 embedding

    我们推测这是因为:item 的路径在开始时是随机分配assignment 的,导致优化难度增加。通过与容易训练的 softmax 模型共享输入,我们能够在优化方向optimization direction 上提升结构模型structure model。所以我们最大化的最终目标 final objective 是:

    $ \mathcal Q = \mathcal Q_{\text{str}} + \mathcal Q_{\text{softmax}} $

    这里是用两路并行模型,将它们的损失函数按照 1:1 相加。一路模型是 DR 模型、另一路模型是简单的 softmax 输出的 DNN 模型,它们共享用户特征 $ \mathbf{\vec x} $ 。

    在使用beam search 算法执行 beam search 以检索一组候选 item 之后,我们使用 softmax 模型(即 $ \mathbf{\vec x}\cdot \mathbf{\vec w}_v $ )来重新排列这些候选item,从而获得最终的 top 候选item

    这种多任务的方式是否表明 DR 模型还不够完善,需要依赖于传统的 DNN 模型。那么 DR 模型的价值体现在哪里?实验部分也没有给出明确的回答。

  8. 算法复杂度分析:我们将DR 中每个阶段的时间复杂度总结如下。

    • 推断阶段的时间复杂度是每个样本 $ O(DKB\log B) $ 的复杂度,相对于 item 数量而言是亚线性 sub-linear 的。
    • 训练连续参数 $ \theta $ 的时间复杂度是 $ O(NJKD^2) $ ,其中 $ N $ 是一个 epoch 中训练样本的数量, $ J $ 是路径的多重性multiplicity
    • 通过坐标下降算法进行路径分配的时间复杂度为 $ O(VJS) $ ,其中 $ V $ 是语料库大小, $ S $ 为候选pathpool size
  9. 未来研究方向:

    • 首先,结构模型仅基于用户侧信息定义路径上的概率分布。一个有用的想法是如何将item 侧信息更直接地整合到 DR 模型中。
    • 其次,我们仅利用 user-item 之间的 positive 互动(如点击、转化、喜欢like)。在将来的工作中,也应该考虑诸如 non-clickdislike 、取消关注unfollow 之类的 negative互动,从而改善模型性能。
    • 最后,当前的 DR 仍然使用 softmax 模型作为 reranker,这可能受到softmax 模型的性能限制。我们也在积极努力解决这个问题。
  10. 人们普遍认为:推荐系统不仅反映了用户的偏好,而且随着时间的推移,它们往往会重塑 reshape 用户的偏好(即,影响用户)。由于系统中的连续反馈回路continuous feedback loop,这可能导致用户决策或用户行为的潜在bias 。我们提出的方法更多地是从改进核心机器学习技术的角度出发,基于用户历史行为数据更好地检索出最相关的候选 item。我们的方法是否放大、还是减缓了实际推荐系统中的现有 bias,这还需要进一步研究。

  11. 读者注:DR 算法本质上和 TDM 算法是相同的。

    • DR 训练算法是最大化路径的概率,如果用负采样来代替 softmax,则它就和 TDM 思想一致。

      不同点:TDM 模型使用 attention 等复杂结构,而 DR 模型仅用简单的 softmaxTDM 的负样本是每个 level 中所有正样本共享的,而 DR 的负样本是每个正样本独立采样的。

    • DR 预测算法是对每一层进行 beam search,这和 TDM 思想一致。

      不同点:二者的 score 不同。TDM 采用当前层每个节点的当前选中概率,DR 使用当前层每个节点的累积选中概率。

    • DR 结构学习算法和 TDM 不同。TDM 采用迭代来优化树结构,而 DR 采用 EM 算法来优化树结构。

    • DR 采用多任务来共同学习用户 representation

9.2 实验

  1. 这里我们研究了DR 在两个公共推荐数据集上的性能:MovieLens-20MAmazon books

    我们将 DR 算法和暴力搜索brute-force算法、以及其它一些推荐 baseline 算法(包括 tree-based 算法 TDMJTM )。

    最后,我们研究了重要的超参数在 DR 中的作用。

  2. 数据集:

    • MovieLens-20M:该数据集包含来自一个叫做 MovieLens 的电影推荐服务中的评分rating 和自由文本标记free-text tagging 活动。

      我们使用 1995 年到 2015 年之间 138493 名用户的行为创建的 20M 子集。每个user-movie 交互都包含一个 user-id、一个 movie-id、一个1.0~5.0 之间的评级、以及一个时间戳。

      为了公平地进行比较,我们严格遵循和 TDM 相同的数据预处理过程。我们仅保留评级大于等于 4.0 的记录、仅保留至少十条评论的用户。经过预处理之后,数据集包含 129797 名用户、20709 部电影、以及 9939873 条交互记录。

      然后我们随机抽取 1000 个用户和相应的交互记录来构造验证集,另外随机抽取 1000 个用户和相应的交互记录来构造测试集,剩余用户及其交互记录作为训练集。对于每个用户,根据时间戳将前半部分评级作为历史行为特征,后半部分评级作为待预测的 ground truth

    • Amazon books:该数据集包含用户对 Amazonbooks 的评论,其中每个 user-book 交互都包含一个 user-id、一个 item-id、以及相应的时间戳。

      类似于 MovieLens-20M,我们遵循和 JTM 相同的预处理过程。数据集包含 294739 名用户、1477922item、以及 8654619 条交互记录。注意,和 Movielens-20M 相比,Amazon books 数据集具有更多的 item,但是交互更少。

      我们随机抽取 5000 名用户及其相应的交互记录作为测试集,另外随机抽取 5000 名用户及其相应的交互记录作为验证集,剩余用户及其相应的交互记录作为训练集。对于每个用户,根据时间戳将前半部分评级作为历史行为特征,后半部分评级作为待预测的 ground truth

  3. 评估指标:我们使用 precision, recall, F-measure 作为指标来评估每个算法的性能。

    我们强调,这些指标是为每个用户分别计算的,并按照 TDMJTM 相同的设置,在没有用户权重的情况下对所有用户进行平均。

    我们通过检索 MovieLens-20M 数据集中每个用户的 top 10item 来计算指标、通过检索 Amazon books 数据集中每个用户的 top 200item 来计算指标。

  4. 训练配置:这里我们提供一些关于实验中的模型和训练过程的一些细节。

    • 由于数据集是以这样的方式进行拆分的:即训练集、验证集、测试集中的用户是不相交的,所以我们删除 user-id,仅使用行为序列作为 DR 的输入。

      如果行为序列长于 69,则将其长度截断为 69;如果行为序列长度短于 69,则将其长度用占位符填充到69

    • 我们使用一个GRU 的递归神经网络,来将行为序列映射到一个固定维度的 embedding 上,从而作为 DR 的输入。

    • 我们采用多任务学习框架multi-task learning framework,并且通过 softmax reranker 对召回路径中的 item 进行 rerank

    • 我们在前两个epoch 共同训练 DRsoftmaxembedding ,然后在接下来的两个epoch 中冻结 softmaxembedding 并训练 DRembedding。原因是为了防止 softmax 模型的过拟合。

    • 在推断阶段,由于 path size 的差异,beam search 检索到的 item 数量并不固定,但是方差并不太大。根据经验,我们控制 beam size,使得 beam searchitem 数量是最终检索item 数量的 5 ~ 10 倍。

  5. 实验结果:我们将 DR 的性能和以下算法进行比较:Item-CFYouTube product DNNTDMJTM

    我们直接使用来自 TDMJTM 论文的 Item-CFYouTube product DNNTDMJTM 结果进行公平地比较。在不同的 TDM 变体中,我们选择了性能最佳的一种来比较。JTM 的结果仅适用于 Amazon books

    我们还将 DR 和暴力brute-force 检索算法进行了比较,后者直接计算用户 embedding 和所有 item embedding 之间的内积(这些 embedding 都是从 softmax 模型学到),从而返回 top K item 。在实际的大型推荐系统中,暴力算法通常在计算上是不可行的,但是在小型数据集上可以作为基于内积模型的上限。

    下表分别给出了 MovieLens-20MAmazon books 数据集上 DR 方法和其它方法的比较结果。对于 DR 和暴力方法,我们独立地训练同一个模型5 次,并计算每个指标的均值和标准差。可以看到:

    • DR 相比包括tree-based 的检索算法(如 TDMJTM)在内的所有其它方法表现更好。
    • DR 的性能相比暴力法的性能非常接近或者不相上下。

  6. 参数敏感性:DR 引入了一些可能显著影响性能的关键超参数,包括结构模型structure model 的宽度 $ K $ 、多路径multiple path 数量 $ J $ 、beam size $ B $ 、以及惩罚因子 $ \alpha $ 。

    MovieLens-20M 的实验中,我们选择 $ K=50, B=25,J=3,\alpha=3\times 10^{-5} $ ;在 Amazon books 的实验中,我们选择 $ K=100, B=50, J=3,\alpha=3\times 10^{-7} $ 。

    我们在 Amazon books 数据集研究了这些超参数的使用,并观察它们如何影响性能。我们在下图中展示了当这些超参数变化时,recall@200 指标是如何变化的(我们以recall@200 为例, precision@200F-measure@200 也遵循类似的趋势)。当改变一个超参数时,我们不改变其它超参数的值。

    • 模型宽度 $ K $ : $ K $ 控制了结构模型的整体容量。

      • 如果 $ K $ 太小,那么对于所有 item 而言,cluster 的数量太小。
      • 如果 $ K $ 太大,那么训练和推断的时间复杂度随着 $ K $ 线性增加。而且 $ K $ 太大可能会增加过拟合的可能性。

      应该根据语料库的大小选择合适的 $ K $ 。

    • 路径数量 $ J $ : $ J $ 使模型能够表达 item 的多方面信息multi-aspect information

      $ J=1 $ 时性能最差,并随着 $ J $ 的增加而不断增加。较大的 $ J $ 可能不会影响性能,但是训练的时间复杂度随着 $ J $ 的增加而线性增加。实际上建议选择 $ J $ 在 35 之间。

    • beam size $ B $ : $ B $ 控制召回的候选路径的数量。

      较大的 $ B $ 导致更好的性能,但是也会带来推断阶段更大的计算量。

    • 惩罚因子 $ \alpha $ : $ \alpha $ 控制每个路径中的 item 数量。

      当 $ \alpha $ 值落在一定范围内时,性能最佳。较小的 $ \alpha $ 导致较大的 path size(如下表所示为包含最多itempath(称作 top path)的 path size 和惩罚因子的关系),因此在 reranking 阶段计算量较大。beam size $ B $ 和惩罚因子 $ \alpha $ 应该适当选择,从而在模型性能和推断速度之间进行权衡 trade-off

    总体而言,我们可以看到 DR 对于超参数是相当稳定的,因为超参数的范围很广wide range ,这导致了接近最优near-optimal 的性能。

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文