Ce mémoire présente une brève introduction aux fonctions de hachage : les principales fonctions de hachage utilisées ainsi que leurs principales utilisations. Une nouvelle fonction de hachage, développée par Yong Wang , Xiaofeng Liao, Di Xao et Kwok-Wo Wong [1], sera introduite et une modification de cette dernière sera proposée. Cette fonction de hachage est basée sur un système dynamique chaotique, ce qui conduit à l'étude des exposants de Lyapunov.

Dans ce mémoire de maîtrise, nous présentons dans un premier temps un algorithme de l'état de l'art appelé Forêts aléatoires introduit par Léo Breiman. Cet algorithme effectue un vote de majorité uniforme d'arbres de décision construits en utilisant l'algorithme CART sans élagage. Par après, nous introduisons l'algorithme que nous avons nommé SORF. L'algorithme SORF s'inspire de l'approche PAC-Bayes, qui pour minimiser le risque du classificateur de Bayes, minimise le risque du classificateur de Gibbs avec un régularisateur. Le risque du classificateur de Gibbs constitue en effet, une fonction convexe bornant supérieurement le risque du classificateur de Bayes. Pour chercher la distribution qui pourrait être optimale, l'algorithme SORF se réduit à être un simple programme quadratique minimisant le risque quadratique de Gibbs pour chercher une distribution Q sur les classificateurs de base qui sont des arbres de la forêt. Les résultasts empiriques montrent que généralement SORF est presqu'aussi bien performant que les forêts aléatoires, et que dans certains cas, il peut même mieux performer que les forêts aléatoires. / In this master's thesis, we present at first an algorithm of the state of the art called Random Forests introduced by Léo Breiman. This algorithm construct a uniformly weighted majority vote of decision trees built using the CART algorithm without pruning. Thereafter, we introduce an algorithm that we called SORF. The SORF algorithm is based on the PAC-Bayes approach, which in order to minimize the risk of Bayes classifier, minimizes the risk of the Gibbs classifier with a regularizer. The risk of Gibbs classifier is indeed a convex function which is an upper bound of the risk of Bayes classifier. To find the distribution that would be optimal, the SORF algorithm is reduced to being a simple quadratic program minimizing the quadratic risk of Gibbs classifier to seek a distribution Q of base classifiers which are trees of the forest. Empirical results show that generally SORF is almost as efficient as Random forests, and in some cases, it can even outperform Random forests.

Un des défis de la radiothérapie externe est d’adapter la planification de traitement à l’anatomie du patient tout au long de son traitement. Il est possible de faire de la thérapie adaptative grâce à l’imagerie de repositionnement en utilisant des algorithmes de recalage d’image. Les contours et la planification peuvent être conformes à l’anatomie du jour des patients au moment de leur fraction quotidienne. Il faut s’assurer préalablement de l’efficacité et la constance de ces algorithmes. Il est plus simple d’isoler des déformations spécifiques avec un fantôme anthropomorphique tridimensionnel que sur des images de patients. Le fantôme construit dans cette étude a permis de construire une banque d’images montrant 7 déformations différentes en intra et intermodalité Cette étude montre l’utilité du fantôme dans la validation et ainsi que l’efficacité de deux algorithmes de recalage d’image. Cette validation permet de cerner les lacunes de cette technologie pour éventuellement l’utiliser en clinique.

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.

SpIOMM, le Spectromètre imageur à transformée de Fourier de l’Observatoire du Mont-Mégantic génère des fichiers de taille imposante, de l’ordre de 700 Mo et SITELLE, son successeur génèrera des fichiers de l’ordre du Go. Puisque plusieurs fichiers peuvent être générés durant une nuit d’observation et que les astronomes ne sont pas toujours sur place pour effectuer leurs observations, ces fichiers apportent à la fois des besoins de stockage et de transfert de données. Afin de minimiser l’espace nécessaire à son stockage et de minimiser la bande passante et le temps de transfert nécessaire pour obtenir le fichier à distance, trois techniques de compression sont abordées. Les deux premières sont des techniques de compression sans perte et la troisième en est une avec perte. Les deux premières permettent d’obtenir de meilleurs taux de compression que les algorithmes génériques que sont zip et gzip2, avec des taux de compression de l’ordre de 1; 19 : 1 à 1; 22 : 1. La troisième permet des taux de compression allant jusqu’à un ratio de 64 : 1. Les effets des perte sont étudiés pour évaluer l’effet de la compression sur les mesures de photométrie et les analyses basées sur les spectres. / SpIOMM, the Imaging Fourier Transform Spectrometer of the Observatoire du Mont-Mégantic generates huge files of about 700 MB per file on average, and SITELLE, its successor will generate files of a few GB. Since several files can be generated during an observation night and the astronomers are not always on-site, there is an increasing need for both storage and transmission. To minimize storage space, bandwidth use and transmission time, three data compression techniques are presented. The first two techniques are lossless data compression and the third one is lossy. The lossless techniques give better results than generic techniques that are zip and gzip2, with compression ratios varying from 1:19 : 1 to 1:22 : 1. The lossy technique compresses files up to a 64 : 1 ratio. The effect of the lossy process on the photometric measurements and the spectra analysis is also studied.

La capacité d'un ensemble est une notion qui, bien que très fortement motivée par la physique, intervient naturellement dans de très nombreuses branches de l'analyse mathématique, comme l'analyse complexe, la théorie du potentiel et des équations aux dérivées partielles ou dans l'approximation rationnelle. Cette thèse se concentre sur les capacités définies par des intégrales à noyaux. Le premier chapitre se veut un bref rappel des concepts fondamentaux en théorie du potentiel ainsi que des outils nécessaires pour la suite de cette thèse. Les deuxième et troisième chapitres de la thèse énoncent les principes des algorithmes de calcul de la capacité dans les cas généraux et pondérés respectivement et contiennent également des preuves rigoureuses de convergence desdits algorithmes. Le quatrième et dernier chapitre de la thèse énonce quelques versions modifiées des méthodes de calculs de la capacité et contient de nombreux exemples illustrés par des tableaux et des graphiques. On y remarque également que les moyens mis en oeuvre pour approximer la capacité permettent d'estimer le support et le potentiel à l'équilibre.

Ce mémoire traite de la résolution de problèmes d’ordonnancement à l’aide de la programmation par contraintes. Il s’intéresse principalement aux contraintes globales et particulièrement à la contrainte cumulative. Il passe en revue les règles permettant de la filtrer et les principaux algorithmes qui les appliquent. Il explique le Edge-Finder de Vilím et son arbre cumulatif. Il propose un algorithme plus performant et plus général pour appliquer les règles découlant du raisonnement énergétique. Le mémoire traite du cas particulier où toutes les tâches sont de durée identique. Pour modéliser efficacement ce type de problèmes, on y conçoit la contrainte multi-inter-distance. L’algorithme d’ordonnancement de López-Ortiz et Quimper est adapté pour réaliser un algorithme qui applique la cohérence de bornes. La contrainte multi-inter-distance s’avère efficace à résoudre le problème de séquençage des atterrissages d’avions du banc d’essai d’Artiouchine et Baptiste. / This thesis discusses how to solve scheduling problems using constraint programming. We study global constraints and particularly the Cumulative constraint. We survey its main filtering rules and their state-of-the-art filtering algorithms. We explain the Vilím’s Edge-Finder and its cumulative tree.We introduce a more efficient and more general algorithm that enforces the filtering rules from the energetic reasoning. We study the special case where all tasks have identical processing times. To efficiently model such problems, we introduce the Multi-Inter-Distance constraint. The scheduling algorithm by López-Ortiz and Quimper is adapted to produce a filtering algorithm enforcing bounds consistency. The constraint Multi-Inter-Distance is proved efficient to solve the runway scheduling problem on the benchmark by Artiouchine and Baptiste.

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.

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.