There’s an acronym you’ve probably heard non-stop for the past few years: LLM, which stands for Large Language Model.

In this article we’re going to take a brief look at what LLMs are, why they’re an extremely exciting piece of technology, why they matter to you and me, and why you should care about LLMs.

Note: in this article, we’ll use Large Language Model, LLM and model interchangeably.

What is an LLM

A Large Language Model, typically referred to as LLM since it is a bit of a tongue twister, is a mathematical model that generates text, like filling in the gap for the next word in a sentence [1].

For instance, when you feed it the sentence The quick brown fox jumps over the lazy ____, it doesn’t know exactly that the next word is dog. What the model produces instead is a list of possible next words with their corresponding probability of coming next in a sentence that starts with those exact words.

The reason why LLMs are so good at predicting the next word in a sentence is because they are trained with an incredibly large amount of text, which typically is scraped from the Internet. So if a model is ingesting the text in this article by any chance, Hi 👋

On the other hand, if you’re building an LLM that is specific to a particular domain, for example, you’re building a chatbot that could converse with you as if they were a character in Shakespeare’s plays, the internet will for sure have a lot of snippets or even his complete works, but it will have a ton of other text that’s not relevant to the task at hand. In this case, you would feed the LLM on the chatbot only Shakespeare context, i.e., all of his plays and sonnets.

Although LLMs are trained with a gigantic amount of data, that’s not what the Large in Large Language Models stands for. Besides the size of the training data, the other large quantity in these models is the number of parameters they have, each one with the possibility of being adjusted, i.e., tuned.

The simplest statistical models is Simple Linear Regression, with only two parameters, the slope and the intercept. And even with just two parameters, there are a few different shapes the model output can take.

As a comparison, when GPT-3 was released in 2020 it had 175B parameters, yes Billion![3] While LLaMa, Meta’s open source LLM, had a number of different models ranging from 7B to 65B parameters when it was released in 2023.

These billions of parameters all start with random values, at the beginning of the training process, and it’s during the Backpropagation part of the training phase that they continually get tweaked and adjusted.

Similar to any other Machine Learning model, during the training phase, the output of the model is compared with the actual expected value for the output, in order to calculate the error. When there’s still room for improvement, Backpropagation ensures the model parameters are adjusted such that the model can predict values with a little bit less error the next time.

But this is just what’s called pre-training, where the model becomes proficient at predicting the next word in a sentence.

In order for the model to have really good interactions with a human, to the point that you — the human — can ask the chatbot a question and its response seems structurally accurate, the underlying LLM has to go through a step of Reinforcement Learning with Human Feedback. This is literally the human in the loop that is often talked about in the context of Machine Learning models.

In this phase, humans tag predictions that are not as good and by taking in that feedback, model parameters are updated and the model is trained again, as many times needed, to reach the level of prediction quality desired.

It’s clear by now that these models are extremely complex, and need to be able to perform millions, if not billions of computations. This high-intensity compute required novel architectures, at the model level with Transformers and for compute, with GPUs.

GPU is this class of graphic processors used in scenarios when you need to perform an incredibly big number of computations in a short period of time, for instance while smoothly rendering characters in a videogame. Compared to the traditional CPUs found in your laptop or tower PC, GPUs have the ability to effortlessly run many parallel computations.

The breakthrough for LLMs was when researchers realized GPUs can also be applied to non graphical problems. Both Machine Learning and Computer Graphics rely on linear algebra, running operations on matrices, so both benefit from the ability to execute many parallel computations.

Transformers is a new type of architecture developed by Google, which makes it such that each operation done during model training can be parallelized. For instance, while predicting the next word in a sentence, a model that uses a Transformer architecture doesn’t need to read the sentence from start to end, it process the entire text all at the same time, in parallel. It associates each word processed with a long array of numbers that give meaning to that word. Thinking about Linear Algebra again for a second, instead of processing and transforming one data point at a time, the combo of Transformers and GPUs can process tons of points at the same time by leveraging matrices.

In addition to parallelized computation, what distinguishes Transformers is an unique operation called Attention. In a very simplistic way, Attention makes it possible to look at all the context around a word, even if it occurs multiple times in different sentences like

At the end of the show, the singer took a bow multiple times.

Jack wanted to go to the store to buy a new bow for target practice.

If we focus on the word bow, you can see how the context in which this word shows up in each sentence and its actual meaning are very different.

Attention allows the model to refine the meaning each word encodes based on the context around them.

This, plus some additional steps like training a Feedforward Neural Network, all done multiple times, make it such that the model gradually refines its capacity to encode the right information. All these steps are intended to make the model more accurate and not mix up the meaning of bow, the motion, and bow (object related to archery) when it runs a prediction task.

The development of Transformers and GPUs allowed LLMs to explode in usage and application compared to prior to language models that needed to read one word at a time. Knowing that a model gets better the more quality data it learns from, you can see how processing one word at a time was a huge bottleneck.

Why LLMs Matter

With the capacity described, that LLMs can process enormous amounts of text examples and then predict with a high accuracy, the next word in a sentence, combined with other powerful Artificial Intelligence frameworks, many natural language and information retrieval tasks that became much easier to implement and productize.

In essence, Large Language Models (LLMs) have emerged as cutting edge artificial intelligence systems that can process and generate text with coherent communication and generalize multiple tasks[2].

Think about tasks like translating from English to Spanish, summarizing a set of documents, identifying certain passages in documents, or having a chatbot answer your questions about a particular topic.

These tasks that were possible before, but the effort required to build a model was incredibly higher and the rate of improvement of these models was much slower due to technology bottlenecks. LLMs came in and supercharged all of these tasks and applications.

You’ve probably interacted or seen someone interacting directly with products that use LLMs at their core.

These products are much more than a simple LLM that accurately predicts the next word in a sentence. They leverage LLMs and other Machine Learning techniques and frameworks, to understand what you’re asking, search through all the contextual information they’ve seen so far, and present you with a human-like and, most times coherent, answer. Or at least some provide guidance about what to look into next.

There are tons of Artificial Intelligence (AI) products that leverage LLMs, from Facebook’s Meta AI, Google’s Gemini, Open AI’s ChatGPT, which borrows its name from the Generative Pre-trained Transformer technology under the hood, Microsoft’s CoPilot, among many, many others, covering a wide range of tasks to assist you on.

For instance, a few weeks ago, I was wondering how many studio albums Incubus had released. Six months ago, I’d probably Google it or go straight to Wikipedia. Nowadays, I tend to ask Gemini.

This is only a simplistic example. There are many other types of questions or prompts you can provide to these Artificial Intelligence products, like asking to summarize a particular text or document, or if you’re like me and you’re traveling to Melbourne, asking for recommendations about what to do there.

It cut straight to the point, provided me with a variety of pointers on what to do, and then I was off to the races, able to dig a bit further on specific places that seemed more interesting to me.

You can see how this saved me a bunch of time that I would probably have to spend between Yelp an TripAdvisor reviews, Youtube videos or blogposts about iconic and recommended places in Melbourne.

Conclusion

LMMs are, without a doubt, a nascent area of research that has been evolving at a lightning fast pace, as you can see by the timeline below.

We’re just in the very early days of productization, or product application. More and more companies are applying LLMs to their domain areas, in order to streamline tasks that would take them several years, and an incredible amount of funds to research, develop and bring to market.

When applied in ethical and consumer-conscious ways, LLMs and products that have LLMs at their core provide a massive opportunity to everyone. For researchers, it’s a cutting edge field with a wealth of both theoretical and practical problems to untangle.

For example, in Genomics, gLMs or Genomic Language Models, i.e., Large Language Models trained on DNA sequences, are used to accelerate our general understanding of genomes and how DNA works and interacts with other functions[4]. These are big questions for which scientists don’t have definitive answers for, but LLMs are proving to be a tool that can help them make progress at a much bigger scale and iterate on their findings much faster. To make steady progress in science, fast feedback loops are crucial.

For companies, there’s a monumental shift and opportunity to do more for customers, address more of their problems and pain-points, making it easier for customers to see the value in products. Be it for effectiveness, ease of use, cost, or all of the above.

For consumers, we get to experience products and tools to assist us on day-to-day tasks, that help perform our our jobs a little better, to gain faster access to knowledge or get pointers to where we can search and dig deeper for that information.

To me, the most exciting part, is the speed at which these products evolve and outdate themselves. I’m personally curious to see how these products will look like in the next 5 years and how they can become more accurate and reliable.

Technological leaps and scientific breakthroughs used to take decades or even centuries to occur. So it’s nothing shy of rational to be apprehensive when we experience big technological step-changes multiple times during our lifetime.

Among all the hype and some of the fads that come and go, the core technology underlying Large Language Models is fascinating and has proven to have interesting and plausible applications.

Hope you enjoyed this brief overview of LLMs, why they matter, and why it’s worth continuing to keep an eye on this research area and new AI products.

Thanks for reading!

References

[1] Large Language Models explained briefly (video)

[2] A Comprehensive Overview of Large Language Models. 2024.Humza Naveed and Asad Ullah Khan and Shi Qiu and Muhammad Saqib and Saeed Anwar and Muhammad Usman and Naveed Akhtar and Nick Barnes and Ajmal Mian.

[3] Language Models are Few-Shot Learners. 2020. Tom B. Brown and Benjamin Mann and Nick Ryder and Melanie Subbiah and Jared Kaplan and Prafulla Dhariwal and Arvind Neelakantan and Pranav Shyam and Girish Sastry and Amanda Askell and Sandhini Agarwal and Ariel Herbert-Voss and Gretchen Krueger and Tom Henighan and Rewon Child and Aditya Ramesh and Daniel M. Ziegler and Jeffrey Wu and Clemens Winter and Christopher Hesse and Mark Chen and Eric Sigler and Mateusz Litwin and Scott Gray and Benjamin Chess and Jack Clark and Christopher Berner and Sam McCandlish and Alec Radford and Ilya Sutskever and Dario Amodei

[4]Genomic Language Models: Opportunities and Challenges. 2024. Gonzalo Benegas and Chengzhong Ye and Carlos Albors and Jianan Canal Li and Yun S. Song.

Large Language Models: A Short Introduction was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

The pavement is uneven, the sun is high. The body moves rhythmically, but the mind is still, it’s all quiet up there. You’re in a familiar place, but it feels different, peaceful. Time stops for a split second, and you’re beaming, a brief out-of-body experience before your foot touches the ground. These are the good days.

On bad days the mind is racing while the body is trying to keep up. Thoughts come and go, you think about work, house chores you’ve been procrastinating on, and why you forgot to call your mom again. Disjointed thoughts, anxieties, musings, all thrown into a blender at high-speed.

While running has had a sort of renaissance lately, for me, it’s been part of my life since I was about ten years old. It was a family activity back then, that went dormant during most of my young adult years.

For a decade or two, my dad was into running, he had his running buddies and raced recreationally, I guess in equals part for the physical and the social aspect. I’m glad I got dragged into that world at such a young age, because it became kind of imprinted in me. I was never the fittest or the fastest, and it doesn’t really matter. Through his experience, I got to appreciate the practice and develop a profound connection with running, develop my own ritual. The thing I like to do regardless of any social pressure, the one thing that constitutes my alone time, even when someone is around.

The process was long, and for most of my adolescence, running was never a thing, it never really clicked. I’d go for a run every now and then, on my own, defying the small town weird looks.

A few years ago I moved to a place that is fairly close to a regional park, with different trails, so picked it up again, as way to clear my head and force myself to workout. Although not on the first try, it shook me to the core. In one of those lightbulb moments, it finally clicked. I could feel it in my body, it became something I need, enjoy and look forward to. The kind of thing you make time for in your life.

Today running is a pillar for my health, physical and mental.

On the days my mind is especially loud and busy, those are the best days to go out for a run. The biggest hurdle is always getting ready, I can find a million reasons why I’m tired or need to do something later and running would delay everything.

Once the running gear is on, there’s no turning back. There’s a habit forming component to it too, and I use every trick I get to keep it going.

On the first few strides, my body gets acclimated and then goes into autopilot, the body knows it’s time to reset and quiet the mind.

Despite never being completely easy, the mental practice is worth the physical discomfort. Many days start off easy, thinking it’s going to be just a stroll, only to realize I’m more tired than I realized. From that moment on, the mind takes over and it’s all about listening to my body, so I don’t get injured, and pushing through, enforcing the discipline, practicing resilience. Just another half mile, just one more.

Some days it’s easier to embrace the challenge and push through, but it's never a sure thing. On those days you throw in the towel and stop, walk back home, and it's fine too.

Even on the days that laziness almost wins, or maybe especially on those days, that’s when running is more rewarding, more restorative. It forces the natural purge of stress and anxiety, you come out on the other side tired and maybe sore, but there’s a glow, a feeling of stillness and accomplishment.

It only takes me a good day, when my body feels good and responsive, mind and body in sync, to forget about the days when each mile felt like a marathon.

Running is a very personal experience, a moment of deep focus introspection. A natural cleanser, a time to organize the mind by being completely silent with myself while still surround by people or nature.

Nature runs are specially peaceful and relaxing. Running on a trail it's almost like asking Nature for permission to be there. It’s a place where nature comes first and if there are animals, it’s their environment, you’re just a passerby, so you have to respect them.

A mix of habit and necessity, it’s something that took me years to appreciate and develop. Looking back, there were times when I completely forgot that it was there for me as a tool and as a practice, a way of keeping me fit and serene.

Today, it’s my ultimate reset.

Running — The Ultimate Reset was originally published in Side Notes by Carolina Bento on Medium, where people are continuing the conversation by highlighting and responding to this story.

São como torres de carbono
Uma a cada dez metros
Ou mais próxima de uma outra

O ritmo interno soa a multidão
E lá fora não há mais nada
Só céu e chão

Abre-se um fogo que vem do meio do estômago
Incendeia e não pára, mesmo em chuva forte
Presente, o tempo todo, como escudo

O peito aperta, a dor é ajuda
E por uns segundos há leveza
A visão é esbatida, mas fica tudo mais claro

O tempo pára, o corpo acelera
E por uns segundos comprimes-te num átomo
Passa tudo tão depressa, queres sentir outra vez

Só a exaustão pára o impulso
Ou o próximo compromisso
Passa tudo tão depressa, queres sentir outra vez

Like towers made of carbon
Ten meters away from one another
Or maybe closer

The rhythm sounds like a massive crowd
And outside there's nothing else
Just the sky and the pavement

There's a fire in the pit of my stomach
Burns bright and doesn't die, even in intense rain
Just there, all the time, like a shield

My chest hurts, the pain is acute
And for a split second you're weightless
My vision in blurry, but everything looks clear now

Time stops, the body races
And for a split second, you're the size of an atom
Everything goes by so fast, you want to feel it again

Only exhaustion stops the impulse
Or the next commitment
Everything goes by so fast, you want to feel it again

Porque é que corres aqui? || Why are you running here? was originally published in Side Notes by Carolina Bento on Medium, where people are continuing the conversation by highlighting and responding to this story.

Hidden Markov Models are probabilistic models used to solve real life problems ranging from something everyone thinks about at least once a week — how is the weather going to be like tomorrow?[1] — to hard molecular biology problems, such as predicting peptide binders to the human MHC class II molecule[2].

Hidden Markov Models are close relatives of Markov Chains, but their hidden states make them a unique tool to use when you’re interested in determining the probability of a sequence of random variables.

In this article we’ll breakdown Hidden Markov Models into all its different components and see, step by step with both the Math and Python code, which emotional states led to your dog’s results in a training exam. We’ll be using the Viterbi Algorithm to determine the probability of observing a specific sequence of observations, and how you can use the Forward Algorithm to determine the likelihood of an observed sequence, when you’re given a sequence of hidden states.

The real world is full of phenomena for which we can see the final outcome, but can’t actually observe the underlying factors that generated those outcomes. One example is predicting the weather, determining if it’s going to be rainy or sunny tomorrow, based on past weather observations and the observed probabilities of the different weather outcomes.

Although driven by factors we can’t observe, with an Hidden Markov Model it’s possible to model these phenomena as probabilistic systems.

Markov Models with Hidden States

Hidden Markov Models, known as HMM for short, are statistical models that work as a sequence of labeling problems. These are the types of problems that describe the evolution of observable events, which themselves, are dependent on internal factors that can’t be directly observed — they are hidden[3].

An Hidden Markov Model is made of two distinct stochastic processes, meaning those are processes that can be defined as sequences of random variables — variables that depend on random events.

There’s an invisible process and an observable process.

The invisible process is a Markov Chain, like chaining together multiple hidden states that are traversed over time in order to reach an outcome. This is a probabilistic process because all the parameters of the Markov Chain, as well as the score of each sequence, are in fact probabilities[4].

Hidden Markov Models describe the evolution of observable events, which themselves, are dependent on internal factors that can’t be directly observed — they are hidden[3]

Just like any other Markov Chain, in order to know which state you’re going next, the only thing that matters is where you are now — in which state of the Markov Chain you’re currently in. None of the previous history of states you’ve been in the past matters to understand where you’re going next.

This kind of short-term memory is one of the key characteristics of HMMs and it’s called the Markov Assumption, indicating that the probability of reaching the next state is only dependent on the probability of the current state.

The other key characteristic of an HMM, is that it also assumes that each observation is only dependent on the state that produced it therefore, being completely independent from any other state in the chain[5].

The Markov Assumption states that the probability of reaching the next state is only dependent on the probability of the current state.

This is all great background information on HMM but, what classes of problems are they actually used in?

HMMs help model the behavior of phenomena. Besides modeling and allowing to run simulations, you can also ask different types of questions those phenomena:

• Likelihood or Scoring, as in, determining the probability of observing a sequence
• Decoding the best sequence of states that generated a specific observation
• Learning the parameters of the HMM that led to observing a given sequence, that traversed a specific set of states.

Let's see this in practice!

Dog Training Performance as an HMM

Today you’re not as worried about the weather forecast, what’s on your mind is that your dog is possibly graduating from their training lessons. After all the time, effort and dog treats involved, all you want is for them to succeed.

During dog training sessions, your four-legged friend is expected to do a few actions or tricks, so the trainer can observe and grade their performance. After combining the scores of three trials, they’ll determine if your dog graduates or needs additional training.
The trainer only sees the outcome, but there are several factors involved that can’t be directly observed such as, if your dog is tired, happy, if they don’t like the trainer at all or the other dogs around them.

None of these are directly observed, unless there’s undoubtably a specific action your dog does only when they feel a certain way. Would be great if they could express how they feel in words, maybe in the future!

With Hidden Markov Models fresh in your mind, this looks like the perfect opportunity to try to predict how your dog was feeling during the exam. They might get a certain score because they were feeling tired, maybe they were hungry, or they were annoyed at the trainer.

Your dog has been taking lessons for a while and, based on data collected during that training, you have all the building blocks needed to build a Hidden Markov Model.

In order to build a HMM that models the performance of your dog in the training evaluation you need:

• Hidden States
• Transition Matrix
• Sequence of Observations
• Observation Likelihood Matrix
• Initial Probability Distribution

Hidden States are those non-observable factors that influence the observation sequence. You’ll only consider if your dog is Tired or Happy.

Knowing your dog very well, the non-observable factors that can impact their exam performance are simply being tired or happy.

Next you need to know what’s the probability of going from one state to another, which is captured in a Transition Matrix. This matrix must also be row stochastic meaning that the probabilities from one state to any other state in the chain, each row in the matrix, must sum to one.

Regardless of what type of problem you’re solving for, you always need a Sequence of Observations. Each observation representing the result of traversing the Markov Chain. Each observation is drawn from a specific vocabulary.

In the case of your dog’s exam you observe the score they get after each trial, which can be Fail, OK or Perfect. These are all the possible terms in the observation vocabulary.

You also need the Observation Likelihood Matrix, which is the probability of an observation being generated from a specific state.

Finally, there’s the Initial Probability Distribution. This is the probability that the Markov Chain will start in each specific hidden state.

There can also be some states will never be the starting state in the Markov Chain. In these situations, their initial probability is zero. And just like the probabilities in the Transition Matrix, these sum of all initial probabilities must add up to one.

The Initial Probability Distribution, along with the Transition Matrix and the Observation Likelihood, make up the parameters of an HMM. These are the probabilities you’re figuring out if you have a sequence of observations and hidden states, and attempt to learn which specific HMM could have generated them.

Putting all of these pieces together, this is what the Hidden Markov model that represents your dog’s performance on the training exam looks like

During the exam, your dog will perform three trials, and graduate only if they don’t Fail in two of those trials.

At the end of the day, if your dog needs more training, you’ll care for them all the same. The big question circling your mind is How are they feeling during the exam.

Imagining a scenario where they graduate with a score of OK — Fail — Perfect exactly in this order, what sequence of emotional states will they be in? Will they be mostly tired, or hungry throughout, or maybe a mix of both?

This type of problem falls right under the category of Decoding problems that HMMs can be applied to. In this case, you’re interested figuring out what’s the best sequence of states that generated a specific sequence of observations, OK — Fail — Perfect.

The problem of decoding the sequence of states that generated a given sequence of observations leverages the Viterbi Algorithm. However, is worth doing a short detour and take a peek into how you could calculate the probability of a given observation sequence — a Likelihood task — using the Forward Algorithm. This will set the stage to better understanding how the Viterbi Algorithm works.

The Forward Algorithm

If you were modeling this problem like a regular Markov Chain, and wanted to calculate the likelihood of observing the sequence of outcomes OK, Fail, Perfect you’d traverse the chain by landing in each specific state that generates the desired outcome. At each step you would take the conditional probability of observing the current outcome given that you’ve observed the previous outcome and multiply that probability by the transition probability of going from one state to the other.

The big difference is that, in a regular Markov Chain, all states are well known and observable. Not in an Hidden Markov Model! In an Hidden Markov Model you observe a sequence of outcomes, not knowing which specific sequence of hidden states had to be traversed in order to observe that.

The big difference is that, in a regular Markov Chain, all states are well known and observable. Not in an Hidden Markov Model!

At this point you might be thinking, Well I can simply traverse all possible paths and eventually have a rule to pick between equivalent paths. The mathematical definition for this approach looks something like this

That’s one strategy for sure! You’d have to calculate the probability of observing the sequence OK, Fail, Perfect for every single combination of hidden states that could ever generate that sequence.

When you have a small enough number of hidden states and sequence of observed outcomes, it's possible to do that calculation within a reasonable time.

Thankfully, the Hidden Markov model you just defined is relatively simple, with 3 observed outcomes and 2 hidden states.

For an observed sequence of length L outcomes, on a HMM with M hidden states, you have “M to the power L” possible states which in your case, means 2 to the power of 3, i.e., 8 possible paths for the sequence OK — Fail — Perfect, involving an exponential computational complexity of O(M^L L), described in Big O-Notation. As the complexity of the model increases, the number of paths you need to take into account grows exponentially.

As the complexity of the model increases, the number of paths you need to take into account grows exponentially.

This is where the Forward Algorithm shines.

The Forward Algorithm calculates the probability of a new symbol in the observed sequence, without the need to calculate the probabilities of all possible paths that form that sequence [3].

Instead of computing the probabilities of all possible paths that form that sequence the algorithm defines the forward variable and calculates its value recursively.

The fact that it uses recursion, is the key reason why this algorithm is faster than calculating all the probabilities of possible paths. In fact, it can calculate the probability of observing the sequence x in only “L times M squared” computations, instead of “M to the power of L times L”.

In your case, with 2 hidden states and a sequence of 3 observed outcomes, it’s the difference between calculating the probabilities O(MˆL L) = 2³x3 = 8x3 = 24 times, as opposed to O(L Mˆ2)=3*2²=3x4 = 12 times.

This reduction in the number of calculations is achieved by Dynamic Programming, a programming technique that uses an auxiliary data structures to store intermediate information, therefore making sure the same calculations are not done multiple times.

Every time the algorithm is about to calculate a new probability it checks if it has already computed it, and if so, it can easily access that value in the intermediate data structure. Otherwise, the probability is calculated and the value is stored.

Let’s get back to your decoding problem, using the Viterbi Algorithm.

The Viterbi Algorithm

Thinking in pseudo code, If you were to brute force your way into decoding the sequence of hidden states that generate a specific observation sequence, all you needed to do was:

• generate all possible permutations of paths that lead to the desired observation sequence
• use the Forward Algorithm to calculate the likelihood of each observation sequence, for each possible sequence of hidden states
• pick the sequence of hidden states with highest probability

For your specific HMM, there are 8 possible paths that lead to an outcome of OK — Fail — Perfect. Add just one more observation, and you’ll have double the amount of possible sequences of hidden states! Similarly to what was described for the Forward Algorithm, you easily end up with an exponentially complex algorithm and hit performance ceiling.

The Viterbi Algorithm, gives you a hand with that.

When the sequence of hidden states in the HMM is traversed, at each step, the probability vt(j) is the probability that the HMM is in the hidden state j after seeing the observation and is being traversed through the most probable state that lead to j.

The key to decoding the sequence of hidden states that generate a specific observation sequence, is this concept of the most probable path. Also called the Viterbi path, the most probable path, is the path that has highest likelihood, from all the paths that can lead to any given hidden state.

The key to decoding the sequence of hidden states that generate a specific observation sequence, is to use the Viterbi path. The most probable path that leads to any given hidden state.

You can draw a parallel between the Forward Algorithm and the Viterbi Algorithm. Where the Forward Algorithm sums all probabilities to obtain the likelihood of reaching a certain state taking into account all the paths that lead there, the Viterbi algorithm doesn’t want to explore all possibilities. It focuses on the most probable path that leads to any given state.

Going back to the task of decoding the sequence of hidden states that lead to the scores of OK — Fail — Perfect in their exam, running the Viterbi Algorithm by hand would look like this

Another unique characteristic of the Viterbi algorithm is that it must have a way to keep track of all the paths that led to any given hidden state, in order to compare their probabilities. To do that it keeps track of backpointers to each hidden state, using an auxiliary data structure typical of dynamic programming algorithms. That way it can easily access the probability of any viterbi path traversed in the past.

Backpointers are the key to figure out the most probable path that leads to an observation sequence.

In the example of your dogs’ exam, when you calculate the Viterbi paths v3(Happy) and v3(Tired), you pick the path with highest probability and start going backwards, i.e., backtracking, through all the paths that led to where you are.

The Viterbi Algorithm in Python

Doing all of this by hand is time consuming and error prone. Miss one significant digit and you might have to start from scratch and re-check all your probabilities!

The good news is that you can leverage software libraries like hmmlearn, and with a few lines of code you can decode the sequence of hidden states that lead to your dog graduating with OK — Fail — Perfect in the trials, exactly in this order.

from hmmlearn import hmm
import numpy as np

## Part 1. Generating a HMM with specific parameters and simulating the exam
print("Setup HMM model with parameters")
# init_params are the parameters used to initialize the model for training
# s -> start probability
# t -> transition probabilities
# e -> emission probabilities
model = hmm.CategoricalHMM(n_components=2, random_state=425, init_params='ste')

# initial probabilities
# probability of starting in the Tired state = 0
# probability of starting in the Happy state = 1
initial_distribution = np.array([0.1, 0.9])
model.startprob_ = initial_distribution

print("Step 1. Complete - Defined Initial Distribution")

# transition probabilities
#        tired    happy
# tired   0.4      0.6
# happy   0.2      0.8

transition_distribution = np.array([[0.4, 0.6], [0.2, 0.8]])
model.transmat_ = transition_distribution
print("Step 2. Complete - Defined Transition Matrix")

# observation probabilities
#        Fail    OK      Perfect
# tired   0.3    0.5       0.2
# happy   0.1    0.5       0.4

observation_probability_matrix = np.array([[0.3, 0.5, 0.2], [0.1, 0.5, 0.4]])
model.emissionprob_ = observation_probability_matrix
print("Step 3. Complete - Defined Observation Probability Matrix")

# simulate performing 100,000 trials, i.e., aptitude tests
trials, simulated_states = model.sample(100000)

# Output a sample of the simulated trials
# 0 -> Fail
# 1 -> OK
# 2 -> Perfect
print("\nSample of Simulated Trials - Based on Model Parameters")
print(trials[:10])

## Part 2 - Decoding the hidden state sequence that leads
## to an observation sequence of OK - Fail - Perfect

# split our data into training and test sets (50/50 split)
X_train = trials[:trials.shape[0] // 2]
X_test = trials[trials.shape[0] // 2:]

model.fit(X_train)

# the exam had 3 trials and your dog had the following score: OK, Fail, Perfect (1, 0 , 2)
exam_observations = [[1, 0, 2]]
predicted_states = model.predict(X=[[1, 0, 2]])
print("Predict the Hidden State Transitions that were being the exam scores OK, Fail, Perfect: \n 0 -> Tired , "
      "1 -> Happy")
print(predicted_states)

In a few seconds you get an output that matches results the calculations you did by hand, much fast and with much less room for error.

Conclusion

What’s fascinating about Hidden Markov Models is how this statistical tool created in the mid 1960’s [6] is so powerful and applicable to real world problems in such distinct areas, from weather forecasting to finding the next word in a sentence.

In this article, you had the chance to learn about the different components of an HMM, how they can be applied to different types of tasks, and spotting the similarities between the Forward Algorithm and Viterbi Algorithm. Two very similar algorithms that use dynamic programming to deal with the exponential number of calculations involved.

Either doing the calculations by hand or plugging in the parameters into TensorFlow code, hope you enjoyed diving deep into the world of HMMs.

Thank you for reading!

References

1. D. Khiatani and U. Ghose, “Weather forecasting using Hidden Markov Model,” 2017 International Conference on Computing and Communication Technologies for Smart Nation (IC3TSN), Gurgaon, India, 2017, pp. 220–225, doi: 10.1109/IC3TSN.2017.8284480.
2. Noguchi H, Kato R, Hanai T, Matsubara Y, Honda H, Brusic V, Kobayashi T. Hidden Markov model-based prediction of antigenic peptides that interact with MHC class II molecules. J Biosci Bioeng. 2002;94(3):264–70. doi: 10.1263/jbb.94.264. PMID: 16233301.
3. Yoon BJ. Hidden Markov Models and their Applications in Biological Sequence Analysis. Curr Genomics. 2009 Sep;10(6):402–15. doi: 10.2174/138920209789177575. PMID: 20190955; PMCID: PMC2766791.
4. Eddy, S. What is a hidden Markov model?. Nat Biotechnol 22, 1315–1316 (2004). https://doi.org/10.1038/nbt1004-1315
5. Jurafsky, Dan and Martin, James H.. Speech and language processing : an introduction to natural language processing, computational linguistics, and speech recognition. Upper Saddle River, N.J.: Pearson Prentice Hall, 2009.
6. Baum, Leonard E., and Ted Petrie. “Statistical Inference for Probabilistic Functions of Finite State Markov Chains.” The Annals of Mathematical Statistics 37, no. 6 (1966): 1554–63.

Hidden Markov Models Explained with a Real Life Example and Python code was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

Explained with a Real Life Example in Python

Receiver Operating Characteristic Curve (ROC) analysis and the Area Under the Curve (AUC) are tools widely used in Data Science, borrowed from signal processing, to assess the quality of a model under different parameterizations, or compare performance of two or more models.

Traditional performance metrics, like precision and recall, rely heavily on positive observations. So instead, ROC and AUC use True Positive and False Positive Rates to assess quality, which take into account both positive and negative observations.

The road from breaking down a problem and solving it with Machine Learning has multiple steps. At a high-level it involves data collection, cleaning and feature engineering, building the model and, last but not least, evaluating model performance.

When you’re evaluating the quality of a model, typically you use metrics like precision and recall, also referred to as confidence in the data mining field and sensitivity, respectively.

These metrics compare the predicted values to the real observation values, usually from a hold-out set, and are best visualized using a confusion matrix.

Let’s focus on Precision first, also referred to as Positive Predictive Value. Using the confusion matrix, you can construction Precision as the ratio of all the true positives over all predicted positives.

Recall, which is also referred to as True Positive Rate, represents the ratio fo True Positives over all the Positives, observed and predicted.

Describing Precision and Recall using the different sets of observations in the confusion matrix, you can start to see how these metrics might provide a narrow view of model performance.

Something that stands out is the fact that Precision and Recall only focus on the positive examples and predictions[1], and don’t take into account any negative examples. Additionally, they don’t compare the performance of the model against a median-scenario, one that simply random-guesses.

After digging deeper into how Precision and Recall are calculated, you can start to see how these metrics might provide a narrow view of model performance.

To complement your model evaluation and rule out biases from Precision and Recall you can reach for a few robust tools in the Data Scientist’s toolkit: the Receiver Operation Characteristic Curve (ROC) analysis and its Area Under the Curve (AUC).

ROC Curve: from Signal Theory to Machine Learning

ROC is as summary tool, used to visualize the trade-off between Precision and Recall[2].

This technique emerged in the field of signal detection theory, as part of the development of radar technology during World War II [3]. The name may be a bit confusing for those unfamiliar with signal theory, but it refers to reading radar signals by military radar operators, hence the Receiver Operating part of Receiver Operating Characteristic Curve.

Part of a radar operator’s job is to identify approaching enemy units on a radar, the key part, being able to literally distinguish signal, i.e., actual incoming units, from noise, e.g., static noise or other random interference. They are experts at determining what’s signal and what’s noise, to avoid charging at a supposed enemy unit when it’s either one of your own units or simply there’s nothing there.

Right now you may be thinking Hold on, this sounds like a familiar task!

And indeed it is, this task is conceptually very similar to classifying an image as a cat or not, or detecting a patient developed a disease or not, while keeping a low false positive rate.

ROC analysis uses the ROC curve to determine how much of the value of a binary signal is polluted by noise, i.e., randomness[4]. It provides a summary of sensitivity and specificity across a range of operating points, for a continuous predictor[5].

The ROC curve is obtained by plotting the False Positive Rate, on the x-axis, against the True Positive Rate, on the y-axis.

Because the True Positive Rate is the probability of detecting a signal and False Positive Rate is the probability of a false alarm, ROC analysis is also widely used in medical studies, to determine the thresholds that confidently detect diseases or other behaviors[5].

A perfect model will have a False Positive of zero and True Positive Rate equal to one, so it will be a single operating point to the top left of the ROC plot. Whereas the worst possible model will have a single operating point on the bottom-right of the ROC plot, where the False Positive Rate is equal to one and True Positive Rate is equal to zero.

It [ROC Curve] provides a summary of sensitivity and specificity across a range of operating points, for a continuous predictor.

A random-guessing model, has a 50% chance of correctly predicting the result so, False Positive Rate will always be equal to the True Positive Rate. That’s why there’s a diagonal on the plot, representing that 50/50 chance of detecting signal vs noise.

Using Area Under the Curve (AUC) to evaluate Machine Learning models

Your parents have a cozy bed and breakfast and you, as a Data Scientist, set yourself up to the task of building a model that classifies their reviews as positive or negative.

To tackle this Sentiment Analysis task, you started off by using the Multilayer Perceptron and used accuracy and loss as a way to understand if was really good enough to solve your classification problem.

Knowing how ROC analysis is resistant to bias, and the fact that it’s used in Machine Learning to compare models or to compare different parameterizations of the same model, you want to see if the Multilayer Perceptron is actually a good model when it comes to classifying reviews from your parents’ bed and breakfast.

To rebuild the model, you take the corpus of reviews, then split it into training and testing and tokenize it.

from sklearn.model_selection import train_test_split
from sklearn.feature_extraction.text import TfidfVectorizer

corpus = [
    'We enjoyed our stay so much. The weather was not great, but everything else was perfect.',
    'Going to think twice before staying here again. The wifi was spotty and the rooms smaller than advertised',
    'The perfect place to relax and recharge.',
    'Never had such a relaxing vacation.',
    'The pictures were misleading, so I was expecting the common areas to be bigger. But the service was good.',
    'There were no clean linens when I got to my room and the breakfast options were not that many.',
    'Was expecting it to be a bit far from historical downtown, but it was almost impossible to drive through those narrow roads',
    'I thought that waking up with the chickens was fun, but I was wrong.',
    'Great place for a quick getaway from the city. Everyone is friendly and polite.',
    'Unfortunately it was raining during our stay, and there weren\'t many options for indoors activities. Everything was great, but there was literally no other oprionts besides being in the rain.',
    'The town festival was postponed, so the area was a complete ghost town. We were the only guests. Not the experience I was looking for.',
    'We had a lovely time. It\'s a fantastic place to go with the children, they loved all the animals.',
    'A little bit off the beaten track, but completely worth it. You can hear the birds sing in the morning and then you are greeted with the biggest, sincerest smiles from the owners. Loved it!',
    'It was good to be outside in the country, visiting old town. Everything was prepared to the upmost detail'
    'staff was friendly. Going to come back for sure.',
    'They didn\'t have enough staff for the amount of guests. It took some time to get our breakfast and we had to wait 20 minutes to get more information about the old town.',
    'The pictures looked way different.',
    'Best weekend in the countryside I\'ve ever had.',
    'Terrible. Slow staff, slow town. Only good thing was being surrounded by nature.',
    'Not as clean as advertised. Found some cobwebs in the corner of the room.',
    'It was a peaceful getaway in the countryside.',
    'Everyone was nice. Had a good time.',
    'The kids loved running around in nature, we loved the old town. Definitely going back.',
    'Had worse experiences.',
    'Surprised this was much different than what was on the website.',
    'Not that mindblowing.'
]

# 0: negative sentiment.  1: positive sentiment
targets = [1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0]

# Splitting the dataset
train_features, test_features, train_targets, test_targets = train_test_split(corpus, targets, test_size=0.25,random_state=123)

#Turning the corpus into a tf-idf array
vectorizer = TfidfVectorizer(stop_words='english', lowercase=True, norm='l1')

The Multilayer Perceptron model is ready to be trained.

from sklearn.neural_network import MLPClassifier

def buildMLPerceptron(train_features, train_targets, num_neurons=2):
    """ Build a Multi-layer Perceptron and fit the data
        Activation Function: ReLU
        Optimization Function: SGD, Stochastic Gradient Descent
        Learning Rate: Inverse Scaling
    """

    classifier = MLPClassifier(hidden_layer_sizes=num_neurons, max_iter=35, activation='relu', solver='sgd', verbose=10, random_state=762, learning_rate='invscaling')
    classifier.fit(train_features, train_targets)

    return classifier

train_features = vectorizer.fit_transform(train_features)
test_features = vectorizer.transform(test_features)

# Build Multi-Layer Perceptron with 3 hidden layers, each with 5 neurons
ml_percetron_model = buildMLPerceptron(train_features, train_targets, num_neurons=5)

All set to train the model! When you run the code above you’ll see something like the following.

To fully analyze the ROC Curve and compare the performance of the Multilayer Perceptron model you just built against a few other models, you actually want to calculate the Area Under the Curve (AUC), also referred to in literature as c-statistic.

The Area Under the Curve (AUC) has values between zero and one, since the curve is plotted on a 1x1 grid and, drawing a parallel with signal theory, it’s a measure of a signal’s detectability[6].

This is a very useful statistic, because it gives an idea of how well models can rank true observations as well as false observations. It’s actually a normalized version of the Wilcoxon-Mann-Whitney sum of ranks test, which tests the null hypothesis where two samples of ordinal measurements are drawn from a single distribution [4].

The c-statistic normalizes the number of pairs of one positive and one negative draws.

[…] drawing a parallel with signal theory, [the area under the curve] it’s a measure of a signal’s detectability.

To plot the ROC Curve and calculate the Area Under the Curve (AUC) you decided to use SckitLearn’s RocCurveDisplay method and compare your Multilayer Perceptron to a Random Forests model, attempting to solve the same classification task.

import matplotlib.pyplot as plt
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import roc_auc_score, RocCurveDisplay

def plot_roc(model, test_features, test_targets):
    """
    Plotting the ROC curve for a given Model and the ROC curve for a Random Forests Models
    """

    # comparing the given model with a Random Forests model
    random_forests_model = RandomForestClassifier(random_state=42)
    random_forests_model.fit(train_features, train_targets)

    rfc_disp = RocCurveDisplay.from_estimator(random_forests_model, test_features, test_targets)
    model_disp = RocCurveDisplay.from_estimator(model, test_features, test_targets, ax=rfc_disp.ax_)
    model_disp.figure_.suptitle("ROC curve: Multilayer Perceptron vs Random Forests")

    plt.show()

# using perceptron model as input
plot_roc(ml_percetron_model, test_features, test_targets)

The code above plots the ROC curves for your Multilayer Perceptron and the Random Forests model. It also calculates the Area Under the Curve (AUC) for both models.

Conclusion

From the ROC analysis plot and the value of the Area Under the Curve (AUC) for each model, you can see the overall AUC for your Multilayer Perceptron model, denoted in the plot as MLPClassifier, is slightly higher.

When compared to a Random Forests model attempting to solve the same task of classifying the sentiment of reviews for your parents’ bed and breakfast, the Multilayer Perceptron did a better job.

In this particular case, that’s also visible by how close the orange line starts getting to the top-left corner of the plot, where the True Positive Rate of the predictions is increasingly higher and, by opposition, the False Positive Rate is increasingly lower.

You can also see the Random Forests model is only slightly better than a Random Model, which would have an AUC equal to 0.5.

Hope you enjoyed learning about ROC analysis and the Area Under the Curve, two powerful techniques to compare Machine Learning models, using metrics that are more resistant to bias.

Thanks for reading!

References

1. Powers, David. (2008). Evaluation: From Precision, Recall and F-Factor to ROC, International Journal of Machine Learning Technology 2:1 (2011), pp.37–63
2. Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2021). An introduction to statistical learning : with applications in R. (2nd Edition) Springer
3. Streiner DL, Cairney J. What’s under the ROC? An Introduction to Receiver Operating Characteristics Curves. The Canadian Journal of Psychiatry. 2007;52(2):121–128
4. Flach, P.A. (2011). ROC Analysis. In: Sammut, C., Webb, G.I. (eds) Encyclopedia of Machine Learning. Springer, Boston, MA.
5. Cook NR. Use and misuse of the receiver operating characteristic curve in risk prediction. Circulation. 2007 Feb 20;115(7):928–35.
6. Green DM. A homily on signal detection theory. J Acoust Soc Am. 2020 Jul;148(1):222.

ROC Analysis and the AUC — Area Under the Curve was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is the second article in a series dedicated to Deep Learning, a group of Machine Learning methods that has its roots dating back to the 1940’s. Deep Learning gained attention in the last decades for its groundbreaking applications in areas like image classification, speech recognition, and machine translation.

The first article focused on the MultiLayer Perceptron. Stay tuned if you’d like to see different Deep Learning algorithms explained with real-life examples and some Python code.

The development of the MultiLayer Perceptron was an important landmark for Artificial Neural Networks. For the first time we could stack together many perceptrons and organize them in layers, to create models that best represent complex problems.

MultiLayer Perceptron works in an atemporal, discrete way. It takes one input vector, performs a feedforward computational step, back-propagates the errors, and stops once the loss function can’t be minimized any further, generating the output.

But lots of real-world problems involve a time dimension. What about when the problem at hand comes in the form of a sequence?

Neural Networks for Sentiment Analysis

In the previous article you used the MultiLayer Perceptron for the task of Sentiment Analysis. You took the reviews for your parents’ cozy bed and breakfast in the countryside, trained a MultiLayer Perceptron and predicted the overall sentiment of the review.

The MultiLayer perceptron used the tokenized word vector of each review as input, but it looked at each review a single, an atomic unit.

A more precise way of analyzing these reviews would take into account the position of each word the review, because the structure of a sentence plays a role in giving it meaning.

A much powerful model than the MultiLayer Perceptron would analyze reviews according to how each sentence is constructed. For instance, with sentences like This time around the service was great and The service was great this time around, it would be clever enough to determine these sentences have same sentiment[1]. Even though the words were shuffled around.

To go one step further in that sentiment analysis task, you need a different model.

You need a model that looks at each review as an ordered sequence of words, not an atomic unit. Each sequence of words can also have and an arbitrary length, since each sentence can be made up of a different number of words.

You need to build a Recurrent Neural Network.

Recurrent Neural Networks

Recurrent Neural Networks are used in several domains. For instance, in Natural Language Processing (NLP), they’ve been used to generate handwritten text, perform machine translation and speech recognition. But their applications are not restricted to processing language. In Computer Vision, Recurrent Neural Networks have been used in tasks like image captioning and image question-answer.

What distinguishes a Recurrent Neural Network from the MultiLayer Perceptron is that a Recurrent Neural Network is built to handle inputs that represent a sequence, like the sequence of words in a review from your parents’ bed and breakfast. But it also handles an output sequence, like when you’re translating a sentence from one language to another.

Recurrent Neural Networks act like a chain. The computation performed at each time step, depends on the previous computation.

The magic of Deep Learning training is in the hidden layers.

At the beginning of training the architecture of the network is defined, in this case, a Recurrent Neural Network. But we only know which inputs match with which outputs. The algorithm will learn how to use the hidden layers to make the best approximation of each input to output data point[1].

Visualizing a Recurrent Neural Network

One of the best ways to visualize a Recurrent Neural Network is as a cyclic computational graph[1]. In this representation the Recurrent Neural Network has three major states:

• Input state, which captures the input data for the model.
• Output state, which captures the results of the model.
• Recurrent state, which is in fact a chain of hidden states, and captures all the computations between the input and output states.

Similarly to other Supervised Machine Learning Models, Recurrent Neural Networks use a loss function to compare the output of the model to the ground truth. That loss is later back-propagated and model weights are update, like in the MultiLayer Perceptron.

This is a compressed view, more like a summary of the mechanics of Recurrent Neural Networks. In practice, it’s easier to visualize the recurrence when you unfold this graph. Especially when working with text sequences.

In this unfolded view of a Recurrent Neural Network each computation corresponds to one step, also referred to as internal state. And each step depends on the computation from the previous step.

As each internal state relies on the previous one, you have information that is propagated onto each layer of neurons in the network since the beginning of the sequence. Like an old memory that is passed on to future generations.

If MultiLayer Perceptron meant stacking multiple neurons in layers, Recurrent Neural Networks means chaining MultiLayer Perceptrons, to create a sequence of dependent computations.

In the case of a Recurrent Neural Network, memories are information about the computations applied to the sequence so far.

Recurrent Neural Network Superpower: Parameter Sharing

A single weight vector is shared across all time steps in the network.

A key characteristic of Recurrent Neural Networks is parameter sharing. There’s only one set of parameters that is used, and optimized, across all parts of the network. If those parameters were not shared, the model would have to learn the parameters for each part of the input sequence and would have a much harder time generalizing examples it had not seen yet[1].

Sharing parameters gives Recurrent Neural Networks the ability to handle inputs with different lengths, and still perform predictions in a an acceptable time frame.

Shared parameters are particularly important to generalize sequences that share inputs, although in different positions. In the case of your parent’s bed and breakfast reviews, without shared parameters, the network would have a much hard time, and would do repeated work learning the same language rules multiple times, to figure out sentences like This time around the service was great and The service was great this time around, have the same output sentiment.

This is a major advantage of RNNs because, without parameter sharing, you’d have to learn a different model for each time step in your sequence, and you’d need a large training set to accommodate the different model training steps.

In practice, parameter sharing means the output function is a result of the output from previous time steps, each step updated with the same rule. The latter being another important aspect of Recurrent Neural Networks, the update rule is the same, which means, at each time step, the network applies the same activation function.

Many Hidden States, the same Activation Function

The network can have as many hidden states as you’d like to, but there’s one important constant. In each hidden state you’re always computing the same activation function. The output of each layer is calculated using the same function[3].

The activation function can be as simple as a linear function or the sigmoid function. But the hyperbolic tangent is also commonly used in Deep Learning, because it tends to have fewer occurrences of vanishing gradients when compared to the sigmoid.

Training a deep neural network with hyperbolic tangent is as simple as training a linear model, as long as computations are small [1].

The hyperbolic tangent, represented as tanh(x), is a solid choice for activation function. It behaves like the identity function near zero, such that tanh(0) = 0.

So, as long as the computations for this activation function are small, training a deep neural network with hyperbolic tangent is as simple as training a linear model[1].

The output layer is special: it may need Softmax

Right now you might be thinking Didn’t you say that every layer uses the same activation function?

Yes but, in classification tasks, the output layer is special.

Specifically for Neural Networks that tackle classification problems, there’s also another activation function, applied only to output layer, almost like a post-processing step. Meet the Softmax function.

The output of a binary classification problem is either a 0 or a 1. But sometimes you’re tackling a multi-class problem, for instance, if the reviews for your parents’ bed and breakfast were categorized as Positive, Neutral or Negative.

In this case, with 3 possible output classes, it’s more useful to know how likely the observation is to belong to the positive class. This is why, along with the activation function you choose for the network, the Softmax function is applied in the output layer.

Vector z is the result of all the computations since the first layer, it’s the vector that reaches the output layer.

For instance, if your neural network only has one linear layer, vector z can be look like:

With Softmax, this vector is exponentiated and, since this is a classification task, normalized across all possible K classes, turning the vector into a probability distribution. That’s why Softmax is also called the Normalized exponential function.

After applying Softmax, the sum of all values of vector z always adds up to one. Its values represent the probability that the observation given to network in the input layer belongs to each class.

If you don’t apply Softmax to the output layer, the output of your Recurrent Neural Network is a number for

each of the possible classes. The output with the highest value is the winning class for that observation[3].

Backpropagation Through Time

So far you’ve looked into the broader architecture and components of a Recurrent Neural, i.e., the activation and loss functions. Let’s focus on the learning.

As the computations flow from each hidden in a layer to the next, it moves forward, towards the output layer. Reaching the output layer you compute the loss function, meaning you compare the output generated to the expected true value for that training observation.

If the process stopped here, the network would not be able to learn. It would be a feedfoward network, since information moves forward in the network structure. But learning needs some sort of loop. Just like when you learn something in school or on your own: information gets to your brain, this is the feedfoward part, then you process it and as you do this, you sanity-check and, sometimes re-learn certain things, this is the part I call the loop.

Neural networks are inspired by the brain, mostly inspired by how neurons work. But these neural network architectures, also have this a loop part. The part where they learn how to map the input data to one of the possible outcomes.

Back to Recurrent Neural Networks!

Inputs go through all the layers and, when it reaches the output layer it computes the loss function. Now, knowing how different, or distant, from the expected result that chain of computations was, it takes the value of the loss function and computes its gradient with respect to the parameters.

Then, with the help of another algorithm, like Stochastic Gradient Descent, that gradient is sent back in the opposite direction. All the way back to the input layer.

This way you’re back-propagating the loss function.

The actual computation of the gradient is what is called back-propagation [1]. But is usually confused with the actual learning part, accomplished by algorithms like Stochastic Gradient Descent.

Reaching the input layer Stochastic Gradient Descent, or other gradient-based optimizer algorithm, adjusts the network weights and the activation function is computed again through every hidden layer.

Each weight in the network is updated by subtracting the value of the gradient with respect to the loss function (J), from the current weight vector (theta). This is also called the weight change amount (vt).

The process goes on until the loss function can’t be minimized anymore, so there’s no point in adjusting weights once again, and the performance of the neural network is improved to the maximum given the current training set and architecture.

More complex algorithms and Neural Network Architectures may increase performance, but it also adds complexity to all computations, leading to longer training time.

In Machine Learning, you’re always dealing with trade-offs. With more complex models some of the trade-offs are (a) increasing performance, but reducing model interpretability or (b) increasing performance, but increasing training time.

RNNs in Action: Sentiment Analysis 👍 👎

Instead of building a Recurrent Neural Network from scratch, you’ve decided to use TensorFlow’s robust library to help with classify the sentiment from reviews of your parents bed and breakfast.

First thing you need is to install TensorFlow on your machine via pip, since you’re going to use the local Python environment.

Following the TensorFlow docs:

# Requires the latest pip
> pip install --upgrade pip

# Current stable release for CPU and GPU
> pip install tensorflow

Then you noticed there’s a robust example of Text Classification using RNNs on the TensorFlow resources[6]. That’s a good basis for what you want to do, you just need to adapt it to your own task.

At a glance, setting up a Recurrent Neural Network to classify the sentiment of all reviews from your parents’ bed and breakfast involves:

1. Organizing Training and Testing Files
2. Loading Training and Testing Datasets
3. Dimensionality Problem: Compressing your Dataset (Vectorization)
4. Building the Recurrent Neural Network
5. Model Fitting and Evaluation
6. Accuracy and Loss Visualized

Organizing Training and Testing Files

The first step is taking the reviews your cousins have helped classify and organizing them into the corresponding directories. There will be train and test directories, each one with sub-directories that contain positive and negative reviews.

After this organization, if you run the command tree on your project directory, you’ll have something like this:

What’s important in this step is there is only one review per file, so it can be properly loaded and processed in the following steps.

Loading Training and Testing Datasets

To load the train and test datasets you can leverage Keras utility method text_dataset_from_directory, which specifically requires the directory dataset structure you put together on the previous step.

Dimensionality Problem: Compressing your Dataset (Vectorization)

Your parents’ bed and breakfast reviews are not that lengthy. There will be more enthusiastic customers, who write a short essay about their experience but, from a data perspective, the result is a vector of relatively low dimensionality.

But what if your parents business was so popular that Travel and Leisure magazines start writing articles, essentially reviews, about them? In this case we’re talking about much larger dataset, and each review is a magazine article of at least 800 words.

In this scenario, you’re dealing with a dimensionality problem. You have very large and sparce vectors, which makes all matrix calculations computationally challenging.

To handle this situation you want to do something similar to what you do with Principal Component Analysis. You want to compress your dataset, while keeping all of its expressiveness, all its core characteristics.

“These are built from a very large corpus of documents by a variant of principal components analysis. The idea is that the positions of words in the embedding space preserve semantic meaning; e.g. synonyms should appear near each other.” [5]

A typical preprocessing step is to reduce the dimensionality with wor2vec[4]. In TensorFlow the Keras TextVectorization layer does something similar. It takes a string and either maps it to a 1-dimensional tensor of indices or a 1-dimensional tensor of floats that represent the data in the string.

At the end of this step, the training dataset is vectorized and the data preparation phase is complete.

Now you’re ready to build the Recurrent Neural Network.

Building the Recurrent Neural Network

Your Recurrent Neural Network model is, in practice, a group of Sequential layers.

The first one is the vocabulary encoder, created on the previous step. It’s used in the Embedding layer, which converts the values in the encoded vectors into a specific range.

For instance, the vocabulary in your reviews consists of 151 words, obtained by running:

len(encoder.get_vocabulary())

So the model takes the vocabulary size as input, via input_dim, and returns an output of size 64, defined using output_dim. And because you specified a vocabulary size of 151, the largest integer in the mapping will be 150.

The next layer, Bidirectional, indicates you want to create a bidirectional Recurrent Neural Network. This means the input of the network is propagates forwards and backwards through the NRR layers. The memories the network creates over time, as it is processing the input, are not only passed forward to the following cells, but are also passed to previous cells. Now, each cell in the network has information about the past and what lies ahead in the input sequence.

The advantage of using a Bidirectional Recurrent Neural Network is that is not just the previous information in the network that contributes to the output prediction. Knowing what is coming up ahead in the sequence can have a significant influence on how the model learns.

This advantage is a double-edged sword. As information is now propagated backwards and forwards, these networks tend to be much slower, because gradients now have a much longer dependency chain.

However, your parents’ bed and breakfast reviews is a small dataset. So you’ve decided it’s worth a try!

The last two layers in the model are Dense Layers. The second to last is used to process the model loss, with the hyperbolic tangent as activation. The last one reshapes the output to be of size 1, given that you want the output of the mode to be the positive or negative class index.

In this case, the RNN is created using 30 GRUCells. These Gated Recurrent Units (GRU) use the hyperbolic tangent as the activation function for recurrent step.

Model Fitting and Evaluation

Now that you’ve built and compiled the Recurrent Neural Network, it’s time to fit it to the training dataset and make some predictions.

A few parameters you can tune are:

• epochs how many times you’d like the algorithm to go through the entire training set
• shuffle in case you’d like to shuffle the training data before each epoch iteration. True by default
• validation_steps the number of batches of samples to draw before the validation step is concluded, and the algorithm starts the new epoch

Accuracy and Loss Visualized

As a final step, it’s always interesting to visualize the loss and accuracy of the model. Especially if it’s running through multiple iterations.

import os
import tensorflow as tf
import matplotlib.pyplot as plt

# Loading Training and Test Datasets
train_dir = os.path.join('', '../datasets/train')

train_dataset = tf.keras.utils.text_dataset_from_directory(
    train_dir, label_mode='int', labels='inferred', follow_links = True
)

test_dir = os.path.join('', '../datasets/test')

test_dataset = tf.keras.utils.text_dataset_from_directory(
    test_dir, label_mode='int', labels='inferred', follow_links = True
)

# Vectorize training dataset
VOCAB_SIZE = 5000
encoder = tf.keras.layers.TextVectorization(max_tokens=VOCAB_SIZE)
encoder.adapt(train_dataset.map(lambda text, label: text))

# Building the Recurrent Neural Network
# using GRU cells and Hyperbolic tangent as activation function
cell = tf.keras.layers.GRUCell(30, recurrent_activation='tanh')
model = tf.keras.Sequential([
    encoder,
    tf.keras.layers.Embedding(
        input_dim=len(encoder.get_vocabulary()),
        output_dim=64,
        # Use masking to handle the variable sequence lengths
        mask_zero=True),
    tf.keras.layers.Bidirectional(tf.keras.layers.RNN(cell)),
    tf.keras.layers.Dense(60, activation='tanh'),
    tf.keras.layers.Dense(1)
])

# Compile model and use the algorithm Adam as optimization function
model.compile(loss=tf.keras.losses.BinaryCrossentropy(from_logits=True), optimizer=tf.keras.optimizers.Adam(1e-2), metrics=['accuracy'])

# Fitting the model
history = model.fit(train_dataset, epochs=10, validation_data=test_dataset, validation_steps=10)

# Model Evaluation
test_loss, test_acc = model.evaluate(test_dataset)

print('Test Loss:', test_loss)
print('Test Accuracy:', test_acc)

# Visualize Model Loss and Accuracy
def plot_graphs(history, metric):
  plt.plot(history.history[metric])
  plt.plot(history.history['val_'+metric], '')
  plt.xlabel("Epochs")
  plt.ylabel(metric)
  plt.legend([metric, 'val_'+metric])

plt.figure(figsize=(16, 8))
plt.subplot(1, 2, 1)
plot_graphs(history, 'accuracy')
plt.ylim(None, 1)
plt.subplot(1, 2, 2)
plot_graphs(history, 'loss')
plt.ylim(0, None)

Here you’re also leveraging code from the handy example from TensorFlow’s documentation page to plot the loss and accuracy for the training and validation datasets.

After making predictions on the test dataset, the accuracy is far from perfect. It hovers around 0.5 which means your model is, technically, not much better than a random guess.

The accuracy stays very much stable at 50% throughout all evaluation epochs, and the loss starts steadily increasing after the third epoch.

But these results shouldn’t discourage you. Your dataset is very small and the RNN architecture used is very simplistic, and could definitely be refined. This is just a first run on understanding RNNs.

Conclusion

There are several different ways to build a recurrent neural network, depending on the task at hand.

It can have a one-to-many structure, like when the model has to create a caption for a given image. But if you’re translating English to French or vice-versa, you’ll be building a Recurrent neural network with a many-to-many structure.

For the Sentiment Analysis task or classifying all reviews from your parents’ cozy bed and breakfast, the network had a many-to-one structure, several words in a review contributing to a single output, the sentiment class. Either positive or negative.

The network you’ve created was relatively simple, and had an unimpressive 50% accuracy.

But I hope you got a better sense of what is a Recurrent Neural Network, why it is such game-changer Deep Learning network architecture, and the kinds of real-life problems it can be applied to.

Thanks for reading!

References

1. Goodfellow, Ian J., Bengio, Yoshua and Courville, Aaron. Deep Learning, MIT Press, 2016
2. The Unreasonable Effectiveness of Recurrent Neural Networks
3. Heaton, Jeff. Applications of Deep Neural Networks
4. Tomas Mikolov Kai Chen Greg S. Corrado Jeffrey Dean. Efficient Estimation of Word Representations in Vector Space. (2013)
5. Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2021). An introduction to statistical learning : with applications in R. (2nd Edition) Springer
6. Text classification with an RNN, TensorFlow Documentation

Recurrent Neural Networks Explained with a Real Life Example and Python Code was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is the first article in a series dedicated to Deep Learning, a group of Machine Learning methods that has its roots dating back to the 1940’s. Deep Learning gained attention in the last decades for its groundbreaking application in areas like image classification, speech recognition, and machine translation.

Stay tuned if you’d like to see different Deep Learning algorithms explained with real-life examples and some Python code.

This series of articles focuses on Deep Learning algorithms, which have been getting a lot of attention in the last few years, as many of its applications take center stage in our day-to-day life. From self-driving cars to voice assistants, face recognition or the ability to transcribe speech into text.

These applications are just the tip of the iceberg. A long path of research and incremental applications has been paved since the early 1940’s. The improvements and widespread applications we’re seeing today are the culmination of the hardware and data availability catching up with computational demands of these complex methods.

Why Deep Learning is Game Changing

In traditional Machine Learning anyone who is building a model either has to be an expert in the problem area they are working on, or team up with one. Without this expert knowledge, designing and engineering features becomes an increasingly difficult challenge[1]. The quality of a Machine Learning model depends on the quality of the dataset, but also on how well features encode the patterns in the data.

Deep Learning algorithms use Artificial Neural Networks as their main structure. What sets them apart from other algorithms is that they don’t require expert input during the feature design and engineering phase. Neural Networks can learn the characteristics of the data.

Deep Learning algorithms take in the dataset and learn its patterns, they learn how to represent the data with features they extract on their own. Then they combine different representations of the dataset, each one identifying a specific pattern or characteristic, into a more abstract, high-level representation of the dataset[1]. This hands-off approach, without much human intervention in feature design and extraction, allows algorithms to adapt much faster to the data at hand[2].

Neural Networks are inspired by, but not necessarily an exact model of, the structure of the brain. There’s a lot we still don’t know about the brain and how it works, but it has been serving as inspiration in many scientific areas due to its ability to develop intelligence. And although there are neural networks that were created with the sole purpose of understanding how brains work, Deep Learning as we know it today is not intended to replicate how the brain works. Instead, Deep Learning focuses on enabling systems that learn multiple levels of pattern composition[1].

And, as with any scientific progress, Deep Learning didn’t start off with the complex structures and widespread applications you see in recent literature.

It all started with a basic structure, one that resembles brain’s neuron.

It all started with a Neuron

In the early 1940’s Warren McCulloch, a neurophysiologist, teamed up with logician Walter Pitts to create a model of how brains work. It was a simple linear model that produced a positive or negative output, given a set of inputs and weights.

This model of computation was intentionally called neuron, because it tried to mimic how the core building block of the brain worked. Just like brain neurons receive electrical signals, McCulloch and Pitts’ neuron received inputs and, if these signals were strong enough, passed them on to other neurons.

The first application of the neuron replicated a logic gate, where you have one or two binary inputs, and a boolean function that only gets activated given the right inputs and weights.

However, this model had a problem. It couldn’t learn like the brain. The only way to get the desired output was if the weights, working as catalyst in the model, were set beforehand.

The nervous system is a net of neurons, each having a soma and an axon […] At any instant a neuron has some threshold, which excitation must exceed to initiate an impulse[3].

It was only a decade later that Frank Rosenblatt extended this model, and created an algorithm that could learn the weights in order to generate an output.

Building onto McCulloch and Pitt’s neuron, Rosenblatt developed the Perceptron.

Perceptron

Although today the Perceptron is widely recognized as an algorithm, it was initially intended as an image recognition machine. It gets its name from performing the human-like function of perception, seeing and recognizing images.

In particular, interest has been centered on the idea of a machine which would be capable of conceptualizing inputs impinging directly from the physical environment of light, sound, temperature, etc. — the “phenomenal world” with which we are all familiar — rather than requiring the intervention of a human agent to digest and code the necessary information.[4]

Rosenblatt’s perceptron machine relied on a basic unit of computation, the neuron. Just like in previous models, each neuron has a cell that receives a series of pairs of inputs and weights.

The major difference in Rosenblatt’s model is that inputs are combined in a weighted sum and, if the weighted sum exceeds a predefined threshold, the neuron fires and produces an output.

Threshold T represents the activation function. If the weighted sum of the inputs is greater than zero the neuron outputs the value 1, otherwise the output value is zero.

Perceptron for Binary Classification

With this discrete output, controlled by the activation function, the perceptron can be used as a binary classification model, defining a linear decision boundary. It finds the separating hyperplane that minimizes the distance between misclassified points and the decision boundary[6].

To minimize this distance, Perceptron uses Stochastic Gradient Descent as the optimization function.

If the data is linearly separable, it is guaranteed that Stochastic Gradient Descent will converge in a finite number of steps.

The last piece that Perceptron needs is the activation function, the function that determines if the neuron will fire or not.

Initial Perceptron models used sigmoid function, and just by looking at its shape, it makes a lot of sense!

The sigmoid function maps any real input to a value that is either 0 or 1, and encodes a non-linear function.

The neuron can receive negative numbers as input, and it will still be able to produce an output that is either 0 or 1.

But, if you look at Deep Learning papers and algorithms from the last decade, you’ll see the most of them use the Rectified Linear Unit (ReLU) as the neuron’s activation function.

The reason why ReLU became more adopted is that it allows better optimization using Stochastic Gradient Descent, more efficient computation and is scale-invariant, meaning, its characteristics are not affected by the scale of the input.

Putting it all together

The neuron receives inputs and picks an initial set of weights a random. These are combined in weighted sum and then ReLU, the activation function, determines the value of the output.

But you might be wondering, Doesn’t Perceptron actually learn the weights?

It does! Perceptron uses Stochastic Gradient Descent to find, or you might say learn, the set of weight that minimizes the distance between the misclassified points and the decision boundary. Once Stochastic Gradient Descent converges, the dataset is separated into two regions by a linear hyperplane.

Although it was said the Perceptron could represent any circuit and logic, the biggest criticism was that it couldn’t represent the XOR gate, exclusive OR, where the gate only returns 1 if the inputs are different.

This was proved almost a decade later by Minsky and Papert, in 1969[5] and highlights the fact that Perceptron, with only one neuron, can’t be applied to non-linear data.

Multilayer Perceptron

The Multilayer Perceptron was developed to tackle this limitation. It is a neural network where the mapping between inputs and output is non-linear.

