A unified approach to learnability

We revisit the theory of Learnability of Valiant as a special topic of 'Order Statistics', where the concept to be learnt becomes a particular cutting function. This approach appears to be useful in two aspects: i) it gives a better understanding of the connections between the randomness of the data and their symbolic representation by concepts, ii) it allows to obtain some refinements and improvements of well known results in learnability theory. From a statistical point of view, we stress to new extents the idea coming from cryptography that a set of data behaves randomly or not depending on the complexity of the function these data refer to. From the other side, we realize a wide class of learnable concepts, and we revisit the notion of almost perfect hypothesis, which relaxes the conditions for learnability, allowing new statements around Natarajan and Vapnik–Chervonenkis dimensions