Stochastic Grammatical Inference of Text Database Structure.
For a document collection in which structural elements are identified with markup, it is often necessary to construct a grammar retrospectively that constrains element nesting and ordering. This has been addressed by others as an application of grammatical inference. We describe an approach based on stochastic grammatical inference which scales more naturally to large data sets and produces models with richer semantics. We adopt an algorithm that produces stochastic finite automata and describe modifications that enable better interactive control of results. Our experimental evaluation uses four document collections with varying structure.
Introduction
1.1. Text Structure
For electronically stored text, there are well known advantages to identifying structural
elements (e.g., chapters, titles, paragraphs, footnotes) with descriptive markup
[4, 5, 12]. Most commonly, markup is in the form of labeled tags interleaved with
the text as in the following example:
!reference?The Art of War: Chapter 3 paragraph 18!/reference?
If you know the enemy and know yourself, you need not fear the
result of a hundred battles. !/sentence?
If you know yourself but not the enemy, for every victory gained
you will also suffer a defeat. !/sentence?
If you know neither the enemy nor yourself, you will succumb in
every battle. !/sentence?
Documents marked up in this way can be updated and interpreted much more robustly
than if the structural elements are identified with codes specific to a particular
system or typesetting style. The markup can also be used to support operations
such as searches that require words or phrases to occur within particular elements.
Further advantages can be gained by using a formal grammar to specify how and
where elements can be used. The above example, for instance, conforms to the
following grammar represented as a regular expression:
quotation ! reference sentence
This specifies that a quotation must contain a reference followed by one or more
sentences. Any other use of the elements, e.g. nesting a sentence in a reference
or preceding a reference by a sentence, is disallowed. Thus the main benefit of
having a grammar is that new or modified documents can be automatically verified
for compliance with the specification. Other benefits include support for queries
with structural conditions, and optimization of physical database layout. Another
important purpose of a grammar is to provide users with a general understanding
of the text's organization. Overall, a grammar for a text database serves much the
same purpose as a schema for a traditional database: it gives an overall description
of how the data is organized [18].
The most widely used standard for text element markup and grammar specification
is SGML (Standard Generalized Markup Language) [24], and more recently,
XML [7]. HTML represents a specific application of SGML, i.e., it uses a single
grammar and set of elements (although the grammar is not very restrictive).
1.2. Automated Document Recognition
Unfortunately, many electronic documents exist with elements and grammar only
implicitly defined, typically through layout or typesetting conventions. For exam-
ple, on the World Wide Web, data is laid out according to conventions that must be
inferred to use it as easily as if it were organized in a database [41]. There is therefore
a pressing need to convert the structural information in such documents to a
more explicit form in order to gain the full benefits of their online availability. Completely
manual conversion would be too time consuming for any collection larger
than a few kilobytes. Therefore, automated or interactive methods are needed for
two distinct sub-problems: element recognition and grammar generation.
If the document is represented by procedural or presentational markup, the first
sub-problem is to recognize and mark up individual structural elements based on
layout or typesetting clues. To do this, it is necessary to know or infer the original
conventions used to map element types to their layout. We do not address this
task here, but there are several existing approaches, based on interactive systems
[14, 26], on learning systems [32], and on manual trial and error construction of
finite state transducers [11, 25].
The second sub-problem is to extract implicit structural rules from a collection of
documents and model them with a grammar. This requires that a plausible model
of the original intentions of the authors be reconstructed by extrapolating from
available examples in some appropriate way. This can be considered an application
of grammatical inference - the general problem that deals with constructing
grammars consistent with training data [42].
GRAMMAR INFERENCE FOR TEXT 3
Note that the two problems may depend on each other. Element recognition
often requires that ambiguities be resolved by considering how elements are used
in context. However, recognition usually considers these usage rules in isolation,
and identifies only the ones that are really needed to recognize an element. A
grammar can be considered a single representation of all usage rules, including
the ones that are not relevant to recognition (which may be the majority). Thus,
even if certain components of the grammar need to be determined manually in the
recognition phase, grammar inference is still useful for automatically combining
these components and filling in the ones that were not needed for recognition.
The grammar inference problem is especially applicable to XML, an increasingly
important variant of SGML in which rich tagging is allowed without requiring a
DTD (grammar). In this case, there is no recognition subproblem and grammar
generation comprises the entire recognition problem.
The benefits of attaching a grammar to documents can be seen from the recent
experience with the database system Lore [31]. Lore manages semistructured
data, where relationships among elements are unconstrained. In place of schemas,
"DataGuides" are automatically generated to capture in a concise form the relationships
that occur [17]. These are then used for traditional schema roles such as
query optimization and aiding in query formulation. Interestingly, the DataGuide
for a tree-structured database is analogous to a context free grammar.
1.3. The Data
We describe our approach to this problem using the computerized version of
the Oxford English Dictionary (OED) [39]. This is a large document with complex
structure [34], containing over sixty types of elements that are heavily nested in over
two million element instances. Figure 1 lists some of the most common elements as
they appear in a typical entry. See the guide by Berg [6] for a complete explanation
of the structural elements used in the OED.
The OED has been converted from its original printed form, through an intermediate
keyed form with typesetting information, to a computerized form with
explicitly tagged structural elements [25]. The text is broken up into over two
hundred ninety thousand top level elements (dictionary entries). The grammar
inference problem can be considered as one of finding a complete grammar to describe
these top level entries, or it can be broken into many subproblems of finding
grammars for lower level elements such as quotation paragraphs or etymologies.
As a choice of data, the OED is a good representative of the general problem
of inferring grammars for text structure. It is at least as complex as any text in
two ways: the amount of structure information is extremely high, and the usage of
structural elements is quite variable.
The large amount of structure information is evidenced by the number of different
types of tags, and also by the high density of tagging as compared to most text
[35]. There are over sixty types of tags and the density of tagging is such that,
HEADWORD GROUP !HG?
Headword Lemma !HL?
Lookup Form !LF?.!/LF?
Stressed Form !SF?.!/SF?
Murray Form !MF?.!/MF?
End of Headword Lemma !/HL?
Murray Pronunciation !MPR?.!/MPR?
IPA Pronunciation !IPR?.!/IPR?
Part of Speech !PS?.!/PS?
Homonym Number !HO?.!/HO?
END OF HEADWORD GROUP !/HG?
VARIANT FORM LIST !VL?
Variant Date !VD?.!/VD?
Variant Form !VF?.!/VF?
END OF VARIANT FORM LIST !/VL?
Sense Number !#?
Definition !DEF?.!/DEF?
Quotation Paragraph !QP?
Earliest Quote !EQ?!Q?
Date !D?.!/D?
Author !A?.!/A?
Work !W?.!/W?
End of Earliest Quote !/Q?!/EQ?
Latest Quote !LQ?!Q?.!/Q?!/LQ?
(Obsolete Entries Only)
End of Quotation Paragraph !/QP?
Sub-Entry (Preceded by"Hence") !SE?
Bold Lemma (+similar tags !BL?.!/BL?
to those following Headword
End of Sub-Entry !/SE?
END OF SENSE(S) !/S0?!/S1?.!/S8?
END OF ENTRY !/E?

Figure

1. Common elements from the OED with their corresponding tags in the order they appear
in a typical dictionary entry. (This is reproduced from Berg [5] and represents a human-generated
high level description of the data.) Indentation denotes containment. Therefore, the headword
group, variant form list, etymology, and senses are top level elements of an entry; their children
are indented one step further; etc. Note that more than one sense element can occur at the top
level.
GRAMMAR INFERENCE FOR TEXT 5
even with all element names abbreviated to three or fewer characters, the amount
of tagging is comparable to the amount of text.
In most text, restrictions on element usage tend to vary between one extreme
where any element can occur anywhere (e.g. italics in HTML), to the other where
elements always occur in exactly the same way (e.g. a newspaper article which
always contains a title, followed by a byline, followed by a body). Neither of
these extremes is interesting for grammar inference. Element usage in the OED,
however, is constrained, yet quite variable. This is mainly a consequence of the
circumstances of its original publication. The compilation spanned 44 years, and
filled over 15,000 pages. There were seven different chief editors over the lifetime of
the project, most of which was completed before 1933 - well before the possibility
of computer support. The structure of the OED is remarkably consistent, but
variable enough to be appropriate for the problem: it can test the method but is
regular enough to make description by a grammar appropriate.
1.4. Text Structure and Grammatical Inference
We now demonstrate the use of marked up text from the OED as training data
for a grammatical inference process. Consider the structure of the two short OED
entries shown in Figure 2. These can be represented by the derivation trees, shown
in

Figure

3, where the nodes are labeled with their corresponding tag names. A
corresponding grammar representation is shown in Figure 4. Each production has
a left hand side corresponding to a non-leaf node, and a right hand side formed
from its immediate children. The number of times a production occurs in the data
is indicated by a preceding frequency. A non-terminal and all of its strings (right
hand sides of its productions) can now be considered a training set for a single sub-
problem. Note that if we generalize each such production to a regular expression
then we have an overall grammar that is context free [28]. This is the standard
choice for modeling text structure.
Three existing grammatical inference approaches for text operate by specifying
rules that are used to rewrite and combine strings in the training set [10, 14, 38].
The following rule, for example, generalizes a grammar by expanding the language
that it accepts:
greater than or equal to a given value
Applied to the first entry in Figure 2 with
for example. Other rules have no effect on the language, but simplify a grammar
by combining productions:
Applied to the two HG productions in Figure 2, for example, the first rule gives
!MF?salama&sd.ndrous !/MF?!/HL?!b?,!/b? !PS?a.!/PS?!/HG?
!LB?rare!/LB?!su?-1!/su?. !ET?f. !L? L.!/L? !CF?
!XL?-ous!/XL?!/XR?.!/ET? !S4?!S6?!DEF?Living as it were
in fire; fiery, hot, passionate. !/DEF?!QP?!Q?!D?1711!/D?
!A?G. Cary!/A? !W?Phys. Phyl.!/W? 29 !T?My Salamandrous
Spirit.my &Ae.tnous burning Humours.!/T?!/Q?!/QP?!/S6?
!W?Expos. Dom. Epist. &amp. Gosp.!/W? Wks. (1629) 76
!T?If a Salamandry spirit should traduce that godly labour,
as the silenced Ministers haue wronged our Communion Booke.
!MF?u&sd.nderstrife !/MF?!/HL?!b?.!/b? !/HG?!LB?poet.!/LB?
!/XR?!/ET? !S4?!S6?!DEF?Strife carried on upon the earth.
!/DEF?!QP?!EQ?!Q?!D?C. 1611!/D? !A?Chapman!/A? !W?Iliad!/W?
xx. 138 !T?We soon shall.send them to heaven, to settle
their abode With equals, flying under&dubh.strifes.!/T?

Figure

2. Two marked up dictionary entries.
Work by Ahonen, Mannila and Nikunen [1, 2, 3] uses a more classical grammatical
inference approach of generating a language belonging to a characterizable subclass
of the regular languages. Specifically, they use languages, an
extension that they propose to k-contextual languages.
In contrast to previous approaches to grammar construction for text structure, we
use the frequency information from the training set to generate a stochastic gram-
mar. The non-stochastic approaches mentioned above are inappropriate for larger
document collections with complex structure. This is because there is no way to
effectively deal with the inevitable errors and pathological exceptions in such cases
without considering frequency information. Stochastic grammars are also better
suited for understanding and exploration since they express additional semantics
and provide a natural way of distinguishing the more significant components of
the grammar. The thesis by Ahonen [1] does partially address such concerns. For
example, when applying her method to a Finnish dictionary of similar complexity
to the OED, she first removed all but the most frequent cases from the training set.
GRAMMAR INFERENCE FOR TEXT 7
daVinci
V1.4.2
QP
A
PS
MF
QP
A
XR
XR
CF
su
PS
MF
daVinci
V2.0.3 T
A
QP
HO
XR
MF

Figure

3. The two parse trees.
She also proposes some ad-hoc methods for separating the final result into high and
low frequency components (after having generated the result with a method that
does not consider frequency information).
We assert that it is better to use an inference method that considers frequency
information from the beginning. The stochastic grammatical inference algorithm
that we have chosen to adopt for this application was proposed by Carrasco and
Oncina [9]. Our modifications are motivated by shortcomings in the ability to tune
the algorithm and by our wish to use it interactively for exploration rather than as a
black box to produce a single, final result. Note that understanding techniques are

Figure

4. The de-facto grammar with production frequencies.
needed to support effective interaction. The primary technique used for examples
in this paper is visualizing automata as bubble diagrams. All bubble diagrams
were generated by the graph visualization program daVinci which performs node
placement and edge crossover minimization [15].
The remainder of the paper is as follows: Section 2 describes the underlying
algorithm, Section 3 explains our modifications, Section 4 evaluates the method on
real and synthetic data, and Section 5 concludes.
2. Algorithm
Here we provide an overview of the algorithm by Carrasco and Oncina [9] in enough
detail to explain our modifications. A longer technical report includes more detailed
descriptions of both the modified and unmodified algorithms [43]. Of the many possible
stochastic grammatical inference algorithms, the particular one used here was
chosen for several reasons. First of all, it is similar to the method of Ahonen et al. in
that it uses a finite automaton state merging paradigm. Since that work represents
the most in-depth examination of grammar inference for text structure to date, it is
reasonable to use a similar approach. In fact, many of their results that go beyond
just the application of the algorithm (such as rewriting the automaton into a gram-
GRAMMAR INFERENCE FOR TEXT 9
mar consisting of productions) can be adapted to the outputs of our algorithm.
The second reason for choosing this algorithm was that the basic generalization
operation of merging states is guided by a justifiable statistical test rather than an
arbitrary heuristic. The Bayesian model merging approach of Stolcke and Omohundro
[40] or a probability estimation approach based on the forward-backward
algorithm [23, 30] were other candidates satisfying this characteristic, but the final
choice was judged the simplest and most elegant.
2.1. ALERGIA
The algorithm ALERGIA by Carrasco and Oncina [9] is itself an adaptation of a
non-stochastic method by Oncina and Garc'ia [33].
The algorithm produces stochastic finite automata (SFAs). These grammar constructs
can be informally explained as finite automata that have probabilities associated
with their transitions. The probability assigned to a string is, therefore,
the product of the probabilities of all transitions followed in accepting it. Note
that every state also has an associated termination probability, and that this is
included in the product. Any state with a non-zero termination probability can be
considered a final state. See the book by Fu [16] for a more formal and complete
description of SFAs and their properties.
The inference paradigm used by ALERGIA is a common one: first build a de-facto
model that accepts exactly the language of the training set; then generalize.
Generalization for finite automata is done by merging states. This is similar to the
state merging operation used in the algorithm for minimizing a non-stochastic finite
automaton [21]. The difference is that merges that change the accepted language
are allowed.
Consider, as an example, the productions for ET from the training data of Figure 4.
These can be represented by the prefix tree in Figure 5. The primitive operation
of merging two states replaces them with a single state, labeled by convention with
the smaller of the two state identifiers. All incoming and outgoing transitions are
combined and the frequencies associated with any transitions they have in common
are added, as are the incoming and termination frequencies. Figure 6 demonstrates
the effect of merging states 2 and 4, then 2 and 5.
Note that if two states have outgoing transitions with the same symbol but different
destinations, these two destinations are also merged to avoid indeterminism.
Thus, merging two non-leaf states can recursively require merging of a long string
of their descendants.
An algorithm based on this paradigm must define two things: how to test whether
two given states should be merged, and the order in which pairs of states are tested.
In ALERGIA, two states are merged if they satisfy the following equivalence
criterion: for every symbol in the alphabet, the associated transition probabilities
from the states are equal; the termination probabilities for the states are equal;
and, the destination states of the two transitions for each symbol are equivalent
according to a recursive application of the same criterion.

Figure

5. A de-facto SFA (prefix tree) for the ET element. States are labeled ID[N,T] where ID is
the state identifier, N is the incoming frequency, and T is the termination frequency. Transitions
are labeled S[F], where S is the symbol, and F is the transition frequency. Final states with
non-zero termination frequencies are marked with double rings.

Figure

6. Figure 4 with states 2,4 and 5 merged.
GRAMMAR INFERENCE FOR TEXT 11
Whether two transitions' probabilities are equal is decided with a statistical test of
the observed frequencies. Let the null hypothesis H o be that they are equal and the
alternative H a be that they differ. Let be the number of strings that arrive at
the states and f 1 be the number of strings that follow the transitions in question
(or terminate). Then, using the Hoeffding bound [19] on binomial distributions, the
p-value is less than a chosen significance level ff if the test statistic
is greater than the expression
In this case, reject the null hypothesis and assume the two probabilities are different,
otherwise assume they are the same. This test ensures that the chosen ff represents a
bound on the probability of incorrectly rejecting the null hypothesis (i.e. incorrectly
leaving two equivalent nodes separate). Thus, reducing ff makes merges more likely
and results in smaller models.
The order in which pairs of nodes are compared is defined as follows: nodes are
numbered in a breadth-first order with all nodes at a given depth ordered lexically
based on the string prefixes used to reach the node. Figure 5 is an example. Pairs
of nodes (q are tested by varying j from 1 to the number of nodes, and i from 0
to 1. For the non-stochastic version of the algorithm, this ordering is necessary
to prove identification in the limit [33]. Its significance in the stochastic version is
unclear.
Note that the worst case time complexity of the algorithm is O(n 3 ). This occurs
for an input where no merges take place, thus requiring that all n(n \Gamma 1)=2 pairs
of nodes be compared, and furthermore, where the average recursive comparison
continues to O(n) depth. In practise, the expected running time is likely to be much
less than this. Carrasco and Oncina report that, experimentally, the time increases
linearly with the number of strings in the training set, as artificially generated
by a fixed size model. We have observed a quadratic increase with the size of
model. However, since this size is normally chosen, through parameter adjustment,
to be small enough for understanding, running time has not been a problem in our
experience.
3. Modifications
In this section we present our modifications to the algorithm, using the PQP
(pseudo-quotation paragraph) element from the OED as an example. Of the
145,289 instances of that element in the entire dictionary, there are 90 unique arrangements
for subelements; thus there are 90 unique strings that appear as right
sides of productions in the defacto grammar. Those are shown in Figure 7 along
with their occurrence frequencies. The 4 elements that occur in a PQP are the
(earliest quotation), Q (quotation), SQ (subsidiary quotation), and LQ (latest
quotation). The usage of the elements (which is known from the dictionary but
can also be deduced from the examples) is as follows: SQ can occur any number
of times and in any position; Q can occur any number of times; EQ can occur at
most once and must occur before the first Q; LQ can occur at most once and must
occur after the last Q. This data is very simple and intended only to illustrate the
modified learning algorithm. We give more complex examples in Section 4.2.
3.1. Separation of Low Frequency Components
The original algorithm assumes that every node has a frequency high enough to
be statistically compared. This is not typically valid. Nodes with too low a frequency
always default to the null hypothesis of equivalence, resulting in inappropriate
merges. The characteristic result is that many low frequency nodes merge with
either the root or another low index node (since the comparisons are made in order
of index). This gives a structure with many inappropriate transitions pointing back
to these low index nodes. Figure 8 shows an example result for the PQP data where
transitions occur from several parts of the model to nodes 0 and 1.
Note that this form of inappropriate merging is not a problem that can be remedied
just by tuning the single parameter ff. As is usual in hypothesis tests, ff is
a bound on the probability of a false reject of the null hypothesis (i.e. failing to
merge two nodes that are in fact equivalent). The complementary bound fi on the
probability of a false accept is unconstrained by the test of ALERGIA, and can be
arbitrarily high for very low frequencies.
The problem can be seen as closely related to the small disjuncts problem discussed
by Holte et al. [20] for rule based classification algorithms: essentially, rules
covering only a few cases of the training data perform relatively badly since they
have inadequate statistical support. Holte et al. give three general approaches for
improving the situation: 1) use exact significance tests in the learning algorithm,
test both significance and error rate of every disjunct in evaluating a result, and
whenever possible, use errors of omission instead of default classifications. Note
that since our training set includes positive examples only, the second point does
not apply. The first point, however corresponds to one of our modifications, and
the third agrees with our own conclusions.
Experiments with several different treatments for low frequency nodes led us to
the conclusion that no single approach would always produce an appropriate result
(certainly not the original action of the algorithm - automatically merging on the
first comparison). This is understandable given that the frequencies in question are
statistically insignificant. Therefore, we chose to first incorporate a significance test
into the algorithm to separate out the low frequency nodes automatically, and then
later decide on alternative treatments for these nodes (discussed in Section 3.4).
The following test is the standard one for checking equivalence of two binomial
proportions while considering significance (see [13], for example). Assume as before
GRAMMAR INFERENCE FOR TEXT 13
21: 3: Q,Q,SQ,Q
524: EQ 4: Q,Q,SQ,Q,Q
5: EQ,LQ 3: Q,Q,SQ,Q,Q,Q
294: EQ,Q 2: Q,Q,SQ,Q,Q,Q,Q
1: EQ,Q,LQ 58: Q,SQ
30: EQ,Q,Q,Q,Q
1: EQ,Q,Q,Q,Q,LQ 9: Q,SQ,Q,Q,Q
15: EQ,Q,Q,Q,Q,Q 2: Q,SQ,Q,Q,Q,Q
8: EQ,Q,Q,Q,Q,Q,Q 3: Q,SQ,Q,Q,Q,Q,Q
5: EQ,Q,Q,Q,Q,Q,Q,Q 2: Q,SQ,Q,Q,Q,Q,Q,Q
3: EQ,Q,Q,Q,Q,Q,Q,Q,Q 1: Q,SQ,Q,Q,Q,Q,Q,Q,Q
3: EQ,Q,Q,Q,Q,Q,Q,Q,Q,Q 1: Q,SQ,Q,Q,Q,Q,Q,Q,Q,Q,Q
1: EQ,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q 2: Q,SQ,SQ
2: EQ,SQ 22: SQ
28: LQ 2: SQ,EQ
20: Q,LQ 5: SQ,EQ,Q,Q
3: SQ,EQ,Q,Q,Q
5: Q,Q,Q,LQ 174: SQ,Q,Q
6335: Q,Q,Q,Q 177: SQ,Q,Q,Q
1: Q,Q,Q,Q,LQ 102: SQ,Q,Q,Q,Q
579: Q,Q,Q,Q,Q,Q,Q 9: SQ,Q,Q,Q,Q,Q,Q,Q
293: Q,Q,Q,Q,Q,Q,Q,Q 8: SQ,Q,Q,Q,Q,Q,Q,Q,Q
124: Q,Q,Q,Q,Q,Q,Q,Q,Q 2: SQ,Q,Q,Q,Q,Q,Q,Q,Q,Q
93: Q,Q,Q,Q,Q,Q,Q,Q,Q,Q 2: SQ,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q
2: SQ,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q
4: Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q 2: SQ,Q,Q,SQ
2: Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q
1: Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q,Q
2: Q,Q,Q,Q,Q,SQ
1: Q,Q,Q,Q,SQ,Q,Q,Q,Q,Q
4: Q,Q,Q,SQ
2: Q,Q,Q,SQ,Q,Q
1: Q,Q,Q,SQ,Q,Q,Q
1: Q,Q,Q,SQ,Q,Q,Q,Q,Q
1: Q,Q,Q,SQ,Q,Q,Q,Q,Q,Q
17: Q,Q,SQ

Figure

7. The PQP example strings.
daVinci
V1.4.2
30[886,45.5]
Q[54.5]
7[142,58.5]
6[78455,56.3]

Figure

8. A result from the unmodified algorithm with transitions characteristic of inappropriate
low frequency merges. Note that termination and transition frequencies f i
are shown converted
to percentages representing f i =n i in this and subsequent figures to simplify comparisons.
GRAMMAR INFERENCE FOR TEXT 15
that true probabilities and that f 1 =n 1 , f 2 =n 2 serve
as the estimates. Sample sizes are required to satisfy the following relationship with
ff and fi (which bound the probabilities of a false reject or a false accept of the null
ae 2ffl
where z x denotes the t value at which the cumulative probability of a standard
normal distribution is equal to 1 \Gamma x; and,
The value ffl is an additional parameter required to bound fi (representing the minimum
true difference between p1 and p2). The null hypothesis is rejected iff
We incorporate this test into the algorithm in the following way. Associate a
boolean flag with each node, initially false; and, set the flag to true the first time
a node is involved in a comparison with another node that satisfies the required
relationship between ff, fi, and sample sizes. Nodes that still have false flags when
the algorithm terminates are classified as low frequency components. An example
result with the PQP data is shown in Figure 9. Low frequency nodes in the graph
are depicted as rectangles.
3.2. Control over the Level of Generalization
An important interactive operation is control over the level of generalization (how
much the finite language represented by the training set is expanded). One possible
approach is to vary ff and fi. Reducing ff increases generalization: it restricts
the possibility of incorrectly leaving nodes separate, and therefore makes merges
more likely. Increasing fi also increases generalization: it increases the allowable
possibility of incorrectly merging nodes. Note that these two are not completely
equivalent since ff and fi are bounds on the probabilities of their respective errors.
Unfortunately, it is not appropriate to control generalization in this way since
ff and fi directly determine which components of the data are treated as too low
frequency to be significant (i.e. the parts that will be merged by default using
the original algorithm, or classified as low frequency according to the test in Section
3.1). Therefore, unless we are in a position to arbitrarily vary the amount
of available data according to our choice of parameters, another modification is
needed.
The goal is to allow independent control over the division into low and high frequency
components, and over the level of generalization. This is done by changing
99[3,33.3]
95[4,25.0]
87[6,33.3]
30[374,47.3]
Q[90.3]
Q[64.3]
Q[87.5]
19[2,100.0]
98[2,50.0]
94[2,0.0]
90[2,0.0]
82[3,33.3]
Q[58.3]
50[16,25.0]
28[42,31.0]

Figure

9. The PQP inference result with
GRAMMAR INFERENCE FOR TEXT 17
the hypothesis for the statistical test. Rather than testing whether two observed
proportions can plausibly be equal, test whether they can plausibly differ by less
than some parameter fl:
The modified test is as follows: let - 1 be f 1 =n 1 , and - 2 be f 2 =n 2 . Then, if
Reject H
A larger value of fl results in a null hypothesis that is easier to satisfy, therefore
producing more merges and an increase in generalization. As an example, consider
the 3 results in Figures 10, 11, and 12 with constant ff and fi values, but varying fl
values (and low frequency components clipped out for the moment). Higher fl values
result in fewer nodes, larger languages, and less precise probability predictions.
3.3. Choosing Algorithm Parameters
The modified algorithm has the following parameters:
ffl fl is the maximum difference in true proportions for which the algorithm should
merge two states.
ffl ff is the probability bound on the chance of making a type I error (incorrectly
concluding that the two proportions differ by more than fl)
ffl fi is the probability bound on the chance of making a type II error (incor-
rectly concluding that the two proportions differ by less than fl) when the true
difference in the proportions is at least fl being the fourth parameter)
We next describe the effects of changing these parameters and also explain that
useful interaction does not necessarily require separate control over all four.
Choosing fl controls the amount of generalization. Setting it to 0 results in very
few states being merged; setting it to 1 always results in an output with a single state
(effectively a 0-context average of the frequency of occurrence of every symbol).
Changes to ff and fi also affect the level of generalization. Their main effect of
interest, however, is that they define the cutoff between high and low frequency
components. Increasing either one decreases the number of nodes classified as low
frequency. For simplified interaction, it is possible to always have both equal and
daVinci
V2.0.3
Q[90.3]
9[62963,
GRAMMAR INFERENCE FOR TEXT 19
daVinci
V2.0.3
Q[90.3]
daVinci
V2.0.3

Figure

12. The PQP inference result with
adjust them together as a single parameter. This does not seriously reduce the
useful level of control over the algorithm's behavior.
The ffl parameter determines the difference to which the fi probability applies.
This must be specified somewhere but is not an especially useful value over which
to have control. It should therefore be fixed, or tied in some way to the size of the
input and the value of fl (we choose to fix it).
it can be seen that control is only really needed over two major
aspects of the inference process. Choosing a combined value for ff and fi sets
the cutoff point between the significant data and the low frequency components.
Choosing fl controls the amount of generalization.
As an example of parameter adjustment, consider the inference result from Figure
9. Examination reveals two possible changes. The first is based on the observation
that nodes 1 and 3 are very similar: they both accept an LQ or SQ or any
number of Q's, and their transition and termination probabilities all differ by less
than ten percent. Unless these slight differences are deemed significant enough to
represent in the model, it is better to merge the two nodes. This can be done by
increasing fl to 0.1, thus allowing nodes to test equal if their true probabilities differ
by up to ten percent.
The second adjustment affects nodes 4, 12 and 21. These express the fact that
strings starting with an SQ are much more likely to end with more than two Q's.
This rule only applies, however, to about five hundred of the over one hundred
GRAMMAR INFERENCE FOR TEXT 21
Q[90.3]
30[374,47.3]
87[6,33.3]
95[4,25.0]
99[3,33.3]
Q[87.5]
Q[64.3]
7[142,58.5]
19[2,100.0]
28[42,31.0]
50[16,25.0]
Q[58.3]
82[3,33.3]
90[2,0.0]
94[2,0.0]
98[2,50.0]

Figure

13. The PQP inference result with
forty five thousand PQPs in the dictionary. If we choose to simplify the model
at the expense of a small amount of inaccuracy for these cases, we can reduce ff
and fi to reclassify these nodes as low frequency. Bisection search of values of ff
and fi between 0 and 0.025 reveals that this is accomplished with
The result after application of the two adjustments described above is shown in

Figure

13.
3.4. What to do with the Low Frequency Components
There are three possible ways of treating low frequency components: assume the
most specific possible model by leaving the components separate (this is the same as
leaving fi fixed and allowing ff to grow arbitrarily high); merge all the low frequency
components into a single garbage state (an approach adopted in [36]); or, merge
low frequency nodes into other parts of the automaton. Many methods can be
invented for the last approach. We have observed that, in general, a single method
does not produce appropriate results for all components of a given model. We
therefore propose a tentative merging strategy. First an ordered list of heuristics is
defined. Then all low frequency components are merged into positions in the model
determined by the first heuristic in the list. If the user identifies a problem with
a particular resulting tentative transition then the subtree can be re-merged into a
position determined by the next heuristic in the list.
Heuristics can be designed based on various grammatical inference or learning
approaches. Note that the problem of choosing a place to merge a low frequency
component differs from the general problem of stochastic grammatical inference
in two ways: 1) the rest of the high frequency model is available as a source of
information, and 2) the frequency information has been classified as insignificant.
The second point implies that, if we choose to consider frequency information, we
may have to use special techniques to compensate. These could include a Laplace
approximation of the probability or a Bayesian approach using a prior probability.
Evidence measures developed for recent work in DFA (rather than SFA) learning
might also be applicable [29].
We mention two heuristics that do not use frequency information but that we
have found to work well. Both guarantee that the model is still able to parse all
strings in the training set. The first is to merge every low frequency node with its
immediate parent. The result is that any terminals occurring in a low frequency
subtree are allowed to occur any number of times and in any order starting at the
nearest high-frequency ancestor. The second heuristic is to locate a position in the
high frequency model from which an entire low-frequency subtree can be parsed.
This subtree can then be merged into the rest of the model by replacing it with a
single transition to the identified position. If more than one possible position exists,
these can be stepped through before proceeding to the next heuristic in the list.
As an example of the application of the second heuristic reconsider Figure 13.
Merging every low frequency tree in that graph into the first (lowest index) node
that can parse it gives the result in Figure 14. Tentative transitions in that diagram
GRAMMAR INFERENCE FOR TEXT 23
daVinci
V1.4.2

