基本思想

GBRank 和 RankSVM 都是用来解决 LTR 问题的 pairwise 方法。利用 \Phi(q,d) 得出 query 和文档的特征向量，x1、x2分别是d1、d2的特征，取(x1, x2)为正样本，(x2, x1)为负样本，代入 SVM 模型中。

介绍

RankSVM 是在2002年提出的，之前工作关于LTR的工作貌似只有 Pointwise 相关的，比如 PRanking，这样的排序学习算法Work需要含有档位标注的训练样本，一般有以下几种获取方式：

1. 需要人工/专家标注
2. 诱导用户对展现的搜索结果进行反馈

这样就会存在会成本高、可持续性低、受标准者影响大等缺点。

而 RankSVM 只需要根据搜索引擎的点击日志构建 Pair 对即可，相对于先前的工作在算法的实用性上有了非常大的改善。

训练样本设计

对于 q 为一次 query，和文档集合 D = \{d_1, \dots,d_m\} ，算法按照相关性给出给出一个文档排序 r^* 。算法一般找不到最优的 r^* ，而是通过其排序顺序 r_{f(q)} 和最优值得差距来评估搜索排序函数 f 。

一般搜索引擎都会记录用户搜索后展现的结果以及用户的点击情况，这种日志成本较低，并且改造系统也较为方便，而RankSVM的训练样本就是从这种点击日志中进行提取。

由于用户点击的doc概率和排序的位置影响很大，虽然一般都是偏爱相关性较大的doc，但是如果这种doc排在很后面的话其实用户也几乎不会点，所以 RankSVM 就只考虑top级别的点击日志，一般为top 10

另外在构建训练数据时同一 query 下认为用户被点击 doc 相关性要高于没有被点击的 doc ，但是由于用户是从上往下浏览网页的，所以排在前面的 doc 被点击的概率会大于后面的 doc ，因此 RankSVM 使用的最终策略为:

Pair 构建策略：给定一组排序情况 (doc_1,doc_2,doc_3,\cdots) ，以及 C 记录了用户点击 doc 的情况，则有
doc_i{\overset{r^*}{<}} doc_j 对于所有pair对 1 \leq i ，同时 i \in C ， j \notin C

r^* 表示应有的优化排序，也就是被点击文档的相关性要大于排在该文档前面并且未被点击的文档，看上去很绕口，看个栗子：

假如某个用户搜索某个 query 得到首页10个doc，按顺序使用 doc_i 进行表示，如果该用户点击了 1,3,7 三个文档，则认为有:

doc_3 {\overset{r^*}{<}} doc_2 \\
doc_7 {\overset{r^*}{<}} doc_2 \\
doc_7 {\overset{r^*}{<}} doc_4 \\
doc_7 {\overset{r^*}{<}} doc_5 \\
doc_7 {\overset{r^*}{<}} doc_6

表示该 query 下 doc_3 的相关性要高于 doc_2 ，理应排在前面，而 doc7 的相关性也应该要高于 doc_{2，4，5，6} ，但是可以发现未见 doc_1 的相关性鉴定，这是由于 doc_1 已经是排在了第一位，本身位置点击概率就就是最高的，所以无法判断与其他文档相关性的高低，同理， doc_{8，9，10} 也未纳入相关性的排序中。

训练样本可以通过这样方式进行构建，但是遗憾的是并没有一种机器学习算法能直接使用这种数据进行训练学习-_-

搜索函数的理论框架

在上面的栗子中，我们希望用新算法完成 doc_{1，3，7} 排在top 3，那这样的文档的真实相关性高的将会排到前面，RankSVM 采用Kendall’s Tau （肯德尔等级相关系数）来统计实际排序与算法排序的度量，先看下面两个变量:

1. P 表示排序序列中保持一致性的 Pair 对数量，也就是真实相关性高的排在第的前面。
2. Q 表示排序序列中保持不一致的 Pair 对数量（逆序数），也就是由于算法的误差导致真实相关性低的排在了高的前面
3. 同时 P+Q=\binom{m}{2} ， m 表示序列中文档的数量，因为长度为 m 的序列可能组成的 Pair 对为 m 的2组合

则 \tau 的计算方式为:

\tau(r_a，r_b)=\frac{P-Q}{P+Q}=1-\frac{2Q}{\binom{m}{2}}

r_a 为真实排序， r_b 为算法排序

比如实际文档中的顺序为:

d_1{\overset{r^*}{<}}d_2{\overset{r^*}{<}}d_3{\overset{r^*}{<}}d_4{\overset{r^*}{<}}d_5

但是算法的排序顺序为:

d_3{\overset{\hat{r}}{<}}d_2{\overset{\hat{r}}{<}}d_1{\overset{\hat{r}}{<}}d_4{\overset{\hat{r}}{<}}d_5

