Authors: Ilja Kucevalovs and Ojārs Krasts, Rūsiņš Freivalds and Thomas Zeugmann
Source: Parallel Processing Letters Vol. 24, Issue 2, 2014, 63 - 79.
Abstract. Probabilistic computations and frequency computations were invented for the same purpose, namely, to study possible advantages of technology involving random choices. Recently several authors have discovered close relationships of these generalizations of deterministic computations to computations taking advice. Various forms of computation taking advice were studied by Karp and Lipton (1982), Damm and Holzer (1995), and Freivalds (2010). In the present paper, we apply the nonconstructive, probabilistic, and frequency methods to an inductive inference paradigm originally due to Gold (1967) and investigate their impact on the resulting learning models. Several trade-offs with respect to the resulting learnability are shown.
Keywords: probabilistic computations; frequency computations; nonconstructive methods; algorithmic learning; inductive inference
* The research was supported by the project ERAF Nr.2DP/188.8.131.52/13/APIA/VIAA/027 and the Invitation Fellowship for Research in Japan S12052 by Japan Society for the Promotion of Science
©Copyright 2014, World Scientific