|
Title:
|
The Consistency dimension and distribution-dependent learning from queries
|
|
Author:
|
Balcázar Navarro, José Luis; Castro Rabal, Jorge; Guijarro Guillem, David
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge |
|
Abstract:
|
We prove a new combinatorial characterization of polynomial
learnability from equivalence queries, and state some of its
consequences relating the learnability of a class with the
learnability via equivalence and membership queries of its
subclasses obtained by restricting the instance space.
Then we propose and study two models of query learning in which there
is a probability distribution on the instance space, both as an
application of the tools developed from the combinatorial
characterization and as models of independent interest. |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica
-Combinatorial characterization
-Polynomial learnability
-Query learning |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Report |
|
Share:
|
|
