How does AI work? Part 2
Tags: ai, ml, math, machinelearning
Published: 2023-01-25 21:07:51

---
series: How does AI work?
---

## Part 2 — Recognizing Sign Language

In Part 1 we learned about Hidden Markov Models, a powerful tool to represent a partially observable world. Now we’ll see another HMM representation, one that will help us recognize American Sign Language.

In Part 1 our variables were binary e.g. rain or no rain, umbrella or no umbrella. What if the data we need to model has a continuous nature? Imagine we have a signal. We’re looking at its value which is a function of time.

![Signal](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/signal.webp)
###### A signal through time

At {% katex inline %}t=0{% endkatex %} its value is {% katex inline %}-2{% endkatex %}. At {% katex inline %}t=10{% endkatex %} it’s {% katex inline %}-1{% endkatex %}. At {% katex inline %}t=15{% endkatex %} it’s {% katex inline %}0{% endkatex %}. At {% katex inline %}t=35{% endkatex %} it’s {% katex inline %}1{% endkatex %}. Finally, at {% katex inline %}t=38{% endkatex %} it’s {% katex inline %}2{% endkatex %}. It looks like there are four parts of this function so we’ll use four states in our HMM. The goal is to design a model that could have generated this signal. We’ll use a representation similar to the one we learned about in Part 1, except that states will include self-transitions, meaning that at each time frame you could either transition to another state or stay in the same state.

![States](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/states1.webp)

Remember when we had those binary evidence variables in Part 1? Another way to call those are emissions or outputs. In this case they are not binary anymore and they are continuous. These output distributions are in fact probability densities but for our purposes we can think of them as probabilities. So we need to figure out these output (evidence) probabilities.

First we need to figure out which values are allowable while we’re in a given state. We will be in the first state while the value of the signal is between {% katex inline %}-2{% endkatex %} and {% katex inline %}-1{% endkatex %}. In the second state the value is between {% katex inline %}-1{% endkatex %} and {% katex inline %}0{% endkatex %}. Third state is between {% katex inline %}0{% endkatex %} and {% katex inline %}1{% endkatex %} and the fourth state is when the signal is between {% katex inline %}1{% endkatex %} and {% katex inline %}2{% endkatex %}. In each of those intervals all the values are equally represented so a boxcar distribution works pretty well to describe how the value will fall in that range.

![States](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/states2.webp)

Now we need the transition probabilities. Let’s start with the transition where we escape state 1. We can see that on state 1, when the signal is between {% katex inline %}-2{% endkatex %} and {% katex inline %}-1{% endkatex %} we spend {% katex inline %}10{% endkatex %} time frames ({% katex inline %}0{% endkatex %} to {% katex inline %}10{% endkatex %} on the horizontal axis). If we should expect to spend {% katex inline %}10{% endkatex %} time frames in state 1, that means that about once every {% katex inline %}10{% endkatex %} frames we’ll escape so the probability of leaving the state is {% katex inline %}1/10 = 0.1{% endkatex %}. Since we only have one other transition (the self-transition) and all transitions out of a state must sum to {% katex inline %}1{% endkatex %} then the self-transition has a {% katex inline %}0.9{% endkatex %} probability. We continue this with state 2 which has {% katex inline %}5{% endkatex %} time frames, state 3 with {% katex inline %}20{% endkatex %} frames, and state 4 with {% katex inline %}3{% endkatex %} frames.

![States](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/states3.webp)

What we’re doing is creating a model by inspection to represent a given signal. In reality we’ll want to have many examples of a signal and create a model that can accommodate all the examples. It will need to strike a balance between two forces:

* Being specific enough to recognize the signal.
* But not so specific that it would fit only the data it already knows and not any new, slightly different examples. This is called overfitting.

---

**American Sign Language**

To show how HMMs work we’ll use only one feature to represent the movements that constitute a sign in ASL. We’ll use the distance that the hand has traveled on the {% katex inline %}y{% endkatex %} axis with respect to the previous frame. It’s a very limited model since we’re not tracking the movements on the {% katex inline %}x{% endkatex %} axis or more than one hand or how the fingers are positioned. Still, HMMs are so powerful it will be enough to show how we can tell two symbols apart with just that information.

For the word “I” the symbol has three motions, giving us three states:
* Hand goes up to the chest.
* Hand stays there momentarily.
* Hand goes down.

