REPOSITORY > RESULTS

Abstract

In this thesis, we address the task of learning models for predicting structured
outputs, which take as input a tuple of attribute values and produce as output
a structured object. In contrast to classification and regression, where the
output is a single scalar value, in our case the output is a data structure,
such as a tuple or a directed acyclic graph. We consider both global and local
prediction of structured outputs, the first based on a single model that predicts
the entire output structure and the latter based on a collection of models, each
predicting a component of the output structure.
In particular, we take the notion of an ensemble, i.e., a collection of predictive
models whose predictions are combined, and apply it in the context of predicting
structured outputs. Ensembles have proved to be highly effective methods for
improving the predictive performance of their constituent models, especially for
classification tree models. We propose in this thesis to build ensemble models
consisting of predictive clustering trees, which generalize classification trees:
these have been used for predicting different types of structured outputs, both
locally and globally.
More specifically, we develop methods for learning several different types of ensembles
of predictive clustering trees for global and local prediction of different
types of structured outputs. The types of outputs considered correspond to
different predictive modeling tasks, i.e., multi-target regression, multi-target
classification, and hierarchical multi-label classification. The different types of
ensembles include bagging, random forests, random subspaces and bagging of
subspaces. Each of the combinations can be applied both in the context of
global prediction (producing a single ensemble) or local prediction (producing
a collection of ensembles).
We conduct an extensive experimental evaluation of bagging and random
forests for structured prediction across a range of benchmark datasets for each
of the three types of structured outputs. We compare ensembles for global and
local prediction, as well as single trees for global prediction and tree collections
for local prediction, both in terms of predictive performance and in terms of
efficiency (running times and model complexity). Both global and local ensembles
perform better than the single model counterparts in terms of predictive
power. Global and local ensembles perform equally well, with global ensembles
being more efficient and producing smaller models, as well as needing fewer
trees in the ensemble to achieve the maximal performance.
We also analyze the computational complexity of the methods theoretically.
The theoretical analyses are consistent with the empirical evidence, showing
that the global ensembles are most efficient, especially random forests. The
analyses also indicate that the proposed approaches are scalable to datasets,
which can be large along any of the following dimensions: number of attributes,
number of examples, and size of the target.
We apply the developed ensemble approaches to three practically relevant problems,
resulting in three detailed case studies: we compare our results to results
of state-of-the-art methods used in the respective domains. First, we constructed
models to better understand the resilience of some vegetation types
and generated maps of the vegetation condition in the sate of Victoria, Australia.
Next, on the task of hierarchical annotation of medical X-ray images,
the ensembles for predicting structured outputs provided the best annotation
results reported so far in the literature. Finally, extensive experimental evaluation
over several tasks of gene function prediction in three organisms showed
that bagging for predicting structured outputs is superior to or competitive
with state-of-the-art methods in this area.
Finally, we present some preliminary results that further explore the proposed
paradigm of ensembles for structured prediction. We first discuss structured
prediction for different types of structured outputs and correspondingly different
distance measures on these. We further propose a method for feature
ranking in the context of structured outputs, based on random forests. Moreover,
we suggest a novel ensemble learning method that is based on the beam
search strategy and can control directly the diversity in the ensemble. With
this, we open a number of avenues for further developments.