Restricted First Order Logic

Name	Restricted First Order Logic
Description	Many machine learning algorithms use a restriction of first order logic as a formalism for representing hypotheses, examples and sometimes background knowledge. Advantages of choosing logical representations are: Representations are readable by humans. Logic is a well-understood mathematical discipline, so a plenty of mathematical results can be used, searching for learning methods and proving their correctness. Examples, hypotheses and background knowledge can be expressed within the same formalism. A problem of full first order logic is that it is algorithmically hard to check whether a formula implies another, which is necessary for finding hypotheses that are consistent with the set of examples. To receive a more tractable formalism, restrictions of first order logic are chosen. Depending on how expressive the restriction has to be, one can choose between propositional logic horn clauses function-free clauses non-recursive clauses and many more specific restrictions. If e.g. background knowledge is given in the form of function-free ground facts (relational database), function-free horn clauses are sufficient as the hypothesis language for a specific learning task, then a possible candidate for an inference operator is the (in the general case incomplete) θ-subsumption. This restriction of first order logic is much more tractable and therefore to be preferred (if it is expressive enough). Typical restrictions of the hypothesis language are variously restricted clauses, e.g. function-free horn clauses.
Methods	Bottom-Up Induction of Horn Clauses FOIL GOLEM PROGOL RDT Star