Cette thèse est consacrée à l'analyse théorique de problèmes non supervisés impliquant des séries temporelles à forte dépendance. Plus particulièrement, nous abordons les deux problèmes fondamentaux que sont le problème d'estimation des points de rupture et le partitionnement de séries temporelles. Ces problèmes sont abordés dans un cadre extrêmement général où les données sont générées par des processus stochastiques ergodiques stationnaires. Il s'agit de l'une des hypothèses les plus faibles en statistiques, comprenant non seulement, les hypothèses de modèles et les hypothèses paramétriques habituelles dans la littérature scientifique, mais aussi des hypothèses classiques d’indépendance, de contraintes sur l'espace mémoire ou encore des hypothèses de mélange.En particulier, aucune restriction n'est faite sur la forme ou la nature des dépendances, de telles sortes que les échantillons peuvent être arbitrairement dépendants. Pour chaque problème abordé, nous proposons de nouvelles méthodes non paramétriques et nous prouvons de plus qu'elles sont, dans ce cadre, asymptotiquement consistantes. Pour l'estimation de points de rupture, la consistance asymptotique se rapporte à la capacité de l'algorithme à produire des estimations des points de rupture qui sont asymptotiquement arbitrairement proches des vrais points de rupture. D'autre part, un algorithme de partitionnement est asymptotiquement consistant si le partitionnement qu'il produit, restreint à chaque lot de séquences, coïncides, à partir d'un certain temps et de manière consistante, avec le partitionnement cible. Nous montrons que les algorithmes proposés sont implémentables efficacement, et nous accompagnons nos résultats théoriques par des évaluations expérimentales.L'analyse statistique dans le cadre stationnaire ergodique est extrêmement difficile. De manière générale, il est prouvé que les vitesses de convergence sont impossibles à obtenir. Dès lors, pour deux échantillons générés indépendamment par des processus ergodiques stationnaires, il est prouvé qu'il est impossible de distinguer le cas où les échantillons sont générés par le même processus de celui où ils sont générés par des processus différents. Ceci implique que des problèmes tels le partitionnement de séries temporelles sans la connaissance du nombre de partitions ou du nombre de points de rupture ne peut admettre de solutions consistantes. En conséquence, une tâche difficile est de découvrir les formulations du problème qui en permettent une résolution dans ce cadre général. La principale contribution de cette thèse est de démontrer (par construction) que malgré ces résultats d'impossibilités théoriques, des formulations naturelles des problèmes considérés existent et admettent des solutions consistantes dans ce cadre général. Ceci inclut la démonstration du fait que le nombre de points de rupture corrects peut être trouvé, sans recourir à des hypothèses plus fortes sur les processus stochastiques. Il en résulte que, dans cette formulation, le problème des points de rupture peut être réduit à du partitionnement de séries temporelles.Les résultats présentés dans ce travail formulent les fondations théoriques pour l'analyse des données séquentielles dans un espace d'applications bien plus large. / This thesis is devoted to the theoretical analysis of unsupervised learning problems involving highly dependent time-series. Specifically, two fundamental problems are considered, namely, the problem of change point estimation as well as time-series clustering. The problems are considered in an extremely general framework, where the data are assumed to be generated by arbitrary, unknown stationary ergodic process distributions. This is one of the weakest assumptions in statistics: not only is it more general than the parametric and model-based settings, but it also subsumes most of the non-parametric frameworks considered for this class of problems, which typically include the assumption that each time-series consists of independent and identically distributed observations or that it satisfies certain mixing conditions. For each of the considered problems, novel nonparametric methods are proposed, and are further shown to be asymptotically consistent in this general framework. For change point estimation, asymptotic consistency refers to the algorithm's ability to produce change point estimates that are asymptotically arbitrarily close to the true change points. On the other hand, a clustering algorithm is asymptotically consistent, if the output clustering, restricted to each fixed batch of sequences, consistently coincides with the target clustering from some time on. The proposed algorithms are shown to be efficiently implementable, and the theoretical results are complemented with experimental evaluations. Statistical analysis in the stationary ergodic framework is extremely challenging. In general for this class of processes, rates of convergence (even of frequencies to respective probabilities) are provably impossible to obtain. As a result, given a pair of samples generated independently by stationary ergodic process distributions, it is provably impossible to distinguish between the case where they are generated by the same process or by two different ones. This in turn, implies that such problems as time-series clustering with unknown number of clusters, or change point detection, cannot possibly admit consistent solutions. Thus, a challenging task is to discover the problem formulations which admit consistent solutions in this general framework. The main contribution of this thesis is to constructively demonstrate that despite these theoretical impossibility results, natural formulations of the considered problems exist to admit consistent solutions in this general framework. Specifically, natural formulations of change-point estimation and time-series clustering are proposed, and efficient algorithms are provided, which are shown to be asymptotically consistent under the assumption that the process distributions are stationary ergodic. This includes the demonstration of the fact that the correct number of change points can be found, without the need to impose stronger assumptions on the process distributions. The results presented in this work lay down the theoretical foundations for the analysis of sequential data in a much broader range of real-world applications.

