Dissertations / Theses on the topic 'Structures de données probabilistes'
To see the other types of publications on this topic, follow the link: Structures de données probabilistes.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Structures de données probabilistes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Perrin, Frédéric. "Prise en compte des données expérimentales dans les modèles probabilistes pour la prévision de la durée de vie des structures." Clermont-Ferrand 2, 2008. http://www.theses.fr/2008CLF21823.
Abstract:
La mécanique probabiliste est une discipline qui permet de tenir compte d'incertitudes concernant un système physique et d'étudier l'impact de ces incertitudes sur la réponse du modèle qui représente le système étudié. Dans certains cas, le point faible de la chaîne de calcul est la construction du modèle probabiliste des données d'entrées, souvent par absence ou manque de données sur ces paramètres. Dans le but de mieux évaluer l'aléa de la réponse d'un modèle, l'objectif majeur de la thèse est de développer un formalime général d'identification des modèles probabilistes à partir des données expérimentales disponibles directement ou indirectement. Dans ce contexte, on propose une formulation pour évaluer le vecteur aléatoire des paramètres d'entrée d'un modèle dans deux cas de figure. En phase de conception du système étudié, on s'intéresse à la prédiction de la variabilité globale de la réponse du modèle : il s'agit de traiter un problème inverse probabiliste. En phase de suivi de maintenance d'un système mécanique particulier, on souhaite actualiser la description probabiliste réalisée en phase de conception. La première partie de la thèse s'intéresse à des méthodes originales qui permettent d'identifier l'incertitude aléatoire portée par le vecteur d'entrée d'un modèle, dans le cas d'un problème inverse probaliste. La seconde partie de la thèse précise comment des méthodes bayésiennes peuvent être utilisées dans l'optique d'actualiser des modèles représentatifs de phénomènes évolutifs. Les méthodes d'identification probabilistes et d'actualisation sont finalement appliquées et validées sur des modèles représentatifs de structures sollicitées en fatigue
2
El, Abri Marwa. "Probabilistic relational models learning from graph databases." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4019/document.
Abstract:
Historiquement, les Modèles Graphiques Probabilistes (PGMs) sont une solution d’apprentissage à partir des données incertaines et plates, appelées aussi données propositionnelles ou représentations attribut-valeur. Au début des années 2000, un grand intérêt a été adressé au traitement des données relationnelles présentant un grand nombre d’objets participant à des différentes relations. Les Modèles Probabilistes Relationnels (PRMs) présentent une extension des PGMs pour le contexte relationnel. Avec l’évolution rapide issue de l’internet, des innovations technologiques et des applications web, les données sont devenues de plus en plus variées et complexes. D’où l’essor du Big Data. Plusieurs types de bases de données ont été créés pour s’adapter aux nouvelles caractéristiques des données, dont les plus utilisés sont les bases de données graphe. Toutefois, tous les travaux d’apprentissage des PRMs sont consacrés à apprendre à partir des données bien structurées et stockées dans des bases de données relationnelles. Les bases de données graphe sont non structurées et n’obéissent pas à un schéma bien défini. Les arcs entre les noeuds peuvent avoir des différentes signatures. En effet, les relations qui ne correspondent pas à un modèle ER peuvent exister dans l'instance de base de données. Ces relations sont considérées comme des exceptions. Dans ce travail de thèse, nous nous intéressons à ce type de bases de données. Nous étudions aussi deux types de PRMs à savoir, Direct Acyclic Probabilistic Entity Relationship (DAPER) et chaines de markov logiques (MLNs). Nous proposons deux contributions majeures. Premièrement, Une approche d’apprentissage des DAPERs à partir des bases de données graphe partiellement structurées. Une deuxième approche consiste à exploiter la logique de premier ordre pour apprendre les DAPERs en utilisant les MLNs pour prendre en considération les exceptions qui peuvent parvenir lors de l’apprentissage. Nous menons une étude expérimentale permettant de comparer nos méthodes proposées avec les approches déjà existantesHistorically, Probabilistic Graphical Models (PGMs) are a solution for learning from uncertain and flat data, also called propositional data or attributevalue representations. In the early 2000s, great interest was addressed to the processing of relational data which includes a large number of objects participating in different relations. Probabilistic Relational Models (PRMs) present an extension of PGMs to the relational context. With the rise of the internet, numerous technological innovations and web applications are driving the dramatic increase of various and complex data. Consequently, Big Data has emerged. Several types of data stores have been created to manage this new data, including the graph databases. Recently there has been an increasing interest in graph databases to model objects and interactions. However, all PRMs structure learning use wellstructured data that are stored in relational databases. Graph databases are unstructured and schema-free data stores. Edges between nodes can have various signatures. Since, relationships that do not correspond to an ER model could be depicted in the database instance. These relationships are considered as exceptions. In this thesis, we are interested by this type of data stores. Also, we study two kinds of PRMs namely, Direct Acyclic Probabilistic Entity Relationship (DAPER) and Markov Logic Networks (MLNs). We propose two significant contributions. First, an approach to learn DAPERs from partially structured graph databases. A second approach consists to benefit from first-order logic to learn DAPERs using MLN framework to take into account the exceptions that are dropped during DAPER learning. We are conducting experimental studies to compare our proposed methods with existing approaches
3
Fekete, Eric. "Etude probabiliste d'arbres issus de l'algorithmique." Versailles-St Quentin en Yvelines, 2007. http://www.theses.fr/2007VERS0016.
Abstract:
Cette thèse porte sur l’étude du comportement d’arbres aléatoires issus de l’algorithmique. Nous utilisons des techniques probabilistes pour étudier des objets aléatoires liés aux arbres. Outre le chapitre 1, dans lequel sont définis formellement plusieurs types d’arbres aléatoires et où sont introduits les résultats principaux, la thèse est composée de trois parties qui portent chacune sur l’étude d’un phénomène aléatoire. Nous établissons dans un premier temps un résultat sur l’asymptotique de la mesure d’occupation d’une marche aléatoire branchante dont l’arbre sous-jacent est un arbre binaire de recherche (ABR). Avec des hypothèses très faibles sur les incréments des marches, nous montrons que cette mesure, une fois renormalisée, converge vers une mesure déterministe qui est liée à la loi stable dont le domaine d’attraction contient la loi des incréments. La preuve de ce résultat repose, entre autres, sur les propriétés fondamentales de la structure des ABRs comme le résultat de Louchard sur la profondeur typique d’un noeud. Cette convergence permet alors d’obtenir des résultats sur des objets liés à l’ABR : les fragmentations homogènes de l’intervalle ]0, 1[ et les arbres récursifs. La deuxième étude traite aussi des ABRs. On s’intéresse au profil de l’arbre (nombre de feuilles à chaque profondeur) en regardant les feuilles selon les types définis par Dekking : les bras, feuilles dont le frère est un noeud interne, et les jambes, feuilles dont le frère est aussi une feuille. On utilise un vecteur dont les coordonnées sont les polynômes appelés polynômes de niveau des bras et des jambes. Les coefficients d’indice k des polynômes de niveau sont respectivement le nombre de bras et de jambes à la hauteur k dans l’ABR de taille n. On obtient, en comparant les deux projections du vecteur sur les sous-espaces propres de la matrice d’évolution, une convergence L2 et presque sûre d’une martingale vectorielle, liée au profil, vers un vecteur associé à la limite de la martingale de Jabbour. Enfin, le dernier chapitre concerne un autre type d’arbres, les tries des suffixes. Ces arbres sont définis à partir d’un mot infini et leur aléa est donné par la source qui génère ce mot. Nous considérons ici une source dynamique -mélangeante. Nous montrons que la hauteur de saturation de l’arbre à n clefs, renormalisée par ln n, converge presque sûrement vers une constante liée à la source. L’étude de ce paramètre se traduit naturellement comme un problème de temps d’apparition de mots que nous résolvons grâce aux travaux de Abadi et Vergne sur le sujetThe aim of this thesis is the study of the behavior of trees used in analysis of algorithms. We use probabilistic techniques to study various random objects connected with trees. We formally define the trees we deal with and introduce our main results in chapter one. Each of the three other parts of the thesis contains a specific random phenomenon. We first establish a result on the asymptotics of the rescaled occupation measure of a branching random walk on binary search trees (BSTs). Under weak hypothesis on the increments, we show that this measure converges to a deterministic measure depending on the stable law whose domain of attraction contains the law of the increments. The proof is based on some fundamental properties of the structure of BST. One of them is the result by Louchard on the height of a typical node. This convergence allows to obtain results on two other objects associated to the BST : homogeneous fragmentations of ]0, 1[ and recursive trees. The second study is also on BSTs. We study the profile of the tree (number of leaves at each level) specifying the types of the leaves : arms are the leaves whose brother is an internal node and feet are the leaves whose brother is also a leaf. We use a vector whose coordinates are the level polynomials of arms and feet. The coefficient of order k of these polynomials is the number of arms and feet at level k in the BST of size n. Comparing the two projections of this vector on the eigenspaces of a so-called evolution matrix, we obtain an almost sure and a L2-convergence of a martingale vector, connected to the profile, to a vector associated to the limit of the Jabbour martingale. Finally, the last part deals with another kind of random trees : the suffix trees. These trees are defined from an infinite word and its randomness is given by the source that creates the word. Here we are concerned with -mixing sources. We prove that the fill-up level of a suffix tree with n keys, normalized by log n, converges almost surely to a constant depending on the source. By definition of the suffix trees, the study of this parameter happens to be a word apparition time issue. We obtain the convergence using results of Abadi and Vergne in this field
4
Scholler, Rémy. "Analyse de données de signalisation mobile pour l’étude de la mobilité respectueuse de la vie privée : Application au secteur du transport routier de marchandises." Electronic Thesis or Diss., Bourgogne Franche-Comté, 2024. http://www.theses.fr/2024UBFCD001.
Abstract:
Les opérateurs de réseau mobile disposent d'une importante source de données issue des communications de l'ensemble des objets connectés (smartphones mais pas uniquement) avec le réseau. Ces données de signalisation constituent une source massive de données de localisation et sont régulièrement utilisées pour l'étude de la mobilité (humaine ou non). Cependant, les usages potentiels se heurtent à deux écueils majeurs: leur faible précision spatiotemporelle et leur caractère éminemment sensible au regard de la protection de la vie privée.Dans un premier temps, les travaux de cette thèse améliorent la connaissance de l'état de mobilité (immobile ou en mouvement), de la vitesse, de la direction de déplacement des objets connectés et de la route qu'ils empruntent sur une infrastructure de transport (routier ou ferré par exemple).Dans un second temps, nous montrons comment garantir la confidentialité de statistiques de mobilité produites en flux continu. L'utilisation de données de signalisation, qu'elle soient relatives à des utilisateurs ou à des objets connectés divers, est encadrée légalement. Pour l'étude de la mobilité, les opérateurs ont donc tendance à publier des statistiques anonymisées (données agrégées). Plus précisément, on cherche à calculer des statistiques de mobilité complexes et anonymisées ``à la volée'' à l'aide de méthodes de confidentialité différentielle et de structures de données probabilistes (telles que des filtres de Bloom).Enfin, dans un troisième temps, nous illustrons le potentiel des données de signalisation et des approches proposées dans ce manuscrit pour le calcul en temps quasi-réel de statistiques anonymes sur le transport routier de marchandises. Cependant, il ne s'agit ici que d'un exemple de ce qui pourrait s'appliquer à d'autres sujets d'analyses de comportements de populations et d'activités avec des enjeux de politiques publiques et économiques importantsMobile network operators have a significant data source derived from communications of all connected objects (not just smartphones) with the network. These signaling data is a massive source of location data and are regularly used for the mobility analysis. However, potential uses face two major challenges: their low spatiotemporal precision and their highly sensitive nature concerning privacy.In the first phase, the thesis work enhances the understanding of the mobility state (stationary or in motion), speed, direction of movement of connected objects, and the route they take on a transportation infrastructure (e.g., road or rail).In the second phase, we demonstrate how to ensure the confidentiality of continuously produced mobility statistics. The use of signaling data, whether related to users or various connected objects, is legally regulated. For the study of mobility, operators tend to publish anonymized statistics (aggregated data). Specifically, the aim is to calculate complex and anonymized mobility statistics "on the fly" using differential privacy methods and probabilistic data structures (such as Bloom filters).Finally, in the third phase, we illustrate the potential of signaling data and the proposed approaches in this manuscript for quasi-real-time calculation of anonymous statistics on road freight transport. However, this is just an example of what could apply to other subjects analyzing population behaviors and activities with significant public and economic policy implications
5
Boyer, Laurent. "Apprentissage probabiliste de similarités d'édition." Phd thesis, Université Jean Monnet - Saint-Etienne, 2011. http://tel.archives-ouvertes.fr/tel-00718835.
Abstract:
De nombreuses applications informatiques nécessitent l'utilisation de distances. Dans le cadre de données structurées, chaînes ou arbres, nous utilisons majoritairement la distance d'édition. Celle-ci correspond au nombre minimal d'opérations d'édition (insertion, délétion et substitution) nécessaire pour transformer la première donnée en la seconde. Suivant l'application traitée, il est possible de paramétrer la distance d'édition en associant à chaque opération d'édition un poids. Dans le cadre de ce manuscrit, nous proposons une technique d'apprentissage automatique supervisée pour apprendre les poids de la distance décrite précédemment. L'algorithme utilisé, appelé Expectation-Maximisation, maximise la vraisemblance des paramètres du modèle à l'aide d'un échantillon d'apprentissage composé de paires d'exemples considérés comme similaires. La première contribution de ce manuscrit est une extension de précédents travaux sur les chaînes aux arbres sous la forme de transducteur à un unique état. Nous montrons sur une tâche de reconnaissance de caractères manuscrits, l'efficacité de l'apprentissage par rapport à l'utilisation de poids non appris. La seconde est une approche sur les chaînes sous contraintes. Le modèle est représenté par un ensemble fini d'états dans lequel les transitions sont contraintes. Une contrainte est représentée par un ensemble fini de fonctions booléennes définies sur la chaîne d'entrée et une de ses positions. Nous utilisons notre modèle pour aborder une application de recherche de sites de facteur de transcription dans des séquences génomiques
6
Jabbour-Hattab, Jean. "Une approche probabiliste du profil des arbres binaires de recherche." Versailles-St Quentin en Yvelines, 2001. http://www.theses.fr/2001VERS002V.
Abstract:
Le sujet principal de cette thèse est l'étude asymptotique du profil des arbres binaires de recherche, c'est à dire la répartition des nuds de ces arbres par niveau de profondeur. Les résultats sont atteints en utilisant conjointement des techniques analytiques et probabilistes et s'étendent au cas des arbres binaires associés à l'algorithme classique de gestion d'équivalence" Union Find". Une étude porte également sur les arbres binaires de recherche multidimensionnels ou k-d arbres ; elle concerne une nouvelle méthode de choix des clés, imaginé par L. Devroye. Nous montrons que, avec cette méthode, le temps moyen mis par l'algorithme de Bentley pour répondre à une recherche d'orthogonale ou à une recherche de correspondances partielles est asymptotiquement optimal.
7
Barriot, Roland. "Intégration des connaissances biologiques à l'échelle de la cellule." Bordeaux 1, 2005. http://www.theses.fr/2005BOR13100.
Abstract:
Cette thèse dans le domaine de la bio-informatique porte sur la représentation et la confrontation des données biologiques. La disponibilité d'un nombre croissant de génomes complets et l'accumulation de résultats expérimentaux produits par des apprcohes post-séquençage à l'échelle de la cellule et à haut débit doivent permettre de mieux comprendre l'articulation entre les mécanismes moléculaires et les fonctions cellulaires. L'intégration de ces données volumineuses et hétérogènes permettra de progresser vers une meilleure connaissance du fonctionnement de la cellule. Nous présentons un cadre formel pour la présentation de ces données permettant leur intégration à l'échelle de la cellule en vue de leur confrontation et de leur recoupement afin d'établir des correspondances nouvelles entre les données. Notre approche repose sur la généralisation du concept de voisinage entre les objets biologiques et sa représentation en ensembles partiellement ordonnés. Nous définissons une mesure de similarité entre les ensemble qui nous permet de confronter des données hétérogènes en recherchant des ensembles similaires entre les ensembles composant différents voisinages. La mise en oeuvre de ces concepts est illustrée avec la conception du système BlastSets grâce auquel des résultats biologiques préliminaires ont permis de valider l'approche.
8
Mohamed, Hanène. "Etude probabiliste d'algorithmes en arbre." Paris 6, 2007. https://tel.archives-ouvertes.fr/tel-00270742.
Abstract:
Cette thèse est dédiée à l'étude d'une large classe d'algorithmes, appelés algorithmes en arbre. En utilisant une représentation probabiliste appropriée, le comportement asymptotique de tels algorithmes est analysé. L'approche unifie les études faites sur ces algorithmes ainsi que simplifie et généralise certains résultats établis dans le domaineIn this thesis a general class of tree algorithms is analyzed. It is shown that, by using an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily. This approach gives a unified probabilistic treatment of these questions. It simplifies and extends some of the results known in this domain
9
Mohamed, Hanene. "Étude Probabiliste d'Algorithmes en Arbre." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2007. http://tel.archives-ouvertes.fr/tel-00270742.
Abstract:
Cette thèse est dédiée à l'étude d'une large classe d'algorithmes, appelés algorithmes en arbre. En utilisant une représentation probabiliste appropriée, le comportement asymptotique de tels algorithmes est analysé. L'approche unifie les études faites sur ces algorithmes ainsi que simplifie et généralise certains résultats établis dans le domaine.
10
Reype, Christophe. "Modélisation probabiliste et inférence bayésienne pour l’analyse de la dynamique des mélanges de fluides géologiques : détection des structures et estimation des paramètres." Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0235.
Abstract:
L'analyse de données hydrogéochimiques a pour objectif d'améliorer la compréhension des échanges de matières entre sol et du sous-sol. Ce travail se concentre sur l'étude des interactions fluides-fluides au travers des systèmes de mélange de fluides et plus particulièrement de la détection des compositions des sources du mélange. La détection se fait au moyen d'un processus ponctuel : le modèle proposé se veut non supervisée et applicable à des données multidimensionnelles. Les connaissances physiques sur les mélanges et géologiques sur les données sont directement intégrés dans la densité de probabilité d'un processus ponctuel de Gibbs, qui distribue des configurations de points dans l'espace des données, appelé le modèle HUG. Les sources détectées forment la configuration de points qui maximise la densité de probabilité du modèle HUG. La densité de probabilité est connue sachant un paramètre choisi par l'utilisateur. Ces sources sont obtenues par un algorithme de type recuit simulé et des méthodes de type Monte-Carlo par Chaînes de Markov (MCMC). Le paramètre du modèle est estimé par une méthode de calcul bayésien approximatif (ABC). Tout d'abord, le modèle est appliqué sur des données synthétiques puis sur des données réelles. Le paramètre du modèle est ensuite estimé pour un jeu de données synthétiques avec les sources connues. Enfin, la sensibilité du modèle aux données, au paramètre et aux algorithmes est étudiéeThe analysis of hydrogeochemical data aims to improve the understanding of mass transfer in the sub-surface and the Earth’s crust. This work focuses on the study of fluid-fluid interactions through fluid mixing systems, and more particularly on the detection of the compositions of the mixing sources. The detection is done by means of a point process: the proposed model is unsupervised and applicable to multidimensional data. Physical knowledge of the mixtures and geological knowledge of the data are directly integrated into the probability density of a Gibbs point process, which distributes point patterns in the data space, called the HUG model. The detected sources form the point pattern that maximises the probability density of the HUG model. This probability density is known up to the normalization constant. The knowledge related to the parameters of the model, either acquired experimentally or by using inference methods, is integrated in the method under the form of prior distributions. The configuration of the sources is obtained by a simulated annealing algorithm and Markov Chain Monte Carlo (MCMC) methods. The parameters of the model are estimated by an approximate Bayesian computation method (ABC). First, the model is applied to synthetic data, and then to real data. The parameters of the model are then estimated for a synthetic data set with known sources. Finally, the sensitivity of the model to data uncertainties, to parameters choices and to algorithms set-up is studied
11
Souihli, Asma. "Interrogation des bases de données XML probabilistes." Thesis, Paris, ENST, 2012. http://www.theses.fr/2012ENST0046/document.
Abstract:
XML probabiliste est un modèle probabiliste pour les bases de données incertaines semi-structurées, avec des applications telles que l'intégration incertaine de données, l'extraction d'informations ou le contrôle probabiliste de versions. Nous explorons dans cette thèse une solution efficace pour l'évaluation des requêtes tree-pattern avec jointures sur ces documents, ou, plus précisément, pour l'approximation de la probabilité d'une requête booléenne sur un document probabiliste. L'approche repose sur, d'une part, la production de la provenance probabiliste de la requête posée, et, d'autre part, la recherche d'une stratégie optimale pour estimer la probabilité de cette provenance. Cette deuxième partie s'inspire des approches des optimiseurs de requêtes: l'exploration de différents plans d'évaluation pour différentes parties de la formule et l'estimation du coût de chaque plan, suivant un modèle de coût établi pour les algorithmes de calcul utilisés. Nous démontrons l'efficacité de cette approche sur des jeux de données utilisés dans des travaux précédents sur l'interrogation des bases de données XML probabilistes, ainsi que sur des données synthétiquesProbabilistic XML is a probabilistic model for uncertain tree-structured data, with applications to data integration, information extraction, or uncertain version control. We explore in this dissertation efficient algorithms for evaluating tree-pattern queries with joins over probabilistic XML or, more specifically, for approximating the probability of each item of a query result. The approach relies on, first, extracting the query lineage over the probabilistic XML document, and, second, looking for an optimal strategy to approximate the probability of the propositional lineage formula. ProApproX is the probabilistic query manager for probabilistic XML presented in this thesis. The system allows users to query uncertain tree-structured data in the form of probabilistic XML documents. It integrates a query engine that searches for an optimal strategy to evaluate the probability of the query lineage. ProApproX relies on a query-optimizer--like approach: exploring different evaluation plans for different parts of the formula and predicting the cost of each plan, using a cost model for the various evaluation algorithms. We demonstrate the efficiency of this approach on datasets used in a number of most popular previous probabilistic XML querying works, as well as on synthetic data. An early version of the system was demonstrated at the ACM SIGMOD 2011 conference. First steps towards the new query solution were discussed in an EDBT/ICDT PhD Workshop paper (2011). A fully redesigned version that implements the techniques and studies shared in the present thesis, is published as a demonstration at CIKM 2012. Our contributions are also part of an IEEE ICDE
12
Souihli, Asma. "Interrogation des bases de données XML probabilistes." Electronic Thesis or Diss., Paris, ENST, 2012. http://www.theses.fr/2012ENST0046.
Abstract:
XML probabiliste est un modèle probabiliste pour les bases de données incertaines semi-structurées, avec des applications telles que l'intégration incertaine de données, l'extraction d'informations ou le contrôle probabiliste de versions. Nous explorons dans cette thèse une solution efficace pour l'évaluation des requêtes tree-pattern avec jointures sur ces documents, ou, plus précisément, pour l'approximation de la probabilité d'une requête booléenne sur un document probabiliste. L'approche repose sur, d'une part, la production de la provenance probabiliste de la requête posée, et, d'autre part, la recherche d'une stratégie optimale pour estimer la probabilité de cette provenance. Cette deuxième partie s'inspire des approches des optimiseurs de requêtes: l'exploration de différents plans d'évaluation pour différentes parties de la formule et l'estimation du coût de chaque plan, suivant un modèle de coût établi pour les algorithmes de calcul utilisés. Nous démontrons l'efficacité de cette approche sur des jeux de données utilisés dans des travaux précédents sur l'interrogation des bases de données XML probabilistes, ainsi que sur des données synthétiquesProbabilistic XML is a probabilistic model for uncertain tree-structured data, with applications to data integration, information extraction, or uncertain version control. We explore in this dissertation efficient algorithms for evaluating tree-pattern queries with joins over probabilistic XML or, more specifically, for approximating the probability of each item of a query result. The approach relies on, first, extracting the query lineage over the probabilistic XML document, and, second, looking for an optimal strategy to approximate the probability of the propositional lineage formula. ProApproX is the probabilistic query manager for probabilistic XML presented in this thesis. The system allows users to query uncertain tree-structured data in the form of probabilistic XML documents. It integrates a query engine that searches for an optimal strategy to evaluate the probability of the query lineage. ProApproX relies on a query-optimizer--like approach: exploring different evaluation plans for different parts of the formula and predicting the cost of each plan, using a cost model for the various evaluation algorithms. We demonstrate the efficiency of this approach on datasets used in a number of most popular previous probabilistic XML querying works, as well as on synthetic data. An early version of the system was demonstrated at the ACM SIGMOD 2011 conference. First steps towards the new query solution were discussed in an EDBT/ICDT PhD Workshop paper (2011). A fully redesigned version that implements the techniques and studies shared in the present thesis, is published as a demonstration at CIKM 2012. Our contributions are also part of an IEEE ICDE
13
Périnel, Emmanuel. "Segmentation en analyse de données symboliques : le cas de données probabilistes." Paris 9, 1996. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1996PA090079.
Abstract:
Les méthodes de segmentation, ou d'arbre de décision, sont des techniques permettant d'expliquer une partition à priori d'une population d'objets décrite par des variables explicatives. Elles ont connu ces dernières années un net regain d'intérêt, aussi bien dans le domaine de la statistique que dans celui de l'apprentissage automatique en intelligence artificielle. Toutefois, ces méthodes sont souvent reconnues sensibles à une information dite imparfaite telle que, des erreurs de mesures, des imprécisions ou incertitudes, des jugements experts, ce phénomène résulte principalement du manque de flexibilité des langages de représentations employés pour décrire les objets étudiés, d'une part, et de la rigidité même du processus d'apprentissage (partitionnement récursif), d'autre part. Dans ce travail, nous proposons une méthodologie générale de construction d'arbre de décision appliquée à des données de nature probabiliste. Celles-ci sont représentées par des assertions probabilistes dans le contexte de l'analyse des données symboliques. Son langage de description, en offrant une représentation plus riche et complexe des objets étudiés, nous permet d'introduire plus de flexibilité dans le processus de segmentation. Le développement de l'arbre repose sur un critère de découpage basé sur la notion générale d'information ou de vraisemblance. La nature imprécise ou incertaine des données conduit, de façon naturelle, à la notion d'appartenance probabiliste des objets aux différents nœuds de l'arbre. La construction de l'arbre se présente alors sous la forme d'une succession de problèmes de mélange de lois de probabilité que l'on résout à l'aide d'un algorithme de type EM (espérance / maximisation). Nous faisons également le lien, dans un cadre probabiliste, entre la notion d'appartenance probabiliste précédente et celle consécutive à l'emploi d'une coupure souple ou floue. L'approche est illustrée sur un jeu de données médicales relatives à l'utilisation de marqueurs biologiques sur des types cellulaires, et dans l'objectif de caractériser le concept de système neuroendocrinien.
14
Ba, Mouhamadou Lamine. "Exploitation de la structure des données incertaines." Electronic Thesis or Diss., Paris, ENST, 2015. http://www.theses.fr/2015ENST0013.
Abstract:
Cette thèse s’intéresse à certains problèmes fondamentaux découlant d’un besoin accru de gestion des incertitudes dans les applications Web multi-sources ayant de la structure, à savoir le contrôle de versions incertaines dans les plates-formes Web à large échelle, l’intégration de sources Web incertaines sous contraintes, et la découverte de la vérité à partir de plusieurs sources Web structurées. Ses contributions majeures sont : la gestion de l’incertitude dans le contrôle de versions de données arborescentes en s’appuyant sur un modèle XML probabiliste ; les étapes initiales vers un système d’intégration XML probabiliste de sources Web incertaines et dépendantes ; l’introduction de mesures de précision pour les données géographiques et ; la conception d’algorithmes d’exploration pour un partitionnement optimal de l’ensemble des attributs dans un processus de recherche de la vérité sur des sources Web conflictuellesThis thesis addresses some fundamental problems inherent to the need of uncertainty handling in multi-source Web applications with structured information, namely uncertain version control in Web-scale collaborative editing platforms, integration of uncertain Web sources under constraints, and truth finding over structured Web sources. Its major contributions are: uncertainty management in version control of treestructured data using a probabilistic XML model; initial steps towards a probabilistic XML data integration system for uncertain and dependent Web sources; precision measures for location data and; exploration algorithms for an optimal partitioning of the input attribute set during a truth finding process over conflicting Web sources
15
Rigouste, Loïs. "Méthodes probabilistes pour l'analyse exploratoire de données textuelles." Phd thesis, Télécom ParisTech, 2006. http://pastel.archives-ouvertes.fr/pastel-00002424.
Abstract:
Nous abordons le problème de la classification non supervisée de documents par des méthodes probabilistes. Notre étude se concentre sur le modèle de mélange de lois multinomiales avec variables latentes thématiques au niveau des documents. La construction de groupes de documents thématiquement homogènes est une des technologies de base de la fouille de texte, et trouve de multiples applications, aussi bien en recherche documentaire qu'en catégorisation de documents, ou encore pour le suivi de thèmes et la construction de résumés. Diverses propositions récentes ont été faites de modèles probabilistes permettant de déterminer de tels regroupements. Les modèles de classification probabilistes peuvent également être vus comme des outils de construction de représentations numériques synthétiques d'informations contenues dans le document. Ces modèles, qui offrent des facilités pour la généralisation et l'interprétation des résultats, posent toutefois des problèmes d'estimation difficiles, dûs en particulier à la très grande dimensionnalité du vocabulaire. Notre contribution à cette famille de travaux est double: nous présentons d'une part plusieurs algorithmes d'inférence, certains originaux, pour l'estimation du modèle de mélange de multinomiales; nous présentons également une étude systématique des performances de ces algorithmes, fournissant ainsi de nouveaux outils méthodologiques pour mesurer les performances des outils de classification non supervisée. Les bons résultats obtenus par rapport à d'autres algorithmes classiques illustrent, à notre avis, la pertinence de ce modèle de mélange simple pour les corpus regroupant essentiellement des documents monothématiques.
16
Hillali, Younès. "Analyse et modélisation des données probabilistes : capacités et lois multidimensionnelles." Paris 9, 1998. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1998PA090015.
Abstract:
Ce travail traite de la réduction d’un tableau de données probabilistes. Nous présentons un modèle statistique qui permet de résumer les descriptions aléatoires d’une classe d’individus par rapport à toutes les variables descriptives, tout en conservant le caractère aléatoire de la description de chaque individu avec un minimum de perte d’information. Nous proposons plusieurs mesures de généralisation et de spécialisation stochastiques basées sur des opérateurs d’union ou d’intersection entre distributions de probabilité et sur des méthodes de construction de lois multi dimensionnelles à marges unidimensionnelles fixées. Nous montrons que ces mesures possèdent les mêmes propriétés que les mesures de capacité au sens de Choquet. Nous présentons également une nouvelle famille de lois multidimensionnelles paramétriques qui permet d’étendre le procédé de généralisation et de spécialisation à un tableau de données probabilistes de grande taille, dans lequel chaque individu est décrit par plusieurs variables aléatoires de dépendances quelconques. Nous proposons trois algorithmes d’estimation de ses paramètres et nous étudions leur comportement dans la pratique. A partir des mesures de généralisation et de spécialisation d’un tableau de données probabilistes, nous proposons une méthode de classification d’individus décrits par des lois de probabilité. Des éléments de recherche qui devraient permettre d’étendre ce travail à des données probabilistes plus complexes, par exemple à des tableaux de données où chaque case contient une loi multidimensionnelle, sont également présentés.
17
Febrissy, Mickaël. "Nonnegative Matrix Factorization and Probabilistic Models : A unified framework for text data." Electronic Thesis or Diss., Paris, CNAM, 2021. http://www.theses.fr/2021CNAM1291.
Abstract:
Depuis l’avènement du Big data, les techniques de réduction de la dimension sont devenues essentielles pour l’exploration et l’analyse de données hautement dimensionnelles issues de nombreux domaines scientifiques. En créant un espace à faible dimension intrinsèque à l’espace de données original, ces techniques offrent une meilleure compréhension dans de nombreuses applications de la science des données. Dans le contexte de l’analyse de textes où les données recueillies sont principalement non négatives, les techniques couramment utilisées produisant des transformations dans l’espace des nombres réels (par exemple, l’analyse en composantes principales, l’analyse sémantique latente) sont devenues moins intuitives car elles ne pouvaient pas fournir une interprétation directe. De telles applications montrent la nécessité de techniques de réduction de la dimensionnalité comme la factorisation matricielle non négative (NMF), utile pour intégrer par exemple, des documents ou des mots dans l’espace de dimension réduite. Par définition, la NMF vise à approximer une matrice non négative par le produit de deux matrices non négatives de plus faible dimension, ce qui aboutit à la résolution d’un problème d’optimisation non linéaire. Notons cependant que cet objectif peut être exploité dans le domaine du regroupement de documents/mots, même si ce n’est pas l’objectif de la NMF. En s’appuyant sur la NMF, cette thèse se concentre sur l’amélioration de la qualité du clustering de grandes données textuelles se présentant sous la forme de matrices document-terme très creuses. Cet objectif est d’abord atteint en proposant plusieurs types de régularisations de la fonction objectif originale de la NMF. En plaçant cet objectif dans un contexte probabiliste, un nouveau modèle NMF est introduit, apportant des bases théoriques pour établir la connexion entre la NMF et les modèles de mélange finis de familles exponentielles, ce qui permet d’offrir des régularisations intéressantes. Cela permet d’inscrire, entre autres, la NMF dans un véritable esprit de clustering. Enfin, un modèle bayésien de blocs latents de Poisson est proposé pour améliorer le regroupement de documents et de mots simultanément en capturant des caractéristiques de termes bruyants. Ce modèle peut être relié à la NMTF (Nonnegative Matrix Tri-Factorization) consacrée au co-clustering. Des expériences sur des jeux de données réelles ont été menées pour soutenir les propositions de la thèseSince the exponential growth of available Data (Big data), dimensional reduction techniques became essential for the exploration and analysis of high-dimensional data arising from many scientific areas. By creating a low-dimensional space intrinsic to the original data space, theses techniques offer better understandings across many data Science applications. In the context of text analysis where the data gathered are mainly nonnegative, recognized techniques producing transformations in the space of real numbers (e.g. Principal component analysis, Latent semantic analysis) became less intuitive as they could not provide a straightforward interpretation. Such applications show the need of dimensional reduction techniques like Nonnegative Matrix factorization (NMF) useful to embed, for instance, documents or words in the space of reduced dimension. By definition, NMF aims at approximating a nonnegative matrix by the product of two lower dimensionalnonnegative matrices, which results in the solving of a nonlinear optimization problem. Note however that this objective can be harnessed to document/word clustering domain even it is not the objective of NMF. In relying on NMF, this thesis focuses on improving clustering of large text data arising in the form of highly sparse document-term matrices. This objective is first achieved, by proposing several types of regularizations of the original NMF objective function. Setting this objective in a probabilistic context, a new NMF model is introduced bringing theoretical foundations for establishing the connection between NMF and Finite Mixture Models of exponential families leading, therefore, to offer interesting regularizations. This allows to set NMF in a real clustering spirit. Finally, a Bayesian Poisson Latent Block model is proposed to improve document andword clustering simultaneously by capturing noisy term features. This can be connected to NMTF (Nonnegative Matrix factorization Tri-factorization) devoted to co-clustering. Experiments on real datasets have been carried out to support the proposals of the thesis
18
Santha, Miklos. "Contributions à l'étude des structures aléatoires et des méthodes probabilistes." Paris 11, 1988. http://www.theses.fr/1988PA112057.
Abstract:
Cette thèse contient quelques contributions à l'étude des structures aléatoires et des méthodes probabilistes en informatique théorique. Certaines d'entre elles étudient les séquences aléatoires et les classes de complexité probabilistes, d'autres traitent des problèmes concrets. Nous introduisons un nouveau modèle mathématique des sources physiques aléatoires imparfaites et nous montrons comment transformer la sortie de ces sources en séquences quasi-aléatoires qu'on ne peut pas distinguer, dans un sens très fort, des séquences parfaitement aléatoires. Nous démontrons l'existence des générateurs de nombres pseudo-aléatoires pour réduire efficacement la probabilité d'erreur des algorithmes probabilistes. Nous présentons un résultat de séparation pour les systèmes de preuve interactifs probabilistes relativisés. Nous étudions dans un modèle probabiliste la distribution optimale des processeurs dans un réseau quand ceux-ci peuvent tomber en panne. Nous déterminons le rayon de certains graphes sur al phabets et nous obtenons des bornes sur la complexité en parallèle de la recherche dans les cubes multi-dimensionnels en utilisant des arguments probabilistesThis thesis contains a few contributions to the study of randomness and probabilistic methods in theoretical computer science. Some of them deal with random sequences and probabilistic complexity classes, the others with concrete problems. We introduce a new mathematical model of imperfect physical sources of randomness and we show how to convert the output of these sources into quasi-random sequences which are indistinguish able from truly random ones in a strong sense. We show the existence of pseudo-random number generators which can reduce efficiently the error probability in probabilistic algorithms. We present a separation result for the relativized interactive probabilistic proof-systems. We study in a probabilistic model the optimal distribution of processors in a network, when they are subject to failure. We compute the radius of certain graphs on alphabets and we obtain tight bounds on the parallel complexity of the searching problem in multi-dimensional cubes by using proba bilistic arguments
19
Santha, Miklos. "Contributions à l'étude des structures aléatoires et des méthodes probabilistes." Grenoble 2 : ANRT, 1988. http://catalogue.bnf.fr/ark:/12148/cb37618440v.
20
Gelgon, Marc. "Structuration statistique de données multimédia pour la recherche d'information." Habilitation à diriger des recherches, Université de Nantes, 2007. http://tel.archives-ouvertes.fr/tel-00450297.
Abstract:
L'unité du travail réside en ce qu'on s'intéresse à la recherche de structure dans les données numériques (issues de données multimédia), en vue d'y faciliter la recherche d'information. Le cadre méthodologique de la résolution est que nous privilégions ici celui des modèles probabi- listes, en particulier les mélanges de lois, et de l'estimation statistique associée. La recherche de structure implique que le jeu de données étudié est composé de sous-populations de caracté- ristiques distinctes : il s'agit de séparer et de caractériser ces sous-populations, deux problèmes fortement imbriqués. Les entités extraites et les attributs qu'on en leur associe seront alors directement utiles pour la recherche d'information.
21
Belazzougui, Djamal. "Structures compactes d'indexation de données." Paris 7, 2011. http://www.theses.fr/2011PA077190.
Abstract:
L'une des tâches les plus importantes en informatique est de pouvoir effectuer des requêtes sur des données. Une approche couramment utilisée pour accélérer les réponses aux requêtes consiste à faire une phase de prétraitement sur les données afin de construire une structure de données occupant un certain espace mémoire et permettant ensuite de répondre aux requêtes en un temps beaucoup plus rapide que si toutes les données originelles devaient être lues. Néanmoins cette approche peut poser des problèmes de performance au cas où la structure de données occupe beaucoup plus d'espace que les données originelles. Ainsi le domaine des structures de données compactes a pour objectif l'encodage des structures de données de sorte à ce qu'elles occupent un espace le plus compact possible tout en préservant un temps de réponse le plus petit possible. Notre premier résultat dans ce domaine est une structure de données compacte et rapide pour des requêtes consistant à trouver l'ensemble des occurrences des mots d'un dictionnaire donné dans un texte quelconque. Notre second résultat est une structure de données compacte et rapide, permettant de répondre à des recherches tolérantes à une erreur d'édition sur un dictionnaire donné à l'avance. Le résultat central de cette thèse est une nouvelle définition d'un nouveau genre de hachage parfait que nous appelons hachage parfait monotone. Dans les deux derniers chapitres nous présentons deux applications du hachage parfait monotone à l'amélioration de deux solutions existantes pour les problèmes de l'indexation de texte et de la recherche des k-plus-pertinents documentsOne of the most important task in Computing is to be able to answer to various queries on a given data. There exist two different ways for this task. The first one is to read the whole data for each query. This approach can be very slow if the data size is very large. The second approach is to do a preprocessing phase on the data and build a "data structure". Later a query is answered by accessing the data structure and possibly a small part of the original data. This approach usually answers to queries in time much smaller than the time needed to read all the data. In some cases, the data structure may occupy much more space than the original data. This could cause a major slowdown to the queries if the data structure becomes too large to fit in fast memory. The solution to this problem is to use some smart encoding of the data structure in such a way that the data structure becomes "compact" enough to fit in the available fast memory while retaining the fastest possible query time. The contribution of this thesis is to show several improvements to known compact data structures as well as new compact data structures. Most of our results are concerned with problems on strings. Our first result is a new compact and fast solution for the dictionary matching problem. Our second result is a compact and fast data structure for the 1-error approximate dictionary problem. Our third result which is a new kind of perfect hashing, we call "monotone minimal perfect hashing". In our last two results, we use the monotone minimal perfect hashing to improve known solutions for the text indexing and the full-text top-k document retrieval problems
22
Vrac, Mathieu. "Analyse et modélisation de données probabilistes par décomposition de mélange de copules et application à une base de données climatologiques." Phd thesis, Université Paris Dauphine - Paris IX, 2002. http://tel.archives-ouvertes.fr/tel-00002386.
Abstract:
Nous étendons les méthodes de décomposition de mélange de densités de probabilité au cas des données "fonctions de répartition", permettant ainsi de classifier ces fonctions et de modéliser une loi pour ces données fonctionnelles particulières. Cette loi est donnée par la notion de "fonctions de distribution de distributions" (FDD), basée sur la définition d'une fonction de répartition pour des variables aléatoires à valeurs dans un espace probabiliste. Les extensions sont effectuées en associant les FDD aux fonctions "copules" par le théorème de Sklar. Les copules "couplent" les fonctions de répartition à n dimensions (jointes) et à 1-dimension (marginales) d'un n-uplet de variables aléatoires. Nous regardons principalement une classe de copules paramétriques, les copules Archimédiennes, et proposons trois nouvelles méthodes d'estimation des paramètres dans le cas de copules multivariées : par coefficients de corrélation de Kendall, de Spearman, et par maximisation de la vraisemblance. L'association des FDD et des copules caractérise l'évolution des données fonctionnelles (i.e. la forme de ces fonctions) entre différents points à l'intérieur des classes pour chaque variable, et donne une mesure de dépendance entre les variables utilisées. Les méthodes sont tout d'abord développées pour une variable, puis divers généralisations sont proposées pour n dimensions. Certains points théoriques sont ensuite discutés, tels que la convergence de l'algorithme et le fait que la méthode par copules est une généralisation du cas classique. Une application de la méthode "approche classification" par copules est réalisée sur des données climatiques de l'atmosphère terrestre. Le but est la classification de "profils" atmosphériques et l'estimation de la loi sous-jacente des données. Les résultats sont comparés avec ceux de méthodes "classiques", prouvant ainsi les performances nettement supérieures de la méthode par décomposition de mélange de copules (DMC) et l'intérêt de l'utilisation des données probabilistes.
23
Arnst, Maarten. "Inversion de modèles probabilistes de structures à partir de fonctionsde transfert expérimentales." Phd thesis, Ecole Centrale Paris, 2007. http://tel.archives-ouvertes.fr/tel-00238573.
Abstract:
L'objectif de la thèse est de développer une méthodologie d'identification expérimentale de modèles probabilistes qui prédisent le comportement dynamique de structures. Nous focalisons en particulier sur l'inversion de modèles probabilistes à paramétrage minimal, introduits par Soize, à partir de fonctions de transfert expérimentales. Nous montrons d'abord que les méthodes classiques d'estimation de la théorie des statistiques mathématiques, telle que la méthode du maximum de vraisemblance, ne sont pas bien adaptées pour aborder ce problème. En particulier, nous montrons que des difficultés numériques, ainsi que des problèmes conceptuels dus au risque d'une mauvaise spécification des modèles, peuvent entraver l'application des méthodes classiques. Ces difficultés nous motivent à formuler l'inversion de modèles probabilistes alternativement comme la minimisation, par rapport aux paramètres recherchés, d'une fonction objectif, mesurant une distance entre les données expérimentales et le modèle probabiliste. Nous proposons deux principes de construction pour la définition de telles distances, basé soit sur la fonction de logvraisemblance, soit l'entropie relative. Nous montrons comment la limitation de ces distances aux lois marginales d'ordre bas permet de surmonter les difficultés mentionnées plus haut. La méthodologie est appliquée à des exemples avec des données simulées et à un problème en ingénierie civile et environnementale avec des mesures réelles.
24
Sellier, Alain. "Modélisations probabilistes du comportement de matériaux et de structures en génie civil." Cachan, Ecole normale supérieure, 1995. http://www.theses.fr/1995DENS0012.
Abstract:
Des méthodes de calcul basées sur la théorie des probabilités sont développées. Elles permettent d'étudier la sécurité de structures métalliques à assemblages semi-rigides et la sécurité de structures en béton arme. Ces méthodes sont également intéressantes pour la modélisation de matériaux hétérogènes. Elles permettent alors de développer une loi de comportement du béton intégrant des phénomènes aussi divers que la localisation des déformations, les effets d'échelle ou les mécanismes physico-chimiques de la réaction alcali-granulats
25
Sellier, Alain. "Modélisations probabilistes du comportement de matériaux et de structures en génie civil /." Cachan : Laboratoire de mécanique et technologie, 1995. http://catalogue.bnf.fr/ark:/12148/cb35814905t.
26
Siolas, Georges. "Modèles probabilistes et noyaux pour l'extraction d'informations à partir de documents." Paris 6, 2003. http://www.theses.fr/2003PA066487.
27
Jaillet, Léonard. "Méthodes probabilistes pour la planifcation réactive de mouvement." Phd thesis, Université Paul Sabatier - Toulouse III, 2005. http://tel.archives-ouvertes.fr/tel-00853031.
Abstract:
Malgré le franc succès des techniques de planification de mouvement au cours de ces deux dernières décennies, leur adaptation à des scènes comprenant à la fois des obstacles statiques et des obstacles mobiles s'est avérée limitée jusqu'ici. Une des raisons en est le coût associé à la mise à jour des structures de données précalculées afin de capturer la connexité de l'espace libre. Notre contribution principale concerne la proposition d'un nouveau planificateur capable de traiter ces problèmes d'environnements partiellement dynamiques composés à la fois d'obstacles statiques et d'obstacles mobiles.
28
Castelli, Aleardi Luca. "Représentations compactes de structures de données géométriques." Phd thesis, Ecole Polytechnique X, 2006. http://tel.archives-ouvertes.fr/tel-00336188.
Abstract:
Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.
29
Darlay, Julien. "Analyse combinatoire de données : structures et optimisation." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00683651.
Abstract:
Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.
30
Sierocinski, Thomas. "Méthodes probabilistes, floues et quantiques pour l'extraction de l'information biologique." Phd thesis, Université Rennes 1, 2008. http://tel.archives-ouvertes.fr/tel-00429878.
Abstract:
Les progrès des technologies de mesure et le séquençage des génomes, ont permis l'émergence, dans les années 1990, de techniques de mesure globale de l'expression génique, les puces à ADN. Ce type d'expérience, dit à " haut débit ", en raison du volume de données qu'elles génèrent nécessitent un traitement automatique pour l'interprétation des résultats. Dans ce but, de nombreuses approches ont été développées, essentiellement réparties en deux familles : les méthodes de classification supervisées et non supervisées. Nous présentons ici la distillation sémantique, une approche de classification non supervisée originale fondée sur un formalisme inspiré de la mesure physique en mécanique quantique permettant l'analyse des résultats d'analyse de puces à ADN. Cette méthode fournit à l'utilisateur une liste de gènes ordonnée par spécificité pour chaque échantillon biologique de l'expérience, décrivant ainsi chaque contexte cellulaire ainsi que l'influence de chaque gène dans ces contextes. Celleci a été mise à l'épreuve sur deux jeux de données : un jeu " tissus-spécifique " pour lequel notre méthode a correctement caractérisé les gènes spécifiques de chaque tissu, et un jeu de données cliniques de patients atteints de fibroses hépatiques à divers stades pour lequel la distillation sémantique a permis de trouver des signatures dans les voies métaboliques et les processus biologiques associés aux gènes spécifiques de chaque stade de la maladie.
31
GILLE-GENEST, ANNE. "Utilisation des methodes numeriques probabilistes dans les applications au domaine de la fiabilite des structures." Paris 6, 1999. http://www.theses.fr/1999PA066212.
Abstract:
La these a ete engagee afin de repondre au besoin de edf de maitriser les methodes de calcul des risques de defaillance pour des composants critiques des centrales nucleaires. Les objectifs de la these sont de fournir des recommandations sur l'utilisation des methodes probabilistes existantes et de reflechir a une amelioration de celles-ci. Deux types de methodes sont adaptees a l'evaluation des faibles probabilites de defaillance : les methodes faiblisses form-sorm et la simulation monte carlo. La difficulte est de determiner la methode la plus efficace pour un probleme considere, c'est a dire celle qui procure le meilleure compromis precision / temps de calcul. Les methodes de monte carlo, simple ou accelerees par des techniques de reduction de variance, sont etudiees a travers differentes applications reelles de edf : le modele de la plaque fissuree, celui de la rupture brutale de la cuve, le logiciel compromis sur la rupture des tubes de generateurs de vapeur et un modele de propagation par fatigue thermique. Un logiciel developpe dans le cadre de la these a permis de realiser de nombreux tests de simulation et de comparer les methodes. Les resultats menent a des recommandations sur leur utilisation selon les caracteristiques du modele etudie : choix de la methode la mieux adaptee, choix des parametres relatifs a la methode, validation des resultats. La seconde partie de la these comporte des resultats sur le tirage d'importance adaptatif. Un algorithme adaptatif de la densite d'importance est construit dans un espace discret. Il permet de definir une densite d'importance qui tend vers la densite optimale et qui mene a une acceleration de la convergence de l'estimateur. Une majoration de sa variance est alors de la forme klogn/n 2 et meme k/n 2 au lieu de 2/n pour la simulation non adaptative.
32
Bouklit, Mohamed. "Autour du graphe du web : modélisations probabilistes de l'internaute et sétection de structures de communauté." Montpellier 2, 2006. http://www.theses.fr/2006MON20096.
33
Fejoz, Loïc. "Développement prouvé de structures de données sans verrou." Phd thesis, Université Henri Poincaré - Nancy I, 2008. http://tel.archives-ouvertes.fr/tel-00594978.
Abstract:
Le sujet central de cette thèse est le développement d'une méthode dédiée à la preuve de structures de données sans verrou. La motivation première vient du constat que les programmes concurrents sont devenu monnaie courante. Ceci a été possible par l'apparition de nouvelles primitives de synchronisation dans les nouvelles architectures matérielles. La seconde motivation est la quête de logiciel prouvé et donc correct. La sûreté des logiciels est en effet devenue primordiale de par la diffusion des systèmes embarqués et enfouis. La méthode proposée est basée sur le raffinement et dédiée à la conception et la vérification d'algorithme non-bloquant, en particulier ceux sans verrou. La méthode a été formalisée et sa correction prouvée en Isabelle/HOL. Un outil a par ailleurs été développé afin de générer des obligations de preuves à destination des solveurs SMT et des prouveurs de théorèmes du premier ordre. Nous l'avons utilisé afin de vérifier certains de ces algorithmes.
34
Jaff, Luaï. "Structures de Données dynamiques pour les Systèmes Complèxes." Phd thesis, Université du Havre, 2007. http://tel.archives-ouvertes.fr/tel-00167104.
Abstract:
Mon travail porte sur la dynamique de certaines structures de données et sur les systèmes complexes. Nous avons présenté une approche de la combinatoire des tableaux et des permutations basée sur la dynamique. Cette approche, que nous appelons (Structures de Données Dynamiques) nous ouvrela porte vers des applications en économie via les systèmes complexes.
Les structures de données que nous avons étudiées sont les permutations qui ne contiennent pas de sous-suite croissante de longueur plus que deux, les tableaux de Young standards rectangles à deux lignes, les mots de Dyck et les codes qui lient ces structures de données.
Nous avons proposé un modèle économique qui modélise le bénéfice d'un compte bancaire dont l'énumération des configurations possible se fait à l'aide d'un code adapté. Une seconde application
concerne l'évolution de populations d'automate génétique . Ces populations sont étudiées par analyse spectrale et des expérimentations sont données sur des automates probabilistes dont l'évolution conduit à contrôler la dissipation par auto-régulation.
L'ensemble de ce travail a pour ambition de donner quelques outils calculatoires liés à la dynamique de structures de données pour analyser la complexité des systèmes.
35
Simacek, Jiri. "Vérification de programmes avec structures de données complexes." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00805794.
Abstract:
Les travaux décrits dans cette thèse portent sur le problème de vérification des systèmes avec espaces d'états infinis, et, en particulier, avec des structures de données chaînées. Plusieurs approches ont émergé, sans donner des solutions convenables et robustes, qui pourrait faire face aux situations rencontrées dans la pratique. Nos travaux proposent une approche nouvelle, qui combine les avantages de deux approches très prometteuses: la représentation symbolique a base d'automates d'arbre, et la logique de séparation. On présente également plusieurs améliorations concernant l'implementation de différentes opérations sur les automates d'arbre, requises pour le succès pratique de notre méthode. En particulier, on propose un algorithme optimise pour le calcul des simulations sur les systèmes de transitions étiquettes, qui se traduit dans un algorithme efficace pour le calcul des simulations sur les automates d'arbre. En outre, on présente un nouvel algorithme pour le problème d'inclusion sur les automates d'arbre. Un nombre important d'expérimentes montre que cet algorithme est plus efficace que certaines des méthodes existantes.
36
Auber, David. "Outils de visualisation de larges structures de données." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12607.
Abstract:
Cette thèse présente un ensemble de résultats théoriques et pratiques, applicables dans le cadre de la visualisation d'informations. La première partie présente l'étude précise d'une structure de données performante. Dans la deuxième partie, nous présentons une amélioration de l'algorithme de Carriere et Kazman dédié au dessin d'arbres en 3D. Puis, nous présentons un algorithme, de complexité mémoire linéaire, permettant la représentation hiérarchique de grands graphes. Dans la troisième partie, nous donnons une méthode de simplification de graphes que npous utilisons pour respecter les contraintes temporelles imposées par le système de perception humain. Nous démontrons certaines propriétés combinatoires du paramètre Strahler et nous en proposons une extension aux cartes pointées. La quatrième partie se consacre à l'étude de deux algorithmes de fragmentation de graphes. Le premier est dédié aux arbres et améliore les résultats obtenus par Herman et al. Le deuxième est consacré aux graphes généraux. Il permet, par exemple, dans le cadre de l'analyse de programmes informatiques d'extraire automatiquement des composants logiciels. L'originalité des deux algorithmes proposés est qu'ils reposent sur des paramètres combinatoires et sont ainsi utilisables sur de grandes structures. Enfin, nous concluons par une brève description de la plate-forme logicielle que nous avons élaborée pour permettre l'expérimentation de nos résultats.
37
Fejoz, Loïc. "Développement prouvé de structures de données sans verrou." Thesis, Nancy 1, 2009. http://www.theses.fr/2009NAN10022/document.
Abstract:
Le sujet central de cette thèse est le développement d'une méthode dédiée à la preuve de structures de données sans verrou. La motivation première vient du constat que les programmes concurrents sont devenu monnaie courante. Ceci a été possible par l'apparition de nouvelles primitives de synchronisation dans les nouvelles architectures matérielles. La seconde motivation est la quête de logiciel prouvé et donc correct. La sûreté des logiciels est en effet devenue primordiale de par la diffusion des systèmes embarqués et enfouis. La méthode proposée est basée sur le raffinement et dédiée à la conception et la vérification d'algorithme non-bloquant, en particulier ceux sans verrou. La méthode a été formalisée et sa correction prouvée en Isabelle/HOL. Un outil a par ailleurs été développé afin de générer des obligations de preuves à destination des solveurs SMT et des prouveurs de théorèmes du premier ordre. Nous l'avons utilisé afin de vérifier certains de ces algorithmesThe central topic of this thesis is the proof-based development of lock-free data-structure algorithms. First motivation comes from new computer architectures that come with new synchronisation features. Those features enable concurrent algorithms that do not use locks and are thus more efficient. The second motivation is the search for proved correct program. Nowadays embedded software are used everywhere included in systems where safety is central. We propose a refinement-based method for designing and verifying non-blocking, and in particular lock-free, implementations of data structures. The entire method has been formalised in Isabelle/HOL. An associated prototype tool generates verification conditions that can be solved by SMT solvers or automatic theorem provers for first-order logic, and we have used this approach to verify a number of such algorithms
38
Maria, Clément. "Algorithmes et structures de données en topologie algorithmique." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4081/document.
Abstract:
La théorie de l'homologie généralise en dimensions supérieures la notion de connectivité dans les graphes. Étant donné un domaine, décrit par un complexe simplicial, elle définit une famille de groupes qui capturent le nombre de composantes connexes, le nombre de trous, le nombre de cavités et le nombre de motifs équivalents en dimensions supérieures. En pratique, l'homologie permet d'analyser des systèmes de données complexes, interprétés comme des nuages de points dans des espaces métriques. La théorie de l'homologie persistante introduit une notion robuste d'homologie pour l'inférence topologique. Son champ d'application est vaste, et comprend notamment la description d'espaces des configurations de systèmes dynamiques complexes, la classification de formes soumises à des déformations et l'apprentissage en imagerie médicale. Dans cette thèse, nous étudions les ramifications algorithmiques de l'homologie persistante. En premier lieu, nous introduisons l'arbre des simplexes, une structure de données efficace pour construire et manipuler des complexes simpliciaux de grandes dimensions. Nous présentons ensuite une implémentation rapide de l'algorithme de cohomologie persistante à l'aide d'une matrice d'annotations compressée. Nous raffinons également l'inférence de topologie en décrivant une notion de torsion en homologie persistante, et nous introduisons la méthode de reconstruction modulaire pour son calcul. Enfin, nous présentons un algorithme de calcul de l'homologie persistante zigzag, qui est une généralisation algébrique de la persistance. Pour cet algorithme, nous introduisons de nouveaux théorèmes de transformations locales en théorie des représentations de carquois, appelés principes du diamant. Ces algorithmes sont tous implémentés dans la librairie de calcul GudhiThe theory of homology generalizes the notion of connectivity in graphs to higher dimensions. It defines a family of groups on a domain, described discretely by a simplicial complex that captures the connected components, the holes, the cavities and higher-dimensional equivalents. In practice, the generality and flexibility of homology allows the analysis of complex data, interpreted as point clouds in metric spaces. The theory of persistent homology introduces a robust notion of homology for topology inference. Its applications are various and range from the description of high dimensional configuration spaces of complex dynamical systems, classification of shapes under deformations and learning in medical imaging. In this thesis, we explore the algorithmic ramifications of persistent homology. We first introduce the simplex tree, an efficient data structure to construct and maintain high dimensional simplicial complexes. We then present a fast implementation of persistent cohomology via the compressed annotation matrix data structure. We also refine the computation of persistence by describing ideas of homological torsion in this framework, and introduce the modular reconstruction method for computation. Finally, we present an algorithm to compute zigzag persistent homology, an algebraic generalization of persistence. To do so, we introduce new local transformation theorems in quiver representation theory, called diamond principles. All algorithms are implemented in the computational library Gudhi
39
Senellart, Pierre. "XML probabiliste: Un modèle de données pour le Web." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2012. http://tel.archives-ouvertes.fr/tel-00758055.
Abstract:
Les données extraites du Web sont chargées d'incertitude: elles peuvent contenir des contradictions ou résulter de processus par nature incertains comme l'intégration de données ou l'extraction automatique d'informations. Dans cette thèse d'habilitation, je présente les modèles de données XML probabilistes, la manière dont ils peuvent être utilisés pour représenter les données du Web, et la complexité de différentes opérations de gestion de données sur ces modèles. Je donne un état de l'art exhaustif du domaine, en insistant sur mes propres contributions. Je termine par un résumé de mes futurs projets de recherche.
40
Gao, Yingzhong. "Modèles probabilistes et possibilistes pour la prise en compte de l'incertain dans la sécurité des structures." Phd thesis, Ecole Nationale des Ponts et Chaussées, 1996. http://pastel.archives-ouvertes.fr/pastel-00569129.
Abstract:
Cette thèse a pour cadre général l'étude de la sécurité des structures, sous un double aspect - probabiliste et possibiliste - de la modélisation des variabilités et incertitudes des variables de calcul introduites dans les états limites. Après avoir rappelé les expressions classiques de la sécurité des structures (approches semi-probabiliste et probabiliste), l'attention est portée sur la définition de pré-mesures de confiance pour l'évaluation du risque de dépassement d'états limites. Divers concepts relatifs à l'expression et à la modélisation des incertitudes sont rappelés, en accentuant les particularités des mesures de possibilité et leur positionnement vis-à-vis des mesures de probabilité. Les notions essentielles de la théorie probabiliste de la fiabilité sont également rappelées. Une démarche analogue à la théorie probabiliste de la fiabilité est choisie pour développer une nouvelle théorie de la fiabilité. Nommée théorie possibiliste de la fiabilité, elle adopte une démarche possibiliste de la modélisation des variabilités et incertitudes liées aux variables de calcul ; deux définitions importantes sont d'ailleurs données dans cette étude - celle de la possibilité de défaillance et celle de l'indice possibiliste de la fiabilité. Les similitudes théoriques entre les deux théories de la fiabilité sont nombreuses et une comparaison entre les approches est présentée, en illustrant d'exemples numériques. Les formulations théoriques sont données pour des états limites linéaires et non linéaires, n'introduisant que des variables distinctes et non liées modélisées par des intervalles flous. Les développements théoriques mettent en évidence des simplifications de calcul remarquables, puisque la détermination de l'indice possibiliste de fiabilité et de la possibilité de défaillance se limite à la recherche d'un minimum scalaire. Ceci est réalisé grâce à la règle des signes, dont le principe est détaillé et illustré. Un exemple concret concernant le calcul de la durée de vie en fatigue d'assemblages soudés, est enfin proposé pour illustrer la démarche possibiliste de la fiabilité. Un soin particulier a été apporté à la modélisation des incertitudes, en utilisant le concept de la régression floue.
41
Li, Xinran. "Evaluation et amélioration des méthodes de chaînage de données." Thesis, Clermont-Ferrand 1, 2015. http://www.theses.fr/2015CLF1MM02/document.
Abstract:
Le chaînage d’enregistrements est la tâche qui consiste à identifier parmi différentes sources de données les enregistrements qui concernent les mêmes entités. En l'absence de clé d’identification commune, cette tâche peut être réalisée à l’aide d’autres champs contenant des informations d’identifications, mais dont malheureusement la qualité n’est pas parfaite. Pour ce faire, de nombreuses méthodes dites « de chaînage de données » ont été proposées au cours des dernières décennies.Afin d’assurer le chaînage valide et rapide des enregistrements des mêmes patients dans le cadre de GINSENG, projet qui visait à mettre en place une infrastructure de grille informatique pour le partage de données médicales distribuées, il a été nécessaire d’inventorier, d’étudier et parfois d’adapter certaines des diverses méthodes couramment utilisées pour le chaînage d’enregistrements. Citons notamment les méthodes de comparaison approximative des champs d’enregistrement selon leurs épellations et leurs prononciations, les chaînages déterministe et probabiliste d’enregistrements, ainsi que leurs extensions. Ces méthodes comptent des avantages et des inconvénients qui sont ici clairement exposés.Dans la pratique, les champs à comparer étant souvent imparfaits du fait d’erreurs typographiques, notre intérêt porte particulièrement sur les méthodes probabilistes de chaînage d’enregistrements. L’implémentation de ces méthodes probabilistes proposées par Fellegi et Sunter (PRL-FS) et par Winkler (PRL-W) est précisément décrite, ainsi que leur évaluation et comparaison. La vérité des correspondances des enregistrements étant indispensable à l’évaluation de la validité des résultats de chaînages, des jeux de données synthétiques sont générés dans ce travail et des algorithmes paramétrables proposés et détaillés.Bien qu’à notre connaissance, le PRL-W soit une des méthodes les plus performantes en termes de validité de chaînages d’enregistrements en présence d’erreurs typographiques dans les champs contenant les traits d’identification, il présente cependant quelques caractéristiques perfectibles. Le PRL-W ne permet par exemple pas de traiter de façon satisfaisante le problème de données manquantes. Notons également qu’il s’agit d’une méthode dont l’implémentation n’est pas simple et dont les temps de réponse sont difficilement compatibles avec certains usages de routine. Certaines solutions ont été proposées et évaluées pour pallier ces difficultés, notamment plusieurs approches permettant d’améliorer l’efficacité du PRL-W en présence de données manquantes et d’autres destinées à optimiser les temps de calculs de cette méthode en veillant à ce que cette réduction du temps de traitement n’entache pas la validité des décisions de chaînage issues de cette méthodeRecord linkage is the task of identifying which records from different data sources refer to the same entities. Without the common identification key among different databases, this task could be performed by comparison of corresponding fields (containing the information for identification) in records to link. To do this, many record linkage methods have been proposed in the last decades.In order to ensure a valid and fast linkage of the same patients’ records for GINSENG, a research project which aimed to implement a grid computing infrastructure for sharing medical data, we first studied various commonly used methods for record linkage. These are the methods of approximate comparison of fields in record according to their spellings and pronunciations; the deterministic and probabilistic record linkages and their extensions. The advantages and disadvantages of these methods are clearly demonstrated.In practice, as fields to compare are sometimes subject to typographical errors, we focused on probabilistic record linkage. The implementation of these probabilistic methods proposed by Fellegi and Sunter (PRL-FS) and Winkler (PRL-W) is described in details, and also their evaluation and comparison. Synthetic data sets were used in this work for knowing the truth of matches to evaluate the linkage results. A configurable algorithm for generating synthetic data was therefore proposed.To our knowledge, the PRL-W is one of the most effective methods in terms of validity of linkages in the presence of typographical errors in the field. However, the PRL-W does not satisfactorily treat the missing data problem in the fields, and the implementation of PRL-W is complex and has a computational time that impairs its opportunity in routine use. Solutions are proposed here with the objective of improving the effectiveness of PRL-W in the presence of missing data in the fields. Other solutions are tested to simplify the PRL-W algorithm and both reduce computational time and keep and optimal linkage accuracy.Keywords:
42
Amoualian, Hesam. "Modélisation et apprentissage de dépendances á l’aide de copules dans les modéles probabilistes latents." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM078/document.
Abstract:
Ce travail de thése a pour objectif de s’intéresser à une classe de modèles hiérarchiques bayesiens, appelés topic models, servant à modéliser de grands corpus de documents et ceci en particulier dans le cas où ces documents arrivent séquentiellement. Pour cela, nous introduisons au Chapitre 3, trois nouveaux modèles prenant en compte les dépendances entre les thèmes relatifs à chaque document pour deux documents successifs. Le premier modèle s’avère être une généralisation directe du modèle LDA (Latent Dirichlet Allocation). On utilise une loi de Dirichlet pour prendre en compte l’influence sur un document des paramètres relatifs aux thèmes sous jacents du document précédent. Le deuxième modèle utilise les copules, outil générique servant à modéliser les dépendances entre variables aléatoires. La famille de copules utilisée est la famille des copules Archimédiens et plus précisément la famille des copules de Franck qui vérifient de bonnes propriétés (symétrie, associativité) et qui sont donc adaptés à la modélisation de variables échangeables. Enfin le dernier modèle est une extension non paramétrique du deuxième. On intègre cette fois ci lescopules dans la construction stick-breaking des Processus de Dirichlet Hiérarchique (HDP). Nos expériences numériques, réalisées sur cinq collections standard, mettent en évidence les performances de notre approche, par rapport aux approches existantes dans la littérature comme les dynamic topic models, le temporal LDA et les Evolving Hierarchical Processes, et ceci à la fois sur le plan de la perplexité et en terme de performances lorsqu’on cherche à détecter des thèmes similaires dans des flux de documents. Notre approche, comparée aux autres, se révèle être capable de modéliser un plus grand nombre de situations allant d’une dépendance forte entre les documents à une totale indépendance. Par ailleurs, l’hypothèse d’échangeabilité sous jacente à tous les topics models du type du LDA amène souvent à estimer des thèmes différents pour des mots relevant pourtant du même segment de phrase ce qui n’est pas cohérent. Dans le Chapitre 4, nous introduisons le copulaLDA (copLDA), qui généralise le LDA en intégrant la structure du texte dans le modèle of the text et de relaxer l’hypothèse d’indépendance conditionnelle. Pour cela, nous supposons que les groupes de mots dans un texte sont reliés thématiquement entre eux. Nous modélisons cette dépendance avec les copules. Nous montrons de manièreempirique l’efficacité du modèle copLDA pour effectuer à la fois des tâches de natureintrinsèque et extrinsèque sur différents corpus accessibles publiquement. Pour compléter le modèle précédent (copLDA), le chapitre 5 présente un modèle de type LDA qui génére des segments dont les thèmes sont cohérents à l’intérieur de chaque document en faisant de manière simultanée la segmentation des documents et l’affectation des thèmes à chaque mot. La cohérence entre les différents thèmes internes à chaque groupe de mots est assurée grâce aux copules qui relient les thèmes entre eux. De plus ce modèle s’appuie tout à la fois sur des distributions spécifiques pour les thèmes reliés à chaque document et à chaque groupe de mots, ceci permettant de capturer les différents degrés de granularité. Nous montrons que le modèle proposé généralise naturellement plusieurs modèles de type LDA qui ont été introduits pour des tâches similaires. Par ailleurs nos expériences, effectuées sur six bases de données différentes mettent en évidence les performances de notre modèle mesurée de différentes manières : à l’aide de la perplexité, de la Pointwise Mutual Information Normalisée, qui capture la cohérence entre les thèmes et la mesure Micro F1 measure utilisée en classification de texteThis thesis focuses on scaling latent topic models for big data collections, especiallywhen document streams. Although the main goal of probabilistic modeling is to find word topics, an equally interesting objective is to examine topic evolutions and transitions. To accomplish this task, we propose in Chapter 3, three new models for modeling topic and word-topic dependencies between consecutive documents in document streams. The first model is a direct extension of Latent Dirichlet Allocation model (LDA) and makes use of a Dirichlet distribution to balance the influence of the LDA prior parameters with respect to topic and word-topic distributions of the previous document. The second extension makes use of copulas, which constitute a generic tool to model dependencies between random variables. We rely here on Archimedean copulas, and more precisely on Franck copula, as they are symmetric and associative and are thus appropriate for exchangeable random variables. Lastly, the third model is a non-parametric extension of the second one through the integration of copulas in the stick-breaking construction of Hierarchical Dirichlet Processes (HDP). Our experiments, conducted on five standard collections that have been used in several studies on topic modeling, show that our proposals outperform previous ones, as dynamic topic models, temporal LDA and the Evolving Hierarchical Processes,both in terms of perplexity and for tracking similar topics in document streams. Compared to previous proposals, our models have extra flexibility and can adapt to situations where there are no dependencies between the documents.On the other hand, the "Exchangeability" assumption in topic models like LDA oftenresults in inferring inconsistent topics for the words of text spans like noun-phrases, which are usually expected to be topically coherent. In Chapter 4, we propose copulaLDA (copLDA), that extends LDA by integrating part of the text structure to the model and relaxes the conditional independence assumption between the word-specific latent topics given the per-document topic distributions. To this end, we assume that the words of text spans like noun-phrases are topically bound and we model this dependence with copulas. We demonstrate empirically the effectiveness of copLDA on both intrinsic and extrinsic evaluation tasks on several publicly available corpora. To complete the previous model (copLDA), Chapter 5 presents an LDA-based model that generates topically coherent segments within documents by jointly segmenting documents and assigning topics to their words. The coherence between topics is ensured through a copula, binding the topics associated to the words of a segment. In addition, this model relies on both document and segment specific topic distributions so as to capture fine-grained differences in topic assignments. We show that the proposed model naturally encompasses other state-of-the-art LDA-based models designed for similar tasks. Furthermore, our experiments, conducted on six different publicly available datasets, show the effectiveness of our model in terms of perplexity, Normalized Pointwise Mutual Information, which captures the coherence between the generated topics, and the Micro F1 measure for text classification
43
Bornard, Raphaël. "Approches probabilistes appliquées à la restauration numérique d'archives télévisées." Phd thesis, Ecole Centrale Paris, 2002. http://tel.archives-ouvertes.fr/tel-00657636.
Abstract:
Dans le contexte de la restauration d'archives, nous abordons dans cette thèse la suppression des défauts impulsifs (taches, "dropouts" vidéo). Les méthodes de détection et correction existantes sont limitées par les défaillances de l'estimation de mouvement dues à la présence de phénomènes naturels complexes. Nous cherchons à prendre en compte ces phénomènes que nous qualifions de mouvement pathologique. Pour les deux étapes de détection et de correction, une approche probabiliste est privilégiée et nos algorithmes sont exprimés à l'aide de champs de Markov paramétriques ou non-paramétriques. La méthode de détection que nous proposons s'inscrit dans le cadre de la théorie bayesienne de l'estimation. Nous considérons une fenêtre temporelle plus large que les trois images utilisées habituellement afin de mieux distinguer les défauts des mouvements pathologiques et éviter ainsi les fausses alarmes. Nous proposons également une méthode de correction dans les zones d'information manquante inspirée de travaux sur la synthèse de texture. Après généralisation aux images naturelles, nous intégrons ces approches dans un contexte spatio-temporel qui permet un repli implicite sur une correction spatiale lorsque le mouvement est trop complexe. Les méthodes proposées sont validées séparément puis intégrées dans un prototype complet de suppression des défauts impulsifs.
44
Claisse, Harry. "Structures chainées et environnement paginé." Compiègne, 1987. http://www.theses.fr/1987COMPI270.
Abstract:
Cette thèse est orientée vers les problèmes de structures de pointeurs. La première partie est consacrée à la recherche des éléments qui résultent de décisions de conception pouvant influencer l'efficacité de l'exécution de LISP dans un environnement paginé. Le problème se résume en une recherche de la réduction du nombre de défauts de pages. Nous utilisons pour cela un ensemble de mesures qui permettent de cerner les points cruciaux tels que : structure de l'espace virtuel, espace de travail, ramasse-miettes. Nous étudions plusieurs méthodes de stockage des symboles (chaînes de caractères permettant de repérer toute entité) pour en évaluer leurs performances. Toutes les conclusions tirées sont mises en application directement sur l'interrogation d'une base de données en exploitation l'UTCThis thesis discusses problems related to pointer data structures. The first part is concerned with results of design decisions that can influence execution efficiency in a paged LISP environment. The main problem can be summarized as a continuing search to reduce the number of page faults. Measurements are used to distinguish crucial points such as structure of core memory, working set sizes and garbage collection. We study several storage implementations of symbols (strings of characters identifying each entities) and we evaluate their performances. The conclusions are applied directly to query data base a used at UTC
45
Mebarki, Abdelkrim. "Implantation de structures de données compactes pour les triangulations." Phd thesis, Université de Nice Sophia-Antipolis, 2008. http://tel.archives-ouvertes.fr/tel-00336178.
Abstract:
La modélisation des objets géométriques est incontournable dans de nombreuses disciplines et applications. L'évolution des moyens l'acquisition et de stockage a produit une hausse énorme des volumes utilisés pour stocker ces objets. La réduction des tailles de ces volumes fait l'objet de plusieurs domaines de recherches ; comme la compression, qui vise à compresser le volume au maximum, et l'élaboration de structures théoriques compactes qui minimisent la taille nécessaire à la représentation. Le but de cette thèse est de concevoir, et d'évaluer des solutions pratiques et exploitables pour représenter defaçon compacte les triangulations. Pour ce faire, deux issues sont explorées : modifier la représentation interne en mémoire des objets géométriques, et redéfinir les types abstraits des objets géométriques correspondants. Une première solution consiste à utiliser des indices sur une taille arbitraire de bits, au lieu des références absolues. Les gains dépendent de la taille de la triangulation, et aussi de la taille du mot mémoire de la machine. Le handicap majeur est le coût élevé de la méthode en termes de temps d'exécution. Une deuxième piste consiste à utiliser des catalogues stables. L'idée consiste à regrouper les triangles dans des micro-triangulations, et de représenter la triangulation comme un ensemble de ces micro-triangulations. Le nombre des références multiples vers les sommets, et des références réciproques entre voisins est alors nettement réduit. Les résultats sont
prometteurs, sachant que le temps d'exécution n'est pas dramatiquement altéré par la modification des méthodes d'accés aux triangles. Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits par rapport aux références absolues. Les résultats de cette techniques sont encourageants, et peuvent être amplifiés par d'autres techniques comme le codage relatif des références, ou le partage de l'information géométrique des sommets sur les bords entre les différentes sous-triangulations. L'élaboration de structures compactes nécessite encore plus d'intérêts, et plusieurs pistes sont à explorer pour pouvoir arriver à des solutions plus économiques en termes d'espace mémoire.
46
Toss, Julio. "Algorithmes et structures de données parallèles pour applications interactives." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM056/document.
Abstract:
La quête de performance a été une constante à travers l'histoire des systèmes informatiques.Il y a plus d'une décennie maintenant, le modèle de traitement séquentiel montrait ses premiers signes d'épuisement pour satisfaire les exigences de performance.Les barrières du calcul séquentiel ont poussé à un changement de paradigme et ont établi le traitement parallèle comme standard dans les systèmes informatiques modernes.Avec l'adoption généralisée d'ordinateurs parallèles, de nombreux algorithmes et applications ont été développés pour s'adapter à ces nouvelles architectures.Cependant, dans des applications non conventionnelles, avec des exigences d'interactivité et de temps réel, la parallélisation efficace est encore un défi majeur.L'exigence de performance en temps réel apparaît, par exemple, dans les simulations interactives où le système doit prendre en compte l'entrée de l'utilisateur dans une itération de calcul de la boucle de simulation.Le même type de contrainte apparaît dans les applications d'analyse de données en continu.Par exemple, lorsque des donnes issues de capteurs de trafic ou de messages de réseaux sociaux sont produites en flux continu, le système d'analyse doit être capable de traiter ces données à la volée rapidement sur ce flux tout en conservant un budget de mémoire contrôlé.La caractéristique dynamique des données soulève plusieurs problèmes de performance tel que la décomposition du problème pour le traitement en parallèle et la maintenance de la localité mémoire pour une utilisation efficace du cache.Les optimisations classiques qui reposent sur des modèles pré-calculés ou sur l'indexation statique des données ne conduisent pas aux performances souhaitées.Dans cette thèse, nous abordons les problèmes dépendants de données sur deux applications différentes: la première dans le domaine de la simulation physique interactive et la seconde sur l'analyse des données en continu.Pour le problème de simulation, nous présentons un algorithme GPU parallèle pour calculer les multiples plus courts chemins et des diagrammes de Voronoi sur un graphe en forme de grille.Pour le problème d'analyse de données en continu, nous présentons une structure de données parallélisable, basée sur des Packed Memory Arrays, pour indexer des données dynamiques géo-référencées tout en conservant une bonne localité de mémoireThe quest for performance has been a constant through the history of computing systems. It has been more than a decade now since the sequential processing model had shown its first signs of exhaustion to keep performance improvements.Walls to the sequential computation pushed a paradigm shift and established the parallel processing as the standard in modern computing systems. With the widespread adoption of parallel computers, many algorithms and applications have been ported to fit these new architectures. However, in unconventional applications, with interactivity and real-time requirements, achieving efficient parallelizations is still a major challenge.Real-time performance requirement shows-up, for instance, in user-interactive simulations where the system must be able to react to the user's input within a computation time-step of the simulation loop. The same kind of constraint appears in streaming data monitoring applications. For instance, when an external source of data, such as traffic sensors or social media posts, provides a continuous flow of information to be consumed by an on-line analysis system. The consumer system has to keep a controlled memory budget and delivery fast processed information about the stream.Common optimizations relying on pre-computed models or static index of data are not possible in these highly dynamic scenarios. The dynamic nature of the data brings up several performance issues originated from the problem decomposition for parallel processing and from the data locality maintenance for efficient cache utilization.In this thesis we address data-dependent problems on two different application: one in physics-based simulation and other on streaming data analysis. To the simulation problem, we present a parallel GPU algorithm for computing multiple shortest paths and Voronoi diagrams on a grid-like graph. To the streaming data analysis problem we present a parallelizable data structure, based on packed memory arrays, for indexing dynamic geo-located data while keeping good memory locality
47
Yahia, Hussein. "Analyse des structures de données arborescentes représentant des images." Paris 11, 1986. http://www.theses.fr/1986PA112292.
Abstract:
Nous sommes conduits à introduire une notion d'image aléatoire qui permet, grâce à la technique des fonctions génératrices, d'obtenir les moments des principaux paramètres associes aux algorithmes manipulant de telles structures de données. Les modèles introduits sont suffisamment souples pour contenir virtuellement tous les modèles déjà existants. Nous analysons alors les performances des quadtrees et des octrees du point de vue de l'occupation mémoire puis nous étudions la complexité moyenne des algorithmes de recherche des voisins, de passage inter-représentations, et d'intersection ou de superposition d'images
48
Vincent, Céline. "Détection de structures tourbillonnaires par analyse de données directionnelles." Montpellier 2, 2007. http://www.theses.fr/2007MON20128.
49
Jaillet, Léonard. "Méthodes probabilistes pour la planification réactive de mouvements." Phd thesis, Université Paul Sabatier - Toulouse III, 2005. http://tel.archives-ouvertes.fr/tel-00011515.
Abstract:
Les techniques de planification de mouvement actuelles sont maintenant capables de résoudre des problèmes mettant en jeu des mécanismes complexes plongés au sein d'environnements encombrés. Néanmoins, l'adaptation de ces planificateurs à des scènes comprenant à la fois des obstacles statiques et des obstacles mobiles s'est avérée limitée jusqu'ici. Une des raisons en est le coût associé à la mise à jour des structures de données qui sont précalculées pour capturer la connexité de l'espace libre. Notre contribution principale concerne la proposition d'un nouveau planificateur capable de traiter des problèmes comprenant à la fois obstacles statiques et obstacles mobiles. Ce planificateur hybride combine deux grandes familles de techniques. D'une part les techniques dites PRM, initialement conçues pour résoudre des problèmes à requêtes multiples et que nous avons étendu à des problèmes de scènes dynamiques. D'autre part, de nouvelles techniques de diffusion, alors que celles-ci sont généralement dédiées aux problèmes simple requête ne nécessitant aucune opération de prétraitement. Les principaux développements accompagnant la construction de ce planificateur sont les suivants : - La proposition d'une architecture originale pour le planificateur dédié aux environnements changeants. Cette architecture inclut notamment plusieurs mécanismes dits d' "évaluation paresseuse" qui permettent de minimiser les test de collision et ainsi d'assurer de bonnes performances. - Le développement d'une nouvelle méthode de diffusion permettant de reconnecter localement certaines portions du réseau invalidées par la présence des obstacles mobiles. Cette méthode, appelée RRT à Domaine Dynamique correspond en fait une extension des planificateur bien connus à bases de RRTs. Un des intérêt propre à notre approche est d'équilibrer automatiquement deux comportements propres au planificateur : l'exploration vers des régions encore inconnues et l'affinage du modèle des régions de l'espac e déjà explorées. - Deux méthodes originales de création de réseaux cycliques qui servent à initialiser notre planificateur. La première assume que les obstacles mobiles sont confinés dans une région donnée, pour construire un réseau adapté aux différents types de changements de position possibles. La seconde est une méthode qui construit des réseaux appelés "réseaux de rétraction". A l'aide d'une structure de donnée de faible taille, cette structure parvient à capturer les différentes variétés de chemins de l'espace, à travers notamment chacune des classes d'homotopie de l'espace libre. Toutes ces méthodes sont implémentées au sein de la plate-forme de travail Move3D développée au LAAS-CNRS et sont évaluées sur différents types de systèmes mécaniques plongés au sein d'environnements 3D.
50
Rochd, El Mehdi. "Modèles probabilistes de consommateurs en ligne : personnalisation et recommandation." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4086.
Abstract:
Les systèmes de recherche ont facilité l’accès à l’information disponible sur le web à l’aide de mécanismes de collecte, d’indexation et de stockage de contenus hétérogènes.Ils génèrent des traces résultant de l’activité des internautes. Il s’agit ensuite d’analyser ces données à l’aide d’outils de data mining afin d’améliorer la qualité de réponse de ces systèmes ou de la personnaliser en fonction des profils des utilisateurs. Certains acteurs, comme la société Marketshot, se positionnent comme intermédiaires entre les consommateurs et les professionnels. Ils mettent en relation les acheteurs potentiels avec les grandes marques et leurs réseaux de distribution à travers leurs sites Internet d’aide à l’achat. Pour cela, ces intermédiaires ont développé des portails efficaces et stockent de gros volumes de données liées à l’activité des internautes sur leurs sites. Ces gisements de données sont exploités pour répondre favorablement aux besoins des internautes, ainsi qu’à ceux des professionnels qui cherchent à comprendre le comportement de leurs clients et anticiper leurs actes d’achats. C’est dans ce contexte, où on cherche à fouiller les données collectées du web, que se placent mes travaux de recherche. L’idée est de construire des modèles qui permettent d’expliciter une corrélation entre les activités des internautes sur les sites d’aide à l’achat et les tendances de ventes de produits dans la « vraie vie ». En effet, ma thèse se place dans le cadre de l’apprentissage probabiliste et plus particulièrement des modèles graphiques « Topic Models ». Elle consiste à modéliser les comportements des internautes à partir des données d’usages de sites webResearch systems have facilitated access to information available on the web using mechanisms for collecting, indexing and storage of heterogeneous content. They generate data resulting from the activity of users on Internet (queries, logfile). The next step is to analyze the data using data mining tools in order to improve the response’s quality of these systems, or to customize the response based on users’ profiles. Some actors, such as the company Marketshot, are positioned as intermediaries between consumers and professionals. Indeed, they link potential buyers with the leading brands and distribution networks through their websites. For such purposes, these intermediaries have developed effective portals, and have stored large volumes of data related to the activity of users on their websites. These data repositories are exploited to respond positively to the needs of users as well as those of professionals who seek to understand the behavior of their customers and anticipate their purchasing actions. My thesis comes within the framework of searching through the data collected from the web. The idea is to build models that explain the correlation between the activities of users on websites of aid for the purchase, and sales trends of products in « real life ». In fact, my research concerns probabilistic learning, in particular Topic Models. It involves modeling the users’ behavior from uses of trader websites