Optymalizacja pamięci. Jak zredukować rozmiar wektorów

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, za pomocą 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. Jeżeli przyjmiemy na przykład (a są to realistyczne wielkości), że 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ę, że już pojedynczy wektor to ponad 4000 bajtów. Jeżeli dokumentów mamy milion, a nie jest to liczba niespotykana w praktyce, czy nawet szczególnie duża liczba, to okazuje się, że 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ę, nadal jednak przechowywanie realistycznie dużych kolekcji wektorów jest problematyczne i kosztowne. Nawet jeżeli 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, że tracenie czasu na 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, że 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, że każdy z naszych wektorów dzielimy na mniejsze fragmenty.

Jeżeli weźmiemy teraz pierwszy fragment dla każdego 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.

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, lecz po prostu numerem tego centroida. 

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. Jeżeli 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.

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])

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.

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

Dodanie wektorów do indeksu (a więc podzielenie i przyporządkowanie fragmentów do centroidow) odbywa się prosto:

index.add(document_vectors)

Zadanie zapytania wygląda analogicznie jak w poprzednich przypadkach:

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)

Powstaje jednak wątpliwość, czy tak przekształcone wektory nadają się jeszcze do czegokolwiek? Przecież nie przypominają już zupełnie oryginalnych. Okazuje się, że mimo tak znacznego przekształcenia wektory zachowują swoje własności w znacznym stopniu i nadal reprezentują dokumenty, chociaż już mniej dokładnie niż miało to miejsce oryginalnie. Jeżeli 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 właściwej 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.

Oferty pracy z

Porównywanie skwantyzowanych wektorów

Stosując kwantyzację otrzymaliśmy kompaktową reprezentację wektorów reprezentujących dokumenty. Jak jednak porównywać te wektory do zapytania? Do tej pory, kiedy wektory reprezentowały dokumenty “wprost”, zapytanie również będące wektorem porównywaliśmy po prostu z wektorami dokumentów licząc ich odległość. Teraz nasze reprezentacje dokumentów zostały zakodowane. Czy musimy je odkodować żeby porównywać? To oznaczałoby, że owszem, zredukowaliśmy rozmiar bazy wektorów, ale płacimy olbrzymi koszt w trakcie obsługi każdego zapytania. Na szczęście nie trzeba tego robić. 

Zapytanie, będące również wektorem, można potraktować w ten sam sposób – dzielimy je na taką samą ilość fragmentów jak wektory dokumentów. Dla każdego z fragmentów musimy wyliczyć i przechować na czas odpowiadania na zapytanie jego odległość od wszystkich centroidów danego fragmentu. Otrzymamy zatem dla naszych przykładowych 16 fragmentów macierz o 16 kolumnach i 256 wierszach.

Następnie, aby otrzymać przybliżoną odległość wektora zapytania od wektora dokumentu wystarczy biorąc po kolei fragmenty wektora dokumentu (czyli numery centroidów) wybrać z tej macierzy odległość od tego centroida dla danego fragmentu i zsumować te odległości dla wszystkich fragmentów.

Odwrócony indeks skwantyzowanych wektorów

Powyższy algorytm wymaga od nas jednak przejrzenia całej przestrzeni wektorów w trakcie przeszukiwania. Tymczasem znamy już opisywaną w poprzednim artykule technikę grupowania wektorów, która pozwala tego uniknąć. Można połączyć oba te sposoby i w ten sposób uzyskać zarówno skompresowanie wektorów dokumentów dzięki kwantyzacji, jak i przyspieszenie czasu odpowiedzi na zapytania, dzięki posłużeniu się indeksem odwróconym opartym na centroidach dla wszystkich wektorów. W pierwszej fazie cała baza wektorów zostaje rozdzielona do poszczególnych klastrów. Musimy najpierw wyliczyć centroidy a następnie przydzielić poszczególne wektory do klastrów. Następnie, dla każdego klastra oddzielnie stosuje się opisaną wyżej kwantyzację wektorów. Odpowiadanie na zapytania w takiej piętrowej strukturze wymaga również kilku kroków:

1. nieprzetworzony wektor zapytania porównywany jest do centroidów grupujących dokumenty na pierwszym poziomie – pozwala to wybrać tylko fragment bazy dokumentów i uniknąć porównywania wszystkich,
2. wektor zapytania jest dzielony na fragmenty,
3. wyliczona jest macierz odległości wszystkich centroidów danego fragmentu od fragmentu zapytania,
4. następuje przeszukanie wszystkich wektorów części bazy wybranej przez pierwszy krok i porównanie ich z wykorzystaniem macierzy odległości.

Biblioteka FAISS pozwala przygotować taki indeks przez złożenie dwóch indeksów – jednego będącego indeksem głównych klastrów, oraz drugiego, stosującego technikę kwantyzacji wektorów.

quantizer = faiss.IndexFlatL2(doc_dimensions_no)  
# the index to hold centroids for partitioning the main index
how_many_parts = 16 
number_of_quantizer_clusters = 100 
m = 8 
index = faiss.IndexIVFPQ(quantizer, doc_dimensions_no, number_of_quantizer_clusters, how_many_parts , m)

Zarówno trening, jak i zadanie zapytania odbywa się w analogiczny, jak wyżej sposób. Jedyną istotną różnicą jest konieczność powiązania pierwszego indeksu z drugim, kwantyzowanym, odwróconym indeksem IVFPQ oraz, w porównaniu do indeksu PQ, ustalenie, ile klastrów pierwszego poziomu chcemy użyć. Oczywiście przytoczone wyżej wartości należy dobrać tak, aby zachować zadowalającą jakość przy zachowaniu oszczędności miejsca w pamięci.

Trzeba pamiętać, że algorytm ten jest obarczony dwoma wadami:

• dokonuje dwukrotnego przybliżenia rzeczywistych wektorów – raz na etapie podzielenia bazy danych na mniejsze części, drugi raz na etapie kwantyzacji. Może się okazać, że dokument rzeczywiście najbliższy zapytania znajdzie się w innej części bazy. Można częściowo zniwelować to niebezpieczeństwo przeszukując nie jeden ale kilka najbliższych zapytaniu klastrów.
• dodawanie nowych dokumentów (aktualizowanie bazy) może pogorszyć wyniki. Możemy przypisać wektor nowego dokumentu do już istniejących klastrów i skwantyzować go, jednak jeżeli nie aktualizujemy centroidów na obu poziomach, to z kolejnymi aktualizacjami centroidy staną się niereprezentatywne.

Mimo tych wad w praktyce zyski z opisanej metody przeważają. Krótkie czasy wyszukiwania, jak również bardzo znaczna kompresja rozmiarów wektorów są bardzo przydatne, a pewna niedokładność może być tolerowana w większości typowych przypadków wykorzystania – na przykład do wyszukiwania podobnych obrazów, utworów muzycznych czy dokumentów tekstowych. Podział dużej bazy na mniejsze części otwiera też jeszcze jedną istotną możliwość. 

Jeżeli chcemy poprawić dokładność przez przeszukiwanie kilku najbliższych zapytaniu klastrów, to można to wykonywać równolegle, niezależnie od siebie, nawet na innych maszynach przechowujących fragmenty bazy. Tego typu rozwiązanie pozwala efektywniej wykorzystać zasoby (np. maszyny o mniejszej ilości pamięci, które nie zmieściłyby całej bazy) a jednocześnie przyspieszyć obliczenia. 

Zdjęcie główne artykułu pochodzi z unsplash.com.