Wzmocnienie skrótu wrażliwego na lokalizację

10

Usiłuję zbudować skrót cosinus wrażliwy na lokalizację, aby znaleźć potencjalne pary podobnych przedmiotów bez konieczności porównywania każdej możliwej pary. Mam to w zasadzie działające, ale większość par w moich danych wydaje się mieć podobieństwo cosinus w zakresie od -0,2 do +0,2, więc staram się pokroić w kostkę dość dokładnie i wybrać rzeczy o podobieństwie cosinus 0,1 i wyższym.

Czytałem rozdział 3 „Górnicze ogromne zbiory danych”. Mówi on o zwiększeniu dokładności wyboru pary kandydatów przez wzmocnienie rodziny wrażliwej na lokalizację. Myślę, że prawie rozumiem matematyczne wyjaśnienie, ale staram się zobaczyć, jak praktycznie to zrealizuję.

To, co mam do tej pory, jest następujące

Powiedziałem 1000 filmów, każdy z ocenami wybranych użytkowników 1 mln. Każdy film jest reprezentowany przez rzadki wektor wyników użytkownika (numer wiersza = identyfikator użytkownika, wartość = wynik użytkownika)
Buduję N losowych wektorów. Długość wektora odpowiada długości wektorów filmowych (tj. Liczbie użytkowników). Wartości wektorowe to +1 lub -1. W rzeczywistości koduję te wektory jako binarne, aby zaoszczędzić miejsce, z +1 mapowanym na 1 i -1 mapowanym na 0
Buduję wektory szkicowe dla każdego filmu, biorąc iloczyn iloczynu filmu i każdego z N losowych wektorów (a raczej, jeśli utworzę macierz R, układając N losowych wektorów poziomo i układając je jeden na drugim, a następnie szkic dla filmu m to R * m), a następnie przyjmuję znak każdego elementu w powstałym wektorze, więc kończę wektorem szkicu dla każdego filmu z + 1s i -1s, który ponownie koduję jako binarny. Każdy wektor ma długość N bitów.
Następnie szukam podobnych szkiców, wykonując następujące czynności
1. Podzieliłem wektor szkicu na pasma r bitów
2. Każde pasmo bitów r jest liczbą. Łączę ten numer z numerem zespołu i dodaję film do segmentu mieszającego pod tym numerem. Każdy film można dodać do więcej niż jednego segmentu.
3. Następnie patrzę w każde wiadro. Wszystkie filmy znajdujące się w tym samym segmencie są parami kandydującymi.

Porównując to do 3.6.3 mmds, mój krok AND ma miejsce, gdy patrzę na pasma bitów r - para filmów przechodzi krok AND, jeśli bity r mają tę samą wartość. Mój krok OR odbywa się w segmentach: filmy są parami kandydującymi, jeśli oba znajdują się w jednym z segmentów.

Książka sugeruje, że mogę „wzmocnić” moje wyniki, dodając więcej kroków AND i OR, ale brakuje mi praktycznego sposobu, aby to zrobić praktycznie, ponieważ wyjaśnienie procesu budowy kolejnych warstw polega raczej na sprawdzeniu równości par niż na parach wymyślanie numerów wiader.

Czy ktoś może mi pomóc zrozumieć, jak to zrobić?

machine-learning

— Philip Pearl
źródło

4

Myślę, że coś wymyśliłem. Zasadniczo szukam podejścia, które działa w środowisku typu mapa / redukcja i myślę, że takie podejście to robi.

Więc,

załóżmy, że mam pasma r rzędów i chcę dodać kolejny etap AND, powiedzmy kolejne c AND.
więc zamiast bitów b * r potrzebuję skrótów bitów b * r * c
i uruchamiam poprzednią procedurę c razy, za każdym razem na bitach b * r
Jeśli x i y zostaną uznane za parę kandydującą w wyniku dowolnej z tych procedur, wyemituje parę klucz-wartość ((x, y), 1), z krotką identyfikatorów (x, y) jako kluczem i wartością 1
Na końcu procedur c grupuję te pary według klucza i sumy
Każda para (x, y) o sumie równej c była parą kandydującą w każdej z rund c, podobnie jak para kandydacka całej procedury.

Więc teraz mam praktyczne rozwiązanie i wszystko, co muszę zrobić, to ustalić, czy zastosowanie 3 takich kroków rzeczywiście pomoże mi uzyskać lepszy wynik przy mniejszej liczbie bitów skrótu lub lepszej ogólnej wydajności ...

— Philip Pearl
źródło

0

Chciałbym tylko skomentować, ale nie mogę. Szukałem praktycznego leczenia wzmocnienia w LSH, a to, co przedstawiłeś, ma sens. Z tego, co zbieram, podstawową funkcją skrótu jestdla niektórych losowych wektorów , po AND staje się , i wreszcie po OR, lubTeraz możesz ORAZ / LUB używając

h (x, v) = {\begin{cases} 0 & if sgn (x \cdot v) < 0 \\ 1 & else \end{cases}

$h(x,v)=\left\{ \begin{array}{ll}0 & \mbox{if }\textrm{sgn}(x\cdot v) < 0\\ 1 & \mbox{else}\end{array} \right.$

v

$v$

h^{'} (x, i) = (h (x, v_{i + 1}), . . ., h (x, v_{i + r}))

$h'(x,i) = (h(x,v_{i+1}),...,h(x,v_{i+r}))$

h^{″} (x, j) = f (h^{'} (x, r j), j)

$h''(x,j) =f(h'(x,rj),j)$

h^{″} (x, y) = {\begin{cases} 1 & if h^{″} (x, j) = h^{″} (y, j) for any j \in [0, b) \\ 0 & else \end{cases}

$h''(x,y) =\left\{ \begin{array}{ll}1 & \mbox{if }h''(x,j) = h''(y,j) \mbox{ for any }j \in [0,b)\\ 0 & \mbox{else}\end{array} \right.$

h^{″} (x, y)

$h''(x,y)$ jak opisujesz. Następnie wybierałbyś kandydatów na podstawie logicznych instrukcji AND / OR; tak naprawdę nie masz już nic. W tym miejscu, aby kontynuować haszowanie, potrzebujesz mapowania przedziałów, tak aby każdy wektor pojawiał się tylko raz w , ale może to również spowodować wprowadzenie fałszywych trafień i / lub negatywy Jednym z pomysłów na skrót jest minimum dla wszystkich (lub minimum dla wszystkich i wszystkich bezpośrednio i pośrednio związanych ). Oba wyraźnie wprowadziłyby stronniczość. Mogę wypróbować jeden z nich, choć nie jestem pewien, czy skróty z jednego losowego AND / OR będą miały znaczenie następnym razem.

\hat{h} : S \to S^{'}

$\hat{h}:S\to S'$

S^{'}

$S'$

h^{″} (x, j)

$h''(x,j)$

j

$j$

j

$j$

y

$y$

v

$v$ i może duża liczba replikacji?

— deasmhumnha
źródło