Compatible Worlds

We discuss a bridge way of inference between Agnostic Learning and Prior Knowledge based on an inference goal represented not by the attainment of truth but simply by a suitable organization of the knowledge we have accumulated on the observed data. In a framework where this knowledge is not definite, we smear it across a series of possible models that we characterize through a probability measure of effectively explaining the observed data which denotes their compatibility with them. We point out the main features and benefits of our approach w.r.t. the two direct competitors: namely, the frequentist and Bayesian approaches, representative respectively of agnostic and a priori knowledge paradigms. Then we explore in greater depth its implementation for learning Boolean functions, showing an unprecedented relation between complexity of the concept class to be learnt and some peculiarities of the features through which the inference problem is represented. Exploiting this relation allows us to compute concretely suitable upper bounds to the classification errors of these functions when they are learnt through a soft-margin kernel-based Support Vector Machine.