Deep Learning meets Projective Clustering
Authors: Alaa Maalouf
Harry Lang
Daniela Rus
Dan Feldman
Venue: ICLR 2021 Poster (2021)
Keywords: Compressing Deep Networks
NLP
Matrix Factorization
SVD

Abstract: A common approach for compressing Natural Language Processing (NLP) networks is to encode the embedding layer as a matrix $A\in\mathbb{R}^{n\times d}$, compute its rank-$j$ approximation $A_j$ via SVD (Singular Value Decomposition), and then factor $A_j$ into a pair of matrices that correspond to smaller fully-connected layers to replace the original embedding layer. Geometrically, the rows of $A$ represent points in $\mathbb{R}^d$, and the rows of $A_j$ represent their projections onto the $j$-dimensional subspace that minimizes the sum of squared distances (``errors'') to the points. 
In practice, these rows of $A$ may be spread around $k>1$ subspaces, so factoring $A$ based on a single subspace may lead to large errors that turn into large drops in accuracy.

Inspired by \emph{projective clustering} from computational geometry,  we suggest replacing this subspace by a set of $k$ subspaces, each of dimension $j$, that minimizes the sum of squared distances over every point (row in $A$) to its \emph{closest} subspace. Based on this approach, we provide a novel architecture that replaces the original embedding layer by a set of $k$ small layers that operate in parallel and are then recombined with a single fully-connected layer. 

Extensive experimental results on the GLUE benchmark yield networks that are both more accurate and smaller compared to the standard matrix factorization (SVD). For example, we further compress DistilBERT by reducing the size of the embedding layer by $40\%$ while incurring only a $0.5\%$ average drop in accuracy over all nine GLUE tasks, compared to a $2.8\%$ drop using the existing SVD approach.
On RoBERTa we achieve $43\%$ compression of the embedding layer with less than a $0.8\%$ average drop in accuracy as compared to a $3\%$ drop previously.

Published as a conference paper at ICLR 2021
DEEP LEARNING MEETS PROJECTIVE CLUSTERING
Alaa Maalouf +1 Harry Lang" 2 Daniela Rus & Dan Feldman'
Robotics & Big Data Labs, Department of Computer Science, University of Haifa
2 CSAIL, MIT
alaamaloufl2 22 gma ill 1. com, Marryl@mit.edu. rus@csail mit edu, dannyf www.pppssttmm.cooommmmmmmmm
ABSTRACT
A common approach for compressing Natural Language Processing (NLP) net- works is to encode the embedding layer as a matrix A E Raxd compute its rank-j approximation Aj via SVD (Singular Value Decomposition), and then fac- tor Aj into a pair of matrices that correspond to smaller fully-connected layers replace the original embedding layer. Geometrically, the rows of A represent points in IRd, and the rows of Aj represent their projections onto the j-dimensional subspace that minimizes the sum of squared distances ("errors") the points. In practice, these rows of A may be spread around k >> 1 subspaces, so factoring A based on single subspace may lead large errors that turn into large drops accuracy.
Inspired by projective clustering from computational geometry, suggest placing this subspace by a set of subspaces, each of dimension j. that minimizes the sum of squared distances over every point (row in A) its closest subspace. Based on this approach, we provide a novel architecture that replaces the original embedding layer by a set of & small layers that operate in parallel and are then recombined with a single fully-connected layer.
Extensive experimental results on the GLUE benchmark yield networks that are both more accurate and smaller compared to the standard matrix factorization (SVD). For example, we further compress DistilBERT by reducing the size of the embedding layer by 40% while incurring only 0.5% average drop in accuracy over all nine GLUE tasks, compared to a 2.8% drop using the existing SVD ap- proach. On RoBERTa we achieve 43% compression of the embedding layer with less than 0.8% average drop in accuracy as compared to 3% drop previously.
INTRODUCTION AND MOTIVATION
Deep Learning revolutionized Machine Learning by improving the accuracy by dozens of percents for fundamental tasks in Natural Language Processing (NLP) through learning representations of a natural language via a deep neural network (Mikolov et al., 20133] Radford et al. 2018 Le and Mikolov 2014 Peters et al. 2018 Radford et 2019). Lately, was shown that there is need to train those networks from scratch each time we receive a new task/data, but to fine-tune a full pre-trained model on the specific task (Dai and Le 2015 Radford et al. 2018 Devlin al. 2019). However, in many cases, those networks are extremely large compared to classical machine learning models. For example, both BERT (Devlin et al. 2019) and XLNet (Yang et al. 2019) have more than 110 million parameters, and RoBERTa (Liu et al. 2019b) consists of more than 125 million parameters. Such large networks have two main drawbacks: (i) they too much storage, e.g. memory or disk space, which may be infeasible for small IoT devices, smartphones, or when personalized network is needed for each user/object/task and (ii) classification may take too much time, especially for real-time applications such as NLP tasks: speech recognition, translation or speech-to-text.
To this end, many papers suggested different techniques to compress Compressed Networks.
large NLP networks, e.g., by low-rank factorization (Wang et al. 2019 Lan et al. 2019), prun-
"qqull contribution

---

