丰台区网站建设公司,自己电脑做网站服务器违法吗,织梦cms安装网站程序,百度开户资质排序系列篇#xff1a; 排序之指标集锦(系列1)原创 排序之损失函数pair-wise loss(系列2)排序之损失函数List-wise loss(系列3) 最早的关于list-wise的文章发表在Learning to Rank: From Pairwise Approach to Listwise Approach中#xff0c;后面陆陆续续出了各种变形#… 排序系列篇 排序之指标集锦(系列1)原创 排序之损失函数pair-wise loss(系列2)排序之损失函数List-wise loss(系列3) 最早的关于list-wise的文章发表在Learning to Rank: From Pairwise Approach to Listwise Approach中后面陆陆续续出了各种变形但是也是万变不离其宗本文梳理重在原理。
论文链接listNet参考的实现代码实现代码
1. 为什么要List-wise loss
pairwise优缺点 优点
一些已经被验证的较好的分类模型可以直接拿来用。在一些特定场景下其pairwise features 很容易就可以获得。
缺点
其学习的目标是最小化文档对的分类错误而不是最小化文档排序的错误。学习目标和实际目标MAE,NDCG有所违背。训练过程可能是极其耗时的因为生成的文档对样本数量可能会非常多。
那么本篇论文是如何解决这些问题呢 在pointwise 中我们将每一个query, document 作为一个训练样本来训练一个分类模型。这种方法没有考虑文档之间的顺序关系而在pariwise 方法中考虑了同一个query 下的任意两个文档的相关性但同样有上面已经讲过的缺点在listwise 中我们将一个query,documents 作为一个样本来训练其中documents 为与这个query 相关的文件列表。 论文中还提出了概率分布的方法来计算listwise 的损失函数。并提出了permutation probability 和top one probability 两种方法。下面会详述这两种方法。
2. 方法介绍
2.1. loss输入格式
假设我们有m 个 querys Q(q(1),q(2),q(3),...,q(m))Q(q^{(1)}, q^{(2)}, q^{(3)},...,q^{(m)}) Q(q(1),q(2),q(3),...,q(m)) 每个query 下面有n 个可能与之相关的文档对于不同的query 其n 可能不同 d(i)(d1(i),d2(i),...,dn(i))d^{(i)} (d^{(i)}_1, d^{(i)}_2, ..., d^{(i)}_n)d(i)(d1(i),d2(i),...,dn(i)) 对于每个query 下的所有文档我们可以根据具体的应用场景得到每个文档与query 的真实相关度得分。 y(i)(y1(i),y2(i),....,yn(i))y^{(i)} (y^{(i)}_1, y^{(i)}_2, ...., y^{(i)}_n)y(i)(y1(i),y2(i),....,yn(i)) 我们可以从每一个文档对(q(i),dj(i))(q^{(i)}, d^{(i)}_{j})(q(i),dj(i))得到该文档的打分q(i)q^{(i)}q(i)与文档集合d(i)d^{(i)}d(i)中的每个文档打分可以得到该query 下的所有文档的特征向量 x(i)(x1(i),x2(i),...,xn(i))x^{(i)} (x^{(i)}_1, x^{(i)}_2, ..., x^{(i)}_n)x(i)(x1(i),x2(i),...,xn(i)) 并且在已知每个文档真实相关度得分的条件下 y(i)(y1(i),y2(i),...,yn(i))y^{(i)} (y^{(i)}_1, y^{(i)}_2, ..., y^{(i)}_n)y(i)(y1(i),y2(i),...,yn(i)) 我们可以构建训练样本 T{(x(i),y(i))}T\begin{Bmatrix} (x^{(i)}, y^{(i)}) \end{Bmatrix}T{(x(i),y(i))}
要特别注意的是这里面一个训练样本是(x(i),y(i))(x^{(i)}, y^{(i)})(x(i),y(i))而这里的x(i)x^{(i)}x(i)是一个与query 相关的文档列表这也是区别于pointwise 和pairwise 的一个重要特征。 关于y(i)y^{(i)}y(i)paper里面的相关描述 2.2. loss计算
那么有训练样本了如何计算loss 呢 假设我们已经有了排序函数 f ff我们可以计算特征向量x(i)x^{(i)}x(i)的得分情况 z(i)(f(x1(i)),f(x2(i)),...,f(xn(i)))z^{(i)} (f(x_1^{(i)}), f(x_2^{(i)}), ..., f(x_n^{(i)}))z(i)(f(x1(i)),f(x2(i)),...,f(xn(i))) 显然我们学习的目标就是最小化真实得分和预测得分的误差 ∑i1mL(y(i),z(i))\sum_{i1}^{m} L(y^{(i)}, z^{(i)})i1∑mL(y(i),z(i)) L 为 listwise 的损失函数。
2.2.1. 概率模型
假设对于某一个query 而言与之可能相关的文档有{1,2,3,...,n}\{1, 2, 3, ..., n\}{1,2,3,...,n}假设某一种排序的结果为π\piπ ππ(1),π(2),..,π(n)\pi\pi(1), \pi(2), .., \pi(n)ππ(1),π(2),..,π(n)
对于n 个文档有n! 种排列情况。这所有的排序情况记为Ωn\Omega_nΩn。假设已有排序函数那么对于每个文档我们都可以计算出相关性得分s(s1,s2,...,sn)s (s_1, s_2, ..., s_n)s(s1,s2,...,sn)。 显然对于每一种排序情况都是有可能发生的但是每一种排列都有其最大似然值。
我们可以这样定义某一种排列π\piπ的概率最大似然值 Ps(π)∏j1nϕ(sπ(j))∑kjnϕ(sπ(k))P_s(\pi) \prod_{j1}^{n} \frac{\phi (s_{\pi(j)})}{\sum_{kj}^{n}\phi(s_{\pi(k)})}Ps(π)j1∏n∑kjnϕ(sπ(k))ϕ(sπ(j)) 其中ϕ\phiϕ表示对分数的归一化处理。
例如有三个文档π1,2,3\pi 1,2,3π1,2,3 其排序函数计算每个文档得分为s(s1,s2,s3)s(s_1, s_2, s_3)s(s1,s2,s3)则该种排序概率为 Ps(π)ϕ(s1)ϕ(s1)ϕ(s2)ϕ(s3)⋅ϕ(s2)ϕ(s2)ϕ(s3)⋅ϕ(s3)ϕ(s3)P_s(\pi) \frac{\phi(s_1)}{\phi(s_1)\phi(s_2)\phi(s_3)} \cdot \frac{\phi(s_2)}{\phi(s_2)\phi(s_3)} \cdot \frac{\phi(s_3)}{\phi(s_3)}Ps(π)ϕ(s1)ϕ(s2)ϕ(s3)ϕ(s1)⋅ϕ(s2)ϕ(s3)ϕ(s2)⋅ϕ(s3)ϕ(s3) 对于另外一种排序例如π′3,2,1{\pi} 3,2,1π′3,2,1 则这种排列概率为
Ps(π)ϕ(s3)ϕ(s3)ϕ(s2)ϕ(s1)⋅ϕ(s2)ϕ(s2)ϕ(s3)⋅ϕ(s1)ϕ(s1)P_s(\pi) \frac{\phi(s_3)}{\phi(s_3)\phi(s_2)\phi(s_1)} \cdot \frac{\phi(s_2)}{\phi(s_2)\phi(s_3)} \cdot \frac{\phi(s_1)}{\phi(s_1)}Ps(π)ϕ(s3)ϕ(s2)ϕ(s1)ϕ(s3)⋅ϕ(s2)ϕ(s3)ϕ(s2)⋅ϕ(s1)ϕ(s1)
很明显 3,2,1 这个排序的打分最低 1,2,3 这个排序的打分最高。
2.2.2. Top K Probability
上面那种计算排列概率的方式其计算复杂度达到n!n!n!太耗时间由此论文中提出了一种更有效率的方法 top one。我们在这里推广到top k来分析总结。
上面计算某一种排序方式概率 Ps(π)∏j1nϕ(sπ(j))∑kjnϕ(sπ(k))P_s(\pi) \prod_{j1}^{n} \frac{\phi (s_{\pi(j)})}{\sum_{kj}^{n}\phi(s_{\pi(k)})} Ps(π)j1∏n∑kjnϕ(sπ(k))ϕ(sπ(j)) 排在第一位的有nnn 种情况排在第二位的有n−1n−1n−1 种情况后面依次类推。相当与利用 top nnn来计算。 那么 top K(Kn)K(Kn)K(Kn)计算 Ps(π)∏j1Kϕ(sπ(j))∑kjnϕ(sπ(k))P_s(\pi) \prod_{j1}^{K} \frac{\phi (s_{\pi(j)})}{\sum_{kj}^{n}\phi(s_{\pi(k)})}Ps(π)j1∏K∑kjnϕ(sπ(k))ϕ(sπ(j)) 同理这里的计算复杂度为n∗(n−1)∗(n−2)∗...∗(n−k1)n∗(n−1)∗(n−2)∗...∗(n−k1)n∗(n−1)∗(n−2)∗...∗(n−k1)即为N!/(N−k)!N!/(N-k)!N!/(N−k)!种不同排列大大减少了计算复杂度。 如果K1K1K1就蜕变成论文中top 1 的情况此时有 n 种不同排列情况 Ps(π)ϕ(sπ(j))∑kjnϕ(sπ(k))P_s(\pi) \frac{\phi (s_{\pi(j)})}{\sum_{kj}^{n}\phi(s_{\pi(k)})}Ps(π)∑kjnϕ(sπ(k))ϕ(sπ(j))
对于N!/(N−k)!N!/(N-k)!N!/(N−k)!种不同的排列情况就有 N!/(N−k)! 个排列预测概率就形成了一种概率分布再由真实的相关性得分计算相应的排列概率得到真实的排列概率分布。由此可以利用 cross−entropy 来计算两种分布的距离作为损失函数 L(y(i),z(i))−∑j1n{Py(i)(j)∗log(Pz(i)(j))}L(y^{(i)}, z^{(i)}) - \sum_{j1}^{n} \{P_{y^{(i)}}(j) *log(P_{z^{(i)}}(j))\}L(y(i),z(i))−j1∑n{Py(i)(j)∗log(Pz(i)(j))}
例如一个查询下有三个文档A,B,CA,B,CA,B,C 上图中 g 为有真实打分计算出的各种排列的概率分布 f、h 为另外两种排列概率分布我们就是需要比较那种排列概率分布与真实的排列概率分布更为接近就用该分布的预测相关性得分作为最终得分。
2.2.3. ListNet
这里给出ListNet最终的形式 在论文中Listnet只是将上面的topKtopKtopK 中的ϕ\phiϕ函数变成 exp 函数: Ps(π)exp(sπ(j))∑kjnexp(sπ(k))P_s(\pi) \frac{\exp (s_{\pi(j)})}{\sum_{kj}^{n}\exp(s_{\pi(k)})}Ps(π)∑kjnexp(sπ(k))exp(sπ(j))
这样不就是计算预测出的得分的softmax 了吗实际上的确如此在实现代码中就是这样做的当时我直接看代码还一脸懵逼这不就是对文档预测出来的得分做了个softmax 操作吗跟top−one 有什么关系仔细看论文才知道怎么回事。
top−1 时只有n 种排列情况这大大减少了计算量。如果top K(K1)K (K1)K(K1)则需要计算的排列情况就会变多。
假设排序函数 f 的参数为w 则 top-one 的排列概率分布为 Pz(i)(fw)(xj(i))exp(fw(xj(i)))∑kjnexp(fw(xk(i)))P_{z^{(i)}(f_w)}(x_j^{(i)}) \frac{\exp (f_w(x_j^{(i)}))}{\sum_{kj}^{n}\exp(f_w(x_k^{(i)}))}Pz(i)(fw)(xj(i))∑kjnexp(fw(xk(i)))exp(fw(xj(i)))
这里还是需要注意是将某一个查询下的所有可能与之相关的文档列表作为一个样本来训练。
最终的损失函数 L(y(i),z(i)(fw))−∑j1n{Py(i)(xj(i))∗log(Pz(i)(fw)(xj(i)))}L(y^{(i)}, z^{(i)}(f_w)) - \sum_{j1}^{n} \{P_{y^{(i)}}(x_j^{(i)}) *log(P_{z^{(i)}(f_w)}(x_j^{(i)}))\}L(y(i),z(i)(fw))−j1∑n{Py(i)(xj(i))∗log(Pz(i)(fw)(xj(i)))} 小编总结 简单来说 Listwise的loss其实从本质上可以归纳如下 step1: 对所有包含正样本和负样本的集合进行softmax step2: 在用交叉熵对所有样本求和计算loss 但是从原理上来说其实这只是一个为了计算速度的折中。另外交叉熵中的groundtruth也就是上面的yj(i)y^{(i)}_jyj(i)打分这样groundtruth打分越高的如果预测误差大导致的loss越大从而对实际为高分但是预测为低分的关注度更高从而提高top的打分。 实现细节
在看源码的时候发现了一个细节paper里面说的是交叉熵但是在代码实现中我发现用的是交叉熵也就是红色里面是KL散度而绿色才是交叉熵。
总结
在pairwise 中只考虑了两个文档对的相对先后顺序却没有考虑文档出现在搜索列表中的位置排在搜索站果前列的文档更为重要如果前列文档出现判断错误代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素即每个文档对根据其在列表中的顺序具有不同的权重越是排在前列的权重越大即在搜索列表前列如果排错顺序的话其付出的代价更高(评价指标NDCG) 而listwise 讲一个查询下的所有文档作为一个样本因为要组合出不同的排列得到其排列概率分布来最小化与真实概率分布的误差这里面就考虑了文档之间的各种顺序关系。很好的避免了这种情况。 从概率模型的角度定义损失函数。 在实做时其实将一个query 下的的所有可能与之相关的n个doc作为一个训练样本这时可以理解batch_sizen 一定要注意在计算top_1 probability 时是在一个query 内的所有文档做softmax 而不是在当前正在训练的所有的样本内做。这是区别pointwise、pairwise 的重要不同之处。
参考链接 论文分享— Learning to Rank: From Pairwise Approach to Listwise Approach
