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

RankSVM原理

RankSVM是使用SVM模型解决Learning to rank问题的Pair-wise方法,和传统的算法的区别就是样本的构造和lable的意义有所改变。将原来的两个样本 \(x_i,x_j\) 表示一个训练数据, \(x_i\) 排名好于 \(x_j\) 就标记为1,反之为-1。本文首先会介绍一下SVM/SVR模型,最后引出RankSVM

 

几何间隔

这里尝试从向量乘法的角度推导几何间隔的计算。

对于一个二维空间,分类面可以表示为:

\(w_1 x_1 + w_2 x_2 + b = 0\)

计算点a到直线的几何距离的思路,就是先计算点a到过O点的平行线的距离,然后再计算两个平行线之间的距离,两者的差,就是我们要求的几何间隔,其中使用的基础公式就是点乘的公式:

\(a^T b = |a| |b| cos \theta\)

下图为具体计算过程:

854C6474-57CC-4613-BF8F-7523F0000F74

损失函数

SVM的损失函数是「几何间隔」最大,这样的目标导致优化问题中约束条件需要除以W的模,这个除法会将计算复杂化。一种容易想到的方法是将这个模放到目标函数中,然后通过目标函数的一些等价的性质将此项从分母位置消除掉。在我看来,这就是为什么会对原始的目标函数进行变换的原因。变换之后的损失函数为:

\(\min_{w,b}\ \ \ \frac{1}{2}|w|^2\\s.t.\ \ \ \ \ \ y_i(w\cdot x_i +b) \ge 1\)

对于线性不可分的情况引入了软间隔的概念,站在损失函数的角度,软间隔使得落在支持向量「内部方向」的点计算损失。其损失值形状类似一个「合页」,如下图,虚线是感知机的损失函数(注意下图的自变量):

B335191E-AC84-4077-953B-CE4FF1549586

引入软间隔之后的损失函数表示为:

\(\min_{w,b}\ \ \ \frac{1}{2}|w|^2 +\sum_{i=1}^N\xi_i \\s.t.\ \ \ \ \ \ y_i(w\cdot x_i +b) \ge 1- \xi_i\)

三层的神经网络

SVM本身可以看做是一个三层的神经网络,因为其决策分类函数形式为:

\(f(x)=sign\left \{ \sum_{i=1}^{N} \alpha_i^* y_i(x \cdot x_i) +b^* \right \}\)

这个神经网络特别的地方在于,隐层节点的个数是样本的个数,网络结构为:

98E75A2C-56BC-4CA7-8079-2AD19FA7DFA3

隐层节点的个数就是样本的个数,好在多数节点的 \(\alpha_i\) 系数都为0,所以进行模型预估的时候只需要考虑系数不为0「支持向量」即可,但是模型学习的过程就变成了一个苦差事,每一条样本都要学出来一个 \(\alpha_i\)

核技巧

在当前空间样本线性不可分的时候,除了加入松弛因子之外,还可以进行特征的组合、变换,将原有样本映射到新的空间。这个映射可以表示为一个函数的操作:

\(x\rightarrow \phi(x)\)

映射之后在新的空间「可能」就线性可分了。明显可以看到的是,映射到的空间如果维度越高,就越容易线性可分,所以除非是重合的样本,否则一定可以在高纬度达到线性可分。加入特征映射之后,损失函数的对偶问题可以表示为:

\(\begin{matrix} maximize &&\sum_{i}\alpha_i - \sum_i \sum_j \alpha_i \alpha_j y_i y_j \phi(x_i)\cdot \phi(x_j)\\s.t . &&\sum_i \alpha_i y_i = 0\\&&0 \le \alpha \le C \end{matrix}\)

分类函数变为:

\(f(x)=sign \left \{ \sum_i \alpha_i^* y_i \phi(x_i) \cdot \phi(x) + b^* \right \}\)

通过上面式子可以发现,我们关心的是 \(\phi(x_i) \cdot \phi(x_j)\) 的结果,对于映射到的具体空间不关心,因为最终也是通过「点乘」变为了一个标量。所以,如果有一个函数满足 \(K(x_i,x_j)=\phi(x_i) \cdot \phi(x_j)\) ,那么就可以直接使用这个函数将其替换。这个函数就被称为核函数。有的核函数有一些特殊的性质,例如高斯核, 与它对应的 \(\phi\) 为无穷维的一个映射,所以理论上可以拟合所有样本。

SVR

SVM Regression简称SVR,就是使用SVM来做回归问题,其实思路也很简单,SVM是求间隔最大,SVM是求回归的值的差尽可能小,回归函数为:

\(F(x)=wx+b\)

目标函数是:

\(\begin{matrix} minimize &&\ \ \ \ \frac{1}{2}|w|^2 \\s.t. && y_i -(wx_i+b) \le \xi\\&&(wx_i+b)-y_i \le \xi \\\end{matrix}\)

松弛操作、核技巧和SVM类似,这里就不说了。

SVR可以看做是找一个超平面,使得点 \((x_1,y_1),(x_2,y_2),...,(x_n,y_n)\) 中支持向量到这个超平面的几何间隔最大。

下面来就是本文的主角:RankSVM。

RankSVM

其实任何模型,首先要确定的就是模型函数,RankSVM使用的模型函数和SVR没有大的区别,依然是:

\(F(x)=wx+b\)

所以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\) 对平面的几何间隔差最大。

RankSVM训练样本

一般来说,工业界不可能手工进行样本的标注,基本都是通过「行为」日志得到训练的样本。这方面有很多论文,因为rank本身具有位置的bias,所以这方面水很深。大多数论文中生成训练样本的原则:

  1.     Click> Skip Above
  2.     LastClick > Skip Above
  3.     Click> Earlier Click
  4.     LastClick > Skip Previous
  5.     Click> No-Click Next

参考资料

《统计学习方法》 李航

SVM Tutorial- Classification, Regression, and Ranking

http://club.alibabatech.org/article_detail.htm?articleId=54

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

评论 3

*

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

    老哥,你是不是搞错了,在损失函数一部分,因该是 min 吧?

    Jackey 伊轲2年前 (2017-02-23)回复
    • 你说的对,取了倒数就变成最小化了,已修改

      leihao2年前 (2017-02-24)回复
      • 竟然有回复了……

        Jackey 伊轲2年前 (2017-02-24)回复

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

本站的GitHub关于本站