Understanding Hinton

Part of Understanding Hinton's Capsule Networks Series:

Part I: Intuition (you are reading it now)
Part II: How Capsules Work
Part III: Dynamic Routing Between Capsules
Part IV: CapsNet Architecture

Quick announcement about our new publication AI³. We are getting the best writers together to talk about the Theory, Practice, and Business of AI and machine learning. Follow it to stay up to date on the latest trends.

1. Introduction

Last week, Geoffrey Hinton and his team published two papers that introduced a completely new type of neural network based on so-called capsules. In addition to that, the team published an algorithm, called dynamic routing between capsules, that allows to train such a network.

Geoffrey Hinton has spent decades thinking about capsules. Source.

For everyone in the deep learning community, this is huge news, and for several reasons. First of all, Hinton is one of the founders of deep learning and an inventor of numerous models and algorithms that are widely used today. Secondly, these papers introduce something completely new, and this is very exciting because it will most likely stimulate additional wave of research and very cool applications.

In this post, I will explain why this new architecture is so important, as well as intuition behind it. In the following posts I will dive into technical details.

However, before talking about capsules, we need to have a look at CNNs, which are the workhorse of today's deep learning.

Architecture of CapsNet from the original paper.

2. CNNs Have Important Drawbacks

CNNs (convolutional neural networks) are awesome. They are one of the reasons deep learning is so popular today. They can do amazing things that people used to think computers would not be capable of doing for a long, long time. Nonetheless, they have their limits and they have fundamental drawbacks.

Let us consider a very simple and non-technical example. Imagine a face. What are the components? We have the face oval, two eyes, a nose and a mouth. For a CNN, a mere presence of these objects can be a very strong indicator to consider that there is a face in the image. Orientational and relative spatial relationships between these components are not very important to a CNN.

To a CNN, both pictures are similar, since they both contain similar elements. Source.

How do CNNs work? The main component of a CNN is a convolutional layer. Its job is to detect important features in the image pixels. Layers that are deeper (closer to the input) will learn to detect simple features such as edges and color gradients, whereas higher layers will combine simple features into more complex features. Finally, dense layers at the top of the network will combine very high level features and produce classification predictions.

An important thing to understand is that higher-level features combine lower-level features as a weighted sum: activations of a preceding layer are multiplied by the following layer neuron's weights and added, before being passed to activation nonlinearity. Nowhere in this setup there is pose(translational and rotational) relationship between simpler features that make up a higher level feature. CNN approach to solve this issue is to use max pooling or successive convolutional layers that reduce spacial size of the data flowing through the network and therefore increase the "field of view" of higher layer's neurons, thus allowing them to detect higher order features in a larger region of the input image. Max pooling is a crutch that made convolutional networks work surprisingly well, achieving superhuman performance in many areas. But do not be fooled by its performance: while CNNs work better than any model before them, max pooling nonetheless is losing valuable information.

Hinton himself stated that the fact that max pooling is working so well is a big mistake and a disaster:

Hinton: "The pooling operation used in convolutional neural networks is a big mistake and the fact that it works so well is a disaster."

Of course, you can do away with max pooling and still get good results with traditional CNNs, but they still do not solve the key problem:

Internal data representation of a convolutional neural network does not take into account important spatial hierarchies between simple and complex objects.

In the example above, a mere presence of 2 eyes, a mouth and a nose in a picture does not mean there is a face, we also need to know how these objects are oriented relative to each other.

3. Hardcoding 3D World into a Neural Net: Inverse Graphics Approach

Computer graphics deals with constructing a visual image from some internal hierarchical representation of geometric data. Note that the structure of this representation needs to take into account relative positions of objects. That internal representation is stored in computer's memory as arrays of geometrical objects and matrices that represent relative positions and orientation of these objects. Then, special software takes that representation and converts it into an image on the screen. This is called rendering.

Computer graphics takes internal representation of objects and produces an image. Human brain does the opposite. Capsule networks follow a similar approach to the brain. Source.

