m_rcin

Milion dolarów za rozszyfrowanie filmowych gustów

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

Netflix nie jest tradycyjną wypożyczalnią. Klienci zamawiają filmy przez Internet, a płyty DVD dostarczane są pocztą. Po obejrzeniu filmu, można go ocenić, 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, przekłada się na zadowolenie klientów i zysk korporacji.

W 2006 roku, przed ogłoszeniem konkursu, idea wspólnej filtracji (ang. collaborative filtering), czyli rekomendacji udzielanych na podstawie zachowania się innych klientów, była powszechnie znana i stosowana przez wiele portali i sklepów internetowych. Algorytmy dające spersonalizowane rekomendacje były też tematem badań niektórych naukowców. Grupa badawcza z Uniwersytetu stanu Minnesota zainwestowała sporo czasu w stworzenie serwisu MovieLens, który pozwala oceniać filmy i, tak jak system Netflixa, przewiduje, jak użytkownikom spodobają się kolejne filmy. W 2006 roku MovieLens miał 140 tys. użytkowników, którzy wystawili łącznie 13 milionów ocen. Była to największa taka baza danych stworzona dla celów akademickich, a serwis MovieLens służył do różnych eksperymentów i stał się podstawą wielu prac naukowych. Jednak jesienią 2006 naukowcy z Minnesoty nagle stracili przewagę, jaką dawały im zgromadzone dane.

W październiku 2006 roku Netflix udostępnił publicznie część swoich danych, 100 milionów ocen wystawionych przez pół miliona klientów, i ogłosił konkurs na najlepszy algorytm przewidujący kolejne oceny. Konkursy, jako sposób na rozwiązywanie problemów, stały się modne po spektakularnym sukcesie zakończonego w 2004 roku konkursu na statek kosmiczny wielokrotnego użytku. Są też częścią szerszego trendu, crowdsourcingu (nazwa ukuta przez magazyn Wired w czerwcu 2006), który polega na outsourcingu zadań, tradycyjnie wykonywanych przez pracowników, do niesprecyzowanej grupy ludzi (tłumu, ang. crowd), których dane zadanie zainteresuje. Konkurs Netflixa stał się kolejnym przykładem na skuteczność tłumu w rozwiązywaniu trudnych problemów. Setki bądź tysiące ludzi, którzy poświęcili swój wolny czas na badanie algorytmów rekomendacji, znacznie rozszerzyło wiedzę w tej dziedzinie.

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, 50 tys. dolarów 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 (czyli lepszy) 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.

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 17 tys.) 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 akademickich 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 z ulubionym aktorem 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.

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. Rozwiązania, które teraz znajdują się w czołówce rankingu, są liniową kombinacją wyników uzyskanych z setek różnych algorytmów. Co ciekawe, dodatkowe informacje, takie jak gatunek filmu albo reżyser, nic nie wnoszą do przewidywania ocen.

Grupa BellKor’s Pragmatic Chaos, która tydzień temu przekroczyła granicę 10%, 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ąć.

Dłuższa i bardziej techniczna wersja artykułu ukazała się w serwisie osnews.pl.

Zdjęcie koperty z filmem zrobił BlueMint, fragment interfejsu Movielens skopiował autor.

CC-BY

Ten utwór jest dostępny na licencji Creative Commons Uznanie autorstwa 2.5 Polska.