Nazywam się Paweł Parhomenko, jestem deweloperem ML. W tym artykule chciałbym opowiedzieć o działaniu usługi Yandex Zen i podzielić się technicznymi usprawnieniami, których wdrożenie pozwoliło zwiększyć jakość rekomendacji. Z wpisu dowiesz się, jak w zaledwie kilka milisekund znaleźć wśród milionów dokumentów te najbardziej relevantne dla użytkownika; jak przeprowadzać ciągłe rozkładanie dużej macierzy (składającej się z milionów kolumn i dziesiątek milionów wierszy), aby nowe dokumenty otrzymywały swój wektor w ciągu dziesiątek minut; jak ponownie wykorzystać rozkładanie macierzy użytkownik-artykół, aby uzyskać dobre wektorowe przedstawienie dla wideo.
Nasza baza rekomendacyjna zawiera miliony dokumentów różnego formatu: artykuły tekstowe, stworzone na naszej platformie i pobrane z zewnętrznych stron, wideo, narracje i krótkie posty. Rozwój takiej usługi wiąże się z wieloma wyzwaniami technicznymi. Oto niektóre z nich:
- Podzielić zadania obliczeniowe: wszystkie ciężkie operacje realizować offline, a w czasie rzeczywistym wykonywać tylko szybkie zastosowanie modeli, aby odpowiadać w ciągu 100-200 ms.
- Szybko uwzględniać działania użytkownika. W tym celu wszystkie zdarzenia muszą być natychmiast dostarczane do rekomendatora i wpływać na wyniki pracy modeli.
- Sprawić, aby feed nowych użytkowników szybko dostosowywał się do ich zachowań. Osoby, które właśnie dołączyły do systemu, powinny odczuwać, że ich feedback wpływa na rekomendacje.
- Szybko rozumieć, komu polecić nowy artykuł.
- Błyskawicznie reagować na ciągłe pojawianie się nowej treści. Codziennie ukazuje się dziesiątki tysięcy artykułów, wiele z nich ma ograniczony czas życia (powiedzmy, wiadomości). W tym różnią się od filmów, muzyki i innej długotrwałej i kosztownej w produkcji treści.
- Przenosić wiedzę z jednej dziedziny na drugą. Jeśli w systemie rekomendacyjnym znajdują się wytrenowane modele dla artykułów tekstowych i dodajemy do niego wideo, można ponownie wykorzystać istniejące modele, aby treść nowego typu była lepiej klasyfikowana.
Opowiem, jak rozwiązaliśmy te zadania.
Selekcja kandydatów
Jak w kilka milisekund skrócić liczbę analizowanych dokumentów tysiąckrotnie, praktycznie nie pogarszając jakości rankingów?
Załóżmy, że wytrenujemy wiele modeli ML, wygenerujemy na ich podstawie cechy i wytrenujemy kolejny model, który klasyfikuje dokumenty dla użytkownika. Wszystko byłoby dobrze, ale nie można po prostu obliczyć wszystkich cech dla wszystkich dokumentów w czasie rzeczywistym, gdy tych dokumentów są miliony, a zalecenia muszą być tworzone w ciągu 100-200 ms. Zadanie polega na wybraniu z milionów pewnego podzbioru, który zostanie sklasyfikowany dla użytkownika. Ten etap zazwyczaj nazywamy selekcją kandydatów. Istnieje kilka wymagań. Po pierwsze, selekcja musi przebiegać bardzo szybko, aby na samo klasyfikowanie pozostało jak najwięcej czasu. Po drugie, znacznie redukując liczbę dokumentów do klasyfikacji, powinniśmy jak najdokładniej zachować dokumenty istotne dla użytkownika.
Nasza zasada selekcji kandydatów ewoluowała i obecnie doszliśmy do wieloetapowego schematu:
Na początku wszystkie dokumenty są dzielone na grupy, a z każdej grupy wybierane są najbardziej popularne dokumenty. Grupami mogą być strony, tematy, klastry. Dla każdego użytkownika na podstawie jego historii dobierane są najbliższe mu grupy, a następnie z nich wybierane są najlepsze dokumenty. Używamy również indeksu kNN do dobierania najbardziej zbliżonych dokumentów do użytkownika w czasie rzeczywistym. Istnieje kilka metod budowy indeksu kNN, u nas najlepiej działa (Hierarchical Navigable Small World graphs). To hierarchiczny model, który pozwala w kilka milisekund znaleźć N najbliższych wektorów dla użytkownika z milionowej bazy. Wcześniej indeksujemy całą naszą bazę dokumentów offline. Ponieważ wyszukiwanie w indeksie działa dość szybko, przy obecności kilku silnych embeddingów można stworzyć kilka indeksów (po jednym dla każdego embeddingu) i odnosić się do każdego z nich w czasie rzeczywistym.
Mamy dziesiątki tysięcy dokumentów dla każdego użytkownika. Nadal jest to dużo do zliczenia wszystkich cech, więc na tym etapie stosujemy lekkie rankingowanie — uproszczony model ciężkiego rankingowania z mniejszą liczbą cech. Celem jest przewidzenie, które dokumenty znajdą się na czołowej pozycji w ciężkim modelu. Dokumenty z najwyższym predyktem będą wykorzystane w ciężkim modelu, czyli na ostatnim etapie rankingowania. To podejście pozwala w ciągu dziesiątek milisekund skrócić bazę rozpatrywanych dokumentów z milionów do tysięcy.
Krok ALS w czasie rzeczywistym
Jak uwzględniać feedback użytkownika zaraz po kliknięciu?
Ważnym czynnikiem w rekomendacjach jest czas reakcji na feedback użytkownika. Jest to szczególnie istotne dla nowych użytkowników: gdy osoba dopiero zaczyna korzystać z systemu rekomendacji, otrzymuje niepersonalizowany strumień różnorodnych dokumentów tematycznych. Gdy tylko dokona pierwszego kliknięcia, konieczne jest, aby natychmiast to uwzględnić i dostosować się do jego zainteresowań. Jeśli wszystkie czynniki będą obliczane offline, szybka reakcja systemu stanie się niemożliwa z powodu opóźnienia. Z tego powodu konieczne jest przetwarzanie działań użytkownika w czasie rzeczywistym. Do tych celów używamy kroku ALS w czasie rzeczywistym do budowy wektorowego przedstawienia użytkownika.
Załóżmy, że dla wszystkich dokumentów mamy wektorowe przedstawienie. Na przykład, możemy offline na podstawie tekstu artykułu zbudować embeddingi przy użyciu ELMo, BERT lub innych modeli uczenia maszynowego. Jak można uzyskać wektorowe przedstawienie użytkowników w tej samej przestrzeni na podstawie ich interakcji w systemie?
Ogólny zasada formowania i rozkładu macierzy użytkownik-dokumentZałóżmy, że mamy m użytkowników i n dokumentów. Dla niektórych użytkowników znana jest ich relacja z niektórymi dokumentami. Informacje te można przedstawić w postaci macierzy m x n: wiersze odpowiadają użytkownikom, a kolumny – dokumentom. Ponieważ większość dokumentów nie została przez człowieka zobaczona, większość komórek macierzy pozostanie pustych, a inne będą wypełnione. Dla każdego zdarzenia (polubienia, niepolubienia, kliknięcia) w macierzy przewidziana jest jakaś wartość – na razie rozważmy uproszczony model, w którym polubienie odpowiada 1, a niepolubienie –1.
Rozłożymy macierz na dwie: P (m x d) i Q (d x n), gdzie d to wymiar wektorowego przedstawienia (zazwyczaj jest to mała liczba). Wówczas każdy obiekt będzie odpowiadał wektorowi d-wymiarowemu (użytkownik – wiersz w macierzy P, dokument – kolumna w macierzy Q). Te wektory będą embeddingami odpowiednich obiektów. Aby przewidzieć, czy użytkownikowi spodoba się dokument, wystarczy pomnożyć ich embeddingi.
Jednym z możliwych sposobów rozkładu macierzy jest ALS (Alternating Least Squares). Będziemy optymalizować następującą funkcję straty:
Tutaj rui to interakcja użytkownika u z dokumentem i, qi to wektor dokumentu i, pu to wektor użytkownika u.
Wtedy optymalny z punktu widzenia średniego błędu kwadratowego wektor użytkownika (przy stałych wektorach dokumentów) znajduje się analitycznie poprzez rozwiązanie odpowiedniej regresji liniowej.
Nazywa się to „krokiem ALS”. Sam algorytm ALS polega na tym, że na przemian ustalamy jedną z macierzy (użytkowników i artykułów) i aktualizujemy drugą, znajdując optymalne rozwiązanie.
Na szczęście, znalezienie wektorowego przedstawienia użytkownika to dość szybka operacja, którą można wykonywać w czasie rzeczywistym, wykorzystując instrukcje wektorowe. Ten trik pozwala od razu uwzględnić opinie użytkownika w rankingach. Ten sam embedding można wykorzystać także w indeksie kNN, aby ulepszyć wybór kandydatów.
Rozproszona filtracja współpracy
Jak przeprowadzać inkrementalną rozproszoną faktoryzację macierzy i szybko znajdować wektorowe przedstawienie nowych artykułów?
Treść to nie jedyne źródło sygnałów dla rekomendacji. Innym ważnym źródłem jest informacja kolaboracyjna. Dobre wskazówki w rankingach tradycyjnie można uzyskać z dekompozycji macierzy użytkownik-dokument. Jednak podczas próby przeprowadzenia takiej dekompozycji napotkaliśmy problemy:
1. Mamy miliony dokumentów i dziesiątki milionów użytkowników. Macierz nie mieści się w całości na jednym urządzeniu, a dekompozycja zajmie bardzo dużo czasu.
2. Większość treści w systemie ma krótki czas życia: dokumenty pozostają aktualne tylko przez kilka godzin. Dlatego trzeba jak najszybciej zbudować ich wektorowe przedstawienie.
3. Jeśli dekompozycja zostanie przeprowadzona tuż po publikacji dokumentu, nie zdąży on być oceniony przez wystarczającą liczbę użytkowników. Dlatego jego wektorowe przedstawienie ma dużą szansę na to, że będzie niewłaściwe.
4. Jeśli użytkownik daje ocenę pozytywną lub negatywną, nie będziemy mogli uwzględnić tego na bieżąco w dekompozycji.
Aby rozwiązać wymienione problemy, zrealizowaliśmy rozproszoną dekompozycję macierzy użytkownik-dokument z częstymi inkrementalnymi aktualizacjami. Jak dokładnie to działa?
Przypuśćmy, że mamy klaster z N maszynami (N liczony w setkach) i chcemy przeprowadzić rozproszoną dekompozycję macierzy, która nie mieści się na jednej maszynie. Pytanie brzmi: jak wykonać tę dekompozycję, tak aby, z jednej strony, na każdej maszynie było wystarczająco dużo danych, a z drugiej, obliczenia były niezależne?
Będziemy używać algorytmu dekompozycji ALS opisanego powyżej. Zobaczmy, jak rozproszono przeprowadzić jeden krok ALS – pozostałe kroki będą podobne. Załóżmy, że mamy ustaloną macierz dokumentów i chcemy zbudować macierz użytkowników. W tym celu podzielimy ją na N części według wierszy, a każda część będzie zawierać mniej więcej tę samą liczbę wierszy. Rozślemy do każdej maszyny niepuste komórki odpowiednich wierszy, a także całą macierz osadzeń dokumentów. Ponieważ nie jest ona zbyt dużych rozmiarów, a macierz użytkownik-dokument jest zazwyczaj bardzo rzadka, te dane zmieszczą się na zwykłej maszynie.
Taki trik można powtarzać przez kilka epok aż do zbieżności modelu, zmieniając kolejno stałą macierz. Jednak nawet wtedy rozkład macierzy może trwać kilka godzin. I to nie rozwiązuje problemu szybkiego uzyskiwania embeddingów nowych dokumentów oraz aktualizowania embeddingów tych, o których było mało informacji podczas tworzenia modelu.
Pomożła nam implementacja szybkiej inkrementalnej aktualizacji modelu. Załóżmy, że mamy aktualnie wytrenowany model. Od momentu jego wytrenowania pojawiły się nowe artykuły, z którymi współdziałali nasi użytkownicy, oraz artykuły, które miały mało interakcji podczas szkolenia. Aby szybko uzyskać embeddingi takich artykułów, wykorzystujemy embeddingi użytkowników uzyskane podczas pierwszego dużego szkolenia modelu i wykonujemy jeden krok ALS, aby obliczyć macierz dokumentów przy stałej macierzy użytkowników. To pozwala na szybkie uzyskiwanie embeddingów — w ciągu kilku minut po publikacji dokumentu — i częste aktualizowanie embeddingów świeżych dokumentów.
Aby działania człowieka były od razu uwzględniane w rekomendacjach, w czasie rzeczywistym nie korzystamy z embeddingów użytkowników uzyskanych offline. Zamiast tego wykonujemy krok ALS i uzyskujemy aktualny wektor użytkownika.
Przeniesienie do innej domeny
Jak wykorzystać opinie użytkowników dotyczące artykułów tekstowych do budowy wektorowego przedstawienia wideo?
Początkowo rekomendowaliśmy jedynie artykuły tekstowe, dlatego wiele naszych algorytmów było dostosowanych do tego typu treści. Jednak przy dodawaniu treści innego typu napotykaliśmy potrzebę dostosowania modeli. Jak rozwiązaliśmy ten problem na przykładzie wideo? Jednym z rozwiązań byłoby ponowne wytrenowanie wszystkich modeli od zera. Jednak to zajmuje dużo czasu, a ponadto część algorytmów jest wymagająca pod względem objętości zbioru treningowego, którego jeszcze nie ma w odpowiedniej ilości dla nowego typu treści w pierwszych momentach jej obecności w serwisie.
Poszliśmy inną drogą i wykorzystaliśmy modele tekstu dla wideo. W stworzeniu wektorowych reprezentacji wideo pomogła nam ta sama sztuczka z ALS. Wzięliśmy wektorową reprezentację użytkowników na podstawie artykułów tekstowych i wykonaliśmy krok ALS, wykorzystując informacje o oglądaniu wideo. W ten sposób bez trudu uzyskaliśmy wektorową reprezentację wideo. W czasie rzeczywistym obliczamy połączenie między wektorem użytkownika, uzyskanym na podstawie artykułów tekstowych, a wektorem wideo.
Podsumowanie
Rozwój rdzenia systemu rekomendacji w czasie rzeczywistym wiąże się z wieloma zadaniami. Należy szybko przetwarzać dane i stosować metody ML do efektywnego wykorzystania tych danych; budować złożone rozproszone systemy, które potrafią w minimalnym czasie przetwarzać sygnały użytkowników oraz nowe jednostki treści; i wiele innych zadań.
W obecnym systemie, którego konstrukcję opisuję, jakość rekomendacji dla użytkownika rośnie wraz z jego aktywnością i czasem spędzonym w serwisie. Ale oczywiście, tu kryje się również główna trudność: systemowi trudno jest na pierwszy rzut oka zrozumieć zainteresowania osoby, która mało interagowała z treściami. Poprawa rekomendacji dla nowych użytkowników to nasze kluczowe zadanie. Będziemy nadal optymalizować algorytmy, aby odpowiednia dla danej osoby treść szybciej trafiała do jego kanału, a nieodpowiednia nie była wyświetlana.
Źródło: habr.com
