Inductive-deductive systems: a mathematical logic and statistical learning perspective

Nicolas Baskiotis 1 Michèle Sebag 1 Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : This document was only presented in a conference with no copyrighted proceedings. The theorems about incompleteness of arithmetic have often been cited as an argument against automatic theorem proving and expert systems. However, these theorems rely on a worst-case analysis, which might happen to be overly pessimistic with respect to real-world domain applications. For this reason, a new framework for a probabilistic analysis of logical complexity is presented in this paper. Specifically, the rate of non-decidable clauses and the convergence of a set of axioms toward the target one when the latter exists in the language are studied, by combining results from mathematical logic and from statistical learning. Two theoretical settings are considered, where learning relies respectively on Turing oracles guessing the provability of a statement from a set of statements, and computable approximations thereof. Interestingly, both settings lead to similar results regarding the convergence rate towards completeness.
Type de document :
Communication dans un congrès
CAP, 2007, Grenoble, France. 16 p., 2007
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00173259
Contributeur : Olivier Teytaud <>
Soumis le : lundi 1 novembre 2010 - 14:58:24
Dernière modification le : jeudi 10 mai 2018 - 02:06:30
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 07:39:39

Fichier

12530ds.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00173259, version 2

Collections

Citation

Nicolas Baskiotis, Michèle Sebag, Olivier Teytaud. Inductive-deductive systems: a mathematical logic and statistical learning perspective. CAP, 2007, Grenoble, France. 16 p., 2007. 〈inria-00173259v2〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

167