Published as a conference paper at ICLR 2021
The third input neuron correspands third of
output neurons.
Standard fully connected layer.
(Aa.1.
.Aa.0
n = 20 input neurons.
The corresponding matrix A E 18 has 200 parameters.
As,1
A3,10
R
Figure I: A standard embedding (or fully-connected) layer of 20 input neurons and 10 output neu- rons. Its corresponding matrix A E R22010 has 200 parameters, where the ith row in A is the vector of weights of the neuron in the input layer.
ing (McCarley) 2019 Michel et al. 2019 Fan et al. 2019; Guo et al., 2019 Gordon et al. 2020
quantization (Zafrir et al. 2019 Shen et al. 2020). weight sharing (L.n et al. 2019), , and knowl- edge distillation (Sanh et al.] 2019| Tang et al. 2019, Mukherjee and Awadallahy 2019) Liu et al.) 2019a [Sun et al. 2019 Jiao et al. 2019]; see more example papers and comparison table in Gor- don (2019) for compressing the BERT model. There is no consensus on which approach should be used in what contexts. However, in the context of compressing the embedding layer, the most common approach is low-rank factorization as in Lan et al. (2019), and it may be combined with other techniques such as quantization and pruning.
In this work, we suggest novel low-rank factorization technique for compressing the embedding layer of a given model. This is motivated by the fact that in many networks, the embedding layer accounts for 20% 40% of the network size. Our approach- MESSI: Multiple (parallel) Estimated SVDs for Smaller Intralayers achieves a better accuracy for the same compression rate compared the known standard matrix factorization. To present it, we first describe an embedding layer, the known technique for compressing it, and the geometric assumptions underlying this technique. Then, we give our approach followed by geometric intuition, and detailed explanation about the motivation and the architecture changes. Finally, we report our experimental results that demonstrate the strong performance of our technique.
Embedding Layer. The embedding layer aims to represent each word from a vocabulary by real-valued vector that reflects the word's semantic and syntactic information that can be extracted from the language. One can think of the embedding layer as a simple matrix multiplication as follows. The layer receives standard vector R (a row of the identity matrix, exactly one non- zero entry, usually called one-hot vector) that represents a word in the vocabulary, multiplies by matrix AT dx to obtain the corresponding d-dimensional word embedding vector y A²'x. which is the row in A that corresponds to the non-zero entry of x. The embedding layer has n input neurons, and the output has d neurons. The nd edges between the input and output neurons define the matrix A E =x Here, the entry in the ith row and jth column of is the weight of the edge between the ith input neuron the jth output neuron; see Figure.
Compressing by Matrix Factorization. A common approach for compressing embedding layer is to compute the j-rank approximation A, E Ruud of the corresponding matrix A via SVD (Singular Value Decomposition;
e.g., Lan et al. 2019); Yu et al. (2017) and Acharya et al. (2019), ) factor A, into two smaller matrices U E R and V E Rix (i.e. A = UV), ), and replace the original embedding layer that corresponds
A by pair of layers that correspond to U and V. The number of parameters is then reduced to j(n + d). Moreover, computing the output takes O(j(n + d)) time, compared to the ((nd) time for computing AF'.. As above, we continue to A, to refer to rank-j approximation of matrix A.
Fine tuning. The layers that correspond to the matrices U and V above are sometimes used only as initial seeds for training process that is called fine tuning. Here, the training data is fed into the
2

---

Published as a conference paper at ICLR 2021
20
4
1X 10
Overall x (20 + 10) 120 parameters.
A
U
d 10 output neurons.
C R represent the 4-dimensional subspace. has parameters.
4 low dimensional
U 28 enccodes every row from A via its coordinates an the sutspaac V. It has 80 parameters.
subspace.
7 = 20 input neurons.
Figure 2: Factorization of the embedding layer (matrix) E 2200100 from Figure via standard matrix factorization (SVD) to obtain two smaller layers (matrices) U E 20 and V E 1 In this example, the factorization was done based on a 4-dimensional subspace. The result compressed layer that consists of 120 parameters. The original matrix had 200 parameters. See more details in the figure.
network, and the error is measured with respect to the final classification. Hence, the structure of the data remains the same but the edges are updated in each iteration to give a better accuracy.
Observe that typically, the SVD takes the form Aj = UDV, where the columns of E [R=xj are orthogonal, the rows of V E R are orthogonal, and D E Rixi is a diagonal matrix. In this paper and in others, we say that A, = UV where V = DV. Furthermore, the orthogonalization is used only to obtain a low rank approximation Ay U V using SVD. After that, this property is not kept in the network during the training process (when applying the fine-tuning).
Geometric intuition. The embedding layer can be encoded into matrix A E R as explained above. Hence, each of the n rows of A corresponds a point (vector) Rd and the j-rank approximation A₂ E Raxd represents the projection on the j-dimensional subspace that minimizes the sum of squared distances ("errors") to the points. Projecting these points onto any j-dimensional this subspace,
subspace of RRd would allow us to encode every point only via its j-coordinates and store only n- entries instead of the original nd entries of A. This is the matrix E Raxj, where each row encodes the corresponding row in A by its j-coordinates on this subspace. The subspace itself can be represented by its basis of j d-dimensional vectors (jd entries), which is the column space of matrix V Rdxj, Figure 2 illlstrrssss the small pair of layers that corresponds U and V. those layers are a compression for the original big layer that corresponds to A.
However, our goal not only compress the network or matrix, but also to approximate the original matrix operator A. To this end, among all the possible j-subspaces of Rd, we may be interested in the j-subspace that minimizes the sum squared distances to the points, i.c., the sum of squared projected errors. This subspace can be computed easily via SVD. The corresponding projections of the rows of A on this subspace are the rows of the j-rank matrix Ay-
The hidden or statistical assumption in this model is that the rows of the matrix A (that represents the embedding layer) were actually generated by adding i.i.d. Gaussian noise to each point set of points on j-dimensional subspace, that is spanned by what are called latent variables or factors. Given only the resulting matrix A, the j-subspace that maximizes the likelihood (probability) of generating the original points is spanned by the j largest singular vectors of A.
Why single distribution? Even if we accept the assumption of Gaussian noise, e.g. due to simplicity of computations or the law large numbers, it is not intuitively clear why we should assume that the rows of A were sampled from single distribution. Natural questions that arise are:
3

---

Published as a conference paper at ICLR 2021
12 x 10
12
The j == low rank of A
8x3
3
8
A
V
A 2
The j 3 low rank of 4
The edges from the 3 most right neurons to the output layer form the matrix V E R2 which represent the close 3-dimensional subspace for A'. 30 parameters.
edges from most left neurons to output layer the matrix R 2 which
d 10 output neurons.
represent the close 3-dimensional subspace A?. It has 30 parameters.
U E RR2x3 encodes every row from cluster A via its coordinates on the subspaceV". Ut has 36 parameters.
R 9x3 encodes every row from cluster A its coordinates on subspacel??, U has parameters.
overall 120 parameters.
A has 8 rows (input neurons).
n, (input neurons).
Figure 3: Example of our compression scheme (MESSI) from A to Z. Here j 3 and k = 2. and we compress the embedding layer from figure D (i) find the set of dimension = 3, that minimizes the sum of squared distances from each point (row in A) to its closest subspace. (ii) Partition the rows of into rows are in the same subset if there closest subspace is the same, (iii) for each subset, factor its corresponding matrix into two smaller matrices based on its closest subspace to obtain the matrices U' Vl, (J2 and V2 (where for every {1..... A}. the matrix U'V is low (j 3) rank approximation for A'), (iii) replace the original fully-connectie (embedding) layer by layers, where the first (red color) and 2 as in the figure, and the second (blue color) is fully-connected layer with all the previews k 2, and its weights corresponds to V and / as follow. For every i (1,'.. k),, the weights form the j = neurons (nodes) that are connected in the previous layer with U are initialized by V'. The result is a compressed layer that consists of nj + kjd- 20 x 3 + 2 x 3 10 120 parameters. See more details in the figure.
subspaces, each of
different subsets A and A?, where two
have & 2 parallel fully-connected layers for (initialized by) U
(i) Can we get smaller and/or more accurate models in real-world networks by assuming mul- tiple instead of single generating distribution (i.e. multiple subspaces)?
(ii) Can we efficiently compute the corresponding factorizations and represent them as part of a network
2 OUR CONTRIBUTION
We answer the above open questions by suggesting the following contributions. short, the answers are:
(i) In all the real-world networks that we tested, it is almost always better to assume k > 2 distributions rather than a single one that generated the data. is better in the sense that the resulting accuracy of the network is better compared to A 1 (SVD) for the same compression rate.
(ii) While approximating the global minimum is Max-SNP- we can efficiently compute many local minima and take the smallest one. We then explain how to encode the result back into the network. This is by suggesting layer architecture that we call MESSI (Multiple (parallel) Estimated SVDs for Smaller Intralayers); Figure Extensive experimental results show significant improvement.
our experiments show that
embedding
4

---

Published as a conference paper at ICLR 2021
Computational Geometry meets Deep Learning. Our technique also constructs the matrix A E RRndd from a given embedding layer. However, inspired by the geometrie intuition from the previous section, we suggest to approximate the n rows of A by clustering them to k 2 2 subspaces instead of one. More precisely, given an integer k 2 1 we aim to compute a set of subspaces in Rd, each of dimension j. that will minimize the sum over every squared distance of every point (row in A) to its nearest subspace. This can be considered as a combination of j-rank or j-subspace approximation, as defined above, and k-means clustering. In the k-means clustering problem we wish to approximate n. points by k center points that minimizes the sum over squared distance between every point to its nearest center. In our case, the l centers points are replaced by subspaces, each of dimension j. In computational geometry, this type of problem is called projective clustering (see Figure(4), and its used in many tasks in the fields of Machine Learning and Computer
Vision Feng et al. 2011 Xu et al. 2005 Liu et al. 2012. Trittenbach and Böhm 2019).
From Embedding layer to Embedding layers. The result of the above technique is set of l matrices A),... , AA, each of rank j and dimension n, x d where the ith matrix corresponds the cluster of n; points that were projected on the vth j-dimensional subspace. Each of those matrices can be factored into two smaller matrices (due its low rank), i... for every E {I.... k). we have A = U'V', where U" E R=:x,, and V E Rixd To plug these matrices as part of the final network instead of the embedded layer, we suggest to encode these matrices via ls parallel sub-layers as described in what follows and illustrated in Figure
Our pipeline: MESSL. We construct our new architecture as follows. We use A to refer to the x d matrix from the embedding layer seek to compress. The input our pipeline is the matrix A, positive integers j and k and (for the final step) parameters for the fine-tuning.
1. Treating the n rows of A as points in Rd, compute an approximate -projjccee clustering. The result l subspaces in Rdd each of dimension j. that minimize the sum of squared distances from each point (row in A) to its closest subspace. For the approximation, we compute local minimum for this problem using the DnnectaationMaxiizznnn (EM) method (Dempster et al. 1977).
2. Partition the rows of A into h different subsets according to their nearest subspace from the previous step. The result submatrices A A A where A is a n; x matrix and +... n = n.
3. For each matrix A' where 1 < i S k., factor it to two smaller matrices U' (of dimensions n, x ÿ) and V (of dimensions j x d) such that U'Vi is the rank-j approximation of A'.
4. In the full network, replace the original fully-connected embedding layer by 2 layers. The first layer is a parallelization of k separate fully-connected layers, where for every i e }}} the ith parallel layer consists of the matrix U²,, i.e. has n, input neurons and j output neurons. Here, each row of A is mapped appropriately. The second layer is by combining the matrices V!.... Vkh Each of the output vectors from the previous layer M,...., Uy are combined as V +...+ V= see Figure 3 for an illustration.
{I....
5. Fine-tune the network.
The result is compressed embedding layer. Every matrix U has nij parameters, and the matrix Vi has jd parameters. Therefore the compressed embedding layer consists of nj + kjd parameters, in comparison to the uncompressed layer of nd parameters.
Practical Solution. The projective clustering problem is known to be Max-SNP-hard even for
d = and j 2, for any approximation factor that is independent of n. Instead, we suggest to use an algorithm that provably converges to a local minimum via the Appectation-Maximiaaae method (Dempster et al. 1977). which is generalization of the well known Lloyd algorithm (Lloyd, 1982). The resulting clusters and factorizations are used to determine the new architecture and its initial weights; see Figure 3 for more details. We run on instances of AWS Amazon EC2 cloud, and detail our results in the next section.
(EM)
Open code and networks. Complete open code to reproduce the resulting networks is provided. We expect it be useful for future research, and give the following few examples.
5

---

Published as a conference paper at ICLR 2021
2.1 GENERALIZATIONS AND EXTENSIONS.
Our suggested architecture can be generalized and extended to support many other optimization functions that may be relevant for different types of datasets, tasks or applications besides NLP.
-eerrrr. For simplicity, our suggested approach aims to minimize sum of squared distances subspaces. However, it can be easily applied also to sum of distances from the points to the subspace, which is a more robust approach toward outliers ("far away points").
Even for k = recent results of Tukan et al. (2020)) show improvement over SVD.
Distance functions. Similarly, we can replace the Euclidean éz-distance by e.g. the Manhattan dis- lance which is the f -ormr between point r and its projection, i.c., I| - z' [|, or sum of differences between the corresponding entries, instead of sum of squared entries, as in the Euclidean distance || - z' in this paper.
Non-uniform dimensions. In this paper we assume that & subspaces approximate the input points, and each subspace has dimension exactly j. where j, k 2 1 are given integers. A better strategy to allow each subspace to have different dimension, ji for every E {1...., ,k],, or add constraint only on the sum j1 + ..... + j& of dimensions. Similarly, the number l may be tuned as in our experimental results. Using this approach we can improve the accuracy and enjoy the same compression rate.
For more details about those generalizations and others, we refer the interested reader to section at the appendix.
Optimal plane (j 2, 1)
Optimal 3 lines (j = 1, k = 3)
VS
Figure 4: Why k subspaces? Here, we have n = 120 data points in R that are spread around k: = 3 lines (j 1). Factoring this data based on the optimal plane P results with large errors, since some points are far from this plane as can be seen in the left hand side of the figure. On the right hand side, factoring the data based the 3 optimal lines E l2, and la gives much smaller errors. Also, storing the factorization based on the plane P requires 2(120 3) 246 parameters, compared to 120 x 1 + x 3 = 129 parameters based on l,, f2, and f3. Lc., less memory and a better result.
EXPERIMENTAL RESULTS
GLUE benchmark. We run our experiments on the General Language Understanding Evaluation (GLUE) benchmark (Wang et al.) 2018). It is widely-used collection of 9 datasets for evaluating natural language understanding systems.
Networks. We use the following networks: (i) RoBERTa (Liu et al. 2019b). it consists of 120 mil- lions parameters, and its embedding layer has 38.9 million parameters (32.5% of the entire network size), (ii) DistilBERT (Sanh et al., 2019) consists of 66 million parameters, and its embedding layer has 23.5 million parameters (35.5% of the entire network size), and (iii ALBERT (base-v2) (Lan et al., 2019), which consists of 11.7 million parameters, and its embedding layer has 3.8 million parameters (33% of the entire network).

---

Published as a conference paper at ICLR 2021
Embedding layer
Model
MRPC
COLA
MNLI
SST-2
STS-B
QNLI
RTE
WNLI
QQP
Avg.
compression rale
20%
0.98
3.4
-0.4
-0.54
-0.23
-0.81
-L08
0.26
DistiBERT
0.17
and j
4 558
4 358
4 358
|558
4 1558
5 5545
7 522
5 1545
5115
DistiBBRT
40%
1.2
3.7
0.9
0011
-0.72
0.4
0.5
& and j 30%
6 100
5 109
4 418
5] 109
3 128
7 392
5 109
5 109
3.1
-0.27
1.4
DistiBBRT
k and j
6 333
5 341
5. 341
5 |/34
5| [44
NA
7| 323
5 341
NA
1.8
RoBERTA
25% 33%
0.2
2.3
0.2
-0.5
0.44
0.2
NA
0.41
& and y
5 1117
10 451
5 517
5 51517
517
5 5117
10
451
5 1517
RoBERTA
40% 50% & and j
5 384
0.2
10 388
5. 384
5 384
0.3
5 384
5 384
10 384
5 384
NA
0.71
Table I: In the table above, we present the compressed models with the best accuracy achieved for specific compression rates (or intervals) of the embedding layer. We report their drop in aceuracy, and the used values of k and j. Specifically, in each entry the "accuracy drop" is presented above the used & and j values. The last column is the average accuracy drop over all tested tasks, Observe that: (i) negative values presents improvements in the accuracy upon the non-compressed version of the corresponding model, and (ii) the results in this table can be improved if we allow to use the best model from higher compression rates also, e.g., in the task RTE on the network DistilBERT, achieved 2.5 accuracy increase when we compressed 60% of the embedding layer, however, in this table we did not add this result for the smaller compression rates of 20, 40 and 50.
Software and Hardware. All the experiments were conducted on a AWS c5a. 16xlare machine with 64 CPUs and 128 RAM [GiB]. To build and train networks, we used the suggested implemen- tation at the Transformers D library from HuggingFace (Wolf al. 2019) (Transformers version 3.1.0, O.O and PyTorch version 1.6.0 (Paszke et al. 2017)). For more detailes about the implementation, we refer the reader to section
A at the appendix.
The setup. All our experiments are benchmarked against their publicly available implementations of the DER,, RoBERTa, and ALBERT models, fine-tuned for each task, which was in some cases higher and in other cases lower than the values printed in the publications introducing these models. Given an embedding layer from a network that is trained on a task from GLUE, an integer k 2 1, and integer j 2 1. We build and initialize new architecture that replaces the original embedding layer by two smaller layers as explained in Figure 3 We then fine tune the resulted network for 2 epochs. We ran the same experiments for several values of k and j that defines different compression rates. We compete with the standard matrix factorization approach in all experiments
3.1 REPORTED RESULTS
Compressing RoBERTA and DistilBERT. (i) In Figures Jnnd and the æ-axis is the compression rate of the embedding layer, i.c. a compression of 40% means the layer is 60% its original size. The y-axis is the accuracy drop (relative error) with respect the original accuracy of the network (with fine tuning for 2 epochs). In Figure 5 each graph reports the results for a specific task from the GLUE benchmark on RoBERTa, while Figure o reports the results of DistilBERT.
(ii) On the task WNLI we achieved 0 error on both networks using the two approaches of SVD and our approach until 60% compression rate, so we did not add figure on it.
(iii) In RoBERTa, we checked only 2 compression rates on MNLI due to time constraints, and we achieved similar results in both techniques, e.g., we compressed 45% of the embedding layer, based on our technique with k = 5 and j 384 to obtain only 0.61% drop in accuracy with fine tuning and 4.2% without, this is compared to 0.61% and 13.9% respectively for the same compression rate via SVD factorization. In DiSTiIBERT, we compressed 40% of the embedding layer with k = 4 and achieved a 0.1% increase in accuracy after fine-tuning, as compared to a 0.05% drop via SVD factorization (on MNLI).
(iv) Table suggests the best compressed networks in terms of accuracy VS size.
7

---

Published as a conference paper at ICLR 2021
Model
Parameters 11.7M
MRPC
COLA
MNLI
SST-2
STS-B
RTE
WNLI
QQP
ALBERT (buse-v2)
89.7
37.7
84.9
92.5
90.5
77.6
59.2
90.7
MESSI-ALBERS (base-v2)
11.7M
90
58.5
84.7
92.7
90.5
78.3
60.6
90.7
In the table above, we report the accuracy achieved by "ALBERT (base-v2)" model on the tasks from GLUE, and compare them to the results achieved on another model of the same size (up to 0.18% increase) which we call "MESSI-AL.BER" (base-v2)". This model is exactly the same as the original "ALBERT (hase-v2)" model up one change, where the original embedding layer of "ALBERT (base-v2)" (consists of 30k rows and 128 columns) is modified to the new suggested MESSI architecture, with & and j = 125 according the pipeline at Section 2 and without fine-tuning. It can be seen by the table, that the new architecture achieved a better results.
Table 2:
Improving the accuracy of pre-trained models using MESSI. In Table 2 we test the MESSI architecture can improve the accuracy of pre-trained model, while maintaining the same number of parameters. The only change done on the given model is factoring its embedding layer to the make sure to choose the
suggested architecture using the detailed pipeline at section 2 Here, right values of k and j such that the original embedding layer size is maintained (up to very small change). We conducted this experiment the model ALBERT (base v2). The results are actually promising.
More results that are placed in the appendix: (i) Figure 8 in section B shows the accuracy drop as a function of the compression rate on the RoBERTA model before fine-tuning. (ii) In section C we compress fully-connected layer in different settings, specifically speaking we compress the two popular models: LeNet-300-1 100 on MNIST (LeCun et al.) 1998), and VGG-19 (Simonyan and Zisserman 2014) on CIFARIO (Krizhevsky et al.J 2009), see results Figures p and [0 (ii)) In
section D we suggest way to determine the values of l and in practice for given compression rate, and we report the results on compressing DistilBERT based on this suggestion; see Figure [I (iv) Finally, in section E we check how another clustering method can fit in our pipeline, i.e., instead of clustering the input neurons of the fully-connected layer (rows of A) via projective clustering (steps 1 and 2 in the pipeline at Section 2), we try the known k-means clustering, and then continue the same by applying SVD on each cluster and building the corresponding new layers. See
results in Figures 12 13 14 and 15
CoLA
RTE
SST-2
201
2.0
Accurary dreop [99]
10.0
Acetrocy drep [99]
MISEL
1.5
Acxurnty y drag
SC354L 1-11
HISSE, L-d
26-
VTS11 Ja
MRSSE Lwa
5.3
0.3
2.5
000
-0.5
20
60
60
Compression sale [X]
Comperssion rale [%]]
Compuesion riee 3]]
MRPC
STS-B
QNLI
Steccion PeTroneTTs
Accurnty drop [99]
117000 E-3
Accuracy drop [9]]
sreee #-1
Acstrnyy drem [99]
117001 2-1
HESE,
0.75
0.50
0000
50
20
80
Compussion tale [%]
Comgression tale [%]]
Coungressso rale [9[
Accuracy drop as a function of compression rate, with fine tuning for 2 epochs after compression. To illustrate the dependence of MESSI the choice of k. we have plotted several contours for constant-k. As the reader will notice, the same dataset may be ideally handled by different values of l depending on the desired compression.
Figure 5: Results on RoBERTa:
8

---

Published as a conference paper at ICLR 2021
CoLA
RTE
SST-2
Accuracy drop [%6]
STAMUUE-PATORRAATA
Aceuracy drop (96
STARDAED SAMOMEE-PACOARAATT PASTORIIATTOO
MESST,
Accuracy drop
10-
7.5
211
512551, 2
311:81, X-
5.0
XLLSS,
06
0.0
20
30
20
60
00
90
21
30
Compression rate [%]
Compression rate [%]
Compression rate [%]]
STS-B
Accurecy dbop (96)
TEOSSRNTTTTTEACCO UAON: UESS:
UZYSL 4-14
MESS 3--5
HESS, I-
Useel and
yasc, bark
uide bad
Compression
Compecasion [X]
Compecssion
Compreasio
Figure 6: Results on DistilBERT: Accuracy drop as a function of compression rate, with fine tuning for 2 epochs after compression.
3.2 DISCUSSION
As shown by Figures and our approach outperforms the traditional SVD factorization. In all experiments, our method achieves better accuracy for the same compression rate compared to the traditional SVD. For example, in RobERTa, that 0.8% average drop in accuracy, this is compared to the 3% drop in the standard technique for smaller compression rate of 40%. In DistilBERT, we achieved 40% compression of the embedding layer while incurring only 0.5% average drop in accuracy over all nine GLUE tasks, compared 2.8% drop using the existing SVD approach. As the reader will notice, the same dataset (and network) may be ideally handled by different values of k depending on the desired compression.
compress 43% of the embedding layer with less
We observed that our technique shines mainly when the network is efficient, and any small change will lead to large error, e.g., as in the COLA/RTE/MRPC graph of Figure 5 Although we achieve better results all of the cases, but here the difference is more significant (up to 10%), since our compressed layer approximates the original layer better than SVD, the errors are smaller, and the accuracy is better. Furthermore, Figure shows clearly that even without fine tuning, the new approach yields more accurate networks. Hence, achieve higher accuracy. Finally, by Table 2 we can see that the MESSI architecture can be used also improve the accuracy of pre-trained models while maintaining the original size.
fine tune for smaller number of epochs and
3.3 CONCLUSION
We suggested a novel approach for compressing fully-comnected layer. This is by clustering the input neurons of the layer into k--sbbsets (via projective clustering) and then factoring the corre- sponding weights matrix of each subset. We then provided novel architecture that replaces the original fully-connected layer by a set of & small layers that operate in parallel and are then re- combined with single fully-connected layer. The experimental results showed that suggested algorithm overcomes the traditional factorization technique and achieves higher accuracy for the same compression rate before and after fine-tuning.
3.4 FUTURE WORK
The future work includes experiments on other networks and data sets both from the field of NLP and outside it, e-g., an inserting experiment modify the ALBERT network (Lan al. 2019) by changing its embedding layer architecture (that consists of two layers based on the standard matrix factorization) to the suggested architecture this paper, while maintaining the same number of pa- rameters, and to check if this modification improved its accuracy, also the suggested generalizations and extensions from section 2.I should be tried, where we strongly believe they will allow us to achieve even better results. Finally, generalizing the approach to other type of layers.

---

Published as a conference paper at ICLR 2021
4 ACKNOWLEDGEMENTS
Support for this research has been provided in part by NSF award 1723943. We are grateful for it.
REFERENCES
Anish Acharya, Rahul Goel, Angeliki Metallinou, and Inderjit Dhillon. Online embedding com- pression for text classification using low rank matrix factorization. Proceedings of the AAAI Conference Arlificial Intelligence, volume 33, pages 6196-6203, 2019.
Kenneth Clarkson and David Woodruff. Input sparsity and hardness for robust subspace ap- proximation. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 310-329. IEEE, 2015.
Andrew M Dai and Quoc Le. Semi-supervised sequence learning. In Advances in neural infor- mation processing systems, pages 3079 1799-307,,40 2015.
Arthur P Dempster, Nan M Laird, and Donald Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- Minneapolis, Min-
guage Technologies, Volume (Long and Short Papers), pages nesota, June 2019. Association for Computational Linguistics. doi: 10. 11118653/1/N11-1440 URL
https:/ www. ac www.wwwbbb..... www.oorg/gaatooo wttp://///.../gg/g//eoooo./e Loyy/ogygn 1423]
Michael Edwards and Kasturi Varadarajan. No coreset, no cry: li. In International Confer- ence on Foundations of Software Technology and Theoretical Computer Science, pages 107-115. Springer, 2005.
Angela Fan, Edouard Grave, and Armand Joulin. Reducing transformer depth demand with structured dropout. International Conference on Learning Representations, 2019.
Jianzhou Feng, Li Song, Xiaokang Yang, and Wenjun Zhang. Learning dictionary via subspace segmentation for sparse representation. In 2011 18th IEEE International Conference on Image Processing, pages 1245-1248. IEEE, 2011.
Mitchell A.
Gordon.
All the ways you htmm.
compress
bert.
2019.
Mitchell Gordon, Kevin Duh, and Nicholas Andrews. Compressing bert: Studying the effects of weight pruning transfer learning. arXiv preprint 2rXiv:2002.08307, 2020.
Fu-Ming Guo, Sijia Liu, Finlay S Mungall, Xue Lin, and Yanzhi Wang. Reweighted proximal pruning for large-scale language representation. arXiv preprint orXiv: / /2486, 2019.
Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. Tinybert: Distilling bert for natural language understanding. arXiv preprint arXiv: /909. 10351, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Sori- cut. Albert: A lite bert for self-supervised learning of language representations, In International Conference on Learning Representations, 2019.
Quoc Le and Tomas Mikolov. Distributed representations sentences and documents. Interna- fional conference machine learning, pages 1 1188-1996 2014.
10

---

Published as a conference paper at ICLR 2021
Yann LeCun, Léon Bottou, Yoshua Bengio. and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-23 -2224, 1998.
Linqing Liu, Huan Wang, Jimmy Lin, Richard Socher, and Caiming Xiong. Attentive student meets multi-task teacher: Improved knowledge distillation for pretrained models. arXiv preprint arXiv: 190::991100088, 2019a.
Risheng Liu, Zhouchen Lin, Fernando De la Torre, and Zhixun Su. Fixed-rank representation for unsupervised visual learning. In 2012 IEEE Conference on Computer Vision and Pattern Recog- nition, pages 598-605. IEEE, 2012.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1692, 2019b.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Julien Mairal, Jean Ponce, Guillermo Sapiro, Andrew Zisserman, and Francis R Bach. Supervised dictionary learning. In Advances in neural information processing systems, pages 1033-1040, 2009.
J Scott McCarley. Pruning a bert-based question answering model. arXiv:1910006360, 2019.
arXiv preprint
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? In Advances in Neural Information Processing Systems, pages 14014-14024 2019.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances in neural information pro- cessing systems, pages 3111-3119, 2013.
Subhabrata Mukherjee and Ahmed Hassan Awadallah. Distilling transformers into simple neural networks with unlabeled transfer data. arXiv preprint arXiv:1910.01769, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Detio,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS- W, 2017.
Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. In Proceedings of the 2018 Con- ference of the North American Chapter the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long Papers), pages 2227-2237, 2018.
Alec Radford, Karthi Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training, 2018
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. OpenAl Blog, 1(8):9, 2019.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 1910.0/008 2019.
Sheng Shen, Zhen Dong, Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Q-bert: Hessian based ultra low precision quantization of bert. In AAAL, pages 8815-8821, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for bert model compression. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP. IJCNLP), pages 4314 4323, 2019.
11

