La prise de décision dans un environnement partiellement observable est un sujet d'actualité en intelligence artificielle. Une façon d'aborder ce type de problème est d'utiliser un modèle mathématique. Notamment, les POMDPs (Partially Observable Markov Decision Process) ont fait l'objet de plusieurs recherches au cours des dernières années. Par contre, résoudre un POMDP est un problème très complexe et pour cette raison, le modèle n'a pas été utilisé abondamment. Notre objectif était de continuer les progrès ayant été réalisé lors des dernières années, avec l'espoir que nos travaux de recherches seront un pas de plus vers l'application des POMDPs dans des applications d'envergures. Dans un premier temps, nous avons développé un nouvel algorithme hors-ligne qui, sur des problèmes tests, est plus performant que les meilleurs algorithmes existants. La principale innovation vient du fait qu'il s'agit d'un algorithme stochastique alors que les algorithmes traditionnels sont déterministes. Dans un deuxième temps, nous pouvons également appliquer cet algorithme dans des environnements en-lignes. Lorsque ceux-ci revêtent une certaine particularité, notre algorithme est beaucoup plus performant que la compétition. Finalement, nous avons appliqué une version simplifiée de notre algorithme dans le cadre du projet Combat Identification du RDDC-Valcartier. / Decision making under uncertainty is a popular topic in the field of artificial intelligence. One popular way to attack such problems is by using a sound mathematical model. Notably, Partially Observable Markov Processes (POMDPs) have been the subject of extended researches over the last ten years or so. However, solving a POMDP is a very time-consuming task and for this reason, the model has not been used extensively. Our objective was to continue the tremendous progress that has been made over the last couple of years, with the hope that our work will be a step toward applying POMDPs in large-scale problems. To do so, we combined different ideas in order to produce a new algorithm called SSVI (Stochastic Search Value Iteration). Three major accomplishments were achieved throughout this research work. Firstly, we developed a new offline POMDP algorithm which, on benchmark problems, proved to be more efficient than state of the arts algorithm. The originality of our method comes from the fact that it is a stochastic algorithm, in comparison with the usual determinist algorithms. Secondly, the algorithm we developed can also be applied in a particular type of online environments, in which this algorithm outperforms by a significant margin the competition. Finally, we also applied a basic version of our algorithm in a complex military simulation in the context of the Combat Identification project from DRDC-Valcartier.

Ce mémoire présente une nouvelle méthode d'analyse des courbes de voltampérométrie cyclique. Cette méthode utilise deux algorithmes distincts afin de permettre la caractérisation automatique et précise des pics gaussiens d'oxydoréduction qui sont liés à la concentration des molécules en solution. En premier lieu, des améliorations significatives sont apportées à un algorithme de suppression de la courbe de fond qui fonctionne par approximation polynomiale itérative. Avec les améliorations proposées, l'algorithme isole les pics d'oxydoréduction à partir des mesures de voltampérométrie cyclique automatiquement. La variation de l'amplitude des pics en fonction de la concentration est alors mieux conservée et les erreurs d'estimation sont diminuées par rapport à l'algorithme initial. Ensuite, le développement d'un algorithme qui permet de caractériser des pics gaussiens basé sur l'algorithme de deuxième ordre MUSIC est présenté. Cet algorithme est adapté de manière à caractériser avec une haute précision le nombre, la position, la largeur et l'amplitude des pics d'oxydoréduction. Finalement, les performances de cet algorithme sont comparées à celles d'autres algorithmes similaires à l'aide de courbes simulées et expérimentales. L'algorithme proposé permet une meilleure caractérisation des pics sans chevauchement ainsi que des pics déformés. Il permet aussi de diminuer la fréquence des fausses détections et d'obtenir une haute précision de la mesure de position, et ce même lorsque les signaux sont bruités. / This master's thesis describes a new method for analyzing cyclic voltammetry curves for an efficient peak detection and automatic baseline substraction. This method uses two distinct algorithms for a precise characterization of Gaussian redox peaks which are correlated with molecules' concentration in a solution. First, significant improvements are made to an existing algorithm that uses iterative polynomial approximations to suppress the baseline automatically from the voltammetric curves. With these enhancements, the algorithm extracts redox peaks from cyclic voltammetry measurements automatically and allows a better representation of the variation of peak's amplitude according to concentration. In addition, the approximation errors are reduced compared to the initial algorithm. Then, the development of an algorithm for characterizing Gaussian peaks based on the MUSIC second-order algorithm is presented. This algorithm is adapted to characterize the number, position, width and amplitude of redox peaks with high accuracy. Finally, the performances of this algorithm are compared with those of other similar algorithms using simulated and experimental curves. The suggested algorithm leads to a better characterization of non-overlapping peaks as well as distorted peaks. It also reduces the frequency of false detections and allows the precise measurement of peaks' positions in noisy signals.

