Singular Value Decomposition vs. Matrix Factorization in Recommender Systems

For nylig, efter at have set Recommender Systems-klassen i professor Andrew Ng's Machine Learning-kursus, blev jeg meget ubehagelig over ikke at forstå, hvordan Matrix Factorization fungerer.

Jeg ved nogle gange, at matematikken i Machine Learning er meget uklar. Det er bedre, hvis vi tænker på det som en sort kasse, men den model var meget “magisk” for mine standarder.

I sådanne situationer forsøger jeg normalt at søge på Google efter flere referencer for bedre at forstå konceptet. Denne gang blev jeg endnu mere forvirret. Mens Prof. Ng kaldte algoritmen som (Low Factor) Matrix Factorization, fandt jeg en anden nomenklatur på Internettet: Singular Value Decomposition.

Hvad der forvirrede mig mest var, at Singular Value Decomposition var meget forskellig fra, hvad Prof. Ng havde undervist. Folk fortsatte med at antyde, at de begge var de samme.

I denne tekst vil jeg opsummere mine fund og forsøge at rydde op i den forvirring, disse udtryk kan forårsage.

Anbefalingssystemer

Recommender Systems (RS) er bare automatiserede måder at anbefale noget til nogen. Sådanne systemer bruges i vid udstrækning af e-handelsfirmaer, streamingtjenester og nyhedswebsteder. Det hjælper med at reducere brugernes friktion, når de prøver at finde noget, de kan lide.

RS er bestemt ikke en ny ting: de har været med siden mindst 1990. Faktisk kan en del af den nylige Machine Learning-hype tilskrives interesse for RS. I 2006 gjorde Netflix et stænk, da de sponsorerede en konkurrence for at finde den bedste RS til deres film. Som vi snart vil se, er begivenheden relateret til nomenklaturens rod, der fulgte.

Matrixrepræsentationen

Der er mange måder, en person kan tænke på at anbefale en film til nogen. En strategi, der viste sig at være meget god, er at behandle filmbedømmelser som en bruger x filmmatrix som denne:

I denne matrix repræsenterer spørgsmålstegnene de film, som en bruger ikke har bedømt. Strategien er derefter at forudsige disse vurderinger på en eller anden måde og anbefale brugerne de film, de sandsynligvis vil kunne lide.

Matrixfaktorisering

En virkelig smart erkendelse foretaget af de fyre, der deltog i Netflixs konkurrence (især Simon Funk) var, at brugernes vurderinger ikke kun var tilfældige gæt. Raters følger sandsynligvis nogle logik, hvor de vejer de ting, de kan lide i en film (en bestemt skuespillerinde eller en genre) mod ting, de ikke kan lide (lang varighed eller dårlige vittigheder) og derefter kommer med en score.

Denne proces kan repræsenteres af en lineær formel af følgende art:

hvor xₘ er en søjlevektor med værdierne for funktionerne i filmen m og θᵤ er en anden søjlevektor med de vægte, som brugeren u giver til hver funktion. Hver bruger har forskellige vægte, og hver film har forskellige værdier for sine funktioner.

Det viser sig, at hvis vi vilkårligt retter antallet af funktioner og ignorerer de manglende ratings, kan vi finde et sæt vægte og funktionsværdier, der opretter en ny matrix med værdier tæt på den oprindelige klassificeringsmatrix. Dette kan gøres med gradientnedstigning, meget lig den, der anvendes i lineær regression. I stedet for det nu optimerer vi to sæt parametre (vægte og funktioner) på samme tid.

Ved hjælp af den tabel, jeg gav som et eksempel ovenfor, ville resultatet af optimeringsproblemet generere følgende nye matrix:

Bemærk, at den resulterende matrix ikke kan være en nøjagtig kopi af den originale i de fleste virkelige datasæt, fordi folk i det virkelige liv ikke laver multiplikationer og summeringer for at bedømme en film. I de fleste tilfælde er vurderingen kun en tarmfølelse, der også kan påvirkes af alle slags eksterne faktorer. Alligevel er vores håb, at den lineære formel er en god måde at udtrykke den vigtigste logik, der driver brugernes vurderinger.

OK, nu har vi en omtrentlig matrix. Men hvordan pokker hjælper det os med at forudsige de manglende ratings? Husk at for at opbygge den nye matrix oprettede vi en formel til at udfylde alle de værdier, inklusive dem der mangler i den oprindelige matrix. Så hvis vi vil forudsige den manglende vurdering af en bruger på en film, tager vi bare alle filmens funktionsværdier ganget med alle brugerens vægte og opsummerer alt. Så i mit eksempel, hvis jeg vil forudsige bruger 2's vurdering af film 1, kan jeg lave følgende beregning:

