Hej alle! Mit navn er Sasha, jeg er CTO & Co-Founder hos LoyaltyLab. For to år siden gik mine venner og jeg, ligesom alle fattige studerende, om aftenen for at købe øl i den nærmeste butik i nærheden af ​​vores hus. Vi var meget kede af, at forhandleren, der vidste, at vi ville komme efter øl, ikke tilbød rabat på chips eller kiks, selvom dette var så logisk! Vi forstod ikke, hvorfor denne situation opstod, og besluttede at starte vores egen virksomhed. Nå, som en bonus, giv dig selv rabat hver fredag ​​på de samme chips.

Og det hele nåede til det punkt, hvor jeg præsenterer materiale om den tekniske side af produktet kl NVIDIA GTC. Vi deler gerne vores arbejde med samfundet, så jeg udgiver min rapport i form af en artikel.

Indledning

Som alle andre i starten af ​​rejsen startede vi med et overblik over, hvordan anbefalingssystemer laves. Og den mest populære arkitektur viste sig at være følgende type:

Den består af to dele:

1. Prøveudtagning af kandidater til anbefalinger ved hjælp af en enkel og hurtig model, som regel en samarbejdsmodel.
2. Rangordning af kandidater med en mere kompleks og langsom indholdsmodel, under hensyntagen til alle mulige funktioner i dataene.

Herefter vil jeg bruge følgende udtryk:

• kandidat/kandidat til anbefalinger — et bruger-produkt-par, der potentielt kan indgå i anbefalinger i produktionen.
• kandidater udvinding/ekstraktor/kandidat ekstraktionsmetode — en proces eller metode til at udtrække "anbefalingskandidater" fra tilgængelige data.

Det første trin involverer normalt brug af forskellige variationer af kollaborativ filtrering. Den mest populære - ALS. Det er overraskende, at de fleste artikler om anbefalingssystemer kun afslører forskellige forbedringer af samarbejdsmodeller i første fase, men ingen taler meget om andre stikprøvemetoder. For os fungerede tilgangen med kun at bruge samarbejdsmodeller og forskellige optimeringer med dem ikke med den kvalitet, vi forventede, så vi gravede i forskning specifikt på denne del. Og i slutningen af ​​artiklen vil jeg vise, hvor meget vi var i stand til at forbedre ALS, som var vores baseline.

Før jeg går videre til at beskrive vores tilgang, er det vigtigt at bemærke, at i realtidsanbefalinger, når det er vigtigt for os at tage højde for data, der fandt sted for 30 minutter siden, er der virkelig ikke mange tilgange, der kan fungere på den nødvendige tid. Men i vores tilfælde skal vi ikke indsamle anbefalinger mere end en gang om dagen og i de fleste tilfælde - en gang om ugen, hvilket giver os mulighed for at bruge komplekse modeller og forbedre kvaliteten flere gange.

Lad os tage udgangspunkt i, hvilke målinger kun ALS viser på opgaven med at udtrække kandidater. De vigtigste målinger, vi overvåger, er:

• Præcision - andelen af ​​korrekt udvalgte kandidater fra stikprøven.
• Tilbagekaldelse er andelen af ​​kandidater, der skete ud af dem, der faktisk var i målintervallet.
• F1-score - F-mål beregnet på de to foregående punkter.

Vi vil også se på målene for den endelige model efter træningsgradientboosting med yderligere indholdsfunktioner. Der er også 3 hovedmetrics her:

• precision@5 - den gennemsnitlige procentdel af produkter fra top 5 i form af sandsynlighed for hver køber.
• response-rate@5 - konvertering af kunder fra et besøg i butikken til køb af mindst ét ​​personligt tilbud (5 produkter i ét tilbud).
• gennemsnit roc-auc pr. bruger - gennemsnit roc-auc for hver køber.

