  A major challenge in inductive logic programming (ILP) is learning large
programs. We argue that a key limitation of existing systems is that they use
entailment to guide the hypothesis search. This approach is limited because
entailment is a binary decision: a hypothesis either entails an example or does
not, and there is no intermediate position. To address this limitation, we go
beyond entailment and use \emph{example-dependent} loss functions to guide the
search, where a hypothesis can partially cover an example. We implement our
idea in Brute, a new ILP system which uses best-first search, guided by an
example-dependent loss function, to incrementally build programs. Our
experiments on three diverse program synthesis domains (robot planning, string
transformations, and ASCII art), show that Brute can substantially outperform
existing ILP systems, both in terms of predictive accuracies and learning
times, and can learn programs 20 times larger than state-of-the-art systems.