Dans de nombreux domaines scientifiques, la taille et la complexité des simulations numériques sont si importantes qu'il est souvent nécessaire d'utiliser des supercalculateurs à mémoire distribuée pour les réaliser. Les données de la simulation ainsi que les traitements sont alors répartis sur différentes unités de calculs, en tenant compte de nombreux paramètres. En effet, cette répartition est cruciale et doit minimiser le coût de calcul des traitements à effectuer tout en assurant que les données nécessaires à chaque unité de calcul puissent être stockées localement en mémoire. Pour la plupart des simulations numériques menées, les données des calculs sont attachées à un maillage, c'est-à-dire une discrétisation du domaine géométrique d'étude en éléments géométriques simples, les mailles. Les calculs à effectuer sont alors le plus souvent effectués au sein de chaque maille et la distribution des calculs correspond alors à un partitionnement du maillage. Dans un contexte de simulation numérique, où les méthodes mathématiques utilisées sont de types éléments ou volumes finis, la réalisation du calcul associé à une maille peut nécessiter des informations portées par des mailles voisines. L'approche standard est alors de disposer de ce voisinage localement à l'unité de calcul. Le problème à résoudre n'est donc pas uniquement de partitionner un maillage sur k parties en plaçant chaque maille sur une et une seule partie et en tenant compte de la charge de calcul attribuée à chaque partie. Il faut ajouter à cela le fait de prendre en compte l'occupation mémoire des cellules où les calculs sont effectués et leurs voisines. Ceci amène à partitionner les calculs tandis que le maillage est distribué avec recouvrement. Prendre explicitement ce recouvrement de données est le problème que nous proposons d'étudier. / In many scientific areas, the size and the complexity of numerical simulations lead to make intensive use of massively parallel runs on High Performance Computing (HPC) architectures. Such computers consist in a set of processing units (PU) where memory is distributed. Distribution of simulation data is therefore crucial: it has to minimize the computation time of the simulation while ensuring that the data allocated to every PU can be locally stored in memory. For most of the numerical simulations, the physical and numerical data are based on a mesh. The computations are then performed at the cell level (for example within triangles and quadrilaterals in 2D, or within tetrahedrons and hexahedrons in 3D). More specifically, computing and memory cost can be associated to each cell. In our context, where the mathematical methods used are finite elements or finite volumes, the realization of the computations associated with a cell may require information carried by neighboring cells. The standard implementation relies to locally store useful data of this neighborhood on the PU, even if cells of this neighborhood are not locally computed. Such non computed but stored cells are called ghost cells, and can have a significant impact on the memory consumption of a PU. The problem to solve is thus not only to partition a mesh on several parts by affecting each cell to one and only one part while minimizing the computational load assigned to each part. It is also necessary to keep into account that the memory load of both the cells where the computations are performed and their neighbors has to fit into PU memory. This leads to partition the computations while the mesh is distributed with overlaps. Explicitly taking these data overlaps into account is the problem that we propose to study.

