Capsule networks are constrained by the parameter-expensive nature of their layers, and the general lack of provable equivariance guarantees. We present a variation of capsule networks that aims to remedy this. We identify that learning all pair-wise part-whole relationships between capsules of successive layers is inefficient. Further, we also realise that the choice of prediction networks and the routing mechanism are both key to equivariance. Based on these, we propose an alternative framework for capsule networks that learns to projectively encode the manifold of pose-variations, termed the space-of-variation (SOV), for every capsule-type of each layer. This is done using a trainable, equivariant function defined over a grid of group-transformations. Thus, the prediction-phase of routing involves projection into the SOV of a deeper capsule using the corresponding function. As a specific instantiation of this idea, and also in order to reap the benefits of increased parameter-sharing, we use type-homogeneous group-equivariant convolutions of shallower capsules in this phase. We also introduce an equivariant routing mechanism based on degree-centrality. We show that this particular instance of our general model is equivariant, and hence preserves the compositional representation of an input under transformations. We conduct several experiments on standard object-classification datasets that showcase the increased transformation-robustness, as well as general performance, of our model to several capsule baselines. The hierarchical component-structure of visual objects motivates their description as instances of class-dependent spatial grammars. The production-rules of such grammars specify this structure by laying out valid type-combinations for components of an object, their inter-geometry, as well as the behaviour of these with respect to transformations on the input. A system that aims to truly understand a visual scene must accurately learn such grammars for all constituent objects -in effect, learning their aggregational structures. One means of doing so is to have the internal representation of a model serve as a component-parsing of an input across several semantic resolutions. Further, in order to mimic latent compositionalities in objects, such a representation must be reflective of detected strengths of possible spatial relationships. A natural structure for such a representation is a parse-tree whose nodes denote components, and whose weighted parent-child edges denote the strengths of detected aggregational relationships. Capsule networks (Hinton et al., 2011) , (Sabour et al., 2017) are a family of deep neural networks that aim to build such distributed, spatially-aware representations in a multi-class setting. Each layer of a capsule network represents and detects instances of a set of components (of a visual scene) at a particular semantic resolution. It does this by using vector-valued activations, termed 'capsules'. Each capsule is meant to be interpreted as being representative of a set of generalised pose-coordinates for a visual object. Each layer consists of capsules of several types that may be instantiated at all spatial locations depending on the nature of the image. Thus, given an image, a capsule network provides a description of its components at various 'levels' of semantics. In order that this distributed representation across layers be an accurate component-parsing of a visual scene, and capture meaningful and inherent spatial relationships, deeper capsules are constructed from shallower capsules using a mechanism that combines backpropagation-based learning, and consensus-based heuristics. Briefly, the mechanism of creating deeper capsules from a set of shallower capsules is as follows. Each deeper capsule of a particular type receives a set of predictions for its pose from a local pool of shallower capsules. This happens by using a set of trainable neural networks that the shallower capsules are given as input into. These networks can be interpreted as aiming to capture possible part-whole relationships between the corresponding deeper and shallower capsules. The predictions thus obtained are then combined in a manner that ensures that the result reflects agreement among them. This is so that capsules are activated only when their component-capsules are in the right spatial relationship to form an instance of the object-type it represents. The agreement-based aggregation described just now is termed 'routing'. Multiple routing algorithms exist, for example dynamic routing (Sabour et al., 2017) , EM-routing (Hinton et al., 2018) , SVD-based routing (Bahadori, 2018) , and routing based on a clustering-like objective function (Wang & Liu, 2018) . Based on their explicit learning of compositional structures, capsule networks can be seen as an alternative (to CNNs) for better learning of compositional representations. Indeed, CNN-based models do not have an inherent mechanism to explicitly learn or use spatial relationships in a visual scene. Further, the common use of layers that enforce local transformation-invariance, such as pooling, further limit their ability to accurately detect compositional structures by allowing for relaxations in otherwise strict spatial relations (Hinton et al., 2011) . Thus, despite some manner of hierarchical learning -as seen in their layers capturing simpler to more complex features as a function of depth -CNNs do not form the ideal representational model we seek. It is our belief that capsule-based models may serve us better in this regard. This much said, research in capsule networks is still in its infancy, and several issues have to be overcome before capsule networks can become universally applicable like CNNs. We focus on two of these that we consider as fundamental to building better capsule network models. First, most capsule-network models, in their current form, do not scale well to deep architectures. A significant factor is the fact that all pair-wise relationships between capsules of two layers (upto a local pool) are explicitly modelled by a unique neural network. Thus, for a 'convolutional capsule' layer -the number of trainable neural networks depends on the product of the spatial extent of the windowing and the product of the number of capsule-types of each the two layers. We argue that this design is not only expensive, but also inefficient. Given two successive capsule-layers, not all pairs of capsule-types have significant relationships. This is due to them either representing object-components that are part of different classes, or being just incompatible in compositional structures. The consequences of this inefficiency go beyond poor scalability. For example, due to the large number of prediction-networks in this design, only simple functions -often just matrices -are used to model part-whole relationships. While building deep capsule networks, such a linear inductive bias can be inaccurate in layers where complex objects are represented. Thus, for the purpose of building deeper architectures, as well as more expressive layers, this inefficiency in the prediction phase must be handled. The second issue with capsule networks is more theoretical, but nonetheless has implications in practice. This is the lack, in general, of theoretical guarantees on equivariance. Most capsule networks only use intuitive heuristics to learn transformation-robust spatial relations among components. This is acceptable, but not ideal. A capsule network model that can detect compositionalities in a provablyinvariant manner are more useful, and more in line with the basic motivations for capsules. Both of the above issues are remedied in the following description of our model. First, instead of learning pair-wise relationships among capsules, we learn to projectively encode a description of each capsule-type for every layer. This we do by associating each capsule-type with a vector-valued function, given by a trainable neural network. This network assumes the role of the prediction mechanism in capsule networks. We interpret the role of this network as a means of encoding the manifold of legal pose-variations for its associated capsule-type. It is expected that, given proper training, shallower capsules that have no relationship with a particular capsule-type will project themselves to a vector of low activation (for example, 2-norm), when input to the corresponding network. As an aside, it is this mechanism that gives the name to our model. We term this manifold the 'space-of-variation' of a capsule-type. Since, we attempt to learn such spaces at each layer, we name our model 'space-of-variation' networks (SOVNET). In this design, the number of trainable networks for a given layer depend on the number of capsule-types of that layer. As mentioned earlier, the choice of prediction networks and routing algorithm is important to having guarantees on learning transformation-invariant compositional relationships. Thus, in order to ensure equivariance, which we show is sufficient for the above, we use group-equivariant convolutions (GCNN) (Cohen & Welling, 2016) in the prediction phase. Thus, shallower capsules of a fixed type are input to a GCNN associated with a deeper capsule-type to obtain predictions for it. Apart from ensuring equivariance to transformations, GCNNs also allow for greater parameter-sharing (across a set of transformations), resulting in greater awareness of local object-structures. We argue that this could potentially improve the quality of predictions when compared to isolated predictions made by convolutional capsule layers, such as those of (Hinton et al., 2018) . The last contribution of this paper is an equivariant degree-centrality based routing algorithm. The main idea of this method is to treat each prediction for a capsule as a vertex of a graph, whose weighted edges are given by a similarity measure on the predictions themselves. Our method uses the softmaxed values of the degree scores of the affinity matrix of this graph as a set of weights for aggregating predictions. The key idea being that predictions that agree with a majority of other predictions for the same capsule get a larger weight -following the principle of routing-by-agreement. While this method is only heuristic in the sense of optimality, it is provably equivariant and preserves the capsule-decomposition of an input. We summarise the contributions of this paper in the following: 1. A general framework for a scalable capsule-network model. A number of insights can be drawn from an observation of the accuracies obtained from the experiments. First, the most obvious, is that SOVNET is significantly more robust to train and test-time geometric transformations of the input. Indeed, SOVNET learns to use even extreme transformations of the training data and generalises better to test-time transformations in a majority of the cases. However, in certain splits, some baselines perform better than SOVNET. These cases are briefly discussed below. On the CIFAR-10 experiments, DeepCaps performs significantly better than SOVNET on the untransformed case -generalising to test-time transformations better. However, SOVNET learns from train-time transformations better than DeepCaps -outperforming it in a large majority of the other cases. We hypothesize that the first observation is due to the increased (almost double) number of parameters of DeepCaps that allows it to learn features that generalise better to transformations. Further, as p4-convolutions (the prediction-mechanisms used) are equivariant only to rotations in multiples of 90°, its performance is significantly lower for test-time transformations of 30°and 60°for the untransformed case. However, the equivariance of SOVNET allows it to learn better from train-time geometric transforms than DeepCaps, explaining the second observation. The second case is that GCaps outperforms SOVNET on generalising to extreme transformations on (mainly) MNIST, and once on FashionMNIST, under mild train-time conditions. However, it is unable to sustain this under more extreme train-time perturbations. We infer that this is caused largely by the explicit geometric parameterisation of capsules in G-Caps. While under mild-tomoderate train-time conditions, and on simple datasets, this approach could yield better results, this parameterisation, especially with very simple prediction-mechanisms, can prove detrimental. Thus, the convolutional nature of the prediction-mechanisms, which can capture more complex features, and also the greater depth of SOVNET allows it to learn better from more complex training scenarios. This makes the case for deeper models with more expressive and equivariant prediction-mechanisms. A related point of interest is that G-Caps performs very poorly on the CIFAR-10 dataset -achieving the least accuracy on most cases on this dataset -despite provable guarantees on equivariance. We argue that this is significantly due to the nature of the capsules of this model itself. In GCaps, each capsule is explicitly modelled as an element of a Lie group. Thus, capsules capture exclusively geometric information, and use only this information for routing. In contrast, other capsule models have no such parameterisation. In the case of CIFAR-10, where non-geometric features such as texture are important, we see that purely spatio-geometric based routing is not effective. This observation allows us to make a more general hypothesis that could deal with the fundamentals of capsule networks. We propose a trade-off in capsule networks, based on the notion of equivariance. To appreciate this, some background is necessary on both equivariance and capsule networks. As the body of literature concerning equivariance is quite vast, we only mention a relevant selection of papers. Equivariance can be seen as a desirable, if not fundamental, inductive bias for neural networks used in computer vision. Indeed, the fact that AlexNet (Krizhevsky et al., 2012) automatically learns representation that are equivariant to flips, rotation and scaling shows the importance of equivariance as well as its natural necessity (Lenc & Vedaldi, 2015) . Thus, a neural network model that can formally guarantee this property is essential. An early work in this regard is the group-equivariant convolution proposed in (Cohen & Welling, 2016) . There, the authors proposed a generalisation of the 2-D spatial convolution operation to act on a general group of symmetry transforms -increasing the parameter-sharing and, thereby, improving performance. Since then, several other models exhibiting equivariance to certain groups of transformations have been proposed, for example (Cohen et al., 2018b) , where a spherical correlation operator that exhibits rotationequivariance was introduced; (Carlos Esteves & Daniilidis, 2017) , where a network equivariant to rotation and scale, but invariant to translations was presented, and Worrall & Brostow (2018) , where a model equivariant to translations and 3D right-angled rotations was developed. A general theory of equivariant CNNs was developed in (Cohen et al., 2018a) . In their paper, they show that convolutions with equivariant kernels are the most general class of equivariant maps between feature spaces. A fundamental issue with group-equivariant convolutional networks is the fact that the grid the convolution works with increases exponentially with the type of the transformations considered. This was pointed out in (Sabour et al., 2017) ; capsules were proposed as an efficient alternative. In a general capsule network model, each capsule is supposed to represent the pose-coordinates of an object-component. Thus, to increase the scope of equivariance, only a linear increase in the dimension of each capsule is necessary. This was however not formalised in most capsule architectures, which focused on other aspects such as routing (Hinton et al., 2018) , (Bahadori, 2018) , (Wang & Liu, 2018) ; general architecture , (Deliège et al., 2018) , (Rawlinson et al., 2018) , Jeong et al. (2019) , (Phaye et al., 2018) , Rosario et al. (2019) ; or application Afshar et al. (2018) . It was only in group-equivariant capsules (Lenssen et al., 2018 ) that this idea of efficient equivariance was formalised. Indeed, in that paper, equivariance changed from preserving the action of a group on a vector space to preserving the group-transformation on an element. While such models scale well to larger transformation groups in the sense of preserving equivariance guarantees, we argue that they cannot efficiently handle compositionalities that involve more than spatial geometry. The direct use of capsules as geometric pose-coordinates could lead to exponential representational inefficiencies in the number of capsules. This is the tradeoff we referred to. We do not attempt a formalisation of this, and instead make the observation given next. While SOVNET (using GCNNs) lacks in transformational efficiency, the use of convolutions allows it to capture non-geometric structures well. Further, SOVNET still retains the advantage of learning compositional structures better than CNN models due to the use of routing, placing it in a favourable position between two extremes. We presented a scalable, equivariant model for capsule networks that uses group-equivariant convolutions and degree-centrality routing. We proved that the model preserves detected compositionalities under transformations. We presented the results of experiments on affine variations of various classification datasets, and showed that our model performs better than several capsule network baselines. A second set of experiments showed that our model performs comparably to convolutional baselines on two other datasets. We also discussed a possible tradeoff between efficiency in the transformational sense and efficiency in the representation of non-geometric compositional relations. As future work, we aim at understanding the role of the routing algorithm in the optimality of the capsule-decomposition graph, and various other properties of interest based on it. We also note that SOVNET allows other equivariant prediction mechanisms -each of which could result in a wider application of SOVNET to different domains. Consider Algorithm 1, which is given below for convenience. The role of the GetW eights and Agreement procedures is to evaluate the relative importances of predictions for a deeper capsule, and the extent of consensus among them, respectively. The second of these is interpreted as a measure of the activation of the corresponding deeper capsule. A formalisation of these concepts to a general framework for even summation-based routing so as to cover all possible notions of relative importance, and consensus is not within the scope of this paper. Indeed, to the best of our knowledge, such a formalisation has not been successfully completed. Thus, instead of a formal description of a general routing procedure, we provide examples to better understand the role of these two functions. We first explain GetW eights, and then Agreement. Algorithm A general weighted-summation routing algorithm for SOVNET. The first example of GetW eights we provide is from the proposed degree-centrality based routing. The algorithm is given below, again. In this case, GetW eights is instantiated by the DegreeScore procedure, which assigns weights to predictions based on their normalised degree centrality scores. Thus, a prediction that agrees with a significant number of its peers obtains a higher importance than one that does not. This scheme follows the principle of routing-by-agreement, that aims to activate a deeper capsule only when its predicting shallower, component-capsules are in an acceptable spatial configuration (Hinton et al., 2011) . The above form for the summation-based routing procedure generalises for several existing routing algorithms. As an example, we present the dynamic routing algorithm of (Sabour et al., 2017) . This differs with our proposed algorithm in that it is a "attention-based", rather than "agreement-based" routing algorithm. That is, the relative importance of a prediction with respect to a fixed deeper capsule is not a direct measure of the extent of its consensus with its peers, but rather a measure of the relative attention it offers to the deeper capsule. Thus, the weight associated with a prediction for a fixed deeper capsule by a fixed shallower capsule depends on other deeper capsules. In order to accomodate such methods into a general procedure, we modify our formalism by having GetW eights take all the predictions as parameters, and return all the routing weights. This modified general procedure is given in Algorithm 5. Consider the dynamic routing algorithm of (Sabour et al., 2017) , given in Algorithm 6 -modified to our notation and also the use of group-equivariant convolutions. The procedure DynamicRouting is the instantiation for GetW eights. Note that the weights c ij (g) depend on the routing weights for the deeper capsules. Due to the formulation of capsules in our paper, as in (Sabour et al., 2017) , we use the 2-norm of a capsule to denote its activation. Thus, our degree-centrality based procedure, and also dynamic routing, do not use a separate value for this. However, examples of algorithms that use a separate activation value exist; for example, spectral routing (Bahadori, 2018) computes the activation score from the sigmoid of the first singular value of the matrix of stacked predictions.
A new scalable, group-equivariant model for capsule networks that preserves compositionality under transformations, and is empirically more transformation-robust to older capsule network models.
{"src": "scitldr-AIC_train", "paper_id": "BJgNJgSFPS"}