Probably approximately correct learning of Horn envelopes from queries
This work addresses a computational efficiency issue in formal concept analysis for researchers in machine learning and logic, though it is incremental as it modifies an existing algorithm.
The authors tackled the problem of learning Horn envelopes from queries, which previously required an exponential number of queries in worst-case scenarios, and developed a polynomial-time probably approximately correct algorithm to achieve this.
We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.