Dekompozicija singularne vrijednosti naspram faktorizacije matrice u sustavima preporučivača

Nedavno, nakon što sam pogledao predavanje o sistemima za preporuke na tečaju strojnog učenja prof. Andrewa Nga, našao sam se vrlo neugodno ne razumijevajući kako funkcionira matrična faktorizacija.

Znam da je ponekad matematika u strojnom učenju vrlo nejasna. Bolje je ako o tome razmišljamo kao o crnoj kutiji, ali taj je model bio vrlo "čaroban" za moje standarde.

U takvim situacijama obično pokušavam potražiti na Googleu više referenci kako bih bolje razumio koncept. Ovaj put sam se još više zbunio. Iako je prof. Ng algoritam nazvao faktorizacijom matrice (niskog faktora), na internetu sam pronašao drugačiju nomenklaturu: Dekompozicija singularne vrijednosti.

Najviše me zbunilo to što se raspad singularne vrijednosti jako razlikovao od onoga što je predavao prof. Ng. Ljudi su neprestano sugerirali da su oboje ista stvar.

U ovom tekstu sažet ću svoja otkrića i pokušati razjasniti neke zbrke koje ti pojmovi mogu prouzročiti.

Sustavi za preporuke

Sustavi za preporuke (RS) samo su automatizirani načini da nekome nešto preporučite. Takve sustave široko koriste tvrtke za e-trgovinu, streaming usluge i web stranice s vijestima. Pomaže smanjiti trenje korisnika kada pokušavaju pronaći nešto što im se sviđa.

RS definitivno nisu nova stvar: pojavljuju se barem od 1990. Zapravo, dio nedavne hipe o strojnom učenju može se pripisati interesu za RS. 2006. Netflix je uspio progovoriti kada je sponzorirao natjecanje u pronalaženju najboljeg RS-a za svoje filmove. Kao što ćemo uskoro vidjeti, taj je događaj povezan s nomenklaturnim neredom koji je uslijedio.

Matrični prikaz

Postoji mnogo načina na koje osoba može smisliti da nekome preporuči film. Jedna od strategija koja se pokazala vrlo dobrom je tretiranje ocjena filmova kao matrice Users x Movies poput ove:

U toj matrici upitnici predstavljaju filmove koje korisnik nije ocijenio. Tada je strategija nekako predvidjeti te ocjene i preporučiti korisnicima filmove koji će im se vjerojatno svidjeti.

Faktorizacija matrice

Stvarno pametna spoznaja koju su postigli dečki koji su se prijavili na Netflixovu konkurenciju (posebno Simon Funk) bila je da ocjene korisnika nisu bile samo slučajne pretpostavke. Ocjenjivači vjerojatno slijede neku logiku gdje ponderiraju stvari koje im se sviđaju u filmu (određena glumica ili žanr) prema stvarima koje im se ne sviđaju (dugo trajanje ili loše šale), a zatim smisle rezultat.

Taj se postupak može predstaviti linearnom formulom sljedeće vrste:

gdje je xₘ vektor stupca s vrijednostima značajki filma m, a θᵤ je drugi vektor stupca s ponderima koje korisnik u daje za svaku značajku. Svaki korisnik ima drugačiji skup težina, a svaki film ima različit skup vrijednosti za svoje značajke.

Ispada da ako proizvoljno popravimo broj značajki i zanemarimo ocjene koje nedostaju, možemo pronaći skup pondera i vrijednosti značajki koji stvaraju novu matricu s vrijednostima bliskim izvornoj matrici ocjena. To se može učiniti s gradijentnim spuštanjem, vrlo sličnim onom koji se koristi u linearnoj regresiji. Umjesto toga sada istodobno optimiziramo dva skupa parametara (težine i značajke).

Koristeći tablicu koju sam dao kao gornji primjer, rezultat problema s optimizacijom generirao bi sljedeću novu matricu:

Primijetite da rezultirajuća matrica ne može biti točna kopija izvorne u većini stvarnih skupova podataka jer u stvarnom životu ljudi ne rade množenja i zbrajanja da bi ocijenili film. U većini slučajeva ocjena je samo osjećaj za utrobu na koji također mogu utjecati sve vrste vanjskih čimbenika. Ipak, nadamo se da je linearna formula dobar način da se izrazi glavna logika koja pokreće ocjene korisnika.

U redu, sada imamo približnu matricu. Ali kako nam, dovraga, to pomaže u predviđanju ocjena koje nedostaju? Imajte na umu da smo za izgradnju nove matrice stvorili formulu za popunjavanje svih vrijednosti, uključujući one koje nedostaju u izvornoj matrici. Dakle, ako želimo predvidjeti ocjenu korisnika koji nedostaje nekom filmu, samo uzmemo sve značajke tog filma, pomnožimo sa svim težinama tog korisnika i sve saberemo. Dakle, u svom primjeru, ako želim predvidjeti ocjenu Korisnika 2 za Film 1, mogu izvršiti sljedeći izračun:

Da bismo stvari učinili jasnijima, možemo razdvojiti θ i x i staviti ih u njihove vlastite matrice (recimo P i Q ). To je zapravo faktorizacija matrice, pa otuda i naziv koji koristi prof. Ng.

Ta je matrična faktorizacija u osnovi ono što je Funk učinio. U Netflixovoj konkurenciji osvojio je treće mjesto, privukavši veliku pažnju (što je zanimljiv slučaj da je treće mjesto slavnije od pobjednika). Njegov se pristup replicirao i usavršio od tada i još uvijek se koristi u mnogim aplikacijama.

Dekompozicija singularne vrijednosti

Unesite dekompoziciju singularne vrijednosti (SVD). SVD je otmjeni način da se matrica faktorizira na tri druge matrice ( A = UΣVᵀ ). Način na koji se vrši SVD jamči da te 3 matrice imaju neka lijepa matematička svojstva.

Postoji mnogo aplikacija za SVD. Jedna od njih je Analiza glavne komponente (PCA), koja upravo smanjuje skup podataka dimenzije n na dimenziju k ( k <n ).

Neću vam iznositi više detalja o SVD-ima jer ni sam ne znam. Poanta je u tome što to nije ista stvar kao što smo to učinili s matričnom faktorizacijom. Najveći dokaz je da SVD stvara 3 matrice, dok Funk-ova faktorizacija matrice stvara samo 2.

Pa zašto se SVD pojavljuje svaki put kad tražim sustave za preporuke? Morao sam malo kopati, ali na kraju sam pronašao neke skrivene dragulje. Prema Luisu Argerichu:

Algoritmi za faktorizaciju matrice koji se koriste za sustave koji preporučuju pokušavaju pronaći dvije matrice: P, Q poput P * Q odgovara ZNANIM vrijednostima matrice korisnosti. Ovaj se princip pojavio u poznatom radu SVD ++ “Faktorizacija u susret susjedstvu” koji je nažalost koristio naziv “SVD ++” za algoritam koji nema apsolutno nikakve veze sa SVD-om .

Za zapisnik, mislim da je Funk, a ne autori SVD ++-a, prvo predložio spomenutu faktorizaciju matrica za sustave koji preporučuju. Zapravo, SVD ++, kao što mu samo ime govori, produžetak je Funkovog rada.

Xavier Amatriain daje nam širu sliku:

Počnimo s isticanjem da metoda koja se obično naziva "SVD" i koja se koristi u kontekstu preporuka nije strogo govoreći matematička dekompozicija singularne vrijednosti matrice, već približan način izračuna aproksimacije niskog ranga matrice minimiziranjem kvadrata izgubljenih pogrešaka. Točniji, iako općenitiji način da se to nazove bio bi faktorizacija matrice. Početnu verziju ovog pristupa u kontekstu Netflixove nagrade predstavio je Simon Funk u svom poznatom blogu Try This at Home. Važno je napomenuti da je pristup "istinskog SVD-a" doista primijenjen na isti zadatak godinama prije, s ne toliko praktičnim uspjehom.

Wikipedia također ima slične podatke zakopane u članku o faktorizmu matrice (sustavi preporučivača):

Izvorni algoritam koji je predložio Simon Funk u svom blogu faktorizirao je matricu ocjenjivanja korisničkih stavki kao proizvod dviju niže dimenzionalnih matrica, prva ima redak za svakog korisnika, dok druga ima stupac za svaku stavku. Redak ili stupac povezan s određenim korisnikom ili stavkom naziva se latentnim čimbenicima. Imajte na umu da se, unatoč imenu, u FunkSVD ne primjenjuje dekompozicija pojedinačne vrijednosti.

Sažeti:

1. SVD je pomalo složena matematička tehnika koja faktorizira matrice u tri nove matrice i ima brojne primjene, uključujući PCA i RS.

2. Simon Funk primijenio je vrlo pametnu strategiju na Netflixovom natjecanju 2006., faktorizirajući matricu na dvije druge i koristeći gradijentni spust kako bi pronašao optimalne vrijednosti značajki i težina. Nije SVD , ali on je svejedno koristio taj izraz da bi opisao svoju tehniku.

3. Najprikladniji izraz za ono što je Funk učinio je Faktorizacija matrice.

4. Zbog dobrih rezultata i slave koja je uslijedila, ljudi još uvijek nazivaju tu tehniku ​​SVD, jer, eto, tako ju je autor nazvao.

Nadam se da ovo pomaže malo razjasniti stvari.