~10²⁶ permutations.
That is a pretty large number and thus this problem has a large state space(Essentially a large number of permutations that we might need to parse).
If we go for using a brute force approach maybe our grandchildren or maybe their grandchildren will get the solution.
So what could we do?MCMC Anyone?We will devise a chain whose states theoretically could be any of these permutations.
Then we will:Start by picking up a random current state.
Create a proposal for a new state by swapping two random letters in the current state.
Use a Scoring Function which calculates the score of the current state Score_C and the proposed State Score_P.
If the score of the proposed state is more than the current state, Move to Proposed State.
Else flip a coin which has a probability of Heads Score_P/Score_C.
If it comes heads move to the proposed State.
Repeat from 2nd.
If we get lucky we may reach a steady state where the chain has the stationary distribution of the needed states and the state that the chain is at could be used as a solution.
What is a Scoring Function?The Main thing we need to worry about here is the Scoring Function.
How do we calculate if a proposal is a good proposal?Remember the hill example from my last post?We want to move to the highest hill and stay there for a long time.
We should use a scoring function for each state(Decryption key) which assigns a positive score to each decryption key.
This score intuitively should be more if the encrypted text looks more like actual English if decrypted using this decryption key.
So how can we quantify such a function?English has a particular structure to it.
We assume that the number of times a certain pair of alphabets occur together may follow some particular pattern.
Thus “TH” is more probable of occurring then “ZF”.
We will check a long text and calculate these statistics.
We will see how many times one alphabet comes after another in a legitimate long text like War and Peace.
The choice of text here is not that important.
For example, we want to find out how many times does ‘BA’ appears in the text or how many times ‘TH’ occurs in the text.
For each pair of characters β₁ and β₂ (e.
g.
β₁ = T and β₂ =H), we let R( β₁,β₂) record the number of times that specific pair(e.
g.
“TH”) appears consecutively in the reference text.
Similarly, for a decryption key x, we let Fₓ(β₁,β₂) record the number of times that pair appears when the ciphertext is decrypted using the decryption key x.
We then Score a particular decryption key x using:This function can be thought of as multiplying, for each consecutive pair of letters in the decrypted text, the number of times that pair occurred in the reference text.
Intuitively, the score function is higher when the pair frequencies in the decrypted text most closely match those of the reference text, and the decryption key is thus most likely to be correct.
To make our life easier with calculations, we will calculate log(Score(x))Let us start working through the problem step by step.
First of all, let us encrypt some text to create our example.
In this cruel world, we have to do everything ourselves.
We might want to start by creating some statistics for our scoring function and the scoring function itself.
We also would like to have a function to create proposal states and random coin toss.
Finally, Here is our MCMC Function which runs using Metropolis-Hastings Algorithm.
Let us now run the whole code using all the functions above.
Output:This chain converges around the 2000th iteration and we are able to unscramble the code.
That’s awesome!Now as you see the MCMC Key found is not exactly the encryption key.
So the solution is not a deterministic one, but we can see that it does not actually decrease any of the value that the MCMC Methods provide.
Now let us help Bilbo.
2.
The Knapsack ProblemSo you have Bilbo Baggins who goes to Smaug’s Lair.
He finds M treasures.
Each treasure has some Weight and some Gold value.
But the problem is that Bilbo cannot really take all of that.
He could only carry a certain Maximum Weight.
But being a smart hobbit, he wants to Maximize the value of the treasures he takes.
Given the values for weights and value of the treasures and the maximum weight that Bilbo could carry, could you find a good solution?This is known as the Knapsack Problem in Computer Science.
So in this problem, we have a 1xM array of Weight Values W, Gold Values G, and a value for the maximum weight w_MAX that Bilbo can carry.
We want to find out a 1xM array X of 1’s and 0’s, which holds whether Bilbo carries a particular treasure or not.
This array needs to follow the constraint:WX < w_MAXi.
e.
the total weight Bilbo Carries is less than Max Weight.
and we want to maximizeGXi.
e.
the total Gold value for a particular state X.
Now as earlier this problem also has a large state space.
If we try doing it by Brute force, the number of permutations we need to take is 2^M.
We can see it could get quite big.
As previously this is where we can use MCMC methods.
So lets first discuss as to how we will create a proposal from a previous state.
Pick a random index from the state and toggle the index value.
Check if we satisfy our constraint.
If yes this state is the proposal state.
Else pick up another random index and repeat.
We also need to think about the Scoring Function.
We need to give high values to states with high gold value.
We will use:We give exponentially more value to a higher score.
The Beta here is a +ve constant.
(T stands for Transpose)But how to choose β?If β is big we will give a very high score to good solutions and the chain will not be able to try new solutions as it can get stuck in local optima.
If we give a small value the chain will not converge to very good solutions.
So we use an Optimization Technique called Simulated Annealing i.
e.
we will start with a small value of β and increase as no of iterations go up.
That way the chain will explore in the starting stages and stay at the best solution in the later stages.
Now, we have everything we need to get started.
Let us start by creating a proposal function and the score function.
And the MCMC program.
Running the Main program:OUTPUT________________________________________________________________MCMC Solution is : [0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0] with Gold Value: 2435Now I won’t say that this is the best solution.
The deterministic solution using DP will be the best for such use case but sometimes when the problems get large, having such techniques at disposal becomes invaluable.
ConclusionIn this post, I tried to solve two problems in computer science using MCMC.
Cryptography is itself a huge subject with many applications.
The Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selecting data chunks in Internet Download Manager and other optimizations.
Both these problems had a large state space and were not possible to solve using brute force.
So what do you think about MCMC Methods?Also, If you find any good applications or would like to apply these techniques to some area, I would really be glad to know about them and help if possible.
You can find the whole code on GitHub or Google Colab.
One of the newest and best resources that you can keep an eye on is the Bayesian Methods for Machine Learning course in the Advanced machine learning specializationI am going to be writing more of such posts in the future too.
Let me know what you think about the series.
Follow me up at Medium or Subscribe to my blog to be informed about them.
As always, I welcome feedback and constructive criticism and can be reached on Twitter @mlwhiz.
ReferenceIntroduction to Probability Joseph K Blitzstein, Jessica HwangWikipedia.. More details