2014年
Active Learning of Recursive Functions by Ultrametric Algorithms
SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE
- ,
- 巻
- 8327
- 号
- 開始ページ
- 246
- 終了ページ
- 257
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-319-04298-5_22
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
We study active learning of classes of recursive functions by asking value queries about the target function f, where f is from the target class. That is, the query is a natural number x, and the answer to the query is f(x). 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.
- リンク情報
- ID情報
-
- DOI : 10.1007/978-3-319-04298-5_22
- ISSN : 0302-9743
- Web of Science ID : WOS:000342283300022