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

Content Provider	Springer Nature Link
Author	Mena, Deiner Montañés, Elena Quevedo, José Ramón Coz, Juan José
Copyright Year	2016
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.
Starting Page	143
Ending Page	169
Page Count	27
File Format	PDF
ISSN	08856125
Journal	Machine Learning
Volume Number	106
Issue Number	1
e-ISSN	15730565
Language	English
Publisher	Springer US
Publisher Date	2016-09-26
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multi-label classification Probabilistic classifier chains Inference A* Admissible heuristics Artificial Intelligence (incl. Robotics) Control, Robotics, Mechatronics Computing Methodologies Simulation and Modeling Language Translation and Linguistics
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Classifier chains for multi-label classification

Scalable and efficient multi-label classification for evolving data streams

On label dependence and loss minimization in multi-label classification

Learning rules for multi-label classification: a stacking and a separate-and-conquer approach

Multi-label classification via multi-target regression on data streams

Asymptotic analysis of estimators on multi-label data

Statistical topic models for multi-label document classification

Multi-stage classifier design

Learning multi-linear representations of distributions for efficient inference

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

Similar Documents

Classifier chains for multi-label classification

Scalable and efficient multi-label classification for evolving data streams

On label dependence and loss minimization in multi-label classification

Learning rules for multi-label classification: a stacking and a separate-and-conquer approach

Multi-label classification via multi-target regression on data streams

Asymptotic analysis of estimators on multi-label data

Statistical topic models for multi-label document classification

Multi-stage classifier design

Learning multi-linear representations of distributions for efficient inference

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