Inspired by this idea, Hinton argues that brains, in fact, do the opposite of rendering. He calls it inverse graphics: from visual information received by eyes, they deconstruct a hierarchical representation of the world around us and try to match it with already learned patterns and relationships stored in the brain. This is how recognition happens. And the key idea is that representation of objects in the brain does not depend on view angle.

So at this point the question is: how do we model these hierarchical relationships inside of a neural network? The answer comes from computer graphics. In 3D graphics, relationships between 3D objects can be represented by a so-called pose, which is in essence translation plus rotation.

Hinton argues that in order to correctly do classification and object recognition, it is important to preserve hierarchical pose relationships between object parts. This is the key intuition that will allow you to understand why capsule theory is so important. It incorporates relative relationships between objects and it is represented numerically as a 4D pose matrix.

When these relationships are built into internal representation of data, it becomes very easy for a model to understand that the thing that it sees is just another view of something that it has seen before. Consider the image below. You can easily recognize that this is the Statue of Liberty, even though all the images show it from different angles. This is because internal representation of the Statue of Liberty in your brain does not depend on the view angle. You have probably never seen these exact pictures of it, but you still immediately knew what it was.

Your brain can easily recognize this is the same object, even though all photos are taken from different angles. CNNs do not have this capability.

For a CNN, this task is really hard because it does not have this build-in understanding of 3D space, but for a CapsNet it is much easier because these relationships are explicitly modeled. The paper that uses this approach was able to cut error rate by 45% as compared to the previous state of the art, which is a huge improvement.

Another benefit of the capsule approach is that it is capable of learning to achieve state-of-the art performance by only using a fraction of the data that a CNN would use (Hinton mentions this in his famous talk about what is wrongs with CNNs). In this sense, the capsule theory is much closer to what the human brain does in practice. In order to learn to tell digits apart, the human brain needs to see only a couple of dozens of examples, hundreds at most. CNNs, on the other hand, need tens of thousands of examples to achieve very good performance, which seems like a brute force approach that is clearly inferior to what we do with our brains.

4. What Took It so Long?

The idea is really simple, there is no way no one has come up with it before! And the truth is, Hinton has been thinking about this for decades. The reason why there were no publications is simply because there was no technical way to make it work before. One of the reasons is that computers were just not powerful enough in the pre-GPU-based era before around 2012. Another reason is that there was no algorithm that allowed to implement and successfully learn a capsule network (in the same fashion the idea of artificial neurons was around since 1940-s, but it was not until mid 1980-s when backpropagation algorithm showed up and allowed to successfully train deep networks).

In the same fashion, the idea of capsules itself is not that new and Hinton has mentioned it before, but there was no algorithm up until now to make it work. This algorithm is called "dynamic routing between capsules". This algorithm allows capsules to communicate with each other and create representations similar to scene graphs in computer graphics.

The capsule network is much better than other models at telling that images in top and bottom rows belong to the same classes, only the view angle is different. The latest papers decreased the error rate by a whopping 45%. Source.

5. Conclusion

Capsules introduce a new building block that can be used in deep learning to better model hierarchical relationships inside of internal knowledge representation of a neural network. Intuition behind them is very simple and elegant.

Hinton and his team proposed a way to train such a network made up of capsules and successfully trained it on a simple data set, achieving state-of-the-art performance. This is very encouraging.

Nonetheless, there are challenges. Current implementations are much slower than other modern deep learning models. Time will show if capsule networks can be trained quickly and efficiently. In addition, we need to see if they work well on more difficult data sets and in different domains.

In any case, the capsule network is a very interesting and already working model which will definitely get more developed over time and contribute to further expansion of deep learning application domain.

This concludes part one of the series on capsule networks. In the Part II, more technical part, I will walk you through the CapsNet's internal workings step by step.

Understanding Hinton's Capsule Networks. Part II: How Capsules Work.

Part of Understanding Hinton's Capsule Networks Series:

Part I: Intuition
Part II: How Capsules Work (you are reading it now)
Part III: Dynamic Routing Between Capsules
Part IV: CapsNet Architecture

