\RequirePackage{fix-cm}
%
\documentclass{svjour3} % onecolumn (standard format)
%\documentclass[smallcondensed]{svjour3} % onecolumn (ditto)
%\documentclass[smallextended]{svjour3} % onecolumn (second format)
%\documentclass[twocolumn]{svjour3} % twocolumn
%
\smartqed % flush right qed marks, e.g. at end of proof
%
\usepackage{graphicx}
\usepackage{natbib}
\usepackage{url}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}

\newcommand{\hsc}{\textsc{CLUS-HSC}}
\newcommand{\hmc}{\textsc{CLUS-HMC}}
\newcommand{\hmcens}{\textsc{CLUS-ENS-HMC}}
\newcommand{\hscens}{\textsc{CLUS-ENS-HSC}}
\newcommand{\mtens}{\textsc{CLUS-ENS-MT}}
\newcommand{\stens}{\textsc{CLUS-ENS-ST}}
\newcommand{\mtdt}{\textsc{CLUS-MTDT}}
\newcommand{\stdt}{\textsc{CLUS-STDT}}
\newcommand{\clus}{\textsc{CLUS}}
\newcommand{\clusbs}{\textsc{CLUS-BS}}
\newcommand{\clusbss}{\textsc{CLUS-BS-S}}
\newcommand{\hmctask}{\textsc{HMC}}
\newcommand{\hsctask}{\textsc{HSC}}


\pdfpagesattr{/CropBox [20 150 475 800]} 

%
% \usepackage{mathptmx} % use Times fonts if available on your TeX system
%
% insert here the call for the packages your document requires
%\usepackage{latexsym}
% etc.
%
% please place your own definitions here and don't use \def but
% \newcommand{}{}
%
% Insert the name of "your journal" with
\journalname{Data Mining and Knowledge Discovery}
%
\begin{document}

\title{Ensembles for Predicting Structured Outputs%\thanks{Grants or other notes
%about the article that should go on the front page should be
%placed here. General acknowledgments should be placed at the end of the article.}
}

%\titlerunning{Short form of title} % if too long for running head

\author{Dragi Kocev \and Celine Vens \and Jan Struyf \and Sa\v{s}o D\v{z}eroski}

\authorrunning{Kocev et al.} % if too long for running head

\institute{Dragi Kocev \at
 Department of Knowledge technologies, Jo\v{z}ef Stefan Institute, Jamova cesta 39, 1000 Ljubljana, Slovenia \\
 Tel.: +386-1-4773639\\
 Fax: +386-1-4773315\\
 \email{Dragi.Kocev@ijs.si} % \\
% \emph{Present address:} of F. Author % if needed
 \and
 Celine Vens \at
 Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3001 Leuven, Belgium\\
 \email{Celine.Vens@cs.kuleuven.be} 
 \and
 Jan Struyf \at
 Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3001 Leuven, Belgium\\
 \email{Jan.Struyf@cs.kuleuven.be} 
 \and
	 Sa\v{s}o D\v{z}eroski \at
 Department of Knowledge technologies, Jo\v{z}ef Stefan Institute, Jamova cesta 39, 1000 Ljubljana, Slovenia \\
 \email{Saso.Dzeroski@ijs.si} % \\
}

\date{Received: date / Accepted: date}
% The correct dates will be entered by the editor


\maketitle

\begin{abstract}

We present an extensive experimental comparison of decision tree ensembles in the context of structured output learning. More precisely, we compare ensemble learners that predict the complete output structure at once to a collection of ensembles that each predicts a component of the output. The main results are that the difference in predictive performance is not significantly different for both approaches. However, in terms of total model size and induction times, ensembles that exploit the output structure are significantly more efficient.

\keywords{ensembles \and predictive clustering trees \and structured outputs}
% \PACS{PACS code1 \and PACS code2 \and more}
% \subclass{MSC code1 \and MSC code2 \and more}
\end{abstract}

\section{Introduction}\label{secintro}
Supervised learning is one of the most widely researched and investigated areas of machine learning. The goal in supervised learning is to learn, from a set of examples with known class, a function that outputs a prediction for the class of a previously unseen example. If the examples belong to two classes (e.g., the example has some property or not) the task is called binary classification. The task where the examples can belong to a single class from a given set of $m$ classes ($m \geq 3$) is known as multi-class classification. The case where the output is a real value, is called regression.

However, in many real life problems of predictive modelling, the output (i.e., the target property) is structured, meaning that there can be dependencies between classes (e.g., classes are organized into a tree-shaped hierarchy or a directed acyclic graph) or some internal relations between the classes (e.g., sequences). These types of problems occur in domains such as life sciences (predicting the gene function, selecting the most important genes for a given disease, detecting toxic molecules, etc), ecology (analysis of remotely sensed data, habitat modelling), multimedia (annotation and retrieval of images and videos) and the semantic web (categorization and analysis of text and web). Having in mind the needs of the application domains and the increasing quantities of structured data, \citet{Yang06:jrnl} and \citet{Kriegel07:jrnl} listed the task of ``mining complex knowledge from complex data'' as one of the most challenging problems in machine learning. 

