DAG-based decomposition of multi-class problems

In words...

The one-versus-one decomposition method transforms a multi-class classification problem into a set of binary binary classification problems whose number of classifiers grows quadratically with the number of classes.

In order to make predictions faster, a directed acyclic graph (DAG) can be constructed, in which each node is a binary classifier with two outgoing branches. To predict the label of a new input pattern, we start by computing the output of the classifier at the root node and branch to another lower-level node depending on this output. Arriving at this node, we take for granted the information given by the previous node regarding the class that the input pattern does not belong to, and go on down the tree until we reach a leaf with a label.

In pictures...

Let us build a DAG to predict whether an image represents an apple, a banana, a kiwi or a lemon. STEP BY STEP...

In maths...