Killing me softly with this song :)

That's very cool: DARPA is sponsoring a research on the intelligent software that can play jazz. The article explains the reason for that, but to me it looks more like a smart PR move to attract public attention. The computer writing stories would sound much more feasible, because it involves tracking several characters, their motivations, events, consequences, predicting responses etc. And the application, aside military purposes, could be quite fancy as well (and lucrative!): making an engine to control NPCs in RPGs and create new quests/substory plots. Many companies have claimed that they have a special engine for this, but in reality the implementation is usually very heavily scripted without much improvization.

Or it could be computer that draws pictures, which also requires improvization. HyperNEAT can do that :) And its predecessor was even used in a simulation computer game to command shooting bots.

One more book

It is amazing how many great things we can find on the Internet. About 15 years ago learning a complicated topic would be quite challenging mostly because the amount of information was not that big and the learning at times resembled solving puzzle with most parts missing.

These days it is still challenging (human factor, heh), however the information is all around us, and now arguably a greater problem is to find the time to stop searching & collecting and start reading / programming.

In a meantime, here is an officially freely available book/technical report from very good researchers:

Deng L, Yu D (2014) DEEP LEARNING: Methods and Applications. MSR-TR-2014-21. NOW Publishers.

Learning about Self-Learning

I wanted to write a post on self-learning for already quite some time. And today I stumbled upon a very interesting research paper, that reviews how students perceive their self-studying, what are common pitfalls and mistakes. The paper is:

Bjork RA, Dunlosky J, Kornell N (2013) Self-Regulated Learning: Beliefs, Techniques, and Illusions. Annu. Rev. Psychol. 64:417–44

It is a psychological paper, written in a very clear language, which is easy to understand for non-professional, as long as you know basic terminology from cognitive sciences. One of the major conclusions there is that people in overall are not really efficient as self-learners. The main reason for that is biased decision-making when judging efficiency of learning techniques and methods. In particular the paper says that spacing and interleaving is often overlooked and underestimated, whereas methods that improve short-term memory (like cramming) are perceived as more advantageous due to their quick benefits.

The Importance of being DRY

When I have time I have fun solving problems from the Euler project. So far I have 15 problems solved, but I started not so long ago. The thing is that, as I noticed, the execution time from most solutions is not good according to the forums. Also here is an example of the discussion about the Problem 12, where the answer got 10 sec to execute, while my solution takes < 100 msec. And in overall I manage to write quite fast code in C#. Here are some results (problems 1, 5 and 15 were solved with pen and paper):

Problem	2	3	4	6	7	8
Time, msec	0.002	29.848	5.689	0.009	0.231	0.440

Problem	9	10	11	12	13	14
Time, msec	0.331	225.789	0.424	93.75	0.022	577.291

And, to be honest, I don't consider myself as a super programmer, even though I might be not bad at all, >20 years is quite a period. But from my perspective this is rather a problem of many (younger?) people to not understand/misuse few (in fact one) important things:

1. DRY (Don't Repeat Yourself) principle applies not only to the design of software, but to computations as well. I saw very many examples of the code with two nested loops, where inner loop runs computations that can be easily done in the outer loop.
2. Dynamic programming and look-up tables. In fact, these two are also implementations of the DRY principle, by reorganizing the algorithm in such a way, that the computations are made only once.

And this fact makes me wondering about the reasons, that ventually lead to not-so-fast code, which we all sooner or later have to deal with via slow UI, game engines, digital cameras, web-pages loading, image processing, and so on. Even well-known commercial software can use naive implementations of the algorithms, that can often be speed-up at least 2-3 times by purely algorithmic means, and without using parallel computing. After thinking a bit, possible reasons for this might be:

1. Incorrect understanding of the programming as something that requires knowledge of technology/programming language rather than skills and good foundations in algorithms and data structures. There are lots of new and interesting programming languages and technologies, like Clojure and Hadoop, which are actively advertised and attract lots of attention. People tend to like languages, which are either trending or have an expressive power, which at times allows to implement tricky algorithm in 1-3 lines of code. What is forgotten here, is that learning a language is basically learning a syntaxis, which does not really improve the programming skills. It is like buying a new cool machine or tool to build a house, but if you are bad at architecture and finishing, this tool will not help much.
2. Not enough attention to mathematics. Again not so many people nowadays connect programming and software development with mathematics, even though just 60-70 years ago programming was only for the people with strong mathematical background.
3. Shift of the paradigm towards parallel computing. It is getting more common to think that to make computations faster, we need to have a parallel version. About 10 years ago computational clusters were very popular, nowadays GPGPU is adopted by many. Even though there are multiple cases, when this line of thinking is true, but this somehow shadows algorithmic improvements and organization of computations in a smarter way.
4. Lack of fundamental knowledge in programming. How many younger programmers know about loop invariants and can correctly state them? They can discuss about Hadoop, Node.js, Clojure and other cool things, but not so many read "A discipline of programming" by E. Dijkstra. Even much more simple example: I was surprised to know that some programmers around my (!) age were not aware about binary mode of the file reading.
5. Technological 'corruption'. The reality is that we have gigabytes of RAMs, gigahertz in CPUs, and terabytes on hard drives. This is more than enough for a huge number of problems, and allows not to care about resources consumption while solving assignments. And this might lead to 'reckless' programming, like the code for multiplication of 100x100 matrices which requires 10MB of memory. Nobody cares, 10MB are peanuts. But what would happen if the same code was written 15 years ago? And what happens, if the matrix dimensions grow 100-fold?
6. Too big hopes on assembler language. It is not so rare to see on a project web-site or in the publication that 'critical parts of the code were written in assembler'. While being good by itself, assembler does not make wonders. Yes, it reduces the overhead, brought by compiler, due to tight control over all operations and variables. However if the underlying algorithm is not good computationally and there are repetitive calculations, they will stay in the assembler code as well.

Can this be fixed? Yes, of course, and I believe that there is more good code than a bad one. And hopefully this proportion will remain and the projects like the Euler Project are very helpful for this, because they make people to think about their code and skills by analysis of other solutions. And this is good :)

One day it can play Zork :)

Very nice paper from famous CSAIL laboratory (sorry for tautology) at MIT:

Narasimhan et al (2015) Language Understanding for Text-based Games Using Deep Reinforcement Learning

In two words: the paper describes a way to teach a machine to perceive game situation through a textual description and make correspondent actions. This is a tough task to do due to complexity of the natural language processing. The algorithm makes use of the Deep Q-Network by Mnih at al (2013 and 2015) and Long-Short Term Memory units. Interestingly an experiment for the transfer learning is also done, that uses networks parameters learned from settings A in the setting B, showing premise of the approach.

Deep reinforcement learning

Cool paper on parallel implementation of a  deep reinforcement learning to play Atari games:

Nair et al (2015) Massively Parallel Methods for Deep Reinforcement Learning

The approach itself, called Deep Q-Networks, is described in these two papers:

1. Mnih et al (2015) Human-level control through deep reinforcement learning
2. Mnih et al (2013) Playing Atari with Deep Reinforcement Learning

The training idea is very generic and human-like: the networks 'sees' a screen and decides which action to take. The action changes the game state, which leads to change of the game screen, etc. Set of actions is different for different games, and what is important is that most (all?) of them are arcades. Because an Atari 2600 emulator is used, the network has enough time to make the computations.

By means of natural selection

I like Tournament selection in evolutionary algorithms. There are a lot of different selection schemes, each of which can perform better for the particular cases. However, the Tournament selection is easy to implement, flexible, and gives some chances to not very fit solutions to take part in the competition. And this selection can be easily adjusted to both minimization and maximization problems. Somewhat arguable feature is independence on the fitness values and their signs, but so far for me this is more an advantage rather than a weakness.

