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

Ramil YarullinRamil Yarullin, Sergei ObiedkovSergei Obiedkov

Ramil Yarullin, Sergei Obiedkov
From equivalence queries to PAC learning: The case of implication theories
International Journal of Approximate Reasoning, 127:1–16, December 2020

Details
Bibtex

KurzfassungAbstract
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.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@article{YARULLIN20201,
title = {From equivalence queries to PAC learning: The case of implication theories},
journal = {International Journal of Approximate Reasoning},
volume = {127},
pages = {1-16},
year = {2020},
issn = {0888-613X},
doi = {https://doi.org/10.1016/j.ijar.2020.08.011},
url = {https://www.sciencedirect.com/science/article/pii/S0888613X20302176},
author = {Ramil Yarullin and Sergei Obiedkov},
keywords = {Attribute exploration, Concept learning, Formal concept analysis, Implications, PAC learning, Query learning},
abstract = {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.}
}