Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ces travaux portent sur l'optimisation de structures stratifiées en utilisant un algorithme génétique. Un programme d'optimisation est développé et est ensuite appliqué à la résolution d'une série de problèmes d'optimisation pour lesquels les variables de design peuvent appartenir soit à un domaine discret soit à un domaine continu. Tout d'abord, il est question de problèmes où le nombre de plis, le matériau et l'épaisseur des plis sont fixés. Les variables de design sont alors l'orientation de chaque pli qui peut prendre, dans un premier cas, des valeurs discrètes (0ʻ, ł45ʻ, 90ʻ) puis des valeurs continues (de 0ʻ à 90ʻ). Deuxièmement, il est question de problèmes pour lesquels le nombre de plis et le matériau des plis deviennent des variables de design qui s'ajoutent alors à l'orientation des plis. Dans ces cas, la valeur des variables de design (matériaux et orientations) est choisie dans une liste de valeurs. / L'objectif de ces problèmes est, en premier lieu, la minimisation du poids ou du coût de la structure sous différentes contraintes et finalement, la minimisation du poids et du coût simultanément avec une formulation multi-objectifs. L'algorithme génétique développé utilise une stratégie multi-élitiste et empêche la présence d'individus identiques dans la population. Finalement, un algorithme génétique hybride, combinant l'algorithme génétique et une recherche locale, est développé et ensuite testé sur ces mêmes problèmes. Cette hybridation de l'algorithme résulte en une diminution du temps de calcul exigé et en une amélioration substantielle des résultats.

