Computation and Analysis of Multiple Structural-Change Models

In a recent paper, Bai and Perron (1998) considered theoretical issues related to the limiting distribution of estimators and test statistics in the linear model with multiple structural changes. In this companion paper, we consider practical issues for the empirical applications of the procedures. We first address the problem of estimation of the break dates and present an efficient algorithm to obtain global minimizers of the sum of squared residuals. This algorithm is based on the principle of dynamic programming and requires at most least-squares operations of order O(T 2) for any number of breaks. Our method can be applied to both pure and partial structural-change models. Secondly, we consider the problem of forming confidence intervals for the break dates under various hypotheses about the structure of the data and the errors across segments. Third, we address the issue of testing for structural changes under very general conditions on the data and the errors. Fourth, we address the issue of estimating the number of breaks. We present simulation results pertaining to the behavior of the estimators and tests in finite samples. Finally, a few empirical applications are presented to illustrate the usefulness of the procedures. All methods discussed are implemented in a GAUSS program available upon request for non-profit academic use.

Improving sampling, optimization and feature extraction in Boltzmann machines

L’apprentissage supervisé de réseaux hiérarchiques à grande échelle connaît présentement un succès fulgurant. Malgré cette effervescence, l’apprentissage non-supervisé représente toujours, selon plusieurs chercheurs, un élément clé de l’Intelligence Artificielle, où les agents doivent apprendre à partir d’un nombre potentiellement limité de données. Cette thèse s’inscrit dans cette pensée et aborde divers sujets de recherche liés au problème d’estimation de densité par l’entremise des machines de Boltzmann (BM), modèles graphiques probabilistes au coeur de l’apprentissage profond. Nos contributions touchent les domaines de l’échantillonnage, l’estimation de fonctions de partition, l’optimisation ainsi que l’apprentissage de représentations invariantes. Cette thèse débute par l’exposition d’un nouvel algorithme d'échantillonnage adaptatif, qui ajuste (de fa ̧con automatique) la température des chaînes de Markov sous simulation, afin de maintenir une vitesse de convergence élevée tout au long de l’apprentissage. Lorsqu’utilisé dans le contexte de l’apprentissage par maximum de vraisemblance stochastique (SML), notre algorithme engendre une robustesse accrue face à la sélection du taux d’apprentissage, ainsi qu’une meilleure vitesse de convergence. Nos résultats sont présent ́es dans le domaine des BMs, mais la méthode est générale et applicable à l’apprentissage de tout modèle probabiliste exploitant l’échantillonnage par chaînes de Markov. Tandis que le gradient du maximum de vraisemblance peut-être approximé par échantillonnage, l’évaluation de la log-vraisemblance nécessite un estimé de la fonction de partition. Contrairement aux approches traditionnelles qui considèrent un modèle donné comme une boîte noire, nous proposons plutôt d’exploiter la dynamique de l’apprentissage en estimant les changements successifs de log-partition encourus à chaque mise à jour des paramètres. Le problème d’estimation est reformulé comme un problème d’inférence similaire au filtre de Kalman, mais sur un graphe bi-dimensionnel, où les dimensions correspondent aux axes du temps et au paramètre de température. Sur le thème de l’optimisation, nous présentons également un algorithme permettant d’appliquer, de manière efficace, le gradient naturel à des machines de Boltzmann comportant des milliers d’unités. Jusqu’à présent, son adoption était limitée par son haut coût computationel ainsi que sa demande en mémoire. Notre algorithme, Metric-Free Natural Gradient (MFNG), permet d’éviter le calcul explicite de la matrice d’information de Fisher (et son inverse) en exploitant un solveur linéaire combiné à un produit matrice-vecteur efficace. L’algorithme est prometteur: en terme du nombre d’évaluations de fonctions, MFNG converge plus rapidement que SML. Son implémentation demeure malheureusement inefficace en temps de calcul. Ces travaux explorent également les mécanismes sous-jacents à l’apprentissage de représentations invariantes. À cette fin, nous utilisons la famille de machines de Boltzmann restreintes “spike & slab” (ssRBM), que nous modifions afin de pouvoir modéliser des distributions binaires et parcimonieuses. Les variables latentes binaires de la ssRBM peuvent être rendues invariantes à un sous-espace vectoriel, en associant à chacune d’elles, un vecteur de variables latentes continues (dénommées “slabs”). Ceci se traduit par une invariance accrue au niveau de la représentation et un meilleur taux de classification lorsque peu de données étiquetées sont disponibles. Nous terminons cette thèse sur un sujet ambitieux: l’apprentissage de représentations pouvant séparer les facteurs de variations présents dans le signal d’entrée. Nous proposons une solution à base de ssRBM bilinéaire (avec deux groupes de facteurs latents) et formulons le problème comme l’un de “pooling” dans des sous-espaces vectoriels complémentaires.

Exploitation du potentiel sismique des étoiles naines blanches

Le but de cette thèse est d’explorer le potentiel sismique des étoiles naines blanches pulsantes, et en particulier celles à atmosphères riches en hydrogène, les étoiles ZZ Ceti. La technique d’astérosismologie exploite l’information contenue dans les modes normaux de vibration qui peuvent être excités lors de phases particulières de l’évolution d’une étoile. Ces modes modulent le flux émergent de l’étoile pulsante et se manifestent principalement en termes de variations lumineuses multi-périodiques. L’astérosismologie consiste donc à examiner la luminosité d’étoiles pulsantes en fonction du temps, afin d’en extraire les périodes, les amplitudes apparentes, ainsi que les phases relatives des modes de pulsation détectés, en utilisant des méthodes standards de traitement de signal, telles que des techniques de Fourier. L’étape suivante consiste à comparer les périodes de pulsation observées avec des périodes générées par un modèle stellaire en cherchant l’accord optimal avec un modèle physique reconstituant le plus fidèlement possible l’étoile pulsante. Afin d’assurer une recherche optimale dans l’espace des paramètres, il est nécessaire d’avoir de bons modèles physiques, un algorithme d’optimisation de comparaison de périodes efficace, et une puissance de calcul considérable. Les périodes des modes de pulsation de modèles stellaires de naines blanches peuvent être généralement calculées de manière précise et fiable sur la base de la théorie linéaire des pulsations stellaires dans sa version adiabatique. Afin de définir dans son ensemble un modèle statique de naine blanche propre à l’analyse astérosismologique, il est nécessaire de spécifier la gravité de surface, la température effective, ainsi que différents paramètres décrivant la disposition en couche de l’enveloppe. En utilisant parallèlement les informations obtenues de manière indépendante (température effective et gravité de surface) par la méthode spectroscopique, il devient possible de vérifier la validité de la solution obtenue et de restreindre de manière remarquable l’espace des paramètres. L’exercice astérosismologique, s’il est réussi, mène donc à la détermination précise des paramètres de la structure globale de l’étoile pulsante et fournit de l’information unique sur sa structure interne et l’état de sa phase évolutive. On présente dans cette thèse l’analyse complète réussie, de l’extraction des fréquences à la solution sismique, de quatre étoiles naines blanches pulsantes. Il a été possible de déterminer les paramètres structuraux de ces étoiles et de les comparer remarquablement à toutes les contraintes indépendantes disponibles dans la littérature, mais aussi d’inférer sur la dynamique interne et de reconstruire le profil de rotation interne. Dans un premier temps, on analyse le duo d’étoiles ZZ Ceti, GD 165 et Ross 548, afin de comprendre les différences entre leurs propriétés de pulsation, malgré le fait qu’elles soient des étoiles similaires en tout point, spectroscopiquement parlant. L’analyse sismique révèle des structures internes différentes, et dévoile la sensibilité de certains modes de pulsation à la composition interne du noyau de l’étoile. Afin de palier à cette sensibilité, nouvellement découverte, et de rivaliser avec les données de qualité exceptionnelle que nous fournissent les missions spatiales Kepler et Kepler2, on développe une nouvelle paramétrisation des profils chimiques dans le coeur, et on valide la robustesse de notre technique et de nos modèles par de nombreux tests. Avec en main la nouvelle paramétrisation du noyau, on décroche enfin le ”Saint Graal” de l’astérosismologie, en étant capable de reproduire pour la première fois les périodes observées à la précision des observations, dans le cas de l’étude sismique des étoiles KIC 08626021 et de GD 1212.

Efficient Priority Rules

We study the assignment of indivisible objects with quotas (houses, jobs, or offices) to a set of agents (students, job applicants, or professors). Each agent receives at most one object and monetary compensations are not possible. We characterize efficient priority rules by efficiency, strategy-proofness, and reallocation-consistency. Such a rule respects an acyclical priority structure and the allocations can be determined using the deferred acceptance algorithm.

A robust algorithm for segmenting fluorescence images and its application to single-molecule counting

La microscopie par fluorescence de cellules vivantes produit de grandes quantités de données. Ces données sont composées d’une grande diversité au niveau de la forme des objets d’intérêts et possèdent un ratio signaux/bruit très bas. Pour concevoir un pipeline d’algorithmes efficaces en traitement d’image de microscopie par fluorescence, il est important d’avoir une segmentation robuste et fiable étant donné que celle-ci constitue l’étape initiale du traitement d’image. Dans ce mémoire, je présente MinSeg, un algorithme de segmentation d’image de microscopie par fluorescence qui fait peu d’assomptions sur l’image et utilise des propriétés statistiques pour distinguer le signal par rapport au bruit. MinSeg ne fait pas d’assomption sur la taille ou la forme des objets contenus dans l’image. Par ce fait, il est donc applicable sur une grande variété d’images. Je présente aussi une suite d’algorithmes pour la quantification de petits complexes dans des expériences de microscopie par fluorescence de molécules simples utilisant l’algorithme de segmentation MinSeg. Cette suite d’algorithmes a été utilisée pour la quantification d’une protéine nommée CENP-A qui est une variante de l’histone H3. Par cette technique, nous avons trouvé que CENP-A est principalement présente sous forme de dimère.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.