Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Gavaldà, R.
Tipus d'activitat
Document cientificotècnic
Data
2009-05
Codi
LSI-09-16-R
Repositori
http://hdl.handle.net/2117/87921 Obrir en finestra nova
Resum
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).
Citació
Gavaldà, R. "Note: More efficient conversion of equivalence-query algorithms to PAC algorithms". 2009.
Paraules clau
Computational Learning, Equivalence Queries, Pac Learning
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants

Arxius