Modeling Parameter Interactions in Ranking SVM
Yaogong Zhang
†§∗
Jun Xu
‡
Yanyan Lan
‡
Jiafeng Guo
‡
Maoqiang Xie
†§
Yalou Huang
†§
Xueqi Cheng
‡
†
College of Computer and Control Engineering ,Nankai University
‡
CAS Key Lab of Network Data Science and Technology,
Institute of Computing Technology, Chinese Academy of Sciences
§
College of Software, Nankai University
ygzhang@mail.nankai.edu.cn, {junxu, lanyanyan, guojiafeng}@ict.ac.cn,
{xiemq, huangyl}@nankai.edu.cn, cxq@ict.ac.cn
ABSTRACT
Ranking SVM, which formalizes the problem of learning a
ranking model as that of learning a binary SVM on prefer-
ence pairs of documents, is a state-of-the-art ranking model
in information retrieval. The dual form solution of Ranking
SVM model can be written as a linear combination of the
preference pairs, i.e., w =
P
(i,j)
α
ij
(x
i
− x
j
), where α
ij
denotes the Lagrange parameters associated with each pair
(i, j). It is obvious that there exist significant interactions
over the document pairs because two preference pairs could
share a same document as their items. Thus it is natural to
ask if there also exist interactions over the model parame-
ters α
ij
, which we may leverage to propose better ranking
model. This paper aims to answer the question. Firstly,
we found that there exists a low-rank structure over the
Ranking SVM model parameters α
ij
, which indicates that
the interactions do exist. Then, based on the discovery, we
made a modification on the original Ranking SVM model
by explicitly applying a low-rank constraint to the param-
eters. Specifically, each parameter α
ij
is decomposed as a
product of two low-dimensional vectors, i.e., α
ij
= hv
i
, v
j
i,
where vectors v
i
and v
j
correspond to document i and j, re-
spectively. The learning process, thus, becomes to optimize
the modified dual form objective function with respect to
the low-dimensional vectors. Experimental results on three
LETOR datasets show that our method, referred to as Fac-
torized Ranking SVM, can outperform state-of-the-art base-
lines including the conventional Ranking SVM.
Categories and Subject Descriptors: H.3.3 [Informa-
tion Systems Applications]: Information Search and Re-
trieval – Retrieval Models
Keywords: Parameter interaction; Ranking SVM
∗
The work was conducted when Yaogong Zhang was visiting
CAS Key Lab of Network Data Science and Technology.
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full cita-
tion on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-
publish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from Permissions@acm.org.
CIKM’15, October 19–23, 2015, Melbourne, Australia.
c
2015 ACM. ISBN 978-1-4503-3794-6/15/10 ...$15.00.
DOI: http://dx.doi.org/10.1145/2806416.2806595.
1. INTRODUCTION
Learning to rank has been widely used in information
retrieval and recommender systems. Among the learning
to rank models, Ranking SVM is a representative pairwise
ranking model, evolving from the popular support vector
machines (SVM) [1] for classification problems. In training,
Ranking SVM first constructs the preference pairs of the
documents based on their relevance labels (or click-through
data [7]). Then, a binary SVM model is learned based on
the preference pairs to capture the differences between docu-
ments with different relevance labels. In ranking, each doc-
ument is assigned a relevance score based on the learned
ranking model. Usually, the ranking model can be writ-
ten in its dual form, the solution is a linear combination of
the training preference pairs, i.e., w =
P
(i,j)
α
ij
(x
i
− x
j
),
where x
i
and x
j
are the first and second document in the
pair (i, j), and α
ij
is the corresponding Lagrange multiplier.
It is obvious that the constructed preference pairs have
significant interactions, since two preference pairs could share
a same document as their items. In the dual form solution of
Ranking SVM, each preference pair is associated with a La-
grange multiplier α. Therefore, it is natural to ask whether
there also exist interactions among these Lagrange multipli-
ers. If the answer is yes, how to utilize the interactions to
improve Ranking SVM?
This paper tries to answer the above questions by analyz-
ing the Lagrange multipliers of the trained Ranking SVM
models. Specifically, we made an arrangement of the La-
grange multipliers and constructed a block diagonal matrix
A, where A(i, j) = α
ij
if α
ij
appears in the Ranking SVM
model and zero otherwise. Then, we performed singular
value decomposition (SVD) on each block of A and sorted
the eigenvalues in descending order. We found that for all
the queries, we just need 40% dimensions to capture 90%
energy, but if we want to capture 100% energy, almost all
the queries need at least 80% dimensions, it means there
exists a low-rank structure in the matrix, which indicates
strong interactions among the Lagrange multipliers.
Based on the discovery, we propose to improve the original
Ranking SVM through explicitly modeling the parameter
interactions in the training process. Specifically, we apply a
low rank constraint over the Lagrange multipliers in the dual
form solution of Ranking SVM. Each Lagrange multiplier
α
ij
in the dual form objective function is factorized as the
dot product of two K-dimensional latent vectors, i.e., α
ij
=
hv
i
, v
j
i, where v
i
and v
j
correspond to the first and second
document in the preference pair, respectively. In this way,
1799
下载后可阅读完整内容，剩余3页未读，立即下载
weixin_38611527
- 粉丝: 8
- 资源: 903
我的内容管理
展开
最新资源
- 深入理解23种设计模式
- 制作与调试：声控开关电路详解
- 腾讯2008年软件开发笔试题解析
- WebService开发指南：从入门到精通
- 栈数据结构实现的密码设置算法
- 提升逻辑与英语能力：揭秘IBM笔试核心词汇及题型
- SOPC技术探索：理论与实践
- 计算图中节点介数中心性的函数
- 电子元器件详解：电阻、电容、电感与传感器
- MIT经典：统计自然语言处理基础
- CMD命令大全详解与实用指南
- 数据结构复习重点：逻辑结构与存储结构
- ACM算法必读书籍推荐：权威指南与实战解析
- Ubuntu命令行与终端：从Shell到rxvt-unicode
- 深入理解VC_MFC编程：窗口、类、消息处理与绘图
- AT89S52单片机实现的温湿度智能检测与控制系统
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