This is how the change in the vertical axis behaves for these 3 movements.

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i1.webp)

* The hand goes up, accelerating up to the point where the hand position in a frame was 10 units higher than in the preceding frame, then slows down until it stops (the frame shows the hand in the same position as the last frame) showing a change of zero.
* The hand stays in the same position for a little while with zero movement.
* The hand goes down, accelerating until it peaks at 10 units lower than the previous frame, then slows down until it stops.

In our earlier example we used a boxcar distribution for our signal where all the values in the interval were equally represented. For hand movements in sign language we’ll make a different assumption: That the changes in hand position will follow a normal distribution, also known as a Gaussian, where in most cases the values will fall around the average and fewer falling further away at both ends.

Furthermore, when the hand goes up or down we expect to see quite a bit of variability in the amount of movement between different people and different examples, while the part where the hand stays at chest level will have very little variation in the change of position across examples.

This means our Gaussian will be wider for the up and down movements and quite narrow for the part where the hand stays in place. Assuming a normal distribution of values ranging from {% katex inline %}0{% endkatex %} to {% katex inline %}10{% endkatex %} the average will be {% katex inline %}5{% endkatex %}. Similarly, for values between {% katex inline %}0{% endkatex %} and {% katex inline %}-10{% endkatex %} the average will be {% katex inline %}-5{% endkatex %} and our output probability density functions (PDFs) will look like this:

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i2.webp)
###### PDFs for “I”

We now have our outputs! As a first pass at getting the transition probabilities we’ll pick something reasonable. For the three distinct motions of the symbol for “I”, which gives us {% katex inline %}3{% endkatex %} states, it looks like we spend a lot of time in states 1 and 3 as the hand goes up and down and only a moment in state 2 when the hand stays at chest level. So let’s give states 1 and 3 a low exit probability meaning we’re likely to spend more frames there, and for state 2 a little higher to allow a higher probability of exiting that state so we don’t stay there too long.

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i3.webp)
###### Transition probabilities for “I”

Now let’s do the same thing for the symbol for “We”. It will have three motions too:
* Hand goes up to chest.
* Hand moves horizontally across chest.
* Hand goes down.

We could have had more states to depict pausing between these movements but to keep it simple we’ll stick to three states. Keeping a similar structure for “I” and “We” will also help us see how we can detect even subtle differences.

A few things to notice: The main difference in our models for “I” and “We” is the second movement. “We” has more variability in the feature we’re measuring (change in the {% katex inline %}y{% endkatex %} axis) because as we’re moving the hand across the chest it might move up or down a little bit, while “I” keeps the hand in one place having very little variability around zero. This means our Gaussian for the second state in “We” will be wider and shorter. Another thing to notice about this second state is that “We” spends more time on it than “I” does so the transition probabilities will reflect that by giving a lower probability to the exit transition and therefore a higher one to the self-transition.

![We](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/we1.webp)
###### Feature: Change in y axis for “We”

![We](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/we2.webp)
###### States for “We”

![We](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/we3.webp)
###### Gaussians for “We”

We’re ready for some recognition! Suppose we have a set of observations that represent the samples we want to recognize. A bunch of videos of people doing signs and we want to recognize what signs they are. We’ll use a tool called a **Viterbi trellis** to see how likely it is that the samples were generated by the models we built. In other words, how likely it is that those signs are an “I” or a “We” in sign language according to our models. The model that gives us the highest probability will be considered the match.

So we have an observation {% katex inline %}O{% endkatex %} with the values for the feature we’re tracking ({% katex inline %}\Delta y{% endkatex %}) at each time frame. We want to find the probability of that observation given the model for “I” denoted with the greek letter {% katex inline %}\lambda{% endkatex %}. In other words:

{% katex %}P(O|\lambda_I){% endkatex %} 
###### Probability of the observation given our model for “I”

We’ll start by laying out the trellis. For each of the seven time frames in our observation we’ll have the observed values and a node for each of the three states. Putting it all together:

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i3.webp)
###### Transition probabilities for “I”

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i2.webp)
###### Gaussians for “I”

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis1.webp)
###### Viterbi trellis

We’re calculating the probability that the observation would be produced by our model for “I”. We’ll trace the states that we could be in if the observation were to match the model. Follow along by reading each step and seeing how it plays out in the next figure.