---

Published as a conference paper at ICLR 2021
Raphael Tang, Yao Lu, Linqing Liu, Lili Mou, Olga Vechtomova, and Jimmy Lin. Distilling task- specific knowledge from bert into simple neural networks. arXiv preprint arXiv:1903. 2019.
Ivana Tosic and Pascal Frossard. Dictionary learning. IEEE Signal Processing Magazine, 28(2):
27-38, 2011.
Holger Trittenbach and Klemens Böhm. One-class active learning for outlier detection with mul- tiple subspaces. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 811-820, 2019.
Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. arXiv preprint arXiv:2006.05482, 2020a.
Murad Tukan, Alaa Maalouf, Matan Weksler, and Dan Feldman. Compressed deep networks: Good- bye svd, hello robust low-rank approximation. arXiv preprint arXiv:2009.05647, 2020b.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNI.P: Analyzing and Interpreting Neural Networks for NLP, pages 353-355, 2018.
Ziheng Wang. Jeremy Wohlwend, and Tao Lei. Structured pruning of large language models. arXiv preprint arXiv: 191.04391. 2019.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, al. Huggingface" transformers: State-of-ther the-ath-rr natural language processing. ArXiv, pages arXiv-1910, 2019.
Dong Xu, Shuicheng Yan, Lei Zhang, Hong-Jiang Zhang, Zhengkai Liu, and Heung-Yeung Shum. Concurrent subspaces analysis. In 2005 IEEE Computer Society Conference on Computer Vision and Pattem Recognition (CVPR'OS) volume pages 203-208. IEEE, 2005.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. In Advances in neural information processing systems, pages 5753-5763, 2019.
Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7370-7379, 2017.
Ofir Zafrir, Guy Boudoukh, Peter Izsak, and Moshe Wasserblat, Q8bert: Quantized 8bit bert. arXiv 2019.
preprint
12

---

Published as a conference paper at ICLR 2021
A IMPLEMENTATION IN PYTORCH
Since we did not find straight support for the new suggested architecture, we implemented it as follows. To represent the matrices V1 V* that are described is Section [ we concatenate them all to a one large matrix = [(V2)² ,............... (V of kj rows and d columns, and we build fully- connected layer the corresponds V. For the parallel layers (matrices) U .... U we build one large sparse matrix U of n rows and kj columns. Every row of this matrix has at least (k - 1)j zero entries, and most j non zero entries, where the non-zero entries of the ith row corresponds the rows in matrix V which encode the closest subspace to that row's s point.
Finally, during the fine tuning or training, we set those zero entries in U non- non-trainable parameters, and we make sure that after every batch of back propaaation they remain zero. Hence we have at most nj non-zero entries (trainable parameters) U and n. + ndd: total.
We hope that in the future, the suggested architecture will be implemented in the known Deep- Learning libraries so it can easily used while taking advantage of the substantial time and space benefits presented in this paper.
kj
7
kj x = 9x7
X1
y1
21
V1
E
R
3x7
0
0
0
X2
y2
22
0
0
X3
Y3
X
V2 E R 3x7
X4
y4
24
X4
y/4
0
0
0
X5
3/5
25
0
0
0
V3 E R 3x7
X6
3%6
Z6
The matrix U²: represent coordinates of cluster "1 on the subspaceV
X6
V6
0
0
0
X7
y7
27
The matrix V: Concatenation the matrices V ... 3 that represent the subspaces.
The matrix I/: the large sparse matrix as explained this section.
Figure 7: Implementation. Example of the factorization A = UV in our implementation. Here and d = 7. The matrix U is built such that row contains partitioned to the 7th subspace. In this example, the 4th and 6th rows were both clustered to the first subspace. Hence, the first 3 coordinates of the corresponding rows in the representation matrix U are nonzero, and the other entries are zero. In this way, we used jk dimensions so that none of the subspaces of dimension interact.
from U where point was
13

---

Published as a conference paper at ICLR 2021
B RESULTS BEFORE FINE TUNING
In this section we report the result compressing RoBERTa without fine-tuning. By Figure can clearly see that even without fine tuning, the new approach yields more accurate networks compared to the standard SVD factorization. Hence, our approach gives a better start for the learning (fine-tuning) process, which implies that we can fine tune for smaller number epochs and achieve higher accuracy and smaller networks.
CoLA
Accuracy 190
STAMDbRR-FF POTTRRREEO
STANDWAD-PGTTORRRIIN
Avcuracy drop [56]
STANDMADDFFATTORRE
MESSL-- 10
Accuracy drop
MESSI, -9
MIES5), 5
MKSSI,
MLSSI, 10
00
20
10
Compression rate [%6]
Compression rate [%6]
Compression rate [%)
MRPC
STS-B
Accuracy dropp [56]
Avcuracy drop [96)
STANDAED-
MESSL, =
AIESSL
MINS51,, 5
Accuracy
20
30
Compression rate [%]]
Compression rate [%6]
Compression rate [96]
Figure 8: Compressing RoBERTa results: Accuracy drop as function of compression rate, without fine tuning.
14

---

Published as a conference paper at ICLR 2021
C COMPRESSING FULLY-CONNECTED LAYERS USING MESSI.
In this section we test our approach on two popular models: LeNet-300- on MNIST (LeCun
al. 1998), and VGG-19 (Simonyan and Zisserman 2014) on CIFARIU (Krizhevsky al. 2009).
Also here, we conducted our experiments on the same hardware described in Section 3
In both experiments, SVD factorization). For every value of k, we compress each layer from the hidden fully-connected layers of the given model by the same percentage and using the same value of k.
approach multiple values of k and compare it to k = (standard
LeNet-300-100. The network consists of 266610 parameters, and it is comprised of two fully- connected hidden layers with 300 and 100 neurons, respectively, trained on the MNIST data set.
We test our approach on à E 32,3,4,5) 4, In Figure 9 we report the accuracy drop function of the compression rate for the whole network. We can see the advantage of our approach when compressing more than 90% of the network.
Accuracy drop [%)
SVT>
RSS112
KSS1,3
MESS14
MBSSI,
85
95
Compression rate [%]
Figure Compressing LeNet-300-100; Accuracy drop as a function of compression rate
VGG-19. We used the implementation at The network consists of 16 convolutional layers, fol- lowed by 2 dense hidden (fully-connected) layers with 512 neurons each. Finally, the classification layer has 10 neurons. The fully-connected layers consists of 530442 parameters.
Here, we tested our approach for & E (2,5). In Figure 10 we report the accuracy drop as a function of the compression rate of the fully-connected layers. The suggested approach has clear advantage for high compression rates.
Accuracy drop [%]
SVD
MESSI, 2-2
20
MESSL,
15-
10
5
0
95.5
96.0
06.5
97.0
97.5
Compression rate [%]
Figure 10: Compressing VGG-19: Accuracy drop function of compression rate of the fully-
connected layers in the network
15

---

Published as a conference paper at ICLR 2021
D MESSI-ENSEMBLE
In this section show only the best computed results of DistilBERT: that is obtained by training models at several values and then evaluating the model that achieves the best accuracy on the training set. Specifically, given folly-connected layer of n imput neurons and d output neurons, for given compression rate (c.g., I 0.4 means that we want to remove 40% of the parameters), we try multiple values of via binary search on For every such & value we compute the implied value j = (1 z)dn/(( (n + kd), and we compress the network based on those k and j via the MESSI pipeline. Finally, we save the model that achieves the best accuracy on the training set, and evaluate reports the results for this approach.
its results on the test set. Figure []
CoLA
RTE
SST-2
Accuracy drop [%]]
30
STANDARI- FATTORIDATION
MESSL, sasRCABL
Accuracy drrap [%6]
10
STANDAND- PACTORRATION
XEESS, axvceasu
Accuracy drop (6
$000.
STAMPARD EATTORIATION
MESSI,
2h-
60-
2.5
0-
20
Compression rate [%)
Compression rate [%]
Compression rate [%]]
MRPC
8T8-8
ONL
QQP
Accurscy doop [X]
Furmersuorr S4FSSA, partinse
Accurary drop 180
Accuvory [X]
1:E551 L...
Compression rate [X]]
Compression rate [X4]
Compression gate [X]
Compression rate [34]
Figure 11: Results DistilBERT: Accuracy drop as function of compression rate, with fine tuning for 2 epochs after compression. The red line (MESSI, ensemble) is obtained by training models at several & values and then evaluating the model that achieves the best accuracy on the training set.
E PROTECTIVE CLUSTERING VS k-MEANS
Recall the suggested pipeline from section 2 in IRd, each of dimension that approximates the (k,j)-projectis Then, the second step partitions the input neurons (rows of A) according to their closest subspace from the set of subspace that is computed in the first step. Then, in step 3, we compute the SVD for each cluster, and in steps 4 and we build (and possibly fine-tune) the corresponding architecture as described (see in Figure B)
The first step of it is compute set of l subspaces
clustering of the input matrix A.
In this section, we compare using projective clustering to using k-means clustering. We do apply steps and 2, as we instead partition the input neurons (rows of A) into h groups via applying k- means clustering on them (instead of projective clustering). We then apply steps 3, and in exactly the same way.
Here, we evaluated our results on the networks: RoBERTa (Liu et al. 2019b) and DistilBERT (Sanh) et al. 2019) on the RTE and MRPC tasks from the GLUE benchmark (Wang et al. (018)) Figures 12 and 13 compare the results on RoBERTA between the two clustering methods, with and without fine-tuning, respectively, while Figures and 15 do the same for the results on DistilBERT.
We also used the LcNet-300-100 model on MNIST LeCun et al. (1998) to check this (same) exper- iment in different setting. See Figure 16
Discussion. In Figure 13 where we test the accuracy drop before fine- tinittnnin, we can see that using projective clustering for partitioning the neurons is better than running k-means them, i.e., the projective clustering approach yielded a better start (accuracy before fine- tuning) than the k-mmaans approach for the learning process.
16