Figure

14. Figure 13 with low frequency components merged into other parts of the graph.
are marked with dashed lines. The tentative transition from node 1 to 0 on input
of SQ creates a cycle that allows more than one EQ to occur. This violates proper
usage of that element as outlined in Section 3. Re-pointing the transition to node 1,
an alternate destination that parses the low frequency subtree, gives an acceptable
result for the PQP element.
4. Evaluation
In this section we compare the modified algorithm (henceforth referred to as mod-
ALERGIA) with ALERGIA. First, using data drawn from four different texts, we
compare performance with automatic searches. Then we use two specific examples
to illustrate some other points of comparison.
4.1. Batch Experiments
We use the following four texts for the automatic search experiments:
ffl OED - the Oxford English Dictionary [39]. This is over 500 Mb and exhibits
complex, sometimes irregular, structure.
pharmaceutical database which is an electronic version of a publication
that describes all drugs available in Canada [27]. This is exhibits a
mix of simple and complex structure.
ffl OALD - the Oxford Advanced Learner's Dictionary [22]. This is 17 Mb and
exhibits complex structure that is more regular than the OED having been
designed from the beginning for computerization.
ffl HOWTO - the SGML versions of HOWTO documents for the Linux operating
system. This is 10 Mb and exhibits relatively simple structure.
Terminal structural elements and non-terminals with very little sub-structure are
not worth performing inference on. As an arbitrary cutoff, we discard those that
give de-facto automatons with fewer than 10 states. This leaves 24 elements in
OED, 24 in CPS, 23 in OALD, and 14 in HOWTO for a total of 85 data sets. The
procedure for each data set is as follows:
1. Randomly split the strings into equal size training, validation, and test sets.
2. Let x be the size (number of states) of the de-facto automaton for the training
set. Generate a collection of models of various sizes using two methods:
(A) Test x parameter values using ALERGIA. (This is enough to find most of
the possible models.)
Test using mod-ALERGIA with
(which behaves the same as ALERGIA). Test the remaining x=2 parameter
varying ff; fi and fl. Merge low frequency components with their immediate
parents.
3. Assess goodness of a model using metric values calculated against the validation
set (see below). For each unique model size (number of states), keep the best
model generated by each method.
4. Recalculate the metrics for the selected models against the test set and compare
the results of the two methods.
Two different metrics are used. The first is cross entropy (also called Kullback-Liebler
divergence) which quantifies the probabilistic fit of one model to another.
This measure has previously been used to evaluate stochastic grammatical inference
methods [37]. Given two probabilistic language models, M 1 and M 2 , the cross
entropy is defined as:
where PM1 (x) is the probability in the set and PM2 (x) is the probability assigned
by the model. We estimate this with L first equal to the validation set and later
the test set.
Some strings in the validation and test sets are not recognized by the model.
We find the total probability of these and call it the error. (It corresponds to the
probability of rejecting a valid string if the SFA is stripped of its probabilities and
GRAMMAR INFERENCE FOR TEXT 25
model size both A B
54.3

Figure

15. Average percentage of each size interval covered. For example, 54.3 percent of interval
[2,16] means an average of models in that interval. The "both" column gives
models generated by both methods. The "A" and "B" columns give models generated just by the
ALERGIA and mod-ALERGIA searches.
used as a DFA.) We use this as the second metric. Also, rather than using an
infinite log value in these cases to give an infinite cross entropy, we use the largest
log value observed in the data set. This gives a finite metric in which a missing
string adds a penalty equal to the worst present string.
Values of ff; fi, and fl are chosen by repeatedly scanning the unit interval with
successively smaller increments until the chosen number of points have been tested.
So, for example, the first pass starts at 0.5 and increments by 1.0 thus testing only
one point; the second starts at 0.25 and increments by 0.5 testing two; and so
on. Values for fl are used directly, while ff and fi values are squared first to allow
probability differences that are more evenly spaced (recall the equivalence test used
for unmodified ALERGIA.)
Since different ranges of model sizes are useful for different purposes, we break
results up into the following size intervals: [2,16], [17,32], [33,64], and [65,128] (size
1 is excluded because all size 1 models for a given element are the same). We also try
to ensure that each search method tests an approximately equal number of points
in each interval. This is done by recording the parameter intervals corresponding to
the model size intervals and avoiding parameters in an interval once enough points
have been tested.
On a SUN supersparc, the runs averaged 11 minutes per element over the 85
elements. A total of 2872 models of different sizes were generated. Of these, 2263
were found by both searches, 27 were found only by the ALERGIA search, and
were found only by the mod-ALERGIA search. Figure 15 shows the average
percentage of each size interval covered. In general, the fact that mod-ALERGIA
finds a significant number of models that ALERGIA does not makes it more useful
when searching for a model of a particular size (we give an example in the next
section).

