Refining the Structure of a Stochastic Context-Free Grammar

1 Introduction

Stochastic context-free grammars (SCFGs) have long been used in the NLP community (where the are more commonly known as probabilistic context-free grammars) and recently have been applied to biological sequence analysis tasks, in particular RNA analysis. One typical learning problem is to create an SCFG from a set of unparsed training sequences that will accurately recognize previously unseen sequences in the class being modeled. The first step of this two step process is to create the underlying context-free grammar, which we refer to as the structure of the model. The second step, the assignment of the probability parameters, is usually performed through an application of an expectation maximization (EM) algorithm called the inside-outside algorithm [Lari & Young, 1990]. One of the limitations of this approach is that if the structure is incomplete or in error, there may be no assignment of probabilities that would result in an accurate model. This is the problem we address in this paper. We introduce a refinement step that can identify and fix a class of structural errors that occur when a nonterminal in the model grammar is performing the function of more than one nonterminal in the target. The particular location refined at each step is determined "diagnostically" by analyzing the interaction between the model and a training set. This method may be contrasted

Mark Craven DEDD

craven@biostat.wisc.edu

DE Department of Biostatistics &Medical Informatics University of Wisconsin

Madison, Wisconsin 53706

to the standard state-space search methodology of applying the best of several competing operations as determined by a heuristic function applied to the successor states. This refinement step can be iterated with the inside-outside algorithm to refine both the structure of the model and the probability parameters. Through experiments with an SCFG designed to model a family of RNA sequences called terminators we show how this method may be used to learn more accurate models than inside-outside alone.

To see the impact a structural error can have, consider trying to learn the simple stochastic regular grammar shown in figure 1(a). Imagine that we have many sequences generated by this grammar for training and the structure we choose is shown in figure 1(b). Given enough training data, the maximum likelihood estimate of each state transition probability is 0.5. The probability of each length-two sequence under this model is therefore 0.25 resulting in a rather inaccurate model. The problemwith this structure is that state CG in the model is overloaded; it is performing the function of both state CG and CH in the target. With the approach presented herein, errors such as this can potentially be corrected.

2 ProblemDomain

The application of SCFGs we consider here is that of modeling of a class of RNA sequences called terminators. RNA

sequences are strings from the alphabet CUa,c,g,uCV corresponding to the four different types of bases in the nucleotides of RNA molecules. The bases a and u are complementary to one another, as are c and g, because they are able to easily form base pairs by becoming chemically bonded 1 .

The three dimensional shape that an RNA sequence assumes to a large degree determines its function, and the shape itself is strongly influenced by which particular bases are paired. For example, an element of RNA structure called a stem is formed when a number of adjacent bases pair with a complementary set of bases later in the sequence. If the intervening bases are unpaired, the resulting structure is called a stem-loop. Figure 2(a) shows an RNA sequence that could assume a stem-loop, and 2(b) shows the stem-loop it forms. The consequence of this is that families of RNA sequences of similar function will share a pattern of dependency between bases in the sequence that are likely to be paired.

Terminators are RNA sequences which signal when to stop the process of transcription, one of the key steps in the expression of a gene to form a protein.

3 Stochastic Context Free Grammars

The structure of an SCFG BZ is a context-free grammar and is defined by a set of nonterminals , a set of terminal symbols CC , a start nonterminal CB BE  and a set of rewrite rules, or productions, of the form  DA AX A0, A0 BE CUB4D2CBB5 CJ CC CV A3 . That is, the right hand side of a production consists of any combination of terminal and nonterminal symbols other the start nonterminal. When we refer to  DA 's productions, we mean the productions with  DA on the left hand side. Nonterminals and terminals are denoted by upper and lower case letters respectively. A grammar can be made into an SCFG by associating with each nonterminal  DA a probability distribution, D4 DA , over  DA 's productions.

SCFGs have proven important in RNA analysis tasks because the defining characteristics of RNA families manifest themselves in sequences through long range dependencies between bases. Such dependencies are troublesome to represent with regular grammars but can be naturally represented by context-free grammars. Figure 2(c) shows an SCFG for a specific set of stem-loops and Figure 2(d) shows the parse tree for an example sequence under this grammar.

There are three fundamental computational tasks relating SCFGs and sequences.

1. Compute D6B4DC CX CYBZB5, the probability of a sequence given a full model.
2. Find the most probable parse tree for a sequence.
3. Given BZ D7 and a set of sequences CG BP CUDC BD BN DC BE BN BMBMBMBN DC  CV, set the probabilities to maximize the likelihood  CXBPBD  D6B4DC CX CYBZB5.

Briefly, the first and second problems are efficiently solvable with dynamic programming algorithms similar to the forward and Viterbi algorithms, but there is no known efficient global solution for the third problem. The most common heuristic is the inside-outside [Lari & Young, 1990] method which, like other EM algorithms, converges to a local maximum.