The necessity to cope with both minimization and maximization problems within one package/class library sometimes can be annoying, that is why, many implementations stick to only minimization problems. Leaving it to people, who use the package, to transform the fitness values, the way they find appropriate. There are many ways to make this kind of transform, but no ultimate one. However with selection methods that do not depend on the sign and the value (like Truncation or Tournament selections) this problem simply does not exist. That is why there are also a lot of packages that use these variants of selection.

Some thoughts about learning

When we learn some new subject, I believe, there are always some common properties of learning, regardless the field of the subject. Here I'll try to consider some of them to summarize the process of learning itself, using some notions from system thinking as it is greatly unites knoweldge about systems and their interactions, and of course the subject to learn is also a system. And I'll be very abstract.

So, if we want to learn the subject we may want to be aware of the following:

- The definition of the subject. It is required not only to recognize the subject, but also to recognize something, which is not a subject, to know its 'borders' and distinctive properties and features. It is also useful to know the conditions for the subject to exist (if approriate).

- Which parts constitute the subject? Sure enough every part can be quite complex, i.e. a standalone subject to learn.

- How these parts interact and relate to each other?

- How the subject interacts with other subjects, which primarily are out of scope of the study?

- What are inputs and outputs for the subject and all of its parts?

- What kind of information and materials are transferred through those inputs and outputs?

Why these are important? Because if we are really serious about learning, we can not learn only one part and ignore the others (like learning speaking without learning grammar). It is not only incomplete, but can also leads to incorrect understanding of the subject, because the subject is a system, and by throwing away some part, we are modifying this system (keep in mind system emergence feature). Sometimes it makes us unable to communicate with other people (without knowing some 'auxiliary' definitions from other fields it is generally impossible to write a proper mathematical statement).

Some examples:

1. Language learning.

Definition: usually there is no definition, but it is good to understand how the language relates to other languages, what are differences and similarities. This is usually given in most textbooks and is intuitively learned during the process.

Parts: grammar, phonetics, vocabulary, morphology, speaking, listening, writing.

Interactions: quite straightforward and common for most languages.

Other subjects (possible variant): history of language, history & geography & culture of a country. Of course it is not required to know all of these to the full extend, but at least knowing some key events and ideas is useful (and not only from the language learning point of view!).

Inputs and outputs (just a few): ears, mouth, books, video, songs, radio, talks.

Information and materials: meanings, sounds, sound waves.

2. Learning some mathematical subject (like probability or functional analysis).

Definition: should give a general picture on what kind of problems are considered by the field and by what means.

Parts: definitions, properties, theorems, proofs, rules, algorithms, exercises, open problems, applications.

Interactions: logical connections between different parts. Very crucial to understand the subject.

Other subjects: history of the subject, main contributors and their results, prerequisites, subjects that can be learned using knowledge from learning the current subject.

Inputs and outputs (just a few): timetable, locations, Internet, eyes, ears.

Information and materials: ideas, properties, specific skills (like integration), books, videos, publications, lecture notes.

3. Learning musical theory.

Definition: to know what for musical theory gives and what happens if we don't study it?

Parts: notes, intervals, chords, harmony, styles.

Interactions: straightforward.

Other subjects: history of musical theory, playing a particular instrument, musical software.

Inputs and outputs (just a few): books, Internet, ears.

Information and materials: sounds, compositions, songs.

How can we use the information like this? If we want to learn something we should attack the subject from all the possible directions, because the parts of the  subject are not independent, they overlap significantly. Thus we can generate synergistic effect, but to do this we first should know the options, otherwise it will be random and less effective. The other important thing is that learning requires memorizing and by looking at different things from various angles (like reading, listening, writing, practising) we intrinsincally repeat them.

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 NexGen Algorithms

