<  Back to the Polytechnique Montréal portal

Operations Research Techniques for Neural Network Compression

Matteo Cacciola

Ph.D. thesis (2023)

[img] Restricted to: Repository staff only until 24 April 2025
Terms of Use: All rights reserved
Show abstract
Hide abstract

Abstract

In numerous scenarios requiring data-driven predictions, Machine Learning (ML) models consistently achieve the State Of The Art (SOTA) performances. Particularly noteworthy are Neural Networks (NNs), which have asserted their dominance in recent years across diverse domains such as Computer Vision and Natural Language Processing. The prediction accuracy of novel NN models improves annually, though accompanied by the trade-off of larger architectures. This results in augmented memory storage and computational power requirements for model training and execution. The substantial parameter count in recent NN architectures has necessitated the development of Model Compression (MC) techniques. These techniques aim to reduce the resource demands of a model while maintaining its performance capabilities. In this context, leveraging Operations Research (OR) techniques appears highly suitable. The inherent high-level problem formulation involves minimizing the resources required by a model while preserving its accuracy within a closely defined range. This naturally paves the way for various potential OR approaches to articulate and address this challenge mathematically. Furthermore, a significant portion of the existing techniques within the MC literature relies on heuristic reasoning or simplistic concepts, often lacking robust theoretical foundations. Additionally, there exists a limited comprehension of the underlying mechanisms responsible for the efficacy of certain MC algorithms and their operational principles. The primary objective of this thesis is to formulate and develop MC methodologies that leverage OR techniques, rooted in robust theoretical foundations, and that contribute towards unraveling the dynamics governing this domain. First, we introduce the Structured Perspective Regularization (SPR), a novel regularization term designed for Pruning NNs. We commence by presenting a mathematical representation of the pruning problem, followed by a stronger reformulation achieved through the perspective function. Through algebraic simplification, we ultimately derive the conclusive expression for the SPR. This term, when incorporated into the loss function during training, facilitates the attainment of sparse architectures. We empirically validate the effectiveness of this technique through its application to filter pruning, using the most common Convolutional architectures and CIFAR and Imagenet datasets. Next, we shift our focus to the realm of Quantization. This technique has seen a significant surge in adoption by practitioners in recent years, though its underlying principles remain elusive. We conduct a convergence analysis of NN training concerning low-bit floating-point architectures. Our investigation yields the establishment of new bounds on loss degradation, which directly depends on the number of bits used to represent the NN weights and to perform the operations required in the forward and backward pass. Finally, we empirically validate the correctness of our results by minimizing artificially perturbed functions as well as training elementary NN architectures on the MNIST dataset. Lastly, we shed light on the advantages of Pruning within the domain of Constraint Learning (CL). A pioneering aspect of our work is the empirical demonstration that applying structured pruning to a model intended for integration into a Mixed Integer Programming (MIP) model leads to a massive reduction in the necessary solving time. Employing the pruning technique we established in the initial chapter of this thesis, we proceed to compress feed-forward NNs before addressing an Adversarial Example Search problem. The outcomes of this application are unequivocal, a drastic reduction in solution times is evident. Furthermore, the results indicate that Pruning does not compromise solution quality within our specific context.

Résumé