1 Base pairs can be formed between non-complementary bases but this is less common.

The inside algorithm, used to solve task 1 above, is a dynamic programming algorithm that fills a three dimensional matrix AB. If run on the sequence DC CX , the elements of the matrix, ABB4CYBN CZBN DAB5, contain the sum of the probabilities of all parse trees of the subsequence DC CX CY BMBMDC CX CZ rooted at  DA . So, if the length of DC CX is  and  BD BP CB, then ABB4BDBN BN BDB5 BP D6B4DC CX CYBZB5.

The partner of the inside algorithm, the outside algorithm calculates a similar dynamic programming matrix AC. An element ACB4CYBN CZBN DAB5 is the sum of the probabilities of all parse trees of the complete sequence DC CX rooted at the start nonterminal, excluding all parse subtrees of DC CX BMBMDC CY rooted at  DA .

From AB and AC the expected number of times each nonterminal is used in the derivation of a sequence can be determined. The sum of these counts over all sequences in a training set are used by the inside-outside algorithm to iteratively re-estimate the production probabilities. In the next section we will show how AB and AC play a role in identifying overloaded nonterminals.

4 Grammar Refinement Approach

When the structure of a hypothesis grammar BZ CW is different from the structure of the target grammar BZ A3 , its accuracy may suffer. We would like to be able to identify and fix grammars in this situation using only a set of training sequences. In this section, we present a grammar refinement operator and a heuristic to do this. The operator is able to fix certain structural errors in BZ CW that occur when a nonterminal in the hypothesis is performing the function of more than one nonterminal of BZ A3 . We refer to such a nonterminal in BZ CW as overloaded. The heuristic identifies overloaded nonterminals by locating data dependencies that are not represented by the structure of BZ CW .

Before we delve into the details of the grammar refinement algorithm, it is helpful to consider the ways in which a hypothesis grammar may differ from the target grammar. Figure 3 gives a taxonomy of possible errors in a hypothesis grammar. The right branch out of the root contains all Table 1: The EXPAND operator. The operator creates a new nonterminal to take the place of nonterminal  on the right hand side of production 

EXPAND(, ) /*  is on the RHS of production  */

1. Create new nonterminal  BC
2. Replace  with  BC in 
3. For each production  AX A0, create  BC AX A0
4. Initialize probabilities for new productions

SCFGs that have a correct structure; that is, there is some assignment of probabilities that results in a grammar equivalent to BZ A3 . Most learning algorithms for SCFGs, including inside-outside are aimed at this situation.

The left branch contains two categories of incorrectly structured grammars: those whose structures can be made correct by adding only productions and those that require additional nonterminals as well. Among the kinds of errors that can occur from missing nonterminals, the class we address occurs when a nonterminal in the hypothesis is overloaded because it is trying to perform the function of two or more nonterminals in the target. For example, the nonterminal CG in the SCFG of Figure 2(c) would be overloaded if the distribution of the first base pair in the family of sequences being modeled was different from the rest. Next, we present a grammar refinement algorithm to identify and fix overloaded nonterminals.

The grammar refinement problem starts with set a sequences CG which we can think of as generated by an unknown target SCFG BZ A3 , an initial hypothesis grammar, and a goal of discovering a model 'close' to BZ A3 . We navigate the space of grammar structures through the application of a grammar modification operator, applied at each step to a part of the current grammar chosen by a heuristic.

4.1 Refinement Operator

Our current grammar refinement procedure has a single operator, EXPAND, shown in Table 1, which is applied to what we call a context. We define a context to be a production and a nonterminal on the right hand side of that production. We denote a context either by the pair B4BNB5 where  is a nonterminal on the right hand side of production  or by CR DAD6 where r indexes into the productions in which nontermi- Table 2: The structure of the SCFG formed following an application of EXPAND(CB AX CG, CG) to the grammar in Figure 2(c). The new nonterminal X' replaces X in the production of the context being expanded, CB AX CG. Productions created by EXPAND are shown in boldface.

nal  DA appears on the right hand side. Every nonterminal node in a parse tree defines a context. For example, the nonterminal CG in the parse tree fragment of Figure 4 is in the context (CB AX CG, CG) the first time it appears and (CG AXa CG u, CG) the second. When applied to B4BN B5, EXPAND creates a new nonterminal  BC , replaces  with  BC in  and creates a production with  BC on the left hand side from each of 's productions. Table 2 shows the structure that is formed after applying EXPAND(CB AX CGBN CG) to the SCFG of Figure 2(c). We explain how to set the probabilities of the new productions below.

4.2 Refinement Heuristics

