touch screen, finger, technology-6091015.jpg

Wszystko, co potrzebujesz wiedzieć o systemach rekomendacyjnych

Czy zastanawiasz się czasami, jak działają algorytmy, które wybierają dla Ciebie wyświetlaną reklamę? Albo dlaczego w mediach społecznościowych dostajesz akurat takie posty?

Za te zadania odpowiadają systemy rekomendacyjne. W MIM Solutions, firmie którą zarządzam, budowanie takich systemów to nasza specjalność. W naszej historii tworzyliśmy je dla wielu dużych firm, jak Play, Plus, Showroom, czy Frisco.

Dziś chciałbym Ci przekazać część naszej wiedzy, dzięki której jesteśmy w tym tak skuteczni. Podzielę się z Tobą różnymi radami, które Ci pomogą tworzyć dobre systemy dla Twojej firmy lub Twoich klientów.

Czym jest system rekomendacyjny?

Dla przypomnienia – system rekomendacyjny to algorytm, który proponuje użytkownikom dostosowane do nich produkty, reklamy, treści, wydarzenia itp. (https://en.wikipedia.org/wiki/Recommender_system). Może być on zamieszczony na przykład w sklepie internetowym, jako panel „Wybrane dla Ciebie produkty” lub „Może Cię zainteresować”.

Najlepiej z tym problemem radzą sobie algorytmy Machine Learning. Nie trzeba w nich określać wprost cech użytkownika lub produktu, na podstawie których rekomendujemy. Zamiast tego algorytm szkoli się sam na podstawie odpowiednio skontruowanego zbioru treningowego.

System rekomendacyjny jako binarna klasyfikacja

Spróbujmy podejść do tego problemu jak do problemu uczenia z nadzorem (uczenie bez nadzoru ma o wiele mniejsze możliwości i w wielu przypadkach nie jest wystarczające).

A zatem dla każdego zdarzenia (np. zakupu lub kliknięcia) potrzebujemy określić cel (target) naszej predykcji. Czy masz pomysł, co by nim mogło być?

Odpowiedź jest prosta – wystarczy, że nasz algorytm dla każdej pary użytkownik-produkt będzie przewidywał, czy użytkownik kupi, czy nie kupi. A precyzyjniej – jakie jest prawdopodobieństwo, że użytkownik kliknie / kupi. Wówczas rekomendacja będzie polegała na tym, że użytkownikowi zostanie zaproponowany ten produkt (lub kilka produktów), które z największym prawdopodobieństwem będą dla niego atrakcyjne. Widzimy zatem, że zadanie rekomendacji zostało sprowadzone do klasyfikacji binarnej.

Zauważmy jeszcze, że w tym podejściu nie interesuje nas tak bardzo, jaka jest dokładna wartość prawdopodobieństwa zwracana przez model. Ważna jest tylko kolejność prawdopodobieństwa produktów dla określonego użytkownika (to będzie ważne w dalszej części artykułu).

Problem ze zbiorem danych

W takim podejściu do rekomendacji jako do zadania klasyfikacji pojawia się jednak kilka problemów.

Pierwszy z nich to fakt, że trudno jest zbudować zbiór treningowy. Dlaczego? Jak wiemy, przy klasyfikacji binarnej zbiór danych musi mieć zarówno przykłady pozytywne, jak i negatywne. Jeśli jednak będziesz gromadzić informacje o historycznych zakupach czy wyświetleniach, zobaczysz tylko to, co użytkownik kupił / obejrzał, ale nie zobaczysz, czego NIE kupił. A zatem będziesz mieć tylko przykłady pozytywne.

Naturalnym rozwiązaniem jest założenie, że jeśli użytkownik U kupił w danym dniu tylko produkt A, to nie kupił produktów B, C, D, … itd. A zatem zbiór treningowy mógłby wyglądać następująco:

Załóżmy, że mamy 3 produkty P1, P2 i P3 i użytkowników U1, U2 i U3, U4. Załóżmy, że użytkownicy U1, U2 i U3 kupili po jednym produkcie i ich zakupy to (U1, P1), (U2, P2) i (U3, P3), wtedy zbiór treningowy to:

U1, P1, 1
U2, P2, 1
U3, P3, 1
U1, P2, 0
U1, P3, 0
U2, P1, 0
U2, P3, 0
U3, P1, 0
U3, P2, 0
U4, P1, 0
U4, P2, 0
U4, P3, 0
U4, P4, 0

gdzie ostatnia wartość 0 / 1 mówi, czy jest to przykład pozytywny, czy negatywny. Czyli po prostu utworzyliśmy wszystkie pozostałe pary użytkownik-produkt i wstawiliśmy zero tam, gdzie nie doszło do transakcji.

Pojawiają się jednak tutaj znowu dwa kolejne problemy. Po pierwsze, czy możemy zakładać, że każdy z użytkowników, którzy nie kupili danego produktu, miał możliwość go kupić, lecz go nie kupił? Może była tylko jedna sztuka produktu P1 i gdy kupił go U1, to U2 nie mógł go już kupić? Może akurat nie był on dostępny w danej chwili? Wszystko zależy od konkretnej sytuacji, ale musisz bardzo uważać z takim założeniem, ponieważ może się okazać, że proste uzupełnienie zerami pełnego iloczynu kartezjańskiego użytkownicy x produkty nie będzie poprawne.

Sytuacja jeszcze bardziej się komplikuje, gdy mówimy na przykład o sklepach stacjonarnych, z których każdy może być nieco inaczej zaopatrzony, a ponadto stan zaopatrzenia zmienia się każdego dnia. Wówczas tworząc zbiór, należy dla każdego klienta wybierać produkty na podstawie stanów magazynowych, czyli produkty, które (przynajmniej teoretycznie) mógł zobaczyć dany klient, lecz ich nie kupił.

Drugi problem to potencjalnie ogromny rozmiar naszej macierzy. Jeśli użytkowników oraz produktów są tysiące, to macierz będzie miała miliony wierszy, z czego zdecydowana większość to będą zera.

Próbkowanie negatywów

Aby rozwiązać problem rzadkiej macierzy, wykonuje się tzw. próbkowanie negatywów (negatives sampling). Nie chcemy generować wszystkich zerowych wierszy, aby uniknąć puchnięcia macierzy, lecz tylko niewielki podzbiór – taki, który będzie konieczny do wytrenowania naszego modelu.

Okazuje się, że jeśli nasz zbiór przedstawimy w następujący sposób 

(wiersze to użytkownicy, a kolumny to produkty),

to możemy z każdej kolumny usunąć ten sam odsetek zer, np.

Łatwo udowodnić matematycznie, że jeśli z każdej kolumny usuniemy ten sam odsetek zer, to nie zmieni się kolejność prawdopodobieństwa zakupów produktów.

Jeśli teraz nasz algorytm będzie trenowany na tym zmodyfikowanym zbiorze, to zmienią się zwracane prawdopodobieństwa, ale nie zmieni się kolejność produktów dla konkretnego użytkownika, a tylko o tę kolejność nam chodzi.

Zauważmy jeszcze jedną rzecz. Jeśli zostawiamy negatywy (czyli produkty, których dany użytkownik nie kupił), to warto, aby były one jak najbardziej zbliżone do rzeczywistych zakupów. Dzięki temu model będzie miał utrudnione zadanie i na etapie treningu nabierze dużo większej precyzji. Czyli jeśli przykładowo chcemy rekomendować filmy i widzimy, że dany użytkownik oglądał tylko komedie, to najlepiej, gdy w zbiorze negatywów dla danego użytkownika również będą same komedie (których nie obejrzał). Jeśli by tam były filmy innego gatunku, to model by nie nauczył się precyzyjnie wybierać filmów, a jedynie trafiałby w gatunek, proponując zawsze jakąś komedię (niekoniecznie dostosowaną do gustów użytkownika).

Różne algorytmy próbkowania negatywów możesz znaleźć np. w tym artykule.

Do „inteligentnego” wyboru negatywów wrócimy jeszcze w kolejnej sekcji.

Generowanie predykcji

Jeśli rozwiązaliśmy już problem ze zbiorem danych, potrafimy go stworzyć i wytrenować model, pojawia się trudność z wyliczaniem predykcji dla każdego użytkownika.

Ponownie mamy do czynienia z puchnięciem naszego zbioru. Jeśli dla każdego użytkownika chcemy zwrócić rekomendację, potrzebujemy prawdopodobieństw dotyczących każdego produktu dla każdego użytkownika. Zatem rozmiar zbioru do przeliczenia przez model może wynosić wiele milionów wierszy.

Rozwiązaniem na to jest generowanie tzw. zbiorów kandydatów dla każdego użytkownika. Za pomocą tego podejścia zdobyliśmy nagrodę w międzynarodowym konkursie RecSys 2016; nasz algorytm opisaliśmy w tej publikacji.

Chodzi o to, żeby model nie musiał dla każdego użytkownika przeliczać wszystkich predykcji. Warto pomyśleć, czy w naszym zbiorze są jakieś inne cechy produktów, które pozwalają nam odfiltrować wiele z nich i wyliczać predykcje tylko dla pewnego podzbioru produktów? Mogą to być np. najpopularniejsze globalnie produkty; produkty, które użytkownik oglądał w ostatnim tygodniu, czy produkty kupione przez podobnych użytkowników (to podobieństwo można różnie definiować).

Warto kontrolować, jaki procent wszystkich pozytywów potrafimy pokryć takimi regułami generowania kandydatów. Reguły tworzenia zbiorów kandydatów powinny pozwolić na uchwycenie jak największej liczby rzeczywistych zakupów na zbiorze treningowym.

Zauważmy teraz, że te same reguły wybierania kandydatów możemy zastosować do wybierania negatywów na etapie treningu modelu. Dzięki temu model nie tylko lepiej będzie się trenował (dostając bardziej realistyczne, a więc trudniejsze przykłady), ale również jego zadanie na zbiorze testowym będzie podobne.

Tworzenie dodatkowych cech

Na koniec podam jeszcze jedną radę, która jest kluczowa dla trenowania skutecznego modelu rekomendacyjnego. Jest to mądre wygenerowanie nowych cech dla modelu.

Zauważmy, że jeśli stworzymy nasz zbiór treningowy, to będziemy mieć tam kolumny dotyczące użytkownika (np. wiek, płeć, zainteresowania), dotyczące produktów (np. nazwa, cena, kategoria), a także interakcji pomiędzy użytkownikami a produktami (np. ile razy użytkownik kupił dany produkt, kiedy ostatni raz kupił itp.).

Tworząc zbiór treningowy, możemy i powinniśmy generować sami dodatkowe cechy, których nie ma w zbiorze. Nie powinniśmy zakładać, że model sam się wszystkiego nauczy, skoro można te cechy wywnioskować z innych kolumn. Z mojego doświadczenia wynika, że im więcej informacji podamy wprost, tym modelowi będzie prościej. Zauważmy, że modele typu XGBoost są kombinacją wielu drzew decyzyjnych i nie mają możliwości „nauczyć się” zależności typu iloczyn dwóch kolumn (mogą jedynie heurystycznie przybliżać je jakimiś regułami).

Dlatego warto dodawać jak najwięcej nowych cech, takich jak:

  • liczba zakupów per produkt globalnie,
  • liczba wyświetleń (np. w sklepie e-commerce) danego produktu przez użytkownika w ostatnim dniu / tygodniu / miesiącu,
  • maksymalna metryka podobieństwa między naszym użytkownikiem a innym użytkownikiem, który kupił dany produkt.

Podsumowanie

W tym artykule przedstawiłem Ci najciekawsze pomysły, jakie stosujemy przy budowie systemów rekomendacyjnych. Na koniec – zadanie dla Ciebie. Wybierz dowolny zbiór do zbudowania systemu rekomendacyjnego (np. stąd) i spróbuj wytrenować model XGBoost, stosując zasady, które wymieniłem w tym artykule.

Daj mi koniecznie znać w komentarzu, jak Ci poszło z tym zadaniem! Jeśli coś jest niejasne, możesz śmiało do mnie napisać: adam.dobrakowski@praktycznyml.pl .