En tant qu'algorithmes d'apprentissage automatique à la pointe de la technologie, les réseaux de neurones profonds nécessitent de nombreux exemples pour bien fonctionner sur une tâche d'apprentissage. La collecte et l'annotation de multiples échantillons nécessitent un travail humain important et c'est même impossible dans la plupart des problèmes du monde réel tel que l'analyse de données biomédicales. Dans le contexte de la vision par ordinateur, la classification d'images à quelques plans vise à saisir la capacité humaine à apprendre de nouveaux concepts avec peu de supervision. À cet égard, l'idée générale est de transférer les connaissances des catégories de base avec plus d'encadrement vers des classes nouvelles avec peu d'exemples. En particulier, les approches actuelles d'apprentissage à quelques coups pré entraînent un modèle sur les classes de base disponible pour généraliser aux nouvelles classes, peut-être avec un réglage fin. Cependant, la généralisation du modèle actuel est limitée en raison de certaines hypothèses lors de la préformation et de restrictions lors de l'étape de mise au point. Cette thèse vise à assouplir trois hypothèses des modèles d'apprentissage à quelques plans actuels et nous proposons un apprentissage de représentation pour la classification d'images à quelques plans. Tout d'abord, le gel d'un modèle préformé semble inévitable dans la phase de réglage fin en raison de la forte possibilité de surentraînement sur quelques exemples. Malheureusement, l'apprentissage par transfert avec une hypothèse de modèle gelé limite la capacité du modèle puisque le modèle n'est pas mis à jour avec aucune connaissance des nouvelles classes. Contrairement au gel d'un modèle, nous proposons un alignement associatif qui permet d'affiner et de mettre à jour le réseau sur de nouvelles catégories. Plus précisément, nous présentons deux stratégies qui détectent et alignent les nouvelles classes sur les catégories de base hautement liées. Alors que la première stratégie pousse la distribution des nouvelles classes au centre de leurs catégories de base associées, la seconde stratégie effectue une correspondance de distribution à l'aide d'un algorithme d'entraînement contradictoire. Dans l'ensemble, notre alignement associatif vise à éviter le surentraînement et à augmenter la capacité du modèle en affinant le modèle à l'aide de nouveaux exemples et d'échantillons de base associés. Deuxièmement, les approches actuelles d'apprentissage à quelques coups effectuent le transfert de connaissances vers de nouvelles classes distinctes sous l'hypothèse uni modale, où tous les exemples d'une seule classe sont représentés par un seul cluster. Au lieu de cela, nous proposons une approche d'apprentissage de l'espace des caractéristiques basée sur le mélange (MixtFSL) pour déduire une représentation multimodale. Alors qu'un précédent travail basé sur un modèle de mélange d'Allen et al. citeallen2019infinite est basé sur une méthode de clusters classique de manière non différentielle, notre MixtFSL est un nouveau modèle multimodale de bout en bout et entièrement différentielle. MixtFSL capture la multimodale des classes de base sans aucun algorithme de clusters classique à l'aide d'un cadre en deux étapes. La première phase s'appeler formation initiale et vise à apprendre la représentation préliminaire du mélange avec une paire de fonctions de perte. Ensuite, l'étape suivante progressive, la deuxième étape, stabilise la formation avec un cadre de formation de type enseignant-élève utilisant une fonction de perte unique. Troisièmement, contrairement aux techniques actuelles à quelques prises de vue consistant à représenter chaque exemple d'entrée avec une seule entité à la fin du réseau, nous proposons un extracteur d'entités d'ensemble et des ensembles d'entités correspondantes qui assouplissent l'hypothèse typique basée sur une seule entité en raisonnant sur des ensembles d'entités. Ici, nous émettons l'hypothèse que l'hypothèse d'une seule caractéristique est problématique dans la classification d'images à quelques prises de vue puisque les nouvelles classes sont différentes des classes de base préformées. À cette fin, nous proposons nouvel extracteur de caractéristiques d'ensemble d'apprentissage profond basé sur les réseaux de neurones hybrides convolution-attention. De plus, nous suggérons trois métriques ensemble à ensemble non paramétriques pour séduire la classe de l'entrée donnée. Cette thèse utilise plusieurs indicateurs standards publiés dans la littérature sur l'apprentissage en peu d'exemples et l'ossature de réseau pour évaluer les méthodes que nous proposons. / As the current state-of-the-art machine learning algorithms, deep neural networks require many examples to perform well on a learning task. Gathering and annotating many samples requires significant human labor, and it is even impossible in most real-world problems such as biomedical data analysis. Under the computer vision context, few-shot image classification aims at grasping the human ability to learn new concepts with little supervision. In this respect, the general idea is to transfer knowledge from base categories with more supervision to novel classes with few examples. In particular, the current few-shot learning approaches pre-train a model on available base classes to generalize to the novel classes, perhaps with fine-tuning. However, the current model's generalization is limited because of some assumptions in the pre-training and restrictions in the fine-tuning stage. This thesis aims to relax three assumptions of the current few-shot learning models, and we propose representation learning for few-shot image classification. First, freezing a pre-trained model looks inevitable in the fine-tuning stage due to the high possibility of overfitting on a few examples. Unfortunately, transfer learning with a frozen model assumption limits the model capacity since the model is not updated with any knowledge of the novel classes. In contrast to freezing a model, we propose associative alignment that enables fine-tuning and updating the network on novel categories. Specifically, we present two strategies that detect and align the novel classes to the highly related base categories. While the first strategy pushes the distribution of the novel classes to the center of their related base categories, the second strategy performs distribution matching using an adversarial training algorithm. Overall, our associative alignment aims to prevent overfitting and increase the model capacity by refining the model using novel examples and related base samples. Second, the current few-shot learning approaches perform transferring knowledge to distinctive novel classes under the uni-modal assumption, where all the examples of a single class are represented with a single cluster. Instead, we propose a mixture-based feature space learning (MixtFSL) approach to infer a multi-modal representation. While a previous mixture-model-based work of Allen et al. [1] is based on a classical clustering method in a non-differentiable manner, our MixtFSL is a new end-to-end multi-modal and fully differentiable model. MixtFSL captures the multi-modality of base classes without any classical clustering algorithm using a two-stage framework. The first phase is called initial training and aims to learn preliminary mixture representation with a pair of loss functions. Then, the progressive following stage, the second stage, stabilizes the training with a teacher-student kind of training framework using a single loss function. Third, unlike the current few-shot techniques of representing each input example with a single feature at the end of the network, we propose a set feature extractor and matching feature sets that relax the typical single feature-based assumption by reasoning on feature sets. Here, we hypothesize that the single feature assumption is problematic in few-shot image classification since the novel classes are different from pre-trained base classes. To this end, we propose a new deep learning set feature extractor based on the hybrid convolution-attention neural networks. Additionally, we offer three non-parametric set-to-set metrics to infer the class of the given input. This thesis employs several standard benchmarks of few-shot learning literature and network backbones to evaluate our proposed methods.

