NeuroCOLT: Neural Networks and Computational Learning Theory

NeuroCOLT

Neural Networks and Computational Learning Theory

1994	1995
1996	1997
1998	1999
2000	2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-97-016

Decision Trees have Approximate Fingerprints

Victor Lavin
Universitat Politècnica de Catalunya, Spain

Vijay Raghavan
Vanderbilt University, USA

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.

Download Compressed Postscript