Dans de nombreux scénarios exigeant des prévisions basées sur les données, les modèles d’Apprentissage Automatique (ML) atteignent constamment les performances de l’état de l’art. À noter en particulier, les Réseaux des Neurones (NNs), qui ont affirmé leur domination ces dernières années dans des domaines divers tels que la Vision par Ordinateur et le Traitement automatique du Langage Naturel. La précision des prédictions des nouveaux modèles NN s’améliore chaque année, bien que cela s’accompagne d’un compromis en termes de tailles d’architectures plus importantes. Cela se traduit par une augmentation des besoins en stockage mémoire et en puissance de calcul pour la formation et l’exécution des modèles. Le nombre substantiel de paramètres dans les architectures NN récentes a nécessité le développement de techniques de Compression de Modèles (MC). Ces techniques visent à réduire les ressources nécessaires à un modèle tout en préservant son intégrité en matière de performance. Dans ce contexte, l’utilisation de techniques de Recherche Opérationnelle (OR) semble très appropriée. La formulation inhérente du problème de haut niveau consiste à minimiser les ressources requises par le modèle tout en préservant une précision assez proche de la precision du modèle. Cela ouvre naturellement la voie à diverses approches potentielles de OR pour formuler mathématiquement une solution à ce défi. En outre, une grande partie des techniques existantes dans la littérature sur la MC ne propose pas de méthodologies dont la base théorique est suffisamment solide, mais plutôt des méthodologies simplistes qui reposent sur un raisonnement heuristique. Par ailleurs, la compréhension présente dans la littérature des mécanismes sous-jacents responsables de l’efficacité de certaines algorithmes de MC et de leurs principes opérationnels demeure restreinte. L’objectif principal de cette thèse est de formuler et de développer des méthodologies de MC qui exploitent les techniques de Recherche Opérationnelle, qui possèdent des bases théoriques solides, et qui contribuent à découvrir les principes directeurs de ce domaine. Dans un premier temps, nous introduisons le SPR, un nouveau terme de régularisation conçu pour l’élagage des NNs. Nous commençons par présenter une représentation mathématique du problème d’élagage, suivie d’une reformulation plus solide obtenue grâce à la fonction de perspective. Par simplification algébrique, nous dérivons finalement l’expression conclusive du SPR. Ce terme, lorsqu’il est incorporé dans la fonction de perte pendant la formation, facilite l’obtention d’architectures creuses. Nous validons empiriquement l’efficacité de cette technique en l’appliquant à l’élagage de filtres, en utilisant les architectures de convolution les plus courantes et les ensembles de données CIFAR et Imagenet.Ensuite, nous nous tournons vers le domaine de la Quantification. Cette technique a connu une augmentation significative de son adoption par les praticiens ces dernières années, bien que ses principes sous-jacents restent insaisissables. Nous menons une analyse de convergence de l’entraînement de NN concernant les architectures en virgule flottante à faible nombre de bits. Notre enquête conduit à l’établissement de nouvelles limites en matière de dégradation de la perte, qui dépendent directement du nombre de bits utilisés pour représenter les poids du NN et pour effectuer les opérations requises lors de la passe avant et arrière. Enfin, nous validons empiriquement la exactitude de nos résultats en minimisant des fonctions artificiellement perturbées ainsi qu’en entraînant des architectures de NN élémentaires sur l’ensemble de données MNIST. Dans un dernier temps, nous mettons en lumière les avantages de l’élagage dans le domaine de l’Apprentissage par Contraintes (CL). Un aspect novateur de notre travail est la démonstration empirique que l’application de l’élagage structuré à un modèle destiné à être intégré dans un Programme Entier Mixte (MIP) conduit à une réduction exponentielle du temps de résolution nécessaire. En utilisant la technique d’élagage que nous avons établie dans la première section de cette thèse, nous procédons à la compression de NNs à propagation avant puis nous abordons un traitement du problème de recherche d’exemples adversaires. Les résultats de cette application sont sans équivoque, une réduction drastique des temps de résolution est évidente. D’ailleurs, les résultats indiquent clairement que l’élagage ne détériore pas la qualité de la solution dans notre contexte spécifique.

Department: Department of Mathematics and Industrial Engineering
Program: Mathématiques
Academic/Research Directors: Dominique Orban, Andrea Lodi and Antonio Frangioni
PolyPublie URL: https://publications.polymtl.ca/56771/
Institution: Polytechnique Montréal
Date Deposited: 19 Dec 2023 15:33
Last Modified: 05 May 2024 14:40
Cite in APA 7: Cacciola, M. (2023). Operations Research Techniques for Neural Network Compression [Ph.D. thesis, Polytechnique Montréal]. PolyPublie. https://publications.polymtl.ca/56771/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item