Det er vigtigt at bemærke, at alle disse målinger er målt på krydsvalidering af tidsserier, det vil sige, at der trænes i de første k uger, og k+1 uge tages som testdata. Sæsonbestemte op- og nedture havde således minimal indflydelse på fortolkningen af ​​modellernes kvalitet. Yderligere på alle grafer vil abscisseaksen angive ugenummeret i krydsvalidering, og ordinataksen vil angive værdien af ​​den specificerede metrik. Alle grafer er baseret på transaktionsdata fra én klient, så sammenligninger mellem hinanden er korrekte.

Inden vi begynder at beskrive vores tilgang, ser vi først på baseline, som er en ALS-trænet model.
Metrics for hentning af kandidater:

Endelige målinger:

Jeg behandler alle implementeringer af algoritmer som en form for forretningshypotese. Således, meget groft sagt, kan enhver samarbejdsmodel betragtes som en hypotese om, at "folk har en tendens til at købe, hvad folk, der ligner dem, køber." Som jeg allerede har sagt, begrænsede vi os ikke til sådan semantik, og her er nogle hypoteser, der fungerer godt på data i offline detailhandel:

1. Som jeg allerede har købt før.
2. Ligesom hvad jeg købte før.
3. Periode med et længe tidligere køb.
4. Populær efter kategori/mærke.
5. Vekselkøb af forskellige varer fra uge til uge (Markov-kæder).
6. Lignende produkter til købere, i henhold til egenskaber bygget af forskellige modeller (Word2Vec, DSSM, osv.).

Hvad har du købt før?

Den mest åbenlyse heuristik, der fungerer meget godt i dagligvarehandelen. Her tager vi alle de varer, som loyalitetskortindehaveren købte inden for de sidste K dage (normalt 1-3 uger), eller K dage for et år siden. Ved kun at anvende denne metode opnår vi følgende metrics:

Her er det helt indlysende, at jo længere vi tager perioden, jo mere tilbagekaldelse har vi og jo mindre præcision har vi og omvendt. I gennemsnit giver de "sidste 2 uger" bedre resultater for kunderne.

Ligesom hvad jeg købte før

Det er ikke overraskende, at "hvad jeg købte før" fungerer godt for dagligvarer, men at udtrække kandidater kun fra det, brugeren allerede har købt, er ikke særlig cool, fordi det er usandsynligt, at det vil overraske køberen med et nyt produkt. Derfor foreslår vi at forbedre denne heuristik en smule ved hjælp af de samme samarbejdsmodeller. Fra de vektorer, som vi modtog under ALS-træning, kan vi få produkter, der ligner det, brugeren allerede har købt. Denne idé minder meget om "lignende videoer" i tjenester til visning af videoindhold, men da vi ikke ved, hvad brugeren spiser/køber på et bestemt tidspunkt, kan vi kun lede efter dem, der ligner det, han allerede har købt, især da vi Vi ved allerede, hvor godt det virker. Ved at anvende denne metode på brugertransaktioner i løbet af de sidste 2 uger opnår vi følgende metrics:

Her k — antallet af lignende produkter, der hentes for hvert produkt købt af køberen i løbet af de sidste 14 dage.
Denne tilgang fungerede især godt for vores klient, for hvem det var afgørende ikke at anbefale noget, der allerede var i brugerens købshistorik.

Sen købsperiode

Som vi allerede har fundet ud af, på grund af den høje frekvens af indkøb af varer, fungerer den første tilgang godt til vores specifikke behov. Men hvad med varer som vaskepulver/shampoo/osv. Det vil sige med produkter, der næppe er nødvendige hver eller anden uge, og som tidligere metoder ikke kan udvinde. Dette fører til følgende idé - det foreslås at beregne købsperioden for hvert produkt i gennemsnit for kunder, der har købt produktet mere k enkelt gang. Og så udtræk det, som køberen højst sandsynligt allerede er løbet tør for. De beregnede perioder for varer kan kontrolleres med dine øjne for tilstrækkelighed:

Og så vil vi se på, om slutningen af ​​produktperioden falder inden for det tidsinterval, hvor anbefalingerne skal i produktion, og prøve, hvad der sker. Fremgangsmåden kan illustreres således:

Her har vi 2 hovedsager, der kan overvejes:

