Oracles and queries that are sufficient for exact learning

Consultar RECERCAT

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/82131

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Bhousty, Nader H.
dc.contributor.author	Cleve, Richard
dc.contributor.author	Gavaldà Mestre, Ricard
dc.contributor.author	Kannan, Sampath
dc.contributor.author	Tamon, Christino
dc.date	1994-08
dc.identifier.citation	Bhousty, N., Cleve, R., Gavaldà, R., Kannan, S., Tamon, C. "Oracles and queries that are sufficient for exact learning". 1994.
dc.identifier.uri	http://hdl.handle.net/2117/82131
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Computational learning
dc.subject	DNF
dc.subject	NP-Oracle
dc.title	Oracles and queries that are sufficient for exact learning
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly learnable in randomized expected polynomial time with equivalence queries and the aid of an NP oracle. We also show that circuits are exactly learnable in deterministic polynomial time with equivalence queries and a Sigma-3 oracle. The paper also contains results on: learning of DNF formulas, learning with membership queries, and an application to Structural Complexity Theory.

Berral García, Josep Lluís; Poggi Mastrokalo, Nicolas; Alonso López, Javier; Gavaldà Mestre, Ricard; Torres Viñals, Jordi; Parashar, Manish

Gavaldà Mestre, Ricard; Universitat Politècnica de Catalunya.

Bifet Figuerol, Albert Carles; Holmes, Geoff; Pfahringer, Bernhard; Gavaldà Mestre, Ricard

Bifet Figuerol, Albert Carles; Holmes, Geoffrey; Pfahringer, Bernhard; Gavaldà Mestre, Ricard

Ruffini, Matteo; Casanellas Rius, Marta; Gavaldà Mestre, Ricard

Coordinació

Patrocini