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.

Digging for Roots

There is an interesting way of finding polynomial roots, which concerns calculation of eigenvalues for the following matrix (http://mathworld.wolfram.com/PolynomialRoots.html):

After eigenvalues have been found the roots are simply computed as 1/lambda.

This method is rather slow especially for large matrices, but it finds all roots, including complex ones, which is hard to do using conventional scheme "root localization + application of numeric method for finding exact root value".

It's interesting that it's possible to obtain a matrix, which eigenvalues are the same as the polynomial's roots. This matrix is:

It's easy to check that AB = E, where E - is identity martix.

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.

Lost in motivation

Motivation is a really tricky thing. Sometimes it seems that it's motivated people who are rolling the Earth (not Ralf Ringer shoes :)). Recently I've been thinking on motivation system for under- and post-graduate students in order to improve their results and gently push them towards self-study.

To tell the truth I was inspired by Steven MacConnell's book "Professional Software Development" where he describes the programme for the professional growth which is used in the Construx company. It gives quite clear picture of professional growth based upon improvement of experience of SW developer (side remark: funny, I've just noticed, that SW stands for both 'Software' and 'Star Wars' as well :)), and was created to motivate self-study, professionalism in general, communication etc.

So here is a sketch of what came into my mind. But in the first place some axioms, which I've tried to follow:
- people's relations are prior.
- benefit for the group.
- reasonable formalism -- there should be clear rules, but these rules should not constrain one's scientific growth and trajectory.
- motivation system should not lead to envy, misjudging, grievance etc. (hopefully)

...a-a-and here it comes:
==============================================
Student of the Month title is established accompanied by a humble reward. The winner is defined by the following measures (the calculation of final decision is yet to be thought about):
- Defense of the thesis.
- Passed exam.
- Personal grant/scholarship obtained.
- Participation in the process of winning group grant, contract (helping with aplicatin, making research for a scientific scientific reserve, reviews etc.).
- Awards in competitions.
- Receiving professional certificates.
- Documents, which acknowledge usage of scientific results in real systems.
- Published papers in journals, conference proceedings.
- Oral and poster reports made on conferences.
- Reports on inner group seminars.
- Scientific service for organization of conferences, workshops, journal reviews.
- Source code of algorithms and modules, which can be used by other members of the group (with a short how-to documentation/manual). Open-source is highly encouraged.
- Scientific web-publication (posts in blogs, personal web-site etc.)
- Attracting new members to the group.
- Various proposals to improve group's organization and working.
- Transition to the next Level (see below).
- Marriage, birth of the child and so on.

Attributes (to think further):
- Challenge cup
- Hat/Crown/Helmet of the Winner.
- (something else).

Remarks:
- The winner is defined at the beginning of each month.
- There might be no winner at all.
- If uncertain situation arises then group members to decide the winner themselves (via open or secret voting or something like that).
- Think about Student of the Year (with extended reward) and Student of the Half-Year.
==============================================

Levels - designed to show ones progress and scientific growth.

Level 1. Entry level. Very small experience in scientific research, writing, programming etc.

Level 2. Small experience in programming in the major domain. Knowledge of essential books (2-3) and some publications related to thesis. Short survey on the thesis theme.

Level 3. Average programming experience in the major domain. Quite good knowledge of books (5-6) and publications related to thesis. Knowledge of essential books (2-3) on neighboring themes. Good knowledge of publications made by leading specialists during last 3 years. The emergence of the second major. 1-2 written thesis chapters or 2-3 good journal papers. Scientific consulting/joint research with the student.

Level 4. Programming experience in the major domain is significantly above average. Very good knowledge of books (9-10) and publications related to thesis. Good knowledge of books (5-6) on neighboring majors. Good knowledge of publications made by leading specialists during last 5 years. The emergence of the second major. Thesis draft, or 4-5 good journal papers, or participation in writing joint monograph.

Level 5. Ready to independent scientific work. Defended PhD thesis. Great knowledge of books (14-15) and publications related to thesis. Good knowledge of books (6-7) on neighboring majors. Very good knowledge of publications made by leading specialists for the major during last 5 years and good knowledge of publications made by leading specialists for the neighboring majors during last 3 years. Reasonably good possession of the second specialization. Own published monograph.

