  Inductive rule learning is arguably among the most traditional paradigms in
machine learning. Although we have seen considerable progress over the years in
learning rule-based theories, all state-of-the-art learners still learn
descriptions that directly relate the input features to the target concept. In
the simplest case, concept learning, this is a disjunctive normal form (DNF)
description of the positive class. While it is clear that this is sufficient
from a logical point of view because every logical expression can be reduced to
an equivalent DNF expression, it could nevertheless be the case that more
structured representations, which form deep theories by forming intermediate
concepts, could be easier to learn, in very much the same way as deep neural
networks are able to outperform shallow networks, even though the latter are
also universal function approximators. In this paper, we empirically compare
deep and shallow rule learning with a uniform general algorithm, which relies
on greedy mini-batch based optimization. Our experiments on both artificial and
real-world benchmark data indicate that deep rule networks outperform shallow
networks.
