Academic literature on the topic 'Apprentissage de structures causales'

Cette thèse a pour but d'expliquer les concepts et principes centraux de la causalité. Nous nous intéresserons particulièrement à la découverte causale à partir de séries temporelles, domaine émergent aujourd’hui avec, notamment, les données industrielles de capteurs. Dans les deux premiers chapitres, nous présentons les concepts puis les algorithmes existants dans ce domaine. Ensuite, nous présentons une nouvelle approche qui infère un graphe récapitulatif du système causal sous-jacent aux séries temporelles tout en assouplissant le cadre idéalisé de fréquences d'échantillonnage égaux, tout en discutant ses hypothèses et sa validité. La principale nouveauté dans cette méthode réside dans l'introduction de la mesure d'information mutuelle temporelle causale qui permet de détecter l'indépendance et l'indépendance conditionnelle entre deux séries temporelles, et l’établissement d'un lien apparent entre l'entropie et le principe d'augmentation de la probabilité d'un effet sachant sa cause, lien qui peut être utilisé pour construire de nouvelles règles pour l'orientation de la direction de la causalité. De plus, à travers le développement de la première méthode, nous proposons plusieurs extensions qui permettent de gérer les causes communes cachées, de déduire un graphe causal temporel à partir d'un graphe récapitulatif et de pouvoir s’adapter aux données ordonnées (pas nécessairement temporelles). Puis, nous nous concentrons sur la découverte de relations causales à partir d'une distribution statistique qui n'est pas entièrement fidèle au graphe causal réel et sur la distinction entre une cause commune et une cause intermédiaire même, en absence d'indicateur de temps. L'aspect clé de notre réponse à ce problème est le recours au principe du bruit additif pour déduire un supergraphe dirigé contenant le graphe causal. Pour converger vers le graphe causal, nous utilisons une nouvelle mesure appelée l'entropie de causalité temporelle qui élague pour chaque nœud du supergraphe dirigé, les parents qui en sont conditionnellement indépendants. En outre, nous explorons des extensions complémentaires de notre deuxième méthode qui impliquent une stratégie par paires et une stratégie multitâche. Nous effectuons une comparaison expérimentale approfondie des algorithmes proposés sur des ensembles de données à la fois synthétiques et réels et nous montrons leurs performances pratiques prometteuses: gain en complexité temporelle tout en préservant la précision<br>This thesis aims to give a broad coverage of central concepts and principles of causation and in particular the ones involved in the emerging approaches to causal discovery from time series.After reviewing concepts and algorithms, we first present a new approach that infer a summary graph of the causal system underlying the observational time series while relaxing the idealized setting of equal sampling rates and discuss the assumptions underlying its validity. The gist of our proposal lies in the introduction of the causal temporal mutual information measure that can detect the independence and the conditional independence between two time series, and in making an apparent connection between entropy and the probability raising principle that can be used for building new rules for the orientation of the direction of causation. Moreover, through the development of this base method, we propose several extensions, namely to handle hidden confounders, to infer a window causal graph given a summary graph, and to consider sequences instead of time series.Secondly, we focus on the discovery of causal relations from a statistical distribution that is not entirely faithful to the real causal graph and on distinguishing a common cause from an intermediate cause even in the absence of a time indicator. The key aspect of our answer to this problem is the reliance on the additive noise principle to infer a directed supergraph that contains the causal graph. To converge toward the causal graph, we use in a second step a new measure called the temporal causation entropy that prunes for each node of the directed supergraph, the parents that are conditionally independent of their child. Furthermore, we explore complementary extensions of our second base method that involve a pairwise strategy which reduces through multitask learning and a denoising technique, the number of functions that need to be estimated. We perform an extensive experimental comparison of the proposed algorithms on both synthetic and real datasets and demonstrate their promising practical performance: gaining in time complexity while preserving accuracy

Cette thèse porte sur les méthodes basées sur des contraintes. Nous présentons comme exemple l’algorithme PC, pour lequel nous proposons une modification qui garantit la cohérence des ensembles de séparation, utilisés pendant l’étape de reconstruction du squelette pour supprimer les arêtes entre les variables conditionnellement indépendantes, par rapport au graphe final. Elle consiste à itérer l’algorithme d’apprentissage de structure tout en limitant la recherche des ensembles de séparation à ceux qui sont cohérents par rapport au graphe obtenu à la fin de l’itération précédente. La contrainte peut être posée avec une complexité de calcul limitée à l’aide de la décomposition en block-cut tree du squelette du graphe. La modification permet d’augmenter le rappel au prix de la précision des méthodes basées sur des contraintes, tout en conservant une performance globale similaire ou supérieure. Elle améliore également l’interprétabilité et l’explicabilité du modèle graphique obtenu. Nous présentons ensuite la méthode basée sur des contraintes MIIC, récemment développée, qui adopte les idées du cadre du maximum de vraisemblance pour améliorer la robustesse et la performance du graphe obtenu. Nous discutons les caractéristiques et les limites de MIIC, et proposons plusieurs modifications qui mettent l’accent sur l’interprétabilité du graphe obtenu et l’extensibilité de l’algorithme. En particulier, nous mettons en œuvre l’approche itérative pour renforcer la cohérence de l’ensemble de séparation, nous optons pour une règle d’orientation conservatrice et nous utilisons la probabilité d’orientation de MIIC pour étendre la notation des arêtes dans le graphe final afin d’illustrer différentes relations causales. L’algorithme MIIC est appliqué à un ensemble de données d’environ 400 000 dossiers de cancer du sein provenant de la base de données SEER, comme benchmark à grande échelle dans la vie réelle<br>This thesis is focused on constraint-based methods, one of the basic types of causal structure learning algorithm. We use PC algorithm as a representative, for which we propose a simple and general modification that is applicable to any PC-derived methods. The modification ensures that all separating sets used during the skeleton reconstruction step to remove edges between conditionally independent variables remain consistent with respect to the final graph. It consists in iterating the structure learning algorithm while restricting the search of separating sets to those that are consistent with respect to the graph obtained at the end of the previous iteration. The restriction can be achieved with limited computational complexity with the help of block-cut tree decomposition of the graph skeleton. The enforcement of separating set consistency is found to increase the recall of constraint-based methods at the cost of precision, while keeping similar or better overall performance. It also improves the interpretability and explainability of the obtained graphical model. We then introduce the recently developed constraint-based method MIIC, which adopts ideas from the maximum likelihood framework to improve the robustness and overall performance of the obtained graph. We discuss the characteristics and the limitations of MIIC, and propose several modifications that emphasize the interpretability of the obtained graph and the scalability of the algorithm. In particular, we implement the iterative approach to enforce separating set consistency, and opt for a conservative rule of orientation, and exploit the orientation probability feature of MIIC to extend the edge notation in the final graph to illustrate different causal implications. The MIIC algorithm is applied to a dataset of about 400 000 breast cancer records from the SEER database, as a large-scale real-life benchmark

L'ensemble des travaux présentés relève de l'Apprentissage Artificiel, et aborde l'apprentissage supervisé, ainsi que l'aide à la découverte par la fouille de données. On se place ici dans le cas où un problème d'apprentissage passe par l'exploration d'un "Espace de Recherche", constitué de représentations formées dans un certain langage d'énoncés. La structure cachée liant "énoncés" et sous-ensembles d'"objets", représentable dans un treillis intension/extension, permet en particulier de réduire l'espace de recherche dans les problèmes d'apprentissage supervisé. Je présente ensuite une forme d'"abstraction" ordonnée faisant varier le niveau de granularité des énoncés, ou des objets considérés, et garantissant que le treillis intension/extension est ainsi lui-même réduit. Certains travaux concernant la recherche de motifs séquentiels réquents, sont également interprétés du point de vue de cette relation intension/extension. Enfin, deux "paradigmes" nouveaux en apprentissage supervisé sont présentés, l'un traitant de la notion d'ambiguïté des exemples, l'autre étendant l'apprentissage supervisé cohérent dans un cadre collectif.

Le programme de recherches présenté dans cette synthèse s'inscrit dans la double problématique de l'étude des langages d'arbres et de l'apprentissage automatique à partir de données arborescentes. <br /> À la base de ce travail se trouve la question de l'accès et de la manipulation automatique d'informations au format XML au sein d'un réseau d'applications réparties dans internet. La réalisation de ces applications est toujours du ressort de programmeurs spécialistes d'XML et reste hors de portée de l'utilisateur final. De plus, les développements récents d'internet poursuivent l'objectif d'automatiser les communications entre applications s'échangeant des flux de données XML. Le recours à des techniques d'apprentissage automatique est une réponse possible à cette situation. <br /> Nous considèrons que les informations sont décrites dans un langage XML, et dans la perspective de ce mémoire, embarquées dans des données structurées sous forme arborescente. Les applications sont basées alors sur des opérations élémentaires que sont l'interrogation ou les requêtes dans ces documents arborescents ou encore la transformation de tels documents. <br /> Nous abordons alors la question sous l'angle de la réalisation automatique de programmes d'annotation d'arbres, permettant de dériver des procédures de transformation ou d'exécution de requêtes. Le mémoire décrit les contributions apportées pour la manipulation et l'apprentissage d'ensembles d'arbres d'arité non bornée (comme le sont les arbres XML), et l'annotation par des méthodes de classification supervisée ou d'inférence statistique.

Les travaux de cette thèse s'inscrivent dans la continuité des travaux faites sur le thème d'apprentissage par analogie dans le projet CORDIAL de l'IRISA. Les efforts précédents ont porté sur l'étude de la proportion analogique dans le cas des objets numériques et symboliques, puis dans le cas de séquences de ces objets, ainsi que sur l'utilisation de ces notions pour l'apprentissage. Nous nous intéressons ici, dans nos travaux, à l'application de ce concept en apprentissage automatique pour le Traitement automatique du langage naturel (TALN), notamment pour l'analyse syntaxique et pour la génération de la prosodie en synthèse de parole. Ceci nécessite de définir le concept de proportion analogique entre quatre structures d'arbres. Notre approche trouve son originalité dans l'utilisation des propriétés hiérarchiques des structures manipulées et dans l'utilisation de mesure de dissemblance analogique (DA) entre ces structures. Son intérêt réside donc dans son adaptation facile à différents contextes et différentes données, quand ceux-ci sont propices à une représentation arborescente. Dans ce cadre, deux algorithmes ont été mis en place pour calculer la DA entre quatre structures d'arbres et pour résoudre une équation analogique. Le principe de notre démarche réside à étendre la notion connue d'alignement entre deux arbres à quatre (ou un plus grand nombre) d'arbres et de profiter des propriétés de l'alignement lors de la définition de l'analogie sur les structures d'arbres en question. Les applications de notre démarche se sont attachées à des problèmes de traitement de langue, notamment en analyse syntaxique et la génération de paramètres prosodiques. Le principe est le même dans les deux cas. Pour ce faire, il est nécessaire de détecter une dissemblance analogique dans le domaine source et de faire l'hypothèse qu'elle pourrait s'appliquer dans le domaine cible. Les résultats se sont montrés encourageants dans leur globalité, en tout cas comparés à la méthode du plus proche voisin. De profondes améliorations sont encore nécessaires, principalement dans la complexité des algorithmes. Nous souhaitons que leur réalisation ultérieure permette d'appliquer cette méthode, qui nous semble prometteuse, à des problèmes variés.

L'inférence de la causalité est une problématique récurrente pour un large éventail de domaines où les méthodes d'interventions ou d'acquisition de données temporelles sont inapplicables. Toutefois, établir des relations de causalité uniquement à partir de données d'observation peut se révéler être une tâche complexe. Je présente ici une méthode d'apprentissage de réseaux qui combine les avantages des méthodes d'inférence par identification de contraintes structurales et par optimisation de scores bayésiens pour reconstruire de manière robuste des réseaux causaux malgré le bruit d'échantillonnage inhérent aux données d'observation. Cette méthode repose sur l'identification de v-structures à l'aide de l'information (conditionnelle) à trois variables, une mesure issue de la théorie de l'information, qui est négative quand elle est associée à un collider et positive sinon. Cette approche soustrait itérativement l'information conditionnelle à trois variables la plus forte à l'information conditionnelle à deux variables entre chaque paire de noeuds. Les indépendences conditionnelles sont progressivement calculées en collectant les contributions les plus fortes. Le squelette est ensuite partiellement orienté et ces orientations sont propagées aux liens non orientés selon le signe et la force de l'interaction dans les triplets ouverts. Cette approche obtient de meilleurs résultats que les méthodes par contraintes ou optimisation de score sur un ensemble de réseaux benchmark et fournit des prédictions prometteuses pour des systèmes biologiques complexes, tels que les réseaux neuronaux du poisson zèbre ou l'inférence des cascades de mutations dans les tumeurs<br>The inference of causality is an everyday life question that spans a broad range of domains for which interventions or time-series acquisition may be impracticable if not unethical. Yet, elucidating causal relationships in real-life complex systems can be convoluted when relying solely on observational data. I report here a novel network reconstruction method, which combines constraint-based and Bayesian frameworks to reliably reconstruct networks despite inherent sampling noise in finite observational datasets. The approach is based on an information theory result tracing back the existence of colliders in graphical models to negative conditional 3-point information between observed variables. This enables to confidently ascertain structural independencies in causal graphs, based on the ranking of their most likely contributing nodes with (significantly) positive conditional 3-point information. Dispensible edges from a complete undirected graph are progressively pruned by iteratively taking off the most likely positive conditional 3-point information from the 2-point (mutual) information between each pair of nodes. The resulting skeleton is then partially directed by orienting and propagating edge directions based on the sign and magnitude of the conditional 3-point information of unshielded triples. This new approach outperforms constraint-based and Bayesian inference methods on a range of benchmark networks and provides promising predictions when applied to the reconstruction of complex biological systems, such as hematopoietic regulatory subnetworks, zebrafish neural networks, mutational pathways or the interplay of genomic properties on the evolution of vertebrates

Un réseau logique de Markov est formé de clauses en logique du premier ordre auxquelles sont associés des poids. Cette thèse propose plusieurs méthodes pour l'apprentissage de la structure de réseaux logiques de Markov (MLN) à partir de données relationnelles. Ces méthodes sont de deux types, un premier groupe reposant sur les techniques de propositionnalisation et un second groupe reposant sur la notion de Graphe des Prédicats. L'idée sous-jacente aux méthodes à base de propositionnalisation consiste à construire un jeu de clauses candidates à partir de jeux de littéraux dépendants. Pour trouver de tels jeux, nous utilisons une méthode de propositionnalisation afin de reporter les informations relationnelles dans des tableaux booléens, qui serviront comme tables de contingence pour des test de dépendance. Nous avons proposé deux méthodes de propositionnalisation, pour lesquelles trois algorithmes ont été développés, qui couvrent les problèmes d'appprentissage génératif et discriminant. Nous avons ensuite défini le concept de Graphe des Prédicats qui synthétise les relations binaires entre les prédicats d'un domaine. Des clauses candidates peuvent être rapidement et facilement produites en suivant des chemins dans le graphe puis en les variabilisant. Nous avons développé deux algorithmes reposant sur les Graphes des Prédicats, qui couvrent les problèmes d'appprentissage génératif et discriminant.

Un auditeur occidental développe une sensibilité aux régularités du système musical tonal par simple exposition répétée aux pièces issues de ce système. Une fois acquises, ces connaissances lui permettraient de construire une présentation mentale de la structure de l’œuvre entendue. Notre travail de recherche porte sur la perception de grandes structures musicales, sur le rôle des connaissances tonales lors du traitement et sur l’acquisition de ces connaissances. Le premier volet de recherche s’intéresse à la perception des structures globales et locales dans des pièces musicales réelles. Différents paradigmes expérimentaux (jugements d’expressivité et de cohérence, résolution de « puzzle musical », détection et reconnaissance d’extraits cibles) montrent que les structures locales prédominent sur les structures globales. Ces dernières ne semblent avoir que peu d’importance pour l’auditeur dans des pièces d’une durée de 3 min. Ou de 20 sec. Le deuxième volet étudie la contribution des connaissances lors du traitement des structures d’événements dans de courtes séquences (de 8 à 14 accords). Le paradigme d’amorçage harmonique met en évidence une influence des structures globales et locales sur le traitement d’un accord. Des simulations réalisées avec un modèle connexionnistes d’une représentation des connaissances tonales (Bharucha, 1987) suggèrent que l’influence des structures émerge d’une simple activation des connaissances et de leur accumulation au cours du temps – sans intégration hiérarchique dans une structure d’ensemble. Des modèles connexionnistes permettent de simuler la capacité du système cognitif à extraire des régularités sous-jacentes de l’environnement. Dans le troisième volet, nous réalisons de simulations d’apprentissage des régularités du système tonal à l’aide des algorithmes d’apprentissage non supervisé. Le réseau doté d’un mécanisme de propagation d’activation permet de simuler des données expérimentales sur la perception des notes, des accords et des tonalités. L’ensemble de résultats conduit à concevoir le traitement des structures d’événements en termes d’accumulation des informations plutôt qu’en terme d’intégration hiérarchique des informations au sens strict<br>Western listeners acquire a sensitivity to the regularities of the tonal system of Western music by mere exposure to tonal musical pieces. Once acquired, this knowledge allows the construction of a mental representation of the structure of tonal musical pieces. The present research examines the perception of large musical structures, the contribution of tonal knowledge in this processing and the acquisition of this knowledge. The first part of the research investigates the perception of global and local structures in real musical pieces. Different experimental paradigms (judgments of expressivity and coherence, resolution of “musical puzzles”, target detection and recognition) provide evidence that local structures prevail over global structures. Global structures seem to have relatively little importance for the listener in pieces of 3 min. Or 20 sec in length. The second part examines the contribution of tonal knowledge to the processing of event structures in short sequences (8 to 14 chords). The harmonic priming paradigm reveals an influence of global and local structures on chord processing. Simulations with a connectionist model of tonal knowledge representation (Bharucha, 1987) suggest that the influence of the structures emerges from simple activation of tonal knowledge and its accumulation over time – without hierarchical integration in an overall structure. Connectionist models allow modeling of the capacity of the cognitive system to extract underlying regularities from the environment. In the third part, learning simulations of the tonal system are realized with the help of an unsupervised learning algorithm. The network, combined with a spreading activation mechanism, allows modeling of experimental data on the processing of event structures in terms of information accumulation rather than in terms of a hierarchical integration strictly speaking

Les systèmes actuels d’improvisation musicales sont capables de générer des séquences musicales unidimensionnelles par recombinaison du matériel musical. Cependant, la prise en compte de plusieurs dimensions (mélodie, harmonie...) et la modélisation de plusieurs niveaux temporels sont des problèmes difficiles. Dans cette thèse, nous proposons de combiner des approches probabilistes et des méthodes issues de la théorie des langages formels afin de mieux apprécier la complexité du discours musical à la fois d’un point de vue multidimensionnel et multi-niveaux dans le cadre de l’improvisation où la quantité de données est limitée. Dans un premier temps, nous présentons un système capable de suivre la logique contextuelle d’une improvisation représentée par un oracle des facteurs tout en enrichissant son discours musical à l’aide de connaissances multidimensionnelles représentées par des modèles probabilistes interpolés. Ensuite, ces travaux sont étendus pour modéliser l’interaction entre plusieurs musiciens ou entre plusieurs dimensions par un algorithme de propagation de croyance afin de générer des improvisations multidimensionnelles. Enfin, nous proposons un système capable d’improviser sur un scénario temporel avec des informations multi-niveaux représenté par une grammaire hiérarchique. Nous proposons également une méthode d’apprentissage pour l’analyse automatique de structures temporelles hiérarchiques. Tous les systèmes sont évalués par des musiciens et improvisateurs experts lors de sessions d’écoute<br>Current musical improvisation systems are able to generate unidimensional musical sequences by recombining their musical contents. However, considering several dimensions (melody, harmony...) and several temporal levels are difficult issues. In this thesis, we propose to combine probabilistic approaches with formal language theory in order to better assess the complexity of a musical discourse, both from a multidimensional and multi-level point of view in the context of improvisation where the amount of data is limited. First, we present a system able to follow the contextual logic of an improvisation modelled by a factor oracle whilst enriching its musical discourse with multidimensional knowledge represented by interpolated probabilistic models. Then, this work is extended to create another system using a belief propagation algorithm representing the interaction between several musicians, or between several dimensions, in order to generate multidimensional improvisations. Finally, we propose a system able to improvise on a temporal scenario with multi-level information modelled with a hierarchical grammar. We also propose a learning method for the automatic analysis of hierarchical temporal structures. Every system is evaluated by professional musicians and improvisers during listening sessions

La Programmation par contraintes est un cadre général utilisé pour modéliser et résoudre des problèmes combinatoires complexes. Cependant, la modélisation d'un problème sous forme d’un réseau de contraintes nécessite une bonne expertise dans le domaine. Ce niveau d'expertise est un obstacle majeur pour une large diffusion de la programmation de contraintes. Pour remédier à ce problème, plusieurs systèmes d'acquisition de contraintes ont été proposés pour aider l'utilisateur dans la tâche de modélisation. Dans ces systèmes, l'utilisateur ne répond qu'à des questions très simples. L'inconvénient est que lorsqu'aucune connaissance de base n’est fournie, l'utilisateur peut avoir besoin de répondre à un grand nombre de questions pour apprendre toutes les contraintes. Dans cette thèse, nous montrons que l'utilisation de la structure du problème peut améliorer considérablement le processus d'acquisition. Pour ce faire, nous proposons plusieurs techniques. Tout d'abord, nous introduisons le concept de requête de généralisation basée sur une agrégation de variables sous forme detypes. Deuxièmement, pour faire face aux requêtes de généralisation, nous proposons un algorithme de généralisation de contraintes, nommé GENACQ, ainsi que plusieurs stratégies. Troisièmement, pour rendre la construction de requêtes de généralisation totalement indépendante de l'utilisateur, nous proposons l'algorithme MINE&amp;ASK, qui est en mesure d'apprendre la structure au cours du processus d'acquisition de contraintes, et d'utiliser la structure apprise pour générer des requêtes de généralisation. Quatrièmement, pour aller vers un concept générique de requête, nous introduisons la requête de recommandation basée sur la prédiction de liens dans le graphe de contraintes apprises jusqu’à présent. Cinquièmement, nous proposons un algorithme de recommandation de contraintes, ppelé PREDICT&amp;ASK, qui demande à l’utilisateur de classifier des requêtes de recommandation chaque fois que la structure du graphe courant a été modifiée. Enfin, nous intégrons toutes ces nouvelles techniques dans l’algorithme QUACQ, menant à trois nouvelles versions, à savoir G-QUACQ, M- QUACQ, et P-QUACQ. Pour évaluer toutes ces techniques, nous avons fait des expérimentations sur plusieurs jeux de données. Les résultats montrent que les versions étendues améliorent considérablement le QUACQ de base<br>Constraint Programming is a general framework used to model and solve complex combinatorial problems.However, modeling a problem as a constraint network requires significant expertise in the field.Such level of expertise is a bottleneck to the broader uptake of the constraint technology.To alleviate this issue, several constraint acquisition systems have been proposed to assist thenon-expert user in the modeling task. Nevertheless, in these systems the user is only asked to answervery basic questions. The drawback is that when no background knowledge is provided,the user may need to answer a large number of such questions to learn all the constraints.In this thesis, we show that using the structure of the problem under consideration may improvethe acquisition process a lot. To this aim, we propose several techniques.Firstly, we introduce the concept of generalization query based on an aggregation of variables into types.Secondly, to deal with generalization queries, we propose a constraint generalization algorithm, named GENACQ, together with several strategies. Thirdly, to make the build of generalization queries totally independent of the user, we propose the algorithm MINE&amp;ASK, which is able to learn the structure, during the constraint acquisition process, and to use the learned structure to generate generalization queries. Fourthly, toward a generic concept of query, we introduce the recommendation query based on the link prediction on the current constraint graph. Fifthly, we propose a constraint recommender algorithm, called PREDICT&amp;ASK, that asks recommendation queries, each time the structure of the current graph has been modified. Finally, we incorporate all these new generic techniques into QUACQ algorithm leading to three boosted versions, G-QUACQ, M- QUACQ, and P-QUACQ. To evaluate all these techniques, we have made experiments on several benchmarks. The results show that the extended versions improve drastically the basic QUACQ