Yksittäisen arvon hajoaminen vs. matriisifaktorointi suositusjärjestelmissä

Viime aikoina, kun katselin professori Andrew Ng: n koneoppimiskurssin Suosittelijajärjestelmät-luokkaa, huomasin olevani hyvin epämiellyttävä ymmärtämättä, miten Matrix Factorization toimii.

Tiedän, että koneoppimisen matematiikka on joskus hyvin hämärää. On parempi, jos ajattelemme sitä mustana laatikkona, mutta tuo malli oli erittäin maaginen standardini mukaan.

Tällaisissa tilanteissa yritän yleensä etsiä Googlesta lisää viitteitä käsitteen ymmärtämiseksi paremmin. Tällä kertaa sekaisin vielä enemmän. Vaikka professori Ng kutsui algoritmia matalatekijöiseksi matriisifaktorisaatioksi, löysin Internetistä toisen nimikkeistön: Singular Value Decomposition.

Eniten hämmensi minua se, että singulaariarvon hajoaminen oli hyvin erilainen kuin prof. Ng oli opettanut. Ihmiset ehdottivat jatkuvasti, että he olivat molemmat sama asia.

Tässä tekstissä esitän yhteenvedon havainnoistani ja yritän selvittää joitain sekaannuksia, joita nämä termit voivat aiheuttaa.

Suosittelijajärjestelmät

Suosittelijajärjestelmät (RS) ovat vain automatisoituja tapoja suositella jotain jollekin. Tällaisia ​​järjestelmiä käyttävät laajasti verkkokaupan yritykset, suoratoistopalvelut ja uutissivustot. Se auttaa vähentämään käyttäjien kitkaa yrittäessään löytää jotain, josta he pitävät.

RS eivät todellakaan ole uusi asia: ne ovat olleet esillä ainakin vuodesta 1990 lähtien. Itse asiassa osa viimeaikaisesta koneoppimisen hypeestä voidaan liittää kiinnostukseen RS: ään. Vuonna 2006 Netflix teki tilaisuuden, kun he sponsoroivat kilpailua parhaan RS: n löytämiseksi elokuvilleen. Kuten näemme pian, tapahtuma liittyy seuraavaan nimikkeistön sotkuun.

Matriisin esitys

On monia tapoja, joilla henkilö voi ajatella suositella elokuvaa jollekulle. Yksi erittäin hyväksi osoittautunut strategia on elokuvien luokittelun käsitteleminen Käyttäjät x Elokuvat -matriisina näin:

Kyseisessä matriisissa kysymysmerkit edustavat elokuvia, joita käyttäjä ei ole arvioinut. Strategiana on sitten ennustaa jotenkin arviot ja suositella käyttäjille elokuvia, joista he todennäköisesti pitävät.

Matriisifaktorointi

Netflixin kilpailuun osallistuneiden kaverien (erityisesti Simon Funk) tekemä todella fiksu oivallus oli, että käyttäjien arviot eivät olleet vain satunnaisia ​​arvauksia. Arvioijat arvioivat todennäköisesti jonkin logiikan, jossa he painottavat elokuvassa pitämiään asioita (tietty näyttelijä tai tyylilaji) asioihin, joista he eivät pidä (pitkäaikainen tai huono vitse) ja keksivät sitten pisteet.

Tämä prosessi voidaan esittää seuraavanlaisella lineaarisella kaavalla:

jossa xₘ on pystyvektori arvojen kanssa ominaisuuksia elokuvan m ja θᵤ on toinen sarake vektori, painot, jotka käyttäjä u antaa kunkin ominaisuuden. Jokaisella käyttäjällä on erilaiset painot ja jokaisella elokuvalla on erilaiset arvot ominaisuuksilleen.

On käynyt ilmi, että jos korjaamme mielivaltaisesti ominaisuuksien lukumäärän ja jätämme huomiotta puuttuvat luokitukset, voimme löytää joukon paino- ja ominaisuusarvoja, jotka luovat uuden matriisin, jonka arvot ovat lähellä alkuperäistä luokitusmatriisia. Tämä voidaan tehdä kaltevalla laskeutumisella, aivan kuten lineaarisessa regressiossa. Sen sijaan optimoimme nyt kaksi parametrisarjaa (painot ja ominaisuudet) samanaikaisesti.

Käyttämällä yllä olevaa esimerkkiä antamaani taulukkoa optimointiongelman tulos tuottaisi seuraavan uuden matriisin:

Huomaa, että tuloksena oleva matriisi ei voi olla tarkka kopio alkuperäisestä useimmissa todellisissa aineistoissa, koska tosielämässä ihmiset eivät tee kertoja ja yhteenvetoja arvioidakseen elokuvaa. Useimmissa tapauksissa luokitus on vain suoliston tunne, johon kaikenlaiset ulkoiset tekijät voivat vaikuttaa. Toivomme kuitenkin, että lineaarinen kaava on hyvä tapa ilmaista päälogiikka, joka ohjaa käyttäjien luokituksia.

OK, nyt meillä on likimääräinen matriisi. Mutta kuinka helvetti auttaa meitä ennustamaan puuttuvat arviot? Muista, että uuden matriisin rakentamiseksi loimme kaavan, joka täyttää kaikki arvot, myös ne, jotka puuttuvat alkuperäisestä matriisista. Joten jos haluamme ennustaa käyttäjän puuttuvan luokituksen elokuvassa, otamme vain kaikki elokuvan ominaisuusarvot, kerrotaan kyseisen käyttäjän kaikilla painoilla ja summataan kaikki yhteen. Joten esimerkissäni, jos haluan ennustaa Käyttäjä 2: n luokituksen Elokuva 1: lle, voin tehdä seuraavan laskelman:

