summaries: In this paper, the authors propose a generative latent variable model, which is named as SPACE, for unsupervised scene decomposition. The proposed model is built on a hierarchical mixture model: one component for generating foreground and the other one for generating the background, while the model for generating background is also a mixture model. The model is trained by standard ELBO with Gumbel-Softmax relaxation of the binary latent variable. To avoid the bounding box separation, the authors propose the boundary loss, which will be combined with the ELBO for training. The authors evaluated the proposed on 3D-room dataset and Atari.

summaries: This paper studies the problem of unsupervised scene decomposition with a foreground-background probabilistic modeling framework. Building upon the idea from the previous work on probabilistic scene decomposition [Crawford & Pineau 2019], this paper further decomposes the scene background into a sequence of background segments. In addition, with the proposed framework, scene foreground-background interactions are decoupled into foreground objects and background segments using chain rules. Experimental evaluations have been conducted on several synthetic datasets including the Atari environments and 3D-Rooms. Results demonstrate that the proposed method is superior to the existing baseline methods in both decomposing objects and background segments.

summaries: The paper proposes SPACE: a generative latent variable models for scene decomposition (foreground / background separation and object bounding box prediction). The authors state the following contributions relative to prior work in this space: 1) ability to simultaneously perform foreground/background segmentation and decompose the foreground into distinct object bounding box predictions, 2) a parallel spatial attention mechanism that improves the speed of the architecture relative to the closest prior work (SPAIR), 3) a demonstration through qualitative results that the approach can segment into foreground objects elements that remain static across observations (e.g. the key in Montezuma's Revenge).

abstractText: The ability to decompose complex multi-object scenes into meaningful abstractions like objects is fundamental to achieve higher-level cognition. Previous approaches for unsupervised object-oriented scene representation learning are either based on spatial-attention or scene-mixture approaches and limited in scalability which is a main obstacle towards modeling real-world scenes. In this paper, we propose a generative latent variable model, called SPACE, that provides a unified probabilistic modeling framework that combines the best of spatial-attention and scene-mixture approaches. SPACE can explicitly provide factorized object representations for foreground objects while also decomposing background segments of complex morphology. Previous models are good at either of these, but not both. SPACE also resolves the scalability problems of previous methods by incorporating parallel spatial-attention and thus is applicable to scenes with a large number of objects without performance degradations. We show through experiments on Atari and 3D-Rooms that SPACE achieves the above properties consistently in comparison to SPAIR, IODINE, and GENESIS. Results of our experiments can be found on our project website: https://sites.google.com/view/space-project-page

title: Continuously differentiable exponential linear units

venue: ArXiv,

authors:
M.G. Bellemare
Y. Naddaf
J. Veness
M. Bowling

title: The arcade learning environment: An evaluation platform for general agents

authors:
Christopher P Burgess
Loic Matthey
Nicholas Watters
Rishabh Kabra
Irina Higgins
Matt Botvinick
Alexander Lerchner. Monet

title: Unsupervised scene decomposition and representation

authors:
Djork-Arné Clevert
Thomas Unterthiner
Sepp Hochreiter

title: Fast and accurate deep network learning by exponential linear units (elus)

venue: In ICLR,

authors:
Eric Crawford
Joelle Pineau

title: Spatially invariant unsupervised object detection with convolutional neural networks

venue: In Proceedings of AAAI,

title: Exploiting spatial invariance for scalable unsupervised object tracking

authors:
Martin Engelcke
Adam R. Kosiorek
Oiwi Parker Jones
Ingmar Posner

title: Genesis: Generative scene inference and sampling with object-centric latent representations, 2019

authors:
SM Ali Eslami
Nicolas Heess
Theophane Weber
Yuval Tassa
David Szepesvari
Geoffrey E Hinton

title: Attend, infer, repeat: Fast scene understanding with generative models

venue: In Advances in Neural Information Processing Systems,

authors:
Klaus Greff
Sjoerd van Steenkiste
Jürgen Schmidhuber

title: Neural expectation maximization

authors:
Klaus Greff
Raphaël Lopez Kaufmann
Rishab Kabra
Nick Watters
Chris Burgess
Daniel Zoran
Loic Matthey
Matthew Botvinick
Alexander Lerchner

title: Multi-object representation learning with iterative variational inference

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In Proceedings of the 32nd International Conference on Machine Learning,

authors:
Max Jaderberg
Karen Simonyan
Andrew Zisserman
Koray Kavukcuoglu

title: Spatial transformer networks. In Advances in neural information processing

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax

venue: arXiv preprint arXiv:1611.01144,

authors:
Jindong Jiang
Sepehr Janghorbani
Gerard De Melo
Sungjin Ahn

title: Scalor: Scalable objectoriented sequential generative models

venue: In International Conference on Learning Representations,

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Adam Kosiorek
Hyunjik Kim
Yee Whye Teh
Ingmar Posner

title: Sequential attend, infer, repeat: Generative modelling of moving objects

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin A. Riedmiller

title: Playing atari with deep reinforcement

venue: learning. ArXiv,

authors:
Joseph Redmon
Santosh Divvala
Ross Girshick
Ali Farhadi

title: You only look once: Unified, real-time object detection

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Adam Santoro
David Raposo
David G Barrett
Mateusz Malinowski
Razvan Pascanu
Peter Battaglia
Timothy Lillicrap

title: A simple neural network module for relational reasoning

venue: In Advances in neural information processing systems,

authors:
Wenzhe Shi
Jose Caballero
Ferenc Huszar
Johannes Totz
Andrew P. Aitken
Rob Bishop
Daniel Rueckert
Zehan Wang

title: Real-time single image and video super-resolution using an efficient sub-pixel convolutional neural network

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

title: On variable binding in connectionist networks

venue: Connection Science,

authors:
Tijmen Tieleman
Geoffrey Hinton

title: Lecture 6.5-rmsprop, neural networks for machine learning

venue: Tech Report,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Sjoerd Van Steenkiste
Michael Chang
Klaus Greff
Jürgen Schmidhuber

title: Relational neural expectation maximization: Unsupervised discovery of objects and their interactions

venue: arXiv preprint arXiv:1802.10353,

authors:
Nicholas Watters
Loı̈c Matthey
Christopher P. Burgess
Alexander Lerchner

title: Spatial broadcast decoder: A simple architecture for learning disentangled representations in vaes

authors:
Adam (Kingma
Ba

heading: 1 INTRODUCTION

text:
One of the unsolved key challenges in machine learning is unsupervised learning of structured representation for a visual scene containing many objects with occlusion, partial observability, and complex background. When properly decomposed into meaningful abstract entities such as objects and spaces, this structured representation brings many advantages of abstract (symbolic) representation to areas where contemporary deep learning approaches with a global continuous vector representation of a scene have not been successful. For example, a structured representation may improve sample efficiency for downstream tasks such as a deep reinforcement learning agent (Mnih et al., 2013). It may also enable visual variable binding (Sun, 1992) for reasoning and causal inference over the relationships between the objects and agents in a scene. Structured representations also provide composability and transferability for better generalization.
Recent approaches to this problem of unsupervised object-oriented scene representation can be categorized into two types of models: scene-mixture models and spatial-attention models. In scenemixture models (Greff et al., 2017; 2019; Burgess et al., 2019; Engelcke et al., 2019), a visual scene is explained by a mixture of a finite number of component images. This type of representation provides flexible segmentation maps that can handle objects and background segments of complex morphology. However, since each component corresponds to a full-scale image, important physical features of objects like position and scale are only implicitly encoded in the scale of a full image and further disentanglement is required to extract these useful features. Also, since it does not explicitly reflect useful inductive biases like the locality of an object in the Gestalt principles (Koffka, 2013),
∗Visiting Student at Rutgers University. Authors named inside {} equally contributed. Correspondance to zxlin.cs@gmail.com and sjn.ahn@gmail.com.
the resulting component representation is not necessarily a representation of a local area. Moreover, to obtain a complete scene, a component needs to refer to other components, and thus inference is inherently performed sequentially, resulting in limitations in scaling to scenes with many objects.
In contrast, spatial-attention models (Eslami et al., 2016; Crawford & Pineau, 2019) can explicitly obtain the fully disentangled geometric representation of objects such as position and scale. Such features are grounded on the semantics of physics and should be useful in many ways (e.g., sample efficiency, interpretability, geometric reasoning and inference, transferability). However, these models cannot represent complex objects and background segments that have too flexible morphology to be captured by spatial attention (i.e. based on rectangular bounding boxes). Similar to scene-mixture models, previous models in this class show scalability issues as objects are processed sequentially.
In this paper, we propose a method, called Spatially Parallel Attention and Component Extraction (SPACE), that combines the best of both approaches. SPACE learns to process foreground objects, which can be captured efficiently by bounding boxes, by using parallel spatial-attention while decomposing the remaining area that includes both morphologically complex objects and background segments by using component mixtures. Thus, SPACE provides an object-wise disentangled representation of foreground objects along with explicit properties like position and scale per object while also providing decomposed representations of complex background components. Furthermore, by fully parallelizing the foreground object processing, we resolve the scalability issue of existing spatial attention methods. In experiments on 3D-room scenes and Atari game scenes, we quantitatively and qualitatively compare the representation of SPACE to other models and show that SPACE combines the benefits of both approaches in addition to significant speed-ups due to the parallel foreground processing.
The contributions of the paper are as follows. First, we introduce a model that unifies the benefits of spatial-attention and scene-mixture approaches in a principled framework of probabilistic latent variable modeling. Second, we introduce a spatially parallel multi-object processing module and demonstrate that it can significantly mitigate the scalability problems of previous methods. Lastly, we provide an extensive comparison with previous models where we illustrate the capabilities and limitations of each method.

heading: 2 THE PROPOSED MODEL: SPACE

text: In this section, we describe our proposed model, Spatially Parallel Attention and Component Extraction (SPACE). The main idea of SPACE, presented in Figure 1, is to propose a unified probabilistic generative model that combines the benefits of the spatial-attention and scene-mixture models.

heading: 2.1 GENERATIVE PROCESS

text:
SPACE assumes that a scene x is decomposed into two independent latents: foreground zfg and background zbg. The foreground is further decomposed into a set of independent foreground objects zfg = {zfgi } and the background is also decomposed further into a sequence of background segments zbg = zbg1:K . While our choice of modeling the foreground and background independently worked well empirically, for better generation, it may also be possible to condition one on the other. The image distributions of the foreground objects and the background components are combined together with a pixel-wise mixture model to produce the complete image distribution:
p(x|zfg, zbg) = αp(x|zfg)︸ ︷︷ ︸ Foreground +(1− α) K∑ k=1 πk p(x|zbgk )︸ ︷︷ ︸ Background . (1)
Here, the foreground mixing probability α is computed as α = fα(zfg). This way, the foreground is given precedence in assigning its own mixing weight and the remaining is apportioned to the background. The mixing weight assigned to the background is further sub-divided among the K background components. These weights are computed as πk = fπk(z bg 1:k) and ∑ k πk = 1. With these notations, the complete generative model can be described as follows.
p(x) = ∫∫ p(x|zfg, zbg)p(zbg)p(zfg)dzfgdzbg (2)
We now describe the foreground and background models in more detail.
Foreground. SPACE implements zfg as a structured latent. In this structure, an image is treated as if it were divided into H ×W cells and each cell is tasked with modeling at most one (nearby) object in the scene. This type of structuring has been used in (Redmon et al., 2016; Santoro et al., 2017; Crawford & Pineau, 2019). Similar to SPAIR, in order to model an object, each cell i is associated with a set of latents (zpresi , z where i , z depth i , z what i ). In this notation, z
pres is a binary random variable denoting if the cell models any object or not, zwhere denotes the size of the object and its location relative to the cell, zdepth denotes the depth of the object to resolve occlusions and zwhat models the object appearance and its mask. These latents may then be used to compute the foreground image component p(x|zfg) which is modeled as a Gaussian distribution N (µfg, σ2fg). In practice, we treat σ2fg as a hyperparameter and decode only the mean image µ
fg. In this process, SPACE reconstructs the objects associated to each cell having zpresi = 1. For each such cell, the model uses the z what i to decode the object glimpse and its mask and the glimpse is then positioned on a full-resolution canvas using zwherei via the Spatial Transformer (Jaderberg et al., 2015). Using the object masks and z depth i , all the foreground objects are combined into a single foreground mean-image µfg and the foreground mask α (See Appendix D for more details).
SPACE imposes a prior distribution on these latents as follows:
p(zfg) = H×W∏ i=1 p(zpresi ) ( p(zwherei )p(z depth i )p(z what i ) )zpresi (3)
Here, only zpresi is modeled using a Bernoulli distribution while the remaining are modeled as Gaussian.
Background. To model the background, SPACE implements zbgk , similar to GENESIS, as (z m k , z c k) where zmk models the mixing probabilities πk of the components and z c k models the RGB distribution p(x|zbgk ) of the kth background component as a Gaussian N (µ bg i , σ 2 bg). The following prior is
imposed upon these latents.
p(zbg) = K∏ k=1 p(zck|zmk )p(zmk |zm<k) (4)

heading: 2.2 INFERENCE AND TRAINING

text:
Since we cannot analytically evaluate the integrals in equation 2 due to the continuous latents zfg and zbg1:K , we train the model using a variational approximation. The true posterior on these variables is approximated as follows.
p(zbg1:K , z fg|x) ≈ q(zfg|x) K∏ k=1 q(zbgk |z bg <k,x) (5)
This is used to derive the following ELBO to train the model using the reparameterization trick and SGD (Kingma & Welling, 2013).
L(x) = Eq(zfg,zbg|x) [ log p(x|zfg, zbg)− K∑ k=1 DKL(q(z bg k |z bg <k,x) ‖ p(z bg k |z bg <k))
− H×W∑ i=1 DKL(q(z fg i |x) ‖ p(zfgi )) ] (6) See Appendix B for the detailed decomposition of the ELBO and the related details.
Parallel Inference of Cell Latents. SPACE uses mean-field approximation when inferring the cell latents, so zfgi = (z pres i , z where i , z depth i , z what i ) for each cell does not depend on other cells.
q(zfg|x) = H×W∏ i=1 q(zpresi |x) ( q(zwherei |x)q(zdepthi |x)q(zwhati |zwherei ,x) )zpresi (7)
As shown in Figure 1, this allows each cell to act as an independent object detector, spatially attending to its own local region in parallel. This is in contrast to inference in SPAIR, where each cell’s latents auto-regressively depend on some or all of the previously traversed cells in a row-major order i.e., q(zfg|x) = ∏HWi=1 q(zfgi |zfg<i,x). However, this method becomes prohibitively expensive in practice as the number of objects increases. While Crawford & Pineau (2019) claim that these lateral connections are crucial for performance since they model dependencies between objects and thus prevent duplicate detections, we challenge this assertion by observing that 1) due to the bottom-up encoding conditioning on the input image, each cell should have information about its nearby area without explicitly communicating with other cells, and 2) in (physical) spatial space, two objects cannot exist at the same position. Thus, the relation and interference between objects should not be severe and the mean-field approximation is a good choice in our model. In our experiments, we verify empirically that this is indeed the case and observe that SPACE shows comparable detection performance to SPAIR while having significant gains in training speeds and efficiently scaling to scenes with many objects.
Preventing Box-Splitting. If the prior for the bounding box size is set to be too small, then the model could split a large object by multiple bounding boxes and when the size prior is too large, the model may not capture small objects in the scene, resulting in a trade-off between the prior values of the bounding box size. To alleviate this problem, we found it sometimes helpful to introduce an auxiliary loss which we call the boundary loss. In the boundary loss, we construct a boundary of thickness b pixels along the borders of each glimpse. Then, we restrict an object to be inside this boundary and penalize the model if an object’s mask overlaps with the boundary area. Thus, the model is penalized if it tries to split a large object by multiple smaller bounding boxes. A detailed implementation of the boundary loss is mentioned in Appendix C.

heading: 3 RELATED WORKS

text:
Our proposed model is inspired by several recent works in unsupervised object-oriented scene decomposition. The Attend-Infer-Repeat (AIR) (Eslami et al., 2016) framework uses a recurrent neural network to attend to different objects in a scene and each object is sequentially processed one
at a time. An object-oriented latent representation is prescribed that consists of ‘what’, ‘where’, and ‘presence’ variables. The ‘what’ variable stores the appearance information of the object, the ‘where’ variable represents the location of the object in the image, and the ‘presence’ variable controls how many steps the recurrent network runs and acts as an interruption variable when the model decides that all objects have been processed.
Since the number of steps AIR runs scales with the number of objects it attends to, it does not scale well to images with many objects. Spatially Invariant Attend, Infer, Repeat (SPAIR) (Crawford & Pineau, 2019) attempts to address this issue by replacing the recurrent network with a convolutional network. Similar to YOLO (Redmon et al., 2016), the locations of objects are specified relative to local grid cells rather than the entire image, which allow for spatially invariant computations. In the encoder network, a convolutional neural network is first used to map the image to a feature volume with dimensions equal to a pre-specified grid size. Then, each cell of the grid is processed sequentially to produce objects. This is done sequentially because the processing of each cell takes as input feature vectors and sampled objects of nearby cells that have already been processed. SPAIR therefore scales with the pre-defined grid size which also represents the maximum number of objects that can be detected. Our model uses an approach similar to SPAIR to detect foreground objects, but importantly we make the foreground object processing fully parallel to scale to large number of objects without performance degradation. Works based on Neural Expectation Maximization (Van Steenkiste et al., 2018; Greff et al., 2017) do achieve unsupervised object detection but do not explicitly model the presence, appearance, and location of objects. These methods also suffer from the problem of scaling to images with a large number of objects. In a related line of research, AIR has also recently been extended to track objects in a sequence of images (Kosiorek et al., 2018; Crawford & Pineau, 2020; Jiang et al., 2020).
For unsupervised scene-mixture models, several recent models have shown promising results. MONet (Burgess et al., 2019) leverages a deterministic recurrent attention network that outputs pixel-wise masks for the scene components. A variational autoencoder (VAE) (Kingma & Welling, 2013) is then used to model each component. IODINE (Greff et al., 2019) approaches the problem from a spatial mixture model perspective and uses amortized iterative refinement of latent object representations within the variational framework. GENESIS (Engelcke et al., 2019) also uses a spatial mixture model which is encoded by component-wise latent variables. Relationships between these components are captured with an autoregressive prior, allowing complete images to be modeled by a collection of components.

heading: 4 EVALUATION

text:
We evaluate our model on two datasets: 1) an Atari (Bellemare et al., 2013) dataset that consists of random images from a pretrained agent playing the games, and 2) a generated 3D-room dataset that consists of images of a walled enclosure with a random number of objects on the floor. In order to test the scalability of our model, we use both a small 3D-room dataset that has 4-8 objects and a large 3D-room dataset that has 18-24 objects. Each image is taken from a random camera angle and the colors of the objects, walls, floor, and sky are also chosen at random. Additional details of the datasets can be found in the Appendix E.
Baselines. We compare our model against two scene-mixture models (IODINE and GENESIS) and one spatial-attention model (SPAIR). Since SPAIR does not have an explicit background component, we add an additional VAE for processing the background. Additionally, we test against two implementations of SPAIR: one where we train on the entire image using a 16×16 grid and another where we train on random 32 × 32 pixel patches using a 4 × 4 grid. We denote the former model as SPAIR and the latter as SPAIR-P. SPAIR-P is consistent with the SPAIR’s alternative training regime on Space Invaders demonstrated in Crawford & Pineau (2019) to address the slow training of SPAIR on the full grid size because of its sequential inference. Lastly, for performance reasons, unlike the original SPAIR implementation, we use parallel processing for rendering the objects from their respective latents onto the canvas1 for both SPAIR and SPAIR-P. Thus, because of these improvements, our SPAIR implementation can be seen as a stronger baseline than the original SPAIR. More details of the baselines are given in Appendix D.
1It is important to note that the worst case complexity of rendering is O(hw ×HW ), (where (h,w) is the image size) which is extremely time consuming when we have large image size and/or large number of objects.

heading: 4.1 QUALITATIVE COMPARISON OF INFERRED REPRESENTATIONS

text:
In this section, we provide a qualitative analysis of the generated representations of the different models. For each model, we performed a hyperparameter search and present the results for the best settings of hyperparameters for each environment. Figure 2 shows sample scene decompositions of our baselines from the 3D-Room dataset and Figure 3 shows the results on Atari. Note that SPAIR does not use component masks and IODINE and GENESIS do not separate foreground from background, hence the corresponding cells are left empty. Additionally, we only show a few representative components for IODINE and GENESIS since we ran those experiments with larger K than can be displayed. More qualitative results of SPACE can be found in Appendix A.
IODINE & GENESIS. In the 3D-Room environment, IODINE is able to segment the objects and the background into separate components. However, it occasionally does not properly decompose objects (in the Large 3D-room results, the orange sphere on the right is not reconstructed) and may generate blurry objects. GENESIS is able to segment the background walls, floor, and sky into multiple components. It is able to capture blurry foreground objects in the Small 3D-Room, but is not able to cleanly capture foreground objects with the larger number of objects in the Large 3DRoom. In Atari, both IODINE and GENESIS fail to capture the foreground properly or try to encode all objects in a single component. We believe this is because the objects in Atari games are smaller, less regular and lack the obvious latent factors like color and shape as in the 3D dataset, and thus detection-based approaches are more appropriate in this case.
SPAIR & SPAIR-P. SPAIR is able to detect tight bounding boxes in both 3D-Rooms and the two Atari games. SPAIR-P, however, often fails to detect the foreground objects in proper bounding boxes, frequently uses multiple bounding boxes for one object and redundantly detects parts of the background as foreground objects. This is a limitation of the patch training as the receptive field of
each patch is limited to a 32× 32 glimpse, prohibiting it from detecting larger objects and making it difficult to distinguish the background from foreground. These two properties are illustrated well in Space Invaders, where it is able to detect the small aliens, but it detects the long piece of background ground on the bottom of the image as foreground objects.
SPACE. In both 3D-Room, SPACE is able to accurately detect almost all objects despite the large variations in object positions, colors, and shapes, while producing a clean segmentation of the background walls, ground, and sky. This is in contrast to the SPAIR model, while being able to provide similar foreground detection quality, encodes the whole background into a single component, which makes the representation less disentangled. Notably, in River Raid where the background is constantly changing, SPACE is able to perfectly segment the blue river while accurately detecting all foreground objects, while SPAIR often cannot properly separate foreground and background.
Joint Training. Figure 4 shows the results of training SPACE jointly across 10 Atari games. We see that even in this setting, SPACE is able to correctly detect foreground objects and cleanly segment the background.
Foreground vs Background. Typically, foreground is the dynamic local part of the scene that we are interested in, and background is the relatively static and global part. This definition, though intuitive, is ambiguous. Some objects, such as the red shields in Space Invaders and the key in Montezuma’s Revenge (Figure 6) are static but important to detect as foreground objects. We found that SPACE tends to detect these as foreground objects while SPAIR considers it background. Similar behavior is observed in Atlantis (Figure 4), where SPACE tends to detect some foreground objects from the middle base that is above the water. One reason for this behavior is because we limit the capacity of the background module by using a spatial broadcast decoder (Watters et al., 2019) which is much weaker when compared to other decoders like sub-pixel convolutional nets (Shi et al. (2016)). This would favor modeling static objects as foreground rather than background.

heading: 4.2 QUANTITATIVE COMPARISON

text:
In this section we compare SPACE with the baselines in several quantitative metrics2. We first note that each of the baseline models has a different decomposition capacity (C), which we define as the capability of the model to decompose the scene into its semantic constituents such as the foreground objects and the background segmented components. For SPACE, the decomposition capacity is equal to the number of grid cells H × W (which is the maximum number of foreground objects that can be detected) plus the number of background components K. For SPAIR, the decomposition capacity is equal to the number of grid cells H × W plus 1 for background. For IODINE and GENESIS, it is equal to the number of components K.
For each experiment, we compare the metrics for each model with similar decomposition capacities. This way, each model can decompose the image into the same number of components. For a setting in SPACE with a grid size of H ×W with KSPACE components, the equivalent settings in IODINE and GENESIS would be with C = (H ×W ) +KSPACE. The equivalent setting in SPAIR would be a grid size of H ×W .
Gradient Step Latency. The leftmost chart of Figure 5 shows the time taken to complete one gradient step (forward and backward propagation) for different decomposition capacities for each of the models. We see that SPAIR’s latency grows with the number of cells because of the sequential
2As previously shown, SPAIR-P does not work well in many of our environments, so we do not include it in these quantitative experiments. As in the qualitative section, we use the SPAIR implementation with sequential inference and parallel rendering in order to speed up the experiments.
Published as a conference paper at ICLR 2020
4× 4 8× 8 16× 16 24× 242 −2
2−1
20
21
22
23
24
Number of Cells (H ×W )
G ra di en t S te p L at en cy
(i n s)
Training Latency Plot
2 4 6
·104
200
400
600
800
1,000
1,200
Wall Clock Time (in s)
R ec on st ru ct io n P ix el M S E
Convergence 3D Room (4× 4)
2 4 6
·104
200
600
1,000
1,400
1,800
2,200
2,600
3,000
Wall Clock Time (in s)
Convergence 3D Room (8× 8)
2 4 6
·104
200
400
600
800
1,000
1,200
Wall Clock Time (in s)
Convergence 3D Room (16× 16)
4× 4 8× 8 16× 16 24× 24
2−1
2
21
22
23
24
Number of Cells (H ×W ) G ra di en t S te p L at en cy
(i n s)

heading: Training Latency Plot

text:
SPACE (C = H ×W + 5) SPAIR (C = H ×W + 1) IODINE (C = H ×W + 5) GENESIS (C = H ×W + 5)
Figure 5: Quantitative performance comparison between SPACE , SPAIR, IODINE and GENESIS in terms of batch-processing time during training, training convergence and converged pixel MSE. Convergence plots showing pixel-MSE were computed on a held-out set during training.
nature of its latent inference step. Similarly GENESIS and IODINE’s latency grows with the number of components K because each component is processed sequentially in both the models. IODINE is the slowest overall with its computationally expensive iterative inference procedure. Furthermore, both IODINE and GENESIS require storing data for each of the K components, so we were unable to run our experiments on 256 components or greater before running out of memory on our 22GB GPU. On the other hand, SPACE employs parallel processing for the foreground which makes it scalable to large grid sizes, allowing it to detect a large number of foreground objects without any significant performance degradation. Although this data was collected for gradient step latency, this comparison implies a similar relationship exists with inference time which is a main component in the gradient step.
Time for Convergence. The remaining three charts in Figure 5 show the amount of time each model takes to converge in different experimental settings. We use the pixel-wise mean squared error (MSE) as a measurement of how close a model is to convergence. In all settings, SPAIR and SPACE converge much faster than IODINE and GENESIS. In the 4 × 4 and 8 × 8 setting, SPAIR and SPACE converge equally fast. But as we scale up to 16×16, SPAIR becomes much slower than SPACE .
Average Precision and Error Rate. In order to assess the quality of our bounding box predictions, we measure the Average Precision and Object Count Error Rate of our predictions. Our results are shown in Table 1. We only report these metrics for 3D-Room since we have access to the ground truth bounding boxes for each of the objects in the scene. Both models have very similar average precision and error rate. Despite being parallel in its inference, SPACE has a comparable count error rate to that of SPAIR.
From our experiments, we can assert that SPACE can produce similar quality bounding boxes as SPAIR while 1) having orders of magnitude faster inference and gradient step time, 2) scaling to a large number of objects without significant performance degradation, and 3) providing complex background segmentation.

heading: 5 CONCLUSION

text: We propose SPACE, a unified probabilistic model that combines the benefits of the object representation models based on spatial attention and the scene decomposition models based on component mixture. SPACE can explicitly provide factorized object representation per foreground object while also decomposing complex background segments. SPACE also achieves a significant speed-up and thus makes the model applicable to scenes with a much larger number of objects without performance degradation. Besides, the detected objects in SPACE are also more intuitive than other methods. We show the above properties of SPACE on Atari and 3D-Rooms. Interesting future directions are to replace the sequential processing of background by a parallel one and to improve the model for natural images. Our next plan is to apply SPACE for object-oriented model-based reinforcement learning.

heading: ACKNOWLEDGMENTS

text: SA thanks to Kakao Brain and Center for Super Intelligence (CSI) for their support. ZL thanks to the ZJU-3DV group for its support. The authors would also like to thank Chang Chen and Zhuo Zhi for their insightful discussions and help in generating the 3D-Room dataset.

heading: A ADDITIONAL RESULTS OF SPACE

heading: B ELBO DERIVATIONS

text:
In this section, we derive the ELBO for the log-likelihood log p(x).
log p(x) ≥ Eq(zfg,zbg|x) [ p(x|zfg, zbg) ] −DKL(q(zfg|x) ‖ p(zfg))−DKL(q(zbg|x) ‖ p(zbg))
= Eq(zfg,zbg|x) [ p(x|zfg, zbg)−DKL(q(zfg|x) ‖ p(zfg))−DKL(q(zbg|x) ‖ p(zbg)) ] = Eq(zfg,zbg|x) [ p(x|zfg, zbg)−
K∑ k=1 DKL(q(z bg k |x, z bg <k) ‖ p(zbg|z bg <k))−
H×W∑ i=1 DKL(q(z fg i |x) ‖ p(zfgi )) ] KL Divergence for the Foreground Latents Under the SPACE ’s approximate inference, the DKL(q(z fg i |x) ‖ p(zfgi )) inside the expectation can be evaluated as follows.
Eq(zfg,zbg|x) [ DKL(q(z fg i |x) ‖ p(zfgi )) ] = Eq(zfg,zbg|x) [ DKL(q(z pres i |x) ‖ p(zpresi )) + Eq(zpresi |x)z pres i [ DKL(q(z where i |x) ‖ p(zwherei ))
+ Eq(zwherei |x)DKL(q(z what i |x, zwherei ) ‖ p(zwhati )) +DKL(q(zdepthi |x) ‖ p(zdepthi ))
]]
= Eq(zfg,zbg|x) [ DKL(q(z pres i |x) ‖ p(zpresi )) + zpresi [ DKL(q(z where i |x) ‖ p(zwherei ))
+DKL(q(z what i |x, zwherei ) ‖ p(zwhati )) +DKL(q(zdepthi |x) ‖ p(zdepthi )) ]] KL Divergence for the Background Latents Under our GENESIS-like modeling of inference for the background latents, the KL term inside the expectation for the background is evaluated as follows.
Eq(zfg,zbg|x) [ DKL(q(z bg k |z bg <k,x) ‖ p(z bg k |z bg <k)) ] = Eq(zfg,zbg|x) [ DKL(q(z m k |zm<k,x) ‖ p(zmk |zm<k)) + Eq(zmk |zm<k,x)DKL(q(z c k|zmk ,x) ‖ p(zck|zmk ))
] = Eq(zfg,zbg|x) [DKL(q(zmk |zm<k,x) ‖ p(zmk |zm<k)) +DKL(q(zck|zmk ,x) ‖ p(zck|zmk ))]
Relaxed treatment of zpres In our implementation, we model the Bernoulli random variable zpresi using the Gumbel-Softmax distribution (Jang et al., 2016). We use the relaxed value of zpres in the entire training and use hard samples only for the visualizations.

heading: C BOUNDARY LOSS

text:
In this section we elaborate on the implementation details of the boundary loss. We construct a kernel of the size of the glimpse, gs × gs (we use gs = 32) with a boundary gap of b = 6 having negative uniform weights inside the boundary and a zero weight in the region between the boundary and the glimpse. This ensures that the model is penalized when the object is outside the boundary. This kernel is first mapped onto the global space via STN Jaderberg et al. (2015) to obtain the global kernel. This is then multiplied element-wise with global object mask α to obtain the boundary loss map. The objective of the loss is to minimize the mean of this boundary loss map. In addition to the ELBO, this loss is also back-propagated via RMSProp (Tieleman & Hinton. (2012)). This loss, due to the boundary constraint, enforces the bounding boxes to be less tight and results in lower average precision, so we disable the loss and optimize only the ELBO after the model has converged well.
D IMPLEMENTATION DETAILS

heading: D.1 ALGORITHMS

