Low-Rank Approximations for Conditional Feedforward Computation in Deep Neural Networks
Authors: Andrew Davis, Itamar Arel
ICLR 2014

Abstract: Scalability properties of deep neural networks raise key research questions, particularly as the problems considered become larger and more challenging. This paper expands on the idea of conditional computation introduced by Bengio, et. al., where the nodes of a deep network are augmented by a set of gating units that determine when a node should be calculated. By factorizing the weight matrix into a low-rank approximation, an estimation of the sign of the pre-nonlinearity activation can be efficiently obtained. For networks using rectified-linear hidden units, this implies that the computation of a hidden unit with an estimated negative pre-nonlinearity can be ommitted altogether, as its value will become zero when nonlinearity is applied. For sparse neural networks, this can result in considerable speed gains. Experimental results using the MNIST and SVHN data sets with a fully-connected deep neural network demonstrate the performance robustness of the proposed scheme with respect to the error introduced by the conditional computation process.


Peer review:
[Review]:
-Demonstrates that the sign approximation method slightly improves test error.
I'm not sure where you're seeing this -- on the test set, the sign approximation always increased the test error (as a function of how poor the approximation was). One should expect the method to make test error slightly worse as a trade-off for faster computation. This approach does not try to improve generalization -- it is forming the basis of a method to trade-off between speed and accuracy.

-The main purpose of the work...
-It's not obvious...
-If computational cost can in fact be reduced...
These three points have been addressed in a new revision of the manuscript. There are many parameters that determine the theoretical speedup (size of each layer, how approximately the weight matrix can be calculated, how sparse the activations are), so the answer (that is, the overall speedup) depends on these factors.

-The baselines that are improved upon are not competitive
The baselines are not intended to be competitive to state-of-the-art methods.  The emphasis is on investigating how the activation estimation degrades the training of the neural network.

-It's not clear that the hyper parameters were chosen in a way that makes the comparisons fair
We've added a description of how the hyperparameters were chosen to the manuscript.

-I don't think you can necessarily conclude...
Interesting, I did not know this -- I was going off of the introduction in Coates et al's paper.

-I don't think you can conclude...
I disagree.  If the biases are part of the weight matrix (an okay thing to do), then we observe the following:

a in R^{N 	imes d}, W in R^{d 	imes h}, U in R^{d 	imes k}, V in R^{k 	imes h}:

UV = hat{W}

Assuming:
rank(hat{W}) = k
rank(a) = d

Then:
rank(ahat{W}) le min(rank(a), rank(hat{W})) = min(d, k)

Because k < d (otherwise, we are wasting time with the conditional computation, because the activation estimator would take longer than the regular feed-forward), the rank of the resulting activations can be fairly well represented by a linear projection of lower-rank, indicating redundancy in the same sense that the weights are redundant.  Redundant does not necessarily mean useless -- the extra dimensionality gives us some more 'wiggle-room' for discrimination.  The key observation is that we may be able to 'get away with' a very low-rank representation of 'W' if we are only interested in recovering the sign of 'a'.

-Simply being able to predict...
Agreed -- the activation estimator is designed to be efficient, but it is certainly possible to be slower overall if a bad choice is made for the rank, or if the activations are not sufficiently sparse.  There are likely smarter and faster ways of doing the conditional computation that have not been investigated.  We've added a section describing the number of FLOPS required for a regular neural net and a neural net augmented by this conditional computation scheme.

-You also need some mechanism...
I agree.  This part will require the most effort to implement well.  It is hard to beat off-the-shelf BLAS libraries, but the proposed matrix-multiplication would not be a sparse-sparse (ie., memory-bound) operation.  It would be dense-dense, with some additional control structure to allow certain dot-products to be skipped.  This will surely add some overhead, and it is hard to speculate exactly how much.  Using the equations in Section 3.4 (the new section on the FLOPS required), there could be as much as a 5-20x speedup in feed-forward for an Imagenet-size network, depending on sparsity and rank. As such, we feel it is worth investigating this special matrix multiplication.

-I think you're missing the fundamental idea...
We disagree.  Bengio, Leonard, and Courville put a preprint on arXiv (http://arxiv.org/abs/1308.3432, citation [3]) using a similar scheme, but differing in execution -- an auxiliary network off to the side that decides which neurons need to be calculated, which is trained by backpropagation (with a sparsity constraint).  This approach is still at least linear in the number of hidden neurons.  Implementing a network that is exponential in the number of features will likely take an incremental effort, and we feel that this approach is a good starting point.

-I'm not sure sparsity of the representation...
Thanks for pointing this out -- indeed, the activations of maxout networks are dense, making the statement in the paper about sparsity too strong.  We only meant to say that sparse representations work well in a lot of cases, so we should take advantage of them.

-Your presentation is confusing...
Thank you for pointing this out, I have fixed this.

-I don't understand the paragraph on dropout...
I have revised the wording here, apologies for the confusion.  There is no obvious connection to the dropout rate and the eventual sparsity of the network, in the sense of 'given a dropout rate p, the sparsity of the activations of the geometric-mean network will be q'.  It is simply a side-effect that a neural net trained with dropout tends to be more sparse than a network that is trained without.

-1 is probably a pretty high value for the initial biases.
We used a suggestion in the Imagenet paper -- set the biases to a high value so the neurons are mostly active for the initial part of training. We had good initial results with it, so we did not explore other values when it came to tuning hyperparameters.

-Was dropout applied to the input...
We were not using dropout on the input layer (is this commonly done outside of the context of denoising autoencoders? I'd be interested in seeing a reference for this.)  Thanks for pointing this out, I've clarified this in the new manuscript.

-Where did these hyper parameters come from?...
I've updated the manuscript to detail the hyperparameter selection (done in the usual way -- split the training set into a training and a validation set, try several sets of hyperparameters, select the set of hyperparameters that yields the best validation set.)  The hyperparameters were chosen using the baseline network and were not used to guide the performance of the predictor network.  You may be misunderstanding the point of this work, which is to investigate the degradation of performance as the activation estimator becomes more approximate -- we are not trying to improve the performance of neural nets with the activation estimator.  The interesting part is how approximate we can make it before performance suffers noticeably.

-...your experiments are bypassing the most important part of the paper, which is to demonstrate a speedup...
This is true, as the conditional matrix multiplication has not yet been implemented in an efficient way.  The implementation of the conditional matrix multiplication will certainly have some overhead, but we do not expect it to be as great as the overhead seen in sparse-sparse operations.  There are two reasons for this:
1) We are still ultimately doing a dense-dense matrix multiplication, so we don't need to spend any time creating sparse matrices.
2) We will still be able to take advantage of things like locality, caching, vector operations, (all of which are mostly off the plate with sparse operations) so we expect the operation to still be mostly compute-bound (as opposed to sparse operations which are memory-bound).  We are beginning to work on a CPU as well as a GPU implementation.
A conditional matrix multiplication could also allow us to only calculate the backpropagation through the required (ie., non-zero) neurons, which could lead to similar speed gains in the backpropagation phase.

-Moreover, as far as I can tell, you don't quantify the cost of frequently running SVD during training.
The cost of the SVD is fairly insignificant because it is evaluated so infrequently (without impacting the accuracy of the estimator too greatly).  On my machine, evaluating an SVD takes ~0.30s for a 1000x784 matrix.  Each epoch for the SVHN net took ~300s.  We've found some interesting ways to speed up successive SVD calculations with warm start methods (faster factorization given a closer starting point to the final factorization), but we have not experimented with them yet.  Admittedly, the SVD is a pretty heavy operation, and we would like to move away from it, especially considering that there are many properties of the SVD that aren't crucial for this approach to work.

-...The bigger of the two has about three million parameters and doesn't seem to be able to fit the SVHN dataset all that well...
The codebase was confined to using a fully-connected net, so it is not surprising that the SVHN results were far from state-of-the-art.  The results are comparable to the stacked auto-encoder results reported in 'Reading Digits in Natural Images with Unsupervised Feature Learning' (Netzer, et al).

-Are your nets actually large enough...
Good question.  deeplearntoolbox turned out to be a slightly inappropriate codebase (a very slow convnet implementation, no GPU support) for the purposes of this work, and I am currently modifying cuda-convnet to work with conditional computation.  We look forward to applying this method to large convolutional networks trained on more difficult datasets, such as Imagenet.

-...I'm confident that your baseline control system is not good...
In Nitish Srivastava's MS thesis, he reports 1.25% for a fully-connected relu network with dropout, and 1.05% for a fully-connected relu network with dropout and a max norm constraint.  It is very difficult to get less than 1% on the permutation-invariant task without resorting to things like elastic deformations.  While the reported ~1.4% in this work is far from these results, I believe the 0.4% difference in performance can be attributed to a less-than-optimal hyperparameter search, or perhaps some subtle difference in implementation, eg., learning rate scheduling, momentum scheduling, weight initialization scheme, etc.  Because the purpose of this work is to investigate the effects of the approximation on the performance of the network, less time was spent on finding hyperparameters that would yield state-of-the-art performance on MNIST.