Como entender o hash sensível à localidade?

156

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?

WoooHaaaa
fonte
3
Leia o capítulo 3 de Ullman - "ENCONTRANDO ITENS SIMILARES" infolab.stanford.edu/~ullman/mmds.html
achini

Respostas:

250

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. insira a descrição da imagem aqui

  • 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.

insira a descrição da imagem aqui

  • 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

verdura
fonte
por que é chamado de localidade sensível? porque a atribuição de cada bit depende da localidade do ponto de dados para cada plano?
Nawara #
21
sensível à localidade - os pontos de dados localizados próximos um do outro são mapeados para hashes semelhantes (no mesmo intervalo com alta probabilidade).
greeness
2
Desculpe o atraso neste tópico, mas eu tinha uma pergunta sobre o cosseno. A apresentação diz que o valor do bit é um se o produto escalar entre o vetor real e o vetor plano> = 0 ou então for 0. Qual é a direção do vetor plano porque ângulos entre 90 graus e 180 graus também fornecerão uma cosseno que é negativo. Suponho que cada plano é composto de dois vetores e assumimos o menor ângulo que é feito com o vetor real.
vkaul11
Obrigado. Então, é correto dizer que h codifica a diferença angular eb a "precisão"? Assim, eu entendo que h * PI é teta em radiante eb a precisão do ângulo.
precisa saber é o seguinte
1
O slide que você forneceu é muito elegante: cs.jhu.edu/~vandurme/papers/VanDurmeLallACL10-slides.pdf - você poderia também explicar a lógica matemática do "truque de agrupamento" - ou os conceitos de álgebra linear que devo procurar em para entender isso?
precisa saber é o seguinte
21

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

insira a descrição da imagem aqui

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

nilsi
fonte
Por que não usar apenas minhash diretamente como sua função LSH?
Thomas Ahle
1
Acredito que, porque o número de não duplicatas por bloco permanece alto o suficiente, enquanto que se usarmos m funções hash independentes, a probabilidade de duplicados não próximos mapear para o mesmo bloco reduz drasticamente.
Shatu
7
  • 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.

insira a descrição da imagem aqui

É 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/

Carlos Teixeira
fonte
2

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.

Philippe Ombredanne
fonte
0

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

Guillaume Chevalier
fonte