RANK_SVM算法解析

发表于   |   分类于

RANK_SVM 原理

RankSVM基于SVM算法，将pair-wise的排序问题，转化为分类问题

SVM算法回顾

  1. SVM的优化目标
    $min \frac{1}{2}||w^2|| $
    $s.t. y_i(w^Tx_i+b) >= 1(i = 1, 2, 3 … n)$

  2. 使用拉格朗日函数 –> 转化为对偶问题来求解

  3. SVM使用的loss func为hinge loss(合页损失函数)
    $min_{w,b}[1 - y_i(w*x + b)]_+ + \lambda||w||_2^2$

RANK_SVM介绍

  1. 定义1：f是排序函数，$x_i\succ x_j \Longleftrightarrow f(x_i) > f(x_j)$, 表示如果$f(x_i) > f(x_j)$，$x_i$需要排在$x_j$的前面

  2. 定义2：假设f(x)是一个线性函数，$f(x) = \langle w, x \rangle$ 表示参数向量w和特征向量x的点乘(inner product)

  3. 定义3，我们可以将排序问题转换为分类问题
    $f(x_i) > f(x_j) \Longleftrightarrow \langle w, x_i - x_j \rangle > 0$

  4. 定义4定义y表示label值, 区值范围+1和-1，

    • y = +1, $if \langle w, x_i - x_j \rangle > 0$
    • y = -1, $if \langle w, x_i - x_j \rangle < 0$
      这样，我们就将排序问题转换成了分类问题

如何求解

这里，传统的SMO优化方法，我们这里不再做具体的介绍，在实做上，我们一般使用的是SGD方法
既然我们已经有了loss function，我们当然可以通过sgd的方法来解

loss func

  • loss = $min_w \frac{\lambda}{2}||w||^2 + \sum_{(d_i, d_j)}max(0, 1 - y_{(d_i, d_j)}\langle w, x_{d_i} - x_{d_j} \rangle)$
  • grad = $\lambda w - \sum_{i,j}I(y_{i,j} \langle w, x_i - x_j\rangle < 1)y_{i,j}(x_i - x_j)$

参考

  1. https://github.com/glycerine/sofia-ml, google实现的ranksvm
  2. learning to rank by lihang
------ 本文结束 ------
k