---

Published as a conference paper at ICLR 2021
roberta-MRRCC
roberta-RTE
MESSLK SEANS 3-3
MESSLR 3-19
Aceuracy drop [%
Accuracy drop [96]
MESSI,, Crimeaaee, I-
4-
2.
2-
20
40
60
20
40
60
Compression rate [%]
Compression rate [%]
Figure 12: Compressing RoBERTa (with two epochs of fine-tuning): Accuracy drop as a function
of compression rate, comparing the projective clustering approach to the known k--maan clustering.
roberta-MRPC
roberta-RTE
10
K-SSSA x-5
KESSS,K- x-10
Accuracy drop [96]
PESSS.PRORRCIVEE CLUSERBI,, K-5
Accuracy drop [%6]
MESSLPRRIEEIIVEE CLUSTERING, K-
20
40
60
20
40
60
Compression rate [%]
Compression rate [%]
Figure 13: Compressing RoBERTa (without fine-tuning): Accuracy drop as function of compres- sion rate, comparing the projective clustering approach to the known k-means clustering.
This could be explained by the fact that our original approach (projective clustering) aims compute a set of lt subspaces (each of dimension j) that minimizes the sum of squared distances from each row the input matrix (neuron) its closest subspace from the set. Hence, factoring the matrix A based those subspaces gives good approximation for it, which is not the case in the k-means clustering.
This advantage may explain the difference between the two approaches after fine-tuning for the same number epochs as can be seen in Figure I2
On the other hand, in Figure 15 the two methods gave similar results in terms of accuracy before fine tuning, and we can see that this effects the results after the fine-tuning, where the two approaches also succeeded to get similar results can be seen in Figure [3]
Hence, the better way to determine the partition (which determines the compressed architecture) and to initialize the new layer in the MESSI pipeline is the projective clustering approach.
17

---

Published as a conference paper at ICLR 2021
distilbert-MRPC
distilbert-RTE
PRODSI,P CLOSERIIEG E-7
Accuracy drop [%]]
Accuracy drop [%]
1.5
MFXSI, VIEAS, X-7
1.0
0.5
2.
CLUSTERING,
MISS8I PRomerivv CLLMERING, R-
1100
MTSSI R-MKARS,
X-SAA,,
20
20
40
60
80
Compression rate [%]
Compression rate [%]]
Figure 14: Compressing DistilBERT (with two epochs of fine-tuming tuning): Accuracy drop as a function of compression rate, comparing the projective clustering approach to the known k-means clustering.
distilbert-MRPC
distilbert-Rii
17.5
BlESSI,PRoozerrt CLUSTERIG, K=?
Accuracy drop [%6]
Accuracy drop [%6]
MISSLK X-7
15.0
.12
12.5
10-
10.0
8
HESSI,PROmCCTIe CLUSTRRING, Rmd
7.5
BIESS..PORICCIS CULSERRING K-3
KAMEAR,,
MENSL, SHERS, SHEARS,
xed
5.0
20
40
60
20
43
60
80
Compression rale [%]
Compression rale [%]
Figure 15: Compressing DistilBERT (without fine-tuning): Accuracy drop as function of com- pression rate, comparing the projective clustering approach to the known k-means clustering.
Accuracy drop [%]
0.8
MESSL MRRorrCTTV--CLLSTEEEE
MESSL. HESSI.K-MB. K-MANS
0.6
0.4
0.0
86
Compression rate [%]
Figure 16: Compressing LeNet-300-100, Accuracy drop as function of compression rate. Here we compare the projective clustering approach to the known k-means clustering.
18

