學(xué)會排序

很多人都聽說過大名鼎鼎的PageRank算法，它能夠自動判斷網(wǎng)頁的重要性，也是決定搜索結(jié)果排序的關(guān)鍵因素之一。但在很多時候，僅僅憑重要性遠遠無法完成一項排序。計算機和我們都有很多東西需要學(xué)習(xí)。

日常生活中存在多種多樣的排序。我們最熟悉的，比如娛樂圈里的“超女”、“快男”，體育界的各項賽事，在學(xué)校里經(jīng)常會碰到的成績排名等等。而在計算機領(lǐng)域內(nèi)，一個最典型和最熱門的例子，恐怕就是排序在搜索引擎中的應(yīng)用了。赫赫有名的PageRank算法，就構(gòu)建了一套巧妙的機制和排序模型，來自動判斷網(wǎng)頁的重要性，并也成為Google的搜索引擎賴以成名的利器之一。

也恰恰是由于人們逐漸意識到排序問題至于搜索引擎效率的重要性，所以最近幾年，整個學(xué)術(shù)界對排序的認識也在迅速提升高度，大家都希望可以非常正規(guī)的把排序當做一個學(xué)術(shù)問題來進行研究，并最終形成一個完整的理論體系。可以說，排序已經(jīng)成為了機器學(xué)習(xí)領(lǐng)域內(nèi)一個最新的分支。

就像該領(lǐng)域內(nèi)的分類、回歸、聚類等其他一些已經(jīng)被研究得很透徹的問題一樣，排序到底應(yīng)該如何界定?存在什么樣的特性?有什么理論的知識蘊含其中?如何通過機器學(xué)習(xí)來自動的構(gòu)建出排序模型?

微軟亞洲研究院(MSRA)大概在三年前開始了有關(guān)“排序?qū)W習(xí)”(Learning to Rank)的研究。2007年，MSRA一篇名為《Learning to Rank: From Pairwise Approach to Listwise Approach》發(fā)表，在整個學(xué)術(shù)界引起了強烈反響。據(jù)專門負責此課題的主任研究員李航博士介紹，這也和信息爆炸時代有一定的關(guān)系，用戶面前的信息量太大，“很多東西都會希望有一個排個序，搜索是最典型的例子，以此來幫助他們?nèi)ピL問到最想要的信息?！?/p>

“其實排序是一種關(guān)系的表現(xiàn)，不像以前比如分類、回歸是一個物體或一個對象本身的屬性，”和李航一起做該課題研究的劉鐵巖博士告訴記者，“以前說一個網(wǎng)頁，它到底是講新聞還是講體育的?其實是個絕對的事，拿到這個網(wǎng)頁一切都知道了，是它的本身的屬性。但排序是指這一個網(wǎng)頁跟別的網(wǎng)頁之間比較的一種關(guān)系。比如以前可以叫做一元學(xué)習(xí)，那么現(xiàn)在則是一個更高元的、更高階的一個問題?！?/p>

李航覺得，這一點對整個傳統(tǒng)的機器學(xué)習(xí)都是一個很大的挑戰(zhàn)。因為按傳統(tǒng)觀點，會存在一些基本假設(shè)，每個樣本背后都是同樣一個規(guī)律在控制。但是對于排序，“其實我們想要挖掘的是要滿足對象之間的那種關(guān)系，這就不能用以前那種假設(shè)去看待了，至少在某種情況下，已經(jīng)不完全成立了，所以會有一些新的理論和實踐要發(fā)生”。

與之前的“Pairwise”不同的是，李航和劉鐵巖他們所提出的新研究方法“Listwise”是基于一個列表的學(xué)習(xí)，也就是以一個列表為基本的學(xué)習(xí)單元，“因為一個列表本身就包含了一些排了序的文檔，某些關(guān)系已經(jīng)嵌在這樣的表達方式里?！眲㈣F巖說，“所以我們不需要像以前研究時的那種假設(shè)，文檔之間會有相對大小的關(guān)系，這些都已經(jīng)在我們學(xué)習(xí)單元里面了，這使得基于此的一些理論和實踐都會比較順暢，和以前有較大不同?！?/p>

Listwise方法之所以受到關(guān)注，是因為在評價排序結(jié)果好壞的時候，它把查詢詞對應(yīng)的所有文檔通盤考慮，全局衡量，而以前的工作把目光中在單個文檔或者一對文檔之上；而且可以對文檔之間的關(guān)系，如相似度等進行建模，因此可以定義更加有效的排序函數(shù)；另外，由于是列表級別，它可以充分利用文檔在列表中的位置信息，因此可以更加強調(diào)排在前面的文檔，而這與用戶的體驗更加一致。

回到搜索，李航說，“排序?qū)W習(xí)”這個研究更多的是關(guān)心算法，以及排序模型的構(gòu)建。比如在互聯(lián)網(wǎng)搜索的時候，網(wǎng)頁的重要度是一個重要的特征，但也要考慮關(guān)聯(lián)度；只有重要度和相關(guān)度可能也不夠，還要考慮其他的一些因素。網(wǎng)絡(luò)搜索發(fā)展到今天，人們已經(jīng)慢慢意識到，有太多的因素會影響到排序，把這些因素視作特征用一些方法綜合考慮得出一個最合理的排序，這是Learning to Rank要解決的問題。