Particle filter demo

Solving Caesarian cypher using particle filter graph alignment

UPDATE
- I fixed an error in laplace smoothing (was using only n, instead of k * n for divisor :-) )
- I also changed weight calculation. I found out, that 1 / distance is kind of aggresive (non-linear) meaning that the more closer some point is, the greater is the magnitude of its weight gain. And this is not exactly what we want, since it is actually more probable, that the very close fit at some point might be a result of noise rather than useful information. So I changed it to 1 / sqrt(distance). It still rewards the close matches, but it is less aggressive and it actually give better results even with greater smoothing. I also played with some maxDistance - distance thing, but it turned out to be too complicated so I went for the sqrt option. But it is good to see, that the way of evaluating the measurement data is also imporant.
- Visualization graph now shows not only non-normalized weights per particle but also sum of normalized weights (4th row) for all particles on that letter index, which shows how likely are these particles (particles corresponding to this letter index) to be sampled (recreated). (For example if there are 3 particles with 0.2 normalized weight, than the sum of that letter index would be 0.6, meaning that it is very likely that at least some of these particles will survive). You can see, that if some letter index has big non-normalized weight (meaning the frequency is very close), but there are very few particles (small size of the 5th row), the resulting normalized weight sum is very small, meaning that even though this index is good for this measurement, it is more likely to die. What it means is that it is good for THIS measurement, but this index overall didn't prove to be very consistent. You can compare the difference on the beggining, where there is same particle count for each letter index (and therefore the normalized weight correspond to the non-normalized) to the situation where some of the indexes are dominant (have greater number of particles, and therefore the indexes with small particle count get a smaller normalized weight even though they receive big non-normalized weight.).
- Added graph at the bottom that show the final frequency graphs alignment after particle filter procedure. You can try how the 1 / distance weight can get more easily deceived by close point matches when using higher k and that 1 / sqrt(distance) is still not ideal for such higer k's.
- Added option to smooth also the original frequency graph. The idea is, that when we smooth the the message frequency, smoothing also the original frequencies makes the graphs similar in terms of shape and since we don't have many data (that's why we used smoothing), this might be useful, because we look for the distance from original frequency.

UPDATE 5
- Fixed some bugs - There was forgotten 3 multiplier for particle count so there was 3 times more of them than specified. Now it seems 1 particle for letter is not enough, more particles are better. Also there was an error from last update. When original alphabet smoothing was on, in the visualization remained weights of particles, that no longer existed (3th and 4th row had bubbles whereas 5th had none).
Thread on reddit: http://www.reddit.com/r/aiclass/comments/nlqsb/particle_filter_for_caesarian_cipher_nlp_exercise/
Encoding tool: http://rumkin.com/tools/cipher/caesar.php
Secret:
Smoothing k (of message letter frequency): Smooth also original alphabet
Probability of particle shift fail (control noise ratio):
Particles per letter:
Non-normalized weight calculation: 1 / sqrt(distance) 1 / distance

Decoded: the first conference on the topic of artificial intelligence was held at dartmouth college in this year.

Below is an animation of particle filtering process. At the top is original alphabet frequency (bigger size, bigger letter frequency). Second is the current measurement (frequency of letter in the encoded message). In the middle is computed non-normalized weight for single particle at specific index (1 / distance of measured frequency vs frequency of alphabet letter at that location). You should see, that the original letters which have similar frequency to the measurement result in bigger weight for corresponding particles. An at the bottom are current particles (bigger particles means more particles). You should see, that if the computed weight at specific point is big, the particles corresponding to that point will prosper (meaning that in the next step, the size will increase because there will be more of them). On the other hand, if there is lot of particles (big size) and their weight is small, in the next step they will start to die out (size will be smaller). The particles that are consistent should take over other particles after some time (big size and big weight = even bigger size).

Visual made easy with help of Google Charts API
Gallery: http://code.google.com/intl/cs-CZ/apis/chart/interactive/docs/gallery.html
Playground: http://code.google.com/apis/ajax/playground/#motion_chart