Dans le domaine de la classification, les algorithmes d'apprentissage par compression d'échantillons sont des algorithmes qui utilisent les données d'apprentissage disponibles pour construire l'ensemble de classificateurs possibles. Si les données appartiennent seulement à un petit sous-espace de l'espace de toutes les données «possibles», ces algorithmes possédent l'intéressante capacité de ne considérer que les classificateurs qui permettent de distinguer les exemples qui appartiennent à notre domaine d'intérêt. Ceci contraste avec d'autres algorithmes qui doivent considérer l'ensemble des classificateurs avant d'examiner les données d'entraînement. La machine à vecteurs de support (le SVM) est un algorithme d'apprentissage très performant qui peut être considéré comme un algorithme d'apprentissage par compression d'échantillons. Malgré son succès, le SVM est actuellement limité par le fait que sa fonction de similarité doit être un noyau symétrique semi-défini positif. Cette limitation rend le SVM difficilement applicable au cas où on désire utiliser une mesure de similarité quelconque. / In classification, sample compression algorithms are the algorithms that make use of the available training data to construct the set of possible predictors. If the data belongs to only a small subspace of the space of all "possible" data, such algorithms have the interesting ability of considering only the predictors that distinguish examples in our areas of interest. This is in contrast with non sample compressed algorithms which have to consider the set of predictors before seeing the training data. The Support Vector Machine (SVM) is a very successful learning algorithm that can be considered as a sample-compression learning algorithm. Despite its success, the SVM is currently limited by the fact that its similarity function must be a symmetric positive semi-definite kernel. This limitation by design makes SVM hardly applicable for the cases where one would like to be able to use any similarity measure of input example. PAC-Bayesian theory has been shown to be a good starting point for designing learning algorithms. In this thesis, we propose a PAC-Bayes sample-compression approach to kernel methods that can accommodate any bounded similarity function. We show that the support vector classifier is actually a particular case of sample-compressed classifiers known as majority votes of sample-compressed classifiers. We propose two different groups of PAC-Bayesian risk bounds for majority votes of sample-compressed classifiers. The first group of proposed bounds depends on the KL divergence between the prior and the posterior over the set of sample-compressed classifiers. The second group of proposed bounds has the unusual property of having no KL divergence when the posterior is aligned with the prior in some precise way that we define later in this thesis. Finally, for each bound, we provide a new learning algorithm that consists of finding the predictor that minimizes the bound. The computation times of these algorithms are comparable with algorithms like the SVM. We also empirically show that the proposed algorithms are very competitive with the SVM.

La programmation linéaire permet d’effectuer l’optimisation de la gestion des réseaux de création de valeur. Dans la pratique, la taille de ces problèmes demande l’utilisation d’un ordinateur pour effectuer les calculs nécessaires, et l’algorithme du simplexe, entre autres, permet d’accomplir cette tâche. Ces solutions sont cependant construites sur des modèles approximatifs et l’humain est généralement méfiant envers les solutions sorties de « boîtes noires ». Les systèmes à initiative partagée permettent une synergie entre, d’une part, l’intuition et l’expérience d’un décideur humain et, d’autre part, la puissance de calcul de l’ordinateur. Des travaux précédents au sein du FORAC ont permis l’application de cette approche à la planification tactique des opérations des réseaux de création de valeur. L’approche permettrait l’obtention de solutions mieux acceptées. Elle a cependant une interface utilisateur limitée et contraint les solutions obtenues à un sous-espace de l’ensemble des solutions strictement optimales. Dans le cadre de ce mémoire, les principes de conception d’interface humain-machine sont appliqués pour concevoir une interface graphique plus adaptée à l’utilisateur type du système. Une interface basée sur le modèle de présentation de données de l’outil Logilab, à laquelle sont intégrées les interactivités proposées par Hamel et al. est présentée. Ensuite, afin de permettre à l’expérience et à l’intuition du décideur humain de compenser les approximations faites lors de la modélisation du réseau de création de valeur sous forme de problème linéaire, une tolérance quant à l’optimalité des solutions est introduite pour la recherche interactive de solutions alternatives. On trouvera un nouvel algorithme d’indexation des solutions à combiner et une nouvelle heuristique de combinaison convexe pour permettre cette flexibilité. Afin d‘augmenter la couverture de l’espace solutions accessible au décideur humain, un algorithme de recherche interactive de solution basé sur le simplexe est introduit. Cet algorithme présente une stabilité similaire à la méthode de Hamel et al., mais ses performances en temps de calcul sont trop basses pour offrir une interactivité en temps réel sur de vrais cas industriels avec les ordinateurs présentement disponibles.Une seconde approche d’indexation complète de l’espace solutions est proposée afin de réduire les temps de calcul. Les nouveaux algorithmes « Linear Redundancyless Recursive Research » (Recherche linéaire récursive sans redondance, LRRR) pour la cartographie et l’indexation de l’espace solutions et « N-Dimension Navigation Direction » (direction de navigation à n-dimensions, NDND) pour l’exploration interactive de celui-ci sont présentés. Ces algorithmes sont justes et rapides, mais ont cependant un coût mémoire au-delà de la capacité des ordinateurs contemporains. Finalement, d’autres pistes d’exploration sont présentées, notamment l’exploitation des méthodes du point intérieur et de l’algorithme de Karmarkar ainsi qu’une ébauche d’approche géométrique.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / Les systèmes de surveillance vidéo comme méthode de prévention et de protection connaissent une popularité grandissante. Cependant, des études tendent à démontrer que le placement des caméras est généralement inadéquat, se soldant en des systèmes à efficacité limitée. Ce mémoire propose une méthode permettant le placement automatique d'un nombre variable de caméras dans un environnement arbitraire en vue d'en optimiser le coût et la performance. Nous développons une formulation de la problématique pouvant servir à l'expression générale de plusieurs problèmes de placement de caméras. Les problèmes sont résolus grâce à un algorithme évolutionnaire, utilisant une représentation à taille variable, qui produit en sortie un ensemble de solutions exprimant les compromis possibles entre le coût et la performance. L'analyse qualitative des solutions est réalisée à l'aide de trois paradigmes de visualisation développée pour ce projet. Nous analysons trois problèmes concrets résolus par l'algorithme.

