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

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.