title:learning to rank
date:2014-09-12
category:機(jī)器學(xué)習(xí)
歷史階段
- Optimizing search engines using clickthrough data, T Joachims, KDD 02——ranksvm的提出。
- Efficient algorithms for ranking with SVMs, O Chapelle——提出primal SVM提升效率斤吐。
- Person Re-Identification by Support Vector Ranking, BMVC2010——提出Ensemble RankSVM解決memory consumption問題和措。
svm算法描述
svm求解的目標(biāo)是能夠正確劃分?jǐn)?shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面蜕煌， 與感知機(jī)的求解誤分類最小的策略有所不同。我們這里僅以線性svm為例進(jìn)行介紹颁褂。
對于超平面(w, b), 樣本點(diǎn)$(x_i, y_i)$, 幾何間隔定義為：
$\gamma_i = y_i (\frac{w}{||w||} \cdot x_i + \frac傀广{||w||})$
超平面(w, b)對于訓(xùn)練數(shù)據(jù)集T的幾何間隔定義為：
$\gamma = min(\gamma_i)$
幾何間隔最大化直觀的解釋是伪冰，以充分大的確信度對訓(xùn)練數(shù)據(jù)進(jìn)行分類， 也就是說靠柑， 不僅能將正負(fù)實(shí)例點(diǎn)分開歼冰， 而且對最難分的實(shí)例點(diǎn)（離超平面最近的點(diǎn)）也有足夠大的確定度將它們分開耻警， 這樣的超平面對未知的新實(shí)例有很好的分類與猜測能力。
具體的腮恩， 這個(gè)問題可以表述為：
$max \ \gamma$
$s.t. y_i (\frac{w}{||w||} \cdot x_i + \frac温兼{||w||}) \ge \gamma$
經(jīng)過變化后， 問題等價(jià)位求如下的最優(yōu)化問題：
$min \frac {1}{2}||w||^2$
$s.t. y_i(w \cdot xi + b) - 1 \ge 0$
現(xiàn)實(shí)中的問題很少能完全做到線性可分荡含， 必然存在一些奇異點(diǎn)的干擾， 我們對每個(gè)樣本點(diǎn)引進(jìn)一個(gè)松弛變量$\xi$, 相應(yīng)的钧排， 問題等價(jià)為：
$min \frac{1}{2}||w||^2 + C\sum{\xi}$
$s.t. y_i(w \cdot xi + b) \ge 1 - \xi$
ranksvm算法描述
如上所述均澳，在svm中是要找到分類超平面使正負(fù)例的幾何間隔最大化，在ranking問題中不存在絕對的正負(fù)例糟袁，而是要使得正確匹配的得分$x_{s}{+}$大于錯(cuò)誤匹配的得分$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}|$表示每一維特征都對應(yīng)相減，得到差值向量仿耽，預(yù)測階段基于差值做出預(yù)測和排序项贺。
訓(xùn)練過程
為了獲得$w^{T}$峭判，我們定義：
- 訓(xùn)練集$X={（xi，yi）}林螃，i=1,2治宣，……m；$
- $xi$為特征向量
- yi為+1或者-1
- 對于每一個(gè)訓(xùn)練樣本xi，X中與xi匹配的正例樣本構(gòu)成集合$d_{i}^{+} = \lbrace x_{i,1}{+},x_{i,2}{+}...x_{i,m{+}}{+} \rbrace$
- X中與xi匹不配的負(fù)例樣本構(gòu)成集合$d_{i}^{-}= \lbrace x_{i,1}{-},x_{i,2}{-}...x_{i,m}^{-} \rbrace绊茧；m{+},m{-}$分別為正負(fù)樣本數(shù)量打掘，存在關(guān)系$m{+}+m{-}=m$。
歸納起來亡笑，就是對訓(xùn)練樣本集中每個(gè)樣本xi，都存在若干正負(fù)例的score pairwise百拓，把訓(xùn)練集中所有score pairwise的集合用P表示晰甚，即$P={（x_{s}{+},x_{s}{-}）}$,作為訓(xùn)練階段的輸入;
綜合之前講述的svm最優(yōu)化表述厕九，RankSVM就可得到如下形式：
$ MAX w{T}(x_{s}{+}-x_{s}^{-}); $
$s.t. w{T}(x_{s}{+}-x_{s}^{-})>0$
即：
$ min \frac{1}{2}||w||^{2}+C\sum\xi _{s} $
$ s.t. w{T}(x_{s}{+}-x_{s}^{-})\geq 1-\xi _{s}。 $
以上就是RankSVM的基本思想俊鱼，ranksvm目前廣泛用于pair wise的訓(xùn)練方式畅买。
優(yōu)化
在實(shí)際應(yīng)用中， postive和negative的數(shù)量都比較巨大的情況下焙蚓， ranksvm幾乎不可用购公， 按照工業(yè)界以能夠處理所有的數(shù)據(jù)優(yōu)先于設(shè)計(jì)精巧的模型原則雁歌， 我們修改了ranksvm的loss，使得他做到線性的復(fù)雜度靠瞎。
PairWise Loss:
$ L_{rank} (f;S) = \frac {1} {mn} \sum_{j=1}{m}\sum_{i=1}{n} 1{\hskip -2.5 pt}\hbox{I}(f(x_i)^+ \le (f(x_j^-)) $Down Sampling PairWise Loss:
$ L_{rank} (f;S) = \frac {1} {n} \sum_{i=1}^{n} 1{\hskip -2.5 pt}\hbox{I}(f(x_i)^+ \le rand(f(x^-)) $
通過這種方式， 能將復(fù)雜度從 $ 2 \cdot n \cdot m $ 下降到 $2 \cdot n$佳窑。
同時(shí)在實(shí)踐中表明， 由于能夠處理的數(shù)據(jù)樣本數(shù)目和維度大大提升父能， down sampling的方式表現(xiàn)優(yōu)于標(biāo)準(zhǔn)的ranksvm神凑。
tips
- L1范數(shù): ||x|| 為x向量各個(gè)元素絕對值之和溉委。公式：$|X|=\sum{|x_i|}$
- L2范數(shù): ||x||為x向量各個(gè)元素平方和的1/2次方瓣喊，L2范數(shù)又稱Euclidean范數(shù)或者Frobenius范數(shù)。公式：$||X||=\sqrt{\sum{x_i^2}})$
- 幾何間隔：
- 樣本點(diǎn)幾何間隔：超平面(w, b)和樣本點(diǎn)(xi, yi)的距離$|w \cdot x_i + b|$表示分類預(yù)測的確信程度洪橘， 而$w \cdot x_i + b$符號(hào)是否一致表示了分類是否正確趴酣， 做歸一化之后表示為：$\gamma_i = y_i (\frac{w}{||w||} \cdot x_i + \frac岖寞{||w||})$
- 平面幾何間隔： 超平面(w, b)關(guān)于訓(xùn)練數(shù)據(jù)集T的幾何間隔定義為： $\gamma = min(\gamma_i)$
- 支持向量：樣本點(diǎn)中與超平面距離最近的點(diǎn)仗谆。
