July 20, 2017 by Thomas Tracey, originally posted on Github

This post explores my work on the second project of the Udacity Self-Driving Car Nanodegree program. My goal is to help other students and professionals who are in the early phases of building their intuition in machine learning (ML) and artificial intelligence (AI).

With that said, please keep in mind that I am a product manager by trade (not an engineer or data scientist). So, what follows is meant to be a semi-technical yet approachable explanation of the ML concepts and algorithms in this project. If anything covered below is inaccurate or if you have constructive feedback, I’d love to hear from you.

My Github repo for this project can be found here. The original Udacity source repo for this project is located here.

Project Goal

The goal of this project is to build a neural network that recognizes traffic signs in Germany.

Udacity’s benchmark for the project is to achieve at least 93% accuracy (on the validation set). However, my personal goal was to surpass the human level performance benchmark of 98.8% accuracy identified in this paper by Mrinal Haloi from the Indian Institute of Technology.

Approach

The basic steps of the project are as follows:

1. Load the data set provided by Udacity
2. Explore, summarize and visualize the data set
3. Design, train and test a model architecture
4. Use the model to make predictions on new images
5. Analyze the softmax probabilities of the new images
6. Summarize the results with a written report

Project Notebook

My code and a detailed view of the outputs for each step are outlined here in this Jupyter notebook.

Data Summary & Exploration

Throughout this section, I use the Numpy, Pandas, and Matplotlib libraries to explore and visualize the traffic signs data set.

Data Size & Shape

• Size of training set: 34,799 (67%)
• Size of the validation set: 4,410 (9%)
• Size of test set: 12,630 (24%)
• Shape of a traffic sign image: (32, 32, 3)
• Number of unique classes/labels: 43

Data Visualization

Before designing the neural network, I felt it was important to visualize the data in various ways to gain some intuition for what the model will “see.” This not only informs the model structure and parameters, but it also helps me determine what types of preprocessing operations should be applied to the data (if any).

There are a few fundamental ways I used visualizations to inform my decisions:

1. Inspect a sample of images. Do the images correspond with the expected number of color channels? — i.e., if channels=3 then the images should appear in color/RGB not grayscale. How clear are the images? Is there anything that makes the signs hard to recognize (e.g. bad weather, darkness, glare, occlusions)?
2. Review a sample of the labels. Do the labels make sense? Do they accurately correspond with images in the data set?
3. Create a histogram showing the distribution of classes/labels. How balanced is the dataset? Are there certain classes that dominate? Are there others that are under-represented?

Image & Label Sample

Below is a sample of the original images before they undergo any preprocessing. Overall, the image quality is good and the labels make intuitive sense. However, immediately you notice a few things we’ll want to adjust during preprocessing:

• Many of the signs are hard to recognize because the images are dark and have low contrast.
• There is little variation in the sign shape and viewing angle. Most of the pictures are taken with a straight on view of the sign, which is good for the core data set. However, in real life, signs are viewed from different angles.
• The signs are void of any deformations or occlusions. Again, this is good because we need a clean set of training samples, but in real life, signs are sometimes damaged, vandalized, or only partially visible. Essentially, we want the model to recognize signs even when the shape is distorted, much like humans can. So, augmenting the training set with a variety of distortions is important.

Class/Label Distribution

As you can see below, the distribution is not uniform. The largest classes have 10x the number of traffic sign images than the smallest classes. This is expected given that in real-life there are certain signs which appear more frequently than others. However, when training the model, I wanted a more uniform distribution so that each class has the same number of training examples and the model, therefore, has an equal number of opportunities to learn each sign.

Data Preprocessing

Given the issues identified above, I decided to explore the following preprocessing operations (in addition to data normalization):

Contrast enhancement:

I used this Scikit histogram equalization function, which not only normalizes the images but also enhances local contrast details in regions that are darker or lighter than most of the image (link to source code). You can see from the image sample below this also inherently increases the brightness of the image.

Augmentation

• Increase the total number of images so that the model has more training examples to learn from.
• Create an equal distribution of images — i.e., the same number of images per class, so that the model has a sufficient number of training examples in each class. I initially tested models on sets of 4k images per class and found that models performed better with more images. I ultimately generated a set of 6k images per class for the final model.
• Apply affine transformations. Used to generate images with various sets of perturbations. Specifically: rotation, shift, shearing, and zoom. But, I decided not to apply horizontal/vertical flipping as this didn’t seem applicable to real-life use cases.
• Apply ZCA whitening to accentuate edges.
• Apply two types of color transformations:
• (1) Color channel shifts. This was done to create slight color derivations to help prevent the model from overfitting on specific color shades. This intuitively seemed like a better strategy than grayscaling.
• (2) Grayscaling. This was performed separately _after_ all of the above transformations. Due to the high darkness and low contrast issues, applying grayscale before the other transformations didn’t make sense. It would only make the contrast issue worse. So, I decided to test the grayscale versions as a separate data set to see if it boosted performance (spoiler alert: it didn’t).

Below are snippets of code that takes the already normalized images (with contrast-enhanced) and applies the other transformations listed above. It outputs a new training set with 6k images per class, including the set of normalized training images (link to source code).

Augmented Image Samples

Below is a sample of a traffic sign images after the complete set of normalization, contrast enhancement, and augmentation steps listed above.

Grayscaling

Here is a sample of images with **grayscaling** then applied. At first glance, it doesn’t appear that grayscaling improves the images in any meaningful way. So, my hypothesis was that the grayscaled versions would perform the same or worse than the augmented images (this turned out to be correct).

Model Architecture

I tested a variety of models (> 25 different combinations). Ultimately, I settled on a relatively small and simple architecture that was easy to train and still delivered great performance. My final model consisted of the following layers:

Model

Below is a snapshot of the model (here is a link to the source code). You can see that I use: (1) a ReLU activation on every layer, (2) maxpooling on alternating convolutional layers with a 5x5 filter, and (3) dropouts on the two fully connected layers with a 0.5 keep probability.

Training Loop

Below are the training loop, loss, and regularization functions (link to source code). You can see that I use AdamOptimizer to take advantage of its built-in hyperparameter tuning, which varies the learning rate based on moving averages (momentum) to help the model converge faster, without having to manually tune it myself. You’ll notice that I also use L2 regularization to help prevent overfitting.

Hyperparameters

Here are the hyperparameters I used (link to source code). My goal was to get the model to converge in less than 50 epochs. Essentially, given time constraints, I didn’t want to spend more than two hours training the model. Everything else is pretty standard. Although, I did decrease my L2 decay rate (i.e. lower penalty on weights) during the tuning process, which yielded a small lift in performance.

Output

Here is the output when I construct the graph (link to source code). I use print statements to verify that the model structure matches my expectations. I find this very useful as it’s easy to get confused when you’re tweaking and testing lots of different models. Especially after 3am. 😵

Final Model Results:

• training accuracy: 100%
• validation accuracy: 99.4%
• test accuracy: 98.2%

Model Iteration & Tuning

Here I’ll try to summarize the approach I took to find a solution that exceeded the benchmark validation set accuracy of 0.93. Although some of the details got lost in the fog of war. I battled with these models for too many days. If you’re curious, you can view a fairly exhaustive list of the models I tested here.

Phase 1

The first steps were to get the most basic version of the LeNet CNN running and begin tuning it. I got 83% validation accuracy without any modifications to the model or preprocessing of the training data. Adding regularization and tuning the hyperparameters made the performance worse. So, I started to explore different types of architectures.

Phase 2

This is where I started making mistakes that cost me a lot of time (although I learned a lot in the process). In hindsight, I should have done two simple things at this point: (1) start applying some basic preprocessing to the data and testing the performance impact, and (2) keep iterating on the LeNet architecture by incrementally adding and deepening the layers.

Instead, I started exploring different architectures such as DenseNets. Just look at this diagram from the DenseNets paper (below).

How hard could it be, right?

Wrong.

DenseNets didn’t seem overly complex at the time, and I probably could have gotten them working if I’d just focused on this. However, in parallel, I tried to get Tensorboard working, which was in beta at the time. Trying to tackle both of these at once was a disaster. In short, creating DenseNets requires a lot of nested functions to create all of the various blocks of convolutional layers. Getting the Tensorboard namespaces to work, getting all of your variables to initialize properly, and getting all of the data to flow in and out of these blocks was a huge challenge. After a bunch of research and trial and error (and coffee), I ultimately abandoned this path. ¯\_(ツ)_/¯

I then tried to implement the (much simpler) inception framework discussed by Vincent during the lectures. After some trial and error, I got an inception network running. But, I couldn’t get it to perform better than 80% validation accuracy, so I abandoned this path as well. I believe this approach could have worked, but by this point, I wanted to get back to the basics. So, I decided to focus on data preprocessing and iterating on the original LeNet architecture (which I should have done from the beginning! Arg.)

Phase 3

After a day of sleep, yoga, and a few dozen ohms to clear my head 🙏…I then got back to work.

I started by applying basic transformations to the data and testing simple adjustments to the LeNet architecture. Model performance started to improve, but I still had a bias problem. In the beginning, my models were consistently overfitting the training data and therefore my training accuracy was high but my validation accuracy was still low.

This is a summary of the tactics I deployed to improve performance.

Here are more details regarding the tactics above (in order of greatest impact on the model):

• Contrast Enhancement. Pound for pound, this tactic had the greatest impact on performance. It was easy to implement and my validation accuracy immediately jumped more than 7%. I only wish I’d done it sooner. As discussed in my initial exploration of the data, I predicted that the low contrast of many of the original images would make it difficult for the model to recognize the distinct characteristics of each sign. This is obvious even to the human eye! But for some reason, I didn’t implement this tactic until halfway through the project. Key lesson: design and test your pipeline around simple observations and intuitions BEFORE you pursue more complicated strategies.
• Augmentation v1 vs v2. The first iteration of my augmentation function boosted performance by 2% (which was great!). However, my range settings for the affine and color transformations were a little too aggressive. This made the training images overly distorted (this was obvious with the naked eye). Because of these distortions, the model kept overfitting (i.e., it achieved high training accuracy but wasn’t able to generalize to the validation set).
• In v2 of my augmentation function, I dialed down the range settings and got a 1% performance boost. Then I added ZCA whitening to improve edge detection and got another 1% lift. In my very last optimization, I then increased the number of images being produced by this function so that there were 6k images per class (instead of 4k). This tactic combined with longer training time yielded the final (and elusive!) 0.4% lift to bring the final validation accuracy to 99.4%. Then I slept.
• More layers and deeper layers. Surprisingly, and after many iterations, I learned that it doesn’t take a high number of layers or incredibly deep layers to achieve human-level performance. That said, some modest increases in the size of the model were critical to breaking the 95% accuracy plateau. You can see from the model diagram that I ended up with seven convolutional layers (five more than LeNet) and that my convolutional and fully connected layers are deeper than LeNet as well. Of course, to mitigate this extra learning power, I had to employ regularization tactics.
• Regularization. Both dropout and L2 regularization proved critical. Initially, I made the mistake of incorporating these too early or setting them too high, which caused the model to underfit. I then removed them altogether until I had a model that was starting to fit (even overfitting) and yielding high training accuracies. At that point, I added regularization back into the model and started to increase it whenever my model was overfitting (i.e., higher dropout and L2 decay values). After a few overcorrections, I ultimately landed on a dropout of 0.5 and decay of 0.0003.
• Bias initialization. Initially, I was initializing my biases at 0.01 (using tf.constant). Once I started initializing the biases at zero, my accuracy jumped more than 2%. This was a big surprise. Even after doing more research on the issue, I’m still not exactly sure why this small bias initialization negatively affected the model. My best guess is even this small amount of bias was not self-correcting enough during backpropagation, and given that the data was normalized, that extra bias was causing additional overfitting in the model (link to source code).
• Grayscale. Just out of curiosity, I ran a test on a grayscaled version of the augmented image set. The grayscale set still performed well with a validation accuracy of 95.8%. But, this test turned out to be more trouble than it’s worth. The big problem was that there are a bunch of tools out there to help you convert RGB images to grayscale, and none of them (as far as I can tell) provide the correct shape. To feed grayscale images into the network, they need to be rank 4 (batch_size, 32, 32, 1). So, you have to convert each RGB image from (32, 32, 3) to (32, 32, 1). Seems simple, right? But all of the scripts I tested strip out the third dimension, yielding an image with shape (32, 32). And, there wasn’t much help for this issue on StackOverflow, etc. After lots of troubleshooting, I finally discovered the underlying problem and used a simple matrix multiplication to apply the grayscale conversion while maintaining the right shape (link to source code).

Testing the Model with New Images

Test Set

I happened to be in Prague at the time, so I took advantage by testing my model on images of local traffic signs (The Czech Republic uses the same traffic signs as Germany and most of the EU, I think). For the test set, I gathered 30 new images: 11 of the images were pulled from the internet, and 19 were shot around the streets of Prague. Overall, I made the new image set quite challenging in order to learn about the strengths and weaknesses of the model.

Here is the complete set of new images and their corresponding originals.

Challenges

Within the new image set, the ones below pose distinct challenges for the model. My hypothesis was that the model would get less than 50% of these correct while scoring above 80% on the other “normal” new images. In particular, some of the signs I found on the streets of Prague seem particularly challenging. How would the model react when it sees two standard signs combined into a single custom sign? Keep reading to find out!

1. Large Vehicles Prohibited. Like many signs that I encountered on the streets of Prague, a single traffic sign includes a combination of two or more signs/symbols.

2. No Trucks or Motorcycles. Again, what are normally two signs are incorporated into one

3. Yield. Yet again, the image includes two signs (this one is from the internet)

4. No Entry. The bracket holding up this sign is damaged, so the sign is heavily tilted.

5. Turn Right. This sign is partially occluded by a very pink van.

6. 50 km/h. The viewing angle makes the image heavily sheared.

7. No Entry. This sign has graffiti on it. Those punks!

8. Ahead Only. This sign is only partially visible.

New Image Test Results

The overall accuracy dropped considerably to 77%, although the model performed pretty well on the new images of “normal” difficulty with 91% accuracy. However, this is still well below the 98.2% accuracy achieved on the original test set. This indicates just how quickly accuracy can drop off when a model encounters new patterns it hasn’t yet seen in the training set.

Top 5 Predictions

Below you can see the top 5 predictions and the corresponding softmax probabilities for a subset of the test images.

Precision & Recall

Next, we’ll measure the model accuracy using precision and recall.

Original Test Images

Listed below are the precision, recall, and F1 scores for the original set of test images.

Here are the worst performing classes among the original test images.

New Images

Here are the worst performing classes for the new image set. Not surprisingly, the worst performing class from the original test set (label 27: Pedestrians) is also one of the poorest performers in the new image set.

There are two things I want to call out here:

1. High errors for similar looking signs. If we look at the images from six of the worst performing classes between the two sets, we can see that they all look quite similar. This would help explain the high occurrence of false positives (low precision) and false negatives (low recall). This may also be a case where the transformations done during preprocessing overly distort the images, especially when they’re applied to low-resolution images. The additional loss in resolution can make it hard to distinguish some of the symbols from each other.

Given this, one future improvement to our pipeline would be to review how each transformation affects the various classes, and if needed, create a custom set of transformations to be applied on a class-by-class basis.

2. Too much augmentation is bad. I think the most interesting insight from the precision/recall data is the misclassification of the label 15: No Vehicles. If we look at image samples from this class (below), it is arguably the simplest sign and should be one of the easiest to recognize. But upon further inspection, we can see that the contrast boosting function that boosted performance in other classes actually hurts us in this case. This is because any minor spots or shadows on the central white portion of the sign get exacerbated by the contrast enhancement function. These dark spots can then resemble symbols to the model. This is another example of how class-specific preprocessing tactics could improve the pipeline.

Contact

I hope you found this useful. Again, if you have any feedback, I’d love to hear it. Feel free to post in the comments.

If you’d like to discuss other collaboration or career opportunities you can find me here on LinkedIn or view my portfolio here.

Aug 29, 2018 by Thomas Tracey, originally posted on Github

Versión en español — A Spanish translation of this post is available here, courtesy of the Ibidem Group. Muchísimas gracias Chema Bescós!

This post explores my work on the final project of the Udacity Artificial Intelligence Nanodegree program. My goal is to help other students and professionals who are in the early phases of building their intuition in machine learning (ML) and artificial intelligence (AI).

With that said, please keep in mind that I am a product manager by trade (not an engineer or data scientist). So, what follows is meant to be a semi-technical yet approachable explanation of the ML concepts and algorithms in this project. If anything covered below is inaccurate or if you have constructive feedback, I’d love to hear from you.

My Github repo for this project can be found here. The original Udacity source repo for this project is located here.

Project Goal

In this project, I build a deep neural network that functions as part of a machine translation pipeline. The pipeline accepts English text as input and returns the French translation. The goal is to achieve the highest translation accuracy possible.

Why Machine Translation Matters

The ability to communicate with one another is a fundamental part of being human. There are nearly 7,000 different languages worldwide. As our world becomes increasingly connected, language translation provides a critical cultural and economic bridge between people from different countries and ethnic groups. Some of the more obvious use-cases include:

• business: international trade, investment, contracts, finance
• commerce: travel, purchase of foreign goods and services, customer support
• media: accessing information via search, sharing information via social networks, localization of content and advertising
• education: sharing of ideas, collaboration, translation of research papers
• government: foreign relations, negotiation

To meet these needs, technology companies are investing heavily in machine translation. This investment and recent advancements in deep learning have yielded major improvements in translation quality. According to Google, switching to deep learning produced a 60% increase in translation accuracy compared to the phrase-based approach previously used in Google Translate. Today, Google and Microsoft can translate over 100 different languages and are approaching human-level accuracy for many of them.

However, while machine translation has made lots of progress, it’s still not perfect. 😬

Approach for This Project

To translate a corpus of English text to French, we need to build a recurrent neural network (RNN). Before diving into the implementation, let’s first build some intuition of RNNs and why they’re useful for NLP tasks.

RNN Overview

RNNs are designed to take sequences of text as inputs or return sequences of text as outputs, or both. They’re called recurrent because the network’s hidden layers have a loop in which the output and cell state from each time step become inputs at the next time step. This recurrence serves as a form of memory. It allows contextual information to flow through the network so that relevant outputs from previous time steps can be applied to network operations at the current time step.

This is analogous to how we read. As you read this post, you’re storing important pieces of information from previous words and sentences and using it as context to understand each new word and sentence.

Other types of neural networks can’t do this (yet). Imagine you’re using a convolutional neural network (CNN) to perform object detection in a movie. Currently, there’s no way for information from objects detected in previous scenes to inform the model’s detection of objects in the current scene. For example, if a courtroom and judge were detected in a previous scene, that information could help correctly classify the judge’s gavel in the current scene, instead of misclassifying it as a hammer or mallet. But CNNs don’t allow this type of time-series context to flow through the network like RNNs do.

RNN Setup

Depending on the use-case, you’ll want to set up your RNN to handle inputs and outputs differently. For this project, we’ll use a many-to-many process where the input is a sequence of English words and the output is a sequence of French words (fourth from the left in the diagram below).

Each rectangle is a vector and arrows represent functions (e.g. matrix multiply). Input vectors are in red, output vectors are in blue and green vectors hold the RNN’s state (more on this soon).

From left to right: (1) Vanilla mode of processing without RNN, from fixed-sized input to fixed-sized output (e.g. image classification). (2) Sequence output (e.g. image captioning takes an image and outputs a sentence of words). (3) Sequence input (e.g. sentiment analysis where a given sentence is classified as expressing positive or negative sentiment). (4) Sequence input and sequence output (e.g. Machine Translation: an RNN reads a sentence in English and then outputs a sentence in French). (5) Synced sequence input and output (e.g. video classification where we wish to label each frame of the video). Notice that in every case are no pre-specified constraints on the lengths sequences because the recurrent transformation (green) is fixed and can be applied as many times as we like.

— Andrej Karpathy, The Unreasonable Effectiveness of Recurrent Neural Networks

Building the Pipeline

Below is a summary of the various preprocessing and modeling steps. The high-level steps include:

1. Preprocessing: load and examine data, cleaning, tokenization, padding
2. Modeling: build, train, and test the model
3. Prediction: generate specific translations of English to French, and compare the output translations to the ground truth translations
4. Iteration: iterate on the model, experimenting with different architectures

For a more detailed walkthrough including the source code, check out the Jupyter notebook in the project repo.

Frameworks

We use Keras for the frontend and TensorFlow for the backend in this project. I prefer using Keras on top of TensorFlow because the syntax is simpler, which makes building the model layers more intuitive. However, there is a trade-off with Keras as you lose the ability to do fine-grained customizations. But this won’t affect the models we’re building in this project.

Preprocessing

Load & Examine Data

Here is a sample of the data. The inputs are sentences in English; the outputs are the corresponding translations in French.

When we run a word count, we can see that the vocabulary for the dataset is quite small. This was by design for this project. This allows us to train the models in a reasonable time.

Cleaning

No additional cleaning needs to be done at this point. The data has already been converted to lowercase and split so that there are spaces between all words and punctuation.

Note: For other NLP projects you may need to perform additional steps such as: remove HTML tags, remove stop words, remove punctuation or convert to tag representations, label the parts of speech, or perform entity extraction.

Tokenization

Next, we need to tokenize the data — i.e., convert the text to numerical values. This allows the neural network to perform operations on the input data. For this project, each word and punctuation mark will be given a unique ID. (For other NLP projects, it might make sense to assign each character a unique ID.)

When we run the tokenizer, it creates a word index, which is then used to convert each sentence to a vector.

Padding

When we feed our sequences of word IDs into the model, each sequence needs to be the same length. To achieve this, padding is added to any sequence that is shorter than the max length (i.e. shorter than the longest sentence).

One-Hot Encoding (not used)

In this project, our input sequences will be a vector containing a series of integers. Each integer represents an English word (as seen above). However, in other projects, sometimes an additional step is performed to convert each integer into a one-hot encoded vector. We don’t use one-hot encoding (OHE) in this project, but you’ll see references to it in certain diagrams (like the one below). I just didn’t want you to get confused.

One of the advantages of OHE is efficiency since it can run at a faster clock rate than other encodings. The other advantage is that OHE better represents categorical data where there is no ordinal relationship between different values. For example, let’s say we’re classifying animals as either a mammal, reptile, fish, or bird. If we encode them as 1, 2, 3, 4 respectively, our model may assume there is a natural ordering between them, which there isn’t. It’s not useful to structure our data such that mammal comes before reptile and so forth. This can mislead our model and cause poor results. However, if we then apply one-hot encoding to these integers, changing them to binary representations — 1000, 0100, 0010, 0001 respectively — then no ordinal relationship can be inferred by the model.

But, one of the drawbacks of OHE is that the vectors can get very long and sparse. The length of the vector is determined by the vocabulary, i.e. the number of unique words in your text corpus. As we saw in the data examination step above, our vocabulary for this project is very small — only 227 English words and 355 French words. By comparison, the Oxford English Dictionary has 172,000 words. But, if we include various proper nouns, words tenses, and slang there could be millions of words in each language. For example, Google’s word2vec is trained on a vocabulary of 3 million unique words. If we used OHE on this vocabulary, the vector for each word would include one positive value (1) surrounded by 2,999,999 zeros!

And, since we’re using embeddings (in the next step) to further encode the word representations, we don’t need to bother with OHE. Any efficiency gains aren’t worth it on a data set this small.

Modeling

First, let’s breakdown the architecture of an RNN at a high level. Referring to the diagram above, there are a few parts of the model we need to be aware of:

1. Inputs. Input sequences are fed into the model with one word for every time step. Each word is encoded as a unique integer or one-hot encoded vector that maps to the English dataset vocabulary.
2. Embedding Layers. Embeddings are used to convert each word to a vector. The size of the vector depends on the complexity of the vocabulary.
3. Recurrent Layers (Encoder). This is where the context from word vectors in previous time steps is applied to the current word vector.
4. Dense Layers (Decoder). These are typical fully connected layers used to decode the encoded input into the correct translation sequence.
5. Outputs. The outputs are returned as a sequence of integers or one-hot encoded vectors which can then be mapped to the French dataset vocabulary.

Embeddings

Embeddings allow us to capture more precise syntactic and semantic word relationships. This is achieved by projecting each word into n-dimensional space. Words with similar meanings occupy similar regions of this space; the closer two words are, the more similar they are. And often the vectors between words represent useful relationships, such as gender, verb tense, or even geopolitical relationships.

Training embeddings on a large dataset from scratch requires a huge amount of data and computation. So, instead of doing it ourselves, we normally use a pre-trained embeddings package such as GloVe or word2vec. When used this way, embeddings are a form of transfer learning. However, since our dataset for this project has a small vocabulary and low syntactic variation, we’ll use Keras to train the embeddings ourselves.

Encoder & Decoder

Our sequence-to-sequence model links two recurrent networks: an encoder and decoder. The encoder summarizes the input into a context variable, also called the state. This context is then decoded and the output sequence is generated.

Since both the encoder and decoder are recurrent, they have loops which process each part of the sequence at different time steps. To picture this, it’s best to unroll the network so we can see what’s happening at each time step.

In the example below, it takes four timesteps to encode the entire input sequence. At each time step, the encoder “reads” the input word and performs a transformation on its hidden state. Then it passes that hidden state to the next time step. Keep in mind that the hidden state represents the relevant context flowing through the network. The bigger the hidden state, the greater the learning capacity of the model, but also the greater the computation requirements. We’ll talk more about the transformations within the hidden state when we cover gated recurrent units (GRU).

For now, notice that for each time step after the first word in the sequence there are two inputs: the hidden state and a word from the sequence. For the encoder, it’s the next word in the input sequence. For the decoder, it’s the previous word from the output sequence.

Also, remember that when we refer to a “word,” we really mean the vector representation of the word which comes from the embedding layer.

Here’s another way to visualize the encoder and decoder, except with a Mandarin input sequence.

Bidirectional Layer

Now that we understand how context flows through the network via the hidden state, let’s take it a step further by allowing that context to flow in both directions. This is what a bidirectional layer does.

In the example above, the encoder only has historical context. But, providing future context can result in better model performance. This may seem counterintuitive to the way humans process language since we only read in one direction. However, humans often require future context to interpret what is being said. In other words, sometimes we don’t understand a sentence until an important word or phrase is provided at the end. Happens this does whenever Yoda speaks. 😑 🙏

To implement this, we train two RNN layers simultaneously. The first layer is fed the input sequence as-is and the second is fed a reversed copy.

Hidden Layer with Gated Recurrent Unit (GRU)

Now let’s make our RNN a little bit smarter. Instead of allowing all of the information from the hidden state to flow through the network, what if we could be more selective? Perhaps some of the information is more relevant, while other information should be discarded. This is essentially what a gated recurrent unit (GRU) does.

There are two gates in a GRU: an update gate and reset gate. This article by Simeon Kostadinov, explains these in detail. To summarize, the update gate (z) helps the model determine how much information from previous time steps needs to be passed along to the future. Meanwhile, the reset gate (r) decides how much of the past information to forget.

Final Model

Now that we’ve discussed the various parts of our model, let’s take a look at the code. Again, all of the source code is available here in the notebook (.html version).

Results

The results from the final model can be found in cell 20 of the notebook.

Validation accuracy: 97.5%

Training time: 23 epochs

Future Improvements

1. Do proper data split (training, validation, test). Currently, there is no test set, only training and validation. Obviously, this doesn’t follow best practices.
2. LSTM + attention. This has been the de facto architecture for RNNs over the past few years, although there are some limitations. I didn’t use LSTM because I’d already implemented it in TensorFlow in another project, and I wanted to experiment with GRU + Keras for this project.
3. Train on a larger and more diverse text corpus. The text corpus and vocabulary for this project are quite small with little variation in syntax. As a result, the model is very brittle. To create a model that generalizes better, you’ll need to train on a larger dataset with more variability in grammar and sentence structure.
4. Residual layers. You could add residual layers to a deep LSTM RNN, as described in this paper. Or, use residual layers as an alternative to LSTM and GRU, as described here.
5. Embeddings. If you’re training on a larger dataset, you should definitely use a pre-trained set of embeddings such as word2vec or GloVe. Even better, use ELMo or BERT.

• Embedding Language Model (ELMo). One of the biggest advances in universal embeddings in 2018 was ELMo, developed by the Allen Institute for AI. One of the major advantages of ELMo is that it addresses the problem of polysemy, in which a single word has multiple meanings. ELMo is context-based (not word-based), so different meanings for a word occupy different vectors within the embedding space. With GloVe and word2vec, each word has only one representation in the embedding space. For example, the word “queen” could refer to the matriarch of a royal family, a bee, a chess piece, or the 1970s rock band. With traditional embeddings, all of these meanings are tied to a single vector for the word queen. With ELMO, these are four distinct vectors, each with a unique set of context words occupying the same region of the embedding space. For example, we’d expect to see words like queen, rook, and pawn in a similar vector space related to the game of chess. And we’d expect to see queen, hive, and honey in a different vector space related to bees. This provides a significant boost in semantic encoding.
• Bidirectional Encoder Representations from Transformers (BERT). So far in 2019, the biggest advancement in bidirectional embeddings has been BERT, which was open-sourced by Google. How is BERT different?

Context-free models such as word2vec or GloVe generate a single word embedding representation for each word in the vocabulary. For example, the word “bank” would have the same context-free representation in “bank account” and “bank of the river.” Contextual models instead generate a representation of each word that is based on the other words in the sentence. For example, in the sentence “I accessed the bank account,” a unidirectional contextual model would represent “bank” based on “I accessed the” but not “account.” However, BERT represents “bank” using both its previous and next context — “I accessed the … account” — starting from the very bottom of a deep neural network, making it deeply bidirectional.
 — Jacob Devlin and Ming-Wei Chang, Google AI Blog

Contact

I hope you found this useful. Again, if you have any feedback, I’d love to hear it. Feel free to post in the comments.

If you’d like to discuss other collaboration or career opportunities you can find me here on LinkedIn or view my portfolio here.

Language Translation with RNNs was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

Deep Reinforcement Learning for Multi-Agent Collaboration & Competition

Dec 26, 2018 by Thomas Tracey, originally posted on Github

This post explores my work on the final project for Udacity’s Deep Reinforcement Learning Nanodegree. My goal is to help other machine learning (ML) students and professionals who are in the early phases of building their intuition in reinforcement learning (RL).

With that said, please keep in mind that I am a product manager by trade (not an engineer or data scientist). So, what follows is meant to be a semi-technical yet approachable explanation of the RL concepts and algorithms in this project. If anything covered below is inaccurate, or if you have constructive feedback, I’d love to hear it.

My Github repo for this project can be found here. The original Udacity source repo for this project is located here.

Big Picture: Why RL Matters

For artificial intelligence (AI) to reach its full potential, AI systems need to interact effectively with humans and with other agents. There are already environments where this type of agent-human and agent-agent interaction is happening on a massive scale, such as the stock market. And more environments are just around the corner, such as our roadways once fully autonomous vehicles are introduced.

One step along this path is to train AI agents to interact with other agents in both cooperative and competitive settings. Reinforcement learning (RL) is a subfield of AI that’s shown promise. RL is distinct from other types of machine learning approaches in that RL agents are goal-oriented. That is, RL algorithms use a reward function (aka an objective function) to “reinforce” certain behaviors. For example, a Pac-Man agent may earn a reward of +1 points for each pellet it eats and -100 points if it collides with a ghost. By trying to maximize its cumulative reward, the Pac-Man agent ultimately learns — through repeated trial-and-error — how to distinguish good actions from bad actions.

OpenAI has made a large set of virtual environments publicly available for training and benchmarking RL agents. This has spurred lots of research and innovation in RL. However, much of the initial progress was in single-agent domains, where building models that predict the behavior of other actors isn’t necessary. As a result, traditional RL approaches (such as Q-Learning) are not well-suited for the complexity that accompanies environments where multiple agents are continuously interacting and evolving their policies.

Unfortunately, traditional reinforcement learning approaches such as Q-Learning or policy gradient are poorly suited to multi-agent environments. One issue is that each agent’s policy is changing as training progresses, and the environment becomes non-stationary from the perspective of any individual agent in a way that is not explainable by changes in the agent’s own policy. This presents learning stability challenges and prevents the straightforward use of past experience replay, which is crucial for stabilizing deep Q-learning. Policy gradient methods, on the other hand, usually exhibit very high variance when coordination of multiple agents is required. Alternatively, one can use model-based policy optimization which can learn optimal policies via back-propagation, but this requires a differentiable model of the world dynamics and assumptions about the interactions between agents. Applying these methods to competitive environments is also challenging from an optimization perspective, as evidenced by the notorious instability of adversarial training methods.

— Lowe and Wu et al, Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments

Wow, that’s a mouthful. Essentially, what’s needed (and what’s explored in this project) is a general framework that allows multiple agents to learn from their own observations in both cooperative and competitive environments. This is without any communication between the agents or modeling of other agents’ behaviors. However, each agent in this project does learn by observing its own actions and the actions of the other agent. Each observation includes: the prior game state, the agent’s action, the reward, and the subsequent game state (s, a, r, sʹ).

New approaches for cooperative and competitive environments are advancing quickly. I won’t explore them further in this post, but I recommend checking out OpenAI Five and DeepMind AlphaStar.

Goal of this Project

The goal of this project is to train two RL agents to play tennis. As in real tennis, the goal of each player is to keep the ball in play. And, when you have two equally matched opponents, you tend to see fairly long exchanges where the players hit the ball back and forth over the net.

The Environment

We’ll work with an environment that is similar, but not identical to the Tennis environment on the Unity ML-Agents GitHub page.

In this environment, two agents control rackets to bounce a ball over a net. If an agent hits the ball over the net, it receives a reward of +0.1. If an agent lets a ball hit the ground or hits the ball out of bounds, it receives a reward of -0.01. Thus, the goal of each agent is to keep the ball in play.

The observation space consists of 8 variables corresponding to the position and velocity of the ball and racket. Each agent receives its own, local observation. Two continuous actions are available, corresponding to moves toward (or away from) the net, and jumping.

The task is episodic, and in order to solve the environment, the agents must get an average score of +0.5 (over 100 consecutive episodes, after taking the maximum over both agents).

Specifically,

• After each episode, we add up the rewards that each agent received (without discounting), to get a score for each agent. This yields 2 potentially different scores. We then take the maximum of these 2 scores.
• This yields a single score for each episode.
• The environment is considered solved when the average (over 100 episodes) of those scores is at least +0.5.

Here is an example of two semi-trained agents interacting in this environment.

Approach

Here are the high-level steps that were taken in building an agent that solves this environment.

1. Establish performance baseline using a random action policy.
2. Select an appropriate algorithm and begin implementing it.
3. Run experiments, make revisions, and retrain the agent until the performance threshold is reached.

DISCLAIMER: I ultimately reached a good solution; however, the results were not consistent. My “best” results were only reproducible if I reran the model numerous times (>10). If you just run the model once (or even 3–5 times), it might not converge. And, during the initial implementation, I ran the model at least 30 times while searching for a reliable set of hyperparameters. If you want to experiment with different approaches, I strongly recommend implementing a more systematic approach to hyperparameter tuning (which I did not do, but wish I had).

Establishing a Baseline

Before building agents that learn, I started by testing ones that select actions (uniformly) at random at each time step.

Running the random agents a few times resulted in scores from 0 to 0.02. Obviously, if these agents need to achieve an average score of 0.5 over 100 consecutive episodes, then choosing actions at random won’t work. However, when you watch the agents acting randomly, it becomes clear that these types of sporadic actions can be useful early in the training process. That is, they can help the agents explore the action space to find some signal of good vs. bad actions. This insight will come into play later when we implement the Ornstein-Uhlenbeck process and epsilon noise decay.

Implementing the Learning Algorithm

To get started, there are a few high-level architecture decisions we need to make. First, we need to determine which types of algorithms are most suitable for the Tennis environment.

Policy-based vs Value-based Methods

There are two key differences in the Tennis environment compared to the ‘Navigation’ environment from the first project in Udacity’s Deep RL program:

1. Multiple agents. The Tennis environment has two different agents, whereas the Navigation project had only a single agent.
2. Continuous action space. The action space is now continuous (instead of discrete), which allows each agent to execute more complex and precise movements. Even though each tennis agent can only move forward, backward, or jump, there’s an unlimited range of possible action values that control these movements. Whereas, the agent in the Navigation project was limited to four discrete actions: left, right, forward, backward.

Given the additional complexity of this environment, the value-based method we used for the Navigation project is not suitable — i.e., the Deep Q-Network (DQN) algorithm. Most importantly, we need an algorithm that allows the tennis agent to utilize its full range and power of movement. For this, we’ll need to explore a different class of algorithms called policy-based methods.

Here are some advantages of policy-based methods:

• Continuous action spaces. Policy-based methods are well-suited for continuous action spaces.
• Stochastic policies. Both value-based and policy-based methods can learn deterministic policies. However, policy-based methods can also learn true stochastic policies.
• Simplicity. Policy-based methods directly learn the optimal policy, without having to maintain a separate value function estimate. With value-based methods, the agent uses its experience with the environment to maintain an estimate of the optimal action-value function, from which an optimal policy is derived. This intermediate step requires the storage of lots of additional data since you need to account for all possible action values. Even if you discretize the action space, the number of possible actions can get quite large. And, using DQN to determine the action that maximizes the action-value function within a continuous or high-dimensional space requires a complex optimization process at every timestep.

Multi-Agent Deep Deterministic Policy Gradient (MADDPG)

The original DDPG algorithm, which I extended to create the MADDPG version, is outlined in this paper, Continuous Control with Deep Reinforcement Learning, by researchers at Google Deepmind. In this paper, the authors present “a model-free, off-policy actor-critic algorithm using deep function approximators that can learn policies in high-dimensional, continuous action spaces.” They highlight that DDPG can be viewed as an extension of Deep Q-learning to continuous tasks.

For the DDPG foundation, I used this vanilla, single-agent DDPG as a template. Then, to make this algorithm suitable for the multiple competitive agents in the Tennis environment, I implemented components discussed in this paper, Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments, by Lowe and Wu, along with other researchers from OpenAI, UC Berkeley, and McGill University. Most notably, I implemented their variation of the actor-critic method (see Figure 1), which I discuss in the following section.

Lastly, I further experimented with components of the DDPG algorithm based on other concepts covered in Udacity’s classroom and lessons. My implementation of this algorithm (including various customizations) is discussed below.

Actor-Critic Method

Actor-critic methods leverage the strengths of both policy-based and value-based methods.

Using a policy-based approach, the agent (actor) learns how to act by directly estimating the optimal policy and maximizing reward through gradient ascent. Meanwhile, employing a value-based approach, the agent (critic) learns how to estimate the value (i.e., the future cumulative reward) of different state-action pairs. Actor-critic methods combine these two approaches in order to accelerate the learning process. Actor-critic agents are also more stable than value-based agents, while requiring fewer training samples than policy-based agents.

What makes this implementation unique is the decentralized actor with centralized critic approach from the paper by Lowe and Wu. Whereas traditional actor-critic methods have a separate critic for each agent, this approach utilizes a single critic that receives as input the actions and state observations from all agents. This extra information makes training easier and allows for centralized training with decentralized execution. Each agent still takes actions based on its own unique observations of the environment.

You can find the actor-critic logic implemented as part of the Agent() class here in maddpg_agent.py of the source code. The actor-critic models can be found via their respective Actor() and Critic() classes here in models.py.

Note: As we did with Double Q-Learning in the last project, Continuous Control: Training a Set of Robotic Arms, we’re again leveraging local and target networks to improve stability. This is where one set of parameters w is used to select the best action, and another set of parameters wʹ is used to evaluate that action. In this project, local and target networks are implemented separately for both the actor and the critic.

Exploration vs Exploitation

One challenge is choosing which action to take while the agent is still learning the optimal policy. Should the agent choose an action based on the rewards observed thus far? Or, should the agent try a new action in hopes of earning a higher reward? This is known as the exploration vs. exploitation dilemma.

In the previous Navigation project, I addressed this by implementing an 𝛆-greedy algorithm. This algorithm allows the agent to systematically manage the exploration vs. exploitation trade-off. The agent “explores” by picking a random action with some probability epsilon 𝛜. Meanwhile, the agent continues to “exploit” its knowledge of the environment by choosing actions based on the deterministic policy with probability (1-𝛜).

However, this approach won’t work for controlling the tennis agents. The reason is that the actions are no longer a discrete set of simple directions (i.e., up, down, left, right). The actions driving the movement of the arm are forces with different magnitudes and directions. If we base our exploration mechanism on random uniform sampling, the direction actions would have a mean of zero, in turn canceling each other out. This can cause the system to oscillate without making much progress.

Instead, we’ll use the Ornstein-Uhlenbeck process, as suggested in the previously mentioned paper by Google DeepMind (see bottom of page 4). The Ornstein-Uhlenbeck process adds a certain amount of noise to the action values at each timestep. This noise is correlated to previous noise and therefore tends to stay in the same direction for longer durations without canceling itself out. This allows the agent to maintain velocity and explore the action space with more continuity.

You can find the Ornstein-Uhlenbeck process implemented here in the OUNoise() class in maddpg_agent.py of the source code.

In total, there are five hyperparameters related to this noise process.

The Ornstein-Uhlenbeck process itself has three hyperparameters that determine the noise characteristics and magnitude:

• mu: the long-running mean
• theta: the speed of mean reversion
• sigma: the volatility parameter

Of these, I only tuned sigma. After running a few experiments, I reduced sigma from 0.3 to 0.2. The reduced noise volatility seemed to help the model converge.

Notice also there’s an epsilon parameter used to decay the noise level over time. This decay mechanism ensures that more noise is introduced earlier in the training process (i.e., higher exploration), and the noise decreases over time as the agent gains more experience (i.e., higher exploitation). The starting value for epsilon and its decay rate are two hyperparameters that were tuned during experimentation.

You can find the epsilon decay process implemented here in the Agent.act() method in maddpg_agent.py of the source code. While the epsilon decay is performed here as part of the learning step.

The final noise parameters were set as follows:

OU_SIGMA = 0.2   # Ornstein-Uhlenbeck noise parameter, volatility
OU_THETA = 0.15  # OU noise parameter, speed of mean reversion
EPS_START = 5.0  # initial value for epsilon in noise decay process
EPS_EP_END = 300 # episode to end the noise decay process
EPS_FINAL = 0    # final value for epsilon after decay

IMPORTANT NOTE: Notice that the EPS_START parameter is set at 5.0. For dozens of experiments, I had this parameter set to 1.0, as I had in previous projects. But, I had a difficult time getting the model to converge, and if it did, it converged very slowly (>1500 episodes). After much trial and error, I realized that the agents had some difficulty discovering signal early in the process (i.e., most episode scores equaled zero). By boosting the noise output from the Ornstein-Uhlenbeck (OU) process, it encouraged aggressive exploration of the action space and therefore improved the chances that signal would be detected (i.e., making contact with the ball). This extra signal seemed to improve learning later in training once the noise decayed to zero.

Learning Interval

In the first few versions of my implementation, the agent only performed a single learning iteration per episode. Although the best model had this setting, this seemed to be a stroke of luck. In general, I found that performing multiple learning passes per episode yielded faster convergence and higher scores. This did make training slower, but it was a worthwhile trade-off. In the end, I implemented an interval in which the learning step is performed every episode. As part of each learning step, the algorithm then samples experiences from the buffer and runs the Agent.learn() method 10 times.

LEARN_EVERY = 1  # learning interval (no. of episodes)
LEARN_NUM = 5    # number of passes per learning step

You can find the learning interval implemented here in the Agent.step() method in maddpg_agent.py of the source code.

Gradient Clipping

In early versions of my implementation, I had trouble getting my agent to learn. Or, rather, it would start to learn but then become very unstable and either plateau or collapse.

I suspect that one of the causes was outsized gradients. Unfortunately, I couldn’t find an easy way to investigate this, although I’m sure there’s some way of doing this in PyTorch. Absent this investigation, I hypothesize that many of the weights from my critic model were becoming quite large after just 50–100 episodes of training. And since I was running the learning process multiple times per episode, it only made the problem worse.

The issue of exploding gradients is described in layman’s terms in this post by Jason Brownlee. Essentially, each layer of your net amplifies the gradient it receives. This becomes a problem when the lower layers of the network accumulate huge gradients, making their respective weight updates too large to allow the model to learn anything.

To combat this, I implemented gradient clipping using the torch.nn.utils.clip_grad_norm function. I set the function to “clip” the norm of the gradients at 1, therefore placing an upper limit on the size of the parameter updates, and preventing them from growing exponentially. Once this change was implemented, my model became much more stable and my agent started learning at a much faster rate.

You can find gradient clipping implemented here in the “update critic” section of the Agent.learn() method, within ddpg_agent.py of the source code.

Note that this function is applied after the backward pass but before the optimization step.

# Compute critic loss
Q_expected = self.critic_local(states, actions)
critic_loss = F.mse_loss(Q_expected, Q_targets)

# Minimize the loss
self.critic_optimizer.zero_grad()
critic_loss.backward()
torch.nn.utils.clip_grad_norm_(self.critic_local.parameters(), 1)
self.critic_optimizer.step()

Experience Replay

Experience replay allows the RL agent to learn from past experience.

As with the previous project, the algorithm employs a replay buffer to gather experiences. Experiences are stored in a single replay buffer as each agent interacts with the environment. These experiences are then utilized by the central critic, therefore allowing the agents to learn from each others’ experiences.

The replay buffer contains a collection of experience tuples with the state, action, reward, and next state (s, a, r, sʹ). The critic samples from this buffer as part of the learning step. Experiences are sampled randomly so that the data is uncorrelated. This prevents action values from oscillating or diverging catastrophically since a naive algorithm could otherwise become biased by correlations between sequential experience tuples.

Also, experience replay improves learning through repetition. By doing multiple passes over the data, our agents have multiple opportunities to learn from a single experience tuple. This is particularly useful for state-action pairs that occur infrequently within the environment.

The implementation of the replay buffer can be found here in the maddpg_agent.py file of the source code.

Results

Once all of the above components were in place, the agents were able to solve the Tennis environment. Again, the performance goal is an average reward of at least +0.5 over 100 episodes, taking the best score from either agent for a given episode.

Here is a video showing the trained agents playing a few points.

The graph below shows the final training results. The best-performing agents were able to solve the environment in 607 episodes, with a top score of 5.2 and a top moving average of 0.927. The complete set of results and steps can be found in the Tennis.ipynb Jupyter notebook.

Future Improvements

• Address stability issues to produce more consistent results. My “best” results are only reproducible if you run the model numerous times. If you just run it once (or even 3–5 times) the model might not converge. I ran the model at least 30 while searching for a good set of hyperparameters, so perhaps implementing a more systemic approach such as grid search would help. Otherwise, more research is needed to find a more stable algorithm or to make changes to the current DDPG algorithm.
• Add prioritized experience replay. Rather than selecting experience tuples randomly, prioritized replay selects experiences based on a priority value that is correlated with the magnitude of the error. This can improve learning by increasing the probability that rare or important experience vectors are sampled.
• Batch Normalization. I did not use batch normalization on this project, but I probably should have. I’ve used batch normalization many times in the past when building convolutional neural networks (CNN), in order to squash pixel values. But, it didn’t occur to me that it would be to this project. Batch normalization was used in the Google DeepMind paper and has proved tremendously useful in my implementation of other projects. Similar to the exploding gradient issue mentioned above, running computations on large input values and model parameters can inhibit learning. Batch normalization addresses this problem by scaling the features to be within the same range throughout the model and across different environments and units. In additional to normalizing each dimension to have unit mean and variance, the range of values is often much smaller, typically between 0 and 1. You can find batch normalization implemented here for the actor and here for the critic, within model.py of the source code of my previous project, Training Robotic Arms with Continuous Control. This greatly improved model performance and stability.

Contact

I hope you found this useful. Again, if you have any feedback, I’d love to hear it. Feel free to post in the comments.

If you’d like to discuss other collaboration or career opportunities you can find me here on LinkedIn or view my portfolio here.

Training Two Agents to Play Tennis was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.