Dans le cadre de l'apprentissage automatique supervisé, un des outils disponibles pour la classification binaire est la Set Covering Machine (SCM). Rapidement construite et en général très performante, elle n'est cependant pas systématiquement infaillible. Il existe encore, à ce jour, une marge pour une amélioration. Ce mémoire présente deux nouvelles façons de construire des SCM. Ces algorithmes sont décrits, expliqués et leur performance est analysée. La première façon est de minimiser une approximation d'une borne sur le risque à l'aide d'un branch-and-bound. La deuxième est d'utiliser le bagging. Lors des tests, les nouveaux classificateurs se sont montrés aussi performants que les SCM originales. Nous avons découvert que celles-ci sont soit déjà optimales au sens du critère utilisé pour le branch-and-bound, soit aussi performantes que les SCM optimales. / In the supervised machine learning field, one of the available tools for binary classification is the Set Covering Machine (SCM). Quickly built and generally having high performance, it's however not proven that they always give optimal results. There is still, to date, a margin for improvement. This study presents two new ways of building SCM. Theses algorithms are described, explained and their performance is analyzed. The first way is to minimize an approximated bound on the risk with a branch-and-bound. The second is using bagging. The new classifiers had the same test-set performance than the original SCM. We discovered that the latter are either already optimal according to the branch-and-bound criterion or having the same performance as the optimal SCM.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2016 / Ce mémoire présente deux algorithmes qui ont pour but d’améliorer la précision de l’estimation de la direction d’arrivée de sources sonores et de leurs échos. Le premier algorithme, qui s’appelle la méthode par élimination des sources, permet d’améliorer l’estimation de la direction d’arrivée d’échos qui sont noyés dans le bruit. Le second, qui s’appelle Multiple Signal Classification à focalisation de phase, utilise l’information dans la phase à chaque fréquence pour déterminer la direction d’arrivée de sources à large bande. La combinaison de ces deux algorithmes permet de localiser des échos dont la puissance est de -17 dB par rapport à la source principale, jusqu’à un rapport échoà- bruit de -15 dB. Ce mémoire présente aussi des mesures expérimentales qui viennent confirmer les résultats obtenus lors de simulations. / This memoir presents two algorithms which goal is to determine the direction of arrival of wideband acoustic sources. The first algorithm, called Source Elimination Method, eliminate the contribution of every source from the covariance matrix to improve the estimation of the direction of arrival estimate of echoes in a low echo-to-noise ratio. The second algorithm, called Multiple Signal Classification with Phase Focalisation, uses the information contained in the phase of every frequency to find the direction of arrival of wideband sources. The combination of the two algorithm permits to find the direction of arrival of two echoes, which power is - 17 dB compared to the main source, up to an echo to noise ratio of -15 dB. Experimental results confirming the precision of these algorithm are presented.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / L’objet principale de cette thèse est l’étude théorique et la conception d’algorithmes d’apprentissage concevant des classificateurs par vote de majorité. En particulier, nous présentons un théorème PAC-Bayes s’appliquant pour borner, entre autres, la variance de la perte de Gibbs (en plus de son espérance). Nous déduisons de ce théorème une borne du risque du vote de majorité plus serrée que la fameuse borne basée sur le risque de Gibbs. Nous présentons également un théorème permettant de borner le risque associé à des fonctions de perte générale. À partir de ce théorème, nous concevons des algorithmes d’apprentissage construisant des classificateurs par vote de majorité pondérés par une distribution minimisant une borne sur les risques associés aux fonctions de perte linéaire, quadratique, exponentielle, ainsi qu’à la fonction de perte du classificateur de Gibbs à piges multiples. Certains de ces algorithmes se comparent favorablement avec AdaBoost. / The main purpose of this thesis is the theoretical study and the design of learning algorithms returning majority-vote classifiers. In particular, we present a PAC-Bayes theorem allowing us to bound the variance of the Gibbs’ loss (not only its expectation). We deduce from this theorem a bound on the risk of a majority vote tighter than the famous bound based on the Gibbs’ risk. We also present a theorem that allows to bound the risk associated with general loss functions. From this theorem, we design learning algorithms building weighted majority vote classifiers minimizing a bound on the risk associated with the following loss functions : linear, quadratic and exponential. Also, we present algorithms based on the randomized majority vote. Some of these algorithms compare favorably with AdaBoost.

Les problèmes de satisfaction de contraintes sont parmi les problèmes fréquents qu'on trouve dans des domaines variés tels que la recherche opérationnelle et l'intelligence artificielle. Dans un problème de satisfaction de contraintes, on cherche à assigner aux variables des valeurs de telle sorte que toutes les contraintes fournies en entrée soient satisfaites. Chaque contrainte est une paire contenant un tuple de variables et une relation définissant les combinaisons de valeurs autorisées pour ce tuple. Ce problème est NP-complet, donc il est important d'identifier des cas particuliers résolubles en temps polynomial. Dans ce travail, on s'intéresse à une approche dite algébrique pour découvrir des classes de problèmes de satisfaction de contraintes traitables efficacement. On se base sur le résultat prouvé par Dalmau "en 2006" qui donne un algorithme polynomial pour une classe assez vaste de problèmes. On analyse et implémente un cas particulier de cet algorithme qui permet de résoudre des instances de 2-SAT. Cette implementation nous aidera à faire des expérimentations et à en apprendre plus sur la nature de l'algorithme de Dalmau et son comportement en pratique.