欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

ListNet原理

ListNet是一种Learning to rank的方法,其模型是神经网络,损失函数是ListWise,优化方法是梯度下降。ListWise已经被证明是效果要优于PairWise的方法,当然求解参数的复杂度也比别的高很多。

ListWise 方法

在搜索的场景中,所有的请求Query表示为: \(\begin{matrix} Q= \left ( q^{(1)},q^{(2)},...,q^{(m)} \right ) \end{matrix}\) ,对于每一个Query都会有一个检索的结果,结果中是排好序的文档,对某个Query其检索结果可以表示为: \(d^{(i)}=\left ( d_1^{(i)}, d_2^{(i)},...,d_{n^i}^{(i)}\right)\) ,相应的会有一个得分向量表示每一个检索结果的得分: \(y^{(i)}=\left ( y1^{(i)},y_2^{(i)},...,y_{n^i}^{(i)}\right )\)

可以使用 \(x_j^i=\phi(q^i,d_j)\) 生成一个特征向量,每一次检索的特征列表可以表示为: \(x^i=(x_1^i,x_2^i,...,x_{n^i}^i)\) 。我们的训练集合可以表示为:

\(\begin{matrix} \tau =\left \{ (x^i,y^i) \right \}_{i=1}^m \end{matrix}\)

接下来就是假设一个模型函数 \(f\) ,输入特征向量输出得分值,对于某一次搜索可以得到得分的列表: \(z^i=\left \{ f(x_1^i),f(x_2^2),...,f(x_{n^i)}^i)\right\}\) ,所以损失函数就可以表示为:

\(\sum_{i=1}^m L(y^i,z^i)\)

L就是我们ListWise的损失函数。

概率模型

接下来要解决的就是如何定义损失函数,论文中定义损失函数的方法是先将两个列表映射为两个分布,然后计算两个分布的相似性。如何得到两个分布的差距的方法,一般是通过交叉熵。

排列分布

「排列分布」就是通过排列生成的一个分布,例如有n个数,一共有n的阶乘种排列,如果每一种排列都有一个概率和其对应,这些数值就组成了一个一维的分布。

定义:π表示某一个排列, \(\phi(\cdot)\) 是一个值域为正数的单调递增函数,对于某一个排列和其得分,定义当前排列的概率为:

\(P_s(\pi)=\prod_j^n \frac{\phi(s_{\pi(j)})}{\sum_{k=j}^n \phi(s_{\pi(k)})}\)

上面公式有一些有用的性质(下面性质论文中均有描述):

  • 所有排列的概率之和为1
  • 概率最大排列是按照得分逆序,最小的是升序
  • 交换排列中两个的位置,得分高的前移会使得概率增加
  • 如果 \(\phi(x)=\alpha x\) 是一个线性函数,可以保证 \(P_s(\pi)\) 缩放不变性
  • 如果 \(\phi(x)=exp(x)\) 是一个指数函数,可以保证 \(P_s(\pi)\) 平移不变性

 Top k 概率

全排列一共有 \(A_n^n\) 种组合,如果只考虑top-k的排列种数就变为 \(A_n^k\) 种,如果k不大可以极大的缩小计算量。变为top-k之后,计算一个排列的概率的时候就不是计算到结尾,而是计算到第k个元素,具体的:

\(P_s(\varepsilon_k (j_1,j_2,...,j_k))=\prod_{t=1}^k \frac{\phi(s_{j_t})}{\sum_{l=t}^n \phi(s_{j_t})}\)

损失函数

损失函数采用交叉熵的方式,和普通的损失函数不同,这里的损失函数的项特别多,对每一组样本,都有 \(A_n^k\) 个损失项。如果和二分类对比的话,次数是一个超级多分类。

损失函数具体形式为:

\(L(y^i,z^i)=-\sum_{g \in \varepsilon_k } P_{y^i}(g)\log(P_{z^i}(g))\)

ListNet

ListNet和RankNet非常近似,RankNet是将一次检索中的n个文档组合长pair进行训练,ListNet是将其看成一个整体进行训练。ListNet中选择的模型依然是神经网络,排列中的变换函数 \(\phi\) 选择指数函数。具体如下:

QQ20160818-0

优化流程

QQ20160818-1

参考资料

http://www.cnblogs.com/kemaswill/archive/2013/01/24/2875434.html

Learning to Rank From Pairwise Approach to Listwise Approach

 

未经允许不得转载:大数据算法 » ListNet原理

评论 2

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    Top k 概率应该是连乘而不是连加。

    曹鹏3个月前 (07-26)回复
    • 多谢,已改

      leihao3个月前 (07-27)回复

关注大数据算法在工业界应用

本站的GitHub关于本站