Uma busca ordenada branch-and-bound para solução do problema de classificação semissupervisionada usando classificadores de larga margem

• Ano de defesa: 2019
• Autor(a) principal: Araújo, Hygor Xavier
• Orientador(a): Villela, Saulo Moraes
• Banca de defesa: Borges, Carlos Cristiano Hasenclever , Leite, Saul de Castro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Juiz de Fora (UFJF)
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação
• Departamento: ICE – Instituto de Ciências Exatas
• País: Brasil
• Palavras-chave em Português: 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
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufjf.br/jspui/handle/ufjf/11434

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.