Systemy rekomendacyjne
Z systemami rekomendacyjnymi spotykamy się niemal codziennie. Towarzyszą nam one w wielu dziedzinach życia, czy to kupujemy w sklepie internetowym czy słuchamy muzyki na Youtubie. Jakiś algorytm próbuje ustalić, jakie produkty nam się spodobają. Można się nawet spotkać z opinią że niektóre rekomendacje nie są trafne jedynie po to, abyśmy nie czuli się obserwowani. Wyobraźmy sobie co by było w przeciwnym przypadku. Jakkolwiek może wydawać się niepokojące to, jak wiele wiedzą o nas takie systemy, stoją za nimi ciekawe techniki i algorytmy.
W problemie rekomendacji występują użytkownicy i produkty. To które któremu rekomendujemy jest w gruncie rzeczy obojętne, nieistotne czy rekomendujemy produkty użytkownikom czy użytkowników produktom. Można sobie to wyobrazić jako macierz użytkownicy na produkty której wartości reprezentują to, na ile użytkownik i produkt do siebie pasują. Jest to często macierz rzadka, a jej puste pola należy interpretować jako nieznane, a nie zerowe, wartości. Celem algorytmów rekomendacji jest przewidzenie które z nieznanych pól będą mieć wysokie wartości, ponieważ wiedza o tych produktach stanowi możliwość zysku właściciela serwisu.
Netflix Prize
W 2006 roku amerykańska wypożyczalnia filmów Netflix ogłosiła konkurs na algorytm osiągający mniejszy średni błąd kwadratowy niż ich obecna metoda. Okazało się to bardzo dobrym sposobem na rozwój– wielu naukowców i zapaleńców kilka lat pracowało nad jak najlepszym algorytmem a nagrodę dostał jedynie zwycięzca. Firma nie musiała obciążać tym swoich pracowników, który mogli być mniej pomysłowi, a także swojego budżetu.
Różne podejścia do rekomendacji
Podczas konkursu okazało się, że najlepsze wyniki osiągały algorytmy oparte o filtrowanie społecznościowe (colaborative filtering). Nie biorą one pod uwagę żadnych jawnie określonych cech filmu czy użytkownika, ale patrzą jedynie na macierz ocen i próbują odkryć podobieństwa i zależności pomiędzy użytkownikami czy produktami (zależności między wierszami czy kolumnami). Problemem takich systemów jest tak zwany zimny start, czyli brak możliwości rekomendacji czegokolwiek gdy nie ma żadnych znanych ocen. Ciekawy pomysł przedstawił Filmaster, proponujący użytkownikom między innymi cotygodniowe rekomendacje filmów w telewizji i kinach. Zakładając konto w serwisie należy ocenić 20 wybieranych dynamicznie przez serwis filmów.
Ułomności tej nie ma content filtering, oparte na wprowadzonych przez eksperta danych o filmach oraz informacji o użytkownikach. Może ono działać od samego początku ale okazuje się, ze osiąga gorsze rezultaty niż colaborative filtering. Poza tym wymaga od użytkownika jawnego podania danych o sobie co może prowadzić do niechęci korzystania z serwisu.
Obie metody sprowadzają się do opisania użytkowników za pomocą wektora cech, które później są porównywane czy do siebie pasują czy nie. Cechy te są jawnie podawane w filtrowaniu za pomocą treści. Systemy oparte o filtrowanie społecznościowe rozkładają macierz ocen na dwie macierze w których kolumny/wiersze odpowiadają wywiedzionym ze zbioru cechom. Może się okazać, że będą one interpretowane dla człowieka albo będą złożeniem cech na które nie wpadłby ekspert opisujący film.
Odkrywanie cech
Odkrywanie takich cech dokonuje się za pomocą rozkładu SVD macierzy, przedstawienie macierzy w taki sposób oddaje wszystkie zależności pomiędzy wartościami. Udowodnione jest, ze ciąg kolejnych wektorów własnych macierzy wraz z wartościami własnymi jest najlepszym możliwym przybliżeniem wartości macierzy na tej ilości kolumn/wierszy. Rozkład SVD niesie niestety ze sobą pewne problemy. Po pierwsze traktuje puste pola jako pewną wartość (np. zero) a nie wartość nieznaną. Po drugie obliczanie rozkładu macierzy w sposób dokładny jest kosztowne obliczeniowo, co stanowi problem w systemie z setkami tysięcy produktów i użytkowników. Po trzecie należy pamiętać, że uzyskawszy idealne dopasowanie na zbiorze uczącym czyli na znanych ocenach, które zapewnia obliczenie pełnego rozkładu SVD, możemy bardzo źle trafiać z rekomendacjami dla nowych, nieznanych, przypadków.
Zamiast dokładnego rozkładu macierzy używa się dekompozycji metodami uczenia maszynowego. Tak samo jak przy obliczaniu SVD znajduje się kolejne wektory które wymnożone przez siebie dają przybliżenie macierzy. Nie liczy się tych wartości dokładnie, ale zmienia się wartości w wektorach odpowiadających danej obserwacji w kierunku spadku gradientu błędu tak aby z każdą kolejną obserwacją bardziej wartości dopasować do zbioru znanych obserwacji.
Metoda stochastycznego spadku wzdłuż gradientu
W swojej pracy magisterskiej zajmuję się właśnie przyrostową dekompozycją macierzy za pomocą stochastycznego spadku wzdłuż gradientu. Jej algorytm polega na uczeniu się kolejnych cech, czyli wektora prezentującego wartość cechy dla każdego użytkownika oraz wektora z wartościami cechy filmów. Każda cecha jest inicjowana małymi liczbami losowymi. Podczas kilkukrotnego przeglądania zbioru uczącego odpowiednie wartości wektora cech użytkowników i wektora cech filmów są modyfikowane aby pomniejszyć błąd osiągany dla aktualnej obserwacji ze zbioru uczącego. W momencie gdy błąd na całym zbiorze przestaje się zmieniać rozpoczyna się uczenie następnej cechy. Warunek stopu dla uczenia się cechy będzie uzależniony od zmian błędu na zbiorze uczącym i wydzielonym z niego zbiorze weryfikującym. Powinno to przyczynić się do szybszego zakończenia uczenia, niż przy odgórnie ustalonej liczbie epok uczenia. Może to także polepszyć wyniki dla nieznanych przypadków.
Wydajność i eksperymenty
Zbiór na którym przeprowadzane są eksperymenty uczenia jest na tyle duży, że konieczne było zwrócenie uwagi na wydajność. Tak więc algorytm jest implementowany w c++, dane są wczytywane do tablicy i przeglądane kolejno. Sporym ograniczeniem jest brak łatwego sposobu zrównoleglenia obliczeń, co bardzo przyspieszyłoby pracę.
Do tego momentu został zaimplementowany algorytm uczenia wraz z zabiegami mającymi na celu osiągnięcie szybszego zbiegnięcia błędu (tak zwaną regularyzacją). Został on jednak przetestowany dopiero na jednej szóstej oryginalnego zbioru danych. Wynika to z faktu, że przeprowadzanie eksperymentów jest bardzo czasochłonne, co utrudnia prace.
Warto zauważyć, ze na jednej szóstej danych osiąga on rezultaty podobne do najlepszych z konkursu Netflix Prize. Nie wiadomo jakie rezultaty osiągnie on na pełnych danych i na pełnym zbiorze testowym. Mogą być one znacznie gorsze. Jest tak ponieważ używany wycinek zbioru treningowego jest zbiorem bardzo przychylnym dla algorytmu, zawiera najczęściej występujące filmy i użytkowników. Pojawienie się innych, rzadziej występujących, z pewnością przyczyni się do zwiększenia średniego błędu predykcji.
Kolejnymi krokami będzie przetestowanie algorytmu na pełnym zbiorze. Jednak z uwagi na rozmiar danych aby uniknąć nieudanych prób uczenia na małym zbiorze, wpierw na podzbiorze zostanie oszacowana dobra konfiguracja algorytmu i ona zostanie zastosowana na dużych danych.
Inne zastosowania SVD
Rozkład według wartości osobliwych znajduje zastosowania w wielu miejscach, nie tylko przy rekomendacji. Kilkoma z wielu dziedzin gdzie się pojawia są wyszukiwarki tekstowe (uogólnianie słów w pojęcia, upraszczanie modelu), kompresja obrazu czy wizualizacja danych wielowymiarowych.
Źródła
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.178.598&rep=rep1&type=pdf
http://www2.research.att.com/~volinsky/papers/ieeecomputer.pdf
Kalina Jasinska
Yehuda Koren, Robert Bell, & Chris Volinsky (2009). Matrix Factorization Techniques for Recommender Systems Computer DOI: 10.1109/MC.2009.263
tsiss@PUT 