text:
Algorithm 1 and Algorithm 3 present SPACE’s inference for foreground and background. Algorithm 2 describe the details of rescalei function in Algorithm 1 that transforms local shift zshifti to global shift ẑshifti .Algorithm 4 show the details of the generation process of the background module. For foreground generation, we simply sample the latent variables from the priors instead of conditioning on the input. Note that, for convenience the algorithms for the foreground module and background module are presented with for loops, but inference for all variables of the foreground module are implemented as parallel convolution operations and most operations of the background module (barring the LSTM module) are parallel as well.
Algorithm 1: Foreground Inference Input: image x Output: foreground mask α, appearance µfg, grid height H and width W êimg = ImageEncoderFg(x) rimg = ResidualConnection(êimg) eimg = ResidualEncoder([êimg, rimg]) for i← 1 to HW do
/* The following is performed in parallel */ ρi = ZPresNet(e img i ) [µdepthi ,σ depth i ] = ZDepthNet(e img i ) [µscalei ,σ scale i ] = ZScaleNet(e img i ) [µshifti ,σ shift i ] = ZShiftNet(e img i ) zpresi ∼ Bern(ρi) zdepthi ∼ N (µdepthi ,σdepth,2i ) zscalei ∼ N (µscalei ,σscale,2i ) zshifti ∼ N (µshifti ,σshift,2i ) /* Rescale local shift to global shift as in SPAIR */ ẑscalei = σ(z scale i ) ẑshifti = rescalei(z shift i ) zwherei = [ẑ scale i , ẑ shift i ] /* Extract glimpses with a Spatial Transformer */ x̂i = ST(x, zwherei ) [µwhati ,σ what i ] =GlimpseEncoder(x̂i) zwhati ∼ N (µwhati ,σwhat,2i ) /* Foreground mask and appearance of glimpse size */ [αatti ,o att i ] = GlimpseDecoder(z what i ) α̂atti = α att i zpresi yatti = α̂ att i oatti /* Transform both to canvas size */ α̂atti = ST −1(α̂atti , z where i ) yatti = ST −1(yatti , z where i ) end /* Compute weights for each component */ w = softmax(−100 · σ(zdepth) α̂att) /* Compute global weighted mask and foreground appearance */ α = sum(w α̂att) µfg = sum(w yatt)
Algorithm 2: Rescale zshifti Input: Shift latent zshifti , cell index i, grid height H and width W Output: Rescaled shift latent ẑshifti /* Get width and heigh index of cell i */ [k, j] = [i%H, i÷H] /* Center of this cell */ ci = [k + 0.5, j + 0.5] /* Get global shift */ z̃shifti = ci + tanh(z shift i ) /* Normalize to range (-1, 1) */ ẑshifti = 2 · z̃shifti /[W,H]− 1
Algorithm 3: Background Inference Input: image x, initial LSTM states h0, c0, initial dummy mask zm0 Output: background masks πk, appearance µbgk , for k = 1, . . . ,K eimg = ImageEncoderBg(x) for k ← 1 to K do
hk, ck = LSTM([z m k−1, e img], ck−1,hk−1) [µmk ,σ m k ] = PredictMask(hk) zm ∼ N (µmk ,σm,2k ) /* Actually decoded in parallel */ π̂k = MaskDecoder(z m k ) /* Stick breaking process as described in GENESIS */ πk = SBP(π̂1:k) [µck,σ c k] = CompEncoder([πk,x]) zc ∼ N (µck,σc,2k ) µbgk =CompDecoder(z c k)
end
Algorithm 4: Background Generation Input: initial LSTM states h0, c0, initial dummy mask zm0 Output: background masks πk, appearance µbgk , for k = 1, . . . ,K for k ← 1 to K do
hk, ck = LSTM(z m k−1, ck−1,hk−1) [µmk ,σ m k ] = PredictMaskPrior(hk) zm ∼ N (µmk ,σm,2k ) /* Actually decoded in parallel */ π̂k = MaskDecoder(z m k ) /* Stick breaking process as described in GENESIS */ πk = SBP(π̂1:k) [µck,σ c k] = PredictComp(z m k ) zck ∼ N (µck,σc,2k ) µbgk =CompDecoder(z c k)
end

heading: D.2 TRAINING REGIME AND HYPERPARAMETERS

text:
For all experiments we use an image size of 128 × 128 and a batch size of 12 to 16 depending on memory usage. For the foreground module, we use the RMSProp (Tieleman & Hinton. (2012)) optimizer with a learning rate of 1 × 10−5 except for Figure 5, for which we use a learning rate of 1×10−4 as SPAIR. For the background module, we use the Adam (Kingma & Ba (2014)) optimizer with a learning rate of 1 × 10−3. We use gradient clipping with a maximum norm of 1.0. For quantitative results, SPACE is trained up to 160000 steps. For Atari games, we find it beneficial to set α to be fixed for the first several thousand steps, and vary the actual value and number of steps for different games. This allows both the foreground as well as the background module to learn in the early stage of training.
We list out our hyperparameters for 3D large dataset and joint training for 10 static Atari games below. Hyperparameters for other experiments are similar, but are finetuned for each dataset individually. In the tables below, (m→ n) : (p→ q) denotes annealing the hyperparameter value from m to n, starting from step p until step q.
3D Room Large Name Symbol Value
zpres prior prob ρ (0.1→ 0.01) : (4000→ 10000) zscale prior mean µscale (−1.0→ −2.0) : (10000→ 20000) zscale prior stdev σscale 0.1 zshift prior µshift,σshift N (0, I) zdepth prior µdepth,σdepth N (0, I) zwhat prior µwhat,σwhat N (0, I) foreground stdev σfg 0.15 background stdev σbg 0.15 component number K 5 gumbel-softmax temperature τ (2.5→ 0.5) : (0→ 20000) #steps to fix α N/A fixed α value N/A boundary loss Yes turn off boundary loss at step 100000
Joint Training on 10 Atari Games Name Symbol Value
zpres prior prob ρ 1× 10−10 zscale prior mean µscale −2.5 zscale prior stdev σscale 0.1 zshift prior µshift,σshift N (0, I) zdepth prior µdepth,σdepth N (0, I) zwhat prior µwhat,σwhat N (0, I) foreground stdev σfg 0.20 background stdev σbg 0.10 component number K 3 gumbel-softmax temperature τ (2.5→ 1.0) : (0→ 10000) #steps to fix α 4000 fixed α value 0.1 boundary loss No turn off boundary loss at step N/A

heading: D.3 MODEL ARCHITECTURE

text:
Here we describe the architecture of our 16 × 16 SPACE model. The model for 8 × 8 grid cells is the same but with a stride-2 convolution for the last layer of the image encoder.
All modules that output distribution parameters are implemented with either one single fully connected layer or convolution layer, with the appropriate output size. Image encoders are fully convolutional networks that output a feature map of shape H ×W , and the glimpse encoder comprises of convolutional layers followed by a final linear layer that computes the parameters of a Gaussian distribution. For the glimpse decoder of the foreground module and the mask decoder of the background module we use the sub-pixel convolution layer (Shi et al. (2016)). On the lines of GENESIS (Engelcke et al. (2019)) and IODINE (Greff et al. (2019)), we adopt Spatial Broadcast Network (Watters et al. (2019)) as the component decoder to decode zck into background components.
For inference and generation of the background module, the dependence of zmk on z m 1:k−1 is implemented with LSTMs, with hidden sizes of 64. Dependence of zck on z m k is implemented with a MLP with two hidden layers with 64 units per layer. We apply softplus when computing standard deviations for all Gaussian distributions, and apply sigmoid when computing reconstruction and masks. We use either Group Normalization (GN) (Wu & He (2018)) and CELU (Barron (2017)) or Batch Normalization (BN) (Ioffe & Szegedy (2015)) and ELU (Clevert et al. (2016)) depending on the module type.
The rest of the architecture details are described below. In the following tables, ConvSub(n) denotes a sub-pixel convolution layer implemented as a stride-1 convolution and a PyTorch PixelShuffle(n) layer, and GN(n) denotes Group Normalization with n groups.
Name Value Comment
zdepth dim 1 zpres dim 1 zscale dim 2 for x and y axis zshift dim 2 for x and y axis zwhat dim 32 zm dim 32 zc dim 32 glimpse shape (32, 32) for oatt,αatt image shape (128, 128)
Foreground Image Encoder Layer Size/Ch. Stride Norm./Act.
Input 3 Conv 4× 4 16 2 GN(4)/CELU Conv 4× 4 32 2 GN(8)/CELU Conv 4× 4 64 2 GN(8)/CELU Conv 3× 3 128 1 GN(16)/CELU Conv 3× 3 256 1 GN(32)/CELU Conv 1× 1 128 1 GN(16)/CELU
Residual Connection Layer Size/Ch. Stride Norm./Act.
Input 128 Conv 3× 3 128 1 GN(16)/CELU Conv 3× 3 128 1 GN(16)/CELU
Residual Encoder Layer Size/Ch. Stride Norm./Act.
Input 128 + 128 Conv 3× 3 128 1 GN(16)/CELU
Glimpse Encoder Layer Size/Ch. Stride Norm./Act.
Input 3 Conv 3× 3 16 1 GN(4)/CELU Conv 4× 4 32 2 GN(8)/CELU Conv 3× 3 32 1 GN(4)/CELU Conv 4× 4 64 2 GN(8)/CELU Conv 4× 4 128 2 GN(8)/CELU Conv 4× 4 256 1 GN(16)/CELU Linear 32 + 32
Glimpse Decoder Layer Size/Ch. Stride Norm./Act.
Input 32 Conv 1× 1 256 1 GN(16)/CELU ConvSub(2) 128 1 GN(16)/CELU Conv 3× 3 128 1 GN(16)/CELU ConvSub(2) 128 1 GN(16)/CELU Conv 3× 3 128 1 GN(16)/CELU ConvSub(2) 64 1 GN(8)/CELU Conv 3× 3 64 1 GN(8)/CELU ConvSub(2) 32 1 GN(8)/CELU Conv 3× 3 32 1 GN(8)/CELU ConvSub(2) 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU
Background Image Encoder Layer Size/Ch. Stride Norm./Act.
Input 3 Conv 3× 3 64 2 BN/ELU Conv 3× 3 64 2 BN/ELU Conv 3× 3 64 2 BN/ELU Conv 3× 3 64 2 BN/ELU Flatten Linear 64 ELU
Mask Decoder Layer Size/Ch. Stride Norm./Act.
Input 32 Conv 1× 1 256 1 GN(16)/CELU ConvSub(4) 256 1 GN(16)/CELU Conv 3× 3 256 1 GN(16)/CELU ConvSub(2) 128 1 GN(16)/CELU Conv 3× 3 128 1 GN(16)/CELU ConvSub(4) 64 1 GN(8)/CELU Conv 3× 3 64 1 GN(8)/CELU ConvSub(4) 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU Conv 3× 3 1 1
Component Encoder Layer Size/Ch. Stride Norm./Act.
Input 3+1 (RGB+mask) Conv 3× 3 32 2 BN/ELU Conv 3× 3 32 2 BN/ELU Conv 3× 3 64 2 BN/ELU Conv 3× 3 64 2 BN/ELU Flatten Linear 32+32
Component Decoder Layer Size/Ch. Stride Norm./Act.
Input 32 (1d) Spatial Broadcast 32+2 (3d) Conv 3× 3 32 1 BN/ELU Conv 3× 3 32 1 BN/ELU Conv 3× 3 32 1 BN/ELU Conv 3× 3 3 1

heading: D.4 BASELINES

text:
Here we give out the details of the background decoder in training of SPAIR (both full image as well as patch-wise training). The foreground and background image encoder is same as that of SPACE with the only difference that the inferred latents are conditioned on previous cells’ latents as described in Section 2.2. For the background image encoder, we add an additional linear layer so that the encoded background latent is one dimensional.
SPAIR Background Decoder Layer Size/Ch. Stride Norm./Act.
Input 32 Conv 1× 1 256 1 GN(16)/CELU ConvSub(4) 256 1 GN(16)/CELU Conv 3× 3 256 1 GN(16)/CELU ConvSub(4) 128 1 GN(16)/CELU Conv 3× 3 128 1 GN(16)/CELU ConvSub(2) 64 1 GN(8)/CELU Conv 3× 3 64 1 GN(8)/CELU ConvSub(4) 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU Conv 3× 3 3 1

heading: SPAIR Background Encoder For Patch Training

text:
Layer Size/Ch. Stride Norm./Act.
Input 3 Conv 2× 2 16 2 GN(4)/CELU Conv 2× 2 32 2 GN(8)/CELU Conv 2× 2 64 2 GN(8)/CELU Conv 2× 2 128 2 GN(16)/CELU Conv 2× 2 32 2 GN(4)/CELU

heading: SPAIR Background Decoder For Patch Training

text:
Layer Size/Ch. Stride Norm./Act.
Input 16 Conv 1× 1 256 1 GN(16)/CELU Conv 1× 1 2048 1 ConvSub(4) 128 1 GN(16)/CELU Conv 3× 3 128 1 GN(16)/CELU Conv 1× 1 256 1 ConvSub(2) 64 1 GN(8)/CELU Conv 3× 3 64 1 GN(8)/CELU Conv 1× 1 256 1 ConvSub(4) 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU Conv 3× 3 16 1 GN(4)/CELU Conv 3× 3 3 1
For IODINE, we use our own implementation following the details as described in (Greff et al., 2019). For GENESIS, we also use our own implementation following the same architecture as in (Engelcke et al., 2019), but the details of individual networks are similar to SPACE’s background module.

heading: E DATASET DETAILS

text:
Atari. For each game, we sample 60,000 random images from a pretrained agent (Wu et al., 2016). We split the images into 50,000 for the training set, 5,000 for the validation set, and 5,000 for the testing set. Each image is preprocessed into a size of 128 × 128 pixels with BGR color channels. We present the results for the following games: Space Invaders, Air Raid, River Raid, Montezuma’s Revenge.
We also train our model on a dataset of 10 games jointly, where we have 8,000 training images, 1,000 validation images, and 1,000 testing images for each game. We use the following games: Asterix, Atlantis, Carnival, Double Dunk, Kangaroo, Montezuma Revenge, Pacman, Pooyan, Qbert, Space Invaders.
Room 3D. We use MuJoCo (Todorov et al., 2012) to generate this dataset. Each image consists of a walled enclosure with a random number of objects on the floor. The possible objects are randomly sized spheres, cubes, and cylinders. The small 3D-Room dataset has 4-8 objects and the large 3DRoom dataset has 18-24 objects. The color of the objects are randomly chosen from 8 different colors and the colors of the background (wall, ground, sky) are chosen randomly from 5 different colors. The angle of the camera is also selected randomly. We use a training set of 63,000 images, a validation set of 7,000 images, and a test set of 7,000 images. We use a 2-D projection from the camera to determine the ground truth bounding boxes of the objects so that we can report the average precision of the different models.


summaries: The paper proposes a CNN compression method, based on the so called EHP operation, which can be used to  analyze and generalize depthwise separable convolution. Based on EHP, the paper develops depthwise separable convolution to compress CNNs, and extend it to a rank-k approach with further improved accuracy. Some analysis is provided about the operation equivalence. The experiments on standard benchmark datasets show the effectiveness of the method.

summaries: The paper is dedicated to studying fast and lightweight convolution for efficient compression and retaining original accuracy. In this paper, the authors interpret existing convolution methods based on depthwise separable convolution and derive FALCON. They claim their FALCON mathematically approximate the standard convolution kernel and achieves a better TA/efficiency tradeoff. They conduct extensive experiments to show that FALCON based method 1) outperforms previous state-of-the-art methods; 2) achieve 8X efficiency while ensuring similar TA.

summaries: This paper proposed a model compression method: Falcon and rank-k Falcon. Both are used to compress CNN type of models by replacing standard convolution layer with a compact Falcon or rank-k Falcon layer to compress the model. Falcon's main idea is to decompose the traditional convolution kernel K into two smaller tensors, one is depthwise convolution kernel D and pointwise convolution kernel P. And DP will reconstruct the original kernel K. Since D+P's memory is  D*D*M+N*M which is smaller than the original size D*D*M*N, and thus when N is large, the memory saving could be large. The paper is in general in good writing and very easy to read.

abstractText: How can we efficiently compress Convolutional Neural Networks (CNN) while retaining their accuracy on classification tasks? A promising direction is based on depthwise separable convolution which replaces a standard convolution with a depthwise convolution and a pointwise convolution. However, previous works based on depthwise separable convolution are limited since 1) they are mostly heuristic approaches without a precise understanding of their relations to standard convolution, and 2) their accuracies do not match that of the standard convolution. In this paper, we propose FALCON, an accurate and lightweight method for compressing CNN. FALCON is derived by interpreting existing convolution methods based on depthwise separable convolution using EHP, our proposed mathematical formulation to approximate the standard convolution kernel. Such interpretation leads to developing a generalized version rank-k FALCON which further improves the accuracy while sacrificing a bit of compression and computation reduction rates. In addition, we propose FALCON-branch by fitting FALCON into the previous state-of-the-art convolution unit ShuffleUnitV2 which gives even better accuracy. Experiments show that FALCON and FALCON-branch outperform 1) existing methods based on depthwise separable convolution and 2) standard CNN models by up to 8× compression and 8× computation reduction while ensuring similar accuracy. We also demonstrate that rank-k FALCON provides even better accuracy than standard convolution in many cases, while using a smaller number of parameters and floating-point operations.

authors:
Eirikur Agustsson
Fabian Mentzer
Michael Tschannen
Lukas Cavigelli
Radu Timofte
Luca Benini
Luc Van Gool

title: Soft-to-hard vector quantization for end-to-end learning compressible representations

venue: Neural Information Processing Systems (NIPS),

authors:
Wenlin Chen
James T. Wilson
Stephen Tyree
Kilian Q. Weinberger
Yixin Chen

title: Compressing neural networks with the hashing trick

venue: International Conference on Machine Learning (ICML),

authors:
Yoojin Choi
Mostafa El-Khamy
Jungwon Lee

title: Towards the limit of network quantization

venue: International Conference on Learning Representations (ICLR),

authors: Chollet Franois

title: Xception: Deep learning with depthwise separable convolutions, 2016

authors:
Matthieu Courbariaux
Yoshua Bengio
Jean-Pierre David

title: Binaryconnect: Training deep neural networks with binary weights during propagations

authors:
Matthieu Courbariaux
Itay Hubara
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Binarized neural networks: Training neural networks with weights and activations constrained to +1 or -1

authors:
Song Han
Jeff Pool
John Tran
William J. Dally

title: Learning both weights and connections for efficient neural networks

authors:
Song Han
Huizi Mao
William J. Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

authors:
Lu Hou
Quanming Yao
James T. Kwok

title: Loss-aware binarization of deep networks

authors:
Andrew G. Howard
Menglong Zhu
Bo Chen
Dmitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: Mobilenets: Efficient convolutional neural networks for mobile vision applications

authors:
Dong Hyun Kim
Chanyoung Park
Jinoh Oh
Sungyoung Lee
Hwanjo Yu

title: Convolutional matrix factorization for document context-aware recommendation

venue: In Recsys,

authors:
Yong-Deok Kim
Eunhyeok Park
Sungjoo Yoo
Taelim Choi
Lu Yang
Dongjun Shin

title: Compression of deep convolutional neural networks for fast and low power mobile applications

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E. Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems

venue: Annual Conference on Neural Information Processing Systems

authors:
Vadim Lebedev
Yaroslav Ganin
Maksim Rakhuba
Ivan Oseledets
Victor Lempitsky

title: Speeding-up convolutional neural networks using fine-tuned cp-decomposition

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

authors:
Ningning Ma
Xiangyu Zhang
Hai-Tao Zheng
Jian Sun

title: Shufflenet V2: practical guidelines for efficient CNN architecture

venue: design. CoRR,

authors:
Pavlo Molchanov
Stephen Tyree
Tero Karras
Timo Aila
Jan Kautz

title: Pruning convolutional neural networks for resource efficient inference

authors:
Alexander Novikov
Dmitry Podoprikhin
Anton Osokin
Dmitry Vetrov

title: Tensorizing neural networks

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

title: Rigid-motion scattering for image classification

venue: PhD thesis, cole Polytechnique,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

authors:
Christian Szegedy
Sergey Ioffe
Vincent Vanhoucke
Alexander A. Alemi

title: Inception-v4, inception-resnet and the impact of residual connections on learning

venue: In AAAI,

authors:
Karen Ullrich
Edward Meeds
Max Welling

title: Soft weight-sharing for neural network compression

authors:
Wenpeng Yin
Hinrich Schütze
Bing Xiang
Bowen Zhou

title: ABCNN: attention-based convolutional neural network for modeling sentence

venue: pairs. TACL,

authors:
Xiangyu Zhang
Xinyu Zhou
Mengxiao Lin
Jian Sun

title: Shufflenet: An extremely efficient convolutional neural network for mobile devices, 2017

authors:
Chenzhuo Zhu
Song Han
Huizi Mao
William J. Dally

title: Trained ternary quantization

title: Comparison of architectures based on depthwise separable convolution. BN denotes batchnormalization, and Relu is an activation function. expansion ratio. The second sub-layer is a D×D depthwise convolution

title: 4gH ′W ′N2 FLOPs

title: G PARAMETERS AND FLOPS We summarize the numbers of parameters and FLOPs for FALCON and competitors

heading: 1 INTRODUCTION

text:
How can we efficiently reduce size and energy consumption of Convolutional Neural Networks (CNN) while maintaining their accuracy on classification tasks? Nowadays, CNN is widely used in various areas including computer vision (Krizhevsky et al. (2012); Simonyan & Zisserman (2014); Szegedy et al. (2017)), natural language processing (Yin et al. (2016)), recommendation system (Kim et al. (2016a)), etc. In addition, model compression has become an important technique due to an increase in the model capacity and the number of parameters in CNN. One recent and promising direction for compressing CNN is depthwise separable convolution (Sifre (2014)) which replaces standard convolution with depthwise and pointwise convolutions. The depthwise convolution applies a separate 2D convolution kernel for each input channel, and the pointwise convolution changes the channel size using 1×1 convolution (details in Section 2.1). Several recent methods (Howard et al. (2017); Sandler et al. (2018); Zhang et al. (2017)) based on depthwise separable convolution show reasonable performances in terms of compression and computation reduction.
However, existing approaches based on depthwise separable convolution have several crucial limitations. First, they are heuristic methods, and their relation to the standard convolution is not clearly identified. Second, due to their heuristic nature, generalizing the methods is difficult. Third, although they give reasonable compression and computation reduction, their accuracy is not sufficient compared to that of standard-convolution-based models.
In this paper, we propose FALCON, an accurate and lightweight method for compressing CNN. FALCON overcomes the limitations of the previous methods based on the depthwise separable convolution using the following two main ideas. First, we precisely define the relationship between the standard convolution and the depthwise separable convolution using EHP (Extended Hadamard
Product), which is our proposed mathematical formulation to correlate the standard convolution kernel with the depthwise convolution kernel and the pointwise convolution kernel. We then design FALCON by fine-tuning and reordering the results of EHP to improve the accuracy of convolution operations. Second, based on the precise definition, we generalize the FALCON to design rank-k FALCON, which further improves accuracy while sacrificing a bit of compression and computation reduction rates. We also propose FALCON-branch by fitting FALCON into the state-of-the-art convolution unit ShuffleUnitV2 which gives even higher accuracy. As a result, FALCON and FALCON-branch provide a superior accuracy compared to other methods based on depthwise separable convolution, with similar compression and computation reduction rates, and rank-k FALCON further improves accuracy, outperforming even the original convolution in many cases. Our contributions are summarized as follows:
• Generalization. We analyze and generalize depthwise separable convolution to our proposed EHP (Extended Hadamard Product) operation. This generalization enables a precise understanding of the relationship between depthwise separable convolution and standard convolution. Furthermore, with fine-tuning operations, it leads to our proposed method FALCON. • Algorithm. We propose FALCON, a CNN compression method based on depthwise separable convolution. FALCON is carefully designed to compress CNN with little accuracy loss. We also propose rank-k FALCON to further improve the accuracy with a little sacrifice in compression and computation reduction rates. FALCON can be easily integrated into other architectures, and we propose FALCON-branch which combines FALCON with a branch architecture for a better performance. We theoretically analyze the compression and computation reduction rates of FALCON and other competitors. • Experiments. We perform extensive experiments and show that FALCON 1) outperforms other state-of-the-art methods based on depthwise separable convolution for compressing CNN, and 2) provides up to 8× compression and computation reduction compared to the standard convolution while giving similar accuracies. Furthermore, we show that rank-k FALCON provides even better accuracy than the standard convolution in many cases while using a smaller number of parameters and floating-point operations.
The rest of this paper is organized as follows. Section 2 explains preliminaries. Section 3 describes our proposed method FALCON. Section 4 presents experimental results. After discussing related works in Section 5, we conclude in Section 6.

