0
雷鋒網(wǎng) AI 科技評論按，在一個搜索已經(jīng)無處不在的世界里，我們大多數(shù)人都有過對搜索結(jié)果不滿意的體驗(yàn)。如果你的初始查詢不返回你想要的結(jié)果，你會怎么辦？當(dāng)然，你可以瀏覽當(dāng)前的前 1 億個查詢的列表，假設(shè)你只需要一秒鐘就可以閱讀一個查詢，這一過程將花費(fèi)你三年的時(shí)間。
說真的，誰有這么多時(shí)間來幫我收集數(shù)據(jù)？
幸運(yùn)的是，微軟的一個團(tuán)隊(duì)決定在這些非常真實(shí)和具有挑戰(zhàn)性的問題上進(jìn)行創(chuàng)新性的嘗試。事實(shí)上，他們的解決方案在墨爾本舉行的第 12 屆 ACM 網(wǎng)絡(luò)搜索和數(shù)據(jù)挖掘國際會議（WSDM 2019）上引起了軒然大波，該解決方案表明上述任務(wù)可以在數(shù)毫秒內(nèi)完成。雷鋒網(wǎng) AI 科技評論將他們的博文編譯整理如下。
微軟印度研究院（Microsoft Research India）首席研究員 Manik Varma 解釋說：「多標(biāo)簽分類是一門構(gòu)建算法的科學(xué)，它可以回答涉及不確定性的多項(xiàng)選擇問題，而這些問題可能有多個正確的答案?！筕arma 把這個問題比作從一家餐館的菜單中點(diǎn)一頓家庭餐，你需要確定在給定的預(yù)算內(nèi)，選擇菜單中的哪些菜最令人滿意。與傳統(tǒng)的多分類相比，這可能是一個更難解決的問題，因?yàn)樵趥鹘y(tǒng)的多分類中，人們只需要從菜單中選擇一道菜。因此，盡管進(jìn)行了幾十年的研究，計(jì)算機(jī)科學(xué)家只能解決涉及少量選擇的問題，將搜索引擎上的查詢建議作為一項(xiàng)多標(biāo)簽分類任務(wù)來考慮甚至是一個沒有希望實(shí)現(xiàn)的課題。
「5 年前，多標(biāo)簽算法幾乎無法擴(kuò)展到涉及 5000 個選擇的問題，」談到極限分類，Himanshu Jain 回憶道，他是前面提到的那篇 WSDM 論文的合著者，也是印度理工學(xué)院 Varma 的博士生，曾在微軟實(shí)習(xí)。2013 年，Varma 的團(tuán)隊(duì)發(fā)表了一篇論文，將可以考慮的選擇數(shù)量爆炸性地從 5000 提升到 1000 萬。這改變了游戲的本質(zhì)，并促使了機(jī)器學(xué)習(xí)中一個新的研究領(lǐng)域——極限分類的出現(xiàn)。極限分類處理涉及大量選擇的多分類和多標(biāo)簽問題。從那時(shí)起，極限分類為排名和推薦應(yīng)用程序開創(chuàng)了一個新的樣式，例如搜索引擎會推薦相關(guān)的查詢。
Varma 解釋說：「當(dāng)選擇從一千個變?yōu)橐话偃f個時(shí)，好答案的標(biāo)準(zhǔn)就發(fā)生了變化。不幸的是，世界上沒有一個人類專家能夠通過一個 1000 萬個選項(xiàng)的列表來找出所有正確的答案。」事實(shí)上，許多新的研究問題都出現(xiàn)在這種規(guī)模上，而機(jī)器學(xué)習(xí)界并沒有傳統(tǒng)地看待這一問題，每個問題只有部分答案以極限的規(guī)模存在，因此即使是最基本的機(jī)器學(xué)習(xí)技術(shù)（如交叉驗(yàn)證）也有可能出錯。這些新的研究問題，加上高影響力的排名和推薦應(yīng)用，使極限分類成為學(xué)術(shù)界和工業(yè)界的熱門研究方向。在過去的六年里，極限分類的研究取得了顯著的進(jìn)步。Varma 觀察到，關(guān)于極限分類的論文已在各種會議上發(fā)表，包括 AAAI, AISTATS, ICML, IJCAI, KDD, NIPS, SIGIR, WSDM, WWW 等，基準(zhǔn)任務(wù)的預(yù)測精度從 2013 年的 19% 提高到今天的 65%。
遺憾的是，極限分類的技術(shù)挑戰(zhàn)不僅在于提高預(yù)測精度，還需要減少訓(xùn)練時(shí)間、預(yù)測時(shí)間和模型大小。訓(xùn)練分類器所需的時(shí)間是極限分類中最大的問題之一。Varma 解釋說，2013 年，他們在和維基百科大小差不多的數(shù)據(jù)集上，對他們基于樹的極限分類器 MLRF 在 1000 個核心集群上進(jìn)行訓(xùn)練，花了 7 個小時(shí)，這種速度在 Bing 的規(guī)模上簡直是不可接受的，因此必須開發(fā)一種新的算法。
他們決定稱這種算法為 Slice。
算法的工作原理
Slice 代表可擴(kuò)展的線性極限分類器，它可以比 MLRF 快一萬倍以上。該算法能夠準(zhǔn)確有效地?cái)U(kuò)展到涉及 1 億個標(biāo)簽和 2.4 億個訓(xùn)練點(diǎn)的問題，為世界上所有其他分類器的擴(kuò)展能力打開了一個新的大門。Slice 為每個標(biāo)簽學(xué)習(xí)一個線性分類器，但在標(biāo)簽數(shù)量上減少了從線性到對數(shù)的訓(xùn)練和預(yù)測成本。只有少數(shù)標(biāo)簽（比如對數(shù)標(biāo)簽）在任何給定的特征空間區(qū)域中都是活動的，它的實(shí)現(xiàn)正是利用了這一點(diǎn)。在給定測試點(diǎn)的情況下，基于近似最近鄰搜索，快速確定所屬特征空間的區(qū)域。然后，它只評估該區(qū)域中活動標(biāo)簽的分類器，這一過程會產(chǎn)生對數(shù)預(yù)測成本。在訓(xùn)練過程中，如果 D 維中有 N 個帶 L 標(biāo)簽的點(diǎn)，slice 通過只訓(xùn)練最難的負(fù)示例（時(shí)間復(fù)雜度 O（（n log l）/L））而不是所有（時(shí)間復(fù)雜度 O（n））負(fù)樣本，將訓(xùn)練成本從 O(NDL) 降低到 O(ND log L)。這是通過一種新的基于近似識別線性分類器生成模型的負(fù)采樣技術(shù)實(shí)現(xiàn)的。這項(xiàng)技術(shù)對于低維深度學(xué)習(xí)尤其有效，因?yàn)樗梢杂行У貜臄?shù)億個點(diǎn)上對幾百個最難的樣本進(jìn)行分類，而不會損失精度。雷鋒網(wǎng)
這復(fù)雜嗎？
復(fù)雜。
值得嗎？
值得。
極限分類為排名和推薦問題創(chuàng)建了一個新的范例。通過將每個項(xiàng)目作為單獨(dú)的標(biāo)簽進(jìn)行排名或推薦，我們可以學(xué)習(xí)一個極限分類器，它以用戶的特征向量為輸入，預(yù)測相關(guān)標(biāo)簽的子集作為輸出，然后根據(jù)應(yīng)用程序?qū)⑴c預(yù)測標(biāo)簽相對應(yīng)的項(xiàng)目作為推薦包或排名列表返回給用戶。在某些情況下，這種方法的結(jié)果相比傳統(tǒng)的方法會有很大的改善。
在 Bing 搜索引擎上再次執(zhí)行上述推薦相關(guān)查詢的任務(wù)。你可以將 Bing 上的前 1 億個查詢都視為單獨(dú)的標(biāo)簽，以用戶查詢?yōu)檩斎耄㈩A(yù)測 1 億個標(biāo)簽（查詢）的相關(guān)子集作為輸出，這是對你的查詢問題的一種極限分類重新表述。
通過這種方式處理問題，Bing 可以提出更相關(guān)的建議，并將查詢的成功率提高 12%，從而使數(shù)百萬用戶能夠更高效地找到想要的答案。
「我第一次聽到 Manik 關(guān)于極限分類的演講是在幾年前，當(dāng)時(shí)，我花了一段時(shí)間才明白他想做什么。這是一種全新的看待多標(biāo)簽分類的方法，其效率以及模型大小是該方法不可能奏效的原因之一。多年來，Manik 和他的合作者已經(jīng)取得了巨大的進(jìn)步，他們?yōu)闄C(jī)器學(xué)習(xí)開創(chuàng)了一個子領(lǐng)域。頂級的 ML 會議現(xiàn)在有關(guān)于極限分類的專題研討。我認(rèn)為這項(xiàng)研究將繼續(xù)對科學(xué)界產(chǎn)生影響。這是一個很好的例子，它展示了持續(xù)的研究如何使不可能的事情成為可能?！埂④浻《妊芯吭嚎偨?jīng)理 Sriram Rajamani。
除了搜索和信息檢索，極限分類還可以應(yīng)用于計(jì)算廣告、推薦系統(tǒng)、計(jì)算機(jī)視覺甚至自然語言處理。例如，你可以使用極限分類來預(yù)測下一個將在 Bing 上鍵入的單詞是什么?；蛘撸憧梢杂盟鼇碜R別你在會議上遇到的陌生人。或者，你甚至可以用它來推薦下一個你應(yīng)該聽的音樂曲目。當(dāng)然，世界上數(shù)百萬人已經(jīng)受益于極限分類法，通過 Bing 廣告系統(tǒng)，他們能更有效地找到和購買他們正在尋找的商品和服務(wù)。
極限分類目前應(yīng)用非常廣泛。它開啟了研究的新前景，并回避了問題：還有什么其他的問題可以被重新定義為極限分類問題，我們現(xiàn)在有更好的解決辦法嗎？
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
