22 obserwujących
105 notek
164k odsłony
338 odsłon

Multi index hashing, czyli jak szybko znaleźć to, czego szukamy w gąszczu liczb.

Google
Google
Wykop Skomentuj2

Wyobraźmy sobie bardzo duuuuży zbiór danych. Zbiór liczony w miliardach rekordów leżących spokojnie na dysku twardym. Nie jest to taki zwykły zbiór. Zawiera on kilkaset tysięcy cech obiektów, z którymi spotykasz się codziennie. Jakich zapytasz? A choćby takich, które teraz widzisz przed oczami - polskich słów połączonych w zdania.

Każdy ciąg liczb w tym zbiorze zawiera atrybuty każdego ze słów w naszym języku i tworzy sens zdania, w jakim to słowo występuje. Każde zdanie jest reprezentowane przez wektor o setkach kolumn. Każda z kolumn to jedna z cech, na którą składają się cechy wszystkich słów (z wagą zależną od istotności słowa).

Miarę podobieństwa dwóch zdań wyznaczamy stosując funkcję cosine similarity. Określa ona kąt między wektorami reprezentującymi wyznaczony wcześniej sens zdań.


0 <= cosim(v1, v2) <= 1 lub bardziej ogólnie -1 <= cosim(v1, v2) <= 1 (-1 to semantyczne przeciwieństwo, zaskakujące prawda?).<br />


Jeśli zdania są podobne - posiadają podobne znaczenie (semantycznie), wynik zbliżony będzie do 1. Zdania zupełnie różne, niepodobne dadzą w wyniku -1. Funkcja jest prosta i całkiem sprawnie działa dla dużej liczby danych (miliardów liczb). Jednak skan całego zbioru wektor po wektorze dla każdego zapytania trwa długo nawet gdy zastosujemy dyski półprzewodnikowe. Długo znaczy kilkadziesiąt sekund a człowiek niecierpliwi się już po 3 sekundach oczekiwania (jedna z zasad konstruowania GUI).

W poprzednich notkach opisywałem jak taki zbiór można uzyskać i do czego może on służyć. W tej opisze jak taki zestaw danych efektywnie przeszukiwać. Nie jest to proste. Nie istnieje bowiem możliwość utworzenia indeksu w takiej postaci jaki znamy z baz danych. Nie jesteśmy w stanie uporządkować zbioru wektorów by łatwo i szybko go przeszukiwać. Nie jesteśmy w stanie bowiem cosine similarity jako funkcja „odległości” nie spełnia warunku triangle inequity (nierówności trójkąta) który jest wymagany dla technik indeksujących a ogólnie mówiąc przestrzeni metrycznych. Kto chce może szybko znaleźć dowód w googlach.

Możemy ratować się normalizacją danych czyli naszych wektorów i sprowadzić funkcję wyznaczającą podobieństwo do postaci np. dot productu ale tracimy masę cennych informacji i reprezentacja staje się mniej użyteczna. Czy można inaczej? Czy można uzyskać jakiś algorytm który da przybliżony wynik do wyniku pełnego skanu zbioru danych?

Najszybsze metody wyszukiwania danych bazują na funkcjach przyporządkowujących danemu zapytaniu pewną liczbę, indeks. Dla dowolnego zapytania dostajemy kolejne indeksy w tablicy wskazujące na szukane dane. Nie ma szybszej metody, istnieją tylko szybsze funkcje wyznaczające indeks. Funkcje powinny być na tyle proste by były szybkie i na tyle złożone by nie zwracały dla dwóch różnych zapytań tego samego indeksu. Nie zwracały zbyt często. Jest to tak zwana kolizja i jest to naturalna konsekwencja istnienia funkcji która działa dla dowolnego zapytania i zwraca indeks ze skończonego zbioru wartości.

Funkcję tę nazywamy funkcja haszującą. Pewne grupy takich funkcji stosuje również kryptografia. Funkcje te jednak spełniają dodatkowe wymagania np. by dla podobnych zapytań (tekstu) indeksy (wynik) znacząco się różniły. W ten sposób znając indeks (wynik) nie jesteśmy w stanie domyślić się zapytania (treści chronionej kryptograficznie). Funkcje MD5, SHA też trapią kolizje ale nie o tym dzisiaj.

Jak wykorzystamy funkcję haszujące do przeszukiwania milionów rekordów? Najpierw trzeba się przyjrzeć naszej funkcji zwracającej miarę podobieństwa zapytania.


