關於極限分類,這裡有你想知道的一切

雷鋒網 AI 科技評論按,在一個搜索已經無處不在的世界裡,我們大多數人都有過對搜索結果不滿意的體驗。如果你的初始查詢不返回你想要的結果,你會怎麼辦?當然,你可以瀏覽當前的前 1 億個查詢的列表,假設你只需要一秒鐘就可以閱讀一個查詢,這一過程將花費你三年的時間。

說真的,誰有這麼多時間來幫我收集數據?

幸運的是,微軟的一個團隊決定在這些非常真實和具有挑戰性的問題上進行創新性的嘗試。事實上,他們的解決方案在墨爾本舉行的第 12 屆 ACM 網絡搜索和數據挖掘國際會議(WSDM 2019)上引起了軒然大波,該解決方案表明上述任務可以在數毫秒內完成。雷鋒網 AI 科技評論將他們的博文編譯整理如下。

微軟印度研究院(Microsoft Research India)首席研究員 Manik Varma 解釋說:「多標籤分類是一門構建算法的科學,它可以回答涉及不確定性的多項選擇問題,而這些問題可能有多個正確的答案。」Varma 把這個問題比作從一家餐館的菜單中點一頓家庭餐,你需要確定在給定的預算內,選擇菜單中的哪些菜最令人滿意。與傳統的多分類相比,這可能是一個更難解決的問題,因為在傳統的多分類中,人們只需要從菜單中選擇一道菜。因此,儘管進行了幾十年的研究,計算機科學家只能解決涉及少量選擇的問題,將搜索引擎上的查詢建議作為一項多標籤分類任務來考慮甚至是一個沒有希望實現的課題。

「5 年前,多標籤算法幾乎無法擴展到涉及 5000 個選擇的問題,」談到極限分類,Himanshu Jain 回憶道,他是前面提到的那篇 WSDM 論文的合著者,也是印度理工學院 Varma 的博士生,曾在微軟實習。2013 年,Varma 的團隊發表了一篇論文,將可以考慮的選擇數量爆炸性地從 5000 提升到 1000 萬。這改變了遊戲的本質,並促使了機器學習中一個新的研究領域——極限分類的出現。極限分類處理涉及大量選擇的多分類和多標籤問題。從那時起,極限分類為排名和推薦應用程序開創了一個新的樣式,例如搜索引擎會推薦相關的查詢。

Varma 解釋說:「當選擇從一千個變為一百萬個時,好答案的標準就發生了變化。不幸的是,世界上沒有一個人類專家能夠通過一個 1000 萬個選項的列表來找出所有正確的答案。」事實上,許多新的研究問題都出現在這種規模上,而機器學習界並沒有傳統地看待這一問題,每個問題只有部分答案以極限的規模存在,因此即使是最基本的機器學習技術(如交叉驗證)也有可能出錯。這些新的研究問題,加上高影響力的排名和推薦應用,使極限分類成為學術界和工業界的熱門研究方向。在過去的六年裡,極限分類的研究取得了顯著的進步。Varma 觀察到,關於極限分類的論文已在各種會議上發表,包括 AAAI, AISTATS, ICML, IJCAI, KDD, NIPS, SIGIR, WSDM, WWW 等,基準任務的預測精度從 2013 年的 19% 提高到今天的 65%。

遺憾的是,極限分類的技術挑戰不僅在於提高預測精度,還需要減少訓練時間、預測時間和模型大小。訓練分類器所需的時間是極限分類中最大的問題之一。Varma 解釋說,2013 年,他們在和維基百科大小差不多的數據集上,對他們基於樹的極限分類器 MLRF 在 1000 個核心集群上進行訓練,花了 7 個小時,這種速度在 Bing 的規模上簡直是不可接受的,因此必須開發一種新的算法。

他們決定稱這種算法為 Slice

算法的工作原理

Slice 代表可擴展的線性極限分類器,它可以比 MLRF 快一萬倍以上。該算法能夠準確有效地擴展到涉及 1 億個標籤和 2.4 億個訓練點的問題,為世界上所有其他分類器的擴展能力打開了一個新的大門。Slice 為每個標籤學習一個線性分類器,但在標籤數量上減少了從線性到對數的訓練和預測成本。只有少數標籤(比如對數標籤)在任何給定的特徵空間區域中都是活動的,它的實現正是利用了這一點。在給定測試點的情況下,基於近似最近鄰搜索,快速確定所屬特徵空間的區域。然後,它只評估該區域中活動標籤的分類器,這一過程會產生對數預測成本。在訓練過程中,如果 D 維中有 N 個帶 L 標籤的點,slice 通過只訓練最難的負示例(時間複雜度 O((n log l)/L))而不是所有(時間複雜度 O(n))負樣本,將訓練成本從 O(NDL) 降低到 O(ND log L)。這是通過一種新的基於近似識別線性分類器生成模型的負採樣技術實現的。這項技術對於低維深度學習尤其有效,因為它可以有效地從數億個點上對幾百個最難的樣本進行分類,而不會損失精度。雷鋒網

這複雜嗎?

複雜。

值得嗎?

值得。

極限分類為排名和推薦問題創建了一個新的範例。通過將每個項目作為單獨的標籤進行排名或推薦,我們可以學習一個極限分類器,它以用戶的特徵向量為輸入,預測相關標籤的子集作為輸出,然後根據應用程序將與預測標籤相對應的項目作為推薦包或排名列表返回給用戶。在某些情況下,這種方法的結果相比傳統的方法會有很大的改善。

在 Bing 搜索引擎上再次執行上述推薦相關查詢的任務。你可以將 Bing 上的前 1 億個查詢都視為單獨的標籤,以用戶查詢為輸入,並預測 1 億個標籤(查詢)的相關子集作為輸出,這是對你的查詢問題的一種極限分類重新表述。

通過這種方式處理問題,Bing 可以提出更相關的建議,並將查詢的成功率提高 12%,從而使數百萬用戶能夠更高效地找到想要的答案。

「我第一次聽到 Manik 關於極限分類的演講是在幾年前,當時,我花了一段時間才明白他想做什麼。這是一種全新的看待多標籤分類的方法,其效率以及模型大小是該方法不可能奏效的原因之一。多年來,Manik 和他的合作者已經取得了巨大的進步,他們為機器學習開創了一個子領域。頂級的 ML 會議現在有關於極限分類的專題研討。我認為這項研究將繼續對科學界產生影響。這是一個很好的例子,它展示了持續的研究如何使不可能的事情成為可能。」——微軟印度研究院總經理 Sriram Rajamani。

除了搜索和信息檢索,極限分類還可以應用於計算廣告、推薦系統、計算機視覺甚至自然語言處理。例如,你可以使用極限分類來預測下一個將在 Bing 上鍵入的單詞是什麼。或者,你可以用它來識別你在會議上遇到的陌生人。或者,你甚至可以用它來推薦下一個你應該聽的音樂曲目。當然,世界上數百萬人已經受益於極限分類法,通過 Bing 廣告系統,他們能更有效地找到和購買他們正在尋找的商品和服務。

極限分類目前應用非常廣泛。它開啟了研究的新前景,並迴避了問題:還有什麼其他的問題可以被重新定義為極限分類問題,我們現在有更好的解決辦法嗎?

via:https://www.microsoft.com/en-us/research/blog/everything-you-always-wanted-to-know-about-extreme-classification-but-were-afraid-to-ask/


想在手機閱讀更多Microsoft資訊?下載【香港矽谷】Android應用
分享到Facebook
技術平台: Nasthon Systems