Le travail présenté dans ce mémoire porte sur l’aide à la navigation pour un fauteuil intelligent. Le but est de réaliser un système de reconnaissance et de suivi de trajets. Ce travail s’inscrit dans le projet VAHM qui utilise des fauteuils électriques du commerce sur lesquels ont été ajoutés une série de capteurs et un calculateur. Le VAHM utilise différents comportements (suivi de direction, suivi de mur, évitement d’obstacles,...) pour contrôler le fauteuil et pour réagir à l’environnement. On étudie, en premier lieu, la possibilité d’utiliser l’enchaînement des comportements du fauteuil pour modéliser et reconnaître un trajet en utilisant les MMC. Cette méthode montre ses limites en ce qui concerne la généralisation du modèle à des trajets non appris. Puis l’utilisation des MMC-MD est alors étudiée en intégrant, en plus des comportements, des données provenant des capteurs. Cependant les essais montrent que la reconnaissance est meilleure en utilisant uniquement les données provenant des capteurs. Ceci qui nous a conduit à n’utiliser que les données provenant des capteurs dans la suite du projet pour réaliser la reconnaissance. L’algorithme CONDENSATION est alors utilisé. Il possède de nombreux avantages dont celui de ne pas avoir besoin de modèle complexe puisque un seul trajet de référence est nécessaire pour réaliser la reconnaissance. Ces modèles de trajets sont ensuite mis dans un réseau bayésien pour faciliter les transitions d’un modèle à l’autre. La dernière partie du mémoire présente les résultats de la mise en œuvre de la reconnaissance en conditions réelles sur le fauteuil VAHM 3 / The work presented in this thesis concerns navigation assistance for a smart wheelchair. We propose a new approach based on this behaviour based structure, aiming at assisting the user in a global way. The intelligent system relies on a modelisation of the most frequently used routes and assists the user when navigating by suggesting the next movement when the route has been recognised. The user will not have to change the direction, thus sparing him/her an action. This work is included in the VAHM project that use commercial electric wheelchair which is enhanced by several sensors and a calculator. The VAHM project is using a multi-agent control system. Different behaviours (direction following, wall following, obstacle avoidance ...) are designed react to the environment. At first, we tried to modelize and recognize behaviour sequences with HMM. This method showed its limits to generalize the recognition of unlearned trajectories. Then we used M-HMM (by adding sensor’s data) to achieve recognition. However, our tests show that the recognition is better by using only sensor’s data. These observations have conducted us to use only sensor’s data for the recognition. The CONDENSATION algorithm had been tested to perform recognition from sensor's data. This system earn numerous advantages including that it doesn’t need a complex model since only one reference trajectory is necessary to perform the recognition. Then these trajectory models have been put into a Bayesian network to facilitate transitions between models in order to recognize a long trajectory. The last part of this thesis presents recognition’s results in real conditions on the VAHM 3 wheelchair prototype

