Leandro L. Minku

Software Engineering By Automated SEarch (SEBASE)

Principal investigator: Prof. Xin Yao.
Keywords: software effort estimation, project scheduling problem, ensembles of learning machines, evolutionary algorithms, online learning, concept drift.

[Section of the home page under construction]

PhD Project

Online Ensemble Learning in the Presence of Concept Drift

Supervisor: Prof. Xin Yao.
Keywords: concept drift, online learning, ensembles of learning machines.

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 long-term.

• 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 drifts.

• 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

• Report 1 (8th November 06)  
• Report 2 (20th April 07)
• Report 3 (Thesis Proposal - 22nd August 07)
• Report 4 (9th April 08)
• Report 5 (22nd October 08)
• Report 6 (19th April 09)
• Report 7 (28th September 09)

MSc Project

EFuNN Parameters Optimisation and EFuNN Ensembles Construction 

Evolving Connectionist 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.

A key 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.

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

BSc Projects

Final Year Project (2003) - Trabalho de Graduação

Undergraduate Research Experience (08/2001 - 07/2002) - Iniciação Científica

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 computer programs.

The 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 genetic programming based testing tool which uses the Chameleon's outputs to do automatic software testing.