---

Published as a conference paper at ICLR 2021
E. GENERALIZATIONS AND EXTENSIONS.
Here, we give more details about the suggested generalizations and extensions from section 2.1 we also add few more:
er-error. For simplicity, our suggested approach aims to minimize sum of squared distances to subspaces. However, it can be easily applied also to sum of distances from the points to the subspace. In this case, we aim to compute the maximum-likclihood of the generating subspaces assuming a Laplacian instead of Gaussian distribution. More generally, may want to minimize the sum over every distance to the power of > O., i.e., we take the g-norm |errll, where err is the distance between a point to its projection on its closest subspace.
Even for k recent results Tukan et al. (2020b) show improvement over SVD.
Observe that given the optimal subspaces, the system architecture in these cases remains the same as ours in Figure
Distance functions. Similarly, we can replace the Euclidean fz-distance by egg. the Manhattan distance which is the fı-norm between a point and its projection, i.e., || - x2|1, or sum of dif- ferences between the corresponding entries, instead of sum of squared entries, as in the Euclidean distance ||2 - 22112 in this paper. More generally, non-distance functions such as M-Estimators that can handle outliers (as in Tukan et al. (2020a)) by replacing dist(p (p, x) with min (dist(p, xr), i) where >> is constant (threshold) that makes sure that far away points will not affect the overall sum too much.
may use the lp distance ||a z'1l
z' or
From an implementation perspective, the EM-algoriin allgortt for k-subspaces uses a l = 1 solver routine blackbox. Therefore extending to other distance functions is simple replacing the SVD solver (the k = for Euclidean distance) by the corresponding solver for k = 1.
Non-uniform dimensions. In this paper assume that & subspaces approximate the input points, and each subspace has dimension exactly j. where j. & 2 1 are given integers. A better strategy to allow each subspace to have different dimension, ji for every E (1....,k), constraint only on the sum j1 + ........ j&k of dimensions. Similarly, the number k may be tuned as in our experimental results. Using this approach we can improve the accuracy and enjoy the same compression rate. This search or parameter tuning, however, might increase the computation time of the compressed network. It also implies layers of different sizes (for each subspace) in Figure 3
add
Dictionary Learning, Our approach of projective clustering is strongly related to Dictionary Learn- ing (Tosic and Frossard, 2011 Mairal et al. 2009). Here, the input is matrix A R xxd and the output is a "dictionary" VT E R and projections or atoms which are the rows of U E RaxJ that minimize A UVI under some norm. It easy to prove that UV simply the j-rank approxima- tion of A, as explained in Section T However, if we have additional constraints, such that every row of U should have, say, only
non-zero entries, then geometrically the columns of VT are the j lines that intersects the origin and minimize the sum of distances to the points. For k > 1 every point is projected onto the subspace that minimizes its distance and is spanned by k: columns of VT*
Coresets are useful tool, especially in projective clustering, reduce the size of the input (compress it in some sense) while preserving the optimal solution or even the sum of distances any set of k subspaces. However, dependency on d and k is usually exponential as in Edwards and Varadarajan (2005). A natural open problem is compute more efficient and practical coresets for projective clustering.
Coresets.
are not aware of any efficient implementations and the
E.2 EXPERIMENTING ON (9-ERROR
To get a taste of the suggested extensions, we tried the first suggestion (9 (9-error, with q = 1. Le.. cluster the rows of the input matrix A based the set of k-subspaces that minimizes the sum of (non-squared) distances from each row in A to its closest subspace from the set.
The local minimum of the new clustering problem still be obtained by the suggested EM al- gorithm. The only difference is that the SVD computation of the optimal subspace for cluster of points (k 1) should be replaced by more involved approximation algorithm for computing the
19

---

Published as a conference paper at ICLR 2021
Clustering method
Task
Fine-tuning epochs
J == 517
J == 348
PC--1
MRPC
0
3.1
5.1
PC-82
MRPC
0
3.9
5.1
PC-f1
MRPC
2
0.2
0.2
PC-f2
MRPC
2
0.2
0.2
PC-E
RTE
0
5
6.8
PC-f2
RTE
0
3.2
7.4
PC-81
RTE
0.47
PC-L2
RTE
2
0.44
Table 3: the table above, we compare two approaches to cluster the rows of the input matrix A (and check how they fit the MESSI pipeline), the first approach is projective clustering with l error (PC-(*), and the second is the standard protective clustering with e² error that we used in all the other experiments.
subspace that minimizes sum over distances to the power of = 1; see e.g. Tukan et al. (202b)) Clarkson and Woodruff (2015).
However, this change increased the running time of the algorithm from minutes to days, this is due the fact the deterministic approximation algorithms for the problem (f'-error) with k take time of O(nd)) at least, where d = 768 in our case, and we need to run this approximation algorithm many times in the EM procedure. For that, conducted our experiments only on one network (RoBERTA) on 2 tasks from the GLUE benchmark (MRPC and RTE).
Table 3 shows the accuracy drop for both techniques for two values of j with A 5 on the MRPC task, and the same on RTE with k = 10. It can be seen from the table, that mostly, using the l' error as initialization is better than the f However,for some reason (that needs further investigation) after fine-tuning for epochs both approaches reached almost the same accuracy, even more, the L approach achieved a better accuracy sometime. We leave this for future research.
20


Reviews:
[{"review_id": "z5Fh_iUbnR9", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper applies projective clustering to the embedding layer of deep networks with large model sizes such as RoBERTa. The idea of finding more than one subspaces to factorize the embedding weight matrix has nice intuition and insights. I vote for accepting.\n\nStrengths:\n1. The paper has convincing evidence showing the reduction in percent of accuracy drop when applying projective clustering to the embedding weight vectors.\n2. The paper has illustration figures that clearly show the intuition of the approach as well as how the compression is achieved.\n\nWeaknesses:\n1. It would be better if more baselines can be included in the experiment comparisons. In particular, Since Step 2-3 of the proposed MESSI pipeline (page 4) is partitioning of all the input neurons and computing SVD for each partition, I would be really interested in seeing the comparison of projective clustering vs simpler clustering methods such as k-means to partition the input neurons, in the evaluation.\n2. The authors discussed extensions such as using $L_1$ error and $L_1$ distance, but no experiments were performed for the extensions. Some experiment results will be better to establish the flexibility of the framework of projective clustering in model compression tasks.\n\nQuestions during rebuttal period: \n1. Please provide some results regarding the weaknesses above, especially the result of more baseline methods.\n2. Is projective clustering the only way to find clusters in multiple subspaces? What are some alternatives? For example, in subspace clustering, all the data points can be projected to the same subspace and form clusters; we may run subspace clustering for multiple times to get clustering results in different subspaces.", "extra_scores": {}, "extra_text": {}}, {"review_id": "tsnw8rFFHb9", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a new approach, based on projective clustering, for compressing the embedding layers of DNNs for natural language modeling tasks. The authors show that the trade-off between compression and model accuracy can be improved by considering a set of k subspaces rather than just a single subspace. Methods for compressing DNNs is an active area of research and this paper presents a promising approach to do so as well as interesting results. \n\nRating: The paper presents interesting ideas for compressing embedding layers. However, since this is an empirical paper, I would expect a more comprehensive set of empirical results and a better comparison with other related methods. Overall, the paper seems not very mature in its current form, hence my rating is 'Ok but not good enough - rejection'.\n\nPros\n----\n* The proposed method is appealing due to its simplicity and the idea of considering multiple subspaces for embedding is plausible in the context of compressing embedding matrices of NLP models.\n\n* The results show improvements as compared to using just a single subspace. \n\n* The framework provides several ideas for future works. \n\nCons\n-----\n* Typically, the SVD takes the form A = UDV, where U and V are the left and right singular vectors and the diagonal entries of D are the singular values. From the discussion it is not clear whether you factor the singular values into U, or whether you simply ignore the singular values? Also, how do you enforce the orthogonality constraints on U and V during the fine tuning stage? Have you considered a simpler low-rank factorization A = EF in your experiments, where no orthogonality constraints on E and F are imposed?\n\n* It would be good to see the progression for k={2,3,4,5} in Figure 5 and 6. Further, the ensemble approach in Figure 6 hasn't been discussed in detail anywhere in the paper. It is not exactly clear to me how you are computing the ensemble.\n\n* It would be very helpful to see some Tables that shows the total number of weights, accuracy, k, j, etc., in order to better understand the performance.  \n\n* How do you determine k and j in practice? Are you using some heuristic or are you simply doing a grid search?\n\n* I would like to see how your method compares to ALBERT and whether a modified ALBERT (as you suggest in your future work section) is doing better.\n \n* I would be interesting to see if you approach is also useful for compressing a fully connected layer in different settings. This should be easy to test and could be reported in the Appendix. \n\nMinor comments:\n--------------\n* It is nice to see that you have many generalizations an extensions in mind, but this section appears very lengthy to me. \n\n* compression rater -> compression rates", "extra_scores": {}, "extra_text": {}}, {"review_id": "RcbG-gMSN45", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends the idea of using subspace clustering to compress the neural nets by considering multiple subspaces and projecting each point to its closest subspace. The paper needs more investigation on the related works. Basically, the idea and the technique is not novel. See the related literature below:\n[1] Trittenbach, Holger, and Klemens Böhm. \"One-Class Active Learning for Outlier Detection with Multiple Subspaces.\" Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2019.\n[2] Liu, Risheng, et al. \"Fixed-rank representation for unsupervised visual learning.\" 2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2012.\n[3] Xu, Dong, et al. \"Concurrent subspaces analysis.\" 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). Vol. 2. IEEE, 2005.\n[4] Feng, Jianzhou, et al. \"Learning dictionary via subspace segmentation for sparse representation.\" 2011 18th IEEE International Conference on Image Processing. IEEE, 2011.\n---------------------------------------------\nPros:\n•\tSmoothly readable. \n•\tThe contribution section is described thoroughly and properly. \n•\tProviding the codes for reproducing results.\n---------------------------------------------\nCons:\nAbstract:\n•\tThe abbreviations like NLP or SVD should be defined first, then used. \n•\tAssuming that the reader already has corresponding field knowledge about systems such as GLUE, DistilBERT, or RoBERTa and mentioning them in the abstract may be bold.\n•\tDetails of the methods such as the use of Aj matrix or k>1 subspace should not be mentioned in the abstract but rather in the contribution or introduction section accordingly.\n•\tThe last sentence “Open Code for ….” Should not be mentioned in the abstract but in the code description section. \n•\tThe figures 1-3 in the paper look not well organized, which makes the proposed simple idea to be extremely complex.\nResults:\n•\tIt would be better to discuss the comparable results more thoroughly. \n•\tModel compression literature should be reviewed and the typical methods should be compared with in the experiments.\nDiscussion and Conclusion:\n•\tOnly discussion of the results is provided in this section and the conclusion is not provided explicitly. \n\n\nFuture Work:\n•\tBetter not to start the section with numbered items right away. Better to have a starting sentence first. \nAppendix B\n•\tTitled results before fine-tuning and includes figures with no explanation. Provide proper description and discussion for each subfigure. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to use projective clustering to compress the embedding layers of DNN. This is a novel interesting idea which can  impact the area of Knowledge distillation. There were some concerns about the empirical study which was addressed to some extent  by the authors during the rebuttal.
Decision: Accept (Poster)