A variety of methods, specialized in predicting a given type of structured output (e.g., a hierarchy of classes \citep{Silla11:jrnl}), have been proposed \citep{Bakir07:book}. These methods can be categorized into two groups of methods for solving the problem of predicting structured outputs \citep{Bakir07:book, Silla11:jrnl}: (1) methods that predict component(s) of the output and then combine the individual models to get the global model and (2) methods that predict the complete structure as a whole (also known as `big-bang' approach). The latter group of methods has several advantages over the former. They exploit and use the dependencies that exist between the components of the structured output in the model learning phase and it results in better predictive performance. Next, they are more efficient: it can easily happen that the number of components in the output is very large (e.g., hierarchies in functional genomics), in which case executing a basic method for each component is not feasible. Furthermore, they produce models that are typically smaller than the sum of the sizes of the models for the components. 

The predictive models that we consider in this article are predictive clustering trees (PCTs). PCTs belong to the group og global methods. PCTs offer a unifying approach for dealing with different types of structured outputs and construct the predictive models very efficiently. They are able to make predictions for several types of structured outputs: tuples of continuous/discrete variables, hierarchies of classes, and time series. More details about the PCT framework can be found in \citep{Blockeel98:proc, Struyf06:proc, Kocev07b:proc, Vens08:jrnl, Slavkov10:jrnl}. 

To further increase the predictive performance of a single predictive model, one can construct an ensemble of predictive models. For the simple classification and regression tasks, it is widely accepted that an ensemble of predictive models lifts the predictive performance of its base predictive models \citep{Seni10:book}. However, for the task of predicting structured outputs whether we use the predictive clustering framework or other global predictive models, this is not that obvious. 

In the case when the base predictive models are decision trees, \citet{Bauer99:jrnl} conclude that the increase in performance is related to the trees being unpruned, i.e., overfitting. On the other hand, \citet{Blockeel06:proc} state that predictive clustering trees overfit less than the trees for classification of a single target variable. Having in mind these two conflicting influences, it is not obvious whether an ensemble of predictive clustering trees can significantly increase the predictive performance over that of a single predictive clustering tree. Furthermore, in an ensemble learning setting, it is not clear if the predictive performance of an ensemble of global predictive models will be better or worse than the predictive performance of ensembles of local predictive models when an ensemble is constructed for each component of the structured output. It is not also clear which method will be more efficient, both in terms of running time and size of the predictive models.

In this article, we investigate the aforementioned questions. We use bagging and random forests as ensemble learning methods, since they are the two most widely used ensemble learning methods in the context of decision trees. We consider two machine learning tasks: predicting multiple target variables and hierarchical multi-label classification. We perform extensive empirical evaluation of the proposed methods over a variety of benchmark datasets.

The remainder of this paper is organized as follows. In Section~\ref{sec:Background}, the considered machine learning tasks are formally defined and the related work is presented. Section~\ref{sec:Methodology} explains first the predictive clustering trees framework and the extensions for predicting multiple targets and hierarchical multi-label classification and then the ensemble methods and their extension for predicting structured outputs. The design of the experiments, the descriptions of the datasets, the evaluation measures and the parameter instantiations for the algorithms are given in Section~\ref{sec:exp}. Section~\ref{sec:res} presents and discusses the obtained results. Finally, the conclusions are stated in Section~\ref{sec:conc}.

\section{Background}\label{sec:Background}

The work presented in this article concerns the learning of ensembles for predicting structured outputs. In this section, we first define the machine learning tasks that we consider: the tasks of predicting multiple targets and hierarchical multi-label classification. We then give a brief overview of methods for predicting structured outputs.

\subsection{Machine learning tasks} \label{sec:MLtasks}

First, we formally describe the machine learning tasks that we consider here. We follow the suggestions by \citet{Dzeroski07b:proc}, where predictive modelling is defined for arbitrary types of input and output data. In particular, we describe the tasks of predicting multiple targets and hierarchical multi-label classification.

\subsubsection{Predicting multiple targets task}

The task of predicting multiple targets was previously referred to as multi-objective prediction \citep{Struyf06:proc,Kocev07b:proc, Demsar06:jrnl}. However, the term `multi-objective' is already established in the area of optimization. We will thus use the term `predicting multiple targets' or multi-target prediction (resp. multi-target classification and regression). We define the task of predicting multiple targets as follows.\\

\noindent{\bf Given:}
\begin{itemize}
 \item {A description space $X$ that consists of tuples of values of primitive data types (boolean, discrete or continuous), i.e., $\forall X_{i} \in X, X_{i} = (x_{i_{1}},x_{i_{2}}, ...,x_{i_{D}})$, where $D$ is the size of the tuple (or number of descriptive variables),}
 \item {a target space $Y$ which is a tuple of several variables that can be either continuous or discrete, i.e., $\forall Y_{i} \in Y, Y_{i} = (y_{i_{1}},y_{i_{2}}, ...,y_{i_{T}})$, where $T$ is the size of the tuple (i.e., number of target variables),}
 \item {a set of examples $E$, where each example is a pair of tuples from the description and target space, respectively, i.e., $E = \{(X_{i}, Y_{i}) | X_{i} \in X, Y_{i} \in Y, 1 \leq i \leq N \}$ and $N$ is the number of examples of $E$ ($N = |E|$), and}
 \item {a quality criterion $q$, which rewards models with high predictive accuracy and low complexity.}
\end{itemize}

\noindent{\bf Find:} a function $f:X \rightarrow Y$ such that $f$ maximizes $q$. 

Here, the function $f$ is represented with decision trees, i.e., predictive clustering trees or ensembles thereof. If the tuples from $Y$ (the target space) consist of continuous/numeric variables then the task at hand is multiple targets regression. Likewise, if the tuples from $Y$ consist of discrete/nominal variables then the task is called multiple targets classification.

\subsubsection{Hierarchical classification task}
Classification is defined as the task of learning a model using a set of previously classified instances and applying the obtained model to a set of previously unseen examples \citep{Breiman84:book,Langley96:book}. The unseen examples are classified into a single class from a set of possible classes. 

Hierarchical classification differs from the traditional classification in the following: the classes are organized in a hierarchy. An example that belongs to a given class automatically belongs to all its super-classes (this is known as the {\it hierarchy constraint}). Furthermore, an example can belong simultaneously to multiple classes that can follow multiple paths from the root class. This task is then called hierarchical multi-label classification ({\hmctask}) \citep{Silla11:jrnl, Vens08:jrnl}. 

We formally define the task of hierarchical multi-label classification as follows:\\
\noindent{\bf Given:}
\begin{itemize}
 \item {A description space $X$ that consists of tuples of values of primitive data types (boolean, discrete or continuous), i.e., $\forall X_{i} \in X, X_{i} = (x_{i_{1}},x_{i_{2}}, ...,x_{i_{D}})$, where $D$ is the size of the tuple (or number of descriptive variables),}
 \item {a target space $S$, defined with a class hierarchy $(C, \leq_{h})$, where $C$ is a set of classes and $\leq_{h}$ is a partial order (structured as a rooted tree) representing the superclass relationship ($\forall\ c_{1}, c_{2} \in C: c_{1} \leq_{h} c_{2}$ if and only if $c_{1}$ is a superclass of $c_{2}$),}
 \item {a set $E$, where each example is a pair of a tuple and a set from the descriptive and target space respectively, and each set satisfies the hierarchy constraint, i.e., $E = \{(X_{i}, S_{i})| X_{i} \in X, S_{i} \subseteq C, c \in S_{i} \Rightarrow \forall c^\prime \leq_{h} c:c^\prime \in S_{i}, 1 \leq i \leq N \}$ and $N$ is the number of examples of $E$ ($N = |E|$), and }
 \item {a quality criterion $q$, which rewards models with high predictive accuracy and low complexity.}
\end{itemize}

\noindent{\bf Find:} a function $f:X \rightarrow 2^{C}$ (where $2^{C}$ is the power set of $C$) such that $f$ maximizes $q$ and $c \in f(x) \Rightarrow \forall c^\prime \leq_{h} c: c^\prime \in f(x)$, i.e., predictions made by the model satisfy the {\it hierarchy constraint}. In our case, the function $f$ is represented with decision trees, i.e., predictive clustering trees or ensembles thereof. 

\subsection{Related work}\label{sec:relwork}

The task of predicting structured outputs is gaining more and more attention within the machine learning research community \citep{Bakir07:book,Silla11:jrnl}. The community has proposed a number of different methods for addressing this task. However, they are typically ``computationally demanding and ill-suited for dealing with large datasets'' \citep{Bakir07:book}. In this article, we propose a global method for predicting structured outputs that has good predictive performance and is very efficient. We use the predictive clustering framework both for predicting multiple targets and for hierarchical multi-label classification. In the literature, there are mostly methods that solve one of these two tasks. In the remainder of this section, we first present the methods that predict multiple targets and then the methods for hierarchical multi-label classification.

\subsubsection{Methods for multi-target prediction}

The task of predicting multiple targets is connected with the {\it multi-task learning} \citep{Caruana97:jrnl} and {\it learning to learn} \citep{Thrun98:book} paradigms. These paradigms include the task of predicting a variable (continuous or discrete) using multiple input spaces (i.e., biological data for a disease obtained using different technologies); predicting multiple variables from multiple input spaces, and predicting multiple variables from a single input space. Here, we consider the last task. The methods we propose can handle two types of outputs: multiple discrete variables (multi-target classification) and multiple continuous variables (multi-target regression), while most of the approaches from the literature can handle only one type of output.

There is extensive empirical work showing an increase in predictive performance when multiple tasks are learned simultaneously as compared to learning each task separately (for example, see \citep{Baxter00:jrnl, Evgeniou05:jrnl, Caponnetto08:jrnl, Ben-David08:jrnl} and the references therein).

The key for the success of multi-task learning is the {\it relatedness} between the multiple tasks. The notion of relatedness is differently perceived and defined by different researchers. For example, \citet{Ando05:jrnl} assume that all related tasks have some common hidden structure. \citet{Greene07:book} models the relatedness under the assumption of correlation between the noise for the different regression estimates. \citet{Baxter00:jrnl} views the similarity through a model selection criterion, i.e., learning multiple tasks simultaneously is beneficial if the tasks share a common optimal hypothesis space. To this end, a generalized VC-dimension is used for bounding the average empirical error of a set of predictive models over a class of tasks.

We present and categorize the related work along four dimensions: statistics, statistical learning theory, Bayesian theory and kernel learning. In statistics, \citet{Brown80:jrnl} extend the standard ridge regression to multivariate ridge regression, while \citet{Breiman97:jrnl} propose the \textsc{Curds\&Whey} method, where the relations between the task are modeled in a post-processing phase. In statistical learning theory, for handling multiple tasks, an extension of the VC-dimension and the basic generalization bounds for single task learning are proposed by \citet{Baxter00:jrnl} and \citet{Ben-David08:jrnl}.

Most of the work in multi-task learning is done using Bayesian theory \citep{Thrun98:book, Bakker03:jrnl, Wilson07:proc}. In this case, simultaneously with the parameters of the models for each of the tasks, a probabilistic model that captures the relations between the various tasks is being calculated. Most of these approaches use hierarchical Bayesian models.

Finally, there are many approaches for multi-task learning using kernel methods. For example, \citet{Evgeniou05:jrnl} extend the kernel methods to the case of multi-task learning by using a particular type of kernel (multi-task kernel). The regularized multi-task learning then becomes equivalent to single-task learning when such a kernel is used. They show experimentally that the support vector machines with multi-task kernels have significantly better performance than the ones with single-task kernels. For more details on kernel methods and SVMs for multi-task learning, we refer the reader to \citep{Caponnetto08:jrnl, Argyriou08:jrnl, Micchelli04:proc, Cai09:proc} and the references therein.

\subsubsection{Methods for hierarchical multi-label classification}

A number of approaches have been proposed for the task of hierarchical multi-label classification \citep{Bakir07:book}. \citet{Silla11:jrnl} survey and categorize the {\hmctask} methods based on some characteristics and the application domains. The characteristics of the methods they consider as most important are: prediction of single or multiple paths from the hierarchy, the depth of the predicted class, the type of the taxonomy that can be handled (tree or directed acyclic graph) and whether the method is local (constructs a model for each part of the taxonomy) or global (constructs a model for the whole taxonomy). The most prominent application domains for these methods are functional genomics (biology), image classification, text categorization, and genre classification. 

Here, we present and group some existing methods based on the learning technique they use. We group the methods as follows: network based methods, kernel base methods and decision tree based methods. 

\noindent{\bf Network based methods}. The network based approaches predict functions of unannotated genes based on known functions of genes that are nearby in a functional association network or protein-protein interaction network \citep{Chen04:jrnl}. Since the network base approaches are based on label propagation, a number of approaches were proposed to combine predictions of functional networks with those of a predictive model. \citet{Tian08:jrnl}, for instance, use logistic regression to combine predictions made by a functional association network with predictions from a random forest.

\noindent{\bf Kernel based methods}. \citet{Obozinski08:jrnl} present a two-step approach in which SVMs are first learned independently for each class separately (allowing violations of the hierarchy constraint) and are then reconciliated to enforce the hierarchy constraint. Similarly, \citet{Barutcuoglu06:jrnl} use un-thresholded SVMs learned for each class separately and then combine the SVMs by using a Bayesian network so that the predictions are consistent with the hierarchical relationships. \citet{Guan08:jrnl} extend the method by \citet{Barutcuoglu06:jrnl} to an ensemble framework. \citet{Valentini09:proc} also propose a hierarchical ensemble method that uses probabilistic SVMs as base learners. The method combines the predictions by propagating the weighted true path rule both top-down and bottom-up through the hierarchy, which ensures consistency with the hierarchy constraint.

\citet{Rousu06:jrnl} present a more direct method that does not require a second step to make sure that the hierarchy constraint is satisfied. Their approach is based on a large margin method for structured output prediction which defines a joint feature map over the input and the output space. Next, it applies a SVM based techniques to learn the weights of a discriminant function (defined as the dot product of the weights and the joint feature map). \citet{Rousu06:jrnl} propose a suitable joint feature map and an efficient way for computing the argmax of the discriminant function (which is the prediction for a new instance). Furthermore, \citet{Gartner09:jrnl} propose to use counting of super-structures from the output to efficiently calculate (in polynomial time) the argmax of the descriminant function. 

\noindent{\bf Decision tree based methods}. \citet{Clare03:phd} adapts the well-known decision tree algorithm C4.5 \citep{Quinlan93:book} to cope with the issues introduced by the {\hmctask} task. This version of C4.5 (called C4.5H) uses the sum of entropies of the class variables to select the best split. C4.5H predicts classes on several levels of the hierarchy, assigning a larger cost to misclassifications higher up in the hierarchy. The resulting tree is then transformed into a set of rules, and the best rules are selected, based on a significance test on a validation set.

\citet{Geurts06:proc} present a decision tree based approach related to predictive clustering trees. They start from a different definition of variance and then kernelize this variance function. The result is a decision tree induction system that can be applied to structured output prediction using a method similar to the large margin methods mentioned above. Therefore, this system could also be used for {\hmctask} after defining a suitable kernel. To this end, an approach similar to that of \citet{Rousu06:jrnl} could be used.

\citet{Blockeel02:proc, Blockeel06:proc} proposed the idea of using predictive clustering trees \citep{Blockeel98:proc} for {\hmctask} tasks. This work \citep{Blockeel06:proc} presents the first thorough empirical comparison between an {\hmctask} and {\hsctask} decision tree method in the context of tree shaped class hierarchies. \citet{Vens08:jrnl} extend the algorithm towards hierarchies structured as DAGs and show that learning one decision tree for predicting all classes simultaneously outperforms learning one tree per class (even if those trees are built by taking into account the hierarchy). 


\section{Ensembles for predicting structured outputs}\label{sec:Methodology}

In this section, we present the ensemble methods for predicting structured outputs. We begin by presenting the predictive clustering trees and their instantiations for predicting multiple continuous variables, predicting multiple discrete variables, and hierarchical multi-label classification. Next, we describe how ensemble learning methods can be adapted to use predictive clustering trees as base predictive models. Finally, we describe an approach to the prediction of structured outputs that use local predictive models.

\subsection{PCTs for structured outputs}\label{sec:PCTs}

The Predictive Clustering Trees (PCTs) framework sees a decision tree as a hierarchy of clusters: the top-node corresponds to one cluster containing all data, which is recursively partitioned into smaller clusters while moving down the tree. The PCT framework is implemented in the {\clus} system \citep{Blockeel02:jrnl}, which is available for download at \url{http://www.cs.kuleuven.be/~dtai/clus}. 

{\clus} takes as input a set of examples $E=\{(x_i,y_i)| i=1,...N\}$, where each $x_i$ is a vector of attribute values and $y_i$ are values of a structured (output) datatype $T_Y$. In this article, we consider three different classes of datatypes $T_Y$: tuples of discrete values, tuples of real values, and hierarchies. For each type $T_Y$, {\clus} needs two functions to be defined. The prototype function returns a representative structured value given a set of such values. The variance function describes how homogeneous a set of structured values is: It is typically based on a distance function on the space of structured values.

PCTs can be induced with a standard {\it top-down induction of decision trees} (TDIDT) algorithm \citep{Breiman84:book}. The algorithm is presented in Table~\ref{alg:clus}. It takes as input a set of examples ($E$) and outputs a tree. The heuristic ($h$) that is used for selecting the tests ($t$) is the reduction in variance caused by partitioning ($\mathcal{P}$) the instances (see line \ref{alg:icv} of BestTest procedure in Table \ref{alg:clus}). By maximizing the variance reduction the cluster homogeneity is maximized and it improves the predictive performance.

\begin{table}[h!]
\centering
\caption{\label{alg:clus}The top-down induction algorithm for PCTs.}
\begin{tabular} {cc}
\hline

\begin{minipage}[t]{0.4\textwidth}
{\bf procedure} PCT($E$) \textbf{returns} tree
 \begin{algorithmic}[1]
 \State $(t^*,h^*,\mathcal{P}^*) = \mathrm{BestTest}(E)$
 \If{$t^* \neq \mathit{none}$}
 \For{\textbf{each} $E_i \in \mathcal{P^*}$}
 \State $\mathit{tree}_i$ = PCT($E_i$)
 \EndFor
 \State \textbf{return} $\mathrm{node}(t^*,\;\bigcup_i \{\mathit{tree}_i\})$
 \Else
 \State \textbf{return} $\mathrm{leaf}(\mathrm{Prototype}(E))$ %(p'(T))
 \EndIf
 \end{algorithmic}
\end{minipage} &
\begin{minipage}[t]{0.5\textwidth}
{\bf procedure} $\mathrm{BestTest}(E)$
 \begin{algorithmic}[1]
 \State $(t^*,h^*,\mathcal{P}^*) = (\mathit{none},0,\emptyset)$
 \For{\textbf{each} possible test $t$} \label{alg:btest1}
 \State $\mathcal{P} = $ partition induced by $t$ on $E$
 \State $h = \mathit{Var}(E) - \sum_{E_i \in \mathcal{P}} \frac{|E_i|}{|E|} \mathit{Var}(E_i)$ \label{alg:icv}
 \If{$(h > h^*) \land \mathrm{Acceptable}(t,\mathcal{P})$}
 \State $(t^*,h^*,\mathcal{P}^*) = (t,h,\mathcal{P})$ \label{alg:btest2}
 \EndIf
 \EndFor
 \State \textbf{return} $(t^*,h^*,\mathcal{P}^*)$
 \end{algorithmic}
\end{minipage}\\

\hline
\end{tabular}
\end{table}

The main difference between the algorithm for learning PCTs and a standard decision tree learner (for example, see the \textsc{C4.5} algorithm proposed by \citet{Quinlan93:book}) is that the former considers the variance function and the prototype function, that computes a label for each leaf, as parameters that can be instantiated for a given learning task. So far, the PCTs have been instantiated for the following tasks: multiple targets prediction \citep{Struyf06:proc,Kocev07b:proc}, hierarchical-multi label classification \citep{Vens08:jrnl} and prediction of time-series \citep{Slavkov10:jrnl}. In this article, we focus on the first two tasks.


\subsubsection{PCTs for predicting multiple target variables}

PCTs that are able to predict multiple targets simultaneously are called multi-target decision trees (MTDTs). The MTDTs that predict a tuple of continuous variables (regression tasks) are called multi-target regression trees (MTRTs), while the MTDTs that predict a tuple of discrete variables are called multi-target classification trees (MTCTs). The instantiation of the {\clus} system that learns multi-target trees is called {\mtdt}.

%\subsubsection{PCTs for multiple continuous variables}

%An example of a MTRT is shown in Figure~\ref{fig:MTRTexample}. The internal nodes of the tree contain tests on the descriptive variables (in this case, data from a geographical information system) and the leafs store the predictions (in this case, a tuple of indices describing the condition of the vegetation).

The variance and prototype functions for MTRTs are instantiated as follows. The variance is calculated as the sum of the variances of the target variables, i.e., $\mathit{Var}(E) = \sum_{i=1}^T Var(Y_i)$. The variances of the targets are normalized, so each target contributes equally to the overall variance. The prototype function (calculated at each leaf) returns as a prediction the tuple with the mean values of the target variables, calculated by using the training instances that belong to the given leaf.

%\begin{figure}[h!]
%\centering
%\includegraphics[width=\textwidth]{figures/examples/mtrt_tree_ex}
%\caption{\label{fig:MTRTexample}Example of a predictive clustering tree for predicting multiple continuous targets \citep{Kocev09a:jrnl}. Each leaf stores a prediction for the values of a set of indices of the state of indigenous vegetation in Victoria, Australia.}
%\end{figure}

%\subsubsection{PCTs for multiple discrete variables}

%An example of a MTCT is shown in Figure~\ref{fig:MTCTexample}. This MTCT presents a habitat model for 14 bioindicator species \citep{Dzeroski00:jrnl}. The internal nodes of the tree contain tests on the descriptive variables (in this case, chemical parameters of the water samples) and the leafs store the predictions (in this case, which species are encountered and which not in a given water sample).

The variance function for the MTCTs is computed as the sum of the Gini indices of the target variables, i.e., $\mathit{Var}(E) = \sum_{i=1}^T \mathit{Gini(E,Y_i)}$. Furthermore, one can also use the sum of the entropies of class variables as a variance function, i.e., $\mathit{Var}(E) = \sum_{i=1}^T \mathit{Entropy(E,Y_i)}$ (this definition has also been used in the context of multi--label prediction \citep{Clare03:phd}).

%\begin{figure}[h!]
%\centering
%\includegraphics[width=\textwidth]{figures/examples/mtct_tree_ex}
%\caption{\label{fig:MTCTexample}Example of a predictive clustering tree for predicting multiple discrete targets. Each leaf stores a prediction for the presence or absence of each bioindicator species.}
%\end{figure}

The prototype function returns a vector of probabilities that an instance belongs to a given class for each target variable. Using these probabilities, the most probable (majority) class for each target attribute can be calculated. In addition to the two aforementioned instantiations of the variance function for classification problems, the {\clus} system also implements other variance functions, such as reduced error, information gain, gain ratio and the $m$-estimate.

\subsubsection{PCTs for hierarchical multi--label classification}\label{sec:pct_hmlc}

Hierarchical multi-label classification is a variant of classification where a single example may belong to multiple classes at the same time and the classes are organized in a form of hierarchy. An example that belongs to some class $c$ automatically belongs to all super-classes of $c$: This is called the hierarchical constraint. Problems of this kind can be found in many domains including text classification, functional genomics, and object/scene classification. \citet{Silla11:jrnl} give a detailed overview of the possible application areas and the available approaches to {\hmctask}.

\citet{Silla11:jrnl} describe the algorithms for hierarchical classification with a 4-tuple $\left\langle \Delta, \Sigma, \Omega, \Theta \right\rangle $. In this 4-tuple, $\Delta$ indicates whether the algorithm makes predictions for a single or multiple paths in the hierarchy, $\Sigma$ is the depth of the predicted classes, $\Omega$ is the taxonomy structure of the classes that the algorithm can handle, and $\Theta$ is the type of the algorithm (local or global). Using this categorization, the algorithm we present here can be described as follows: 
\begin{itemize}
 \item {$\Delta = $ multiple path prediction: the algorithm can assign multiple paths or predicted classes to each instance.}
 \item {$\Sigma = $ non-mandatory leaf-node prediction: an instance can be labeled with a label at any level of the taxonomy.}
 \item {$\Omega = $ tree or directed acyclic graph: the algorithm can handle both tree-shaped or DAG hierarchies of classes.}
 \item {$\Theta = $ global classifier: the algorithm constructs a single model valid for all classes.}
\end{itemize}


\hmc{} is the instantiation (with the distances and prototypes as defined bellow) of the PCT algorithm for hierarchical classification implemented in the {\clus} system.

%An example of a PCT for {\hmctask} is shown in Figure~\ref{fig:HMC_tree_example}. This PCT is predicting the annotations of medical X-ray images \citep{Dimitrovski08:proc}. The internal nodes of the tree contain tests on the descriptive variables (in this case, descriptors of the images extracted by the edge histogram technique) and the leafs store the predictions/annotations (in this case, classes organized into a tree-shaped hierarchy called IRMA coding scheme \citep{Lehmann03:proc}).

%\begin{figure}[h!]
%\centering
%\includegraphics[width=\textwidth]{figures/examples/hmlc_tree_ex}
%\caption{\label{fig:HMC_tree_example}Example of a predictive clustering tree for hierarchical multi-label classification. Each leaf stores a prediction for the annotations of a given medical X-ray image from the IRMA coding scheme.}
%\end{figure}

%\subsubsection{Instantiation of PCTs for {\hmctask}}
To apply PCTs to the task of hierarchical multi-label classification, the variance and prototype are defined as follows \citep{Vens08:jrnl}. First, the set of labels of each example is represented as a vector with binary components; the $i$'th component of the vector is 1 if the example belongs to class $c_i$ and 0 otherwise. It is easily checked that the arithmetic mean of a set of such vectors contains as $i$'th component the proportion of examples of the set belonging to class $c_i$. 

The variance of a set of examples $E$ is defined as the average squared distance between each example's class vector $(L_{i})$ and the set's mean class vector $(\overline{L})$, i.e., 
\[\mathit{Var}(E) = \frac{1}{|E|} \cdot \sum\limits_{E_{i} \in E} d(L_{i},\overline{L})^2.\]

In the {\hmctask} context, the similarity at higher levels of the hierarchy is more important than the similarity at lower levels. This is reflected in the distance measure used in the above formula, which is a weighted Euclidean distance:
\[d(L_1,L_2) = \sqrt{\sum\limits_{l = 1}^{|L|} w(c_l)\cdot(L_{1,l}-L_{2,l}})^2,\] where $L_{i,l}$ is the $l$'th component of the class vector $L_i$ of an instance $E_i$, $|L|$ is the size of the class vector, and the class weights $w(c)$ decrease with the depth of the class in the hierarchy.
More precisely, $w(c) = \ensuremath{w_0 \cdot\mathrm{avg_j}\ \{w(p_j(c))\}}$, where $p_j(c)$ denotes the $j$'th parent of class $c$ and $0 < w_0 < 1$).

For example, consider the toy class hierarchy shown in Figure~\ref{fig:simple_hier}(a,b), and two data examples: $(X_1,S_1)$ and $(X_2,S_2)$ that belong to the classes $S_1 = \{c_{1},c_{2},c_{2.2}\}$ (boldface in Figure~\ref{fig:simple_hier}(b)) and $S_2 = \{c_{2}\}$, respectively. We use a vector representation with consecutive components representing membership of class $c_{1}$, $c_{2}$, $c_{2.1}$, $c_{2.2}$ and $c_{3}$, in that order (preorder traversal of the tree). The distance is then calculated as follows: 
\[d(S_1,S_2) = d([1,1,0,1,0],[0,1,0,0,0]) = \sqrt{w_0+w_0^2}.\]

\begin{figure}[h!]
\centering
\includegraphics[width=0.95\textwidth]{figures/hier_example}
\caption{\label{fig:simple_hier}Toy examples of hierarchies structured as a tree and a DAG.(a) Class label names contain information about the position in the hierarchy, e.g., $c_{2.1}$ is a subclass of $c_{2}$. (b) The set of classes $\{c_{1},c_{2},c_{2.2}\}$, shown in bold in the hierarchy, represented as a vector. (c) A class hierarchy structured as a DAG. The class $c_{6}$ has two parents: $c_{1}$ and $c_{4}$.}
\end{figure}

Note that our definition of $w(c)$ allows the classes to be structured in a form of directed acyclic graph (DAG). Figure~\ref{fig:simple_hier}(c) depicts an example of a DAG structured hierarchy. When the hierarchy is a DAG, then the depth of a class is not unique: classes do not have a single path from the top-node (for example see class $c_{6}$ in Figure~\ref{fig:simple_hier}(c)). After an extensive experimental evaluation, \citet{Vens08:jrnl} recommend to use as a weight of a given class the average over the depths of all its parents ($w(c) = w_0 \cdot\mathrm{avg_j}\{w(par_j(c))\}$).


%Note that our definition of $w(c)$ allows the classes to be structured in a form of directed acyclic graph (DAG). Figure~\ref{fig:simple_hier}(c) depicts an example of a DAG structured hierarchy. In general case, a DAG hierarchy can have two interpretations: if an example belongs to a given class $c$, it either a) also belongs to all super-classes of $c$, or b) belongs to at least one superclass of $c$. Here, we adapt the first case, i.e., the multiple inheritance interpretation.

%The variance function used for tree-shaped hierarchies uses the weighted Euclidean distance between the class vectors, where the weight of a class depends on its depth in the hierarchy. When the hierarchy is a DAG, then the depth of a class is not unique: classes do not have a single path from the top-node (for example see class $c_{6}$ in Figure~\ref{fig:simple_hier}(c)). To resolve this issue, \citet{Vens08:jrnl} suggest four aggregation schemes of the possible paths from the top-node to a given class: average, maximum, minimum and sum. The aggregation schemes use the observation that $w(c)=w_{0}^{depth(c)}$ can be rewritten as the recursive relation $w(c)=w_{0} \cdot w(par(c))$, with $par(c)$ as the parent class of $c$, and the weights of the top-level classes equal to $w_{0}$. After an extensive experimental evaluation, \citet{Vens08:jrnl} recommend to use the average as aggregation function ($w(c) = w_0 \cdot\mathrm{avg_j}\{w(par_j(c))\}$).

%\subsubsection{Calculation of the prediction}\label{sec:HMC_prediction}

A classification tree stores in a leaf the majority class for that leaf, which will be the tree's prediction for all examples that will arrive in the leaf. In the case of {\hmctask}, an example may have multiple classes, thus the notion of {\it majority class} does not apply in a straightforward manner. Instead, the mean $\bar{L}$ of the class vectors of the examples in the leaf is stored as a prediction. Note that the value for the $i$-th component of $\bar{L}$ can be interpreted as the probability that an example arriving at the given leaf belongs to class $c_i$. 

The prediction for an example that arrives in the leaf can be obtained by applying a user defined threshold $\tau$ on the probability; if the $i$-th component of $\bar{L}$ is above $\tau$ then the examples belong to the class $c_i$. When a PCT is making a prediction it preserves the hierarchy constraint (the predictions comply to the parent child relationships from the hierarchy) if the values for the thresholds $\tau$ are chosen as follows: $\tau_i \leq \tau_j$ whenever $c_i \leq_{h} c_j$ ($c_i$ is ancestor of $c_j$). The threshold $\tau$ is selected depending on the context. The user may set the threshold such that the resulting classifier has high precision at the cost of lower recall or vice versa, to maximize the F-score, to maximize the interpretability or plausibility of the resulting model etc. In this work, we use a threshold-independent measure (precision-recall curves) to evaluate the performance of the {\hmctask} models.


\subsection{Ensembles of PCTs for predicting structured outputs}

An ensemble is a set of predictive models (called base predictive models). In homogeneous ensembles, such as the ones we consider here, the base predictive models are constructed by using the same algorithm. The prediction of an ensemble for a new instance is obtained by combining the predictions of all base predictive models from the ensemble. In this dissertation, we consider ensembles of PCTs for structured prediction. The PCTs in the ensembles are constructed by using bagging and random forests methods that are often used in the context of decision trees. We have adapted these methods to use PCTs.

\subsubsection{Constructing ensembles of PCTs}

A necessary condition for an ensemble to have better predictive performance than any of its individual members, is that the base predictive models are accurate and diverse \citep{Hansen90:jrnl}. An accurate predictive model does better than random guessing on new examples. Two predictive models are diverse if they make different errors on new examples. There are several ways to introduce diversity in a set of base predictive models: by manipulating the training set (by changing the weight of the examples \citep{Breiman96:jrnl,Freund96:proc}, by changing the attribute values of the examples \citep{Breiman01b:jrnl}, by manipulating the feature space \citep{Breiman01a:jrnl, Ho98:jrnl}) and by manipulating the learning algorithm itself \citep{Breiman01a:jrnl, Dietterich00:proc}. 

We have implemented the bagging and random forests methods within the {\clus} system. These two ensemble learning techniques are most widely known and have primarily been used in the context of decision trees. The algorithms of these ensemble learning methods are presented in Table~\ref{alg:rf}. For the random forests method (right in Table~\ref{alg:rf}), the PCT algorithm for structured prediction needed changes: A randomized version of the selection of attributes was implemented, which replaced the standard selection of attributes. 

\subsubsection{Bagging}
Bagging \citep{Breiman96:jrnl} is an ensemble method that constructs the different classifiers by making bootstrap replicates of the training set and using each of these replicates to construct a predictive model (Table~\ref{alg:rf}, left). Each bootstrap sample is obtained by randomly sampling training instances, with replacement, from the original training set, until an equal number of instances as in the training set is obtained. \citet{Breiman96:jrnl} showed that bagging can give substantial gains in predictive performance, when applied to an unstable learner (i.e., a learner for which small changes in the training set result in large changes in the predictions), such as classification and regression tree learners.

\subsubsection{Random forests}
A random forest \citep{Breiman01a:jrnl} is an ensemble of trees, where diversity among the predictors is obtained by using bootstrap replicates as in bagging, and additionally by changing the set of descriptive attributes during learning (Table~\ref{alg:rf}, right). More precisely, at each node in the decision trees, a random subset of the descriptive attributes is taken, and the best attribute is selected from this subset. The number of attributes that are retained is given by a function $f$ of the total number of descriptive attributes $D$ (e.g., $f(D)= 1$, $f(D)= \lfloor \sqrt D +1\rfloor$, $f(D)=\lfloor log_2(D)+1\rfloor$~\ldots). By setting $f(D)=D$, we obtain the bagging procedure. The algorithm for learning a random forest using PCTs as base classifiers is presented in Table \ref{alg:rf}.

\begin{table} [t!]
\caption{\label{alg:rf}The four ensemble induction algorithms: bagging, random forests, random subspaces and bagging of subspaces. Here, $E$ is the set of the training examples, $k$ is the number of trees in the forest, and $f(D)$ is the size of the feature subset that is used to learn the model (for random subspaces and bagging of subspaces) and that is considered at each node during tree construction (for random forests).}
\centering
\vspace*{0.25cm}
\begin{tabular} {cc}
\hline
%\centering
\begin{minipage}[h]{0.45\textwidth}
{\bf procedure} Bagging($E,k$) \newline \textbf{returns} Forest
 \begin{algorithmic}[1]
 \State $F$ = $\emptyset$
 \For{$i = 1 $ {\bf to} $k$}
 \State $E_i$ = $bootstrap(E)$
 \State $T_i$ = $PCT(E_i)$ \label{alg:bag_pct}
 \State $F$ = $F \bigcup T_{i}$
 \EndFor
 \State \textbf{return} $F$
 \end{algorithmic}
\end{minipage} & 
\begin{minipage}[h]{0.45\textwidth}
{\bf procedure} RForest($E,k,f(D)$) \newline \textbf{returns} Forest
 \begin{algorithmic}[1]
 \State $F$ = $\emptyset$
 \For{$i = 1 $ {\bf to} $k$}
 \State $E_i$ = $bootstrap(E)$
 \State $T_i$ = $PCT\_rnd(E_i,f(D))$ \label{alg:rf_pct}
 \State $F$ = $F \bigcup T_{i}$
 \EndFor
 \State \textbf{return} $F$
 \end{algorithmic}
\end{minipage}\\
% \ & \ \\
% \begin{minipage}[h]{7.2cm}
% {\bf procedure} RSubspaces($E,k,f(D)$) \newline \textbf{returns} Forest
% \begin{algorithmic}[1]
% \State $F$ = $\emptyset$
% \For{$i = 1 $ {\bf to} $k$}
% \State $E_i$ = $feature\_space(E,f(D))$
% \State $T_i$ = $PCT(E_i)$ \label{alg:subsp_pct}
% \State $F$ = $F \bigcup T_{i}$
% \EndFor
% \State \textbf{return} $F$
% \end{algorithmic}
% \end{minipage} & 
% \begin{minipage}[h]{7.2cm}
% {\bf procedure} BagSubspaces($E,k,f(D)$) \newline \textbf{returns} Forest
% \begin{algorithmic}[1]
% \State $F$ = $\emptyset$
% \For{$i = 1 $ {\bf to} $k$}
% \State $E_t$ = $bootstrap(E)$
% \State $E_i$ = $feature\_space(E_t,f(D))$
% \State $T_i$ = $PCT(E_i)$ \label{alg:bagsub_pct}
% \State $F$ = $F \bigcup T_{i}$
% \EndFor
% \State \textbf{return} $F$
% \end{algorithmic}
% \end{minipage}\\
\hline
\end{tabular}
\end{table}

% \subsection{Random subspaces}
% 
% The random subspaces method \citep{Ho98:jrnl} creates an ensemble by learning each of the base models on different feature subspaces (Table~\ref{alg:rf}, bottom-left). This method first selects a subset of the descriptive attributes and then learns a base model using the projection of the dataset on these attributes. The number of descriptive attributes that are used to learn the base models is given with a function $f$ of the total number of descriptive attributes $D$ (as for random forests). \citet{Ho98:jrnl} suggests that best results are obtained with $f(D) = \lfloor 0.5 \cdot D + 1\rfloor$. The random subspaces method performs better when the number of descriptive attributes is large and when the number of examples is not small. This method is also more successful when redundant attributes are present. 
% 
% \subsection{Bagging of subspaces}
% 
% The bagging of subspaces method \citep{Panov07:proc} combines bagging and random subspaces. This method is outlined in Table~\ref{alg:rf}, bottom-right, and learns the base models as follows. It generates a training set for a base model by first creating a bootstrap replicate of the whole training set (in a manner similar to bagging) and then by random selection of a subset of the descriptive attributes (in a manner similar to random subspaces). The number of descriptive attributes used to learn the base models are given as a function $f$ of the number of descriptive attributes $D$ (as for random forests and random subspaces): \citet{Panov07:proc} evaluated the method using $f(D) = \lfloor 0.75 \cdot D + 1\rfloor$. The performance of this method is comparable to the performance of random forests when decision trees are used as base models, while it performs statistically significantly better than bagging and random subspaces. Furthermore, this method can use any type of predictive model (such as decision trees, classification rules, etc) as a base model.


\subsubsection{Combining the predictions of individual PCTs}\label{sec:ens_voting}

The prediction of an ensemble for a new instance is obtained by combining the predictions of all the base predictive models from the ensemble. The predictions from the models can be combined by taking the average (for regression tasks) and the majority or probability distribution vote (for classification tasks), as described in \citep{Bauer99:jrnl,Breiman96:jrnl}, or by taking more complex aggregation schemes \citep{Kuncheva04:book}.

We use PCTs as base predictive models for the ensembles for structured outputs. To obtain a prediction from an ensemble for predicting structured outputs, we accordingly extend the voting schemes. For the datasets with multiple continuous targets, as prediction of the ensemble, we take average per target of the predictions of the base classifiers. For the datasets for hierarchical classification we also use the average of the predictions and apply the thresholding described in Section~\ref{sec:pct_hmlc}. We obtain the ensemble predictions for the datasets with multiple discrete targets using probability distribution voting (as suggested by \citet{Bauer99:jrnl}) per target.

\subsection{Local prediction of structured outputs with PCTs and ensembles}\label{sec:pct_local}

The presented structured output learning algorithms ({\mtdt} and {\hmc}) belong to the group of methods known as `big-bang' or global predictive models \citep{Silla11:jrnl, Bakir07:book}. Global predictive models make a single prediction for the entire structured output, i.e., simultaneously predict all of its components. Local predictive models of structured outputs, on the other hand, use a collection of predictive models, each predicting a component of the overall structure that needs to be predicted.

The local predictive models for the task of predicting multiple targets are constructed by learning a predictive model for each of the targets separately. In the task of hierarchical multi-label classification, however, there are four different approaches that can be used: flat classification, local classifiers per level, local classifiers per node, and local classifiers per parent node (see \citep{Silla11:jrnl} for details).

% The first approach, flat classification, constructs a classifier for each leaf node from the hierarchy, typically using the one vs. all strategy. The examples belonging to a given leaf node from the hierarchy are labeled as positive, while the other examples as negative. A binary classifier is then learned using the labeled training set. This procedure is repeated for each leaf node from the hierarchy. In this approach, the classifiers are not aware of the hierarchical dependencies that exist between the classes and they are incapable of making predictions for the non-leaf nodes of the hierarchy.
% 
% The second approach, local classifiers per level, constructs a classifier for each level of the hierarchy. This approach also requires post-processing to solve the class-membership inconsistencies that may appear. It has been used only as a baseline in comparisons by \citet{Clare03:jrnl} and \citet{Costa07:proc}.
% 
% The third approach, local classifiers per node, constructs a classifier for each node from the hierarchy, except the root. This is the most widely used approach by the community. There are several policies for selecting the positive and negative examples that will be used to train the local classifiers (for details, see \citep{Eisner05:proc, Ceci07:jrnl}). 
% 
% The last approach, local classifiers per parent node, constructs a classifier for each non-leaf node from the hierarchy. One can learn a multi-class classifier for each parent node or transform the problem using the one vs. all scheme and then use binary classifiers for each child node (i.e., construct a classifier for each edge in the hierarchy).

\citet{Vens08:jrnl} investigated the performance of the last two approaches with local classifiers over a large collection of datasets from functional genomics. The conclusion of the study was that the last approach (called hierarchical single-label classification - {\hsctask}) performs better in terms of predictive performance, smaller total model size and faster induction times.

In particular, the {\hsc} algorithm by \citet{Vens08:jrnl}, presented in Figure~\ref{fig:hslc}(a), constructs a decision tree classifier for each edge (connecting a class $c$ with a parent class $par(c)$) in the hierarchy, thus creating an architecture of classifiers. The corresponding tree predicts membership to class $c$, using the instances that belong to $par(c)$. The construction of this type of tree uses few instances: only instances labeled with $par(c)$ are used for training. The instances labeled with class $c$ are positive instances, while the ones that are labeled with $par(c)$, but not with $c$ are negative.

\begin{figure}[h!]
\centering
\begin{tabular}{cc}
\includegraphics[width=0.425\textwidth]{figures/hslc_single_tree} & \includegraphics[width=0.425\textwidth]{figures/hslc_ensemble}\\
(a) & (b) \\
\end{tabular}
\caption{An illustration of the hierarchical single-label classification approach used by \citet{Vens08:jrnl}. The local classifiers at each branch from the hierarchy are: (a) decision trees and (b) ensembles of decision trees.}\label{fig:hslc}
\end{figure}


The resulting {\hsctask} tree predicts the conditional probability $P(c|par(c))$. A new instance is predicted by recursive application of the product rule $P(c) = \mathrm{min}_j \;P(c\:|\:par_j(c))\cdot{}P(par_j(c))$ (with $par_j(c)$ denoting the $j$-th parent of $c$ in the case of a DAG), starting from the tree for the top-level class. Again, the probabilities are thresholded to obtain the set of predicted classes. To satisfy the hierarchy constraint, the threshold $\tau$ should be chosen as in the case of {\hmc}. 

In this article, we extend the approach of \citet{Vens08:jrnl} by applying ensembles as local classifiers, instead of single decision trees. The {\hsc} algorithm can be applied to ensemble learning in two ways by constructing: an ensemble of architectures or an architecture of ensembles. The first approach creates the ensemble by creating multiple architectures (as shown in Figure~\ref{fig:hslc}(a)). These multiple architectures can be created on different bootstrap replicates, on different feature spaces, by different local classifiers etc. The second approach is simpler and, instead of a single local classifier (for example a decision tree), uses an ensemble as a classifier at each branch (depicted in Figure~\ref{fig:hslc}(b)). We prefer here the second approach since it is closer to the learning of local classifiers for predicting multiple target variables.

%In Chapter~\ref{chap:Exp}, we will compare global predictive models to collections of local predictive models. Single PCTs for structured prediction (global predictive models) will be compared to collections of PCTs for the components of the output (local predictive models). Ensembles of PCTs (global predictive models) will be compared to collections of PCT ensembles for the components of the output (local predictive models), following the architecture-of-ensembles approach from Figure~\ref{fig:hslc}(b). 



\section{Experimental design}\label{sec:exp}

In this section, we describe the procedure for experimental evaluation of the proposed ensemble methods for predicting structured outputs. First, we state the questions we consider. Next, we present the datasets we use to evaluate the algorithms, and then the evaluation measures we applied. In the last subsection, we give the parameter values used in the algorithms and the statistical tests that we used.

\subsection{Experimental questions}\label{sec:questions}

Given the methodology from Section~\ref{sec:Methodology}, we construct several types of trees and ensembles. First, we construct PCTs that predict components of the structured output: a separate tree for each variable from the target tuple and a separate tree for each hierarchy edge. Second, we learn PCTs that predict the entire structured output simultaneously: a tree for the complete target tuple and a tree for the complete hierarchy. Finally, we construct the ensemble classifiers in the same manner by using both bagging and random forests.

We consider the following questions:
\begin{itemize}
 \item {{\it Predictive performance}: Does the performance of PCTs for structured outputs increases when combined into an ensemble? Can exploitation of the structure of the output lift the predictive performance of an ensemble? }
 \item {{\it Convergence}: Does the performance of the ensembles for structured outputs converge/saturate faster than for ensembles that predict components of the output?}
 \item {{\it Efficiency}: How much can the learning process benefit, in terms of time and memory consumption, from the ensembles for structured outputs as compared to the sets of ensembles that predict components of the structured output?}
\end{itemize}

We compare the algorithms that predict the complete structured output with the algorithms that predict the components of the structured outputs separately. First, we inspect the predictive performance of all algorithms. Next, we focus only on the ensembles and examine their predictive performance at different ensemble sizes (i.e., we construct saturation curves). Our intention is to investigate whether the performance of the ensembles for structured outputs saturates at a smaller number of trees as compared to the saturation of ensembles predicting the components of the structured output. At the end, we compare the running times and the sizes of the obtained models.

\subsection{Descriptions of the datasets}

In this section, we present the datasets that were used to evaluate the predictive performance of the ensembles. The datasets are divided into three groups based on the type of their output: multiple continuous targets datasets (regression), multiple discrete targets datasets (classification) and hierarchical multi-label classification datasets ({\hmctask}). Statistics about the used datasets are presented in Tables~\ref{tab:regdata}, \ref{tab:classdata}, and \ref{tab:hmlcdata}, respectively.

\begin{table}[h!]
\caption{\label{tab:regdata}Properties of the datasets with multiple continuous targets (regression datasets); $N$ is the number of instances, $\overline{D/C}$ the number of descriptive attributes (discrete/continuous), and $T$ the number of target attributes.}
\centering
\bigskip
\begin{tabular}{lrrr} 
\hline
 Name of dataset & $N$ & $\overline{D/C}$& $T$\\
\hline
Collembola \citep{Kampichler00:jrnl} & 393 & 8/39 & 3 \\
EDM \citep{Karalic95:phd} & 154 & 0/16 & 2 \\
Forestry-Kras \citep{Stojanova10:jrnl} & 60607 & 0/160 & 11 \\
Forestry-Slivnica-LandSat \citep{Stojanova09:msc} & 6218 & 0/150 & 2 \\
Forestry-Slivnica-IRS \citep{Stojanova09:msc} & 2731 & 0/29 & 2 \\
Forestry-Slivnica-SPOT \citep{Stojanova09:msc} & 2731 & 0/49 & 2 \\
Sigmea real \citep{Demsar05:proc} & 817 & 0/4 & 2 \\
Soil quality \citep{Demsar06:jrnl} & 1944 & 0/142 & 3 \\
Solar-flare 1 \citep{Asuncion07:misc} & 323 & 10/0 & 3 \\
Solar-flare 2 \citep{Asuncion07:misc} & 1066 & 10/0 & 3 \\
Vegetation Clustering \citep{Gjorgjioski08:tech} & 29679 & 0/65 & 11 \\
Vegetation Condition \citep{Kocev09a:jrnl} & 16967 & 1/39 & 7 \\
Water quality \citep{Blockeel99:proc,Dzeroski00:jrnl} & 1060 & 0/16 & 14 \\ 
\hline
\end{tabular}
\end{table}

\begin{table}[h!]
\caption{\label{tab:classdata}Properties of the datasets with multiple discrete targets (classification datasets); $N$ is the number of instances, $\overline{D/C}$ the number of descriptive attributes (discrete/continuous), and $T$ the number of target attributes.}
\centering
\bigskip
\begin{tabular}{lrrr} 
\hline
 Name of dataset & $N$ & $\overline{D/C}$& $T$\\
\hline
EDM \citep{Karalic95:phd} & 154 & 0/16 & 2 \\
Emotions \citep{Trohidis08:proc} & 593 & 0/72 & 6 \\
Mediana \citep{Skrjanc01:jrnl} & 7953 & 21/58 & 5 \\
Scene \citep{Boutell04:jrnl} & 2407 & 0/294 & 6 \\
Sigmea real \citep{Demsar05:proc} & 817 & 0/4 & 2 \\
Solar-flare 1 \citep{Asuncion07:misc} & 323 & 10/0 & 3 \\
Thyroid \citep{Asuncion07:misc} & 9172 & 22/7 & 7 \\
Water quality \citep{Blockeel99:proc,Dzeroski00:jrnl} & 1060 & 0/16 & 14 \\
Yeast \citep{Elisseeff01:proc} & 2417 & 0/103 & 14 \\

\hline
\end{tabular}
\end{table}

\begin{sloppypar}
The datasets with multiple continuous targets (13 in total, see Table~\ref{tab:regdata}) are mainly from the domain of ecological modelling. The datasets with multiple discrete targets (9 in total, see Table~\ref{tab:classdata}) are from various domains: ecological modelling ({\it Sigmea Real} and {\it Water Quality}), biological ({\it Yeast}), multimedia ({\it Scene} and {\it Emotions}) and media space analysis ({\it Mediana}). The datasets that have classes organized in a hierarchy come from various domains, such as: biology ({\it Expression-FunCat, SCOP-GO, Yeast-GO} and {\it Sequence-FunCat}), text classification ({\it Enron, Reuters} and {\it WIPO}) and image annotation/classification ({\it ImCLEF07D, ImCLEF07A} and {\it Diatoms}). Hence, we use 10 datasets from 3 domains (see Table~\ref{tab:hmlcdata}). Note that two datasets from the biological domain have a hierarchy organized as a DAG (they have GO in the dataset name), and the remaining datasets have tree-shaped hierarchies. For more details on the datasets, we refer the reader to the referenced literature.
\end{sloppypar}

\begin{table}[h!]
\caption{\label{tab:hmlcdata}Properties of the datasets with hierarchical targets; $N_{tr}/N_{te}$ is the number of instances in the training/testing dataset, $D/C$ is the number of descriptive attributes (discrete/continuous), $|\mathcal{H}|$ is the number of classes in the hierarchy, $\mathcal{H}_{d}$ is the maximal depth of the classes in the hierarchy, $\overline{\mathcal{L}}$ is the average number of labels per example, and $\overline{\mathcal{L}}_{L}$ is the average number of leaf labels per example.}
\centering
\bigskip
\begin{tabular}{lcccccc} 
\hline
Domain & $N_{tr}/N_{te}$ & $D/C$ & $|\mathcal{H}|$ & $\mathcal{H}_{d}$ & $\overline{\mathcal{L}}$ & $\overline{\mathcal{L}_{L}}$\\
\hline
ImCLEF07D\citep{Dimitrovski08:proc} & 10000/1006 & 0/80 & 46 & 3.0 & 3.0 & 1.0 \\
ImCLEF07A\citep{Dimitrovski08:proc} & 10000/1006 & 0/80 & 96 & 3.0 & 3.0 & 1.0 \\
Diatoms \citep{ADIAC08:www} & 2065/1054 & 0/371 & 377 & 3.0 & 1.95 & 0.94 \\
Enron \citep{Klimt04:proc} & 988/660 & 0/1001 & 54 & 3.0 & 5.30 & 2.84 \\
Reuters \citep{Lewis04:jrnl} & 3000/3000 & 0/47236 & 100 & 4.0 & 3.20 & 1.20 \\
WIPO \citep{Rousu06:jrnl} & 1352/358 & 0/74435 & 183 & 4.0 & 4.0 & 1.0 \\
Expression--FunCat \citep{Clare03:phd} & 2494/1291 & 4/547 & 475 & 4.0 & 8.87 & 2.29 \\
SCOP-GO \citep{Clare03:phd} & 6507/3336 & 0/2003 & 523 & 5.5 & 6.26 & 0.95 \\
Sequence-FunCat \citep{Clare03:phd} & 2455/1264 & 2/4448 & 244 & 4.0 & 3.35 & 0.94 \\
Yeast-GO \citep{Barutcuoglu06:jrnl} & 2310/1155 & 5588/342 & 133 & 6.3 & 5.74 & 0.66 \\
\hline
\end{tabular}
\end{table}


\subsection{Evaluation measures}\label{sec:eval_measures}

Empirical evaluation is the most widely used approach for assessing the performance of machine learning algorithms. The performance of a machine learning algorithm is assessed using some evaluation measure. The different machine learning tasks, described in Section~\ref{sec:MLtasks}, use `task-specific' evaluation measures. We first describe the evaluation measures for multiple continuous targets (regression), then for multiple discrete targets (classification) and at the end for hierarchical classification.

For the task of predicting multiple continuous targets (regression), we employed three well known measures: the correlation coefficient ($CC$), root mean squared error ($RMSE$) and relative root mean squared error ($RRMSE$). For each of these measures, we performed tests for statistical significance and constructed saturation curves. We present here only the results in terms of $RRMSE$, but same conclusions hold for the other two measures.

What evaluation measure to use in the case of classification algorithms is not as clear as in the case of regression. \citet{Sokolova09:jrnl} conducted a systematic analysis of twenty four performance measures that can be used in a classification context. They conclude that evaluation measures for classification algorithms should be chosen based on the application domain.

In our study, we used seven evaluation measures for classification: accuracy, precision, recall, F-score, the Matthews correlation coefficient, balanced accuracy (also known as Area Under the Curve) and discriminant power. We used two averaging approaches to adapt these measures for multi-class problems: micro and macro averaging (note that averaging is not needed for accuracy). Since the goal of this study is not to assess the evaluation measures themselves, we present here only the results in terms of the micro average F-score ($F = 2 \cdot \frac{Precision \cdot Recall}{Precision + Recall}$). However, the conclusions drawn from the evaluation of the performance of the algorithms using the other measures concur with the ones presented here.

In the case of hierarchical classification, we evaluate the algorithms using the Area Under the Precision-Recall Curve ($AUPRC$), and in particular, the Area Under the Average Precision-Recall Curve ($AU\overline{PRC}$) as suggested by \citet{Vens08:jrnl}. A Precision-Recall curve plots the precision of a classifier as a function of its recall. The points in the $PR$ space are obtained by varying the value for the threshold $\tau$ from 0 to 1 with step 0.02. The precision and recall are micro averaged for all classes from the hierarchy.

%In these domains, the positive examples for a given class are only few as compared to the negative ones. The $PR$ evaluation of these algorithms is most suitable in this context because we are more interested in correctly predicting the positive examples (i.e., that an example belongs to a given class), rather than correctly predicting negative instances. 

Finally, we compare the algorithms by measuring their efficiency in terms of time consumption and size of the models. We measure the processor time needed to construct the models: in the case of predicting the components of the structure, we sum the times needed to construct the separate models. In a similar way, we calculated the sizes of the models as the total number of nodes (internal nodes and leafs). The experiments for predicting multiple targets were performed on a server running Linux, with two Intel Quad-Core Processors@2.5GHz and 64GB of RAM. The experiments for the hierarchical classification were run on a cluster of AMD Opteron processors (1.8 -- 2.4GHz, $\geq$ 2GB RAM).

\subsection{Experimental setup}\label{sec:exp_setup}

Here, we first state the parameter values used in the algorithms for constructing the single trees and the ensembles for all types of targets. We then describe how we assessed the statistical significance of the differences in performance of the studied algorithms.

The single trees for all types of outputs are obtained using F-test pruning. This pruning procedure uses the exact Fisher test to check whether a given split/test in an internal node of the tree results in a reduction in variance that is statistically significant at a given significance level. If there is no split/test that can satisfy this, then the node is converted to a leaf. An optimal significance level was selected by using internal 3-fold cross validation, from the following values: 0.125, 0.1, 0.05, 0.01, 0.005 and 0.001.

The construction of an ensemble takes, as an input parameter, the size of the ensemble, i.e., number of base predictive models to be constructed. We constructed ensembles with 10, 25, 50, 75 and 100 base predictive models for all types of outputs and all datasets. In addition, for the datasets with multiple continuous targets we constructed ensembles with 150 and 250 base predictive models, and for the datasets with multiple discrete targets ensembles with 250, 500 and 1000 base predictive models. Following the findings from the study conducted by \citet{Bauer99:jrnl}, the trees in the ensembles were not pruned.

The random forests algorithm takes as input the size of the feature subset that is randomly selected at each node. For the multiple targets datasets, we apply the logarithmic function of the descriptive attributes $\lfloor \log_{2}|D| \rfloor + 1$, which is recommended by \citet{Breiman01a:jrnl}. For the hierarchical classification datasets, we used $\lfloor 0.1 \cdot |D| \rfloor + 1$, since the feature space of some of these datasets is large (several thousands of features) and the logarithmic function is under-sampling the feature space.

On the datasets with multiple targets, the predictive performance of the algorithms is estimated by 10-fold cross-validation. The hierarchical datasets were previously divided (by the data providers) into train and test sets. Thus, we estimate the predictive performance of the algorithms on the test sets. 

We adopt the recommendations by \citet{DemsarJ06:jrnl} for the statistical evaluation of the results. We use the Friedman test \citep{Friedman40:jrnl} for statistical significance with the correction from \citet{Iman80:jrnl}. Afterwards, to check where the statistically significant differences appear (between which algorithms), we use the Nemenyi post-hoc test \citep{Nemenyi63:phd}. We present the results from the statistical analysis with {\it average ranks diagrams}. The diagrams plot the average ranks of the algorithms and connect the ones whose average ranks are smaller than a given value, called critical distance. The critical distance depends on the level of the statistical significance, in our case 0.05. The difference in the performance of the algorithms connected with a line is not statistically significant at the given significance level.

%(see Figures~\ref{fig:mtr_stattest}, \ref{fig:mtr_efficiency},\ref{fig:mtc_stattest}, \ref{fig:mtc_efficiency}, \ref{fig:hmlc_stattest} and \ref{fig:hmlc_efficiency}). 


\section{Results and discussion}\label{sec:res}

The results from the experiments can be analyzed along several dimensions. First, we present the saturation curves of the ensemble methods (both for predicting the structured outputs and the components of the outputs). Then, we compare models that predict the complete structured output vs. models that predict components of the structured output. We thereby also compare single trees vs. ensembles of trees. Last, we evaluate the algorithms by their efficiency in terms of running time and model size. We do these comparisons for each task separately: multiple targets regression, multiple targets classification and hierarchical multi--label classification. We conclude the section with a general discussion.

\subsection{Multi-target regression}

In Figure~\ref{fig:mtr_satcurv}, we present the saturation curves for the ensemble methods for multi-target regression. Although these curves are averaged across all target variables for a given dataset, they still provide useful insight on the performance of the algorithms. Figure~\ref{fig:mtr_satcurv} (a) and (b) present the saturation curves for two specific datasets, while Figure~\ref{fig:mtr_satcurv}~(c) presents averaged curves for all datasets. We have checked at which ensemble size (saturation point) the RRMSE is not longer statistically significantly changed, i.e., when adding trees in the ensemble does not increase the predictive performance significantly. For all algorithms, the difference is not statistically significant with 50 trees are added. Thus, we compare the performance of the algorithms after 50 trees for the rest of the analysis.

\begin{figure}[h!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.31\textwidth]{figures/satcurv/RRMSE_Forestry_Kras_all} & \includegraphics[width=0.31\textwidth]{figures/satcurv/RRMSE_soil_quality_all} & \includegraphics[width=0.31\textwidth]{figures/satcurv/RRMSE_Complete_all} \\
(a) {\it Forestry-Kras} & (b) {\it Soil quality} & (c) {\it Overall} \\
\end{tabular}
\caption{\label{fig:mtr_satcurv}Saturation curves for multi-target regression. These curves are obtained by averaging the $RRMSE$ values for all of the target variables in a dataset. Smaller $RRMSE$ values mean better predictive performance. The algorithm names are abbreviated as follows: random forests for the prediction of multiple targets -- $MTRF$, random forests for the prediction of a single target -- $STRF$, bagging for the prediction of multiple targets -- $MTBag$ and bagging for the prediction of a single target -- $STBag$.}
\end{figure}

The statistical test in Figure~\ref{fig:mtr_stattest} shows that the difference in the predictive performance of the ensemble methods is not statistically significant at the level of 0.05. For most of the datasets, the best performing method is random forests for predicting multiple targets. However, if we look at the saturation curves in Figure~\ref{fig:mtr_satcurv} (c), we note that, on average, multiple targets bagging is best. A closer look at the results learns that, especially for the larger datasets (e.g., {\it Forestry-Kras} from Figure~\ref{fig:mtr_satcurv}(a)), random forests tend to outperform bagging, both for the local and global algorithms. The difference in performance between ensembles and the single PCTs is statistically significant at 0.05. The PCTs for predicting multiple targets simultaneously are better (though not statistically significant) than the trees for predicting the multiple targets separately.

\begin{figure}[h!]
\centering
\includegraphics[width=0.35\textwidth]{figures/stattests/Size50_MTRegression_RRMSE_05}
\caption{\label{fig:mtr_stattest}Average rank diagrams at significance level of 0.05 for multi-target regression. The ensembles contain 50 trees. The difference in the performance of the algorithms connected with a red line are not statistically significant. The numbers after the name of the algorithm indicate its average rank. The abbreviations are same as in Figure~\ref{fig:mtr_satcurv} with addition of predicting clustering tree for multiple continuous targets -- $MTRT$ and predictive clustering tree for single continuous target -- $STRT$.}
\end{figure}

Finally, we compare the algorithms by their running time and the size of the models for ensembles of 50 trees (see Figure \ref{fig:mtr_efficiency}). The statistical tests show that, in terms of time efficiency, random forests for multi-target regression significantly outperform ensemble methods for predicting the targets separately. Also, bagging for multiple targets is significantly faster than bagging for separate prediction of the targets.
In terms of size of models, both random forests and bagging for predicting multiple targets simultaneously outperform significantly the ensembles that predict multiple targets separately. 

\begin{figure}[h!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.35\textwidth]{figures/efficiency/Size50_MTRegression_timings_05} & & \includegraphics[width=0.35\textwidth]{figures/efficiency/Size50_MTRegression_sizes_05} \\
(a) {\it Time efficiency} & \ \ \ \ \ & (b) {\it Size of the models}\\
\end{tabular}
\caption{\label{fig:mtr_efficiency}Efficiency (running time and model size) of the ensembles for prediction of multiple continuous targets. The size of the ensembles is 50 trees.}
\end{figure}


\subsection{Multi-target classification}

%The performance of the algorithms for multi-class classification can be assessed using different measures, some of which we listed in Section~\ref{sec:eval_measures}. The evaluation measure should be selected based on the application domain \citep{Sokolova09:jrnl}. In our study, we used micro weighted averaged F-score ($\mu F-score$): reasonable compromise between all measures, since it combines the precision and the recall values.

%The results for algorithms that predict multiple discrete targets are presented in Figures~\ref{fig:mtc_satcurv}, \ref{fig:mtc_stattest} and \ref{fig:mtc_efficiency}. In Figure~\ref{fig:mtc_satcurv}, we present the saturation curves. Next, we discuss the statistical analysis of the results (Figure~\ref{fig:mtc_stattest}). At the end, we compare the algorithms by their efficiency (Figure~\ref{fig:mtc_efficiency}).

In Figure~\ref{fig:mtc_satcurv}, we present three saturation curves for the ensemble methods for multi-target classification. Same as for multi-target regression, the values for drawing the curves are averaged from all target variables for a given dataset (and in Figure~\ref{fig:mtc_satcurv}(c) averaged across all datasets). In a similar manner as for the multi-target regression, we determined the ensemble size after which the predictive performance is no longer statistically significant. The ensembles for predicting the multiple targets simultaneously saturate with 50 trees added, while the ensembles for separate prediction of the targets require more trees: 75 for the random forests and 250 for bagging. After this, we select ensembles sizes of 50 (Figure~\ref{fig:mtc_stattest})to compare the algorithms. This is in line with the results from the saturation curves which show that ensembles for multi-target classification perform better than the ensembles for single-target classification at smaller ensemble sizes (this can be also noticed in the overall saturation curve shown in Figure~\ref{fig:mtc_satcurv}(c)).

\begin{figure}[h!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.31\textwidth]{figures/satcurv/MIC_F_Sigmeareal-dis_all} & \includegraphics[width=0.31\textwidth]{figures/satcurv/MIC_F_water-quality-nom_all} & \includegraphics[width=0.31\textwidth]{figures/satcurv/MIC_F_Complete_all} \\
(a) {\it Sigmea real} & (b) {\it Water quality} & (c) {\it Overall} \\
\end{tabular}
\caption{\label{fig:mtc_satcurv}Saturation curves for the prediction of multiple discrete targets. These curves are obtained by averaging the $\mu F-score$ values for all of the target variables. Bigger $\mu F-score$ values mean better predictive performance. The algorithm names are abbreviated as follows: random forests for prediction of multiple targets -- $MTRF$, random forests for prediction of single target -- $STRF$, bagging for prediction of multiple targets -- $MTBag$ and bagging for prediction of single target -- $STBag$.}
\end{figure}

The statistical tests reveal that there is no statistically significant difference at the level of 0.05 in the performance of the ensemble methods (Figure~\ref{fig:mtc_stattest}). Bagging for predicting the multiple targets simultaneously is the best performing method (average rank 2.59) and the remaining methods have larger and very close to each other average ranks (ranging from 3.0 to 3.11) with random forest for separate prediction of the targets having the largest average rank. The both types of ensembles (multi-target and single-target classification) perform statistically significantly better than the single PCTs. Furthermore, the single PCTs for multi-target classification perform better (although not statistically significantly) than the PCTs for single-target classification.

\begin{figure}[h!]
\centering
\includegraphics[width=0.35\textwidth]{figures/stattests/Size50_MTClassification_MicAvgF_05} 

\caption{\label{fig:mtc_stattest}Average ranks diagrams at significance level of 0.05 for prediction of multiple discrete targets. The ensembles contain 50 trees. The difference in the performance of the algorithms connected with a red line are not statistically significant. The numbers after the name of the algorithm indicate its average rank. The abbreviations are same as in Figure~\ref{fig:mtc_satcurv} with addition of predicting clustering tree for multiple discrete targets -- $MTCT$ and predictive clustering tree for single discrete target -- $STCT$.}
\end{figure}

Finally, we compare the ensembles by their efficiency: running times (Figure~\ref{fig:mtc_efficiency}(a)) and size of models (Figure~\ref{fig:mtc_efficiency}(b)). Concerning the running time, we can state that the random forests for predicting multiple targets simultaneously significantly outperform the bagging for predicting the multiple targets separately. As for the size of the models, we can note the following: (1) the bagging for predicting multiple targets simultaneously significantly outperforms both ensemble methods for separate prediction of the targets and (2) random forests for predicting multiple targets simultaneously significantly outperform the random forests for separate prediction of the targets.

\begin{figure}[h!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.35\textwidth]{figures/efficiency/Size50_MTClassification_PDVote_timings_new_05} & & \includegraphics[width=0.35\textwidth]{figures/efficiency/Size50_MTClassification_PDVote_sizes_new_05} \\
(a) {\it Time efficiency} & \ \ \ \ \ & (b) {\it Size of the models}\\
\end{tabular}
\caption{\label{fig:mtc_efficiency}Efficiency of the ensembles for prediction of multiple discrete targets. The size of the ensembles is 50 trees.}
\end{figure}


\subsection{Hierarchical multi-label classification}

In this subsection, we compare the performance of ensembles and PCTs for the tasks of {\hmctask} and {\hsctask}. We begin by presenting the saturation curves of the ensemble methods in Figure~\ref{fig:hmlc_satcurv}. Figures~\ref{fig:hmlc_satcurv}(a) and \ref{fig:hmlc_satcurv}(b) show the saturation curves for {\it SCOP-GO} and {\it ImCLEF07D} domains, respectively, while Figure~\ref{fig:hmlc_satcurv}(c) shows the saturation curve averaged across all domains. We determine the ensemble size after which adding trees in the ensemble does not statistically significantly improve ensemble's performance. Both ensembles for {\hmctask} and random forests for {\hsctask} saturate after 50 trees are added in the ensemble, while bagging for {\hsctask} saturates after only 25 trees. We further compare the performance of the ensembles at 50 trees (Figure~\ref{fig:hmlc_stattest}). 

\begin{figure}[h!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.325\textwidth]{figures/satcurv/HMLC_Scop_all} &\includegraphics[width=0.325\textwidth]{figures/satcurv/HMLC_ImageClef_2_all} & \includegraphics[width=0.325\textwidth]{figures/satcurv/HMLC_Complete_all} \\
(a) {\it SCOP-GO} & (b) {\it ImCLEF07D} & (c) {\it Overall}\\
\end{tabular}
\caption{\label{fig:hmlc_satcurv}Saturation curves for hierarchical multi--label classification. These curves are obtained by averaging the $AU\overline{PRC}$ values for all of the target variables. Bigger $AU\overline{PRC}$ values mean better predictive performance. The algorithms are abbreviated as follows: random forests for hierarchical multi--label classification -- $HMLCRF$, random forests for hierarchical single-label classification -- $HSLCRF$, bagging for hierarchical multi--label classification -- $HMLCBag$ and bagging for hierarchical single-label classification -- $HSLCBag$.}
\end{figure}


\begin{figure}[h!]
\centering
\includegraphics[width=0.4\textwidth]{figures/stattests/Size50_HMLC_performance_05} 
\caption{\label{fig:hmlc_stattest}Average ranks diagrams at significance level of 0.05 for hierarchical multi--label classification. The ensembles contain 50 trees. The difference in the performance of the algorithms connected with a red line are not statistically significant. The numbers after the name of the algorithm indicate its average rank. The abbreviations are same as in Figure~\ref{fig:hmlc_satcurv} with addition of predicting clustering tree for hierarchical multi--label classification -- $HMLCPCT$ and predictive clustering tree for hierarchical single--label classification -- $HSLCPCT$.}
\end{figure}

The average ranks diagram for the ensembles with 50 trees (Figure~\ref{fig:hmlc_stattest}) shows that the performance of the ensembles is not statistically significantly different. Note that the best performing method is random forests for {\hsctask} (average rank 2.25) and worst performing method is bagging for {\hsctask} (average rank 2.85). Ensembles for {\hmctask} and {\hsctask} are statistically significantly better than single PCT for {\hmctask} and {\hsctask}. However, if we focus on the overall saturation curve from Figure~\ref{fig:hmlc_satcurv}(c), bagging for {\hmctask} is the best performing method. Moreover, ensembles for {\hmctask} perform better than ensembles for {\hsctask} on the datasets with larger hierarchies (i.e., datasets with $(|\mathcal{H}| > 300)$). 

Finally, we compare the algorithms by their efficiency when they contain 50 trees (running times in Figure~\ref{fig:hmlc_efficiency}(a) and size of the models in Figure~\ref{fig:hmlc_efficiency}(b)). The random forests for {\hmctask} are statistically significantly faster than both bagging for {\hmctask} and {\hsctask}, while random forests for {\hsctask} are significantly faster than bagging for {\hsctask}. The models of bagging of {\hmctask} are statistically significantly smaller than the models from both ensembles for {\hsctask}, while the models of random forests for {\hmctask} are statistically significantly smaller than the models from the random forests for {\hsctask}.


\begin{figure}[h!]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.35\textwidth]{figures/efficiency/Size50_HMLC_timings_05} & & \includegraphics[width=0.35\textwidth]{figures/efficiency/Size50_HMLC_sizes_05} \\
(a) {\it Time efficiency} & \ \ \ \ \ & (b) {\it Size of the models}\\
\end{tabular}
\caption{\label{fig:hmlc_efficiency}Efficiency of the ensembles for hierarchical multi--label classifications. The size of the ensembles is 50 trees.}
\end{figure}





