Contents

List of Figures

List of Tables

This thesis has been possible with the continuous support of many, many friends and colleagues. Sometimes just a word of encouragement, a smile in the corridor was all what it takes to keep the flow of effort through the days.

First and foremost, I would like to thank my family, in special my parents Ariel and Patricia, and my sister Carolina for their continuous support all through the years. I dedicate this thesis to them. To my extended family, in particular to Jaime, Mema, Victor, Ana, Vicky, Conri, Marina, Gusti, also my deepest thanks.

This thesis has been possible through the continuous guidance and support of my advisor, Prof. Dr. Kathleen R. McKeown. I have been blessed of having Kathy as my advisor. She is not only extremely knowledgeable in the subject matter of this dissertation, but I do believe she as also able to let out the best in each of her students. When Kathy speaks, she is the voice of the community speaking. Every time I had to change something in a paper following her advice, I find out later at conferences that her advice was well motivated. For all these years, thanks Kathy.

My thesis committee contained an unusual rainbow of skills that evaluated and contributed criticism to this thesis from different, varied perspectives. The committee chair, Prof. Dr. Julia Hirschberg has asked me some of the toughest research questions I have been asked in my life. Questions that kept me thinking for months. Questions for which I may spend years after having finished this thesis still looking for answers. I am most thankful to Julia for sharing her continuous scientific curiosity with me. My external committee members Prof. Dr. Dan Jurafsky and Dr. Owen Rambow both offered different perspectives over the subjects dealt in this dissertation. Dan made a many comments about the indirect supervised part. His comments helped me shape the problem in the way it is presented today. Owen was the other NLG person in the committee (aside from Kathy). I have admired Owen’s work since my candidacy exam and it has been a pleasure to have him in my committee. Finally, Prof. Dr. Tony Jebara contributed his deep knowledge in Machine Learning in several, different ways. I have learned a lot from Tony, both in the technical aspects of Machine Learning and in the inter-personal issues related to communicating with researchers in that community. I just wish I have had started interacting with Tony earlier in this dissertation. The machine learning part would be definitely better.

Special thanks go for Smara, Michel and Tita. This thesis wouldn’t be here without their continuous support through the years. Seriously. You know that very well. Thanks, thanks, thanks.

To my friends at the CU NLP Group: Michel Galley, Smaranda Muresan, Min-Yen Kan, Noemie Elhadad, Sasha Blair-Goldensohn, Gabriel Illouz, Simone Teufel, Hong Yu, Nizar Habash, Elena Filatova, Ani Nenkova, Carl Sable, Dave Evans, Barry Schiffman, James Shaw, Shimei Pan, Hongyan Jing, Regina Barzilay, Judith Klavans, Owen Rambow, Vassielios Hatzivassiloglou, David Elson, Brian Whitman, Dragomir Radev, Melissa Holcombe, Greg Whalen, Rebecca Passonneau, Sameer Maskey, Aaron Harnly, John Chen, Peter Davis, Melania Degeratu, Jackson Liscombe and Eric Siegel. To the GENIES Team, in special to Andrey Rzhetsky. To the MAGIC Team, in special to Dr. Desmond Jordan. To the Columbia and Colorado AQUAINT team for creating the environment where half of this thesis flourished, in particular to James Martin, Wayne Ward and Sameer Pradham.

To my friends at the Computer Science Department: Amélie Marian (et Cyril!), Sinem Guven, Guarav Kc, Panos (Panagiotis Ipeirotis), Liz Chen, Kathy Dunn, Alpa Shah, Gautam Nair, Anurag Singla, Tian Tian Zhou, Blaine Bell, Rahul Swaminathan, Vanessa Frias, Maria Papadopouli, Phil Gross, Katherine Heller, Jennifer Estaris, Eugene Agichtein and Gabor Blasko thanks for their friendship and support. My deepest thanks to Martha Ruth Zadok, Anamika Singh, Twinkle Edwards, Remiko Moss and Patricia Hervey. To my officemates: Liu Yan, Lijun Tang, dajia xiexie. Special thanks to the professors Luis Gravano, David Sturman, Bernie Yee, Bill Noble, and Sal Stolfo. Finally, to to my former students Howard Chu, Yolanda Washington, Min San Tan Co, Ido Rosen and Mahshid Ehsani, from which I learned much than what they might learned from me, most certainly.

To the many friends at Columbia University that keep me away from screens and keyboards and let me regain some of my lost sanity. Special thanks to Fabi (Fabiola Brusciotti), Sato (Satoko Shimazaki), Cari (Carimer Ortiz), Al (Alberto Lopez-Toledo), Steve (Steven Ngalo), Sila Konur, Daniel Villela, Ana Belén Benítez Jiménez, Gerardo Hernández Del Valle, Victoria Dobrinova Tzotzkova, Raúl Rodríguez Esteban. Also to: Tarun Kapoor, Hui Cao, Tammy Hsiang, Maria Rusanda Muresan, Priya Sangameswaran, Shamim Ara Mollah, Ivan Iossifov, Su-Jean Hwang, Enhua Zhang, Kwan Tong, Barnali Choudhury, Manuel Jesus Reyes Gomez, Isabelle Sionniere.

To the CRF staff, specially Daisy, Mark and Dennis, for allowing me to terrorize their computer facilities and cleaning after my mess.

I would like also to thank also my friends in Argentina, for their many years of support. In particular, special thanks to Maximal (Maximiliano Chacón), Alvarus (Álvaro De La Rua), Juancho (Juan Lipari), Juanjo (Juan José Gana), Erne (Ernesto Cerrate) and El Unca (Nicolás Heredia), for standing my continuous rantings over non-issues and always receiving me with an open container of unspecified beverages. Also thanks to my friends Diego Pruneda, Martin Lobo, Victoria de Marchi, Paola Allamandri, Andrea Molas, Carlos Abaca, Virginia Depiante, Dolores Table, Alejandra Villalba, Shunko Rojas, Eugenia Rivero, Andriana Quiroga, Clarita Ciuffoli, Maximiliano Oroná, Mariana Cerrate, Gustavo Gutierrez, Facundo Chacón, Paula Asis and Hernán Cohen for being my friends in spite of the distances.

To my friends at Fa.M.A.F.: Gabriel Infante López, Sergio Urinovksy, Nicolás Wolovick, Guillermo Delgadino, Tamara Rezk, Mirta Luján, Pedro Sánchez Terraf and Martin Dominguez, for making me feel I never left. To the professors Javier Blanco, Daniel Fridlender, Francisco Tamarit, Pedro D’Argenio and Oscar Bustos, for their friendship over the years. To my former students: Paula Estrella and Jimena Costa, may the luck of the draw with their next advisors be more favorable to them.

To my friends at UES21: Daniel Blank, Alejandra Jewsbury, Cristina Álamo and to my former students José Norte, Rolando Rizzardi, Federico Gomez, Liliana Novoa and Manuel Diomeda.

To my Argentinian friends in or around NYC: Matt (Matias Cuenca Acuña) and Cecilia Martinez for their continuous support even if I tend to disappear well too often, Alejandro Troccoli, Agus (Agustín Gravano), Quique (Sebastián Enrique), Nicolás Bruno, Guadalupe Cabido, Miguel Mosteiro, Paola Cyment, Marcelo Mydlarz, Tincho (Martín Petrella) and Nacho (Ignacio Miró).

To my Argentinian friends around the world: Patricia Scaraffia and Walter Suarez for being part of my extended family, Horacio Saggion, Fernando Cuchietti and Soledad Búcalo, Paula Sapone, Silvia Seiro, and family, Rainiero Rainoldi, and Alejandra González-Beltrán.

To Tita, Coco and Marina, for being my family away from home.

To my friends from the Association for Computational Linguistics: Anja Belz, Maria Lapata, Nikiforos Karamanis, Roger Evans, Michael White, Gideon Mann, Tomasz Marciniak, Roxana Girju, Maarika Traat, Francesca Carota, Stephen Wan, John Atkinson, Paul Piwek, David Reitter, Nicolas Nicolov, Karin Verspoor, Monica Rogati, Dan Melamed, Clare Voss, Roy Byrd, Srinivas Bangalore, Satoshi Sekine, Aggeliki Dimitromanolaki, Farah Benamara, Mila Ramos-Santacruz, Aline Villavicencio, Sonja Niessen, Rada Mihalcea, Ingrid Zukerman, Mona Diab, Rui Pedro Chaves, Nawal Nassr, Esther Sena, Sara Mendes. Many of you helped directly or indirectly to the completion of this dissertation. I look forward further collaboration in the years to come.

To my friends: Annie, Ellen, Xiao Ma, Raúl, Claudio, Sylvia, Marcos, Gimena, Bella, Grace. Maringela, Marylu, Flavia, Aparna, for being my friends in unusual circumstances.

For helping me go through this ordeal at different moments in my life: Lily, Kaming, Carolinita, Niina, Viara, Anushik, Jessica, Alba, Tiantian, Chihiro, Roxy, Keunyoung, Jael, Annie, Sepide, Ale, Patty, Vika, Patty, Luisa, and Cyd. My fondest memories are with each of you.

To my former suite-mates: Lillian, Yen, Majid, Stephen, Onur, Sakura, Miho, Susie, Ansel, Victoria, Arnaud, Gurol, Chihiro, Ramiro, Vikren, Heather, Muhammad, Veronica, Liz, and Melina. You guys taught me how to make the life in New York City a thrilling experience. May God brightens your path in life.

To my new colleagues at IBM: Jennifer Chu-Carroll, John Prager, Kryzsztof Czuba, Bill Murdock and Chris Welty, thanks for bearing the deposit frenzy. I look forward working with you. Also thanks to Glenny and Annie for a daily smile at the workplace (and pocky!).

A mis padres, Ariel y Patricia.

A mi hermana preferida, Carolina.

Chapter 1
Introduction

In a standard generation pipeline, any non-trivial multi-sentential/multi-paragraph generator will require a complex Strategic Component,¹ responsible for the distribution of information among the different paragraphs, bulleted lists, and other textual elements. Information-rich inputs require drastic filtering, resulting in a small amount of the available data being conveyed in the output. Moreover, building a strategic component is normally tightly coupled with the semantics and this depends on the idiosyncrasies of each particular domain.

Traditionally, Strategic Generation is divided into two subtasks: Content Selection, i.e., choosing the right bits of information to include in the final output, and Document Structuring, i.e., organizing the data in some sensible way. The overall goals of Strategic Generation are to produce text that is at the same time coherent (marked by an orderly, logical, and aesthetically consistent relation of parts; this measure relates to the structuring subtask), concise (expressing much in few words; this measure arguably relates to both subtasks, and it is not always a requirement) and appropriate (meant or adapted for an occasion or use; this measure relates to the selection subtask).

Figure 1.1, an example of the strategic generation task, shows the two main elements of input to a generation system: the input knowledge base (a set of facts, e.g., ex-spouse(person-1, person-2)) and the communicative goal (e.g., “Who is Sean Connery,”² or “Convince the Hearer that Sean loves Micheline,”³). The two example text excerpts differ at the content level (as opposed to differences at the word level, for example). Both of the aforementioned subtasks of the strategic component can be seen in this example. The first text is not only wrongly structured, but also contains facts that are irrelevant for the given communicative goal (e.g., eye-color) while failing to mention important ones (e.g., occupation). In contrast, the second text presents a much more felicitous selection of content, in addition to linking the facts in a reasonable and natural way.

The example also illustrates some related concepts in the strategic generation literature. For instance, there is a rhetorical relation of Cause between the facts award(person-1,oscar-1) and work(person-1,bond-1). The cue phrase “because” makes this relation explicit. The output of the Content Selection step is the relevant knowledge pool that in the example does not contain eye-color. The document plan is a sequence of messages, where each message is the instantiation of a rhetorical predicate using the input knowledge as arguments. In the example, intro-person(..) is a predicate with arguments first-name, last-name, occupation.⁴ On the other hand, intro-person(person-1) is a message —verbalized as “Sean Connery is an actor and a producer.”

Figure 1.2: Graph Rendering of my Knowledge Representation.

The difficulty of the strategic generation task resides in the fact that, without prior knowledge, any ordering in a subset of the input is a possible document plan. Since the planner can select any number k of facts between 1 and n (in ways) and then reorder each such set in k! ways, there are ∑_k=2ⁿ possible plans. This large number of possibilities makes for a very challenging task, that needs to be approximated with strong domain heuristics.

These domain heuristics depend on the type of the target texts. Of particular importance to this dissertation are texts that exhibit a fixed structure that can be explained by tracking the evolution of discourse in a field over time, but can not be explained with the information the text contains nor with domain knowledge itself. That is the case, for example, in discourse reporting or summarizing factual information. In such cases, the extra knowledge required to structure documents in these domains has been named Domain Communicative Knowledge or DCK (Kittredge et al., 1991). In the medical domain, therefore, we can distinguish domain independent knowledge (e.g., people have diseases that can be treated with surgery), domain specific knowledge (e.g., a surgery patient needs to be anesthetized), from DCK (e.g., in medical reports about bypass surgeries, the anesthestetics information should start the description of the surgery, right after the description of the patient). It is clear that DCK helps reduce the large number of orderings that can be expected a priori to a manageable set of feasible possibilities.

Even though there are general tools and techniques to deal with surface realization (Elhadad and Robin, 1996, Lavoie and Rambow, 1997) and sentence planning (Shaw, 1998, Dalianis, 1999), the inherent dependency on each domain makes the Strategic Generation problem difficult to deal with in a unified framework. My thesis builds on machine learning in an effort to provide such a tool to deal with Strategic Generation in an unified framework; machine learning techniques can bring a general solution to problems that require customization for every particular instantiation.

The work described in this thesis investigates the automatic acquisition of Strategic Generation logic,⁵ in the form of Content Selection rules and Document Structuring schemata, from an aligned Text-Knowledge corpus. A Text-Knowledge corpus is a paired collection of human-written texts and structured information (knowledge), similar to the knowledge base the generator will use to generate a text satisfying the same pragmatic (i.e., communicative) goals being conveyed in the human input text. For example, weather reports for specific dates may be paired with weather prediction data for each of those dates. The construction of such corpora is normal practice during the knowledge acquisition process for the building of NLG systems (Reiter et al., 2000). These corpora are increasingly popular in learning for NLG because they are readily available and do not require expensive hand labelling. However, they only provide indirect information about whether each piece of knowledge should be selected or omitted or the actual document structure. Indirect Supervised Learning (ISL) is my proposed solution to this problem. ISL has two steps; in the first step, the Text-Knowledge corpus is transformed into matched texts, an intermediate structure indicating where in the text each piece of knowledge is appearing (if it appears at all). From the matched texts, a training dataset of selected/omitted classification labels or document plans can be read out, accordingly. In the second step, Content Selection rules or Document Structuring schemata are learned in a supervised way, from the training dataset constructed in the previous step.

My thesis, therefore, receives as input the natural datasets for its learning task, in the form of text and knowledge. Such input is natural for this task, in the sense that this is the same material humans will use to acquire the Strategic Generation logic themselves. This is the type of information a knowledge engineer may use, together with other knowledge sources, to build a Strategic Generation component for a NLG system.

The rest of this chapter will address the definition of my problem in the next section, present my research hypothesis (Section 1.2), summarize my methods (Section 1.3), enumerate my contributions (Section 1.4), and introduce the domains (medical reports, biographical descriptions) where this research is grounded. An overview of each chapter concludes this introduction.

1.1 Problem Definition

My problem is the learning of control logic for particular implementations of the first two modules in a generation system. The acquired logic has to be appropriate to solve the Strategic Generation problem in isolation and within existing NLG systems. I describe the integration of my technique in existing NLG systems first, by examining my assumed NLG architecture, and then go deeper into the internals of the logic being sought.

