Meta-learning and a Concept Drift

Just some thoughts on how concept drift can appear in the meta-learning study.

When trying to learn how to learn one can formulate this problem as the problem of controlling the learning algorithm (sub-learner) by another learning algorithm (meta-learner). An approach, which emerges just at the very beginning, is to recognize some sort of regimes or modes of the sub-learner, e.g. use operators A and B in mode 1 and operators 2, 3 and 4 in  mode 2. The definition of these modes depends on the sub-learner.

For example if the sub-learner is a neuroevolutionary algorithm the modes may be:
1. Complexify network structure.
2. Simplify network structure.
3. Search the weights space using current or only slightly changing structure.

There may also be combinations of these or some other modes.

To understand in which mode the sub-learning algorithm is performing some set of mode features should be defined. Possible variant is to trace the algorithm's behaviour and recognize modes depending on the behaviour outcomes. So for NE algorithm there's a set of operators, like add/remove connection or change activations and we can log fitness changes involved by these operators for each individual in the population. Averaged influence of the operators on the Ne algorithm performance over several last generations can indicate the current mode.

However the analysis of operators' performance may be affected by the problem at hand and a good meta-learning approach should be able to deal with various problems. So for problem P1 mode 1 can be indicated by the different operators log than for some other problem P2. It is presumed that the meta-learner starts without knowing which problem the sub-learner is to solve and should make decisions on the fly based upon analysis of sub-learner performance.