heading: 2 PRELIMINARY

text: We describe preliminaries on depthwise separable convolution and methods based on depthwise separable convolution. Symbols used in this paper are described in Table 4 of Appendix.

heading: 2.1 DEPTHWISE SEPARABLE CONVOLUTION

text:
Depthwise Separable Convolution (DSConv) consists of two sub-layers: depthwise convolution and pointwise convolution. The architecture of each convolution layer in DSConv is illustrated in Figure 5(a). Depthwise convolution (DWConv) kernel consists of several D×D 2-dimensional filters. The number of 2-dimension filters is the same as that of input feature maps. Each filter is applied on the corresponding input feature map, and produces an output feature map. Pointwise convolution (PWConv), known as 1× 1 convolution, is a standard convolution with kernel size 1. DSConv is defined as follows:
O′h′,w′,m = D∑ i=1 D∑ j=1 Di,j,m · Ihi,wj ,m (1)
Oh′,w′,n = M∑ m=1 Pm,n ·O′h′,w′,m (2)
where Di,j,m and Pm,n are depthwise convolution kernel and pointwise convolution kernel, respectively. O′h′,w′,m ∈ RH ′×W ′×M denotes intermediate feature maps. DSConv performs DWConv on
input feature maps Ihi,wj ,m using equation 1, and generates intermediate feature maps O ′ h′,w′,m. Then, DSConv performs PWConv on O′h′,w′,m using equation 2, and generates output feature maps Oh′,w′,n.

heading: 2.2 METHODS BASED ON DEPTHWISE SEPARABLE CONVOLUTION

text: Several CNN methods have been proposed based on Depthwise Separable Convolution (DSConv) recently. DSConv was first introduced by Sifre (2014). Chollet & Franois (2016) built Xception module using DSConv in a few layers. Howard et al. (2017) built Mobilenet with all convolution layers replaced by DSConv. Sandler et al. (2018) built MobileNetV2 with inverted bottleneck block, denoted as MobileConvV2 in this paper. Zhang et al. (2017) built a CNN model with Shufflenet Unit, denoted as ShuffleUnit in this paper. Ma et al. (2018) improved Shufflenet by designing ShufflenetV2 Unit, denoted as ShuffleUnitV2 in this paper. The architecture and detailed descriptions are in Figure 5 and Appendix D.

heading: 3 PROPOSED METHOD

text: We describe FALCON, our proposed method for compressing CNN. We first define Extended Hadamard Product (EHP), a key mathematical formulation to generalize depthwise separable convolution, in Section 3.1. We interpret depthwise separable convolution used in Mobilenet using EHP in Section 3.2. We propose FALCON in Section 3.3 and explain why FALCON can replace standard convolution. Then, we propose rank-k FALCON, which extends the basic FALCON, in Section 3.4. We show that FALCON can be easily integrated into a branch architecture to compress it with little sacrifice of accuracy in Section 3.5. Finally, we theoretically analyze the performance of FALCON in Appendix C.

heading: 3.1 EXTENDED HADAMARD PRODUCT (EHP)

text:
We define Extended Hadamard Product (EHP), a generalized elementwise product for two operands of different shapes, to generalize the formulation of the relation between standard convolution and depthwise separable convolution. Before generalizing the formulation, we give an example of formulating the relation between standard convolution and depthwise separable convolution. Suppose we have a 4-order standard convolution kernel K ∈ RI×J×M×N , a 3-order depthwise convolution kernel D ∈ RI×J×M , and a pointwise convolution kernel P ∈ RM×N . Let Ki,j,m,n be (i, j,m, n)-th element of K, Di,j,m be (i, j,m)-th element of D, and Pm,n be (m,n)-th element of P. Then, it can be shown that applying depthwise convolution with D and pointwise convolution with P is equivalent to applying standard convolution kernel K where Ki,j,m,n = Di,j,m · Pm,n (see Section 3.2 for detailed proof).
To formally express this relation, we define Extended Hadamard Product (EHP) as follows.
Definition 1 (Extended Hadamard Product). Given p-order tensor D ∈ RI1×···×Ip−1×M and qorder tensor P ∈ RM×J1×···×Jq−1 , the Extended Hadamard Product D E P of D and P is defined to be the tensor K ∈RI1×...×Ip−1×M×J1×...×Jq−1 where the last axis of D and the first axis of P are the common axes such that
Ki1,...,ip−1,m,j1,...,jq−1 = Di1,...,ip−1,m ·Pm,j1,...,jq−1 for all elements of K.
Contrary to Hadamard Product which is defined only if the shapes of the two operands are the same, Extended Hadamard Product (EHP) deals with tensors of different shapes. Now, we define a special case of Extended Hadamard Product (EHP) for a third-order tensor and a matrix.
Definition 2 (Extended Hadamard Product for a third order tensor and a matrix). Given a thirdorder tensor D ∈ RI×J×M and a matrix P ∈ RM×N , the Extended Hadamard Product D E P is defined to be the tensor K ∈RI×J×M×N where the third axis of the tensor D and the first axis of the matrix P are the common axes such that
Ki,j,m,n = Di,j,m ·Pm,n. for all elements of K.
We will see that the depthwise separable convolution in Mobilenet can be easily expressed with EHP in Section 3.2; we also propose a new architecture FALCON based on EHP in Section 3.3. EHP is also a core operation that helps us understand other convolution architectures including MobilenetV2 and Shufflenet (see Appendix E).

heading: 3.2 DEPTHWISE SEPARABLE CONVOLUTION AND EHP

text:
In this section, we discuss how to represent the convolution layer of Mobilenet as Extended Hadamard Product (EHP) described in Section 3.1. We interpret the depthwise separable convolution, which is the convolution of Mobilenet, as an application of EHP. This interpretation leads to designing a better convolution architecture FALCON in Section 3.3.
We represent the relationship between standard convolution kernel K ∈ RD×D×M×N and depthwise separable convolution consisting of depthwise convolution kernel D ∈ RD×D×M and pointwise convolution kernel P ∈ RM×N using one EHP operation. Figure 2(a) illustrates the relationship between standard convolution and depthwise separable convolution used in Mobilenet. We show that applying depthwise separable convolution with D and P is equivalent to applying standard convolution with a kernel K which is constructed from D and P.
Theorem 1. Applying depthwise separable convolution with depthwise convolution kernel D ∈ RD×D×M and pointwise convolution kernel P ∈ RM×N is equivalent to applying standard convolution with kernel K = D E P.
Proof. See Appendix B.1.

heading: 3.3 FAST AND LIGHTWEIGHT CONVOLUTION (FALCON)

text:
We propose FALCON (FAst and Lightweight CONvolution), a novel lightweight convolution that replaces standard convolution. FALCON is an efficient method with fewer parameters and computations than those that the standard convolution requires. In addition, FALCON has better accuracy than competitors while having similar compression and computation reduction rates. The main idea of FALCON is 1) to carefully align depthwise and pointwise convolutions, and 2) initialize kernels using the convolution kernels of the trained standard model. We observe that a typical convolution has more output channels than input channels. In such a setting, performing depthwise convolution after pointwise convolution would allow the depthwise convolution to extract more features from richer feature space; on the other hand, performing pointwise convolution after depthwise convolution as in Mobilenet only combines features extracted from a limited feature space. Based on the observation, FALCON first applies pointwise convolution to generate an intermediate tensor O′ ∈ RH×W×N and then applies depthwise convolution.
We represent the relationship between standard convolution kernel K ∈ RD×D×M×N and FALCON by applying an EHP operation on pointwise convolution kernel P ∈ RN×M and depthwise convolution kernel D ∈ RD×D×N in Figure 2(b). In FALCON, the kernel K is represented by EHP of D and P as follows:
K = TT(1,2,4,3)(D E P) s.t. Ki,j,m,n = Pn,m ·Di,j,n. where TT(1,2,4,3) indicates tensor transpose operation to permute the third and the fourth dimensions of a tensor. Note that the common axis is the output channel axis of the standard convolution, unlike EHP for depthwise separable convolution where the common axis is the input channel axis of the standard convolution.
As in Section 3.2, we show that applying FALCON is equivalent to applying standard convolution with a specially constructed kernel.
Theorem 2. FALCON which applies pointwise convolution with kernel P ∈ RN×M and then depthwise convolution with kernel D ∈ RD×D×N is equivalent to applying standard convolution with kernel K = TT(1,2,4,3)(D E P).
Proof. See Appendix B.2.
Based on the equivalence, we initialize pointwise convolution and depthwise convolution kernels D and P of FALCON by fitting them to the convolution kernels of the trained standard model; i.e., D,P = argminD′,P′ ||K−TT(1,2,4,3)(D′ E P′)||F . After pointwise convolution and depthwise convolution, we add batch-normalization and ReLU activation function as shown in Figure 1(b). We note that FALCON significantly reduces the numbers of parameters and FLOPs compared to standard convolution, which we discuss at Appendix C.
3.4 RANK-k FALCON
We propose rank-k FALCON, an extended version of FALCON that improves accuracy while sacrificing a bit of compression and computation reduction rates. The main idea is to perform k independent FALCON operations and sum up the result. Then, we apply batch-normalization (BN) and ReLU activation function to the summed result. Since each FALCON operation requires independent parameters for pointwise convolution and depthwise convolution, the number of parameters increases and thus the compression and the computation reduction rates decrease; however, it improves accuracy by enlarging the model capacity. We formally define the rank-k FALCON with EHP as follows.
Definition 3 (Rank-k FALCON with Extended Hadamard Product). Rank-k FALCON expresses standard convolution kernel K ∈ RD×D×M×N as EHP of depthwise convolution kernel D(i) ∈
RD×D×N and pointwise convolution kernel P(i) ∈ RN×M for i = 1, 2, ..., k such that
K = k∑ i=1 TT(1,2,4,3)(D (i) E P(i)) s.t. Ki,j,m,n = k∑ i=1 P(i)n,m ·D (i) i,j,n
Figure 2(c) illustrates the relation between standard convolution and rank-k FALCON. For each i = 1, 2, ..., k, we construct the tensor K(i) using EHP of the depthwise convolution kernel D(i) and the pointwise convolution kernel P(i). Then, we construct the standard kernel K by the elementwise sum of the tensors K(i) for all i.

