{'fraction_non_alphanumeric': 0.029344871581516614, 'fraction_numerical': 0.0051589282742552835, 'mean_word_length': 4.839974084872044, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Prediction of Lexicalized Tree Fragments in Text

There is a mismatch between the distribution of information in text, and a variety of grammatical formalisms for describing it, including ngrams, context-free grammars, and dependency grammars. Rather than adding probabilities to existing grammars, it is proposed to collect the distributions of flexibly sized partial trees. These can be used to enhance an ngram model, and in analogical parsing.


THE PROBLEM WITH PROBABILIZED GRAMMARS
For a variety of language processing tasks, it is useful to have a predictive language model, a fact which has recently led to the development probabilistic versions of diverse grammars, including ngram models, context free grammars, various dependency grammars, and lexicalized tree grammars. These enterprises share a common problem: there is a mismatch between the distribution of information in text and the grammar model.
The problem arises because each grammar formalism is natural for the expression of only some linguistic relationships, but predictive relationships in text are not so restricted. For example, context-free grammars naturally express relations among sisters in a tree, but are less natural for expressing relations between elements deeper the tree. In this paper, first we discuss the distribution of information in text, and its relationship to various grammars. Then we show how a more flexible grammatical description of text can be extracted from a corpus, and how such description can enhance a language model.

Ngram Models
The problem can be seen most simply in ngram models, where the basic operation is to guess the probability of a word given n -1 previous words. Obviously, there is a deeper structure in text than an n-gram model admits, though thus far, efforts to exploit this information have been only marginally successful. Yet even on its own terms, ngram models typically fail to take into account predictive information.
One way that ngram models ignore predictive information is in their strategy for backing off. Consider, for example, a trigram model where the basic function is to predict a word (wo) given the two previous words (W_l and w-2). In our Wall Street Journal test corpus, the three word sequence give kittens to appears once, but not at all in the training corpus.
Thus, a trigram model will have have difficulty predicting to given the words give kittens.
In this case, the standard move of backing off to a bigram model is not very informative. It is more useful to predict to using the word give than the word kittens, because we know little about what can follow kittens, but much about what typically follows give. We would expect for cases where the bigram (w_ 1,w0) does not exist, the alternative bigram (w_2,wo) will be a better predictor (if it exists) than the simple unigram.
Obviously, in this example, the fact that complementation in English is not expressed purely by adjacency explains some of the power of the w_ 1 predictor.
A second problem with ngram models arises because different word sequences call for a greater or smaller n. For example, while many 6-grams are unique and uninformative, some are powerful predictors. A second problem is that CFG's naturally abstract away from syntactic function: for example, in a CFG, a noun phrase is described by the same set of rules whether it occurs as subject, object, object of preposition or whatever. While this ability to generalize across contexts is a strength of CFG's, it is disastrous for guessing whether a noun phrase will be a pronoun or not. Table 2 shows the probabilities of a noun phrase being realized as a pronoun in various contexts, in a sample of spoken and written texts produced by college students and matched for content (Hindle 1978). Clearly, ignoring whether a noun phrase is subject or not reduces the effectiveness of a predictive model. (Note too that the differences between spoken and written English are not to be ignored. There are of course ways to admit lexical and functional information into a CFG. But except for carefully restricted domains (e.g semantic grammars), these typically lead to an explosion of nonterminals and rules, making parameter estimation difficult.  Dependency Grammars Dependency grammars naturally address part of the mismatch between CFG's and predictive associations, since they are expressed in terms of relations between words (Melcuk 1988), Nevertheless, in dependency grammars as well, certain syntactic relationships are problematic.
In dependency grammar, there are two competing analyses both for noun phrases and for verb phrases. For noun phrases, the head may be taken to be either 1) the head noun (e.g. man in the men) or 2) the determiner (e.g the in the men); analogously, for verb phrases, the head may be taken to be either 1) the mail verb (e.g. see in had seen) or 2) the tensed verb of the verb group (e.g have in had seen). Each analysis has its virtues, and different dependency theorists have preferred one analysis or the other. It is not our purpose here to choose a dependency analysis, but to point out that whatever the choice, there are consequences for our predictive language models. The two models imply different natural generalizations for estimating probabilities, and thus will lead to different predictions about the language probabilities. If the determiner is taken to be the head of the noun phrase, then in guessing the probability of a verb-det-noun structure, the association between the verb and the determiner will predominate, since when we don't have enough information about a verb-det-noun triple, we can back off to pairs. Conversely, if the noun is taken to be the head of the noun phrase, then the predominant association will be between verb and noun. (Of course, a more complex relationship between the grammar and the associated predictive language model may be defined, overriding the natural interpretation.) A ten million word sample of Wall Street Journal text was parsed, and a set of verb-det-noun triples extracted. Specifically, object noun phrases consisting of a noun preceded by a single determiner preceded by a verb were tabulated. That is, we consider only verbs with an object, where the object consists of a determiner and a noun. The five most common such triples (preceded by their counts) were:  Table 3: Three predictive models for verb-det-noun triples in Wall Street Journal text ignore predictive information, assuming in the first case that the choice of noun is independent of the verb, and in the second case, that the choice of determiner is independent of the verb. Neither assumption is warranted, as Table 3 shows (both have higher entropy than the trigram model), but Model 1, the determiner=head model, is considerably inferior. Model 1 is for this case like a bigram model, and Table 3 makes it clear that this is not a particularly good way to model dependencies between verb and object: the dominant dependency is between verb and noun.
In terms of using the distributional information available in text, neither choice is correct, since the answer is lexicaUy specific. For example, in predicting the object of verbs, answer is a better predictor of its object noun (call, question), while alter is better a predicting its determiner (the, its).
In contrast to dependency grammars and context free grammars, lexicalized tree adjoining grammars have considerable flexibility in what relations are represented, since the tree is an arbitrary-sized unit (Shabes 1988). In practice however, lexicalized TAGs have typically been written to reduce the number of rules, and thus to assume independence like other grammars. In general, for any grammar that is written without regard to the distribution of forms in text, simply attaching probabilities to the grammar will always ignore useful information. This does not imply any claim about the descriptive power of various grammar formalisms; with sufficient ingenuity, just about any recurrent relation that appears in a corpus can be encoded in any formalism. However, different grammar formalisms do differ in what they can naturally express.
There is a clear linguistic reason for the mismatch between received grammars and the distribution of structures in text: language provides several cross cutting ways of organizing information (including various kinds of dependencies, parallel structures, listing, name-making templates, etc.), and no single model is good for all of these.

