Relating Simultaneous Learning and Simultaneous Estimation for Classes of Setsand Classes of Probabilities

摘要

We introduce two concepts, simultaneous learnability and simultaneousestimability, and describe their relation to each other. We also connect these notions with learnability (as commonly defined in computational learning literature) and the uniform estimation of probabilities via relative frequencies. Simultaneous learning involves the approximation of a class of sets from examples that are labelled by those sets. In contrast, simultaneous estimation entails approximating the probabilities of the sets in a class from examples that are labelled by those sets. In both cases, the examples are assumed to be distributed according to some member of a class of probabilities. The particular classes and sets and probabilities involved determine whether a certain level of approximation is attainable and, if so, the number of examples required.