3803952813

Wstęp

Niniejsza praca stanowi podsumowanie moich dotychczasowych zmagań z konkursem Netflix Prize. Celem konkursu jest wygenerowanie możliwie dokładnej prognozy ocen, jakie klienci internetowej wypożyczalni filmów Netflix wystawiają oglądanym przez siebie tytułom. Każda z ocen jest liczbą całkowitą z przedziału [1,5], a prognoza może być oparta praktycznie tylko na bogatej (ponad 100 min rekordów) historii wcześniejszych ocen użytkowników. Jest to szczególny (choć dość typowy) przypadek ogólnego problemu przewidywania preferencji.

Praca rozpoczyna się ogólnym opisem problemu przewidywania preferencji, po którym następuje jego formalna, konkursowa specyfikacja. Następnie przedstawione są najpopularniejsze metody stosowane w tego typu zagadnieniach. O ile w większości są to powszechnie znane i stosowane podejścia, o tyle często ich adaptacja do wymogów konkursu nie jest zadaniem trywialnym.

Pierwszym napotykanym problemem jest rozmiar danych, które należy przetworzyć (ponad 2GB w formie dostarczanej przez Netflbc, ok. 1GB po uważnym skompresowaniu). Powoduje to całą masę problemów technicznych związanych przykładowo z ograniczeniami architektury 32-bitowej albo z dostępną pamięcią RAM. Są to jednak zagadnienia bardziej informatyczne i wypracowane sposoby ich rozwiązywania leżą w zasadzie poza tematem tej pracy. Istotny pozostaje jednak fakt, że z uwagi na ilość przetwarzanych danych na wyniki znacznej części omawianych algorytmów trzeba czekać zazwyczaj kilka godzin, a często nawet dłużej, co znacząco ograniczyło ilość wariantów każdej z metod, które udało mi się przetestować.

Drugim problem związanym z adaptacją omawianych metod do potrzeb przewidywania preferencji jest charakterystyka dostępnych danych. Przykładowo częstym problemem jest fakt, że nie znamy pełnej macierzy ocen (tzn. oceny każdego filmu przez każdego użytkownika). Powoduje to kłopoty z brakiem stosownej metryki w metodzie k-Srodków albo uniemożliwia zastosowanie klasycznego rozkładu na wartości szczególne oraz inne podobne kłopoty.

Zagadnieniem, któremu poświęcam znaczną część pracy jest konfiguracja poszczególnych metod - dobór stosownych parametrów, odpowiednie wstępne przetwarzanie danych itp. Okazuje się, że w wielu sytuacjach jakość otrzymanych rezultatów bardzo mocno zależy od tego typu dopracowania metody. Niestety z uwagi na dostępny czas i możliwości techniczne udało mi się przetestować jedynie ograniczony zestaw spośród wielu możliwych konfiguracji.

Najsilniejszą metodą przewidywania preferencji opisywaną w pracy jest wykorzystanie rozkładu na wartości szczególne (rozdział 6). Metoda została pierwszy raz wykorzystana w konkursie Netflbc Prize przez Simona Funka (zob. [1]) i od tego czasu jest powszechnie stosowana oraz stanowi podstawę wyników większości zespołów z aktualnej czołówki. O ile idea stojąca za omawianym podejściem jest stosunkowo naturalna, o tyle problemem jest jej głębsze zrozumienie i zaproponowanie wydajnej implementacji. W ramach pracy udało mi się opracować i przedstawić alternatywny (inny niż zaproponowany oryginalnie) algorytm znajdowania wartości rozkładu. Pomimo, że osiąga on w konkursie nieco gorsze wyniki posiada kilka ciekawych zalet, które krótko przedstawiam w rozdziale 6.

5