Figure

compares cross entropy and error for the 2263 model sizes found by
both methods across the 85 data sets. Improvements diminish for larger models.
This is because larger models keep more high frequency nodes from the de-facto
automaton. These high frequency nodes tend to be statistically significant and
model size cross entropy error

Figure

16. Average percent improvements of mod-ALERGIA over ALERGIA in cross entropy and
error for models in different size intervals. The bracketed numbers are p-values for a one sided t
test that the difference is greater than 0.
avg. node freq. cross entropy error
12-20 4.1 (5e-15) 4.8 (4e-17)

Figure

17. Average percent improvement of mod-ALERGIA over ALERGIA in cross entropy
and error for models generated from de-facto automata with various average node frequencies.
Intervals were chosen to break the data into four equal size sets. The bracketed numbers are
p-values for a one sided t test that the difference is greater than 0.
are therefore treated essentially the same by both algorithms leaving fewer low
frequency components to treat differently. Put another way, there are fewer different
ways for mod-ALERGIA to generate a model with many states, and thus less
differentiation from ALERGIA for such a model.
In addition to target model size, the size and variability of the training set affects
the relative performance of the two algorithms. We quantify this amount by calculating
the average node frequency in the de-facto automaton (which is the same as
the sum of all string lengths in the training set divided by the number of states in
the de-facto automaton). Sorting the 2263 data points according to this value and
breaking them into four equal size sets gives the results in Figure 17. As expected,
the modified algorithm does better when less frequency information is available.
these experiments demonstrate that mod-ALERGIA can be used to produce
more models in any given size range; and, even with a completely automatic
procedure and simple default treatment of low frequency components, it can be
used to find probabilistically better models. The advantage of mod-ALERGIA is
greatest for small models and low frequency training sets.
GRAMMAR INFERENCE FOR TEXT 27
daVinci
V1.4.2

