Uma busca ordenada branch-and-bound para solução do problema de classificação semissupervisionada usando classificadores de larga margem - Araújo, Hygor Xavier (2019)
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.