[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] MATHEUS TELLES WERNER

[pt] DISTANCIA ENTRE DOCUMENTOS

[pt] WORD MOVER S DISTANCE

[pt] WORD EMBEDDING

[en] DOCUMENT DISTANCE

[en] WORD MOVER S DISTANCE

[en] WORD EMBEDDING

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

EDUARDO SANY LABER

MARCO SERPA MOLINARO

EDUARDO SANY LABER

RAUL PIERRE RENTERIA

2020-04-02

2019-04-24

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317@2

https://doi.org/10.17771/PUCRio.acad.47317