\subsection{Summary of the results}

To summarize the results from the experiments, we discuss some general conclusions by formulating an answer to each of the questions from Section~\ref{sec:questions}. 

\subsubsection{Predictive performance}

%We have observed that, in each of the three learning tasks, the predictive performance of ensembles that exploit the structure in the output is not significantly different (at the 0.05 level) from that of ensembles that focus on a component from the structured output. Also, none of the four considered ensemble algorithms is consistently performing best. However, compared to non-ensemble methods, all ensembles are consistently better. Among the non-ensemble methods, there is also no significant winner considering the predictive performance.

The ensembles for predicting structured outputs (i.e., ensembles of PCTs) lift the predictive performance of a single PCT. The difference in performance is statistically significant at the significance level of 0.05. Previously this was shown only on applications where the target is a single continuous or discrete variable. This finding is valid for all three machine learning tasks that we consider in this article. %This suggests that the non-trivial relations that might exist between the components of the structure are still captured when combining predictions of several classifiers or when injecting randomness in the learning algorithm.

The differences in predictive performances between ensembles of PCTs and ensembles of trees predicting components of the output are not statistically significant at 0.05 in any task. Also, none of the four considered ensemble algorithms is consistently performing best. However, the ensembles of PCTs often have better predictive performance (i.e., smaller average ranks) than the ensembles of trees predicting components of the output.

\subsubsection{Convergence}

We looked at the saturation point of the ensembles' performances with respect to the number of base classifiers. In the majority of the cases, the predictive performance of the ensembles saturates after the 50th tree is added in the ensemble. Exceptions of this are: bagging for {\hsctask} that saturates when 25 trees are added and random forests and bagging for predicting multiple discrete targets separately that saturate after 75 and 250 trees, respectively. Furthermore, the saturation curves offer some insight about the application of a given method on a given dataset (summarized by their number of examples and number of descriptive variables). Also, the curves show that on majority of the datasets the ensembles for predicting the structured outputs as a whole have better performance than the ensembles that predict the components. This is especially the case when the ensembles contain fewer trees.

\subsubsection{Efficiency}

With respect to model size and induction times, the ensembles that exploit the structure do have a significant advantage. The advantage is more pronounced when the datasets have large number of instances and descriptive attributes. Moreover, because of the feature sampling, the random forests for predicting structured outputs benefit even more, in terms of induction time, when the datasets have many descriptive attributes.

Averaged over all datasets considered in this study, we obtain that random forests for predicting the complete structured outputs are $~4$ times faster to construct and the models are $~3.4$ times smaller than a collection of random forests for predicting single targets or labels. In addition, they are $~5.5$ times faster to construct and have models with similar size as bagging for predicting the complete structured output. Furthermore, the latter is $~3.9$ times faster and yields models that are $~2.9$ times smaller than a collection of bagged trees for predicting single targets or labels. 


