Search

Widely adopted for more than 20 years in industrial fields, business rules offer the opportunity to non-IT users to define decision-making policies in a simple and intuitive way. To facilitate their use, rule-based systems, known as business rule management systems, have been developed, separating the business logic from the computer application. While they are suitable for processing structured and complete data, they do not easily allow working with probabilistic data. PROCOP (Probabilistic Rules Optimized and COmPilation) is a thesis proposing a new approach for the integration of probabilistic reasoning in IBM Operational Decision Manager (ODM), IBM's business rules management system, in particular through the introduction of a concept of global risk on the evaluation of the execution conditions of an action, complicating the compilation phase of the system but increasing the expressiveness of the business rules. Various methods are explored, implemented and compared in order to allow the use of such a powerful reasoning capacity on a large scale, in particular in order to answer the problems linked to the use of probabilistic graphical models in complex networks.; Adoptées depuis plus de 20 ans par le monde de l’industrie, les règles métiers (business rules) offrent la possibilité à des utilisateurs non-informaticiens de définir des politiques de prise de décision de manière simple et intuitive. Pour faciliter leurs utilisations, des systèmes à base de règles, dits « systèmes de gestion des règles métier », ont été développés, séparant la logique métier de l’application informatique. S’ils sont adaptés pour traiter des données structurées et complètes, ils ne permettent pas aisément de travailler sur des données probabilistes. PROCOP (Probabilistic Rules Optimized and COmPilation) est une thèse proposant une nouvelle approche pour l’intégration de raisonnement probabiliste dans IBM Operational Decision Manager (ODM), le système de gestion des règles métier développé par IBM, notamment via l’introduction d’une notion de risque global sur l'évaluation des conditions d'exécution d'une action, complexifiant la phase de compilation du système mais augmentant l’expressivité des règles métiers. Diverses méthodes sont explorées, implémentées et comparées afin de permettre l'utilisation d'une telle capacité de raisonnement à large échelle, notamment afin de répondre aux problématiques liées à l'utilisation de modèles graphiques probabilistes dans des réseaux complexes.

As the quantity and size of available data grow, the existing algorithms for solving sparse inverse problems can become computationally intractable. In this work, we explore two main strategies for accelerating such algorithms. First, we study the use of structured dictionaries which are fast to operate with. A particular family of dictionaries, written as a sum of Kronecker products, is proposed. Then, we develop stable screening tests, which can safely identify and discard useless atoms (columns of the dictionary matrix which do not correspond to the solution support), despite manipulating approximate dictionaries.; En raison de la vertigineuse croissance des données disponibles, la complexité computationnelle des algorithmes traitant les problèmes inverses parcimonieux peut vite devenir un goulot d'étranglement. Dans cette thèse, nous explorons deux stratégies pour accélérer de tels algorithmes. D'abord, nous étudions l'utilisation de dictionnaires structurés rapides à manipuler. Une famille de dictionnaires écrits comme une somme de produits Kronecker est proposée. Ensuite, nous développons des tests d'élagage sûrs, capables d'identifier et éliminer des atomes inutiles (colonnes de la matrice dictionnaire ne correspondant pas au support de la solution), malgré l'utilisation de dictionnaires approchés.

