Home
This Title All WIREs
WIREs RSS Feed
How to cite this WIREs title:
WIREs Data Mining Knowl Discov
Impact Factor: 2.111

An overview of inference methods in probabilistic classifier chains for multilabel classification

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

This study presents a review of the recent advances in performing inference in probabilistic classifier chains for multilabel classification. The interest of performing such inference arises in an attempt of improving the performance of the approach based on greedy search (the well‐known CC method) and simultaneously reducing the computational cost of an exhaustive search (the well‐known PCC method). Unlike PCC and as CC, inference techniques do not explore all the possible solutions, but they increase the performance of CC, sometimes reaching the optimal solution in terms of subset 0/1 loss, as PCC does. The ε‐approximate algorithm, the method based on a beam search and Monte Carlo sampling are those techniques. An exhaustive set of experiments over a wide range of datasets are performed to analyze not only to which extent these techniques tend to produce optimal solutions, otherwise also to study their computational cost, both in terms of solutions explored and execution time. Only ε‐approximate algorithm with ε=.0 theoretically guarantees reaching an optimal solution in terms of subset 0/1 loss. However, the other algorithms provide solutions close to an optimal solution, despite the fact they do not guarantee to reach an optimal solution. The ε‐approximate algorithm is the most promising to balance the performance in terms of subset 0/1 loss against the number of solutions explored and execution time. The value of ε determines a degree to which one prefers to guarantee to reach an optimal solution at the expense of increasing the computational cost. WIREs Data Mining Knowl Discov 2016, 6:215–230. doi: 10.1002/widm.1185

A generic node and its children of the probability binary tree. The top part of each node contains the combination of labels and the bottom part includes the joint probability of such combination. The edges are labeled with the conditional probability.
[ Normal View | Magnified View ]
An example of one observation drawn using Monte Carlo sampling. In each node v, a biased coin is flipped to decide whether the label is relevant or not. The probability of tails and heads are given, respectively, by the weights π(lc(v)) and π(rc(v)) of the left and right child of a node v. If the random number is lower or equal than π(lc(v)) then the left child is selected and the label is irrelevant; the right child is selected otherwise. One observation of the conditional distribution is obtained when a leaf is reached.
[ Normal View | Magnified View ]
An example of paths followed by an instance using Beam Search (BS) with b = 2. The cross out nodes with a cross mean that this node has not any of the highest marginal joint conditional probabilities and, hence, it is not explored anymore. The dotted arrows show the path followed by the algorithm.
[ Normal View | Magnified View ]
Several examples of the paths followed by ε‐A algorithm for different values of ε. The nodes with a cross are those that have a marginal joint conditional probability lower than ε and, hence, they are not explored anymore. The dotted arrows show the path followed by the algorithm. The solid arrows indicate the path followed by the algorithm when the marginal joint conditional probability does not exceed the value of ε, and, hence a GS is applied to this node from here to the bottom of the tree. (a) ε‐A algorithm with ε=.0(k = m), (b) ε‐A algorithm with ε=.5(k = 1), (c) ε‐A algorithm with ε=.25(k = 2).
[ Normal View | Magnified View ]
An example of paths followed by an instance using Greedy Search (CC). The dotted arrows show the path followed by the algorithm. (a) Greedy Search (CC) and (b) Exhaustive Search (PCC).
[ Normal View | Magnified View ]

Browse by Topic

Technologies > Classification
Technologies > Machine Learning

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts