Approximative Sparse Factorization of Neural Network Weight Matrices

Abstract: In modern image processing applications, Convolutional Neural Networks (CNNs) are indispensable. Especially in the domains of object classification and face recognition, CNNs achieve impressive results. However, the increasingly accurate predictions are accompanied by ever-larger networks and consequently more computations. The number of operations required to compute the matrix vector product of a dense matrix M ∈ N N ×N in the fully connected layer scales with O (N 2 ) , mainly responsible that networks like VGG19 require 19.6 billion Floating-point Operations (FLOPs) to evaluate a single image. This thesis investigates the factorization of weight matrices, of the fully connected layer, into a product of sparse matrices, which potentially reduces the order of operations needed to the subquadratic domain. Consequently, the number of operations required for inference and thus, resource consumption is reduced. I examine three approximation algorithms, namely Butterfly factorization, sparse EigenGame, and Flexible Approximate MUlti-layer Sparse Transform ( F AμST ). The approaches are compared regarding the sparseness of their approximation and the approximation error. Furthermore, weight matrices of pre-trained Convolutional Neural Networks are factorized and compared regarding their prediction accuracy after approximation. 
The best performance in terms of approximation error of the matrix and subsequent prediction accuracy was achieved by F AμST . F AμST was able to make sufficiently accurate predictions with only 20 % of the parameters. Where sufficient accurate means that the prediction accuracy drops by only 1 %. For similar results, the other algorithms needed 3 % (Butterfly) and 18 % (sparse EigenGame) more computations than the original matrix-vector product. 
The experiments show that Approximative Sparse Factorization (ASF) of the weight matrices can significantly decrease resources consumption without deteriorating the accuracy of the predictions too much. This can enable complex computer vision algorithms to be used on devices with low computational resources or time-critical systems.

FINISHED