RUO Home

Repositorio Institucional de la Universidad de Oviedo

View Item 
  •   RUO Home
  • Producción Bibliográfica de UniOvi: RECOPILA
  • Capítulos de libros
  • View Item
  •   RUO Home
  • Producción Bibliográfica de UniOvi: RECOPILA
  • Capítulos de libros
  • View Item
    • español
    • English
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

All of RUOCommunities and CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_issnAuthor profilesThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_issn

My Account

LoginRegister

Statistics

View Usage Statistics

RECENTLY ADDED

Last submissions
Repository
How to publish
Resources
FAQs

Using A* for inference in probabilistic classifier chains

Author:
Mena Waldo, DeinerUniovi authority; Montañés Roces, ElenaUniovi authority; Quevedo Pérez, José RamónUniovi authority; Coz Velasco, Juan José delUniovi authority
Publication date:
2015
Editorial:

Association for the Advancement of Artificial Intelligence

Publisher version:
http://www.aaai.org/Library/IJCAI/ijcai15contents.php
Descripción física:
p. 3707-3713
Abstract:

Probabilistic Classifiers Chains (PCC) offers interesting properties to solve multi-label classification tasks due to its ability to estimate the joint probability of the labels. However, PCC presents the major drawback of having a high computational cost in the inference process required to predict new samples. Lately, several approaches have been proposed to overcome this issue, including beam search and an -Approximate algorithm based on uniform-cost search. Surprisingly, the obvious possibility of using heuristic search has not been considered yet. This paper studies this alternative and proposes an admisible heuristic that, applied in combination with A* algorithm, guarantees, not only optimal predictions in terms of subset 0/1 loss, but also that it always explores less nodes than -Approximate algorithm. In the experiments reported, the number of nodes explored by our method is less than two times the number of labels for all datasets analyzed. But, the difference in explored nodes must be large enough to compensate the overhead of the heuristic in order to improve prediction time. Thus, our proposal may be a good choice for complex multi-label problems

Probabilistic Classifiers Chains (PCC) offers interesting properties to solve multi-label classification tasks due to its ability to estimate the joint probability of the labels. However, PCC presents the major drawback of having a high computational cost in the inference process required to predict new samples. Lately, several approaches have been proposed to overcome this issue, including beam search and an -Approximate algorithm based on uniform-cost search. Surprisingly, the obvious possibility of using heuristic search has not been considered yet. This paper studies this alternative and proposes an admisible heuristic that, applied in combination with A* algorithm, guarantees, not only optimal predictions in terms of subset 0/1 loss, but also that it always explores less nodes than -Approximate algorithm. In the experiments reported, the number of nodes explored by our method is less than two times the number of labels for all datasets analyzed. But, the difference in explored nodes must be large enough to compensate the overhead of the heuristic in order to improve prediction time. Thus, our proposal may be a good choice for complex multi-label problems

Description:

IJCAI-15, Buenos Aires, Argentina, 25–31 de julio de 2015

URI:
http://hdl.handle.net/10651/35763
ISBN:
978-1-57735-738-4
Patrocinado por:

Research supported by MINECO, grant TIN2011-23558

Id. Proyecto:

MEC/TIN2011-23558

Collections
  • Capítulos de libros [5376]
  • Informática [605]
  • Investigaciones y Documentos OpenAIRE [6092]
Files in this item
Thumbnail
untranslated
Postprint (448.4Kb)
Compartir
Exportar a Mendeley
Estadísticas de uso
Estadísticas de uso
Metadata
Show full item record
Página principal Uniovi

Biblioteca

Contacto

Facebook Universidad de OviedoTwitter Universidad de Oviedo
The content of the Repository, unless otherwise specified, is protected with a Creative Commons license: Attribution-Non Commercial-No Derivatives 4.0 Internacional
Creative Commons Image