Kernels on Prolog Ground Terms

1 Introduction

Starting from the seminal work of Haussler on convolution kernels [Haussler, 1999], several researchers have proposed kernels on discrete data structures such as sequences, trees and graphs (see [G¨ artner, 2003] for a review). Recently, kernels over complex individuals have been defined using higher order logic abstractions [G¨ artner et al., 2004]. The family of kernels developed in this paper originates from a specialization to first-order logic of such kernels, as it is designed to work on individuals represented as Prolog ground terms. There are several reasons for such a specialization. Simplicity: Prolog representations provide a simpler representational framework. Sufficiency: useful higher order structures such as sets can be simulated in Prolog. Types can also be introduced. In practice, Prolog based representations are sufficiently expressive for many application domains. Legacy: many inductive logic programming systems and knowledge bases are actually based on first order logic and Prolog is a well supported language. Extendibility: first-order logic programs have been extended to deal with uncertainty through the use of probability resulting in models such as stochastic and Bayesian logic programs (see [De Raedt and Kersting, 2003] for a review); these extensions can be very interesting in the context of machine learning.

We develop variants of the kernel on typed and untyped terms. The present formulation allows us to obtain a relatively simple proof of positive definiteness based on showing that kernels over terms are a special case of convolution kernels [Haussler, 1999]. We finally present experimental evidence of the usefulness of these kernels by learning the boiling point of alkanes from their chemical structure.

2 Kernels on Prolog ground terms

We begin with kernels on untyped terms. For a given program P we denote by B the Herbrand universe of P (i.e. the set of all ground terms that can be formed from symbols in P) by C ⊂ B the set of all constants, and by F the ranked set of functors.

Definition 1 (Kernels on untyped terms). The kernel between two terms t and s is a function K : B × B ↦→ IR defined inductively as follows:

• if s ∈ C and t ∈ C then K(s, t) = κ(s, t) where κ : C × C ↦→ IR is a valid kernel on constants;
• else if s and t are compound terms and have different arities or functors, i.e. s = f(s1, . . . , sn) and t = g(t1, . . . , tm), then

where ι : F × F ↦→ IR is a valid kernel on functors;

• else if s and t are compound terms and have the same arity and functor, i.e. s = f(s1, . . . , sn) and t = f(t1, . . . , tn), then

• in all other cases K(s, t) = 0.

We call κ and ι atomic kernels as they operate on nonstructured symbols. A special but useful case is the atomic match kernel δ defined as δ(x, z) = 1 if x = z and δ(x, z) = 0 if x ̸= z.

A finer level of granularity in the definition of ground term kernels can be gained from the use of typed terms. This extra flexibility may be necessary to specify different kernel functions associated with constants of different type (e.g. numerical vs. categorical). It may also be necessary in order to specify different kernels associated to different arguments of compound terms. Our approach for introducing types is similar to that proposed in [Lakshman and Reddy, 1991]. We denote by T the ranked set of type constructors. The type signature of a function of arity n has the form τ1×, . . . , ×τn ↦→ τ ′ where n ≥ 0 is the number of arguments, τ1, . . . , τk ∈ T their types, and τ ′ ∈ T the type of the result. Functions of arity 0 have signature ⊥ ↦→ τ ′ and can be therefore interpreted as constants of type τ ′ . The type signature of a predicate of arity n has the form τ1×, . . . , ×τn ↦→ Ω where Ω ∈ T is the type of booleans. We write t : τ to assert that t is a term of type τ. We denote by B the set of all typed ground terms, by C ⊂ B the set of all typed constants, and by F the set of typed functors. Finally we introduce a (possibly empty) set of distinguished type signatures D ⊂ T that can be useful to specify ad-hoc kernel functions on certain compound terms.

Definition 2 (Kernels on typed terms). The kernel between two typed terms t and s is defined inductively as follows:

• if s ∈ C, t ∈ C, s : τ, t : τ then K(s, t) = κτ(s, t) where κτ : C × C ↦→ IR is a valid kernel on constants of type τ ;
• else if s and t are compound terms that have the same type but different arities, functors, or signatures, i.e. s = f(s1, . . . , sn) and t = g(t1, . . . , tm), f : σ1×, . . . ,×σn ↦→ τ ′ , g : τ1×, . . . ,×τm ↦→ τ ′ , then

where ιτ ′ : F ×F ↦→ IR is a valid kernel on functors that construct terms of type τ ′

• else if s and t are compound terms and have the same type, arity, and functor, i.e. s = f(s1, . . . , sn), t = f(t1, . . . , tn), and f : τ1×, . . . ,×τn ↦→ τ ′ , then

• in all other cases K(s, t) = 0.

In the case of numerical constants, examples of useful kernels include κReal (x, z) = exp(-γ(x - z)2 ) and κReal (x, z) = min{x, z}.

Theorem 1. The kernel functions on Prolog ground terms given in Definitions 1 and 2 are positive definite (pd).

Proof sketch. Let us introduce the following decomposition structure (see [Shawe-Taylor and Cristianini, 2004]): R = 〈(X1,X2),R, (k1, k2)〉 with X1 = F (the set of functors), X2 = (F, IN, B)), and

Then it can be immediately verified that the kernel function of Eq. 1 and 2 correspond to the direct sum decomposition kernel associated with the decomposition structure R if k1 = ι and k2((f, n, a), (g, m, b)) = δ(f, g)δ(n, m)k′ (a, b) where given a = (s1, . . . , sn) and b = (t1, . . . , tn)

Since kernels are closed under direct sum, if K is pd then K′ is also pd. The proof then follows from Haussler's decomposition framework [Haussler, 1999] and by induction using as base step the fact that κ is a valid kernel on constants.

The proof that kernels on typed terms (Def. 2) are pd is obtained similarly, replacing functor arities by type signatures in the decomposition structure. □

Alternative forms of typed and untyped kernels can be obtained by replacing sums with products in Eq. (2) and (4), while keeping the rest of the definitions unchanged. Since kernels are closed under tensor product, positive definiteness can be proven using the same technique as in Theorem 1.

3 Experimental evaluation

The kernel has been tested on a quantitative structureproperty relationship (QSPR) prediction task, namely predicting the boiling point of alkanes given their chemical structure. Alkanes can be represented as ordered rooted trees using a very simple procedure [Bianucci et al., 2000], and trees can be easily encoded as Prolog ground terms, as shown in Fig. 1. We addressed this task using kernel ridge regression [Shawe-Taylor and Cristianini, 2004] with the kernel K on untyped terms of Def. 1, a match kernel for functors (carbon atoms), and a null kernel for constants (hydrogen atoms). In this way the kernel measures the number of carbon atoms in corresponding positions. As an additional source of information, we extracted the depths of the trees representing the molecules, and summed their product to the term kernel, obtaining a more informed kernel K′ . Finally, we employed a Gaussian kernel on top of K and K′ . Performance was evaluated by a ten fold cross validation procedure, Hyperparameters (namely, the Gaussian width and the regularization parameter), were chosen by a hold-out procedure on the training set of the first fold, and kept fixed for the successive 10 fold cross validation procedure. When using kernel K we obtained an average mean square error of 4.6 Celsius degrees while using K′ the error can be reduced to 3.8 degrees. These results are comparable to those produced by the highly tuned networks developed in [Bianucci et al., 2000].

Figure 1: Ground term representation of an Alkane.

Acknowledgements

We wish to thank Luc de Raedt for fruitful discussions. This research is supported by EU Grant APrIL II (contract n◦ 508861) and by MIUR Grant 2003091149 002.