Jotta asiat olisivat selkeämpiä, voimme erottaa θ: t ja x: t ja laittaa ne omiin matriiseihinsa (sanoa P ja Q ). Se on tosiasiallisesti Matrix Factorization, joten nimi, jota professori Ng.

Tuo Matrix Factorization on pohjimmiltaan Funk. Hän sai kolmannen sijan Netflixin kilpailussa houkuttelemalla paljon huomiota (mikä on mielenkiintoinen tapaus kolmannen sijan ollessa kuuluisampi kuin voittajat). Hänen lähestymistapaansa on toistettu ja parannettu siitä lähtien, ja sitä käytetään edelleen monissa sovelluksissa.

Yksittäisen arvon hajoaminen

Syötä singulaariarvon hajoaminen (SVD). SVD on hieno tapa jakaa matriisi kolmeen muuhun matriisiin ( A = UΣVᵀ ). Tapa, jolla SVD suoritetaan, takaa, että näillä 3 matriisilla on mukavia matemaattisia ominaisuuksia.

SVD: lle on monia sovelluksia. Yksi niistä on pääkomponenttianalyysi (PCA), joka vain pienentää ulottuvuuden n tietojoukon ulottuvuudeksi k ( k <n ).

En anna sinulle lisätietoja SVD: stä, koska en tunne itseäni. Asia on, että se ei ole sama asia kuin teimme Matrix Factorizationin kanssa. Suurin todiste on siitä, että SVD luo 3 matriisia, kun taas Funkin Matrix Factorization vain 2.

Joten miksi SVD ilmestyy jatkuvasti joka kerta kun etsin Suosittelijajärjestelmiä? Minun täytyi kaivaa vähän, mutta lopulta löysin piilotettuja helmiä. Luis Argerichin mukaan:

Suositusjärjestelmissä käytettävät matriisifaktorointialgoritmit yrittävät löytää kaksi matriisia: P, Q, kuten P * Q, vastaavat apuohjelmamatriisin TUNNETUT arvot. Tämä periaate ilmestyi kuuluisassa SVD ++ -lehdessä "Factorization meets the neighborhood", jossa valitettavasti käytettiin nimeä "SVD ++" algoritmille, jolla ei ole mitään yhteyttä SVD: hen .

Uskon, että Funk, joka ei ole SVD ++: n kirjoittaja, ehdotti ensin mainittua matriisifaktorointia suositusjärjestelmille. Itse asiassa SVD ++, kuten nimestäkin käy ilmi, on Funkin jatke.

Xavier Amatriain antaa meille suuremman kuvan:

Aloitetaan huomauttamalla, että suositusten yhteydessä käytetty menetelmä, jota yleensä kutsutaan SVD: ksi, ei tarkoita matriisin matemaattista singulaariarvon hajoamista , vaan pikemminkin likimääräinen tapa laskea matriisin matalatasoinen likiarvo minimoimalla neliövirhehäviöt. Tarkempi, vaikkakin yleisempi tapa kutsua tätä olisi Matrix Factorization. Alustavan version tästä lähestymistavasta Netflix-palkinnon yhteydessä esitti Simon Funk kuuluisassa Try This at Home -blogissa. On tärkeää huomata, että ”tosi SVD” -lähestymistapaa oli todellakin sovellettu samaan tehtävään vuosia aikaisemmin, eikä käytännön menestys ollut niin suuri.

Wikipedia sisältää myös vastaavia tietoja matriisifaktorointia (suosittelijajärjestelmiä) koskevassa artikkelissa:

Simon Funkin blogikirjoituksessaan ehdottama alkuperäinen algoritmi kertoi käyttäjän kohteiden luokitusmatriisin kahden alemman ulottuvuuden matriisin tulona, ​​ensimmäisessä on rivi kullekin käyttäjälle, kun taas toisessa sarake kullekin tuotteelle. Tiettyyn käyttäjään tai kohteeseen liittyvää riviä tai saraketta kutsutaan piileviksi tekijöiksi. Huomaa, että nimestään huolimatta FunkSVD: ssä ei sovelleta yksikköarvon hajotusta.

Yhteenvetona:

1. SVD on melko monimutkainen matemaattinen tekniikka, joka ottaa huomioon matriisit kolmen uuden matriisin sisällä ja jolla on monia sovelluksia, mukaan lukien PCA ja RS.

2. Simon Funk sovelsi erittäin älykästä strategiaa vuoden 2006 Netflix-kilpailussa jakamalla matriisin kahteen muuhun ja käyttämällä kaltevuuslaskua ominaisuuksien ja painojen optimaalisten arvojen löytämiseen. Se ei ole SVD , mutta hän käytti joka tapauksessa tätä tekniikkaa kuvaamaan tekniikkaansa.

3. Tarkempi termi Funkin toiminnalle on Matrix Factorization.

4. Hyvien tulosten ja sitä seuranneen maineen vuoksi ihmiset kutsuvat tätä tekniikkaa edelleen SVD: ksi, niin, niin kirjoittaja nimitti sen.

Toivon, että tämä auttaa selventämään asioita hieman.