推荐算法实战五-召回（下）

一、FM的召回功能

（一）打压热门物料

FM主要应用于U2I召回场景，正样本采用与用户正向交互过的样本。负样本来源于两个途径，一个是随机采样，一个是曝光但未点击的负向物料。由于热门物料曝光率高，因此正负样本中热门物料参与度都不小，为了确保推荐结果的多样性，对正负样本分别采取不同的热门物料打压策略。

1、热门物料在正样本中要降采样

降低热门物料被选为正样本的概率，曝光率越高，选为正样本的概率就越低。定义一个物料t_i能被任何用户选为正样本的概率P_post(t_i)为：

α是一个超参数，可以认为是冷门物料的门槛，当f(t_i)<=α并且被用户点击过，那么可以认定为正样本。

2、热门物料在负样本中要过采样

负样本采样需要满足以下两个要求：需要尽可能广泛地采样负样本，覆盖尽可能多的物料样本；采集一些热门物料来抵消少数热门物料垄断正样本的情况。负采样概率如下所示：

其中V是所有物料的集合。当超参数b为1的时候，对热门物料的打压力度最大；当超参数b为0的时候，则是uniform sampling，任何物料选为负样本的概率都一样大。

（二）增广Embedding

拆解得到用户特征和物料特征后，用FM表示用户u和物料t的匹配程度如下式所示：

W_t是一阶物料特征权重之和，W_u是一阶用户特征权重之和，V_uu是用户特征集内部两两交叉，V_tt是物料特征集内部两两交叉，V_ut是用户特征和物料特征的两两交叉。

由于b、W_u、V_uu对于不同物料都是相同的，因此可以省略这三项，后面变成向量内积的形式求解：

E_u是在在线召回时实时计算得到的用户向量。E_t是物料向量，离线计算好存入faiss建立索引。面对新用户V_ut提供的信息有限，主要依赖W_t和V_tt。训练的时候没必要将用户向量和物料向量拆开，只在预测时使用上式。

FM召回的主力函数如下所示：

二、大厂主力：双塔模型

（一）不同场景下的正样本

1、I2I

同一个用户在同一个会话中交互过的两个物料可以组成为正样本。

2、U2I

用户和其交互过的物料可以组成正样本。

3、U2U

用户一半历史行为和另外一个用户一半历史行为，基于同一个兴趣爱好的，可以组成为正样本。

（二）简化负采样

1、Batch内负采样

方式：u_i交互过的物料表示为t_i，负样本则由一个batch中其他正样本中除了t_i以外的物料t_j和u_i组成。
优点：因为t_j在正样本中被计算过了，复用向量t_j避免了大量重复计算。
缺点：一个batch内大部分正样本都被热门物料垄断了，因此负采样得到的物料大多是热门物料，这是hard negative。缺少与用户兴趣毫不相干的easy negative。这种现象被称为样本选择偏差sample selection bias（SSB）。

2、混合负采样

为了解决batch内负采样造成的样本选择偏差，采用混合负采样策略（mixed negative sampling)。

主要思想如下：

额外建立了向量缓存，缓存多个Batch的物料向量。
batch内负采样作为hard negative。
额外从向量缓存中取出之前计算好的物料向量作为easy negative。

（三）双塔结构特点

塔内可以复杂，塔间不能。

1、单塔可以很复杂

塔就是一个DNN。
U2I的话就是将用户特征输入用户塔，物料特征喂给物料塔，输出embedding。
塔底座可以很宽，不局限于user ID,item ID这两种特征，可以接受的特征很丰富。
塔高可以足够高，实现充分的交叉。

2、双塔一定要解耦

解耦：①在特征上解耦：不使用物料特征和用户特征的交叉特征。②在结构上解耦：不能像DIN那样使用候选物料特征对用户行为序列做attention。③补充：用户特征向量和物料特征向量只有最后一步才点积交叉。
将用户行为序列接入用户塔：①最简单的方式是average pooling，但是这样会将所有历史行为视为相同重要。②由于无法使用候选物料对用户历史行为序列做attention，因此可以采用以下方式：（1）利用用户搜索文本当做query。（2）阿里巴巴将用户画像当做query给历史行为打分。（3）微信利用用户行为序列中最后交互的物料来体现用户最新行为兴趣，来衡量历史行为的重要性。

（四）sampled softmax loss的技巧

双塔模型常用的基于Batch内负采样的sampled softmax loss。

其中G(u,t)表示物料和用户的匹配程度。

1、L2正则化

已知u表示用户向量，t表示物料向量。每个向量都除以向量的L2正则，这样就将点积求匹配度转换成了cosine。由于cosine的范围在-1到1，更容易衡量匹配度。