Quick announcement about our new publication AI³. We are getting the best writers together to talk about the Theory, Practice, and Business of AI and machine learning. Follow it to stay up to date on the latest trends.

Introduction

In Part I of this series on capsule networks, I talked about the basic intuition and motivation behind the novel architecture. In this part, I will describe, what capsule is and how it works internally as well as intuition behind it. In the next part I will focus mostly on the dynamic routing algorithm.

What is a Capsule?

In order to answer this question, I think it is a good idea to refer to the first paper where capsules were introduced — "Transforming Autoencoders" by Hinton et al. The part that is important to understanding of capsules is provided below:

"Instead of aiming for viewpoint invariance in the activities of "neurons" that use a single scalar output to summarize the activities of a local pool of replicated feature detectors, artificial neural networks should use local "capsules" that perform some quite complicated internal computations on their inputs and then encapsulate the results of these computations into a small vector of highly informative outputs. Each capsule learns to recognize an implicitly defined visual entity over a limited domain of viewing conditions and deformations and it outputs both the probability that the entity is present within its limited domain and a set of "instantiation parameters" that may include the precise pose, lighting and deformation of the visual entity relative to an implicitly defined canonical version of that entity. When the capsule is working properly, the probability of the visual entity being present is locally invariant — it does not change as the entity moves over the manifold of possible appearances within the limited domain covered by the capsule. The instantiation parameters, however, are "equivariant" — as the viewing conditions change and the entity moves over the appearance manifold, the instantiation parameters change by a corresponding amount because they are representing the intrinsic coordinates of the entity on the appearance manifold."

The paragraph above is very dense, and it took me a while to figure out what it means, sentence by sentence. Below is my version of the above paragraph, as I understand it:

Artificial neurons output a single scalar. In addition, CNNs use convolutional layers that, for each kernel, replicate that same kernel's weights across the entire input volume and then output a 2D matrix, where each number is the output of that kernel's convolution with a portion of the input volume. So we can look at that 2D matrix as output of replicated feature detector. Then all kernel's 2D matrices are stacked on top of each other to produce output of a convolutional layer.

Not only can the CapsNet recognize digits, it can also generate them from internal representations. Source.

Then, we try to achieve viewpoint invariance in the activities of neurons. We do this by the means of max pooling that consecutively looks at regions in the above described 2D matrix and selects the largest number in each region. As result, we get what we wanted — invariance of activities. Invariance means that by changing the input a little, the output still stays the same. And activity is just the output signal of a neuron. In other words, when in the input image we shift the object that we want to detect by a little bit, networks activities (outputs of neurons) will not change because of max pooling and the network will still detect the object.

The above described mechanism is not very good, because max pooling loses valuable information and also does not encode relative spatial relationships between features. We should use capsules instead, because they will encapsulate all important information about the state of the features they are detecting in a form of a vector (as opposed to a scalar that a neuron outputs).

Capsules encapsulate all important information about the state of the feature they are detecting in vector form.

Capsules encode probability of detection of a feature as the length of their output vector. And the state of the detected feature is encoded as the direction in which that vector points to ("instantiation parameters"). So when detected feature moves around the image or its state somehow changes, the probability still stays the same (length of vector does not change), but its orientation changes.

Imagine that a capsule detects a face in the image and outputs a 3D vector of length 0.99. Then we start moving the face across the image. The vector will rotate in its space, representing the changing state of the detected face, but its length will remain fixed, because the capsule is still sure it has detected a face. This is what Hinton refers to as activities equivariance: neuronal activities will change when an object "moves over the manifold of possible appearances" in the picture. At the same time, the probabilities of detection remain constant, which is the form of invariance that we should aim at, and not the type offered by CNNs with max pooling.

How does a capsule work?

Let us compare capsules with artificial neurons. Table below summarizes the differences between the capsule and the neuron:

Important differences between capsules and neurons. Source: author, inspired by the talk on CapsNets given by naturomics.

Recall, that a neuron receives input scalars from other neurons, then multiplies them by scalar weights and sums. This sum is then passed to one of the many possible nonlinear activation functions, that take the input scalar and output a scalar according to the function. That scalar will be the output of the neuron that will go as input to other neurons. The summary of this process can be seen on the table and diagram below on the right side. In essence, artificial neuron can be described by 3 steps:

1. scalar weighting of input scalars

2. sum of weighted input scalars

3. scalar-to-scalar nonlinearity

Left: capsule diagram; right: artificial neuron. Source: author, inspired by the talk on CapsNets given by naturomics.

On the other hand, the capsule has vector forms of the above 3 steps in addition to the new step, affine transform of input:

1. matrix multiplication of input vectors

2. scalar weighting of input vectors

3. sum of weighted input vectors

4. vector-to-vector nonlinearity

Let's have a better look at the 4 computational steps happening inside the capsule.

1. Matrix Multiplication of Input Vectors

Input vectors that our capsule receives (u1, u2 and u3 in the diagram) come from 3 other capsules in the layer below. Lengths of these vectors encode probabilities that lower-level capsules detected their corresponding objects and directions of the vectors encode some internal state of the detected objects. Let us assume that lower level capsules detect eyes, mouth and nose respectively and out capsule detects face.

These vectors then are multiplied by corresponding weight matrices W that encode important spatial and other relationships between lower level features (eyes, mouth and nose) and higher level feature (face). For example, matrix W2j may encode relationship between nose and face: face is centered around its nose, its size is 10 times the size of the nose and its orientation in space corresponds to orientation of the nose, because they all lie on the same plane. Similar intuitions can be drawn for matrices W1j and W3j. After multiplication by these matrices, what we get is the predicted position of the higher level feature. In other words, u1hat represents where the face should be according to the detected position of the eyes, u2hat represents where the face should be according to the detected position of the mouth and u3hat represents where the face should be according to the detected position of the nose.

At this point your intuition should go as follows: if these 3 predictions of lower level features point at the same position and state of the face, then it must be a face there.

Predictions for face location of nose, mouth and eyes capsules closely match: there must be a face there. Source: author, based on original image.

2. Scalar Weighting of Input Vectors

At the first glance, this step seems very familiar to the one where artificial neuron weights its inputs before adding them up. In the neuron case, these weights are learned during backpropagation, but in the case of the capsule, they are determined using "dynamic routing", which is a novel way to determine where each capsule's output goes. I will dedicate a separate post to this algorithm and only offer some intuition here.

Lower level capsule will send its input to the higher level capsule that "agrees" with its input. This is the essence of the dynamic routing algorithm. Source.

In the image above, we have one lower level capsule that needs to "decide" to which higher level capsule it will send its output. It will make its decision by adjusting the weights C that will multiply this capsule's output before sending it to either left or right higher-level capsules J and K.

Now, the higher level capsules already received many input vectors from other lower-level capsules. All these inputs are represented by red and blue points. Where these points cluster together, this means that predictions of lower level capsules are close to each other. This is why, for the sake of example, there is a cluster of red points in both capsules J and K.

So, where should our lower-level capsule send its output: to capsule J or to capsule K? The answer to this question is the essence of the dynamic routing algorithm. The output of the lower capsule, when multiplied by corresponding matrix W, lands far from the red cluster of "correct" predictions in capsule J. On the other hand, it will land very close to "true" predictions red cluster in the right capsule K. Lower level capsule has a mechanism of measuring which upper level capsule better accommodates its results and will automatically adjust its weight in such a way that weight C corresponding to capsule K will be high, and weight C corresponding to capsule J will be low.

3. Sum of Weighted Input Vectors

This step is similar to the regular artificial neuron and represents combination of inputs. I don't think there is anything special about this step (except it is sum of vectors and not sum of scalars). We therefore can move on to the next step.

4. "Squash": Novel Vector-to-Vector Nonlinearity

Another innovation that CapsNet introduce is the novel nonlinear activation function that takes a vector, and then "squashes" it to have length of no more than 1, but does not change its direction.

Squashing nonlinearity scales input vector without changing its direction.