Les travaux de recherche présentés se situent dans le contexte des méthodologies d’aide à l’implémentation d’algorithmes graphe flot de données sur architectures reconfigurables dynamiquement de type RSoC (Reconfigurable System on Chip) à base de technologie FPGA. La stratégie visée consiste à mettre en œuvre une approche de conception basée simultanément sur la reconfiguration dynamique (RD) et la synthèse architecturale (SA) en vue d’atteindre la meilleur Adéquation Algorithme Architecture (A3). La méthodologie consiste à identifier et extraire les parties d’une application décrite sous forme d’un GFD afin de les implanter soit par partie successivement reconfigurées (PT), soit par la SA ou bien en combinant les deux méthodes. Pour développer notre solution dans un but d’optimisation et de juste compromis entre les deux approches RD et SA, nous avons défini un paramètre permettant une évaluation du degré inter-partition de mise en œuvre d’unités fonctionnelles partagées. Afin de valider la stratégie méthodologique proposée, nous présentons les résultats de l’application de notre approche sur deux applications temps réel. Une analyse comparative en terme de résultats d’implémentation illustre l’intérêt et la capacité d’optimisation de cette méthode pour l’implémentation en reconfiguration dynamique d’applications complexes sur RSoC. / AThe research work presented in the context of methodologies is to assist the implementation of data flow graph algorithms on dynamically reconfigurable RSoC (Reconfigurable System on Chip)-based FPGA architectures.The main strategy consists in implementing a design approach based on simultaneously both the dynamic reconfiguration (DR) and synthesis architecture (SA) in order to achieve a best Adequacy Algorithm Architecture (A3). The methodology consists in identifying and extracting the parts of an application which is described in form of DFG in order to implement either by successively partial reconfiguration (TP), or by the AS or by combining the two approaches.To develop our solution with a view of optimizing and suitable compromise between the two approaches RD and SA, we propose a parameter in order to evaluate the degree of the inter-partition implementation based on functional units shared. In order to validate the proposed methodological strategy, we present the results of the implementation of our approach on two real-time applications. A comparative analysis with the respecting of the implementation results illustrates the interest and the optimisation ability of our method, which is also for dynamic reconfiguration implementation of the complex applications on RSoC.

L’analyse statistique des réseaux complexes est une tâche difficile, étant donné que des modèles statistiques appropriés et des procédures de calcul efficaces sont nécessaires afin d’apprendre les structures sous-jacentes. Le principe de ces modèles est de supposer que la distribution des valeurs des arêtes suit une distribution paramétrique, conditionnellement à une structure latente qui est utilisée pour détecter les formes de connectivité. Cependant, ces méthodes souffrent de procédures d’estimation relativement lentes, puisque les dépendances sont complexes. Dans cette thèse nous adaptons des stratégies d’estimation incrémentales, développées à l’origine pour l’algorithme EM, aux modèles de graphes. Additionnellement aux données de réseau utilisées dans les méthodes mentionnées ci-dessus, le contenu des noeuds est parfois disponible. Nous proposons ainsi des algorithmes de partitionnement pour les ensembles de données pouvant être modélisés avec une structure de graphe incorporant de l’information au sein des sommets. Finalement,un service Web en ligne, basé sur le moteur de recherche d’ Exalead, permet de promouvoir certains aspects de cette thèse. / He statistical analysis of complex networks is a challenging task, given that appropriate statistical models and efficient computational procedures are required in order for structures to be learned. The principle of these models is to assume that the distribution of the edge values follows a parametric distribution, conditionally on a latent structure which is used to detect connectivity patterns. However, these methods suffer from relatively slow estimation procedures, since dependencies are complex. In this thesis we adapt online estimation strategies, originally developed for the EM algorithm, to the case of graph models. In addition to the network data used in the methods mentioned above, vertex content will sometimes be available. We then propose algorithms for clustering data sets that can be modeled with a graph structure embedding vertex features. Finally, an online Web application, based on the Exalead search engine, allows to promote certain aspects of this thesis.