* We have to start in state {% katex inline %}S1{% endkatex %} at {% katex inline %}t=1{% endkatex %}.
* We have to end in {% katex inline %}S3{% endkatex %} at {% katex inline %}t=7{% endkatex %}.
* At {% katex inline %}t=1{% endkatex %} we can go from {% katex inline %}S1{% endkatex %} to {% katex inline %}S1{% endkatex %} (self-transition) or to {% katex inline %}S2{% endkatex %}.
* At {% katex inline %}t=2{% endkatex %} we can go from {% katex inline %}S1{% endkatex %} to {% katex inline %}S1{% endkatex %} or to {% katex inline %}S2{% endkatex %} and from {% katex inline %}S2{% endkatex %} to {% katex inline %}S2{% endkatex %} or to {% katex inline %}S3{% endkatex %}.

At this point we’ve “touched” all three states from the beginning on the left side of the trellis (blue arrows) so let’s now walk back from the end (green arrows).

* At {% katex inline %}t=7{% endkatex %} the only way to get to {% katex inline %}S3{% endkatex %} (remember we must end at {% katex inline %}S3{% endkatex %}) is from either {% katex inline %}S2{% endkatex %} of a self-transition from {% katex inline %}S3{% endkatex %}.
* At {% katex inline %}t=6{% endkatex %} the only way to get to {% katex inline %}S2{% endkatex %} is from {% katex inline %}S1{% endkatex %} or {% katex inline %}S2{% endkatex %} and the only way to get to {% katex inline %}S3{% endkatex %} is from {% katex inline %}S2{% endkatex %} or {% katex inline %}S3{% endkatex %}.
* At {% katex inline %}t=5{% endkatex %} you can get from {% katex inline %}S1{% endkatex %} to {% katex inline %}S1{% endkatex %}, to {% katex inline %}S2{% endkatex %} from {% katex inline %}S1{% endkatex %} or {% katex inline %}S2{% endkatex %}, and to {% katex inline %}S3{% endkatex %} from {% katex inline %}S2{% endkatex %} or {% katex inline %}S3{% endkatex %}.
* At {% katex inline %}t=4{% endkatex %} you can get to {% katex inline %}S1{% endkatex %} from {% katex inline %}S1{% endkatex %}, to {% katex inline %}S2{% endkatex %} from {% katex inline %}S1{% endkatex %} or {% katex inline %}S2{% endkatex %}, and to {% katex inline %}S3{% endkatex %} from {% katex inline %}S2{% endkatex %}.

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i3.webp)
###### Transition probabilities for “I”

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis2.webp)
###### Viterbi trellis for “I”

Now we have to add the transition probabilities to our trellis. We get them from our model for “I”.

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis3.webp)
###### Viterbi trellis for “I” with transition probabilities

That takes care of the transitions but how do we get the overall probabilities? Since we’re building this by inspection just to show the general mechanism, we won’t be using very exact numbers. In reality we would have true probability density functions but in this high-level example we’re going to use approximate figures based on the assumption that the feature we’re tracking behaves a certain way, namely following a normal distribution.

We’ll start by looking at {% katex inline %}t=1{% endkatex %}. Our observation was a {% katex inline %}\Delta y{% endkatex %} of {% katex inline %}3{% endkatex %} and at that time frame we can be only in State 1. State 1 has a mean of {% katex inline %}5{% endkatex %} so it seems more or less reasonable to find a value of {% katex inline %}3{% endkatex %}. It’s not too far from the mean. Again, in real life we would have a real distribution for these outputs and we’d be able to calculate the exact probability of getting a {% katex inline %}3{% endkatex %} but for this example we’ll use our best guess. As long as we’re consistent, it will work. Let’s say our estimate of the probability that the Gaussian for State 1 generates a {% katex inline %}3{% endkatex %} is {% katex inline %}0.5{% endkatex %}. We’ll update the corresponding node with a {% katex inline %}0.5{% endkatex %}.

![I](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/i2.webp)
###### Gaussians for “I”

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis4.webp)
###### Output probabilities for “I”