The right side of equation (blue rectangle) scales the input vector so that it will have unit length and the left side (red rectangle) performs additional scaling. Remember that the output vector length can be interpreted as probability of a given feature being detected by the capsule.

Graph of the novel nonlinearity in its scalar form. In real application the function operates on vectors. Source: author.

On the left is the squashing function applied to a 1D vector, which is a scalar. I included it to demonstrate the interesting nonlinear shape of the function.

It only makes sense to visualize one dimensional case; in real application it will take vector and output a vector, which would be hard to visualize.

Conclusion

In this part we talked about what the capsule is, what kind of computation it performs as well as intuition behind it. We see that the design of the capsule builds up upon the design of artificial neuron, but expands it to the vector form to allow for more powerful representational capabilities. It also introduces matrix weights to encode important hierarchical relationships between features of different layers. The result succeeds to achieve the goal of the designer: neuronal activity equivariance with respect to changes in inputs and invariance in probabilities of feature detection.

Summary of the internal workings of the capsule. Note that there is no bias because it is already included in the W matrix that can accommodate it and other, more complex transforms and relationships. Source: author.

The only parts that remain to conclude the series on the CapsNet are the dynamic routing between capsules algorithm as well as the detailed walkthrough of the architecture of this novel network. These will be discussed in the following posts.

Understanding Hinton's Capsule Networks. Part III: Dynamic Routing Between Capsules.

Part of Understanding Hinton's Capsule Networks Series:

Part I: Intuition
Part II: How Capsules Work
Part III: Dynamic Routing Between Capsules (you are reading it now)
Part IV: CapsNet Architecture

Quick announcement about our new publication AI³. We are getting the best writers together to talk about the Theory, Practice, and Business of AI and machine learning. Follow it to stay up to date on the latest trends.

Introduction

This is the third post in the series about a new type of neural network, based on capsules, called CapsNet. I already talked about the intuition behind it, as well as what is a capsule and how it works. In this post, I will talk about the novel dynamic routing algorithm that allows to train capsule networks.

One of the earlier figures explaining capsules and routing between them. Source.

As I showed in Part II, a capsule i in a lower-level layer needs to decide how to send its output vector to higher-level capsules j. It makes this decision by changing scalar weight c_ij that will multiply its output vector and then be treated as input to a higher-level capsule. Notation-wise, c_ij represents the weight that multiplies output vector from lower-level capsule i and goes as input to a higher level capsule j.

Things to know about weights c_ij:

1. Each weight is a non-negative scalar

2. For each lower level capsule i, the sum of all weights c_ij equals to 1

3. For each lower level capsule i, the number of weights equals to the number of higher-level capsules

4. These weights are determined by the iterative dynamic routing algorithm

The first two facts allow us to interpret weights in probabilistic terms. Recall that the length a capsule's output vector is interpreted as probability of existence of the feature that this capsule has been trained to detect. Orientation of the output vector is the parametrized state of the feature. So, in a sense, for each lower level capsule i, its weights c_ij define a probability distribution of its output belonging to each higher level capsule j.

Recall: computations inside of a capsule as described in Part II of the series. Source: author.

Dynamic Routing Between Capsules

So, what exactly happens during dynamic routing? Let's have a look at the description of the algorithm as published in the paper. But before we dive into the algorithm step by step, I want you to keep in your mind the main intuition behind the algorithm:

Lower level capsule will send its input to the higher level capsule that "agrees" with its input. This is the essence of the dynamic routing algorithm.

Now that we have this in mind, let's go through the algorithm line by line.

Dynamic routing algorithm, as published in the original paper.

The first line says that this procedure takes all capsules in a lower level l and their outputs u_hat, as well as the number of routing iterations r. The very last line tells you that the algorithm will produce the output of a higher level capsule v_j. Essentially, this algorithm tells us how to calculate forward passof the network.

In the second line you will notice that there is a new coefficient b_ij that we haven't seen before. This coefficient is simply a temporary value that will be iteratively updated and, after the procedure is over, its value will be stored in c_ij. At start of training the value of b_ij is initialized at zero.

