Training Neural Networks to Perform Structured Prediction Task

Malgré leurs nombreux succès sur diverses tâches complexes, les réseaux de neurones profonds ont encore du mal à apprendre la structure combinatoire, où de multiples sorties discrètes ont des relations interconnectées régies par des contraintes. Ceci est particulièrement vrai lorsqu’il n’y a pas suffisamment de données pour que le modèle apprenne la structure de sortie. La programmation par contraintes, un type d’algorithme non-apprenant, se concentre sur la structure. Elle a un passé développé et couronné de succès dans la reconnaissance de structures combinatoires qui reviennent fréquemment, et dans le développement d’algorithmes avancés pour extraire des informations de ces structures. En particulier, nous nous intéressons à la fréquence relative d’une affectation donnée variable-valeur dans cette structure combinatoire. Le cadre de programmation par contraintes avec propagation de croyance généralise ce modèle en propageant ces fréquences relatives issues d’un modèle de programmation par contraintes pour approximer les fonctions de masse de probabilité marginales de chaque variable. Ces probabilités marginales estimées sont utilisées comme pénalités au sein de la fonction de perte, améliorant l’apprentissage et l’efficacité du réseau neuronal à partir des échantillons. Dans ce mémoire, nous proposons de former un réseau de neurones pour générer une sortie qui s’aligne sur une structure combinatoire exprimée comme un modèle de programmation par contraintes. Ceci est réalisé en calculant une fonction de perte qui inclut les marginales déterminées par la programmation par contraintes avec un solveur de propagation de croyance. Nous soutenons que ce modèle offre une intégration plus naturelle de la programmation par contraintes et des réseaux neuronaux. Nous apportons des preuves pratiques que la formation du modèle en utilisant cette approche améliore considérablement ses performances, surtout lorsqu’il existe une quantité limitée de données disponibles. Nos résultats sur le problème du Carré Latin Partiel indiquent une amélioration constante de la précision du modèle par rapport aux méthodes existantes.

Abstract

Despite their numerous successes on various challenging tasks, deep neural networks still struggle to learn combinatorial structure, where multiple discrete outputs have interconnected relationships governed by constraints, especially when there is not enough data for the model to learn the output structure. Constraint programming, a type of non-learning algorithm, focuses on structure. It has a developed and successful past in recognizing combinatorial structures that frequently recur, and in developing advanced algorithms to extract information from these structures. In particular, we are interested in the relative frequency of a given variable-value assignment in that combinatorial structure. The constraint programming with belief propagation framework generalizes this model by propagating these relative frequencies from a constraint programming model to approximate the marginal probability mass functions of each variable. These estimated marginal probabilities are used as penalties within the loss function, improving the neural network’s learning and efficiency from samples. In this thesis, we propose to train a neural network to generate output that aligns with a combinatorial structure expressed as a constraint programming model. This is achieved by calculating a loss function that includes marginals determined by constraint programming with a belief propagation solver. We argue that this model offers a more natural integration of constraint programming and neural networks. We offer practical evidence that training the model using this approach significantly enhances its performance, especially when there is a limited amount of data available. Our results on the Partial Latin Square problem indicate consistent improvement in the accuracy of the model over the existing methods.