Uma busca ordenada branch-and-bound para solução do problema de classificação semissupervisionada usando classificadores de larga margem
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidade Federal de Juiz de Fora (UFJF)
DOI
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.
Description
Citation
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwise noted, this item's license is described as Acesso Aberto

