Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 7 / Issue 9

available in:   PDF (253 kB) PS (171 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-007-09-0794


Efficient Measure Learning

Sandra Fontani (University of Siena, Italy)

Abstract: We study the problem of efficient identification of particular classes of p-time languages, called uniform. We require the learner to identify each language of such a class by constantly guessing, after a small number of examples, the same index for it. We present three identification paradigms based on different kind of examples: identification on informant (positive and negative information), measure identification (positive information in a probabilistic setting), identification with probability (positive and negative information in a probabilistic setting). In each case we introduce two efficient identification paradigms, called efficient and very efficient identification respectively. We characterize efficient identification on informant and with probability and, as a corollary, we show that the two identification paradigms are equivalent. A necessary condition is shown for very efficient identification on informant, which becomes sufficient if and only if P = NP. The same condition is sufficient for very efficient identiffication with probability if and only if NP=RP. We show that (very) efficient identification on informant and with probability are strictly stronger than (very) efficient measure identiffication.

Keywords: learning theory

Categories: I.2.6