Empirically Estimating Order Constraints for
Content Planning in Generation
Pablo A. Duboue and Kathleen R. McKeown
Computer Science Department
Columbia University
10027, New York, NY, USA
{pablo,kathy}@cs.columbia.edu
Abstract
In a language generation system, a
content planner embodies one or more
“plans” that are usually hand–crafted,
sometimes through manual analysis of
target text. In this paper, we present a
system that we developed to automati-
cally learn elements of a plan and the
ordering constraints among them. As
training data, we use semantically an-
notated transcripts of domain experts
performing the task our system is de-
signed to mimic. Given the large degree
of variation in the spoken language of
the transcripts, we developed a novel al-
gorithm to find parallels between tran-
scripts based on techniques used in
computational genomics. Our proposed
methodology was evaluated two–fold:
the learning and generalization capabil-
ities were quantitatively evaluated us-
ing cross validation obtaining a level of
accuracy of 89%. A qualitative evalua-
tion is also provided.

on techniques used in computational genomics
(Durbin et al., 1998), where from large amounts
of seemingly unorganized genetic sequences, pat-
terns representing meaningful biological features
are discovered. In our application, a transcript is
the equivalent of a sequence and we are searching
for patterns that occur repeatedly across multiple
sequences. We can think of these patterns as the
basic elements of a plan, representing small clus-
ters of semantic units that are similar in size, for
example, to the nucleus-satellite pairs of RST.
1
By learning ordering constraints over these ele-
1
Note, however, that we do not learn or represent inten-
tion.
age, gender, pmh, pmh, pmh, pmh, med-preop,
med-preop, med-preop, drip-preop, med-preop,
ekg-preop, echo-preop, hct-preop, procedure,

Figure 2: The semantic sequence obtained from
the transcript shown in Figure 1.
ments, we produce a plan that can be expressed
as a constraint-satisfaction problem. In this pa-
per, we focus on learning the plan elements and
the ordering constraints between them. Our sys-
tem uses combinatorial pattern matching (Rigout-
sos and Floratos, 1998) combined with clustering
to learn plan elements. Subsequently, it applies
counting procedures to learn ordering constraints

these briefings were collected and annotated for
the aforementioned evaluation. The resident was
2
These units can be loosely related to the concept of mes-
sages in (Reiter and Dale, 2000).
equipped with a wearable tape recorder to tape
the briefings, which were transcribed to provide
the base of our empirical data. The text was sub-
sequently annotated with semantic tags as shown
in Figure 1. The figure shows that each sentence
is split into several semantically tagged chunks.
The tag-set was developed with the assistance of
a domain expert in order to capture the different
information types that are important for commu-
nication and the tagging process was done by two
non-experts, after measuring acceptable agree-
ment levels with the domain expert (see (McK-
eown et al., 2000)). The tag-set totalled over 200
tags. These 200 tags were then mapped to 29 cat-
egories, which was also done by a domain expert.
These categories are the ones used for our current
research.
From these transcripts, we derive the sequences
of semantic tags for each transcript. These se-
quences constitute the input and working material
of our analysis, they are an average length of 33
tags per transcript (min = 13, max = 66, σ =
11.6). A tag-set distribution analysis showed that
some of the categories dominate the tag counts.
Furthermore, some tags occur fairly regularly to-

pmh
, treated
with to his neck, back and chest.
Hyperspadias
pmh
,
BPH
pmh
,
hiatal hernia
pmh
and
proliferative lymph edema in his right arm
pmh
. No IV’s or blood pressure down in the left
arm. Medications —
Inderal
med-preop
,
Lopid
med-preop
,
Pepcid
med-preop
,
nitroglycerine
drip-preop
and
heparin
med-preop

SPLASH (Califano, 1999) are good representa-
tives of this kind of algorithm. We used an adap-
tation of TEIRESIAS.
The algorithm can be sketched as follows: we
apply combinatorial pattern discovery (see Sec-
tion 3.1) to the semantic sequences. The obtained
patterns are refined through clustering (Section
3.2). Counting procedures are then used to es-
timate order constraints between those clusters
(Section 3.3).
3.1 Pattern detection
In this section, we provide a brief explanation of
our pattern discovery methodology. The explana-
tion builds on the definitions below:
L, W pattern. Given that Σ represents the se-
mantic tags alphabet, a pattern is a string of
the form Σ (Σ|?)
∗
Σ, where ? represents a
don’t care (wildcard) position. The L, W 
parameters are used to further control the
amount and placement of the don’t cares:
every subsequence of length W, at least L
positions must be filled (i.e., they are non-
wildcards characters). This definition entails
that L ≤ W and also that a L, W  pattern
is also a L, W + 1 pattern, etc.
Support. The support of pattern p given a set of
sequences S is the number of sequences that
contain at least one match of p. It indicates

.
offset list: {(α, 0); (α, 6); (β, 2); . . .}
Figure 3: A pattern, a set of sequences and an
offset list.
ABC??DF
ABCA?DF ABC??DFG
❍
❍
❍❥
✟
✟
✟✙
less specific than
Figure 4: The specificity relation among patterns.
threshold, finding maximal L, W-patterns with
at least a support of support threshold. Our im-
plementation can be sketched as follows:
Scanning. For a given window size n, all the pos-
sible subsequences (i.e., n-grams) occurring
in the training set are identified. This process
is repeated for different window sizes.
Generalizing. For each of the identified subse-
quences, patterns are created by replacing
valid positions (i.e., any place but the first
and last positions) with wildcards. Only
L, W patterns with support greater than
support threshold are kept. Figure 5 shows
an example.
Filtering. The above process is repeated increas-
ing the window size until no patterns with

larity in context.
A convenient solution was to further cluster the
patterns, according to an approximate matching
distance measure between patterns, defined in an
appendix at the end of the paper.
We use agglomerative clustering with the dis-
tance between clusters defined as the maximum
pairwise distance between elements of the two
clusters. Clustering stops when no inter-cluster
distance falls below a user-defined threshold.
Each of the resulting clusters has a single pat-
tern represented by the centroid of the cluster.
This concept is useful for visualization of the
cluster in qualitative evaluation.
3.3 Constraints inference
The last step of our algorithm measures the fre-
quencies of all possible order constraints among
pairs of clusters, retaining those that occur of-
ten enough to be considered important, accord-
ing to some relevancy measure. We also discard
any constraint that it is violated in any training
sequence. We do this in order to obtain clear-cut
constraints. Using the number of times a given
constraint is violated as a quality measure is a
straight-forward extension of our framework. The
algorithm proceeds as follows: we build a table
of counts that is updated every time a pair of pat-
terns belonging to particular clusters are matched.
To obtain clear-cut constraints, we do not count
overlapping occurrences of patterns.

≺
preceded
B
The obtained estimates, e
1
= c/c
1
and e
2
= c/c
2
,
will in general yield different numbers. We use
the arithmetic mean between both, e =
(e
1
+e
2
)
2
,
as the final estimate for each constraint. It turns
out to be a good estimate, that predicts accuracy
of the generated constraints (see Section 4).
4 Results
We use cross validation to quantitatively evaluate
our results and a comparison against the plan of
our existing system for qualitative evaluation.
4.1 Quantitative evaluation
We evaluated two items: how effective the pat-

L, W = 2, 3 and support threshold of 3. The
algorithm will normally find around 100 maximal
motifs. The clustering algorithm used a relative
distance threshold of 3.5 that translates to an ac-
tual treshold of 120 for an average inter-cluster
distance of 174. The number of produced clusters
was in the order of the 25 clusters or so. Finally, a
threshold in relevancy of 0.1 was used in the con-
straint learning procedure. Given the amount of
data available for these experiments all these pa-
rameters were hand-tunned.
4.2 Qualitative evaluation
The system was executed using all the available
information, with the same parametric settings
used in the quantitative evaluation, yielding a set
of 29 constraints, out of 23 generated clusters.
These constraints were analyzed by hand and
compared to the existing content-planner. We
found that most rules that were learned were val-
idated by our existing plan. Moreover, we gained
placement constraints for two pieces of semantic
information that are currently not represented in
the system’s plan. In addition, we found minor
order variation in relative placement of two differ-
ent pairs of semantic tags. This leads us to believe
that the fixed order on these particular tags can
be relaxed to attain greater degrees of variability
in the generated plans. The process of creation
of the existing content-planner was thorough, in-
formed by multiple domain experts over a three