Thus it is possible to define at least two possible sources of the concept drift for the meta-learning approach:
1. The concept drift due to problems swtiching (the mode1 definition changes  when the problem is changed).
2. The concept drift due to dynamical problem environment (conditions for sub-learner are changing and hence influence it's performance and operators analysis).

The Neuroevolution, or to Randomness and Back Again

Most researchers, who develop neuroevolutionary algorithms involving evolution of ANN structure, concentrate on creating 'smart' algorithms out-of-box. This means, that the algorithm should have some predefined constraints to prevent too fast growth of the number of nodes and connections. It's also possible to track nodes' activity, counting each node's degree or total signal, which is translated through a node. Knowing these activities can be helpful for defining, for example, which nodes to connect ('active' ones) and which to remove ('lazy' nodes)
In one of my earlier posts there was an interesting observation that average number of hidden units tend to stabilize over time if there were some rules to decide, which operation to modify ANN structure to apply. Those rules depended on current ANN topology.
The interesting question is whether we could observe this 'auto'-stabilization if no ad-hoc rules are there, guiding which operation to use to mutate ANN.
I made series of experiments for one of the simplest NE algorithms for evolving both weights and structure of ANN (including activations).
The following operators were used

• Add Node with Default Activation (Sigmoid). Adds isolated node. This operations has no immediate effect on individual's fitness (neutral operation), but in some consequent generation this node can be advantageous. Note also that even adding connections to this node not obligatory lead to a fitness change, if there is no other node in the network that accepts output signal of a new node.
• Remove Random Node. Removes random node regardless on the number of its connections or that ANN structure can become meaningless, when input signals are not translated onto ANN outputs. Input and output nodes can not be removed.
• Add Random Connection. Adds connection with random weight between two randomly chosen nodes.
• Remove Random Connection. Removes random connection from a network. If in result some node becomes isolated, then this node is removed ('dying').
• Modify Weight. Changes weight of randomly chosen connection. The weight's delta is defined using uniform distirbution.
• Modify Activation. Changes activation function for random node. Can not change activation for input nodes

It's easy to see that these operators do not use any heuristic rules and behave randomly. To make algorithm even more random selection of operators is made also at random. That is when some ANN undergoes mutation and the algorithm to decide mutation operator, a random operator is picked.
I've used quite a bunch of test problems

• XOR
• Artificial Ant
• 1 and 2 Poles Balancing
• 7 problems from the Proben1 set (cancer1, card1, diabetes1, glass1, heart1, horse1, thyroid1)

And here are some results. Below are plots with averaged change of average number of nodes and connections for different problems (click to enlarge).

It's easy to see, that in most problems change of nodes number is step-like and that increase of the number of hidden nodes goes slowly.
So even for the NE algorithm with simplest acting operators and pure random operators choice scheme the number of hidden nodes seems to be controllable. Thus we can conclude that ANN structure growth during evolution may be not a major problem. Surely if some rules for application of operators change then different results can be achieved.
One more interesting question is was such a random NE algorithm succesfull at solving the test problems. And the answer is partially.

Here are the solved problems (in brackets there are test set classification errors)

• 1-Pole Balancing (100k ticks equilibrium)
• Artificial Ant (ate all 89 pellets)
• card1 (13,95%)
• heart1 (21,30%)
• horse1 (31,87%)

And the unsolved problems

• 2-Poles
• cancer1 (37,36%)
• diabetes1 (36,46%)
• glass1 (69,81%)
• thyroid1 (97,78%)
• XOR (66,06%)

The results for unsolved problems seem rather devastating (up to 97,78% errors), but I doubt that everything was that bad. It was a very simple NE algorithm, a lot should be done to make it work well. And moreover it's already sort of miracle that this algorithm was able to solve several problems working almost at random using only evolution for a guidance.
One of the errors with current algorithm is that for some problems the resulting ANN always fires with only one output, and all other outputs are silent. Such a network gives correct answers from time to time, but it's just like stopped clock that shows correct time twice a day. So possible solution is to add regularization term into fitness function to encourage diversity of ANN outputs. But it is a work for future research and there are some other interesting results which I'll present a bit later.

Neureka

Yesterday I was making experiments on using neuroevolution for adaptive increase of dimension of the features space. The idea is simple: According to the Cover’s theorem (1965) the probability to randomly ‘place’ separating hyperplane, which minimizes the number of ambiguous/incorrect recognitions, is increasing with the growth of dimensionality. In other words, theoretically, increasing the features space dimensionality should ease the recognition.

Since it’s not known what dimensionality to target and how the original features space should be transformed I did experiments when artificial neural network (ANN), which is used for recognition, consists of two parts:

1.      ANN-1 which is trained by an evolutionary algorithm.

2.      ANN-2 which is trained using RProp algorithm from the Encog library (see http://www.heatonresearch.com/encog).

Output signals for ANN-1 are input signals for ANN-2 and thus one can treat these networks as two parts of the one and the same neural network.

The error criterion for evolutionary training of ANN-1 was the largest error, obtained after training of three ANN-2 for 50 epochs. I chose to pick the largest error to avoid the overfitting effect.

The first results were not very encouraging (see here http://qai.narod.ru/Workshop/Tsoy_cai2010.pdf (in Russian)), I didn’t get the improvement for all test problems (from the Proben1 suit, see http://www.filewatcher.com/b/ftp/ftp.cs.cuhk.hk/pub/proben1.0.0.html) and when this method worked better the average classification accuracy wasn’t near the best results obtained so far.

I was pretty puzzled by this and decided to change the ANN-1’s error criterion to pursue minimal correlation between outputs of ANN-1. And mistakenly set evolutionary algorithm to maximize this criterion. And suddenly I started obtaining good results. For example, the table below contains classification errors on a test data set (mean (stdvar)) for several problems,

Problem	Ref. Proben1 results	Prev. best result	Cur. best result (maximization of signals correlation)	Cur. best result (minimization of signals correlation, sigmoid nodes at ANN-1 output)	Cur. best result (minimization of signals correlation, linear nodes at ANN-1 output)
Cancer1	1,38 (0,49)	2,07 (0,73)	1,26 (0,45)	1,03 (0,53)	2,53 (0,30)
Horse1	29,19 (2,62)	34,40 (3,84)	28,35 (2,25)	28,02 (3,03)	24,51 (0,53)

The first column contains best results obtained by Lutz Prechelt using hand-tuned neural structures. The second columns shows experimental results with old fitness function (published in http://qai.narod.ru/Workshop/Tsoy_cai2010.pdf), while the last 3 columns contain new results and in most cases considered so far, it’s possible to obtain better results than the old ones.

There are only two problems are shown (cancer1 and horse1), because they caused problems for algorithm with old fitness function, which minimizes ANN-2 training error directly. There are some interesting regularities in results when the number of nodes on ANN-1 output is changing, but I’d better leave them for the next post when I’ll have more statistics.

Meanwhile I’d like to discuss possible causes of these results. First of all why increasing correlation between outputs lead to better results? My intuition tells me that increasing correlation tends to lead to dimensionality reduction, which can be useful according to numerous results obtained by other researchers. And this can be particularly important when the number of input signals is rather large. For example, in horse1 problem there were 58 input signals and the best obtained results corresponds to cases when ANN-1 had only 14 outputs, which means that input features space was reduced by a factor of ~4. When number of outputs of ANN-1 for this problem was increased to 29 or more the results become worse (in some cases I obtained testing errors >60%).

From the other hand for ANN-1 having more outputs than inputs can be useful and cancer1 problem is a good example here. The best results obtained for ANN-1 with 22 and 27 outputs while the number of inputs for this problem is 9.

It’s quite indicative that ANN-1 with linear output nodes didn’t get the improvement in the cancer1 problem since in this case the real dimensionality of ANN-1 output didn’t exceed that of the input. The reason is simple ANN-1 with linear output signals performs linear transform of the input signal, which can’t increase the dimensionality, while ANN-1 with sigmoid outputs can increase the number of features space dimensions and this indeed leads to the improvement.

Obtained results show that varying number of outputs of ANN-1 dynamically, during the evolutionary algorithm run, it’s possible to obtain quite effective classification algorithm.

Another good result is that such approach demonstrates practical need in neuroevolutionary algorithms, which allow variation of the number of outputs. It’s good because I could not figure out earlier a nice example for such algorithms, except of impossible (?) for implementation A-Life and adaptive behavior problems, when the environment changes dynamically and it requires emergence of new limbs/effectors.

A good question here is where this method more effective, than 'conventional' approach with 'toggling' input features on and off using genetic algorithm with binary encoding. Think this may be a theme for a good research paper.

An observation

I am currently experimenting with a neuroevolutionary algorithm which is based upon two of my previous algorithms: the one from my master and doctoral dissertation and the algorithm based on some ideas from gene regulatory networks. Since the work is in progress I think that it's too early to provide a description of the algorithm, and for now it's enough to say that the algorithm considers evolution of both structure and weights of the neural network with emphasis on growing networks, but with possibility to reduce network size if necessary.

One of the features, which I'd like to see in my algorithm, is self-organization because I believe that it is a key feature for building complex systems, which are able to adapt to wide variety of changes.

Here is a very first result (which, hopefully is free of program bugs). One of my standard tasks to check algorithm's functioning is a well-known XOR problem, which means that ANN should be trained implement logical eXclusive OR operation. Though this problem is rather easy, it requires creation of ANN able to perform some intermediate calculation, due to the nature of the XOR operation output. Thus the NE algorithm is required to find ANN with hidden units and proper structure and weights for this problem. To track the algorithm performance I've plotted dynamics of minimal fitness, average number of hidden nodes and average number of connections. The result (without averaging over multiple runs, be careful!) is:

The generation number is plotted along the horizontal axis, and there are two vertical axis: the left one for minimal fitness and the right one for average number of hidden nodes and connections.

The most interesting thing is there is a kind of plateu for average number of hidden nodes. Each node can be added or deleted from ANN under some probabilistic conditions, which use infromation about current ANN structure. It might seem like the algorithm found optimal number of hidden nodes by itself and that the further search is conducted for different schemes of connections and combinations of weights. Since the results are (very) preliminary it's not very reliable to judge the algorithm properties for now, but I believe that there is a hope to construct NE algorithm which will show similar behaviour for many other problems.

One of possible improvements here is a temporal disabling of nodes adding/removal, which may improve the speed of search because this way the search becomes more 'concentrated' (more 'local' if one could say so). I just need to find good condition fo toggle this regime on.

How can study of complex adaptive systems contribute to the neuroevolution?

Complex adaptive systems (CAS) domain studies properties large systems consisting of heterogenous elements. The research interests are focused on system-level phenomena like self-organization, adaptation, emergent properties, etc. One of the main organization which deals with CASs is well-known Santa Fe Institute.

It's not surprizing that CAS study also concerns neural networks. Quite a number of publications concerns a kind of multi-agent systems, where each agent is driven by its neural network, which in most cases evolves during the experiment. The examples are publications by the evolutionary robotics related groups members. Thus one can say that CAS utilizes neuroevolutionary algorithms to study system-level behaviour. This is possible because evolving ANNs tend to create more complex agents' behaviours, which leads to the more complex interactions. Good example here is an evolving predator-prey system where both predator and prey movement was driven by their evolved ANNs. As time passed several strategies had been tested by both sides and each following strategy was 'invented' to compete the current opposing strategy. Here is an illustrative picture from Floreano D, Keller L (2010) Evolution of Adaptive Behaviour in Robots by Means of Darwinian Selection. PLoS Biol 8(1): e1000292. doi:10.1371/journal.pbio.1000292

But this is about how NE can help to CAS. And is there a 'feedback'? How can CAS contribute to the neuroevolution? I think that since ANN is a complex adaptive system itself the CAS study can be helpful answering the following questions:

• how to evolve irregular-structured ANNs, which possess some desired system-level properties *and* are robust and reliable.
• how can neural modules, consisting of multiple nodes, be connected and arranged to perform some specified task.
• what are the ways and principles to dynamically change ANN structure and interconnections between modules and nodes to provide adaptivity in changing environment.

These might be not all questions but, as I believe, they have a great importance for creating reliable and adaptive neuroevolutionary algorithms which perform well in off-line and on-line learning.

Why I have doubts about neuroevolution and possible way out

Recent thoughts and readings made me doubt about promises of neuroevolution. I still believe that it is a really good research domain and that it is truly easy approach for many problems which are complicated to solve using traditional methods (board games playing, adaptive behavior, robotic control in complex situations, artificial music and art etc.). But the basis of my doubts is in randomness of evolutionary search which involves solutions with badly predictable structure and features, without any "physically" clear explanation of why this works and thus not very reliable when it comes to practice (nobody wants to risk much, you know).

Consider classification problem for supervised learning. Feasible approach is to extract regularities from training data and use problem dependent priors to create a structure for classifier (here I mean what parts this classifier has and how they are tuned and interconnected). This approach can be probabilistic since priors often come from statistics and somewhat tricky thing, which is called "experience", and hence the solution can have some variations when the approach is restarted. And one can even say that the result is in some way smart. But any way the classifier's structure is guided by the knowledge.

Next just look at the NE approach. We have (preprocessed) training data and then an NE algorithm is run to minimize the error function. The resulting structure of neural network will really have some reasons to be what it is (otherwise it would be unable to perform well). But I bet that in most cases it still have some unnecessary elements while some other useful elements and parts are not there. And there can also be some space for optimization of connection weights.

This can be exampled by house building for the purpose of living in it (yes, just this general). Traditional architect makes a plan, all the calculations etc. and builds a house. And the house's structure is guided by knowledge of how to build right. But evolutionary architect just builds the house up through trials and errors until something suitable is received. And imagine that our evolutionary architect is able to build any house (not only choosing, say, number of floors and roof type). And there is rather high probability that this house will be … um, very original and non-standard, not saying ridiculous (for example, having lots of wrongly shaped windows, which may be good for design, but bad for convenience). So evolutionary structure of the house is random. One can say that we can guide evolution through additional restrictions and penalties. But these restrictions can not be very strict since the purpose is very general (just like "minimize the error") and moreover it is almost impossible to consider all of them (because it can lead to the ridge objective function), thus the space of possible houses is till ve-e-ery large and mostly consists of "designed" houses, which are still good for living. Well at least for now I'm pretty sure that things are like this and that the same thing is about evolving neural networks.

Does it bad? Yeah. But… I believe that it is possible to involve self-organization principles, like those which lead to emergence of scale-free networks, together with some rules of thumb to make NE algorithms behave better and to produce more feasible solutions. And this is what I'm going to do for next several years.