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.

Compatible Worlds / B. Apolloni, S. Bassis, D. Malchiodi. - In: NONLINEAR ANALYSIS. - ISSN 0362-546X. - 71:12(2009 Dec), pp. e2883-e2901.

Compatible Worlds

B. Apolloni
Primo
;
S. Bassis
Secondo
;
D. Malchiodi
Ultimo
2009-12

Abstract

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.
Algorithmic inference; Compatibility measure; Complexity indices; Computational learning theory; Detail; Representation features; Support Vector Machines
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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/2434/69991
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact