REPOSITORY > RESULTS

Abstract

In this thesis, we deal with structured output prediction (SOP) on data streams. SOP
is concerned with learning predictive models that can predict structured outputs, i.e.,
outputs that are composed from multiple component values. On the other hand, data
stream mining is concerned with learning in the online setting, where new data examples
arrive at high frequencies and a predictive model is expected to operate in real-time.
Methods for SOP are now common in the classical batch data mining setting. However,
they are fairly rare in the online setting, where the most addressed SOP tasks are multitarget
regression (MTR) and multi-label classification (MLC). In MTR, we predict multiple
real-valued targets, while in MLC we predict the presence or absence of predefined labels.
Methods for online SOP tasks are typically specific to the SOP task that they address.
In this thesis, we introduce the incremental Structured Output Prediction Tree (iSOUPTree)
family of methods that are designed to address multiple SOP tasks in the online
learning setting. We introduce tree-based methods for online MTR: iSOUP-Tree, a method
that uses the Hoeffding inequality and an intra-cluster variance reduction heuristic to grow
the tree, iSOUP-OptionTree, a method that extends iSOUP-Tree toward option trees,
online bagging of iSOUP-Trees and online random forests of iSOUP-Trees.
We continue by introducing the MLC via MTR problem transformation methodology
that transforms an online MLC task into an online MTR task. We use the introduced
methods for online MTR in combination with this methodology to address online MLC.
We then extend the iSOUP-Tree method to handle hierarchical prediction tasks, hierarchical
MTR and hierarchical MLC where a hierarchy of the target variables is given. To
this end, we adapt a batch method that introduces feature weights in the splitting heuristic
of iSOUP-Tree where the weights are based on the target hierarchy.
We continue by extending iSOUP-Trees into the predictive clustering framework and
introduce iSOUP predictive clustering trees (iSOUP-PCTs). We use iSOUP-PCTs for
online semi-supervised MTR, where we learn from incompletely annotated examples as
well as from completely annotated examples that are used in regular, supervised learning.
We also address the task of online feature ranking for SOP tasks. Feature ranking is
concerned with identifying the input attributes that are most crucial for learning models
with good predictive performance. We adapt the symbolic random forest feature ranking
method from the batch to the online setting by using online random forests of iSOUP-Trees.
We evaluate the introduced methods through experiments suited to the SOP tasks
we address. For online MTR, we find that bagging of iSOUP-Trees has the best performance,
while random forests of iSOUP-Trees provide a good trade-off between predictive
performance and consumption of computational resources. For online MLC, the compared
methods are competitive with state-of-the-art methods. For the online hierarchical tasks,
the introduced methods show promise, though further examination is warranted. In semisupervised
learning, iSOUP-PCTs perform well, particularly, when there are few labeled
examples. For online feature ranking for SOP, the obtained results are unclear and warrant
further examination.