2、温度调整难度

$\tau$ 被称为温度，由Tower loss可知，应当使得正样本的匹配程度尽量大，负样本的匹配程度尽量小。因此当负样本训练得不够好的时候，1/ $\tau$ 就会放大这个问题，导致分母变大，损失增加，没被训练好的负样本就会被重新聚焦。

$\tau$ 设置的足够小的时候，对错误放大的功能很强，会将与用户交互过的物料牢牢记住，而将没有交互过的物料与用户向量强行分开，这样推荐精度很高，但是兴趣覆盖不够。
$\tau$ 设置的足够大的时候，对错误放大能力较弱，会突破信息茧房来为用户推荐更广兴趣范围的物料，但是有损精度。

3、采样概率修正

除了batch内负采样之外，引入向量缓存中的物料向量作为负样本。

（五）Tensorflow实现双塔



class MovielensModel(tfrs.models.Model):
    """电影推荐场景下的双塔召回模型"""

    def __init__(self, layer_sizes):
        super().__init__()
        self.query_model = QueryModel(layer_sizes)  # 用户塔
        self.candidate_model = CandidateModel(layer_sizes)  # 物料塔
        self.task = tfrs.tasks.Retrieval(......)  # 负责计算Loss

    def compute_loss(self, features, training=False):
        # 只把用户特征喂入“用户塔”，得到user embedding "query_embeddings"
        query_embeddings = self.query_model({
            "user_id": features["user_id"],
            "timestamp": features["timestamp"],
        })
        # 只把物料特征喂入“物料塔”，生成item embedding "movie_embeddings"
        movie_embeddings = self.candidate_model(features["movie_title"])

        # 根据Batch内负采样方式，计算Sampled Softmax Loss
        return self.task(query_embeddings, movie_embeddings, ......)


class Retrieval(tf.keras.layers.Layer, base.Task):

    def call(self, query_embeddings, candidate_embeddings,
             sample_weight, candidate_sampling_probability, ......) -> tf.Tensor:
        """
        query_embeddings: [batch_size, dim]，可以认为是user embedding
        candidate_embeddings: [batch_size, dim]，可以认为是item embedding
        """
        # query_embeddings: [batch_size, dim]
        # candidate_embeddings: [batch_size, dim]
        # scores: [batch_size, batch_size]，batch中的每个user对batch中每个item的匹配度
        scores = tf.linalg.matmul(query_embeddings, candidate_embeddings, transpose_b=True)

        # labels: [batch_size, batch_size]，对角线上全为1，其余位置都是0
        labels = tf.eye(tf.shape(scores)[0], tf.shape(scores)[1])

        if self._temperature is not None:  # 通过温度，调整训练难度
            scores = scores / self._temperature

        if candidate_sampling_probability is not None:
            # SamplingProbablityCorrection的实现就是
            # logits - tf.math.log(candidate_sampling_probability)
            # 因为负样本是抽样的，而非全体item，Sampled Softmax进行了概率修正
            scores = layers.loss.SamplingProbablityCorrection()(scores, candidate_sampling_probability)

        ......

        # labels: [batch_size, batch_size]
        # scores: [batch_size, batch_size]
        # self._loss就是tf.keras.losses.CategoricalCrossentropy
        # 对于第i个样本，只有labels[i,i]等于1，scores[i,i]是正样本得分
        # 其他位置上的labels[i,j]都为0，scores[i,j]都是负样本得分
        # 所以这里实现的是Batch内负采样，第i行样本的用户，把除i之外所有样本中的正例物料，当成负例物料
        loss = self._loss(y_true=labels, y_pred=scores, sample_weight=sample_weight)
        return loss

二、GCN召回

图卷积网络GCN（Graph Convolutional Network)受到机器学习领域的广泛关注。

（一）GCN基础

1、GCN的结构与描述

可以用图来表示推荐系统中的一些关系，比如说可以将各种实体作为图的顶点（比如用户、商品、店铺等等），将各种交互关系（比如收藏、点击、购买）等作为图的边。

GCN的召回建模为边预测问题，预测点之间是否有边存在。如果用户u和物料t之间有边存在，那么t可以作为u的U2I的召回结果；如果物料t1和物料t2之间有边存在，那么t1可以作为t2的I2I的召回结果。

2、GCN向量化建模的四个关键问题

