W poprzednim artykule o tworzeniu serwisów umożliwiających porównywanie dokumentów, obrazków, ofert handlowych czy dowolnych innych mogliście przeczytać o technikach, dzięki których można to osiągnąć. Teraz zajmiemy się optymalizacją. Dzięki mniejszej ilości zajętej przez serwis pamięci i zachowaniu krótkiego czasu odpowiedzi, staje się on praktyczny, ponieważ spada koszt jego utrzymania, a serwis działa efektywnie. Dowiecie się jak poradzić sobie w sytuacji, kiedy mamy miliony czy dziesiątki milionów obiektów do porównania.
Kwantyzacja wektorów (Quantization)
Głównym problemem, który trzeba rozwiązać jest zredukowanie rozmiaru wektorów przechowywanych w indeksie. o ile przyjmiemy na przykład (a są to realistyczne wielkości), iż pojedynczy wektor reprezentujący dokument to kilkaset liczb (powiedzmy 512), przy czym każda z nich jest reprezentowana przez 8 bajtów (aby zachować odpowiednią dokładność zwykle używa się liczb zmiennoprzecinkowych o takiej właśnie wielkości), to okazuje się, iż już pojedynczy wektor to ponad 4000 bajtów. o ile dokumentów mamy milion, a nie jest to liczba niespotykana w praktyce, czy choćby szczególnie duża liczba, to okazuje się, iż nieskompresowane wektory w tej ilości zajmą około 4GB pamięci.
Do niedawna jeszcze rozmiary pamięci tego rzędu wykluczały praktyczne posługiwanie się opisywanymi tutaj technikami. W ostatnich latach ceny pamięci spadły, a ich dostępne rozmiary powiększyły się, przez cały czas jednak przechowywanie realistycznie dużych kolekcji wektorów jest problematyczne i kosztowne. choćby o ile tak duży indeks załadujemy do pamięci, to zabiera to czas. W praktyce często potrzebne jest wznawianie działania serwisu obsługującego użytkowników, co powoduje, iż tracenie czasu w ciągłe ładowanie tak dużych zbiorów danych do pamięci staje się realnym problemem.
Czy da się zatem zmniejszyć wektory, przy zachowaniu ich użyteczności do bezpośrednich obliczeń?
Nie wchodzą tutaj w grę standardowe sposoby kompresji danych, bo przekształcają je w taki sposób, iż nie da się na nich przeprowadzać obliczeń bez wcześniejszego rozpakowania. Pomocne okazują się jednak techniki tzw. kwantyzacji wektorowej.
Proces “pomniejszania”’ wektora wymaga jednak przygotowania. Wyobraźmy sobie, iż każdy z naszych wektorów dzielimy na mniejsze fragmenty.
Rys 1. Każdy z wektorów w kolekcji dzielimy na fragmenty o równej długości (tutaj do każdego fragmentu należą tylko dwie liczby z wektora, w praktyce jest ich zwykle więcej).Jeżeli weźmiemy teraz pierwszy fragment dla wszystkich z wektorów, to otrzymujemy kolekcję o takiej samej ilości elementów jak wyjściowa, ale o mniejszym rozmiarze (dajmy na to podzieliliśmy wektor na 16 fragmentów, a więc rozmiar jest 16x mniejszy). Dla takich “skróconych” wektorów można policzyć centroidy. Musimy określić, ile tych centroidów chcemy mieć – dajmy na to 256.
Rys 2. Każdy fragment traktujemy jak oddzielną kolekcję (o zmniejszonej długości wektorów) i liczymy centroidy. Na rysunku przyjmujemy tylko trzy centroidy i przestrzeń dwuwymiarową w której je liczymy (długość wektora = 2). W praktyce przestrzeń jest wielowymiarowa (tyle wymiarów jaką przyjęliśmy długość wektora we fragmencie), a centroidów może być znacznie więcej.Następnie porównać każdy “skrócony” wektor i wybrać centroid, który będzie go najlepiej reprezentował. Każdy centroid ma reprezentujący go numer. Następnie dokonujemy podmiany – fragment oryginalnego wektora zastępujemy centroidem go reprezentującym, ale nie wartościami, ale po prostu numerem tego centroida.
Rys 3. Kodowanie wektorów. Każdy fragment każdego wektora zastępujemy numerem centroida (tutaj reprezentowanym przez jego kolor) najbliższego danemu fragmentowi.Z każdym kolejnym fragmentem postępujemy podobnie: liczymy nowy zestaw centroidów dla wycinka wektorów, a następnie podmieniamy fragmenty wektorów na numery reprezentujących je centroidów. W ten sposób uzyskujemy bardzo znacznie zredukowane wektory. Poprzednio jeden wektor to około 4000 bajtów. o ile podzieliliśmy każdy z nich na 16 części, każdą część reprezentuje numer centroida (1 bajt, bo tyle wystarczy, aby zapisać numer jednego z 256 centroidów odpowiednich dla danego fragmentu) to otrzymujemy reprezentację wektora o długości zaledwie 16 bajtów! To 250-krotna redukcja rozmiaru!
Przyjrzyjmy się temu jak osiągnąć taką redukcję przy pomocy biblioteki FAISS, którą wykorzystaliśmy już w poprzednim artykule. Przygotowujemy, podobnie jak wcześniej, bazę losowych stu tysięcy wektorów.
[crayon-6358e026dac2a577728460 inline="true" ]import faiss from numpy import random, arange, dot from numpy.linalg import norm doc_dimensions_no = 512 number_of_docs = 100_000 random.seed(10234) # make reproducible document_vectors = random\ .random((number_of_docs, doc_dimensions_no))\ .astype(’float32’) print(document_vectors[:, 0])[/crayon]Tak przygotowane wektory możemy użyć do wytrenowania indeksu biblioteki FAISS. W ramach treningu (czyli wyznaczenia centroidów poszczególnych fragmentów wektorów) możemy oczywiście użyć części, nie całej kolekcji wektorów – to obniża nieco dokładność wyznaczonych centroidów, ale równocześnie przyspiesza znacznie trening.
[crayon-6358e026dac2c508736874 inline="true" ]how_many_parts = 16 m = 8 index = faiss.IndexPQ(doc_dimensions_no, how_many_parts, m) if not index.is_trained: index.train(document_vectors) assert index.is_trained[/crayon]Dodanie wektorów do indeksu (a więc podzielenie i przyporządkowanie fragmentów do centroidow) odbywa się prosto:
[crayon-6358e026dac2e735525210 inline="true" ]index.add(document_vectors)[/crayon]Zadanie zapytania wygląda analogicznie jak w poprzednich przypadkach:
[crayon-6358e026dac30002927011 inline="true" ]number_of_results = 5 # we want to see 5 nearest neighbors number_of_queries = 1 query_vectors = random\ .random((number_of_queries, doc_dimensions_no))\ .astype(’float32’) distances, similar_docs = index.search(query_vectors, number_of_results)[/crayon]Powstaje jednak wątpliwość, czy tak przekształcone wektory nadają się jeszcze do czegokolwiek? Przecież nie przypominają już zupełnie oryginalnych. Okazuje się, iż mimo tak znacznego przekształcenia wektory zachowują swoje własności w znacznym stopniu i przez cały czas reprezentują dokumenty, chociaż już mniej dokładnie niż miało to miejsce oryginalnie. o ile jednak tworzymy serwis porównujący dokumenty, to nie musimy skupiać się na dokładności porównania, a jedynie na wskazaniu dokumentów najbardziej podobnych we adekwatnej kolejności. W praktyce daje się to osiągnąć mimo tak znacznej redukcji rozmiarów wektorów i częściowej utraty dokładności.
Oczywiście przytoczone wyżej parametry (podział na 16 fragmentów, reprezentacja przez 256 centroidów) są przykładowe i w konkretnym przypadku należy je dobrać indywidualnie, sprawdzając jak duży wpływ będą miały na dokładność oczekiwanych wyników.
