markov_chain.md

   1 # Markov Chain
   2
   3 Markov chain is a relatively simple [stochastic](stochastic.md) (working with probability) mathematical model for predicting or generating sequences of symbols. It can be used to describe some processes happening in the [real world](real_world.md) such as behavior of some animals, Brownian motion or structure of a language. In the world of programming Markov chains are pretty often used for generation of texts that look like some template text whose structure is learned by the Markov chain (Markov chains are one possible model used in [machine learning](machine_learning.md)). Chatbots are just one example.
   4
   5 There are different types of Markov chains. Here we will be focusing on discrete time Markov chains with finite state space as these are the ones practically always used in programming. They are also the simplest ones.
   6
   7 Such a Markov chain consists of a finite number of states *S0*, *S1*, ..., *Sn*. Each state *Si* has a certain probability of transitioning to another state (including transitioning back to itself), i.e. *P(Si,S0)*, *P(Si,S1)*, ..., *P(Si,Sn)*; these probabilities have to, of course, add up to 1, and some of them may be 0. These probabilities can conveniently be written as a *n x n* matrix.
   8
   9 Basically Markov chain is like a [finite state automaton](finite_state_automaton.md) which instead of input symbols on its transition arrows has probabilities.
  10
  11 ## Example
  12
  13 Let's say we want to create a simple [AI](ai.md) for an NPC in a video [game](game.md). At any time this NPC is in one of these states:
  14
  15 - **Taking cover** (state A):
  16   - 50% chance to stay in cover
  17   - 50% chance to start looking for a target
  18 - **Searching for a target** (state B):
  19   - 50% chance to remain searching for a target
  20   - 25% chance to start shooting at what it's looking at
  21   - 25% chance to throw a grenade at what it's looking at
  22 - **Shooting a bullet at the target** (state C):
  23   - 70% chance to remain shooting
  24   - 10% chance to throw a grenade
  25   - 10% chance to start looking for another target
  26   - 10% chance to take cover
  27 - **Throwing a grenade at the target** (state D):
  28   - 50% chance to shoot a bullet
  29   - 25% chance to start looking for another target
  30   - 25% chance to take cover
  31
  32 Now it's pretty clear this description gets a bit tedious, it's better, especially with even more states, to write the probabilities as a matrix (rows represent the current state, columns the next state):
  33
  34 |     |  A  |  B  |  C  |  D  |
  35 | --- | --- | --- | --- | --- |
  36 |  A  | 0.5 | 0.5 |  0  |  0  |
  37 |  B  | 0   | 0.5 |0.25 |0.25 |
  38 |  C  | 0.1 | 0.1 | 0.7 | 0.1 |
  39 |  D  |0.25 |0.25 | 0.5 | 0   |
  40
  41 We can see a few things: the NPC can't immediately attack from cover, it has to search for a target first. It also can't throw two grenades in succession etc. Let's note that this model will now be yielding random sequences of actions such as [*cover*, *search*, *shoot*, *shoot*, *cover*] or [*cover*, *search*, *search*, *grenade*, *shoot*] but some of them may be less likely (for example shooting 3 bullets in a row has a probability of 0.1%) and some downright impossible (e.g. two grenades in a row). Notice a similarity to for example natural language: some words are more likely to be followed by some words than others (e.g. the word "number" is more likely to be followed by "one" than for example "cat").
  42
  43 ## Code Example
  44
  45 Let's write an extremely primitive Markov bot that will work on the level of individual text characters. It will take a training text on input, for example a book, and learn the probabilities with which any letter is followed by another letter. Then it will generate a random output according to these probabilities, something that should resemble the training text. Yes, you may say we are doing a super simple [machine learning](machine_learning.md).
  46
  47 Keep in mind this example is really extremely simple, it only looks one letter back and makes some further simplifications, for example it only approximates the probabilities with kind of a [KISS](kiss.md) hack -- we won't record any numeric probability, we'll only hold a table of letters, each one having a "bucket" of letters that may possibly follow; during training we'll always throw a preceding letter's follower to a random place in the preceding letter's bucket, with the idea that once we finish training, statistically in any bucket there will remain more letters that are more likely to follow given letter, just because we simply threw more such letters in. Similarly when generating the output text we will choose a letter to follow the current one by looking into the table and pulling out a random follower from that letter's bucket, again hoping that letters that have greater presence in the bucket will be more likely to be randomly selected. This approach has issues, for example regarding the question of ideal bucket size, and it introduces statistical biases (maximum probability is limited by bucket size, order matters, later letters are kind of privileged), but it kind of works. Try to think of how we could make a better text generator -- for starters it might work on the level of words and could take into account a history of let's say three letters, i.e. it would record triplets of words and then list of words that likely follow, along with each one's probability that we would record as an actual number to make the probabilities accurate.
  48
  49 Anyway with all this said, below is a [C](c.md) code implementing the above described text generator. To use it just pipe some input ASCII text to it, however make it reasonably sized (a few thousand lines maybe, please don't feed it whole Britannica, the output won't be better), keep in mind the program always trains itself from scratch (in practice we might separate training from generation, as serious training might take very long, i.e. we would have a separate training program that would output a trained model, i.e. the learned probabilities, and then a generator that would only take the trained model and generate output text). Here is the code:
  50
  51 ```
  52 #include <stdio.h>
  53 #include <stdlib.h>
  54
  55 #define OUTPUT_LEN 10000   // length of generated text
  56 #define N 16               // bucket size for each letter
  57 #define SEED 123456
  58 #define IGNORE_NEWLINES 1
  59
  60 unsigned char charFollowers[256][N];
  61
  62 int main(void)
  63 {
  64   srand(SEED);
  65
  66   for (int i = 0; i < 256; ++i)
  67     for (int j = 0; j < N; ++j)
  68        charFollowers[i][j] = ' ';
  69
  70   unsigned char prevChar = 0;
  71
  72   while (1)
  73   {
  74     int c = getchar();
  75
  76     if (c == EOF)
  77       break;
  78
  79 #if IGNORE_NEWLINES
  80     if (c == '\n')
  81       c = ' ';
  82 #endif
  83
  84     charFollowers[prevChar][rand() % N] = c; // put char at random place
  85     prevChar = c;
  86   }
  87
  88   prevChar = ' ';
  89
  90   for (int j = 0; j < OUTPUT_LEN; ++j) // now generate the output
  91   {
  92     prevChar = charFollowers[prevChar][rand() % N]; // take random follower
  93     putchar(prevChar);
  94   }
  95
  96   puts("\n");
  97   return 0;
  98 }
  99 ```
 100
 101 Trying it out on the text of [this wiki](LRS_wiki.md) may output something like this:
 102
 103 ```
 104 Ther thellialy oris threstpl/pifragmediaragmagoiby s agmexes, den
 105 atss pititpenaraly d thiplio s ts gs, tis wily NU gmarags gos
 106 aticel/EEECTherixed atstixedells, s s ores agolltixes tixe. TO: N
 107 s, s, TOpedatssth NUCAPorag: puffrits, pillly ars agmen No tpix abe
 108 aghe. aragmed ssh titixen plioix ag: Th tingoras TOD s wicipixe d
 109 tpllifr.edarenexeramed Thecospix ts ts s osth s pes ovipingor
 110 g: agors agass s TOnamand s aghech th wopipistalioiaris agontibuf
 111 ally Thrixtply tiaceca th oul/EEEEEEEECPU), wicth NU athed wen
 112 aragag athichipl Thechixthass s gmelliptilicex th ostunth gmagh
 113 atictpixe. ar Th on wipixexepifrag gman g: sthabopl/te.
 114 ```
 115
 116 We see at first glance it looks a bit like English text, even with some quirks specific to this wiki, for example here and there having FULL CAPS words (due to acronyms and also rants that often appear here). It even generated the word "CPU". Notice the algorithm correctly learned punctuation, i.e. it knows that after commas and periods there is almost always space and after space there is usually not another space. For comparison here is a Spanish-like text generated from Don Quixote (with accents removed):
 117
 118 ```
 119 Diloma Dadro hacaci gua usta lesano strore sto do diaco; ma ro
 120 hiciso stue ue dita. do que menotamalmeci ma quen do gue lo;
 121 denestajo qucos rdo horor Da que qunca. quadombuce que queromiderbre
 122 hera ha rlabue F de querdos Dio macino; dombidrompo mi ste derdiba
 123 l, mbiolo Ferbes l ste s lolo que ha Du hano quenore Dio ueno que
 124 hala F uano he Dorame de qus rl, ha didesa que halanora Fla quco
 125 dil qucio ue do mestostaloste hados de gusta querana. stuce F s s
 126 Do lo dre s hal Fro gue sa sa. la sido la dico; hado mbuno Do.
 127 mororo; rdenaja. qunolole Diba. do. Fa gor stamestamo ha quno
 128 unostabro quero mue s Diado Didota. quencoralor dio sotomo Fuen
 129 que halora. gunore quabrbe rol gostuno hadolmbe Da que unendor
 130 que le di so; qunta rajos s F de qucol
 131 ```
 132
 133 We see some shorter words like *lo*, *le*, *de*, *he*, *que* and *sido* are real Spanish words. Though punctuation is quite nice, the algorithm fails to learn that after period the word of the next sentence should start with a capital letter (it only does so sometimes by pure chance) -- this is due to the algorithm only seeing one character back; after a period there is also one space which already makes the algorithm forget about the period. This would be addressed by keeping longer history, as said above. Now let's try a difference kind of text altogether, let's try to feed in the source code of [Anarch](anarch.md):
 134
 135 ```
 136   2  camechererea = 20;
 137 #erereppon.xereponioightFuaighe16_ARABEIUnst
 138 chtreraySqua->rarepL_RCL_CL_PE;
 139   caminsin.yDINeramaxer = costRCL_PERCL_ditsins->pL_ime1
 140    = 0;
 141
 142   * = RCL_dime1,y 1)
 143   0;
 144 }
 145 }
 146   ck;
 147   camererayDimameaxSqua ca  = ca->ra caininin.xS_UAME;
 148   caminstFua-> 0 0;
 149 }   ca->ponstramiomereaxSquts  chts 154;
 150   1)
 151 ```
 152
 153 Here it's pretty clear the code won't work but its structure really does resemble the original source: curly brackets and semicolons are correctly followed by newlines, assignments look pretty correct as well, dereference arrows (`->`) appear too -- the code even generated the `RCL_` prefix of the [raycastlib](raycastlib.md) functions that's widely seen in the original code.