Line 3 says that the steps in 4–7 will be repeated r times (the number of routing iterations).

Step in line 4 calculates the value of vector c_i which is all routing weights for a lower level capsule i. This is done for all lower level capsules. Why softmax? Softmax will make sure that each weight c_ij is a non-negative number and their sum equals to one. Essentially, softmax enforces probabilistic nature of coefficients c_ij that I described above.

At the first iteration, the value of all coefficients c_ij will be equal, because on line two all b_ij are set to zero. For example, if we have 3 lower level capsules and 2 higher level capsules, then all c_ij will be equal to 0.5. The state of all c_ij being equal at initialization of the algorithm represents the state of maximum confusion and uncertainty: lower level capsules have no idea which higher level capsules will best fit their output. Of course, as the process is repeated these uniform distributions will change.

After all weights c_ij were calculated for all lower level capsules, we can move on to line 5, where we look at higher level capsules. This step calculates a linear combination of input vectors, weighted by routing coefficients c_ij, determined in the previous step. Intuitively, this means scaling down input vectors and adding them together, which produces output vector s_j. This is done for all higher level capsules.

Next, in line 6 vectors from last step are passed through the squash nonlinearity, that makes sure the direction of the vector is preserved, but its length is enforced to be no more than 1. This step produces the output vector v_j for all higher level capsules.

Dot product is an operation that takes 2 vectors and outputs a scalar. There are several scenarios possible for the two vectors of given lengths but different relative orientations: (a) largest positive possible values; (b) positive dot product; (c) zero dot product; (d) negative dot product; (e) largest possible negative dot product. You can think of the dot product as a measure of similarity in the context of CapsNets. Source: author.

To summarize what we have so far: steps 4–6 simply calculate the output of higher level capsules. Step on line 7 is where the weight update happens. This step captures the essence of the routing algorithm. This steps looks at each higher level capsule j and then examines each input and updates the corresponding weight b_ij according to the formula. The formula says that the new weight value equals to the old value plus the dot product of current output of capsule j and the input to this capsule from a lower level capsule i. The dot product looks at similarity between input to the capsule and output from the capsule. Also, remember from above, the lower level capsule will sent its output to the higher level capsule whose output is similar. This similarity is captured by the dot product. After this step, the algorithm starts over from step 3 and repeats the process r times.

After r times, all outputs for higher level capsules were calculated and routing weights have been established. The forward pass can continue to the next level of network.

Intuitive Example of Weight Update Step

Two higher level capsules with their outputs represented by purple vectors, and inputs represented by black and orange vectors. Lower level capsule with orange output will decrease the weight for higher level capsule 1 (left side) and increase the weight for higher level capsule 2 (right side). Source: author.

In the figure on the left, imagine that there are two higher level capsules, their output is represented by purple vectors v1 and v2 calculated as described in previous section. The orange vector represents input from one of the lower level capsules and the black vectors represent all the remaining inputs from other lower level capsules.

We see that in the left part the purple output v1 and the orange input u_hatpoint in the opposite directions. In other words, they are not similar. This means their dot product will be a negative number and as result routing coefficient c_11 will decrease. In the right part, the purple output v2 and the orange input v_hat point in the same direction. They are similar. Therefore, the routing coefficient c_12 will increase. This procedure is repeated for all higher level capsules and for all inputs of each capsule. The result of this is a set of routing coefficients that best matches outputs from lower level capsules with outputs of higher level capsules.

How Many Routing Iterations to Use?

The paper examined a range of values for both MNIST and CIFAR data sets. Author's conclusion is two-fold:

1. More iterations tends to overfit the data

2. It is recommended to use 3 routing iterations in practice

Conclusion

In this article, I explained the dynamic routing algorithm by agreement that allows to train the CapsNet. The most important idea is that similarity between input and output is measured as dot product between input and output of a capsule and then routing coefficient is updated correspondingly. Best practice is to use 3 routing iterations.

In the next post, I will walk you through CapsNet architecture, where we will put together all pieces of the puzzle that we learned so far.