如何定义正样本：如果图中两顶点之间有边存在，那么可以作为正样本。
如何定义负样本：随机采取图中顶点作为负样本。
如何Embedding：两个用户之间的信息可以通过共同购买过的商品等等进行传递，丰富用户建模来源；两个物料之间的信息可以通过共同属于的品牌等等进行传递，丰富物料建模来源。
如何定义loss：NEG、sampled softmax loss等都可以用。

3、GraphSAGE和传统GCN

传统的GCN是直推式的（transductive)，训练和预测使用同一张图，得到的是各个节点的向量，无法对新节点进行预测。

GraphSage是一种图，它学习的不是节点的向量，而是转换函数，是归纳式的inductive。输入节点和链接关系，通过转换函数，可以得到向量。这样就可以学习到新节点的向量了。

注：直推式学习假设模型在训练时能够访问所有的测试数据。归纳式学习假设模型在训练时只能访问训练数据，而测试数据是不可见的。模型在训练时学习到的知识（如特征表示、参数等）必须能够应用于未来的、从未见过的测试数据。

（1）GraphSAGE的思想

其中h_v^0表示第0层的卷积结果是x_v，也就是v的特征向量。h_v^k表示v在第k层的卷积结果，z_v是v的最终向量表示。GraphSAGE将邻居信息和本身旧的信息融合成一个新向量，再进行线性和非线性激活。

第二个公式可以看出进行第k层卷积，主要是由两部分进行非线性激活 $\sigma$ 构成的：v的邻居结点还有v在k-1层的结果。第一部分通过average pooling得到各个邻居向量的聚合后再通过权重W_k进行线性映射。聚合方式还可以采用拼接、attention等。

如果忽略了第一部分，那么就是将上层得到的向量进行非线性激活，也就是MLP中第k层的公式。

（2）GraphSAGE的卷积过程

图中PROJB表示B_k，也就是第k层的权重，AGG表示聚合操作。在第三层输出的结点A的信息来源其实包含了图中所有的结点，因为在第二层的时候，C中已经包含了E和F的信息。也就是说通过GraphSAGE信息来源变多，建模结果具有全局视野，扩大了单个节点的感受野（Receptive Field）。

感受野描述的是网络中某一层的一个神经元所能看到的输入图像的区域大小。换句话说，感受野表示的是网络中某个特定神经元对原始输入图像的影响范围。

（二）PinSage大规模图卷积的经典案例

PinSage是在超大型图上实现了GraphSage的召回算法系统。

1、内容

Pinsage建模的是主要包含两类结点的二部图。两类结点分别是Pin和Board，举个例子来说Pin相当于网页，Board就像浏览器收藏夹可以收藏网页。Pin每个节点包含ID、文本、图片特征等，而Board相当于只包含ID的特殊Pin节点，将二部图按照同构图模式建模。

2、目标

学习出高质量的Pin Embedding，用于I2I召回。比如用户收藏了Pin1，系统给用户推荐相似的Pin，假如用户后续收藏了Pin2，那么(pin1,pin2)可以组成正样本。

3、伪代码

伪代码主要包含三个部分：第一部分是将节点v所有邻居节点向量通过一层非线性映射再聚合成一个向量n_v；第二部分是将n_v与节点v的旧向量表示z_v拼接起来，进行非线性映射得到新向量表示；最后将新获得的向量表示做一下正则化，得到最后的卷积结果。

4、Mini-Batch训练

基于Minibatch的PinSage算法是对大规模图数据进行处理的有效方法，主要通过将图的节点划分为小批次（minibatch），逐步更新每个批次中的节点表示，以降低计算复杂度和内存开销。

每轮训练中，GPU只计算当前Mini-Batch所需的子图，也只回代该Mini-batch涉及的节点。

①输入、输出

输入1：一个节点的集合M。

输入2：M中节点的部分邻居节点采样。

输出：M中所有节点的embedding。

②算法流程

（1）收集节点信息

如图卷积过程所示，在第K层得到M集合中所有节点的向量信息；而在K-1层，是汇聚了中M集合所有结点的向量信息和部分邻接节点信息。

（2）进行卷积

首先，先获取第0层的特征向量；再逐层进行卷积操作。遍历 $u\in S^{(k)}$ ，遍历的是有限的节点；后面获取的邻居节点也是有限的。

（3）进行映射

把卷积结果进行映射。

③生产者-消费者（Producer-Consumer）

PinSage产生了生产者-消费者（Producer-Consumer）的机制，主要表现为以下几点：

通过CPU，获取mini-batch中每层计算子图。
通过GPU，进行各个子图的卷积操作。
抽取子图和子图卷积并发进行，提高了训练效率。

5、邻居采样

①基本描述