Notes:
- levels are necessary for writing applications for grants and projects. A student can attract other group students only if he or she has level 3 or higher. Besides, only students with lower or equal level can be considered as collaborators. Only students at level 5 can invite PhDs as collaborators. I hope that this rule will push students to promote to higher levels to make their own projects.
- transition on each level can be made with violation of desirable achievement (for example level 5 can be reached without defending PhD).
- to approve book reading the student should make a report on the group seminar which states what information from the book and in what way can used to obtain dissertation goals. Some analysis of the approach should be made and it's quite desirable that some discussion could be made on this theme. Short excuse-phrases like "I'd like to use method X, I hope it'll work", should not score in no way, there should be some speculations behind this.
- student who only read books and don't do anything else should not be promoted to the next level. Knowledge is good only when combined with practice.
- a book should not be scientific in the first place. It's enough that the book contains useful ideas or approaches which can be used to make disseration (good examples: biographies of known people, some books which develop imagination, like 'Alice in Wonderland' etc.).

Reservoir neural network (a concept)

Intro
Sometimes rather interesting ideas come into my mind and I give myslef a promise to implement them and then put them aside, so that they just piled on backstages of my memory. Some details can dissappear with time, hence I think it's worth writing these ideas somewhere so that later they could be useful for me or somebody else.

Description

Goal: General-purpose learning with self-adaptation of the artificial neural network’s (ANN) structure and parameters.

Idea: The idea is inspired by influence of biochemical reactions and spatial relations on brain’s functioning, which is not considered in most known models of ANNs. To implement this ANN is placed inside an expandable virtual 2d or 3d reservoir which can have different zones affecting the signals transmitting, activation of nodes, learning rates etc.

The network’s structure and reservoir parameters change over time in the following ways:
- New nodes and connections can appear.
- Some nodes and connections can be removed dynamically (to implement forgetting and/or giving other nodes more space to function).
- Nodes can change their location, moving towards “coherent” nodes, so that nodes with correlated outputs would tend to be located closer organizing structures.
- Connections can change their weight and length (the latter should have some impact on signal’s transmitting).
- The size and form of different zones in reservoir change to affect ANN functioning without training or corrections.
- Reservoir can have regulators defining number and parameters of zones and which can be changed either externally (by user or some control-program, it models the case of eating, making some physical actions and psychology), or by some law (models change of daytime, biorhythms etc.), or from the current state of nodes within the reservoir (models self-control and self-regulation). Or combination of all these can be used.
- The reservoir’s size can change to house as many nodes as required or to shrink if there’s too much of free space. This is required to implement evolution of the ANN.

Extension 1
The scheme above gives a general outline for dynamical creation and training of ANN in complex environment. This extension provides the idea for building hierarchy within the network. There are several variants (which can be used simultaneously):

1. Embedded reservoirs. When new node appears it is placed in its own reservoir if this node is located rather far from all other nodes. This reservoir can have its own zones and reservoirs which are (partially) independent from the parent reservoir. Each reservoir can have only one parent, while each parent can have multiple sibling-reservoirs. The decision whether new reservoir should be created can be made via judging the minimal distance between a new node and existing ones. If this distance is less than some dist_critical then new reservoir is created. For the embedded reservoirs critical distance can be reduced logarithmically and can optionally depend upon reservoir’s size.
2. United nodes. As nodes with correlating outputs move towards each other then when maximal distance between such nodes is below some threshold these nodes can be separated by creating new reservoir in their current location and placing them inside it. Again for the embedded reservoir the value of threshold for uniting its nodes can be reduced in logarithmical scale.

The reservoirs described above can be used further as independent units, i.e. they can treated as single nodes or be copied/deleted, form their own reservoirs by the 2nd variant etc.

Problem with meta-knowledge
I position this concept as an approach to implement data-independent learning which deals with different types of input data and can solve learning, inference, recognition and prediction problems. But it’s unknown how to make such a system to decide which kind of data or task it faces. E.g. this system should somehow get to know about this variety of problems and data. In other words the system should be able to form and extract meta-knowledge. And implementation of this might be a big problem. I believe that to check this at least some.

Some thoughts on recognizing systems