1. Er det nødvendigt at prøve produkter fra kunder, der har købt produktet mindre end K gange.
2. Er det nødvendigt at prøve et produkt, hvis slutningen af ​​dets periode falder før begyndelsen af ​​målintervallet.

Følgende graf viser, hvilke resultater denne metode opnår med forskellige hyperparametre:

ft — Tag kun kunder, der har købt produktet mindst K (her K=5) gange
tm — Tag kun kandidater, der falder inden for målintervallet

Det er ikke overraskende, at han er i stand (0, 0) den største tilbagekaldelse og den mindste præcision, da der under denne betingelse hentes flest kandidater. De bedste resultater opnås dog, når vi ikke prøver produkter til kunder, der har købt et bestemt produkt mindre end k tider og udtræk, herunder varer, hvis udløb falder før målintervallet.

Populær efter kategori

En anden ret oplagt idé er at prøve populære produkter på tværs af forskellige kategorier eller mærker. Her beregner vi for hver køber top-k "favorit" kategorier/mærker og udtræk "populær" fra denne kategori/mærke. I vores tilfælde vil vi bestemme "favorit" og "populær" ud fra antallet af køb af produktet. En yderligere fordel ved denne fremgangsmåde er dens anvendelighed i tilfælde af koldstart. Det vil sige for kunder, der enten har foretaget meget få indkøb, eller ikke har været i butikken i længere tid, eller lige har udstedt et loyalitetskort. For dem er det nemmere og bedre at lagerføre varer, der er populære hos kunderne og har en historie. De resulterende metrics er:

Her betyder tallet efter ordet "kategori" niveauet for indlejring af kategorien.

Samlet set er det heller ikke overraskende, at smallere kategorier opnår bedre resultater, da de udtrækker mere præcise "favorit"-produkter til shoppere.

Vekselkøb af forskellige varer fra uge til uge

En interessant tilgang, som jeg ikke har set i artikler om anbefalingssystemer, er en ret simpel og samtidig fungerende statistisk metode af Markov-kæder. Her tager vi 2 forskellige uger, derefter bygger vi for hver kunde par produkter [købt i uge i]-[købt i uge j], hvor j > i, og herfra beregner vi for hvert produkt sandsynligheden for at skifte til et andet produkt i næste uge. Altså for hvert par varer produkti-produktj Vi tæller deres antal i de fundne par og dividerer med antallet af par, hvor produkti var i den første uge. For at udtrække kandidater tager vi købers sidste kvittering og udtrækker top-k de mest sandsynlige næste produkter fra den overgangsmatrix, vi modtog. Processen med at konstruere en overgangsmatrix ser sådan ud:

Fra virkelige eksempler i overgangssandsynlighedsmatrixen ser vi følgende interessante fænomener:

Her kan du bemærke interessante afhængigheder, der afsløres i forbrugeradfærd: for eksempel elskere af citrusfrugter eller et mærke mælk, hvorfra de sandsynligvis vil skifte til en anden. Det er heller ikke overraskende, at produkter med en høj frekvens af genkøb, som smør, også ender her.

Metrikken i metoden med Markov-kæder er som følger:

k — antallet af produkter, der hentes for hvert købt produkt fra køberens sidste transaktion.
Som vi kan se, er det bedste resultat vist ved konfigurationen med k=4. Stigningen i uge 4 kan forklares med sæsonbestemt adfærd omkring helligdage. 

Lignende produkter til købere, i henhold til egenskaber bygget af forskellige modeller

Nu er vi kommet til den sværeste og mest interessante del - at søge efter nærmeste naboer baseret på vektorer af kunder og produkter bygget efter forskellige modeller. I vores arbejde bruger vi 3 sådanne modeller:

• ALS
• Word2Vec (Item2Vec til sådanne opgaver)
• DSSM

Vi har allerede beskæftiget os med ALS, du kan læse om, hvordan det lærer her. I tilfældet med Word2Vec bruger vi den velkendte implementering af modellen fra gensim. I analogi med teksterne definerer vi tilbuddet som en købskvittering. Når man konstruerer en produktvektor, lærer modellen således at forudsige for produktet i kvitteringen dets "kontekst" (de resterende produkter i kvitteringen). I e-handelsdata er det bedre at bruge købers session i stedet for en kvittering; fyrene fra Ozon. Og DSSM er mere interessant at parse. Oprindeligt blev det skrevet af gutterne fra Microsoft som en model til søgning, Du kan læse den originale forskningsartikel her. Modellens arkitektur ser således ud:

