Software Engineering By Automated SEarch (SEBASE)
investigator: Prof. Xin Yao.
Engineering and Physical Sciences Research
Keywords: software effort estimation, project scheduling problem,
ensembles of learning machines, evolutionary algorithms, online
learning, concept drift.
[Section of the home page under construction]
Online Ensemble Learning in the Presence of Concept
Supervisor: Prof. Xin Yao.
Research Students (ORS) Award and School Research Studentship
(School of Computer Science, The University of Birmingham).
Keywords: concept drift, online learning, ensembles of learning
Abstract: Most machine
learning algorithms operate in offline mode. They first learn how to
perform a certain task, and then are used to perform this task.
However, most practical problems change with time, i.e., they suffer
concept drift. For example, the problem of predicting users'
preferences in information filtering systems may involve changes in
users' preferences; the problem of classifying webpages may involve
changes in the most representative words of different webpage
categories; the problem of credit card approval may involve changes in
customers' reliability. Different from offline learning algorithms,
online learning algorithms can be used to adapt to concept drifts based
on newly incoming training examples. These algorithms do not have a
separate training and testing phase, but learn throughout their
lifetime as they are used to perform a certain task, by processing each
new training example separately and then discarding it.
Due to the practical need for adaptive learning systems, there has been
an increasing number of works on online learning algorithms able to
deal with concept drift. In particular, online ensembles of learning
machines have been used. However, there has been no deep study of why
they can be helpful for dealing with drifts and which of their features
can contribute for that. This thesis mainly investigates not only how
ensemble diversity affects accuracy in online learning in the presence
of concept drift, but also how to use diversity in order to
significantly improve accuracy in changing environments. This is the
first diversity study in the presence of concept drift. The main
contributions of the thesis are:
- A better understanding of when, how and why ensembles of learning machines can help to handle concept drift in online learning. This
study shows that one reason for ensembles to be helpful for dealing
with concept drifts is the diversity among their base learners.
Diversity is even more important in changing environments than in
static environments. A proper level of diversity at each different
environmental condition can significantly reduce the test errors of the
learning machines as follows. Before a drift, ensembles with less
diversity obtain lower test errors. On the other hand, it is a good
strategy to maintain very highly diverse ensembles to obtain lower test
errors shortly after a drift independent of the type of drift, even
though high diversity is more important for more severe drifts. Longer
after a drift, high diversity becomes less important. High diversity by
itself can help to reduce the initial increase in error caused by a
drift, but does not provide faster recovery from drifts in the
- Knowledge of how to use information learnt before a concept drift to aid the learning after a concept drift.
Previous works have never attempted to use information learnt before a
concept drift to aid the learning after a concept drift. However, a
good learning machine for changing environments should not only avoid
using outdated information, but also be able to use information
previously learnt whenever it becomes useful. This thesis shows that
ensembles trained before a concept drift with very high diversity can
be used to transfer useful information learnt from the old concept to
the new concept. Information learnt before a concept drift is shown to
be helpful for the learning process after the drift when the drift is
slow or does not cause too many changes. Very highly diverse ensembles
perform well in comparison to other strategies after these concept
drifts as long as low diversity is enforced after the concept drift.
- A new online ensemble learning approach called Diversity for Dealing with Drifts (DDD).
Based on the deep diversity studies summarized above, a new approach
called DDD was proposed. A good learning approach for changing
environments should: (i) maximize performance when the concept is
stable; (ii) minimize the drop in performance when there is concept
drift; (iii) quickly recover from concept drifts; and (iv) efficiently
use information previously learnt whenever it is beneficial. DDD was
carefully designed to use ensemble diversity for dealing with these
requirements. It maintains ensembles with different levels of diversity
which are automatically emphasized during environmental states in which
they are helpful. In this way, DDD is robust to different types of
concept drift. A study based on both artificial data sets and real
world data sets in the domains of credit card approval, computer
network intrusion detection and electricity price trend prediction
showed that DDD was able to outperform state-of-the-art approaches. In
all the experimental comparisons carried out, DDD always performed at
least as well as other drift handling approaches under various
conditions, with very few exceptions. Furthermore, DDD was shown to be
very robust to false positive drift detections, outperforming other
drift handling approaches in terms of accuracy under these conditions.
- A new concept drift categorisation to allow principled studies of drifts.
The existing literature presented very heterogeneous and ambiguous
categorisations of concept drifts. In this thesis, a categorisation
using mutually exclusive and unambiguous categories was proposed.
Drifts are categorised according to different criteria in order to aid
the development and evaluation of approaches to deal with concept
- An analysis of negative correlation in incremental learning.
This thesis also presents a study of the suitability of ensembles based
on negative correlation learning for incrementally learning new chunks
of training examples under stable environments. It shows that even
though it is possible to use negative correlation learning for that,
chunk-based incremental learning approaches face a difficult trade-off
between avoiding catastrophic forgetting under periods of stability and
attaining plasticity when adaptivity to changes is needed.
Research Progress Reports Presented
1 (8th November 06)
2 (20th April 07)
3 (Thesis Proposal - 22nd August 07)
4 (9th April 08)
- Report 5 (22nd October 08)
- Report 6 (19th April 09)
- Report 7 (28th September 09)
EFuNN Parameters Optimisation and EFuNN Ensembles
Supervisor: Prof. Teresa B. Ludermir.
Keywords: online parameters optimisation, numeric parameters
optimisation, fuzzy neural networks, ensembles of neural networks.
Funding: Brazilian Council for Scientific and
Technological Development (CNPq).
Degree congregation: 2006.
Systems (ECoSs) are systems composed by one or more neural networks
whose structures adapt according to the data in a continuous
interaction with the environment. Evolving Fuzzy Neural Networks
(EFuNNs) are ECoSs which join the neural networks functional
characteristics to the power of fuzzy logic. Fuzzy systems have been
showing to be very efficient to represent
and reason about uncertain knowledge. This is very important, as,
many times, human knowledge is uncertain.
challenge in Artificial Intelligence is to create systems that are
able not only to represent human knowledge and reason about it, but
also to evolve and adapt their structures in a changing environment.
This kind of system is able to model processes that continually
develop and change over time, e.g., biological data processing,
electricity load forecasting and adaptive speech recognition. A
system with these characteristics needs to be able to tune its
parameters in an on-line manner, according to the environment. EFuNNs
have some adaptable parameters and their structures can also adapt
according to incoming data. However, they still have many parameters
that are fixed before the learning and have great influence on its
results. The problem of using a fixed set of parameters is that an
optimal set to a particular state of the environment can be
unsuitable when the state of the environment changes.
In this work, two new techniques which use
evolutionary algorithms to
evolve the EFuNN parameters in an on-line manner were developed.
These techniques are able to create fuzzy systems that are completely
tunable, according to unpredictable and unknown environments. The
techniques showed to be able to have better accuracy than the
techniques existent in the literature to evolve EFuNN parameters in
an on-line manner.
the necessity to create new techniques to allow changing environments
to be represented, it is always important to develop approaches with
increasing generalization capabilities and lower execution time.
Ensembles of neural networks have formally and empirically shown to
outperform systems composed by only one neural network. Thus, this work
also proposes a new approach to create ensembles of neural networks,
e.g., ensembles of EFuNNs. The approach uses a clustering method and
co-evolutionary algorithms to create the ensembles in an innovative
way, explicitly partitioning the input space, in order to allow the
networks that compose the ensemble to specialise in different parts
of it and work in a divide-an-conquer manner. The approach showed to
be able to improve the accuracy of single EFuNNs generated using
evolutionary algorithms similar to the co-evolutionary algorithms
used in the approach. Furthermore, the execution time of the approach
is lower than the execution time of evolutionary algorithms to
generate single EFuNNs.
Final Year Project
(2003) - Trabalho de
Generation for Action and Planes Logics - Geração de Dependências Para
Lógica de Ações e Planos.
Supervisor: Dr. Marcos Alexandre Castilho.
Keywords: knowledge representation, reasoning about actions, modal
logics, causality, dependence relation, prime implicates.
In this work, the semi-automatic creation of a dependency relation
between actions and literals in action and planes logics is
investigated. The creation of this relation is important for the
correct treatment of the ramification problem and the relation itself
is important for the correct treatment of the frame problem presented
by action and planes logics. Interactive
algorithms serving as the basis of the development
of a program which creates the relation are presented.
Research Experience (08/2001 - 07/2002) - Iniciação
Nature is a great font of
inspiration to technology and human inventions. One of the big dreams
of the humanity is to create machines that are able to imitate the
human reasoning and behavior. A great challenge to the artificial
intelligence community is to create computer programs capable to be
programmers, i.e., computer programs that create
work developed during my "research training" consisted in developing a
new version of a tool, called
Chameleon, which is capable to create computer programs using Genetic
Programming. The tool was used to perform experiments with a
programming based testing tool which uses the Chameleon's outputs to
do automatic software testing.