# 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...