• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

From equivalence queries to PAC learning: The case of implication theories

Yarullin R., Obiedkov S.

In Angluin's exact-learning framework, equivalence queries can be simulated by stochastic equivalence testing to achieve a probably approximately correct identification of an unknown concept. We present an analysis of the number of samples that need to be generated in the process leading to a theoretical improvement on an earlier approach. We apply this modification to a previously known probably approximately correct algorithm for computing implication bases with an implication oracle and evaluate its performance in terms of the number of queries to the oracle on artificial and real-world data.