heading: 3.5 FALCON-BRANCH

text:
FALCON can be easily integrated into a CNN architecture called standard convolution operation with a branch (StConv-branch), which consists of two branches: standard convolution on the left branch and a residual connection on the right branch (see Figure 1(c)). Ma et al. (2018) improved the performance of CNN by applying depthwise and pointwise convolutions on the left branch of StConv-branch. Since FALCON replaces standard convolution, we observe that StConv-branch can be easily compressed by applying FALCON on the left branch.
StConv-branch first splits an input in half along the depth dimension. A standard convolution operation is applied to one half, and no operation to the other half. The two are concatenated along the depth dimension, and an output is produced by shuffling the channels of the concatenated tensor. FALCON-branch (see Figure 1(d)) is constructed by replacing the standard convolution branch (left branch) of StConv-branch with FALCON. Advantages of FALCON-branch are that 1) the branch architecture improves the efficiency since convolutions are applied to only half of input feature maps and that 2) FALCON further compresses the left branch effectively. FALCON-branch is initialized by fitting FALCON to the standard convolution kernel of the left branch of StConv-branch.

heading: 4 EXPERIMENTS

text:
We validate the performance of FALCON through extensive experiments. We aim to answer the following questions:
• Q1. Accuracy vs. Compression (Section 4.3). What are the accuracy and the compression tradeoffs of FALCON, FALCON-branch, and competitors? Which method gives the best accuracy for a given compression rate? • Q2. Accuracy vs. Computation (Section 4.4). What are the accuracy and the computation tradeoffs of FALCON, FALCON-branch, and competitors? Which method gives the best accuracy for a given amount of computation? • Q3. Rank-k FALCON (Section 4.5). How do the accuracy, the number of parameters, and the number of FLOPs change as the rank k increases in FALCON?

heading: 4.1 EXPERIMENTAL SETUP

text:
Datasets. We perform image classification task on four famous datasets - CIFAR10, CIFAR100, SVHN, and ImageNet. Detailed information of these datasets is described in Table 1.
Models. For CIFAR10, CIFAR100, and SVHN datasets, we choose VGG19 and ResNet34 to evaluate the performance. We shrink the sizes of both models since the sizes of these three datasets are smaller than that of Imagenet. In VGG19, we reduce the number of fully connected layers and the number of features in fully connected layers: three large fully connected layers (4096-4096-1000) in VGG19 are replaced with two small fully connected layers (512-10 or 512-100). In ResNet34, we remove the first 7 × 7 convolution layer and max-pooling layer since the input size (32 × 32) of these datasets is smaller than the input size (224 × 224) of ImageNet. On both models, we replace all standard convolution layers (except for the first convolution layer) with those of FALCON or other competitors in order to compress and accelerate the model. For ImageNet, we choose VGG16 BN (VGG16 with batch normalization after every convolution layer) and ResNet18. We use the pretrained model from Pytorch model zoo as the baseline model with standard convolution, and replace the standard convolution with other types of convolutions.
Competitors. We compare FALCON and FALCON-branch with four convolution units consisting of depthwise convolution and pointwise convolution: DSConv, MobileConvV2, ShuffleUnit, and ShuffleUnitV2 (see Figure 5, Section 2.1, and Appendix D for more details). To evaluate the effectiveness of fitting depthwise and pointwise convolution kernels to standard convolution kernel, we build EHP-in which is DSConv where kernels D and P are fitted from the pretrained standard convolution kernel K; i.e., D,P = argminD′,P′ ||K−D′ E P′||F .
Implementation. We construct all models using Pytorch framework. All the models are trained and tested on GeForce GTX 1080 Ti GPU.

heading: 4.2 FITTING CONVOLUTION UNIT INTO MODEL

text:
We evaluate the performance of FALCON against DSConv, MobileConvV2, ShuffleUnit, and ShuffleUnitV2. We take each standard convolution layer (StConv) as a unit, and replace StConv with those from FALCON or other competitors. We evaluate the classification accuracy, the number of parameters in the model, and the number of FLOPs needed for forwarding one image. We only explain how to apply FALCON in this section. The details of how to fit other convolution units into the models are described in Appendix F.
FALCON. When replacing StConv with FALCON, we use the same setting as that of StConv. I.e., if there are BN and ReLU after StConv, we add BN and ReLU at the end of FALCON; if there is only ReLU after StConv, we add only ReLU at the end of FALCON. This is because FALCON is initialized by approximating the StConv kernel using EHP. Using the same setting for BN and ReLU as StConv is more efficient for FALCON to approximate the StConv. We initialize the pointwise convolution kernel and the depthwise convolution kernel of FALCON by approximating the pretrained standard convolution kernel using EHP. The approximation process is as follows: 1) we first initialize the pointwise convolution kernel and the depthwise convolution kernel randomly, and 2) the pointwise convolution kernel and the depthwise convolution kernel are updated using gradient descent such that the mean squared error of their EHP product and the standard convolution kernel is minimized. Rank-k FALCON uses the same initialization method.

heading: 4.3 ACCURACY VS. COMPRESSION

text:
We evaluate the accuracy and the compression rate of FALCON and competitors. Table 2 shows the results on four image datasets. Note that FALCON or FALCON-branch provides the highest accuracy in 7 out of 8 cases while using similar or smaller number of parameters than competitors. Specifically, FALCON and FALCON-branch achieve up to 8× compression rates with less than 1% accuracy drop compared to that of the standard convolution (StConv). Figure 3 shows the tradeoff between accuracy and the number of parameters. Note that FALCON and FALCON-branch show the best tradeoff (closest to the “best” point) between accuracy and compression rate, giving the highest accuracy with similar compression rates.
Ablation study. We perform an ablation study on two components: 1) the order of depthwise and pointwise convolutions, and 2) initialization. We observe that with a similar number of parameters, 1) FALCON and FALCON without initialization always result in better accuracy than EHP-in and
DSC, respectively, and 2) EHP-in always results in better accuracy than DSC. Furthermore, FALCON results in better accuracy than FALCON without initialization in 6 out of 8 cases. These observations prove our claims in Section 3.3 that 1) EHP-out (FALCON) is more efficient than EHP-in, and 2) the fitting and the initialization of kernels using EHP improves accuracy. Additionally, we observe that overall performance is more sensitive towards ordering compared to initialization.

heading: 4.4 ACCURACY VS. COMPUTATION

text: We evaluate the accuracy and the amount of computation of FALCON and competitors. We use the number of multiply-adds floating point operations (FLOPs) needed for forwarding one image to a model as the metric of computation. Table 2 also shows the accuracies and the number of FLOPs of methods on four image datasets. Note that FALCON or FALCON-branch provide the highest accuracy in 7 out of 8 cases while using similar FLOPs as competitors do. Compared to StConv, FALCON and FALCON-branch achieve up to 8× FLOPs reduction across different models on different datasets. Figure 4 shows the tradeoff between accuracy and the number of FLOPs. Note that FALCON and FALCON-branch show the best tradeoff (closest to the “best” point) between accuracy and computation, giving the highest accuracy with a similar number of FLOPs.

heading: 4.5 RANK-K FALCON

text:
We evaluate the performance of rank-k FALCON by increasing the rank k and monitoring the changes in the numbers of parameters and FLOPs. In Table 3, we observe three trends as the rank k increases: 1) the accuracy becomes higher than that of rank-1 FALCON, 2) the number of parameters increases,
and 3) the number of floating point operations (FLOPs) increases. Although the rank k that gives the best tradeoff of rank and compression/computation reduction varies, rank-k FALCON improves the accuracy of FALCON in all cases. Especially, we note that rank FALCON often gives even higher accuracy than the standard convolution, while using smaller number of parameters and FLOPs. For example, rank-3 FALCON applied to VGG19 on CIFAR100 dataset shows 1.31 percentage point higher accuracy compared to the standard convolution, with 2.8× smaller number of parameters and 2.8× smaller number of FLOPs. Thus, rank-k FALCON is a versatile method to further improve the accuracy of FALCON while sacrificing a bit of compression and computation.

heading: 5 RELATED WORK

text:
Over the past several years, a lot of studies focused on compressing and accelerating DNN to reduce model size, running time, and energy consumption.
It is believed that DNNs are over-parameterized. Weight-sharing (Han et al. (2016); Ullrich et al. (2017); Chen et al. (2015); Choi et al. (2017); Agustsson et al. (2017)) is a common compression
method which stores only assignments and centroids of weights. While using the model, weights are loaded according to assignments and centroids. Pruning (Han et al. (2014); Li et al. (2016)) aims at removing useless weights or setting them to zero. Although weight-sharing and pruning can significantly reduce the model size, they are not efficient in reducing the amount of computation. Quantizing (Courbariaux et al. (2015; 2016); Hou et al. (2017); Zhu et al. (2017)) the model into binary or ternary weights reduces model size and computation simultaneously: replacing arithmetic operations with bit-wise operations remarkably accelerates the model.
Layer-wise approaches are also employed to efficiently compress models. A typical example of such approaches is low-rank approximation (Lebedev et al. (2015); Kim et al. (2016b); Novikov et al. (2015)); it treats the weights as a tensor and uses general tensor approximation methods to compress the tensor. To reduce computation, approximation methods should be carefully chosen, since some of approximation methods may increase computation of the model.
Compressing existing models has limitations since they are originally designed to be deep and large to give high accuracy. A recent trend is to design a brand new architecture that is small and efficient. Mobilenet (Howard et al. (2017)), MobilenetV2 (Sandler et al. (2018)), Shufflenet (Zhang et al. (2017)), and ShufflenetV2 (Ma et al. (2018)) are the most representative approaches, and they use depthwise convolution and pointwise convolution as building blocks for designing convolution layers. Our proposed FALCON gives a thorough interpretation of depthwise convolution and pointwise convolution, and applies them into model compression, giving the best accuracies with regard to compression and computation.

heading: 6 CONCLUSION

text: We propose FALCON, an accurate and lightweight convolution method to replace standard convolution. By interpreting existing convolution methods based on depthwise separable convolution using EHP operation, FALCON and its general version rank-k FALCON provide accurate and efficient compression on CNN. We also propose FALCON-branch, a variant of FALCON integrated into a branch architecture of CNN for model compression. Extensive experiments show that FALCON and its variants give the best accuracy for a given number of parameter or computation, outperforming other convolution models based on depthwise separable convolution. Compared to the standard convolution, FALCON and FALCON-branch give up to 8× compression and 8× computation reduction while giving similar accuracy. We also show that rank-k FALCON provides better accuracy than the standard convolution, while using smaller numbers of parameters and computations.

heading: A CONVOLUTIONAL NEURAL NETWORK

