summaries: In this paper, the authors propose a spatial-Winograd pruning framework, consisting of spatial structured pruning and Winograd direct pruning.  First, spatial structured pruning allows the pruned weight in the spatial domain to be kept in the Winograd domain. Then, Winograd direct pruning can further improve the sparsity in the Winograd domain. The organization of paper is OK.  The main concern is about the practical part. In the experiment, the advantage of propose framework is marginal, compared to the relevant approaches.  More comparisons with the state-of-the-art approaches should be investigated, such as light-weight design (MobileNet, ShuffleNet).

summaries: The paper proposes a technique (well, two) to prune convolutional layers to reduce the required amount of computation when  the convolutions are done using the winograd algorithm. Winograd convolutions first transform the image and the filter, apply a multiplication in the transformed space, and then retransform the image back to the intended image space. The transformation of the filter, however, means that sparsity in the regular domain does not translate to sparsity in the winograd domain.

abstractText: Deep convolutional neural networks (CNNs) are deployed in various applications but demand immense computational requirements. Pruning techniques and Winograd convolution are two typical methods to reduce the CNN computation. However, they cannot be directly combined because Winograd transformation fills in the sparsity resulting from pruning. Li et al. (2017) propose sparse Winograd convolution in which weights are directly pruned in the Winograd domain, but this technique is not very practical because Winograd-domain retraining requires low learning rates and hence significantly longer training time. Besides, Liu et al. (2018) move the ReLU function into the Winograd domain, which can help increase the weight sparsity but requires changes in the network structure. To achieve a high Winograd-domain weight sparsity without changing network structures, we propose a new pruning method, spatial-Winograd pruning. As the first step, spatial-domain weights are pruned in a structured way, which efficiently transfers the spatial-domain sparsity into the Winograd domain and avoids Winograd-domain retraining. For the next step, we also perform pruning and retraining directly in the Winograd domain but propose to use an importance factor matrix to adjust weight importance and weight gradients. This adjustment makes it possible to effectively retrain the pruned Winograd-domain network without changing the network structure. For the three models on the datasets of CIFAR10, CIFAR-100, and ImageNet, our proposed method can achieve the Winograddomain sparsities of 63%, 50%, and 74%, respectively.

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient dnns

venue: In Advances In Neural Information Processing Systems,

authors:
Song Han
Huizi Mao
William J Dally

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

venue: arXiv preprint arXiv:1510.00149,

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

venue: In Advances in neural information processing systems,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

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

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Andrew Lavin
Scott Gray

title: Fast algorithms for convolutional neural networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Sheng Li
Jongsoo Park
Ping Tak Peter Tang

title: Enabling sparse winograd convolution by native pruning

venue: arXiv preprint arXiv:1702.08597,

authors:
Xingyu Liu
Yatish Turakhia

title: Pruning of winograd and fft based convolution

authors:
Xingyu Liu
Jeff Pool
Song Han
William J Dally

title: Efficient sparse-winograd convolutional neural networks

venue: arXiv preprint arXiv:1802.06367,

authors:
Michael Mathieu
Mikael Henaff
Yann LeCun

title: Fast training of convolutional networks through ffts

venue: arXiv preprint arXiv:1312.5851,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

venue: NIPS-W,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International Journal of Computer Vision,

authors:
Jost Tobias Springenberg
Alexey Dosovitskiy
Thomas Brox
Martin Riedmiller

title: Striving for simplicity: The all convolutional net

venue: arXiv preprint arXiv:1412.6806,

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning structured sparsity in deep neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
Jiecao Yu
Andrew Lukefahr
David Palframan
Ganesh Dasika
Reetuparna Das
Scott Mahlke

title: Scalpel: Customizing dnn pruning to the underlying hardware parallelism

venue: In ACM SIGARCH Computer Architecture News,

heading: 1 INTRODUCTION

text:
Deep convolutional neural networks (CNNs) have been ubiquitously utilized in various application domains. However, their performance comes at the cost of a significant amount of computation which keeps growing over time. As an example, for the ImageNet challenge (Russakovsky et al., 2015), Krizhevsky et al. (2012) proposed AlexNet which requires more than 1.1 × 109 multiplications. Later, in 2016, the ResNet-152 model (He et al., 2016) increased the computation cost to 11.3 × 109 multiplications. This high computation cost limits the deployment of larger and deeper CNN models.
There are two primary methods to reduce the required computation of CNN models: pruning techniques and Winograd/FFT convolution. Pruning removes redundant weight parameters, inducing sparsity into the network. On the other hand, Winograd convolution (Lavin & Gray, 2016) and FFT convolution (Mathieu et al., 2013) transform the computation into different domains. The convolution operations can then be replaced by element-wise multiplications. For the typical convolution kernel size of 3 × 3, Winograd convolution can achieve more than twofold speedup over highly optimized spatial convolution algorithms, and typically requires fewer flops than FFT-based approaches (Li et al., 2017). Therefore, in this paper, we focus on the Winograd convolution.
The pruning techniques and Winograd convolution are not directly compatible with each other. Sparse weight matrices, which are generated by pruning, lose most of the sparsity after the Winograd transformation from the spatial (original) domain to the Winograd domain. The remaining sparsity is much lower than what we need for improving computation performance.
To increase the Winograd-domain sparsity, Li et al. (2017) propose to perform pruning and retraining directly on Winograd-domain weights. However, it requires using an extremely small learning rate,
e.g., 200x smaller for AlexNet, in retraining and is difficult to be applied to deep networks. Besides, Winograd-ReLU pruning (Liu et al., 2018) moves ReLU function into the Winograd domain, which helps increase Winograd-domain sparsity but requires changes in the network structure.
In this paper, to further improve the sparsity of Winograd-domain weights without changing the network structure, we propose a new pruning method, spatial-Winograd pruning. It includes two parts: spatial structured pruning and Winograd direct pruning. In spatial structured pruning, we prune the spatial-domain weights in a structured way, in which the structures are designed to transfer the spatial-domain sparsity into the Winograd domain efficiently. After spatial structured pruning, weights of the pruned layers will be converted to and kept in the Winograd domain. Then, for Winograd direct pruning, we perform pruning and retraining entirely in the Winograd domain to improve the sparsity further.
This paper makes the following contributions:
• We propose a new pruning method, spatial-Winograd pruning. Without changing the network structure, it can achieve higher sparsity in Winograd-domain weights compared with previous methods.
• As the first part of spatial-Winograd pruning, we provide a structured pruning method to transfer the spatial-domain sparsity into the Winograd domain efficiently. It can help avoid Winograd-domain retraining in this part and accelerate the pruning process.
• In the second part, to perform pruning directly in the Winograd domain, we present a new approach to measuring the importance of each Winograd-domain weight based on its impact on output activations. Also, we propose to use an importance factor matrix to adjust the gradients of Winograd-domain weights, which makes it much faster to retrain deep networks directly in the Winograd domain without changing the network structure.

heading: 2 PRELIMINARY AND RELATED WORK

