Note: More efficient conversion of equivalence-query algorithms to PAC algorithms

All of RECERCAT

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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor	Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
dc.contributor.author	Gavaldà Mestre, Ricard
dc.date	2009-05
dc.identifier.citation	Gavaldà, R. "Note: More efficient conversion of equivalence-query algorithms to PAC algorithms". 2009.
dc.identifier.uri	http://hdl.handle.net/2117/87921
dc.language.iso	eng
dc.relation	LSI-09-16-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Computational learning
dc.subject	Equivalence queries
dc.subject	PAC learning
dc.title	Note: More efficient conversion of equivalence-query algorithms to PAC algorithms
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	We present a method for transforming an Equivalence-query algorithm using Q queries into a PAC-algorithm using Q/epsilon + O( (Q^(2/3) / epsilon ) * log(Q / delta) examples in expectation. The method is a variation of that by Schuurmans and Greiner (1995) which provides, for each gamma>0, an algorithm using (1+gamma)Q/epsilon + O( (1/epsilon) * log(Q / delta) examples in expectation. In other words, we show that the constant in front of the dominating term Q/epsilon can be made 1+o(1).