Prawie trzy lata temu Netflix, amerykańska wysyłkowa wypożyczalnia filmów, ogłosiła konkurs na przewidywanie filmowych gustów. Główna nagroda — milion dolarów. Kilka dni temu jeden z zespołów znalazł algorytm spełniający wymagania konkursu, więc jest to dobry moment, żeby przypomnieć całą historię.

W ciągu tych trzech lat informacje o netflix prize pojawiały się w różnych mediach, od technicznego magazynu Wired do New York Timesa i amerykańskiego publicznego radia. Autor nie brał udziału w konkursie, ale ponieważ nie zauważył zainteresowania polskich mediów tym ciekawym tematem, postanowił zwrócić na niego uwagę niniejszym tekstem.

Netflix to wypożyczalnia, która wysyła filmy pocztą (tradycyjną), a od niedawna również przez Internet. Płacąc miesięczny abonament klient może wypożyczać płyty DVD tak często jak chce. Dla przykładu, za $9 (mniej więcej tyle co bilet do kina albo niedrogi lunch w USA) można wypożyczać po jednym filmie, a za $17 po trzy naraz. Po odesłaniu filmów trzeba poczekać parę dni na następną porcję — poczta musi dostarczyć przesyłkę tam i z powrotem. 10M (milionów) klientów ma do dyspozycji 100k (tysięcy) tytułów na 55M płyt. Wypożyczalnia wysyła dziennie około 2M płyt DVD i płaci amerykańskiej poczcie ok. $300M rocznie.

Obejrzane filmy można oceniać, a system, analizując dotychczasowe oceny, poleca kolejne pozycje. Na podstawie tych rekomendacji klienci wypożyczają aż 60% filmów, więc odgadnięcie, co się komu spodoba, jest ważne dla korporacji, bo zniechęceni klienci oglądają mniej filmów i nieraz, dochodząc do wniosku, że stały abonament im się nie opłaca, wracają do tradycyjnych wypożyczalni.

W 2006 roku, przed ogłoszeniem konkursu, było już wiele portali wdrażających ideę wspólnej filtracji (collaborative filtering) oraz sklepów internetowych stosujących spersonalizowane rekomendacje. Byli też naukowcy badający wzorce ludzkich wyborów i szukający najlepszych algorytmów. Wśród nich grupa z Uniwersytetu stanu Minnesota, która przyjęła nazwę GroupLens. Ta grupa zainwestowała sporo czasu w stworzenie MovieLens, jednego z popularniejszych serwisów dających spersonalizowane rekomendacje filmowe. Dzięki temu dysponowała danymi do swoich badań — największą akademicką bazą filmowych ocen — w 2006 roku było to 13M ocen wystawionych przez 140k użytkowników. Mniej więcej tyle ocen, ile Netflix otrzymywuje w ciągu tygodnia.

W październiku 2006 roku Netflix udostępnił małą część swoich danych, 100M ocen, i ogłosił konkurs na najlepszy algorytm przewidujący kolejne oceny. Udostępnione dane z ocenami miały postać czwórek: użytkownik – film – ocena – data wystawienia. Uczestnicy dostali też zbiór testowy w postaci trójek: użytkownik – film – data, i zostali poproszeni o uzupełnienie tego zbioru o oceny. Dla ochrony prywatności klientów użytkownicy zostali oznaczeni numerami i jedyne, co o nich wiadomo, to kiedy i jak oceniali filmy. Upubliczniona baza danych, wraz z obiecaną nagrodą, dały nowy impuls do badań nad collaborative filtering.

W tamtym czasie naukowcy z Minnesoty wydawali się już zmęczeni szukaniem najlepszego algorytmu i zajmowali się innymi tematami. Na przykład tym, czy trafność rekomendacji rzeczywiście odzwierciedla ich użyteczność. W jednej z publikacji wręcz kontestowali istniejące algorytmy, porównując je do systemu dla turystów, który poleca nam podróże w te miejsca, w których już byliśmy. Badali też zagrożenia dla prywatności wynikające z ujawniania swoich preferencji (wideo z wykładu). Wkrótce okazało się jednak, że szukając odpowiedzi na podstawowe pytanie, jaki matematyczny model najlepiej opisuje gusty ludzkie, można odkryć jeszcze wiele nowych rzeczy. I odkryją to uczestnicy konkursu.

Za punkt odniesienia w konkursie posłużył algorytm stosowany wówczas przez Netflixa, nazwany Cinematch. Regulamin przewidywał, że główna nagroda, milion dolarów, zostanie przyznana dopiero 30 dni po tym, jak jedna z drużyn osiągnie wynik o 10% lepszy niż Cinematch (teraz znamy już datę, 30 dni minie 26 lipca). W międzyczasie co rok przyznawano nagrodę za postępy, $50K dla drużyny pierwszej w rankingu.

Za miarę skuteczności algorytmu przyjęto RMSE (pierwiastek z błędu średniokwadratowego, ang. root mean squared error). Cinematch miał RMSE=0.9525. W tydzień po ogłoszeniu konkursu pierwsza z drużyn dysponowała algorytmem dającym mniejszy RMSE. Miesiąc później poprawa wynosiła już około 5%. Rok później — ponad 8%, ale poprawianie wyników stawało się coraz trudniejsze. Pod koniec 2008 roku, kiedy najlepsze drużyny rozciągnięte były między 8 a 9%, niektórzy zawodnicy zastanawiali się, czy cel jest w ogóle możliwy do ociągnięcia. W końcu, dwa lata i 9 miesięcy po rozpoczęciu konkursu, 10% zostało przekroczone.

Zwykła średnia z ocen dla danego filmu, bez żadnej personalizacji, daje RMSE o ok. 10% większy niż Cinematch. RMSE o 10% mniejszy dawał z kolei główną nagrodę. Dużo wskazuje na to, że pomiędzy prostą średnią a najlepszym możliwym algorytmem jest dwadzieścia kilka procent różnicy, a szum, z którym nie da się nic zrobić, przekracza poziom RMSE=0.8. Użytkownicy Netflixa mogą mogą przyznawać filmom od 1 do 5 gwiazdek. Niepewność bliska jednej gwiazdki wydaje się dość duża, bo przecież, obstawiając ocenę na środku skali, możemy się pomylić najwyżej o 2 gwiazdki. Na szum, który uniemożliwia dokładniejsze prognozy, składają się czynniki, których nie sposób uwzględnić w modelu, takie jak nasz humor w trakcie oglądania filmu. Być może przeszkodą jest również mała ilość ocen na skali. Wielu użytkowników Netflixa narzeka na brak połówkowych gwiazdek, ale przeprowadzone testy pokazały, że większy wybór zniechęca ludzi do oceniania. Dziesięć procent poprawy, które było celem konkursu, nie brzmi imponująca, jednak według analizy Yehudy Korena z drużyny prowadzącej w rankingu, niewielka poprawa RMSE, nawet o 1%, przekłada się na znacznie trafniejszy wybór polecanych filmów.

Cinematch, tak samo jak algorytmy w MovieLens, Amazon i większości innych silników rekomendacji w 2006 roku, opierał się na podobieństwie filmów lub użytkowników. Jeśli ktoś ma gust podobny do mojego, to pewnie nasze oceny będą zbliżone również w przyszłości. Jeżeli dwa filmy są oceniane podobnie, to znaczy, że są podobne, więc jeśli wysoko oceniliśmy jeden z nich, to system zakłada, że spodoba nam się również drugi. Podobieństwo obliczano przy użyciu algorytmu k najbliższych sąsiadów (kNN). Tym tropem szli też na samym początku uczestnicy konkursu. Wkrótce jednak nastąpił przełom.

Jedną z rzeczy, która zaskoczyła organizatorów konkursu, było to, jak chętnie uczestnicy dzielą się swoimi doświadczeniami. Wprawdzie organizatorzy zadbali o forum dyskusyjne do wymiany myśli, ale współpraca drużyn przerosła ich oczekiwania. Dyskusje na forum dotyczyły różnych rzeczy. Narzędzi programistycznych. Osobliwości znalezionych w bazie danych, takich jak 17k guy, rekordzista, który ocenił prawie wszystkie filmy (ponad 17k) z udostępnionego podzbioru danych. Ale co najważniejsze, dotyczyły również stosowanych algorytmów. Wielu uczestników, czy to z braku wiary w wygraną, czy z akadmickich przyzwyczajeń, ujawniało swoje sekrety, dzięki czemu wszyscy czynili szybkie postępy.