Ce travail concerne l’étude expérimentale de la sensibilité de l’écoulement du moteur et de ses variations cycle à cycle (VCC) à trois variations des conditions aux limitesliée à l’optimisation du remplissage moteur. Dans la configuration standard, l’écoulement tridimensionnel de rouleau (« tumble ») est décrit pendant les phases d’admission et de compression.Un phasage plus précoce de la loi de levée d’admission augmente le débit de masse aux soupapes et amplifie les fluctuations dès le début de l’admission. L’intensité du rouleau est beaucoup plus faible à phase mi-compression. L’énergie fluctuante au point mort haut est plus faible. Une course rallongée du moteur conduit, en fin de compression, à un basculement de l’écoulement moyen et à une évolution très différente des vitesses fluctuantes,due au confinement différent vue par l’aérodynamique du moteur. Enfin, la modification des conduits d’admission entraîne une variation de l’intensité et une structuration fondamentalement différente de l’écoulement. En outre, pour décrire le transfert vers la turbulence,deux méthodologies de classification des structures de l’écoulement en groupe par corrélation spatiale, puis par « clustering » sont adaptées. L’analyse statistique du contenu des différents groupes et des transitions entre groupes permet de montrer que les VCC sont associées à différentes trajectoires dans l’espace des groupes. Des statistiques conditionnelles sont calculées pour analyser les données de chaque groupe et permettent de définir une décomposition triple. Ces caractérisations plus précises des VCC sont très générales et applicables à des grandes bases de données expérimentales ou numériques. / This experimental work concerns a sensitivity study of the in-cylinder flow in aspark-ignition engine and of the cycle to cycle variations (CCV) by comparing three variationsof boundary conditions related to the optimisation of air filling conditions. In the reference case, the three dimensional tumble flow is characterized during the intake and compression phases. A earlier intake cam phase increases the mass flow rate at inlet valves and amplifiesthe fluctuations immediately after the start of intake phase. The tumble ratio is much lowerat mid-compression phase. The fluctuating energy at top dead center is reduced. A longerengine stroke leads, at the end of compression phase, to a shift of mean flow and to a verydistinct evolution of the fluctuating velocity, due to the different confinement from the pointof view of the engine internal flow. Finally, the modification of intake duct design changes theflow intensity and reorganizes in depth the flow structure. Moreover, to describe the transfer into turbulence, two methodologies of classification in groups of flow structures, by spatial correlation then by clustering, are proposed. A phase-averaged analysis of the statistics of group content and inter-group transitions shows that CCV can be associated with different sets of trajectories during the second half of the compression phase. The conditional statistics are computed to analyse the data in each group, which leads to a triple decomposition. It is important to point out that this more accurate evaluation of CCV is applicable to very large sets of experimental or numerical data.

L’augmentation de la quantité de données à visualiser due au phénomène du Big Data entraîne de nouveaux défis pour le domaine de la visualisation d’information. D’une part, la quantité d’information à représenter dépasse l’espace disponible à l’écran, entraînant de l’occlusion. D’autre part, ces données ne peuvent pas être stockées et traitées sur une machine conventionnelle. Un système de visualisation de données massives doit permettre la scalabilité de perception et de performances. Dans cette thèse, nous proposons une solution à ces deux problèmes au travers de l’abstraction multi-échelle des données. Plusieurs niveaux de détail sont précalculés sur une infrastructure Big Data pour permettre de visualiser de grands jeux de données jusqu’à plusieurs milliards de points. Pour cela, nous proposons deux approches pour implémenter l’algorithme de canopy clustering sur une plateforme de calcul distribué. Nous présentons une application de notre méthode à des données géolocalisées représentées sous forme de carte de chaleur, ainsi qu’à des grands graphes. Ces deux applications sont réalisées à l’aide de la bibliothèque de visualisation dynamique Fatum, également présentée dans cette thèse. / With the advent of the Big Data era come new challenges for Information Visualization. First, the amount of data to be visualized exceeds the available screen space. Second, the data cannot be stored and processed on a conventional computer. To alleviate both of these problems, a Big Data visualization system must provide perceptual and performance scalability. In this thesis, we propose to use multi-scale abstractions as a solution to both of these issues. Several levels of detail can be precomputed using a Big Data Infrastructure in order to visualize big datasets up to several billion points. For that, we propose two approaches to implementing the canopy clustering algorithm for a distributed computation cluster. We present applications of our method to geolocalized data visualized through a heatmap, and big graphs. Both of these applications use the dynamic visualization library, which is also presented in this thesis