因此可以发现算法排序中有3对 Pair 不一致了( \{d_2，d_3\} ， \{d_1，d_2\} ， \{d_1，d_3\} )，所以 Q=3 ， P=4+3+2+1-3 = 7 ，最终的 \tau(r，\hat{r})=\frac{7-3}{10}=4
\tau 的值越大，表示排序效果越接近真实，比如上面的 \tau(r，r)=\frac{10-0}{10}=1

还证明了由逆序数 Q 的一个式子为平均准确率指标的下界(具体证明看原文附录):

 AvgPrec(\hat{r}) \geq \frac{1}{R} \left[Q+\binom{R+1}{2}\right]^{-1} \left(\sum_{i=1}^{R} \sqrt{i}\right)^2

R 为排序出现的文档中与 query 相关文档数量（这个是[Mean Average Precision](http://kubicode.me/2016/02/15/Machine Learning/Learning-To-Rank-Base-Knowledge/#MAP)中的标注，与 Pair 对的样本稍微有点差别）
从这个角度也可以看到 \tau 来衡量排序效果好坏的合理性.

现在可以定义学习排序函数得问题，对于有 m 个文档的 D 集合上，有固定且未知分布的概率 P{r(q, r^*)} ，目标是学习到一个 f(q) ，其使得肯德尔系数 \tau 最大化。

\tau_{P}(\mathrm{f})=\int \tau\left(\mathrm{r}_{\mathrm{f}(\mathrm{q})}, \mathrm{r}^{*}\right) d \operatorname{Pr}\left(\mathrm{q}, \mathrm{r}^{*}\right)

以下算法采用经验风险最小化，假设现在有 n 个 q_i 作为训练样本，他们各自的目标排序为 r_i^* ，也就是:

(q_1,r_1^*),(q_2,r_2^*),(q_3,r_3^*),\cdots,(q_n，r_n^*)

给定一个大小为 n 且独立同分布的训练样本 S ，其中算法排序为 \hat{r}_i ，则排序算法的优化目标是将下列式子

\tau_{S}(\mathrm{f})=\frac{1}{n} \sum_{i=1}^{n} \tau\left(\mathrm{r}_{\mathrm{f}\left(\mathrm{q}_{i}\right)}, \mathrm{r}_{i}^{*}\right)

最大化。

RankSVM 排序

假设能找到一个排序算法 f 能使得上面的 \tau_s 得到最大化，对于一个指定的查询 q ，每个文档 d_i 使用特征向量映射方法 \Phi(q，d_i) ， \vec{w} 是通过学习调整的权重向量。 \Phi(q,d) 是映射到描述查询 q 和文档 d 之间的匹配的特征的映射，例如网页 title, h1, h2 标题共有的单词数，或者 d 的页面排名。

如果是直接使用线性排序方法:

\left(\mathrm{d}_{i}, \mathrm{~d}_{j}\right) \in \mathrm{f}_{\vec{w}}(\mathrm{q}) \Longleftrightarrow \vec{w} \Phi\left(\mathrm{q}, \mathrm{d}_{i}\right)>\vec{w} \Phi\left(\mathrm{q}, \mathrm{d}_{j}\right)

\vec{w} 表示权重向量，线性排序下，排序分数为权重 x 特征向量

上图表示一个二维的权重与特征图，在排序的顺序的就是特征在权重上的投影位置顺序，比如单从 W_1 维度进行观察可以看到的排序顺序为{1，2，3，4}，而如果按 W_2 维度则是{2，3，1，4}。

在这里，间隔被定义为当数据点投射到排序向量 w 时两个数据点之间的最近距离，如图 d_1,d_2 ：

为了最大化 \tau_s ，可以最小化 Q 来代替，也就是说对于线性的排序， Q=0 就是表示下面的等式全成立(也就是最大化)

\forall (d_i,d_j) \in r_1^* : \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j) \\
… \\
\forall (d_i,d_j) \in r_n^* : \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j)

不幸的是，优化这个是一个NP问题。
但我们可以让他们绝大多数都成立，SVM 在由于软间距最大时可以看到熟悉的身影，可以通过引入（非负）松弛变量 \xi_{i,j,k} 并按如下方式最小化上限 \sum\xi_{i,j,k} 来使用SVM技术来近似解。：

\begin{aligned}
&\min[\frac{1}{2} \vec{w} \cdot \vec{w} + C \sum \xi_{i，j，k}]
\\ \\
\text{s.t. }&\forall (d_i,d_j) \in r_1^* : \vec{w} \Phi(q,d_i) \geq \vec{w} \Phi(q,d_j) + 1 - \xi_{i,j,1} \\
&\cdots \\
&\forall (d_i,d_j) \in r_n^* : \vec{w} \Phi(q,d_i) \geq \vec{w} \Phi(q,d_j) +1 - \xi_{i,j,n} \\
&\forall_i \forall_j \forall_k:\xi_{i,j,k} \geq 0
\end{aligned}

