Neural Network in C++ From Scratch and Backprop-Free Optimizers

Image for post
Image for post

Introduction

So this code can also be used for some research because you can also do things you couldn’t do in other frameworks.

In this article:

  1. Features of the framework
  2. Neural networks from scratch
  3. Framework design
  4. Exotic backpropagation-free optimizer: Shaking Tree optimizer
  5. What I learned doing this
  6. Github repository

Let’s go!

1. Features of the framework

  • Neural network, neurons and edges as explicit objects
  • Only multilayer perceptrons with Linear/ReLU/Sigmoid activations
  • No parallel computations, no optimizations, no convolutional layers
  • Exotic backpropagation-free optimizer

2. Neural networks from scratch

Image for post
Image for post
A graph representing a neural network

That’s how neural networks are usually represented, vertices(neurons) + oriented edges(dendrites), a directed graph. But in practice they’re used with matrices because computations are much faster on GPUs that way.

For complete beginners, you can try playing with neural network on this webpage. The easy version of how a neural network does the forward pass is as follows:

(0) create a neural network following the above architecture

(1) put values in the input neurons (exp: 3 neurons with value 1, 5 and 3)

(2) trigger the input layer. The values are multiplied with a weight linking each input neuron to each neuron of the 2nd layer (3neurons*4neurons=12scalars/weights/edges). Then sum the 3 inputs*weights for each of the 4 neurons of the 2nd layer. (exp: 1*a1+5*b1+3*c1 for 1st neuron of 2nd layer, then 1*a2+5*b2+3*c2 etc.)

(3) trigger the 2nd layer and do (2) between the 3rd layer and the 2nd layer (the same way it was done between the 2nd and the 1st layer)

(4) read the two values accumulated by the 3rd/output layer

The forward pass is easy. The same computations can be done with matrices. What’s harder to understand and important to re-implement is the backward pass, the method used to learn the right weights. The inputs [1, 5, 3] and outputs of each layer depend on the data we’re processing. The weights [a1, b1, c1, a2..] are here to process all inputs correctly. We’ll focus on finding the good weights.

In this repo, neural networks are implemented in a graph way. Some Github repositories of that kind exist because people - including me - think it’s a great way to be sure you understood how neural networks work, and it’s also a great way to play with neural networks.

This repo is a beginning of neural network framework in C++ because it’s more elaborated than “just the neural-network part” in one file. It’s not even 0.01% of what libs like dlib are, and it’s not meant to be a framework that would serve anything but playing around and understanding neural networks.

3. Framework Design

  • Neural: Contains classes related to the neural network
  • Dataset: Contains one simple class for reading a dataset
  • Optimizer: Contains a generic optimizer class, a classical backpropagation optimizer and an exotic optimizer
  • Misc: Contains activation functions and their derivatives

2. Neural Classes

  • NeuralNetwork.h/.cpp: the main class containing a model. A NeuralNetwork is composed of multiple layers
  • Layer.h/.cpp: A Layer is composed of multiple neurons. It has a type (INPUT/STANDARD/OUTPUT) because it doesn’t work the same way depending on its type and it has an activation function
  • Neuron.h/.cpp: A Neuron has a parent layer. A neuron accumulates the input of the neurons connected to it (_accumulated), it outputs that input to its edges after processing it with its _activation_function (which you can change on a per-neuron basis). A neuron knows its _next and _previous edges.
  • Edge.h/.cpp: An Edge knows its next neuron (_n), the neuron its coming from (_nb), it has a weight (_w), it can memorize how much its weight was shift (_last_shift) last time it was, and it has a backpropagation memory so that it can retain a part of the chain rule

3. Dataset / Optimizer

  • Dataset.h/.cpp: It gives the data. One input/output is just a vector (again, no matrices, no images). So the list of all inputs is a vector of vector. The Dataset class is also responsible for doing the train/test split.
  • Optimizer.h/.cpp: Abstract class that links the network and the dataset together. Child classes must implement a “minimize” method that is called during the optimization process to minimize the loss.
  • Backpropagation.h/.cpp: Implementation of the backpropagation optimizer (though the backpropagation computations are in the neuron class for simplification). This class is mostly there to call these methods in the neuron class and to apply the new computed weights. It uses a batch size, the learning rate is a global variable because it’s common to all implemented optimizers and it’s easier to access it from anywhere.
  • ShakingTree.h/.cpp: Exotic optimizer that’ll be detailed later.

Computation example

Just use the “mattmazur_step_by_step” branch on git, this branch serves only that purpose and contains older code than the code on “master”.

Image for post
Image for post
Second iteration reproduces the computation on mattmazur’s website

You can add logs wherever you want to understand the computations following the blog post from mattmazur. Mostly you can uncomment the cout line in the “getBackpropagationShifts” method in neuron.cpp.

As you can see, the results are exactly the same he got.

Building a Neural Network

Image for post
Image for post

Instanciate the class. Add an input layer, specify the number of neurons (size). Then add hidden layers (standard), specify the number of neurons (size=5 neurons) and an activation function (sigmoid). Finally, add an output layer, its size (1 output value) and an activation function (sigmoid).

Yeah, C++ can have a quite great readability now.

The “autogenerate” adds the edges (connectComplete) so that the layers are fullyconnected, and it also randomizes all the weights:

Image for post
Image for post

Predicting a value

Image for post
Image for post

The inputs are set up in the _accumulated variable of the input neurons, then trigger() calls each layer to fire successively. Finally the output() just returns the activation_function(accumulated) for each neuron of the last/output layer.

Backpropagation

Image for post
Image for post

