?

Learning to Rank之Ranking SVM 簡介

http://www.cnblogs.com/kemaswill/p/3241963.html

ranking svm主頁

http://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html

感謝博主CrazStone的辛苦工作！ 原文地址：

http://blog.csdn.net/sysu_stone/article/details/11022637

根據目前了解的跡象表明，RankSVM應該是T。T. Joachims. Optimizing search engines using clickthrough data. In KDD ’02:ACMSIGKDD.提出來的。后來O. Chapelle and S. Keerthi. Efficient algorithms for ranking with svms. Information Retrieval, 18, 2010. 提出primal SVM（PRSVM）,提高了運算效率，應用在document retrieval 中。Bryan et al.BMVC2013 提出Ensemble RankSVM解決memory consumption問題，并應用于Person re-identification.

?? 下面重點總結一下將RankSVM應用于Personre-identification問題。

?

??? 在傳統svm中是找到分類超平面使正負例的分類間隔最大化，在ranking問題中不存在絕對的正負例，而是要使得正確匹配的得分x_{s}^{+}大于錯誤匹配的得分x_{s}^{-}，即（x_{s}^{+}-x_{s}^{-}）>0,并且使得（x_{s}^{+}-x_{s}^{-}）最大化。

??? 定義查詢樣本x對于樣本xi匹配的得分x_{s}:? x_{s}=w^{T}|x-x_{i}| ; |x-x_{i}|表示每一維特征都對于相減，得到差值向量。

??? 在識別階段就是利用此公式將目標樣本進行排序。

??? 現在講怎樣通過訓練得到w^{T}，訓練集X={（xi，yi）}，i=1,2，……m；xi為特征向量，yi為+1或者-1。對于每一個訓練樣本xi，X中與xi匹配的正例樣本構成集合d_{i}^{+}=\left \{x_{i,1}^{+},x_{i,2}^{+}...x_{i,m^{+}}^{+}{}? \right \}；

X中與xi匹不配的負例樣本構成集合d_{i}^{-}=\left \{x_{i,1}^{-},x_{i,2}^{-}...x_{i,m^{-}}^{-}{}? \right \}；m^{+},m^{-}分別為正負樣本數量，存在關系m^{+}+m^{-}+1=m。

??? 歸納起來，就是對訓練樣本集中每個樣本xi，都存在若干正負例的score pairwise，把訓練集中所有score pairwise的集合用P表示，即P={（x_{s}^{+},x_{s}^{-}）},作為訓練階段的輸入;

??? 以上前提下的RankSVM就可得到如下形式：

???? MAX w^{T}(x_{s}^{+}-x_{s}^{-});

????? s.t.?w^{T}(x_{s}^{+}-x_{s}^{-})>0

即：min \frac{1}{2}\left \| w \right \|^{2}+C\sum_{s=1}^{\left | P \right |}\xi _{s}

?????s.t.?w^{T}(x_{s}^{+}-x_{s}^{-})\geq 1-\xi _{s}。

?

???? 以上就是RankSVM的基本思想，實際中由于訓練集的正負里數量都比較大時，會存在計算復雜度的問題。chapelle et al.2010提出無約束模型的PRSVM提高了計算效率：

w=\underset{w}{argmin}\frac{1}{2}\left \| w \right \|^{2}+C\sum_{s=1}^{\left | P \right |}\iota (0,1-w^{T}(x_{s}^{+}-x_{s}^{-})；

??? Prosser et al. 2011在此基礎上提出了 ensemble RankSVM,利用Boosting思想，將樣本集分成若干子集，分別訓練若類器weak RankSVMs: w_{i},通過學習不同weak RankSVMs的權值\alpha_{i},組合成最優RankSVM：

??? w_{opt}=\sum_{i}^{N}\alpha _{i}.w_{i}

? ?

總結

以上是生活随笔為你收集整理的RankSVM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。