Implicitly Learning to Reason in First-Order Logic (Extended Abstract)

The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence. The deduction camp concerns itself with questions about the expressiveness of formal languages for capturing knowledge about the world, together with proof systems for reasoning from such knowledge bases. The learning camp attempts to generalize from examples about partial descriptions about the world. In an influential paper, Valiant (2000) recognized that the challenge of learning should be integrated with deduction. In particular, he proposed a semantics to capture the quality possessed by the output of (probably approximately correct) PAC-learning algorithms when formulated in a logic. Although weaker than classical entailment, it allows for a powerful model theoretic framework for answering queries.