Her Q — forespørgsel, brugersøgning, D[i] — dokument, internetside. Input til modellen er attributterne for henholdsvis anmodningen og siderne. Efter hvert inputlag er der et antal fuldt forbundne lag (flerlagsperceptron). Dernæst lærer modellen at minimere cosinus mellem vektorerne opnået i de sidste lag af modellen.
Anbefalingsopgaver bruger nøjagtig den samme arkitektur, kun i stedet for en anmodning er der en bruger, og i stedet for sider er der produkter. Og i vores tilfælde er denne arkitektur omdannet til følgende:

Nu, for at kontrollere resultaterne, er det tilbage at dække det sidste punkt - hvis vi i tilfælde af ALS og DSSM eksplicit har defineret brugervektorer, så har vi i tilfælde af Word2Vec kun produktvektorer. For at bygge brugervektoren har vi her defineret 3 hovedtilgange:

1. Du skal blot tilføje vektorerne, så viser det sig for cosinusafstanden, at vi simpelthen har beregnet et gennemsnit af produkterne i købshistorien.
2. Vektor summering med en vis tidsvægtning.
3. Vejning af varer med TF-IDF koefficient.

Ved lineær vægtning af købervektoren går vi ud fra den hypotese, at det produkt, som brugeren købte i går, har større indflydelse på hans adfærd end det produkt, han købte for seks måneder siden. Så vi betragter købers foregående uge med odds 1, og hvad der skete derefter med odds på ½, ⅓ osv.:

For TF-IDF-koefficienter gør vi nøjagtig det samme som i TF-IDF for tekster, kun vi betragter køber som henholdsvis et dokument, og checken som et tilbud, ordet er et produkt. På denne måde vil brugerens vektor flytte sig mere mod sjældne varer, mens hyppige og velkendte varer for køberen ikke vil ændre det meget. Fremgangsmåden kan illustreres således:

Lad os nu se på metrikkerne. Sådan ser ALS-resultaterne ud:

Metrics for Item2Vec med forskellige variationer af konstruktion af købervektoren:

I dette tilfælde bruges nøjagtig samme model som i vores baseline. Den eneste forskel er, hvilken k vi vil bruge. For kun at bruge samarbejdsmodeller, skal du tage omkring 50-70 nærmeste produkter for hver kunde.

Og målinger ifølge DSSM:

Hvordan kombinerer man alle metoder?

Fedt, siger du, men hvad skal man gøre med sådan et stort sæt af kandidatekstraktionsværktøjer? Hvordan vælger du den optimale konfiguration til dine data? Her har vi flere problemer:

1. Det er nødvendigt på en eller anden måde at begrænse søgerummet for hyperparametre i hver metode. Det er selvfølgelig diskret overalt, men antallet af mulige point er meget stort.
2. Ved hjælp af et lille begrænset udsnit af specifikke metoder med specifikke hyperparametre, hvordan kan du vælge den bedste konfiguration til din metrik?

Vi har endnu ikke fundet et endegyldigt korrekt svar på det første spørgsmål, så vi går ud fra følgende: For hver metode skrives en hyperparameter-søgepladsbegrænser, afhængigt af nogle statistikker om de data, vi har. Ved at kende den gennemsnitlige periode mellem køb fra folk kan vi gætte med hvilken periode vi skal bruge metoden "hvad der allerede er købt" og "periode for et længe tidligere køb".

Og efter at vi har gennemgået et vist passende antal variationer af forskellige metoder, bemærker vi følgende: hver implementering udtrækker et vist antal kandidater og har en vis værdi af nøglemetrikken for os (tilbagekaldelse). Vi ønsker at få et samlet antal kandidater, afhængigt af vores tilladte regnekraft, med den højest mulige metrik. Her falder problemet smukt sammen i rygsækproblemet.