L'analyse statistique des séquences biologiques telles les séquences nucléotidiques (l'ADN et l'ARN) ou d'acides aminés (les protéines) nécessite la conception de différents modèles s'adaptant chacun à un ou plusieurs cas d'étude. Etant donnée la dépendance de la succession des nucléotides dans les séquences d'ADN, les modèles généralement utilisés sont des modèles de Markov. Le problème de ces modèles est de supposer l'homogénéité des séquences. Or, les séquences biologiques ne sont pas homogènes. Un exemple bien connu est la répartition en gc : le long d'une même séquence, alternent des régions riches en gc et des régions pauvres en gc. Pour rendre compte de l'hétérogénéité des séquences, d'autres modèles sont utilisés : les modèles de Markov cachés. La séquence est divisée en plusieurs régions homogènes. Les applications sont nombreuses, telle la recherche des régions codantes. Certaines particularités biologiques ne pouvant apparaître suivant ces modèles, nous proposons de nouveaux modèles, les chaînes de Markov régulées (DMM pour drifting Markov model). Au lieu d'ajuster une matrice de transition sur une séquence entière (modèle de Markov homogène classique) ou différentes matrices de transition sur différentes régions de la séquence (modèles de Markov cachés), nous permettons à la matrice de transition de varier (to drift) du début à la fin de la séquence. A chaque position t dans la séquence, nous avons une matrice de transition Πt/n(où n est la longueur de la séquence) éventuellement différente. Nos modèles sont donc des modèles de Markov hétérogènes contraints. Dans cette thèse, nous donnerons essentiellement deux manières de contraindre les modèles : la modélisation polynomiale et la modélisation par splines. Par exemple, pour une modélisation polynomiale de degré 1 (une dérive linéaire), nous nous donnons une matrice de départ Π0 et une matrice d'arrivée Π1 puis nous passons de l'une à l'autre en fonction de la position t dans la séquence : <br />Πt/n = (1-t/n) Π0 + t/n Π1.<br />Cette modélisation correspond à une évolution douce entre deux états. Par exemple cela peut traduire la transition entre deux régimes d'un chaîne de Markov cachée, qui pourrait parfois sembler trop brutale. Ces modèles peuvent donc être vus comme une alternative mais aussi comme un outil complémentaire aux modèles de Markov cachés. Tout au long de ce travail, nous avons considéré des dérives polynomiales de tout degré ainsi que des dérives par splines polynomiales : le but de ces modèles étant de les rendre plus flexibles que ceux des polynômes. Nous avons estimé nos modèles de multiples manières puis évalué la qualité de ces estimateurs avant de les utiliser en vue d'applications telle la recherche de mots exceptionnels. Nous avons mis en oeuvre le software DRIMM (bientôt disponible à http://stat.genopole.cnrs.fr/sg/software/drimm/, dédié à l'estimation de nos modèles. Ce programme regroupe toutes les possibilités offertes par nos modèles, tels le calcul des matrices en chaque position, le calcul des lois stationnaires, des distributions de probabilité en chaque position... L'utilisation de ce programme pour la recherche des mots exceptionnels est proposée dans des programmes auxiliaires (disponibles sur demande).<br />Plusieurs perspectives à ce travail sont envisageables. Nous avons jusqu'alors décidé de faire varier la matrice seulement en fonction de la position, mais nous pourrions prendre en compte des covariables tels le degré d'hydrophobicité, le pourcentage en gc, un indicateur de la structure des protéines (hélice α, feuillets β...). Nous pourrions aussi envisager de mêler HMM et variation continue, où sur chaque région, au lieu d'ajuster un modèle de Markov, nous ajusterions un modèle de chaînes de Markov régulées.

Cette thèse se situe à l'interface de la statistique et de la fouille de données. Elle est composée de trois parties indépendantes. Dans la première, nous cherchons à estimer l'ordre (le nombre d'États cachés) d'un modèle de Markov caché dont la distribution d'émission appartient à la famille exponentielle. Nous nous plaçons dans le cas où aucune borne supérieure sur cet ordre n'est connue a priori. Nous définissons deux estimateurs pénalisés pour cet ordre, l'un basé sur le maximum de vraisemblance et l'autre sur une statistique de mélange bayésien. Nous montrons la consistance forte de ces estimateurs. Dans la deuxième partie, nous extrayons des motifs séquentiels dont la fréquence est exceptionnellement élevée par rapport à un modèle de Markov. L'approche consiste à dénombrer dynamiquement toutes les positions possibles d'un motif au sein d'une séquence. Puis la fréquence observée est comparée à la fréquence attendue à l'aide d'un test binomial. Une procédure est utilisée pour tenir compte des tests multiples. Des expérimentations sont menées sur des bases synthétiques et des séquences de protéines. Enfin, dans la troisième partie, nous nous intéressons au calcul de l'estimateur à noyau de la densité. Les observations sont regroupées dans des structures hiérarchiques d'arbres binaires. Les calculs sont réalisés sur les nœuds, plutôt que sur les points, pour une plus grande efficacité. Nous effectuons le calcul sur un Échantillon de points de chaque nœud, au lieu de sa totalité, en utilisant des inégalités de concentration non-paramétriques pour contrôler l'erreur. Puis, nous proposons un nouveau parcours de l'arbre pour effectuer ces échantillonnages sur un nombre réduit de nœuds. Nous testons notre approche sur des jeux de données synthétiques. / This Ph.D thesis lies at the interface of statistics and data mining. It contains three independent parts. In the first one, we aim at estimating the order (the number of hidden states) of a Hidden Markov Model, whose emission distribution belongs to the exponential family. We suppose that no upper bound is known on this order. We define two penalised estimators for this order, one based on the maximum likelihood, an the other on a bayesian mixture statistic. We prove that both estimators are strongly consistent. In the second part, we extract sequential patterns of exceptional frequency given a Markov model. We first dynamically enumerate all the possible occurences of a pattern in a sequence. Then, the observed frequency is compared to the expected frequency using a binomial test. Multiple testing is taken into account. Experiments are led on synthetic databases and protein sequences. Finally, in the third chapter, we are interested in kernel density estimation. The observations are gathered in hierarchical structures called binary trees. Computations are done on nodes of trees, rather than on raw observations, for greater efficiency. We only take into account samples on each node, instead of all the observations, using a non-parametric concentration inequality to control the error. We also propose to only browse some parts of the tree. We test our approach on synthetic datasets.

Cette étude présente une méthode de structuration d'une vidéo utilisant des indices sonores et visuels. Cette méthode repose sur un modèle statistique de l'entrelacement temporel des plans de la vidéo. Le cadre général de la modélisation est celui des modèles de Markov cachés. Les indices visuels sont utilisés pour caractériser le type des plans. Les indices audio décrivent les événements sonores apparaissant durant un plan. La structure de la vidéo est représentée par un modèle de Markov caché hiérarchique, intégrant les informations a priori sur le contenu de la vidéo, ainsi que sur les règles d'édition. L'approche est validée dans le cadre des vidéos de tennis, ce dernier présentant une structure intrinsèque hiérarchique bien définie. En résultat de l'analyse de l'entrelacement temporel des différents types de plans, des scènes caractéristiques du tennis sont identifiées. De plus, chaque plan de la vidéo est assigné à un niveau de hiérarchie décrit en terme de point, jeu et set. Cette classification et segmentation simultanées de la structure globale de la vidéo peuvent être utilisées pour la création de résumés vidéo ou pour permettre une navigation non linéaire dans le document vidéo.

Cette thèse présente un traitement inspiré du fonctionnement du système auditif pour améliorer la reconnaissance vocale. Pour y parvenir, le signal de la parole est filtré par un banc de filtres et compressé pour en produire une représentation auditive. L'innovation de l'approche proposée se situe dans l'extraction des éléments acoustiques (formants, transitions et onsets ) à partir de la représentation obtenue. En effet, une combinaison de détecteurs composés de neurones à décharges permet de révéler la présence de ces éléments et génère ainsi une séquence d'événements pour caractériser le contenu du signal. Dans le but d'évaluer la performance du traitement présenté, la séquence d'événements est adaptée à un système de reconnaissance vocale conventionnel, pour une tâche de reconnaissance de chiffres isolés prononcés en anglais. Pour ces tests, la séquence d'événements agit alors comme une sélection de trames automatique pour la génération des observations (coefficients cepstraux). En comparant les résultats de la reconnaissance du prototype et du système de reconnaissance original, on remarque que les deux systèmes reconnaissent très bien les chiffres prononcés dans des conditions optimales et que le système original est légèrement plus performant. Par contre, la différence observée au niveau des taux de reconnaissance diminue lorsqu'une réverbération vient affecter les données à reconnaître et les performances de l'approche proposée parviennent à dépasser celles du système de référence. De plus, la sélection de trames automatique offre de meilleures performances dans des conditions bruitées. Enfin, l'approche proposée se base sur des caractéristiques dans le temps en fonction de la nature du signal, permet une sélection plus intelligente des données qui se traduit en une parcimonie temporelle, présente un potentiel fort intéressant pour la reconnaissance vocale sous conditions adverses et utilise une détection des caractéristiques qui peut être utilisée comme séquence d'impulsions compatible avec les réseaux de neurones à décharges.

Les machines électriques polyphasées présentent des avantages intrinsèques (fractionnement de la puissance, faible ondulation du couple) par rapport à leurs équivalents triphasés qui sont appréciés notamment pour la propulsion navale. Structurellement, ces machines disposent également de capacités de reconfiguration du fait des redondances offertes par leur grand nombre de phases. L'exploitation de ces capacités est susceptible d'augmenter leur sûreté de fonctionnement en adoptant des modes de marche dégradée. Les travaux présentés proposent une méthode permettant de quantifier la fiabilité de toute la chaine de conversion. Le convertisseur statique y est particulièrement étudié car ses composants constituent un point faible en matière de fiabilité dans le système polyphasé. Des bases virtuelles continues de ces composants sont développées afin de s'affranchir des effets de quantification. Les principaux facteurs de stress sont identifiés et intégrés dans l'évaluation des taux de défaillance des différents éléments du système. Les modèles de Markov sont exploités pour prendre en compte les effets des reconfigurations sur la fonction de fiabilité. Un critère couplant la performance et à la fiabilité est introduit afin de caractériser les modes de marche dégradée dans l'évaluation de la fiabilité du système. Des exemples d'application de la méthode sur des systèmes issus essentiellement de l'environnement maritime sont exposés en intégrant leur topologie, leur profil de mission et leur stratégie de commande, ceux-ci influençant fortement les facteurs de stress. Enfin une étude de sensibilité de l'impact de la variabilité des données d'entrée sur la fonction de fiabilité est proposée. / Electrical multi-phase machines exhibit intrinsic advantages (power subdivision, weak torque ripple) compared to 3-phase machines. Multi-phase machines are appreciated for marine propulsion. They own reconfiguration capabilities due to redundancy because of their high number of phases. Those capabilities are able to improve multi-phase machines reliability by using degraded modes. Presented work proposes a methodology to quantify the multi-phase system reliability. Static converter is particularly investigated as its components are a weak point in the system. Continuous virtual bases of the components are developed to prevent quantification effects. Main stressors are identified and included in the failure rates assessment of the different system components. Markov models are used to take into account the reconfiguration consequences onto the reliability function. A coupled criterion performance-reliability is introduced to characterize degraded modes into the reliability assessment. Examples of the method application from marine environment are exhibited including their topology, mission profile and control strategy, which strongly influence the stressors. A sensitivity analysis is proposed showing the input data scattering effect onto the reliability function.

Nous nous intéressons dans cette thèse à la planification pour les problèmes de prise de décision décentralisée séquentielle dans l'incertain. Dans le cadre centralisé, l'utilisation des formalismes MDP et POMDP a permis d'élaborer des techniques de planification efficaces. Le cadre Dec-POMDP permet de formaliser les problèmes décentralisés. Ce type de problèmes appartient à une autre classe de complexité que les problèmes centralisés. Pour cette raison, jusqu'à récemment, seuls de très petits problèmes pouvaient être résolus et uniquement pour des horizons très faibles. Des algorithmes heuristiques ont récemment été proposés pour traiter des problèmes de taille plus conséquente mais n'ont pas de preuve théorique de qualité de solution. Nous montrons comment une information heuristique sur le problème à résoudre représentée par une distribution de probabilité sur les croyances centralisées permet de guider la recherche approchée de politique. Cette information heuristique permet de formuler chaque étape de la planification comme un problème d'optimisation combinatoire. Cette formulation conduit à des politiques de meilleure qualité que les approches existantes. / In this thesis, we focus on planning in decentralised sequentialdecision taking in uncertainty. In the centralised case, the MDP andPOMDP frameworks leads to efficient planning algorithms. The Dec-POMDPframework is used to model decentralised problems. This kind ofproblems is in a higher class of complexity than the centralisedproblem. For this reason, until recently, only very small problem could be solved and only for very small horizons. Recently, some heuristic algorithms have been proposed to handle problem of higher size but there is no theoretic proof of the solution quality. In this thesis, we show how to use a heuristic information in the problem, modelled as a probability distribution on the centralised beliefs, to guide the search for a good approximate policy. Using this heuristic information, we formulate each time step of the planning procedure as a combinatorial optimisation problem. This formulation leads to policies of better quality than previously existing approaches.

Les modèles de Markov cachés (MMC) par exemple ceux de la librairie Pfam sont des outils très populaires pour l'annotation des domaines protéiques. Cependant, ils ne sont pas toujours adaptés aux protéines les plus divergentes. C'est notamment le cas avec Plasmodium falciparum (principal agent du paludisme chez l'Homme), où les MMC de Pfam identifient peu de familles distinctes de domaines, et couvrent moins de 50% des protéines de l'organisme. L'objectif de cette thèse est d'apporter des méthodes nouvelles pour affiner la détection de domaines dans les protéines divergentes.Le premier axe développé est une approche d'identification de domaines utilisant leurs propriétés de co-occurrence. Différentes études ont montré que la majorité des domaines apparaissent dans les protéines avec un ensemble très réduits d'autres domaines favoris. Notre méthode exploite cette propriété pour détecter des domaines trop divergents pour être identifiés par l'approche classique. Cette détection s'accompagne d'une estimation du taux d'erreur par une procédure de ré-échantillonnage. Chez P. falciparum, elle permet d'identifier, avec un taux d'erreur estimé inférieur à 20%, 585 nouveaux domaines dont 159 familles étaient inédites dans cet organisme ce qui représente 16% du nombre de domaines connus.Le second axe de mes recherches présente plusieurs méthodes de corrections statistiques et évolutives des MMC pour l'annotation d'organismes divergents. Deux types d'approches ont été proposées. D'un côté, nous intégrons aux alignements d'apprentissage des MMC, les séquences précédemment identifiés dans l'organisme cible ou ses proches relatifs. La limitation de cette solution est que seules des familles de domaines déjà connues dans le taxon peuvent ainsi être identifiées. Le deuxième type d'approche contourne cette limitation en corrigeant tous les modèles par une prise en compte de l'évolution des séquences d'apprentissage. Pour cela, nous faisons appel à des techniques classiques de la bioinformatique et de l'apprentissage statistique. Les résultats obtenus offrent un ensemble de prédictions complémentaires totalisant 663 nouveaux domaines supplémentaires dont 504 familles inédites soit une augmentation de 18% à ajouter aux précédents résultats. / Hidden Markov Models (HMMs) from Pfam database for example are popular tools for protein domain annotation. However, they are not well suited for studying highly divergent proteins. This is notably the case with Plasmodium falciparum (main causal agent of human malaria), where Pfam HMMs identify few distinct domain families and cover less than 50% of its proteins. This thesis aims at providing new methods to enhance domain detection in divergent proteins.The first axis of this work is an approach of domain identification based on domain co-occurrence. Several studies shown that a majority of domains appear in proteins with a small set of other favourite domains. Our method exploits this tendency to detect domains escaping to the classical procedure because of their divergence. Detected domains come along with an false discovery rate (FDR) estimation computed with a shuffling procedure. In P. falciparum proteins, this approach allows us identify, with an FDR below 20%, 585 new domains with 159 families that were previously unseen in this organism which account for 16% of the known domains.The second axis of my researches involves the development of statistical and evolutionary methods of HMM correction to improve the annotation of divergent organisms. Two kind of approaches are proposed. On the one hand, the sequences previously identified in the target organism and its close relatives are integrated in the learning alignments. An obvious limitation of this solution is that only new occurrences of previously known families in the taxon can be discovered. On the other hand, we evade this limitation by adjusting HMM parameters by simulating the evolution of the learning sequences. To this end, classical techniques from bioinformatics and statistical learning were used. Alternative libraries offer a complementary set of predictions summing 663 new domains with 504 previously unseen families corresponding to an improvement of 18% to add to the previous results.

La conception d'outils de simulation capables de reproduire la dynamique et l'évolution de phénomènes complexes réels est une tâche difficile. La modélisation de ces phénomènes par des approches analytiques est souvent impossible, obligeant le concepteur à s'orienter vers des approches comportementales. Dans ce contexte, les simulations multi-agents représentent aujourd'hui une alternative crédible aux simulations classiques. Elles restent cependant délicates à mettre en œuvre. En effet, le concepteur de la simulation doit être capable de transcrire en comportement d'agents la dynamique du phénomène qu'il observe. Cette étape requiert généralement les compétences d'un spécialiste possédant une certaine expertise du phénomène à simuler. Dans cette thèse, nous proposons une manière originale de traiter l'observation de comportements réels à simuler, sans avoir recours à l'aide d'un expert.Il s'agit de s'appuyer sur des techniques d'apprentissage non supervisé pour identifier et extraire des comportements et ainsi faciliter l'agentification de la simulation. Notre approche constitue, de ce fait, un pas vers la conception automatique de simulations multi-agents reproduisant des phénomènes observables. Cette approche est motivée par un cadre applicatif visant la simulation de comportements de clients à l'intérieur d'un espace de vente. / The design of simulation tools, which are able to reproduce the dynamics and evolution of complex real phenomena, is hard. Modeling these phenomena by analytical approaches is often unsuitable, forcing the designer to turn towards behavioral approaches. In this context, multi-agent simulations are now a credible alternative to the classical simulations. However, they remain difficult to implement. In fact, the designer of the simulation must be able to transcribe the dynamic of the phenomenon being observed in agents behavior. This step usually requires the skills of a specialist with some expertise in the phenomenon to be simulated. In this thesis, we propose a novel way to treat observing real behaviors to simulate, without resorting to the help of an expert.It is relying on unsupervised learning techniques to identify and extract behavior and facilitate the agentification. Our approach is, therefore, a step towards the automatic design of multi-agent simulations reproducing observable phenomena. This approach is motivated by an application context aiming the simulation of customers’ behavior within a retail space.

Nous nous intéressons dans cette thèse à la planification pour les problèmes de prise de décision décentralisée séquentielle dans l'incertain. Dans le cadre centralisé, l'utilisation des formalismes MDP et POMDP a permis d'élaborer des techniques de planification efficaces. Le cadre Dec-POMDP permet de formaliser les problèmes décentralisés. Ce type de problèmes appartient à une autre classe de complexité que les problèmes centralisés. Pour cette raison, jusqu'à récemment, seuls de très petits problèmes pouvaient être résolus et uniquement pour des horizons très faibles. Des algorithmes heuristiques ont récemment été proposés pour traiter des problèmes de taille plus conséquente mais n'ont pas de preuve théorique de qualité de solution. Nous montrons comment une information heuristique sur le problème à résoudre représentée par une distribution de probabilité sur les croyances centralisées permet de guider la recherche approchée de politique. Cette information heuristique permet de formuler chaque étape de la planification comme un problème d'optimisation combinatoire. Cette formulation conduit à des politiques de meilleure qualité que les approches existantes.