A family of admissible heuristics for A* to perform inference in probabilistic classifier chains.
Saved in:
| 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, Elena1 elena@aic.uniovi.es, Quevedo, José1 quevedo@aic.uniovi.es, Coz, Juan1 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 120548737 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A family of admissible heuristics for A* to perform inference in probabilistic classifier chains. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Mena%2C+Deiner%22">Mena, Deiner</searchLink><i> deiner.mena@utch.edu.co</i><br /><searchLink fieldCode="AR" term="%22Montañés%2C+Elena%22">Montañés, Elena</searchLink><relatesTo>1</relatesTo><i> elena@aic.uniovi.es</i><br /><searchLink fieldCode="AR" term="%22Quevedo%2C+José%22">Quevedo, José</searchLink><relatesTo>1</relatesTo><i> quevedo@aic.uniovi.es</i><br /><searchLink fieldCode="AR" term="%22Coz%2C+Juan%22">Coz, Juan</searchLink><relatesTo>1</relatesTo><i> juanjo@aic.uniovi.es</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Machine+Learning%22">Machine Learning</searchLink>. Jan2017, Vol. 106 Issue 1, p143-169. 27p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Heuristic%22">Heuristic</searchLink><br /><searchLink fieldCode="DE" term="%22Probabilistic+inference%22">Probabilistic inference</searchLink><br /><searchLink fieldCode="DE" term="%22Monte+Carlo+method%22">Monte Carlo method</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Parameters+%28Statistics%29%22">Parameters (Statistics)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=120548737 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10994-016-5593-5 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 27 StartPage: 143 Subjects: – SubjectFull: Heuristic Type: general – SubjectFull: Probabilistic inference Type: general – SubjectFull: Monte Carlo method Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Parameters (Statistics) Type: general Titles: – TitleFull: A family of admissible heuristics for A* to perform inference in probabilistic classifier chains. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Mena, Deiner – PersonEntity: Name: NameFull: Montañés, Elena – PersonEntity: Name: NameFull: Quevedo, José – PersonEntity: Name: NameFull: Coz, Juan IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: Jan2017 Type: published Y: 2017 Identifiers: – Type: issn-print Value: 08856125 Numbering: – Type: volume Value: 106 – Type: issue Value: 1 Titles: – TitleFull: Machine Learning Type: main |
| ResultId | 1 |