Figure

18. An inference result for the Entry element from the OED.
4.2. Particular Examples
This section gives two examples that demonstrate some other advantages of the
stochastic inference approach in general, and of the modified algorithm in particular.
For the first example we use the Entry element from the OED and create an overgeneralized
model to compare with the prototypical entry presented in Figure 1.
ALERGIA does not produce any models for this element in the size range of 2 to
nodes. (Even using a bisection search that narrows the search interval all the
way down to adjacent numbers in a double precision floating point representation.)
In contrast, the mod-ALERGIA search described in the previous section generates
a model for every size in this interval. After inspection of a few of these smaller
models, we found the seven node graph shown in Figure 18 as most similar to the
prototypical entry. This model highlights several interesting characteristics. One
Level Model
Rest of High0011000000111111000000000111111111
Figure

19. The first three nodes of the Monograph element from the CPS data. All clipped
components indicated with scissors are low frequency components.
of the paths (HG VL ET S4*) does correspond to the prototypical entry, but note
some of the semantics that are not present in the non-stochastic description:
ffl The variant form list (VL) is optional and is actually omitted more often than
not.
ffl The etymology (ET) can also be omitted, skipping directly to the senses. Most
often this does not happen.
ffl An element not mentioned in Figure 1, the status (ST), frequently precedes the
headword group (HG) and its presence significantly increases the chance that
the ET and VL will be bypassed. If they are not bypassed, however, a label
(LB) element is normally inserted between them and the HG.
ffl Any number of LBs can also occur in an entry without an ST. Usually, however,
not many occur (the loop probability is only 0.262).
Properties such as these can be extremely useful when it comes to exploring and
understanding the data, even if they are disregarded for more standard grammar
applications such as validating a document instance. Furthermore, the stochastic
properties of the grammar can be used to exercise editorial control when new entries
are introduced into the dictionary: patterns that rarely occur can first trigger a
message to the operator to double-check for correctness; if asserted to be what was
GRAMMAR INFERENCE FOR TEXT 29
intended they can be entered, yet flagged for subsequent review and approval by
higher-level editorial authorities.
In our second example we use the Monograph element from the CPS data to
again comment on the advantage of separating low frequency components (we have
already done this for the PQP example). Figure 19 shows the first three high
frequency nodes of a model for this data. Outgoing low frequency components are
shown clipped. To get a final detailed model, we need to expand and examine the
subtrees of these low frequency components one at a time. For each subtree we
have the option of interactively stepping through positions where it can merge (for
instance the immediate parent, and all other nodes from which it can be parsed),
deciding to change the inference parameters to reclassify part of it as high frequency,
or deciding that it represents an error in the data. This type of interactive correction
is not possible with unmodified ALERGIA.
5. Conclusions and Future Work
This study was concerned with the application of grammatical inference to text
structure, a subject that has been addressed before [1, 2, 3, 10, 14, 38]. Grammar
generation can be an important tool for maintaining a document database system.
It is useful for creating grammars for standard text database purposes, but also
allows a more flexible view. Rather than having a fixed grammar that describes
all possible forms of the data, the grammar is fluid and evolves. Not only does the
grammar change as new data is added, but many different forms of the grammar
can be generated at any time, an over-generalized high-level view or a description
for a subset of the data, for example. Thus we can generate grammars as much to
summarize and understand the organization of the text as to serve in traditional
capacities like a schema.
Our approach adds two things to previous approaches: extension to stochastic
grammatical inference, and an algorithm with greater freedom for interactive tun-
ing. The advantages of changing to stochastic inference are as follows:
ffl Stochastic inference is more effective since it uses frequency information as part
of the inference process. This is true for any learning method.
ffl Stochastic models have richer semantics and are therefore easier to interpret
and interactively adjust. This was demonstrated with the Entry example in Section
4.2. Note that stochastic models can easily be converted to non-stochastic
ones by dropping the probability information. Therefore, we are free to use the
algorithm just as a more effective method for learning non-stochastic models.
ffl A stochastic inference framework allows parameterization that can be used to
produce different models for a single data set. This flexibility can be used
to search for a single best model, or to explore several models at different
generalization levels. Existing non-stochastic approaches to this problem all
work as black boxes producing a single, un-tunable result.
The additional tunability of the modified algorithm was shown to be useful in
two ways: an experimental evaluation using four different texts, and two examples
using specific elements from those texts.
Possibilities exist for further improvement of the algorithm. For example, the
state merging paradigm for learning finite automata has seen some development
since ALERGIA was first published. In particular, a control strategy that compares
and merges nodes in a non-fixed order has been developed [29]. This gives
more freedom to merge nodes in order of the evidence supporting the merges. Incorporating
it into our algorithm would be straightforward, especially in view of
the fact that it is trivial to convert the result of a statistical test to an evidence
measure. Another improvement would be to develop evidence measures to assist
the user in choosing merge destinations for low frequency components. Possible
starting points were mentioned in Section 3.4.
Much future work exists integrating the method into a system to support traditional
applications. For example, the semi-structured database system Lore [31]
does generate schemas for use in query planning and optimization but performs no
generalization, effectively stopping at the prefix tree. The schemas are therefore
not necessarily compact or understandable.
In addition to traditional applications, the stochastic part of the grammar also
suggests many novel applications. For example, a system could be constructed to
assist authors in the creation of documents by flagging excessively rare structures in
the process of their creation, or listing possible next elements of partially complete
entries in order of their probability. Stochastic grammars could also be used as
structural classifiers by characterizing the authoring styles of two or more people
who use the same tag set.

Acknowledgments

Financial assistance from the Natural Sciences and Engineering Research Council
of Canada through a postgraduate scholarship, the Information Technology Re-search
Center (now, Communications and Information Technology Ontario), and
the University of Waterloo is gratefully acknowledged.



--R

Generating Grammars for Structured Documents Using Grammatical Inference Methods.
Forming grammars for structured docu- ments: An application of grammatical inference
Generating grammars for SGML tagged texts lacking DTD.
Structured Documents.
The research potential of the electronic OED2 database at the University of Waterloo: a guide for scholars.
A Guide to the Oxford English Dictionary: The essential companion and user's guide.
Extensible markup language (xml) 1.0.

Learning stochastic regular grammars by means of a state merging method.
Grammar generation and query processing for text databases
Finite state transduction tools.
Markup systems and the future of scholarly text processing.

daVinci 1.4 User Manual
Syntactic Pattern Recognition and Applications.
Enabling query formulation and optimization in semistructured databases.
Mind your grammar: a new approach to modelling text.
Probability inequalities for sums of bounded random variables.
Concept learning and the problem of small disjuncts.
Introduction to Automata Theory
Oxford Advanced Learner's Dictionary of Current English (Fourth Edition).
Hidden Markov Models for Speech Recognition.

Structuring the text of the Oxford English Dictionary through finite state transduction.
A structured document database system.
Krogh, editor. Compendium of Pharmaceuticals and Specialties
Regular right part grammars and their parsers.
Results of the Abbadingo one DFA learning competition and a new evidence driven state merging algorithm.
The estimation of stochastic context-free grammars using the inside-outside algorithm
A database management system for semistructured data.
Wrapper induction for semistructured
Inferring regular languages in polynomial updated time.
Oxford University Press.
Visualizing text.
On the learnability and usage of acyclic probabilistic automata.
Statistical inductive learning of regular formal languages.
creating DTDs via the GB-engine and Fred
The Oxford English Dictionary
Inducing probabilistic grammars by Bayesian model merging.

