Active Learning of Recursive Functions by Ultrametric Algorithms

Authors: Rūsiņš Freivalds and Thomas Zeugmann.

Source: “SOFSEM 2014: Theory and Practice of Computer Science
40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings,”

(Viliam Geffert, Bart Preneel, Branislav Rovan, Július Štuller, and A Min Tjoa, Eds.), Lecture Notes in Computer Science 8327, pp. 246-257, Springer International Publishing Switzerland 2014.

Abstract. We study active learning of recursive functions by asking queries of the type “f(17)= ?”. The complexity measure in this paper is the worst-case number of queries asked. We prove that for some classes of recursive functions ultrametric active learning algorithms can achieve the learning goal by asking significantly fewer queries than deterministic, probabilistic, and even nondeterministic active learning algorithms. This is the first ever example of a problem where ultrametric algorithms have advantages over nondeterministic algorithms.

The research was supported by Grant No. 09.1570 from the Latvian Council of Science and the Invitation Fellowship for Research in Japan S12052 by the Japan Society for the Promotion of Science
©Copyright 2014, Springer

Valid HTML 4.1