This paper presents a study on learning algorithms for relational pattern languages from positive examples, introducing a framework that unifies existing approaches. It offers a polynomial-time algorithm for learning relational patterns with bounded variable frequency, characterizes positive characteristic sets for learnability, and provides theoretical analysis of sample complexity bounds.
Key findings
A novel framework unifying existing approaches to pattern language learning under Gold's model.
A polynomial-time algorithm for learning relational patterns with bounded variable frequency.
Characterization of positive characteristic sets that guarantee learnability.
Theoretical analysis of sample complexity bounds, showing the teaching dimension as both upper and lower bounds on the number of examples required.
Limitations & open questions
The study focuses on restricted classes of relational patterns with bounded variable frequency and restricted relation types.
The practical applicability is demonstrated on synthetic and real-world datasets, but further validation on a broader range of datasets is needed.