(Langkilde and Knight, 1998; Bangalore and
Rambow, 2000; Knight and Hatzivassiloglou,
1995)). Concurrent work analyzing constraints on
ordering of sentences in summarization found that
a coherence constraint that ensures that blocks of
sentences on the same topic tend to occur together
(Barzilay et al., 2001). This results in a bottom-
up approach for ordering that opportunistically
groups sentences together based on content fea-
tures. In contrast, our work attempts to automati-
cally learn plans for generation based on semantic
types of the input clause, resulting in a top-down
planner for selecting and ordering content.
6 Conclusions
In this paper we presented a technique for extract-
ing order constraints among plan elements that
performs satisfactorily without the need of large
corpora. Using a conservative set of parameters,
we were able to reconstruct a good portion of a
carefully hand-crafted planner. Moreover, as dis-
cussed in the evaluation, there are several pieces
of information in the transcripts which are not
present in the current system. From our learned
results, we have inferred placement constraints of
the new information in relation to the previous
plan elements without further interviews with ex-
perts.
Furthermore, it seems we have captured order-
sensitive information in the patterns and free-
order information is kept in the don’t care model.

versity Center for Advanced Technology in In-
formation Management (funded by the New York
State Science and Technology Foundation). The
authors would like to thank Regina Barzilay,
intraop-problems intraop-problems



operation 11.11%
drip 33.33%
intraop-problems 33.33%
total-meds-anesthetics 22.22%



drip
intraop-problems



operation 14.29%
drip 14.29%
intraop-problems 42.86%
total-meds-anesthetics 28.58%



drip drip
intraop-problems intraop-problems


1st International Conference on Natural Language
Generation (INLG-2000), pages 194–200, Mitzpe
Ramon, Israel.
Andrea Califano. 1999. Splash: Structural pattern lo-
calization analysis by sequential histograms. Bioin-
formatics, 12, February.
Mukesh Dalal, Steven Feiner, , Kathleen McKeown,
ShiMei Pan, Michelle Zhou, Tobias Hollerer, James
Shaw, YongFeng,and Jeanne Fromer. 1996. Nego-
tiation for automated generation of temporal multi-
media presentations. In Proceedings of ACM Mul-
timedia ’96, Philadelphia.
Robert Dale. 1988. Generating referring expressions
in a domain of objects and processes. Ph.D. thesis,
University of Edinburgh.
Richard Durbin, S. Eddy, A. Krogh, and G. Mitchi-
son. 1998. Biological sequence analysis. Cam-
bridge Univeristy Press.
David Fisher, Stephen Soderland, Joseph McCarthy,
Fangfang Feng, and Wendy Lehnert. 1995. De-
scription of the umass system as used for muc-
6. In Morgan Kaufman, editor, Proceedings of the
Sixth Message Understanding Conference (MUC-
6), pages 127–140, San Francisco.
Eduard H. Hovy. 1993. Automated discourse gener-
ation using discourse structure relations. Artificial
Intelligence. (Special Issue on Natural Language
Processing).
J. Hudak and Marcela McClure. 1999. A comparative
analysis of computationalmotif–detectionmethods.

ence of the Association for Computational Linguis-
tics (ACL’97), Madrid, Spain.
Johanna D. Moore and C´ecile L. Paris. 1993. Plan-
ning text for advisory dialogues: Capturing inten-
tional and rhetorical information. Computational
Linguistics, 19(4):651–695.
Ehud Reiter and Robert Dale. 2000. Building Natural
Language Generation Systems. Cambridge Univer-
sity Press.
Isidore Rigoutsos and Aris Floratos. 1998. Combina-
torial pattern discovery in biological sequences: the
teiresias algorithm. Bioinformatics, 14(1):55–67.
Ellen Riloff. 1993. Automatically constructing a dic-
tionary for information extraction. In AAAI Press
/ MIT Press, editor, Proceedingsof the Eleventh Na-
tional Conference on Artificial Intelligence, pages
811–816.
Jacques Robin and Kathleen McKeown. 1996. Em-
pirically designing and evaluating a new revision–
based model for summary generation. Artificial In-
telligence, 85(1–2):135–179.
Appendix - Definition of the distance mea-
sure used for clustering.
An approximate matching measure is de-
fined for a given extended pattern. The ex-
tended pattern is represented as a sequence of
sets; defined positions have a singleton set,
while wildcard positions contain the non-zero
probability elements in their don’t care model
(e.g. given intraop-problems, intraop-problems, {drip 10%,intubation

1
. This is, again, a real number in [0, 1]. To
ensure symmetry, we define the distance between
p
1
and p
2
as the average between the one way dis-
tance between p
1
and p
2
and between p
2
and p
1
.