1.1.1 Assumed NLG Architecture

As I am automatically acquiring the knowledge necessary for two internal processes inside a NLG system, the assumed architecture of the system is of great importance. I need to consider an architecture abstract enough to allow for a broad range of applications of the rules and schemata but grounded enough to be executable.

I expect the input data to be provided in a frame-based knowledge representation formalism. Each frame is a table of attribute-value pairs. Each attribute is unique, but it is possible to have lists as values. As such, the values can be either atomic or list-based. The atomic values I use in my work are Numeric (either integer or float); Symbolic (or unquoted string); String (or quoted string); and frame references (a distinguished symbolic value, containing the name of another frame in the frameset).⁶ The list-based types are lists of atomic values. Each frame has a unique name and a distinguished TYPE feature. This feature has a symbolic filler that can be linked to an ontology, if provided.

Because my knowledge representation allows for cycles, the actual knowledge representation can be seen as a directed graph: each frame is represented as a node and there are edges labeled with the attribute names joining the different nodes. Atomic values are also represented as special nodes. From this standpoint, the knowledge base of Figure 1.1 is just a factual rendering of the underlying representation. The actual knowledge base would be as shown in Figure 1.2.

Figure 1.3 shows my assumed two-stage NLG architecture. The Strategic Component is divided into the two modules I am learning. The figure also highlights the interaction between Strategic Generation and both aggregation and lexicalization in the Tactical Component, as they pose challenges to my learning system. The aggregation module will take a list of aggregation chunks (each containing a number of messages) and produce as output a list of sentences (each sentence containing one or more messages). The lexicalization module changes messages into words; it encompasses referring expressions, lexicalization and surface realization. Therefore, aggregation and lexicalization will re-order messages locally; when observing text as evidence of document plans the original ordering will be distorted. I will now discuss Content Selection and Document Structuring as they are the focus of this dissertation.

1.1.2 Content Selection Rules

The Content Selection module takes the full knowledge base as input and produces a projection (a subset) as output. This module should also consider the communicative goal when building the output subset. The output of the Content Selection module has been termed the relevant knowledge pool (McKeown, 1985), viewpoints (Acker and Porter, 1994) or generic structure potential (Bateman and Teich, 1995).

A possible implementation of a Content Selection module uses rules to decide whether or not to include a piece of information. This decision is based solely on the semantics of the data (e.g., the relation of the information to other data in the input). These rules take as input a node in the knowledge representation graph and execute a predicate on it (f : node →).

The decision of whether to include a given piece of data is done solely on the given data (no text is available during generation, as the generation process is creating the output text).⁷ The current node and all surrounding information are useful to decide whether or not to include a piece of data. For example, to decide whether or not to include the name of a movie, whether the movie was the reason behind an award (and the award itself) may be of use. Such a situation can be addressed with the rules defined below.

While I experimented with a number of rule languages, I will describe here the tri-partite rule language, a solution that exhibits the right degree of simplicity and expressive power to capture my training material in the biographical profiles domain. Other domains may require a more complex rule language but, in practice, the tri-partite rules are quite expressive and very amenable for learning.

Tri-partite rules select a given node given constraints on the node itself and a second node, at the end of a path rooted on the current node. For the constraints on nodes, I have used two particular type of constraints: whether or not the value of the node belongs to a particular set (e.g., value ∈) or a special (True) constraint that always selects the item for inclusion (the absence of any rule that selects a node is equivalent to a False rule). Again, more complex constraints are possible, but these types of constraints are easily learnable. Some example rules are detailed in Figure 1.4.

(-, -, -).       ;Select-All

Always say the first name of the person being described.

: (false, -, -).      ;Select-None

Never say the eye color of the person being described.

: (value ∈, -,-).

Only mention the name of an award if it is whether a Golden Globe or an Oscar.

: (-,,value ∈).

Only mention the title of a movie if the movie received an Oscar or a Golden Globe.

Figure 1.4: Example Content Selection rules.

1.1.3 Document Structuring Schemata

A schema is a particular solution to the Document Structuring task, a task that takes as input a subset of the knowledge base (the relevant knowledge pool) and returns a sequence of messages (a document plan). These messages are produced by communicative predicates (Figure 1.5) composed of three items: variables, properties and output. Each variable has a type, which further constrains the possible values it can take. The actual number and nature of these predicates varies from domain to domain. A predicate can be considered as a function that takes a number of defined (and maybe undefined) variables and searches the knowledge representation for values of the undefined variables that satisfy the constraints inside the predicate. If none are found (or if the provided variables do not satisfy the constraints), the predicate cannot be instantiated. For each set of values⁸ that satisfy its constraints, the predicate produces a message (Figure 1.6), a data structure assembled using the variable assignment found during the search. The messages are the nexus between the schema and the rest of the NLG system. A predicate, therefore, can be thought of in this context as a blueprint for making messages.

predicate Education
  variables
  

person	:	c-person
education-event	:	c-education-event

  properties
   education-event≡person.education
  output
  

Figure 1.5: Example of a communicative predicate in the biographical descriptions domain. This predicate uses a person and an education event frames such that the education event is among the person’s education events (education-event ≡ person.education). The generated output accesses fields in the education event to fill the output frame, e.g., the subject matter being studied (education-event→subject-matter).

  

Figure 1.6: Example of an instantiated predicate (message). These messages are later grouped by the aggregation component and verbalized by the lexicalization component.

Given a set of predicates, a schema (shown in Chapter 5, Figure 5.3) is a finite state machine over the language of predicates with variable references. At each step during schema instantiation, a current node is kept and all the predicates in the edges departing from the current node are instantiated. A focus mechanism will then select the next node (and add the message to the document plan). The instantiation process finishes when no new predicate can be instantiated departing from the current node. While the schema itself is simple (an automaton with predicate and variable names on its edges), the instantiation process presents some complexities. Interestingly, my schema induction algorithm is independent of the instantiation process or its internal details. However, this complexity forbids using existing learning techniques for finite state machines to learn the schemata.

Schemata are explained in detail in Chapter 2 (McKeown’s original definition, Section 2.2.1) and Chapter 5 (my schemata implementation, Section 5.1).

1.2 Research Hypothesis

My research hypothesis is three-fold. First, I share (McKeown, 1983)’s original research hypothesis that the text structure is usually different from the knowledge structure.⁹ I refer to the structure of the knowledge as domain orderings, such as time or space. This type of information controls some of the placement of information in the text, e.g., news articles about a certain event enumerate some events chronologically (Barzilay et al., 2001). However, these orderings cannot be expected a priori for every domain and, in general, text structure is not governed by them.

Second, as this dissertation focuses on learning schemata, my main hypothesis is centered on the feasibility of automatically constructing schemata from indirect observations, using shallow methods. Indirect observations refer to learning schemata from positive examples, contained in a Text-Knowledge corpus. I have this corpus instead of a fully supervised training material (in the form of document plans or sequences of predicates). Text has a linear structure, defined by the fact that words come one after another. Even though exact word placement is misleading (as it interacts with aggregation and lexicalization), I can match text and knowledge and migrate the text linear structure to the knowledge. In that sense, my hypothesis implies that shallow text analysis methods can be used to acquire Domain Communicative Knowledge (cf. Section 2.2, Chapter 2) for schema construction. That is, to gain information about the domain behavior in general, via Indirect Supervised Learning as described in the next section. This level of analysis lets me gain information about the behavior of the domain in general, but not necessarily solve an understanding task for each particular text.

Finally, part of my research hypothesis is that schemata are useful as a learning representation. Their simplicity, a fact that has been criticized in the literature (Zock, 1986, Hovy, 1993), make them a prime candidate for learning. Moreover, the fact they are learnable should shed more light on their empirical importance (already highlighted by the number of deployed NLG systems employing them (Paris, 1987, Maybury, 1988, Bateman and Teich, 1995, Lester and Porter, 1997, Milosavljevic, 1999)).¹⁰

1.3 Methods

The input to my learning system is thus knowledge and text. For the task of learning Strategic Generation logic, this is a supervised setting; the learning system is presented with the input to Strategic Generation (knowledge) and text that is determined from the output of the strategic generation component (relevant knowledge and document plans). As the text is not the output of the Strategic Generation component, but something that can be derived from the output of the strategic component, my solution to this problem is Indirect Supervised Learning, which I explain at length in Chapter 3, Section 3.2.

As mentioned in Section 1.1, the output of the Strategic Generation component is defined as follows: the relevant knowledge pool is a subset of the knowledge base, which I assume is a frame-based knowledge representation. The document plan is a sequence of messages (rhetorical predicates instantiated from the relevant knowledge pool), segmented into paragraphs and aggregation sets.¹¹

To obtain the relevant knowledge pool and the document plan, I build without human intervention an intermediate structure, the matched text, by using assumptions on how knowledge can be verbalized within the text. These matched texts are built without any examples of actual matched texts (unsupervised learning). For example, the first sentence of the biography in Figure 1.1 will produce the following matched text¹² when matched against the knowledge base shown in the figure:

With the matched text in hand, it is easy to see which knowledge has been selected for inclusion in the text: any piece of knowledge matched to a text segment is thus assumed to be selected by the human author for inclusion in the text. Having now a task (Content Selection) with training input (KB) and output (KB plus selection labels) pairs, this comprises a well defined learning problem, where Content Selection rules can be learned.

Continuing with the example, let’s suppose we have two biographies:

• Sean Connery is an actor and a producer. He received an Oscar for Best Actor for his acting in the movie ‘James Bond’.
• Sean Connery is an actor and a producer. He married and later divorced the actress Diane Cilento with whom he had a child, Jason. He also married Micheline Roquebrune, a painter.

The first biography is a business-style biography, while the second one is a family-style biography. For each style, the matched text provides labels for each fact in the knowledge base. These labels (selected or omitted) are shown in Figure 1.7 for the business-style biography.

To choose among the different possible rulesets (e.g., ruleset ₁ and ruleset ₂), I look at the information retrieval task of retrieving the labels (selected, omitted) for each piece of knowledge in the input knowledge base. The F^*-measure from information retrieval (van Rijsbergen, 1979) of this retrieval task can be used as a likelihood for each ruleset. The supervised learning step becomes searching for the ruleset that maximizes this likelihood. Therefore, if the F^*-measure of the labels obtained by applying ₁ to the training set is greater than the F^*-measure of applying ₂, then ₁ should be preferred over ₂.

The matched text also provides input and output for learning schemata: the input to a schemata-based strategic component is the relevant knowledge pool, extracted in the previous Content Selection step. The output of the schema, the document plan, can not directly be extracted from the matched text, but the sequence of matched pieces of knowledge can approximate the messages.

That is, the sequence of pieces of knowledge (facts) extracted for the matched text of the biography shown in Figure 1.1 will read as follows:

Compare this to the document plan shown in Figure 1.1. As document plans are at the predicate level, I mine patterns over the placement of atomic pieces of knowledge in the knowledge sequence extracted from the text (in the example above, I find that name-first, name-last, occupation is a recurring pattern), mine order constraints over them and use the constraints to evaluate the quality of document plans from possible schemata. Finally, to compare sequences of atomic pieces of knowledge to predicates, I defined a dynamic programming-based metric, explained in Chapter 5, Section 5.4.2.

Given a set of relevant knowledge pool–document plan pairs, I define the likelihood of a schema by summing up three terms:

• F* of the associated knowledge retrieval task (on-line content selection): disregarding the ordering, see which percentage of the right information appears in the output.
• Number of order constraints the output of the schema satisfies: measures local ordering.
• Alignment distance between the output of the schema and the target sequence of atomic values: measures global ordering.

As with Content Selection, defining means to tell good schemata from bad ones renders the learning problem an optimization one.

1.3.1 Technical Approach

On technical grounds, Figure 1.8 shows a generalized graphical model¹³ for my system. There, my observed input (knowledge base) and output (text) are marked in black. The mapping I am interested in learning is “knowledge base” to “relevant knowledge pool” and “relevant knowledge pool” to document plan.

Indirect Supervised Learning involves an unsupervised step, based on assumptions on the structure of the model, to elucidate the hidden variables and supervised steps to generalize from the constructed mapping.¹⁴ The assumptions on the model I use are related to the ways knowledge can appear on the text. More specifically, I see the knowledge as a collection of atomic items (the concepts), and I see the text as a collection of phrases. The relation between phrases and concepts is given by a verbalization function from concepts to sets of phrases (possible verbalizations). The model I use for the unsupervised part is summarized by the following two tests, where H₀ is the null hypothesis, p and c are particular phrases and concepts, is the set of phrases that make a particular text, is the set of concepts that make a particular knowledge representation (where and refer to the same entity) and is the verbalization dictionary:

Here, H₀ says that if a given phrase p is not a verbalization of a given concept c, then knowing that c holds will not change the chances of p appearing in the text. On the contrary, H₁ says that is p is a verbalization for c, knowing that c holds makes it much more likely for p to appear in the text.

Figure 1.8: Learning Architecture.

Supervised Learning. As the experiments in Chapter 3 will attest, the matched text construction process is able to identify in an automatic fashion training material with an F^*-measure as high as 0.70 and as low as 0.53. These results imply that learning using the matched texts as training material will require a robust machine learning methodology. I will now mention some features common to the supervised learning algorithms presented in Chapter 4 and Chapter 5. Both Content Selection rules and Document Structuring schemata are symbolic and highly structured in nature. In both cases, I have input and output pairs (I,O) to learn them, extracted from the matched text. I am interested in finding the object o^* (belonging to the set of all possible Content Selection rules or Document Structuring schemata, in either case) such that o^* maximizes the posterior probability given the training material:

Here, instead of computing the probability P(o|I,O), I use the input/output pairs to compute for each putative object o a likelihood f(o,I,O). This likelihood will also allow me to compare among the different o and it is thus a quality function in the representation space. In both cases, I use a similarly defined function: employ the rules or the schemata to generate from the input I a set of outputs O′. The sought quality function becomes the distance between the training output and the produced output, ||O-O′||, for suitable distances.

Given the quality function, finding o implies a search process on the large space of representations. Several algorithms can be of use here (e.g., A^*, hill-climbing or simulated annealing). However, given the highly structured nature of my representations, I have found it valuable to define a successor instance coming from two instances in the search pool, instead of one. This type of approach is known as Genetic Algorithms (GAs). In general, I consider GAs as a meaningful way to perform symbolic learning with statistical methods.

System Architecture. The process described above is sketched in Figure 1.9, using the thresholds and parameters¹⁵ described in Table 1.1. The Text and Knowledge corpus is fed into a matched text construction process, described in Chapter 3. This process will employ the model with a minimum score on the t-values (thr_t) for concepts that appear in at least thr_supp documents. Once some matches have been identified, a disambiguation process using w words around each match will be spanned.

From the matched text, a Content Selection dataset will be used to learn Content Selection rules (presented in Chapter 4). This process is centered about a GA with a population of population_size. This initial population is built using a bread-first search until depth depth in the knowledge graph. The fitness function will weight precision and recall using a weight of α.

Also from the matched text, sequences of semantic labels are extracted and used to learn Order Constraints (Chapter 5). For this process, only patterns that appear in a supportthreshold sequences are further considered. The mined constraints are only considered if their associated probability is above thr_oc.

Finally, the Content Selection dataset, the Order Constraints, sequences of atomic values extracted from the matched text and rhetorical predicates are all used to learn schemata (Chapter 5). A population of population_size⁽²⁾ is used to learn schemata with a maximum of n_v variables per type.

Figure 1.9: System Architecture.

1.4 Contributions

This thesis puts forward contributions at three levels. First, it contributes by devising, implementing and testing a system for the automatic construction of training material for learning Content Selection and Document Structuring logic. The technique described in Chapter 3 is able to process hundreds of text and knowledge pairs and produce Content Selection training material with quality as high as 74% precision and 67% recall. The Document Structuring material (orderings) it produces is also highly correlated to hand annotated material. This matched texts construction process emphasizes the use of structured knowledge as a replacement for manual tagging. The Text-Knowledge corpus in the biographies domain assembled as part of this thesis is now a valuable resource, available for further research in the area, together with the machinery to obtain new training material in a number of domains discussed in Chapter 9. The evaluation methodology employed in this thesis is also a contribution: using a number of human written texts for evaluation, dividing them into training and test set and using the test set to evaluate both the unsupervised as well as the supervised steps. Alternative approaches will require larger amounts of human-annotated data or will leave the unsupervised part without proper evaluation.

Second, among my contributions are also the proposal and study of techniques to learn Content Selection logic from a training material consisting of structured knowledge and selection labels. As the training material is automatically obtained, it contains a high degree of noise. Here, my contribution includes techniques that are robust enough to learn in spite of this noise. I set the problem as a rule optimization of the F^*-measure over the training material. My techniques have elucidated Content Selection rules in four different styles in the biographies domain. Moreover, my experiments in Content Selection contribute to our understanding of the Content Selection phenomenon at several levels. First, it separates nicely the need for off-line (high-level) Content Selection from on-line Content Selection, where the approach described in this thesis could potentially be used to learn Content Selection logic at both levels.¹⁶ From a broader perspective, my acquired Content Selection rules provide an empirical metric for interestingness of given facts.

Finally, I defined the problem of learning Document Structuring schemata from indirect observations, proposing, implementing and evaluating two different, yet similar techniques in two different domains. The Document Structuring problem is one of the most complex problems in NLG. My techniques are among the first efforts to effectively learn Document Structuring solutions automatically. At a fine grained level of detail, my main contribution is a dynamic-programming metric that compares sequences of values (that can be read out from text) to sequences of messages (that are produced by the schemata). The acquired schemata are written in a declarative formalism, another contribution of this thesis. Previous implementations of schemata had mixed declarative/procedural definitions that impose a high burden for any learning technique.

1.5 Domains

I discuss now my experimental domains (Medical Reports and Person Descriptions). These domains were central to research projects I have been involved with. Other potential domains are discussed in Section 9.3, including Biology, Financial Markets, Geographic Information Systems, and Role Playing Games.

1.5.1 Medical Domain: MAGIC

MAGIC (Dalal et al., 1996, McKeown et al., 2000) is a system designed to produce a briefing of patient status after the patient undergoes a coronary bypass operation. Currently, when a patient is brought to the intensive care unit (ICU) after surgery, one of the residents who was present in the operating room gives a briefing to the ICU nurses and residents. The generation system uses data collected from the machine in the operating room to generate such a presentation, avoiding distracting a caregiver at a time when they are critically needed for patient care.

Figure 1.10 shows an example of a data excerpt (a data file in the classic formalism with 127 facts on average) and presentation. Several of the resident briefings were collected and annotated for a past evaluation. Each transcription was subsequently annotated with semantic tags as shown in Figure 6.2, on page §.

1.5.2 Person Descriptions: AQUAINT Q&A

As part of the Question Answering project (AQUAINT) taking place jointly at Columbia University and University of Colorado, I have developed ProGenIE, a system that generates biographic descriptions of persons, taking as input information gathered from the WWW. The biographical descriptions domain is central, as it has available larger amounts of data compared to the medical domain. Because of this data availability, I only pursued Content Selection experiments in this domain.

For these experiments, fact-sheet pages and other structured data sources provide the input knowledge base (Duboue and McKeown, 2003b). The texts are the biographies written by professional writers or volunteers, depending on the corpus. Figure 1.11 exemplifies an aligned pair.

This domain is very rich, allowing me to gather multiple biographies for each person I have independently obtained knowledge. Such multi-aligned corpus had also proven useful for mining verbalization templates (Barzilay and Lee, 2002).

1.6 Structure of this Dissertation

This dissertation is divided into the following chapters.

Chapter 2.

Relation between this thesis and previous research. The research in Strategic Generation is quite vast, so the focus of the chapter is in document structuring via schemata (although key RST-based papers are also discussed). Other learning approaches in NLG are also discussed.

Chapter 3.

Learning approach, focusing on the unsupervised part. The construction of the matched texts is the focus of this chapter. It presents the foundation for learning Content Selection rules and Document Structuring schemata. Its experimental results are in the biographical profiles generation.

Chapter 4.

Supervised learning of Content Selection rules. This includes a discussion of the rules themselves and different methods to acquire them automatically. Meaningful baselines for comparison are also discussed. It also contains experimental results in the biographies domain.

Chapter 5.

Supervised learning of Document Structuring schemata. A new, declarative, version of (McKeown, 1985) schemata is introduced and its automatic construction through an adaptation of existing methods to learn finite state machines is presented.

Chapter 6.

Preliminary Document Structuring experiments performed in medical domain. They show the feasibility of the technique in a different domain.

Chapter 7.

Document Structuring experiments in biographical profile generation.

Chapter 8.

Limitations of the approach. A succinct description of some limitations I have identified throughout the thesis.

Chapter 9.

Conclusions and some possible extensions.

Chapter 2
Related Work

In this chapter, I discuss related work in Strategic Generation and learning in NLG. These topics are very broad; I have decided to focus on a small number of highly relevant papers. I first analyze related work in Content Selection (Section 2.1), in particular, the work on the ILEX (Cox et al., 1999, O’Donnell et al., 2001) and STOP (Reiter et al., 1997) projects. Afterwards, I introduce the Document Structuring task together with schemata and RST, its two most widespread document structuring solutions. I then relate my work to other recent learning efforts in NLG in Section 2.3. To conclude this chapter, I present related work in a number of assorted areas, including the relation between the strategic component and other modules of the NLG pipeline, planning diverse media, summarization and biography generation.

2.1 Related Work in Content Selection

Content Selection, the task of choosing the right information to communicate in the output of a NLG system, has been argued to be the most important task from a user’s standpoint; users may tolerate errors in wording, as long as the information being sought is present in the text (Sripada et al., 2001). This task has different levels of complexity, with solutions requiring a full inferential engine in certain cases (Zukerman et al., 1996).

I will present here one of the most recent Content Selection algorithms in the literature, developed as part of the ILEX project and compare it to my two level Content Selection approach. In Section 2.1.2, I will summarize the knowledge acquisition process that the researchers in the STOP project pursued to build their Content Selection module. I will also compare that human acquisition with my the automated one described in Chapter 4. Some remarks regarding integrated or separated Content Selection close this section.

2.1.1 ILEX Content Selection Algorithm

One of the most well-regarded integrated Content Selection algorithms proposed in the literature is the one used in the ILEX project (Cox et al., 1999, O’Donnell et al., 2001), a generation system that provides dynamic labels for exhibits in a Web-based museum gallery. ILEX tries to improve current static (fully pre-written) Web pages by means of Dynamic Hypertext (Dale et al., 1998), the marriage of NLG and hypertext systems. In Dynamic Hypertext, a generator will produce not only text that lives in the nodes of a hyper-linked environment, but also the links between these nodes.

In the ILEX Content Selection algorithm, each tuple coming from a relational database is transformed into an object definition where each of the entries in the object must be declared in a predicate definition (Figure 2.1). These definitions contain, among other things, a simplified user model composed of three items: interest (how appealing is this fact to the user, static), importance (contribution of the fact for an overall task, also static) and assimilation (level of acquaintance to the fact, dynamically updated). These numbers are hardwired in the predicate definition.

Their algorithm computes a relevant knowledge pool with an innovative relevancy metric. They follow the same line of work presented by (McKeown, 1985) Content Selection (pages 113–121, “Selection of relevant knowledge”), that is, to take the object being described and the entities directly reachable in the Content Potential, a graph with objects as nodes. ILEX also collects all entities relevant to the entity being described, with an innovative spreading-activation relevancy metric. In this metric, the relevancy of an object is given by the mathematical combination of the static importance of the object and the relevancy of the object in the path to the object being described. Their relevance calculation allows them to prioritize the top n most salient items, while maintaining coherence. Different links preserve relevance in different ways. ILEX authors assigned for each class of links hand-picked relevancy multipliers.

The ILEX Content Selection algorithm is complementary to my approach. For instance, my algorithm could be used to provide ILEX interest scores, an appealing topic for further work.

2.1.2 STOP Content Selection Knowledge Acquisition

(Reiter et al., 1997)’s work addresses the rarely studied problem of knowledge acquisition for Content Selection in generation. Knowledge acquisition is used for STOP, a NLG system that generates letters encouraging people to stop smoking. STOP’s input is a questionnaire, filled out by a smoker; STOP uses the questionnaire to produce a personalized letter encouraging the smoker to quit. Reiter et al. explored four different knowledge acquisition techniques: directly asking experts for knowledge, creating and analyzing a corpus, structured group discussions and think aloud sessions. I detail each of them below.

The first technique they employed was to directly inquire domain experts for Content Selection knowledge, given that STOP was a multidisciplinary project with motivated experts within reach of the NLG team. This technique proved unsuccessful, as experts would usually provide “textbook style” responses (academic knowledge). Such knowledge differs very much from their actual knowledge as practitioners.

Their next effort focused on creating a small Text-Knowledge corpora (what they call a conventional corpus). They collected 11 questionnaire-letter pairs, with letters written by five different experts. Problems arised when comparing letters written by different doctors; the difference in style, length and content make this corpus very difficult to use.

Their final two methods were borrowed from the Knowledge Engineering literature (Buchanan and Wilkins, 1993) and proved to be very useful (structured group discussions and think-aloud sessions).

This research is relevant to my Content Selection work (presented in Chapter 4) where I propose automated mining of Content Selection rules from a Text-Knowledge corpus similar to the one Reiter et al. collected. Interestingly enough, they found the corpus approach insufficient. I find these possible explanations to their problem:

Size of the corpus.

Text production has many variables, the natural variability among normally occurring text will make 11 pairs very likely to diverge noticeably just by chance.

Lack of a well defined task.

It is possible that, in an effort to avoid biasing the corpus collection effort, the experts were given little or no instructions about the letter cessation writing task. High variability in collected data is usually a signal of this type of problem.

Lack of expertise in the task.

The experts in their work were medical experts, but not necessarily smoke cessation letters experts.

Excessive number of experts.

As 11 pairs is too small to come up with a model for a single expert, using more experts rendered the whole task unsurmountable (as they concluded).

These problems are not present in my biographies work (neither in a number of domains that I have identified as suitable for application of my technique), where I have found hundreds of biography-knowledge pairs, written by professional biographers that have to adhere to a writing style.

2.1.3 Separated vs. Integrated Content Selection

While most classical approaches (Moore and Swartout, 1991, Moore and Paris, 1993) tend to perform the Content Selection task integrated with the Document Structuring, there seems to exist some momentum in the literature for a two-level Content Selection process (Lester and Porter, 1997, Sripada et al., 2001, Bontcheva and Wilks, 2001). For instance, (Lester and Porter, 1997) distinguish two levels of content determination: local content determination is the “selection of relatively small knowledge structures, each of which will be used to generate one or two sentences,” while global content determination is “the process of deciding which of these structures to include in an explanation.” Global content determination makes use of the concept of viewpoints, introduced by (Acker and Porter, 1994), which allow the generation process to be somewhat detached from the knowledge base (KB). My Content Selection rules, then, can be thought of as picking the global Content Selection items.

In the same vein, (Bontcheva and Wilks, 2001) use a Content Selection algorithm that operates at early stages of the generation process, allowing for further refinement down the pipeline. They present it as an example of techniques to overcome the identified problems in pipelined architectures for generation (they call this a recursive pipeline architecture, similar to (Reiter, 2000)).

Most recently, the interest in automatic, bottom-up content planners has put forth a simplified view where the information is entirely selected before the document structuring process begins (Marcu, 1997, Karamanis and Manurung, 2002, Dimitromanolaki and Androutsopoulos, 2003). While this approach is less flexible, it has important ramifications for machine learning, as the resulting algorithm can be made simpler and more amenable to learning. Nevertheless, two-level Content Selection can provide a broad restriction of the information to consider, with more fine grained, hand-built algorithms applied later on to select information in context or with length restrictions.

My work is in the schema tradition, with a two level Content Selection. The first, global level is performed with Content Selection rules and the second level is within the Document Structuring schema.

2.2 Document Structuring

I will now address some generalities to the Document Structuring problem; namely, its output and overall algorithms employed, before introducing schemata and RST-based planners, the two most widely deployed solutions.

The output of the Document Structuring is a document plan, normally a tree or a sequence of messages. The relations between these messages usually are rhetorical in nature and employed later on to divide the discourse into textual units, such as paragraphs or bulleted lists (Bouayad-Agha et al., 2000) and sentences (Shaw, 2001, Cheng and Mellish, 2000). Most systems use trees as document plans; the RAGS consensus architecture (Cahill et al., 2000) defines the Rhetoric representation level as a tree. Sequences, on the other hand, are more restricted than trees, but for several applications present enough expressive power. Examples include the works of (Huang, 1994) and (Mellish et al., 1998). Sequences are important for my work as schemata, as defined originally by (McKeown, 1985), use sequences as document plans (when employed without schemata recursion). Moreover, even if trees have more momentum as document plans in the literature, several incompatibility results (Marcu et al., 2000, Bouayad-Agha et al., 2000), may suggest otherwise. The use of trees seem forced in some cases, for example (Mann and Thompson, 1988) claim that the rhetorical structure ought to be a tree in most of the texts. However, their Joint rhetorical relation seems to be just an ad hoc procedure to keep a tree from becoming a forest (Rambow, 1999). Finally, (Danlos et al., 2001) analyze cases where trees are not expressive enough. Their solution is to employ equational systems (actually directed acyclic graphs or DAGs) that increase expressivity by reusing rhetorical nodes.

The algorithm normally involves a search on the space of possible document plans. That is the case of Schemata-based, RST-based or opportunistic planners, which I discuss later in this section. However, several Document Structuring problems in the literature have been solved with no search, as in a good number of cases, planning is just a label for a stage solved by other means, as pointed out by (Rambow, 1999). Complex planning process examples include (Huang, 1994), working on automatic verbalization of the output of theorem provers and (Ansari and Hirst, 1998), working on generating instructional texts. In general, full planning is the most comprehensive solution to the document structuring problem, although it is expensive and requires modeling complex issues such as the intentional status of both hearer and speaker, and the full consequences of all actions that may not be necessary (or even feasible) in all domains of interest to NLG practitioners.

Another question being asked by previous research is the direction of the building of the plan. Normally, speed and ease of understanding motivates building top-down planners, e.g., (Young and Moore, 1994), which uses the Longbow AI planner (Young, 1996). However, other authors, for example (Marcu, 1997), see the whole planning process as a linking among facts by means of input-given RST-relations, an approach that is indeed bottom-up (I discuss opportunistic planners in Section 2.2.2). A hybrid approach is taken by (Huang, 1994), which combines a top-down (planned) approach with a bottom-up opportunistic perspective based on centering.

Several other approaches have been investigated. Besides the approaches I discuss later in this section, (Power, 2000) poses the problem as a constraint satisfaction and uses CSP techniques (Jaffar and Lassez, 1986) to solve it. (Knott et al., 1997) make a stand for the use of defeasible rules as a tool for planning coherent and concise texts. (Wolz, 1990) models the problems by having different AI-plans compete with each other to come out with a final decision (another mechanism for doing CSP). In my work, I learned schemata from data (a bottom-up approach), where the schemata are a type of planner that involves a local search during instantiation (top-down skeleton planners, as discussed by (Lim, 1992)).

