We investigate learning of classes of distributions over a discrete domain in a PAC context. We introduce two paradigms of PAC learning, namely absolute PAC learning, which is independent of the representation of the class of hypotheses, and PAC learning wrt the indexes, which heavily depends on such representations. We characterize non-computable learnability in both contexts. Then we investigate efficient learning strategies which are simulated by a polynomial-time Turing machine. One strategy is the frequentist one. According to this strategy, the learner conjectures a hypothesis which is as close as possible to the distribution given by the frequency relative to the examples. We characterize the classes of distributions which are absolutely PAC learnable by means of this strategy, and we relate frequentist learning wrt the indexes to the NP = RP problem. Finally, we present another strategy for learning wrt the indexes, namely learning by tests.

Magnoni, L., Mirolli, M., Montagna, F., & Simi, G. (2003). PAC learning of probability distributions over a discrete domain. THEORETICAL COMPUTER SCIENCE, 299(1-3), 37-63 [10.1016/S0304-3975(01)00265-1].

PAC learning of probability distributions over a discrete domain

Magnoni, L.;Mirolli, M.;Montagna, F.;Simi, G.
2003

Abstract

We investigate learning of classes of distributions over a discrete domain in a PAC context. We introduce two paradigms of PAC learning, namely absolute PAC learning, which is independent of the representation of the class of hypotheses, and PAC learning wrt the indexes, which heavily depends on such representations. We characterize non-computable learnability in both contexts. Then we investigate efficient learning strategies which are simulated by a polynomial-time Turing machine. One strategy is the frequentist one. According to this strategy, the learner conjectures a hypothesis which is as close as possible to the distribution given by the frequency relative to the examples. We characterize the classes of distributions which are absolutely PAC learnable by means of this strategy, and we relate frequentist learning wrt the indexes to the NP = RP problem. Finally, we present another strategy for learning wrt the indexes, namely learning by tests.
Magnoni, L., Mirolli, M., Montagna, F., & Simi, G. (2003). PAC learning of probability distributions over a discrete domain. THEORETICAL COMPUTER SCIENCE, 299(1-3), 37-63 [10.1016/S0304-3975(01)00265-1].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/7171
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo