Use este identificador para citar ou linkar para este item: https://repositorio.ufjf.br/jspui/handle/ufjf/11434
Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
hygorxavieraraujo.pdf515.82 kBAdobe PDFThumbnail
Visualizar/Abrir
Tipo: Dissertação
Título: Uma busca ordenada branch-and-bound para solução do problema de classificação semissupervisionada usando classificadores de larga margem
Autor(es): Araújo, Hygor Xavier
Primeiro Orientador: Villela, Saulo Moraes
Co-orientador: Neto, Raul Fonseca
Membro da banca: Borges, Carlos Cristiano Hasenclever
Membro da banca: Leite, Saul de Castro
Resumo: Para a solução do problema de classificação através da inferência transdutiva, é necessário encontrar os rótulos de um conjunto previamente definido. No entanto, calcular a melhor rotulação dessas amostras é um problema combinatorial NP-difícil. Neste trabalho, um método que combina os métodos de busca branch-and-bound e best-first é proposto para resolver o problema de rotulação buscando pela solução ótima. Para orientar a busca, foram usados classificadores baseados em margem, como a Máquina de Vetores Suporte (Support Vector Machine – SVM), e uma função de avaliação monótona com base nos valores de margem deste classificador, o que leva á solução globalmente ótima. Para lidar com o alto custo computacional da solução de máxima margem, também foi proposta uma solução heurística que é usada como um limite inferior sendo computado em tempo constante através da solução de um problema de classificação com o SVM. Comparando o método proposto com a Máquina de Vetores Suporte Transdutiva (Transductive Support Vector Machine – TSVM), os resultados mostraram melhorias significativas no tempo de execução e valores superiores de margem. Além disso, duas novas heurísticas são apresentadas para reduzir o número de estados explorados e acelerar a exploração do espaço de busca. O método e suas heurísticas são avaliados e comparados ao SVM e ao TSVM, mostrando resultados competitivos.
Abstract: To solve the classification problem through the transductive inference, it is necessary to find the labels of a previously defined set. However, computing the best labeling of these samples is an NP-hard combinatorial problem. In this work, a method that combines the branch-and-bound and the best-first search methods is proposed to solve the labeling problem by searching for the optimal solution. To guide the search, margin-based classifiers, such as the Support Vector Machine (SVM), and a monotone evaluation function based on the margin values of this classifier were used, leading to the optimal global solution. To deal with the high computational cost of the maximum margin solution, we also propose a heuristic solution that is used as a lower bound, being computed in constant time by solving a classification problem with SVM. Comparing our method with the Transductive Support Vector Machine (TSVM), the results showed significant improvements in the runtime and higher margin values. Furthermore, two new heuristics are presented to reduce the number of explored states and speed up the exploration of the search space. The method and its heuristics are evaluated and compared to SVM and TSVM, showing competitive results.
Palavras-chave: Inferência transdutiva
Aprendizado semissupervisionado
Busca ordenada admissível
Máquina de vetores suporte
Separação de baixa densidade
Transductive inference
Semi-supervised learning
Best-first search
Support vector machine
Low density separation
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editor: Universidade Federal de Juiz de Fora (UFJF)
Sigla da Instituição: UFJF
Departamento: ICE – Instituto de Ciências Exatas
Programa: Programa de Pós-graduação em Ciência da Computação
Tipo de Acesso: Acesso Aberto
Attribution 3.0 Brazil
Licenças Creative Commons: http://creativecommons.org/licenses/by/3.0/br/
URI: https://repositorio.ufjf.br/jspui/handle/ufjf/11434
Data do documento: 5-Set-2019
Aparece nas coleções:Mestrado em Ciência da Computação (Dissertações)



Este item está licenciado sob uma Licença Creative Commons Creative Commons