Going into details wouldn’t serve much as you mostly only need to read the guide from mattmazur to understand what’s being done in here.

You need the target to do the computations for the output layer (the “if” block), then you need to keep in memory a part of the computations to apply the chain rule so that it backpropagates to all other layers(the “else” block).

dw stands for delta_weight, so for each neuron you’re essentially computing a delta to apply to each of its _previous edges.

“outputDerivative” and other functions are named so that they’re easy to read and to understand.

That’s basic backpropagation. No momentum, no tricks, nothing but gradients.

4. Exotic backpropagation-free optimizer: ShakingTree optimizer

Why “ShakingTree”? Because we’re going to randomly change the weights, like if we were shaking the graph as a tree or if we were randomly shaking some branches so that only the weaker ones are replaced by greater ones.

Theory

Can you change the weights of a neural network without doing a forward pass to compute the loss? Well at some points you need to evaluate what you’re doing and how it impacts the loss (1)+(2), so the main thing I wanted to remove is the gradients computations (3).

But I still need a way to change the weights. Ok, some people tried genetic algorithms, it works but it’s quite random, and of course the more weights, the harder it gets to find the right values...but that’s also true with vanishing gradients. We know that gradients give a great estimation of how to change the weights of a neural network. The main idea of ShakingTree is to try to approximate the gradients (OR something that would be at least as great as gradients) from random values without explicitly computing the gradients.

So, is it worth it to quickly try random values? Or is it better to slowly compute gradients? Is there a way to be quick and compute “random” values that end up being better than the gradients? That’s what I tried to answer.

I tried two methods, a “basic” one and a “complex” one.

  1. Basic method
  • Evaluate the score with current weights on a part of the dataset
  • Save current weights
  • Apply new weights randomly (amplitude, distribution, number of weights etc.. many hyperparameters)
  • Re-evaluate the score on (another?) part of the dataset
  • If the new score is worst, re-apply old weights

2. Complex method

  • Evaluate the score with current weights
  • Generate a delta to be applied to all weights (this delta is meant to act like the gradients)
  • Apply the delta weight, evaluate it, save the delta score and the delta weight
  • Now technically you can evaluate a kind of f(delta_weight) = delta_score (that’s what the gradients aim to be!)
  • Each N iterations, average the delta_weight of the weights that reduced the score (delta_score < 0), and apply that delta

That’s all for the theory, now you know the idea, what are the resuls?

In practice

The plots:

Image for post
Image for post
Loss on test set = f(seconds) on a dedicated machine

Why is it noisy? Because it’s random and it can sometimes quickly get to bad results. The fact that it goes from bad results to good results partially shows how easy the task is (but changing the final output layer parameters’ can also quickly give bad results and changing them back again can give good results again quickly). minimizeBasicLarger2 and minimizeBasic use the “basic” method of ShakingTree with different hyperparameters. Backpropagation is in blue and the complex version of ShakingTree is in red.

The first hyperparameters I chose for minimizeBasicLarger gave much more random results so I changed them once or twice, giving the green curve. I didn’t change the parameters of the other algorithms on that particular task.

Keeping only the best iteration:

Image for post
Image for post
Best loss on test set = f(seconds) on a dedicated machine

Limitations

These ShakingTree algorithms with their worst hyperparameters could probably look like a random search but the added hyperparameters are there to avoid being too close to a random search. These algorithms could probably also be approximated by genetic algorithms, but the same apply, it’s not exactly the same algorithm.

We’re not doing much better than any algorithm that probably performs well on MNIST and actually proving that these algorithms work on these datasets is far from being able to prove that they work on real-life datasets. But maybe with some hyperparameter tuning and with a more tensor-oriented approach it could be applied to convolutional filters on a more standard framework like Pytorch.

This article is mainly a proposition for a new backpropagation-free algorithm. There are many other backprop-free algorithms that could perform better on small datasets with small networks, but which probably are always worst than backprop on larger datasets with larger networks.

5. What I learned doing this

  • Backpropagation is very efficient because it’s two operations in one. When doing backprop, you’re evaluating a way to change your parameters AND evaluating the score of your parameters at the same time. And this delta you apply to your parameters is qualitative, it’s based on a rigorous metric.
  • Doing better than backprop in some configurations will always be possible. But to create completely new and better optimization algorithms that scale well, we need to focus on this qualitative way to change the parameters. There’s tons of information that can be used, variance of parameters on a layer, statistics on one particular layer, on its outputs etc.. so I seriously doubt that backpropagation or its derivatives give the best possible “delta” you could apply on the weights. New kind of optimization algorithms definitely should get more attention.
  • Neural networks are not blackboxes. That’s just a way to say that it’s a complex model but if you made hyperparameters optimization to find the best features to extract from images in the past, that could also be a blackbox. The way they’re optimized can be explained fairly well and the gradient descent algorithm is easy to understand in its basic form. ShakingTree also shows that finding a great value for one parameter and doing so multiple times helps in finding the overall great weights for a neural network. So backpropagation doesn’t have to always be right, it only needs to be right most of the time, that’s even more true when you use a momentum.
  • Finally, building the root of a deep learning framework is insanely hard and people developing Pytorch, Tensorflow or CuDNN truly deserve some recognition and it’s not a surprise that these guys are supported by some of the biggest companies in the world.

Thanks for reading!

6. Github repository / code

Nota-Bene: this code was written in 2018

____________________________________________

This article was written on Medium, by Elie D, for https://www.hyugen.com/en.

Support us 💙

Date: 2020/10/13

Written by

We work on statistics, machine learning, AI and we want to bring Artificial General Intelligence into the real world — Website: https://www.hyugen.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store