Traditionally, Strategic Generation problems have been addressed in NLG by means of two techniques: AI planners and Schemata. Reasoning can derive the text structure in some cases. In a scenario (Figure 2.2) borrowed from the work of (Rambow, 1999), a reasoning process ¹ can derive the text shown in the figure, using, for example, operators derived from rhetorical relations (Section 2.2.2). Reasoning-based Strategic Generation focuses on domains where the structure can be fully deduced from the input data and the intentions of the speaker.

Not all text can be fully deduced from the input; some text has fixed structure coming from the domain. Even though I consider AI-style content planning a useful and interesting approach, many cases require special domain knowledge. For instance, if I know that an actor won three Oscars, was married twice and is 58 years old, common knowledge about biographies would dictate starting a biography with the age and occupation, leaving the rest of the information for later. Nothing intrinsic to age or awards specifies this ordering (it is not part of the domain knowledge itself). The text structure in formulaic domains presents very little intentional structure and is historically motivated; while its current form has logically evolved over time, there is no rationale behind it that can be used for planning. What is needed in such domains is domain knowledge related to its communicative aspects: Domain Communication Knowledge (DCK). DCK has been defined by (Kittredge et al., 1991) as:

This knowledge can be explicitly or implicitly represented in a strategic component, depending on the judgement of the authors and on its importance for the scenario at hand. In most cases it is left implicitly represented. A notable exception is the work of (Huang, 1994), which defines the notion of proof communicative act (PCAs).

I know my interlocutor will believe in Sam’s word. I know Sam saw John without shaving. I want to convince my interlocutor that John overslept. I know my interlocutor will not believe me directly. I know my interlocutor knows that a man doesn’t shave when he oversleeps.

Figure 2.2: Example scenario and rhetorical tree.

What is happening behind the scenes is that three different structures can be mapped to the discourse: informative, intentional and focus. In certain domains, one structure dominates the production of texts and a formalism based on only one of them can be enough to structure the text. (Rambow, 1999) proposes an integrated approach to deal with DCK and other issues.

With respect to intention, (Moore and Paris, 1993) (also (Hovy, 1988)) present a discussion of how to represent the beliefs of the Hearer and the intentions of the Speaker in instructional dialogs. Also, the degree of belief may be important to model as in the works of (Zukerman et al., 1996), (Walker and Rambow, 1994) and (Rambow, 1999). However, other approaches, e.g., (Moore and Paris, 1993) and (Young and Moore, 1994), prefer to consider belief as a binary (believe or disbelieve) datum. In my work, I do not represent nor use intentional structure, beyond the Report(Fact) type of intention, as part of simplifying assumptions to make Strategic Generation amenable for learning. An interesting area for future work is to incorporate intentional data coming from text by using current research in opinion identification (Zhou et al., 2003, Yu and Hatzivassiloglou, 2003). The matched text can be enriched with opinion and opinion polarity labels by an automatic opinion/polarity tagger. My system can then use this extra information to theorize Content Selection rules that take into account the agent’s stance toward certain facts (that information will need to be modelled outside of the learning system, using traditional cognitive modelling).

I will turn now to schemata-based document structuring.

2.2.1 Schemata-based Document Structuring

In this section, I present McKeown’s original schemata, then discuss KNIGHT, MAGIC and other schema-like systems. McKeown’s schemata are grammars with terminals in a language of rhetorical predicates, discussed below. The four schemata identified by McKeown in her work are the attributive, (Figure 2.3) identification, constituency, and compare and contrast schemata. The schemata accept recursion, as some entries inside the schema definition can be fulfilled directly with predicates or by other schemata. They are not fully recursive as only four schemata are proposed and there are 23 predicates, although McKeown expressed her belief that the formalism can be possibly extended to full recursion.

Her predicates are important for my work as they contain a major operational part, the search for associated knowledge. When the schema reaches a rhetorical predicate such as attribute, it fills it with required arguments, e.g., the entity the attribute belongs to. From there, the rhetorical predicate (actually a piece of Lisp code) will perform a search on the relevant knowledge pool for all possible attributes to the given entity. These instantiated predicates (messages in this dissertation) will be available for the schema-instantiation mechanism to choose (by virtue of her focus mechanism, explained below) and then build the document plan.

Schemata are then structure and predicates. My work focuses in learning the structure but not the predicates (I basically learn only part of the schemata, in a sense). Which predicates to use and how to define them is an important part of the schema that I thus assume to be part of the input to my learning system. This is a point of divergence with McKeown’s schemata that used predicates rhetorical in nature. My predicates are domain dependent, what makes creating these predicates a process worth automating. As a step in that direction, I have been able to provide a declarative version of these predicates in a constraint satisfaction formalism (discussed in Chapter 5, Section 5.1).

To implement the schemata, McKeown employed Augmented Transition Networks (ATNs) an extensible declarative formalism where some of her requirements used these extensions. In her system, the rhetorical predicates are executed when traversing different arcs. Both the actions in the arcs and the conditions are arbitrary pieces of Lisp code. An example ATN (Figure 2.4) shows a fair degree of possibilities at each node (seen by the number of arcs leaving each state). One contribution from McKeown’s work is to use focus to guide the local decision of which arc to traverse at each moment. I will discuss her focus mechanism now.

Focus

(McKeown, 1985) contains a full chapter (“Focusing in Discourse,” pages 55–81) describing the importance of centering theory and proposing a motivated solution for discourse planning. She built on the works of both Grosz (global focus) and Sidner (local focus) to extend their interpretation theories with decision heuristics for generation. McKeown’s work on focus is a major ingredient of her schemata and has been adapted for use in other generation systems (e.g., (Paris, 1987)’s TAILOR generator). However, few schema-like planners mentioned in the literature include this piece of the schema. I find that a major oversight of later followers of McKeown’s work.

As pointed out by (Kibble and Power, 1999), research on focus in understanding is interested in discourse comprehension, mostly solving cases of anaphora, e.g., pronominalization. Most centering theories, therefore, provide tools to cut down the candidate search space for anaphora resolution. Nevertheless, the generation case is different, as these theories lack insights of how to choose among the set of candidates. Understanding does not require these decisions, as they have been taken by the human author in the text already. McKeown complemented centering theories with heuristics suitable for generation. For recent work on centering, (Karamanis, 2003) presents a learning approach to the problem.

McKeown presents heuristics for two decision problems involving focus. In the first problem, the system has to decide between continuing speaking about the current focus or switching to an entity in the previous potential focus list. Her heuristic in that case is to switch, otherwise the speaker will have to reintroduce the element of the potential focus list at a later point. The next decision arises when deciding whether to continue talking about the current focus or switching back to an item in the focus stack. Here her heuristic was to stick to the current focus, to avoid false implication of a finished topic.

This is, grosso modo, McKeown’s treatment of focus. The details are more complex but I will skip them as I use McKeown’s focus mechanism without any modifications. Her focus mechanism is important because my machine learning mechanism interacts with it and has to learn schemata in spite of the actual focus system.

Figure 2.4: McKeown’s Attributive Schema (ATN).

KNIGHT Explanation Design Packages

(Lester and Porter, 1997) were interested in robust explanation systems for complex phenomena. When designing their Document Structuring module, they focused on two issues, expressiveness (the Document Structuring module should be able to perform its duties), and Discourse-Knowledge Engineering (DCK requires expertise to be acquired and represented, see Section 2.2, they were particularly interested in providing tools to support this vision). This last issue arise after working in an non-declarative Explanation Planning module for a period of time. As the module grew larger, adding new functionality or understanding existing ones became an issue as the actual logic was buried under lines and lines of Lisp code.

To solve this problem, Lester and Porter took the most declarative pieces of their approach and moved it to the knowledge representation system, creating the Explanation Design Packages (EDP). EDPs are trees represented as frames in a knowledge representation. The frames encapsulate a good deal of Lisp code, defining local variables, conditions over local and global variables, invoking KB accessors and arbitrary functions. They are as rich as a programming language.

When compared to schemata, it seems that Lester and Porter arrive at a similar solution coming from the opposite direction. McKeown analyzed a number of texts and background work in rhetorical predicates to hypothesize her schemata as a suitable representation of discourse that she later operationalized using ATNs. As ATNs are of a hybrid declarative/procedural nature, extensions can be coded in by means of extra Lisp code. Her schemata required using some of these extensions. McKeown, therefore, arrived at a hybrid declarative/procedural implementation starting from a fully declarative problem. Lester and Porter, on the other hand, started with a fully procedural implementation and further structured and simplified it until they arrived to their hybrid declarative/procedural EDPs.

True to their roots, EDPs have a more procedural flavor, but that does not avoid making a direct comparison with schemata. The frames in EDP correlate roughly to schemata’s states. Note, however, that there are no cycles on the EDPs (as they are trees). The loops in the schemata are represented in EDP by an iteration mechanism. More interestingly, the KB accessor functions behave operationally exactly the same as McKeown’s predicates. The major difference (and this may be the reason why Lester and Porter did not draw this parallelism) is that McKeown stressed the rhetorical nature of her predicates. KNIGHT predicates are not rhetorical, but domain dependent; this is an approach I follow in my work as well. Finally, both approaches allow plugging a sizeable amount of extra Lisp code into their formalisms. EDPs provide more places to do so, while the ATNs concentrated this in the arc transitions.

A key distinction is that, while schemata are skeleton-planners because they contain the skeleton of a plan but they perform a local search (driven by McKeown’s focus mechanism) to arrive to the final plan (Lim, 1992), EDPs lack any type of search. Lester and Porter did not mention this fact on their work and it is clear they did not need such a mechanism for their robust generation approach.

EDPs expand schemata by providing a hierarchical organization of the text that is suitable for multi-paragraph texts. Moreover, they include a prioritization model that makes for a bare-bones user model (but does not compare to either the TAILOR (Paris, 1987) or ILEX (O’Donnell et al., 2001) treatment of the issue) and a number of well-defined non-rhetorical predicates for natural entities and processes. However, Lester and Porter followed a more procedural extension of the schemata, which makes them unsuitable for my learning approach.

Other Schema-like Planners

MAGIC. MAGIC took the topic tree approach of Lester and Porter and simplified it until it became fully declarative, with a high toll on its expressive power. Its schema is a tree with topic internal nodes and predicate-leaves. The internal nodes constitute the text organization and structure the output into two levels of chunking (paragraph chunks that contain aggregation chunks). The predicate-leaves fetch from the knowledge base all the values matching the predicate and insert the resulting messages into the output. This is the only iteration process in the MAGIC planner. By being encapsulated into the leaves, it spares the need of cycles as in TEXT or iterators and local variable definitions as in KNIGHT. The MAGIC planner is so simple that it is surprising that it works. A closer look may reveal MAGIC’s secret: the repetition-at-the-leaves approach produces highly cohesive lists of related facts, realized in the form of enumerations, with the rest of the information shuffled around inside the aggregation chunks by the MAGIC complex aggregation component, one of the foci of the project. Interestingly enough, this representation was very amenable to my learning techniques (Chapter 5). The representation, however, seems only suitable for planning single-topic discourse (all discourse in MAGIC has the same focus —the patient the surgery was about).

Figure 2.5: An example of MAGIC’s schemata-like Document Structuring trees (left, straight edges nodes) and output (right, rounded nodes). The Document Structuring tree is instantiated for the four semantic units (drugend-1, drugend-2, hypotension-1, name-1, surgerylen-1). The resulting document plan has four leafs, five internal nodes and eight edges (shown in bold).

Other schemata implementations. Plenty of other people used schemata, including the work in the TAILOR generator (Paris, 1987) that expands schemata with user model and trace-explanation systems, the work done by (Maybury, 1988) that attempts to add more rhetorical predicates, the work in the KOMET project (Bateman and Teich, 1995) that expands schemata for text and graphics, and the work in the Peba-II system, that applies schemata to dynamic multimedia and comparisons (Milosavljevic, 1999). I detail my own declarative implementation of schemata in Chapter 5.

2.2.2 RST-based planning

Continuing with the idea already present in McKeown’s work of consolidating and improving rhetorical relations defined previously in the literature, (Mann and Thompson, 1988) studied a number of texts in different genres and styles and formulated their Rhetorical Structure Theory (RST). RST states that every text has a unique rhetorical structure based on text spans where rhetorical relations hold. They add to the rhetorical treatment of McKeown two key ingredients: hierarchy and asymmetry. Now a text span can be subdivided into sub-relations and a super relation can hold over it. Schema recursion is supposed to capture this fact but McKeown did not investigate schema recursion much herself. Hierarchy is not the only key ingredient added to the picture by Mann and Thompson, as they also realize that a number (almost all) of the rhetorical relations they identified in texts were asymmetrical, in the sense that they contained two text spans, one of which (the nucleus) was central to the discussion and could not be removed, while the second span (the satellite) expands or complements the nucleus.

From their analysis, they propose 23 rhetorical relations, divided into two categories, presentational and informational. The distinction is made depending on whether they hold in the text by virtue of the text flow (presentational) or by virtue of the underlining truth of the given facts (informational). For example, a relation such as Justify will only hold depending on what has been said before and what we want to say now (that is, it depends on the information selected and how it is placed on the text, in the intention of the speaker), while a relation such as Volitional Cause holds statically between two facts in the knowledge base.

RST is a theory designed to capture the structure of texts in general, without particular ties to understanding or generation. Relative early success in understanding (Marcu, 2000) has run into problems defining a set of rhetorical relations (Marcu and Echihabi, 2002). Nowadays, the existence of rhetorical relations that hold between spans of text is an agreed fact and research focuses on the sizes of those spans and the number and nature of the relations. Regarding the size of the spans, (Mann and Thompson, 1988) work at the clause level but other researchers such as (Stent, 2000) use variable sizes from words to sentences. Regarding the number of the relations, (Knott and Dale, 1993) provide a bottom-up perspective on the number of relations issue, postulating that despite the actual relations taxonomy, it should in some way be reflected by the existence of related cue phrases. (Marcu and Echihabi, 2002) put this idea into practice, in their study using a very large corpus. Other approaches postulate a large number of relations, which (Hovy and Maier, 1995) organized in a taxonomy. Finally, there is the issue of whether or not the number of rhetorical relations is bounded. On the one hand, (Rambow, 1999) and (Knott and Dale, 1993) argue in favor of bounding their number as otherwise the theory will become unsound. On the other hand, (Mann and Thompson, 1988) and (Hovy and Maier, 1995) sacrifice soundness on behalf of a further reaching theory (on pragmatic grounds).

From the generation perspective, (Hovy, 1988) was the first to apply it for building a strategic component (Hovy, 1993). His approach involved reversing the direction of the RST relations defined by Mann and Thompson (so its observed effect is used as a precondition and its applicability constraints as post-conditions) and using them as operators in a planning process. While this approach enjoyed limited success, it has a number of drawbacks. Some problems between this planning approach and intentional structure have been discussed at length by (Moore and Pollack, 1992) (e.g., how intentional structure will be lost if only rhetorical structure is kept as the output of the planner, complicating follow-up reasoning over the generated text), but more relevant to my dissertation are the operational issues involved in a RST-based planner. Building a RST-based planner requires modelling carefully the intentions of both the speaker and the hearer (cognitive modelling), a problem in purely informative domains, where the only intentional structure that can be associated with the text is the simple Report(Facts). Moreover, purely informative domains are prime candidates for using NLG techniques and therefore of practical importance. As pointed out by (Lim, 1992), a RST-planner requires additional guidance to be able to plan reasonable text in reasonable amounts of time. In that direction, my work can be adapted to acquire this domain-based information from a Text-Knowledge corpus.

Opportunistic Planning