Her er antallet af kandidater vægten af ​​barren, og tilbagekaldelsesmetoden er dens værdi. Der er dog yderligere 2 punkter, der bør tages i betragtning ved implementering af algoritmen:

• Metoder kan have overlap i de kandidater, de henter.
• I nogle tilfælde vil det være korrekt at tage én metode to gange med forskellige parametre, og kandidatoutputtet fra den første vil ikke være en delmængde af den anden.

For eksempel, hvis vi tager implementeringen af ​​"hvad jeg allerede har købt"-metoden med forskellige intervaller til hentning, så vil deres sæt af kandidater blive indlejret i hinanden. Samtidig giver forskellige parametre i "periodiske køb" ved udgangen ikke fuldstændig kryds. Derfor opdeler vi prøvetagningsmetoderne med forskellige parametre i blokke, således at vi fra hver blok højst ønsker at tage en ekstraktionstilgang med specifikke hyperparametre. For at gøre dette skal du være lidt klog til at implementere rygsækproblemet, men asymptotikken og resultatet vil ikke ændre sig.

Denne smarte kombination giver os mulighed for at få følgende metrics i sammenligning med blot samarbejdsmodeller:

I de endelige målinger ser vi følgende billede:

Men her kan du bemærke, at der er et afdækket punkt for anbefalinger, der er nyttige for erhvervslivet. Nu har vi lige lært, hvordan man gør et godt stykke arbejde med at forudsige, hvad brugeren vil købe, for eksempel i næste uge. Men blot at give rabat på noget, han allerede vil købe, er ikke særlig fedt. Men det er fedt at maksimere forventningerne, for eksempel til følgende metrics:

1. Margin/omsætning baseret på personlige anbefalinger.
2. Gennemsnitlig kundetjek.
3. Hyppighed af besøg.

Så vi multiplicerer de opnåede sandsynligheder med forskellige koefficienter og omrangerer dem, så de produkter, der påvirker metrikkerne ovenfor, kommer til tops. Der er ingen færdig løsning til, hvilken tilgang der er bedst at bruge. Vi eksperimenterer endda med sådanne koefficienter direkte i produktionen. Men her er interessante teknikker, der oftest giver os de bedste resultater:

1. Gang med produktets pris/margin.
2. Gang med den gennemsnitlige kvittering, hvori produktet står. Så der kommer varer op, som de normalt tager noget andet med.
3. Multiplicer med den gennemsnitlige hyppighed af besøg fra købere af dette produkt, baseret på den hypotese, at dette produkt provokerer folk til at vende tilbage efter det oftere.

Efter at have udført eksperimenter med koefficienter opnåede vi følgende metrikker i produktionen:

Her overordnet produktkonvertering — andelen af ​​købte produkter ud af alle produkter i de anbefalinger, vi genererede.

Den opmærksomme læser vil bemærke en væsentlig forskel mellem offline og online metrics. Denne adfærd forklares med, at ikke alle dynamiske filtre for produkter, der kan anbefales, kan tages i betragtning ved træning af modellen. For os er det en normal historie, når halvdelen af ​​de hentede kandidater kan filtreres fra; denne specificitet er typisk i vores branche.

Med hensyn til omsætning er følgende historie opnået, det er klart, at efter lanceringen af ​​anbefalinger vokser testgruppens omsætning kraftigt, nu er den gennemsnitlige stigning i omsætningen med vores anbefalinger 3-4%:

Afslutningsvis vil jeg sige, at hvis du har brug for ikke-realtidsanbefalinger, så kan der findes en meget stor kvalitetsstigning i forsøg med at udtrække kandidater til anbefalinger. En stor mængde tid til deres generation gør det muligt at kombinere mange gode metoder, som samlet set vil give flotte resultater for forretningen.

Jeg vil med glæde chatte i kommentarerne med alle, der finder materialet interessant. Du kan stille mig spørgsmål personligt på telegram. Jeg deler også mine tanker om AI/startups i min telegram kanal - Velkommen :)

Kilde: www.habr.com