Probabilistic program synthesis
| dc.contributor.author | Podnieks, Karlis | |
| dc.date.accessioned | 2015-11-28T17:49:23Z | |
| dc.date.available | 2015-11-28T17:49:23Z | |
| dc.date.issued | 1977 | |
| dc.description.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. | en_US |
| dc.identifier.citation | K. Podnieks. Probabilistic programs synthesis. In: Theory of Algorithms and Programs, Vol. 3, Latvia State University, 1977, pp. 57–88 | en_US |
| dc.identifier.uri | https://dspace.lu.lv/dspace/handle/7/31217 | |
| dc.language.iso | rus | en_US |
| dc.publisher | Latvia State University | en_US |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.subject | machine learning | en_US |
| dc.subject | inductive inference | en_US |
| dc.subject | program synthesis | en_US |
| dc.title | Probabilistic program synthesis | en_US |
| dc.type | info:eu-repo/semantics/article | en_US |