[en] A FAST AND SPACE-ECONOMICAL APPROACH TO 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 p...
| Author: | |
|---|---|
| Format: | Doctoral thesis |
| Status: | Published version |
| Publication date: | 2020 |
| Country: | Brasil |
| Institution: | PUC_RIO |
| Repository: | Repositório Institucional da PUC-RIO (Projeto Maxwell) |
| Language: | English |
| OAI Identifier: | oai:MAXWELL.puc-rio.br:47317 |
| Online Access: | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317&idi=1 https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317&idi=2 http://doi.org/10.17771/PUCRio.acad.47317 |
| Access Level: | Open access |
| Keyword: | [pt] DISTANCIA ENTRE DOCUMENTOS [pt] WORD MOVER S DISTANCE [pt] WORD EMBEDDING [en] DOCUMENT DISTANCE [en] WORD MOVER S DISTANCE [en] WORD EMBEDDING |
| _version_ | 1878752173865566208 |
|---|---|
| author | MATHEUS TELLES WERNER |
| author_browse | MATHEUS TELLES WERNER |
| author_facet | MATHEUS TELLES WERNER |
| author_role | author |
| collection | Repositório Institucional da PUC-RIO (Projeto Maxwell) |
| description | [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. |
| eu_rights_str_mv | openAccess |
| format | doctoralThesis |
| id | BR_24a85f32a35fb3eabbbef8f6fa5a287c |
| institution | PUC_RIO |
| instname_str | Pontifícia Universidade Católica do Rio de Janeiro (PUC-RIO) |
| language | eng |
| network_acronym_str | BR |
| network_name_str | Brasil |
| oai_identifier_str | oai:MAXWELL.puc-rio.br:47317 |
| publishDate | 2020 |
| publishDateSort | 2020 |
| publisher | MAXWELL |
| publisherStr | MAXWELL |
| reponame_str | Repositório Institucional da PUC-RIO (Projeto Maxwell) |
| spelling | [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 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. MAXWELL https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317&idi=1 https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317&idi=2 http://doi.org/10.17771/PUCRio.acad.47317 |
| spellingShingle | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE 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 |
| status_str | publishedVersion |
| title | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE |
| title_full | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE |
| title_fullStr | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE |
| title_full_unstemmed | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE |
| title_short | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE |
| title_sort | [en] A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE |
| topic | [pt] DISTANCIA ENTRE DOCUMENTOS [pt] WORD MOVER S DISTANCE [pt] WORD EMBEDDING [en] DOCUMENT DISTANCE [en] WORD MOVER S DISTANCE [en] WORD EMBEDDING |
| topic_facet | [pt] DISTANCIA ENTRE DOCUMENTOS [pt] WORD MOVER S DISTANCE [pt] WORD EMBEDDING [en] DOCUMENT DISTANCE [en] WORD MOVER S DISTANCE [en] WORD EMBEDDING |
| url | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317&idi=1 https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=47317&idi=2 http://doi.org/10.17771/PUCRio.acad.47317 |