Everyone and welcome back to this class natural language processing in Python.
In this lecture, we are going to summarize everything we learn in this section.
This section was really a combination of three interesting topics.
Number one, ciphers and coded messages.
Number two, probabilistic language models.
And number three genetic algorithms.
When we put these three things together, we get a working solution for cypher decryption.
We started off this section by describing the substitution cipher.
This means that we encode a message by substituting one letter with some other letter.
The idea is we have a mapping, one unique letter to one unique letter.
The uniqueness is, of course, necessary in order to reverse the mapping.
We did a simple example of how we might encode and decode a message using a substitution cipher.
So hopefully that gave you an idea of how you might implement this in code.
Next, we looked at how to build a character level language model.
The key idea behind building this model is the Markov assumption, where we assume that the current
letter depends only on the previous letter and none of the other letters in the word.
This is, of course, a faulty assumption, but as you saw, it works decently well.
It's certainly possible to extend this model by making less restrictive assumptions.
The way we estimate the probabilities in the language model starts from pretty much the simplest idea
possible counting.
I assume everybody knows how to count, and therefore we should have no trouble building these probabilities.
This is just like a coin toss.
The probability of heads would be estimated as the number of heads divided by the total number of coin
tosses.
Next, we decided this model would have to be extended by using add one smoothing.
This is because we would like to give rare transitions that may not have occurred in our training set
non-zero probabilities.
If we don't and we find such a rare transition in the test set, then the entire likelihood would be
zero.
Since anything multiplied by zero is zero.
And of course, we can't solve the problem if the correct answer has a probability of zero.
Another modification we made was to use the log likelihood rather than just the likelihood.
This is because the likelihood ends up being the multiplication of many, many small terms.
If we multiply many small numbers together, this approach is zero quite fast and due to the finite
precision of numbers stored in a computer.
This will eventually just round down to zero.
So again, we have this problem of zeros.
We can't compare one likelihoods to another.
If they both return zero, taking the log solves this problem since the log is a monotonically increasing
function and therefore preserves the relative fitness of each parameter setting.
Finally, we talked about genetic algorithms, genetic algorithms are useful when we can't differentiate
the objective with respect to the model parameters, the thing we want to optimize in our case, the
thing we want to optimize is more like a discrete string rather than a continuous number.
Therefore, genetic algorithms are well-suited to this use case.
The intuition behind genetic algorithms follows biological evolution, and each generation the genes
mutate and these can be better or worse.
Nature itself picks which genes are better because the better genes tend to propagate more, and the
worst genes tend to not.
We call this natural selection.
In our case, the selection mechanism is the log likelihood of the decrypted message.
We use this as our measure of fitness for each of the DNA strings that we try.
Eventually, after many generations of DNA and mutations and offspring, we arrive at the maximum likelihood
solution.
One interesting result that we saw is that the DNA that gives us the true maximum likelihood can still
be a slightly wrong answer.
We saw that the real answer can give us a smaller likelihood.
In this case, the genetic algorithm is behaving as it should.
Finding the maximum likelihood solution.
So the genetic algorithm is working as intended.
In fact, it's the model that's wrong.
Specifically, using Vikram's and making the mark of assumption is probably too restrictive, although
it's worth noting that this type of model is very common in NLP.
It's always a good first approach to try.
So how can we improve this model?
Here's some ideas for how you can extend this project.
First, try using programs or even higher end grabs if you use try grams.
You still need a unit gram and bigram probabilities, since you still need to model the first letter
of each word and the first two letters of each word.
You can extend what we learned previously to infer that the number of triggers and probabilities you'll
have to estimate is VQ.
And this is assuming V is the length of your alphabet.
If you want to get really advanced, you could even replace the Markov model entirely with a deep learning
type of model like an art.
In general, I'm always going to try to give you a few ways to extend all of the projects we do in this
course.
The best way to make sure you've really understood what you've learned is to apply it.
One way of doing that is to take the same problem, but try to modify and improve the approach.
This will give you a better understanding of the code and of the concepts behind the code.
So hopefully you can think of a few ways you might want to extend what we did.
So give that a try, and I'll see you in the next lecture.