Special thanks to Shreya Sajal, Vishal Agarwal and Aravinth Muthu for giving very helpful feedback on previous versions of this post!

A common challenge with using Large Language Models (LLMs) in production is hallucination, where a model produces responses that sounds real/accurate but is factually incorrect, leading to lack of reliability in LLM-powered apps. We have been using LLMs successfully in production to analyse and extract information from thousands of legal contracts at HyperStart, a contract-lifecycle management tool for Small and Medium scale Businesses (SMBs). In this post, I’ll share a simple technique that has improved the accuracy and reliability of our system on the most challenging tasks multi-fold.

Before we jump into the approach, let’s understand the problem a bit more. The two most common techniques for mitigating hallucination are Chain-Of-Thought (CoT) prompting [1, 2] and Retrieval Augmented Generation (RAG) [3, 4]. If you’re not already familiar with these, do check out the links and return back to the blog post later.

You might be able to tackle hallucination for your specific use case almost entirely using CoT + RAG itself (although you will likely need to iterate a few times to land at the right custom prompt). However, if your problem statement involves a strong reasoning component with multiple reasoning steps, this might not be enough. The gap between where you want to be and where you land after applying CoT + RAG (and their variations) [the reasoning gap] is what this blog post aims to fill.

Note: I haven’t tested Claude Opus/Gemini 1.5 yet (the only other models in the class of GPT4 at the time of this post) and it is very likely that future versions of all these models will be much better at reasoning, in which case you might not need this technique. But one can speculate that when that future arrives, you might not need a lot of things. But that’s a separate post. Let’s focus on solving the problems of today while being optimistic about the future!

For ease of understanding, let’s assume you want the LLM to produce the desired output in a given JSON format. Arriving at the final JSON answer requires multiple steps of reasoning. Let’s consider the following example to automatically screen a candidate’s resume:

System prompt:
You are a very good recruiting assistant. 

You will be given the resume of a candidate for a Machine Learning role. 

You need to assess whether the candidate must be shortlisted.

Use the following criteria for deciding if the candidate must be shortlisted:
- Number of internships in machine learning/deep learning
- GPA
- Number of publications and personal projects they have worked on related to
  machine learning

If the GPA is more than 9.5, then, they only need to have one internship to be
shortlisted. If the GPA is more than 9 but less than 9.5, along with one
internship, they need at least one publications or projects as well. If the
GPA is between 8 and 9, publications + project + internship must be >= 3, with
at least one internship. Otherwise, the number combined must be atleast 4.

Give your final answer as a JSON with the key `is_shortlisted` which should be a boolean value.

This is an example of a multi-step reasoning task as the LLM has to first extract various details like the GPA, identify which parts of the CV represent projects vs internships vs publications, classify the relevance of each of them and then, use the provided rubric to come up with the final answer.

Here, the candidate’s resume will be provided as context to the LLM for extracting the final answer. Since we’ve asked the model to simply output a JSON, without any chain-of-thought prompting, the model will likely instantly respond with:

{ "is_shortlisted": True }

Note: this is a relatively simpler example and the actual challenge here is figuring out how to classify a given project/internship/publication as relevant. But let’s ignore that for now and focus on the model’s behaviour.

You might evaluate this prompt on your dataset and are likely to observe poor performance. Your first instinct should be to utilise “Chain-of-Thought Prompting” which asks the model to include reasoning steps before arriving at the final answer. You’re likely to notice a significant boost in performance.

However, you might notice there are still several mistakes. Upon inspecting the responses, you might notice that the model correctly inferred the GPA as well as the number of relevant projects (n_p), internships (n_i) and publications (n_pu) individually. However, it still failed to arrive at the correct output. For one such error sample, it might have incorrectly added n_pi, n_p, and n_i. For another one, it might have computed the sum correctly but failed to follow the rubric.

There are two types of reasoning steps you’ll encounter when breaking a problem into smaller steps. We’ll be looking at each of them with an example along with how to tackle them.

Deterministic reasoning

In this case, the next reasoning step is deterministic over the outputs of the previous reasoning steps. As shown in the example above, is_shortlisted must be decided using a rubric (mentioned in the system prompt), which is a deterministic step, given the gpa, n_pu, n_i, and n_p as inputs.

Instead of asking the LLM to output is_shortlisted, the core information that only the LLM can extract is really just gpa, n_pu, n_i, and n_p . We don’t need the LLM to refer to the rubric to give the final output. The LLM is just a tool and we should use the right tool to solve a given problem. Once the values have been extracted, the LLM is not the right tool to follow the rubric. The rubric can simply be applied outside the LLM call as shown in the image below.

An additional benefit of doing this is one level deeper explainability for the final response given by the system as we now know the input to the rubric, which helps with building user trust as well as debugging (in case the inputs have been extracted incorrectly).

Semantic reasoning

Here, the current reasoning step requires an LLM to operate on the outputs of the previous steps to arrive at the final answer. Suppose your task is to count the number of times the co-leads in a movie script are playing a positive role vs a negative role. You could ask the LLM to give the answer directly in one go. But it is possible that it might confuse the positive/negative role occurrences between the co-leads.

A better approach could be:

1. Extract the names of the co-leads (1 LLM call)
2. For each name, count the number of times that person played a positive and negative role (N API calls for N co-leads).

Summary

Given the examples above, the core idea can be summarised as:

• Break the problem statement down into smaller steps such that every reasoning step requires only one level of reasoning (as explained above).
• At each step, use the LLM as an extractor of information that can be used by the next step to get closer to the final output.
• Depending on whether the current step requires deterministic or requires semantic reasoning, either avoid using LLMs (e.g. handle conditionals separately through code instead of asking an LLM to follow a given rubric) or make further LLM calls respectively.

It probably does not look very different from thinking step-by-step or using function calling in agentic flows. The key change proposed here is in the mindset of what each step means. Typically, we expect an LLM inference to perform all the reasoning steps in one go before arriving at the final answer, even steps where an LLM is not even needed (e.g. following a rubric). LLM Agent flows would usually consider the multiple steps we’ve proposed as just one block in the flow, with a single LLM call. A mindset shift is needed to see one block as being composed of potentially multiple blocks itself.

There are a couple of tradeoffs in this approach that you must be aware of. If the individual steps require semantic reasoning, you’ll need to make multiple LLM calls, which will increase your inference cost and time. If your problem statement resembles the second example above (extracting the number of negative and positive roles for all the co-leads), you can run the LLM inference for each co-lead in parallel in the second step, reducing the increase in the overall inference time.

Conclusion

This technique has radically improved the reliability of the systems I’ve built and given a massive boost to their overall accuracy. I hope this post was helpful and gave you a handy tool for improving the performance of your LLM apps too.

LLMs as single-step reasoners: mitigating hallucination in multi-step reasoning was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

I’ve been working with LLMs on production for the last 10 months. Naturally, reliability and accuracy become crucial. So is debugging LLMs. I haven’t seen enough discussions around the processes people have adopted for debugging LLMs. But that is natural given that there hasn’t been enough time for best practices to emerge yet. I want to contribute my bit to the conversation by sharing the technique I’ve arrived at which has helped me dramatically improve the accuracy and reliability of the systems I build, quickly and efficiently:

• Replication: Copy the system prompt and user prompt for which the LLM is failing to OpenAI’s Playground (after formatting, i.e. “\n” should become a new line), set all the parameters like temperature, max_tokens, top_p, etc. to the exact same value as that in your API call and hit “Submit”. If you’re lucky, you would be able to replicate the issue on the first go. Depending on your settings, however, you might have to repeat this a few times until you can reproduce the bug because the LLM’s output can vary on each API call (the chances of this reduces if you set temperature to 0 but it doesn’t guarantee deterministic outputs as described in more detail below).
• Problem identification: Once you’re able to replicate the issue, simply ask the LLM to “explain” the part of the output that is incorrect. It is very important not to ask “why did you output X” as the LLM will simply resort to apologising and giving the correct answer. The goal of this step is to figure out the part (s) of your prompt that is confusing the LLM, or any instructions that are missing in your prompt for the specific edge case where it is failing, probably because it is trying to provide an answer with missing information.
• Iteration: Once you’ve identified what’s incorrect or missing, you need to update your prompt to handle that edge case. The way you word your new instruction matters a lot. Writing correct grammatical sentences with consistent, appropriate spacing and punctuation marks has an unexpected impact on the consistency and reliability of the outputs. You might have to experiment with adding the instruction at the start of the prompt or at the end, or inside the description for a field if you’re extracting a JSON and have provided a JSON template for the LLM to output. I tend to keep a section named “Important Instructions” in my system prompt to which I keep adding new instructions as the need surfaces upon debugging. Now, you might be tempted to pile on more and more instructions but Mark Twain once said, “I didn’t have time to write a short letter, so I wrote a long one instead”. It takes more effort to identify the clunky bits in your prompt and make your prompt concise. If it is becoming confusing for you to go through the list of instructions, it is likely confusing for the LLM as well. Keep going back and try to find redundant pieces of instructions or instructions that are contradicting each other. You might have written an instruction as an overly complicated sentence. Sometimes, making a sentence simpler solves the problem. You are likely to see that the problem persists even after adding a new instruction that should have ideally handled the edge case. In such cases, you might want to rephrase your instruction or make it “shout” by adding phrases like: “if so and so happens, make sure to ALWAYS do so and so. It is very important that you pay a lot of attention to this and never make a mistake”. There is nothing magical about this exact phrase. It is just an example meant to convey a point. The main takeaway being that prompt engineering requires a lot of perseverance the harder your task is and the more nuanced your edge case becomes. You cannot give up. You have to keep iterating. But don’t blindly iterate. Pay attention to the pattern of its mistakes and find smarter experiments to try rather than simply adding/removing sentences/words randomly/thoughtlessly.
• Double checking: Alas, the moment has arrived. Your hours of hard work has paid off and the LLM is finally able to give the correct output. Unfortunately, it’s not yet the time to celebrate. Delete the assistant response and hit “Submit” again. You cannot believe yourself. It is back to generating the incorrect output. “How can that be?”, you might wonder. “The temperature is 0, shouldn’t the output be deterministic?”. Unfortunately, not. The parameters like temperature, top_p, etc. are just some of the sources of randomness in the inference step of an LLM. There are others that you cannot control. Because of this, even with the temperature being 0, the outputs of the LLM can vary. Sometimes, these variations are not harmful because they eventually land at the same answer, even if they are using a different combination of words in the output. But sometimes, they can break your heart and hurt your sleep. Typically, these variations that oscillate between the correct and the incorrect output are a result of ambiguity, confusion, contradiction or lack of instructions in your prompt. Thus, you’ll have to go back to the “Iteration” step to update your prompts until multiple LLM calls for the same input give the correct output consistently every time.
• Benchmarking: Are you kidding me? We aren’t done yet? Unfortunately not. But we are engineers who care about building a solid, reliable system using a technology that has immense potential but doesn’t have a good reputation for reliability. So, you found what was missing or incorrect in your prompt and after 100s of iterations, you’ve finally landed on something that consistently produces the correct output for the edge case where it was previously failing. That’s awesome. But how do you know that the new prompt doesn’t create new edge cases? You don’t. So, you’ll need to rerun the inference on your entire benchmark dataset (if you don’t have a benchmark dataset and you’re building an LLM application for production, you really need one, like, yesterday, trust me). If none of the other examples are affected, bravo. The debugging is complete. At least, for the moment. However, if the performance worsens on other samples now, you’ll have to go back to step 1 for those new erroneous samples.

If the sounds like a lot of work, it is. But that is also what makes it fun (although it doesn’t look like anything remotely resembling fun when you’re knee deep in the debugging process). Not everyone will be able to persevere, find the correct underlying patterns that can apply correctly across all the samples, gracefully handling all the edge cases. But you did. And that’s what makes you awesome.

I hope you learnt something useful from this post. I’d love to hear your experiences (and frustrations) with prompt engineering (or LLMs, RAG, etc.) as well.

Disclaimer: this debugging tactic assumes that you’ve already tried (to no avail) some of the basic prompt engineering hacks like assigning a role to the LLM, enclosing your responses within delimiters, giving the model time to think using techniques like chain-of-thought reasoning. Many of these basic tactics have been documented in OpenAI’s prompt engineering guide along with other excellent prompt engineering guides available online.

A simple (not easy) technique for debugging LLMs using LLMs was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

I provide the context for how I got started in the competition, my struggles, journey to the final solution and everything I learned

I recently took part in the SIIM-ISIC Melanoma Classification challenge hosted on Kaggle during the last 2 weeks of the competition and was able to secure my first silver🏅on the platform. This was only my 2nd Kaggle competition, and the first one in 4 years.

The point of mentioning this is merely to indicate what is possible even within such a short time frame. It was a tremendous learning opportunity for me and I regretted not being a part of this earlier. The goal of this post is walk through my journey of beginning the competition in its final phase — my initial struggles, starting off step-by-step and arriving at my final submission — and to share everything that I learned in the process, specifically about the Kaggle community. This is how the blog post is structured:

• Participating in the competition
• Arriving at the final solution
• Some of the things I avoided
• Learnings
• References

I hope this blog post can convince you that irrespective of what you might think of yourself, you are always welcomed in the Kaggle community and the best way to start learning is by just diving right in and doing something.

Participating in the competition

The main reason that I hadn’t participated in a Kaggle competition seriously before was that I was not sure what I could learn from it that I wouldn’t from my everyday work as an AI researcher and hence, most of my time was spent completely at work. However, over time, I’ve realized that I have not been able to stay updated about the latest practical tips for improving model performance as a majority of my time at work is dedicated towards data, compounded with the data size being relatively small. So, I needed a playground for me to test out my wild ideas and learn about the techniques that worked in practice. This was a major reason for me to explore Kaggle and I found the SIIM-ISIC Melanoma Classification challenge as the perfect starting point as the binary image classification task is simple enough for me to get a feel for the platform and also, have a realistic chance of performing well as I’ve been working on computer vision for many years now.

Initial struggles 😔

Contrary to what I had expected, I felt extremely overwhelmed seeing the amount of discussions, knowledge sharing (in the form of data and code) that was taking place and the current best leaderboard scores. I wanted to keep track of everything and understand everything in one day so that I could be at the same place as everyone else. I ended up putting a lot of pressure on myself and this made me lose my initial motivation.

Slowly making progress 🤞

Thankfully, I realized quickly that it wasn’t possible for me to get a hold of everything and there will be things that I am missing out. I convinced myself to be comfortable with knowing that I won’t be knowing everything there is to know. I started off slowly by creating the right cross-validation data for validating model performance. Creating the right split was crucial for this competition and as I’ll mention later, the cross-validation score was very important in determining the final outcome. Then, I created a baseline model using ResNet-18 with a basic input processing pipeline. This helped me get an AUC of 0.84 on the public LeaderBoard (LB) and allowed me to complete the pipeline of submitting a result.

I usually breathe a sigh of relief once the end-to-end pipeline of anything that I’m working on is complete. This allows me the flexibility to tune individual components and be sure that there are no unknown unknowns down the road that would need my attention. So, I was happy after doing this and going forward, I kept adding new components to it one at a time and I’ll describe what finally landed me in the top 5% out of 3000+ competitors.

Before describing the final solution, I want to share three philosophies that helped me iterate faster:

• The first one is an advice from Jeremy Howard from fast.ai that practically, you often don’t need all of the data or even the entire input to arrive at a decent performance. This could mean using a fraction of the entire dataset and using images of smaller resolution (say, 224 x 224) instead of using the entire image, which could be 1024 x 1024 and take a lot of time to load and process.
• Another philosophy is something that can be considered widely known to truly matter for improving model performance but I’ll still state it explicitly — feed the data correctly, more data helps, use the correct data augmentations, find the right optimization recipe and identify the right model class. Just focusing on these things should land you a pretty decent performance. It’s all about finding the right mix now. Once I found the right recipe on images with a smaller resolution, I used the same recipe with a larger image resolution. That is expected to improve performance.
• Ensembling generally always helps. Model ensembling has a theoretical justification for model improvement with the current set of base models. This blog post is an excellent reference. Simple techniques like combining diverse models (models with low correlation in their predictions) and combining the same model trained on different input sizes can provide a significant lift.

Arriving at the final solution 🗻

Once I had a solid base, I played around with different aspects of the entire pipeline which I listed towards the end of the last section— model, optimization, image sizes, using external data (data that is not a part of the competition), data augmentation and handling data imbalance.

My best model was an ensemble (taking the mean of the predictions of the individual models) of 4 models.

Image sizes

3 models were trained on 512x512 images and 1 model on 384x384.

Augmentations

2 models use the following augmentations (using kornia):

- name: Rescale
  params:
      value: 255.
- name: RandomAffine
  params:
      degrees: 180
      translate:
        - 0.02
        - 0.02
- name: RandomHorizontalFlip
  params:
      p: 0.5
