1. 幂律分布無處不在
自然和社會中，許多事物的特征，其發生頻率遵循幂律分布（power law distribution）。幂律分布的密度函數是如圖所示的幂函數。幂律分布的特點是，20%的高頻特征的頻率大約占整體的80%，稱為頭部（head，圖中淺綠色部分）；另一方面，低頻特征的頻率逐漸減小，形成一個長長的尾部（tail，圖中黃色部分）。Zipf在語言學中，Pareto在經濟學中，最早研究了幂律分布，也被簡化為80/20規則。
幂律分布無處不在，有很多例子。若用80/20規則來描述，則成為以下現象。語言中，20%的常用詞彙占據80%的文章篇幅；社會中，20%的富裕階層擁有80%的财富；商業中，20%的優質客戶帶來80%的營業收入；蟻群中，20%的“勤奮”螞蟻承擔80%的工作；公司中，20%的核心員工創造80%的産值。注意這裡20%-80%隻是個近似，在具體執行個體中其比例會有不同。
2. 頭部的成功
近十年來，随着計算機處理能力的提高，海量資料得以收集、存儲、處理，大規模資料挖掘、大規模機器學習被廣泛應用的各個領域，給産業界帶來巨大變化。其中，使用者行為資料（user behavior data）是一種具有代表性的資料，被成功地利用到不同的産品、服務中。使用者行為資料也遵循幂律分布，其成功主要在于頭部資料利用的成功，如以下微軟Office産品與網際網路搜尋的例子所示。
2-1．微軟Office産品
微軟從Office 2007起對Office産品的使用者界面做了全面的更新；之前的菜單形式的工具欄被Ribbon形式的工具欄所替代。Ribbon中，功能按照使用者使用特點被分類。大家有沒有産生過這樣的疑問。為什麼粘貼（paste）被放在了Ribbon的最左邊？如上圖所示。其實這一設計是基于大規模使用者行為資料挖掘的 [1]。
Office産品在其發展過程中，遇到了很大的挑戰。一方面，使用者希望添加各種新功能；随着版本更新，新功能不斷增加，如上圖所示。另一方面，使用者又發現菜單變得越來越複雜，在系統中經常難于找到要找的功能。
從Office2003開始，微軟公司在争得許可的條件下，記錄并收集了部分使用者使用Office的行為資料。這些使用者使用Office時的操作，如菜單選項的點選，都會被記錄下來，并送到Office的資料中心。微軟進行了基于大規模資料挖掘的使用者界面設計，在Office 2007中推出了全新的Ribbon界面。資料挖掘結果發現，全球使用者中，最常用的指令是：paste, save, copy, undo, bold。這就是paste被放在最醒目的界面左上角的原因。
Ribbon界面得到了廣大使用者的支援，取得了很大成功，至少是部分解決了上述難題。使用者行為資料挖掘也為工業設計開辟了一條新路。産品功能的使用頻率也是符合幂律分布的；可以說，Ribbon界面僅僅有效地利用了頭部資料，并未觸及尾部資料的使用。
2-2. 網際網路搜尋
網際網路搜尋在近十幾年裡經曆了兩次大的技術革新。第一次以錨文本（anchor text）的使用和PageRank算法為代表，第二次以日志資料挖掘（log data mining）為代表。而日志資料就是搜尋引擎記錄的使用者搜尋行為資料。兩次技術革新都使搜尋引擎的相關排序（relevance ranking）結果有了很大的提高。下面介紹第二次技術革新的兩個例子：點選資料（click through data）的使用與BrowseRank算法。
使用者搜尋的每次查詢，包括查詢語句、點選網頁的URL等都會被搜尋引擎記錄下來。将一段時間内的所有查詢彙總，就會得到點選資料。點選資料表示，對每個查詢語句，使用者在搜尋結果中點選URL的次數。以上兩圖顯示在Bing的日志資料中得到的關于查詢“microsoft”與“machine learning”的點選資料。對查詢“microsoft”，microsoft.com的點選次數最多,有27萬以上；相反,有1萬個URL其點選次數僅為1。對查詢“machine learning”，點選最多的URL其點選次數有1千多；相反，有近1百個URL其點選次數僅為1。可以看出，點選資料是符合幂律分布的。
頭部查詢（高頻查詢），往往有豐富的點選資料，成為搜尋引擎的寶貴資源。它告訴搜尋引擎，針對每個查詢，使用者最想要什麼結果，結果的排序是什麼。事實上，現在的搜尋引擎都在不同程度上使用點選資料，特别是頭部點選資料。但是，大部分查詢屬于尾部查詢（低頻查詢），其點選資料極其稀少，比如隻有一兩次，可信度較低。是以尾部資料不能簡單地直接使用。如何有效地利用尾部點選資料成為網際網路搜尋的一個重要課題。
BrowseRank是我們開發的一個網頁重要度的算法[2]。網頁重要度是網頁相關度排序的一個重要特征，搜尋引擎一般将相關度與重要度都高的網頁排在前面。
傳統的網頁重要度算法是PageRank。直覺上，有許多連結指向的網頁重要，網頁的重要度通過連結可以在網上傳播；PageRank用馬爾可夫模型實作這一直覺。具體地，PageRank将網際網路當作一個有向圖，在有向圖上定義馬爾可夫過程，通過馬爾可夫過程中的随機遊動（random walk）實作網頁重要度的傳播。最後，PageRank用馬爾可夫過程的平穩分布表示網頁的重要度。
可以認為BrowseRank是PageRank的擴充。BrowseRank首先根據使用者行為資料建構使用者浏覽圖。圖上的結點表示網頁，邊表示使用者在網頁間的轉移。結點上記錄了使用者在網頁上的平均停留時間，邊上記錄了使用者在網頁間轉移的次數。BrowseRank然後再在使用者浏覽圖上定義連續時間馬爾可夫過程，用其平穩分布表示網頁的重要度。直覺上，使用者在網頁上平均停留時間越長，網頁就越重要；被指向的邊越多，且邊上的轉移次數越高，網頁就越重要。PageRank基于離散時間馬爾可夫過程，是以是BrowseRank的特殊情況。
BrowseRank通過使用者行為資料計算網頁重要度，與PageRank成互補關系，是一個有效的算法。它對頭部網頁（熱門網頁）的重要度計算可以很準确，而對尾部網頁（冷門網頁）的重要度計算卻常常是鞭長莫及的。在這一點上PageRank也是一樣的。
3. 長尾挑戰
網際網路搜尋主要還是基于關鍵字比對。尾部查詢（低頻查詢）是不容易做好的，因為沒有足夠多的信号（signal），包括錨文本與點選資料。這時，查詢語句與網頁不能有很好的比對，搜尋引擎常常無法做出正确的相關度判斷。比如，查詢語句是“zhongguanchun swimming pool schedule”，網頁隻含有“zhongguanchun pool schedule”。由于swimming一詞沒有出現在網頁中，如果這個網頁沒有錨文本與點選資料，就不容易準确地判斷它們之間的相關度；很有可能這個網頁不會被找到，或排在前面。
Goel等對使用者搜尋，以及其他資訊通路的需求做了研究[3]。他們發現，使用者需求的分布呈幂律分布，每個使用者都有頭部的需求（熱門需求）與尾部的需求（冷門需求）。有些使用者頭部的需求多一些，有些使用者尾部的需求多一些。是以，網際網路搜尋中僅把容易做的頭部查詢做好是不足以滿足絕大多數使用者需求的。
網際網路搜尋中，提供高品質的尾部查詢服務能夠極大提高使用者的滿意度。網際網路搜尋引擎，不但應做好頭部查詢，而且應做好尾部查詢，使使用者無論找什麼東西都能很快、很全、很準地找到。做好尾部查詢是網際網路搜尋不可回避的，需要不斷努力的目标。長尾挑戰不僅在網際網路搜尋中，在其他産品、服務中也都存在。
4. 可能的解決途徑
4-1．康德哲學的啟示
怎樣讓計算機克服長尾挑戰呢？我們可以看一看人是如何擁有知識，如何做智能性活動的。
現在我們普遍認為人的知識是由先天的能力與後天的實踐相結合産生的。有大量的證據可以證明這一點。但是人類達到這一認識是從十八世紀康德開始的。在他之前有理性主義與經驗主義之争。前者的代表有笛卡兒、斯賓諾莎、萊布尼茲，後者的代表有培根、洛克、休谟。理性主義認為理性是人的知識的基礎，是普遍的、生來就有的。笛卡爾說：“在這個世界上，良知是被配置設定得最為公平的東西”（Good sense is of all things in the world the most equally distributed）。相反，經驗主義認為人的知識是通過實踐得來的。理性主義很難解釋為什麼人可以通過實踐獲得新知識，經驗主義很難解釋為什麼人的知識會有普遍性。康德站在理性主義的立場上，提出了将理性主義與經驗主義結合的想法，即，知識是基于先天的能力通過後天的實踐得到的。隻有這樣看待這個問題，才能将理性主義與經驗主義的沖突同時解決。
人在學習中并不會感受到長尾現象的困擾。從康德的觀點來看，這是因為人有一定的先驗知識。是以，要讓計算機戰勝長尾挑戰就需要将更多的先驗知識賦予計算機。這或許是解決長尾問題的唯一途經。
4-2．網際網路搜尋中的嘗試
近年來，我和同僚們一直從事網際網路相關排序的研究，重點是提高尾部查詢的相關排序精度。我們開發了一系列新算法，其核心想法是，針對查詢語句與網頁比對，假設頭部與尾部遵循同樣的規律，從頭部資料學習知識，并将這些知識推廣到尾部資料。下面介紹一個例子[4]，其它可參見[5，6]。
據統計，有10%-15%的英文查詢語句含有拼寫錯誤。查詢語句中的拼寫錯誤自動糾正是網際網路搜尋的一個重要研究課題。我們提出了一個新的機器學習算法，能夠很好地解決這個問題[4]。這個方法首先從搜尋日志資料中自動找出使用者輸入的拼寫錯誤及其糾正。使用者經常會輸入含有拼寫錯誤的查詢語句，但有時會馬上對其糾正，如先輸入nicrosoft，之後改為microsoft。從日志資料中可以發現大量的此類資料；當然它們都是頭部資料。我們的方法從這些資料中自動找出大量的拼寫轉換規則，比如，ni到mi，shi到si，并自動學習轉換規則的權值，建構一個拼錯糾正模型。轉換規則雖然是從頭部學到的，但它們具有普遍性，在尾部也适用。比如，可以用于從ninecraft到minecraft的拼寫錯誤糾正。這樣，就可以将從頭部學到的知識推廣到尾部。
5．總結
長尾問題是機器學習、資料挖掘需要解決的重大問題之一。可能的解決途徑是将先驗知識與機器學習相結合；目前已有一些嘗試，取得了一些進展。但是，如何将更多的先驗知識加入計算機中，如何在計算機中表示先驗知識，如何将先驗知識融合到機器學習，在我們面前，還有許多待解的難題。
本文由11月14日複旦大學講演整理而成。
緻謝
廖振同學幫助生成文中點選資料，在此表示感謝。
參考文獻
[1] Jensen Harris: An Office User Interface Blog, http://blogs.msdn.com/b/jensenh/archive/tags/why+the+new+ui_3f00_/default.aspx
[2] Yuting Liu, Bin Gao, Tie-Yan Liu, Ying Zhang, Zhiming Ma, Shuyuan He, Hang Li. BrowseRank: Letting Users Vote for Page Importance, In Proceedings of the 31st Annual International ACM SIGIR Conference (SIGIR’08), pages 451-458, 2008. (SIGIR’08 Best Student Paper Award).
[3] Sharad Goel, Andrei Z. Broder, Evgeniy Gabrilovich, Bo Pang: Anatomy of the long tail: ordinary people with extraordinary tastes. WSDM 2010: 201-210.
[4] Ziqi Wang, Gu Xu, Hang Li and Ming Zhang, A Fast and Accurate Method for Approximate String Search, In Proceedings of the 49th Annual Meeting of Association for Computational Linguistics: Human Language Technologies (ACL-HLT’11), 52-61, 2011.
[5] Jingfang Xu, Gu Xu, Learning similarity function for rare queries. WSDM 2011: 615-624.
[6] Wei Wu, Hang Li, and Jun Xu, Learning Query and Document Similarities from Click-through Bipartite Graph with Metadata, Microsoft Research Technical Report, MSR-TR-2011-126, 2011.