Another avenue to incorporate rhetorical relations when planning purely informative texts is to rely solely on informative relations, precalculated on the semantic input (considered, therefore as an integrated part of the knowledge representation) and then search for a text that is able to incorporate as many of the rhetorical relations as possible (Marcu, 1997), together with other text structuring operators (Mellish et al., 1998) and most importantly, focus-based constraints (Karamanis and Manurung, 2002). That approach renders the document structuring an optimization process, a search for the text structure that maximizes an evaluation (objective) function. Interestingly enough, the techniques employed to solve this problem involve also genetic algorithms (in particular, Genetic Search (Michalewicz, 1992)). I also use genetic algorithms in my work. While (Mellish et al., 1998)’s intention was to push stochastic search as a feasible method for implementing a document structurer, I pursue the automatic construction of the schema itself. My system, moreover, uses a corpus-based fitness function, while they use a rhetorically-motivated heuristic function with hand-tuned parameters.

Considering rhetorical relations as part of the input has the advantage of avoiding an explicit representation of the intentional state of the Hearer. In such settings, a trivial cognitive model, where every fact uttered by the speaker will be immediately assimilated and believed by the hearer, can be employed. While opportunistic planners succeed in incorporating rhetorical relations in their outputs, they seem to be limited to problems lacking any real use of the communicative power of the rhetorical structure. In contrast, most content planners, (Young and Moore, 1994) and architectures (Cahill et al., 2000) find the relations while structuring the document. By doing so, they can find relations that hold as a result of the structure (presentational relations). In my case, the input is the relevant knowledge pool, a subset of the KB in the frame-based Knowledge Representation described in Chapter 1, Section 1.1.1 and it contains no rhetorical information.

2.3 Related Work in Learning in NLG

In recent years, there has been a surge of interest in empirical methods applied to natural language generation (Columbia, 2001). One of the first applications of machine learning to NLG systems is a hybrid architecture trained on target text (example outputs) introduced by (Knight and Hatzivassiloglou, 1995). In this architecture, a first component over-generates a large number of possible solutions, and a second component chooses among them. The first component is quite simple and the second component is the one based on machine learning. For example, a symbolic engine may generate his success as an actress and her success as an actress but the probabilities in a corpus of related texts will choose the second (correct) output. My system is an example of an alternative architecture that is trained in input/output pairs, in the form of a Text and Knowledge corpus (besides the fact that my system works in learning for the Strategic Generation component and not the syntactic/realization component).

Text-Knowledge corpora, a traditional resource for knowledge acquisition in Natural Language Generation, are recently gaining momentum as a resource for Statistical NLG (Barzilay and Lee, 2002, Duboue and McKeown, 2002, Sripada et al., 2003, Barzilay et al., 2003). They have been employed for learning elements at the strategic level (Duboue and McKeown, 2002, Duboue and McKeown, 2003a), for lexical choice (Barzilay and Lee, 2002, Sripada et al., 2003) and at other levels (Barzilay et al., 2003, Ratnaparkhi, 2000).

(Dimitromanolaki and Androutsopoulos, 2003) worked also in machine learning applied to Document Structuring. Their training material consisted of sequences of atomic values, an ideal training set, as each atomic value was actually a message and thus the input of the document structurer was compatible with its output. In my case, in contrast, the input are facts and the output are messages assembled over those facts. Because each of these sequences was rather short (about six messages long), the following approach proved fruitful: they trained a cascade of classifiers to decide the exact (absolute) position that each pre-selected fact has to take in the output. It is unclear whether their approach will apply to other (more complex) settings. Absolute and relative positioning are quite similar in sequences of six elements, but in longer sequences, telling between the two allows for a better utilization of the training material. My mining of order constraints described in Chapter 5 is an example of relative orderings.

(Shaw and Hatzivassiloglou, 1999) work on the probabilistic ordering of pre-modifiers in complex NPs (e.g., “a 35-year-old asthmatic male patient of Dr. Smith”), a task also addressed by a number of authors (Cheng et al., 2001, Malouf, 2000, Poesio et al., 1999). Because this type of ordering information is domain dependent, they designed an algorithm to acquire order constraints from a corpus. This algorithm is important for this thesis, as I have employed an adaptation of it for my Document Structuring work described in Chapter 5. Their algorithm starts by collecting a table of observed ordering behaviors. In this table, the entry at position i,j indicates the number of times in the corpus the object i came before the object j. From the table, they try to reject the null hypothesis that i,j came in any order (equivalent to saying that the probability of i coming before j is 0.5). The following formula will compute the probability of the observed frequencies:

where m is the total number of times i has been seen occurring before j in the corpus and n is total number of times i and j occur in a pair. That equation can be used with a threshold to select “likely enough” constraints or can be piped into more complex, smoothing techniques described at length by (Shaw, 2001).

Nitrogen (Langkilde and Knight, 1998) is the generation component in a Japanese-English machine translation system. They employ a language model like those used in speech recognition (an n-gram model, in this case a bigram model) and a symbolic module that uses a grammar to transform the input representation into an intermediate representation (a word lattice) that is scored by the language model. The word lattice has several drawbacks (Langkilde and Knight, 1998). Langkilde (Langkilde, 2000) moves away from the word lattice by replacing it with a packed forest on the same underlying model.

Varges and Mellish (Varges and Mellish, 2001, Varges, 2003) employ instance-based learning to build IGEN, a surface realizer with limited sentence planning capabilities, trained on input/output pairs. An interesting difference from Nitrogen is that the symbolic generator uses a semantic grammar extracted from training data (in an approach similar to Fergus (Bangalore and Rambow, 2000)). The sentence is chosen as a function of the sum of the cosine similarity to a set of instances, and the ratio of input semantic elements covered in the output sentence, a memory-based approach (a technique already employed in surface realization by (Neumann, 1997), in concept-to-speech by (McKeown and Pan, 1999) and recently in sentence planning by (Pan and Shaw, 2004)). Interestingly, his training material is very close to my matched texts, although Varges created them by hand.

A system completely trained on input/output pairs is Amalgam, a trainable generation module for Machine Translation, developed at Microsoft Research (Corston-Oliver et al., 2002).

At higher levels in the generation pipeline, SPoT (Walker et al., 2002), a trainable sentence planner, uses a ranking process for the filtering. The ranking methodology is based on experiments that showed that it was easier to train the system based on human preferences than clear cut selection. Candidate sentence plans for a sequence of communicative goals are generated randomly. Then, the chooser component determines which of the candidates is most suitable. This chooser component has been trained by having human subjects rank candidates during the training phase; boosting is used to learn discriminative re-ranking rules. This system is trained on ranked outputs.

(Barzilay and Lee, 2002) work on the problem of inducing a generation lexicon. Such a lexicon provides words for parametric predicates, in the form of templates where the parameters from the predicate can be plugged in. As input they use data to be verbalized and a variety of human-written verbalizations for such data. This is a multi-aligned Text-Knowledge corpus.

All these systems receive symbolic representations as input, mixing seamlessly with my learned schemata (that contains symbolic representations in the predicates).

2.4 Related Work in Other Areas

I will discuss work in the related areas of summarization and dialog systems.

2.4.1 Related Work in Dialog Systems

(Oh and Rudnicky, 2000) work on NLG for dialog systems. In such systems “NLG and TTS synthesis are the only component that users will experience directly. But with limited development resources, NLG has traditionally been overlooked by spoken dialog system developers.” They presented an n-gram based system that operates at different levels of the NLG pipeline. As their output is very small for the NLG tradition (one or two sentences), their work is an example of the power of n-grams when dealing with short output. While they claim their model to be grounded on (Knight and Hatzivassiloglou, 1995)’s model (the model later popularized by the Nitrogen generator), they have a major divergence from them, as their system is fully statistical and not hybrid. More important to this dissertation, they perform limited Content Selection by defining a task mixing Content Selection and lexical choice and solving it with statistics computed on text (outputs only). Their approach is very valuable but their simplified task only makes sense when the mapping from concepts to words is as direct as in the case of some dialog systems. In my case, the need for a verbalization dictionary makes more clear the need for training in both input and output pairs and therefore the need for inducing such dictionary if it is not available. At any rate, both approaches are comparable. A synergy between them is interesting for further work, if there is interest in applying my technique to dialog systems.

Also working in dialog systems, (Young, 2002) presented a theoretical fully trainable system “built” from published trainable components and models. While he does not address any Strategic Generation issues per se (dialog systems have very simplified generation needs, as discussed before), he arrives at the (Knight and Hatzivassiloglou, 1995) model coming from a fully statistical setting, as a corrective term to linearize concepts verbalized from the understanding probabilities. These coefficients are estimated on target texts (example outputs), following Nitrogen’s example. The only reason I can postulate for him not using input/output pairs to train the linearization component (e.g., as it is done in Amalgam (Corston-Oliver et al., 2002) for surface realization and in this thesis for Strategic Generation), is the fact that he based his model in published works, and at that time there were few or no work done on trainable systems on input/output pairs.

2.4.2 Related Work in Summarization

In summarization, the two subtasks of the strategic component in generation get mapped to the task of selecting which sentence or clauses to include in the output and how to order them. For the task of selecting sentences using machine learning approaches, most of the work on the field can be tracked back to the seminal work of (Kupiec et al., 1995). There, they collected 188 summaries plus the original texts and aligned summary sentences to text (semi-automatic construction of the summarization equivalent of my matched texts). From there, they computed a number of features on the original texts (similar to my computation of structural features on the semantic representation) and used them to predict which sentences were more likely to be included in the output. While they were working in a text-to-text environment, both approaches are compatible. The main difference, besides the novel use of shallow knowledge in my work, is that summarization works with a fixed output size as an argument to the task while in my generation task the output size is unconstrained, but has to mimic exactly the information selected in the target texts (that is, some biographies contain one paragraph, while others contains three paragraphs, just because there are more things worth telling about the latter person; the key is not including irrelevant facts).

After the work of Kupiec and colleagues, effort has concentrated on evaluation (Van Halteren and Teufel, 2003, Nenkova and Passonneau, 2004), feature consolidation (Radev et al., 2002), improving the matching between text summary and text source (Jing and McKeown, 1999, Daumé III and Marcu, 2004) or better theoretical frameworks (Filatova and Hatzivassiloglou, 2004). The overall relation between my Content Selection work and summarization is an issue I am particularly interested in following up in further work.

With respect to sentence ordering, this constitutes very little problem in single document summarization, where the order in which the sentences appear in the document normally constitutes a reasonable and appropriate ordering, although there are some exceptions (Jing and McKeown, 2000). The situation changes when confronted with a number of sentences coming from different documents. (Barzilay et al., 2002) investigated this problem of re-ordering clusters of sentences (which they call themes) for multi-document summarization. They performed a number of experiments with human subjects before proposing a bottom-up algorithm, based on chronological ordering and topical structure. Their first experiment validated the importance of re-ordering and found out that “if reordering is not, in general, helpful, there is only a 7% chance that doing reordering anyway would produce a result that is different in quality from the original ordering.” That speaks of the importance of ordering for the summarization task. They then compared two naïve algorithms, Chronological Ordering, which presents each theme at the earliest of its publication time and Majority Ordering, that presents each theme according to the relative position in the original texts of most sentences (as possible). For the majority ordering, they employed the greedy approximation proposed by (Cohen et al., 1999). Their experiments showed both strategies to be unsatisfactory so they went on to perform experiments at a larger scale to elucidate the impact of ordering according to human judges. In one experiment, they found out that ‘“there are many acceptable orderings given one set of sentences.” This reinforces my using a population of schemata as in my GA-based algorithm in Chapter 5, as opposed to finding the one and only best schemata (as in, for example, hill climbing). On the other hand, from 40,320 possible orderings, 50 subjects produced only 21, speaking of a small number of acceptable solutions.

They collected a corpus of ordering preferences among subjects and used them to estimate a preferred ordering. They found out that there is a certain stability on clusters of objects (a phenomenon that re-inforces my use of pattern detection algorithms to preprocess the sequences) and modeled that stability with a coherence constraint that ensures that blocks of sentences on the same topic tend to occur together. This technique results in a bottom-up approach for ordering that opportunistically groups sentences together based on content features. In contrast, my work attempts to automatically learn schemata for generation based on semantic types of the input clause, resulting in a top-down planner for selecting and ordering content. While the learning approach is also bottom-up, the schemata learned are top-down, resulting in efficient execution times.

(Kan and McKeown, 2002) presented work on sentence reordering trained in a corpus annotated with semantic predicates. The main contribution was to compare different decay functions for modelling the context in an environment where majority orderings were built by search. My approach differs from Kan in two key aspects: first, I have developed techniques to automatically annotate training material, using a Text-Knowledge corpus. The knowledge is used to replace the human annotation. From these, instead of collecting statistics over the training and using them at runtime to order the facts (what I call the “on-line” approach), I use the corpus (sometimes also collecting statistics) to build a schema that will order the facts at runtime more efficiently (the “off-line” approach). My approach, therefore, has the advantage of using structured knowledge instead of hand labelled data and of providing a more efficient and easier to understand document structurer.

A later approach also employed a Markov assumption for text structuring (Lapata, 2003). Lapata’s system used a number of computable features (including syntactic and lexical features) to collect statistics of which sentence may follow a previous one. Working only with the previous sentence (i.e., using a very short memory in the Markov process), a necessary constraint to obtain meaningful statistics, she obtained very promising results that speak very well of her election of features. My approach, in contrast, tries to obtain a global (top-down) text structurer from a rich training set (the Text-Knowledge corpus). Her system, however, can be trained directly on text and might be more independent of particular domains.

Very recently, (Barzilay and Lee, 2004) proposed and evaluated a method for constructing HMM-based content models from text. Their system constructs topical models of text while also constructing models of the ordering between these topics. Their system has never been applied to NLG tasks, but it will require the full verbalization of the text to do so (as it only orders text and not concepts). In a similar situation, (Reiter, 2000) found such an approach to be very inefficient. Moreover, for their technique to work in NLG, the concepts should be verbalized in a way that is compatible with the training text. For example, if the training text said “X was born on DATE”, their system may find the word “born” as a strong marker of a topic but if the NLG system decides to verbalize this concept as “(DATE)” then the word “born” will not appear there to signal it. Compare this with my approach in Chapter 3 where I induce the verbalization dictionary from a Text-Knowledge corpus. Barzilay and Lee’s algorithm is also a highly efficient method for sentence selection. Theirs is a method to incorporate the position of the sentences in the text to be summarized as a sentence selection criteria. Such an approach can not be applied easily to knowledge selection, as the knowledge to be selected (“summarized”) appears unordered in the knowledge representation. Besides the inherent differences on working with or without a knowledge representation, my technique targets planners that work with smaller spans of text (as small as a single word), allow for cycles and that are very efficient planners and easy to understand by humans. In summary, they present a new solution fully trained in unannotated text with a number of results for summarization. Their approach seems very appealing for NLG and more research in that direction must prove fruitful.

2.4.3 Related Work in Assorted Areas

Requirements on the output of the strategic component. The decisions taken at the planner level may relate issues at levels lower than the actual document plans. Two items worth mentioning in this regard are the location inside the generation pipeline where the connectives (e.g., cue phrases like ‘but’ or ‘however’) should be defined and whether or not the particularities in the realization of given phrases (active/passive, to-inf/gerund) should be synchronized with rhetorical decisions. Dealing with instructional text, (Vander Linden, 1992) provides a very detailed analysis of the issues concerning the election of syntactical forms given a communicative context. The authors identify different factors, including pragmatic, semantic and user-related constraints, that affect this choice. For example, for the Cause relation, the order between nucleus and satellite depends upon whether the consequence is intended or not. (Rambow, 1999) introduces a framework that allows the content planner to synthesize decisions at different levels of abstractions. (Bouayad-Agha et al., 2000) analyze possible incompatibilities between the text structure (i.e., paragraphs and sections) and the rhetorical structure. With respect to sentence planning, (Shaw, 2001) expects the strategic component to provide a document plan segmented into aggregation chunks. Information inside each aggregation chunk can be reshuffled by his aggregation component.

