Learning to compute inner consensus: A novel approach to modeling agreement between Capsules
Gonçalo Faria


headings






Learning to compute inner consensus










G. Faria

Instituto Superior Técnico
 Lisboa, Portugal 


Learning to compute inner consensus 
 A novel approach to modeling agreement between CapsulesSupported by Calouste Gulbenkian Foundation
    Gonçalo Faria 
 goncalorafaria@tecnico.ulisboa.pt
    
========================================================================================================================================





    This project considers Capsule Networks, a recently introduced machine learning model that has shown promising results regarding generalization and preservation of spatial information with few parameters. 
    The Capsule Network's inner routing procedures thus far proposed, a priori, establish how the routing relations are modeled, which limits the expressiveness of the underlying model. 
    In this project, I propose two distinct ways in which the routing procedure can be learned like any other network parameter. 





§ INTRODUCTION


Starting with the developments made by Frank Rosenblatt surrounding the Perceptron algorithm <cit.>, 
innovative techniques have marked the beginning of a new, biologically inspired, approach in Artificial Intelligence that is, surprisingly, better suited to deal with naturally unstructured data.

The now called field of Deep Learning has expanded these ideas by creating models that stack multiple layers of Perceptrons. These Multilayer Perceptrons, commonly known as Neural Networks, achieve greater representation capacity, due to the layered manner the computational complexity is added, especially when compared with its precursor. Attributable to this compositional approach they are especially hard-wired to learn a nested hierarchy of concepts. 

Aided by the increase in computational power as well as efforts to collect high quality labeled data, in the last decade, a particular subset of Neural Networks, called Convolutional Neural Networks(CNN) <cit.>, have accomplished remarkable results <cit.>. As their common trait, having to deal with high dimension unstructured data, computer vision <cit.>, speech recognition <cit.>, natural language processing <cit.>, machine translation <cit.> and medical image analysis <cit.> are the fields in which these models have shown greater applicability.

Colloquially, a CNN as presented by Yann LeCun and others, is a model that uses multiple layers of feature detectors that have local receptive fields and shared parameters interleaved with sub-sampling layers <cit.>. 
For attaining translation invariance, by design, these sub-sampling layers discard spatial information <cit.>, which, when applied to the classification task, assist in amplifying the aspects of its input that are useful for discriminating and suppress irrelevant variations that are not.

Translation invariance, 
however helpful in attaining a model that has the same classification when applied to entities in different viewpoints, 
inevitably requires training on lots of redundant data. 
This redundancy is artificially introduced to force the optimization process to find solutions that can not distinguish between different viewpoints of the same entity. 
Additionally, disregarding spatial information produces models incapable of dealing with recognition tasks, 
such as facial identity recognition, that require knowledge of the precise spatial relationships between high-level parts, like a nose or a mouth. 

To address these drawbacks, adaptations on CNNs  have been proposed. 
This project focuses on improving an existing equivariant approach, 
introduced by Sara Sabour, Geoffrey E. Hinton and Nicholas Frosst, 
called Capsule Networks <cit.>.

The Capsule Network model proposed by Sabour et al. <cit.> uses, layer wise, dynamic routing. 
Since dynamic routing is a sequential extremely computationally expensive procedure, 
if the network were to be scaled, in order to be suited to solve more challenging datasets, 
would incur in overly expensive costs in training and inference time. 
Furthermore, when applied to many capsules, 
the gradient flow through the dynamic routing computations is dampened. 
This inhibits learning, regardless of the computational resources used. 
Additionally, both dynamic routing as well as other routing procedures proposed, 
a priori, establish the way in which the routing relations are modeled, which limits the expressiveness of the underlying model. 

In this work, I propose two distinct ways in which the routing procedure can be discriminatively learned. 
In parallel with <cit.>, 
I employ routing to local receptive fields with parameter sharing, 
in order to reduce vanishing gradients, 
take advantage of the fact that correlated capsules tend to concentrate in local regions and reduce the number of model parameters.



§ RELATED WORK


Capsules were first introduced in <cit.>, whereas the logic of encoding instantiation parameters was
established in a transforming autoencoder.

More recently, further work on capsules <cit.> garnered
some attention achieving state-of-the-art performance on MNIST, with a shallow Capsule Network
using an algorithm named Dynamic routing.

Shortly thereafter, a new routing algorithm, based on an Expectation-Maximization extension applied to a Gaussian Mixing Model, was proposed in <cit.>.
Additionally, capsule vectors were replaced by matrices to reduce the number of parameters and also convolutional capsules were introduced. 
State-of-the-art performance was achieved on the smallNORB dataset using a relatively small Capsule Network.

An analysis of Dynamic routing algorithm as an optimization problem was presented in <cit.> as  well as a discussion of possible ways to improve Capsule Networks.
Furthermore, researchers have proposed several extentions <cit.> showing that there is still room for improvement.



§  CAPSULE NETWORKS 


In parallel with a neural network, a Capsule Network <cit.> is, in essence, multiple levels of capsule layers which, in part, are composed of various capsules. 
A capsule is a group of artificial neurons which learns to recognise an implicitly defined entity, in the network’s input, and outputs a tensor representation, the pose, which captures the properties of that entity relative to an implicitly defined canonical version and an activation probability. The activation probability was designed to express the presence of the entity the capsule represents in the network’s input. In the high-level capsules this activation probability corresponds to the inter-class invariant discriminator used for classification.
Moreover, every capsule’s pose is equivariant, meaning that as the entity moves over the appearance manifold, the pose moves by a corresponding amount.  

Every capsule layer is either calculated from multiple feature maps, when they correspond to the primary capsule layer, or by a series of transformations, followed by a mechanism called routing, applied to the outputs of the previous capsule layer.

Disentangling the internal representations in viewpoint invariant, presence probability and viewpoint equivariant, instantiation parameters may prove to be a more generalizable approach for representing knowledge than the conventional CNN view, that only strives for representational invariance. Early evidence of this has been revealed by experimenting on the effects of varying individual components of the individual capsules. The MNIST trained network presented in <cit.>, without being explicitly designed to, learned to capture properties such as stroke, width and skew.  In addition to this, as mentioned  by Hinton and others <cit.>, the same network, despite never being trained with digits, that were subject to affine transformations, was able to accurately classify them during test time, which seems to suggest greater generalization capacity when in comparison with conventional CNNs. 



 §.§ Routing Procedure



Routing consists of a dot-product self-attention <cit.> procedure that assigns, for each output capsule, a distribution of compatibility probabilities to the transformed previous layer's capsules, the capsule votes. These compatibility probabilities, after multiplied to corresponding capsule votes are combined and result in the output capsule's pose. Furthermore, the routing procedure also assigns the activation probability to the respective output capsule, usually based on the amount of agreement between the votes with higher compatibility probabilities.

This procedure provides the framework for a consensus mechanism in the multi-layer capsule hierarchy, which, for the higher levels of the input’s domain, will solve the problem of assigning parts to wholes.
Additionally, it can be applied to local receptive fields with shared transformation matrices. Figure <ref> contains a diagram representing how routing is applied convolutionally in one dimension. The 2D and 3D convolutional routing is extrapolated in the same manner as the usual 2D and 3D convolution would.



The vote transformations are traditionally linear transformations. 
However, due to some stability issues that occur during training, equation <ref>, proposed by <cit.>, will be used instead. The capsule vote from the ith input capsule to the jth output capsule is obtained by multiplying the matrix W_ij to the pose of the ith input capsule P_i divided by the frobenius norm of W_ij.
 

    v_ij =   W_ij/ W_ij_ℱ P_i


In algorithm <ref>, I present a generalization of the routing procedure that encompasses most of the routing algorithms proposed. The definition of the activation and compatibility functions is what caracterizes the particular routing procedure. 






§ LEARNING THE ROUTING PROCEDURE

In hopes of improving the performance of Capsule Networks and of incorporating routing into the whole training process, instead of designing an alternative routing procedure, 
that necessarily constrains the parts to whole relationships that can be modeled, 
I present methods for parameterizing it, such that, 
either for each layer or each network, the routing procedure itself can be discriminatively learned like any other model parameter. 

In the following subsections I present two distinct alternatives. 
The first one exposes routing as a classic clustering algorithm based on the application of parametric kernel functions.
The second takes a less structured approach that defines the activation and compatibility functions simply as neural networks. 




 §.§ Similarity Learning Approach



