ALCOMFT-TR-01-21

José Luis Balcázar, Jorge Castro and David Guijarro
A General Dimension for Exact Learning
Barcelona. Work package 1. March 2001.

Abstract: We introduce a new combinatorial dimension that gives a good approximation of the number of queries needed to learn in the exact learning model, no matter what set of queries is used. This new dimension generalizes previous dimensions providing upper and lower bounds for all sort of queries, and not for just example-based queries as in previous works. Our new approach gives also simpler proofs for previous results. We present specific applications of our general dimension for the case of unspecified attribute value queries, and show that unspecified attribute membership and equivalence queries are not more powerful than standard membeship and equivalence queries for the problem of learning DNF formulas.

Postscript file: ALCOMFT-TR-01-21.ps.gz (75 kb).