Vienkartinės vertės skaidymas ir matricos faktorizavimas rekomenduojančiose sistemose

Neseniai, peržiūrėjęs prof. Andrew Ng mašininio mokymo kursą „Rekomenduojančios sistemos“, man pasidarė labai nepatogu nesuprasti, kaip veikia „Matrix Factorization“.

Aš žinau, kad kartais mašininio mokymosi matematika yra labai neaiški. Geriau, jei mes galvojame apie tai kaip apie juodą dėžę, bet tas modelis buvo labai „stebuklingas“ mano standartams.

Tokiose situacijose dažniausiai stengiuosi ieškoti „Google“ daugiau nuorodų, kad geriau suprasčiau šią sąvoką. Šį kartą dar labiau sutrikau. Nors prof. Ng algoritmą vadino (mažo faktoriaus) matricos faktorizavimu, aš internete radau kitokią nomenklatūrą: „Singular Value Decomposition“.

Labiausiai mane glumino tai, kad vienaskaitos vertės skaidymas labai skyrėsi nuo to, ko mokė prof. Ng. Žmonės vis teigė, kad jie abu yra tas pats.

Šiame tekste apibendrinsiu savo išvadas ir bandysiu išaiškinti kai kuriuos painiavus, kuriuos gali sukelti šie terminai.

Rekomenduojančios sistemos

Rekomenduojančios sistemos (RS) yra tik automatizuoti būdai ką nors rekomenduoti. Tokias sistemas plačiai naudoja elektroninės prekybos įmonės, srautinio perdavimo paslaugos ir naujienų svetainės. Tai padeda sumažinti vartotojų trintį bandant rasti tai, kas jiems patinka.

RS tikrai nėra naujas dalykas: jie buvo pristatomi mažiausiai nuo 1990 m. Tiesą sakant, dalį naujausio mašininio mokymosi ažiotažo galima priskirti susidomėjimui RS. 2006 m. „Netflix“ sukėlė nerimą, kai rėmė konkursą, kuriame ieškojo geriausio savo filmų RS. Kaip netrukus pamatysime, tas įvykis yra susijęs su tolesne nomenklatūros netvarka.

Matricos pavaizdavimas

Yra daug būdų, kaip žmogus gali sugalvoti kam nors rekomenduoti filmą. Viena strategija, kuri pasirodė labai gera, yra filmų įvertinimų traktuojimas kaip „Vartotojų x filmų“ matricos šitaip:

Toje matricoje klaustukai rodo filmus, kurių vartotojas neįvertino. Tuomet strategija yra kažkaip nuspėti tuos reitingus ir rekomenduoti vartotojams filmus, kurie jiems tikriausiai patiks.

Matricos faktorizavimas

Tikrai protingas vaikinų, dalyvavusių „Netflix“ konkurse (ypač Simonas Funkas) supratimas buvo tas, kad vartotojų įvertinimai nebuvo tik atsitiktiniai spėjimai. Reitinguotojai tikriausiai vadovaujasi tam tikra logika, kai jie vertina filmui patinkančius dalykus (konkrečią aktorę ar žanrą) prieš tai, kas jiems nepatinka (ilga trukmė ar blogi pokštai), tada sugalvoja balą.

Tą procesą galima pavaizduoti tokia linijine formule:

kur xₘ yra stulpelis vektorius su filmo funkcijų reikšmių m ir θᵤ yra kita skiltis vektorius su svoriais, kad vartotojas U suteikia kiekvienam funkcija. Kiekvienas vartotojas turi skirtingą svorių rinkinį, o kiekvieno filmo savybės yra skirtingos.

Pasirodo, jei savavališkai pataisysime funkcijų skaičių ir nepaisysime trūkstamų įvertinimų, galime rasti svorių ir funkcijų verčių rinkinį, kuris sukuria naują matricą, kurios vertės yra artimos pradinei vertinimo matricai. Tai galima padaryti su gradientiniu nusileidimu, labai panašiu į tą, kuris naudojamas tiesinei regresijai. Vietoj to dabar vienu metu optimizuojame du parametrų rinkinius (svorius ir savybes).

Naudojant lentelę, kurią pateikiau kaip pavyzdį aukščiau, optimizavimo problemos rezultatas sukurs šią naują matricą:

Atkreipkite dėmesį, kad gaunama matrica negali būti tiksli originalo kopija daugumoje realių duomenų rinkinių, nes realiame gyvenime žmonės nedaro dauginimo ir apibendrinimo, kad įvertintų filmą. Daugeliu atvejų reitingas yra tik žarnyno jausmas, kurį taip pat gali paveikti įvairūs išoriniai veiksniai. Vis dėlto mes tikimės, kad tiesinė formulė yra geras būdas išreikšti pagrindinę logiką, skatinančią vartotojų reitingus.

Gerai, dabar mes turime apytikslę matricą. Bet kaip gi tai padeda mums numatyti trūkstamus reitingus? Atminkite, kad norėdami sukurti naują matricą, mes sukūrėme formulę, kad užpildytume visas reikšmes, įskaitant tas, kurių trūksta pradinėje matricoje. Taigi, jei norime numatyti trūkstamą vartotojo reitingą filme, mes tiesiog imame visas to filmo funkcijų vertes, padauginame iš visų to vartotojo masių ir viską susumuojame. Taigi, savo pavyzdžiu, jei noriu nuspėti „User 2“ 1 filmo įvertinimą, galiu atlikti šiuos skaičiavimus:

