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.