text:
Winograd convolution (Lavin & Gray, 2016) is a typical algorithm to reduce the arithmetic complexity of CNNs. It transforms the computation into the Winograd domain, and the convolution operations can then be replaced by element-wise multiplications. We call the domain, in which the conventional convolution operation is executed, to be the spatial domain.
The basic block of Winograd convolution works on a 2D input tile, I , with a size of m ×m and a 2D weight filter, W , with a size of n × n. In this case, the 2D output tile generated, O, will have a size of (m − n + 1) × (m − n + 1). For a typical convolutional layer, the input feature maps are first disassembled into input tiles and, after the Winograd convolution, the output tiles will be reassembled into the output feature maps.
Figure 1a shows how conventional Winograd convolution works. As the first step, the weight filter W and the input tile I are converted into the Winograd domain using the predefined matrices G and B. Element-wise multiplication is then applied to the Winograd-domain weight filter, GWG>, and input tile, B>I B, to generate the Winograd-domain output tile with a size of m ×m. In the last step, the output tile is converted back into the spatial domain with another predefined matrix A. With as the Hadamard product (element-wise multiplication), the entire process can be written as
O = A>[(GWG>) (B>I B)]A (1)
The transform/inverse-transform matrices A, B and G are only determined by m and n. These matrices contain many repeating elements and applying them requires only few multiplications. In this case, considering only the element-wise multiplication between GWG> and B>I B, the Winograd convolution can reduce the number of multiplications from (m− n+ 1)2n2 to m2. In addition to Winograd convolution, pruning is also a well-explored method to reduce CNN computation. Han et al. (2015b;a) propose to perform pruning and retraining iteratively, which can help reduce the computation by up to 5×. To fully utilize the sparsity incurred by pruning to accelerate CNN computation, Wen et al. (2016) and Yu et al. (2017) prune networks in a structured way: weights are clustered into groups with hardware-friendly structures and then get pruned in groups.
However, Winograd convolution is not directly compatible with conventional pruning algorithms. The transformation GWG> fills in the zeros in the sparse weight filters generated by pruning. There have been several research attempts to solve this problem.
Liu & Turakhia (2016) propose to directly mask out Winograd-domain weights and use backpropagation to train the spatial-domain weights. However, compared with spatial-domain weights, Winograd-domain weights are in a higher-dimensional space. Directly setting Winograd-domain weights to zero will cause an inconsistency between the spatial domain and the Winograd domain. This inconsistency will lead to a significant accuracy loss or a low sparsity on networks, e.g., AlexNet, for large datasets (Li et al., 2017).
To address the inconsistency between the spatial and Winograd domain, Li et al. (2017) propose the sparse Winograd convolution. Figure. 1b shows how it works. Weight values are stored in the Winograd domain instead of the spatial domain. Both pruning and retraining are applied directly to Winograd-domain weights. This native pruning algorithm achieves > 90% sparsity on AlexNet (Krizhevsky et al., 2012) but cannot provide a high sparsity for deep networks (Liu et al., 2018). Also, direct retraining in the Winograd domain requires an extremely small learning rate, e.g., 200x smaller for AlexNet, which makes the retraining much slower.
Based on sparse Winograd convolution, Liu et al. (2018) introduce the Winograd-ReLU pruning. It moves the ReLU function from the spatial domain into the Winograd domain. In this case, the computation of Winograd convolution becomes
O = A>[(GWG>) ReLU(B>I B)]A (2)
The Winograd-domain inputs also become sparse, which helps further reduce the required computation. Besides, a higher sparsity in Winograd-domain weights can be achieved. However, with weight filters being sparse, it is challenging to utilize both the weight and input sparsity for CNN acceleration on general-purpose processors due to more irregularity in the access pattern and control flow. Also, Winograd-ReLU pruning cannot be applied to conventional CNN models since the new computation in Equation 2 does not correspond to the original convolution operation. It requires changing the network structure and retraining the network from scratch.

heading: 3 SPATIAL-WINOGRAD PRUNING

text:
In this paper, to achieve a high Winograd-domain weight sparsity on deep CNN models without changing network structures, we propose the spatial-Winograd pruning. As shown in Figure 2, it consists of two parts: spatial structured pruning and Winograd direct pruning.
In spatial structured pruning, spatial-domain weights are pruned in a structured way and then retrained to regain the original accuracy. After spatial structured pruning, the weights of the pruned model will be transferred into and kept in the Winograd domain. The Winograd direct pruning then
performs pruning and retraining directly onto the weights in the Winograd domain. The pruning and retraining steps in both spatial structured pruning and Winograd direct pruning will be iteratively executed until we achieve the desired sparsity or the produced model loses much accuracy.

heading: 3.1 SPATIAL STRUCTURED PRUNING