Related Work in Artificial Intelligence. The AI Planning community (Minton, 1993) focuses its learning efforts in acquiring information that allows speeding up the control of the planner, e.g., ordering between the rules to speed up the planner or to arrive greedily to a good local solution. My techniques also provide as output skeleton planners with very efficient runtime. Also within AI, (Muslea, 1997) presents a Genetic Programming (Koza, 1994) based planner. The plans being learned are competitive with the state of the art in AI planning, with impressive running times.

Multimedia/Multilingual/Layout. When planning different type of content, textual and non-textual information can be planned together. There is interest in reusing the results of the planning process across content types, as it impacts the economics of the generation process. In particular, the layout affects the communicative process, and different languages affect the structuring of the message. (Dale et al., 1997) try to approach the building of interactive websites with an NLG dialog perspective, with mixed results. (Kamps et al., 2001) provide a very comprehensive study of the relation between graphical disposition of textual and non-textual elements on the page, and show that it is possible to plan layout and content altogether. (Stent, 2000) adapts RST to model dialogs. (Marcu et al., 2000) show a negative result on the sharing of rhetorical trees between English and Japanese. Other multilingual generation papers include the work of (Rösner and Stede, 1992). (Bouayad-Agha et al., 2000) show another incompatibility result, now between rhetorical structure and text structure. (André and Rist, 1995) present schema-like coordinated text and graphics system.

With respect to Dynamic Hypertext, (O’Donnell et al., 2001) argue that their problem of prioritization, history awareness, limited output and limited planning made schemata unsuitable for their task. That is true when considering schemata as originally defined by (McKeown, 1983), but certain aspects of their problem would have benefited from a schemata-based planner. They seem to imply that a schema is a completely fixed interaction, while ignoring the focus-based decoding process. Their Content Selection algorithm can be used to provide a relevant knowledge pool and then a schemata could have been written, rich in choices that would have followed through using focus to produce coherent texts.

Related Work in Biography Generation. Part of the research described in this thesis has been done for the automatic construction of the Content Selection and Document Structuring modules of ProGenIE (Duboue et al., 2003), a biography generator. Biography generation has the advantages of being a constrained domain amenable to current generation approaches, while at the same time offering more possibilities than many constrained domains, given the variety of styles that biographies exhibit, as well as the possibility for ultimately generating relatively long biographies. The need for person descriptions has been addressed in the past by IR, summarization and NLG techniques. IR-based systems (Müller and Kutschekmanesch, 1995) look for existing biographies in a large textual database such as the Internet. Summarization techniques (Radev and McKeown, 1997, Schiffman et al., 2001) produce a new biography by integrating pieces of text from various textual sources. Natural language generation systems for biography generation (Teich and Bateman, 1994, Kim et al., 2002) create text from structured information sources. ProGenIE is a novel approach, which builds on the NLG tradition. It combines a generator with an agent-based infrastructure expecting to ultimately mix textual (like existing biographies and news articles) as well as non-textual (like airline passengers lists and bank records) sources. ProGenIE offers significant advantages, as pure knowledge sources are able to be mixed directly with text sources and numeric databases. It diverges from the NLG tradition, as it uses examples from the domain to automatically construct content plans. Such plans guide the generation of biographies on unseen people. Moreover, the output of the system is able to be personalized; and by the fact that the system learns from examples, it is able to be dynamically personalized.

2.5 Conclusions

The Strategic Generation literature is quite vast. It usually deals with the many ways to model the Strategic Generation phenomenon. For the sake of this dissertation, this literature puts forward different representations to capture such phenomenon in NLG systems. This thesis contributes some empirical answers to the question of which representations might or might not been amenable for learning.

The NLG machine learning literature is more recent than its Strategic Generation counterpart, although it starts gaining ground. Nevertheless, Strategic Generation have not received as much attention in NLG learning as the surface generation and sentence planning areas.

Chapter 3
Indirect Supervised Learning

To address the needs of Strategic Generation, I learn sets of rules and schemata. Even though each of these two representations pose different problems and challenges, I learn both from a Text-Knowledge corpus, using similar methods. In this chapter, I introduce the methods common to both learning tasks.

The evidence available as input to my learning system makes for an indirect source, as my Knowledge and Text pairs are different from the ideal training material to learn Content Selection rules or Document Structuring schemata. In both cases, the ideal training material are input and output pairs. In the case of Content Selection, these pairs are pairs of Knowledge and Relevant Knowledge, while in the case of Document Structuring, they are pairs of Relevant Knowledge and document plans. Interestingly, a compound data structure (matched text) can be derived in an unsupervised fashion from the Text-Knowledge corpus to solve this lack of ideal training material. A matched text is a semantically tagged text where each tag is linked to the knowledge representation conveyed by the piece of text under the tag. The ideal training pairs mentioned above can be easily extracted from the matched text. For instance, the Relevant Knowledge can be read out from a matched text as all the knowledge that appears matched somewhere in the text. Similarly, the document plan can be approximated from the placement clues provided by the matched text.

This coupling of an unsupervised technique (construction of the matched text) with a supervised one (learning of Content Selection rules or Document Structuring schemata) is what I call Indirect Supervised Learning (Section 3.2) and is the focus of this chapter. The next two chapters will then present the specifics of the Indirect Supervised Learning process for each task: extraction of the training material from the matched text and supervised learning. While the supervised learning step varies in each case, I conclude this chapter by presenting an unified view of the technique employed to learn both Content Selection rules and Document Structuring schemata. I will now introduce some key definitions.

3.1 Definitions

In this section, I define my knowledge representation, the decomposition of texts into phrases, the matched texts and related notions. These definitions are used in the algorithms presented in the next sections.

Knowledge Representation. I expect the input data to be represented in a frame-based knowledge representation formalism, similar to RDF (Lassila and Swick, 1999). Each frame is a table of attribute-value pairs with a unique NAME and a distinguished TYPE feature (that can be linked to an ontology, if provided). Each attribute is unique, but it is possible to have lists as values. As such, the values can be either atomic or list-based. The atomic values I use in my work are Numeric (either integer or float); Symbolic (or unquoted string); and String (or quoted string).¹ Non-atomic values are lists and frame references. The list-based types are lists of atomic values or frame references. Because my knowledge representation allows for cycles, the actual knowledge representation can be seen as a graph: each frame is a node on the representation and there are edges labelled with the attribute names joining the different nodes. Atomic values are also represented as special nodes, with no departing edges (Figure 3.1).

Figure 3.1: A frame-based knowledge representation example, in the biographies domain. Here, “Daniel” and “Dashiel” belong to the same data-class, namely defined by the data-path relative person name first.

Data-classes. Any equivalence class over the nodes of the graph qualifies as a data-class. Data-classes are similar to semantic tags in other contexts. I will describe now the data-classes I use in my work, but other definitions are possible (for example, path plus frame types across the path), a subject I am interested in pursuing in further work (Chapter 9, Section 9.2).

Data-paths. As domain independent data-classes,² I employed paths in the knowledge representation (data-paths). I need to identify particular pieces of knowledge inside the graph. I thus select a particular frame as the root of the graph (the person whose biography I am generating, in my case —doubly circled in the figure) and consider the paths in the graph as identifiers for the different pieces of data. Each path will identify a class of values, given the fact that some attributes are list-valued (e.g., the relative attribute in the figure). I use the notation to denote these data paths (Figure 3.1 shows an example).

Text. A text is a sequence of words.

Concept. To compute statistics over knowledge representations, I need a means to decompose them into statistical events. A concept is anything that can be asserted to be true or false (false as a negation of true) given a knowledge representation. To avoid data sparseness I employ concepts in the form of a data-path to an atomic node and the value of the atomic node (e.g., ). More complex concepts can include decision logic (e.g., value > 35) and mix several atomic nodes, a subject I started some preliminary investigations (Duboue, 2004). To clarify, based on this definition, and are different concepts. is a data-path (a type of data-class), and not a concept.

Phrase. In the same vein, phrases provide a way to decompose a text into statistical events over which statistics can be computed. In my work, I have used uni-grams as phrases (bi-grams in preliminary investigations (Duboue and McKeown, 2003a)). This decision was also taken to avoid data sparseness. In general, patterns over the text (e.g., “found x out”) would make for ideal phrases.

Verbalization Dictionary. A function that takes a concept as input and returns a set of phrases that can potentially verbalize the given concept.

Matched Text. A matched text (an example is shown in Figure 3.2) is a text where selected phrases are linked to concepts.³ The data-path provide a semantic tag for the piece of matched text.

Figure 3.2: An example of a matched text (excerpt). Here, for example, “American Conservatory Theater” is linked to item number 20 (one of the elements at the end of the data-path ) in the knowledge representation.

3.2 Indirect Supervised Learning

My work can be termed Indirect Supervised Learning⁴ because my training material is fully supervised but the input/output pairs do not have the information needed for direct learning. I thus have input (the knowledge representation), output (text) and a hidden class (the document plans). I want to learn the mapping from input to the hidden class (how to build document plans from a knowledge source, the task of the strategic component in a NLG system) and I have a model of the mapping from the hidden class to the output (from document plans to texts, the remainder of the NLG system). The key is that I want to learn the estimator for the hidden class together with the estimator for the text to the hidden class. While I could have a classifier that assigns sets of observed outputs to values of the hidden class, I am actually trying to approximate this classifier from some independence assumptions.⁵

My current model assumes that the hidden class (the document plan) is the only element needed to determine the wording in the text (an independence assumption). I thus consider the text to be randomly sampled from all the texts that verbalize the document plan (Figure 3.3). Therefore, Indirect Supervised Learning has two steps; in the first step, the indirect training material (natural dataset) is transformed into direct training material (the hidden class is elucidated). In the second step, output learning representations are learned in a supervised way, from the training dataset constructed in the previous step.

A different alternative I explore in Chapter 6 is to compute the output of the hidden class, that is, to produce text from the document plans and then use text-to-text metrics for learning. However, as I am not learning the transformation from document plans to final text, the verbalization becomes a deterministic step where no parameters are estimated, and will therefore be a source of constant noise.⁶

Figure 3.3: Learning Architecture. The full circles represent observed data (text and knowledge in my case). The grayed circles represent hidden variables (relevant knowledge and document plans in my case).

3.2.1 Evaluation

The evaluation process I follow for my Indirect Supervised Learning task is also a contribution of this thesis, as it lets me evaluate both the supervised and unsupervised steps at the same time. Given the training material, I divide it into train (Tr) and test (Te) sets. I then proceed to hand-annotate the test set (Te).

To evaluate the unsupervised part, I join Tr +Te (again, only to evaluate the unsupervised part) and induce annotations automatically (by virtue of the unsupervised nature of the process) over the whole Tr+Te set. Now, I bring back the human annotations over Te and use them to evaluate the quality of the automatically assigned annotations. This measures the quality of the training material for the supervised part.

To evaluate the supervised system, I execute the unsupervised system again, but now only over Tr alone. I then use the annotations automatically obtained over Tr to train the supervised system and execute it over Te (that was not available during training at any point) and compare it to the quality of the human annotations over Te. This measures the generalization power of the technique.

I evaluate the matched texts extrinsically for Content Selection and Document Structuring. The extrinsic evaluation (how good are the matched texts with respect to selection and ordering) is motivated by the fact that I do not have a gold standard matched text constructed by hand; instead, I have annotated the selection labels on the text set and ordered them by first mention on the text.

As a Content Selection metric, I use precision (P ), recall (R) and F^* measure, from information retrieval (van Rijsbergen, 1979). They are defined as:

Where true positives is the number of atoms present in both the hand-tagged test set and the automatically constructed matched texts. The number of items wrongly included becomes the number of false positives. Finally, the items that should have been included but were missed are the number of false negatives.

To evaluate statistical significance of the results, I followed (Mitchell, 1997), pages 146-147, and divide Tr and Te into three non-overlapping folds. In each fold, I executed different variants of the system and then compare their differences in error rate on each fold. This constitutes a case of a paired experiment (every system is trained and tested in the same data). Because each of the sets is non-overlapping, this setting makes for more reliable statistics. For each fold, the error rate E defined as

is computed. Then the error differences δ_i in each fold are computed. Therefore, given three folds (Tr₁,Te₁), (Tr₂,Te₂), (Tr₃,Te₃) and two system variants _A, _B, each variant is trained in (Tr₁ +Te₁), (Tr₂ +Te₂), (Tr₃ +Te₃) and tested in Te₁,Te₂,Te₃. Then defining:

The true difference in the two variants lies in the interval

Where δ is the mean of the differences and S_δ is an estimator for the standard deviation of the differences. The t_2,N are the t-values for two degrees of freedom and they depend on the confidence interval (N%). They are given by the following table:

As a Document Structuring metric, I employ Kendall’s τ correlation coefficient (Lebanon and Lafferty, 2002) between the elements common to the hand-tagged test set and the automatically obtained training material:

Where N is the number of atomic values in the intersection and inversions is the number of exchanges on consecutive objects required to put them in the order appearing in the hand tagged reference. This metric ranges over the interval [-1.0,1.0] with a value of 1.0 meaning perfect correlation, 0.0 no correlation and -1.0 inverse correlation. As explained in Chapter 5, this is an accepted metric for ordering in text structure (Lapata, 2003).

3.3 Unsupervised Construction of Matched Texts

In this section, I detail how general training material, in the form of Text and Knowledge is transformed into a matched text, a training material that can be used for both the task of learning Content Selection rules and Document Structuring schemata.

3.3.1 Dictionary Induction

Indirect supervised learning involves an unsupervised step, based on assumptions on the structure of the model, to elucidate the hidden variable and supervised steps to generalize from the constructed mapping. My assumptions are related to the ways knowledge can appear on the text. This model is summarized by the following two tests, where H₀ is the null hypothesis, p and c are particular phrases and concepts, is the set of phrases that make a particular text, is the set of concepts that make a particular knowledge representation (where and refer to the same entity) and is the verbalization dictionary:

The null hypothesis H₀ (an independence equation) can be paraphrased as saying that if a phrase p does not belong to the verbalization dictionary for a given concept c, then, for a given text (decomposed into a set of phrases ), knowing that the concept belongs to the knowledge representation associated with that text⁷ does not affect the chances of the phrase p appearing in the text. On the contrary, H₁ says that the chances are much greater if the phrase p does belong to the verbalization dictionary of c. This model is inspired by the work of (Dunning, 1993). It is clear that, given a verbalization dictionary , the matched text construction reduces to a disambiguation task. My experiments, however, use H₀ and H₁ in an attempt to elucidate the while constructing the matched texts.

In a sense, I am using the existence of a concept in a particular knowledge representation as a way to partition the set of all knowledge representations. For example, I can use the concept of being a comedian to put together all the data of comedians vs. non-comedians. I then want to see if I can observe changes on the distribution of phrases over the texts associated with the partitions. This statistical test selects words that are then added to the verbalization dictionary (Figure 3.4). I will now analyze each of the components of the system (Concept Enumeration and Statistical Filtering).⁸

Figure 3.4: Dictionary induction.

Concept Enumeration

The dictionary induction starts by enumerating all possible concepts that can be asserted over a set of knowledge representations. This process starts by enumerating all paths in a composite graph (e.g., ) and then checking the possible values that can be found at the end of each path for each of the input knowledge representations (e.g., for Winona Ryder, for Pablo Duboue and so on). Concepts found this way make for a large total number (the concept enumeration can generate as many as 20,000 concepts in a given run). Only concepts that are true for a minimum number of knowledge representations (the concept’s support) are used. More complex concepts can be enumerated via clustering (Duboue and McKeown, 2003b). Thus open class sets are only enumerated for their more common elements (e.g., first-name=“John”). In my experiments, I use a support value of thr_supp, as shown in Table 3.10.

Hypothesis Testing

I then compare the distribution of phrases in the partition of texts associated with the partition in the knowledge representations induced by the concept.⁹ That is to say, I want to see if there is a change in the distribution of words between the two sets; for example, if the biographies of people born in ‘MI’ (a concept) have a higher-than-expected chance of containing the phrase “Michigan.”

Therefore, I have two sets of texts (Michigan and non-Michigan) and I analyze if they diverge in their associated language models over phrases; if they represent samples coming from two different distributions. To achieve this goal, I collect phrasal counts (uni-grams over words in my case) and analyze whether or not these counts can be considered samples coming from the same probability distribution. I collect counts over all phrases (i.e., words in my case). This process is schematically represented by the pseudo-code shown in Figure 3.5.

Student’s t-test. I investigated statistical tests on the counts for each phrase on either partition. In my statistical test, I test the null hypothesis that these words appeared there just by chance. For example, if the partition is induced by the concept “his or her occupation is to be a comedian,” I want to conclude that their associated biographies contain the phrases (i.e., words) “comedian,” “stand-up,” and “comic” more than expected by chance on this corpus.

There might be other terms found frequently for a given concept that are not exact verbalizations of that concept. For example, for people born in Michigan, phrases like “Upper Peninsula” or “Detroit” are to be expected. Therefore, this approach might over-generate.

I compared three statistical tests χ², likelihood ratios and Student’s t-test. My counts were too small for χ², likelihood ratios do not allow for the sampling process described below and therefore only Student’s t-test is used as part of the final algorithm.

I have the total number of occurrences of the events (in this case, phrases) and I want to see if a phrase is associated with the partition induced by the concept. Therefore, as shown in the pseudo-code in Figure 3.8, I split the texts into two sets, the texts belonging to the partition, and the texts that do not belong to the partition. If I apply likelihood ratios or similar techniques to the counts associated with the whole clusters, usually the most descriptive phrases for each element in the cluster will prevail (e.g., in the case of biographies, the names of the people involved in the cluster will appear).¹⁰ I thus resort to a sampling process to avoid this effect. I sample sets of five texts from the partition and five from texts outside and collect phrasal counts. After several samples (100 in my case), I end up with two sequences of numbers, representing the number of times a given phrase appear in each partition; to determine if the two sequences of numbers belong to the same distribution I use the Student’s t-test.¹¹ If the test results are over a threshold thr_t (see Table 3.10), I consider the phrase to be a verbalization adding it to the verbalization dictionary.

The output of the dictionary induction process is a verbalization dictionary containing sets of putative verbalizations for each concept. An example of newly added words is shown in Figure 3.6. I only evaluated this dictionary extrinsically, my measuring its impact on the quality of the obtained matched texts.

Figure 3.7: Verbalize-and-search.

3.3.2 Verbalize-and-search

The verbalize-and-search process (Figure 3.7) aims to identify pieces from the input that contain known verbalizations in the target text. It enriches a matched text initialized with plain target texts. The verbalization step takes a concept and returns all the phrases associated with the concept in the verbalization dictionary. For example, given a concept such as (, “John”), I will search for the strings “John”,“J.” and “JOHN”. To search for the phrases in the text, any classical search algorithm can be employed, e.g., KMP or Boyer-Moore (Gusfield, 1997).

The overall operation is prone to two type of errors: omission (if the verbalization dictionary misses the exact verbalization, e.g., c-comedian appears in the text as “he performed comedy for several years” or “MA” instead of “Maryland”) and over-generation (if there are several values for it, e.g., “Smith” appears in the text and it is simultaneously the name of the father and a brother). The former errors were addressed by the dictionary induction technique described in the previous section. The latter errors are addressed by means of disambiguation methods explained below.

Disambiguation

The ambiguity problem in the verbalize-and-search approach cannot be overlooked. For example, Winona Ryder was born in a city named Winona, in Minnesota. When the phrase “Winona” is found in the text whether the previous words are “born in” or “born as” can provide strong indication for either usage. To acquire the contexts (“born in” vs. “born as”) for each data-class ( vs. ), I compute all ambiguous matches across documents and use standard disambiguation techniques (Naïve Bayes) to smooth¹² the evidence and decide for each class against a null model (trained in every word in the document). This is a local disambiguation, using a very small window (w = 3, see Table 3.10).

In other words, I accumulate statistics for matching at the data-class level. Each match is delimited by a context and all the contexts are accumulated across all the members of the class. This process works on the assumption that, for example, the words surrounding the name of a relative are the same across names of relatives and different biographies. Therefore, I have my list of verbalizations and the places where they match, some of these matches are spurious matches, but working on the hypothesis that the good matches still outnumber the spurious ones (something that is normally the case), I collect statistics from all these contexts. Figure 3.8 shows pseudo-code for this process.

Moreover, I retrain the disambiguators after some matches have been identified to improve their generalization capabilities. For example, if my system has successfully identified an occurrence of “Ryder” in the text “Winona Ryder is an actress” as , it can use it later to disambiguate “Winona” as rather than .

While my final system uses Naïve Bayes disambiguation, I also investigated three other variants, shown in Table 3.1 (this experiment was done on the biography.com corpus mentioned later in this chapter). In the table, the strict variants refer to whether to require that only the left or right context decides in favor of the class (regular variant) or to require that both contexts decide in favor of the class (strict variant). My experiments with the strict variant did not confirm the intuition that it should provide a higher precision, therefore I discontinued its use. I also re-implemented a HMM-based disambiguator following the IdentiFinder trainable named-entity system (Bikel et al., 1999). My implementation, however, did not include the complex class-based smoothing complexities described by Bikel et al., with an inferior performance to the Naïve Bayes approach. I thus decided to focus on the Naïve Bayes technique.

3.4 Data

The Text-Knowledge corpus used in this chapter consists of knowledge extracted from a semi-structured knowledge base, biographical fact-sheets of assorted celebrities. These fact-sheets were crawled from E! on-line¹³ in November 2002. In addition to this knowledge source, I also employ an extended knowledge source, also extracted from E! on-line but with a slightly different ontology and with added information about which movies each actor appeared in. This extended knowledge source was incorporated as part of these experiments at the end of this dissertation and was not used during system development (i.e., no parameters were fit on this corpus). Different biographical sites provide the text part, to test the ability of the system to learn from different types of data. The process of constructing this Text-Knowledge corpus is detailed in Chapter 7, Section 7.1, I will just detail here the overall size of each Text-Knowledge corpus. As explained in Section 3.2.1, each corpus was split into a training and test set, with the test set tagged for selection and ordering (ordering only in the last corpus) by the author.

3.4.1 biography.com

The biography.com corpus is the smallest (in number of pairs) corpus of the collection and it was used mostly for development. The biographies are clearly written by professional editors and present the higher level of homogeneity.

In the table, pairs refer to the number of text and knowledge pairs; frames refer to the number of internal nodes in the graph; triples refer to the number of triples in the form (frame, link, target), the equivalent of an arrow in Figure 3.1; words and chars refer to the number of words and characters in the target texts, respectively. The average number of words per biography and its standard deviation speaks of quite lengthy biographies with a stable length (compared to the next two corpora).

The test set contains 334 selected triples, from a total of 744 triples to select from (an F*¹⁴ for the Select-All strategy of 0.62 —The Select-All strategy can be thought of as a baseline). The total number of triples is different than the number shown in the table as the table also shows triples that connect internal nodes.

This corpus was a fine development corpus, as its small size allowed me to implement and test different ideas quite quickly. On the other hand, this corpus constitutes a high baseline that makes it difficult to appreciate the relative differences of system variants. For that reason, I introduced the other corpora detailed next, each of which presents a relatively harder matched text construction task.

3.4.2 s9.com

The s9.com corpus is the largest corpus (in number of pairs) and the one with the shortest biographies. The biographies are mostly one-liners and it is unclear whether or not they have been written by editorial staff.

Because of the small size of each biography, this is a challenging corpus, where out of 1,377 triples to select from, only 170 are selected (an F* for the Select-All strategy of 0.22). The texts are so small (36 words on average) that one would be hard pressed to call them biographies. The standard deviation is also pretty large.

3.4.3 imdb.com

In previous work (Duboue and McKeown, 2003a, Duboue, 2004), I have used the corpus assembled from imdb.com as a test corpus. It is of medium size and has biographies submitted by volunteers over the Web; this made it more challenging than corpora written by an editorial staff.

The test set contains a total of 369 selected triples out of 1,060 (an F* for Select-All of 0.516). While the size of each biography is around 300 words, so is the standard deviation; and thus, the biographies on this corpus are clearly of diverging sizes.

3.4.4 wikipedia.org

Near the end of this dissertation work, I created an extended knowledge source by adding to the previous knowledge extra information in the form of artistic credits (the movie starred by each actor). This extended knowledge source was paired against biographies from wikipedia.org. The site wikipedia.org is a collaborative collection of encyclopedic articles embodied in the concept of a Wiki, a page that allows any person with WWW access to edit it. The Wiki approach produces a very dynamic set of pages that pose a more challenging environment than the previous corpora. On the bright side, this corpus contains more pairs than the imdb.com and it has a very liberal license that allows for corpus re-distribution. This is the only corpus annotated with ordering information, because the extended knowledge source is the only one compatible with the hand-written communicative predicates presented in Chapter 5. These predicates are a requirement for learning Document Structuring schemata.

The test set contains 598 selected triples out of 2,906 (an F* for Select-All of 0.341).

3.5 Experiments

The architecture presented in the previous sections leaves room for a number of variations, some of which I have investigated in this thesis. I investigated the following issues:

Addition of the matches to the matched text being constructed. As mentioned in Section 3.3.2, it is advantageous to retrain the disambiguators after a certain number of matches have been identified. I investigated two possibilities for adding matches to the partial matched text. I describe them below.

(Path_add)

Path-based addition. I have investigated adding all matches in a data-path in order (data-paths with more selected matches first). For each match, the algorithm selects the ones with a score over the null model for that position. I then record the percentage of total matches over selected matches. The data-path with a higher percentage was considered to be of better quality and thus added to the matched text. The problem of this approach is that it may incorporate a good deal of noise in one step (and that noise will be carried on afterwards, as the algorithm does not allow for backtracking).

(Score_add)

Score-based addition. To avoid the problem of forcing a decision over all elements in a data-path (including some matches over which the system has less than perfect evidence), I investigated adding a percentage of the higher scoring matches (across different data-paths) in each step. Given a set of selected matches (i.e., matches that are higher than the null model), I order them by their predicted belonging to the class. I then add to the matched text the top scoring 10% of the matches in the first step (20% in the second step and so on). In general, an EM-based algorithm (Dempster et al., 1977) will be the most general solution to this problem, but will imply learning also how to extract the knowledge from the text.

Creation of the verbalization dictionary. While in this thesis I focus on the automatic construction of the verbalization dictionary (Section 3.3.1), this dictionary can be obtained in a number of ways, some of which do not necessarily include learning:

(Trivial_dict)

Trivial. The verbalization for (path, phrase) is phrase, e.g., for a concept such as , the verbalization is John. This will obviously not work in the case the value is not phrase, e.g., .

(External_dict)

External. A small external dictionary with possible verbalizations of states, months and numbers can be provided as a knowledge-based external verbalization dictionary. This problem of small variations in numbers and dates is similar to the problem of telling them apart in Speech Recognition or reading them aloud in Speech Synthesis (Jurafsky and Martin, 2000); I thus employ a small verbalization system based on Finite State Transducers (shallow generation grammars). Examples of these paraphrases include number verbalizations (e.g., “three” for ‘3’), months (e.g., “September” for ‘9’) and state names (e.g., “Michigan” for ‘MI’).

(On-line_dict)

On-line. The on-line dictionary construction implies executing the dictionary induction only when the number of available matches is low or its quality is below a threshold thr_add (see Table 3.10). For example, in the data-path variant, if the ratio of matches accepted by the disambiguator is below 20% (that is 80% of the matches for a data-path are considered spurious by the disambiguator), the dictionary induction is executed. An advantage of this variant is that the dictionary induction is executed over the matched texts, where the pieces of text matched to a concept are replaced with semantic tags —the data-path for the concept.

(Off-line_dict)

Off-line. This involves executing the dictionary induction algorithm before the verbalize-and-search process. Because the partial matches are not available at this point, this dictionary induction may introduce some noise in the process.

I explored these options through the following variants:

Variant 0 (Path_add+ Trivial_dict)

Simplest system, with no dictionary induction and no disambiguation; the most popular path is added first, where popular means the path with more matches. Such a system is similar to currently used approaches for bootstrapping information extraction systems (Chieu et al., 2003).

Variant 1 (Path_add+ On-line_dict)

This variant adds matches in a path-based fashion with the dictionary updated after the scores fell under threshold thr_add (see Table 3.10).

Variant 2 (Score_add+ Off-line_dict)

This variant adds matches to the matched text being constructed in a percentage-based fashion, with an off-line computation of the dictionary.

Variant 3 (Score_add+ External_dict)

This variant adds matches to the matched text being constructed in a percentage-based fashion, using an external verbalization dictionary.

Variant 4 (Score_add+ External_dict+ Off-line_dict)

This variant combines Variants 2 and 3; it adds matches in a percentage-based fashion, using both an external verbalization dictionary and an off-line computation of the dictionary.

The results for the Content Selection quality of the learned matched texts are shown in Table 3.2.

Variant 1 was computationally too expensive to compute on the larger corpora and only biography.com results are included. The relative differences between Variant 1 and Variant 2 can only be seen if we plot precision and recall during the matched text construction process (Figure 3.9 and Figure 3.10). The figures are obtained by evaluating the matched text being constructed as matches are being added to the matched text. The y-axis measures precision and recall and the x-axis are iterations on the matched text construction process. These figures show clearly how Variant 1 starts very well until its curves suddenly drop (around the tenth iteration), most likely because it commits itself to add all matched instances in a wrongly matched data-path. Variant 2, on the other hand, has a much softer curve, where the benefits of re-training the disambiguators on earlier matches can be seen clearly;¹⁵ even precision improves after some matches have been identified.

In general, Variant 0 has the best precision across all corpora, with Variant 4 presenting the best recall. When considering F^*-measure, Variant 4 has the best F^* overall, although that is not the case in all corpora.

Because of the differences in Table 3.2 are pretty small, I conducted a cross-fold validation experiment to test the differences between the variants. The actual results of these experiments are presented in Appendix A. I will mention here the highlights. For biography.com, only Variant 1 has a statistically significant difference with a good level of confidence. For s9.com and imdb.com, no difference has a good confidence, although the difference between variants 3 and 4 in imdb.com is noteworthy. In wikipedia.org, the differences between Variant 2 and the Variants 0 and Variants 3 are statistically significant with good confidence.

In this evaluation, the system is trained in (Tr+Te) and tested in Te (as explained in Section 3.2.1). Here Tr is used to provide extra evidence to the dictionary induction and disambiguation methods. This approach begs the question of the importance of the size of Tr for the results reported over Te. Moreover, because the cross-validation experiments that measure statistical significance are trained in one third of Tr each fold, it is also important to understand how different such system may be with respect to the system trained in all Tr. Figure 3.11 and Figure 3.12 show the impact of the size of Tr for Variants 2 and 3 in 10 different random subsets of different size (10,11,..,30, 40, ..., 90) of Tr (plus all Te) and testing the obtained labels on Te. The figures show clearly that Variant 2 requires at least 60 instances to stabilize, while Variant 3 (that does not performs any dictionary induction) profits from the extra training material very slowly (by improving the disambiguators).

