Hey, everyone, and welcome back to this class natural language processing in Python.
In the previous lecture, we looked at the model that we will use to decrypt and encoded message.
We know that if our decrypted message is correct, it should have a higher probability than an incorrectly
decrypted message.
So here's some simple code to approach this problem.
First, we call a function to get all possible substitution ciphers.
Then we initialize some variables.
The best log likelihood is initialized to minus infinity.
And the best message is initialized to none.
Then we loop through each map inside the loop.
We use the current map to decode the encrypted message.
Then we calculate the log likelihood of the decrypted message.
Then we check if that log likelihood is better than our current best log likelihood.
If it is, then we make this message our new best message and we make this log likelihood, our current
best log likelihood in this way.
We will have found the maximum log likelihood message by the end of this loop.
But here's one problem.
How do we find all possible descriptions?
In fact, this is an infeasible task.
Consider that we have 26 letters.
We have 26 possible positions that they can appear in our mapping.
So what is the total number of combinations we would have to try if we took a brute force approach?
This is equal to 26 times, 25 times 24 and so forth.
In other words, that's 26 factorial, which is about four times 10 to the power 26.
This is not a practical amount of combinations to try, even if each possibility could be checked in
just one nanosecond.
This would still take about twelve point seven billion years to complete.
Luckily, there is a better solution genetic algorithms in order to have better intuition about genetic
algorithms.
It's helpful to understand a little bit about how genetics and evolution works at a high level.
The basic idea is this each generation of individuals will produce offspring.
You can think of this as like a parent and child relationship.
The parent passes on their DNA to their children.
That's why, for example, if you have black hair, then your children will also have black hair.
If you have curly hair, then your children will also have curly hair and so on.
However, in each generation, the child isn't an exact copy of the parent.
Things always change a tiny bit.
Now, it's important to be clear about what we're talking about.
If we think about humans, this doesn't really apply because human beings are made from two parents.
So the child's DNA is a mixture of the DNA from both parents.
So we have to think on a lower level the level of individual cells or the kinds of organisms where the
offspring can come from just a single parent.
So what happens when one of these organisms creates offspring?
Well, since there is only a single parent, the offspring takes DNA only from that parent.
The offspring is therefore a copy of the parent.
However, mistakes can happen.
You can think of DNA as a string, just like we have in computer programming, but this string is only
allowed to contain a four letters, whereas in English we have 26 letters.
The language of DNA has only a four letter, Alphabet, ATC and G.
Well, what happens when DNA gets copied is that mistakes can happen, and the DNA string from the parent
may not be an exact copy of the child.
There are several kinds of mistakes that can occur.
Sometimes one letter might be replaced by some other letter.
So Atci becomes 8g, for example, this is called a substitution.
Another kind of mistake is called an insertion.
So atci might become 8c tg.
Another kind of mistake is called a deletion, so atci might become 8g.
The idea is that every time DNA gets copied, either from a parent cell to a child cell or from a parent
organism to a child organism, there is a chance that one or more of these errors can occur in a multiple
places along the DNA string.
These are called mutations.
Of course, the probability of such errors is very small.
Otherwise, offspring would not resemble their parents at all.
In fact, they would probably have trouble surviving.
That's why the process of evolution is so slow, depending on the context evolutionary changes happen
on the scale of about one million years.
To put that into context, the average human lifespan is less than 100 years, which is just a tiny
fraction of that.
But over time, these mutations in DNA will build up, and the changes that have the highest fitness
will be the ones that persevere.
So one small change leads to the next until the new organism is now very different from its ancestor
one million years ago.
The idea of fitness and natural selection is the guiding principle behind genetic algorithms.
Mutations that can happen can be either bad or good.
We have many examples of bad mutations we call these genetic diseases.
Luckily, our technology has progressed enough so that we have now just started treating genetic diseases
with DNA editing.
In general, however, what happens when a bad genetic mutation occurs?
If we don't have the technology to treat that individual, then they will have a smaller chance of survival
and to pass on their genes.
Therefore, from an objective standpoint, unfit genes have a smaller chance of propagating to the next
generation.
On the other end of the spectrum, genes that propagate more will have more copies of themselves in
the next generation.
This is almost tautological.
If you have more children, then more of your DNA will exist in the next generation.
So this is biology perspective on what it means to be fit.
In the long term, what's happening can be put in rather simplistic terms.
Genes that copy themselves more well, just keep doing that.
Genes, which mutated but happened to be unlucky and get a bad mutation will have less opportunity to
copy themselves, and they won't make it to subsequent generations.
In the end, theoretically, we should be left with only the best mutations and the most fit DNA.
Now, that can be pretty abstract if you're not a biologist.
So let's think about this in terms of a numerical optimization problem.
Let's phrase this in terms of maximization.
So on the horizontal axis, you have some number representing DNA.
On the vertical axis, you have some number representing the fitness of that DNA.
In other words, the fitness is a function of the DNA, which makes sense in the context of biological
organisms.
In order to evolve our DNA, we can mutate the existing DNA, which means in this case, moving a little
bit left or a little bit right.
We can actually create multiple offspring from the parent DNA at once.
Then we can check the fitness of each of those offspring.
As with biological and natural selection, the less fit offspring will die off and not make it to the
next generation, whereas the Morphett offspring will persevere and become the new parents of the next
generation.
So you can imagine that as we keep mutating and only keeping the most fit mutations that if we keep
iterating over this process, we will eventually end up at the point of maximum fitness.
Now, this is assuming that we don't have to deal with complications such as the environment changing,
which is the case in our example.
So just to give you a simple example of that, consider animals that evolved to be great swimmers.
Then suppose that the environment changes so that water disappears and the world is covered in dry land,
then great swimming will no longer entail great fitness, and some other trait will lead to better fitness.
In our example, which is simpler.
No such environmental changes are possible.
Abstractly, you can think of the process we just described in the context of optimizing any function.
The concept of fitness and DNA are just analogies.
This part of the lecture is optional, so you can feel free to skip it if you're not familiar with these
concepts.
If you have a machine learning background, then you should be fairly comfortable.
So you might recognize the numerical optimization problem as something we often have to do in machine
learning.
You might be familiar with tools such as gradient descent, which tell us the exact direction to go
to improve the value of the function we're trying to optimize.
So you might ask why can't we use gradient descent for a decryption algorithm?
And then the problem with that is in order to do gradient descent, we would have to be able to find
the gradient.
The gradient is the derivative of the objective with respect to the model parameters.
In our case, the objective is the log likelihood of the decrypted sentence and the model parameters
are the dictionary we use to map the coded letter to the unencrypted letter.
Unfortunately, as you can see, the objective is not differential with respect to the model parameters.
Thus, there is no gradient to be found and we can't do gradient descent.
The next issue we have to contend with, and this part is not optional is how do we represent our model
parameters as a DNA string that we can mutate on each round?
Our DNA, unlike real DNA, cannot be comprised of just the four letters ATCI.
But remember that our model is just a mapping from one letter to some other, possibly different letter
in the alphabet.
We can also think of this as a dictionary.
In this way, we don't need to consider the keys of the dictionary, since these can just be the alphabet
in alphabetical order.
We only need to vary the values of the dictionary.
In other words, the letters we want to map to now this can be a string.
In fact, it's just the 26 letters of the alphabet organized in some order without any repetition.
So our DNA is just the 26 letters of the alphabet, which can be in any order constrained by the fact
that every letter must appear once.
And no letter can be repeated.
This is just the assumption of our model assuming that the code really does use the substitution cipher.
Of course, if we had a different cipher, we would have to modify our DNA.
From this, it's possible to write a function F that takes as input a DNA string and outputs a fitness
value.
This fitness value is just the log likelihood of the translated message.
So at a high level, this is what our Function F looks like.
Step number one is to take the DNA string and use this to decode the encrypted message.
Step number two is to calculate the log likelihood of the decrypted message.
Then the function returns this value.
At this point, you should have a pretty good idea of how you would write this function in code.
Actually, here's a good accounting exercise that you might want to do given an input DNA string.
You should write a function that returns a dictionary which maps letters in alphabetical order, two
letters in the order given by the DNA string.
So, for example, in this DNA string, we have the letters FlexJobs and so on.
You might recognize that this is the same mapping we had before.
In this case, it should be mapped.
L b should be mapped to X, C should be mapped, j and so on.
Therefore, our dictionary should have a key a mapped to a value l a key be mapped to a value X. and
so forth.
So please make sure you can write such a function in Python code by yourself without any resources.
At this point, we understand how to represent our DNA code in code.
We also understand the high level picture of how a genetic algorithm should work.
But what does it actually look like in code or pseudocode?
That's what we'll discuss for the rest of this lecture.
First, we have to consider what it even means to mutate our DNA in the first place.
Earlier, we discussed this in the biological picture, where the A's, T's, C's and G's can be changed
by insertion, deletion or substitution.
But in our case, we have to ask the question Do these operations make sense?
Recall that for us, we must have 26 input letters and 26 output letters are input letters are just
the alphabet in alphabetical order.
So it's the 26 output letters that form the DNA code.
What happens if we do an insertion or a deletion, then the result will no longer be 26 letters.
Therefore, these operations should not be allowed.
What about substitution in this case after doing a substitution?
We will have the same number of letters, so that's good.
But remember that we want the letters to be unique.
Therefore, this also cannot work.
So what's the solution?
In order to make sure we meet the constraints of our problem while still following the principle of
mutation, we'll use swapping.
Remember that for each generation, the mutation rate should be very small.
Therefore, whenever we generate an offspring, there will be only one swap from the parents of the
child.
You can verify for yourself that swapping does not violate any of our constraints.
If we swap two characters, the total number of characters is still 26.
Furthermore, all the characters in the sequence are still unique, and we always have the same set
of characters that we started with.
The only thing that has changed is their position.
Now that we understand how to mutate our DNA.
Let's look at a very basic genetic algorithm.
This isn't the final form of what we're using, but it will help us get started and lay the foundation.
As with most optimization algorithms, our code will take the form of a loop to start well, first pick
a random DNA strain and evaluate the log likelihood using our function F.
Next ones are a loop that will iterate over a predetermined number of epochs inside the loop, we will
mutate our DNA.
More specifically, will choose a new DNA string such that two characters from the existing string get
switched.
We'll call this DNA new.
Next will evaluate the new DNA using the same function f if the new DNA leads to a better log likelihood
than the old DNA.
Then we will keep the new DNA.
Otherwise, we'll keep the old DNA.
In the sense, if you want to keep with the evolution analogy, this means that the parent always has
two children.
One child is an exact copy of itself and another child is a mutated copy.
Only one child survives to procreate.
The next generation.
And that child will also have two children the same way.
This is just a fancy way of saying we'll keep whichever of the two days give us the better log likelihood,
the old one or the new one.
As you can imagine, as we keep doing this at each iteration, the next log likelihood we get must be
at least as good as the old one.
The fitness of the DNA should never decrease because we always keep the old DNA if the new DNA is worse.
And this way, we should at least find a local maximum.
You might recognize this as a form of hill climbing.
There is a problem with this method, as is, unfortunately, it's too easy to get stuck at a local
maximum that is suboptimal.
In fact, if you think about real world biology, it does not work like this.
We won't just have one organism that has only one mutated child who then goes on to have one mutated
child so forth.
Usually, we have an entire population of individuals.
For example, we have seven billion humans on the planet Earth.
Humans are constantly making more humans, creating new mutations and evolving very slowly in a mathematical
sense.
This will help us search many different directions and locations at once, which will improve our chances
at finding the correct answer.
So it's a phrase that in a simpler way, in each generation, we're always going to hold a population
of DNA strings.
Each of the DNA strings, which represent a unique individual, will have multiple offspring creating
the next generation at each generation.
Not every individual will survive to procreate.
We'll keep only the fittest individuals that will create the next generation to phrase it even more
simply.
This is just the common saying survival of the fittest.
OK, so how does this work in pseudocode to begin, we're going to create an entire pool of DNA strings.
These will all be completely random so we can search multiple areas of the parameter space more efficiently.
Let's say we create a pool of 20 individuals, and each generation will always be a size 20.
Next, we're going to enter a loop that iterates for a predetermined number of steps.
Inside the loop, we're going to check if it's the first iteration.
If it is, then we'll just do nothing because we already have the 20 individuals in our pool.
If it's not, then we'll create some offspring.
Specifically, we'll create three offspring per parent, which you'll understand why as we go on.
So next, we need to live through the industry in our pool and evaluate its fitness, once we've done
that, we can sort each day string by its fitness.
We'll keep only the top five fittest individuals.
So now you understand why we created three mutated children per parent.
Say we have five parents, we create three mutations per parent.
Then we have 15 children.
But remember that we would also like to copy the parent directly.
So in total, that means we have 15 plus five individuals, which is 20.
Therefore, on each iteration of the loop, we will always have 20 individuals in total.
Now, of course, this is not necessary.
This is just the way I decided to build it.
The hope is that by the end of this loop, we will have converged to the solution.
Finding the best DNA to decrypt are encoded message.
This is the DNA that leads to the maximum likelihood of the decrypted message under our language model.
Let's summarize this lecture since it's been quite long.
First, we discuss the biological side of evolution and why that leads to a better fitness over time
in the evolutionary sense.
Fitness is just who survives and procreate.
This has nothing to do with how successful someone is in their life or anything like that.
For example, you could be a genius billionaire who doesn't want to have children so you choose not
to procreate, which means you're not successful in the evolutionary sense, but you are successful
by most people's standards, which is a completely different concept.
Well, we are doing is just cold, hard math.
So in this lecture, the challenge was to relate this idea of genetic evolution to our decryption problem.
We recognize that our substitution cipher can be represented by a simple DNA string with some constraints.
Unlike real DNA, we can't do operations like insertion, deletion and substitution.
What we can do is swapping since the number of letters must remain the same.
And we must include all letters of the alphabet.
In our case, the fitness of each DNA string is simply the log likelihood of the decrypted message.
As we discussed previously, messages in real English should have a higher log likelihood than messages
with random letters.
Next, we developed the pseudo code that will implement our version of evolution.
We started with a basic hill climbing strategy, but we extended that idea to include an entire population
of individuals.
Each individual would create more than one offspring at each generation, which allows for more variation
and a higher chance of reaching the optimal value.