Decision trees have approximate fingerprints

Autor:	Lavín Puente, Víctor Angel, Raghavan, Vijay
Přispěvatelé:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Jazyk:	angličtina
Rok vydání:	1996
Předmět:	Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC] Decision trees Computational learning Aproximate fingerprint property
Zdroj:	UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Recercat. Dipósit de la Recerca de Catalunya instname
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::529eca019f6bf98b94bba8ce984d5812 http://hdl.handle.net/2117/82909 Zobrazit plný text záznamu