Laboratoire d'Informatique Fondamentale de Lille (UMR 8022 Lille1/CNRS) © Sophie TISON,
Mentions légales
The problem considered is as follows. Given a growing sequence of observations x1,...,xn...., one is required, at each time step n, to make some inference about the stochastic mechanism generating the sequence. Several problems that have numerous applications in different branches of mathematics and computer science can be formulated in this way. For example, one may want to forecast probabilities of the next outcome xn+1 (sequence prediction); to make a decision on whether the mechanism generating the sequence belongs to a certain family H_0 versus it belongs to a different family H_1 (hypothesis testing); to take an action in order to maximize some utility function.
In each of these problems, as well as in many others, in order to be able to make inference, one has to make some assumptions on the probabilistic mechanism generating the data. Typical assumptions are that xi are independent and identically distributed, or that the distribution generating the sequence belongs to a certain parametric family. The central question addressed in this work is: under which assumptions is inference possible? This question is considered for several problems of inference, including sequence prediction, hypothesis testing, classification and reinforcement learning.
The most important results presented here are as follows. For the problem of hypothesis testing, a topological characterization (necessary and sufficient conditions) of those (composite) hypotheses H_0, contained in the set E of all stationary ergodic discrete-valued process measures, that can be consistently tested against the complement E \ H_0 is obtained. The developed approach, which is based on empirical estimates of the distributional distance, is also used to obtain consistent procedures for change point estimation, process classification and clustering, under the only assumption that the data (real-valued, in this case) is generated by stationary ergodic distributions: a setting that is much more general than those in which consistent procedures were known before. I have also demonstrated that a consistent test for homogeneity does not exist for the general case of stationary ergodic (discrete-valued) sequences. For the problem of sequence prediction, it is shown that if there is a consistent predictor for a set of process distributions C, then there is a Bayesian predictor consistent for this set. This is a no-assumption result: the distributions in C can be arbitrary (non-i.i.d., non-stationary, etc.) and the set itself does not even have to be measurable. Several descriptions (sufficient conditions) of those sets C of process distributions for which consistent predictors exist. For the problem of selecting an optimal strategy in a reactive environment (perhaps, the most general inference problem considered) some sufficient conditions on the environments under which it is possible to find a universal asymptotically optimal strategy are identified.
A rapid evolution of networks, workstations, large supercomputers and personal computers, gives rise to new architectural alternatives for parallel and distributed computing. Clusters, grids and, more recently, cloud computing can therefore give an answer to constantly growing demands for computational resources, thanks to new paradigms, software concepts and systems, which are all based on distributed programming. The main features of distributed and heterogeneous applications are their irregularity and unpredictability. To enable efficient execution of such applications, we propose a programming environment for distributed applications in Java and the runtime environment ADAJ (Adaptive Distributed Applications in Java), which optimizes dynamic placement of application objects on clusters and computers within a grid. This distribution is based on a novel mechanism of observation of object work, and the relationships between the objects. The gain from this flexible and adaptive object distribution results in better execution efficiency and in better use of the power of different computers. At the same time it minimizes communication costs and reduces extra cost associated with application control. With these mechanisms, ADAJ provides automatic and adaptive distribution of application elements across the job execution platform, giving thus a reply to the computing and resource availability changes. This operation is based on a cycle stealing method and can control of the application execution granularity. As a result, the programmer does not need to worry about it anymore.
Mechanisms have been implemented for various platforms and technologies. Initially, they have been designed to run on clusters of workstations containing no more than a hundred computers. In order to scale up the solution designed for cluster computing, we have re-engineered, processed and completed it. Specifically, we have introduced a framework based on software components, to help the designer to build applications for grids of computers. This work was then extended so that the platform ADAJ is today a full middleware stack. It is based on web services and it’s information system is based on agents. Mechanisms of ADAJ can now manage grid execution platforms, consisting of thousands of nodes. Finally we have tested this approach on datamining problems with some distributed algorithms, which have been specifically developed. By this work, we have responded to the current problems concerning the implementation and use of grids by designing a new SOKU (Service Oriented Knowledge Utilities) architecture. Finally, we show how this research can be integrated in the theme of embedded systems.
Keywords: Grid computing, auto-adaptive applications, dynamic load balancing, SOKU systems, datamining
L’Internet des objets est un large sujet qui englobe tous les objets communicants comme les réseaux de capteurs et les systèmes RFID. Ce mémoire résume mes principales contributions dans l’auto-organisation et le passage à l’échelle de la RFID active et passive, plus précisément au travers des intergiciels RFID et des réseaux de capteurs et d’actionneurs sans fil. Cette HDR résume les études et solutions proposées à différents niveaux pour ces différents types de réseaux : auto-organisation, localisation, routage, contrôle de topologie.
Nous décrivons de nouvelles modélisations et des approches de résolution que nous appliquons à des problèmes de découpe et de conditionnement. Les structures « simples » des problèmes de bin-packing et de sac à dos font que ces problèmes NP-difficiles font partie des plus étudiés dans la littérature de recherche opérationnelle. Ils ont été notamment à la base de nombreuses contributions concernant les algorithmes d'approximation ou la programmation en nombres entiers. Il apparaît clairement que les méthodes développés pour ces problèmes ont des répercussions pour de nombreuses applications en optimisation combinatoire, ce qui justifie la très abondante littérature dont ils font l'objet.
Au cours de notre travail, nous avons mobilisé des résultats provenant de plusieurs disciplines au sein de la communauté optimisation à l'aide de modèles originaux. Nos travaux utilisent en effet des résultats de programmation mathématique, programmation par contraintes, méta-heuristiques, programmation dynamique et de théorie des graphes. Ces méthodes sont utilisées dans des méthodes collaboratives qui reposent très fortement sur nos nouveaux modèles.
Nous avons tout d'abord travaillé sur des méthodes de décompositions et des méthodes méta-heuristiques basées sur des stratégies dites d'oscillation. Ces techniques ont été validées sur des problèmes de packing avec différents types de conflits. Une autre famille de contributions concerne les fonctions dites dual-réalisables, qui permettent d'obtenir des évaluations par défaut rapides pour plusieurs problèmes de packing, et d'améliorer des coupes en programmation en nombres entiers. Nous proposons aussi des modèles originaux pour des problèmes de placement en deux dimensions. Ces modèles donnent lieu à des techniques hybridant techniques de programmation par contraintes et recherche opérationnelle.
Toutes nos contributions sont validées de manière théorique (classes de complexité, preuves de dominance) et pratique (expérimentation et comparaison avec les meilleures méthodes de la littérature). Elles donnent lieu à de nombreuses perspectives pour la résolution de problèmes de packing et pour la mise en place de méthodes
collaboratives.
Ce travail présente nos principales contributions à la résolution de problèmes d'optimisation combinatoire en environnements déterministe et stochastique.
Au niveau des métaheuristiques, une vue unifiée de la conception de métaheuristiques à solution unique et de métaheuristiques multi-objective est proposée. Cette unification a permis notamment de retravailler la plateforme ParadisEO afin d’offrir plus de flexibilité et de polyvalence.
La synthèse des travaux présente également une vue unifiée des métaheuristiques coopératives. Nous montrons que cette vue convient aussi bien pour des coopérations entre métaheuristiques que des coopération entre des métaheuristiques et des méthodes exactes mais également des coopérations entre des métaheuristiques et des algorithmes d’extraction de connaissances. Différents exemples de coopérations réalisées dans mes travaux de recherche illustent ces coopérations et leur application à des problèmes d’optimisation combinatoire mono- et multi-objectif.
Cette habilitation se termine par la présentation de travaux réalisés en optimisation stochastique notamment dans le cadre de l’optimisation sous incertitude et de l’optimisation dynamique. L’importance des critères de robustesse est discutée ainsi que l’intérêt et la mise en œuvre de méthodes coopératives dans un contexte dynamique.
Les principales applications présentées on été réalisées sur des problèmes en transport et logistique ainsi qu’en biologie dans le cadre de l’ANR Dock.
Ce manuscrit résume mes travaux de recherche depuis ma thèse soutenue en septembre 2002. Certains de mes travaux présentés sont achevés à l’heure actuelle, d’autres sont en cours d’avancement ou encore à un stade exploratoire. Tout au long de ces années, mes travaux se sont inscrit dans le contexte de la conception conjointe logicielle/matérielle de SoCs dédiés aux applications de traitement de signal intensif.
La complexité des systèmes ciblant ce domaine d’application ne cesse de s’accroitre lors des dernières années. En effet, les besoins grandissants, en terme de puissance de calcul et stockage mémoire des applicatifs du traitement de signal intensif, rendent la conception des Soc les implémentant très fastidieuse et nécessitant un temps et des efforts considérables.
Ainsi, la ligne directrice de mes travaux a toujours été de fournir des méthodes et outils d’aide à la conception de tels SoC, permettant un maximum d’automatisation, une augmentation de la productivité des concepteurs et une réduction des temps de mise sur le marché des systèmes conçus.
Je me suis donc concentré principalement sur trois aspects : la modélisation de haut niveau en fournissant des méta-modèles et profils respectant le standard MARTE ; les plateformes de simulation distribuées, supportant l’interopérabilité entre plusieurs niveaux d’abstraction tout en permettant une bonne estimation de la consommation d’énergie ; et finalement la production d’outils de conception basés sur les transformations automatiques modèle à modèle de l’approche IDM.
Etant convaincu du grand potentiel des FPGAs partiellement et dynamiquement reconfigurables, j’oriente de plus en plus mes travaux pour cibler de telles architectures. Ainsi, mes travaux futurs iront certainement dans le même sens, dans le cadre notamment du projet ANR FAMOUS que je dirige. Ainsi, les grandes orientations de mes recherches concerneront notamment : la modélisation (basée sur MARTE) de la reconfiguration dynamique sous toutes ses facettes (architecture, application, association, déploiement; et partitionnement); la simulation des FPGAs et l’estimation de leur consommation (pour piloter l’exploration d’architectures) ; et enfin l’intégration dans des outils de conception basés sur les standards (tels que MARTE et IDM).
Pas de résumé
Les génomes peuvent être vus de manière simplifiée comme des suites de gènes, objets codants pour la production de protéines. De la même manière que les caractères physiques des êtres vivants évoluent au cours du temps, les caractères physiques des génomes évoluent également. Il s'agit alors de comprendre cette évolution à travers l'organisation des gènes sur le génome. Le problème peut être abordé sous un angle dynamique où l'on retrace les événements ayant permis les modifications, ou sous un angle statique en observant la localisation et le regroupement des gènes. D'autres part, les gènes nécessitent pour s'exprimer et se transformer en protéine, d'être d'abord transcrits en ARN. Le mécanisme de contrôle de la transcription fait appel, entre autres, à des protéines qui viennent se fixer en amont du gène, sur l'ADN, en reconnaissant de courts motifs. Une tâche récurrente, précédant toute autre analyse, est de trouver les occurrences de ces motifs qui ont la particularité d'être courts et particulièrement dégénérés.
Nous retraçons le travail réalisé autour de ces deux problématiques biologiques : l'évolution de la structure des génomes et la localisation des motifs de fixation. Les méthodes mises en oeuvre relèvent de l'algorithmique discrète sur les permutations pour la première partie et sur les mots pour la seconde.
Mon domaine de recherche est l’Interaction Homme-Machine (IHM). Mes travaux dans ce domaine s’organisent autour de deux axes. Le premier axe concerne l’adaptation des interfaces hommes-machines. Je m’intéresse en particulier à la manière dont on peut concevoir et réaliser des interfaces qui pourront s’adapter, selon le contexte, aux utilisateurs et à leurs rôles, aux périphériques utilisés ou encore à la tâche à exécuter lors de l’interaction. Le deuxième axe concerne les interactions multimodales et multicanales. J’étudie plus particulièrement les interfaces couplant le vocal (aussi bien en entrée qu’en sortie), avec d’autres moyens d’interaction, notamment via le canal téléphonique. Cette HDR présente les problématiques liées à ces deux axes principaux de recherche, les travaux s’y rapportant auxquels j’ai participé depuis septembre 2000 et quelques perspectives de recherche dans ces thématiques.
