r-grams: Relational Grams

1 Introduction

Probabilistic sequence models occupy an important position within the field of machine learning. They are not only theoretically appealing but have also proven to provide effective learning algorithms across many application areas, ranging from natural language processing to bioinformatics and robotics. In traditional sequence models, sequences are strings s = w1 . . .wk over a (finite) alphabet Σ. Typically, the goal is to estimate the joint distribution P(s) over all possible strings. Given P(s) several tasks can be solved, including sequence classification, sampling, or predicting the next event in a sequence given a history of preceding events.

Recent technological advances and progress in artificial intelligence has led to the generation of structured data sequences. One example is that of the smart phone, where communication events of many phone users have been logged during extended periods of time [Raento et al., 2006]. Other ones are concerned with logging the activities and locations of persons [Liao et al., 2005], or visits to websites [Anderson et al., 2002]. Finally, in bioinformatics, sequences often contain also structural information [Durbin et al., 1998]. These developments together with the interest in statistical relational learning (see [De Raedt and Kersting, 2003] for an overview) have motivated the development of probabilistic models for relational sequences. These are sequences of tuples or atoms such as that indicated in Example 1. The Relational Markov Model (RMM) approach by [Anderson et al., 2002] extends traditional Markov models to this domain, and the Logical Hidden Markov Models (LOHMMs) by [Kersting et al., 2006] upgrade traditional HMMs towards relational sequences and also allow for logical variables and unification. Motivated by these models and the success and simplicity of n-gram models, we introduce relational grams, which upgrade the traditional n-grams towards relational sequences. There are two distinguished features of the r-grams. First, as LOHMMs and RMMs they allow one to work with generalized, i.e. abstract atoms in the sequences. For instance, in the bioinformatics example the atom helix(right,alpha,short) can be generalized to helix(X,alpha,Y) to describe an alphahelix of any orientation and length. Secondly, the use of variables and unification allows one to make abstraction of object identifiers and to share information between events. For example, the (abstract) sub-sequence outcall(X,fail), outtxt(X) describes that a user, after failing to reach a person, writes a text message to the same person, without stating the identity of the person. This is especially important when generalizing the patterns across phones or users, as the objects referred to will typically be different, and the precise identifiers do not matter but the relationships and events they occur in do.

The paper is structured as follows: in Section 2, we introduce relational sequences and define the notion of a generative model that takes into account the nature of identifiers and object identity; in Section 3, we then start from n-grams to derive r-grams; in Section 4, we report on some experiments, and finally, in Section 5, we conclude and touch upon related work.

2 Relational Sequences

An atom p(t1, . . . , tn) is a relation p of arity n that is followed by n terms ti. We will work with three kinds of terms: constants (in slanted font), identifiers (in italic) and variables (starting with an upper case character). Furthermore, the relations are typed, i.e. for each argument position i of the relation p, one can either have constants or identifiers. Variables may appear at any position. We shall also distinguish constant-variables from identifier-variables; the former can be instantiated to constants, the latter to identifiers. They will be written in italic or slanted font respec- Example 1. The following sequences over atoms are examples for relational sequences from different domains:

outcall(116513 ,fail), outcall(116513 ,fail), incall(116513 ,succ), outtxt(213446 ), intxt(213446 ), . . . mkdir(rgrams), ls(rgrams), emacs(rgrams.tex), latex(rgrams.tex), . . .

strand(sa,plus,short), helix(right,alpha,medium), strand(blb,plus,short), helix(right,f3to10,short),. . .

The first domain describes incoming and outgoing calls and text messages for a mobile phone user. In the second domain, Unix shell commands executed by a user are described in terms of command name and arguments. In the third domain, helices and strands as protein secondary structure elements are defined in terms of their orientation, type, and length.

tively. For instance, the relation outcall has identifiers at the first position, and constants at the second one. Therefore, outcall(111365 ,fail) is type-conform. The types, constants, identifiers, variables and relations together specify the alphabet Σ, i.e. the set of type-conformatoms. ¯Σ ⊆ Σ is the set of atoms that do not contain identifiers. A relational sequence is then a string s = w1, . . . , wm in Σ∗ . An expression is ground if it does not contain any variable. Example sequences will typically be ground, cf. Example 1.

Notice that constants typically serve as attributes describing properties of the relations, and identifiers identify particular objects in the domain. Identifiers have no special meaning and they are only used for sharing object identity between events. Moreover, there is no fixed vocabulary for identifiers which is known a priori, rather, new identifiers will keep appearing when applying a model to unseen data. Therefore, it is desirable to distinguish ground sequences only up to identifier renaming, which motivates the following definition.

Definition 1 (Sequence Congruence). Two relational sequences p1 . . . pm, q1 . . . qm are n-congruent if for all i ∈ {1, . . . ,m-n} the subsequences pi . . . pi+n-1, ri . . . ri+n-1 are identical up to identifier renaming. Two sequences s1, s2 are identical up to identifier renaming if there exist a one-to-one mapping ϕ of the identifiers in s1 to those in s2 such that s1 equals s2 after replacing the identifiers according to ϕ.

Example 2. The sequences r(x)p(a,y)r(y)p(b,x) and r(z)p(a,w)r(w)p(b,u) are 3-congruent (but not 4-congruent).

m-congruent sequences are identical up to identifier renaming. For n < m, the definition takes into account a limited history: two sequences are congruent if their object identity patterns are locally identical. Finally we note that ncongruence defines an equivalence relation, i.e. it is reflexive, symmetric and transitive.

Let us now define a generative model for relational sequences. It should not sample actual identifier values, but rather equivalence classes of congruent sequences. This yields the following definition:

Definition 2 (Generative Model). Let Σ be a relational alphabet. Let S(Σ) be the set of all ground sequences of length m over Σ, and let Sn(Σ) be the set of equivalence classes induced on S(Σ) by n-congruence. Then a generative model of order n over Σ defines a distribution over Sn(Σ).

Such a generative model can be learned from a set of ground sequences and the alphabet Σ. In its simplest form, the learning problem can be stated as maximum likelihood estimation:

Given

• a relational alphabet Σ
• a set S of ground sequences over Σ
• n ∈ N
• a family Λ of generative models of order n over Σ,

Find a model λ ∈ Λ that maximizes

where [s] denotes the equivalence class of s with regard to ncongruence. A simple instance of such a family of generative models will be introduced in the next section.

3 r-gramModels for Relational Sequences

Markov Chains are amongst the simplest yet most successful approaches for sequence modeling. n-grams are based on higher-order Markov chains, and employ certain smoothing techniques to avoid overfitting the sample distribution. In this section, we will briefly review n-grams, and then propose a simple extension of n-grams for relational sequences.

3.1 n-grams: SmoothedMarkov Chains

n-grams define a distribution over sequences w1...wm of length m by an order n - 1 Markov assumption:

(where wi-n+1 is a shorthand for wmax(1,i-n+1)). In the most basic case, the conditional probabilities are estimated from a set S of training sequences in terms of "gram" counts:

where C(w1...wk) is the number of times w1...wk appeared as a subsequence in any s ∈ S. Note that this is indeed the estimate maximizing the likelihood.

The gram order n defines the tradeoff between reliability of probability estimates and discriminatory power of the model. Rather than selecting a fixed order n, performance can be increased by combining models of different order which are discriminative but can still be estimated reliably [Manning and Sch¨utze, 1999]. The two most popular approaches are back-off and interpolation estimates. In this paper, we will focus on the latter approach, which defines conditional distributions as linear combinations of models of different order:

where the α1, ..., αn are suitable weights with ∑nk=1 αk = 1, and the lower-order distributions Pk(wi | wi-k+1 . . .wi-1) are estimated according to maximum likelihood (Equation 1). Several more advanced smoothing techniques have been proposed (cf. [Manning and Sch¨utze, 1999]), but are beyond the scope of this paper.

(2)

3.2 r-grams: Smoothed Relational Markov Chains

Consider ground relational sequences of the form g1 . . . gm ∈ S(Σ). The key idea behind r-grams is a Markov assumption

However, defining conditional probabilities at the level of ground grams does not make sense in the presence of object identifiers. Thus, ground grams will be replaced by generalized ones. Generality is defined by a notion of subsumption:

Definition 3 (Subsumption). A relational sequence l1, . . . , lk subsumes another sequence k1, . . . , kn with substitution θ, notation l1, . . . , lk ⪯θ k1, . . . , kn, if and only if k ≤ n and ∀i, 1 ≤ i ≤ k : liθ = ki. A substitution is a set {V1/t1, . . . , Vl/tl} where the Vi are different variables and the ti are terms such that no identifier or identifier variable occurs twice in {t1, ..., tl}.

The restriction on the allowed substitutions implements the object identity subsumption of [Semeraro et al., 1995]. The notion of sequence subsumption is due to [Lee and De Raedt, 2003]. It can be tested in linear time.