\xi 为松弛项， C 表示平衡项

因此优化该问题时可以将约束转为:

\vec{w} \Phi(q，d_i)-\vec{w} \Phi(q，d_j) \geq 1 - \xi_{i，j，1}

并且由于是线性排序，可以进一步精简为:

\vec{w} \left(\Phi(q，d_i)-\Phi(q，d_j)\right) \geq 1 - \xi_{i，j，1}

在 Pair 对中只可能 d_i 是否排在 d_j 前面是一个二值结果，所以我们可以将 d_i 排在 d_j 前面的 Pair 为正标签，否则为负标签:

y=\left\{
\begin{aligned}
+1 & \quad if \quad \vec{w} \Phi(q，d_i)>\vec{w} \Phi(q，d_j) \\
-1 & \quad otherwise\\
\end{aligned}
\right.

则最终可以将约束可以写成:

y_i \cdot \vec{w} \left(\Phi(q，d_i)-\Phi(q，d_j)\right) \geq 1 - \xi_{i，j，1}

其中传统的偏置项在 RankSVM 是不需要的，以为正好 Pair 相减时就消掉了

所以这样一个问题等价于 SVM 应用于成对向量差上的分类问题。完全将上面构建的样本转为一个分类问题，使用 SVM 的对偶形式进行求解，并且还可以使用核函数进行非线性的分类。 \vec{w} 对应了排序函数，可以对query-doc pair进行打分和排序。

所以 RankSVM 可以看做是一个回归问题，模型应用的时候，使用当前样本的预估值作为排序的依据。

但是样本的构造就发生了变化，每一条样本表示的是一个序关系。所以，损失函数变为（样本 x_i 排名好于 x_j ）

\begin{matrix} minimize &&\ \ \ \ \frac{1}{2}|w|^2+C\sum_{ij} \xi_{ij}\\s.t. && (wx_i+b) -(wx_j+b) \ge 1-\xi_{ij}\\ &&\xi_{ij}\ge 0 \end{matrix}

上式为了方便理解，没有进行化简，上式也可以依葫芦画瓢引入核函数。

RankSVM 可以看做是寻找一个超平面，使得点对 (x_i , x_j) 对平面的几何间隔差最大。

rsv(q，d_i)= \vec{w}^* \Phi(q，d_i) = \sum_l^n \alpha_{k,l}^*y_i(\Phi(q_k，d_l) \cdot \Phi(q，d_j))

上面是表示两个不同的 query 所表示的特征空间，不同的形状表示文档与对应 query 的相关性档位，三角形 x_1 表示相关性档位高，圆圈 x_2 表示相关性档位一般，叉叉 x_3 表示相关性档位差。
将这些样本转为 Pair 对之后可以有：

可以发现 x_1-x_3 和 x_1-x_2 为正样本，而 x_2-x_1 和 x_3-x_1 为负样本，因此可以形成对应的训练数据进行训练，其实这样形成的样本是对称的，因此在实际使用中一般只保留一侧即可。

总结

RankSVM 很好的解决原始训练样本构建难的问题，根据点击日志构建样本，既考虑了doc之间的顺序，又保证了可持续性，并且其 Pair 对的训练正好可以使用SVM进行求最优化，而SVM分类器已经是非常成熟并且广泛使用的一种机器学习算法。
因此 RankSVM 虽然在2002年就提出，但是至今在工业界还是广泛使用，但是现在的主要难点是样本 Pair 对的构建，针对不同的场景也不同的策略，不一定只是根据点击顺序，实际使用中还要考虑新样本数据。

参考

1. Joachims T. Optimizing search engines using clickthrough data[C], Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2002:133-142.

2. Learning to Rank for Information Retrieval and Natural Language Processing, Hang Li

3. 原始博文来源于 [RankSvm-基于点击数据的搜索排序算法](http://kubicode.me/2016/03/30/Machine Learning/RankSvm-Optimizing-Search-Engines-using-Clickthrough-Data/)，但他转述错了论文的某些细节部分，感觉像机翻，所以修正写好重发。

4. LTR中RankSVM算法的基本思路是什么？

5. RankSVM原理

一般的约束优化问题

约束优化问题常常可以化简为以下不等式，

\begin{aligned}

&\min_{x\in\mathbb{R^p}}f(x)\\
&s.t.\ m_i(x)\le0,i=1,2,\cdots,M\\
&\ \ \ \ \ \ \ \ n_j(x)=0,j=1,2,\cdots,N

\end{aligned}

可以写成拉格朗日函数

L(x,\lambda,\eta)=f(x)+\sum\limits_{i=1}^M\lambda_im_i(x)+\sum\limits_{i=1}^N\eta_in_i(x)

那么原问题可以等价于无约束形式：

\min_{x\in\mathbb{R}^p}\max_{\lambda,\eta}L(x,\lambda,\eta)\  \\s.t.\ \lambda_i\ge0

求偏导后， n_i(x) 会等于0。当未满足约束时， m_i(x) 0 ， \lambda_i 可以调整为最大值 \infin ， \max_{\lambda,\eta}L(x,\lambda,\eta)\ = \infin ；满足其约束时， m_i(x) \le 0 ， \max_{\lambda,\eta}L(x,\lambda,\eta) 为常数。取 min 显然过滤了不满足约束情况。

这个问题的对偶形式：

\max_{\lambda,\eta}\min_{x\in\mathbb{R}^p}L(x,\lambda,\eta)\ s.t.\ \lambda_i\ge0

对偶问题是关于 \lambda, \eta 的最大化问题。

\max_{\lambda_i,\eta_j}\min_{x}L(x,\lambda_i,\eta_j)\le\min_{x}\max_{\lambda_i,\eta_j}L(x,\lambda_i,\eta_j)

证明，理解为L的值域，值域里面的任何一个数，大于等于它的最小值，小于等于它的最大值

   \min\limits_{x}L\le L\le\max\limits_{\lambda,\eta}L \\  
  \Rightarrow \max\limits_{\lambda,\eta}\min\limits_{x}L\le L   , \min\limits_{x}\max\limits_{\lambda,\eta}L\ge L \\

对偶问题的解小于原问题，有两种情况：

1. 强对偶，能取等于号
2. 弱对偶，不能取等于号

几何解释

特别的，二次规划问题都满足 slater 条件。对于一个凸优化问题，有如下定理：

凸优化问题满足某些条件如 Slater 条件 \Rightarrow 它和其对偶问题满足强对偶关系。

注意是充分不必要条件。记问题的定义域为： \mathcal{D}=\mathrm{dom}f(x)\cap \mathrm{dom} m_i(x)\cap \mathrm{dom}n_j(x) 。 Slater 条件为：

\exist\hat{x}\in \mathrm{relint}\mathcal{D}\ \text{s.t. } \forall i=1,2,\cdots,M,m_i(x)\lt0 \\  \mathrm{relint} \text{ 表示相对内部（不包含边界的内部）。}\\

1. 对于大多数凸优化问题，Slater 条件成立。
2. 对于不满足条件的，可以松弛 Slater 条件，如果 M 个不等式约束中，有 K 个函数为仿射函数，那么只要其余的 (M – K) 个函数满足 Slater 条件即可。

KKT 条件

原问题及其拉格朗日函数为

\begin{aligned}

&\min_{x\in\mathbb{R^p}}f(x)\\
&s.t.\ m_i(x)\le0,i=1,2,\cdots,M\\
&\ \ \ \ \ \ \ \ n_j(x)=0,j=1,2,\cdots,N
\\
&L(x,\lambda,\eta)=f(x)+\sum\limits_{i=1}^M\lambda_im_i(x)+\sum\limits_{i=1}^N\eta_in_i(x) \\
&\text{令 } g(\lambda, \eta) = \min_{x} L(x,\lambda,\eta)
\end{aligned}

对偶问题有

\begin{aligned}
&\max_{\lambda, \eta} g(\lambda, \eta) \\
&\text{s.t. } \lambda_i\ge0
\end{aligned}

原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件，KKT 条件 \Leftrightarrow 强对偶关系。关于原问题， p^* 是最优解， x^* 是最优解参数。关于对偶问题， d^* 是最优解， \lambda^*, \eta^* 是最优解参数。证明弱对偶性实际上就是证明 d^* \le p^* ，强对偶性是证明 d^* = p^* 。KKT 条件对最优解的条件为：

1. 可行域：

   \begin{aligned}
   m_i(x^*)\le0\\
   n_j(x^*)=0\\
   \lambda^*\ge0
   \end{aligned}

2. 互补松弛 \lambda^*m_i(x^*)=0,\forall m_i

   \begin{aligned}
   d^*&=\max_{\lambda,\eta}g(\lambda,\eta)=g(\lambda^*,\eta^*) \\
   &=\min_{x}L(x,\lambda^*,\eta^*) \\
   &\le L(x^*,\lambda^*,\eta^*) \\
   &=f(x^*)+\sum\limits_{i=1}^M\lambda^*m_i(x^*) \\
   &\le f(x^*)=p^*
   \end{aligned}

   为了满足相等，两个不等式必须成立，于是，对于第一个不等于号，需要有梯度为0条件，对于第二个不等于号需要满足互补松弛条件。

3. 梯度为0： \frac{\partial L(x,\lambda^*,\eta^*)}{\partial x}|_{x=x^*}=0