The present report summarizes the research activities that I have carried out since completion of my PhD. My attention has focused on the fundamental signal processing problem of source signal estimation from the observation of corrupted measurements, in scenarios where the measured data can be considered as unknown linear transformations of the sources. Two typical problems of this kind are the deconvolution or equalization of channels introducing linear distortions and source separation in linear mixtures. The blind approach makes as few assumptions as possible about the problem in hand: these typically reduce to the statistical independence of the sources and the invertibility of the channel or mixing matrix characterizing the propagation medium. Despite the advantages that have driven the interest in these techniques since the 70's, blind criteria also present some important drawbacks such as the existence of estimation ambiguities, the presence of local extrema leading to spurious solutions, and a high computational complexity often linked to slow convergence. My research has been devoted to the design of novel signal estimation techniques alleviating the drawbacks and thus improving the performance of the blind approach. Special emphasis has been laid on two specific applications in telecommunications and biomedical engineering: equalization and source separation in digital communication channels and atrial activity extraction in surface electrocardiogram recordings of atrial fibrillation patients. Most of the proposed techniques can be considered as semi-blind in that they aim at exploiting available prior information about the problems under study other than source independence; e.g., the existence of training data in communication systems or specific properties about the atrial source in atrial fibrillation. In communications, the approaches that I have explored include algebraic solutions to contrast functions based on digital modulations, the combination of blind and training-based contrasts into semi-blind criteria, and an iterative optimization technique with an optimal step-size coefficient computed algebraically. Our efforts to extract the atrial signal in multi-lead atrial fibrillation recordings has led not only to new contrast functions based on second- and higher-order statistics incorporating priors about the source statistics, but also to novel results of clinical and physiological significance about this challenging cardiac condition. The report concludes by proposing some possible avenues for the continuation of this work. This investigation has been carried out in collaboration with a number of colleagues in France and abroad, and has also comprised the joint supervision of several PhD students. The resulting contributions have given rise to over sixty publications in international journals, conferences and book chapters. A compilation of selected publications is attached to this document.; Ce rapport résume mes activités de recherche depuis l'obtention de mon doctorat. Je me suis penché sur le problème fondamental de l'estimation de signaux sources à partir de l'observation de mesures corrompues de ces signaux, dans des scénarios où les données mesurées peuvent être considérées comme une transformation linéaire inconnue des sources. Deux problèmes classiques de ce type sont la déconvolution ou égalisation de canaux introduisant des distorsions linéaires, et la séparation de sources dans des mélanges linéaires. L'approche dite aveugle essaie d'exploiter un moindre nombre d'hypothèses sur le problème à résoudre : celles-ci se réduisent typiquement à l'indépendance statistique des sources et l'inversibilité du canal ou de la matrice de mélange caractérisant le milieu de propagation. Malgré les avantages qui ont suscité l'intérêt pour ces techniques depuis les années soixante-dix, les critères aveugles présentent aussi quelques inconvénients importants, tels que l'existence d'ambiguïtés dans l'estimation, la présence d'extrema locaux associés à des solutions parasites, et un coût de calcul élevé souvent lié à une convergence lente. Ma recherche s'est consacrée à la conception de nouvelles techniques d'estimation de signal visant à pallier aux inconvénients de l'approche aveugle et donc à améliorer ses performances. Une attention particulière a été portée sur deux applications dans les télécommunications et le génie biomédical : l'égalisation et la séparation de sources dans des canaux de communications numériques, et l'extraction de l'activité auriculaire à partir des enregistrements de surface chez les patients souffrant de fibrillation auriculaire. La plupart des techniques proposées peuvent être considérées comme étant semi-aveugles, dans le sens où elles visent à exploiter des informations a priori sur le problème étudié autres que l'indépendance des sources ; par exemple, l'existence de symboles pilotes dans les systèmes de communications ou des propriétés spécifiques de la source atriale dans la fibrillation auriculaire. Dans les télécommunications, les approches que j'ai explorées incluent des solutions algébriques aux fonctions de contraste basées sur la modulation numérique, la combinaison de contrastes aveugles et supervisés dans des critères semi-aveugles, et une technique d'optimisation itérative basée sur un pas d'adaptation calculé algébriquement. Nos efforts visant à extraire le signal atrial dans des enregistrements de fibrillation auriculaire nous ont permis non seulement de dégager de nouvelles fonctions de contraste basées sur les statistiques de second ordre et d'ordre élevé incorporant l'information a priori sur les statistiques des sources, mais aussi d'aboutir à de nouveaux résultats d'impact clinique et physiologique sur ce trouble cardiaque encore mal compris. Ce rapport se conclut en proposant quelques perspectives pour la continuation de ces travaux. Ces recherches ont été menées en collaboration avec un nombre de collègues en France et à l'étranger, et ont également compris le co-encadrement de plusieurs doctorants. Les contributions qui en ont découlé ont donné lieu à plus de soixante publications dans des journaux, des conférences et des ouvrages collectifs à caractère international. Quelques-unes de ces publications sont jointes à ce document.

