首页 体育 教育 财经 社会 娱乐 军事 国内 科技 互联网 房产 国际 女人 汽车 游戏

基于行列式点过程的推荐多样性提升算法的直观理解

2020-01-04

多样性和相关性是衡量引荐体系的常用的方针,这两个方针一起影响着引荐体系的商业方针和用户体会。Hulu在NIPS 2018 会议上宣布的论文《 Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity 》中,提出了依据行列式点进程的引荐多样性提高算法,尽管网上能够找到许多解读文章,但个人觉得解说得不是很直观和易懂。本文测验给出一种愈加简略和简略了解的解读,而且给出算法的完成代码,是对自己了解进程的一次总结,也期望能够协助到读者。

咱们有一个待引荐的候选产品调集$Z=\lbrace 1,2,…,M \rbrace$,针对一个给定的用户,引荐体系需求挑选产品调集$Z$中的$N$个产品展示给用户,一起期望展示给用户的产品列表满意必定相关性和多样性。这便是咱们要处理的问题,那么首要咱们有必要弄清楚怎样衡量相关性和多样性。

相关性很好了解,便是引荐给用户的产品有必要契合用户的爱好,满意用户的购物需求。用户会用点击行为来表达爱好,用下单行为来满意购物需求。用户的点击和购买行为便是体系收集到的样本,依据这些样本引荐体系的从业者一直以来都在做的点击率和转化率预估,其实便是对相关性的一种衡量和量化。给定用户 $u$ 和候选产品调集 $C_u$,界说向量 $r_u$ 为相关性衡量值,其间 $r_i$ 表明用户与产品 $i$ 的相关程度,详细地,能够用用户对该产品的预估点击转化率来描写。关于怎样预估点击转化率,能够参阅《 CVR预估的新思路:完好空间多任务模型 》这篇文章。

引荐多样性衡量单个引荐列表中物品之间的差异程度,经过核算在同一个引荐 list 中两两 Item 之间的类似度的平均值来进行衡量。那么怎样量化引荐列表的多样性呢?要量化引荐列表的多样性,咱们首要要能够核算列表中恣意两个产品之间的类似性。核算两个目标之间的类似性有许多办法,这儿咱们假定用特征向量的余弦类似度的办法来核算。产品在表明成特征向量之后,两个特征向量之间的夹角越小,阐明这两个向量越类似,也便是对应的两个产品越类似。

引荐列表中的产品互相之间的类似度越低,引荐列表的多样性也就越高。咱们用一个界说在产品调集的类似度矩阵上的函数 $f\in R$ 来表明产品调集的多样性。函数的输入是产品调集的类似度矩阵,矩阵的每个元素 $S_{ij}=cosine$ 是产品对 $\langle i,j \rangle$ 的类似度衡量;函数的输出是衡量产品调集多样性程度的一个标量。那么,什么样的函数能够满意这样的界说呢?

一个很好的挑选便是矩阵 $S$ 的行列式 $det$。这是由于矩阵能够看着是一组向量的调集,而矩阵的行列式的物理含义为矩阵中的各个向量张成的平行多面体体积的平方。这些向量互相之间越不类似,向量间的夹角就会越大,张成的平行多面体的体积也就越大, 矩阵的行列式也就越大,对应的产品调集的多样性也就越高 。当这些向量互相正交的时分,多样性到达最高。能够经过一个二维平面上的比如直观地了解一下这背面的逻辑。

现在咱们能够别离衡量相关性和多样性了,接下来的问题便是能否在同一个进程中一起衡量相关性和多样性。答案当然是必定的,详细地,咱们引进一个叫做核矩阵的概念,用核矩阵的行列式来一起衡量产品调集的多样性和相关性。那么核矩阵是怎样界说的呢?怎样构建核矩阵才干有机交融相关性和多样性呢?

核矩阵是由$n$维欧氏空间中$k$个向量的内积组成的矩阵,可被称之为Gram矩阵。所以,核矩阵是一个半正定矩阵。关于半正定矩阵的界说,能够参阅“ 怎样了解正定矩阵和半正定矩阵 ”。

给定一个巨细为 $n imes n$ 的实对称矩阵 $A$,若关于恣意长度为 $n$ 的非零向量 $x$,有 $ x^T Ax$恒建立,则矩阵 $A$ 是一个 半正定矩阵 。

由于核矩阵 $L$是一个半正定矩阵,所以能够被分化为 $L=B^T B$,其间 $B$ 的每一列为候选会集产品的表明向量,详细地$B$ 的每一个列向量能够构建为相关性分数 $r_i \ge 0$ 与归一化后的产品特征向量 $f_i \in R^D $ 的乘积。因而,核矩阵中的元素能够被写成:

其间,$\langle f_i, f_j \rangle = S_{ij}$ 是产品 $i$ 与产品 $j$ 之间的类似度的衡量。所以,核矩阵能够被进一步写为:

其间,$Diag$ 是对角阵,它的对角向量是相关性衡量向量$r_u$。

假定体系挑选出的引荐给用户的产品子集为 $R_u$,$L_{R_u}$表明被产品子集$R_u$索引的核矩阵的子矩阵,则产品子集 $R_u$ 的相关性和多样功能够用下式衡量:

其间,$det$ 表明矩阵的行列式。上式等号右边的两项别离衡量引荐列表的相关性和多样性;等式把相关性衡量和多样性衡量有机地交融在一起。

前一末节解说了怎样衡量引荐列表的相关性和多样性,但并未解说怎样从候选产品调会集挑选产品组成终究的引荐列表。产品列表挑选的进程其实便是从一切的候选产品子会集挑选一个能使上述量化值最大的子集,而这个挑选的进程需求凭借行列式点进程来完成。

DPP行列式点进程,是一种功能较高的概率模型,其将杂乱的概率核算转换成简略的行列式核算,经过核矩阵的行列式核算每一个子集的概率。该概率能够了解为用户对引荐列表满意的概率,遭到相关性与多样性两个要素的影响。详细地,关于一个离散的调集$Z=\lbrace 1,2,…,M \rbrace$,一个DPP $P$ 是界说在该调集的一切子集$2^Z$上的一个概率衡量。当 $P$ 会为空集给出非零概率时,存在一个矩阵 $L∈R^{M M}$,关于一切子集$Y⊆Z$,$Y$的概率为:

其间,$L$ 是一个实数型、半正定的kernel matrix,它经过 $Z$ 的元素进行索引。

为了描绘的便利,给出一些契合界说:

出于简练,咱们假定:

引荐列表便是从候选产品调会集挑选能够最大化后验概率的产品子集,这一挑选进程便是行列式点进程的最大后验概率揣度MAP。

行列式点进程的MAP求解是一个杂乱的进程,Hulu的论文中提出了一种改善的贪心算法能够快速求解,该算法的时刻杂乱度为 $O$,$N$为回来的产品列表中产品的个数。

这一求解进程简略来说便是每次从候选会集贪心肠挑选一个能使边沿收益最大的产品加入到终究的成果子会集,直到满意中止条件中止,即每次挑选产品 $j$ 添加到成果会集 $Y_g$中,$Y_g$初始化为空集,产品 $j$ 需求满意下面的等式:

其间行列式$det$直接求解杂乱度较高,需求有奇妙的办法简化核算进程。假定$det 0$,$L_{Y_g}$的柯列斯基分化如下:

其间$V$是一个可逆下三角矩阵。关于恣意$i \in Z \backslash Y_g$,$L_{Y_g \cup \lbrace i \rbrace}$的柯列斯基分化能够定为:

其间,等式右边右上角的子矩阵为0向量,是由于$V$是一个下三角矩阵。依据矩阵乘法公式,行向量$c_i$和标量$d_i≥0$满意:

\begin{align}

V{c_i^{ op}} = L_{Y_{g,i}} ag{3} \

d_i^2 = L_{ii} - | c_i |_2^2 ag{4}

\end{align}

别的,依据等式, 能够得到:

因而,等式能够简化为:

一旦等式被求解,依据等式,$L_{Y_g \cup \lbrace i \rbrace}$的Cholesky decomposition变成是:

其间,$c_j$ 和 $d_j$ 是现已核算出来了的。当一个新item被添加到$Y_g$之后,$L_{Y_g}$的Cholesky因子能够被有用更新。

关于每个item $i$,$c_i$ 和 $d_i$ 能够被增量更新。在等式被求解后,将 $c_i’$ 和 $d_i’$ 界说为新的需求求解的向量和标量,其间 $i \in Z \backslash $。依据等式和等式,咱们有:

经过将等式和等式组合,咱们能够对 $c_i$ 和 $d^2_i$ 进行更新,有:

等式意味着:

开始,$Y_g = \emptyset$, 等式意味着: $d_i^2 = det = L_{ii}$。完好算法描绘如下:

其间,中止条件为$d_j^2 1$或许$|Y_g| N$。

Python代码如下:

热门文章

随机推荐

推荐文章