Uma busca ordenada branch-and-bound para solução do problema de classificação semissupervisionada usando classificadores de larga margem
| Autor: | Araújo, Hygor Xavier |
|---|---|
| Přispěvatelé: | Villela, Saulo Moraes, Neto, Raul Fonseca, Borges, Carlos Cristiano Hasenclever, Leite, Saul de Castro |
| Jazyk: | portugalština |
| Rok vydání: | 2019 |
| Předmět: |
Aprendizado semissupervisionado
Support vector machine Máquina de vetores suporte CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO [CNPQ] Semi-supervised learning Best-first search Separação de baixa densidade Transductive inference Low density separation Inferência transdutiva Busca ordenada admissível |
| Zdroj: | Repositório Institucional da UFJF Universidade Federal de Juiz de Fora (UFJF) instacron:UFJF |
| Popis: | 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. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|