Since for each input, in every output capsule, 
the routing computations are reminiscent of an agglomerative fuzzy clustering algorithm, 
following the avenue taken in <cit.>, in this subsection, routing it’s analyzed as the optimization of a clustering-like objective function. The resulting cluster is interpreted as the agreement over the capsule votes and is used as the routing procedure's output capsule's pose.
Similarly with <cit.> I propose <ref>, inspired by the algorithm presented in <cit.>.


    minℒ(C,μ) = - ∑_i=1^n c_i ⟨μ , v_i ⟩_θ + λ_1 D_KL(C∥ U) + λ_2 D_KL(C∥ A)


subject to


    ∑_i=1^n c_i = 1, c_i ∈ [0,1 ], 1 ≤ i ≤ n

where ⟨· , ·⟩_θ is a kernel function defined by θ, μ is the output capsule's pose, v_i, a_i and c_i are, respectively, 
the ith input capsule vote, its activation and compatibility probability. A = [a_i] and C = [c_i] are vectors of n components. 
The compatibility probability corresponds to the weight of the ith input capsule vote has in 
the output capsule's pose. The parameters λ_1 and λ_2, which are both positive or equal to zero, are the weights of the penalty terms applied to C. The symbol U denotes the uniform distribution.

The first term in the objective function is the weighted average of the similarity between the output pose and the ith input votes. 
The weights are the compatibility probabilities. 
In this way, the more compatible an input capsule is the more significant its vote similarity is in the optimization process. 
The remaining terms are penalty terms weighted by λ_1 and λ_2. The second term, as in <cit.>, 
is proportional to the Kullback–Leibler(KL) divergence<cit.> of the compatibility probabilities 
and the uniform distribution. Additionally, the third term is proportional to the KL diverge between the compatibility probabilities and 
the activations. In other words, the expectation of the logarithmic difference between the A and C, where the expectation 
is taken with respect to C.
The penalty terms were introduced in order to pay, independently, both for the nonalignment between the 
activations and compatibility probabilities aswell as the nonuniformity of the compatibility probabilities.

The minimization problem is solved by partially optimizing ℒ(C,μ) for C and μ.

    For a fixed C, μ is updated as 
    

    μ = ∑_i=1^n c_i v_i


For a fixed μ, C is updated as follows: Using the Lagrangian multiplier technique, 
We obtain the unconstrained minimization problem <ref>.


    ℒ̃(C,α) = - ∑_i=1^n c_i ⟨μ , v_i ⟩_θ +  λ_1 D_KL(C∥ U) + λ_2 D_KL(C∥ A) - α (∑_i=1^n c_i - 1), λ_2 >= 0, λ_1 >= 0

where α is the Lagrangian multiplier. 
If (Ĉ,α̂) is a minimizer of ℒ̃(C,α) then the gradient must be zero. Thus,
    
 
    ∂ℒ̃(Ĉ,α̂)/∂ c_i = - ⟨μ , v_i ⟩_θ + (λ_1 +λ_2 )( 1 + log ĉ_̂î) - λ_2 log a_i - α̂ = 0, 1≤ i ≤ n
   

and


    ∂ℒ̃(Ĉ,α̂)/∂α = ∑_i=1^nĉ_̂î - 1 = 0


From <ref>, we obtain


    ĉ_̂î =  exp( ⟨μ , v_i ⟩_θ/λ_1+λ_2) exp( α̂/λ_1+λ_2 ) a_i^λ_2/λ_1+λ_2  exp(-1), 1 ≤ i ≤ n


By substituting <ref> into <ref>, we have
    

    ∑_i=1^nĉ_̂î =exp(-1) exp( α̂/λ_1+λ_2 ) ∑_i=1^n exp( ⟨μ , v_i ⟩_θ/λ_1+λ_2) a_i^λ_2/λ_1+λ_2 = 1

which, when solved for α̂, results in


    α̂ = (λ_1+λ_2)log 1/ exp(-1) ∑_j = 1^ exp(⟨μ , v_j ⟩_θ/λ_1+λ_2 ) a_j^λ_2/λ_1+λ_2


It follows that by substituting <ref> into <ref>, leading to


    ĉ_̂î =  a_i^λ_2/λ_1+λ_2 exp( ⟨μ , v_i ⟩_θ/λ_1+λ_2) /∑_j=1^n a_j^λ_2/λ_1+λ_2 exp( ⟨μ , v_j ⟩_θ/λ_1+λ_2) , 1 ≤ i ≤ n

and C can be updated by <ref>.

Figure <ref>, contains an illustrative example, applied to a toy dataset,
of the derived clustering algorithm for different pairs of λ_1 and λ_2. 



