One-sided error probabilistic inductive inference and reliable frequency identification
type: Item
instance of: scholarly article
title: One-sided error probabilistic inductive inference and reliable frequency identification
zbMATH Open document ID: 0727.03028
DOI: 10.1016/0890-5401(91)90011-P
author: Efim Kinber
author: Thomas Zeugmann
published in: Information and Computation
publication date: 1991-01-01T00:00:00Z
review text: The paper deals with the inductive synthesis of programs for recursive functions. An inference machine is a recursive device which, when given more and more ordered pairs from the graph of some function, outputs more and more hypotheses, i.e. programs. There are many possible requirements on the sequence of these created programs. The paper deals with ``explanatory'' inference, where the sequence has to converge to a single program correctly computing the given function, as well as ``behaviorally correct'' inference, where all but finitely many programs have to satisfy the relevant correction criterion. Furthermore, the situation is considered where the sequence of programs is required to contain a correct hypothesis with a certain frequency only. A new notion of probabilistic inference, as well as a new concept of reliable identification are introduced. These two types of inference are related to each other and to previously defined modes of identification. One- sided error probabilistic inference is shown to coincide with reliable frequency identification. Four new infinite hierarchies of inferable functions are established and compared with known hierarchies. Although the paper is overburdened with results and is not completely self- contained, it reflects the present state of the theory of inductive inference. The paper may be also useful for those working with machine learning and abstract theory of program synthesis.
Mathematics Subject Classification ID: 03D80
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03D55
zbMATH DE Number: 4200187
zbMATH Keywords: automatic program synthesis
zbMATH Keywords: inductive synthesis of programs for recursive functions
zbMATH Keywords: inference machine
zbMATH Keywords: probabilistic inference
zbMATH Keywords: reliable identification
zbMATH Keywords: hierarchies of inferable functions
zbMATH Keywords: inductive inference
zbMATH Keywords: machine learning
zbMATH Keywords: abstract theory of program synthesis
reviewed by: Stasys Jukna
MaRDI profile type: Publication
cites work: Q3993187
cites work: Q4149719
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: Toward a mathematical theory of inductive inference
cites work: Periodicity in generations of automata
cites work: Comparison of identification criteria for machine inductive inference
cites work: Tradeoffs in the inductive inference of nearly minimal size programs
cites work: On the error correcting power of pluralism in BC-type inductive inference
cites work: Q3774988
cites work: Limiting recursion
cites work: Q3722485
cites work: Research in the theory of inductive inference by GDR mathematicians - A survey
cites work: Q4153600
cites work: Some natural properties of strong-identification in inductive inference
cites work: Probabilistic inductive inference
cites work: Q4096931
cites work: Q4096932
cites work: Q5573961
cites work: The Power of Pluralism for Automatic Program Synthesis
cites work: Q4170707
cites work: Q3329450
description: scientific article; zbMATH DE number 4200187