[發(fā)明專利]使用多嵌套排序來改善排序結果

有效

• 申請?zhí)枺?/td>: 200680045523.1
• 申請日: 2006-11-17
• 公開（公告）號: CN101322125A
• 公開（公告）日: 2008-12-10
• 發(fā)明（設計）人: C·J·博格斯;I·瑪特維娃;L·W·翁;A·S·拉魯夏斯;T·伯卡德
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q90/00
• 代理公司: 上海專利商標事務所有限公司
• 代理人: 陳斌

背景

搜索對計算機用戶而言已經變?yōu)閼贸绦蚝筒僮飨到y的重要特征。甚至， 它成為計算機市場上高度有利可圖的部分。一方面，廣告客戶購買關鍵詞和/ 或當遇到某些搜索項時對期望的列出位置支付額外費用。另一方面，消費者主 要關注搜索的質量，且通常基于其以往的性能和聲譽來選擇搜索應用程序或引 擎。

更通常地，用戶啟動文本搜索來在因特網、其網絡或其本地PC上查找特 定內容。搜索請求可按照各種格式提交。取決于他/她正在尋找的內容和搜索的 位置，用戶可使用關鍵詞、短語或詞語的任何組合。搜索引擎的任務是檢索與 用戶查詢相關的文檔。當存在與相同或類似項相關的若干文檔時，必須有某種 適當的技術來以反映其與查詢和用戶的相關性程度的次序將其呈現給用戶。因 此，對檢索出的文檔排序可能是信息檢索中最有挑戰(zhàn)性的任務。由于大多數用 戶一般僅查看列表(由搜索引擎返回)頂部的前幾個結果，因此對這些結果實 現高準確度變?yōu)槿找嬷匾?

常規(guī)排序系統繼續(xù)努力來產生良好的排序但仍有問題。這部分是由于可響 應于查詢而返回的文檔的巨大數目。為了正確地看待這個問題，當前在因特網 或Web上大約有250億個文檔(例如，網站、圖像、URL)。因此，響應于 任何一個查詢返回數千(如果不是數百萬)文檔上可行的。盡管當前的排序系 統作出了對這樣大量文檔準確排序的嘗試，但頂部的幾個結果仍可能不是與查 詢和/或用戶最相關的。這是由于若干原因產生的。一個原因可能是因為這樣的 常規(guī)排序系統可能嘗試以排序較高的結果為代價來提高低排序結果，可能會降 低頂部返回的結果的相關性。第二個可能的原因可能是使用單個排序算法來解 決整個問題(對所有可能的查詢)可能限制過多。因此，仍需要改善檢索出的 項目的排序同時最小化排序系統性能的花費。

概述

以下呈現了簡化概述，以提供對此處所述的系統和/或方法的某些方面的 基本理解。本概述不是對此處所述的系統和/或方法的概觀。它并非旨在標識關 鍵/重要元素，也非旨在描繪這樣的系統和/或方法的范圍。其概述的唯一目的 是以一種簡化的形式來介紹一些概念，作為稍后呈現的更為詳細的描述的序 言。

本申請涉及一種便于改善排序結果的系統和/或方法。具體地，該系統和 方法應用多個嵌套級的排序技術以對之前排序的項目的子集重新排序。可按此 方式采用不同的排序技術，但是為了討論并為簡明起見，此處將討論一種排序 技術。

本系統和方法涉及將排序任務分成多級，其中對高或較高排序的項目的遞 減子集應用排序技術。假定排序技術采用被訓練來對項目排序的神經網絡。可 對信息的較小集合訓練多個網絡以產生向用戶呈現的更相關的前幾個項目。例 如，想象用戶向搜索組件提交了查詢。搜索組件可針對給定查詢檢索超過一百 萬個項目，其中項目可對應于文檔、文件、圖像或URL。可訓練第一神經網絡 來對該項目的初始集定序或排序。從排序項目的初始集中取前幾個(例如，前 2500個)結果，并訓練可用于對其重新定序的第二神經網絡。可使用修改后的 項目集合——在此示例中為前2500個項目——訓練第二神經網絡。之后，可 經由第二神經網絡對這2500個項目重新排序。從這重新排序的2500個項目中， 取得高排序項目(例如，前1000個)的更小的子集，并訓練第三神經網絡以 隨后對其重新定序。在前1000個被重新排序之后，可使用排序在頂部的項目 的更小的子集以訓練另一網絡——例如前100個。前100個可按類似方式重新 排序，以產生前10個項目，這前10個項目也可被重新排序。總的效果是在分 開的級中對前2500個結果重新排序，這有效地提高了搜索組件的總體排序性 能。大多數用戶僅審閱針對給定查詢發(fā)回的前幾個結果。通過使用以上系統和 方法，可對前幾個結果重復地重新排序以改善其相關性和排序次序。因使用這 樣的分級系統而得到的改善可部分地源自在每一級，在該級使用的學習機器僅 必須學習正在解決的總排序問題的小的子問題的事實。分級系統的第二個優(yōu)點 是由于對某些應用(諸如，Web搜索)結果必須實時返回的事實。因此，如果 僅使用單個算法來執(zhí)行排序，則該算法必須非常快。然而，在分級方法中，每 一問題涉及少得多的數據，且因此可在每一級應用更復雜(且更慢)的排序方 法。