Face au volume croissant de données audio et multimédia, les technologies liées à l'indexation de données et à l'analyse de contenu ont suscité beaucoup d'intérêt dans la communauté scientifique. Parmi celles-ci, la segmentation et le regroupement en locuteurs, répondant ainsi à la question 'Qui parle quand ?' a émergé comme une technique de pointe dans la communauté de traitement de la parole. D'importants progrès ont été réalisés dans le domaine ces dernières années principalement menés par les évaluations internationales du NIST. Tout au long de ces évaluations, deux approches se sont démarquées : l'une est bottom-up et l'autre top-down. L'ensemble des systèmes les plus performants ces dernières années furent essentiellement des systèmes types bottom-up, cependant nous expliquons dans cette thèse que l'approche top-down comporte elle aussi certains avantages. En effet, dans un premier temps, nous montrons qu'après avoir introduit une nouvelle composante de purification des clusters dans l'approche top-down, nous obtenons des performances comparables à celles de l'approche bottom-up. De plus, en étudiant en détails les deux types d'approches nous montrons que celles-ci se comportent différemment face à la discrimination des locuteurs et la robustesse face à la composante lexicale. Ces différences sont alors exploitées au travers d'un nouveau système combinant les deux approches. Enfin, nous présentons une nouvelle technologie capable de limiter l'influence de la composante lexicale, source potentielle d'artefacts dans le regroupement et la segmentation en locuteurs. Notre nouvelle approche se nomme Phone Adaptive Training par analogie au Speaker Adaptive Training / The ever-expanding volume of available audio and multimedia data has elevated technologies related to content indexing and structuring to the forefront of research. Speaker diarization, commonly referred to as the `who spoke when?' task, is one such example and has emerged as a prominent, core enabling technology in the wider speech processing research community. Speaker diarization involves the detection of speaker turns within an audio document (segmentation) and the grouping together of all same-speaker segments (clustering). Much progress has been made in the field over recent years partly spearheaded by the NIST Rich Transcription evaluations focus on meeting domain, in the proceedings of which are found two general approaches: top-down and bottom-up. Even though the best performing systems over recent years have all been bottom-up approaches we show in this thesis that the top-down approach is not without significant merit. Indeed we first introduce a new purification component leading to competitive performance to the bottom-up approach. Moreover, while investigating the two diarization approaches more thoroughly we show that they behave differently in discriminating between individual speakers and in normalizing unwanted acoustic variation, i.e.\ that which does not pertain to different speakers. This difference of behaviours leads to a new top-down/bottom-up system combination outperforming the respective baseline system. Finally, we introduce a new technology able to limit the influence of linguistic effects, responsible for biasing the convergence of the diarization system. Our novel approach is referred to as Phone Adaptive Training (PAT).

L'ordonnancement de tâches sur un système temps réel dur correspond à trouver une façon de choisir, à chaque instant, quelle tâche doit être exécutée sur le processeur pour que chacune ait le temps de terminer son travail avant son échéance. Ce problème, dans le contexte monoprocesseur, est déjà bien étudié et permet des applications sur des systèmes en production (aérospatiale, bourse etc.). Aujourd'hui, les plateformes multiprocesseur se sont généralisées et ont amené de nombreuses questions telles que l'utilisation efficace de tous les processeurs. Dans cette thèse, nous explorons les approches existantes pour résoudre ce problème. Nous étudions tout d'abord l'approche par partitionnement qui consiste à utiliser les recherches existantes en ramenant ce problème à plusieurs systèmes monoprocesseur. Ici, nous proposons un algorithme générique dont les paramètres sont adaptables en fonction de l'objectif à atteindre. Nous étudions ensuite l'approche par semi-partitionnement qui permet la migration d'un nombre restreint de tâches. Nous proposons une solution avec des migrations restreintes qui pourrait être assez simplement implémentée sur des systèmes concrets. Nous proposons ensuite une solution avec des migrations non restreintes qui offre de meilleurs résultats mais est plus difficile à implémenter. Enfin, les programmeurs utilisent de plus en plus le concept de tâches parallèles qui peuvent utiliser plusieurs processeurs en même temps. Ces tâches sont encore peu étudiées et nous proposons donc un nouveau modèle pour les représenter. Nous étudions les ordonnanceurs possibles et nous définissons une façon de garantir l'ordonnançabilité de ces tâches pour deux d'entre eux / The scheduling of tasks on a hard real-time system consists in finding a way to choose, at each time instant, which task should be executed on the processor so that each succeed to complete its work before its deadline. In the uniprocessor case, this problem is already well studied and enables us to do practical applications on real systems (aerospace, stock exchange etc.). Today, multiprocessor platforms are widespread and led to many issues such as the effective use of all processors. In this thesis, we explore the existing approaches to solve this problem. We first study the partitioning approach that reduces this problem to several uniprocessor systems and leverage existing research. For this one, we propose a generic partitioning algorithm whose parameters can be adapted according to different goals. We then study the semi-partitioning approach that allows migrations for a limited number of tasks. We propose a solution with restricted migration that could be implemented rather simply on real systems. We then propose a solution with unrestricted migration which provides better results but is more difficult to implement. Finally, programmers use more and more the concept of parallel tasks that can use multiple processors simultaneously. These tasks are still little studied and we propose a new model to represent them. We study the possible schedulers and define a way to ensure the schedulability of such tasks for two of them

Le clustering est le processus de partitionnement d’un ensemble de données en groupes, de sorte que les instances du même groupe sont plus semblables les unes aux autres qu’avec celles de tout autre groupe. De nombreux algorithmes de clustering ont été proposés, mais aucun d’entre eux ne s’avère fournir une partitiondes données pertinente dans toutes les situations. Le clustering par consensus vise à améliorer le processus de regroupement en combinant différentes partitions obtenues à partir de divers algorithmes afin d’obtenir une solution de consensus de meilleure qualité. Dans ce travail, une nouvelle méthode de clustering par consensus, appelée MultiCons, est proposée. Cette méthode utilise la technique d’extraction des itemsets fréquents fermés dans le but de découvrir les similitudes entre les différentes solutions de clustering dits de base. Les similitudes identifiées sont représentées sous une forme de motifs de clustering, chacun définissant un accord entre un ensemble de clusters de bases sur le regroupement d’un ensemble d’instances. En traitant ces motifs par groupes, en fonction du nombre de clusters de base qui définissent le motif, la méthode MultiCons génère une solution de consensus pour chaque groupe, générant par conséquence plusieurs consensus candidats. Ces différentes solutions sont ensuite représentées dans une structure arborescente appelée arbre de consensus, ouConsTree. Cette représentation graphique facilite la compréhension du processus de construction des multiples consensus, ainsi que les relations entre les instances et les structures d’instances dans l’espace de données / Clustering is the process of partitioning a dataset into groups, so that the instances in the same group are more similar to each other than to instances in any other group. Many clustering algorithms were proposed, but none of them proved to provide good quality partition in all situations. Consensus clustering aims to enhance the clustering process by combining different partitions obtained from different algorithms to yield a better quality consensus solution. In this work, a new consensus clustering method, called MultiCons, is proposed. It uses the frequent closed itemset mining technique in order to discover the similarities between the different base clustering solutions. The identified similarities are presented in a form of clustering patterns, that each defines the agreement between a set of base clusters in grouping a set of instances. By dividing these patterns into groups based on the number of base clusters that define the pattern, MultiCons generates a consensussolution from each group, resulting in having multiple consensus candidates. These different solutions are presented in a tree-like structure, called ConsTree, that facilitates understanding the process of building the multiple consensuses, and also the relationships between the data instances and their structuring in the data space. Five consensus functions are proposed in this work in order to build a consensus solution from the clustering patterns. Approach 1 is to just merge any intersecting clustering patterns. Approach 2 can either merge or split intersecting patterns based on a proposed measure, called intersection ratio

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