A Multilayer Perceptron has input and output layers, and one or more hidden layers with many neurons stacked together. And while in the Perceptron the neuron must have an activation function that imposes a threshold, like ReLU or sigmoid, neurons in a Multilayer Perceptron can use any arbitrary activation function.

Multilayer Perceptron falls under the category of feedforward algorithms, because inputs are combined with the initial weights in a weighted sum and subjected to the activation function, just like in the Perceptron. But the difference is that each linear combination is propagated to the next layer.

Each layer is feeding the next one with the result of their computation, their internal representation of the data. This goes all the way through the hidden layers to the output layer.

But it has more to it.

If the algorithm only computed the weighted sums in each neuron, propagated results to the output layer, and stopped there, it wouldn’t be able to learn the weights that minimize the cost function. If the algorithm only computed one iteration, there would be no actual learning.

This is where Backpropagation[7] comes into play.

Backpropagation

Backpropagation is the learning mechanism that allows the Multilayer Perceptron to iteratively adjust the weights in the network, with the goal of minimizing the cost function.

There is one hard requirement for backpropagation to work properly. The function that combines inputs and weights in a neuron, for instance the weighted sum, and the threshold function, for instance ReLU, must be differentiable. These functions must have a bounded derivative, because Gradient Descent is typically the optimization function used in MultiLayer Perceptron.

In each iteration, after the weighted sums are forwarded through all layers, the gradient of the Mean Squared Error is computed across all input and output pairs. Then, to propagate it back, the weights of the first hidden layer are updated with the value of the gradient. That’s how the weights are propagated back to the starting point of the neural network!

This process keeps going until gradient for each input-output pair has converged, meaning the newly computed gradient hasn’t changed more than a specified convergence threshold, compared to the previous iteration.

Let’s see this with a real-world example.

Using Perceptron for Sentiment Analysis

Your parents have a cozy bed and breakfast in the countryside with the traditional guestbook in the lobby. Every guest is welcome to write a note before they leave and, so far, very few leave without writing a short note or inspirational quote. Some even leave drawings of Molly, the family dog.

Summer season is getting to a close, which means cleaning time, before work starts picking up again for the holidays. In the old storage room, you’ve stumbled upon a box full of guestbooks your parents kept over the years. Your first instinct? Let’s read everything!

After reading a few pages, you just had a much better idea. Why not try to understand if guests left a positive or negative message?

You’re a Data Scientist, so this is the perfect task for a binary classifier.

So you picked a handful of guestbooks at random, to use as training set, transcribed all the messages, gave it a classification of positive or negative sentiment, and then asked your cousins to classify them as well.

In Natural Language Processing tasks, some of the text can be ambiguous, so usually you have a corpus of text where the labels were agreed upon by 3 experts, to avoid ties.

With the final labels assigned to the entire corpus, you decided to fit the data to a Perceptron, the simplest neural network of all.

But before building the model itself, you needed to turn that free text into a format the Machine Learning model could work with.

In this case, you represented the text from the guestbooks as a vector using the Term Frequency — Inverse Document Frequency (TF-IDF). This method encodes any kind of text as a statistic of how frequent each word, or term, is in each sentence and the entire document.

In Python you used TfidfVectorizer method from ScikitLearn, removing English stop-words and even applying L1 normalization.

TfidfVectorizer(stop_words='english', lowercase=True, norm='l1')

On to binary classification with Perceptron!

To accomplish this, you used Perceptron completely out-of-the-box, with all the default parameters.

After vectorizing the corpus and fitting the model and testing on sentences the model has never seen before, you realize the Mean Accuracy of this model is 67%.

That’s not bad for a simple neural network like Perceptron!

On average, Perceptron will misclassify roughly 1 in every 3 messages your parents’ guests wrote. Which makes you wonder if perhaps this data is not linearly separable and that you could also achieve a better result with a slightly more complex neural network.

How would MultiLayer Perceptron perform in this case?

Using SckitLearn’s MultiLayer Perceptron, you decided to keep it simple and tweak just a few parameters:

• Activation function: ReLU, specified with the parameter activation=’relu’
• Optimization function: Stochastic Gradient Descent, specified with the parameter solver=’sgd’
• Learning rate: Inverse Scaling, specified with the parameter learning_rate=’invscaling’
• Number of iterations: 20, specified with the parameter max_iter=20

By default, Multilayer Perceptron has three hidden layers, but you want to see how the number of neurons in each layer impacts performance, so you start off with 2 neurons per hidden layer, setting the parameter num_neurons=2.

Finally, to see the value of the loss function at each iteration, you also added the parameter verbose=True.

In this case, the Multilayer Perceptron has 3 hidden layers with 2 nodes each, performs much worse than a simple Perceptron.

It converges relatively fast, in 24 iterations, but the mean accuracy is not good.

While the Perceptron misclassified on average 1 in every 3 sentences, this Multilayer Perceptron is kind of the opposite, on average predicts the correct label 1 in every 3 sentences.

What about if you added more capacity to the neural network? What happens when each hidden layer has more neurons to learn the patterns of the dataset?

Using the same method, you can simply change the num_neurons parameter an set it, for instance, to 5.

buildMLPerceptron(train_features, test_features, train_targets, test_targets, num_neurons=5)

Adding more neurons to the hidden layers definitely improved Model accuracy!

You kept the same neural network structure, 3 hidden layers, but with the increased computational power of the 5 neurons, the model got better at understanding the patterns in the data. It converged much faster and mean accuracy doubled!

In the end, for this specific case and dataset, the Multilayer Perceptron performs as well as a simple Perceptron. But it was definitely a great exercise to see how changing the number of neurons in each hidden-layer impacts model performance.

It’s not a perfect model, there’s possibly some room for improvement, but the next time a guest leaves a message that your parents are not sure if it’s positive or negative, you can use Perceptron to get a second opinion.

Conclusion

The first Deep Learning algorithm was very simple, compared to the current state-of-the-art. Perceptron is a neural network with only one neuron, and can only understand linear relationships between the input and output data provided.

However, with Multilayer Perceptron, horizons are expanded and now this neural network can have many layers of neurons, and ready to learn more complex patterns.

Hope you’ve enjoyed learning about algorithms!

Stay tuned for the next articles in this series, where we continue to explore Deep Learning algorithms.

References

1. LeCun, Y., Bengio, Y. & Hinton, G. Deep learning. Nature 521, 436–444 (2015)
2. Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. The MIT Press.
3. McCulloch, W.S., Pitts, W. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics 5, 115–133 (1943)
4. Frank Rosenblatt. The Perceptron, a Perceiving and Recognizing Automaton Project Para. Cornell Aeronautical Laboratory 85, 460–461 (1957)
5. Minsky M. L. and Papert S. A. 1969. Perceptrons. Cambridge, MA: MIT Press.
6. Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2013). An introduction to statistical learning : with applications in R. New York :Springer
7. D. Rumelhart, G. Hinton, and R. Williams. Learning Representations by Back-propagating Errors. Nature 323 (6088): 533–536 (1986).

Multilayer Perceptron Explained with a Real-Life Example and Python Code: Sentiment Analysis was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

Gradient Boosted Decision Trees Explained with a Real-Life Example and Some Python Code

Gradient Boosting algorithms tackle one of the biggest problems in Machine Learning: bias.

This is the third and last article in a series dedicated to Tree Based Algorithms, a group of widely used Supervised Machine Learning Algorithms.

The first article was about Decision Trees, while the second explored Random Forests. Everything explained with real-life examples and some Python code.

Gradient Boosting algorithms tackle one of the biggest problems in Machine Learning: bias.

Decision Trees is a simple and flexible algorithm. So simple to the point it can underfit the data.

An underfit Decision Tree has low depth, meaning it splits the dataset only a few of times in an attempt to separate the data. Because it doesn’t separate the dataset into more and more distinct observations, it can’t capture the true patterns in it.

When it comes to tree-based algorithms Random Forests was revolutionary, because it used Bagging to reduce the overall variance of the model with an ensemble of random trees.

In Gradient Boosted algorithms the technique used to control bias is called Boosting.

In the late 1980’s and 1990’s, Robert Schapire and Yoav Freund developed one of the most popular Boosting algorithms, AdaBoost, to address underfitting and reduce bias.

But they were not alone. The field of Computer Science and Theoretical Machine Learning was riding this wave of enthusiasm and groundbreaking algorithms, and more scientists started developing Boosting approaches.

Friedman explored how Boosting can be the optimization method for an adequate loss function. While Schapire and Freund took inspiration on a question posed by Michael Kearns, Can a set of weak learners create a single strong learner?

In this context, a weak learner is any model that is slightly better than a random model, and will never efficiently achieve a training error of zero. A strong learner is the opposite, a model that can be improved and efficiently bring the training error down to zero.

Around the same time Jerome Freidman, was also experimenting with Boosting. He ended up developing several new algorithms, the most popular being Gradient Boosted Decision Trees.

The ingenious efforts of these and other scientists contributed to a vibrant new chapter in Machine Learning. It generated robust and powerful algorithms. Many of which are still relevant today.

Boosting 101

The motto with Boosting is that the result is greater than the sum of its parts.

Boosting is based on the assumption that it’s much easier to find several simple rules to make a prediction than it is to find the one rule that is applicable to all data and generates the best possible prediction[1].

The intuition behind Boosting is that you train the same weak learner, a model with simple rules, several times. Then combine its weak predictions into a single, more accurate result. The model is always of the same type same but, each time, it is trained with different weights for the observations it misclassified.

Predictions that were previously misclassified will have more weight on the next weak learner, so each weak learner focuses on the hardest observations[1].

When you combine different weak learners sequentially, each one will make some incorrect predictions. But they will cover each others blindspots, making better predictions where other learners were not as good. Each model learns slowly from the errors the previous one made[2].

What’s common across all Boosting Algorithms

All Boosting algorithms are ensemble Classifiers or Regressors, depending on the task at hand, because they combine the results of several models.

In the aggregation step of a Regression task you might compute the weighted sum of all predictions for each observation. While in a classification task, a majority vote decides which class to assign.

Creating a Boosting Ensemble

Most algorithms focus on parameter estimation, to find the parameters that minimize their loss function. Boosting algorithms focus on function estimation.

The ensemble of weak learners is actually a set of functions that map features to targets and minimize the loss function[3].

And because the optimization algorithm used to find the next weak learner is Gradient Descent, the loss function must differentiable and convex.

However, this time Gradient Descent is used in a function space.

Typically, Gradient Descent starts off at a random point in a differentiable convex function, and only stops when it finds its minimum value.

The same concept is translated Boosting algorithms with a Gradient Descent, but in the function space.

The algorithm starts off with a very simple weak learner, for instance, always predicting the class 0.

With each weak learner added to the ensemble the algorithm is taking a step towards the right targets, because it only adds weak learners that minimizes the loss function.

The exponential loss is typically used in Classification tasks while in Regression tasks it’s the Squared Loss.

Gradient Boosted Decision Trees vs Adaboost vs …

All Boosting algorithms share a common principle, they use Boosting to create an ensemble of learners that are later combined. But each of them has distinct characteristics that make them more suitable for particular tasks.

For instance, in Gradient Boosted Decision Trees, the weak learner is always a decision tree.

In Stochastic Gradient Boosting, Friedman introduces randomness in the algorithm similarly to what happens in Bagging. At each iteration, instead of using the entire training dataset with different weights, the algorithm picks a sample of the training dataset at random without replacement and uses that to train the next learner[4].

Adaboost is in many ways similar to Gradient Boosted Decision Trees, in a sense that you have the distribution of weights for each observation in the training dataset and, in each iteration the algorithm adjusts those weights based on how the previous weak learner performed. But its adaptive nature comes into play when, during each iteration, it chooses a new the learning rate alpha based on the weak learner’s error rate[1].

Now that you know a bit more about the different Boosting algorithms, let’s see them in practice!

🛩🏝 Reducing model Bias with Boosting Algorithms

Planning a vacation is challenging. The hardest part, picking a destination.

But you’re a Data Scientist. You’re confident that Machine Learning can give an algorithmic opinion on what should be your next vacation destination.

Whenever planning a vacation, you always take into account:

• Duration of the vacation,
• Personal budget,
• Weather forecast,
• If your extended family is joining,
• If you’re feeling adventurous and want to explore new places.

When it comes to picking a classification algorithm, you know Decision Trees are said to mimic how humans make decisions. But it has limitations, just a single Decision Tree is not a very powerful predictor.

Random Forests would get you better results, if you’re focused on controlling bias, not model variance. So Random Forests is not an option.

Since using a low bias model is your goal, Boosting algorithms are exactly what you’re looking for.

The firs thing you do is to go through your old notes and collect some data on how you picked previous vacation destinations. You gather all the information like your budget at the time and the duration of the vacation, and your previous destinations, which were typically a choice between Beach and Countryside.

In the code below I’m creating a synthetic dataset to simulate that data.

Spotting Model Bias

The whole reason you want to use a Boosting algorithm is to control model bias.

In a Regression task, where you predict numerical values, Bias is described by this equation:

In this case, you just need plug the numbers in the formula.

But you’re trying to get an algorithmic opinion on your next vacation destination, a classification task.

For this purpose, you can use the misclassification rate, i.e, average of the 0–1 loss.

If your model has a high proportion of misclassified observations in the training set, it means it has high bias.

Boosting algorithms ✅ Method to calculate Bias ✅

So you start with the the simplest algorithm Decision Trees. With ScikitLearns’ Decision Tree Classifier you create a single decision tree that only splits the dataset twice. That’s why max_depth=2.

The average misclassification rate in the training set, the 0–1 loss, is 44%. That’s almost as good as a random model! High Bias ✅

Now you turn to a Gradient Boosted Classifier.

You set the depth of each weak learner in the ensemble to 1, using the parameter max_depth once again. In this case you’re training the smallest tree possible, what in the machine learning lingo it’s called a decision stump.

And in terms of the size of the ensemble, you picked a rather arbitrary number, 210 trees. That’s the parameter n_estimators in the GradientBoostingClassifier method.

Gradient Boosted Decision Trees did indeed reduce Bias. A 0–1 loss of 32% is much better!

Ok, you built a model with relatively low bias. But you know there are other Boosting algorithms out there, besides Gradient Boosted Decision Trees.

How much better would Adaboost be at predicting your next vacation destination?

In the case of Adaboost, training the same number of trees didn’t reduce bias as much. But it still brought the misclassification rate down to 38%, from the 44% observed with Decision Trees.

When it goes to picking your next vacation destination, with the dataset at hand, Gradient Boosted Decision Trees is the model with lowest bias.

Now all you need to do is give the algorithm all information about your next vacation, i.e., the duration, if you’re feeling adventurous and all that.

The algorithm will tell you if your next vacation should be a Beach vacation or on the Countryside.

Conclusion

Now you can be confident about using Gradient Boosting Decision Trees to predict your next vacation destination. Instead of training just a single Decision Tree.

What sets Gradient Boosted Decision trees apart from other approaches is:

• Speed, the algorithm is memory efficient so you can make predictions much faster.
• No preprocessing required you don’t need to prepare the data before building the model.
• Data robustness the algorithm handles all types of data nicely.

Event thought it is more complex than Decision Trees, it continues to share the advantages of tree-based algorithms.

But there’s always a catch. Gradient Boosted Decision Trees make two important trade-offs:

• Faster predictions over slower training,
• Performance over interpretability.

Faster predictions vs slower training

Even though one of the advantages mentioned above is the memory efficiency, that is when it comes to make predictions.

The algorithm is more complex and builds each tree sequentially. It’s predictions are fast, but the training phase is computationally more demanding.

Performance over interpretability

Similarly to what happens with Random Forests, you trade-off performance for interpretability.

You’ll no longer be able to see exactly how the algorithm split each tree node to reach the final prediction.

Hope you enjoyed learning about Boosting algorithms, the problems the address and what ultimately makes them unique.

Make sure to check the other two articles in this Tree-based Machine Learning algorithms series. The first one explores Decision Trees and the second Random Forests.

Thanks for reading!

References

1. Schapire Robert E. (2002) The Boosting Approach to Machine Learning: An Overview
2. Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2013). An introduction to statistical learning : with applications in R. New York :Springer
3. Friedman, J.H., 2001. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189–1232.
4. Friedman, J.H., 1999. Stochastic Gradient Boosting. Computational Statistics and Data Analysis. 38 pp. 367–368

Gradient Boosted Decision Trees explained with a real-life example and some Python code was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is article number two in a series dedicated to Tree Based Algorithms, a group of widely used Supervised Machine Learning Algorithms.

The first article was about Decision Trees. The next, and last article in this series, explores Gradient Boosted Decision Trees. Everything explained with real-life examples and some Python code.

Stay tuned!

Random Forests is a Machine Learning algorithm that tackles one of the biggest problems with Decision Trees: variance.

Even though Decision Trees is simple and flexible, it is greedy algorithm. It focuses on optimizing for the node split at hand, rather than taking into account how that split impacts the entire tree. A greedy approach makes Decision Trees run faster, but makes it prone overfitting.

An overfit tree is highly optimized to predicting the values in the training dataset, resulting in a learning model with high-variance.

How you calculate variance in a Decision Tree depends on the problem you’re solving.

In a Regression task you can calculate actual variance of the prediction compared to the true targets. If the tree produces results that are too far off from its true targets, it has high-variance and therefore, it is overfit.

A highly overfit tree has high-variance. That means its predictions are extremely far off from the actual targets.

But in a Classification task, you can’t use the same approach. The way to detect if the Decision Tree is overfit is by looking at the test error. If the tree has a high test error, meaning it’s not good at classifying observations it wasn’t trained on, it is overfit.

In Regression tasks overfitting is detected by high-variance, while in Classification tasks it’s by a high generalization error.

To address overfitting, and reduce the variance in Decision Trees, Leo Breiman developed the Random Forests algorithm[1]. This was an innovative algorithm because it utilized, for the first time, the statistical technique of Bootstrapping and combined the results of training multiple models into a single, more powerful learning model.

But before you see Random Forests in action, and code, let’s take a detour to explore what makes Random Forests unique.

Bagging: Bootstrap Aggregation

Bagging, short for Bootstrap Aggregation, is a technique developed by Leo Breiman, with the goal of reducing the variance of a learning model. Bagging is also model agnostic, so regardless of type of model you’re using, the process is the same.

The Bootstrapping part of Bagging refers to the resampling method in which several random samples are drawn with replacement from a dataset[3]. As a consequence, Bootstrapping creates multiple, smaller random datasets drawn from the same distribution.

Each of the bootstrapped datasets is used to train a model, and the outputs are then Aggregated into one final result.

But aggregation also means different things, depending on the type of problem you’re solving.

When you’re working on a Regression problem, aggregation means averaging the results of each observation, across all models. While in Classification aggregation means picking the most common class for each observation, like doing a majority vote.

This is impressive but, how does this actually help reduce model variance?

Each model is trained on a different dataset, because they’re bootstrapped. So inevitably, each model will make different mistakes, and have a distinct error and variance. Both the error and variance get reduced in the aggregation step where, literally in the case of Regression, they are averaged out.

And because you end up with a single model, which combines the output of multiple models, Bagging is called and ensemble technique.

Bootstrapping

With Bootstrapping you’re following the motto of doing more with less. You’re taking one dataset and multiplying it into several smaller random datasets.

The initial dataset only had 10 elements, but you ended producing 5 sampled datasets of size 4.

In a way, you multiplied the dataset, going from just 10 observations to 4x5=20 observations, when you sum up the individual bootstrapped datasets.

The reason why Bootstrapping works is because you’re sampling with replacement.

You can pick the same datapoint multiple times, like in the last two samples, but each sampled dataset is slightly different from the previous one.

Without replacement you’d quickly run out of data points, and would only be able to generate a limited number of samples.

This detour was focused on what makes Random Forest unique.

Let’s get back to the main topic, how Random Forests reduces model variance.

Random Forests

Random Forests was developed specifically to address the problem of high-variance in Decision Trees. Like the name suggests, you’re not training a single Decision Tree, you’re training an entire forest! In this case, a forest of Bagged Decision Trees.

At a high-level, in pseudo-code, Random Forests algorithm follows these steps:

1. Take the original dataset and create N bagged samples of size n, with n smaller than the original dataset.
2. Train a Decision Tree with each of the N bagged datasets as input. But, when doing a node split, don’t explore all features in the dataset. Randomly select a smaller number, M features, from all the features in training set. Then pick the best split using impurity measures, like Gini Impurity or Entropy.
3. Aggregate the results of the individual decision trees into a single output.
4. Average the values for each observation, produced by each tree, if you’re working on a Regression task.
5. Do a majority vote across all trees, for each observation, if you’re working on a Classification task.

While Forest part of Random Forests refers to training multiple trees, the Random part is present at two different points in the algorithm.

There’s the randomness involved in the Bagging process. But then, you also pick a random subset of features to evaluate the node split. This is what guarantees that each tree is different and, therefore, ensures each model produces a slightly different result.

And while you could be thinking that randomly sampling features at each split introduces yet another hyperparameter you might need to tune, that’s not the case. The model takes care of it for you!

You can certainly tune this hyperparameter. However, there’s mathematical consensus about randomly picking a number of features that is equal to the square root of the total number of available features in the dataset[2].

Why use Random Forests?

Random Forests has several advantages, when compared to training a single Decision Tree.

All the advantages of Decision Trees, but more powerful

At the core of this algorithm is a Decision Tree so, Random Forests shares all its advantages.

It’s a data robust algorithm, being able to handle different types of data, and doesn’t require any data preprocessing.

The true potential of Random Forests comes from combining the results different Decision Trees.

Each model is different

Like Decision Trees, the algorithm optimizes for the local split. But, instead of exploring all possible splits for each feature in the dataset, it randomly picks a subset of those features.

This reduces the number of outcomes the algorithm needs to evaluate at each split and, it makes each trained tree is slightly different.

No holdout set required

In Machine Learning you typically split the dataset into training and testing sets, in an effort to evaluate model performance with observations it has never seen before.

This becomes a challenging problem when you have a small dataset or the cost, and effort, of collecting more data is high.

But with Random Forests you can use the entire dataset to train and evaluate the model. The Bagging process takes care of it for you! Since you’re generating N smaller, random datasets picked with replacement, there’s always going to be a set of points that was not used to create the tree.

Take a look at the earlier example, which bootstrapped the dataset [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

If you were to use each of these samples to train a Decision Tree, there are observations the trees simply don’t know about, because they were not part of their training set.

With Random Forests you can use the entire dataset to train the model and calculate the test error directly from its results. You don’t need to set aside part of the dataset just for testing.

This new type of error, calculated directly from its results of the trained trees, is called the Out-of-bag Error.

🛩🏝 Reducing model variance with Random Forests

Planning a vacation is challenging. This time you’re going to put your Machine Learning skills into practice and get an algorithmic opinion on what should be your next vacation destination.

Whenever you start planning a vacation, you always take into account:

• Duration of the vacation,
• Personal budget,
• Weather forecast,
• If your extended family is joining,
• If you’re feeling adventurous and want to explore new places.

Decision Trees are said to mimic how humans make decisions. But as you’ve seen on the previous article of this series, a single Decision Tree is not a very powerful predictor.

Random Forests is an improvement on Decision Trees, but is it really that much better?

There’s only one way to find out!

But first, take another look at the performance of a single Decision Tree.

Test error for a single Decision Tree

If you train just one Decision Tree, the test error is approximately 70%.

The test error, also known as generalization error, is considerably high. A sign of high variance.

Ok, you’re convinced! Decision Trees is definitely not the best algorithm to help you in the critical task of picking the next vacation destination.

Let’s train a Random Forests model using ScikitLearn, completely out-of-the-box and without any hyperparameter tuning.

Right away Random Forests reduced the Test Error by 30%!

This is an impressive result, comparing to the performance of a single Decision Tree.

One thing you noticed was that, by default the algorithm trains and combines the result of 100 bagged trees. This is one of the many hyperparameters you can tune in Random Forests.

Curiosity just kicked-in!

Why 100 trees?

Would the algorithm perform better or worse with a different number of trees?

How much can you reduce the generalization error?

Find the Optimal Number of Trees

Instead of tuning this hyperparameter by trail and error, you decided plot the Out-Of-Bag-Error as a function of the number of trees in the Random Forest.

You settled on training the arbitrary number of 150 trees. But you’re starting with only 5 and slowly making your way up to 150, building a new model, each time with one additional tree.

Training a large forest doesn’t improve the model.

In the process you’ve found the performance sweet spot for your task. You only need 8 trees in the Random Forests to drop the generalization error to 33%.

Looking at the plot, it’s easier to see the Out-Of-Bag Error getting worse past the sweet-spot of 8 trees. Then the model hits a performance plateau, when the forest gets bigger than 50 trees.

Conclusion

You successfully reduced the variance of your model!

Now you can be more confident about using Random Forests to predict your next vacation destination. Instead of training a single Decision Tree.

This was a simple example, but you could see the generalization error decline significantly, from 67% to 33%.

Random Forests is a powerful algorithm, but it has a clear disadvantage. You can’t see how the model makes decisions.

A cool aspect of Decision Trees is that, after the model is trained, you can actually visualize how the model makes decisions. With a small enough tree you can trace the entire decision-making process for a new observation.

But with Random Forests, you trade-off interpretability for performance.

As soon as you start combining the decisions of multiple trees, the decision process gets much more complex and impossible to visualize.

Hope you enjoyed learning about Random Forests, and why it is more powerful than Decision Trees.

Stay tuned for the next article and last in this series! It’s about Gradient Boosted Decision Trees. Explained with a real-life example and some Python code.

References

1. Breiman, L. Random Forests. Machine Learning 45, 5–32 (2001)
2. Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2013). An introduction to statistical learning : with applications in R. New York :Springer
3. Breiman, L. Bagging predictors. Mach Learn 24, 123–140 (1996)

Random Forests Algorithm explained with a real-life example and some Python code was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

Decision Tree is a Supervised Machine Learning Algorithm that uses a set of rules to make decisions, similarly to how humans make decisions.

This is article number one in a series dedicated to Tree Based Algorithms, a group of widely used Supervised Machine Learning Algorithms.

Stay tuned if you’d like to see Decision Trees, Random Forests and Gradient Boosting Decision Trees, explained with real-life examples and some Python code.

Decision Tree is a Supervised Machine Learning Algorithm that uses a set of rules to make decisions, similarly to how humans make decisions.

One way to think of a Machine Learning classification algorithm is that it is built to make decisions.

You usually say the model predicts the class of the new, never-seen-before input but, behind the scenes, the algorithm has to decide which class to assign.

Some classification algorithms are probabilistic, like Naive Bayes, but there’s also a rule-based approach.

We humans, also make rule-based decisions all the time.

When you’re planning your next vacation, you use a rule-based approach. You might pick a different destination based on how long you’re going to be on vacation, the budget available or if your extended family is coming along.

The answer to these questions informs the final decision. And if you continually narrow down the available vacation destinations based on how you answer each question, you can visualize this decision process as a (decision) tree.

A tree that makes decisions

Decision trees can perform both classification and regression tasks, so you’ll see authors refer to them as CART algorithm: Classification and Regression Tree. This is an umbrella term, applicable to all tree-based algorithms, not just decision trees.

But let’s focus on decision trees for classification.

The intuition behind Decision Trees is that you use the dataset features to create yes/no questions and continually split the dataset until you isolate all data points belonging to each class.

With this process you’re organizing the data in a tree structure.

Every time you ask a question you’re adding a node to the tree. And the first node is called the root node.

The result of asking a question splits the dataset based on the value of a feature, and creates new nodes.

If you decide to stop the process after a split, the last nodes created are called leaf nodes.

Every time you answer a question, you’re also creating branches and segmenting the feature space into disjoint regions[1].

One branch of the tree has all data points corresponding to answering Yes to the question the rule in the previous node implied. The other branch has a node with the remaining data points.

This way you narrow down the feature space with each split or branch in the tree, and each data point will only belong to one region.

The goal is to continue to splitting the feature space, and applying rules, until you don’t have any more rules to apply or no data points left.

Then, it’s time to assign a class to all data points in each leaf node.

Assigning a class

The algorithm tries to completely separate the dataset such that all leaf nodes, i.e., the nodes that don’t split the data further, belong to a single class. These are called pure leaf nodes.

But most times you end up with mixed leaf nodes, where not all data points have to the same class.

In the end, the algorithm can only assign one class to the data points in each leaf node.

With pure leaf nodes that already taken care of, because all data points in that node have the same class.

But with mixed leaf nodes the algorithm assigns the most common class among all data points in that node.

It’s hard to build the perfect tree

The ideal tree is the smallest tree possible, i.e. with fewer splits, that can accurately classify all data points.

This sounds simple, but it’s actually a NP hard problem. Building the ideal tree would take polynomial time, which increases exponentially as the dataset grows.

For example, for a dataset with only 10 data points and an algorithm with quadratic complexity, O(n²), the algorithm executes 10*10 = 100 iterations to build the tree. Expand that dataset a bit more to have 100 data points, and the number of iterations the algorithm will execute jumps to 10,000.

Finding the best tree is ideal in theory, but as the dataset grows, it becomes computationally unfeasible!

To turn this NP-hard problem into something computationally feasible the algorithm uses a greedy approach to build the next best tree.

A greedy approach makes locally optimal decisions to pick the feature used in each split, instead of trying to make the best overall decision[2].

Since it optimizes for local decisions, it focuses only on the node at hand, and what’s best for that node in particular. So it doesn’t need to explore all possible splits for that node and beyond.

Picking the best split

On every split, the algorithm tries to divide the dataset into the smallest subset possible[2]. So, like any other Machine Learning algorithm, the goal is to minimize the loss function as much as possible.

A popular loss function for classification algorithms is Stochastic Gradient Descent but, it requires the loss function to be differentiable. So, it’s not an option in this case.

But since you’re separating data points that belong to different classes, the loss function should evaluate a split based on the proportion of data points belonging to each class before and after the split.

Decision Tree use loss functions that evaluate the split based on the purity of the resulting nodes.

n order words, you’d want a loss function that evaluates the split based on the purity of the resulting nodes. A loss function that compares the class distribution before and after the split[2], like Gini Impurity and Entropy.

Gini Impurity

Gini Impurity is measure of variance across the different classes[1].

Entropy

Similarly to Gini Impurity, Entropy is a measure of chaos within the node. And chaos, in the context of decision trees, is having a node where all classes are equally present in the data.

Using Entropy as loss function, a split is only performed if the Entropy of each the resulting nodes is lower than the Entropy of the parent node. Otherwise, the split is not locally optimal.

Why you want to use Decision Trees

Even though Decision trees is a simple algorithm, it has several advantages:

• Interpretability you can visualize the decision tree.
• No preprocessing required you don’t need to prepare the data before building the model.
• Data robustness the algorithm handles all types of data nicely.

Interpretability: visualizing trees

One of the biggest advantages of tree-based algorithms it that you can actually visualize the model.

You can see the decisions the algorithm made, and how it classified the different data points.

This is a major advantage, because most algorithms work like blackboxes, and it’s hard to clearly pinpoint what made the algorithm predict a specific result.

No preprocessing required

Several machine learning algorithms require feature values to be as similar as possible, so the algorithm can best interpret how the changes in those features impact the target.

The most common preprocessing requirement is feature normalization, so all features in the same scale and any change in those values has the same proportional weight.

The rules in tree-based algorithms are built around each individual feature, instead of considering the entire feature set. Each decision is made looking at one feature at a time, so their values don’t need to be normalized.

Data robustness

Tree-based algorithms are great at handling different data types. Your dataset can have a mix of numerical and categorical data, and you won’t need to encode any of the categorial features.

This is an item on the pre-processing checklist that tree-based algorithms handle on their own.

🛩🏝 Picking a vacation destination

Planning the next vacation can be challenging. Vacations are never long enough, there are budget constraints, and sometimes the extended family wants to come along, which makes logistics more complicated.

You like the idea of asking for a second opinion, from an algorithm, when it’s time to make a decision that involves way too many variables to keep track of. Picking a vacation destination is a perfect example!

Whenever you start planning a vacation, you always take into account:

• Duration of the vacation,
• Personal budget,
• Weather forecast,
• If your extended family is joining,
• If you’re feeling adventurous and want to explore new places.

Since Decision Trees are said to mimic how humans make decisions, that’s the algorithm you’re using.

The bonus piece it that, in the end, you’ll be able to visualize the decision tree and see how the algorithm picked the destination.

Thinking through your decision process for previous vacations and the criteria you always take into consideration, you put together a dataset.

Even though the Decision Tree algorithm can handle different data types, ScikitLearn’s current implementation doesn’t support categorical data.

To use the Decision Tree classifier from ScikitLearn, you can’t skip the pre-processing step and need to encode all categorical features and targets before training the model.

import numpy as np
from sklearn import preprocessing

def encode_feature(array):
    """ Encode a categorical array into a number array
    
    :param array: array to be encoded
    :return: numerical array
    """
  
    encoder = preprocessing.LabelEncoder()
    encoder.fit(array)
    return encoder.transform(array)

feature_names = ['number_days', 'family_joining', 'personal_budget', 'weather_forecast', 'explore_new_places']

class_names = ['Countryside', 'Beach']

features = np.array([[10, 'Yes', 950, 75, 'Yes'],
                     [10, 'Yes', 250, 78, 'Yes'],
                     [7, 'Yes', 600, 80, 'No'],
                     [8, 'Yes', 750, 67, 'Yes'],
                     [10, 'Yes', 800, 73, 'Yes'],
                     [8, 'Yes', 850, 64, 'Yes'],
                     [15, 'No', 350, 78, 'No'],
                     [8, 'Yes', 850, 81, 'Yes'],
                     [6, 'No', 750, 59, 'Yes'],
                     [12, 'Yes', 1050, 54, 'Yes'],
                     [10, 'No', 230, 74, 'No'],
                     [3, 'Yes', 630, 74, 'Yes'],
                     [10, 'Yes', 830, 74, 'No'],
                     [12, 'No', 730, 52, 'Yes']])

# Encoding categorical features
features[:, 1] = encode_feature(features[:, 1])
features[:, 4] = encode_feature(features[:, 4])

targets = np.array(['Countryside','Beach','Beach','Countryside',
                    'Beach', 'Countryside', 'Beach','Countryside',
                    'Beach', 'Beach', 'Countryside','Countryside',
                    'Beach', 'Beach'])

targets = encode_feature(targets)

Pre-processing: Done ✅

Now it’s time to build and visualize the Decision Tree.

import pandas as pd
from sklearn import tree
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split

def print_feature_importance(names_array, importances_array):

    """ Prints out a feature importance array as a dataframe. """

    importances = pd.DataFrame(data=names_array)
    importances[1] = importances_array

    importances = importances.T
    importances.drop(0, axis=0, inplace=True)
    importances.columns = feature_names
    
    print(str(importances.reset_index(drop=True)))

def build_tree(features, targets, feature_names, class_names):

    """ Builds a decision tree.
        Prints out the decision tree 1) as a plot, 2) as text.
        Also outputs: 1) feature importance, 2) training set and test set mean accuracy of tree
    
        :param features: model features
        :param targets: model targets
        :param feature_names: names of the dataset features
    """
  
    train_features, test_features, train_targets, test_targets = train_test_split(features, targets, test_size=0.2, random_state=123)

    decision_tree = tree.DecisionTreeClassifier(random_state=456)
    decision_tree = decision_tree.fit(train_features, train_targets)

    # Visualizing the decision tree
    
    # 1. Saving the image of the decision as a png   

    plt.subplots(figsize=(17, 12))
    tree.plot_tree(decision_tree, feature_names=feature_names, filled=True, rounded=True, class_names=class_names)
    plt.savefig("decision_tree.png")

    # 2. Output the tree as text in the console
    tree_as_text = tree.export_text(decision_tree, feature_names=feature_names)
    print(tree_as_text)

    # Feature Importance
    # Turns the feature importance array into a dataframe, so it has a table-like output format
    print_feature_importance(feature_names, decision_tree.feature_importances_)

    # Training and test mean accuracy
    train_error = np.round(decision_tree.score(train_features, train_targets), 2)
    test_error = np.round(decision_tree.score(test_features, test_targets), 2)
    
    print("Training Set Mean Accuracy = " + str(train_error))
    print("Test Set Mean Accuracy = " + str(test_error))

build_tree(features, targets, feature_names, class_names)

This code does lots of things at once, so let’s unpack it.

It starts by splitting the dataset into training and test with the train_test_split function, so you can test model accuracy with data points that were not used to train the model.

Building the model and visualizing the tree

By default ScikitLearn uses Gini Impurity as a loss function. But you can also use Entropy as the loss function and tune other parameters in the DecisionTreeClassifier.

With the model trained, you can visualize the resulting decision tree with the plot_tree method, and save as decision_tree.png.

You can also visualize the tree in the output console, you can use the export_text method.

Feature Importances

But there’s something wrong with that decision tree!

You noticed the feature explore_new_places doesn’t show up anywhere. Even though you’re sure it’s an important part of your decision process.

To get to the bottom of this and understand why explore_new_places is not used in the model you lookup the feature_importances_ property in the decision tree model. This will tell you how much each features contributes to the accuracy of the model.

The feature_importances_ property is simply an array of values, with each value corresponding to a feature of the model, with the same order as the input dataset.

So, for better readability, you can decided to create the function print_feature_importance and transform the value array from feature_importances_ property into a dataframe and use the feature names as headers.

explore_new_places has a feature importance of 0, which means it’s not used at all in the prediction.

At first glance you might be thinking, I can just get rid of this feature.

But feature importance doesn’t necessarily mean the feature is never going to be used in the model. It only means it was not used in this tree, which as a specific training-test split.

So you can’t eliminate this feature right away.

To confirm that explore_new_places is not relevant to the model, you can build several trees with different train-test splits f the dataset and check if explore_new_places still has zero importance.

Model Performance

Finally, to evaluate the algorithm’s performance you calculate the mean accuracy of the predictions on both the training and test sets, using the score method.

As you can see, this model is overfit and memorized the training set. And with a 67% of mean accuracy for the test set, it doesn’t generalize very well to observations it has never seen before.

One Decision Tree is not enough

Despite their advantages, Decision Trees don’t provide the same level of accuracy as other classification and regression algorithms.

Decision trees are prone to overfitting. If you build a very tall tree, splitting the feature set until you get pure leaf nodes, you’re likely overfitting the training set. The resulting tree is so complex that it’s also hard to read and interpret.

On the other hand, if your decision tree is very small it underfits the data, resulting in high bias.

Decision trees are robust in terms of the data types they can handle, but the algorithm itself is not very robust. A slight change in the data can drastically change the tree and, consequently the final results[1].

The power hidden in the forest

A single Decision Tree by itself has subpar accuracy, when compared to other machine learning algorithms. One tree alone typically doesn’t generate the best predictions, but the tree structure makes it easy to control the bias-variance trade-off.

A single Decision Tree is not powerful enough, but an entire forest is!

In algorithms that combine multiple trees and control for bias or variance, like Random Forests, the model has a much better performance when compared to a single decision tree.

Stay tuned for the next articles in this series, because they’re about Boosting and Bagging. These techniques are applied to tree-based algorithms and tackle, respectively, the issues with bias and variance.

Conclusion

Decision trees are a rule-based approach to classification and regression problems. They use the values in each feature to split the dataset to a point where all data points that have the same class are grouped together.

However, there’s a clear trade-off between interpretability and performance.

You can easily visualize and interpret a small tree, but it has high variance. A small change in the training set, may result in a completely different tree, and completely different predictions.

On the other hand, a tall tree with multiple splits generates better classifications. But it’s likely memorizing the training dataset. So it not good at classifying data it has never seen before.

Hope you enjoyed learning about Decision Trees!

Stay tuned for the next articles in this series! The next articles explore Tree-based Ensemble algorithms that use Boosting and Bagging techniques to control bias and variance.

Thanks for reading!

References

1. Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani. (2013). An introduction to statistical learning : with applications in R. New York :Springer
2. P. Tan, M. Steinbach, and V. Kumar. (2005) Introduction to Data Mining. Addison Wesley

Decision Tree Classifier explained in real-life: picking a vacation destination was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.