在社交网络中, 节点间的链接关系通常分为两类:正关系和负关系.正关系表示喜欢、好友、信任等积极正面的含义; 负关系则表示讨厌、敌人、不信任等消极负面的含义.对网络中的部分或者全部链接关系进行正负关系标注, 其结果是形成一个符号网络.在现实生活中, 符号网络无所不在.例如:国家间的合作与敌对关系; 社交网络中, 用户之间好友与敌人的关系; 在线游戏中, 玩家伙伴与竞争的关系; 生物学上神经元间的促进与抑制关系等.如图 1所示, 符号社会网络正负关系预测问题是指:在符号网络中, 已知部分边的符号甚至所有边的符号都未知的情况下, 预测出其余边的符号[1].更确切地讲, 给定一个图G=(V, E, S), 其中, V={1, 2, …, n}为该图节点的集合, 集合E为该图的边集, 集合E中已知符号的边总数为m, e(i, j)∈E, e(i, j)={0, 1}, e(i, j)=1表示图中存在从点i指向点j的边, e(i, j)=0表示不存在从点i指向点j的边, 其中, i, j∈V; s(i, j)∈S, s(i, j)={-1, 0, 1}, s(i, j)=1表示边e(i, j)的符号为正, s(i, j)=-1表示边e(i, j)的符号为负, s(i, j)=0表示边e(i, j)的符号未知.符号网络中, 正负关系预测的主要目标即为预测出s(i, j)=0对应的边的符号.
Fig. 1 Schematic diagram of sign predction problem in signed social networks
图 1 符号网络链接正负关系预测示意图
现有的符号网络预测方法大致分为基于矩阵的[1-5]和基于分类的两种[6-11].在基于矩阵的符号预测中, 矩阵分解是最常用的预测方法.然而, 在实际符号网络数据中存在大量的上下文特征, 对这些特征信息, 矩阵分解模型无法有效利用.若能将上述上下文特征用于分解模型, 对符号网络预测的帮助无疑是巨大的.本文中, 我们考虑使用因子分解机模型来完成符号网络中正负关系的预测.
因子分解机模型(以下若无特殊情况, 均简称“模型”)由Steffen Rendle提出, 并成功应用于推荐和预测任务中[12-14].该模型之所以能在稀疏数据环境下取得较好的性能, 其原因在于它通过将每一列特征分解为一个隐向量来对特征间的交互进行建模, 极大地降低了数据稀疏带来的挑战.此外, 作为一个泛化性较强的模型, 通过结合任意启发式特征, 它能够模拟其他先进的方法, 如支持向量机模型和逻辑斯蒂回归模型等.
尽管在因子分解机模型上已经存在大量研究成果[15, 16], 在工业应用中依然存在大量未解决的问题.首先, 在于局部最优解的存在.因子分解机模型是非凸模型, 在使用随机梯度下降法和交替最小二乘法进行优化时, 其非凸函数的特性使得模型很容易陷入局部最优解.其次, 在于模型的大数据规模下的应用.大数据环境下, 由于我们需要将每个用户、项目和相关的启发式特征分解为一个低秩向量, 导致对内存的需求巨大, 即:数据增长带来的模型复杂度增加, 单机环境下的因子分解机模型会因为计算效率和内存问题失效.因此, 因子分解机模型的分布式优化成为一种流行的解决方案.目前, 有关因子分解机模型的分布式研究已有一些成果[17, 18], 但由于其采用的服务器-客户端框架, 模型的计算有效性仍受限于服务器与各客户端节点间的网络带宽压力.这种分布式框架如图 2(a)所示:每个客户端节点从服务器拉取最新的参数, 使用分派的子数据集更新对应的部分参数空间, 最后将更新后的参数推送回服务器端.显而易见, 在服务器端和各客户端节点集中通信时, 其带宽压力是巨大的.
Fig. 2 Difference between server-client and client-to-client framework
图 2 传统服务器-客户端模式与端到端分布式框架对比
首先, 为解决模型陷入局部最优解的问题, 本文提出了利用随机梯度Langevin动力学(SGLD)方法来优化模型.SGLD是由Welling提出的马尔科夫链蒙特卡洛(MCMC)学习方法的一种近似, 通过向随机优化方法的参数更新中添加噪声来实现[19].根据文献调研可知, 目前, SGLD优化的应用仅限于解决逻辑斯蒂回归、矩阵分解和隐狄利克雷分布(LDA)[19-21].因此在本文中, 我们尝试将SGLD方法应用于因子分解机模型中, 与随机梯度下降方法相比, SGLD能够通过随机噪声的添加来避免模型的学习陷入局部最优.
其次, 为进一步适应模型在大规模数据集上的应用, 我们提出一种新的分布式框架, 并将模型在SGLD下的优化扩展至该架构.不同于传统的服务器-客户端分布式系统, 新的分布式架构减轻了由于参数在服务器端和客户端的拉取和推送带来的通信压力, 框架结构如图 2(b)所示, 称为端到端分布式架构.结合模型的SGLD优化, 简称C2CDF(client to client distributed framework).在新的框架中, 客户端节点无需与服务器端做参数交互, 参数的传递按照预定的调度策略仅限于客户端节点之间进行.通过这种方式, 传统结构中的服务器端集中通信压力被分散到了所有的客户端机器上.
最后, 我们将提出的C2CDF模型应用到了3个不同的真实数据集上.实验结果显示:与模型在随机梯度下降方法下的优化相比, C2CDF能够取得更好的准确性.为了评估新提出分布式框架的效率, 我们将C2CDF和传统服务器-客户端架构下模型的SGLD实现进行了对比, 结果表明, C2CDF在获得更好准确性的同时取得2.3倍~ 3.3倍的加速比.
本文第1节解释如何使用SGLD解决模型的优化问题.第2节具体介绍端到端分布式框架.第3节设计实验验证新架构的效率和新方法的有效性.第4节介绍本文的相关工作.第5节总结全文.
1 模型和优化
本节首先介绍因子分解机模型和SGLD方法, 然后解释如何使用SGLD来优化解决因子分解机模型.
1.1 因子分解机模型
在基于分解的方法研究上, SVD++[22]、biased MF[23]、PITF[24]和FPMC[25]等多种可适用于不同领域和特征的模型纷纷问世.因子分解机模型[14]作为一种泛化性较强的方法, 除了具备上述分解方法的特点外, 还可以像支持向量机和逻辑斯蒂回归等分类方法一样, 结合更多的启发式特征.
因子分解机模型的核心思想在于通过分解每个特征为一个低秩向量对特征间的高阶交互进行建模.然后, 使用学习得到的特征向量完成分类、预测和排序等多种任务.假设一个预测数据集X∈Rn×p, 其中, 第i行xi∈Rp表示由p维组成的数据实例, n表示数据集的大小, p表示数据集特征数.对于每一个数据实例x, 都存在预测标签y∈R.基于上述数据集, 模式在阶d=2时的函数可定义如下:
$
{{\hat{y}}_{i}}(x)={{w}_{0}}+\sum\limits_{i=1}^{p}{{{w}_{i}}{{x}_{i}}}+\sum\limits_{i=1}^{p}{\sum\limits_{j=i+1}^{p}{\langle {{v}_{i}}, {{v}_{j}}\rangle }}{{x}_{i}}{{x}_{j}},
$
其中, w0表示全局影响因子; wi表示第i个特征的权重; vi表示第i个特征与其他特征的交互权重向量, 该向量由k维组成.k作为超参定义了分解所需的隐向量维度.从模型的函数定义可知:模型在建模特征交互权重时, 是通过分解每个特征为一个低秩隐向量, 而非一个单独的权重.这保证了模型良好的扩展性和参数空间的稳定, 同时降低数据的稀疏度, 使模型的优化取得更好的效果.模型的参数空间定义如下:
$
{{w}_{0}}\in R, w\in {{R}^{p}}, V\in {{R}^{p}}^{\times k}.
$
通常来说, 模型的特征维度p包括3个部分:用户规模、推荐或预测项目规模以及其他启发式特征如用户年龄、性别、朋友信息以及项目的价格、类别、流行度等.在特殊情况下, 若忽略启发式特征, 模型可以退化为一个典型的带偏置的矩阵分解模型, 该矩阵模型仅对用户与项目的隐向量进行建模.
1.2 SGLD
首先, 我们对随机优化方法先进行简单的回顾, 假设现有数据集$X=\{{{x}_{n}}\}_{n=1}^{N}$, 其后验分布可表示为$p(\theta |X)\propto p(\theta )\prod\nolimits_{t=1}^{N}{p({{x}_{i}}|\theta )}$, 其中, p(θ)为先验, p(xi|θ)为数据实例xi在给定模型参数θ下的概率.我们的目标是:通过最大化上述后验分布概率的对数形式, 学习得到模型参数θ.随机优化作为一个典型的方法, 常用于解决该问题, 其核心思想是:在每次迭代t时, 抽样全部数据集中的批量数据Xt={xt1, xt2, …, xtn}来更新模型参数.参数更新函数定义如下:
$
{{\theta }_{t+1}}\to {{\theta }_{t}}+\frac{{{\varepsilon }_{t}}}{2}\left[\nabla \log p({{\theta }_{t}})+\frac{N}{n}\sum\limits_{i=1}^{n}{\nabla \log p({{x}_{ti}}|{{\theta }_{t}})} \right],
$
其中, εt表示在第t次迭代时的步长.批量抽样的思想是, 在批量数据集上计算梯度来近似整个数据集上的梯度.这种随机优化方法的缺点在于:因为没有考虑参数的不确定性, 可能发生过拟合.因此, SGLD应运而生.
SGLD使用一种MCMC技巧——Langevin dynamics来捕捉参数的不确定性.通过在上述随机优化的基础上添加Langevin dynamics, 可得到如下SGLD优化方法的定义:
$
{{\theta }_{t+1}}\to {{\theta }_{t}}+\frac{{{\varepsilon }_{t}}}{2}\left[\nabla \log p({{\theta }_{t}})+\frac{N}{n}\sum\limits_{i=1}^{n}{\nabla \log p({{x}_{ti}}|{{\theta }_{t}})} \right]+{{\nu }_{t}}\ \ where\ {{\nu }_{t}}\tilde{\ }N(0, {{\varepsilon }_{t}}I),
$
其中, vt表示一个服从高斯分布的噪声抽样.通过向参数更新过程中添加高斯噪声, 使得批量数据样本的方差符合后验分布.从上述推论可以看出:SGLD的批量模式不但能够有效地用于大规模数据, 还可从贝叶斯方法角度捕捉参数的不确定性.
1.3 因子分解机模型的SGLD推导
经过大量的文献调研可知, SGLD方法目前仅用于优化逻辑斯蒂回归[19, 20]、基于贝叶斯概率矩阵分解[21]和LDA[26]等模型.本节将SGLD用于优化因子分解机模型, 并给出详细的推导过程.假设在目标损失函数中正则项使用L2正则化方法.在高斯噪声分布的假设下, 由于平方和损失函数作为最大似然估计的结果出现, 模型参数可被视为服从平均数为0的正太先验分布, 可定义如下:
$
{{w}_{0}}\tilde{\ }N(0, 1/{{\lambda }^{0}}), w\tilde{\ }N(0, 1/{{l}^{w}}), v\tilde{\ }N(0, 1/{{\lambda }^{v}}),
$
其中, λ0, λw, λv为正则化项参数.
根据上述对SGLD方法的介绍, 我们优化的目标是最大化参数后验对数分布, 即, 等于最大化其先验对数分布和对数似然:
$
\nabla \text{log}p(\theta |X)=\nabla \text{log}p\left( \theta \right)+\nabla \text{log}p\left( X|\theta \right).
$
首先, 对先验对数分布logp(θ)进行梯度推导, 根据上述给出的参数先验分布形式, 模型参数服从正太分布, 可表示如下:
$
p({{w}_{0}})\propto \exp \left( -\frac{{{\lambda }^{0}}}{2}