Modern evolutionary algorithms do not learn. They can be adaptive during the search of solution, but when the run is over, they forget everything and if we re-run the problem, the algorithm starts its work from a scratch. This is normal for algorithms, but if we look at all living beings we'll see that they do not forget everything that catastrophically! Yes, single experience can be resultless, but after trying to solve some problem for hundreds and thousands times a new knowledge and experience eventually emerges. This is the way people learn to walk, speak, handle spoon and many other things. As people get older their past experience helps them to learn things easier (if these new things correlate with their experience).
From the other hand there are incremental learning algorithms, which are being more or less actively developed for the last 2 decades. Those algorithms can learn in complexifying and/or dynamic environments, which makes them more adaptive and they do not suffer that much from 'afterun amnesia'. There are certain problems though, like 'catastrophic forgetting', when after several updates algorithm totally forgets what it learned initially and starts behave in a new unexpected way. Well, that's normal for humans, it's just like if some person learned to speak English in a childhood and after living in France for years speaking in French this person forgets its first language. I believe that if catastrophic forgetting is not very fast then it's not a major problem. The larger issue here is that incremental earning algorithms usually are applicable to a certain domain only. That is they do learn something and collect past experience, but this experience is almost useless for solving other problems. So 'increamental learning' can be called something like 'temporal adaptation' and is good in its way, but still far from true learning algorithm. And, yes, increamental learning is usually for machine learning, but not for optimization.
The ultimate goal here may be in creation of the algorithms, which simply learns from any problem and extracts some general abstract regularities and rules to improve its performance for future tasks. This is closely related to the meta-learning concept and I believe that this can be done if some external trainable control system is attached to the algorithm to guide this algorithm's behaviour. This is a very amibitious task, connected with creation of very adaptive algorithms and probably one of the milestones to overcome on the way to true AI, since some implicit method 'to learn how to learn' is already built-in by evolution inside living organisms (animals can improve their skills!) and is essential for survival and for emergence of highly-organized intelligence.
There's a well-known meta-systems transition theory by V. Turchin which states that system enters a new level of development when a meta-level control system appears. For the existing evolutionary algorithms some origins of such systems can be found, like rules for adaptation or some heuristics like: if we move in the same direction, then increase movement speed; or try to cluster variables to understand their relations for proper optimization. And the next big step here is possible unification of these heuristics and adding memory fo EA, so that the algorithm could remember what problems it already solved and what were useful and useless rules. Having this memory it could be possible to recognize some common parts between problems (like, 'hmm, I solved something like this before, and I probably should apply correpondent set of optimization rules'). That may be my fantasy, and there are a lot of open questions (how to store information about problems features and compare problems of different dimensionalities etc.), but this is a real task for scientists, which probably can boost development of algorithms. That's why NexGen :)    

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.

Gradiention Day

This is a sketch for a review on meta-heuristic tricks for learning properties of a search space. More formally, a lot of advanced (and not so much) algorithms try to figure out an information about local gradient for more efficient evolutionary search. This is surely feasible, because (ideally) the gradient shows the best direction to move towards local optimum and most numeric optimization methods use this information. The question about how to get away from a local optimum concerns another (although associated) problem and is not considered.

It's worth noting, that getting gradient info for noisy functions can be difficult and requires some statistical processing, which may result in several alternatives for the best direction (not obligatory collinear). Probably fuzzy logic could be of help here. I also assume that objective function has local trend, i.e. that for each point *there is* the best movement direction, which is at least good for some not very small neighborhood, because otherwise finding gradient doesn't make sense. One can say that this means that the function can be approximated by some smooth function with the same global optimum.

We can find 2 groups of methods, which learn gradient information:
1. Explicit gradient learning. There are formulae for gradient approximation, which are used during recombination or variation operations.
2. Implicit gradient learning. These methods simply do not tell directly that they are learning gradient, but they are sort of 'I'll-know-it-when-I-see-it'.

