一种高效算法的应用，将淘宝“有好货”销售总额提升2.75%

众所周知，以淘宝为代表的电商平台通常会设计复杂的推荐策略以达到提高用户购买率的目的。然而目前的电商推荐系统通常仅依赖用户自身的历史购买行为为其作出推荐。

虽然已有大量研究表明用户的购买行为会显著受到朋友购买行为的影响（即社会推荐），电商平台中所缺乏的可靠信任关系，成为社会推荐这一推荐策略成功落地的最大障碍。

为此，本文以阿里巴巴淘宝平台上推荐系统所面临的实际问题为例，探讨如何推断大规模图中用户间的信任关系。

以上图为例，已知某些用户之间存在相互信任的关系，例如家庭关系、同学关系以及同事关系等，如何推荐其他用户之间的信任关系？

为解决该问题，我们提出了一个同时考虑关系之间的二元关联关系以及三元关联关系的因子图模型，基于此近一步提出一个效果相当但效率提升1000倍以上的近似模型。

我们将提出的模型应用到了阿里巴巴淘宝平台的实际业务场景中，A/B测试结果证明将模型所发现的信任关系应用到推荐系统中，能够显著优化电商平台的一系列重要商业评价指标。

我们定义了四种信任关系类型：家人(Fa)、同学(Cl)、同事(Co)、朋友(Kn)。上图展示了在已知用户A与B之间的关系（以及用户A与C之间的关系）的情况下，用户B-C之间的关系类型的分布。

图中的实线表示已知的关系，虚线表示需要推断的关系。从图中可以观察到，在大多数（开）闭三角形结构中，需要推断的关系很大概率上跟其中一个已知的关系类型相同。

我们提出的因子图模型能够根据输入数据自动学习图中所列举的（开）闭三角形结构在信任推断问题中的重要程度。

上图是我们建立的因子图模型（Factor Graph Model）。每两个用户之间的关系都对应一个特征向量 x 以及一个标签y（分别对应下图右侧下方和上方两个部分）。特征因子函数f定义在一个关系的 x 和y上：

二元因子函数g和三元因子函数h分别定义在两个相邻和三个构成三角形的用户关系上，分别反映了关系之间的二元关联关系以及三元关联关系：

其中是模型需要学的参数。

建立这样一个因子图模型之后，我们通过最大化似然函数得到优化目标：

其中Y^L表示所有已知标签的集合，p(Y|G)定义为图G中所有关系符合标签集合Y的概率。我们将这个联合概率建模成各个因子的乘积：

其中，Z表示全局归一化因子。我们使用梯度下降算法来求解模型的参数，以求解为例，我们计算目标函数对该参数的偏导数：

上式右方的期望可以展开为：

在计算上式的期望时，我们需要计算边缘概率p(yi, yj, yk)。我们使用循环置信传播算法（Loopy Belief Propagation）来近似该边缘概率。通过梯度下降算法，我们能得到因子图模型的参数。最后根据模型的参数来推断所有未知关系的标签。我们把所提出的这种方法叫做eTrust。具体的算法描述如下：

然而，在真实大规模图数据上，循环置信传播算法求解效率极其低下，因此我们提出了一种新效果相当但效率提升1000多倍的近似算法。我们用一个容易求解的概率来代替原本需要用循环置信传播算法求解的边缘概率。

具体来说，在每一轮迭代时，将上一轮迭代推断出的标签信息近似看做已知标签，由此得到新的负对数的目标函数：

其中带^的yj和yk表示上一轮推断得到的标签，全局归一化因子被局部归一化因子Zi所取代：

模型的参数仍然可以通过梯度下降法来得到，我们以参数为例给出其偏导数：

其中

我们把提出的这种近似方法叫做eTrust-s。具体的算法描述如下：

我们在阿里数据集以及另外3个公开的有关信任关系的数据集上验证了我们提出的模型的效果以及效率。数据集的统计信息如下：

我们的模型跟监督和半监督算法的比较如下：

我们的模型跟无监督算法的比较如下：

我们提出的eTrust-s相对于eTrust的效率比较如下：

eTrust-s模型在四个数据集上的因子分析以及收敛分析如下：

最后， 我们将eTrust-s模型在阿里巴巴真实用户数据中所推断出的信任关系应用到阿里巴巴线上推荐系统中，并对应用前与应用后的业务上进行了A/B测试。

应用了信任关系的推荐系统在淘宝商品搜索场景中，在退货率、差评率和中评率指标上相比于传统的协同过滤推荐算法分别降低了30.09%、45.45%和42.08%；在淘宝“有好货”场景中，给销售总额带来了2.75%的提升。