Un bloc de bits est équilibré s’il contient un nombre de bits à 0 égal à celui des bits à 1. Les codes équilibrés (Balanced Codes, BC) sont largement appliqués dans plusieurs domaines. Par exemple, ils sont utilisés pour réduire le bruit dans les systèmes VLSI (Tabor, 1990). Dans le domaine de la télécommunication, ils sont utilisés dans la synchronisation et la transmission des données par fibre optique (Bergmann et al., 1986). Leur utilisation dans le domaine de l’identification par radiofréquence (RFID) permet d’augmenter les taux de transfert de données via les canaux RFID (Durgin, 2015). Étant donnée leur importance, plusieurs travaux de recherche ont été menés pour optimiser leur construction. Knuth fut le premier à trouver une méthode simple et rapide pour l’élaboration des codes équilibrés (Knuth, 1986). Il a introduit un algorithme très simple pour générer les codes équilibrés sans l’utilisation des tables de correspondance. Cependant, cet algorithme ajoute presque le double de la redondance minimale nécessaire pour la création des codes équilibrés. Une partie de cette redondance est due à la multiplicité d’encodage (ME) de cet algorithme. Plusieurs chercheurs ont essayé de réduire la redondance de l’algorithme de Knuth (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). Dans les derniers travaux de Al-Rababa’a et al. (2013), les auteurs ont réussi à éliminer la redondance créée par ME et pourtant un écart par rapport au seuil minimal subsiste. Ce travail présente une alternative à l’algorithme de Knuth pour créer les codes équilibrés sans surplus de redondance. Nous proposons un algorithme nommé « Pacman » ¹ basé sur les permutations et les nombres entiers à précision limitée. En effet, le processus de codage de cet algorithme peut être assimilé à un Pacman qui consomme et produit des blocs d’informations d’une façon cyclique. Au cours de ce travail, nous allons montrer analytiquement et expérimentalement que la redondance introduite par notre technique est particulièrement faible, que les résultats sont nettement meilleurs que ceux des travaux antérieurs et que les complexités temporelle et spatiale utilisées sont linéaires. ¹. Inspiré de la marque de commerce PAC-MAN de l’entreprise BANDAI NAMCO. / A block of m bits is said to be balanced if it contains an equal number of zeros and ones. Note that m has to be an even number. Balanced codes (BC) have applications in several domains. For example, they are used to reduce noise in VLSI systems (Tabor, 1990). In telecommunication, they are used in synchronization and data transmission by optical fibers (Bergmann et al., 1986). Their use in the field of radio frequency identification (RFID) can help to boost data transfer rate through RFID channels (Durgin, 2015). Given their importance, several research works have been carried out to optimize their construction. Knuth was the first to find a simple and fast method to create balanced codes (Knuth, 1986). He introduced a very simple algorithm to generate balanced codes without using lookup tables. However, Knuth’s balanced codes incur redundancy that is almost twice the one attested by the lower bound. A part of this redundancy is due to the multiplicity of encoding (ME) of this algorithm. Improvements to the Knuth’s algorithm are discussed in several research works (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). In the last one (Al-Rababa’a et al., 2013), redundancy created by ME was eliminated and yet there is still some gap that needs to be closed. This work presents an alternative to Knuth’s algorithm for creating balanced codes without unwanted redundancy overhead. We propose an algorithm called "Pacman" ² that is based on permutations and limited-precision integers. Indeed, the coding process of this algorithm can be assimilated to a special Pacman that consumes and produces pills of information in a cyclical manner. In the presented work, we prove analytically and experimentally that our algorithm closes the mentioned redundancy gap while preserving a favorable compromise between calculation speed and memory consumption. ². Inspired by the trademark PAC-MAN of BANDAI NAMCO.

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.