-1 <= cosim(v1, v2) <= 1</p>


dla dwóch dowolnych wektorów v1, v2 z N-wymiarowej przestrzeni przyporządkowuje liczbę z przedziału -1..1


Mamy więc zwykły zbiór liczb rzeczywistych z określonego przedziału. Wyznaczając losowo punkty w tym przedziale jesteśmy w stanie określić położenie każdego z wektorów względem wylosowanych punktów. Położenia określonego binarnie - tak punkt jest na lewo od punktu p1, nie punkt jest na prawo od punktu p2 itd.

image

Nie wyznaczamy "odległości" w przestrzeni a jedynie stwierdzamy, po której stronie wybranego losowo punktu znajduje się nasz badany wektor. Pewnie uważny czytelnik zauważy, że dla serii punktów dobranych losowo p1,p2,p3,p4,... otrzymujemy binarną reprezentację naszego wektora wyznaczoną z dowolną precyzją. Tym ona większa im dłuższa seria losowych punktów i dłuższy binarny wektor.

Reprezentacje binarne wektorów dla podanego zbioru odniesienia:
A = 111
B = 001
C = 001
D = 000

Zatem dla każdego wektora z naszego zbioru i dla wcześniej przygotowanego zbioru losowych wektorów odniesienia istnieje tylko jedna reprezentacja binarna. Zauważcie, że dla wektorów podobnych reprezentacje binarne będą również podobne i znamy miarę ich podobieństwa - odległość Hamminga.

Mamy, więc zamiast setek liczb rzeczywistych krótki ciąg zer i jedynek (256, 128, 64 bit). Reprezentacje są wspólne dla podobnych wektorów wejściowych i stanowią koszyk - bucket, inaczej mówiąc indeks naszej funkcji haszującej, która z postaci wektora liczb rzeczywistych utworzyła binarną reprezentację o skończonej liczbie kombinacji. W koszyku znajdują się wszystkie wektory reprezentujące najlepszych kandydatów, których teraz powinniśmy żmudnie, siłowo wektor po wektorze sprawdzić z naszym zapytaniem. Nie jest ich już dużo tylko kilkadziesiąt tysięcy a z takimi liczbami komputery radzą sobie w pojedynczych milisekundach.

Jest tylko jeden problem. Ilość kombinacji wciąż przekracza możliwości adresowe komputera. Indeks reprezentowany przez 32bity daje 4294967296 możliwych kombinacji a 64bity 1.8446744e+19. To wciąż sporo. Czy możemy coś jeszcze zrobić?

Możemy zbudować multindeks, który znacznie ograniczy rozmiar tablicy adresującej wektory. Całą reprezentację binarną rozbijemy na części o stałej długości. Indeksujemy cały zbiór danych tyle razy na ile części rozbijemy reprezentację binarną.

Przypuśćmy, że 128 bitowa reprezentacja zostanie rozbita na 8 bitowe koszyki nowych indeksów. Indeksów będzie w takiej konfiguracji 16 i w każdym, każdy wektor naszego dużego zbioru zostanie przypisany do jednego z 256 koszyków (8 bitowy rozmiar koszyka). Możliwości podziału jest oczywiście wiele.

Wyszukując wektor (zapytanie) i wektory podobne (odpowiedzi najlepiej dopasowane) algorytm wymaga zebrania z kolejnych 16 indeksów wszystkich pasujących koszyków (8 bit fragmentów) i wykonania na tak ograniczonym zbiorze standardowego porównania zapytania z elementami zbioru. Zamiast skanu całego zbioru, wykonujemy operację cosine similarity tylko na liście kandydatów, co przyspiesza całą operację kilkaset razy, gdy trzymamy indeksy w pamięci operacyjnej komputera.

Pomijam złożone, inżynieryjne kwestie optymalizacji algorytmu, wspomnę, że wydajność zależy mocno od ilości podziałów reprezentacji binarnej jej długości oraz od organizacji dostępu do dysku by wykorzystać maksymalne transfery dzisiejszych dysków w trybie random access  (3-4 GB) oraz architektury sieciowej (indeks można śmiało rozproszyć na N serwerów).

Wykop Skomentuj2
Ciekawi nas Twoje zdanie! Napisz notkę Zgłoś nadużycie

Więcej na ten temat

Salon24 news

Co o tym sądzisz?

Inne tematy w dziale Technologie