Probabilistic program synthesis
Date
1977
Authors
Podnieks, Karlis
Journal Title
Journal ISSN
Volume Title
Publisher
Latvia State University
Abstract
The following model of inductive inference is considered. Arbitrary numbering tau = {tau_0, tau_1, tau_2, ... } of total functions N->N is fixed. A "black box" outputs the values f(0), f(1), ..., f(m), ... of some function f from the numbering tau. Processing these values by some algorithm (a strategy) F we try to identify a tau-index of f (i.e. a number n such that f = tau_n). Strategy F outputs hypotheses h_0, h_1, ..., h_m, ... If lim h_m = n and tau_n = f, we say that F identifies in the limit tau-index of f. The complexity of identification is measured by the number of mindchanges, i.e. by F_tau(f) = card{m | h_m <> h_{m+1} }. One can verify easily that for any numbering tau there exists a deterministic strategy F such that F_tau(tau_n) <= n for all n. This estimate is exact. In the current paper the corresponding exact estimate ln n + o(log n) is proved for probabilistic strategies.
Description
Keywords
machine learning , inductive inference , program synthesis
Citation
K. Podnieks. Probabilistic programs synthesis. In: Theory of Algorithms and Programs, Vol. 3, Latvia State University, 1977, pp. 57–88