The heuristic we use to guide the search expands a single context at each step. It chooses to expand the nonterminal that is used most differently in that context compared to its expected usage based on its probability distribution. Let D2 DAD6 be the vector of expected usage counts of the productions of  DA in context CR DAD6 (i.e., on the right hand side of the production indicated by D6) for the training sequences and let D2 DAD6D0 be an element of this vector that refers to the expected number of times that the D0 D8CW production with  DA on the left hand side is used in context CR DAD6 . EXPAND(CR DAD6 ) sets the probability distribution of the nonterminal it creates to the one defined by D2 DAD6 . Given a measurement of difference between the data distribution D2 DAD6 and  DA 's probability distribution D4 DA we define our heuristic to choose to expand the context that maximizes this difference. We have investigated two difference measures, one based on the Kullback-Leibler (KL) divergence and the other based on the AV BE statistic.

The KL divergence, also called relative entropy, between two probability distributions D4 and D5 with the same discrete domain is defined as

Consider the example in Table 3. Column (3) in this table shows D4 DAD6 for the productions of CG in the context (CB AX CG, CG). We can use KL divergence to compare this distribution to D4 DA , shown in column (5), which is the probability distribution for the productions of CG over all of CG's contexts. Using this measure, we select the nonterminal  DA in context D6 that maximizes

where D4 DAD6 is the probability distribution defined by D2 DAD6 , and the sum calculates the expected total number of times  DA is in CR DAD6 . By one interpretation, this measure selects the context that would waste the most bits in transmitting a message for each production applied in that context if the encoding used is the optimal encoding defined by D4 DA instead of D4 DAD6 .

The second heuristic we consider, the AV BE statistic, is commonly used to determine if the hypothesis that a data sample was drawn according to some distribution can be rejected. Using the vector of expected usage counts of nonterminal  DA in context CR DAD6 , D2 DAD6 , as the "observed" counts and CT DAD6 BP D4 DA A3 B4  D0 D2 DAD6D0 B5 for the expected counts,

Our method selects for expansion the context CR DAD6 which maximizes AV BE DAD6 . Returning to the example in Table 3, we can use AV BE to assess the significance of differences between column (2), the observed counts for the productions applied in the given context, and column (4) the expected observations given the probabilities in column (5).

To apply either of these heuristics, we must first calculate the counts D2 DAD6D0 . These can be calculated from the inside and outside matrices AB and AC in a similar way as the usage counts of productions and nonterminals are calculated in the inside-outside algorithm. For example, the expected number of times that the production  DB AX c  DD g is used in the context B4 DA AX CP DB D9BN DB B5 in the derivation of the sequence DC CX is

where

and
is an indicator variable that is 1 if DC CX CY BP CPBN DC CX CYB7BD BP CRBN DC CX CZA0BD BP CV and DC CX CZ BP D9, and 0 otherwise. Also, the counts are smoothed by adding 1 to each D2 DAD6D0 .

5 Experiments

We have constructed an SCFG model of terminator sequences by incorporating known features of terminators identified in the terminator literature. The structure of the terminator grammar we start with, shown in Table 4, models the eight bases before and eight bases after the stem-loop and the stem-loop itself. The recursive nature of STEM MID and LOOP MID's productions enables variable length stems and loops to be represented. An unpaired base in the interior of the stem, a bulge, can also be represented.

Positive examples consist of the sequences of 142 known or proposed terminators of E. coli. Each of these sequences is 50 base pairs long with the BFBC D8CW base aligned to the assumed termination point. We have 125 negative sequences, also of length 50, which were collected from the regions following genes that are presumed to not contain terminators.

We performed a five fold cross validation experiment using the KL and AV BE heuristic as well as a control where the context to EXPAND at each step is randomly chosen. The following steps were repeated.

1. Extract CC , the most probable subsequence of each positive sequence in the training set given the current model.

1. Fit the probability parameters by running inside-outside to convergence on CC .
2. EXPAND the context chosen by the heuristic.

The first step is needed because the positive sequences contain more bases than what is being modeled by the grammar. The probabilities in the stem were initialized with a preference for complementary base pairs; elsewhere, a uniform distribution was used.

For each test sequence, we determine the probability of its most probable subsequence as given by each model. To compare various methods, we rank our test-set predictions by these probability values and then construct ROC curves. We get a single ROC curve for each approach by pooling predictions across test-sets.

Figure 5 shows the ROC curves that result from the original grammar, and from running our grammar refinement algorithm for 25 iterations using the AV BE , KL, and random heuristics. The random curve is the average over 35 random runs. The curves in this figure show that our heuristics provide better predictive accuracy than both the original grammar and our control of randomly selecting the context to expand at each step. These results support our hypothesis that directed changes to the structure of the grammar can result in more accurate learned models.

To consider how the predictive accuracy of the grammars changes as a function of the number of refinement iterations, we construct ROC curves after each iteration and then calculate the area under each curve. Figure 6 plots the area under these curves versus the number of nonterminals added for the three heuristics considered in Figure 5. The DD-axis for this figure starts at 0.5 which is the expected area under the curve for a model that guessed randomly (such a model would result in an ROC "line" defined by: TP rate = FP rate). The results in this figure show that steady improvement is seen through about the 15th additional nonterminal using the KL heuristic and through about the 20th using AV BE . Our approach does not appear to overfit the training data, at least through the 25 iterations for which we have run it.

One possible reason that the AV BE heuristic results in more accurate models than the KL heuristic is the following. We know that our calculations of KL Divergence are biased because they are calculated with finite samples [Herzel & Grosse, 1997], but that this bias is not uniform across the nonterminals and contexts we are comparing because the sample sizes differ. Therefore, one avenue for future research is to investigate measures that correct for the finite-sample bias of our KL Divergence calculation.

We have examined the sequence of contexts expanded for both the AV BE and the KL Divergence heuristics, and noticed that several of the early refinements adjust a part of the grammar that describes the first few positions following the stem. There is known preference for t bases in this part of terminators, but our initial grammar did not encode it. This result suggests that our method can compensate for a known inadequacy in the initial grammar. However, we note that the algorithm makes additional modifications to other parts of the initial grammar that represent our best effort at encoding relevant domain knowledge.

One of the limitations of this algorithm as presented is the one-way nature of the search. That is, there is no way to make the grammar more general. If the initial grammar encodes the most general knowledge of the domain expert, this limitation may not be problematic initially. However, as EXPAND creates more nonterminals, it is likely that the grammar would become overly specific in places. The most obvious way of addressing this problem is by introducing a generalization operator. For example, a MERGE operator could be used to combine two nonterminals with the same RHS domain if their probability distributions are sufficiently similar. Note however, as mentioned by Stolcke (1994), that this operator will not introduce any new embedding structure into the grammar. This may not be a problem if such structure is present in the initial grammar.

6 RelatedWork

The approach we present here is related to the grammar induction algorithms of Stolcke (1994) and Chen (1996). These works both address the induction of SCFGs from text corpora for use as language models. Both methods incorporate a prior probability distribution over model structures and perform a search through posterior model probability space where Stolcke proceeds specific to general and Chen general to specific. One of the key differences between these algorithms and ours is that each of these addresses tabula rasa grammar induction while ours begins with a grammar structure created from prior knowledge. Another key difference is the way in which steps in the search space are selected. The methods of both Stolcke and Chen evaluate a candidate operator application by doing one-step lookahead. Since it can be expensive to calculate the posterior probability of the data given the changed model, heuristics are used to estimate this value. The operator application that results in the greatest estimated posterior probability is accepted. Our approach, on the other hand, is more "diagnostic." Instead of doing one-step lookahead, our heuristics try to directly identify places in which the grammar structure is inadequate. This approach may somewhat insulate our method from the overfitting pitfalls of likelihood driven searches. A third difference is that Stolcke and Chen use a richer set of operators than we do. As suggested in the previous section, however, we believe that our diagnostic approach can be generalized to work with other operators.

A different view of our approach is as an instance of a theory refinement algorithm [Pazzani & Kibler, 1992; Ourston &Mooney, 1994; Towell & Shavlik, 1994]. In theory refinement, the goal is to improve the accuracy of an incomplete or incorrect domain theory, from a set of labeled training examples. The primary difference between our work and previous work in theory refinement is the representation used by our learned models. Whereas previous theory-refinement methods have focused on logic-based and neural network representations, our learned models are represented using stochastic context free grammars.

The task we address is also similar to the problem of learning the structure of Bayesian networks [Heckerman, Geiger, & Chickering, 1995; Chickering, 1996], where the statistical properties of a training set are used to guide the modifications of the network structure. Again, the principal difference between our approach and this body of work is the difference in the representation language.

There has also been related work in learning SCFGs for RNA modeling tasks [Eddy & Durbin, 1994; Sakakibara et al., 1994]. These iterative methods both update grammar structure using information gathered from the most probable parse of each of the training sequences at each step. Although we intend to compare our refinement algorithm to both of these approaches in future work, we consider our work to be complementary to these methods because it could be run on every one of their iterations.

7 Conclusion

We have considered the problem of refining the structure of a deficient SCFG using a set of training sequences. We introduced a grammar refinement operator, EXPAND, for repairing a type of SCFG structural error resulting from an overloaded nonterminal as well as a pair of heuristics, based on KL divergence and AV BE , for locating them. Preliminary results indicate that our method is able to improve the accuracy of an SCFG designed to model terminators by correcting known structural errors as well making modifications to parts of the grammar with no known deficiencies.

Acknowledgments

This research was supported in part by NSF CAREER award IIS-0093016 and NIH Grant 1R01 LM07050-01. Thanks to Soumya Ray for helpful comments on an earlier version of this paper.