Examples of the first group are: EA with direction crossover and Pseudo-Gradient, CMA-ES, many real-valued EDAs and (h)BOA algorithms.

For the second group examples are: Swarm Optimization Methods, Differential Evolution.

In my opinion, the meta-heuristic method can be aknowledged as 'gradient learning' if there is sort of memory for the best movement direction.

Where are conventional real-coded EAs? In my current understanding it should be placed into the 2nd group. Here is my motivation: many EA operators do not look for gradient, but simply search for better solutions in vicinity of parent individuals. Most operators do not 'remember' good searching directions. But there is a selection, which selects in which direction the population evolves and thus follows the gradient. Probably many EAs should even be treated as 'implicitly implicit' gradient learning methods :).

Up to now only continuous spaces were considered, because gradient is natural there. What about binary spaces? Or spaces of graphs, computer programs, agents policies or neural networks? I believe that the gradient notion can still be applied there as long as there is a proper metric over the set of representations.

Recall that there's a large class of finite-difference methods, which quintify the space making it non-continous, but can still be succesfully applied for continous modelling problems. It can be also argued that one of the most used variant of the Taylor expansion has linear form from which the approximate gradient can be calculated.

So the largest problem for defining gradient in non-continous spaces is setting a good metric. By this 'good' word I mean that it should not be just everything, which satisfies metric properties, but it also should reflect the problem's properties. For example, setting metric for directed weighted graphs for TSP problem is not the same as setting metric for directed weighted graphs for evolution of neural networks. That's the issue. An interesting question: if a kind of 'approximate' metrics exists, which is metrics, but without the whole pack of desired problem dependent properties?

On representation of candidate-solutions

Recently I've come up with an idea that traditional approach for programming EAs may have a strong alternative.

In a traditional way we are dancing from the EA perspective, that is, there are individuals = candidate-solutions, they form population, which is modified by EA, consisting of various operators and a (posssibly hardcoded) scheme for their application sequence. Problem domain is somewhat alien and is communicated via fitness function. If some unusual representation of the solution is used (like Gray-coded strings for real-valued optimization problem), then genotype->phenotype transform should be made to evaluate an individual's performance. This transform is often made somewhere inside a fitness function, which means that fitness function can be divided into 2 sections:

1. Transform of the solution to the representation, which can be evaluated, even if a single method is called.
2. Evaluation itself.

Many implementations consider that problem lives in a problem environment, which is often convenient for control, adaptive behaviour and A-Life applications, but candidate-solutions are still are part of the EA.

We can say that here fitness function is a 'friend' for EA, which means that EA can work with any representation and the function performs all the necessary transformations itself or that individuals can convert themselves to different phenotypes (arrays, matrices, networks etc.). It's very convenient for EA, but not very convenient for the problem, we have to track whether individual can be transformed to the proper representation for fitness evaluation.

Nothing is wrong with this approach, it's good, but there's another decomposition variant.

Suppose that candidate-solutions are independent things. That is they have two sides (or faces/facets): one for EA and the other for a problem. The first side can be binary chromosome, or Lisp expression, or some graph representation, whatever the EA operators can work with. The second side is for the problem: real-valued vector, neural network, agent's policy representation, whatever the fitness function should handle.

In other words, candidate solutions are no longer parts of EA (although they can still be named individuals, particles, and so on), neither they are parts of a problem. This can be convenient for both EA and a problem, because there's no need to worry about conversions and transforms. When EA side is set, the problem's side can be updated at once, or on the first demand (implementing so called 'lazy' programming concept). If 1-to-1 mapping between genotype and phenotype exists, then this transform can be reversed and if problem's side is updated, for example by some local search algorithm, the EA side can be updated as well.

There're no miracles, it just means that all conversions are localized and they should be implemented explicitely, but neither EA nor problem's side should worry how it's done and by what means.