Applied to the general routing procedure framework, presented in algorithm <ref>, 
we can take the compatibility function to be equation <ref>.


    compatibility_θ,λ_1,λ_2(V, a_i, μ,γ, s_i) ≐ (  a_i^λ_2/λ_1+λ_2 exp( ⟨μ , v_i ⟩_θ/λ_1 + λ_2) /∑_j ∈γ^ a_j^λ_2/λ_1+λ_2 exp( ⟨μ , v_j ⟩_θ/λ_1 + λ_2) , s_i )


In this way, we obtain a compatibility function that is parameterized by θ, λ_1 and λ_2 which are learned discriminatively using back-propagation during the training process of the entire capsule network.
The remaining function for the definition of the routing procedure is the activation which is present in <ref>.


    activation_β(μ, V, C, γ) ≐ sigmoid( β_1 ∑_i ∈γ^ c_i ⟨μ , v_i ⟩_θ - β_2 D_KL(C∥ A) + β_3 ), β_2 ≥ 0, β_1 ≥ 0


In the context of convolutional routing, λ_1, λ_2, β_1, β_2, 
and β_3 are distinct for each channel in every convolutional routing layer. 
The parameters of the kernel function could either be shared across convolutional channel or layer, 
in the following sections, we assume they only shared across layers.



 §.§ Connectionist Approach



An alternative approach to the more formal presented in the previous subsection, to modeling the routing procedure, 
is to allow the activation and compatibility functions in Algorithm <ref> to be Neural Networks. 
More precisely I employed a LSTM cell <cit.>, which is designed to keep track of arbitrary long-term dependencies, 
in conjunction with two distinct neural networks to obtain a learnable routing mechanism that plays an active role throughout the iterations.

Figure <ref> presents a diagram of the LSTM cell employed. 
The input of the cell is a concatenation of the previous iteration intermediate output capsule pose μ, 
the capsule vote from the ith input capsule v_i and the corresponding compatibility probabilities c_i and the activation a_i. 
After initialized with zeros(s_0 = 0), 
the cell state s_i^t and hidden state h_i^t are updated throughout the iterations to obtain representations that are subsequently fed to two distinct neural networks.

The neural network f_θ is applied to the outputs of the hidden state to produce the compatibility probabilities at the end of every iteration. 
Eventually, at the end of the iterative process, the cell states, correspondent to every input capsule, after combined, 
are fed to the neural network g_β and result in the output capsule's final activation as indicated by <ref>.
The definition of the compatibility function is presented in algorithm <ref>.


    activation_β(C, γ, S^t) ≐ g_β ( ∑_i ∈γ^ c_i s^t_i )



The parameters from the LSTM and both neural networks are shared across every single input capsule. 
Additionally, the dimension of the LSTM's cell state and hidden state, as well as the architectures of the neural networks used, 
become hyperparameters.




§ EXPERIMENTS

In order to evaluate the effectiveness of the proposed routing algorithms, when compared with the extension of Expectation-Maximization(EM) applied to a Gaussian Mixture Model, introduced in <cit.>, 
experiments were conducted in both MNIST dataset <cit.> and smallNORB <cit.>.
They consist in training the same Capsule Network architecture, for 100 epochs, with every routing procedure running for three iterations, for both of the proposed algorithms and the one present in <cit.> and comparing the respective test set results. 

The MNIST dataset was selected, in the early stages, as proof of concept. 
It is a large database of handwritten digits that has become the classic benchmark for machine learning models. 
The training set is composed of 60000 examples and the test set 10000.

The smallNORB dataset was chosen due to it being much closer to natural images and yet devoid of context and color.
It is composed of 50 toys belonging to 5 generic categories(four-legged animals, human figures, airplanes, trucks, and cars).  
The objects were imaged by two cameras under 6 lighting conditions, 9 elevations (30 to 70 degrees every 5 degrees), 
and 18 azimuths (0 to 340 every 20 degrees). Figure <ref> contain some sampled examples of the dataset.
The training set is composed of 5 instances of each category(24300 examples), and the test set of the remaining 5 instances(24300 examples).

For the experiments with smallNORB, this dataset was preprocessed precisely in the same manner as in <cit.>. 
The images were normalized and downsampled to 48 × 48. 
During training, they were randomly cropped into 32 × 32 patches and random brightness and contrast were added. 
During test and validation, however, each crop was correspondent to the center of the image. 