text:
Convolutional Neural Network (CNN) is a type of deep neural network used mainly for structured data. CNN uses convolution operation in convolution layers. In the following, we discuss CNN when applied to typical image data with RGB channels.
Each convolution layer has three components: input feature maps, convolution kernel, and output feature maps. The input feature maps I ∈ RH×W×M and the output feature maps O ∈ RH′×W ′×N are 3-dimensional tensors, and the convolution kernel K ∈ RD×D×M×N is a 4-dimensional tensor. The convolution operation is defined as:
Oh′,w′,n = D∑ i=1 D∑ j=1 M∑ m=1 Ki,j,m,n · Ihi,wj ,m (3)
where the relations between height hi and width wj of input, and height h′ and width w′ of output are as follows:
hi = (h ′ − 1)s+ i− p and wj = (w′ − 1)s+ j − p (4)
where s is the stride size, and p is the padding size. The third and the fourth dimensions of the convolution kernel K must match the number M of input channels, and the number N of output channels, respectively.
Convolution kernel K can be seen as N 3-dimensional filters Fn ∈ RD×D×M . Each filter Fn in kernel K performs convolution operation while sliding over all spatial locations on input feature maps. Each filter produces one output feature map.

heading: B PROOFS OF THEOREMS

text:
B.1 PROOF OF THEOREM 1
Proof. From the definition of EHP, Ki,j,m,n = Di,j,m ·Pm,n. Based on equation 3, we replace the kernel Ki,j,m,n with the depthwise convolution kernel Di,j,m and the pointwise convolution kernel Pm,n.
Oh′,w′,n = D∑ i=1 D∑ j=1 M∑ m=1 Di,j,m ·Pm,n · Ihi,wj ,m
where Ihi,wj ,m is the (hi, wj ,m)-th entry of the input. We split the above equation into the following two equations.
O′h′,w′,m = D∑ i=1 D∑ j=1 Di,j,m · Ihi,wj ,m (5)
Oh′,w′,n = M∑ m=1 Pm,n ·O′h′,w′,m (6)
where O′h′,w′,m ∈ RH ′×W ′×M is an intermediate tensor. Note that equation 5 and equation 6 correspond to the depthwise convolution and the pointwise convolution, respectively. Therefore, the output O′h′,w′,m is equal to the output applying depthwise separable convolution used in Mobilenet.
B.2 PROOF OF THEOREM 2
Proof. From equation 3, we replace the kernel Ki,j,m,n with the pointwise convolution kernel P and the depthwise convolution kernel D.
Oh′,w′,n = M∑ m=1 D∑ i=1 D∑ j=1 Pm,n ·Di,j,n · Ihi,wj ,m
where Ihi,wj ,m is the (hi, wj ,m)-th entry of the input I. We split the above equation into the following two equations.
O′hi,wj ,n = M∑ m=1 Pm,n · Ihi,wj ,m (7)
Oh′,w′,n = D∑ i=1 D∑ j=1 Di,j,n ·O′hi,wj ,n (8)
where I, O′, and O are the input, the intermediate, and the output tensors of convolution layer, respectively. Note that equation 7 and equation 8 correspond to pointwise convolution and depthwise convolution, respectively. Therefore, the output Oh′,w′,n is equal to the output applying FALCON.

heading: C QUANTITATIVE ANALYSIS

text:
In this section, we evaluate the compression and the computation reduction of FALCON and rank-k FALCON. All the analysis is based on one convolution layer. The comparison of the numbers of parameters and FLOPs of FALCON and other competitors is in Appendix G.
C.1 FALCON
We analyze the compression and the computation reduction rates of FALCON in Theorems 3 and 4.
Theorem 3. Compression Rate (CR) of FALCON is given by
CR = # of parameters in standard convolution
# of parameters in FALCON =
D2MN
MN +D2N
where D2 is the size of standard kernel, M is the number of input channels, and N is the number of output channels.
Proof. Standard convolution kernel has D2MN parameters. FALCON includes pointwise convolution and depthwise convolution which requires MN and D2N parameters, respectively. Thus, the compression rate of FALCON is CR = D2MN
MN +D2N .
Theorem 4. Computation Reduction Rate (CRR) of FALCON is described as:
CRR = # of FLOPs in standard convolution
# of FLOPs in FALCON
= H ′W ′MD2N
HWMN +H ′W ′D2N where H ′ and W ′ are the height and the width of output, respectively, and H and W are the height and the width of input, respectively.
Proof. The standard convolution operation requires H ′W ′D2MN FLOPs (Molchanov et al. (2017)). FALCON includes pointwise convolution and depthwise convolution. Pointwise convolution has kernel size D = 1 with stride s = 1 and no padding, so the intermediate tensor O′ has the same height and width as those of the input feature maps. Thus, pointwise convolution needs HWMN FLOPs. Depthwise convolution has the number of input channel M = 1, so it needs H ′W ′D2N FLOPs. The total FLOPs of FALCON is HWMN +H ′W ′D2N , thus the computation reduction rate of FALCON is CRR = H ′W ′D2MN
HWMN +H ′W ′D2N .
C.2 RANK-K FALCON
We analyze the compression and computation reduction rates of rank-k FALCON in Theorem 5.
Theorem 5. Compression Rate (CRk) and Computation Reduction Rate (CRRk) of rank-k FALCON are described as:
CRk = CR
k CRRk =
CRR
k
Proof. The numbers of parameters and FLOPs increase for k times since rank-k FALCON duplicates FALCON for k times. Thus, the compression rate and the computation reduction rate are calculated as CRk = CR
k and CRRk =
CRR
k .

heading: D DESCRIPTION OF RELATED CONVOLUTION UNITS

text:
MobileNetV2. Sandler et al. (2018) proposed a new convolution architecture which we call as MobileConvV2, in their MobilenetV2 model. MobileConvV2 consists of three sub-layers as shown in Figure 5(b). The first and the third sub-layers are pointwise convolution for adjusting the number of channels. The first sub-layer expands the number of channels from M to tM , where t is an
expansion ratio. The second sub-layer is a D×D depthwise convolution. Since depthwise convolution cannot change the number of channels, the third sub-layer adjusts the number of channels from tM to N . There is a shortcut connection between the input, and the output of the third sub-layer to facilitate flow of gradient across multiple layers. MobileConvV2 needs tM2 + D2tM + tMN parameters and tHWM2 + tH ′W ′D2M + tH ′W ′MN FLOPs.
ShuffleNet. Zhang et al. (2017) proposed a computation-efficient CNN architecture named Shufflenet. As shown in Figure 5(c), each unit of Shufflenet (we call it ShuffleUnit) consists of three sublayers, first group pointwise convolution, depthwise convolution, and second group pointwise convolution, as well as a shortcut. The number of depthwise convolution channels is 14 of output channels N . ShuffleUnit uses group convolution in two pointwise convolution layers to reduce the parameters and FLOPs. However, it is hard to exchange information among groups when group convolutions are stacked. To deal with this problem, ShuffleUnit adds a channel shuffle layer after the first pointwise group convolution. The channel shuffle layer rearranges the order of channels. making it possible to obtain information from different groups. The number of groups is represented as g. ShuffleUnit needs 14gMN+ 1 4D 2N+ 14gN 2 parameters and 14gHWMN+ 1 4H ′W ′D2N+ 14gH ′W ′N2 FLOPs.
ShufflenetV2. Ma et al. (2018) proposed a practically efficient CNN architecture ShufflenetV2. As shown in Figure 5(d), each unit of ShufflenetV2 (we call it ShuffleUnitV2) consists of two branches. The left branch consists of two pointwise convolutions and one depthwise convolution like MobileConvV2, and the right branch is an identity operation. Note that outputs of both branches maintain the number of channels as M/2. The final output is produced by concatenating and shuffling the output tensors from both of the branches. ShuffleUnitV2 needs 12 (M
2+D2M) parameters and 12HW (M 2 +D2M) FLOPs.

heading: E GENERALITY OF EHP

text:
We show that EHP is a key operation to understand other convolution architectures based on depthwise separable convolution.
MobilenetV2. As shown in Figure 5(b), MobilenetV2 has an additional pointwise convolution before depthwise convolution in Mobilenet: one layer of MobilenetV2 consists of two pointwise convolutions and one depthwise convolution. In another point of view, MobilenetV2 can be understood as FALCON followed by additional pointwise convolution; i.e., MobilenetV2 performs EHP operation as FALCON does, and performs additional pointwise convolution after that.
Shufflenet. As shown in Figure 5(c), Shufflenet consists of depthwise convolution and pointwise group convolution which is a variant of pointwise convolution. We represent the convolution layer of Shufflenet using EHP as follows. Let g be the number of groups. We divide the standard convolution
kernel K ∈ RD×D×M×N into g group standard convolution kernels. Then, the relation of g-th group standard convolution kernel Kg ∈ RD×D× M g × N g with regard to g-th depthwise convolution kernel Dg ∈ RD×D× M g and g-th pointwise group convolution kernel Pg ∈ R M g × N g is
Kg = Dg E Pg s.t. Kgi,j,mg,ng = D g i,j,mg ·Pgmg,ng
where mg = 1, 2, ..., Mg and ng = 1, 2, ..., N g . Each group standard convolution is equivalent to the combination of a depthwise convolution and a pointwise convolution, and thus easily expressed with EHP as in Mobilenet.
Therefore, each layer of Shufflenet is equivalent to the layer consisting of one group convolution followed by standard convolution.
ShufflenetV2. As shown in Figure 5(d), the left branch of ShufflenetV2 has the same convolutions as in MobilenetV2: it consists of two pointwise convolutions and one depthwise convolution. Like MobilenetV2, the left branch of ShufflenetV2 can be understood as FALCON followed by additional pointwise convolution.

heading: F FITTING OTHER CONVOLUTION UNITS INTO MODELS

text:
DSConv. DSConv (shown in Figure 5(a)) has the most similar architecture as FALCON among competitors, and thus DSConv has nearly the same number of parameters as that of FALCON. As in the setting of FALCON, the existence of BN and ReLU at the end of DSConv depends on that of StConv.
MobileConvV2. In MobileConvV2 architecture (shown in Figure 5(b)), we adjust the numbers of parameters and FLOPs by changing the expansion ratio t as described in Appendix D, which is represented as ‘MobileConvV2-t’. We choose t = 0.5 as the baseline MobileConvV2 to compare with FALCON, since two pointwise convolutions bring lots of parameters and FLOPs to MobileConvV2.
ShuffleUnit. In ShuffleUnit (shown in Figure 5(c)), we adjust the numbers of parameters and FLOPs by changing the width multiplier α (Howard et al. (2017)) and the number of groups g, which is represented as ‘ShuffleUnit α×(g=g)’. Note that the width multiplier is used to adjust the number of input channels M and the number of output channels N of a convolution layer; if the width multiplier is α, the numbers of input and output channels become αM and αN , respectively. While experimenting with ResNet, we find that ShuffleUnit does not cooperate well with ResNet: ResNet34 with ShuffleUnit does not converge. We suspect that residual block and ShuffleUnit may conflict with each other because of redundant residual connections: the gradient may not find the right path towards previous layers. For this reason, we delete the shortcut of all residual blocks in ResNet34 when using ShuffleUnit.
ShuffleUnitV2. In ShuffleUnitV2 (shown in Figure 5(d)),we also adjust the number of parameters and FLOPs by changing the width multiplier α, which is represented as ’ShuffleUnitV2 α×’. Other operations of ShuffleUnitV2 stay the same as in Ma et al. (2018).

heading: G PARAMETERS AND FLOPS

text: We summarize the numbers of parameters and FLOPs for FALCON and competitors in Table 5.