Efficient Measure Learning
Дата
Авторы
Fontani,Sandra
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
learning theory