• Home
  • Technologie
    • Bezpieczeństwo
    • Sprzęt
    • Oprogramowanie
    • Mobile
  • Kryptowaluty
  • Marketing
    • Reklama
    • Social Media
  • Finanse
  • Felietony
  • [IP]
  • Kontakt
    • Reklama w OSnews
    • Pakiet Public Relations
    • Content Marketing w OSnews
OSnews.pl
OSnews.pl
  • Home
  • Technologie
    • Bezpieczeństwo
      Prawda czy fikcja? Popularny były haker twierdzi, że ma 7 miliardów dolarów w BTC

      Prawda czy fikcja? Popularny były haker twierdzi, że ma 7 miliardów dolarów w BTC

      Certyfikat SSL, a hosting – dlaczego warto poszukać serwera z darmowymi certyfikatami?

      Certyfikat SSL, a hosting – dlaczego warto poszukać serwera z darmowymi certyfikatami?

      75-latek dorabiał do emerytury na szyfrowaniu cudzych danych

      75-latek dorabiał do emerytury na szyfrowaniu cudzych danych

      Ujawniono najczęściej używane hasła w 2016 roku

      Ujawniono najczęściej używane hasła w 2016 roku

    • Sprzęt
      Tanie laptopy poleasingowe – czym się charakteryzują i co je różni od nowego sprzętu z marketu?

      Tanie laptopy poleasingowe – czym się charakteryzują i co je różni od nowego sprzętu z marketu?

      Jaki tablet dla dziecka?

      Jaki tablet dla dziecka?

      Pancerne laptopy – sprzęt, który sprawdza się w każdych warunkach

      Pancerne laptopy – sprzęt, który sprawdza się w każdych warunkach

      Zadbaj o swój kręgosłup i spraw sobie wygodne krzesło biurowe

      Zadbaj o swój kręgosłup i spraw sobie wygodne krzesło biurowe

    • Oprogramowanie
      Jak zrobić dobrze wyglądające wideo nawet jeśli nie jesteś profesjonalistą

      Jak zrobić dobrze wyglądające wideo nawet jeśli nie jesteś profesjonalistą

      Ta firma potrafi śledzić ruch przy pomocu dźwięku zamiast światła

      Ta firma potrafi śledzić ruch przy pomocu dźwięku zamiast światła

      Dzięki Google nasze smartfony będą na tyle inteligentne, że będą rozpoznawać ludzi i przedmioty w filmach wideo

      Dzięki Google nasze smartfony będą na tyle inteligentne, że będą rozpoznawać ludzi i przedmioty w filmach wideo

      Tłumacz Google wspomagany sztuczną inteligencją działa z trzema nowymi językami

      Tłumacz Google wspomagany sztuczną inteligencją działa z trzema nowymi językami

    • Mobile
      Prawdziwie multimedialny Samsung Galaxy A5 (2017)

      Prawdziwie multimedialny Samsung Galaxy A5 (2017)

      LTE w smartfonie - nie tylko do social media

      LTE w smartfonie - nie tylko do social media

      Nadchodzące premiery smartfonów - Samsung Galaxy S9, LG G7 i inne

      Nadchodzące premiery smartfonów - Samsung Galaxy S9, LG G7 i inne

      Kupujemy smartfon. O czym pamiętać?

      Kupujemy smartfon. O czym pamiętać?

  • Kryptowaluty
  • Marketing
    • Reklama
    • Social Media
  • Finanse
  • Felietony
  • [IP]
  • Kontakt
    • Reklama w OSnews
    • Pakiet Public Relations
    • Content Marketing w OSnews
  • Follow
    • Facebook
    • Twitter
    • RSS

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.

fragment interfejsu serwisu MovieLens

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ąć.

  • Tags
  • algorytmy
  • media
  • programowanie
  • rekomendacje
Facebook Twitter Google+ LinkedIn Pinterest
Następny wpis W3C zamrozi rozwój XHTML na rzecz HTML 5
Poprzedni wpis Android Netbook od Nokii | aktualizacja: jednak nie

Warto przeczytać

Warsztaty programowania dla dzieci - czy warto ? Technologie

Warsztaty programowania dla dzieci - czy warto ?

Zaprogramowani.com. Szkoła programowania dla dzieci i młodzieży w wieku szkolnym. Technologie

Zaprogramowani.com. Szkoła programowania dla dzieci i młodzieży w wieku szkolnym.

Najbardziej opłacalne języki programowania – które są najbardziej pożądane na rynku? Technologie

Najbardziej opłacalne języki programowania – które są najbardziej pożądane na rynku?

Tagi

android apple bezpieczeństwo biznes cenzura Debian edukacja facebook Firefox firma google gry hardware imprezy intel internet iphone kaspersky KDE kraj Laptopy Linux media microsoft mobile mozilla open-source oprogramowanie piractwo prawo press-release programowanie prywatność reklama Samsung smartfon Smartfony software standardy Ubuntu UNIX usa windows Wydania Wydarzenia

O blogu



OSNews to serwis poświęcony nowym technologiom oraz ich roli we współczesnym biznesie. Opowiadamy o przydatnych usługach, zmianach na rynku oraz najnowszym oprogramowaniu, które ułatwi Tobie pracę.
  • Home
  • Technologie
  • Kryptowaluty
  • Marketing
  • Finanse
  • Felietony
  • [IP]
  • Kontakt
  • Back to top

Meta

  • Zaloguj się
  • Kanał wpisów
  • Kanał komentarzy
  • WordPress.org

Kontakt

Masz jakieś pytania? Chcesz podzielić się swoimi uwagami na temat serwisu? Nie ma sprawy, po prostu napisz do nas maila.

OSNews.pl
Conrada 30
01-920 Warszawa
redakcja@osnews.pl
© OSnews.pl 2016-2023. All rights reserved.