On the power of probabilistic strategies in inductive inference (Q760795): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:26, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the power of probabilistic strategies in inductive inference |
scientific article |
Statements
On the power of probabilistic strategies in inductive inference (English)
0 references
1984
0 references
The paper deals with probabilistic algorithms for inductive inference of programs solely from input/output examples. Let \(LIM_ n\) denote the family of all classes of recursive functions U limit identifiable with n changes of hypotheses in the following sense: there exists a deterministic Turing machine with input tape and output tape such that for every function \(f\in U\), starting the computation when exactly all the values f(0), f(1), f(2),... are written on the input tape in natural order, the machine never stops and on the output tape it writes a nonempty, finite sequence of at most \(n+1\) numbers, the last one of which being an f-program, i.e. an index of f in an acceptable Gödel numbering of partial recursive functions. For p \((1/2\leq p<1)\) let \(p\)-LIM\({}_ n\) denote the family of all classes U such that, with probability p, U is limit identifiable (by some probabilistic Turing machine) with n changes of hypotheses. It is proved that \(\cup_{n\in N}1/2-LIM_ n=\cup_{n\in N}LIM_ n\). However if the number of changes of hypotheses is a priori bounded then probabilistic identification strategies are more powerful than deterministic ones. Namely, it is shown that: (1) for every \(n\geq 2\) there is a class U such that U is in \((1- \epsilon)-LIM_ n\) for every \(\epsilon >0\), but \(U\not\in LIM_ n\); (2) for every \(n\geq 0\) and every p \((1/2\leq p<1)\), \(LIM_{\det (n,p)}\subseteq p-LIM_ n\), where \(\det (n,p)=\max \{k:\) \(k\leq ((n+1)/(p+\epsilon))-1\) for some \(\epsilon >0\}\); (3) for every \(n\geq 0\), \(LIM_{2n}\subset 1/2-LIM_ n\subset LIM_{8n+2}\). This last result shows both the strength and the weakness of probabilistic strategies with a priori bounded number of changes of hypotheses.
0 references
probabilistic algorithms
0 references
inductive inference of programs
0 references
recursive functions
0 references
Turing machine
0 references
Gödel numbering
0 references
probabilistic strategies
0 references