Implementation

1BC has been implemented in C in the context of the first-order descriptive learner Tertius [7]. Let us first describe briefly Tertius' abilities which are used in 1BC.

Tertius is able to deal with extensional explicit knowledge (i.e. the truth value of all ground facts is given), with extensional knowledge under the Closed World Assumption (i.e. all true ground facts are given), or with intensional knowledge (i.e. truth values are derived using either prolog inference mechanism or a theorem prover). Tertius can also deal with (weakly) typed predicates, that is each argument of a predicate belongs to a named type and the set of constants belonging to one type defines its domain. Moreover, if a domain is continuous, Tertius allows one to discretise it into several intervals of one standard deviation and centered on the mean.

Given some knowledge concerning the domain, Tertius returns a list of interesting sets of literals. It performs a top-down search, starting with the empty set and iteratively refines it. In order to avoid to consider the same clauses several times (and their refinements!), the refinement steps (i.e. adding a literal, unifying two variables, and instantiating a variable) are ordered. Once a particular refinement step is applied, none of its predecessors are applicable anymore. The search space can be seen as a generalisation of set-enumeration trees [14] to first-order logic.

Since there might be an infinite number of refinements, the search is restricted to a maximum number of literals and of variables. Other language biases are the declaration of structural predicates and properties, the distinction between functional and non-determinate structural predicates, and the use of parameters, as explained in the previous section.

Elementary first-order features are generated by constraining Tertius to generate only hypotheses containing exactly one property and no unnecessary structural predicates. The features can optionally be read from a file. In Equation 2, the features A_i = a_i are replaced by elementary first-order features f. Each conditional probability P(f|c) of the feature value f given the value c of the class is then estimated from the training data. Writing $n(f \wedge c)$ for the number of individuals satisfying f and Cl=c, n(c) for the number of individuals satisfying Cl=c, and F for the number of values of the feature (the number of possible values for a multivalued feature, 2 for a boolean or a non-determinate feature), the Laplace estimate $P(f\vert c) = \frac{n(f \wedge c)+1}{n(c) + F}$is used in order to avoid null probabilities in the product in Equation 2.