Learning in Natural Language

1 Introduction

Generative probability models provide a principled way to the study of statistical classification in complex do­ mains such as natural language. It is common to assume a generative model for such data, estimate its parame­ ters from training data and then use Bayes rule to ob­ tain a classifier for this model. In the context of natural language most classifiers are derived from probabilistic language models which estimate the probability of a sen­ tence s, say, using Bayes rule, and then decompose this probability into a product of conditional probabilities according to the generative model assumptions.

----- *Research supported by NSF grants IIS-9801638 and SBR-9873450.

This general scheme has been used to derive classifiers for a variety of natural language applications including speech applications [Rabiner, 1989], part of speech tag­ ging [Kupiec, 1992; Schiitze, 1995], word-sense disam­ biguation [Gale et al., 1993], context-sensitive spelling correction [Golding, 1995] and others. While the use of Bayes rule is harmless, most of the work in statistical language modeling and ambiguity resolution is devoted to estimating terms of the form Pr(wlh). The genera­ tive models used to estimate these terms typically make Markov or other independence assumptions. It is evident from looking at language data that these assumptions are often patently false and that there are significant global dependencies both within and across sentences. For ex­ ample, when using (Hidden) Markov Model (HMM) as a generative model for the problem of part-of-speech tag­ ging, estimating the probability of a sequence of tags in­ volves assuming that the part of speech tag t; of the word w; is independent of other words in the sentence, given the preceding tag t;_1 . It is not surprising therefore that making these assumptions results in a poor estimate of the probability distribution density function 1 . However, classifiers built based on these false assumptions never­ theless seem to behave quite robustly in many cases.

In this paper we develop a learning theory account for this phenomenon. We show that a variety of models used for learning in Nat ural Language make their predic­ tion using Linear Statistical Queries (LSQ) hypotheses. This is a family of linear predictors over a set of fairly simple features which are directly related to the indepen­ dence assumptions of the probabilistic model assumed. We claim that the success of classification methods which are derived from incorrect probabilistic density estima­ tion is due to the combination of two factors:

• The low expressive power of the derived classifier.
• Robustness properties shared by all linear statistical queries hypotheses.

1 Experimental evidence to that effect will not be included in this extended abstract for lack of space (but see Sec. 5).

We define the class of LSQ hypotheses and prove these claims. Namely, we show that since the hypotheses are computed over a feature space chosen so that they per­ form well on training data, learning theory implies that they perform well on previously unseen data, irrespec­ tive of whether the underlying probabilistic assumptions hold. We then show how different models used in the lit­ erature can be cast as LSQ hypotheses by selecting the statistical queries (i.e., set offeatures) appropriately and how this affects the robustness of the derived hypothesis.

The main contribution of the paper is in providing a unified learning theory account for a variety of methods that are widely used in natural language applications. The hope is that providing a coherent explanation for when and why learning approaches work in this context could help in developing better learning methods and a better understanding of the role of learning in natural language inferences.

We first present learning theory preliminaries and then define the class of linear statistical queries hypotheses and discuss their properties. In Sec. 4 we show how to cast known probabilistic predictors in this framework, and in Sec. 5 we discuss the difference between LSQ learning and other learning algorithms.

2 Preliminaries

In an instance of pac learning [Valiant, 1984], a learner needs to determine a close approximation of an un­ known target function from labeled examples of that function. The unknown {0, 1 }-valued function g is as­ sumed to be an element of a known function class Q over the instance space X = { 0, 1} n, and the exam­ ples are distributed according to some unknown prob­ ability distribution D on X. A learning algorithm draws a sample of labeled examples according to D and even­ tually outputs a hypothesis h from some hypothesis class H. The error rate of the hypothesis h is defined to be error( h)= PrD[h(x) =/=- g(x)]. The learner goal is to out­ put, with probability at least 1 - 8, a hypothesis h E 1i whose error rate is at most c, for the given error parame­ ter c and confidence parameter 8, using sample size that is polynomial in the relevant parameters. The learner is then called a pac learner. The algorithm is an efficient pac learning algorithm if this is done in time polynomial in the relevant parameters.

A more realistic variant of the pac-learning model, the agnostic learning model [Haussler, 1992; Kearns et al., 1992], applies when we do not want to assume that the labeled training examples (x, l) arise from a target con­ cept of an a-priori simple structure g E Q. In this model one assumes that data elements (x, l) are sampled ac­ cording to some arbitrary distribution Don X x {0, 1}. D may simply reflect the distribution of the data as it occurs "in nature" (including contradictions) with­ out assuming that the labels are generated according to some "rule" . The true error of the hypothesis h is defined to be errorD(h) = Pr(x,l)ED[h(x) =/=- l], and the goal of the learner is to compute, with high probability, a hypothesis h E 1i with true error not larger than c + infhE1ierrorD(h). A learner that can carry out this task for any distribution D is called an efficient ( agnos­ tic) pac learner for hypothesis class 1i if the sample size m(c, 8) and the time required to produce the hypothesis are polynomial in the relevant parameters.

In practice, one cannot compute the true error error D (h), and in many cases it may be hard to guaran­ tee that the computed hypothesis h is close to optimal in 1{. Instead, the input to the learning algorithm is a sam­ ple S = { (xi, li)} r; 1 of m labeled examples, the learner tries to find a hypothesis h with a small empirical error

and hopes that it behaves well on future examples.

The hope that a classifier learned from a training set will perform well on previously unseen examples is based on the basic theorem of learning theory [Valiant, 1984; Vapnik, 1995] which, stated informally, guarantees that if the training data and the test data are sampled from the same distribution, good performance on large enough training sample guarantees good performance on the test data (i.e., good "true" error). This is quantified in the following uniform convergence result:

Theorem 2.1 ([Haussler, 1992]) If the size of the training sampleS is at least m(c,8) = ~(kVC(H) + ln: + ln ~) then with probability at least 1 - 8,

where k is some constant and VC(H) is the VC­ dimension of the class 1i [Vapnik, 1982], a combinatorial parameter which measures the richness of 1i.

In practice the sample size lSI may be fixed, and the result simply indicates how much can one count on the true accuracy of a hypothesis selected according to its performance on S. Also, the computational problem of choosing a hypothesis which minimizes the empirical er­ ror on S (or even approximates a minimum) may be hard [Kearns et al., 1992; Hi:iffgen and Simon, 1992]. Finally, notice that the main assumption in the theorem above is that the training data and the test data are sampled from the same distribution; Golding and Roth [1999] discuss this assumption in the NLP context.

3 Robust Learning

This section defines a learning algorithm and a class of hypotheses with some generalization properties, that we later show to capture many probabilistic learning meth­ ods used in NLP. The learning algorithm discussed here is a Statistical Queries(SQ) algorithm [Kearns, 1993]. An SQ algorithm can be viewed as a learning algorithm that interacts with its environment in a restricted way. Rather than viewing examples, the algorithm only re­ quests the values of various statistics on the distribution of the labeled examples to construct its hypothesis. (E.g. "What is the probability that a randomly chosen labeled example (x, l) has x; = 0 and l = 1"?) A feature is an in­ dicator function x : X -+ {0, 1} which defines a subset of the instance space- all those elements which are mapped to 1 by X· X denotes a class of such indicator functions. X can be viewed as a transformation of the instance space X; each example (x1 , ... xn) EX is mapped to an example (Xl,X2,···XIXI) in the new space. To simplify notation, we sometimes view a feature as an indicator function over the labeled instance space X x { 0, 1} and say that x(x, l) = 1 for examples x E x(X) with labell.

A statistical query has the form [x, l, T], where x E X is a feature, l E {0, 1} is a further (optional) restriction imposed on the query and T is an error parameter. A call to the SQ oracle returns an estimate P, 1 D 1 1 of X, , T

which satisfies IFx- Pxl < T. (When clear from the con­ text we omit T and/or l from this notation.) A statistical queries algorithm is a learning algorithm that constructs its hypothesis only using information received from an SQ oracle. An algorithm is said to use a query space X if it only makes queries of the form [x, l, T] where X E X. As usual, an SQ algorithm is said to be a good learning algorithm if, with high probability, it outputs a hypothesis h with small error, using sample size that is polynomial in the relevant parameters.

In order to simulate the behavior of the SQ oracle on a query [x, l, T] on the distribution D, we simply draw a large sample S of labeled examples (x, l) according to D and evaluate

Chernoff bounds guarantee that the number of exam­ ples required to achieve tolerance T with probability at least 1- o is polynomial in 1/T and log 1/o.

The SQ model of learning was introduced by Kearns [1993] and studied in [Decatur, 1993; Aslam and De­ catur, 1995]. It was viewed as a tool for demonstrating that a pac learning algorithm is noise-tolerant. In par­ ticular, it was shown that learning with an SQ algorithm allows the learner to tolerate examples with noisy labels - labels which, with some probability < 1/2, are ·incon­ sistent with the target function (classification noise), as well as various forms of corrupted examples (malicious noise, attribute noise). A typical noise-tolerant learning result in the pac model states that if an SQ algorithm learns a concept class Q, in the sense that it produc~s a hypothesis with small true error, then this algorithm is noise tolerant in that it would have produces a hypoth­ esis with small true error even when trained with noisy data. The running time of the algorithm and the num­ ber of data samples required depend on the tolerance required from the statistical queries. This, in turn, is determined by the noise level the algorithm is required to tolerate (up to some bounds; see the references for details). In the next section we consider a special SQ al­ gorithm and prove a robustness result that may be more satisfying from a practical point of view.

3.1 Linear Statistical Queries Hypotheses

Let X be a class of features and f : { 0, 1} -+ ~ a function that depends only on the values P 1 ~, l] for x E X. A Linear Statistical Queries (LSQ) hypothesis predicts l E {0, 1} given x EX when

Clearly, the LSQ is a linear discriminator over the fea­ ture space X, with coefficients f that are computed given (potentially all) the values P 1 ~, l]. The definition gener­ alizes naturally to non-binary classifiers by allowing l to range over a larger set of labels; in this case, the discrim­ inator between predicting l and other values is linear. A learning algorithm that outputs an LSQ hypothesis is called an LSQ algorithm.

Example 3.1 The naive Bayes predictor [Duda and Hart, 1973} is derived using the assumption that given the label l E L the features ' values are statistically inde­ pendent. Consequently, the Bayes optimal prediction is given by:

where Pr(l) denotes the pnor probability of l (the frac­ tion of examples labeled l} and Pr(x;ll) are the condi­ tional feature probabilities (the fraction nf the examples labeled l in which the ith feature has value x;).

The LSQ definition implies:

Claim 3.1 The naive Bayes algorithm is an LSQ al­ gorithm over a set X which consists of n + 1 features: Xo = 1, Xi =X; fori= 1, ... , n and where

We note that formalized this way, as is commonly done in NLP (e.g., [Golding, 1995}}, features which are not active in the example are assumed unobserved and are not taken into account in the naive Bayes estimation. It is possible to assume instead that features which are not active are false (x = 0}; this assumption yields an LSQ algorithm over the same features, with different coeffi­ cients (see, e.g., [Roth, 1998} for the derivation).

The observation that the LSQ hypothesis is linear over X yiedls the first robustness result. VC dimension theory implies (via a variation of, e.g., [Anthony and Holden, 1993], and due to the restriction LSQ imposes on the coefficients) that:

Claim 3.2 The VC dimension of the class of LSQ hy­ potheses is bounded above by lXI. If all the features used are polynomials of the form x = Ilx;, X; 2 ··· x;k (which are all linearly independent}, the VC dimension of the LSQ hypotheses is exactly lXI.

This, together with the basic theorem 2.1 implies:

Corollary 3.3 For any LSQ learning algorithm and given a performance guarantee on previously unseen ex­ amples (sampled from the same distribution) , the number of training examples required in order to maintain this performance scales linearly with the number of features used.

3.2 Distributional Robustness

LSQ hypotheses are computed by an SQ algorithm; it calls the SQ oracle to estimate P[~,l} for all elements in X, and applies f. Then, given an example x E X it evaluates the hypothesis to make the prediction.

As discussed above, the SQ model was introduced as a tool for demonstrating that a pac learning algorithm is noise-tolerant. In a practical learning situation we are given a fixed sample of data to use in order to generate a hypothesis, which will be tested on a different sample, hopefully "similar" to the training sample. Our goal is to show . that an algorithm that is able to learn under these restrictions (namely, interacting only via SQs) is guaranteed to produce a robust hypothesis. Intuitively, since the SQ predictor does not really depend on spe­ cific examples, but only on some statistical properties of the data, and only within some tolerance, it should still perform well in the presence of data sampled according to a different distribution, as long as it has the same statistical properties within this tolerance.

Next we formalize this intuition and show that the ba­ sic results proved for the SQ model can be adapted to this situation. Formally, we assume that there is a test sample, Stest, generated according to some distribution D', and that we care about our hypothesis' performance on this sample. However, training is performed on a dif­ ferent sample, Strain, generated according to a different distribution D. We show that an SQ hypothesis trained over Strain can still perform well on Stest. if D and D' are not too different. A common distance measure be­ tween distributions is the variation distance 2 d(D, D') = ~ LxEX ID(x)- D'(x)j. It is easy to see that this mea­ sure is equivalent to d(D, D') = maxAcx ID(A) -D'(A)i which is more convenient for our purposes. A more bi­ ased measure, strictly smaller than the standard mea­ sures may also be used in this case:

yielding better robustness guarantees for the algorithm.

Theorem 3.4 Let A be an SQ( r, X) learning algorithm for a function class g over the distribution D and assume that dx(D, D') < "( (for"( inversely polynomial in r ) . Then A is also an SQ(r, X) learning algorithm for Q over D'.

Proof: Since A is an SQ( r, X, D) algorithm, a hypoth­ esis generated with estimates P~ that are r close to P~, behaves well on D. In order for the hypothesis to behave well on D' we can simply run A with oracle calls of tol­ erance r - 'Y to get P~ that is within r - 'Y of P~. By the definition of the distance measure, the difference between the probability of events of interest occurring under D and D' is no more than 'Y and therefore

2 [Yamanishi, 1992] shows that this measure is equivalent to other well known measures such as the KL divergence.

Thus, this procedure simulates estimates that are within r on D', implying a well behaved hypothesis on D'. To simulate the more accurate estimates, with tolerance r - "(, there is a need to use more samples, but only polynomially more due to the relation between 'Y and r.

· For the final point regarding robustness, observe that the proof shows the importance of the tolerance. In prac­ tice, the sample is given, and the robustness of the algo­ rithm to different distributions depends on the sample's size. The richness of the feature class X plays an impor­ tant role here. To ensure tolerance of r for all features in X one needs to use aeog;XI) samples (more generally, 0( vc;x)) samples). For a given size sample, therefore, the use of simpler features in the LSQ representation provides better robustness. This, in turn, can be traded off with the ability to express the learned function with an LSQ over a simpler set of features.

4 Applications: Probabilistic Classifiers

In this section we cast a few widely used probabilistic classifiers as LSQ hypotheses, implying that they are subject to the properties discussed in Sec. 3.

4.1 Naive Bayes

As shown in Example 3.1, the naive Bayes predictor is an LSQ hypothesis. The implication is that this method, which has been widely used for· natural language tasks [Gale et al., 1993; Golding, 1995] satisfies:

Corollary 4.1 The naive Bayes algorithm is a robust learning method in the sense of Cor. 3.3 and Thm 3.4.

4.2 General Bayesian Classifier

The naive Bayes predictor can be generalized in sev­ eral ways. First, one can consider a generalization of the naive model, in which hidden variables are allowed. The simplest generalization in this direction would as­ sume that the distribution is generated by postulating a "hidden" random variable z. Having randomly chosen a value z for the hidden variable, we choose the value for each observable Xi independently of each other.

As a motivating example consider the case of disam­ biguation or tagging in natural language tasks, where the "context" or a tag may be viewed as hidden variables.

The prediction problem here is to predict the value of one variable, given known values for the remaining variables. One can show that the predictor in this setting is again an LSQ that uses essentially the same features as in the simple (observable) naive Bayes case discussed above (e.g., [Grove and Roth, 1998]).

A second generalization of naive Bayes is to assume that the independence structure around the predicted variable x is more complicated and is represented, for ex­ ample, using a Bayesian network that is not as trivial as the naive Bayes network. In this case too, since we care only about predicting a value for a single variable having observed the other variables, it is not hard to verify that the Bayes optimal predictor is an LSQ hypothesis. The features in this case are polynomials X = Ilx;, x; 2 ... x;k of degree that depends on the number of neighbors of x in the network. The details of this analysis are not included for lack of space. Instead, we concentrate on a special case that is of great interest in natural language.

4.3 Markov Models

Markov Models and Hidden Markov Models (HMMs) are a standard model used in language modeling in general and in disambiguation tasks such as part-of-speech (pos) tagging in particular. (See, e.g.,[Rabiner, 1989]; we will assume familiarity with them here). For a bi-gram pos tagger, the states of the HMM are pos tags. Transition probabilities are probabilities of a tag given the previous tag, and emission probabilities are probabilities of a word given a tag. The standard algorithms first estimate the transition and emission probabilities from training data; then they use the Markov model assumption in order to evaluate the probability of a particular part of speech sequence given a sentence. For example, for the part-of­ speech sequence of the sentence this can will rust one computes

Of course, this is correct only under the Markov as­ sumption; namely, one assumes that given a tag for the ith word in the sentence, the value of the word is independent of other words or tags (yielding the term P(caniNN)), and the tag of the i + 1 word is indepen­ dent of preceding tags (yielding P(M DIN N)). In order to tag a sentence for pos one needs to maximize this term over all possible assignments of pos tags. This is usually done using a dynamic programming technique, e.g., a variation of the Viterbi algorithm.

Here we will be interested in the main computational step in this process - predicting the pos of a single word, given the sentence and assuming the pos of all the neigh­ boring words as input. We will disregard the global opti­ mization of finding the best simultaneous pos assignment to all words in the sentence 3 . We call this predictor the Markov predictor. For this prediction, it is easy to see that given an example

3 Interestingly, experimental studies have shown that sometimes the global optimization is not required and the local predictions actually produce better results [Deicher et

al., 1993; Roth and Zelenka, 1998] .

we predict pos( w;) = t iff t E T maximizes

or, equivalently,

where T is the set of all possible pos tags. In the above example, for the word 'can' we will select the tag t that maximizes P(tiDT) · P(canit) · P(MDit).

Let T, W denote the sets of all tags t and all words w, resp., which occur in the examples. In order to represent the Markov predictor as an LSQ algorithm we use X= { T, W, 1} x { T, W, 1}, the set of all singletons and pairs of words and tags. With this set of features and the notation introduced in Eq. 1 it is clear that the Markov predictor above can be written as an LSQ hypothesis:

where

and otherwise, f[x,t] () = 0.

Notice that in this formalization each word in the sen­ tence yields a single training example and features are computed with respect to the word for which the tag is to be predicted. We get that:

Claim 4.2 The Markov predictor is an LSQ algorithm over a set X of singletons and pairs of words and tags. Therefore, the Markov predictor is a robust learning method in the sense of Cor. 3.3 and Thm 3.4. This fact naturally generalizes to higher order Markov predictors by increasing the expressivity of the features.

4.4 Maximum Entropy Models

Maximum Entropy (ME) models [Jaynes, 1982] are ex­ ponential distributions which satisfy given constraints. Constraints are what we have called features and the distribution is defined in terms of the expected value of the feature over the training set. These models have been used successfully to generate predictors for several disambiguation tasks [Ratnaparkhi et al., 1994; Ratnaparkhi, 1997], typically by estimating the ME probability model for the conditional probability p(wih) (as in Sec. 1).

It can be shown that the distribution that maxi­ mizes the entropy and is consistent with a set of con­ straints (features) x E X must have the form PME = Il k Xj(x) h . 1' . d c j=l aj , w ere c IS a norma 1zatwn constant an the Ctj are the model parameters. Each parameter Ctj corresponds to exactly one feature Xi and can be viewed as the weight of that feature.

Predictions using the ME model are performed as fol­ lows. Given that the probability distribution PM E has been estimated as above, and given the observed sen­ tence s we would predict

Equivalently, by taking logarithms, we get a linear deci­ sion surface over the feature space.

However, while the optimal coefficients for an ME pre­ dictor are also a function of the features' statistics over the training data, they cannot be written explicitly. In­ stead, an iterative algorithm (e.g., [Darroch and Ratcliff, 1972]) that approximates the optimal coefficients (but is not known to converge efficiently) is required. The ME predictor is thus a Linear predictor but, strictly speak­ ing, in its optimal form is not an SQ algorithm.

5 LSQ vs. Consistent Learning

In this section we discuss an important difference be­ tween an LSQ algorithm and "standard" learning algo­ rithms, using the naive Bayes classifier as a running ex­ ample. In most cases, algorithms studied in Machine Learning search for a hypothesis that is (almost) consis­ tent with the training data and then rely on Thm 2.1 to guarantee good performance in the future. An LSQ algorithm, on the other hand, need not seek consistency. It simply computes a hypothesis from the responses of the SQ oracle and uses that hypothesis to make future predictions. Indeed, it is easily verified that the hypoth­ esis produced by, say, a naive Bayes algorithm may not be consistent with the data that was used to compute it. Nevertheless, when the data satisfies the probabilistic as­ sumptions used to derive the predictor, namely features' values are independent given the label, this hypothesis is the optimal predictor for future examples (although it may still make many mistakes). However, when the probabilistic assumptions do not hold, the success of the predictor is directly related to its success on the training data.

Consistency (or almost consistency) is not a trivial re­ quirement . In fact, it is hard to come up with structural properties of classes for which naive Bayes is an optimal predictor. Even when the target concept is very simple - the class of Boolean conjunctions - consistency is not achieved in general, and the naive Bayes algorithm is not a good predictor for this class 4 .

Example 5.1 Consider the Boolean conjunction f = x1 1\ x2 over over { x1 , x2 , ... Xn}. Assume that exam­ ples are generated according to the following distribution: Exactly half of the examples are positive. Over the pos­ itive examples necessarily x 1 = x2 = 1 and we define X3 = X4 = xs, and that this value is 1 with probability 1/2. x6 , ... Xn are 1 with probability 1/2, independently of anything else. Over the negative examples x 1 is 1 with probability 1/2 and x 2 =f. x 1 . x 3 = x4 = x 5 and this value is 1 with probability 7/8. x 6 , . . . Xk are 1 with probability 1/2, independently of anything else.

4 Domingo&Pazzani claim in a 1998 MLJ paper that naive Bayes is optimal for Boolean conjunctions and disjunctions. Their proof, however, holds only for product distributions, for which the naive Bayes assumptions hold. The following example may be viewed as a counterexample to a more gen­ eral interpretation of their claim.

In this way we have that p(x1 ll = 1) = p(x2ll = 1) = 1 and p(x; = 111 = 1) = 1/2 for i = 3, ... k. For the negative examples we have that p(x; = 111 = 0) = 7/8 fori= 3, 4, 5 and p(x;l l = 0) = 1/2 for i =f. 3, 4, 5.

It is now easy to see that while the naive Bayes algo­ rithm does not make mistakes on negative examples of a conjunction, it will predict incorrectly on half of the positive examples, all those for which x 3 = x4 = x 5 = 1.

Clearly, this behavior is indicative of the performance of this predictor on any data presented to it which is sampled according to this distribution.

Practitioners, however, do not simply compute the LSQ hypothesis and use it, confident that it performs well since (when the assumptions of the underlying model hold) it represents the maximum likelihood hy­ pothesis. Instead, they spend time choosing a feature set with which the predictor performs well on the train­ ing set. Once this is achieved, according to the results in Sec. 3, the predictor behaves well on previously unseen examples, but this happens regardless of whether the un­ derlying probabilistic assumptions hold 5 . The only limi­ tation on growing the feature set is the relation between the expressiveness of these features and the sample size required to achieve small tolerance, which we have al­ luded to. The role of the probabilistic assumptions in this case may be viewed as supplying guidance for se­ lecting good features.

The question of why it is that even in seemingly hard NLP tasks, the search for good features is fairly sim­ ple, making it unnecessarily to resort to very expressive features, is an orthogonal question that we address in a companion paper. For the sake of the argument de­ veloped here, it is sufficient to realize that all the al­ gorithms presented rely on their good behavior on the training set, and thus behave well even if the probabilis­ tic assumptions that were used to derive the predictor do not hold.

6 Conclusion

In the last few years we have seen a surge of empiri­ cal work in natural language. A significant part of this work is done by using statistical machine learning tech­ niques. Roth [1998] has investigated the relations among some of the commonly used methods and taken prelimi­ nary steps towards developing a better theoretical under­ standing for why and when different methods work. This work continues to develop the theoretical foundations of learning in natural language, focusing on the study of probabilistic density estimation models and their use in performing natural language predictions.

5 Experimental evidence to this effect is presented in [Gold­ ing and Roth, 1999] . Two sets of features are compared. The one which provides a better conditional probability estima­ tion, by virtue of better satisfying the independence assump­ tion, nevertheless supports significantly worse performance on the prediction task.

In addition to providing better learning techniques, developing an understanding for when and why learn­ ing works in this context is a necessary step in studying the role of learning in higher-level natural language in­ ferences.

Acknowledgments

I am grateful to Jerry DeJong, Lenny Pitt and anony­ mous referees for their useful comments on an earlier version of this paper.