Learning Unions of Tree Patterns Using Queries

Abstract

This paper characterizes the polynomial time learnability of TP ^ k , the class of collections of at most k first-order terms. A collection in TPA ^ k defines the union of the languages defined by each first-order terms in the set. Unfortunately, the class TP ^ k not polynomial time learnable in most of learning frameworks under standard assumptions in computational complexity theory. To overcome this computational hardness, we relax the learning problem by allowing a learning algorithm to make membership queries. We present a polynomial time algorithm that exactly learns every concept in TP ^ k using O(kn) equivalence and O(k ^2 n · max{ k, n }) membership queries, where n is the size of longest counterexample given so far. In the proof, we use a technique of replacing each restricted subset query by several membership queries under some condition on a set of function symbols. As corollaries, we obtain the polynomial time PAC-learnability and the polynomial time predictability of TP ^ k when membership queries are available. We also show a lower bound Ω(kn) of the number of queries necessary to learn TP ^ k using both types of queries. Further, we show that neither types of queries can be eliminated to achieve efficient learning of TP ^ k . Finally, we apply our results in learning of a class of restricted logic programs, called unit clause programs.