For at gøre tingene klarere kan vi adskille θ'erne og x'erne og sætte dem i deres egne matricer (siger P og Q ). Det er faktisk en matrixfaktorisering, deraf navnet benyttet af prof. Ng.

Den matrixfaktorisering er grundlæggende hvad Funk gjorde. Han fik tredjepladsen i Netflixs konkurrence og tiltrak meget opmærksomhed (hvilket er et interessant tilfælde af, at en tredjeplads er mere berømt end vinderne). Hans tilgang er blevet gentaget og forfinet siden da og er stadig i brug i mange applikationer.

Enkel værdi nedbrydning

Indtast SVD (Singular Value Decomposition). SVD er en fancy måde at faktorisere en matrix i tre andre matricer ( A = UΣVᵀ ). Måden SVD gøres garanterer, at de 3 matricer har nogle gode matematiske egenskaber.

Der er mange applikationer til SVD. En af dem er Principal Component Analysis (PCA), som bare reducerer et datasæt af dimension n til dimension k ( k <n ).

Jeg vil ikke give dig yderligere detaljer om SVD'er, fordi jeg ikke kender mig selv. Pointen er, at det ikke er det samme som vi gjorde med Matrix Factorization. Det største bevis er, at SVD opretter 3 matricer, mens Funk's Matrix Factorization kun opretter 2.

Så hvorfor dukker SVD op hver gang jeg søger efter Recommender Systems? Jeg var nødt til at grave lidt, men til sidst fandt jeg nogle skjulte perler. Ifølge Luis Argerich:

Matrixfaktoriseringsalgoritmerne, der anvendes til anbefalingssystemer, prøver at finde to matricer: P, Q, såsom P * Q, matcher de KENDTE værdier i hjælpematrixen. Dette princip dukkede op i den berømte SVD ++ ”Factorization meets the neighbourhood” papir, der desværre brugte navnet “SVD ++” til en algoritme, der absolut ikke har noget forhold til SVD .

For ordens skyld, tror jeg Funk, ikke forfatterne af SVD ++, foreslog først den nævnte matrixfaktorisering til anbefalsystemer. Faktisk er SVD ++, som navnet antyder, en udvidelse af Funk's arbejde.

Xavier Amatriain giver os et større billede:

Lad os starte med at påpege, at metoden, der normalt omtales som "SVD", der bruges i forbindelse med anbefalinger , ikke strengt taget er den matematiske nedbrydning af en matrix, men snarere en tilnærmet måde at beregne den lave rangtilnærmelse af matrixen på. ved at minimere det kvadrede fejltab. En mere nøjagtig, omend mere generisk, måde at kalde dette på ville være Matrix Factorization. Den første version af denne tilgang i forbindelse med Netflix-prisen blev præsenteret af Simon Funk i hans berømte Try This at Home-blogpost. Det er vigtigt at bemærke, at den ægte SVD-tilgang faktisk var blevet anvendt på den samme opgave år før med ikke så meget praktisk succes.

Wikipedia har også lignende oplysninger begravet i sin artikel om matrixfaktorisering (anbefalingssystemer):

Den oprindelige algoritme, der blev foreslået af Simon Funk i hans blogindlæg, faktoriserede matrixen for bruger-element-klassificering som produktet af to lavere-dimensionelle matricer, den første har en række for hver bruger, mens den anden har en kolonne for hvert element. Rækken eller kolonnen, der er knyttet til en bestemt bruger eller et element, kaldes latente faktorer. Bemærk, at der på trods af navnet i FunkSVD ikke anvendes nedbrydning af entalværdi.

At opsummere:

1. SVD er en noget kompleks matematisk teknik, der faktoriserer matricer i tre nye matricer og har mange applikationer, herunder PCA og RS.

2. Simon Funk anvendte en meget smart strategi i Netflix-konkurrencen i 2006 ved at faktorisere en matrix i to andre og bruge gradientnedstigning til at finde optimale værdier for funktioner og vægte. Det er ikke SVD , men han brugte det udtryk alligevel til at beskrive sin teknik.

3. Det mere passende udtryk for, hvad Funk gjorde, er Matrix Factorization.

4. På grund af de gode resultater og den berømmelse, der fulgte, kalder folk stadig den teknik SVD, fordi det er sådan, forfatteren navngav den.

Jeg håber, det hjælper med at afklare tingene lidt.