Collecte de connaissances cachées et du sens commun à partir de services web

In this thesis, we harvest knowledge of two different types from online resources . The first one is commonsense knowledge, i.e. intuitive knowledge shared by most people like ``the sky is blue''. We extract salient statements from query logs and question-answering by carefully designing question patterns. Next, we validate our statements by querying other web sources such as Wikipedia, Google Books, or image tags from Flickr. We aggregate these signals to create a final score for each statement. We obtain a knowledge base, QUASIMODO, which, compared to its competitors, has better precision and captures more salient facts.The other kind of knowledge we investigate is hidden knowledge, i.e. knowledge not directly given by a data provider. More concretely, some Web services allow accessing the data only through predefined access functions. To answer a user query, we have to combine different such access functions, i.e., we have to rewrite the query in terms of the functions. We study two different scenarios: In the first scenario, the access functions have the shape of a path, the knowledge base respects constraints called ``Unary Inclusion Dependencies'', and the query is atomic. We show that the problem is decidable in polynomial time, and we provide an algorithm with theoretical evidence. In the second scenario, we remove the constraints and create a new class of relevant plans called "smart plans". We show that it is decidable to find these plans and we provide an algorithm.In this thesis, we harvest knowledge of two different types from online resources . The first one is commonsense knowledge, i.e. intuitive knowledge shared by most people like ``the sky is blue''. We extract salient statements from query logs and question-answering by carefully designing question patterns. Next, we validate our statements by querying other web sources such as Wikipedia, Google Books, or image tags from Flickr. We aggregate these signals to create a final score for each statement. We obtain a knowledge base, QUASIMODO, which, compared to its competitors, has better precision and captures more salient facts.Dans cette thèse, nous collectons sur le web deux types de connaissances. Le premier porte sur le sens commun, i.e. des connaissances intuitives partagées par la plupart des gens comme ``le ciel est bleu''. Nous utilisons des logs de requêtes et des forums de questions-réponses pour extraire des faits essentiels grâce à des questions avec une forme particulière. Ensuite, nous validons nos affirmations grâce à d'autres ressources comme Wikipedia, Google Books ou les tags d'images sur Flickr. Finalement, nous groupons tous les signaux pour donner un score à chaque fait. Nous obtenons une base de connaissance, QUASIMODO, qui, comparée à ses concurrents, montre une plus grande précision et collecte plus de faits essentiels.Le deuxième type de connaissances qui nous intéresse sont les connaissances cachées, i.e. qui ne sont pas directement données par un fournisseur de données. En effet, les services web donnent généralement un accès partiel à l'information. Il faut donc combiner des méthodes d'accès pour obtenir plus de connaissances: c'est de la réécriture de requête. Dans un premier scénario, nous étudions le cas où les fonctions ont la forme d'un chemin, la base de donnée est contrainte par des "dépendences d'inclusion unitaires" et les requêtes sont atomiques. Nous montrons que le problème est alors décidable en temps polynomial. Ensuite, nous retirons toutes les contraites et nous créons un nouvelle catégorie pertinente de plans: les "smart plans". Nous montrons qu'il est décidable de les trouver