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