If genotype and phenotype are the same (real-valued EAs, direct graphs representation etc.) the individuals can be made either one-sided (I would call it 'Moebius representation' ;)) or two-sided, but with no difference between sides.

And as adopted, some pros and cons of this approach:

Pros:

• Can appear as two distinct objects at the same time.
• Potentially faster (because phenotype can be computed when genotype is changed)
• More natural (genotype + phenotype)
• Objective function does not need to support different encodings, it obtains the object it's meant to evaluate --> Easier to adapt for 3rd party applications
• Possibly easier to parallelize because problem side representations are independent and there very small chance of their conflicts.

Cons:

• Requires more memory, because problem-side representations are stored for each EA-side representation.
• Adds extra interaction layer between EA and a problem.
• Probably more code to write due to more complex structure of candidate-solutions.
• The candidate-solutions become 'heavier'.

Anyway, I think this idea of two-sided representations is interesting.

P.S. Oh, it's possible that I've just rediscovered someone else's idea. Yeah. What if Plato was right? ;)

A few hints on scripting

Currently one of my tasks is creation a scripting engine for .NET which would satisfy the following demands:

• Extendable syntaxis (ability to add new, possibly very exotic, syntaxical constructions).
• Dynamical typization (in order to simplify the scripting writing process, because language is oriented on non-programmers as well).
• Full execution control (for external control over the script execution).