All the experiments where made using a Tensorflow <cit.> implementation of the underlying models [https://github.com/goncalorafaria/learning-inner-consensus]. 
The optimizer used was Adam <cit.> with a learning rate of 3-e3 scheduled by an exponential decay.
Additionally, the models were trained using kaggle notebooks, approximately 40 hours each, a free research tool for machine learning that provides a Tesla P100 Nvidia GPU as part of an accelerated computing environment.

Apart from the implementation of the routing procedure, all of the models contained in the experiments instantiate the Capsule Network architecture present in Table <ref> and use 4x4 matrices as poses. 
The model is a slight modification of the smaller Capsule Network used in <cit.>. 
More precisely, after the initial convolutions batch normalization <cit.> is applied, and the transformation used is the one described in equation <ref>. 
Applied to smallNORB, the model has 86K parameters, excluding the ones pertaining to the different routing procedures.






The model present in table <ref> contains three layers to which routing is applied.
When used in the described experiments, the routing algorithm presented in section <ref>, used the hyperparameters described in table <ref>. 
Moreover, the routing algorithm presented in section <ref> used the kernel defined in equation <ref>, a combination of gaussian kernels<cit.>. The first two layers in the Capsule Network have Q = 4 and the last one has Q = 10.


    ⟨ x , x' ⟩_θ≐∑^Q_q=1θ^q_1 exp( -  x - x' ^2/ 2(θ^q_2)^2  )

The choice of routing hyperparameters was based on making the routing procedure in the deeper layers have more parameters. 
What motivated this design choice was the intuition that, the more complex the features, further complex needed to be the routing.
Ideally, if there were not computational limitations, these parameters would have been chosen using a randomized grid search with cross-validation or other more suitable hyperparameter search method.




The results pertaining to all of the experiments are contained in table <ref>.
The table contains the percentual error rate achieved in the evaluation of the models.


§ DISCUSSION


The results we obtained on smallNORB are far from the ones reported by <cit.>.
However, when in comparison with the best open-source versions, the same does not hold. 
I speculate that the original authors did not present all of the needed implementation details, 
which would indeed explain the observed discrepancy.
When in comparision with the best open-source versions, 
the Connectionist approach is on par or surpasses them while the Similarity Learning approach does not.

The main challenge I encountered while fitting the models was the computational time required. 
Although the convolutional Capsule networks require less floating-point operations and fewer training parameters, 
than any comparable CNN, they are much slower and ran out of memory with relatively small models. 
This is due to Tensorflow beeing optimized for CNNs, 
and not having natively the operations required to compute the Capsule's routing convolutions. 
To compute the routing Convolutions, for each native TensorFlow operation employed, 
TensorFlow's functional API makes a copy of the underlying tensors, which greatly increases the memory requirements. 



§ CONCLUSION

In this paper, 
I have presented two distinct ways to learn Capsule Network's inner routing mechanism using backpropagation.
The Similarity Learning and the Connectionist approach.
The proposed methods build on the work of <cit.> and <cit.> 
by augmenting the part whole relationships that can be modeled.

The experimental results show that the Connectionist approach is on par or surpasses
with the best open-source implementations of Capsule Networks using EM while the Similarity Learning does not.
When in comparison with the original paper, with EM routing, the results of the introduced approaches fall short.
I suspect this is due to missing implementation details that are not mentioned in the original paper. 
When these are made available, 
I expect the results from the routing mechanisms proposed to considerably improve.

Future work will focus on additional applications, of the proposed extension of capsule networks, 
in different domains and computer vision tasks, 
experiment with distinct kernel parameters for distinct convolutional channels, 
and study the interpretability of the proposed models.
Particularly, for applications in object detection tasks, 
I intend to use the capsule poses of the last layer to more effectively identify the location of bounding boxes.
The study of the interpretability of the proposed models will be
aimed at facilitating model building and present mechanisms for verifying the usefulness of the model predictions. 
Aditionally, I intend to augment the Similarity learning approach to more general divergence functions such as the Jensen–Tsallis divergence.




ACKNOWLEDGMENTS A special thank you to the Gulbenkian Foundation, the scientific committee of the Artificial Intelligence Program and this project's tutor Professor Cesar Analide. 
Addittionally, I would also like to thank the reviewers for their
constructive comments which helped to improve the proposed methodology.

splncs