Kad viskas būtų aiškiau, galime atskirti θ ir x ir suskirstyti juos į savo matricas (sakykime P ir Q ). Tai iš tikrųjų yra „Matrix Factorization“, taigi ir prof. Ng naudojamas vardas.

Ta „Matrix Factorization“ iš esmės yra tai, ką Funkas padarė. „Netflix“ konkurse jis gavo trečią vietą, pritraukdamas daug dėmesio (o tai yra įdomus atvejis, kai trečioji vieta yra garsesnė už nugalėtojus). Nuo tada jo požiūris buvo pakartotas ir patobulintas ir vis dar naudojamas daugelyje programų.

Vienaskaitos vertės suskaidymas

Įveskite pavienės vertės skaidymą (SVD). SVD yra išgalvotas būdas suskaidyti matricą į tris kitas matricas ( A = UΣVᵀ ). SVD atlikimo būdas garantuoja, kad šios 3 matricos turi puikių matematinių savybių.

Yra daugybė SVD programų. Vienas iš jų yra pagrindinio komponento analizė (PCA), kuri tik sumažina n matmens duomenų rinkinį iki k ( k <n ).

Nepateiksiu daugiau informacijos apie SVD, nes pats nepažįstu. Esmė ta, kad tai nėra tas pats, ką mes darėme su „Matrix Factorization“. Didžiausias įrodymas yra tai, kad SVD sukuria 3 matricas, o Funko „Matrix Factorization“ - tik 2.

Taigi kodėl SVD nuolat pasirodo kiekvieną kartą, kai ieškau „Rekomenduojančių sistemų“? Teko truputį kasti, bet galiausiai radau paslėptų brangakmenių. Pasak Luiso Argericho:

Rekomenduojančiose sistemose naudojami matricos faktorizavimo algoritmai bando rasti dvi matricas: P, Q, pvz., P * Q, sutampa su žinomomis naudingumo matricos reikšmėmis. Šis principas pasirodė garsiajame SVD ++ „Faktorizavimas atitinka kaimynystę“ dokumente, kuriame, deja, buvo naudojamas „SVD ++“ pavadinimas algoritmui, visiškai neturinčiam jokių ryšių su SVD .

Įrašai, manau, kad Funkas, o ne „SVD ++“ autoriai, pirmiausia pasiūlė minėtą rekomenduojančių sistemų matricos faktorizavimą. Tiesą sakant, SVD ++, kaip rodo jo pavadinimas, yra Funko pratęsimas.

Xavieras Amatriainas suteikia mums didesnį vaizdą:

Pradėkime pažymėdami, kad rekomendacijų kontekste naudojamas metodas, paprastai vadinamas „SVD“, nėra griežtai matematinis matricos singuliarinės vertės skaidymas , o apytikslis būdas apskaičiuoti žemos rangos matricos aproksimaciją sumažinant klaidų praradimą kvadratu. Tikslesnis, nors ir bendresnis būdas tai pavadinti būtų „Matrix Factorization“. Pradinę šio požiūrio versiją „Netflix“ prizo kontekste Simonas Funkas pristatė savo garsiajame „Try This at Home“ tinklaraštyje. Svarbu pažymėti, kad „tikrasis SVD“ metodas iš tikrųjų buvo taikomas tam pačiam uždaviniui prieš daugelį metų ir nebuvo toks praktinis.

„Wikipedia“ taip pat yra panaši informacija, esanti „Matrix factorization“ (rekomenduojančių sistemų) straipsnyje:

Originalus algoritmas, kurį Simonas Funkas pasiūlė savo tinklaraščio įraše, atsižvelgė į vartotojo elementų įvertinimo matricą kaip dviejų apatinių matricų sandaugą, pirmoji turi eilutę kiekvienam vartotojui, o antroji turi stulpelį kiekvienam elementui. Eilutė arba stulpelis, susietas su konkrečiu vartotoju ar elementu, vadinami latentiniais veiksniais. Atkreipkite dėmesį, kad, nepaisant jo pavadinimo, FunkSVD netaikomas vienaskaitos vertės skaidymas.

Apibendrinti:

1. SVD yra šiek tiek sudėtinga matematinė technika, kuri suskirsto matricas į tris naujas matricas ir turi daugybę programų, įskaitant PCA ir RS.

2. Simonas Funkas 2006 m. „Netflix“ konkurse pritaikė labai išmanią strategiją, suskirstydamas matricą į dvi kitas ir naudodamasis gradientiniu nusileidimu, kad surastų optimalias funkcijų ir svorio vertes. Tai nėra SVD , tačiau jis vis tiek vartojo šį terminą savo technikai apibūdinti.

3. Tinkamesnis terminas tam, ką padarė Funkas, yra „Matrix Factorization“.

4. Dėl gerų rezultatų ir po to sekusios šlovės žmonės vis tiek tą techniką vadina SVD, nes, na, taip autorius ją ir pavadino.

Tikiuosi, kad tai padės šiek tiek išsiaiškinti dalykus.