Como entender o hash sensível à localidade?

Percebi que o LSH parece uma boa maneira de encontrar itens semelhantes com propriedades de alta dimensão.

Depois de ler o artigo http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf , ainda estou confuso com essas fórmulas.

Alguém conhece um blog ou artigo que explica isso da maneira mais fácil?

O melhor tutorial que eu já vi para o LSH está no livro: Mineração de conjuntos de dados maciços. Verifique o Capítulo 3 - Encontrar itens semelhantes http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Também recomendo o slide abaixo: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . O exemplo no slide ajuda-me bastante a entender o hash da semelhança de cosseno.

Tomo emprestado dois slides de Benjamin Van Durme e Ashwin Lall, ACL2010 e tento explicar um pouco as intuições das famílias LSH para distância cosseno.

• Na figura, existem dois círculos de cor vermelha e amarela , representando dois pontos de dados bidimensionais. Estamos tentando encontrar a semelhança de cossenos usando LSH.
• As linhas cinzas são alguns aviões uniformemente escolhidos aleatoriamente.
• Dependendo da localização do ponto de dados acima ou abaixo de uma linha cinza, marcamos essa relação como 0/1.
• No canto superior esquerdo, existem duas linhas de quadrados brancos / pretos, representando a assinatura dos dois pontos de dados, respectivamente. Cada quadrado corresponde a um bit 0 (branco) ou 1 (preto).
• Portanto, uma vez que você tenha um conjunto de aviões, poderá codificar os pontos de dados com sua localização respectiva aos planos. Imagine que, quando temos mais planos na piscina, a diferença angular codificada na assinatura fica mais próxima da diferença real. Porque apenas os planos que residem entre os dois pontos darão aos dois dados um valor de bit diferente.

• Agora, olhamos para a assinatura dos dois pontos de dados. Como no exemplo, usamos apenas 6 bits (quadrados) para representar cada dado. Este é o hash LSH para os dados originais que temos.
• A distância entre os dois valores de hash é 1, porque suas assinaturas diferem apenas em 1 bit.
• Considerando o comprimento da assinatura, podemos calcular sua similaridade angular, como mostrado no gráfico.

Eu tenho algum código de exemplo (apenas 50 linhas) em python aqui que está usando similaridade de cosseno. https://gist.github.com/94a3d425009be0f94751

Os tweets no espaço vetorial podem ser um ótimo exemplo de dados de alta dimensão.

Confira minha postagem no blog sobre a aplicação do Locality Sensitive Hashing em tweets para encontrar outros semelhantes.

http://micvog.com/2013/09/08/storm-first-story-detection/

E como uma imagem é composta por mil palavras, verifique a imagem abaixo:

http://micvog.files.wordpress.com/2013/08/lsh1.png

Espero que ajude. @mvogiatzis

Aqui está uma apresentação de Stanford que explica isso. Isso fez uma grande diferença para mim. A parte dois é mais sobre o LSH, mas a parte um também cobre.

Uma imagem da visão geral (há muito mais nos slides):

Pesquisa com vizinhos próximos em dados de alta dimensão - Parte 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Pesquisa por vizinhos próximos em dados de alta dimensão - Parte 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

• O LSH é um procedimento que recebe como entrada um conjunto de documentos / imagens / objetos e gera uma espécie de Tabela Hash.
• Os índices desta tabela contêm os documentos, de modo que os documentos que estão no mesmo índice são considerados semelhantes e os que estão em índices diferentes são " diferentes " ".
• Onde similar depende do sistema métrico e também de um limiar de similaridade s que atua como um parâmetro global de LSH.
• É até você para definir o que é o limite adequado é é para o seu problema.

É importante sublinhar que diferentes medidas de similaridade têm diferentes implementações de LSH.

No meu blog, tentei explicar minuciosamente o LSH para os casos de minHashing (medida de similaridade do jaccard) e simHashing (medida da distância do cosseno). Espero que você ache útil: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Eu sou uma pessoa visual. Aqui está o que funciona para mim como uma intuição.

Diga que cada uma das coisas que você deseja pesquisar aproximadamente são objetos físicos, como uma maçã, um cubo, uma cadeira.

Minha intuição para um LSH é que é semelhante às sombras desses objetos. Por exemplo, se você pegar a sombra de um cubo 3D, obterá um quadrado 2D em um pedaço de papel, ou uma esfera 3D obterá uma sombra circular em um pedaço de papel.

Eventualmente, existem muito mais do que três dimensões em um problema de pesquisa (onde cada palavra em um texto pode ser uma dimensão), mas a analogia da sombra ainda é muito útil para mim.

Agora podemos comparar com eficiência seqüências de bits em software. Uma cadeia de bits de comprimento fixo é mais ou menos como uma linha em uma única dimensão.

Assim, com um LSH, eu projeto as sombras dos objetos eventualmente como pontos (0 ou 1) em uma única linha de comprimento fixo / sequência de bits.

O truque é pegar as sombras de forma que elas ainda façam sentido na dimensão inferior, por exemplo, elas se assemelham ao objeto original de uma maneira suficientemente boa que possa ser reconhecida.

Um desenho 2D de um cubo em perspectiva me diz que é um cubo. Mas não consigo distinguir facilmente um quadrado 2D de uma sombra de cubo 3D sem perspectiva: os dois me parecem um quadrado.

O modo como apresento meu objeto à luz determinará se eu recebo uma boa sombra reconhecível ou não. Então, penso em um LSH "bom" como aquele que transformará meus objetos diante de uma luz, de modo que sua sombra seja melhor reconhecível como representando meu objeto.

Para recapitular: penso nas coisas que indexam com um LSH como objetos físicos como um cubo, uma mesa ou cadeira, e projeto suas sombras em 2D e, eventualmente, ao longo de uma linha (uma sequência de bits). E uma "função" boa "LSH" "é como apresento meus objetos na frente de uma luz para obter uma forma aproximadamente distinguível na planície 2D e, posteriormente, na minha sequência de bits.

Finalmente, quando quero pesquisar se um objeto que eu tenho é semelhante a alguns objetos que indexei, tomo as sombras desse objeto de "consulta" da mesma maneira para apresentar meu objeto na frente da luz (eventualmente terminando um pouco string também). E agora posso comparar o quão semelhante é essa cadeia de bits com todas as minhas outras cadeias de bits indexadas, que é um proxy para procurar todos os meus objetos se eu encontrasse uma maneira boa e reconhecível de apresentar meus objetos à minha luz.

Como uma resposta muito curta, tldr :

Um exemplo de hash sensível à localidade pode ser o primeiro a definir planos aleatoriamente (com rotação e deslocamento) no seu espaço de entradas para hash e, em seguida, soltar seus pontos em hash no espaço e para cada plano que você medir se o ponto for acima ou abaixo (por exemplo: 0 ou 1), e a resposta é o hash. Portanto, pontos semelhantes no espaço terão um hash semelhante se medidos com a distância do cosseno antes ou depois.

Você pode ler este exemplo usando o scikit-learn: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer