Relational Learning for NLP using Linear Threshold Elements

1 Introduction

The paper explores some aspects of relational knowledge representation and their learnability. While the discus­ sion is to a large extent general it is made in the context of low-level natural language processing (NLP) tasks. Recent efforts in NLP emphasize empirical approaches, that attempt to learn how to perform various natural language tasks by being trained using an annotated cor­ pus. These approaches have been used for a wide variety of fairly low level tasks such as part-of-speech tagging, prepositional-phrase attachment, context-sensitive text correction, and word selection in speech recognition and translation.

In this paper we study the general form of such prob­ lems in a relational setting. Thus, our interest here is in learning to perform such tasks given a set of previously processed sentences, each represented using a relational representation. We use the task of Part of speech tagging (POS) - one of the basic tasks studied in this line of re­ search and often viewed as a prerequisite to performing many of the other tasks - as our running example. POS is the task of assigning each word in a given sentence the part of speech it assumes in that sentence. For example, assign N or V to talk in the following pair of sentences: Have you listened to his (him) talk?

*Partly supported by EPSRC grant GR/M21409.

tResearch supported by NSF grants IIS-9801638 and SBR-9873450.

'Research supported by grants NSF-CCR-95-04436 and ONR-N00014-96-l-0550.

Leslie G. Valiant+ Engineering and Applied Sciences Harvard University Cambridge, MA 02138 USA valiant@deas.harvard.edu

The SNoW system [Roth, 1998] has been used suc­ cessfully for several NLP tasks and, in particular, for learning to perform part of speech tagging [Roth and Zelenko, 1998]. The system uses perceptron-like repre­ sentations and propositional learning algorithms. On the other hand, relational representations are very natural for NLP tasks and logic programs have been widely used in this context [Hobbs et al., 1993; Pereira and Shieber, 1987]. A natural approach would thus be to apply learn­ ing in first order logic or Inductive Logic Programming (ILP) for learning to perform the relevant tasks, as done e.g in [Cussens, 1997; Dzeroski and Erjavec, 1997].

In this paper we discuss the theoretical basis underly­ ing the SNoW system in terms of the Neuroidal Architec­ ture, particularly following specific suggestions [Valiant, 1998a; 1999] for representing relational information using linear threshold elements as discussed earlier in [Valiant, 1994]. Using this analysis we show that SNoW can be viewed as a relational learning system, and this enables us to go on to compare it more directly with ILP.

The main contribution of the paper is therefore in an­ alyzing the SNoW system in terms of the Neuroidal Ar­ chitecture and consequently as a system learning rela­ tional information. This analysis provides insight into some of the theoretical and practical considerations that have been made in the search for scalable systems in this context. Secondly, since the theory is somewhat more general than current implementations, this sug­ gests that extending the SNoW system in a manner con­ sistent with the theory may provide new levels of func­ tionality. Finally, by providing a single framework for discussing both SNoW and ILP we enable future com­ parative work of these seemingly disparate approaches.

The presentation is organized as follows. We first de­ scribe the input (a sentence) and program representa­ tion (Horn rules and variants) for the relational tasks under consideration. We then discuss various computa­ tional aspects of the representations and their learnabil­ ity. This leads to a description of the SNoW system and a discussion of some of the pragmatics of systems that learn to perform these tasks.

2 Representing a Sentence

We use first order logic statements with a finite set of predicates and allow only constants (i.e. no other func­ tion symbols) in expressions. Since the specific predi­ cates used do not affect the conceptual issues, we shall give a simple running example that will serve to illus­ trate the computational issues. 1 The representation is as follows:

• Each word has a constant associated with it.
• The linear structure of the sentence is captured by the predicate bef( w1, w2) which means that word w1 is immediately before w2 in the sentence.
• A variety of relations conveying linguistic or seman­ tic information may be added. For example we may add ppos( w, p) if p is a possible part of speech for word w. Another example is adding isa( w1, w2) where w1 is a word describing an object in a class of objects described by the word w2.

For simplicity we assume in the examples below that bef() and ppos() are the only relations used in the rep­ resentation. Thus the sentence this can will rust is represented as the collection of all the atoms that hold (are active) in it:

It is implicit in the above that atoms not listed (such as bef(this, rust)) are false for this sentence.

The above representation may be too restricted if worrls appear more than once in a. sentence. This can be easily dealt with formally by replacing constants rep­ resenting words with unary predicates and using "to­ ken constants" to represent positions in the sentence [Valiant, 1998a; 1999]. In order to keep the notation simple we ignore this issue in the rest of the paper.

3 Representing Programs

3.1 Horn Representations

A program should take a sentence as an input and pro­ duce part of speech tags for the words in this sentence. One possible representation for such a program is a set of Horn rules. For example, the rules 2

R2 = [Vx, bef( x, will)-+ h(x)]

R3 = [Vx, h (x) A h(x) -+ pos(x, noun)]

represent a simple program for predicting whether a word is a noun or not. These rules exemplify several aspects of the representation. First, we may want to construct "complex features" such ash() and h() out of the base predicates. Secondly, such features may in­ clude existentially quantified variables as in the first rule or constants as in the first or second rule. Note that the same program can be represented by the single rule R4 = [Vx, (:Jy, z, bef(x, y) A bef(y, z) A ppos(z, verb))

1 The examples are meant only to illustrate the language used and may not be the most accurate - indeed, one reason learning is crucial in this domain is that it is hard to come up with concise rules that perform well.

2 Note that the first rule is logically equivalent to [\fx,y,z,(bef( x,y) 1\ bef(y,z) 1\ppos(z,verb)-+ /l(x))], but the existential presentation is more intuitive from an opera­ tional perspective.

A bef(x, will) -+ pos(x, noun)]

3.2 Threshold Elements with Quantified Propositions

This section reviews a previous proposal for implement­ ing relational predicates by means of linear threshold elements [Valiant, 1998a; 1999]. Consider a relational Horn rule

R5 = [Vx, (:Jy, c1(x, y) A c2(x, y))-+ new(x)] where y appears only in the antecedent. By an appro­ priate choice for w1, w2 , (), this rule can be represented using a threshold element

R6 = [Vx, (:Jy, [w1·c1(x, y)+w2·c2(x, y) > B])-+ new(x)] We impose the restriction that the quantified antecedent variables appear in each condition separately. That is, the rule R6 is not legal since y is shared between c1 and c2 . An example for a legal rule (not equivalent to the one above) is:

In fact, our restriction also allows for universally quan­ tified variables within a single condition (which differs from quantification outside the rule). Under this restric­ tion, for any sentence and given a binding for x, the conditions of the form (Qy,c(x,y)) (where Q is a quan­ tifier) are essentially Boolean variables. That is, they are either true or false but have no parameters. We call these quantified propositions to emphasize this point.

As before, rules that use quantified propositions can be described using a linear threshold element:

Thus a special case of rule representations is used but it is generalized through the use of linear threshold elements (that can represent A as well as other functions) , and more general quantifiers.

Note that the restriction can be overcome by changing the set of relations. For example, instead of R5 above we could have

R10 = [Vx,(:Jy,h(x,y))-+ new(x)]

While the resulting program is the same, the represen­ tation will need to include h() that explicitly mentions the variable y.

4 Learning

In this section we discuss the learnability of programs of the form presented in Sec. 3 in a supervised learn­ ing paradigm. The input to the learning algorithm is given in terms of an input sentence representation S as in Eq. (1) along with an atom p, such as pos (rust, verb), that holds in this sentence. We call the pair < S, p > a labeled example. A single sentence may thus give rise to several examples, one for each word.

In the following discussion it is sometimes useful to assume that there is a program in the class of programs discussed, that can produce correct labels for any sen­ tence. Such a program is called the target program.

4.1 Relational Methods

An example < S, p > can b.e represented as ( S ---+ p). An example of this form is a ground Horn clause that is implied by the target program (a set of Horn rules). This is exactly the scheme of learning from entailment studied in inductive logic programming. (Notice that this representation assumes that negative atoms are not relevant for the label i.e. we cannot use ·bef(x, can) in the condition of a rule). Several techniques from ILP use examples in this form, and can be applied to this task [Muggleton and De Raedt, 1994; Cohen, 1995a].3 One of the main features that distinguishes ILP from other formalizations of learning is the use of background knowledge. A similar effect can be achieved in our for­ malization by enriching the input representation of sen­ tences with the relevant relational information. Thus, given rules, say, that compute isa() relations between words, (e.g., using WordNet) we can augment our initial representation S with the isa() atoms implied by these rules (for words in the sentence).

Studies in ILP suggest that unless the rule representa­ tion is restricted the learning problem is intractable. We briefly discuss some of the common restrictions studied and their relation to the use of quantified propositions. A Horn clause is constrained if all the variables in the con­ sequent also appear in the antecedent [Page and Frisch, 1992]. This is a special case of determinacy defined as follows. Assume one imposes an order (left to right) on the predicates in a rule's antecedent. A predicate is de­ terminate if in any example and given a binding for the consequent and the first i- 1 predicates, there is at most one binding that makes the i'th predicate true. Clearly, given a binding for the consequent, every predicate in the condition is a Boolean variable, similar to our restriction above, a fact which has been used both in theoretical results and practical applications [Dzeroski et al., 1992; Lavrac and Dzeroski, 1994]. In our case, while there may be more than one binding for each quantified proposition (::Jy ... ) the condition is still Boolean.

Another related restriction is the depth of terms in a clause. We assign a depth to terms using the order on conditions in the antecedent from left to right. A term in the consequent is of depth 0. If p( u, v, ... ) is the next atom in the condition, such that u has been assigned depth i (and no other term has been assigned a lower depth) and v has not yet been assigned a depth, then v is of depth i + 1. Depth is only assigned to "linked" clauses where at least one term in any atom is already assigned a depth by the previous atoms. Clearly our re­ striction means that variables in clauses are of depth at most 1 but constants may create chains of longer depth. Positive results in ILP [Dzeroski et al., 1992; Cohen, 1995a] show that a single non-recursive (or with limited recursion) determinate clause of constant depth is learnable in polynomial time. However, relaxing any of the restrictions, to 2 clauses, non-constant depth, recur­ sive clauses, or non determinate clauses makes the prob­ lem computationally hard [Kietz and Dzeroski, 1994; Cohen, 1995b; Cohen and Page, 1995].

3 Previous ILP work for similar problems [Cussens, 1997; Dzeroski and Erjavec, 1997] use a different formalization and are therefore not directly comparable here.

On the other hand, there are heuristics for learning programs with more than one rule and these may be used here as well [Muggleton and De Raedt , 1994; Cussens, 1997]. Another way to make the problem tractable is to use queries. In particular, for entailment membership queries, the learner presents a new example (Sn ---+ Pn) and asks whether it is implied by the target. If a user can answer such questions or if one can otherwise simulate these then techniques from [Khardon, 1998; Reddy and Tadepalli, 1998] can be used to learn programs with more than one rule.

To summarize, the restriction imposed by using quan­ tified propositions creates a situation that is similar to determinacy and constant depth in that it reduces the complexity of the learning problem but is incomparable to these. One important difference is the fact that deter­ minacy is a property of the data that may not hold for every domain whereas our restriction is purely syntactic.

4.2 Using Quantified Propositions

In the rest of this section we concentrate on the prob­ lem of learning a single rule that uses quantified propo­ sitions and can be expressed given the predicates in the representation of the sentence. To make this concrete, in terms of the examples above, we might be trying to learn the rule R3 from sentence representations that include bef(),ppos(),JI(),h(). In the next section we discuss combining rules learned separately in a single system.

Projection

A possible reduction in complexity comes from splitting the learning task into a few smaller ones. This is natural for part of speech tagging. It seems unlikely that the same condition can be used to predict the part of speech of, say, both nouns and verbs. Therefore, it may be bet­ ter to avoid trying to learn a general rule of the form condition ---+ pos( x, y) and instead learn a set of rules, one (or more) for each part of speech, e.g. ( condition1 ---+ pos(x, noun)), (condition2 ---+ pos(x, verb)) etc. If gen­ eral patterns do not occur (and thus will not be useful) then we are effectively reducing the complexity of the learning problem.

One can think of this as projecting the relation pos(x, y) over its second argument (the pos tag), where pas() is implemented as a logical disjunction of the var­ ious sub-relations. This clearly works if the instances describe disjoint sets, which they do. The projection we use here (for pos()) depends on the label of the exam­ ple. This does not cause a problem during the learning process but one may need to resolve between competing learned rules when the programs are used. Other pro­ jections, that depend only on the input sentence, can be used in other NLP tasks. In fact, this has been done implicitly in NLP studies, where the task is defined as disambiguating between a small set of candidates. 4

Our examples of projections simply partition the learned predicate into several disjoint parts, where the parts are identifiable in advance, and all parts are needed (e.g. we need to learn pos(x, y) for each possible value of y). Projection learning [Valiant, 1998b] provides some more general conditions under which learning projec­ tions on the input space is guaranteed to work. This holds even if one has a set of projections that is not dis­ joint and not all projections are needed. In addition, as we discuss below, this can be done in an attribute efficient manner.

Using Propositional Learning Algorithms

As presented in Sec. 3.2 the Neuroidal Architecture [Valiant, 1998a] restricts the use of rules so that quan­ tified variables in different parts of the condition can be evaluated separately from the others. The main advan­ tage of this restriction is that it allows one to encode relational learning examples into a propositional setting. Consider learning the rule

R7 = [Yx,((::lylcl(x,y1)) 1\ (::ly2c2(x,y2)))-+ new(x)] where c1 () and c2 () are the features used in the repre­ sentation. For a sentence representation S and a bind­ ing of the variable x (which determines the example provided to the learning algorithm) each predicate in a rule (e.g. :3y1 c1 ( x, y1)) is assigned a single binary value. Thus an example can be described by assigning a binary value to each of the given features. In our example sen­ tence (learning R3 in terms of be f (), ppos (), h (), h ()) for x =this we have h(x) = 1, h(x) = 0, bef(x,can) = 1, and for x =can we have fl(x) = 1, h(x) = 1, and bef(x, can) = 0. Since an example always specifies the binding for the atom in the consequent this can always be done. 5 As a result, under this restriction any proposi­ tional learning algorithm can be used for learning, even though the rule itself is relational! The rule learned is an approximation to an equivalence rather than an im­ plication [Valiant, 1999].

4 When learning to perform context sensitive spelling, the task is to decide what is the correct word to use for a given confusion set e.g. piece or peace. In this case, projection on the confusion set (i.e., learning for piece, peace and for weather, whether separately) makes sense since it is unlikely that the same condition will disambiguate different sets.

5 This should be contrasted with the expression R5 = [Vx, (:Jy, c1 (x, y) 1\ c2 (x, y) -t new(x) )] where for each bind­ ing for y we still get a binary value for each attribute, but these binary values are dependent upon each other, so that the example cannot be described simply using a set of binary values.

Dealing with Many Attributes

Recall that in the ILP setting an example is a clause of the form (S -+ p), implicitly assuming that the atoms that do not hold in the sentence are irrelevant for it. This "closed world assumption" is especially important if the number of atoms that hold in a sentence (positive atoms) is much smaller than the number of those that do not hold in it (negative atoms). This is likely to be the case in the current context especially if we use features that are partly ground, such as bef(x, can), bef(x, will), bef(x, table) etc., repeated for every word in our lexicon. In this setting, the number of potential features may be in the order of 10 5 and explicitly mentioning all of them may be computationally costly.

Therefore, when using a propositional learning algo­ rithm in this setting one would like to make sure that the algorithm handles only the features active in the ex­ ample and, preferably, does not even represent negative features since even their representation and manipula­ tion will be time consuming. In turn, this efficiency requirement may imply that the program learned can­ not depend on negative features. The infinite attribute model suggested by Blum [1992] provides a theoretical framework in which this can be studied. In this model, an example is represented as a list of the attributes that are active in it, and a learning algorithm is required to be efficient (polynomial) in terms of the number of the fea­ tures active in the examples rather than the total num­ ber of attributes. To a certain extent, algorithms in the infinite attribute model can deal with negative features [Blum, 1992].

Attribute Efficient Algorithms

The sample complexity - the number of examples re­ quired in order to achieve learnability - is another im­ portant aspect that requires attention. Consider the case when the target program depends only on nr (relevant) attributes, which is small relative to ne, the number of attributes active in any particular example, and very small relative to na the number of potential attributes. As indicated above, this is realistic in many NLP prob­ lems, in which the number of potential attributes de­ pends on the size of the lexicon. In this case, one would like the number of examples required for learning the program to depend only weakly on ne or na. Little­ stone's Winnow algorithm [Littlestone, 1988] (adapted to the infinite attribute model) can achieve this and re­ quires 0( nr log ne) examples. That is, the number of examples needed is independent of na and depends only logarithmically on ne.

An important aspect of projection learning, as men­ tioned previously, is that it can be achieved attribute efficiently [Valiant, 1998b]. This requires no special at­ tention if the projection forms a partition, as in the POS example, but even in a more general case when we have a large number of projections of which only a small num­ ber is relevant, there is a logarithmic dependence on the number of irrelevant projections.

Target-Word Centered Representation

Our initial description used a single representation for a sentence, as in Eq. (1). In this formulation, a single sen­ tence gives rise to several examples, each corresponding to the part of speech of a word in the sentence, but all have the same relational representation and differ only in their label. It is thus worth noting that when using the propositional translation this does not hold. In par­ ticular, the Boolean value of the features depends on the binding for x, the word for which we are trying to pre­ dict the part of speech. In this way, a sentence produces several examples, each corresponding to a word and its part of speech, but the propositional representation of each of these examples is different.

5 The SNoW System

The SNoW system 6 provides an architecture within which several learning algorithms - all making predic­ tions using linear functions over the feature space - can be implemented. The architecture is a network of linear t hreshold gates. Nodes in the input layer of the network represent simple relations on the input sentence and are being used as the input features. Target nodes represent features for which programs are sought. Target nodes are linked via weighted edges to input features; if Ft is the set of features linked to the target node t, Wi is the weight associated with the ith feature, and Bt is a thresh­ old associated with t , we can say that t is represented by the generalized rule

Each SNoW unit may include a collection of subnet­ works, one for each of the relations for which a program is learned. A given example is treated autonomously by each target subnetwork; an example labeled t is treated as positive example by the subnetwork fort and as a neg­ ative example by the rest of the target nodes (modulo projection considerations). The learning policy is on­ line and mistake-driven, and the most successful update rule used within SNoW is the Sparse Winnow Algorithm. This is a variant of Littlestone's [1988] multiplicative up­ date rule, tailored to the situation in which the set of input features is not known a priori, as in the infinite attribute model [Blum, 1992]. Once target subnetworks have been learned and the network is being evaluated, a decision support mechanism is employed to select the dominant active target node in the network or to output an otherwise coherent output [Munoz et al., 1999].

Originally, the SNoW system was described as a propositional system. In the rest of this section we shall detail a new interpretation of it as a relational system.

6 0ther NLP learning systems like Brill's system [1995] also incorporate some of the aspects we present; in particular, they use similar features and decompose the tasks similarly. However, SNoW corresponds more directly to the Neuroidal Architecture in its use of threshold elements.

We briefly discuss how some of the aspects presented ear­ lier are reflected in the design of the system, and then present a few more pragmatic aspects that are some­ what harder to discuss theoretically at this point. Most of these aspects have been evaluated experimentally and found to perform successfully on a variety of NLP tasks. In particular, single SNoW units have been evaluated on context-sensitive spelling correction [Golding and Roth, 1999]; chaining of SNoW units (as well as other as­ pects) has been studied in [Roth and Zelenko, 1998; Munoz et al., 1999] several aspects of projections have been studied in [Rosen, 1999], and a preliminary study of incorporating background knowledge by augmenting the input features is in [Krymolovsky and Roth, 1998] .

5.1 Sentence representation

While the description above suggests that SNoW uses a propositional representation, a relational representa­ tion of sentences as in Eq. (1) is used. This is done by utilizing quantified propositions and using a proposi­ tional representation of these as features. Accordingly, examples are target-word centered and a single relational sentence representation may give rise to several proposi­ tional examples, corresponding to the target word.

Quantified propositions include features with con­ stants (as in hO in Sec. 3) and existential features (as in h () in Sec. 3). The system generates the features and the word-centered representation automatically using a simple language for relational feature definitions. Specif­ ically, features are relations of the form 3y, c(x, y) where the predicate c() is one of three types: ( 1) relations that can be readily read from the sentence, like bef(this, can). (2) Relations that become active as a result of evaluat­ ing other, previously learned programs. (3) Relations that are read from an outside source. These may in­ clude predicates like isa(), and synonym(). In this way background knowledge is incorporated in a transparent way and plays the same role in the representation as do simpler predicates.

The predicate c() can also be a small conjunction of predicates of the above types. The pattern for existen­ tial features is restricted to bind words within a fixed distance of the target word. Thus, h () above can be rephrased as "ppos(y, verb) holds for the word y which is two positions to the right of x". Notice that due to the semantics of bej(), these features are determinate in any rule; more general features like "ppos(y, verb) holds for some wordy which is at most 5 positions away from x" are also used, but they too have bounded determinacy.

The above syntactic description generates a large num­ ber of possible features. Following the positive sentence representation principle discussed above, features are al­ located only if they are active in the example sentence. The architecture supports a limited use of negative fea­ tures by learning several programs at the same time and using positive features for one program as potential neg­ ative features for others.

5.2 Learning

• SNoW is a propositional learning system that uses linear threshold functions over the set of quantified propositions as its knowledge representation.
• Two complementary aspects of projection are han­ dled in SNoW. Precondition projection is similar to the one described above. This is a condition ap­ plied to the input representation (either just the sentence or the label as well) that is employed to learn several target programs rather than a single, more abstract, program as described above for POS and the spelling examples. In this way, different examples can be used to train different programs. Task projection is a form of projection that is em­ ployed at prediction time, when several learned pro­ grams are being evaluated, and is used to restrict the programs that are being evaluated on a given input example, thereby simplifying the prediction process. For example, when learning programs for each of the possible POS, a (learned) task projec­ tion may prevent the evaluation of the pos(x, adj) program given that the target word is can. In par­ ticular, this form of projection addresses one of the issues discussed above, when the projection is with respect to the label. An experimental evaluation of the forms of projections within SNoW, exhibiting both significant efficiency and performance gains is presented in [Rosen, 1999].
• SNoW implements several on line learning algo­ rithms for linear functions, including variations of Winnow, Perceptron, naive Bayes and a memory based algorithms (the last two use only positive ex­ amples for learning) . In all cases, the variation im­ plemented is tuned to (be on-line and) deal with many attributes along the lines described above. This is imposed by the sparse architecture of the system, which assigns a positive weight to a feature only if it is active together with the target predicate in a single example.

5.3 Other Pragmatic Issues

• SNoW can learn programs that are represented in terms of predicates which are themselves conse­ quents of other programs (that were learned pre­ viously). Thus SNoW supports chaining of learned programs assuming that each of the learning stages is supervised. One difficulty in this process is that learned rules may not be completely accurate, resulting in potentially noisy input to the other learning stages. This imposes another practical constraint on the algorithms used in this setting, namely robustness to attribute noise.
• SNoW allows for some use of recursive rules in the following way. When learning from labeled data, the pas() labels are available for all words and may be included in the input representation. As a result, the learned rule may be recursive in that it includes pas() predicates in the antecedent.

However, when evaluating the learned program for pos() on new sentences that are not annotated, one needs to initialize the pos() predicates in the an­ tecedent in some way (e.g., use the most frequent part of speech for each word) and then, the same program may be applied to the sentence represen­ tation (even several times) as to improve the ap­ proximate input representation before the output pos() is decided upon [Roth and Zelenko, 1998; Munoz et al., 1999] .

• Finally, whenever a collection of programs is learned, given an input sentence, there is a need to make a decision that may involve several learned programs. In particular, as in POS, the programs compute competing pos tags and there isa need for a procedure that determines which of them to se­ lect. (Note that in SNoW this results from the use of projection.) SNoW employs a few mechanisms for decision making including a winner-take-all mecha­ nism and a learned decision making mechanism.

6 Discussion

Based on an analysis of SNoW in terms of the Neu­ roidal Architecture, we presented a framework describ­ ing SNoW as a relational learning system and explained its relation to ILP. This, in particular, facilitates future comparative studies involving SNoW and ILP.

Since the theory presented is more general than cur­ rent implementations, extensions of SNoW along the lines suggested by the theory may provide new levels of scalability and functionality. This is, however, not straightforward and requires careful consideration. Ad­ ditionally, our analysis may provide guidelines for further analysis of some issues which are not well understood yet.

One of the issues that can be addressed in future work is the following tradeoff: adding more complex existen­ tial features to the representation increases computa­ tional complexity, but at the same time results in more expressive programs and more significant gain from the use of attribute efficient algorithms. A second issue is the use of more general forms of projections. Finally, one advantage of relational methods is the ability to choose the right features dynamically and in fact change them during the learning process. For example, if a sentence includes the atom bef(can, will), this feature may be needed as part of a learned rule. Naturally, we do not know in advance whether the feature should be ground or whether a more general form, one of bef(x, will), bef(can, y), or bef(x, y) should be used. In the current propositional setting, each of these is used separately as a feature and the learning algorithm may use any of them. On the other hand, computing the least general general­ ization [Plotkin, 1970] over several example sentences we may be able to find the right general form of the feature. It is not clear whether a technique that changes the fea­ tures in this way, during the on-line process of learning, can be incorporated in the propositional setting.