Example 3. Let Y, Z, U, V be identifier variables.

but

We can now refine equation 3 to take into account generalized sequences. This will be realized by defining

where li-n+1...li ⪯θ gi-n+1...gi. This generalization abstracts from identifier values and at the same time yields smoothed probability estimates, with the degree and characteristic of the smoothing depending on the particular choice of li-n+1...li. This is formalized in the following definition.

Definition 4 (r-gram model). An r-gram model R of order n over an alphabet Σ is a set of relational grams

where

1. ∀i : l1...ln-1lin ∈ ¯Σ∗ ;
2. ∀i : lin contains no constant-variables;
3. ∀i : lin is annotated with the probability values Pr(lin | l1...ln-1) such that ∑di=1 Pr(lin | l1...ln-1) = 1
4. ∀i ̸= j : l1...ln-1lin ̸⪯ l1...ln-1ljn; i.e. the heads are mutually exclusive.

Example 4. The following is an example of an order 2 relational gram in the mobile phone domain (see Example 1).

It states that after not reaching a person a user is more likely to write a text message to this person than to somebody else.

We still need to show that an r-gram model R defines a distribution over relational sequences. We first discuss a basic model by analogy to an unsmoothed n-gram, before extending it to a smoothed one in analogy to Equation 2.

A Basic Model

In the basic r-grammodel, for any ground sequence g1...gn-1 there is exactly one gram l1n ∨ ... ∨ ldn ← l1...ln-1 with l1...ln-1 ⪯θ g1...gn-1. Its body l1...ln-1 is the most specific sequence in ¯Σ∗ subsuming g1...gn-1. According to Equation 3, we start by defining a probability PR(g | g1...gn-1) for any ground atom g given a sequence g1...gn-1 of ground literals. Let g be a ground literal and consider the above gram r subsuming g1...gn-1. If there is an i ∈ {1, ..., d} such that l1...ln-1lin ⪯θ g1...gn-1g it is unique and we define

Otherwise, PR(g | g1...gn-1) = 0. From PR(g | g1...gn-1), a probability value PR(g1...gm) can be derived according to Equation 3. Note that this is not a distribution over all ground sequences of length m, as the model does not distinguish between n-congruent sequences. Instead, the following holds:

Lemma 1. Let R be an order n r-gram over Σ, and s, s′ ∈ S(Σ) be relational sequences with s n-congruent to s′ . Then PR(s) = PR(s′ ) .

Let us therefore define PR([s]) := PR(s) for any [s] ∈ Sn(Q). Furthermore, ∑[s]∈Sn(Σ) PR([s]) = 1. Therefore,

Theorem1. An order n r-gram over Σ is a generative model over Σ.

Example 5. Consider the r-gram model R with grams

and uniform distributions over head literals. ϵ is an artificial start symbol that only matches at the beginning of the sequence. The ground sequence g1...g5 = r(u)p(a,u)r(v)p(b,v)r(v) has probability PR(g1...g5) = 1 · 0.5 · 0.5 · 0.5 · 1 = 0.125.

Smoothing r-grams

In the basic model, there was exactly one gram r ∈ R subsuming a ground subsequence g1...gn-1, namely the most specific one. As for n-grams, the problemwith this approach is that there is a large number of such grams and the amount of training data needed to reliably estimate all of their frequencies is prohibitive unless n is very small. For n-grams, grams are therefore generalized by shortening their bodies, i.e., smoothing with k-gram estimates for k < n (Equation 2).

The basic idea behind smoothing in r-grams is to generalize grams logically, and mix the resulting distributions:

where Pr(g | g1...gn-1) is the probability defined by r as explained above, ˆR is the subset of grams in R subsuming g1...gn-1, and α is a normalization constant, i.e. α = ∑r∈ ˆR αr. The more general r, the more smooth the probability estimate Pr(g | g1...gn-1) will be. The actual degree and characteristic of the smoothing is defined by the set of matching r-grams together with their relative weights αr.

By analogy with n-grams, additional smoothing can be obtained by also considering relational grams r ∈ R with shorter bodies l1...lk-1, k < n. However, there is a subtle problem with this approach: Relational grams of order k < n define a probability distribution over Sk(Σ) rather than Sn(Σ), i.e. the sequences are partitioned into a smaller number of equivalence classes. However, this can be taken care of by a straightforward normalization, which distributes the probability mass assigned to an equivalence class modulo k equally among all subclasses modulo n.