Przełomem, który nastąpił w pierwszym miesiącu trwania konkursu, było zastosowanie SVD, po polsku: rozkładu macierzy według wartości szczególnych. Odpowiada to rozłożeniu filmów na czynniki, które mogą się podobać lub nie. Okazało się, że porównywanie filmów całościowo daje gorszy rezultat niż porównywanie elementów, które składają się na film, a ludzki gust może być modelowany jako liniowe reakcje na poszczególne elementy. Dwie osoby mogą lubić tego samego aktora, ale jedna z nich może nie lubić magii albo przemocy. Końcowa ocena filmu, zawierającego te i inne elementy, będzie wypadkową wszystkich czynników. Przy dostatecznej ilości danych algorytm może te czynniki rozdzielić. Jeden z członków zespołu prowadzącego w rankingu pisze, że modelowanie widza przy pomocy tylko 50 czynników daje całkiem dobre rezultaty, a powyżej 200 dalsze zwiększanie liczby czynników nie powoduje już poprawy. Powyższy przykład może być o tyle mylący, że film jest rozkładany na czynniki automatycznie. Komputer powie nam, w jakich filmach i w jakich ilościach występuje, dajmy na to, czynnik numer 23, ale interpretacja, co naprawdę te filmy mają ze sobą wspólnego i czemu dany czynnik odpowiada, wydaje się niemożliwa. Na szczęście, nie jest to potrzebne do przewidywania ocen. Co ciekawe, przydatność SVD dla collaborative filtering była już wzmiankowana w pracach naukowych w ubiegłym stuleciu, jednak do czasu konkursu Netflixa nie znalazła szerszego uznania.

Yehuda Koren, w swojej pracy przedstawionej na konferencji w ubiegłym roku, wyróżnia dwa rodzaje podejść do konkursowego problemu: modele sąsiedzkie (czyli podobieństwo filmów bądź użytkowników) i modele z ukrytymi czynnikami (takie jak SVD). Jak pisze, najlepsze rezultaty daje połączenie różnych modeli. Łączenie algorytmów jest tutaj bardzo proste. Dwa algorytmy można połączyć biorąc średnią z przewidywanych ocen. Rozwiązania, które teraz znajdują się w czołówce rankingu, są liniową kombinacją wyników uzyskanych z setek różnych algorytmów.

Walcząc o ostatnie dwa procenty, zawodnicy stosowali coraz bardziej subtelne metody. W roku 2008 najważniejszym postępem stało się uwzględnienie daty oceny i zmienności gustu w czasie. Dużo pracy włożono też, aby zbudować lepszy model przy użyciu danych zewnętrznych, takich jak gatunek filmu albo występujący aktorzy. W końcu jednak okazało się, że dodatkowe informacje nic nie wnoszą do przewidywania ocen.

Granicę 10% została przekroczona po połączeniu się dwóch drużyn z czołówki. Powstały zespół, BellKor’s Pragmatic Chaos, aktualnie z wynikiem 10,05%, składa się łącznie z trzech drużyn, a jego najgroźniejszy konkurent, Grand Prize Team, 9,84%, to 9 zespołów, które wymieszały swoje wyniki.

Grupa BellKor’s Pragmatic Chaos składa się z siedmiu specjalistów z USA, Kanady, Austrii i Izraela. Jeszcze nie jest pewne, czy to oni zdobędą główną nagrodę, ale wygląda na to, że niektórzy z pozostałych uczestników też mogą być zadowoleni z udziału w zabawie. Ponad rok temu magazyn Wired poświęcił długi artykuł bezrobotnemu psychologowi z Londynu (bezrobotnemu z wyboru), który niespodziewanie znalazł się w czołówce. W matematyce pomagała mu córka. Obecnie psycholog prowadzi rodzinną firmę zajmującą się podobnymi analizami i pisze, że ma więcej zleceń niż jest w stanie przyjąć.