On the Usability of Probably Approximately Correct Implication Bases
This work addresses the usability of approximate methods in formal concept analysis for data mining applications, but it is incremental as it revisits and tests an existing notion.
The paper investigates whether probably approximately correct (PAC) implication bases can serve as practical substitutes for exact implication bases by evaluating their precision and recall on artificial and real-world datasets, finding that they can still capture meaningful knowledge.
We revisit the notion of probably approximately correct implication bases from the literature and present a first formulation in the language of formal concept analysis, with the goal to investigate whether such bases represent a suitable substitute for exact implication bases in practical use-cases. To this end, we quantitatively examine the behavior of probably approximately correct implication bases on artificial and real-world data sets and compare their precision and recall with respect to their corresponding exact implication bases. Using a small example, we also provide qualitative insight that implications from probably approximately correct bases can still represent meaningful knowledge from a given data set.