Example 6. Consider the r-gram model R with grams r,q given by

uniform distribution over head literals and αr = αq = 0.5. We expect PR(r(u) | r(v))+PR(r(v) | r(v)) = 1. However, when directly mixing distributions

as the r-gram q does not distinguish between the sequences r(x)r(x) and r(x)r(y). Instead, we mix by

where γ = 2 is the number of subclasses modulo 2-congruence of the class [r(X)].

The ultimate level of smoothing can be obtained by a relational gram r of the form l1n ∨...∨ldn ←where the lin are fully variablized (also for non-identifier arguments). For this gram

where X1, ...,Xa are the non-identifier arguments of lin and x1, ..., xa their instantiations in g. This case corresponds to an out-of-vocabulary event (observing an event that was not part of the training vocabulary) for n-grams.

3.3 Building r-grams FromData

To learn an r-gram from a given set S of training sequences, we need to 1) choose the set R of relational grams; 2) estimate their corresponding conditional probabilities; and 3) define the weights αr for every r ∈ R. Before specifying our algorithm, we need to define counts in the relational setting:

Our algorithm to learn r-grams is specified below:

r-grams(input: sequences S; alphabet: Σ; parameters: γ, n)

In Line 1 of the algorithm, one computes all r-grams that occur in the data. Notice that no identifiers occur in these r-grams (cf. ¯Σ∗ ). This can be realized using either a frequent relational sequence miner, such as MineSeqLog [Lee and De Raedt, 2003], or using an on-the-fly approach. In the latter case, a relational gram with body l1...lk is only built and added to R when and if it is needed to evaluate PR(g | g1...gn-1) with l1...lk ⪯ g1...gk on unseen data. In Line 3, all possible literals lik are sought that occur also in the data. They are maximally specific, which means that they do not contain constant-variables (cf. condition 2 of Definition 4). Line 4 then computes the maximum likelihood estimates and Lines 5-7 the weight αr. Here S(r) denotes the set of all ground subsequences g1...gn-1g appearing in the data which are subsumed by r. The likelihood L(r) of r defined in Line 5 is a measure for how well the distribution defined by r matches the sample distribution. The αr as in Line 7 is then defined in terms of |S(r)| and the parameter γ, which controls the tradeoff between smoothness and discrimination. Highly discriminative (specific) rules have higher likelihood than more general ones as they are able to fit the sample distribution better, and thus receive more weight if γ > 0.

4 Experiments

This section reports on an empirical evaluation of the proposed method in several real-world domains. More specifically, we seek to answer the following questions:

• (Q1) Are r-grams competitive with other state-of-the-art approaches for relational sequence classification?
• (Q2) Is relational abstraction, especially of identifiers, useful?

Experiments were carried out on real-world sequence classification problems from three domains. In the Unix Shell domain [Greenberg, 1988; Jacobs and Blockeel, 2003], the task is to classify users as novice programmers or non-programmers based on logs of 3773 shell sessions containing 94537 commands (constants) and their arguments (identifiers). To reproduce the setting used in [Jacobs and Blockeel, 2003], we sampled 10 subsets of 50/1000 instances each from the data, measured classification accuracy on these using 10-fold cross-validation, and averaged the results. In the Protein fold classification domain, the task is to classify proteins as belonging to one of five folds of the SCOP hierarchy [Hubbard et al., 1997]. Strand names are treated as identifiers, all other ground terms as constants. This problem has been used as a benchmark before [Kersting et al., 2006; Kersting and G¨artner, 2004], and we reproduce the experimental setting used in this earlier work: the same 200 examples per fold are used for training, and the remaining examples as the test set. In the Context Phone domain, data about user communication behavior has been gathered using a software running on Nokia Smartphones that automatically logs communication and context data. In our study, we only use information about incoming and outgoing calls and text messages. Phone numbers are identifiers, other ground terms constants. The task in Phone I is to discriminate between real sequences of events and "corrupted" ones, which contain the same sequence elements but in random order. For k ∈ {20, 40, 60, 80, 100}, 5 subsets of size k were sampled randomly, 5-fold cross-validation performed and averaged for each k. In Phone II, the task is to classify communication logs as belonging to one of three users, based only on their communication patterns but without referring to actual phone numbers in the event sequence.

In all domains sequence classification is performed by building an r-gram model RC for each class C and labeling unseen sequences s with the class that maximizes PC(s)P(C). We used bigrammodels in the Phone II domain and trigrammodels for all other domains, and the smoothing parameter γ was set to 1 in all experiments. Learning the rgram model was done on-the-fly as explained in Section 3.3.

Table 1 compares the classification accuracy of r-grams with accuracy results from the literature in the Protein Fold and Unix Shell domains. In the Protein Fold domain, a handcrafted Logical Hidden Markov Model achieves 74% accuracy [Kersting et al., 2006]. This has been improved to 82.4% by a fisher kernel approach, in which the gradient of the likelihood function of the Logical Hidden Markov Model is used as input in a support vector machine [Kersting and G¨artner, 2004]. The Unix Shell log classification problem was originally tackled using a k-nearest neighbor method based on customized sequence similarity [Jacobs and Blockeel, 2003]. In the same paper, the authors present results for a C4.5 decision tree learner using a bag-of-words representation. In both cases, r-grams yield competitive classification accuracy, which is a positive answer to question (Q1). Furthermore, we note that even using a na¨ıve implementation r-grams are computationally efficient. Times for building an r-gram model ranged from 3 to 240 seconds in the presented experiments 1 .

In a second set of experiments, the effect of using relational abstraction was examined in more detail. More precisely, r-grams were compared to n-grams which implement non-relational smoothing as outlined in Section 3.1, treating the atoms in Σ as flat symbols. For these experiments, we tried keeping identifiers in the events (n-grams) or removing them from the data (n-grams w/o IDs). Accuracy results for the Protein Fold, Unix Shell and Context Phone domains are given in Table 2. If identifiers are treated as normal constants, accuracy is reduced in all cases, especially for the identifierrich Unix and Context Phone domains. This is not surprising, as most identifiers appearing in the test data have never been observed in the training data and thus the corresponding event has probability zero. When identifiers are removed from the data, performance is similar as for r-grams in the Protein Fold and Unix Shell domain, but worse in the Context Phone domains. On Phone I, r-grams significantly outperform n-grams w/o IDs (unpaired sampled t-test, p = 0.01). Figure 1 shows more detailed results on Phone I for different numbers of training examples. It can be observed that relational abstraction is particularly helpful for small numbers of training examples. To summarize, there are domains where it is possible to ignore identifiers in the data, but in other domains relational abstraction is essential for good performance. Therefore, question (Q2) can be answered affirmatively as well.

1 All experiments were run on standard PC hardware with 3.2GHz processor and 2GB of main memory.

5 Conclusions and RelatedWork

We have presented the first approach to upgrading n-grams to relational sequences involving identifiers. The formalism employs variables, unification and distinguishes constants from identifiers. It also implements smoothing by relationally generalizing the r-grams. The approach was experimentally evaluated and shown to be promising for applications involving the analysis of various types of logs.

The work that we have presented is related to other work on analyzing relational and logical sequences. This includes most notably, the RMMs by [Anderson et al., 2002] who presented a relational Markov model approach, and the LOHMMs by [Kersting et al., 2006] who introduced Logical Hidden Markov Models. RMMs define a probability distribution over ground relational sequences without identifiers. Furthermore, they do not employ unification (or variable propagation) but realize shrinkage through the use of taxonomies over the constant values appearing in the atoms and decision trees to encode the probability values. RMMs only consider first order Markov models, i.e. the next state only depends on the previous one, so RMMs do not smooth over sequences of variable length. RMMs have been applied to challenging applications in web-log analysis. Whereas RMMs upgrade Markov models, LOHMMs upgrade HMMs to work with logical sequences. As r-grams, they allow for unification and offer also the ability to work with identifiers. In addition, they allow one to work with structured terms (and functors). However, as RMMs, they only consider first order Markov models. Furthermore, they do not smooth distributions using models of different specificity. Finally, MineSeqLog [Lee and De Raedt, 2003] is a frequent relational sequences miner that employs subsumption to test whether a pattern matches a relational sequence. One might consider employing it to tackle the first step in the r-gramAlgorithm.

There are several directions for further work. These include: extending the framework to work with structured terms, considering back-off smoothing instead of interpolation, and, perhaps most importantly, applying the work to challenging artificial intelligence applications.

Acknowledgments

The authors would like to thank the anonymous reviewers, Kristian Kersting and Hannu Toivonen for valuable comments, and Mika Raento for making the Context Phone data available. The research was supported by the European Union IST programme, contract no. FP6-508861, Application of Probabilistic Inductive Logic Programming II.