- name: ColorJitter
  params:
      saturation:
        - 0.7
        - 1.3
      contrast:
        - 0.8
        - 1.2
      brightness: 0.1
- name: Normalize
  params:
      mean: imagenet
      std: imagenet

The meaning of different parameters can be found from kornia's documentation. The other 2 models additionally use Cutout:

- name: RandomErasing
  params:
      p: 0.5
      ratio:
        - 0.3
        - 3.3
      scale:
        - 0.02
        - 0.1

Data Sampling

To iterate faster and handle data imbalance, instead of upsampling the minority class, I downsample the majority class per epoch. However, to avoid wasting data, I sample different instances from the majority class per epoch.

Network

The same network architecture is used for all the 4 models — EfficientNet-B5 features followed by a Linear layer. I tried a vast range of models but EfficientNet-B5 was the best single model.

Optimization — SuperConvergence

One of the decisions I made for iterating faster was to restrict the number of epochs to 20. To achieve this, I used the OneCycle learning rate scheduler introduced in this paper. This scheduler requires one to specify the minimum and maximum learning rates. These two were found to be 5e-6 and 2e-4 respectively, using the LR-range-test. Also, to address overfitting, I apply a weight decay of 0.1. Adam usually obtains the best results in a very quick time. However, this paper clarifies how weight decay is not applied correctly in Adam, and instead, proposes a modification to Adam — AdamW. That is the final optimizer that I have used.

Test Time Augmentation (TTA)

TTA was introduced in fast.ai to improve model performance during inference. Contrary to the general wisdom of turning data augmentation off during inference, TTA refers to keeping it on during inference as well. Since there is randomness associated with augmentations, trusting on running inference only once can lead to wrong conclusions and might even give a worse performance. Hence, in TTA, we run inference for N_TTA number of times. Finally, to obtain the prediction for each instance, we combine the predictions across the N_TTA inference runs. One simple way of combining is by taking the mean of the predictions. For this competition, I used N_TTA = 15. Note that this is computationally very expensive but it leads to clear performance improvement for this task.

Things I wanted to try but couldn’t

That’s it. These components helped me land in the top 5% of the competition in just 2 weeks. If they seem too simple to you, then you are right! :)

However, there were still many ideas that I wanted to try but I couldn’t, given the time shortage. I’m also listing them down in case there is something to learn from them:

• Train on images of different sizes better: I would like to diligently keep track of the best experiments on images of lower resolution and re-run ALL of them for images with higher resolution followed by ensembling all of them. I didn’t stay consistent with this framework.
• Combine metadata with images: The competition also provides a lot of metadata for each image that could be used to improve performance. The winning team used the metadata by stacking it with the features extracted from the CNN before feeding it to the classifier.
• Spend time improving my ensembles: As I mention in the learnings section, ensembling was key and I, unfortunately, didn’t spend time learning about the best practices here and just stuck to averaging the predictions of my base models. More on this later.
• Trying more augmentations: There were a variety of augmentations discussed throughout the competition along with augmentations specific to the type of data in the augmentation (like adding hair randomly to images because a lot of images contained hairs).
• Custom head: My network consisted of a single linear layer after the features extracted from the convolutional network. However, it is often better to add more than one linear layer.

Some of the things I avoided

There were many overly complicated things mentioned in the discussions like generating images from the data and using that as additional training data. These might be good ideas but I tend to like simplistic solutions and I wanted to achieve the best possible results using them. I still feel that I could get a higher score simply by using a better ensembling technique.

Learnings

1 - the power of ensembling

Ensembling is the technique of combining the predictions of several independent models/learners. I won’t go into technical details here as there are many excellent articles that already do that (this one for example). I noticed people reporting a cross-validation (CV) score much higher than what I was getting with a similar setup. It was only much later that I realized that the best CV score for a single model was still very close to what I was getting. The winners used advanced ensembling techniques like stacking, ranking (this one is specific to the metric being optimized here) and model blending to improve their final performance dramatically. One of the top submissions was actually just a weighted average of 20 public submissions. Thus, one should focus on getting the right ensembling recipe.

2 - trust your CV

One of the dramatic moments of the competition was when the private leaderboard results were opened. There was a massive shake-up in the entire leaderboard with many top submissions dropping significantly low and many teams jumping up more than 1000 spots (I myself climbed around 800 spots). This left many people reasonably disappointed as they had overfitted to the public leaderboard. However, a lot of the solution overviews posted after the competition ended strongly emphasized the need to focus on the CV score as the public leaderboard can often lie but they found a strong correlation between their CV scores and the private leaderboard ranking. So, the mantra became: “In CV, we trust”. Because I found this out very late, contrary to the general method of reporting cross-validation performance by taking the mean and standard deviation across all the folds, there is a better way that is typically used to report CV score in Kaggle competitions. This notebook illustrates that very nicely. Essentially, for each fold, you should save your Out-Of-Fold (OOF) predictions (predictions for the instances forming the validation set in that particular fold) for each fold. At the end of 5 folds, you will have a list of predictions for each sample in the train set and you should compute the metric on this list of predictions to get your final CV score.

3 - code sharing through kernels

Many people shared their submission notebooks publicly which truly helped clarify several doubts that often stay, even after people have tried their best (or not) to explain their methodology. It also helps to learn about minor implementation details that often get left out while talking about the big picture. Additionally, reading other people’s code is a great way of improving your own coding skills. I personally learned quite a bit as well. Finally, Kaggle Kernels offer both GPU and TPU for a limited quota. This is awesome and it removes the need to depend on on-prem infra or the requirement of being able to spend a lot of money on cloud VMs.

4 - discussions and knowledge sharing 💡

I was truly surprised to see how willing people were to engage with each other, often sharing their code and data to provide a very good starting point for other people. People also shared their approaches while the competition was still ongoing while also discussing what worked for them and what didn’t. Considering the fact that this is a competition with a monetary prize associated with it, I was truly taken aback by how collaborative the nature of discussions was and how kind everyone was to any newcomer asking silly questions as well.

5 - community of doers 👨‍💻👩‍💻

Finally, I just want to say that it was amazing to have found a community of doers — people who focus on actually getting the job done, with whom I could have deep, meaningful technical discussions (and jokes). I have struggled to find the right online community for myself and although I am yet to find my footing there, I definitely know that I am here to stay! :)

References

I’ll keep adding more to this list.

General resources

• Collections of solutions from the competition
• Ten Techniques Learned From fast.ai
• Kornia: an Open Source Differentiable Computer Vision Library for PyTorch

Cross-validation

• How To CV and How To Ensemble OOF Files
• Computing CV score correctly and example of stacking

Optimization

• Intuition to LR Range Test, Cyclical LR and the One-Cycle Policy
• A disciplined approach to neural network hyper-parameters: Part 1 — learning rate, batch size, momentum, and weight decay
• Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates
• AdamW — Decoupled Weight Decay Regularization

Ensembling

• Kaggle ensembling guide
• Several model averaging techniques
• Improve blending using Rankdata

I hope this blog post was able to serve as a good starting point for anyone looking to jump into Kaggle. I have tried to cover all the topics that I felt was completely new to me and I had to dig through the discussions to understand them. In the near future, I plan to release my experimentation framework along with the code for this competition to foster reproducibility and help others build on top of my work — built with ❤️ using PyTorch.

If there’s anything that you might want to share with me or give me any feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on Twitter, LinkedIn or follow me on Github. To stay updated with my posts, do follow me on Medium.

A community of doers: learnings from winning a solo silver medal within 2 weeks in my 2nd Kaggle… was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

Over the past couple of years, the state-of-the-art AI algorithms have started moving out from research labs to out in the real world. This has significant implications as the advancements that have been happening in the AI community, now has the potential to reach billions of people across the globe. However, once you decide to deploy an AI model, there are a ton of things that need to be decided, one of them being the nature of the deployment.

There are broadly two ways in which one can deploy an AI model:

While it is easier to deploy your AI model on the server, it has several shortcomings. One of the major ones is the variability of network connection when the model is used on a large scale. Even though the internet seems ubiquitous today, there are still large parts of the world where internet connectivity is intermittent, if not absent. And if your target audience happens to reside in those geographies, you need to consider on-device inference seriously. Some of the other factors that make a case for on-device inference are privacy on the client side and server cost, to name a few.

Now that we understand the need for on-device inference, there are a few significant roadblocks to consider. Firstly, the average size of deep learning models is hundreds of MB; for example, VGGNet is > 500 MB. One cannot deploy such a large model directly on the phone. Second is the inference time. Having a cloud-based model has the benefit that the inference can be done using a GPU, and hence, the inference time can be minimal. That is not the case when you have to run your model on a phone, which has much lower compute power. Finally, one also needs to consider energy efficiency — running your model shouldn’t drain out the battery of the phone completely.

There is an ongoing body of work in the AI research community (including both academia and industry) in the direction of Model Compression — which aims to tackle either all or some of the roadblocks discussed above. In this blog post, I’ll discuss some of the techniques which are commonly used to compress an AI model along with reducing the inference time, while trying to improve energy efficiency. As a guide along this journey, we’ll keep the following metrics in mind while discussing any new technique:

1. Model accuracy drop/rise (rise? yes!)
2. Model size
3. Inference time
4. Energy efficiency

Within model compression itself, there are two broad categories of techniques. One class of compression techniques focus on reducing the model size once the model has been trained. They are referred to as post-training techniques. Pruning and Quantisation are two techniques which belong to this class. The second category, on the other hand, trains a smaller model, to begin with, to match the accuracy of a larger model for the same task. MobileNets (v1 and v2) are an example of this category of techniques.

MobileNets

We will first discuss the category of techniques which design a smaller and efficient model, to begin with, and train it from scratch. The most widely known work in this class of compression techniques is referred to as MobileNets, which is essentially a toolkit of layers and tricks that make a deep learning model more efficient in terms of runtime while reducing the number of parameters as well. MobileNetv1 discussed the idea of Depthwise Separable Convolution (DS convolution), which is a parameter-efficient way to achieve the output that standard 2D convolution does. It also proposes two hyperparameters — width and resolution multiplier — that can be used to tradeoff between latency and accuracy. I’ll take a stab at explaining the difference between a DS convolution and a regular convolution.

A regular convolution operation takes place as shown below:

Here, the size of the input feature map is I x I x M , the kernel (also referred to as filter throughout the post) size is K x K and the desired output feature map is of size O x O x N . The figure highlights the computation of one cell of one of the channels of the output feature map. To compute one channel of the output feature map requires K x K x M x I x I multiplications and additions (referred to as MultAdds from now). For an N-channel output feature map, the total number of MultAdds is, therefore, K x K x M x I x I x N .

A standard convolution combines both the filtering step (via the kernel) and the combining of input features (as each filter has a shape of K x K x M as shown in the figure above). DS convolution factorises these two operations in two separate steps — depthwise convolution and pointwise convolution — to reduce the total number of parameters as well as the number of MultAdds.

The depthwise convolution step performs only the filtering operation and doesn’t combine the input features. The size of the filters and the depthwise convolution is visually shown below:

The Depthwise convolution step is extremely efficient compared to regular convolution as the number of MultAdds involved is only K x K x M x I x I .

The pointwise convolution step uses a 1x1 convolution to combine the output of the depthwise convolution to generate the feature map of the desired number of output channels. The number of MultAdds in a pointwise convolution is M x N x O x O . Thus, the total number of MultAdds in a Depthwise Separable convolution is: K x K x M x I x I + M x N x I x I (I’ve replaced O x O by I x I in the calculation of the number of MultAdds for pointwise convolution just so that the comparison with a regular convolution is easy and asymptotically, it won’t matter).

Thus, there is a reduction in the number of MultAdds by a factor of 1/K² (using K x K x M x I x I + M x N x I x I / K x K x M x I x I x N for the calculation and ignoring the 1/N term as N is usually large). Using a kernel size (K) of 3 gives a reduction by approximately 8–9 times.

The paper also introduced two hyperparameters for tweaking the network architecture to tradeoff between latency and accuracy:
i) Width multiplier (α): The paper refers to the number of channels in each feature map as the width of that feature map. α can be used to make each of the feature maps, and hence, the network, either thinner or thicker. For a DS convolution with the number of input channels M and output channels N, using a width multiplier, α, makes them `αM` and `αN` respectively. Thus, the number of MultAdds becomes: K x K x αM x I x I + αM x αN x I x I . Use α < 1 to reduce the width of the network.
ii) Resolution multiplier (ρ): This is used to reduce the resolution of each of the feature maps in the network. Together with α, the number of MultAdds becomes K x K x αM x ρI x ρI + αM x αN x ρI x ρI . This is effectively implemented by reducing the input size.

Pruning

Now, we shift over to the post-training class of techniques. The first among them is pruning. The broad idea is shown below. You start with the trained model and essentially “cut” or remove some connections such that they don’t have a major effect on the final accuracy. The resulting model is the pruned model which has fewer parameters.

There are a few design choices involved here. One important decision is the criteria based on which certain filters are removed while others are retained. Another crucial factor is the level at which pruning is done. To understand this, consider the figure below.

The figure shows two levels of pruning — one at the level of individual connections between neurons and other at the level of nodes, where individual nodes are removed (and thus, any connection to/from that node).

This design choice is especially relevant for Convolutional Neural Networks, where the connections are non-trivial and instead of removing individual weights within each of the filters, most techniques perform a filter-level pruning, i.e. they either reject or retain an entire filter (which has a shape of K x K x M , where the terms refer to their meanings as used in the section above). This is understood better using the image below:

Most pruning algorithms actually work in an iterative manner. This means that they prune a few weights, retrain the pruned model to recover from the drop in accuracy as a result of the pruning operation, prune again, and so on. This is done until a threshold on the accuracy drop is reached beyond which the model cannot be pruned further.

As shown above, it is possible to achieve almost no drop in accuracy by pruning almost 95% of the parameters. More details can be found in the original paper here.

Quantisation

All the weights don’t need to be stored in full-precision, and maybe, even, shouldn’t be stored in full precision. As a crude example, 1.98, 2.11, 2.03 can all be represented simply by 2. The reason why this could be even better than the original model is that it could provide some level of regularization. However, naive approximation might not be the best idea. This paper introduced the idea of trained quantisation, where you can not only perform quantisation in a better way but even train your quantised model further. Also, as shown in the image above, energy efficiency becomes almost thrice when using 16-bit float vs 32-bit float.

The broad idea of trained quantization is to cluster the weight values using K-means clustering where the number of clusters is decided based on the number of bits desired, create a codebook for each weight value, use the codebook to perform a forward pass and get the gradients and update the centroid values of each cluster using the gradient updates. This last step is explained in a bit more detail later.

So, we start with clustering the trained weights and replacing their values with the value of the centroid of the cluster they belong to.

Then, a forward pass is made using the centroid-replaced weight values, and the gradients are calculated accordingly (since each cell goes through a different forward pass, the cells belonging to the same cluster may end up having different gradient values). Since we know which cell indices belong to the same cluster, we group the gradient values based on the cluster the cell indices belong to, and sum over the gradients to receive the gradient value for a cluster. Finally, we perform the usual gradient descent update step on the older centroid values using the gradient value obtained above.

Now, one needs to store only the cluster indices and centroid values. Suppose that 16 clusters are chosen, the weight matrix can be represented using only 4-bits, which is an 8X reduction in model size (asymptotically). Combining this with Huffman coding to represent the bits efficiently, the final model size can be reduced dramatically with only a small drop in accuracy. The combination of Pruning + Quantization + Huffman coding was proposed in the Deep Compression paper which has been referenced throughout this post.

Resources:

• CS 231N Guest Lecture: Efficient Methods and Hardware for Deep Learning (slides) (video)
• Awesome model compression (Github)
• Official PyTorch implementation for MobileNetv2
• PyTorch implementation of MobileNetv1 compatible for Object Detection
• PyTorch implementation of Pruning (Github)
• PyTorch implementation of Deep Compression (Github)

This post was a very gentle introduction to the world of model compression. There is a ton of work out there that has not been covered, and this is an active area of research in the AI community — with a major push from industry. I intend to write another blog post covering a few more techniques, especially Intrinsic Dimension (from Uber Research) and MobileNetv2 in their gory details. I hope this was a fun read for you and served as a starting point for you to now understand the concepts discussed above in more details as well as become comfortable with the terminologies generally used in this field.

When I was in college, I wanted to be involved in things that would change the world. Now I am.
- Elon Musk

If there’s anything that you might want to share with me or give me any feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on LinkedIn, or follow me on Github. To stay updated with my posts, do follow me on Medium. You can follow our publication on Medium here.

Don’t forget to give us your 👏 and follow us!

Compression in the AI world: MobileNets, Pruning & Quantisation was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

This post explains the working of the Single-Shot MultiBox Detector along with a code walkthrough

Object detection refers to the task of identifying various objects within an image and drawing a bounding box around each of them. A few examples are shown below to illustrate this better:

A lot of research has happened in this domain and the most commonly heard object detection algorithm is You Only Look Once (YOLO), which was the first effort towards obtaining a real-time detector and ever since it was introduced, it has undergone several updates. A major problem with the first version of YOLO was that its accuracy was very low compared to the state-of-the-art detectors of that time, all of whom operated in two stages: the first stage generated a list of proposals or guesses for where the objects could be within the image and the second stage classified each of the proposed boxes. For more details on how two-stage detectors work, follow this blog post. YOLO belongs to the category of one-stage detectors which remove the proposal generation step and predict the class scores along with the bounding box coordinates directly from the image in an end-to-end framework. Single-Shot Multibox Detector (SSD) was the first one-stage detector to achieve an accuracy reasonably close to the two-stage detectors while still retaining the ability to work in real-time. There have been a lot of efforts towards making one-stage detectors surpass the accuracy of two-stage detectors by tackling several issues with SSD and adding an additional stage of refinement in the one-stage pipeline, but most of them use SSD as the starting point. In his post, I’ll explain each and every component of SSD in detail. Throughout the post, I’ll refer to this excellent implementation of SSD in PyTorch to map the concepts with the corresponding code samples.

1. Understanding Default Boxes

The key idea underlying SSD is the concept of default boxes (or anchors). Don’t worry if you have a lot of questions by the end of this section. This section is just meant to give you a high-level picture and a flavour for the things to come.

Default boxes represent carefully selected bounding boxes based on their sizes, aspect ratios and positions across the image. SSD contains 8732 default boxes. The goal of the model is to decide which of the default boxes to use for a given image and then predict offsets from the chosen default boxes to obtain the final prediction. If this sounded like a lot of jargon, stay with me. The following example and the subsequent sections should clear this further. But you need to keep coming back to this point and make sure you are very clear about it. The image below contains objects of two different scales and aspect ratios. We know that as we keep adding convolutional layers, the resolution of the feature map keeps reducing and hence, the receptive field of each cell of the feature map keeps increasing. Thus, earlier layers, having a smaller receptive field are better suited to detect smaller objects whereas later layers, having larger receptive field, can detect larger objects better.

In the image above, the green (positive) boxes are the default boxes that match at least one ground truth (cat, in case of the left one, and dog, in the right one) whereas the black (negative) default boxes are those that didn’t get matched to any ground truth. Matching here means assigning a label to a default box, positive or negative. I’ll talk about this in more detail later, but the essence here is that certain default boxes are matched to certain bounding boxes in the ground truth while the rest are considered negative. From a high-level, the network is trained to perform two tasks:

i) Classify which amongst its 8732 default boxes are positive;

ii) Predict offsets from the positive default box coordinates to obtain the final predicted bounding boxes.

2. Architecture

The architecture of SSD consists of 3 main components:

i) Base network

ii) Extra feature layers

iii) Prediction layers

The base network is essentially the initial layers of any standard image classification network, pre-trained on the ImageNet dataset. The authors use VGG-16. The fully connected layers at the end are implemented as convolutional layers. The final output of the base network is a feature map of size 19 x 19 x 1024.

On top of the base network, 4 additional convolutional layers are added such that the size of the feature maps keep reducing until a final feature map of size 1 x 1 x 256 is obtained.

The prediction layers are a crucial component of SSD. Instead of just using one feature map for predicting the classification scores and bounding box coordinates, several feature maps, representing multiple scales are used. This is where the idea of default boxes and feature map resolutions, discussed above, is used. Specifically, the layers conv4_3, conv7, conv8_2, conv9_2, conv10_2 and conv11_2(shown in the figure) are used for the bounding box predictions.

As shown in the image earlier, there are default boxes associated with each cell of a feature map and the number of such boxes — either 4 or 6 — is decided beforehand. Considering the number of classes (including the background class as class 0) to be C, each prediction is represented by (C + 4) numbers: C classification scores and 4 offsets: ∆cx, ∆cy, w and h, representing the offsets from the center of the default box and its dimensions. Thus, for a feature map with k default boxes per cell, the prediction layer is a 3 x 3 convolutional layer with k * (C + 4) channels.

3. Forward pass

In this section, I’ll describe how the complete forward pass looks like. Before we move to the code, one important detail to specify is that it has been shown that the feature map corresponding to conv4_3 layer of VGG has a very different scale compared to the later layers.

So, the features from that specific layer are normalized and set to an initial scale value of 20. The actual scale is then learned during back-propagation via the weight parameter. The code for the L2Norm layer is shown below:

Finally, the forward pass through the network is shown below. sources contains the various feature maps that contribute to the final prediction.

4. Choosing default boxes

As SSD relies heavily on default boxes, it is very sensitive to the choice of the default boxes, specifically their scale and aspect ratios. In the paper, the authors design the default boxes such that each feature map corresponds to a specific scale of default boxes along with a list of aspect ratios for each scale. The minimum and maximum scales, s_min and s_max, are set to 0.2 and 0.9. For the kth feature map (among m feature maps), the scale is chosen as:

For a feature map corresponding to a specific scale and having 6 default boxes associated with it, the heights and widths of the default boxes are obtained as shown below:

For each feature map, an additional default box of scale s* and aspect ratio 1 is added. Feature maps having only 4 default boxes do not use aspect ratios 3 and 1/3. The center of each default box is set as the center of the cell to which it belongs. The default boxes are defined in code as shown below:

5. Training

The loss function used is the MultiBox loss, which consists of two terms: the confidence loss and the localization loss. The network outputs (C + 4) predictions for each of the 8732 boxes: C class scores and 4 localization offsets.

Anchor Matching: To train the network, all the default boxes are matched to the ground truth boxes. First, each ground truth box is matched to the default box having the maximum jaccard overlap. This is done to make sure that each ground truth box has at least one corresponding default box. Then, each default box is matched to any ground truth box having a jaccard overlap > 0.5. This essentially turns the problem into a multi-label problem for each box. The implementation below matches each default box to only the best matching ground truth, but it can be easily modified to incorporate the multi-label criteria.

Loss function: The default boxes that didn’t get matched to any ground truth box are considered negative and contribute only to the confidence loss, whereas all the positively matched boxes add to the confidence loss as well as the localization loss. The confidence loss is essentially the cross-entropy loss while the localization loss is the Smooth L1 loss between the actual offsets of the default boxes to the ground truth boxes and the predicted offsets.

The final loss is given by a combination of both the losses where α is the relative weighing of the localization loss w.r.t the confidence loss (set to 1 by cross validation) and N is the number of positively matched boxes.

Hard Negative Mining: Most of the boxes, out of the 8732 default boxes, are negative. Using all the negative boxes directly would lead to a severe class imbalance during training and hence, once the matching is done, only those negative boxes having the highest confidence losses are retained such that the ratio between the positive and negative boxes is at least 1:3.

Data augmentation: Not using data augmentation leads to a major drop in performance. The important data augmentation strategies used are:

6. Inference

During inference, we now have 8732 boxes for each class (because we output C confidence scores for each box). Most of these boxes are negative and among the positive ones, there would be a lot of overlapping boxes, as shown below:

Upon receiving an image as input, first, default boxes are generated for all classes together (top right). Then, a confidence threshold of 0.01 is applied per class to obtain positive boxes (bottom right). Finally, Non-Maximal Suppression (NMS) is applied to get rid of overlapping boxes per class and return at most 200 boxes, using an Jaccard Index as the measure of overlap and an overlap threshold of 0.45. The need of NMS and how it’s done can be understood from this video. NMS essentially does the following (per class): sort the boxes based on the confidence scores, pick the box with the largest confidence score, remove all the other predicted boxes with Jaccard overlap > the NMS threshold (0.45 here), repeat the process until all boxes are covered.

7. Discussion

Some general points to keep in mind regarding SSD are:

• Data augmentation is very critical to better performance, especially for small objects.
• The network is very sensitive to default boxes and it is important to choose the default boxes based on the dataset that it is being used on. A good strategy is to use K-means clustering to identify the right default box sizes.
• Using stronger image classification networks as the base network - like Resnet, Inception, Xception - is likely to improve performance.
• SSD does not work well with small objects. One potential reason for this, discussed in this paper, is that the earlier layers which have smaller receptive field and are responsible for small object detection, are too shallow. There is also a structural contradiction where the earlier layers are supposed to learn low-level features to be passed on to the higher layers whereas also learn high-level abstraction for correctly identifying boxes. This paper adds more context to the predictions and shows significantly higher performance on small objects. Using higher resolution images is also likely to improve performance on small objects.
• 80% of the forward pass time is spent in the base network. Significant improvement in inference time can be obtained by using MobileNet instead of VGG.
• Using multi-scale feature maps for prediction is imperative to SSD’s performance. Adding more default boxes can improve accuracy at the cost of lower speed.

8. Resources

• Original SSD paper
• PyTorch codebase used throughout the post
• Original Caffe code
• Other blog posts explaining SSD: 1, 2, 3

To summarize, SSD is the first one-stage detector to achieve an accuracy comparable to two-stage detectors while maintaining real-time efficiency. It uses the idea of default boxes and multi-scale predictions to directly regress on the bounding box coordinates, without the need of a proposal generation step. There are a few shortcomings of SSD as well, like it doesn’t work well with small objects, and a lot of ideas have been proposed to tackle its various issues. We’ll discuss these ideas in the next post.

I, personally, found this to be a very fascinating read and as I went into the implementation details, I only got more interested. This is a perfect example of the importance of small details and I definitely learned a lot while working on it. For someone looking to get their hands dirty with object detection, SSD is one of the best places to start. Also, if you found the post useful, make sure to give it a clap and share with other people who might benefit from it.

If you want to stay notified about my future posts, do follow me on Medium. If there’s anything that you might want to share with me or give any sort of feedback on my writing/thoughts, I would love to hear it as well. Feel free to connect with me on LinkedIn, or follow me on Github.

Real-time object detection part 1: Understanding SSD was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is a series of blog posts on the Deep Learning book where we are attempting to provide a summary of each chapter highlighting the concepts that we found to be the most important so that other people can use it as a starting point for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer this for more clarity on notation.

We are excited to say that this is going to be the last chapter that we cover before entering the Deep Learning Research section of the book which is, for the most part, unfamiliar terrains for us. A lot of what we’d been talking about till now covered the theoretical aspects of Deep Learning. However, there’s a large gap between theory and what works in practice. This chapter is specifically dedicated to practitioners and people who are looking to apply Deep Learning for building cool applications and solving real-world problems.

A good machine learning practitioner needs to know how to choose an algorithm for a particular application and how to monitor and respond to feedback obtained from experiments in order to improve a machine learning system.

The various choices that one might need to make include which type of data to gather, where would they find that data, should they gather more data, change model complexities, change (add/remove) regularization, improve optimization, debug the software implementation, etc. The recommended practical design process is as follows:

• Decide on a a single number metric to evaluate your model. This represents the final goal and you need to set a specific target that you want to achieve. Coming from Andrew Ng’s Machine Learning Yearning and also from personal experience, most teams forget to decide upon this only to realize the mistake very late in the process that setting this up would have gave them a clear guide on what they wanted to improve.
• Get an end-to-end pipeline working as soon as possible, including the evaluation of the required metrics. This will, more often than not, require that you use a very simple model that can accept the inputs correctly and produce the outputs in the right format that can be further used for training / evaluation / analysis. The major benefit here is that now you can solely focus on improving the model and on doing any specific change, you can instantly get the final results and check whether that change improved the model or not.

• Instrument the system well to determine bottlenecks in performance which requires diagnosing which components perform worse than expected and understanding the reason behind poor performance — overfitting, underfitting, modelling, problems in data, software implementation errors, etc.
• Based on the diagnosis above, keep improving the algorithm iteratively either by adding more data, increasing the capacity of the model, tuning hyperparameters or improving the quality of data by better annotation, etc.

The chapter is divided into the following sections:

• Performance Metrics
• Default Baseline Models
• Determining Whether to Gather More Data
• Selecting Hyperparameters
• Debugging Strategies

1. Performance Metrics

As mentioned above, it’s extremely important to decide on which error metric to use as that will ultimately guide you on how to make progress. It should be sufficiently representative of the end goal that you are trying to achieve. Let me give you an example. Suppose you are working on a Semantic Segmentation problem where we want to assign a class to each pixel of the input image. The image below demonstrates how the output should look like given an input image:

To simplify, let’s consider a binary segmentation task where class 1 represents “man” and class 0 represents the background class. Thus, the expected output now becomes:

Now, what would be a reasonable metric to choose here that would be representative of the final goal here? — Think before looking down.

A default metric to start off with is accuracy, which indicates the percentage of pixels where our model predicted the right class. Although the example above has a fairly equal number of class 1 and class 0 pixels, this need not be the case. There can be images where there is a single person in the image or there can be a lot of images with no people. In such cases where there is a high class imbalance, a very simple way to achieve a high accuracy could be to always predict the class 0. However, it’s clearly not a good classifier although it might get 90% accuracy. You’d ideally like a metric that is not dependent on the distribution of the classes in the dataset. For this reason, the most commonly used metric for semantic segmentation is Intersection over Union (IoU), which is defined as follows:

The image below shows why IoU is a good metric:

One more thing that I’d like to point out before moving on from this example is that it is equally useful in images where there is no object, i.e. the entire image represents the background class. This is achieved by adding a small ϵ to both the numerator and denominator during the calculation of IoU. Now, if the ground truth contained only background class and our model predicted that as well, the intersection as well as the union is 0. Thus, the IoU becomes (0 + ϵ) / (0 + ϵ) = ϵ / ϵ = 1. This indicates the importance of choosing the right metric.

Then there can be problems where one type of mistake is more costly than another. In the case of spam detection, classifying a spam mail as non-spam is much less costlier than classifying a non-spam message as spam. In such cases, instead of measuring the error rate, we might be interested in observing some form of total cost which is representative of our problem.

Similar to the semantic segmentation problem described above, there are many cases where there is a large class imbalance. For example, in a particular sample of population, one out of a 1000 people might have cancer. Thus, 9999 people don’t have cancer. If I simply use a classifier that classifier everyone as not having cancer, I can achieve an accuracy of 99.99%. But would you be willing to use this classifier for testing yourself?
Definitely not. In such a case, accuracy is a bad metric. We instead use precision and recall to evaluate our classifier. I generally use this figure to remember what both of them mean:

Precision represents the fraction of detections that were actually true, whereas Recall stands for the the fraction of true events that were successfully detected.

Now, consider that if a detector says that all the cases are not cancer will achieve the perfect precision, but 0 recall. Many a times, it’s actually desirable to have a single metric to judge on, rather than have a trade-off between two of them. F1-score, which is the Harmonic Mean of Precision & Recall is a widely accepted metric:

However, F1-score gives equal weightage to both precision and recall. There can be cases where you want to weigh one over the other and hence, we have the more general, F-beta score:

Also, in some cases the machine learning algorithm can refuse to make any decision at all in cases where it’s not very confident about it’s decision. This can be important in situations where a misclassification can be harmful and it’d be much better for a human to have a look. Then again, a ML system is useful only when it significantly reduces the number of instances that a human operator must process. A natural performance metric here is coverage, which stands for the fraction of images that where the machine learning system is able to produce a response.

In most applications, it might not be possible to achieve absolute zero error even after having infinite data either due to the features not being sufficiently representative or the system being intrinsically stochastic. The minimum amount of error possible for a system is called the Bayes’ error for the system.

A major bottleneck to performance is often the fact that training data is limited. Now, once away from standard datasets like MNIST into more real-world problems, you’ll realize that getting accurate data is much more harder than it initially seems and in most often, doesn’t come for free as well. So, you really need to analyze how much is additional data going to improve your performance metric. I’ll try to explain this with an example. As mentioned in Andrew’s book, Machine Learning Yearning, a standard method of error analysis to actually observe (say) 100 examples where your model is failing and then checking which classes actually account for the maximum % of error:

From the figure above, it can be clearly seen that collecting more Dog images might improve the error rate by 8% at max. However, collecting more Blurry images might potentially improve the error rate by 61%, which is very significant. Thus, it makes sense to spend time on collecting more blurry images and doing this exercise would save you the embarrassment of spending months on collecting better Dog images only to see the error rate improve by 8%. For more such tips, refer to the book linked above.

The bottom line being that you need to decide what is realistic desired error rate for your intended application beforehand and use that to guide your design decisions in the future.

2. Default Baseline Models

As mentioned at the start, it is very important to establish a working end-to-end system as soon as possible. Depending on the complexity of the problem, we might even choose to begin with a very simplistic model like logistic regression. However, if the problem that you intend to solve falls under the “AI-complete” category like Image Classification, Speech Recognition, etc., starting off with a deep learning model would almost always be better.

You first begin with choosing the general category of model to use based on the structure of your data. If your data consists of fixed-size vectors and you intend to perform a supervised learning task, use a multi-layer perceptron. If your data has a fixed topological structure, using a Convolutional Neural Network might be the best way forward. Similarly, if your data has a sequential pattern, Recurrent Neural Networks would be the ideal starting point. However, the speed at which Deep Learning as a field is progressing, default algorithms are likely to change. For example, 3–4 years ago AlexNet would have been the ideal starting point for image-based tasks. However, now ResNets are the widely accepted default choice.

For training the model, a reasonable starting point is to use the Adam optimizer. Apart from this, SGD with momentum and a learning rate decay is widely used too where the learning rate is decayed exponentially until a point and then, reduced linearly by a factor of 2–10 each time validation error plateaus. Batch-Normalization would, in general, always improve performance by providing stability and allowing the use of larger learning rate thereby helping to reach convergence faster.

As you increase your model complexity, you’ll eventually become prone to overfitting since your training data is limited. Thus, it’s always advised to add some regularization to your model as well. Common choices include L2-penalty to the loss function, Dropout between layers, Early stopping and Batch-Normalization. Using Batch-Normalization allows the omission of Dropout. If you missed our post on regularization, feel free to go through it where all of these have been explained in detail.

If your task is reasonably similar to any other task where prior work has been done, it is advised to just copy the model (along with the weights) from the latter and use that as an initialization point for your task. This way of training is called transfer learning. For example, in the famous Dogs Vs Cats Image Classification challenge on Kaggle, a model pretrained on ImageNet which contained similar images, was used as the starting point to achieve the best performance, rather than training the model from scratch.

Finally, some domains like Natural Language Processing (NLP) benefit tremendously from using unsupervised learning methods during initialization. In the current trend of Deep Learning applied to NLP, it’s common to represent each word as an embedding (vector) and there exist unsupervised learning methods like word2vec and GLoVe for learning these word embeddings.

3. Determining Whether to Gather More Data

Numbers have an important story to tell. They rely on you to give them a clear and convincing voice.

— Stephen Few

A rookie mistake that a lot of people make is that they keep trying different algorithms to improve the performance of their models, whereas simply improving the data they have or gathering more data can be the best source of improvement. We touched upon the topic of how to decide when to get more data, but since data is the most integral part of getting an AI solution working, we’ll explore this in a bit more detail now.

So, how do you decide when to get more data? Firstly, if the performance of your model on your training set is poor, it is not making full use of the information present in your data and in this case, you need to increase the complexity of your model by adding more layers or increasing the number of hidden units in each layer. Also, hyperparameter tuning is an important step to perform. You’d be surprised how large an effect choosing the right hyperparameters can have in getting your model working. For example, learning rate is THE most important hyperparameter that you need to tune. Setting the right value of the learning rate for your problem can save you loads of hours of wasted effort. However, if your model is reasonably complex and optimization carefully tuned but still the performance is not up to the desired level, the problem might be the quality of data instead, in which you have to go back to square one and start collecting cleaner data.

If the training error is low but the validation error is much higher, then you can safely assume that your best would be to say:

The specific situation mentioned above, where training error is low but test error is high, is called overfitting and is one of the most commonly occurring problems in training deep models, in which case regularization might help. To reinforce the importance of data in the modern deep networks, for those who might not be aware, the reason that Deep Learning started gaining attention was the ImageNet competition where a deep learning model outperformed the previous best model by a significantly large margin in 2012. ImageNet consists of millions of annotated images and the creation of similar large labelled datasets is the reason that extremely complex problems like object detection have become solved problems today.

Finally, it’s generally observed that adding a small fraction of the total number of examples won’t have a noticeable effect on the performance. Thus, we need to monitor how much the performance of a model improves as the dataset size increases and it should be monitored at a logarithmic scale.

As can been seen from the plot above, the training error will generally increase as you increase the dataset size. This is because the model will find it harder to fit to all the datapoints exactly now. Also, by increasing the dataset size, your validation (dev) error will decrease as the model would learn to be more generalized now.

4. Selecting Hyperparameters

Most deep learning algorithms have a lot of hyperparameters that need to be chosen correctly. Different hyperparameters control different aspects of the model. Some affect the memory cost like the number of layers to use while others affect the performance like the keep probability for Dropout, learning rate, momentum, etc. Broadly, there are two approaches to choosing these hyperparameters. The first one is to choose them manually which involves understanding what the hyperparameters do and how they affect training and generalization. The other approach is to choose the hyperparameters automatically, which reduces the complexity a lot but comes at the cost of compute power. We’ll discuss these two approaches in more details now:

i) Manual Hyperparameter Tuning:

As briefly mentioned above, manual hyperparameter tuning requires a lot of domain knowledge and fundamental understanding of training error, generalization error, learning theory, etc. The primary aim of manual hyperparameter tuning is to achieve effective capacity to match the complexity of the task by trading off memory and runtime. Factors influencing the effective capacity are representational capacity of the model, ability of the learning algorithm to minimize the cost function used to train the model and the degree to which the cost function and the training procedure regularize the model.

The generalization error typically follows a U-shaped curve as shown below:

On the extreme left, we are in the underfitting regime where the capacity of the model is low and both training and generalization errors are high. On the extreme right, we enter the overfitting regime where the training error is low but the gap between the training error and test error is high. The optimal spot is somewhere in the middle where we trade-off a slightly higher training error for the lowest possible generalization error.

Many hyperparameters affect overfitting (or underfitting) and in different ways. For e.g. increasing certain hyperparameters like, the number of hidden units, increases the chances of overfitting, whereas increasing others like weight decay reduces. Some of them are discrete like the number of hidden units, whereas others might be binary like whether to use Batch Normalization or not. Some hyperparameters have bounds that implicitly restrict them, like the weight decay coefficient which can only reduce capacity. Thus, if the model is underfitting, you can’t get it to overfit by adding weight decay.

As mentioned before, if you can tune only one hyperparameter, tune the learning rate. The effective capacity of the model is the highest at the right learning rate, neither too high nor too low. We discuss in more details about the effect of learning rate on the training process in one of our earlier posts, but to summarize: setting the learning rate too low slows training and might even cause the algorithm to get stuck in local minima; setting it too high might make the training unstable due to wild oscillations.

If the training error is high, general approach is to add more layers or more hidden units to increase the capacity. If the training error is low but the test error is high, you need to reduce the gap between the train and test errors without increasing the training error too much. Usually, a sufficiently large model which is well-regularized (for e.g. by using Dropout, Batch Normalization, weight decay, etc.) works the best.

The two broad approaches to achieve the final goal of a low generalization are: adding regularization to the model and increasing the dataset size. The table below shows how each hyperparameter affects capacity:

ii) Automatic Hyperparameter Optimization Algorithms: Hyperparameter tuning can be viewed as an optimization process itself which optimizes an objective function, such as the validates, sometimes under constraints like training time, memory limits, etc. Thus, we can design Hyperparameter Optimization (HO) algorithms that wrap a learning algorithm and choose its hyperparameters. Unfortunately, these HO algorithms have their own set of hyperparameters, but these are generally easier to choose as would be discussed now:
Grid Search: For grid search, first pick a range of values that you feel is suitable for each hyperparameter. Then, you train the model for each possible combination of the values of the hyperparameters. To simplify, if you have 2 hyperparameters and pick a range of N values for each of them, you’ll need to train the model for all the possible N² combinations. You generally set the maximum and minimum of the range based on your understanding (and/or experience) and then choose the values in between, generally, on a logarithmic scale. For e.g. possible values for learning rate: {0.1, 0.01, 0.001}, number of hidden units: {50, 100, 200, 400}, etc.

Also, Grid search works best when performed repeatedly. E.g. if the range that you set was {0.1, 0, 1} and the best performing one was 1, you probably set the range wrong and you should check again for a higher range like {1, 2, 3}. In case the best performing value comes out as 0, then you should do a more refined search between {-0.1, 0, 0.1}.

The main problem with Grid Search is the computational cost. If there are m hyperparameters to be tuned, and each of them can take N values, the number of training and evaluation trials grows as O(N^m).

Random Search: A better and faster approach is something known as random search. In this case, you define some distribution over the choice of values, e.g.binomial for binary, multinomial for discrete, uniform on a log-scale for say, learning rate:

Then, for each run, randomly sample the value of each hyperparameter based on its distribution. This can prove to be exponentially more efficient than grid search. The figure below explains this:

To make it clearer, the main reason that random search reduces validation error faster than grid search is that it doesn’t perform any wasted computation. Since grid search goes over all possible combinations, it’ll evaluate cases where the value of only one hyperparameter changes, with the values of the rest being the same. Now, if this hyperparameter doesn’t affect the performance too much, then grid search has performed a wasted evaluation. However, in the case of random search, for different values of a hyperparameter, the values of the rest of the hyperparameters would most likely also be different. Thus, random search doesn’t do any wasted evaluation.

Model-based Hyperparameter Optimization: As mentioned briefly above, hyperparameter tuning can be viewed as an optimization process. In simplified settings, it might be possible to take the gradient of some differentiable error measure on the validation set with respect to the hyperparameters and simply use Gradient Descent. However, in most practical settings, this gradient is not unavailable. To compensate for this, you can build a model of the validation error and perform optimization on this model. A general approach is to build a Bayesian regression model to estimate the expected value of the validation error along with the uncertainty around this estimate. Bayesian Hyperparameter Optimization (BHO) is still nascent and not sufficiently reliable. One major drawback compared to random search would be that BHO requires each experiment to go till completion to be able to extract any information out of it, whereas in many cases it might be clearly visible at the initial stages itself that that particular set of hyperparameters doesn’t work.

5. Debugging Strategies

Machine learning systems are invariably one of the most difficult ones to debug as it’s hard to figure out if the error was in training the model or in the software implementation. Another major bottleneck is that we ourselves are not sure what the intended behaviour of the algorithm is, since, the original goal of training machine learning algorithms is that they can discover useful behaviour from the data that we, as humans, might be unaware of. For example, if we are working on a new classification task (that no one has worked on before), it’s not sure that getting a 5% error is good or bad as we have nothing to compare it against.

There are various debugging strategies which are commonly used. I’m listing the ones that I commonly tend to use. Feel free to refer the book for a few more:
1) Visualize the model in action: This is one of the best ways to verify if the training is going correctly and also, understanding which areas might need improvement. Once the training starts, visualize the output of your model after a few epochs. If you’re working on a semantic segmentation problem, look at the segmentation output. If you’re training a generative model of speech, listen to a few sample of speech that it produces. Also, it’s common to have bugs in the evaluation metric as they might need corner-case handling which you might not have taken care of. Evaluation bugs are the hardest ones to catch and they fool you into believing that your model is performing/not performing well.

2) Visualize the worst mistakes: Going back to the semantic segmentation problem above, suppose we run the model on our test set. Based on the IoU scores, we can sort the samples to identify where our model performed the worst. Visualizing those examples where the model fails terribly, is a great way to identify errors in data processing/annotation. In the case where you infer that the problem had been with the annotation of data, the best way to improve performance would be to actually correct the annotations, even manually if required, as the payoff of having the correct data is very high.

3) Fit a tiny dataset: Before starting to train on your entire training set, always fit your model to a small subset of the entire dataset. Even very simple models will overfit to a handful of examples. Taking the extreme case of a single example, it’s very easy to correctly fit to it by setting the weights to zero and the biases appropriately. From my practical experience too, if you’re making a modification or trying something different, first make sure that it can overfit on a small enough dataset. If it can’t, then there’s a high probability that there’s been a software bug in setting up the training process.

4) Monitor histograms of activations and gradients: It can be useful to monitor the pre-activation values of hidden units in case there is a problem in training. What to monitor depends on the type of activation function used. For example, in the case of ReLU (commonly used between layers), we can check how often is the unit off (which would happen if the pre-activation value is less than 0). In the case of sigmoidal units, it can be useful to check how often does it stay in the saturated regions, i.e. either too positive or too negative. Also, if the gradients grow or vanish too quickly, it can be a problem during training. It has advised in the book that the magnitude of the gradient should be approximately 1% of the magnitude of the parameter, neither too high (50%) nor too low (0.001%). Thus, comparing the two magnitudes can be a good approach for debugging too.

Finally, it can be shown (covered in later chapters) that some optimization algorithms provide certain guarantees, like the objective function not increasing after each epoch, all the gradients being zero at convergence, etc. and as a safekeeping step, we can ensure that these guarantees are met.

This concludes our summary and explanation for Chapter 11. The motivation behind this post was to give you an intuition about the various knobs of a deep learning model and give you practical tips on getting your model to perform well. I believe that if you judiciously follow what was taught here, training your model wouldn’t be the bottleneck for you anymore. DATA will always be ;)
To stay updated with our posts, follow our publication, Inveterate Learner. If you’re looking for the summary of previous chapters or are more comfortable reading from a Jupyter Notebook, feel free to have a look over our repository here.

If you get up in the morning and think the future is going to be better, it is a bright day. Otherwise, it’s not.

- Elon Musk

If there’s anything that you might want to share with me or give any sort of feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on LinkedIn, Facebook or follow me on Github.

But wait, how to ACTUALLY do the cool stuff? — Chapter 11 was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is going to be a series of blog posts on the Deep Learning book where we are attempting to provide a summary of each chapter highlighting the concepts that we found to be the most important so that other people can use it as a starting point for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer this for more clarity on notation.

This is a continuation of our previous post on the first three sections of Chapter 8. The main concepts that we discussed were How learning differs from pure optimization, Challenges in Neural Network Optimization and the Basic algorithms used in optimization. The remaining sections of the chapter deal with:

• Parameter Initialization Strategies
• Algorithms with Adaptive Learning Rates
• Approximate Second-Order Methods
• Optimization Strategies and Meta-Algorithms

1. Parameter Initialization Strategies

Training algorithms for deep learning models are iterative in nature and require the specification of an initial point. This is extremely crucial as it often decides whether or not the algorithm converges and if it does, then does the algorithm converge to a point with high cost or low cost.

We have limited understanding of neural network optimization but the one property that we know with complete certainty is that the initialization should break symmetry. This means that if two hidden units are connected to the same input units, then these should have different initialization or else the gradient would update both the units in the same way and we don’t learn anything new by using an additional unit. The idea of having each unit learn something different motivates random initialization of weights which is also computationally cheaper.

Biases are often chosen heuristically (zero mostly) and only the weights are randomly initialized, almost always from a Gaussian or uniform distribution. The scale of the distribution is of utmost concern. Large weights might have better symmetry-breaking effect but might lead to chaos (extreme sensitivity to small perturbations in the input) and exploding values during forward & back propagation. As an example of how large weights might lead to chaos, consider that there’s a slight noise adding ϵ to the input. Now, we if did just a simple linear transformation like W * x, the ϵ noise would add a factor of W * ϵ to the output. In case the weights are high, this ends up making a significant contribution to the output. SGD and its variants tend to halt in areas near the initial values, thereby expressing a prior that the path to the final parameters from the initial values is discoverable by steepest descent algorithms. A more mathematical explanation for the symmetry breaking can be found in the Appendix.

Various suggestions have been made for appropriate initialization of the parameters. The most commonly used ones include sampling the weights of each fully-connected layer having m inputs and n outputs uniformly from the following distributions:

• U(-1 / √m, 1 / √m)
• U(- √6 / (m+n), √6 / (m+n))

These initializations have already been incorporated into the most commonly used Deep Learning frameworks nowadays so that you can just specify which initializer to use and the framework takes care of sampling appropriately. For e.g. Keras, which is a very famous deep learning framework, has a module called initializers, where the second distribution (among the 2 mentioned above) is implemented as glorot_uniform .

One drawback of using 1 / √m as the standard deviation is that the weights end up being small when a layer has too many input/output units. Motivated by the idea to have the total amount of input to each unit independent of the number of input units m, Sparse initialization sets each unit to have exactly k non-zero weights. However, it takes a long time for GD to correct incorrect large values and hence, this initialization might cause problems.

If the weights are too small, the range of activations across the mini-batch will shrink as the activations propagate forward through the network.By repeatedly identifying the first layer with unacceptably small activations and increasing its weights, it is possible to eventually obtain a network with reasonable initial activations throughout.

The biases are relatively easier to choose. Setting the biases to zero is compatible with most weight initialization schemes except for a few cases for e.g. when used for an output unit, to prevent saturation at initialization or when using unit as a gate for making a decision. Refer to the chapter for details.

2. Algorithms with Adaptive Learning Rates

• AdaGrad: As mentioned in Part I , it is important to incrementally decrease the learning rate for faster convergence. Instead of manually reducing the learning rate after each (or several) epochs, a better approach is to adapt the learning rate as the training progresses. This can be done by scaling the learning rates of each model parameter individually inversely proportional to the square root of the sum of historical squared values of the gradient. In the parameter update equation below, r is initialized with 0 and the multiplication in the update step happens element-wise as mentioned. Since the gradient value would be different for each parameter, the learning rate is scaled differently for each parameter too. Thus, those parameters having a large gradient have a large decrease in the learning rate as the learning rate might be too high leading to oscillations or it might be approaching the minima but having large learning rate might cause it to jump over the minima as explained in the figure below, because of which the learning rate should be decreased for better convergence, while those with small gradients have a small decrease in the learning rate as they might have already approached their respective minima and should not be pushed away from that. Even if they have not, reducing the learning rate too much would reduce the gradient even further leading to slower learning.

However, accumulation of squared gradients from the very beginning can lead to excessive and premature decrease in the learning rate. Consider that we had a model with only 2 parameters (for simplicity) and both the initial gradients are 1000. After some iterations, the gradient of one of the

parameters has reduced to 100 but that of the other parameter is still around 750. However, because of the accumulation at each update, the accumulated gradient would still have almost the same value. For e.g. let the accumulated gradients at each step for the Parameter 1 be 1000 + 900 + 700 + 400 + 100 = 3100, 1/3100=0.0003 and that for Parameter 2 be: 1000 + 900 + 850 + 800 + 750 = 4300, 1/4300 = 0.0002. This would lead to a similar decrease in the learning rates for both the parameters, even though the parameter having the lower gradient might have its learning rate reduced too much leading to slower learning.

• RMSProp: RMSProp addresses the problem caused by accumulated gradients in AdaGrad. It modifies the gradient accumulation step to an exponentially weighted moving average in order to discard history from the extreme past. The RMSProp update is given by:

This allows the algorithm to converge rapidly after finding a convex bowl, as if it were an instance of AdaGrad initialized within that bowl. Let me explain why this is so. Consider the figure below. The region represented by 1 indicates usual RMSProp parameter updates as given by the update equation, which is nothing but exponentially averaged AdaGrad updates. Once the optimization process lands on A, it essentially lands at the top of a convex bowl. At this point, intuitively, all the updates before A can be seen to be forgotten due to the exponential averaging and it can be seen as if (exponentially averaged) AdaGrad updates start from point A onwards.

• Adam: Adapted from “adaptive moments”, it focuses on combining RMSProp and Momentum. Firstly, it views Momentum as an estimate of the first-order moment and RMSProp as that of the second moment. The weight update for Adam is given by:

Secondly, since s and r are initialized as zeros, the authors observed a bias during the initial steps of training thereby adding a correction term for both the moments to account for their initialization near the origin. As an example of what the effect of this bias correction is, we’ll look at the values of s and r for a single parameter (in which case everything is now represented as a scalar). Let’s first understand what would happen if there was no bias correction. Since s (notice that this is not in bold as we are looking at the value for a single parameter and the s here is a scalar) is initialized as zero, after the first iteration, the value of s would be (1 — ρ1) * g and that of r would be (1 — ρ2) * g². The preferred values for ρ1 and ρ2 are 0.9 and 0.99 respectively. Thus, the initial values of s and r are pretty small and this gets compounded as the training progress. However, if we now use bias correction, after the first iteration, the value of s is just g and that of r is just g². This gets rid of the bias that occurs in the initial phase of training. A major advantage of Adam is that it’s fairly robust to the choice of these hyperparameters, i.e. ρ1 and ρ2.

The figure below shows the comparison between the various optimization methods discussed above. It can be clearly seen that algorithms with adaptive learning rates provide faster convergence:

3. Approximate Second-Order Methods

The optimization algorithms that we’ve looked at till now involved computing only the first derivative. But there are many methods which involve higher order derivatives as well. The main problem with these algorithms are that they are not practically feasible in their vanilla form and so, certain methods are used to approximate the values of the derivatives. We explain three such methods, all of which use empirical risk as the objective function:

• Newton’s Method: This is the most common higher-order derivative method used. It makes use of the curvature of the loss function via its second-order derivative to arrive at the optimal point. Using the second-order Taylor Series expansion to approximate J(θ) around a point θo and ignoring derivatives of order greater than 2 (this has already been discussed in previous chapters), we get:

We know that we get a critical point for any function f(x) by solving for f'(x) = 0. We get the following critical point of the above equation (refer to the Appendix for proof):

For quadratic surfaces (i.e. where cost function is quadratic), this directly gives the optimal result in one step whereas gradient descent would still need to iterate. However, for surfaces that are not quadratic, as long as the Hessian remains positive definite, we can obtain the optimal point through a 2-step iterative process — 1) Get the inverse of the Hessian and 2) update the parameters.

Saddle points are problematic for Newton’s method. If all the eigenvalues are not positive, Newton’s method might cause the updates to move in the wrong direction. A way to avoid this is to add regularization:

However, if there is a strong negative curvature i.e. the eigenvalues are largely negative, α needs to be sufficiently high to offset the negative eigenvalues in which case the Hessian becomes dominated by the diagonal matrix. This leads to an update which becomes the standard gradient divided by α:

Another problem restricting the use of Newton’s method is the computational cost. It takes O(k³) time to calculate the inverse of the Hessian where k is the number of parameters. It’s not uncommon for Deep Neural Networks to have about a million parameters and since the parameters are updated every iteration, this inverse needs to be calculated at every iteration, which is not computationally feasible.

• Conjugate Gradients: One weakness of the method of steepest descent (i.e. GD) is that line searches happen along the direction of the gradient. Suppose the previous search direction is d(t-1). Once the search terminates (which it does when the gradient along the current gradient direction vanishes) at the minimum, the next search direction, d(t) is given by the gradient at that point, which is orthogonal to d(t-1) (because if it’s not orthogonal, it’ll have some component along d(t-1) which cannot be true as at the minimum, the gradient along d(t-1) has vanished).
  Upon getting the minimum along the current search direction, the minimum along the previous search direction is not preserved, undoing, in a sense, the progress made in previous search direction.

In the method of conjugate gradients, we seek a search direction that is conjugate to the previous line search direction:

with d(t) and d(t-1) being conjugates if d(t)' H d(t-1) = 0. βt decides how much of d(t-1) is added back to the current search direction. There are two popular choices for βt — Fletcher-Reeves and Polak-Ribière. These discussions assumed the cost function to be quadratic where the conjugate directions ensure that the gradient along the previous direction does not increase in magnitude. To extend the concept to work for training neural networks, there is one additional change. Since it’s no longer quadratic, there’s no guarantee anymore than the conjugate direction would preserve the minimum in the previous search directions. Thus, the algorithm includes occasional resets where the method of conjugate gradients is restarted with line search along the unaltered gradient.

• BFGS: This algorithm tries to bring the advantages of Newton’s method without the additional computational burden by approximating the inverse of H by M(t), which is iteratively refined using low-rank updates. Finally, line search is conducted along the direction M(t)g(t). However, BFGS requires storing the matrix M(t) which takes O(n²) memory making it infeasible. An approach called Limited Memory BFGS (L-BFGS) has been proposed to tackle this infeasibility by computing the matrix M(t) using the same method as BFGS but assuming that M(t−1) is the identity matrix.

4. Optimization Strategies and Meta-Algorithms

• Batch Normalization: Batch normalization (BN) is one of the most exciting innovations in Deep learning that has significantly stabilized the learning process and allowed faster convergence rates. The intuition behind batch normalization is as follows: Most of the Deep Learning networks are compositions of many layers (or functions) and the gradient with respect to one layer is taken considering the other layers to be constant. However, in practise all the layers are updated simultaneously and this can lead to unexpected results. For example, let y* = x W¹ W² … W¹⁰. Here, y* is a linear function of x but not a linear function of the weights. Suppose the gradient is given by g and we now intend to reduce y* by 0.1. Using first-order Taylor Series approximation, taking a step of ϵg would reduce y* by ϵg’ g. Thus, ϵ should be 0.1/(g’ g) just using the first-order information. However, higher order effects also creep in as the updated y* is given by:

An example of a second-order term would be ϵ² g1 g2 ∏ wi. ∏ wi can be negligibly small or exponentially high depending on whether the individual weights are less than or greater than 1. Since the updates to one layer is so strongly dependent on the other layers, choosing an appropriate learning rate is tough. Batch normalization takes care of this problem by using an efficient reparameterization of almost any deep network. Given a matrix of activations, H, the normalization is given by: H’ = (H-μ) / σ, where the subtraction and division is broadcasted.

Going back to the earlier example of y*, let the activations of layer l be given by h(l-1). Then h(l-1) = x W1 W2 … W (l-1). Now, if x is drawn from a unit Gaussian, then h(l-1) also comes from a Gaussian, however, not of zero mean and unit variance, as it is a linear transformation of x. BN makes it zero mean and unit variance. Therefore, y* = Wl h(l-1) and thus, the learning now becomes much simpler as the parameters at the lower layers mostly do not have any effect. This simplicity was definitely achieved by rendering the lower layers useless. However, in a realistic deep network with non-linearities, the lower layers remain useful. Finally, the complete reparameterization of BN is given by replacing H with γH’ + β. This is done to retain its expressive power and the fact that the mean is solely determined by XW. Also, among the choice of normalizating X or XW + B, the authors recommend the latter, specifically XW, since B becomes redundant because of β. Practically, this means that when we are using the Batch Normalization layer, the biases should be turned off. In a deep learning framework like Keras, this can be done by setting the parameter use_bias=False in the Convolutional layer.

• Coordinate Descent: Generally, a single weight update is made by taking the gradient with respect to every parameter. However, in cases where some of the parameters might be independent (discussed below) of the remaining, it might be more efficient to take the gradient with respect to those independent sets of parameters separately for making updates. Let me clarify that with an example. Suppose we have the following cost function:

This cost function describes the learning problem called sparse coding. Here, H refers to the sparse representation of X and W is the set of weights used to linearly decode H to retrieve X. An explanation of why this cost function enforces the learning of a sparse representation of X follows. The first term of the cost function penalizes values far from 0 (positive or negative because of the modulus, |H|, operator. This enforces most of the values to be 0, thereby sparse. The second term is pretty self-explanatory in that it compensates the difference between X and H being linearly transformed by W, thereby enforcing them to take the same value. In this way, H is now learned as a sparse “representation” of X. The cost function generally consists of additionally a regularization term like weight decay, which has been avoided for simplicity. Here, we can divide the entire list of parameters into two sets, W and H. Minimizing the cost function with respect to any of these sets of parameters is a convex problem. Coordinate Descent (CD) refers to minimizing the cost function with respect to only 1 parameter at a time. It has been shown that repeatedly cycling through all the parameters, we are guaranteed to arrive at a local minima. If instead of 1 parameter, we take a set of parameters as we did before with W and H, it is called block coordinate descent (the interested reader should explore Alternating Minimization). CD makes sense if either the parameters are clearly separable into independent groups or if optimizing with respect to certain set of parameters is more efficient than with respect to others.

Coordinate descent may fail terribly when one variable influences the optimal value of another variable.

• Polyak Averaging: Polyak averaging consists of averaging several points in the parameter space that the optimization algorithm traverses through. So, if the algorithm encounters the points θ(1), θ(2), … during optimization, the output of Polyak averaging is:

The figure below explains the intuition behind Polyak averaging:

Most optimization problems in deep learning are non-convex where the path taken by the optimization algorithm is quite complicated and it might happen that a point visited in the distant past might be quite far from the current point in the parameter space. Thus, including such a point in the distant past might not be useful, which is why an exponentially decaying running average is taken. This scheme where the recent iterates are weighted more than the past ones is called Polyak-Ruppert Averaging:

• Supervised Pre-training: Sometimes it’s hard to directly train to solve for a specific task. Instead it might be better to train for solving a simpler task and use that as an initialization point for training to solve the more challenging task. As an intuition for why this seems logical, consider that you didn’t have any background in integration and were asked to learn how to compute the following integral:

If you’re anyone close to a normal person, your first reaction would be:

However, wouldn’t it be better if you were asked to understand the more basic integrations first:

I hope you understand what I meant with this example — learning a simpler task would put you in a better position to understand the more complex task. This particular strategy of training to solve a simpler task before facing the herculean one is called pretraining. A particular type of pretraining, called greedy supervised pretraining, firstly breaks a given supervised learning problem into simpler supervised learning ones and solving for the optimal version of each component in isolation. To build on the above intuition, the hypothesis as to why this works is that it gives better guidance to the intermediate layers of the network and helps in both, generalization and optimization. More often that not, the greedy pretraining is followed by a fine-tuning stage where all the parts are jointly optimized to search for the optimal solution to the full problem. As an example, the figure below shows how each hidden layer is trained one at a time, where the input to the hidden layer being learned is the output of the previously trained hidden layer.

Also, FitNets shows an alternative way to guide the training process. Deep networks are hard to train mainly because as deeper the model gets, more non-linearities are introduced. The authors propose the use of a shallower and wider teacher network that is trained first. Then, a second network which is thinner and deeper, called the student network is trained to predict not only the final outputs but also the intermediate layers of the teacher network. For those who might not be clear with what deep, shallow, wide and thin might mean, refer the following diagram:

The idea is that predicting the intermediate layers of the teacher network provides some hints as to how the layers of the student network should be used and aids the optimization procedure. It was shown that without the hints to the hidden layers, the students networks performs poorly in both the training and test data.

• Designing Models to Aid Optimization: Most of the work in deep learning has been towards making the models easier to optimize rather than designing a more powerful optimization algorithm. This is evident from the fact that Stochastic Gradient Descent, which is primarily used for training deep models today, has been in use since the 1960s. Many of the current design choices lend towards using linear transformations between layers and using activation functions like ReLU [max(0, x)] which are linear for the most part and enjoy large gradients as compared to sigmoidal units which saturate easily. Also, linear functions increase in a particular direction. Thus, if there’s an error, there’s a clear direction towards which the output should move to minimize the error.

Residual connections reduce the length of the shortest path from the output to the lower layers, thereby allowing a larger gradient to flow through and hence, tackling the vanishing gradient problem. Similarly, GoogleNet attached multiple copies of the output to intermediate layers so that a larger gradient flows to those layers. Once training is complete, the auxiliary heads are removed.

• Continuation Methods and Curriculum Learning: Based on the explanation given in the book (and also given that it’s fairly short), I’d recommend the interested reader to refer the book directly. The reason being that I realized that the content there was exactly to the point with no further scope of summarizing and hence, found it redundant to explain it again here. To give a very brief idea, Continuation Methods are a family of strategies where instead of a single cost function, a series of cost functions are optimized to aid optimization by making sure that the algorithm spends most of the time in well-behaved regions in the parameter space. The series of cost functions are designed such that the cost functions become progressively harder to solve, i.e. the first cost function is easiest to solve and the final cost function (which is actually the cost function we wanted to minimize) is the toughest, and the solution to each easier cost function serves as a good initialization point for the next, harder-to-optimize cost function. Curriculum Learning can be interpreted as a type of continuation method where the learning process is planned such that the simpler concepts are learned first and then the harder ones which depend on those simpler concepts. This concept had been shown to accelerate progress in animal training. One simple way to use it in the context of machine learning is to initially show the algorithm more of the easier images and less of the harder images. As the learning progresses, the proportion of easier images is reduced and that of the harder images is increased so that the model can ultimately learn the harder task.

This concludes the 2nd part of our summary for Chapter 8. This has been one of the most math intensive chapters that I have ever read and if you’ve made it this far, I have two things for ya: Thank You for taking the time out and Congratulations, as hopefully you have a much better clarity on what goes under the hood. Since Medium doesn’t support math symbols yet, a few of the mathematical notations were not proper and if you’re looking for a version with better notation, feel free to have a look over our repository here which contains Jupyter Notebooks entailing the same content but with the symbols converted to LaTex. Our next post will be about Chapter 11: Practical Methodology which focuses upon practical tips for making your Deep Learning model work. To stay updated with our posts, follow our publication, Inveterate Learner. Finally, I thank my co-author, Ameya Godbole, for thoroughly reviewing the post and suggesting many important changes. A special thanks to Raghav Somani for providing an in-depth review from a theoretical perspective that played an important role in the final shaping of this post.

Patience is a virtue and I’m learning patience. It’s a tough lesson.

- Elon Musk

If there’s anything that you might want to share with me or give any sort of feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on LinkedIn, Facebook or follow me on Github.

Deep Learning Book: Chapter 8 — Optimization For Training Deep Models Part II was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is going to be a series of blog posts on the Deep Learning book where we are attempting to provide a summary of each chapter highlighting the concepts that we found to be the most important so that other people can use it as a starting point for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer this for more clarity on notation.

When discussing deep learning, two models have become the leading buzzwords — Convolutional Neural Networks, which are the topic of this post, and Recurrent Neural Networks, which will be discussed soon.

Convolutional networks are an example of the successful application of insights obtained by studying the brain. We will avoid reiteration, and direct the reader to a summary of the history of deep learning and how convolutional networks tie in, which can be found at the end of this chapter.

• The Convolution Operation
• Motivation
• Pooling
• Convolution and Pooling as an Infinitely Strong Prior
• Variants of the Basic Convolution Function
• Structured Outputs
• Data Types
• Efficient Convolution Algorithms
• Random and Unsupervised Features
• The Neuroscientific Basis for Convolutional Networks

1. The Convolution Operation

The convolution operates on the input with a kernel (weights) to produce an output map given by:

Let us break down the formula. The steps involved are:

1. Express each function in terms of a dummy variable τ
2. Reflect the function g i.e. g(τ) → g(-τ)
3. Add a time offset i.e. g(τ) → g(t-τ). Adding the offset shifts the input to the right by t units (by convention, a negative offset shits it to the left)
4. Multiply f and g point-wise and accumulate the results to get output at instant t. Basically, we are calculating the area of overlap between f and shifted g

For our application, we are interested in the discrete domain formulation:

When the kernel is not flipped in its domain, we obtain the cross-correlation operation. The basic difference between the two operations is that convolution is commutative in nature, i.e. f and g can be interchanged without changing the output. Cross-correlation is not commutative. This difference is highlighted in the image below:

Although these equations imply that the domains for both f and g are infinite, in practice, these two variables are non-zero only in a finite region. As a result, the output is non-zero only in a finite region (where the non-zero regions of f and g overlap).

The intuition for convolution in 1-D can be extended to n-dimensions by nesting the convolution operations. Vincent Dumoulin and Francesco Visin provide an in depth analysis of how input and output shapes and computations are tied. Below is their visualization of a 2-D convolution operation:

The 1D convolution operation can be represented as a matrix vector product. The kernel marix is obtained by composing weights into a Toeplitz matrix. A Toeplitz matrix has the property that values along all diagonals are constant.

To extend this principle to 2D input, we first need to unroll the 2D input into a 1D vector. Once this is done, the kernel needs to be modified as before but this time resulting in a block-circulant matrix. What’s that?

A circulant matrix is a special case of a Toeplitz matrix where each row is a circular shift of the previous row. To see that it is a special case of the Toeplitz matrix is trivial.

A matrix which is circulant with respect to its sub-matrices is called a block circulant matrix. If each of the submatrices is itself circulant, the matrix is called doubly block-circulant matrix.

Now, given a 2D kernel, we can create the block-circulant matrix that will act allow matrix-vector implementation of convolution as below:

2. Motivation

Sparse Interactions

Each output unit is connected to (affected by) only a subset of the input units.

If there are m input units and n output units, a fully connected layer would require mn parameters (one per connection) and correspondingly the number of operations would scale as O(mn). On the other hand, if each output unit is sparsely connected to k input units, the layer requires kn parameters and O(kn) computations. In general, for a convolutional layer, the number of output units are a function of kernel size, stride and padding (discussed later). This actually makes n a function of m. Keeping this in mind O(mn) ~ O(m²) while O(kn) ~ O(km). By keeping k several orders of magnitude smaller than m, we see that the computational saving from sparse connections are huge.

As a practical example, consider a 3x3kernel operating on a black and white image of dimensions 224x224(this is a very standard setting of kernel size and image size, and can be seen in the first layer of the VGGNet). For same padding and stride as 1 (discussed in detail later), output size will also be 224x224. If this first layer were to be a fully connected layer, number of parameters would be ~2.5 billion (=224² x 224²). On the other hand, using a sparse layer with each output connected to 9(=3x3) inputs, the number of parameters is ~451 thousand (=224² x 9). In fact, a convolutional layer also incorporates parameter sharing (see below) and this number will decrease further.

Parameter Sharing

In the previous section, we saw that the output units are only connected to a small number of input units. In a convolutional layer, each kernel weight is used at every input position (except maybe at boundaries where different padding rules apply as discussed below), i.e. parameters used to compute different output units are tied together. By tied together, we mean that at all times their values are same. This means that even during training, they are updated by the same amount and by collecting the gradients from all output units.

Parameter sharing allows models to capture local connectivity while simultaneously computing the same features at different spatial locations. We will see the use of this property soon.

Here we make a short detour to section 5 for discussing locally connected layers and tiled convolution.

• Locally connected layer/unshared convolution: The connectivity graph of convolution operation and locally connected layer is the same. The only difference is that parameter sharing is not performed, i.e. each output unit performs a linear operation on its neighbourhood but the parameters are not shared across output units. This allows models to capture local connectivity while allowing different features to be computed at different spatial locations. This however requires much more parameters than the convolution operation.
• Tiled convolution is a sort of middle step between locally connected layer and traditional convolution. It uses a set of kernels that are cycled through. This reduces the number of parameters in the model while allowing for some freedom provided by unshared convolution.

The parameter complexity and computation complexity can be obtained as below. Note that:

• m = number of input units
• n = number of output units
• k = kernel size
• l = number of kernels in the set (for tiled convolution)

You can see now that the quantity of ~451 thousand parameters corresponds to the locally connected convolution operation. If we use a set of 200 kernels, the number of parameters for tiled convolution is 1.8 thousand. For a traditional convolution operation, this number is 9 parameters.

Equivariance

A function f is said to be equivariant to a function g if

f(g(x)) = g(f(x))

i.e. if input changes, the output changes in the same way.

Parameter sharing in a convolutional network provides equivariance to translation. What this means is that translation of the image results in corresponding translation in the output map (except maybe for boundary pixels). The reason for this is very intuitive: the same feature is being computed at all input points.

Note that convolution operation by itself is not equivariant to changes in scale or rotation. I’ve added a code snippet to demonstrate this. See the figure below that for more clarity on this:

3. Pooling

A convolutional layer can be broken down into the following components:

• Convolution
• Activation (detector stage)
• Pooling

The pooling function calculates a summary statistic of the nearby pixels at the point of operation. Some common statistics are max, mean, weighted average and L² norm of a surrounding rectangular window.

Pooling makes the representation slightly translation invariant, in that small translations in the input do not cause large changes in the output map. It allows detection of a particular feature if we only care about its existence, not its position in an image.

Pooling over feature channels can be used to develop invariance to certain transformations of the input. For e.g., units in a layer may be developed to learn rotated features and then pooled over. This property has been used in Maxout networks.

Pooling reduces the input size to the next layer in turn reducing the number of computations required upstream. Variable sized inputs are an issue when presented to a fully connected layer. To counter this, the pooling operation maybe performed on regions of the input (such as quadrants) thus allowing the model to work on variable sized inputs.

Theoretical guidelines for which pooling to use have been studied. Dynamic pooling has also been studied.

4. Convolution and Pooling as an Infinitely Strong Prior

What is a weight prior?

Assumptions about the weights (before learning) in terms of acceptable values and range are encoded into the prior distribution of the weights. A weak prior is has a high variance and shows that there is low confidence in the initial value of the weight. A strong prior is turn shows a narrow range of values about which we are confident before learning begins. An infinitely strong prior demarkates certain values as forbidden completely assigning them zero probability.

If we view the convolutional layer as a fully connected layer, convolution imposes an infinitely strong prior by making the following restrictions on the weights:

• Adjacent units must have the same weight but shifted in space.
• Except for a small spatially connected region, all other weights must be zero.

Likewise the pooling stage imposes an infinitely strong prior by requiring features to be translation invariant.

Insights:

• Convolution and pooling can cause underfitting if the priors imposed are not suitable for the task. As an example, consider this scenario. We may want to learn different features for different parts of an input. But the compulsion to used tied weights (enforced by standard convolution) on all parts of an image, forces us to either compromise or use more kernels (extract more features).
• Convolutional models should only be compared with other convolutional models. This is because other models which are permutation invariant can learn even when input features are permuted (thus loosing spatial relationships). Such models need to learn these spatial relationships (which are hard-coded in CNNs).

5. Variants of the Basic Convolution Function

In practical implementations of the convolution operation, certain modifications are made which deviate from the discrete convolution formula mentioned above:

• In general a convolution layer consists of application of several different kernels to the input. This allows the extraction of several different features at all locations in the input. This means that in each layer, a single kernel (filter) isn’t applied. Multiple kernels (filters), usually a power of 2, are used as different feature detectors.
• The input is generally not real-valued but instead vector valued (e.g. RGB values at each pixel or the feature values computed by the previous layer at each pixel position). Multi-channel convolutions are commutative only if number of output and input channels is the same.
• In order to allow for calculation of features at a coarser level strided convolutions can be used. The effect of strided convolution is the same as that of a convolution followed by a downsampling stage. This can be used to reduce the representation size.

• Zero padding helps to make output dimensions and kernel size independent. 3 common zero padding strategies are:

1. valid: The output is computed only at places where the entire kernel lies inside the input. Essentially, no zero padding is performed. For a kernel of size k in any dimension, the input shape of m in the direction will become m-k+1 in the output. This shrinkage restricts architecture depth.
2. same: The input is zero padded such that the spatial size of the input and output is same. Essentially, for a dimension where kernle size is k, the input is padded by k-1 zeros in that dimension. Since the number of output units connected to border pixels is less than that for centre pixels, it may under-represent border pixels.
3. full: The input is padded by enough zeros such that each input pixel is connected to the same number of output units.
   In terms of test set accuracy, the optimal padding is somewhere between same and valid.

• Besides locally-connected layers and tiled convolution, another extension can be to restrict the kernels to operate on certain input channels. One way to implement this is to connect the first m input channels to the first n output channels, the next m input channels to the next n output channels and so on. This method decreases the number of parameters in the model without dereasing the number of output units.
• When max pooling operation is applied to locally connected layer or tiled convolution, the model has the ability to become transformation invariant because adjacent filters have the freedom to learn a transformed version of the same feature. This essentially similar to the property leveraged by pooling over channels rather than spatially.
• Bias terms can be used in different ways in the convolution stage. For locally connected layer and tiled convolution, we can use a bias per output unit and kernel respectively. In case of traditional convolution, a single bias term per output channel is used. If the input size is fixed, a bias per output unit may be used to counter the effect of regional image statistics and smaller activations at the boundary due to zero padding.

6. Structured Outputs

Convolutional networks can be trained to output high-dimensional structured output rather than just a classification score. A good example is the task of image segmentation where each pixel needs to be associated with an object class. Here the output is the same size (spatially) as the input. The model outputs a tensor S where S[i,j,k] is the probability that pixel (j,k) belongs to class i.

To produce an output map as the same size as the input map, only same-padded convolutions can be stacked. Alternatively, a coarser segmentation map can be obtained by allowing the output map to shrink spatially.

The output of the first labelling stage can be refined successively by another convolutional model. If the models use tied parameters, this gives rise to a type of recursive model as shownbelow. (H¹, H², H³ share parameters)

The output can be further processed under the assumption that contiguous regions of pixels will tend to belong to the same label. Graphical models can describe this relationship. Alternately, CNNs can learn to optimize the graphical models training objective.

Another model that has gained popularity for segmentation tasks (especially in the medical imaging community) is the U-Net. The up-convolution mentioned is just a direct upsampling by repetition followed by a convolution with same padding.

7. Data Types

The data used with a convolutional network usually consist of several channels, each channel being the observation of a different quantity at some point in space or time.

One advantage to convolutional networks is that they can also process inputs with varying spatial extents.

When the output is accordingly variable sized, no extra design change needs to be made. If however the output is fixed sized, as in the classification task, a pooling stage with kernel size proportional to the input size needs to be used.

8. Efficient Convolution Algorithms

In some problem settings, performing convolution as pointwise multiplication in the frequency domain can provide a speed up as compared to direct computation. This is a result from the property of convolution:

When a d-dimensional kernel can be broken into the outer product of d vectors, the kernel is said to be separable. The corresponding convolution operations are more efficient when implemented as d 1-dimensional convolutions rather than a direct d-dimensional convolution. Note however, it may not always be possible to express a kernel as an outer product of lower dimensional kernels.

This is not to be confused with depthwise separable convolution (explained brilliantly here). This method restricts convolution kernels to operate on only one input channel at a time followed by 1x1 convolutions on all channels of the intermediate output.

Devising faster ways of performing convolution or approximate convolution without harming the accuracy of the model is an active area of research.

9. Random and Unsupervised Features

To reduce the computational cost of training the CNN, we can use features not learned by supervised training.

1. Random initialization has been shown to create filters that are frequency selective and translation invariant. This can be used to inexpensively select the model architecture. Randomly initialize several CNN architectures and just train the last classification layer. Once a winner is determined, that model can be fully trained in a supervised manner.
2. Hand designed kernels may be used; e.g. to detect edges at different orientations and intensities.
3. Unsupervised training of kernels may be performed; e.g. applying k-means clustering to image patches and using the centroids as convolutional kernels. Unsupervised pre-training may offer regularization effect (not well established). It may also allow for training of larger CNNs because of reduced computation cost.

Another approach for CNN training is greedy layer-wise pretraining most notably used in convolutional deep belief network. For example, in the case of multi-layer perceptrons, starting with the first layer, each layer is trained in isolation. Once the first layer is trained, its output is stored and used as input for training the next layer, and so on.

10. The Neuroscientific Basis for Convolutional Networks

Hubel and Wiesel studied the activity of neurons in a cat’s brain in response to visual stimuli. Their work characterized many aspects of brain function.

In a simplified view, we have:

1. The light entering the eye stimulates the retina. The image then passes through the the optic nerve and a region of the brain called the LGN (lateral geniculate nucleus)
2. V1 (primary visual cortex): The image produced on the retina is transported to the V1 with minimal processing. The properties of V1 that have been replicated in CNNs are:

• The V1 response is localized spatially, i.e. the upper image stimulates the cells in the upper region of V1 [localized kernel].
• V1 has simple cells whose activity is a linear function of the input in a small neighbourhood [convolution].
• V1 has complex cells whose activity is invariant to shifts in the position of the feature [pooling] as well as some changes in lighting which cannot be captured by spatial pooling [cross-channel pooling].

3. There are several stages of V1 like operations [stacking convolutional layers].

4. In the medial temporal lobe, we find grandmother cells. These cells respond to specific concepts and are invariant to several transforms of the input. In the medial temporal lobe, researchers also found neurons spiking on a particular concept, e.g. the Halle Berry neuron fires when looking at a photo/drawing of Halle Berry or even reading the text Halle Berry. Of course, there are neurons which spike at other concepts like Bill Clinton, Jennifer Aniston, etc.

The medial temporal neurons are more generic than CNN in that they respond even to specific ideas. A closer match to the function of the last layers of a CNN is the IT (inferotemporal cortex). When viewing an object, information flows from the retina, through LGN, V1, V2, V4 and reaches IT. This happens within 100ms. When a person continues to look at an object, the brain sends top-down feedback signals to affect lower level activation.

Some of the major differences between the human visual system (HVS) and the CNN model are:

• The human eye is low resolution except in a region called fovea. Essentially, the eye does not receive the whole image at high resolution but stiches several patches through eye movements called saccades. This attention based gazing of the input image is an active research problem. Note: attention mechanisms have been shown to work on natural language tasks.
• Integration of several senses in the HVS while CNNs are only visual.
• The HVS processes rich 3D information, and can also determine relations between objects. CNNs for such tasks are in their early stages.
• The feedback from higher levels to V1 has not been incorporated into CNNs with substantial improvement.
• While the CNN can capture firing rates in the IT, the similarity between intermediate computations is not established. The brain probably uses different activation and pooling functions. Even the linearity of filter response is doubtful as recent models for V1 involve quadratic filters.

Neuroscience tells us very little about the training procedure. Backpropogation which is a standard training mechanism today is not inspired by neuroscience and sometimes considered biologically implausible.

In order to determine the filter parameters used by neurons, a process called reverse correlation is used. The neuron activations are measured by an electrode when viewing several white noise images and a linear model is used to approximate this behaviour. It has been shown experimentally that the weights of the fitted model of V1 neurons are described by Gabor functions. If we go by the simplified version of the HVS, if the simple cells detect Gabor-like features, then complex cells learn a function of simple cell outputs which is invariant to certain translations and magnitude changes.

A wide variety of statistical learning algorithms (from unsupervised (sparse code) to deep learning (first layer features)) learn features with Gabor-like functions when applied to natural images. This goes to show that while no algorithm can be touted as the right method based on Gabor-like feature detectors, a lack of such features may be taken as a bad sign.

This concludes our discussion on one of the most important architectures that has caused a series of advancements in AI as described in Chapter 9. We hope that this gave you a good understanding of the basics of convolution, CNNs and the various tweaks that have been made to improve its performance. We’re sure that if you understand this post thoroughly, you won’t have a lot of difficulty in understanding various papers on CNNs. To stay updated with our posts, follow our publication, Inveterate Learner. If you’re looking for the summary of previous chapters or are more comfortable reading from a Jupyter Notebook, feel free to have a look over our repository here.

I think it’s important to reason from first principles rather than by analogy. With analogy, we are doing a thing because it’s like something else that was done by other people. With first principles, you boil things down to the most fundamental truths and then reason up from there.

- Elon Musk

If there’s anything that you might want to share with me or give any sort of feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on LinkedIn, Facebook or follow me on Github.

Deep Learning Book: Chapter 9— Convolutional Networks was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is going to be a series of blog posts on the Deep Learning book where we are attempting to provide a summary of each chapter highlighting the concepts that we found to be the most important so that other people can use it as a starting point for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer this for more clarity on notation.

There are many types of optimization problems involved in deep learning, with the toughest one being that of training a neural network. The main theme of the chapter is to focus on one type of optimization — finding the parameters θ that reduce a cost function J(θ).

Since this is a very math intensive chapter, in order to make concepts crystal clear, explanations are required at a lot of places. To avoid making this post too long, we are presenting the summary in two parts. We do not want to compromise on the main goal which is to make Deep Learning accessible to the largest audience possible. The sections of the chapter presented in this part are listed below:

• How Learning Differs from Pure Optimization
• Challenges in Neural Network Optimization
• Basic Algorithms

1. How Learning Differs from Pure Optimization

• In Machine Learning (ML), we care about a certain performance measure (say P, for e.g. accuracy) defined w.r.t the test set and optimize J(θ) (for e.g. cross-entropy loss) with the hope that it improves P as well. In pure optimization, optimizing J(θ) is the final goal.
• The expected generalization error (risk) is taken over the true data-generating distribution p_data. If we do have that, it becomes an optimization problem.

When we don’t have p_data but a finite training set, we have a ML problem. The latter can be converted back to an optimization problem by replacing p_data with the empirical distribution with p̂_data obtained from the training set, thereby reducing the empirical risk. This is called empirical risk minimization (ERM):

Although this might look relatively similar to optimization, there are two main problems. Firstly, ERM is prone to overfitting with the possibility of the dataset being learned by high capacity models (models with the ability to learn extremely complex functions). Secondly, ERM might not be feasible. Most optimization algorithms now are based on Gradient Descent (GD) which requires a derivative calculation and hence, may not work with certain loss functions like the 0–1 loss (as it is not differentiable).

• It is for the reasons mentioned above that a surrogate loss function (SLF) is used instead, that acts as a proxy. For e.g. the negative log-likelihood of the true class is used as a surrogate for 0–1 loss. I’ve added a code snippet below that would help you understand why 0–1 loss won’t work for Gradient Descent but cross-entropy, being a smooth function, would.

Using a SLF might even turn out to be beneficial as you can keep continuing to obtain a better test error by pushing the classes even further apart to get a more reliable classifier. By this, I mean that suppose we were using a 0–1 loss with a threshold of, say, 0.5 to assign each class. Here, in case the true class is 1, our model would have no motivation to push the prediction score close to 1 once it’s able to get it above 0.5. However, using cross-entropy, since we are using the raw prediction scores, the model keeps trying to push the prediction closer to the true class.

• Another common difference is that training might be halted following some convergence criterion based on Early Stopping to prevent overfitting, when the derivative of the surrogate loss function might still be large. This is different from pure optimization which is halted only when the derivative becomes very small. If you’re not familiar with Early Stopping, I’d recommend you to look at our previous post where we talk about Early Stopping and other regularization techniques.
• In ML optimization algorithms, the objective function decomposes as a sum over the examples and we can perform updates by randomly sampling a batch of examples and taking the average over the examples in that batch. If we consider n random variables, each having the true mean given by μ, the Standard Error (S.E.) of the mean estimated from those n random variables(see Appendix for derivation) is given as follows:

This indicates that as we include more examples for making an update, the returns of additional examples in improving the error is less than linear. Thus, if we use 100 and 10000 examples separately to make an update, the latter takes 100 times more compute, but reduces the error only by a factor of 10. Thus, it’s better to compute rapid approximate updates rather than a slow exact update.

• There are 3 types of sampling based algorithms — batch gradient descent (BGD), where the entire training set is used to make a single update, stochastic gradient descent (SGD), where a single example is used to make a weight update and mini-batch gradient descent (MBGD), where a batch (not to be confused with BGD) of examples is randomly sampled from the entire training set and is used to make an update. Mini-batch GD is nowadays commonly referred to as Stochastic GD.

It is a common practise to use batch sizes of powers of 2 to offer better run-time with certain hardware. Small batches tend to have a regularizing effect because of the noise they inject as each update is made by seeing only a very small portion of the entire training set, a.k.a. a batch of samples.

• The mini-batches should be selected randomly. It is sufficient to shuffle the dataset once and iterate over it multiple times. In the first epoch, the network sees each example for the first time and hence, the estimate of gradient is an unbiased estimate of the gradient of the true generalization error. However, from the second epoch onward, the estimate becomes biased as it is re-sampling from data that it has already seen. Such a sampling algorithm is called Random Reshuffling and although their analysis even for generalized linear models, which are strongly convex, is an open problem till date, reasonable efforts have been made to show that this biased estimate of the gradient is decent enough (at least as good as i.i.d. based Batch SGD).

2. Challenges in Neural Network Optimization

The optimization problem for training neural networks is generally non-convex. Some of the challenges faced are mentioned below:

• Ill-conditioning of the Hessian Matrix: The Hessian matrix and condition number have been covered in our summary for Chapter 4. For the sake of completion, the Hessian matrix H of a function f with a vector-valued input x is given as:

The ill-conditioning of H (defined below) can cause the SGD to get stuck in a sense that even very small steps may increase the cost function. A more rigorous explanation of this, added by Raghav Somani is given next.

Assuming local convexity, another way of looking at ill-conditioned Hessian is by considering its eigenvalues. Condition number of the Hessian is high if the largest positive eigenvalue of the local Hessian is too large, or when the lowest eigenvalue of the Hessian is very close to zero. It can be shown that the optimal step size is less than the inverse of the local smoothness constant of the function (smoothness, is informally proportional to the largest eigenvalue), so for the former case, if the largest eigenvalue of the Hessian is very large, the step-size required needs to be extremely small (leading to slow convergence). On the other hand, if the least eigenvalue is extremely small, then we again encounter slow convergence due to lack of enough convexity.

If local convexity is not assumed, it gets difficult to say just via first order optimization methods if we are converging to a saddle point or to a local minima.

In Chapter 4, it was shown that moving by a factor of ϵg would add the term given below to the cost function:

Ill-conditioning is said to happen when the first term exceeds the second term as then the cost would be increasing. In many cases, the gradient might be large leading to a large gradient norm (i.e. g’g). However, g’Hg might be even larger than the gradient norm. This would lead to slower learning as we would need to reduce the learning rate to make the first term lower than the second. To clarify more on this, since the first term contains the 2nd power of ϵ, and ϵ being less than 1, ϵ² < ϵ. So, to prevent ill-conditioning, the first term should be lower than the second, but given that g’Hg > g’g, this can be achieved only by reducing the learning rate, leading to slower learning. Thus, although ideally the gradient norm should decrease during training (since our primary aim is to reach a global minima where the gradient is 0), we can still get successful training even with the gradient norm increasing as shown below:

• Local minima: Nearly any Deep Learning (DL ) model is guaranteed to have an extremely large number of local minima (LM) arising due to the model identifiability problem.

A model is said to be identifiable if a sufficiently large training set can rule out all but one setting of the model parameters. In case of neural networks, we can obtain equivalent models by swapping the position of the neurons. Thus, they are not identifiable.

However, all the local minima caused due to this have the same value of the cost function, thus not being a problem. However, if local minima with high cost are common, it becomes a serious problem as shown above. Many points other than local minima can lead to low gradients. Nowadays, it’s common to aim for a low but not minimal cost value.

• Plateaus, Saddle Points and Other Flat Regions: Saddle point (SP) is another type of point with zero gradient where some points around it have higher value and the others have lower. Intuitively, this means that a saddle point acts as both a local minima for some neighbors and a local maxima for the others. Thus, Hessian at SP has both positive and negative eigenvalues (a very good explanation for this can be found here. TL;DR — for a function to curve upwards or downwards around a point as in the case of local minima and local maxima, the eigenvalues should have the same sign, positive for local minima and negative for local maxima).

For many classes of random functions, saddle points become more common at high dimensions with the ratio of number of SPs to LMs growing exponentially with n for an n-dimensional space. Many random functions have an amazing property that near points with low cost, the Hessian tends to take up mostly positive eigenvalues. SGD empirically tends to rapidly avoid encountering a high-cost saddle point. For SGD to rapidly avoid saddle points, it needs to have sufficiently high stochastic variance along all directions. Langevin dynamics stochastic gradient, is a set of SGD based algorithms that play around with SGD with added white noise to get off local minimas and saddles with high probability under mind conditions. There also might be wide, flat regions of constant value, thereby having a zero gradient. These can be problematic if the cost is high in these regions.

• Cliffs and Exploding Gradients: Neural Networks (NNs) might sometimes have extremely steep regions resembling cliffs due to the repeated multiplication of weights. Suppose we use a 3-layer (input-hidden-output) neural network with all the activation functions as linear. We choose the same number of input, hidden and output neurons, thus, using the same weight W for each layer. The output layer y = W*h where h = W*x represents the hidden layer, finally giving y = W*W x. So, deep neural networks involve multiplication of a large number of parameters leading to sharp non-linearities in the parameter space. These non-linearities give rise to high gradients in some places. At the edge of such a cliff, an update step might throw the parameters extremely far.

It can be taken care of by using Gradient Clipping (GC). The gradient indicates only the direction in which to make the update. If the GD update proposes making a very large step, GC intervenes to reduce the step size.

• Long-Term Dependencies: This problem is encountered when the NN becomes sufficiently deep. For example, if the same weight matrix W is used in each layer, after t steps, we’d get W *W * W … (t times). Using the eigendecomposition of W:

Thus, any eigenvalues not near an absolute value of one would either explode or vanish leading to the Vanishing and Exploding Gradient problem. The use of the same weight matrix is especially the case in Recurrent NNs (RNNs), where this is a serious problem.

• Inexact Gradients: Most optimization algorithms use a noisy/biased estimate of the gradient in cases where the estimate is based on sampling, or in cases where the true gradient is intractable for e.g. in the case of training a Restricted Boltzmann Machine (RBM), an approximation of the gradient is used. For RBM, the contrastive divergence algorithm gives a technique for approximating the gradient of its intractable log-likelihood.
• Neural Networks might not end up at any critical point at all and such critical points might not even necessarily exist. A lot of the problems might be avoided if there exists a space connected reasonably directly to the solution by a path that local descent can follow and if we are able to initialize learning within that well-behaved space. Thus, choosing good initial points should be studied.

3. Basic Algorithms

• Stochastic Gradient Descent: This has already been described before but there are certain things that should be kept in mind regarding SGD. The learning rate ϵ is a very important parameter for SGD. ϵ should be reduced after each epoch in general. This is due to the fact that the random sampling of batches acts as a source of noise which might make SGD keep oscillating around the minima without actually reaching it. This is shown below:

The true gradient of the total cost function (involving the entire dataset) actually becomes 0 when we reach the minimum. Hence, BGD can use a fixed learning rate. The following conditions guarantee convergence under convexity assumptions in case of SGD:

Setting it too low makes the training proceed slowly which might lead to the algorithm being stuck at a high cost value. Setting it too high would lead to large oscillations which might even push the learning outside the optimal region. The best way is to monitor the first several iterations and set the learning rate to be higher than the best performing one, but not too high to cause instability.

A big advantage of SGD is that the time taken to compute a weight update doesn’t grow with the number of training examples as each update is computed after observing a batch of samples which is independent of the total number of training examples. Theoretically, for a convex problem, BGD makes the error rate O(1/k) after k iterations whereas SGD makes it O(1/√k). However, SGD compensates for this with its advantages after a few iterations along with the ability to make rapid updates in the case of a large training set.

• Momentum: The momentum algorithm accumulates the exponentially decaying moving average of past gradients (called as velocity) and uses it as the direction in which to take the next step. Momentum is given by mass times velocity, which is equal to velocity if we’re using unit mass. The momentum update is given by:

The step size (earlier equal to learning rate * gradient) now depends on how large and aligned the sequence of gradients are. If the gradients at each iteration point in the same direction (say g), it will lead to a higher value of the step size as they just keep accumulating. Once it reaches a constant (terminal) velocity, the step size becomes ϵ || g|| / (1 — α). Thus, using α as 0.9 makes the speed 10 times. Common values of α are 0.5, 0.9 and 0.99.

Viewing it as the Newtonian dynamics of a particle sliding down a hill, the momentum algorithm consists of solving a set of differential equations via numerical simulation. There are two kinds of forces involved as shown below:

Read more about momentum in this excellent blog post by distill.ai: Why Momentum Really Works.

• Nesterov Momentum: This is a slight modification of the usual momentum equation. Here, the gradient is calculated after applying the current velocity to the parameters, which can be viewed as adding a correction factor:

The intuition behind Nesterov momentum is that upon being at a point θ in the parameter space, the momentum update is going to shift the point by αv. So, we are soon going to end up in the vicinity of (θ + αv). Thus, it might be better to compute the gradient from that point onward. The figure below describes this visually:

This concludes the 1st part of our summary for Chapter 8. We hope that this gave you a good intuition and understanding on the fundamental concepts behind Optimization used in Deep Learning. Part II of the summary would contain more advanced concepts like algorithms with adaptive learning rates and batch-normalization which are also fundamental in making Deep Learning practically applicable to real-world problems. To stay updated with our posts, follow our publication, Inveterate Learner. If you’re looking for the summary of previous chapters or are more comfortable reading from a Jupyter Notebook, feel free to have a look over our repository here. Finally, I thank my co-author for the publication, Ameya Godbole, for reviewing the post and suggesting many important areas for further explanations along with several nip ticks. A special thanks to Raghav Somani for providing deeper mathematical insights and clarity in a lot of places that gave me (and I hope everyone else too) a better understanding of the concepts.

When something is important enough, you do it even if the odds are not in your favor.

- Elon Musk

If there’s anything that you might want to share with me or give any sort of feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on LinkedIn, Facebook or follow me on Github.

Deep Learning Book: Chapter 8— Optimization For Training Deep Models Part I was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.

This is going to be a series of blog posts on the Deep Learning book where we are attempting to provide a summary of each chapter highlighting the concepts that we found to be the most important so that other people can use it as a starting point for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer this for more clarity on notation.

In Machine Learning, and more so in Deep Learning, overfitting is a major issue that occurs during training. A model is considered as overfitting the training data when the training error keeps decreasing but the test error (or the generalisation error) starts increasing. At this point we tend to believe that the model is learning the training data distribution and not generalising to unseen data. Regularization is a modification we make to the learning algorithm or the model architecture that reduces its generalisation error, possibly at the expense of increased training error. There are various ways of doing this, some of which include restriction on parameter values or adding terms to the objective function, etc.

These constraints are designed to encode some sort of prior knowledge, with a preference towards simpler models to promote generalisation (see Occam’s Razor). The sections present in this chapter are listed below:

• Parameter Norm Penalties
• Norm Penalties as Constrained Optimization
• Regularization and Under-Constrained Problems
• Dataset Augmentation
• Noise Robustness
• Semi-Supervised Learning
• Mutlitask Learning
• Early Stopping
• Parameter Tying and Parameter Sharing
• Sparse Representations
• Bagging and Other Ensemble Methods
• Dropout
• Adversarial Training
• Tangent Distance, Tangent Prop and Manifold Tangent Classifier

1. Parameter Norm Penalties

The idea here is to limit the capacity (the space of all possible model families) of the model by adding a parameter norm penalty, Ω(θ), to the objective function, J:

Here, θ represents only the weights and not the biases, the reason being that the biases require much less data to fit and do not add much variance.

1.1 L² Parameter Regularization

Here, we have the following parameter norm penalty:

Applying the 2nd order Taylor-Series approximation (ignoring all terms of order greater than 2 in the Taylor-Series expansion) at the point w* (where J̃(θ; X, y) assumes the minimum value, i.e., ∇J̃ (w*)= 0), we get the following expression (as the first order gradient term is 0):

Finally, ∇ Ĵ(w) = H(w — w*) since the first term is just a constant and the derivative of X’ H X (’ represents the transpose) is 2 H X. The overall gradient of the objective function (gradient of Ĵ + gradient of Ω(θ))becomes:

As α approaches 0, w comes closer to w*. Finally, since H is real and symmetric, it can be decomposed into a diagonal matrix ∧ and an orthonormal set of eigenvectors, Q.That is, H = Q’ ∧ Q.

Because of the marked term, the value of each weight is rescaled along the eigenvectors of H. The value of the weights along the eigenvector i,is rescaled by λi /(λi+α), where λi represents the eigenvalue corresponding to that eigenvector.

The diagram below illustrates this well:

To look at its application to Machine Learning, we have to look at linear regression. The objective function there is exactly quadratic, given by:

1.2 L¹ parameter regularization

Here, the parameter norm penalty is given by: Ω(θ) = ||w||¹

This makes the gradient of the overall objective function:

Now, the last term, sign(w), creates some difficulty as the gradient no longer scales linearly with w. This leads to a few complexities in arriving at the optimal solution (details of which can be found in this Appendix notebook):

My current interpretation of the max term is that, there shouldn’t be a zero crossing, as the gradient of the absolute value function is not differentiable at zero.

Thus, L¹ regularization has the property of sparsity, which is its fundamental distinguishing feature from L². Hence, L¹ is used for feature selection as in LASSO.

2. Norm penalties as constrained optimization

From chapter 4’s section 4, we know that to minimize any function under some constraints, we can construct a generalized Lagrangian function containing the objective function along with the penalties. Suppose we wanted Ω(θ) < k, then we could construct the following Lagrangian:

We get optimal θ by solving the Lagrangian. If Ω(θ) > k, then the weights need to be compensated highly and hence, α should be large to reduce its value below k. Likewise, if Ω(θ)<k, then the norm shouldn’t be reduced too much and hence, α should be small. This is now similar to the parameter norm penalty regularized objective function as both of them encourage lower values of the norm. Thus, parameter norm penalties naturally impose a constraint, like the L²-regularization, defining a constrained L²-ball. Larger α implies a smaller constrained region as it pushes the values really low, hence, allowing a small radius and vice versa. The idea of constraints over penalties is important for several reasons. Large penalties might cause non-convex optimization algorithms to get stuck in local minima due to small values of θ, leading to the formation of so-called dead cells, as the weights entering and leaving them are too small to have an impact. Constraints don’t enforce the weights to be near zero, rather being confined to a constrained region.

Another reason is that constraints induce higher stability. With higher learning rates, there might be a large weight, leading to a large gradient, which could go on iteratively leading to numerical overflow in the value of θ. Constrains, along with reprojection (to the corresponding ball), prevent the weights from becoming too large, thus, maintaining stability.

A final suggestion made by Hinton was to restrict the individual column norms of the weight matrix rather than the Frobenius norm of the entire weight matrix, so as to prevent any hidden unit from having a large weight. The idea here is that if we restrict the Frobenius norm, it doesn’t guarantee that the individual weights would be small, just their norm. So, we might have large weights being compensated by extremely small weights to make the overall norm small. Restricting each hidden unit individually gives us the required guarantee.

3. Regularized & Under-constrained problems

Underdetermined problems are those problems that have infinitely many solutions. A logistic regression problem having linearly separable classes with w as a solution, will always have 2w as a solution and so on. In some machine learning problems, regularization is necessary. For e.g., many algorithms (e.g. PCA) require the inversion of X’ X, which might be singular. In such a case, we can use a regularized form instead. (X’ X + αI) is guaranteed to be invertible.

Regularization can solve underdetermined problems. For e.g. the Moore-Pentose pseudoinverse defined earlier as:

This can be seen as performing a linear regression with L²-regularization.

4. Data augmentation

Having more data is the most desirable thing to improving a machine learning model’s performance. In many cases, it is relatively easy to artificially generate data. For a classification task, we desire for the model to be invariant to certain types of transformations, and we can generate the corresponding (x,y)pairs by translating the input x. But for certain problems, like density estimation, we can’t apply this directly unless we have already solved the density estimation problem.

However, caution needs to be maintained while augmenting data to make sure that the class doesn’t change. For e.g., if the labels contain both “b” and “d”, then horizontal flipping would be a bad idea for data augmentation. Adding random noise to the inputs is another form of data augmentation, while adding noise to hidden units can be seen as doing data augmentation at multiple levels of abstraction.

Finally, when comparing machine learning models, we need to evaluate them using the same hand-designed data augmentation schemes or else it might happen that algorithm A outperforms algorithm B, just because it was trained on a dataset which had more / better data augmentation.

5. Noise Robustness

Noise with infinitesimal variance imposes a penalty on the norm of the weights. Noise added to hidden units is very important and is discussed later in Dropout. Noise can even be added to the weights. This has several interpretations. One of them is that adding noise to weights is a stochastic implementation of Bayesian inference over the weights, where the weights are considered to be uncertain, with the uncertainty being modelled by a probability distribution. It is also interpreted as a more traditional form of regularization by ensuring stability in learning.

For e.g. in the linear regression case, we want to learn the mapping y(x) for each feature vector x, by reducing the mean square error.

Now, suppose a zero mean unit variance Gaussian random noise, ϵ, is added to the weights. We till want to learn the appropriate mapping through reducing the mean square. Minimizing the loss after adding noise to the weights is equivalent to adding another regularization term which makes sure that small perturbations in the weight values don’t affect the predictions much, thus stabilising training.

Sometimes we may have the wrong output labels, in which case maximizing p(y | x)may not be a good idea. In such a case, we can add noise to the labels by assigning a probability of (1-ϵ) that the label is correct and a probability of ϵ that it is not. In the latter case, all the other labels are equally likely. Label Smoothing regularizes a model with k softmax outputs by assigning the classification targets with probability (1-ϵ ) or choosing any of the remaining (k-1) classes with probability ϵ / (k-1).

6. Semi-Supervised Learning

P(x,y) denotes the joint distribution of x and y, i.e., corresponding to a training sample x, I have a label y. P(x) denotes the marginal distribution of x, i.e., just the training examples without any labels. In Semi-supervised Learning, we use both P(x,y)(some labelled samples) and P(x)(unlabelled samples) to estimate P(y|x)(since we want to predict the class, given the training sample). We want to learn some representation h = f(x)such that samples which are closer in the input space have similar representations and a linear classifier in the new space achieves better generalization error.

Instead of separating the supervised and unsupervised criteria, we can instead have a generative model of P(x) (or P(x, y)) which shares parameters with the discriminative model. The idea is to share the unsupervised/generative criterion with the supervised criterion to express a prior belief that the structure of P(x) (or P(x, y)) is connected to the structure of P(y|x), which is expressed by the shared parameters.

7. Multitask Learning

The idea is to improve the generalization error by pooling together examples from multiple tasks. Similar to how more data leads to more generalization, using a part of the model for different tasks constrains that part to learn good values. There are two types of model parameters:

• Task-specific: These parameters benefit only from that particular task.
• Generic, shared across all tasks: These are the ones which benefit from learning through various tasks.

Multitask learning leads to better generalization when there is actually some relationship between the tasks, which actually happens in the context of Deep Learning where some of the factors, which explain the variation observed in the data, are shared across different tasks.

8. Early Stopping

As mentioned at the start of the post, after a certain point of time during training, for a model with extremely high representational capacity, the training error continues to decrease but the validation error begins to increase (which we referred to as overfitting). In such a scenario, a better idea would be to return back to the point where the validation error was the least. Thus, we need to keep calculating the validation metric after each epoch and if there is any improvement, we store that parameter setting. Upon termination of training, we return the last saved parameters.

The idea of Early Stopping is that if the validation error doesn’t improve over a certain fixed number of iterations, we terminate the algorithm. This effectively reduces the capacity of the model by reducing the number of steps required to fit the model. The evaluation on the validation set can be done both on another GPU in parallel or done after the epoch. A drawback of weight decay was that we had to manually tweak the weight decay coefficient, which, if chosen wrongly, can lead the model to local minima by squashing the weight values too much. In Early Stopping, no such parameter needs to be tweaked which reduces the number of hyperparameters that we need to tune.

However, since we are setting aside some part of the training data for validation, we are not using the complete training set. So, once Early Stopping is done, a second phase of training can be done where the complete training set is used. There are two choices here:

• Train from scratch for the same number of steps as in the Early Stopping case.
• Use the weights learned from the first phase of training and retrain using the complete data.

Other than lowering the number of training steps, it reduces the computational cost also by regularizing the model without having to add additional penalty terms. It affects the optimization procedure by restricting it to a small volume of the parameter space, in the neighbourhood of the initial parameters. Suppose 𝛕 and ϵ represent the number of iterations and the learning rate respectively. Then, ϵ𝛕 effectively represents the capacity of the model. Intuitively, this can be seen as the inverse of the weight decay co-efficient λ. When ϵ𝛕 is small (or λ is large), the parameter space is small and vice versa. This equivalence holds true for a linear model with quadratic cost function (initial parameters w⁰ = 0). Taking the Taylor Series Approximation of J(w) around the empirically optimal weights w*:

multiplying with Q’ on both sides and using the fact that Q’Q = I (Q is orthonormal):

Assuming ϵ to be small enough:

The equation for L² regularization is given by:

Thus, if the hyperparameters are such that:

L²-regularization can be seen as equivalent to Early Stopping.

9. Parameter Tying and Parameter Sharing

Till now, most of the methods focused on bringing the weights to a fixed point, e.g. 0 in the case of norm penalty. However, there might be situations where we might have some prior knowledge on the kind of dependencies that the model should encode. Suppose, two models A and B, perform a classification task on similar input and output distributions. In such a case, we’d expect the parameters for both the models to be similar to each other as well. We could impose a norm penalty on the distance between the weights, but a more popular method is to force the set of parameters to be equal. This is the essence behind Parameter Sharing. A major benefit here is that we need to store only a subset of the parameters (e.g. storing only the parameters for model A instead of storing for both A and B) which leads to large memory savings. In the example of Convolutional Neural Networks or CNNs (discussed in Chapter 9), the same feature is computed across different regions of the image and hence, a cat is detected irrespective of whether it is at position ior i+1 .

10. Sparse Representations

We can place penalties on even the activation values of the units which indirectly imposes a penalty on the parameters. This leads to representational sparsity, where many of the activation values of the units are zero. In the figure below, h is a representation of x, which is sparse. Representational sparsity is obtained similarly to the way parameter sparsity is obtained, by placing a penalty on the representation h instead of the weights.

Another idea could be to average the activation values across various examples and push it towards some value. An example of getting representational sparsity by imposing hard constraint on the activation value is the Orthogonal Matching Pursuit (OMP) algorithm, where a representation h is learned for the input x by solving the constrained optimization problem:

where the constraint is on the the number of non-zero entries indicated by b. The problem can be solved efficiently when W is restricted to be orthogonal

11. Bagging and Other Ensemble Methods

The techniques which train multiple models and take the maximum vote across those models for the final prediction are called ensemble methods. The idea is that it’s highly unlikely that multiple models would make the same error in the test set.

Suppose that we have K regression models, with the model #i making an error ϵi on each example, where ϵi is drawn from a zero mean, multivariate normal distribution such that: 𝔼(ϵi²)=v and 𝔼(ϵiϵj)=c. The error on each example is then the average across all the models: (∑ ϵi)/K.

The mean of this average error is 0 (as the mean of each of the individual ϵiϵi is 0). The variance of the average error is given by:

Thus, if c = v, then there is no change. If c = 0, then the variance of the average error decreases with K. There are various ensembling techniques. In the case of Bagging (Bootstrap Aggregating), the same training algorithm is used multiple times. The dataset is broken into K parts by sampling with replacement (see figure below for clarity) and a model is trained on each of those K parts. Because of sampling with replacement, the K parts have a few similarities as well as a few differences. These differences cause the difference in the predictions of the K models. Model averaging is a very strong technique.

12. Dropout

Dropout is a computationally inexpensive, yet powerful regularization technique. The problem with bagging is that we can’t train an exponentially large number of models and store them for prediction later. Dropout makes bagging practical by making an inexpensive approximation. In a simplistic view, dropout trains the ensemble of all sub-networks formed by randomly removing a few non-output units by multiplying their outputs by 0. For every training sample, a mask is computed for all the input and hidden units independently. For clarification, suppose we have h hidden units in some layer. Then, a mask for that layer refers to a h dimensional vector with values either 0(remove the unit) or 1(keep the unit).

There are a few differences from bagging though:

• In bagging, the models are independent of each other, whereas in dropout, the different models share parameters, with each model taking as input, a sample of the total parameters.
• In bagging, each model is trained till convergence, but in dropout, each model is trained for just one step and the parameter sharing makes sure that subsequent updates ensure better predictions in the future.

At test time, we combine the predictions of all the models. In the case of bagging with K models, this was given by the arithmetic mean. In case of dropout, the probability that a model is chosen is given by p(μ), with μ denoting the mask vector. The prediction then becomes ∑ p(μ)p(y|x, μ). This is not computationally feasible, and there’s a better method to compute this in one go, using the geometric mean instead of the arithmetic mean.

We need to take care of two main things when working with geometric mean:

• None of the probabilities should be zero.
• Re-normalization to make sure all the probabilities sum to 1.

The advantage for dropout is that first term can be approximated in one pass of the complete model by dividing the weight values by the keep probability (weight scaling inference rule). The motivation behind this is to capture the right expected values from the output of each unit, i.e. the total expected input to a unit at train time is equal to the total expected input at test time. A big advantage of dropout then is that it doesn’t place any restriction on the type of model or training procedure to use.

Points to note:

• Reduces the representational capacity of the model and hence, the model should be large enough to begin with.
• Works better with more data.
• Equivalent to L² for linear regression, with different weight decay coefficient for each input feature.

Biological Interpretration:

During sexual reproduction, genes could be swapped between organisms if they are unable to correctly adapt to the unusual features of any organism. Thus, the units in dropout learn to perform well regardless of the presence of other hidden units, and also in many different contexts.

Adding noise in the hidden layer is more effective than adding noise in the input layer. For e.g. let’s assume that some unit learns to detect a nose in a face recognition task. Now, if this unit is removed, then some other unit either learns to redundantly detect a nose or associates some other feature (like mouth) for recognising a face. In either way, the model learns to make more use of the information in the input. On the other hand, adding noise to the input won’t completely removed the nose information, unless the noise is so large as to remove most of the information from the input.

13. Adversarial Training

Deep Learning has outperformed humans in the task of Image Recognition, which might lead us to believe that these models have acquired a human-level understanding of an image. However, experimentally searching for an x′ (given an x), such that prediction made by the model changes, shows otherwise. As shown in the image below, although the newly formed image (adversarial image) looks almost exactly the same to a human, the model classifies it wrongly and that too with very high confidence:

Adversarial training refers to training on images which are adversarially generated and it has been shown to reduce the error rate. The main factor attributed to the above mentioned behaviour is the linearity of the model (say y = Wx), caused by the main building blocks being primarily linear. Thus, a small change of ϵ in the input causes a drastic change of Wϵ in the output. The idea of adversarial training is to avoid this jumping and induce the model to be locally constant in the neighborhood of the training data.

This can also be used in semi-supervised learning. For an unlabelled sample x, we can assign the label ŷ (x) using our model. Then, we find an adversarial example, x′, such that y(x′)≠ŷ (x) (an adversary found this way is called virtual adversarial example). The objective then is to assign the same class to both x and x′. The idea behind this is that different classes are assumed to lie on disconnected manifolds and a little push from one manifold shouldn’t land in any other manifold.

14. Tangent Distance, Tangent Prop and manifold Tangent Classifier

Many ML models assume the data to lie on a low dimensional manifold to overcome the curse of dimensionality. The inherent assumption which follows is that small perturbations that cause the data to move along the manifold (it originally belonged to), shouldn’t lead to different class predictions. The idea of the tangent distance algorithm to find the K-nearest neighbors using the distance metric as the distance between manifolds. A manifold Mi is approximated by the tangent plane at Xi, hence, this technique needs tangent vectors to be specified.

The tangent prop algorithm proposed to learn a neural network based classifier, f(x), which is invariant to known transformations causing the input to move along its manifold. Local invariance would require that ▽ f(x) is perpendicular to the tangent vectors V(i). This can also be achieved by adding a penalty term that minimizes the directional directive of f(x) along each of the V(i).

It is similar to data augmentation in that both of them use prior knowledge of the domain to specify various transformations that the model should be invariant to. However, tangent prop only resists infinitesimal perturbations while data augmentation causes invariance to much larger perturbations.

Manifold Tangent Classifier works in two parts:

• Use Autoencoders to learn the manifold structures using Unsupervised Learning.
• Use these learned manifolds with tangent prop.

I have missed out on many details along the way in the trade-off for explaining the ones I found the most relevant today. If you’re looking for the summary of previous chapters or are more comfortable reading from a Jupyter Notebook, feel free to have a look over our repository here. If you are interested in reading more such summaries and/or receiving research paper implementations/explanations, follow our publication, Inveterate Learner. Finally, I thank my co-author for the publication, Ameya Godbole, for reviewing the post and doing several important corrections. A special thanks to Harsh Patel for pointing out the mistake in my definition of regularization and Raghav Somani for providing clarification in the norm notation of OMP’s constrained optimization problem.

Persistence is very important. You should not give up unless you are forced to give up.

-Elon Musk

If there’s anything that you might want to share with me or give any sort of feedback on my writing/thoughts, I would love to hear it from you. Feel free to connect with me on LinkedIn, Facebook or follow me on Github.

Deep Learning Book: Chapter 7 — Regularization for Deep Learning was originally published in Inveterate Learner on Medium, where people are continuing the conversation by highlighting and responding to this story.