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