Resource-bounded relational reasoning: Induction and deduction through stochastic matching

One of the obstacles to widely using first-order logic languages is the fac t that relational inference is intractable in the worst case. This paper pr esents an any-time relational inference algorithm: it proceeds by stochasti cally sampling the inference search space, after this space has been judici ously restricted using strongly-typed logic-like declarations. We present a relational learner producing programs geared to stochastic inf erence, named STILL, to enforce the potentialities of this framework. STILL handles examples described as definite or constrained clauses, and uses sa mpling-based heuristics again to achieve any-time learning. Controlling both the construction and the exploitation of logic programs yi elds robust relational reasoning, where deductive biases are compensated fo r by inductive biases, and vice versa.