USING PARTIAL STRUCTURES
The preceding section has given evidence that adding probabilities to existing grammars in several formalisms is less than optimal since significant predictive relationships are necessarily ignored. The obvious solution is to enrich the grammars to include more information. To do this, we need variable sized units in our database, with varying terms of description, including adjacency relationships and dependency relationships. That is, given the unpredictable distribution of information in text, we would like to have a more flexible approach to representing the recurrent relations in a corpus. To address this need, we have been collecting a database of partial structures extracted from the Wall Street Journal corpus, in a way designed to record recurrent information over a wide range of size and terms of the description.

Extracting Partial Structures
The database of partial structures is built up from the words in the corpus, by successively adding larger structures, after augmenting the corpus with the analysis provided by an unsupervised parser. The larger structures found in this way are then entered into the permanent database of structures only if a relation recurs with a frequency above a given threshold. When a structure does not meet the frequency threshold, it is generalized until it does.
The descriptive relationships admitted include: • basic lexical features spelling -part-of-speech -lemma -major category (maximal projection) • dependency relations -depends on • adjacency relations -precedes Consider an example from the following sentence from the a training corpus of 20 million words of the Wall Street Journal. (

1) Reserve board rules have put banks between a rock and a hard place
The first order description of a word consists of its basic lexical features, i.e. the word spelling, its part of speech, its lemma, and its major category. Looking at the word banks, we have as description Assuming that we require at least two instances for a partial description to be entered into the database, none of these three descriptions qualify for the database. Therefore we must abstract away, using an arbitrarily defined abstraction path. First we abstract from the spelling to the lemma. This move admits two relations (since they are now frequent enough)

PRUNED STRUCTURES
(precedes (put, VB,put/V, VG) (,NN,bank/N,NG)) (depends (put,VB,put/V, VG) (,NN,bank/N,NG)) units are selected in using language depends on a variety of factors, including meaning, subject matter, speaking situation, style, interlocutor and so on. Of course, demonstrating that this intuition is valid remains for future work.
The set of partial trees can be used directly in an analogical parser, as described in Hindle 1992. In the parser, we are not concerned with estimating probabilities, but rather with finding the structure which best matches the current parser state, where a match is better the more specific its description is.
The third relation is still too infrequent, so we further generalize to (precedes (,NN,,NG) (between,IN,between/I,PG)) a relation which is amply represented (3802 occurrences).
The process is iterated, using the current abstracted description of each word, adding a level of description, then generalizing when below the frequency threshold. Since each level in elaborating the description adds information to each word, it can only reduce the counts, but never increase them. This process finds a number of recurrent partial structures, including between a rock and a hard place (3

occurrences in 20 million words), and [vpput [NP distance] [pp between]] (4 occurrences).
General Caveats There is of course considerable noise introduced by the errors in analysis that the parser makes.
There are several arbitrary decisions made in collecting the database. The level of the threshold is arbitrarily set at 3 for all structures. The sequence of generalization is arbitrarily determined before the training. And the predicates in the description are arbitrarily selected. We would like to have better motivation for all these decisions.
It should be emphasized that while the set of descriptive terms used in the collection of the partial structure database allows a more flexible description of the corpus than simple ngrams, CFG's or some dependency descriptions, it nevertheless is also restrictive. There are many predictive relationships that can not be described. For example, parallelism, reference, topic-based or speaker-based variation, and so on.
Motivation The underlying reason for developing a database of partial trees is not primarily for the language modeling task of predicting the next word. Rather the partialtree database is motivated by the intuition that partial trees are are the locus of other sorts of linguistic information, for example, semantic or usage information. Our use of language seems to involve the composition of variably sized partially described units expressed in terms of a variety of predicates (only some of which are included in our database). Which

ENHANCING A TRIGRAM MODEL
The partial structure database provides more information than an ngram description, and thus can be used to enhance an ngram model. To explore how to use the best available information in a language model, we turn to a trigram model of Wall Street Journal text. The problem is put into relief by focusing on those cases where the trigram model fails, that is, where the observed trigram condition (w-2, w_l) does not occur in the training corpus.
In the current test, we randomly assigned each sentence from a 2 million word sample of WSJ text to either the test or training set. This unrealistically minimizes the rate of unseen conditions, since typically the training and test are selected from disjoint documents (see . On the other hand, since the training is only a million words, the trigrams are undertrained. In general, the rate of unseen conditions will vary with the domain to be modeled and the size of training corpus, but it will not (in realistic languages) be eliminated. In this test, 26% (258665/997811) of the bigrams did not appear in the test, and thus it is necessary to backoff from the trigram model.
We will assume that a trigram model is sufficiently effective at preediction in those cases where the conditioning bigram has been observed in training, and will focus on the problem of what to do when the conditioning bigram has not appeared in the training. In a standard backoff model, we would look to estimate Pr(wolw_l). Here we want to consider a second predictor derived from our database of partial structures. The particular predictor we use is the lemma of the word that w-1 depends on, which we will call G(W_l). In the example discussed above, the first (standard) predictor for the word between is the preceding word banks and the second predictor for the word between is G(banks), which in this case is put/v.
We want to choose among two predictors, w-i and G(w_l).
In general, if we have two conditions, Ca and CCb and we want to find the probability of the next word given these conditions.
Intuitively, we would like to choose the predictor C'i for which the predicted distribution of w differs most from the unigram distribution. Various measures are possible; here we con-model logprob unigram backoff w_ l backoff G(w_ l) backoff w-t then G(w_ t) backoff (MAX IS ofw_l and G(w_l)) 9.55 8.06 8.20 7.97 7.99 In the course of processing sentence (1), we need an estimate of Pr(between]put banks). Our training corpus does not include the collocation put banks, so no help is available from trigrams, therefore we backoff to a bigram model, choosing the bigram predictor with maximum IS. The maximum IS is for put/V (G(w_x)) rather than for w-1 (banks) itself, so G(w_l) is used as predictor, giving a logprob estimate of -10.2 rather than -13.1.
The choice of G(w_ 1) as predictor here seems to make sense, since we are willing to believe that there is a complementation relation between put/V and its second complement between.
Of course, the choice is not always so intuitively appealing. When we go on to predict the next word, we need an estimate of Pr(albanks between). Again, our training corpus does not include the collocation banks between, so no help is available from trigrams. In this case, the maximum IS is for banks rather than between, so we use banks to predict a rather than between, giving a logprob estimate of-5.6 rather than -7.10.
Overall, however, the two predictors can be combined to improve the language model, by always choosing the predictor with higher IS score.
As shown in Table 4, this slightly improves the logprob for our test set over either predictor independently. However, Table  4 also shows that a simple strategy of chosing the raw bigram first and the G(w_l) bigram when there is no information available is slightly better. In a more general situation, where we have a set of different descriptions of the same condition, the IS score provides a way to choose the best predictor.

CONCLUSION
Recurrent structures in text vary widely both in size and in the terms in which they are described. Existing grammars are too restrictive both in the size of structure they admit and in their terms of description to adequately capture the variation in text. A method has been described for collecting a database of partial structures from text. Methods of fully exploiting the database for language modeling are currently being explored.