Finally, to shed further light on the differences in Table 3.2, I analyzed the error over each data-path. Tables 3.3 and 3.4 show major contributors to the error and success rates, respectively. These contributors perform similarly across all variants. There we can see that the free-text paths (for example, paths that end in canned-text in this particular knowledge representation) and the symbolic paths (paths that finish in #TYPE, for example) are responsible for a large number of errors. On the other end of the spectrum (more successful paths), there are paths such as or (movie names and the like) that have higher chances of appearing in the text exactly as they appear in the knowledge representation (they are stronger anchors, in the nomenclature of Chapter 1). These are data-paths containing more named-entity alike information and they are better captured by my system.

While my system has no provisions for free-text values, the dictionary induction should deal with the #TYPE paths. This can be seen in Tables 3.5-3.8 that show error contribution itemized per variant for data-paths with variant-related differences. In biography.com corpus, for example the table shows that the variants with dictionary induction (Variants 1 and 2) mildly address the symbolic fields with Variant 1 marginally better than Variant 2. This is to be expected as Variant 1 does a very costly on-line dictionary induction, where the dictionary is re-induced after some matches are identified (improving the quality of the language models). With respect to the differences coming from the use of disambiguation, this can be appreciated in the last name of relatives (). However, the use of disambiguators makes the whole system more wary of places where little evidence across frames supports the match (the system becomes more conservative). This situation slightly increases the number of mismatches in a number of paths.

The error analysis for the s9.com corpus (Table 3.6) shows the same overall behavior of biography.com, although here the disambiguation improves more paths than in biography.com. Interestingly, as the system becomes more conservative, the gains equalize again. This is because I am averaging over all paths. The table shows how the distribution of errors is more uniform thanks to the disambiguated system. This will be particularly important for the ordering behavior in the wikipedia.org corpus.

Table 3.7 contains the misses per data-path in imdb.com, which are also in line with the previous two corpora. Note how benefits from the small external dictionary in Variant 3.

The results for Document Structuring on the wikipedia.org corpus are shown in Table 3.9. While the sequences are similar in length to the text set, according to Table 3.2 only half of the information there appears also in the test set. For these elements in the intersection, there is a near-perfect correlation in the ordering. This implies this data can be used positively to learn Document Structuring schemata.

The sequences evaluated here are sequences of atomic values as they appear in the matched text. These sequences are different from sequences of instantiated communicative predicates (such sequences are document plans) but they will nevertheless be used in Chapter 5 to evaluate different schemata during learning. The sequences of atomic values will also be used to learn Order Constraints.

3.6 Conclusions

The process presented in this chapter is able to automatically identify training material with an F^*-measure as high as 0.70 and as low as 0.53 and a τ as high as 0.94 and as low as 0.86. These results imply that learning using the matched texts as training material will require a robust machine learning methodology as the ones introduced in the next two chapters.

Moreover, as it will be discussed in Chapter 8, the technique presented here cannot learn after a certain point. Particularly, it has problems with free-text fields (e.g., “claim to fame”) or facts included in the text out of being of extraordinary nature.

Chapter 4
Learning of Content Selection Rules

This chapter presents my work on the automatic acquisition of a set of Content Selection rules. These rules provide a particular solution to the Content Selection task (a task defined in the next section). I decided to use these symbolic rules (also described in the next section) as a representation for learning because they capture the requirements of my Content Selection problem. Moreover, they are also easy to understand by humans, allowing the output of the learning system to be further refined for quality, if needed.

The internals of this rule learning process are the focus of this chapter. The rule learning mechanism described here learns from the ideal dataset for the task of learning Content Selection rules: knowledge data with select (sel) or omit (¬sel) labels (Figure 4.1 (b)). Such training material can be considered ideal for learning Content Selection logic as it is the input and output of the Content Selection process. The labels will thus signal, for each piece of data, whether or not the piece of data should be selected for inclusion in the final text. The ideal dataset can be obtained directly by hand-tagging but I am interested in a solution without any human intervention, neither from a knowledge engineer or annotators. Therefore, I learn from a noisy approximation obtained from the natural dataset for the task, in the form of a Text-Knowledge corpus (Figure 4.1 (a)), using the matched text from the previous chapter.¹ The Supervised Learning step (Section 4.2) will thus search for rules that better accommodate this training material. The training material from the biographies domain sketched in the previous chapter (Section 3.4, discussed at length in Chapter 7, Section 7.1) will be used to run a number of experiments, presented in Section 4.3.

Learning from a dataset extracted automatically makes for a very challenging task. For instance, my approach of analyzing how variations in the data affect the text (used to build the matched texts in the previous chapter) is prone to over-generation, as explained in the limitations chapter, Section 8.2. This over-generation implies that the rules learned from this dataset will be likely to have low precision.

Sean Connery 84Kg 188cm	Sean Connery 84Kg 188cm
⇓	⇓
Sean Connery, born Thomas Sean Connery in August 25th, 1930 in Scotland is an actor, director and producer. …	Sean Connery 84Kg 188cm
(a)	(b)

Figure 4.1: Input to the learning system. (a) Actual input, a set of associated knowledge base and text pairs (indirect evidence for learning) (b) Fully supervised input with selected items shown in bold; this is obtained as a byproduct of the processing done by my system.

label	data-path	value
sel		“Sean”
sel		“Connery”
¬sel		84Kg
¬sel		188cm
sel		“Oscar”
¬sel		“MTV”
sel		c-grand-son
sel		“Dashiel”
¬sel		c-step-cousin
¬sel		“Jason”

(a)

Sean Connery received an Oscar and has a grand-son, Dashiel …
(b)

Figure 4.2: Content Selection Example. (a) The input to the Content Selection module plus its output (selection labels) (b) Verbalization of the selected attribute-value pairs.

4.1 Definitions

I will now introduce some definitions I use in the remainder of this chapter.

Content Selection. This is the action of choosing the right information to communicate in a NLG system, a complex and domain dependent task. Figure 4.2 shows an example; its input is a set of attribute-value pairs, and its output is a subset of the input attribute-value pairs, determined by the selection labels (sel or ¬sel). The labeled with sel subset contains the information that will make up the final, generated text. Content Selection can be thought of as a filtering or as a labelling process. When thought of as a labelling process, the system will choose between two labels: sel (i.e., filter accepts) or ¬sel (i.e., filter rejects). The labelling approach allows for a generalized Content Selection task, where each piece of data is assigned a salience score. In my work, I will consider a labelling task with two classes. My approach can be extended to accommodate generic classes as discussed in the Conclusions chapter (Section 9.2).

Content Selection rules. The output of my learning system are Content Selection rules, which base their decision solely on the available knowledge. All rules are functions from a node to ; that is, they take a node in the knowledge representation and return true or false. In this way, my Content Selection rules contain decision logic only for atomic nodes. In this chapter, expressions such as “a piece of data to be selected” are formalized as an atomic node in the knowledge representation graph (of all types but Reference type, see the definitions in the previous chapter). The decision of whether to include a given piece of data is made solely on the given data (no text is available during generation, as the generation process is creating output text). Sometimes it is enough only to analyze the value of the atomic node (e.g., to tell an Oscar from a BAFTA award). In other cases, however, it is also necessary to look at the surrounding information to decide whether or not to include a piece of data. For example, to tell the name of a cousin from the name of a grand-son (Figure 4.3) or to tell a successful movie (movies that received a number of awards) from failures. A simplifying assumption involved in a two level Content Selection approach, as the one presented in this thesis, is that all nodes are processed independently during the first Content Selection level. Therefore, the outcome of the decision about other nodes is not part of a given node decision. This simplifying assumption is clearly wrong (in a extreme case, if a piece of information appears repeated as two different nodes, the inclusion of one node should prevent the other node to be included), but Content Selection in context is attacked by the fitness function presented in the next chapter.

I mine a different set of rules for each data-class (data-path in my case). The impact of the data-class equivalence classes for the quality of Content Selection rules is a subject I am interested in pursuing in further work.

Figure 4.3: The value of nodes outside the node being selected may contain information that governs the selection process. In this example, to decide whether to include “Dashiel” or “Jason,” the type of the relative frame is important (in the nomenclature used in this dissertation, that value can be accessed through the path .

Select-All/Select-None rules. The first type of rules, Select-All/Select-None, addresses the first four rows of Figure 4.2. After analyzing a number of target biographies in a hypothetical style, it is easy to see that the first and last names of the person being described should always be included in the biography. Conversely, his weight or height should never be included. These rules will select or omit each and every instance of a given data-class at the same time (e.g., if is selected, then “Dashiel” and “Jason” will both be selected in Figure 4.2).²

Tri-partite rules. After careful analysis of my training data and experimentation with different rule languages, I have settled for rules containing three pieces of information (these rules are applied to an atomic node in the graph, the ‘current node’):

1. Constraints on the current node.
2. Path to a second node (relative to the current node).
3. Constraints on the second node³ (the node at the end of the path).

The constraints can be very general (including access to global variables or arithmetic operations on Numeric nodes), but in my work I have used two simple constraints. The first constraint, True, always selects the information for inclusion. It is marked as ‘-’ in my representation of the rules. The second type of constraints are constraints saying that the value of the node has to belong to a set of values. They are marked as ‘value ∈’. The tri-partite rules can contain empty paths (denoted as ‘-’), in which case there should be no constraints on the second node.

This rule language addresses three types of selection needs, all shown in the example knowledge base with selection labels of Figure 4.2. To begin with, it is possible to express Select-All/Select-None rules in this language (first two rules in Figure 4.4), successfully addressing the first four rows of Figure 4.2.

The next two rows, regarding different awards the person has received make for a more interesting case, where the information should be included only if it belongs to a certain set of important values. In the celebrities domain, important awards include, for example, Oscars or the Golden Globes (motivating rules such as the third one in Figure 4.4). Obviously, the relative importance of the different awards is clearly domain dependent. The case shown in the figure is paradigmatic: MTV movie awards are seldom mentioned in target biographies. This omission is to be expected according to people I consulted who are interested in celebrities issues. Nothing a priori in the data prepare you for that result, as MTV is a source of authority in the celebrities domain. As the experiments in Section 4.3 show, my system is able to acquire this type of information.

Finally, for the last four rows in Figure 4.2, the information to solve the selection of the name of the relative does not lie on the name itself but in the value of another node that can be reached from the name node: the type of the relation. This fact motivates the path and the constraints in the other node (as part of the tri-partite rule). My final goal has been to be able to express with the rules concepts as complex as this movie should be selected if it received an Oscar, as shown in the last rule of Figure 4.4.

(-, -, -).       ;Select-All

Always say the first name of the person being described.

: (false, -, -).      ;Select-None

Never say the eye color of the person being described.

: (value ∈, -,-).

Only mention the name of an award if it is whether a Golden Globe or an Oscar.

: (-,,value ∈).

Only mention the title of a movie if the movie received an Oscar.

Figure 4.4: Example content selection rules. In the path, -title refers to traversing a link title in the opposite direction. I employ hard rules instead of soft percentages to allow for a natural integration with hand-written rules. reviewPablosay this also in the text

Complex Content Selection Rules. In preliminary investigations (Duboue, 2004), I presented a variant of my system that targets more complex rules than the tri-partite ones I have just defined. These rules allow for recursion and are summarized in Figure 4.5. While this rules are more expressive than the tri-partite ones, I discontinue their use in favor of the tri-partite rules, as the latter are a more constrained representation that makes better use of the training material.

TRUE()

Always select.

IN(list of atomic values)

Select if the value is in the list.

TRAVERSE(path in the graph,rule)

Select if the node at the of the path are selected by the rule.

TRAVERSE-EQ(path in the graph)

Select if the value of the node at the end of the path is equal to the value of the current node.

AND(rules)

Select if all the rules select the current node.

OR(rules)

Select if any of the rules select the current node.

Figure 4.5: Complex Rule language. All rules are of the form f : node →, that is, they take a node in the knowledge representation and return true or false. These rules are more expressive than their simplified counterpart.

4.2 Supervised Learning

Figure 4.6 illustrates my two-step indirect supervised learning approach, divided into a number of modules. The first step, Dataset Construction (discussed in the previous chapter), turns the aligned Text-Knowledge corpus into a training dataset consisting of knowledge and selected or omitted labels (the Relevant Knowledge). Once the labels have been elucidated, the Supervised Learning module performs a Genetic Search in the space of possible rulesets, as described in this section.

I have thus a dataset consisting of classification labels (selected, sel, or omitted, ¬sel) for each piece of input knowledge. I want to learn that mapping (from concept to classification label) and capture that information about the mapping using Content Selection rules. This constitutes a case for Supervised Learning. The information available to the learner is thus the frame knowledge representation (a graph) plus the labels. This implies learning from structural information (as compared to learning from flat feature vectors). To this end, several alternatives are possible, including using memory-based learning, inductive logic programming, combinatorial algorithms and kernel methods (Washio and Motoda, 2003). Given the high dimensionality of the decision space over graphs, I have found it valuable to be able to define a successor instance coming from two instances in the search pool, instead of one. This type of approach is known as Genetic Algorithms (Section 4.2.1). In general, I consider GAs as a meaningful way to perform symbolic learning with statistical methods. To motivate its use I also propose a comparison to ML classification systems in Section 4.2.2 and to some meaningful baselines in Section 4.2.3.

4.2.1 Learning Rules

↓
rule
1 2
↓		training
	← F-measure →

Figure 4.7: Rule evaluation. Each rule is executed and its output compared to the automatically obtained reference.

I have input and output pairs of knowledge and labels (K,L), with labels extracted from the matched text. I am interested in finding the rules r^* (belonging to the set of all possible Content Selection rules) such that r^* maximizes the posterior probability given the training material:

instead of computing a probability, I use the input and output pairs to compute for each putative rules r a likelihood f(r,K,L) that allows me to compare among them. This likelihood is thus a quality function in the representation space. I use the rules (r) to generate from the input knowledge K a set of labels L′. The sought quality function becomes the distance between the training output and the produced output, ||L-L′||. As distance, I use the F-measure from Information Retrieval (IR). This process is sketched in Figure 4.7.

With the quality function in hand, finding the rules r^* implies a search process on the large space of representations. The key ingredients in a Genetic Algorithms solution are the fitness function (the quality function mentioned above), the operators and the initial population. I will describe them shortly.

Fitness Function. The fitness function takes a tri-partite rule r and computes its expected goodness with respect to the training material. One contribution of this thesis is to employ as fitness function the F_α measure (weighted f-measure from IR (van Rijsbergen, 1979)) of the classification task of recovering all selection labels on the training datasets. That is to say, for a given data-class, there are a number of items in the data-class to be selected according to the training material. The tri-partite rule r is applied to the knowledge and the number of correctly selected items becomes the rule’s number of true positives. The number of items the rule wrongly selects is its number of false positives. Finally, the items the rule should have selected but it missed are the rule’s number of false negatives. The F_α then is defined as follows, where P stands for precision and R stands for recall:

The fitness function is the key to learning using GAs. In earlier versions of my system the fitness function was too biased towards selecting all elements in the data-class. The key ingredient for a successful function in my problem has been to add information about the priors for each class (selected or omitted) in each data-class. The function defined above implicitly incorporate these priors (in the counts of false positives and false negatives).

As I wanted to obtain rules with higher recall than precision, I employed α = 2.0 (recall is doubly as important as precision), as shown in Table 4.5. I added a minimum description length (MDL) term to the fitness function to avoid over-fitting the data (by memorizing all training instances). The final fitness function is then:

MDL term. To avoid overtraining I use a MDL term as part of the fitness function. The type of over-training I try to avoid are, for example, cases where month-of-birth is always selected but I only see all months but June in the training material. There a rule like (value ∈ “Sep”, , -,-) will accomodate the training material, but (-,-,-) (True) will also explain it, and generalize better.