A family of admissible heuristics for A* to perform inference in probabilistic classifier chains.

Saved in:

Bibliographic Details
Title:	A family of admissible heuristics for A* to perform inference in probabilistic classifier chains.
Authors:	Mena, Deiner deiner.mena@utch.edu.co, Montañés, Elena¹ elena@aic.uniovi.es, Quevedo, José¹ quevedo@aic.uniovi.es, Coz, Juan¹ juanjo@aic.uniovi.es
Source:	Machine Learning. Jan2017, Vol. 106 Issue 1, p143-169. 27p.
Subjects:	Heuristic, Probabilistic inference, Monte Carlo method, Algorithms, Parameters (Statistics)
Abstract:	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 $$\epsilon $$ -approximate algorithm, beam search and Monte Carlo sampling are appropriate techniques, but only $$\epsilon $$ -approximate algorithm with $$\epsilon =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 $$\epsilon $$ -approximate algorithm with $$\epsilon =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 $$\epsilon $$ -approximate algorithm with $$\epsilon =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. [ABSTRACT FROM AUTHOR]
	Copyright of Machine Learning is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	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 $$\epsilon $$ -approximate algorithm, beam search and Monte Carlo sampling are appropriate techniques, but only $$\epsilon $$ -approximate algorithm with $$\epsilon =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 $$\epsilon $$ -approximate algorithm with $$\epsilon =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 $$\epsilon $$ -approximate algorithm with $$\epsilon =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. [ABSTRACT FROM AUTHOR]
ISSN:	08856125
DOI:	10.1007/s10994-016-5593-5