text:
The first part of the spatial-Winograd pruning is spatial structured pruning. Spatial-domain weights which affect the same Winograd-domain weight are clustered into the same group. Less important weight groups are removed, and the pruned network will be retrained to regain the accuracy. This structured pruning method can help transfer more spatial-domain sparsity into the Winograd domain.
Spatial Pruning For each spatial-domain filter W , we need to generate a mask M spatial to indicate the redundant weights. Assuming W has a size of n× n and the Winograd-domain filter Q is m×m, we have Q = GWG>. Each element of the Winograd-domain filter, Qi,j , is the weighted sum of the spatial-domain weights:
Qi,j = ∑
06u,v6n−1
(Si,j,u,v ·Wu,v) 0 6 i, j 6 m− 1 (3)
where S is a 4D tensor containing the weight coefficients of the spatial-domain weights and is only determined by m and n. Details about the calculation of S can be found in Appendix A.1.
For each Winograd-domain weight Qi,j , we can create a set Di,j containing the spatial-domain weights which affect the value of Qi,j . Di,j is defined as
Di,j = {Wu,v ∣∣ Si,j,u,v 6= 0, 0 6 u, v 6 n− 1} (4)
In this case, for each weight group Di,j , we use a function h(Di,j) to measure its importance. In this paper, we use the maximum norm function as h
h(Di,j) = max({ |Wu,v| ∣∣Wu,v ∈ Di,j}) (5)
With a specific threshold tspatial, if h(Di,j) < tspatial, then Di,j is considered as redundant and all weights included need to be removed. In this case, the corresponding Qi,j will be fixed to 0 and also removed. The set of redundant weights for entire W is the union of all redundant Di,j and can be calculated as
D = ⋃
06i,j6m−1,h(Di,j)<tspatial Di,j (6)
Here we define Di,j in a structured way based on the relation between spatial-domain weights and Winograd-domain weights. It helps transfer as much spatial-domain sparsity into Winograd-domain sparsity as possible.
The mask matrix M spatial can be generated by
M spatialu,v = { 0 Wu,v ∈ D 1 Wu,v /∈ D 0 6 u, v 6 n− 1 (7)
Spatial Retraining After spatial pruning, we can perform the spatial retraining with conventional training algorithms, e.g., stochastic gradient descent (SGD). The removed weights are fixed to 0 by applying W = W M spatial after each training iteration. is element-wise multiplication. The steps of spatial pruning and spatial retraining will be iteratively performed until the retrained model loses much accuracy. The threshold tspatial is gradually increased to incur more sparsity into the network.
In spatial structured pruning, both pruning and retraining steps are performed in the spatial domain. It helps avoid the Winograd-domain retraining to accelerate the pruning process but, at the same time, incurs high Winograd-domain sparsity.

heading: 3.2 WINOGRAD DIRECT PRUNING

text:
After spatial structured pruning, as in sparse Winograd convolution, weights of the pruned model will be transferred into and kept in the Winograd domain. In Winograd direct pruning, we measure
the importance of each weight based on its impact on output activations, and unimportant weights are removed. The pruned network is then retrained in the Winograd domain, and an importance factor matrix is deployed to adjust the weight gradients.
Winograd Pruning Similar to spatial pruning, in Winograd pruning, we need to generate a mask matrix MWinograd for each Winograd-domain filter Q to indicate the redundant weights. With the weight filter Q in the Winograd domain, the output tile O is calculated as
O = A>[Q (B>I B)]A (8)
Each output element can be considered as the weighted sum of the products of weights and inputs Ox,y = ∑
06i,j,s,t6m−1
(Hx,y,i,j,s,t ·Qi,j · Is,t) 0 6 x, y 6 m− n (9)
where H is a 6D tensor containing the weight coefficients of different products (Qi,j · Is,t) and is only determined by m and n. Details about the calculation of H can be found in Appendix A.2.
By removing one weight Qi,j , the change on each output Ox,y is ∆Ox,y|Qi,j = −1 · ∑
06s,t6m−1
(Hx,y,i,j,s,t ·Qi,j · Is,t) 0 6 x, y 6 m− n (10)
In Winograd pruning, we need to remove a certain amount of weights while minimizing the change of the output activations ||∆O||2. Removing an important weight will lead to a larger change in output activations. Therefore, we propose to measure the importance of each weight Qi,j by the expected value of ||∆O|Qi,j || 2 2. In this case, we have
E(||∆O|Qi,j || 2 2) = E ( ∑ 06x,y6m−n [ ∑ 06s,t6m−1 (Hx,y,i,j,s,t ·Qi,j · Is,t) ]2)
= Q2i,j · { ∑
06x,y6m−n,06s,t6m−1
[ H2x,y,i,j,s,t · E(I2s,t) ] +
∑ 06x,y6m−n
06s,t,s′,t′6m−1 (s,t)6=(s′,t′)
[ Hx,y,i,j,s,t ·Hx,y,i,j,s′,t′ · E(Is,t · Is′,t′)
]} (11)
For simplicity, we can assume input values are independent and identically distributed (i.i.d.), and have expected values of 0. With this assumption, we have
E(Is,t · Is′,t′) = E(Is,t) · E(Is′,t′) = 0 (s, t) 6= (s′, t′) (12)
Since the importance of weights are relative numbers, we can assume E(I2s,t) = 1. In this case,
E(||∆O|Qi,j || 2 2) = Q 2 i,j · ∑ 06x,y6m−n,06s,t6m−1 H2x,y,i,j,s,t (13)
Based on Equation. 13, we can generate an importance factor matrix F , where
Fi,j =
√ E(||∆O|Qi,j || 2 2)
Q2i,j = √ ∑ 06x,y6m−n,06s,t6m−1 H2x,y,i,j,s,t 0 6 i, j 6 m− 1 (14)
Therefore, F is only determined bym and n, and keeps the same for all 2D Winograd-domain filters Q in a specific layer. Then Equation. 13 can be simplified to
E(||∆O|Qi,j || 2 2) = Q 2 i,j · F 2i,j (15)
In this case, with a specific threshold tWinograd, we can generate the mask matrix MWinograd as
MWinogradi,j = { 0 Q2i,j · F 2i,j < tWinograd 1 Q2i,j · F 2i,j > tWinograd
0 6 i, j 6 m− 1 (16)
For a specific weight Qi,j , conventional pruning algorithms (Han et al., 2015b; Guo et al., 2016) use its absolute value |Qi,j | as the weight importance, which is equivalent to using Q2i,j . Therefore, in Equation 16, the employed weight importance, Q2i,j ·F 2i,j , can be considered as using the importance factor matrix F to adjust the conventional weight importance Q2i,j .
Winograd Retraining As the same with the spatial retraining, we fix the removed Winograddomain weights to 0 by applying Q = Q MWinograd after each training iteration. However, using conventional SGD to retrain the Winograd-domain parameters will lead to divergence. This is because, as shown in Equation. 14, different locations of Winograd-domain weights have different importance and, therefore, require different learning speeds. Using an extremely small learning rate can avoid the divergence but makes the retraining much slower.
To address this problem, in Winograd retraining, we propose to adjust the gradients of Winograddomain weights with the importance factor matrix F . Assume loss to be the loss value. At the training step k, after the backward computation, the gradients of Q, ∂ loss∂Q |k, will be adjusted by
( ∂ loss
∂Q ∣∣∣ k )adjusted = ∂ loss ∂Q ∣∣∣ k F ◦α (17)
where and ◦α are the Hadamard division (element-wise division) and Hadamard power (elementwise power of α) function, respectively. In this paper, based on empirical results, α is fixed to 1.5. In this case, with the learning rate of η, the SGD update for the Winograd-domain weights Q at the training step k becomes
Q|k+1 = Q|k − η · ( ∂ loss
∂Q ∣∣∣ k F ◦α) (18)

heading: 4 EXPERIMENTS

text:
To evaluate the spatial-Winograd pruning, we perform the experiments on three datasets: CIFAR10, CIFAR-100 (Krizhevsky, 2009) and ImageNet (ILSVRC-2012) (Russakovsky et al., 2015). PyTorch (Paszke et al., 2017) is used to implement the pruning framework.
We use the Winograd-ReLU pruning (Liu et al., 2018) as the baseline pruning technique. To show the effectiveness of our proposed method, we test the same models as in Winograd-ReLU pruning: VGG-nagadomi (Nagadomi, 2014), ConvPool-CNN-C (Springenberg et al., 2014) and ResNet18 (He et al., 2016) on the three datasets tested, respectively. Those models are chosen since the majority of the included convolutional layers use 3× 3 kernels. For 3×3 kernels, we set the input tile sizem to 6 instead of 4. A larger input tile size can help achieve higher computation speedup. With our proposed method, we expect that lower input tile sizes can lead to a similar or higher sparsity. This is because, with lower input tile sizes, the spatial-domain weights have less correlation between each other and the spatial structured pruning can achieve a higher sparsity.

heading: 4.1 CIFAR-10: VGG-NAGADOMI

text:
For the CIFAR-10 dataset, we test the VGG-nagadomi model (Nagadomi, 2014). It contains 8 convolutional layers with 3×3 kernels. We use batch normalization instead of dropout to regularize the convolutional layers. The original model has a prediction accuracy of 93.96%. We prune the first convolutional layer with a fixed Winograd-domain sparsity of 20%. For the remaining convolutional layers, we incur a uniform Winograd-domain sparsity, increasing from 20% to 80%, for simplicity.
Figure 3a shows the pruning results. The baseline result reported in (Liu et al., 2018) is shown as the dashed line. With <0.1% accuracy loss, it achieves a sparsity of 60%. With spatial-Winograd pruning, we can achieve a Winograd-domain sparsity of 63%. It is similar to Winograd-ReLU pruning, but spatial-Winograd pruning does not require changing the network structure.

heading: 4.2 CIFAR-100: CONVPOOL-CNN-C

text:
For the CIFAR-100 dataset, the ConvPool-CNN-C model (Springenberg et al., 2014) is tested. It contains 9 convolutional layers, in which 7 layers use 3 × 3 kernels. The original model has a
prediction accuracy of 69.95%. We prune the first convolutional layer with a fixed Winograd-domain sparsity of 20%. Similar to the VGG-nagadomi model, the remaining 6 convolutional layers with 3× 3 kernels are iteratively pruned and retrained with uniform Winograd-domain sparsities. Figure. 3b shows the result of the relative accuracy against the Winograd-domain sparsity. The baseline result reported in (Liu et al., 2018) is shown as the dashed line. With <0.1% accuracy loss, it achieves a sparsity of 40%. Winograd direct pruning is applied to the model pruned by spatial structured pruning with 30% sparsity. With no accuracy loss, spatial-Winograd pruning can reach a sparsity of 50%, which is 10% higher than Winograd-ReLU pruning.

heading: 4.3 IMAGENET: RESNET-18

text:
We test the ResNet-18 model on the ImageNet (ILSVRC-2012) dataset. As the same with WinogradReLU pruning, we replace each 2×2-stride 3×3 convolutional layer with a 2×2-stride max-pooling layer followed by a 1 × 1-stride 3 × 3 convolutional layer. This change makes it easier to apply Winograd convolution on most of the convolutional layers.
The original model has a top-1/top-5 prediction accuracy of 69.82%/89.55%. However, for Winograd-ReLU pruning, Liu et al. (2018) use the model with the original top-1/top-5 accuracy of only 66.67%/87.42%. Despite this, we still use the relative accuracies reported in (Liu et al., 2018) as the baseline.
We prune the 16 convolutional layers in the residual blocks with the same Winograd-domain sparsity. The first convolutional layer and the downsample layers are kept intact. Figure. 4 shows the results of the relative accuracy against the Winograd-domain sparsity. As the dashed line show, the WinogradReLU pruning achieves a sparsity of 70%/65% with <0.1% top-1/top-5 accuracy loss.
We apply Winograd direct pruning to the models pruned by spatial structured pruning with 65% and 70% Winograd-domain sparsity, annotated as Winograd direct pruning - 0.65 and 0.70, respectively. As shown in the figure, with <0.1% top-1/top-5 accuracy loss, applying Winograd direct pruning to the model with 70% Winograd-domain sparsity can achieve a higher sparsity of 74%/72%. This is
because, with the sparsity increasing, Winograd direct pruning makes the prediction accuracy drop much faster than spatial structured pruning. Although we can use the importance factor matrix F to adjust the weight gradients to accelerate the Winograd-domain retraining, the learning rate still needs to be much lower than in the spatial retraining. In this case, the accuracy loss recovered through Winograd retraining is limited, which makes the accuracy drop much faster when applying Winograd direct pruning.

heading: 4.4 EFFECTIVENESS OF IMPORTANCE FACTOR MATRIX

text:
In Winograd direct pruning, we use the importance factor matrix F to adjust the weight importance and gradients for different locations of Winograd-domain weights. Here we test the effectiveness of employing the importance factor matrix in both the Winograd pruning and retraining.
We first test how the importance factor matrix F helps in Winograd pruning. Winograd pruning without retraining is applied to the model pruned by spatial structured pruning with 70% sparsity. Figure 5a shows the relative accuracy against the sparsity when pruning with weight importance unadjusted or adjusted with F . As shown in the figure, adjusting the weight importance with the importance factor matrix can dramatically reduce the accuracy loss when performing Winograd pruning. When pruning the model to 76% sparsity, using the absolute value as the weight importance will cause a 22% accuracy loss. In comparison, using the importance factor matrix to adjust the weight importance can help reduce the accuracy loss to 10%.
We also test the effectiveness of the importance factor matrix in Winograd retraining. For the model pruned with spatial structured pruning (70% sparsity), Winograd pruning is applied to increase the sparsity to 74%. We then perform Winograd retraining for 10 epochs. Figure 5b shows the relative accuracy against the retraining epochs with unadjusted and adjusted gradients. For unadjusted gradients, we try three learning rates of 1e-7, 1e-8 and 1e-9. Higher learning rates, e.g., 1e-6, will lead to an accuracy drop through retraining. As shown in the figure, adjusting the gradients with the importance factor matrix can substantially accelerate the convergence. With retraining of only 10 epochs, it reduces the accuracy loss to 0.2% while retraining without gradient adjustment only reduces the accuracy loss to 0.7%.

heading: 5 CONCLUSION

text: In this paper, we present a new pruning method, spatial-Winograd pruning, to improve the Winograd-domain weight sparsity without changing network structures. It includes two steps: spatial structured pruning and Winograd direct pruning. In spatial structured pruning, we prune the spatial-domain weights based on the internal structure in the Winograd transformation. It can help efficiently transfer the spatial-domain sparsity into the Winograd domain. For Winograd direct pruning, we perform both pruning and retraining in the Winograd domain. An importance factor matrix is proposed to adjust the weight gradients in Winograd retraining, which makes it possible to effectively retrain the Winograd-domain network to regain the original accuracy without changing the network structure. We evaluate spatial-Winograd pruning on three datasets, CIFAR-10, CIFAR-100, ImageNet, and it can achieve the Winograd-domain sparsities of 63%, 50%, and 74%, respectively.

heading: A COEFFICIENT TENSORS S AND H

text:
The coefficient tensors S and H contain the weight coefficients in Equation 3 and Equation 9. They are only determined by the input tile size m and the weight filter size n.
A.1 COEFFICIENT TENSOR S
To calculate the tensor S, we first introduce an equivalent transformation: for two vectors a and b with a size of m, and a matrix C with a size of m×m, we have
a>Cb = ~1 >
[(ab>) C] ~1 (19) where ~1 is a vector of size m and all its entries are 1.
For matrix S, with the weight transform matrix G, we have Q = GWG>. Each element in Winograd-domain weight filter Q is calculated as
Qi,j = Gi,: ·W · (Gj,:)> = ~1 >[( (Gi,:) >Gj,: ) W ] ~1
= ∑
06u,v6n−1
(Gi,u ·Gj,v ·Wu,v) (20)
where 0 6 i, j 6 m − 1. In this case, compared with Equation 3, each element in the coefficient tensor S can be calculated as Si,j,u,v = Gi,u ·Gj,v (21) where 0 6 i, j 6 m− 1, 0 6 u, v 6 n− 1.
A.2 COEFFICIENT TENSOR H
With the Winograd-domain weight filter Q, the output tile O is calculated as
O = A>[Q (B>I B)]A (22) Each element Ox,y is calculated as
Ox,y = (A:,x) >[Q (B>I B)]A:,y (23)
where 0 6 x, y 6 m− n. Based on Equation 19, we have
Ox,y = ~1 > [(A:,x(A:,y) >) Q (B>I B)] ~1 (24)
Let V = (A:,x(A:,y)>) Q (B>I B), then Vi,j = (Ai,xAj,y) ·Qi,j · (B>I B)i,j (25)
where 0 6 i, j 6 m− 1. The element (B>I B)i,j can be calculated as (B>I B)i,j = (B:,i) >I B:,j
= ~1 > [(B:,i(B:,j) >) I] ~1 = ∑
06s,t6m−1
[(Bs,iBt,j) · Is,t] (26)
Based on Equation 24, 25 and 26, we have Ox,y = ∑
06i,j6m−1
Vi,j
= ∑
06i,j6m−1
[(Ai,xAj,y) ·Qi,j · (B>I B)i,j ]
= ∑
06i,j6m−1
[ (Ai,xAj,y) ·Qi,j · ∑ 06s,t6m−1 [(Bs,iBt,j) · Is,t] ]
= ∑
06i,j,s,t6m−1
[(Ai,xAj,yBs,iBt,j) ·Qi,j · Is,t]
(27)
Therefore, compared with Equation 9, each element in the coefficient tensor H is calculated as
Hx,y,i,j,s,t = Ai,xAj,yBs,iBt,j (28)
where 0 6 x, y 6 m− n, 0 6 i, j, s, t 6 m− 1.

heading: B RESNET-18 PRUNING WITH VARIED SPARSITIES ACROSS LAYERS

text:
In addition to pruning ResNet-18 with the same sparsity across all targeting layers, we experiment incurring different sparsities into different layers with spatial-Winograd pruning.
For spatial structured pruning, we first test the pruning sensitivity of each convolutional layer to decide which layers need to be pruned and the corresponding thresholds. To choose the targeting layers, we measure the accuracy loss when 60% of Winograd-domain weights are pruned for each layer. Only one layer is pruned at one time, and other layers are kept intact. Figure. 6 shows the results. In ResNet-18, the i-th residual block contains two convolutional layers, i-a and i-b. As shown in the figure, the first layer in each residual block is much more sensitive to pruning than the second layer. Therefore, we will only prune the second convolutional layer, i-b, in each residual block.
For each targeting layer i-b, we determine the corresponding pruning threshold tspatiali based on its pruning sensitivity. We gradually increase the threshold until the validation accuracy drops by 2% and the threshold is recorded as tspatial, 2% lossi . Then in spatial structured pruning, we can calculate the threshold used for layer i-b as tspatiali = β · t spatial, 2% loss i where β is a multiplier shared across all targeting layers. With a larger β, the threshold and, therefore, the sparsity will be higher. Also, in Winograd direct pruning, we use the same strategy to choose the thresholds used for different layers.
0 1 2 3 4 5
0
1
2
3
4
5
(a) (b) 0 1 2 3 4 5
0
1
2
3
4
5
100
80
60
40
20
0
S p a rsity (% )
Figure 8: Sparsity of different locations of Winograd-domain weights for: (a) filters with 20 weights pruned; (b) filters with at least one weight remaining. Darker locations have higher sparsities.
Table 1 lists the pruning results. After spatial structured pruning, we can reach an average Winograddomain sparsity of 79.4% for the pruned layers. The corresponding spatial-domain sparsity is 88.9% which is 9.5% higher. Winograd direct pruning can further improve the Winograd-domain sparsity to 87.6% and layer 5-b has the highest sparsity of 93.0%.

heading: C SPARSITY DISTRIBUTION

text:
For the pruned ResNet-18 model, we analyze more detailed sparsity distribution across and inside 2D weight filters. Here each Winograd-domain weight matrix Q is considered as a 2D filter. We use the last convolutional layer (7-b) as an example. The model with a uniform sparsity of 74% across all pruned layers, which corresponds to point P in Figure 4a, is tested. Figure 7 shows the sparsity distribution across the filters. As shown in the figure, more than half (62%) of the filters have all weights removed. An interesting observation is that a large portion of the filters have exact 20 weights removed.
To explain why many filters have exact 20 weights removed, we visualize the sparsity distribution inside the filters. Figure 8a shows the sparsity of different locations for the filters with 20 weights removed. Darker locations have higher sparsities where more weights are removed. The border part of the 6 × 6 filter, which includes 20 weights, has much higher sparsity than the central part. It means the border part of the Winograd-domain weights is much less important than weights in the central part. A potential reason is that the weights in the central part are correlated to more spatial-domain weights and, therefore, removing them will lead to a larger difference in the output activations. In Figure 8b, we also visualize the sparsity distribution inside the filters with at least one weight remaining, and it shows a similar pattern.

title: SPATIAL-WINOGRAD PRUNING ENABLING SPARSE WINOGRAD CONVOLUTION


summaries: The paper uses Generative Adversarial Networks (GAN) for unsupervised and semi-supervised clustering. Neural network based generators are used for sampling using a mixture model. The parameters of the generators are optimised during training against a discriminator that tries to distinguish between generated distributions. Experimental results on MNIST and SVHN datasets are given to motivate their models.

summaries: The paper presents a generative model that can be used for unsupervised and semi-supervised data clustering. unlike most of previous method  the latent  variable is composed of both continuous and discrete variables. Unlike previous methods like ALI the conditional probability  p(y|x) of the labels given the object is represented by a neural network and not simply drown from the data.  The  authors show a  clustering error rate on the MNIST data that is better than previously proposed methods.

abstractText: The Adversarially Learned Mixture Model (AMM) is a generative model for unsupervised or semi-supervised data clustering. The AMM is the first adversarially optimized method to model the conditional dependence between inferred continuous and categorical latent variables. Experiments on the MNIST and SVHN datasets show that the AMM allows for semantic separation of complex data when little or no labeled data is available. The AMM achieves unsupervised clustering error rates of 3.32% and 20.4% on the MNIST and SVHN datasets, respectively. A semi-supervised extension of the AMM achieves a classification error rate of 5.60% on the SVHN dataset.

title: InfoGAN: Interpretable representation learning by information maximizing generative adversarial nets

venue: In Advances in Neural Information Processing Systems

authors:
Zihang Dai
Zhilin Yang

title: Good semi-supervised learning that requires a bad GAN

authors:
Zhijie Deng
Hao Zhang

title: Structured generative adversarial networks

authors:
Nat Dilokthanakul
Pedro A.M. Mediano

title: Deep unsupervised clustering with Gaussian mixture variational autoencoders

venue: arXiv preprint arXiv:1611.02648,

authors:
Jeff Donahue
Philipp Krähenbühl
Trevor Darrell

title: Adversarial feature learning

venue: In International Conference on Learning Representations,

authors:
Vincent Dumoulin
Ishmael Belghazi

title: Adversarially learned inference

authors:
Zhe Gan
Liqun Chen

title: Triangle generative adversarial networks

authors:
Ian Goodfellow
Jean Pouget-Abadie

title: Generative adversarial nets

authors:
Ishaan Gulrajani
Faruk Ahmed

title: Improved training of Wasserstein GANs

venue: arXiv preprint arXiv:1704.00028,

authors:
Weihua Hu
Takeru Miyato

title: Learning discrete representations via information maximizing self-augmented training

venue: arXiv preprint arXiv:1702.08720,

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with Gumbel-softmax

venue: arXiv preprint arXiv:1611.01144,

authors:
Zhuxi Jiang
Yin Zheng

title: Variational deep embedding: An unsupervised and generative approach to clustering

venue: In Proceedings of the 26th International Joint Conference on Artificial Intelligence,

authors:
Alex Kendall
Yarin Gal

title: What uncertainties do we need in Bayesian deep learning for computer vision

authors:
Ozsel Kilinc
Ismail Uysal

title: Learning latent representations in neural networks for clustering through pseudo supervision and graph-based activity regularization

venue: arXiv preprint arXiv:1802.03063,

authors:
Diederik Kingma
Max Welling

title: Auto-encoding variational Bayes

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Diederik P Kingma
Shakir Mohamed

title: Semi-supervised learning with deep generative models

authors:
Chongxuan Li
Kun Xu
Jun Zhu
Bo Zhang

title: Triple generative adversarial nets

venue: arXiv preprint arXiv:1703.02291,

authors:
Lars Maaløe
Marco Fraccaro
Ole Winther

title: Semi-supervised generation with cluster-aware generative models

venue: arXiv preprint arXiv:1704.00637,

authors:
Chris J. Maddison
Andriy Mnih
Yee Whye Teh

title: The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables

authors:
Alireza Makhzani
Jonathon Shlens

title: Adversarial autoencoders

authors:
Takeru Miyato
Shin-ichi Maeda

title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning

venue: arXiv preprint arXiv:1704.03976,

authors:
Yuval Netzer
Tao Wang

title: Reading digits in natural images with unsupervised feature learning

venue: In NIPS Workshop on Deep Learning and Unsupervised Feature Learning,

authors:
Kevin Roth
Aurelien Lucchi

title: Stabilizing training of generative adversarial networks through regularization

authors:
Tim Salimans
Ian Goodfellow

title: Improved techniques for training GANs

title: Unsupervised and semi-supervised learning with categorical generative adversarial networks

venue: arXiv preprint arXiv:1511.06390,

heading: 1 INTRODUCTION

text:
Semi-supervised or unsupervised representation learning enables the utilization of all available data when tackling problems where there are little or no labeled examples. This is a common scenario in many applications of machine learning, such as medical image analysis, where it is reinforced by the expense of obtaining expert labeled examples. Moreover, machine-learned representations are more likely to be used for subsequent tasks if they are interpretable and meaningful. Deep generative modelling is a suitable approach to this problem, as derived models have been shown capable of learning from both labeled and unlabeled examples, embedding data according to desired latent variable distributions, and producing realistic data examples generated from samples of those latent variables.
The Generative Adversarial Network (GAN) has recently emerged as a powerful framework for modeling complex data distributions without having to approximate intractable likelihoods. In the formulation by Goodfellow et al. (2014), a GAN consists of two networks: a generator G that is trained to yield unique samples from the data distribution, and a discriminator D that is trained to distinguish between generated and true data samples.
Dumoulin et al. (2016) and Donahue et al. (2017) have proposed the ALI and BiGAN models that add an inference process, i.e., the ability to map data samples to points in the latent space, to the GAN framework. A second generator for inference, or encoder, is added to the original GAN generator and the discriminator is adapted for the two-dimensional space of data inputs and latent representations. A variant of the resulting model is also introduced by Dumoulin et al. (2016) for conditional data generation, but still assumes that the class of the data is always observed, as inference of categorical variables is not included.
Adversarial approaches for the inference of both continuous and categorical variables are actively researched. Chen et al. (2016) introduce a hybrid adversarial method that is capable of modelling both continuous and categorical latent variables for unsupervised clustering and feature disentanglement. Another hybrid adversarial method is introduced by Makhzani et al. (2016) where adversarial objectives on continuous and categorical latent variables are optimized for unlabeled examples and categorical cross entropy on categorical variables is optimized for labeled examples. Li et al. (2017) and Deng et al. (2017) point toward fully adversarial semi-supervised classification using inferred categorical variables by introducing a “three player” adversarial game, but stop short by adding auxiliary “collaborative” objectives. In each of these methods, it is assumed that categorical and continuous latent variables are independently distributed. This independence assumption results in discontinuities in the latent space between categories, which removes the notion of inter-categorical proximity.
Another notable family of generative models, Variational Autoencoders (VAEs), maximize the posterior distribution of latent representations given the data instead of using an adversarial approach. As VAEs integrate inference, semi-supervised classification can be performed by conditioning the
continuous latent variable of the VAE on the class label (Kingma et al., 2014; Dilokthanakul et al., 2016; Maaløe et al., 2017). However, the quality of VAE results depend on the expressiveness of the inference distribution and every time the assumptions about the inference or data distributions are changed a new objective function needs to be derived. In this way, variational optimization is not as versatile as adversarial training.
We present the Adversarially Learned Mixture Model (AMM). The AMM is, to our knowledge, the first generative model inferring both continuous and categorical latent variables to perform either unsupervised or semi-supervised clustering of data using a single adversarial objective. This is enabled, in part, by explicitly modelling the dependence between continuous and categorical latent variables, which eliminates discontinuities between categories in the latent space. Semi-supervised clustering and classification is enabled by a simplified formulation of the “three player game”, presented by Li et al. (2017). In this paper we show that the AMM achieves an unsupervised clustering error rate of 3.32% and 20.4% on the MNIST (LeCun & Cortes, 2010) and SVHN datasets (Netzer et al., 2011) respectively, and that a semi-supervised extension, SAMM, achieves a classification error rate of 5.60% on the SVHN dataset . To support the reproducibility of the methodology and experiments presented, a public version of the code will be made available.

heading: 2 METHOD

heading: 2.1 PRELIMINARIES

text:
The ALI and BiGAN models are trained by matching two joint distributions of images x∈RD and their latent code z ∈RL. The two distributions to be matched are the inference distribution q(x,z) and the synthesis distribution p(x,z), where,
q(x,z) = q(x)q(z |x), (1) p(x,z) = p(z)p(x |z). (2)
Samples of q(x) are drawn from the training data and samples of p(z) are drawn from a prior distribution, usuallyN (0,1). Samples from q(z |x) and p(x |z) are drawn from neural networks that are optimized during training. Dumoulin et al. (2016) show that sampling from q(z |x)=N (µ(x),σ2(x)I) is possible by employing the reparametrization trick (Kingma & Welling, 2013), i.e. computing
z=µ(x)+σ(x) , ∼N (0,I), (3)
where is element wise vector multiplication. A conditional variant of ALI has also been explored by Dumoulin et al. (2016) where an observed class-conditional categorical variabley has been introduced. The joint factorization of each distribution to be matched are:
q(x,y,z) = q(x,y)q(z |y,x), (4) p(x,y,z) = p(y)p(z)p(x |y,z). (5)
Samples of q(x,y) are drawn from the data. Samples of p(z) are drawn from a continuous prior on z, and samples of p(y) are drawn from a categorical prior on y, both of which are marginally independent. Samples from q(z | y,x) and p(x | y,z) are drawn from neural networks that are optimized during training.
In the following sections we present graphical models for q(x,y,z) and p(x,y,z) that build off of conditional ALI. Where conditional ALI requires the full observation of categorical variables, the models we present will account for both unobserved and partially observed categorical variables. We finally show how they can be optimized using a single adversarial objective.

heading: 2.2 ADVERSARIALLY LEARNED MIXTURE MODEL

text:
The AMM is an adversarial generative model for deep unsupervised clustering of data. Figure 1 presents an overview of the model.
Like conditional ALI, a categorical variable is introduced to model the labels. However, the unsupervised setting now requires a different factorization of the inference distribution in order to
enable inference of the categorical variable y, namely:
q1(x,y,z)=q(x)q(y |x)q(z |x,y), (6) or q2(x,y,z)=q(x)q(z |x)q(y |x,z). (7) Samples of q(x) are drawn from the training data, and samples from q(y |x), q(z |x,y) or q(z |x), q(y |x,z) are generated by neural networks. The reparametrization trick is not directly applicable to discrete variables and multiple methodologies have been introduced to approximate categorical samples (Jang et al., 2016; Maddison et al., 2017). We follow Kendall & Gal (2017) and sample from q(y |x) by computing
hy(x) = µy(x)+σy(x) , ∼N (0,I), (8) y(x) = softmax(hy(x)). (9)
Then, we can sample from q(z |x,y) by computing z(x,hy(x))=µz(x,hy(x))+σz(x,hy(x)) , ∼N (0,I). (10)
A similar sampling strategy can be used to sample from q(y |x,z) in (7). The factorization of the synthesis distribution p(x,y,z) also differs from conditional ALI:
p(x,y,z)=p(y)p(z |y)p(x |y,z). (11) The product p(y)p(z | y) can be conveniently given by a mixture model. Samples from p(y) are drawn from a multinomial prior, and samples from p(z | y) are drawn from a continuous prior, for example,N (µy=k,1). Samples from p(z |y) can alternatively be generated by a neural network by again employing the reparameterization trick. Namely,
z(y)=µ(y)+σ(y) , ∼N (0,I). (12) This approach effectively learns the parameters ofN (µy=k,σy=k).

heading: 2.2.1 ADVERSARIAL VALUE FUNCTION

text:
We follow Dumoulin et al. (2016) and define the value function that describes the unsupervised game between the discriminatorD and the generatorG as:
min G max D V (D,G)=Eq(x)[log(D(x,Gy(x),Gz(x,Gy(x))))]
+Ep(y,z)[log(1−D(Gx(y,Gz(y)),y,Gz(y)))]
= ∫∫∫ q(x)q(y |x)q(z |x,y)log(D(x,y,z))dxdydz
+ ∫∫∫ p(y)p(z |y)p(x |y,z)log(1−D(x,y,z))dxdydz.
(13)
There are four generators in total: two for the encoderGy(x) andGz(x,Gy(x)), which map the data samples to the latent space; and two for the decoderGz(y) andGx(y,Gz(y)), which map samples from the prior to the input space. Gz(y) can either be a learned function, or be specified by a known prior (see Algorithm 1 for a detailed description of the optimization procedure).
Algorithm 1 AMM training procedure using distributions (6) and (11). θGy(x),θGz(x,Gy(x)),θGz(y),θGx(y,Gz(y)),θD . Initialize AMM parameters while not done do x(1),...,x(M)∼q(x) . Sample from data and priors y(1),...,y(M)∼p(y) z(j)∼p(z |y=y(j)), j=1,...,M x̃(j)∼p(x |y=y(j),z=z(j)), j=1,...,M . Sample from conditionals ỹ(i)∼q(y |x=x(i)), i=1,...,M z̃(i)∼q(z |x=x(i),y= ỹ(i)), i=1,...,M ρ (i) q ←D(x(i),ỹ(i),z̃(i)), i=1,...,M .Compute discriminator predictions ρ (j) p ←D(x̃(j),y(j),z(j)), j=1,...,M LD←− 1M ∑M i=1log(ρ (i) q )− 1M ∑M j=1 log(1−ρ (j) p ) .Compute discriminator losses
LGx(y,Gz(y))=LGz(y)←− 1M ∑M i=1log(ρ (i) p ) .Compute x generator losses
LGy(x)=LGz(x,Gy(x))←− 1M ∑M i=1log(1−ρ (i) q ) .Compute y and z generator loss θD←θD−∇θDLD .Update discriminator parameters θGx(y,Gz(y))←θGx(y,Gz(y))−∇θGx(y,Gz(y))LGx(y,Gz(y)) .Update generator parameters θGz(y)←θGz(y)−∇θGz(y)LGz(y) θGy(x)←θGy(x)−∇θGy(x)LGy(x) θGz(x,Gy(x))←θGz(x,Gy(x))−∇θGz(x,Gy(x))LGz(x,Gy(x))

heading: 2.3 SEMI-SUPERVISED ADVERSARIALLY LEARNED MIXTURE MODEL

text:
The Semi-Supervised Adversarially Learned Mixture Model (SAMM) is an adversarial generative model for supervised or semi-supervised clustering and classification of data. The objective for training SAMM involves two adversarial games to match pairs of joint distributions. The supervised game matches inference distribution (4) to synthesis distribution (11) and is described by the following value function: min G max D V (D,G)=Eq(x,y)[log(D(x,y,Gz(x,y)))]+Ep(y,z)[log(1−D(Gx(y,Gz(y)),y,Gz(y)))]
= ∫∫∫ q(x,y)q(z |x,y)log(D(x,y,z))dxdydz
+ ∫∫∫ p(y)p(z |y)p(x |y,z)log(1−D(x,y,z))dxdydz.
(14)
The unsupervised game matches either of the inference distributions, (6) or (7) to the synthesis distribution (11). In the case using distribution (6), the unsupervised game is described by (13). The generator for semi-supervised learning has three components: encoders Gz(x,Gy(x)) and Gz(x,y) map the labeled and unlabeled data samples, respectively, to the latent space, and a decoder Gx(y,Gz(y)) maps samples of y and z to the input space, where Gz(z) can either be a learned function or be specified by a prior. The encoder for labeled data again consists of two generators (Figure 1). A detailed description of the training algorithm is given in algorithm 2 of the appendix. In practice, optimization of each of the generators and the discriminator can be done simultaneously for both the unsupervised and semi-supervised updates.

heading: 3 RELATED WORKS

text:
Unsupervised clustering using hybrid adversarial approaches are proposed by both Makhzani et al. (2016) (AAE) and Chen et al. (2016) (InfoGAN). For AAE, the synthesis generator is optimized
by minimizing the per-example L2 loss between between input data {xi} and their reconstructions {ẋi=Gxi(Gy(xi),Gz(xi))}, while the inference generator is optimized using both the L2 objective and an adversarial objective. For InfoGAN, the inference generator is optimized by maximizing the per-example Mutual Information (MI) between samples of categorical latent variables {yi∼p(y)} and continuous latent variables {zi∼p(z)} and their “reconstructions” {{ẏi,żi}=Gy,z(Gx(yi,zi)}, while the synthesis generator is optimized using both the MI objective and an adversarial objective.
Recent approaches using self-supervision with data augmentation have also been proposed for unsupervised discrete representation learning by Kilinc & Uysal (2018) (LALNets) and Hu et al. (2017) (IMSAT). In IMSAT, a network is trained to maximize the Mutual Information between input data and a discrete representation, similar to InfoGAN. In addition to this objective, the network is regularized by encouraging the representation of original, unperturbed data {xi} to be close to that of transformed data {T (xi)}. In the LALNets framework, a network is trained to distinguish unperturbed data and augmented data, and then k-means clustering is performed on the latent space representation of the unperturbed data to obtain cluster labels.
On the other end of the generative spectrum, Dilokthanakul et al. (2016) and Jiang et al. (2017) offer non-adversarial, VAE-based approaches for unsupervised clustering. Like in the AMM, the combination of priors for the latent variables y and z is modeled as a Gaussian mixture model, where y corresponds to the mixture components.
Multiple adversarial methodologies have been proposed for supervised or semi-supervised learning (Springenberg, 2015; Salimans et al., 2016; Miyato et al., 2017; Dai et al., 2017), but they suffer from the same limitation as the original GAN: they do not provide inference. Gan et al. (2017), Li et al. (2017) and Deng et al. (2017) introduce a third player to the adversarial game. Although this extra player allows to infer categorical variables, these approaches are not fully adversarial as auxiliary “collaborative” terms are added to the objective function. Moreover, categorical and continuous latent variables are modeled independently.
The adversarial and hybrid-adversarial approaches thus far discussed all model y and z as being conditionally independent from each other. This may be an ideal prior structure for inference, for example, in learning disentangled representations ofx sampled from a limited domain (Chen et al., 2016). However, the independence assumption cannot account for the notion of proximity between categories because z is identically distributed for each category in y. Therefore, the distance between categories is equal and indeterminate. AMM and SAMM are presented as adversarial approaches to model conditional dependencies between y and z, but they do not preclude the independence assumption. The proposed methods can model y and z as conditionally independent with inference distribution
q(x,y,z)=q(x)q(y |x)q(z |x), (15) and synthesis distribution
p(x,y,z)=p(y)p(z)p(x |y,z); (16)
however, analysis of this graphical model is left for future work.

heading: 4 EVALUATION

text:
AMM and SAMM are evaluated using two image datasets: MNIST (LeCun & Cortes, 2010) and SVHN (Netzer et al., 2011). The provided training and testing splits are used for MNIST experiments with 5000 randomly selected examples left out of the training set for validation. The same training, testing, and validation splits as Dumoulin et al. (2016) are used for SVHN. Preprocessing is limited to scaling image intensities on the range [0,1]. Detailed architectures for each experiment are shown in Section B of the appendix. We optimize all networks using Adam (Kingma & Ba, 2014) withα=0.0002 and β1=0.5. All kernel weights are initialized using a Gaussian distribution with standard deviation 0.02, all biases are initialized to 0.0. Following the criteria in Jiang et al. (2017), the performance is evaluated as follows:
ACC=max n∈N
∑M i=11{yi=n(ỹz̃,i)}
M , (17)
whereM is the number of samples, yi is the true label, and ỹz̃,i is the predicted cluster label, andN is the set of all mappings between cluster labels and true labels.

heading: 4.1 GRADIENT PENALTY

text:
The gradient penalty introduced by Gulrajani et al. (2017) is added to the discriminator loss to help stabilize training of AMM and SAMM models. This penalty keeps the gradients of the discriminator with respect to the inputs x, y, and z on the same order of magnitude. The penalty applied to the discriminator loss is
L∇x̂,ŷ,ẑ =λ E (x̂,ŷ,ẑ)∼Px̂,ŷ,ẑ
[ (||∇x̂,ŷ,ẑD(x̂,ŷ,ẑ)||2−1)2 ] , (18)
where points (x̂,ŷ,ẑ) are drawn at random on straight lines between real or prior samples (x,ỹ,z̃) and synthesized or inferred samples (x̃,y,z). The gradient penalty for Jensen-Shannon GAN introduced by Roth et al. (2017) has also been explored, but did not produce better results. The regularization term is set to λ=10.0, and λ=0.01 for MNIST and SVHN experiments, respectively.

heading: 4.2 MNIST

text: In this section, the AMM is evaluated on the task of unsupervised clustering of hand-drawn digits using the MNIST dataset. To model p(y)p(z |y), a 64 dimensional mixture of Gaussians is used with 10, 20, and 30-components across 3 experiments. A multinomial prior is used for p(y) with uniform probability for each class. The mean and variance of each component distribution are learned using the reparameterization trick via (12). Table 1 reports the test-set clustering error-rate mean and standard deviation over 10 trials, with the 10-component AMM achieving a 3.32± 0.39 percent error rate. Figure 2 visualizes results from 1 of the 10 trials.

heading: 4.3 SVHN

heading: 4.3.1 UNSUPERVISED CLUSTERING

text:
In this section, unsupervised clustering is revisited. The SVHN dataset is used to investigate how confounding attributes, such as color and contrast, affects the semantic separation of digits. To model p(y)p(z |y) a 64 dimensional mixture of Gaussians is used with 10, 20, and 30-components across 3 experiments. A multinomial prior is used for p(y)with uniform probability for each class, and the mean and variance of each component distribution are learned using the reparameterization trick via (12).
Figure 3a shows random samples drawn from each component distribution generated byGx. Figure 3b is a t-SNE projection of test samples drawn from Gz onto a 2D manifold. We show in 3c that AMM learns a smooth latent manifold as we interpolate between examples from SVHN. The cluster matrix for the SVHN test set is shown in figure 3d, demonstrating an overall classification error rate of 20.4%±0.80. From these results, we can make a few observations. First, the generated images are realistic looking. This is the case for every cluster other than cluster 5, which appears to be a noise cluster. Secondly, each cluster only contains a single digit. Finally, we observe that for each digit there are multiple clusters, one containing a dark background with light numbers (ie. cluster 28), and another containing a light background with dark numbers (ie. cluster 12). This is important, as it shows that the AMM has learned semantically meaningful clusters.

heading: 4.3.2 SEMI-SUPERVISED CLUSTERING AND CLASSIFICATION

text:
It is evident from the last experiment that the confounders introduced by the SVHN dataset made unsupervised semantic clustering more difficult. In this section we show how SAMM can be used to guide clustering along predefined categories using only a small amount of labeled data. To this end, we limit the samples drawn from q(x,y) to a random selection of 1000 examples from the training set. To model p(y)p(z | y) we use a 64 dimensional mixture of 10 spherical Gaussians, where the the mean and variance of each component distribution are learned using the reparameterization trick via (12). There is considerable class imbalance in the SVHN dataset, so a multinomial prior is used for p(y) with each class probability set to the frequency observed in the labeled subset of the training data.
Table 2 reports the test-set error-rate mean and variance over 10 trials. SAMM achieves 5.60±0.45 percent error rate, which is an improvement over the ALI baseline. Figure 4 shows visualizations of results from 1 of the 10 trials. Finally, given that we have defined p(y)p(z |y) we can use Bayes’ theorem to derive p(y |z) and get a classifier given an image embedding z̃:
ỹz̃=argmax k
[p(z= z̃ |y=k)p(y=k)] (19)
Figures 4e and 4f compare the confusion matrices for predictions given by ỹz̃ and those given by ỹ fromGy. The similarity between each is further evidence that the inference network has learned to embed data according to the desired distribution.

heading: 5 CONCLUSION

text:
The AMM is presented as a generative model for unsupervised or semi-supervised data clustering with several contributions. The AMM is the first fully adversarially optimized method to model the conditional dependence between categorical and continuous latent variables, providing impressive unsupervised clustering and competitive semi-supervised classification results on benchmark datasets. In contrast with other semi-supervised approaches, we have shown that the use of additional losses or discriminators (Gan et al. (2017); Li et al. (2017); Deng et al. (2017)) are redundant additions to frameworks, as the AMM yields similar or better results to these methods. In contrast with Dai et al. (2017), our strong semi-supervised performance and qualitatively good image generation demonstrate that semi-supervised performance and image generation are not necessarily opposing goals. As a fully adversarial framework, the AMM provides a simple, yet powerful formulation as a foundation for
future work. For example, the distribution of mixture components can be something be other than a Gaussian without the need to derive an new evidence lower bound. Furthermore, by learning conditional dependencies betweeny andz, the AMM preserves the notion of proximity between classes in the latent space, which could be useful for applications in metric space learning and few shot learning. On top of this, learning the mean and variance of mixture components gives access to subsequent analysis of the likelihood function, which could provide an interpretable insight of the learned distributions. With that, the mixture coefficients are the only terms to be integrated into the framework. As a whole, the AMMs demonstrably strong performance validates its use in future work and extension into other domains.

heading: APPENDIX A SAMM ALGORITHM

text:
Algorithm 2 outlines the SAMM training procedure.
Algorithm 2 SAMM training procedure using distributions (4), (6), and (11). θGy(x),θGz(x,Gy(x)),θGz(y),θGx(y,Gz(y)),θD . Initialize SAMM parameters while not done do x (1) u ,...,x (M) u ∼q(x) . Sample from unlabeled data and priors
y (1) u ,...,y (M) u ∼p(y) z (j) u ∼p(z |y=y(j)u ), j=1,...,M x̃ (j) u ∼p(x |y=y(j)u ,z=z(j)u ), j=1,...,M . Sample from conditionals ỹ (i) u ∼q(y |x=x(i)u ), i=1,...,M z̃ (i) u ∼q(z |x=x(i)u ,y= ỹ(i)u ), i=1,...,M( x (1) ` ,...,x (M) ` ) , ( ỹ (1) ` ,...,ỹ (M) ` ) ∼q(x,y) . Sample from labeled data and priors
y (1) ` ,...,y (M) ` ∼p(y) z (j) ` ∼p(z |y=y (j) ` ), j=1,...,M x̃ (j) ` ∼p(x |y=y (j) ` ,z=z (j) ` ), j=1,...,M . Sample from conditionals z̃ (i) ` ∼q(z |x=x (i) ` ,y= ỹ (i) ` ), i=1,...,M ρ (i) qu←D(x(i)u ,ỹ(i)u ,z̃(i)u ), i=1,...,M .Compute predictions for unlabeled data ρ (j) pu ←D(x̃(j)u ,y(j)u ,z(j)u ), j=1,...,M ρ (i) q` ←D(x(i)` ,ỹ (i) ` ,z̃ (i) ` ), i=1,...,M .Compute predictions for labeled data ρ (j) p` ←D(x̃(j)` ,y (j) ` ,z (j) ` ), j=1,...,M
LDu←− 12M ∑M i=1log(ρ (i) qu )− 12M ∑M j=1 log(1−ρ (j) pu ) .Compute discriminator losses
LD`←− 12M ∑M i=1log(ρ (i) q` )− 12M ∑M j=1 log(1−ρ (j) p` )
LGyu (x)=LGzu (x,Gy(x))←− 12M ∑M i=1log(1−ρ (i) qu ) .Compute inference losses LGz` (x,Gy(x))←− 1 2M ∑M i=1log(1−ρ (i) q` )
LGxu (y,Gz(y))=LGzu (y)←− 12M ∑M i=1log(ρ (i) pu ) .Compute x generator losses LGx` (y,Gz(y))=LGz` (y)←− 1 2M ∑M i=1log(ρ (i) p` ) θD←θD−∇θD (LDu+LD`) .Update discriminator parameters θGz(x,Gy(x))←θGz(x,Gy(x))−∇θGz(x,Gy(x)) ( LGzu (x,Gy(x))+LGz` (x,Gy(x)) ) . Update z inference parameters θGy(x)←θGy(x)−∇θGy(x)LGyu (x) .Update y inference parameters θGx(y,Gz(y))←θGx(y,Gz(y))−∇θGx(y,Gz(y)) ( LGxu (y,Gz(y))+LGx` (y,Gz(y)) ) . Update x synthesis parameters θGz(y)←θGz(y)−∇θGz(y) ( LGzu (y)+LGz` (y) ) .Update z synthesis parameters

heading: APPENDIX B EXPERIMENT INFORMATION

text:
B.1 MODEL ARCHITECTURES
Tables 3, 4, 5 and 6 detail the model architectures for the MNIST experiments. Tables 7, 8, 9 and 10 detail the model architectures for the SVHN experiments. Model inputs and outputs are highlighted in boldface. “Leak” denotes Leaky ReLU activations. “ExpN” denotes the following activation function:
ExpN(x)=exp(0.5 x) , ∼N (0,I). (20)