Although the best solution would be to find an existing implementation and use it, but googling lead to either Lua/Perl/Python interopearbility (which doesn't satisfy the 2nd criterion) or to use of the .NET classes for dynamical compilation of the code.

After some time I did almost all the work by myself and here are some advices, which are hopefully useful (unless you had a compilers theory course and a good practice and already know much more):

• For quick introduction in scripting read correspondent chapters in books on games programming. They will give the baseline terminology and the overall scheme of what-to-do given a script text. Books on compilers theory are good, but if you need a hands-on approach then they probably contain too much theoretical information.
• Do not try to solve all problems at once like "Ok, I've got a script and now I'm simply going to process and execute the raw source. Nothing serious really, because I can easily see assignments, function calls, conditions etc., so writing a program, which would do the same, is a piece of cake". This is a suicide, because a problem is much harder than it seems. Just think about code like: a = sqrt(abs(c - d[i + 1])).
• Simplified (a bit) source processing procedure includes: (1) removal of comments; (1a) concatenation of the whole script into a single string; (2) tokenization (breaking the script into atomic entries like operators, brackets, identifiers etc.); (3) creation of a parse tree (http://en.wikipedia.org/wiki/Parse_tree), which define a kind of 'execution atoms', and the order at which they should be processed; (4) optimization of the parse tree.
• It's convenient to create a special class for tokens with fields like Contents and Type. The latter defines what kind of token it is (keyword, operator, bracket and so on). This will make life much easier on the parse tree building step.
• BNFs (http://en.wikipedia.org/wiki/Backus-Naur_Form) are really-really-really useful things, especially when describing a formalized grammar. You can represent a BNF as collection of arrays consisting of tokens. Big advantage is that BNFs has inherent recursion property and allow reuse of one BNFs as part of other BNFs (so the good KISS and DRY principles hold).
• BNFs should be applied for building of a parse tree given a collection of tokens. You just start from the very beginning with BNF for the entire script and use recursion. The complex part is that it's not known beforehand, which BNF suits current collection of tokens the best, so you'll have to try any suitable BNF you have, which start from the same token. But there is a way to make the problem easier, see advices below.
• Handling recursively embedded BNF is not a simple thing and your brains will boil, so be very careful with this. Use loop and class invariants (http://en.wikipedia.org/wiki/Loop_invariant) for functions to control the process. But you'll be surprised how little code it takes to make things work.
• Use dynamic programming (http://en.wikipedia.org/wiki/Dynamic_programming) approach for finding BNF, which suits current list of tokens best. This means that if you found that some subset of tokens is described by some BNF then you can mark the first token in this subset so that not to consider it again and again when trying other BNFs. Otherwise you'll end up redoing some work over and over and it's very likely that you'll get a stack overflow error.
• Probably the most amasing thing about BNFs is that when you need to extend a syntaxis, you'll just need to extend the set of BNFs used during a parse tree building procedure. And taking that BNFs can be read from some file, it's even possible to extend the grammar *without* recompilation of the program (in case you've written everything correctly, use loop and class invariants!).
• The drawback of using BNFs is that arithmetic and logical exressions are written in a 'direct' representation, not in the Polish notation (http://en.wikipedia.org/wiki/Polish_notation), hence optimization of the tree is required, because otherwise you'll have to make the transform to the Polish notation at each scripting execution, which is really unwise.
• Parse tree is enough for execution of the script.
• It's convenient to keep additional information in parse tree nodes about their BNF (if any). This information can be used to handle execution of conditoinals etc. Moreover you can specify special external handlers, which are called by BNF names. Hence it's possible to obtain a control over script execution, which may be convenient for setting external break points or specific execution rules.
• Script execution is guided in terms of the program state (http://en.wikipedia.org/wiki/Program_state), which include (among others) global and local variables data. You can add any extra information you need for the program state (call stack, current parse tree node, environment variables etc.).

Good news is that my implementation (not final though) of the scripting engine is available as a part of the MentalAlchemy project (http://code.google.com/p/mentalalchemy/). See evooelements subproject, molecules section. It is still lacking some things like local program states and handling of some BNFs, but I'm planning to finish them in 1-2 weeks.

Two diagonals

There is a matrix bidiagonalization algorithm in a good book Golub G.H., Van Loan C.F. Matrix Computation. 2nd edition. The John Hopkins Univ. Press, 1989, which relies on the Householder's reflections to create zeroes below the lower triangle part of any matrix and above the upper subdiagonal so that the resulting matrix would be something like:

This matrix is usually be used for the Singular Value Decomposition by elimination of values above the main diagonal (so that the resulting matrix performes a required scaling). There are two interesting moments:

------------------------------------

1. The algorithm 5.4.2, which performs bidiagonalization, in the book seems a bit wrong. Namely two lines can be omitted without harming the result. Those are: A(j+1:m,j) = v(j+1:m) and A(j,j+1:n) = v(j+2:m)' (in Matlab notation). These lines perform copying of the Householder's vector into the matrix, but this is not required because aff ected column and row already nulli fied by the Housholder transform and are not changed as the algorithm goes on. So these copyings simply do something wrong. Here is an example from the book: for input matrix

the following bidiagonalized matrix should be obtained:

But implementation of the algorithm yields the following result:

Note that values on the main diagonal and the upper sub-diagonal are almost the same, while there are a lot of "undesired" non-zeros as well (the di fferences are due to use of single-precision calculations). There are also signs misplaced, but I haven't found the source of this error (?) yet.

Now removing the copying of the Householder's vectors we obtain:

------------------------------------

2. I suppose that there is a good way for calculation of the matrix rank using this bidiagonalization procedure. There a lot of ways to calculate the rank, the simpliest one is to use Gauss eliminations, but it's not numerically stable, and a more reliable and convenient way is to use SVD and to calculate singular values larger than some threshold. One of the typical ways to calculate SVD is to use Golub-Reinsch algorithm, which firstly transforms the input matrix to the bidiagonal form (!) and then eliminates non-zeroes above the main diagonal. My idea is that the values on the main diagonal of bidiagonalized matrix can tell the number of singular values. If it's true then the matrix rank calculation can be performed via using bidiagonalization and then calculating non-zero values on the main diagonal. For the example above the initial matrix rank is 2 and the number of non-zeroes on the main diagonal of bidiagonalized form is also two.
------------------------------------


I may be wrong for these two notes, so any comments and critics are wellcome :).

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