Decision trees have approximate fingerprints

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/82909

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Lavín Puente, Víctor Angel
dc.contributor.author	Raghavan, Vijay
dc.date	1996-04
dc.identifier.citation	Lavin, V., Raghavan, V. "Decision trees have approximate fingerprints". 1996.
dc.identifier.uri	http://hdl.handle.net/2117/82909
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Decision trees
dc.subject	Aproximate fingerprint property
dc.subject	Computational learning
dc.title	Decision trees have approximate fingerprints
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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.