The present report summarizes the research activities that I have carried out since completion of my PhD. My attention has focused on the fundamental signal processing problem of source signal estimation from the observation of corrupted measurements, in scenarios where the measured data can be considered as unknown linear transformations of the sources. Two typical problems of this kind are the deconvolution or equalization of channels introducing linear distortions and source separation in linear mixtures. The blind approach makes as few assumptions as possible about the problem in hand: these typically reduce to the statistical independence of the sources and the invertibility of the channel or mixing matrix characterizing the propagation medium. Despite the advantages that have driven the interest in these techniques since the 70's, blind criteria also present some important drawbacks such as the existence of estimation ambiguities, the presence of local extrema leading to spurious solutions, and a high computational complexity often linked to slow convergence. My research has been devoted to the design of novel signal estimation techniques alleviating the drawbacks and thus improving the performance of the blind approach. Special emphasis has been laid on two specific applications in telecommunications and biomedical engineering: equalization and source separation in digital communication channels and atrial activity extraction in surface electrocardiogram recordings of atrial fibrillation patients. Most of the proposed techniques can be considered as semi-blind in that they aim at exploiting available prior information about the problems under study other than source independence; e.g., the existence of training data in communication systems or specific properties about the atrial source in atrial fibrillation. In communications, the approaches that I have explored include algebraic solutions to contrast functions based on digital modulations, the combination of blind and training-based contrasts into semi-blind criteria, and an iterative optimization technique with an optimal step-size coefficient computed algebraically. Our efforts to extract the atrial signal in multi-lead atrial fibrillation recordings has led not only to new contrast functions based on second- and higher-order statistics incorporating priors about the source statistics, but also to novel results of clinical and physiological significance about this challenging cardiac condition. The report concludes by proposing some possible avenues for the continuation of this work. This investigation has been carried out in collaboration with a number of colleagues in France and abroad, and has also comprised the joint supervision of several PhD students. The resulting contributions have given rise to over sixty publications in international journals, conferences and book chapters. A compilation of selected publications is attached to this document.; Ce rapport résume mes activités de recherche depuis l'obtention de mon doctorat. Je me suis penché sur le problème fondamental de l'estimation de signaux sources à partir de l'observation de mesures corrompues de ces signaux, dans des scénarios où les données mesurées peuvent être considérées comme une transformation linéaire inconnue des sources. Deux problèmes classiques de ce type sont la déconvolution ou égalisation de canaux introduisant des distorsions linéaires, et la séparation de sources dans des mélanges linéaires. L'approche dite aveugle essaie d'exploiter un moindre nombre d'hypothèses sur le problème à résoudre : celles-ci se réduisent typiquement à l'indépendance statistique des sources et l'inversibilité du canal ou de la matrice de mélange caractérisant le milieu de propagation. Malgré les avantages qui ont suscité l'intérêt pour ces techniques depuis les années soixante-dix, les critères aveugles présentent aussi quelques inconvénients importants, tels que l'existence d'ambiguïtés dans l'estimation, la présence d'extrema locaux associés à des solutions parasites, et un coût de calcul élevé souvent lié à une convergence lente. Ma recherche s'est consacrée à la conception de nouvelles techniques d'estimation de signal visant à pallier aux inconvénients de l'approche aveugle et donc à améliorer ses performances. Une attention particulière a été portée sur deux applications dans les télécommunications et le génie biomédical : l'égalisation et la séparation de sources dans des canaux de communications numériques, et l'extraction de l'activité auriculaire à partir des enregistrements de surface chez les patients souffrant de fibrillation auriculaire. La plupart des techniques proposées peuvent être considérées comme étant semi-aveugles, dans le sens où elles visent à exploiter des informations a priori sur le problème étudié autres que l'indépendance des sources ; par exemple, l'existence de symboles pilotes dans les systèmes de communications ou des propriétés spécifiques de la source atriale dans la fibrillation auriculaire. Dans les télécommunications, les approches que j'ai explorées incluent des solutions algébriques aux fonctions de contraste basées sur la modulation numérique, la combinaison de contrastes aveugles et supervisés dans des critères semi-aveugles, et une technique d'optimisation itérative basée sur un pas d'adaptation calculé algébriquement. Nos efforts visant à extraire le signal atrial dans des enregistrements de fibrillation auriculaire nous ont permis non seulement de dégager de nouvelles fonctions de contraste basées sur les statistiques de second ordre et d'ordre élevé incorporant l'information a priori sur les statistiques des sources, mais aussi d'aboutir à de nouveaux résultats d'impact clinique et physiologique sur ce trouble cardiaque encore mal compris. Ce rapport se conclut en proposant quelques perspectives pour la continuation de ces travaux. Ces recherches ont été menées en collaboration avec un nombre de collègues en France et à l'étranger, et ont également compris le co-encadrement de plusieurs doctorants. Les contributions qui en ont découlé ont donné lieu à plus de soixante publications dans des journaux, des conférences et des ouvrages collectifs à caractère international. Quelques-unes de ces publications sont jointes à ce document.

This thesis presents methods and algorithms for the performance evaluation of large state space models described by high-level formalisms. Among the various formalisms we use Stochastic Automata Networks (SAN) formalism. SAN formalism is dedicated to modeling very large systems by the composition of its subsystems (automata), where these automata interact with each other by synchronizing events or functional rates and probabilities. The state space explosion of a model is a common problem when computing the reachable state space of complex systems. In the first part of this thesis, we propose reachable state space generation methods of structured models which use functional rates (general state dependant rates) and probabilities. We use Multi-valued Decision Diagrams (MDD) to store sets of reachable spaces and SAN formalism to describe structured models. MDD is a multilevel data structure which efficiently manipulates a extremely large state spaces. Regarding state-of-the-art generation methods, our methods allow to construct a huge reachable state space of a model which uses functional rates and probabilities. The methods are tested on some models in order to illustrate this contribution. In the second part, we are interested in the solution of a discrete time SAN model whose transition matrix is represented by a tensor formula (called discrete descriptor). For this purpose, we present the Complex Tensor Algebra (XTA) adapted to the parallel composition of the discrete time SANs in order to represent the discrete descriptor and we prove some properties that are the basis for iterative methods for solving the Markov chain associated to the SAN model. Representing a SAN model by a descriptor is a compact way to describe the transitions among global states of the model: we replace a description in a product space by a single tensor product on factors that describe what happens on a single dimension (one automaton of the SAN model). In order to take advantage of this representation, we present a vector-descriptor product method which performs the multiplication of a probability vector and the discrete descriptor. This method aims at exploiting the properties of the complex tensor product so that the multiplication by an operator on the product space is replaced by a series of operations that manipulate data on the size of an automaton (and for all automata).; Cette thèse présente des méthodes et des algorithmes pour l'évaluation de performance de systèmes à grand espace d'états décrits par des formalismes de haut niveau. Parmi les différents formalismes de haut niveau normalement utilisés, nous nous sommes intéressés au formalisme des Réseaux d'Automates Stochastiques (SAN). Le formalisme SAN se caractérise par la modélisation de systèmes complexes, où un système est représenté par la composition de sous-systèmes (automates) qui interagissent entre eux. Cette interaction se réalise par l'occurrence des événements synchronisants ou des taux fonctionnels. Lorsqu'on calcule l'espace d'états atteignables de systèmes complexes, le principal problème qui surgit est l'explosion combinatoire de l'espace d'états du modèle. Dans la première partie de cette thèse, nous proposons des méthodes pour la génération de l'espace d'états atteignables de modèles compositionnels qui utilisent des taux fonctionnels. Nous utilisons les Diagrammes de Décision Multi-valués (MDD) pour représenter et manipuler les espaces d'états et le formalisme SAN pour la modélisation de systèmes. Un MDD est une structure de donnée arborescente qui permet de représenter et de manipuler de façon performante un très grand espace d'états. L'avancée par rapport à l'état de l'art a été de proposer de méthodes qui prennent en compte ces fonctions qui expriment des relations entre les composants des modèles. Des études d'exemples sont présentées afin d'illustrer les apports de ces méthodes. Dans la deuxième partie de cette thèse, nous nous sommes intéressés à la résolution d'un modèle SAN à temps discret dont la matrice de transition est représentée par une formule tensorielle (appelée descripteur discret). A cet effet, nous présentons l'Algèbre Tensorielle compleXe (ATX) adaptée à la composition parallèle des SAN à temps discret pour la représentation du descripteur et nous démontrons des propriétés qui servent de base aux méthodes itératives pour la résolution de la chaîne de Markov associée au modèle SAN. Un des avantages de représenter un modèle SAN par un descripteur est la façon compacte par laquelle on peut représenter les transitions du modèle: on remplace une description dans un espace produit par un unique produit tensoriel portant sur des facteurs qui décrivent ce qui se passe sur une seule dimension (une composante du modèle SAN). Afin de profiter de cette représentation, nous présentons une méthode de multiplication d'un vecteur de probabilité par un descripteur discret adaptée à cette algèbre. Cette méthode vise à exploiter des propriétés du produit tensoriel complexe de façon à ce que la multiplication par un opérateur sur l'espace produit soit remplacée par une suite d'opérations qui manipulent des données de la taille d'une composante (et pour toutes les composantes).

This thesis presents methods and algorithms for the performance evaluation of large state space models described by high-level formalisms. Among the various formalisms we use Stochastic Automata Networks (SAN) formalism. SAN formalism is dedicated to modeling very large systems by the composition of its subsystems (automata), where these automata interact with each other by synchronizing events or functional rates and probabilities. The state space explosion of a model is a common problem when computing the reachable state space of complex systems. In the first part of this thesis, we propose reachable state space generation methods of structured models which use functional rates (general state dependant rates) and probabilities. We use Multi-valued Decision Diagrams (MDD) to store sets of reachable spaces and SAN formalism to describe structured models. MDD is a multilevel data structure which efficiently manipulates a extremely large state spaces. Regarding state-of-the-art generation methods, our methods allow to construct a huge reachable state space of a model which uses functional rates and probabilities. The methods are tested on some models in order to illustrate this contribution. In the second part, we are interested in the solution of a discrete time SAN model whose transition matrix is represented by a tensor formula (called discrete descriptor). For this purpose, we present the Complex Tensor Algebra (XTA) adapted to the parallel composition of the discrete time SANs in order to represent the discrete descriptor and we prove some properties that are the basis for iterative methods for solving the Markov chain associated to the SAN model. Representing a SAN model by a descriptor is a compact way to describe the transitions among global states of the model: we replace a description in a product space by a single tensor product on factors that describe what happens on a single dimension (one automaton of the SAN model). In order to take advantage of this representation, we present a vector-descriptor product method which performs the multiplication of a probability vector and the discrete descriptor. This method aims at exploiting the properties of the complex tensor product so that the multiplication by an operator on the product space is replaced by a series of operations that manipulate data on the size of an automaton (and for all automata).; Cette thèse présente des méthodes et des algorithmes pour l'évaluation de performance de systèmes à grand espace d'états décrits par des formalismes de haut niveau. Parmi les différents formalismes de haut niveau normalement utilisés, nous nous sommes intéressés au formalisme des Réseaux d'Automates Stochastiques (SAN). Le formalisme SAN se caractérise par la modélisation de systèmes complexes, où un système est représenté par la composition de sous-systèmes (automates) qui interagissent entre eux. Cette interaction se réalise par l'occurrence des événements synchronisants ou des taux fonctionnels. Lorsqu'on calcule l'espace d'états atteignables de systèmes complexes, le principal problème qui surgit est l'explosion combinatoire de l'espace d'états du modèle. Dans la première partie de cette thèse, nous proposons des méthodes pour la génération de l'espace d'états atteignables de modèles compositionnels qui utilisent des taux fonctionnels. Nous utilisons les Diagrammes de Décision Multi-valués (MDD) pour représenter et manipuler les espaces d'états et le formalisme SAN pour la modélisation de systèmes. Un MDD est une structure de donnée arborescente qui permet de représenter et de manipuler de façon performante un très grand espace d'états. L'avancée par rapport à l'état de l'art a été de proposer de méthodes qui prennent en compte ces fonctions qui expriment des relations entre les composants des modèles. Des études d'exemples sont présentées afin d'illustrer les apports de ces méthodes. Dans la deuxième partie de cette thèse, nous nous sommes intéressés à la résolution d'un modèle SAN à temps discret dont la matrice de transition est représentée par une formule tensorielle (appelée descripteur discret). A cet effet, nous présentons l'Algèbre Tensorielle compleXe (ATX) adaptée à la composition parallèle des SAN à temps discret pour la représentation du descripteur et nous démontrons des propriétés qui servent de base aux méthodes itératives pour la résolution de la chaîne de Markov associée au modèle SAN. Un des avantages de représenter un modèle SAN par un descripteur est la façon compacte par laquelle on peut représenter les transitions du modèle: on remplace une description dans un espace produit par un unique produit tensoriel portant sur des facteurs qui décrivent ce qui se passe sur une seule dimension (une composante du modèle SAN). Afin de profiter de cette représentation, nous présentons une méthode de multiplication d'un vecteur de probabilité par un descripteur discret adaptée à cette algèbre. Cette méthode vise à exploiter des propriétés du produit tensoriel complexe de façon à ce que la multiplication par un opérateur sur l'espace produit soit remplacée par une suite d'opérations qui manipulent des données de la taille d'une composante (et pour toutes les composantes).

Resume Une methode de calcul rapide du spectre de la decomposition harmonique d'un tenseur quelconque est presentee. Pour citer cet article : N. Auffray, C. R. Mecanique 336 (2008).

Markov Chains facilitate the performance analysis of dynamic systems in many areas of application. This thesis presents the formalism of stochastic automata networks (SANs) to represent Markov systems. The main goal of this work consists in improving existing methods for the performance evaluation of systems with a large state space. For this, we introduce the concept of SANs with replicas, and techniques to reduce the state space of such models. To obtain performance indices, we propose an improvement of the basic operations by taking into account the fact that inside the product state space, the actual reachable state space can be much smaller. The new methods and algorithms have been implemented into the PEPS 2003 software. Numerical examples are provided to illustrate the contributions of this thesis., Les chaînes de Markov facilitent l'analyse des performances des systèmes dynamiques dans de nombreux domaines d'application. Cette thèse présente le formalisme des réseaux d'automates stochastiques pour représenter des systèmes markoviens. Le principal objectif des travaux consiste à améliorer les méthodes existantes pour évaluer les performances de systèmes informatiques à grand espace d'états. Pour cela, nous introduisons le concept de réseaux d'automates stochastiques avec réplication, ainsi que des techniques pour simplifier le modèle étudié en réduisant la taille de l'espace d'états. Pour rechercher des indices de performances, on propose une amélioration de l'opération de base en tenant compte du fait que dans de nombreux modèles, la proportion d'états accessibles est faible. Les méthodes et algorithmes développés au cours de la thèse ont été implémentés dans le logiciel PEPS 2003. Des exemples numériques sont présentés pour illustrer les apports de cette thèse.

Ce document est une introduction à l'algèbre tensorielle pour non mathématiciens. Écrite à l'origine dans le cadre de la vision par ordinateur, elle tire de ce domaine, et de la géométrie projective très employée en vision, quelques exemples. Elle contient une approche intuitive et une introduction plus formelle des notions de base : covariance et contravariance, produit tensoriel, bases et changements de bases, contraction et invariants, cas des espaces euclidiens.

Université : Faculté des sciences de l'Université de Grenoble