English español

Repositorio de la Universidad de Oviedo > Producción Bibliográfica de UniOvi: RECOPILA > Artículos >

Use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10651/40518

Título : A family of admissible heuristics for A* to perform inference in probabilistic classifier chains
Autor(es) y otros: Mena Waldo, Deiner
Montañés Roces, Elena
Quevedo Pérez, José Ramón
Coz Velasco, Juan José del
Palabras clave: Multi-label classification
Probabilistic classifier chains
Inference A*
Admissible heuristics
Fecha de publicación : 2017
Editorial : Springer
Versión del editor: http://dx.doi.org/10.1007/s10994-016-5593-5
Citación : Machine Learning, 106(1), p. 143-169 (2017); doi:10.1007/s10994-016-5593-5
Descripción física: p. 143-169
Resumen : Probabilistic classifier chains have recently gained interest in multi-label classification, due to their ability to optimally estimate the joint probability of a set of labels. The main hindrance is the excessive computational cost of performing inference in the prediction stage. This pitfall has opened the door to propose efficient inference alternatives that avoid exploring all the possible solutions. The ϵϵ -approximate algorithm, beam search and Monte Carlo sampling are appropriate techniques, but only ϵϵ -approximate algorithm with ϵ=0ϵ=0 theoretically guarantees reaching an optimal solution in terms of subset 0/1 loss. This paper offers another alternative based on heuristic search that keeps such optimality. It consists of applying the A* algorithm providing an admissible heuristic able to explore fewer nodes than the ϵϵ -approximate algorithm with ϵ=0ϵ=0 . A preliminary study has already coped with this goal, but at the expense of the high computational time of evaluating the heuristic and only for linear models. In this paper, we propose a family of heuristics defined by a parameter that controls the trade-off between the number of nodes explored and the cost of computing the heuristic. Besides, a certain value of the parameter provides a method that is also suitable for the non-linear case. The experiments reported over several benchmark datasets show that the number of nodes explored remains quite steady for different values of the parameter, although the time considerably increases for high values. Hence, low values of the parameter give heuristics that theoretically guarantee exploring fewer nodes than the ϵϵ -approximate algorithm with ϵ=0ϵ=0 and show competitive computational time. Finally, the results exhibit the good behavior of the A* algorithm using these heuristics in complex situations such as the presence of noise
URI : http://hdl.handle.net/10651/40518
ISSN : 0885-6125
Aparece en las colecciones: Artículos
Investigaciones y Documentos OpenAIRE

Ficheros en este ítem:

Fichero Tamaño Formato
ipcc-versionGreenAccess.pdf1,2 MBAdobe PDFVisualizar/Abrir

Exportar a Mendeley

Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.


Base de Datos de Autoridades Biblioteca Universitaria Consultas / Sugerencias