Onlinehandlare sätter vanligtvis ihop några ord för att söka efter den produkt de vill ha, men i en värld med miljontals produkter och shoppare, uppgiften att matcha de ospecifika orden till rätt produkt är en av de största utmaningarna inom informationssökning.

Genom att använda en dela-och-härska-metod som utnyttjar kraften i komprimerad avkänning, datavetare från Rice University och Amazon har visat att de kan minska mängden tid och beräkningsresurser det tar att träna datorer för produktsökning och liknande "extrema klassificeringsproblem" som talöversättning och att svara på allmänna frågor.

Forskningen kommer att presenteras denna vecka vid 2019 års konferens om neurala informationsbehandlingssystem (NeurIPS 2019) i Vancouver. Resultaten inkluderar tester som utfördes 2018 när huvudforskaren Anshumali Shrivastava och huvudförfattaren Tharun Medini, både av ris, besökte Amazon Search i Palo Alto, Kalifornien.

I tester på en Amazon-sökdatauppsättning som inkluderade cirka 70 miljoner frågor och mer än 49 miljoner produkter, Shrivastava, Medini och kollegor visade sitt sätt att använda "sammanslagna medelklassificerare via hash, " (MACH) krävde en bråkdel av utbildningsresurserna för vissa toppmoderna kommersiella system.

"Våra träningstider är ungefär 7-10 gånger snabbare, och våra minnesavtryck är 2-4 gånger mindre än de bästa utgångsresultaten för tidigare rapporterade storskaliga, distribuerade system för djupinlärning, sa Shrivastava, en biträdande professor i datavetenskap vid Rice.

Medini, en Ph.D. student på Rice, nämnda produktsökning är utmanande, till viss del, på grund av det stora antalet produkter. "Det finns ungefär 1 miljon engelska ord, till exempel, men det finns lätt mer än 100 miljoner produkter online."

Det finns också miljontals människor som handlar efter dessa produkter, var och en på sitt sätt. Vissa skriver en fråga. Andra använder nyckelord. Och många är inte säkra på vad de letar efter när de börjar. Men eftersom miljontals onlinesökningar görs varje dag, teknikföretag som Amazon, Google och Microsoft har mycket data om framgångsrika och misslyckade sökningar. Och att använda dessa data för en typ av maskininlärning som kallas djupinlärning är ett av de mest effektiva sätten att ge bättre resultat för användarna.

System för djupinlärning, eller neurala nätverksmodeller, är stora samlingar av matematiska ekvationer som tar en uppsättning tal som kallas ingångsvektorer, och omvandla dem till en annan uppsättning tal som kallas utdatavektorer. Nätverken är sammansatta av matriser med flera parametrar, och state-of-the-art distribuerade djupinlärningssystem innehåller miljarder parametrar som är uppdelade i flera lager. Under träning, data matas till det första lagret, vektorer transformeras, och utgångarna matas till nästa lager och så vidare.

"Extrema klassificeringsproblem" är sådana med många möjliga utfall, och sålunda, många parametrar. Modeller för djupinlärning för extrem klassificering är så stora att de vanligtvis måste tränas på vad som faktiskt är en superdator, en länkad uppsättning grafikprocessorenheter (GPU) där parametrar distribueras och körs parallellt, ofta i flera dagar.

"Ett neuralt nätverk som tar sökinput och förutsäger från 100 miljoner utdata, eller produkter, kommer vanligtvis att sluta med cirka 2, 000 parametrar per produkt, " Sa Medini. "Så du multiplicerar dem, och det sista lagret av det neurala nätverket är nu 200 miljarder parametrar. Och jag har inte gjort något sofistikerat. Jag talar om en mycket, mycket död enkel neurala nätverksmodell."

"Det skulle ta cirka 500 gigabyte minne för att lagra dessa 200 miljarder parametrar, " Sa Medini. "Men om du tittar på nuvarande träningsalgoritmer, det finns en berömd som heter Adam som tar ytterligare två parametrar för varje parameter i modellen, eftersom det behöver statistik från dessa parametrar för att övervaka träningsprocessen. Så, nu är vi på 200 miljarder gånger tre, och jag kommer att behöva 1,5 terabyte arbetsminne bara för att lagra modellen. Jag har inte ens kommit till träningsdatan. De bästa grafikprocessorerna där ute har bara 32 gigabyte minne, så att träna en sådan modell är oöverkomlig på grund av massiv kommunikation mellan GPU.

MACH tar ett helt annat tillvägagångssätt. Shrivastava beskriver det med ett tankeexperiment som slumpmässigt delar upp de 100 miljoner produkterna i tre klasser, som har formen av hinkar. "Jag blandar, låt oss säga, iPhones med laddare och T-shirts alla i samma hink, " sa han. "Det är en drastisk minskning från 100 miljoner till tre."

I tankeexperimentet, de 100 miljoner produkterna sorteras slumpmässigt i tre hinkar i två olika världar, vilket gör att produkter kan hamna i olika hinkar i varje värld. En klassificerare är tränad att tilldela sökningar till hinkarna snarare än produkterna i dem, vilket innebär att klassificeraren bara behöver mappa en sökning till en av tre produktklasser.

"Nu matar jag en sökning till klassificeraren i värld ett, och det står hink tre, och jag matar den till klassificeraren i värld två, och det står hink ett, " sa han. "Vad tänker den här personen på? Den mest troliga klassen är något som är vanligt mellan dessa två hinkar. Om du tittar på den möjliga skärningspunkten mellan hinkarna finns det tre i världen en gånger tre i värld två, eller nio möjligheter, " sa han. "Så jag har minskat mitt sökutrymme till ett över nio, och jag har bara betalat kostnaden för att skapa sex klasser."

Lägga till en tredje värld, och tre hinkar till, ökar antalet möjliga korsningar med en faktor tre. "Det finns nu 27 möjligheter för vad den här personen tänker, " sa han. "Så jag har minskat mitt sökutrymme med en över 27, men jag har bara betalat kostnaden för nio klasser. Jag betalar en kostnad linjärt, och jag får en exponentiell förbättring."

I sina experiment med Amazons träningsdatabas, Shrivastava, Medini och kollegor delade slumpmässigt de 49 miljoner produkterna i 10, 000 klasser, eller hinkar, och upprepade processen 32 gånger. Det minskade antalet parametrar i modellen från cirka 100 miljarder till 6,4 miljarder. Och att träna modellen tog mindre tid och mindre minne än några av de bästa rapporterade träningstiderna på modeller med jämförbara parametrar, inklusive Googles Sparsely-Gated Mixture-of-Experts (MoE) modell, sa Medini.

Han sa att MACHs viktigaste funktion är att det inte kräver någon kommunikation mellan parallella processorer. I tankeexperimentet, det är vad som representeras av de separata, oberoende världar.

"De behöver inte ens prata med varandra, " Sa Medini. "I princip, du kan träna var och en av de 32 på en GPU, vilket är något du aldrig skulle kunna göra med ett icke-oberoende tillvägagångssätt."

Shrivastava sa, "I allmänhet, utbildning har krävt kommunikation över parametrar, vilket innebär att alla processorer som körs parallellt måste dela information. Ser fram emot, kommunikation är ett stort problem inom distribuerad djupinlärning. Google har uttryckt ambitioner att utbilda ett nätverk med 1 biljon parametrar, till exempel. MACH, för närvarande, kan inte tillämpas på användningsfall med litet antal klasser, men för extrem klassificering, den uppnår den heliga graal noll kommunikation."