Stavolta Deus vult: Netflix Prize

Dio mi aveva dato dei numeri da giocare al superenalotto per diventare milionario, ma io ho dubitato e non ho vinto. Dio, però nella sua misericordia, mi ha perdonato e dopo avermi mandato un nuovo segno (perché quello è la doppia macchia di umidità comparsa nel soggiorno appena ridipinto, vero?) mi ha fatto capire che mi vuole non solo ricco, ma anche famoso! L’occasione mi viene data dal Netflix Prize. Netflix, ancora poco sperimentato in Italia, è un servizio online di noleggio DVD molto conosciuto negli Stati Uniti. Ciò che rende veramente unico ed interessante questa azienda è il modo in cui il servizio viene offerto: pagando una quota mensile che va dai 5 fino ai 50 dollari al mese, si scrive sul sito una lista, grande a piacere, di film che vorremmo vedere, Netflix spedisce a casa un busta contenente i primi tre film della lista che possono essere visti e tenuti quanto si vuole, dopodiché usando la stessa busta preaffrancata con cui sono arrivati i film si rispediscono uno o più DVD indietro e Netflix in risposta vi manderà un ugual numero di film scelti tra quelli seguenti nella lista iniziale. Il numero di DVD totali che si possono vedere in un mese varia ovviamente con il profilo tariffario scelto. Gli utenti, sul sito, possono poi dare un giudizio sul film visto; voto che va da uno a cinque stelle: elaborando questi dati tramite un algoritmo chiamato Cinematch, Netflix è in grado di suggerire all’utente dei film che non sono nella lista, ma che potrebbero essere di suo gradimento. Insomma Netflix è anche un Recommender System. Qualche anno fa Netflix ha instituito il Netflix Prize un concorso on line aperto a tutti con lo scopo di trovare un algoritmo migliore di Cinematch. Che significa migliore? Netflix mette a disposizione dei partecipanti un enorme database anonimo con i voti di migliaia di utenti su circa diciassettemila film e l’anno in cui il voto è stato dato e un database più piccolo con gli stessi utenti e film del primo, dove però i voti sono cancellati: tramite i dati presenti nel primo database bisogna prevedere il voto di ogni singolo utente nel secondo database. Per fare un esempio, nel primo grande database trovate i voti dell’utente Mario a film come "Guerre Stellari", "Harry Potter" e "Via col vento", e l’anno in cui gli stessi voti sono stati assegnati sapendo ciò dovete prevedere il voto che Mario ha dato a "Forrest Gump" (voto che noi non conosciamo, ma Netflix che è il giudice si). È noto anche qual è la prestazione dell’attuale algoritmo messo alla prova sullo stesso set di dati. Il premio per chi riuscirà a migliorare le prestazioni dell’attuale algoritmo di almeno il 10% è di un milione di dollari! Io mi sono iscritto e di tanto in tanto posterò su questo blog aggiornamenti sull’andamento del concorso.

Attualmente ho scaricato tutto il materiale disponibile sul sito (i database e altri programmi per calcolare la RMSE) e sto cominciando a fare delle valutazioni sui possibili modelli da seguire. L’idea è di valutarli tutti in parallelo e approfondire quello che da subito fornisce i migliori risultati, oppure realizzare dei modelli ibridi. I possibili modelli a cui sto pensando sono per ora sette, suggerimenti e critiche costruttive sono bene accette, soprattutto da altri partecipanti italiani. Ecco le mie idee esposte usando il nostro utente tipo, Mario:

1. E’ la prima idea che mi è venuta; per conoscere il voto che Mario darebbe a "Forrest Gump" potrei individuare altri utenti che hanno gusti simili a quelli di Mario, ma di cui conosco il voto dato a "Forrest Gump". Probabilmente il voto di Mario sarà simile. Per individuare utenti con gusti simili, basta cercare tra coloro che hanno votato in maniera uguale o quasi gli stessi film che ha votato Mario. Questo algoritmo è meglio conosciuto in letteratura come K-nearest neighbors (k-NN). Sembra estremamente promettente ed ha una vasta letteratura, va perfezionato o integrato con altri modelli per potere superare il 10%.
2. Regressione Lineare basata sull’utente. Sfruttando i voti dati agli altri film potrei calcolare per ogni utente, Mario compreso, una funzione matematica del tipo . Dove x è però funzione di altri parametri (sarebbe più corretto, in effetti, parlare di regressione lineare multivariata). Il problema è capire quali sono questi parametri. I fattori che per esempio potrebbero essere discriminanti per la scelta di un film sono il genere, il regista, gli attori presenti, il direttore della fotografia, lo sceneggiatore e il musicista. Purtroppo sono dati che non ho.
3. Regressione Lineare basata sul film. Come prima, ma basata sul singolo film: per ogni film potrei creare una funzione matematica che mi esprime il valore in funzione dei voti espressi ad altri film. Una volta calcolata la funzione matematica associata a "Forrest Gump" basterebbe utilizzare i voti dati da Mario ad altri film per calcolare il probabile voto. Sembra promettente, ma molto impegnativo dal punto di vista computazionale e matematico.
4. Slope One. Leggendo in giro ho trovato questa versione semplificata dell’idea precedente. Consiste nel calcolare il voto medio di un film e vedere come i voti dati agli altri film lo modificano mediamente in positivo o in negativo. Sembra promettente, ma meno accurato del precedente, occorrerebbe trovare una via di mezzo.
5. Per ogni film e per ogni classe di voto (cinque classi ogni film) si potrebbe calcolare un modello probabilistico di utente tipo che potrebbe esprimere quel determinato voto per quel determinato film. Bisognerebbe poi vedere a quale classe di utente tipo si avvicina il nostro Mario per il suddetto film. Mi sembra realizzabile, anche se occorrerebbe capire se esistono dati sufficienti per ogni film per fornire un profilo statisticamente credibile per ogni voto possibile.
6. Realizzare un classificatore Bayesiano. L’idea mi è venuta pensando ai filtri antispam: applicando il teorema di Bayes si potrebbe calcolare qual è la probabilità che Mario dia un determinato voto a "Forrest Gump" condizionata ai voti dati agli altri film. Sembra promettente anche se occorre un largo database.
7. Realizzare una rete neurale. Forse la soluzione "più semplice", se la rete è ben addestrata, ma mi lascia perplesso per due motivi. Conosco la teoria delle reti neurali e delle tecniche di apprendimento per retro propagazione, ma non ne ho mai realizzata una; una rete neurale non è un algoritmo è una soluzione a "scatola chiusa" del problema, certo rappresenta una approssimazione non lineare del problema ma è complesso se non impossibile capire i meccanismi interni che hanno portato ad una determinata scelta invece che ad un’altra.

Io comincio, vi iscrivete anche voi?