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.