\section{Conclusions}\label{sec:conc}

In this article, we present and compare several approaches for learning decision tree ensembles for structured output prediction. We compare approaches that exploit the output structure to approaches that focus on a component of the structure. All approaches are implemented in the predictive clustering tree framework.

We performed the empirical evaluation over a wide range of datasets. In particular, we used 13 datasets for the task of multi-target regression, 9 datasets for the task of multi-target classification and 10 datasets for the task of hierarchical multi-label classification.

The experimental comparison comprises 32 datasets from three learning tasks: multiple targets regression, multiple targets classification, and hierarchical multi-label classification. To our knowledge, this is the first extensive comparison of ensemble methods for predicting structured outputs.

The main results are summarized as follows.
First, we have shown that the fact that ensembles lift the predictive performance of a single classifier carries over to the context of structured outputs. This finding suggests that the non-trivial relations that might exist between the components of the structure are maintained when combining predictions of several classifiers or when injecting some source of randomness in the learning algorithm.

Second, we have presented saturation curves, which show that in the majority of cases, the predictive performance of the ensembles saturates at about 50 trees. Furthermore, the curves suggest that, especially when the ensembles contain smaller number of trees, for the majority of the datasets considered, the global ensemble methods have better predictive performance than the local ensemble methods.

Finally, we have shown that, although the ensembles for predicting structured output often have smaller average ranks than the ensembles for predicting the components of the structure, the differences in predictive performance of all ensemble methods are not statistically significant at the 0.05 level in any of the tasks. Furthermore, ensembles that predict the whole structure at once are preferable when considering efficiency in terms of total model size and induction times.

\begin{acknowledgements}
The authors would like to thank Ivica Dimitrovski from the Faculty of Electrical Engineering and Information Technologies, Skopje, Macedonia for providing the image annotation datasets. Celine Vens is a postdoctoral fellow of the Research Fund -- Flanders (FWO--Vlaanderen).
\end{acknowledgements}

% BibTeX users please use one of
\bibliographystyle{spbasic} % basic style, author-year citations
%\bibliographystyle{spmpsci} % mathematics and physical sciences
%\bibliographystyle{spphys} % APS-like style for physics
\bibliography{EnsemblesSP_refs} % name your BibTeX data base

% Non-BibTeX users please use
% \begin{thebibliography}{}
% %
% % and use \bibitem to create references. Consult the Instructions
% % for authors for reference list style.
% %
% \bibitem{RefJ}
% % Format for Journal Reference
% Author, Article title, Journal, Volume, page numbers (year)
% % Format for books
% \bibitem{RefB}
% Author, Book title, page numbers. Publisher, place (year)
% % etc
% \end{thebibliography}

\end{document}
% end of file template.tex

