Explorando paralelismo em tarefas de similaridade de documentos e aplicações

Autor: Amorim, Leonardo Afonso
Přispěvatelé: Martins, Wellington Santos, Vincenzi, Auri Marcelo Rizzo, Rodrigues, Cássio Leonardo, Rosa, Thierson Couto, Martins, Weber
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da UFG
Universidade Federal de Goiás (UFG)
instacron:UFG
Popis: A quantidade de dados disponíveis continua a crescer rapidamente e muitos desses dados correspondem a textos que expressam a linguagem humana, que é de natureza não estruturada. Uma maneira de dar alguma estrutura a esses dados é convertendo os documentos em um vetor de recursos correspondentes a frequências de palavras (contagem de termos, tf-idf etc.) ou construindo palavras com representação latente. Essa transformação nos permite processar dados textuais com operações como medida de similaridade, pesquisa de similaridade, classificação, entre outras. No entanto, isso só é possível graças a algoritmos mais sofisticados que exigem maior poder computacional. Neste trabalho, exploramos o paralelismo para permitir o uso de algoritmos eficientes para realizar tarefas de busca de documentos por similaridade e aplicar alguns dos resultados a uma importante aplicação em engenharia de software. A busca por similaridade de dados textuais é comumente realizada por meio do algoritmo kNN, os “k” vizinhos mais próximos, no qual pares de vetores de documentos são comparados e os “k” mais similares são retornados. Para esta tarefa apresentamos o FaSST-kNN, um algoritmo paralelo de granularidade fina, que aplica técnicas de filtragem baseadas nos termos mais importantes do documento de consulta usando tf-idf. O algoritmo implementado em uma GPU melhorou os k vizinhos mais próximos na busca por até 60x em comparação com uma linha de base, também em execução em uma GPU. A similaridade de documento usando tf-idf é baseada em um esquema de frequência para palavras que reflete a importância de uma palavra para um documento em uma coleção. Recentemente, uma medida de similaridade mais sofisticada, chamada representação latente de palavras (word embedding), se tornou popular. Um vetor é criado para cada palavra. O vetor armazena de forma latente relações de coocorrência entre palavras em um determinado contexto, capturando relações semânticas complexas entre palavras. A fim de gerar eficientemente representação latente de palavras, propomos um algoritmo paralelo de granularidade fina que encontra as palavras k menos similares ou mais próximas para gerar amostras negativas para criar essas representações. O algoritmo implementado em um sistema multi-GPU escala linearmente e foi capaz de gerar representações de palavras 13x mais rápidos que o algoritmo Word2Vec multicore original, mantendo a precisão dos resultados no mesmo nível daqueles produzidos pelo programa padrão de geração de representação de palavras latentes. Finalmente, aplicamos nossa solução acelerada de de representação de palavras latentes ao problema de avaliar a qualidade das correções em Reparo Automatizado de Software. A implementação proposta foi capaz de lidar com grande corpus, de forma computacionalmente eficiente, sendo uma alternativa promissora ao processamento de milhões de arquivos de código fonte necessários para esta tarefa. The amount of data available continues to grow rapidly and much of it corresponds to text expressing human language, that is unstructured in nature. One way of giving some structure to this data is by converting the documents to a vector of features corresponding to word frequencies (term count, tf-idf, etc) or word embeddings. This transformation allows us to process textual data with operations such as similarity measure, similarity search, classification, among others. However, this is only possible thanks to more sophisticated algorithms which demand higher computational power. In this work, we exploit parallelism to enable the use of parallel algorithms to document similarity tasks and apply some of the results to an important application in software engineering. The similarity search for textual data is commonly performed through a k nearest neighbor search in which pairs of document vectors are compared and the k most similar are returned. For this task we present FaSSTkNN, a fine-grain parallel algorithm, that applies filtering techniques based on the most common important terms of the query document using tf-idf. The algorithm implemented on a GPU improved the top k nearest neighbors search by up to 60x compared to a baseline, also running on a GPU. Document similarity using tf-idf is based on a scoring scheme for words that reflects how important a word is to a document in a collection. Recently a more sophisticated similarity measure, called word embedding, has become popular. It creates a vector for each word that indicates co-occurrence relationships between words in a given context, capturing complex semantic relationships between words. In order to generate word embeddings efficiently, we propose a fine-grain parallel algorithm that finds the k less similar or farthest neighbor words to generate negative samples to create the embeddings. The algorithm implemented on a multi-GPU system scaled linearly and was able to generate embeddings 13x faster than the original multicore Word2Vec algorithm while keeping the accuracy of the results at the same level as those produced by standard word embedding programs. Finally, we applied our accelerated word embeddings solution to the problem of assessing the quality of fixes in Automated Software Repair. The proposed implementation was able to deal with large corpus, in a computationally efficient way, being a promising alternative to the processing of million source code files needed for this task. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
Databáze: OpenAIRE
Externí odkaz: