Return to search

[en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE / [pt] UMA ABORDAGEM RÁPIDA E ECONÔMICA PARA WORD MOVER S DISTANCE

[pt] O Word Mover s Distance (WMD) proposto por Kusner et al.
[ICML,2015] é uma função de distância entre documentos que se aproveita
das relações semânticas entre palavras extraidas por suas Word Embeddings. Essa função de distância se mostrou bastante eficaz, obtendo taxas
de erro estado da arte para problemas de classificação, porém ao mesmo
tempo inviável para largas coleções ou grandes documentos devido a ser
necessário computar um problema de transporte em um grafo bipartido
completo para cada par de documentos.
Assumindo algumas hipóteses, que são respaldadas por propriedades empíricas das distâncias entre as Word Embeddings, nós simplificamos o WMD
de forma a obter uma nova função de distância o qual requer a solução
de um problema de fluxo máximo em um grafo esparço, que pode ser resolvido mais rapidamente do que um problema de transporte em um grafo
denso. Nossos experimentos mostram que conseguimos obter ganhos de performance até três ordens de magnitude acima do WMD enquanto mantendo
as mesmas taxas de erro na tarefa de classificação de documentos. / [en] The Word Mover s Distance (WMD) proposed in Kusner et. al.
[ICML,2015] is a distance between documents that takes advantage of semantic relations among words that are captured by their Word Embeddings.
This distance proved to be quite effective, obtaining state-of-the-art error
rates for classification tasks, but also impracticable for large collections or
documents because it needs to compute a transportation problem on a complete bipartite graph for each pair of documents.
By using assumptions, that are supported by empirical properties of the
distances between Word Embeddings, we simplify WMD so that we obtain a
new distance whose computation requires the solution of a max flow problem
in a sparse graph, which can be solved much faster than the transportation
problem in a dense graph. Our experiments show that we can obtain a
performance gain up to three orders of magnitude over WMD while maintaining
the same error rates in document classification tasks.

Identiferoai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:47317
Date02 April 2020
CreatorsMATHEUS TELLES WERNER
ContributorsEDUARDO SANY LABER
PublisherMAXWELL
Source SetsPUC Rio
LanguageEnglish
Detected LanguagePortuguese
TypeTEXTO

Page generated in 0.0021 seconds