Here are some thoughts just to organize my ideas for possible future research and clarify some problems and questions. The general problem is building a classifier (recognizing) system, which could evolve and learn to get new knowledge hopefully from various sources. This is a well known and a very challenging problem, which is not solved yet though a lot of people proposed their own solutions (like CEC, Phaeco, Adaptive Resonance Theory, ontologies, large-scale knowledge-based systems, biology-inspired approaches etc.). They are all good to some extent, but they also miss something, which makes them non-universal. I do not claim that I can propose my own solution (and quite possibly I'm not the person who will do this), but here are just some thoughts and classifications sketches, which are useful to think about.

===========================================
All learning systems can be divided into 2 major classes:
1. Supervised - there is a "teacher" which tells the System what output it should yield on a given input.
2. Unsupervised - the System itself to decide what to do with an input data looking for possible regularities. After the training such Systems can be used either "as is" (like Kohonen's maps) or their output can be further processed, e.g. mapped into classes space like in Echo-State Networks or Hawkins Networks.

===========================================
Input data is in general falls into (combination of) the following types:
1. Permutation-invariant, e.g. if we swap some values in object's description the object's class will remain the same. This is typical for images analysis problem when rotation or moving of the object on the image should not change the recognition result. This corresponds to the non-ordered feature vectors case. Some times this type of data doesn't demand full-scale permutation invariance, for example when recognizing hand-written text it's rotation or panning should not affect the recognition, but swapping pixels at random can distort the input critically.
2. Not permutation-invariant. Just the opposite case when order of feature vector components is significant which is often met in traditional setting of the classification problem, recognition of speech, processing time-series etc.
3. Scale invariant. This is a somewhat tricky thing. Input vector size remains the same but its spatial and/or temporal resolution changes. The example is recognition of letters and numbers from their images or recognition of fastened or slowed speech. The System, which is able to deal with this type of data, should adapt somehow to the characteristic scale of the input. In image processing this is sometimes reached via using the local maxima of Laplacian-of-Gaussian or Difference-of-Gaussian.

Note, that input data can be either of (1st and/or 3rd) or 2nd types, which means that types (1+3) and 2 are exclusive and their simultaneous processing demands either different subsystems or a kind of switching (with adaptive recognition of what type of data is being introduced on input).

===========================================
Most modern recognizing systems are just mere numerical windmills: they process numerical data using ad hoc + experimental assumptions like "if we have significant change of variance than the object under consideration changes its state", "it's enough to utilize information about lines orientation to recognize image category". But (almost?) no system have "semantic layer", which could consider interconnections between different classes and notions, organize them into sentences and statements etc., and which could affect the result of recognition. I believe that all researches feel that we've got to use semantic information as an important element in recognition process, but no good solution has yet been proposed. The problem here is twofold:
- it's extremely difficult to build such a system, because we do not have enough knowledge of what cognitive features are and how they can be modeled in a full-scale.
- most successive system rely on mathematics --> we will (almost?) definitely use numbers. Yes there are approaches which take into consideration fuzziness of the data, but such systems are still strictly governed by numbers, which define their vital parameters.

The big question is whether we can numerically approximate human's brain (or whatever is used for thinking, storing memories, setting goals, wishes, creating emotions and so on). There've been a lot of arguments on this theme, but the answer is unknown.

===========================================
I believe that the importance of multi-layered recognizing systems have been acknowledged for several past years. There are "deep-learning" architectures of neural networks (like those used by Yann LeCun and Geoffry Hinton), Hawkins networks, many good systems have a multi-component organization with separate stages of processing and recognition. However such system are still non-universal in terms of input data types (see text above) and solved problems and really important questions are still unanswered:
- How many layers to use for different problems? And how many different problems from the layers number points of view exist?
- How these layers should be formed?
- What components they should include?
- Is there a set of universal components (like nucleotides in DNA or subatomic particles)? And how strong they are "granulated" (how small they are)?
- How should we connect different layers?
- How to organize "natural" hierarchy so that a multi-layered architecture could be considered as a single layer?
- In brain spatial relations, bio-chemical and physiological  processes play very important role. How can we utilize our knowledge about them?
- How can we make such multi-layered systems in a fully automatic unified manner?

Since there is no system or approach which solves these problems automatically, we all have "hands to kiss and babies to shakes" ((c) by LeChuck), let's work :)