Technical Reports

This thesis studies the complexity of learning logical expressions in the model of Exact Learning from Membership and Equivalence Queries. The focus is on Horn expressions in first order logic but results for propositional logic are also derived. The thesis includes several contributions towards characterizing the complexity of learning in these contexts. First, a new algorithm for learning first order Horn expressions is presented and proved correct. The algorithm improves on previous work in two ways. It can learn a larger class of expressions than previously known, and its query and time complexity improve on previous algorithms. In particular the algorithm can learn both the class of range-restricted expressions, and the class of constrained expressions, which were previously considered in the literature. Second, the thesis includes several lower bound results and techniques studying the optimal complexity of these learning problems, thus trying to identify whether it is possible to improve over the complexity of our algorithm. We study the VC Dimension of Horn expressions, a tool that gives lower bounds on query complexity in our model. Our results characterize exactly the VC Dimension of Horn expressions, providing the best lower bound possible using this technique. This technique leaves a gap to the upper bound provided by our algorithm. Our analysis also highlights problematic aspects of measuring learning complexity in first order logic that have been ignored in previous work. We study the Certificate Size, a tool that characterizes the query complexity of learning in our model. Our results give certificate constructions for several classes of important propositional expressions, including Horn CNF expressions. We also show that any certificate for a slight generalization of Horn CNF expressions, the class of renamable Horn CNF expressions, is of exponential size, thus showing that this class is not efficiently learnable. Finally, we study the lattice structure induced by generality relations in first order logic expressions, and derive some conclusions for learning complexity in more restricted scenarios.