Grammatical inference: An introductory survey.
Application of a stochastic grammatical inference method to text struc- ture
--TR
Markup systems and the future of scholarly text processing
On the learnability and usage of acyclic probabilistic finite automata
Lore
Regular right part grammars and their parsers
Introduction To Automata Theory, Languages, And Computation
Hidden Markov Models for Speech Recognition
Grammatical Inference
Learning Stochastic Regular Grammars by Means of a State Merging Method
Forming Grammars for Structured Documents
Inducing Probabilistic Grammars by Bayesian Model Merging
DataGuides
Mind Your Grammar
Statistical Inductive Learning of Regular Formal Languages

--CTR
Robert H. Warren , Frank Wm. Tompa, Multi-column substring matching for database schema translation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: Learning Document Type Descriptors from XML Document Collections, Data Mining and Knowledge Discovery, v.7 n.1, p.23-56, January
Enrique Vidal , Franck Thollard , Colin de la Higuera , Francisco Casacuberta , Rafael C. Carrasco, Probabilistic Finite-State Machines-Part I, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1013-1025, July 2005
Enrique Vidal , Frank Thollard , Colin de la Higuera , Francisco Casacuberta , Rafael C. Carrasco, Probabilistic Finite-State Machines-Part II, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1026-1039, July 2005
text database structure;stochastic grammatical inference