Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Publication date
1996-04
Abstract
We prove that decision trees exhibit the
"approximate fingerprint" property,
and therefore are not polynomially learnable
using only equivalence queries.
A slight modification of the proof
extends this result to several other representation classes
of boolean concepts which have been studied in
computational learning theory.
