[en] APPROXIMATE NEAREST NEIGHBOR SEARCH FOR THE KULLBACK-LEIBLER DIVERGENCE

• Ano de defesa: 2018
• Autor(a) principal: DANIEL ALEJANDRO MESEJO-LEON
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] DIVERGENCIA KULLBACK-LEIBER; [pt] ARVORES DE BREGMAN; [pt] HASH SENSIVEL A LOCALIDADE; [pt] INDICES INVERTIDOS; [pt] BUSCA DE VIZINHOS MAIS PROXIMOS; [en] KULLBACK-LEIBLER DIVERGENCE; [en] BREGMAN BALL TREE; [en] LOCALITY SENSITIVE HASHING; [en] INVERTED INDEX; [en] NEAREST NEIGHBOR SEARCH
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=33305&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=33305&idi=2; http://doi.org/10.17771/PUCRio.acad.33305

[pt] Em uma série de aplicações, os pontos de dados podem ser representados como distribuições de probabilidade. Por exemplo, os documentos podem ser representados como modelos de tópicos, as imagens podem ser representadas como histogramas e também a música pode ser representada como uma distribuição de probabilidade. Neste trabalho, abordamos o problema do Vizinho Próximo Aproximado onde os pontos são distribuições de probabilidade e a função de distância é a divergência de Kullback-Leibler (KL). Mostramos como acelerar as estruturas de dados existentes, como a Bregman Ball Tree, em teoria, colocando a divergência KL como um produto interno. No lado prático, investigamos o uso de duas técnicas de indexação muito populares: Índice Invertido e Locality Sensitive Hashing. Os experimentos realizados em 6 conjuntos de dados do mundo real mostraram que o Índice Invertido é melhor do que LSH e Bregman Ball Tree, em termos de consultas por segundo e precisão.