c - para - labels trello




Como entender o Hashing Sensível à Localidade? (4)

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

Depois de ler o documento 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?



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 a tomar as sombras desses objetos. Como se você pegasse a sombra de um cubo 3D, você obtém um quadrado 2D em um pedaço de papel, ou uma esfera 3D lhe dará uma sombra semelhante a um círculo em um pedaço de papel.

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

Agora podemos comparar eficientemente strings de bits no software. Uma cadeia de bits de comprimento fixo é mais ou menos como uma linha em uma única dimensão.

Assim, com um LSH, projeto as sombras dos objetos como pontos (0 ou 1) em uma única linha de comprimento / linha de bit fixa.

O truque todo é pegar as sombras de tal 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 pode ser reconhecida.

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

Como eu apresento meu objeto para a luz determinará se eu obtenho uma boa sombra reconhecível ou não. Então eu penso em um LSH "bom" como aquele que irá transformar meus objetos na frente de uma luz tal que sua sombra seja mais reconhecível como representando meu objeto.

Então, para recapitular: eu penso em coisas para indexar com um LSH como objetos físicos como um cubo, uma mesa ou uma cadeira, e eu projetei suas sombras em 2D e, eventualmente, ao longo de uma linha (uma cadeia de bits). E uma "boa" função "LSH" é como eu apresento meus objetos na frente de uma luz para obter uma forma aproximadamente distinta na planície 2D e depois na minha cadeia de bits.

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



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

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

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





locality-sensitive-hash