Learning definite Horn formulas from closure queries
From MaRDI portal
Abstract: A definite Horn theory is a set of n-dimensional Boolean vectors whose characteristic function is expressible as a definite Horn formula, that is, as conjunction of definite Horn clauses. The class of definite Horn theories is known to be learnable under different query learning settings, such as learning from membership and equivalence queries or learning from entailment. We propose yet a different type of query: the closure query. Closure queries are a natural extension of membership queries and also a variant, appropriate in the context of definite Horn formulas, of the so-called correction queries. We present an algorithm that learns conjunctions of definite Horn clauses in polynomial time, using closure and equivalence queries, and show how it relates to the canonical Guigues-Duquenne basis for implicational systems. We also show how the different query models mentioned relate to each other by either showing full-fledged reductions by means of query simulation (where possible), or by showing their connections in the context of particular algorithms that use them for learning definite Horn formulas.
Recommendations
- Learning closed Horn expressions
- Construction and learnability of canonical Horn formulas
- Exact learning: on the boundary between Horn and CNF
- Learning with queries inside the class of unate \(k\)-quasi-Horn formulas
- Learning a subclass of \(k\)-quasi-Horn formulas with membership queries
- Learning orthogonal F-Horn formulas
- Bridging the gap between Horn clausal logic and description logics in inductive learning
- Probably approximately correct learning of Horn envelopes from queries
- Learning orthogonal F-Horn formulas
Cites work
- scientific article; zbMATH DE number 1470716 (Why is no real title available?)
- scientific article; zbMATH DE number 7635224 (Why is no real title available?)
- A Note on the Relationship between Different Types of Correction Queries
- A general dimension for query learning
- A theory of finite closure spaces based on implications
- Attribute exploration with background knowledge
- Canonical Horn representations and query learning
- Construction and learnability of canonical Horn formulas
- Learning DFA from Correction and Equivalence Queries
- Learning conjunctions of Horn clauses
- Learning from examples with unspecified attribute values.
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Minimum Covers in Relational Database Model
- Necessary and sufficient conditions for learning with correction queries
- On sentences which are true of direct unions of algebras
- Queries and concept learning
- Reasoning with models
- The decision problem for some classes of sentences without quantifiers
- When won't membership queries help?
Cited in
(8)- Learning orthogonal F-Horn formulas
- Construction and learnability of canonical Horn formulas
- Bounds on the size of PC and URC formulas
- Probably approximately correct learning of Horn envelopes from queries
- Canonical Horn representations and query learning
- Learning closed Horn expressions
- Learning a propagation complete formula
- From equivalence queries to PAC learning: the case of implication theories
This page was built for publication: Learning definite Horn formulas from closure queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507524)