Now we move on to the nodes at {% katex inline %}t=2{% endkatex %}. We have two nodes there, one for State 1 ({% katex inline %}\overline{S1}=5{% endkatex %}) and one for State 2 ({% katex inline %}\overline{S2}=0{% endkatex %}). What’s the probability of getting the observed value of {% katex inline %}7{% endkatex %} in State 1? {% katex inline %}7{% endkatex %} is {% katex inline %}2{% endkatex %} units away from the mean of {% katex inline %}5{% endkatex %} just like {% katex inline %}3{% endkatex %} was {% katex inline %}2{% endkatex %} units away from it so it seems reasonable to give it the same probability of {% katex inline %}0.5{% endkatex %}. How about State 2? It has {% katex inline %}\overline{S2}=0{% endkatex %} and a very small standard deviation, which we can tell by its narrow shape. The probability of getting a {% katex inline %}7{% endkatex %} there is very small, almost zero. So let’s pick a very small number. Say, {% katex inline %}10^{-7}{% endkatex %}.

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis5.webp)
###### Output probabilities for “I”

Follow the same process to fill out the rest of the nodes in the trellis and you’ll have something similar to this.

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis6.webp)
###### Output probabilities for “I”

Now we need to find the most likely path. Along this path we’ll multiply the transition probability times the output probability. So what’s the path with the highest probability? Note that the highest probability path will not necessarily be the *greedy* one. In other words, the highest expected value at each transition may not necessarily lead to the highest value in the overall path.

So let’s consider the transition from State 1 to State 2. Our options are staying on State 1 or moving to State 2. The expected value of staying in State 1 is {% katex inline %}.8(.5) = .4{% endkatex %} while the expected value of moving to State 2 is {% katex inline %}.2 (10^{-7}) = 2\mathrm{e}{-8}{% endkatex %}. The greedy algorithm would choose to stay in State 1 since that value is bigger. But we need to keep track of all the possible sequences in the trellis so we can choose the path with the highest overall value, not the one where we end up by simply following what looks best at that moment without reconsidering our choices.

We’ll keep going through the time frames looking at all the possible paths, multiplying the transition probabilities from start to end of the path. At each time frame we’re going to keep the path with the maximum value for each state.

For example, at {% katex inline %}t=3{% endkatex %} we have four possible paths. The best (highest probability) paths so far for each state are in bold.
- {% katex inline %}1 \times .5 \times .8 \times .5 \times .8 \times .6{% endkatex %} **path to state 1**
- {% katex inline %}1 \times .5 \times .8 \times .5 \times .2 \times 10^{-5} = 4\mathrm{e}{-7}{% endkatex %} **path to state 2**
- {% katex inline %}1 \times .5 \times .2 \times 10^{-7} \times .5 \times 10{^-5} = 5\mathrm{e}{-14}{% endkatex %} path to state 2
- {% katex inline %}1 \times .5 \times .2 \times 10^{-7} \times .5 \times 10^{-4}{% endkatex %} **path to state 3**

At the end at {% katex inline %}t=7{% endkatex %} we choose the most likely overall path. For our example it’s the one shown in the next diagram and it has a probability of {% katex inline %}0.00035{% endkatex %}.

![Trellis](https://raw.githubusercontent.com/santisbon/reference/main/assets/img/trellis7.webp)
###### Viterbi path for “I”

A few ways to express our interpretation of this result. These all mean the same thing:
* This is the probability that this observation sequence was generated by our model for “I”.
* This is the probability that this observation corresponds to the symbol for “I”.
* This is the probability that the person making the sign depicted by these observed data meant to say “I” in sign language.

Now we can do the same process for “We” and compare that result to this one. For example, if doing this for “We” results in a most likely path with probability {% katex inline %}0.00016{% endkatex %} that would mean that it’s a lot more probable that the model for “I” generated these data.

This shows us how powerful HMMs can be for distinguishing which sign is the correct one even with relatively bad features. Remember that we chose {% katex inline %}\Delta y{% endkatex %} even though it’s not the best way to tell “I” and “We” apart.

One last note about these probabilities. You might be wondering what happens as these observation sequences get longer, making the probability smaller and smaller until we run out of precision for our computers to correctly represent these numbers. This is called an underflow. In reality, we wouldn’t use the raw probabilities as we did on this example but instead the **log probability** to avoid this problem.

We’re done! You now have a good understanding of how Artificial Intelligence would go about interpreting sign language. This technique is used in a wide variety of classification tasks. Keep learning and come back soon for more AI content.