进行邻居采样，而不是将节点u的所有邻居都纳入计算子图中。采取随机游走（Random Walk）的方式进行邻居采样，步骤如下描述所示：从图中某个节点k开始进行若干次随机游走，记录访问到的结点和访问的次数，选取访问次数排在前K位的节点作为邻居结点。

②流程步骤

最外层循环：Pin中每个节点。
中层循环：随机游走的次数控制。
内层循环：开始一次随机游走，直到被打断。打断方式是通过设置一个概率实现。

③邻居向量的AGG聚合

邻居向量中的AGG聚合本质上是加权平均函数，权重就来自于visit[p]的访问次数。

6、基于MapReduce分布式推理

①进行MapReduce的原因

（1）单机进行图中所有节点计算的计算量太大，因此应该采用分布式计算。

（2）进行图中某个节点中的邻居节点采样，会采取到重复的邻居节点，这样会导致相同的邻居节点被反复计算，浪费了资源。

②进行MapReduce的基本流程

MapReduce进行分布式计算，并发生成每个节点的embedding。进行第k层卷积以后，各个节点发将上一轮卷积得到的旧向量映射成新向量，并发送给各个邻居结点、。

7、源代码

class Mapper:
    def __init__(self, k) -> None:
        # 装载第k层卷积的权重
        self._Q = load_variables(k, "Q")
        self._q = load_variables(k, "q")

    def map(self, node, embedding, neighNodes, weightsToNeigh):
        """
        node: 某个节点
        embedding: node上一轮卷积后得到的向量
        neighNodes: node的邻居节点
        weightsToNeigh: node对其每个邻居的重要程度
        """
        # 线性映射+非线性激活，获得要发向邻居的新向量
        emb4neigh = ReLU(self._Q * embedding + self._q)

        for (destNode, weight2neigh) in zip(neighNodes, weightsToNeigh):
            message = (node, emb4neigh, weight2neigh)
            # node作为消息来源，将其新向量发往，目标destNode
            # MapReduce框架会以destNode为key，将所有message聚合起来
            emit(destNode, message)

        # node自己作为目标节点，也要参与reduce，所以也要发出
        emit(node, (node, embedding, 1))


class Reducer:
    def __init__(self, k) -> None:
        # 装载第k层卷积的权重
        self._W = load_variables(k, "W")
        self._w = load_variables(k, "w")

    def reduce(self, node, messages):
        """
        node: 当前节点
        messages: node的所有邻居发向node的消息集合
        """
        old_self_embedding = None
        neigh_agg_embedding = zero_vector()  # 初始化空向量
        neigh_sum_weight = 0

        for (nbNode, nbEmbedding, nbWeight) in messages:
            # 每个消息由三部分组成：
            # nbNode: 从哪个邻居节点发来的
            # nbEmbedding: 邻居节点发来的向量
            # nbWeight: 邻居节点对当前节点node的重要程度
            if nbNode == node:
                old_self_embedding = nbEmbedding  # 当前节点上一轮的向量
            else:
                neigh_agg_embedding += nbWeight * nbEmbedding
                neigh_sum_weight += nbWeight

        # 所有邻居向当前节点扩散信息的加权平均
        neigh_agg_embedding = neigh_agg_embedding / neigh_sum_weight

        new_embedding = ReLU(self._W * concat(neigh_agg_embedding, old_self_embedding) + self._w)
        new_embedding = new_embedding / l2_norm(new_embedding)  # L2 normalization

        emit(node, new_embedding)  # MapReduce会把每个节点和它的新向量，保存到HDFS上

（三）异构图上的GCN

1、同构图和异构图

上面介绍的同构图中包含的是相同类型的节点、关系，而实际上包含各种类型的节点（商品、店铺、用户等等）和多种关系（点击、收藏等）。

GCN关键是通过聚合邻居节点传来的信息，异构图则是通过聚合不同类型的邻居节点传来的信息。

2、MultiBiSage

MultiBiSage将异构图拆解为若干个同构图，思路是在不同的同构图上进行卷积最后在聚合生成节点向量。

主要步骤如下：

挖掘出所有的二部图，具有某种交互关系的Pin和Board组成二部图。
在某种单一的二部图上，进行卷积，得到embedding向量。
汇聚节点p从不同的二部图中得到的embedding得到一个序列，喂给transformer进行self attention，最终得到p节点融合了各种交互信息的embedding。

3、GraphTR

微信的GraphTR主要思路如下：直接在异构图上进行卷积，但是不同的邻居结点需要在卷积时分类。利用transformer对同类节点进行内部的信息交叉，利用FM进行不同类型的邻居节点之间的信息交叉。