Learning Schemata for Natural Language Processing

LEARNING SCHEMATA FOR NATURAL LANGUAGE PROCESSING

Raymond Mooney Gerald DeJong

Coordinated Science Laboratory University of Illinois at Urbana..(;hampaign Urbana, IL 61801

in the normal course of processing narratives. 1 After acquiring new schemata, the system is able to correctly process narrative.~ that were previously beyond its capabilities.

We call the learning process used by GENESIS explanatory schei'TUl acquisit.ion [DeJong83! It is a form of explanation-based learning [DeJong8.5l which can be briefly defined as learning a new problem solving method by analyzing the causal structure of a problem solution. The system is fully implemented and an example sequence demonstrating the system's learning is given later in the paper. A longer version of this paper appears as [Mooney8.5!

D GENERAL SYSTEM ORGANIZATION

The general organization of the GENESIS narrative processing system is shown in figure 1. First, English input is processed by a parser into a conceptual representation (CRep), a case-frame representation which uses some conceptual dependency prim.ilives [Schank7.5) as well as predicates for complex schemata. Currently, we are using an adaptation of Dyer's McDYPAR [Dyer83) for this purpose; however, since the focus of our research is learning, we make no claims about parsing and alternative approaches could be used for this task (e.g. [Marcus80, Waltz84)).

The basic task of the understander is to construct a causally complete representation called the model. A model for a narrative has explicit representations for all the inputs as well as the many inferences that must be made to causally connect them together. There are four types of causal links for connecting assertions in the model of a narrative. These are:

p1·econdition: A link between a state and an action it enables.

effect:

A link. between an action and a resulting state.

1 The ust of tht term "story" in naturallan&ua&< proccssin& hLI betn controvtr sial 1Brewer82l Therrfore, in this paper .,. .· havc adopted tho trrrn "narrative" to rrfcr to connected text which may Jack a plot or other de!inin~ aspect or · ""ory."

ABSTR.ACf

This paper describes a natural language system which improves its own performance through learning. The system processes short English narratives and is able to acquire, from a sin­ gle narrative, a new schema for a stereotypical set of actions. Dur­ ing the understanding process, the system attempts to construct explanations for characters' actions in terms of the goals their actions were meant to achieve. When the system observes that a character has achieved an interesting goal in a novel way, it gen­ eralizes the set of actions they used to achieve this goal into a new schema. The generalization process is a knowledge-based analysis of the causal structure of the narrative which removes unnecessary details while maintaining the validity of the causal explanation. The resulting generaliud set of actions is then stored as a new schema and used by the system to correctly process narratives which were previously beyond its capabilities.

I INTRODUCTION

A natural language system requires extensive knowledge about the world. Clearly, if a computer system is to summarize, translate, or answer questions about a text, it must have knowledge about the concepts expressed in the text. Imagine trying to process a narrative describing a bank robbery without knowledge of money and why people want it. This is a conceptual rather than linguistic requirement, and it means that at the heart of a natural language processor there must be a problem solver to infer missing but important concepts, to insure that the narrative phrases are causally related in an appropriate way, and perhaps to guide the linguistic processing [DeJong82!

Schema-based problem solvers [Charniak77, Minsky7.5, Schank 77) have proven themselves more workable for natural language processing applications than their heuristic search counter­ parts. In order to process a wide range of text, a schema-based natural language processor must possess many schemata, perhaps hundreds of thousands. This presents both practical and theoretical problems. Somehow these schemata must find their way into the system. They cannot all be built in by hand; there are simply too many. Furthermore, hand coding does not allow for dynamic aug­ mentation of world knowledge. This is an important facet of language processing. For example, the word wSkyjacking," is now an accepted newspaper term but was unheard of twenty years aso. Readers have learned it as a by-product of their normal newspaper reading and natural language processing systems must be able to do the same.

We have taken the first steps in this direction at the t:niver­ sity of Illinois. A natural language processing system called GENESIS (for GENeralizing Explanations of Stories Into Schemata) has been designed and implemented which acquires new schemata

Thi· work ,. ... supponed in pan by th< Air Foret' Oilier of Scicnti!ic Reotarch under grant F49b20-82·K-0009 and in part by tht National Science Foundation undrr grant NSF· IST- ~3-178~9.

motivation:

in fer·en.ce:

A link between a volitional action and the belit'fs and goals of the actor which motivated him to per­ form the action.

A link between a state and another state which it implies.

To avoid confusion, such "causal" links between assertions in the model will be called support links. since a precondition of an action supports the performance of that action but does not cause it. The closely related term data dependency link [Doyle78l is not used since it is normally reserved for the support of inferences, not for the support of both inferences and actions. Inferring causal connec­ tions necessarily employs a large amount of background knowledge which is stored in the sclumw library. The techniques and representations used in this process are similar to those used in past work in narrative understanding [Charniak 77, Cullingford78, DeJong82, Dyer83, Wilensky83] and are discussed in sections IV and V.

In order to demonstrate the abilities of the understander, a simple question answering system is used to inspect the model. Since our interests lie in guiding the generalization process through the use of causal relationships. this subsystem is primarily used for accessing the reasons why an actor performed a certain action or why a particular state exists. This information is easily retrieved by inspecting the support links between the various states and actions in the model. Of course, there are many issues involved in retrieving the most appropriate answers to questions (see [Lehnert78]) which we do not fully confront in this subsystem. A simple natural language generator for translating replies into English is also included as part of the system.

If an actor in a narrative achieves an important goal through a novel combination of actions. the explanalion for how the goal was achieved is generalized into a new schema. The combination of actions which supports the achieved goal state is generalized as far as possible without breaking any of the connecting support links or violating the well-formedness of individual actions and states. This genera !ired structure is then stored as a new schema in the library where it is used to facilitate the processing of future narra­ tives. This generalization process is discussed in section VI and is the key to the learning technique of explanatory schema acquisition.

III AN EXAMPLE

Currently, GE'\ESJS has acquired two new schemata. In one example, the system learns a schema for someone kidnapping an indi vidual and holding them for ransom. ln the other, it learns a schema for someone burning his own building to collect the insurance. Here we \\"ill show the performance of the system on the kidnapping example. Before processing the following narratives. GEl\ESIS contains information in its schema library about bargain­ ing, capturing and confming indi viduals. threatening. and many other concepts; however, it does not have a schema for kidnapping for ransom. First it receives the following "test" narrative:

ll\PUT: Ted is the husband of Alice. He won S 100000 in the lot­ tery. Bob imprisoned Alice in his basement. Bob got S75000 and released Alice.

Processing Story_

Finished processing.

No thematic goals achieved by a novel combination of actions: no generalization.

Ready for questions:

? (Who gave Bob the money) Answer unknown.

? (Why did Bob lock Alice in his basement) Cannot find sufficient reason for his action.

? (Why did Bob release Alice)

Cannot find sufficient reason for his action.

Notice that in this narrative it is not mentioned how Bob got the money or why Bob imprisoned Alice and then released her. Since the system does not have a schema for kidnapping, it cannot infer the missing information and construct a causally complete explana­ tion of the narrative. Next, it is given the following narrative.

INPUT: Fred is the father of Mary and is a millionaire. John approached Mary. She was wearing blue jeans. John pointed a gun at her and told her he wanted her to get into his car. He drove her to his hotel and locked her in his room. John called Fred and told him John was holding Mary captive. John told Fred if Fred gave him S 250000 at Trenos then John would release Mary. Fred gave him the money and John released Mary.

Processing Story_

Finished processing.

John achieved the thematic goal: John has S 250000.

Generalizing- Assembling new schema: CAPTURE-BARGAIN.

Ready for questions:

? (Why did John imprison Mary in his room)

So John and Fred could make a bargain in which John released Mary and Fred gave John 250000 dollars at Trenos restaurant.

? (Why did John make the bargain with Fred)

Because John wanted to have 25000 dollars more than he wanted to hold Mary captive.

? (Why did Fred make the bargain with John )

Because Fred wanted !'\'lary to be free more than he wanted to have 250000 dollars.

? (Why did Fred want Mary free) Because Fred was Mary's father.

Unlike the first narrative, this one is detailed enough to allow GENESIS to causally connect the individual actions. The resulting causal structure is then generalized into a new schema of kidnap­ ping for ransom (which GENESIS calls CAPTURE BARGAIN). Next, the system is given the first narrative again, and using the schema it has just acquired. it is able to infer the missing information and causally connect the actions. Consequently, it is able to answer the questions which previously it could not answer.

INPUT: Ted is the husband of Alice. He won S 100000 in the lot­ tery. Bob imprisoned Alice in his basement. Bob got S75000 and released Alice.

Processing Story_

Finished processing.

No thematic goals achieved by a novel combination of actions: no generalization.

Ready for questions:

? (Who gave Bob the money)

Ted gave Bob 75000 dollars.

? (Wh.y did Bob lock Alice in his basement)

So Bob and Ted could make a bargain in which Bob released Alice and Ted gave Bob 75000 dollars.

? (Why did Bob release Alice)

Because Bob and Ted made a bargain in which Bob released Alice and Ted gave Bob 75000 dollars.

IV KNOWLEOOE REPRESENTATION

GENESIS' knowledge is represented in a library of schemata: packets of general information about stereotypical objects, situa- I I

I

I

I

I

I

I

tions, and actions. All schemata in the library are arranged in a hierarchical inheritance net under the three major classes of ACTION, STATE, and OBJECT (the highest level class is simply called SCHEMA). Each schema has a set of roles associated with it which can be filled by other schemata to create an instance of the schema. The type of information associated with a schema depends on whether it is an ACTION. STATE, or OBJECT so each of these will be discussed in turn.

ACTION schemata represent dynamic events which change the state of the world. The following pieces of information are attached to ACTION schemata. In addition to the information attached directly to a particular schema, each ACTION inherits the informa­ tion attached to ACTIONs above it in the abstraction hierarchy.

Role Constraints:

Defaults:

Preconditions:

Motivations:

Effects:

Terminations:

Expansion Schemata:

Suggested Schemata:

Each role is marked with the type of schema which can legally fill iL

Default fillers can be specif1ed for each role.

States which must be true in order for the action to take place.

States (BELIEFs and GOALs) which explain why an actor would perform this action.

States which are true after the action is performed.

States which are no longer true after the action is performed. (These are similar to the delete-lists in STRIPs but states are temporally marked as no longer holding instead of being deleted from the model.)

A set of lower-level states and actions which actually make up this action along with the support relationships between them (similar to the body of a script).

Larger composite actions which this ac­ tion may be a part of.

Determining Conditions: A set of lower-level actions and states which if all present indicate the oc­ currence of this action.

STATES, on the other hand, represent relatively static situa­ tions in the world, such as an individual being someone's father or being in possession of some objecL The following pieces of informa­ tion are attached to STATE schemata. In addition to the information attached directly to a particular schema, each STATE inherits the information attached to STATEs above it in the abstraction hierar­ chy.

Role Constraints: Each role is marked with the type of schema which can legally fill iL

Defaults:

Default fillers can be specified for each role.

Inferences:

Other states which are reasonable inferences to make from this state.

Achieving Actions: Actions which can be used to achieve this state.

OBJECTs represent types of things in the world. The informa­ tion attached to OBJECT schemata varies from class to class. Com­ mon examples for physical objects would be defaults for size, shape, and other physical attributes.

V THE UNDERSTANDING PROCESS

Since applying explanatory schema acquisition depends on having a causal chain of actions to generalize, the "understanding" ability of GE:'-/ESIS is concentrated on constructing this chain by inferring missing information and causally connecting inputs together. \Ve do not attempt to deal with other important issues which have recently occupied researchers in narrative understand­ ing such as plor units [Lehnertli2l thematic abstractions units [Dyer83l story points [Wilensky!i3l affect [Dyer83l and iruegr·ated parsing [DeJong82, Dyerli3!

In accomplishing the task of constructing caus;~l wnnections, GENESIS, like FAUSTUS [l\:orvig83, Wilenskyli3l uses a combina­ tion of top-down and bottom-up processing techniques. If a set of inputs in a narrative matches a schema which the system already has, then it uses top-dov.·n processing to fill in the exparuum of this Schema with the particular inputs of this narrati\'e, much like a script driven program such as SAM [Cullingfnrd78) or FRUMP [DeJong82! However, if an action in the narrative is not explained by a known schema, it attempts to rnnnrl'l it to other actions and states in the narrative by searching for existing states which fulfill the preconditions for this action, or by hypothesizing intermediate actions which causally connect it to existing states or actions. In this way, it also operates in a more bottom-up fashion like plan· based programs such as PAM [Wilensky83!

A. Schema Activation and Determination

If a schema-based system is to be able to process a range of possible inputs, it must have access to a large number of schemata. Therefore, in order to avoid repeated searching through the entire database of schemata, it must also have an efficient method for selecting the particular schemata which are applicable to the current inpuL Several researchers have addressed this difficult problem [Charniak78, DeJong82, Norvig83) and below is a brief description of the approach GENESIS uses.

When GENESIS processes an input, it adds it to the model and activales all the schemata in the list of suggested sclu!ma.ta attached to the schema class of the inpuL Active schemata then monitor subsequent inputs and check if they match parts of its expansion and can therefore be considered part of this active schema. When all the determining conditions of an active schema are met, it is determined or considered to have occurred in the nar­ rative and is added to model along with the schemata and support relationships given in its expansion. 2 If a determining condition is an action, then it is also considered to have occurred if all of its effects are in the model.

B. Bottom-up Construction of Support Relationships

When a new schema instance is added to the model (either as the result of an input or an inference on the part of the system), the system first tries to explain it as part of a known schema. How­ ever, if the new instance does not suggest any higher-level sche­ mata nor match part of any already active schemata, then GENESIS tries to causally connect it to other actions and states in the model using planning information.

The first step in integrating a new schema instance into the model is to add any primary inferences or effects. The effects and inferences attached to a schema are divided into primary and .l'econda,·y categories. Primary ones are used in a forward inferenc· ing fashion while secondary ones are used in a back wards inferenc· ing fashion and only added to the model if they are required by the explanation.

If the new instance is an action, then its preconditions must be reconciled with the model. This means that it first searches the model for each precondition and if it finds it, it adds an appropri­ ately labeled support link from it to the new action. If it does not ftnd a precondition, it next attempts to infer it by searching for secondary effects or inferences which match this precondition. If this also fails, it hypothesizes the existence of an action which can i'X' used to achieve this p~econdition (using the achieving actions attached to this state) and attempts to reconcile its preconditions with the model.

GENESIS also attempts to find motivations for volitional actions. It does this by checking if the action achieves a state which is a goal for the actor, or if it the actor has the specific goals and beliefs marked as possibly motivating this action. Goals which arise from known themes [Schank 77) can be automatically inferred if they will motivate a character's action. Such goals will be called therrw.tic goals and represent the highest level goals which motivate a person. Goals of possessing money, satisfying hunger, and preserving one's health are examples of thematic goals.

2 The term determined is borrowed from FAUSTUS [Norvig83] which also uses a multi-step schema selection process.

Other plan-based understanding systems such as PAM [Wilen­ sky83) used planning information to predict future courses of actions a character might take. However, searching through a space of possible future actions is combinatorially explosive. Conse­ quently, such an approach is intractable if a system's knowledge of actions is large, which it obviously must be if it is to be able to understand a wide range of narratives. For example, if a PAM-like system were used to process the detailed kidnapping narrative, it would conduct an exhaustive search for an explanation of why John captured Mary before continuing to process the rest of the text. If the system had a large knowledge base of actions, it would be a long time before it stumbled upon the idea of using the action of releasing Mary as part of a bargain with another person.

Since GENESIS does not conduct a complete search for an explanation, it is incapable of "understanding" narratives which have large gaps and do not suggest known schemata. When the first kidnapping narrative is processed without a schema for "kid­ napping for ransom," very little of the missing structure can be inferred and the only support links the system can construct are shown in figure 2. As a result, it is unable to answer the questions shown earlier. However, with the same initial knowledge, it is able to understand the second narrative because the gaps and missing int"ormation are not too severe. Consequently, the understander is

able to construct the support network shown in figure 3. It should be noted that the support networks shown in this paper (called highesr-level support networks) contain only the highest level sche­ mata which were determined to be in the narrative. Most of the representation at the level of the inputs and their connecting infer­ ences is contained in the expansions of the CAPTURE and BARGAIN schemata which were activated bottom-up from the inputs.

As indicated earlier, this structure is then generalized into a new schema. When the first narrati ve is processed again, Bob's action of imprisoning Alice in his basement determines a CAPTURE schema, and this in turn suggests the new "kidnap" schema. The new schema is then used in a top-down fashion to fill in missing information. It is finally determined when both of the effects of the BARGAIN: Alice becoming free again and Ted receiving money, are added to the model. The final support network (the expansion of the ne~· schema for this narrative) is shown in figure 4. This causal structure allows the system to answer the questions it could not answer before learning the schema.

VI THE GENERALIZATION PROCESS

Once a causally complete explanation has been constructed for a narrative, GE?\ESIS determines whether or not it can be used to learn a useful new schema. If so, it generalizes the causal struc­ ture in the model into a new schema and ·stores it in the schema library where it can be used in the processing of future narratives.

A. When to Generalize

If every combination of actions the system encountered was generali?.ed into a new schema, the system would soon become over­ loaded with rarely used schemata. Most actions would activate a large number of schemata and selecting among these would require an excessive amount of processing time. In order to avoid this prob­ lem, ,-enain conditions must be met before a combination is general­ ized.

First, the combination of actions shnuld achieve a goal for one of the characters in the narrative. In the process of motiYating anions, the understander checks if an action achie\·es a goal for a character. so finding achie\·ed goals is a simple matter of inspecting the moctel. Second, this goal should be a common one which is likely to be encountered again. A goal is considered to be common enough if it is a thematir goa l, for example satisfying hunger or acquiring money. Since in the sample narrative John achieves the thematic goal of possessing money, it satisfies both of these condi­ tions.

The final condition for generalization is the obvious one of not already possessing a schema for the combination of actions which ad1ieves the thematic goal. This simply involves checking the highest-level support for the achievement of the goal and making sure it contains a combination of actions. If the system already had a schema for th1s case, it would have used it in processing the nar­ rati ve and the goal would be supported by an instance of this schema instead of a combination of actions. Additional conditions for generalization were discussed in [DeJong83~ however, these are currentl y not implemented.

B. Generalizing the Support Network

After deciding to generalize, the system extracts the explana­ tion for the goa l state, isolating the actions and states which actu­ ally contribute to its achievement. This simply involves extracting the highest-level support for the achieved state. In the example, the achieved state is John possessing $250,000 and the support for this state is shown in figure 3. This step eliminates extraneous informa­ tion in the narrative which does not contribute to the achievement of the goal, such as the fact in the example that Mary was wearing blue jeans.

Once the support network is extracted, there are several steps involved in constructing a generalized version of this causal struc­ ture. The overall approach is to initially generalize as far as possi­ ble and then re-introduce only the constraints necessary to main­ tain the causal connections bet ween schemata and the well­ formedness of individual schemata. Initially, the class of each schema instance is generalized to SCHEMA (the highest level in the hierarchy) and each role filler is replaced by a unique new parame­ ter. Constraints are then imposed on this over-generalized structure to make it a well-formed causal network. These constraints progres­ sively refine the class of each instance and constrain certain role fillers to be equal.

First, the goal which the support network achieves is con­ strained to be a thematic goal. This is accomplished by constraining it to match the pattern for the thematic goal which was achieved in the original narrative. In the kidnapping example, this con­ strains the goal state to be the kidnapper acquiring money.

Next the interschenUl constraints are imposed. These involve maintaining the validity of each connecting support link in the network. We will use the kidnapping narrative to illustrate this process by showing how the FATHER relationship in its support net­ work is only constrained by the explanation to be a POSJm·E-JPT (for posi tive-interpersonal-theme, a superclass of rARENT, SPOUSE. etd. tvery time a support link is adde.d during understanding, it is annotattd with the pattern from the schema library used to con­ struct it <md thf class in the schema hierarchv where it was inher­ ited from. In the example, when GENESIS infers that Fred wants Mary frt t more than he want.~ to have $250000 as a secondary inference f'rom the fact that he is her father, it annotates wilh the corresponding inference pattern from the schema library and the fact that this inference was inherited from the schema POSJTI\'E·IPT. When the interschema constraints for this link are imposed, the ransom payer's GOAL·PRIORITY is constrained to match the system's inferen(.'t patttrn, and the instance which was a FATHER state in the original narrative is constrained to be a POSJTJVE-JPT. Thus, the sys­ tfm only Imposts tht required relationship between the individuals filling the roles of kidnap victim and ransom payer. The fact that there was a specific father-<iaughter relationship in this particular narrative is recognized as incidental and not crucial in maintaining the validity of the explanation.

Next, the intraschenw constraints are imposed. These concern maintaining the well-formedness of each individual schema instance. This is accomplished by imposing on the filler of each role the appropriate role constraint from the schema library. For exam­ ple, since the role constraints specify that the SUBJECT of a POSSESS schema be a PERSON, the SUBJECT role filler of each POSSESS schema in the support network is constrained to be a PERSON.

The final step in constructing a generalized support network is to merge parameterized instances which have been constrained to be equal. The resulting instances form a set of conceptual roles for the overall schema. In the example, this collects together all the indivi­ dual occurrences of the kidnapper, the victim, the ransom payer, and the ransom money and creates a unique OBJECT for each one.

The result of this generalization process is a general causal structure which achieves a common goal. The generalized support network generated for the kidnapping example is shown in figure 5.

C. Packaging Into a New Schema

The final step in acquiring a new schema is separating the generalized support network into preconditions, effects, expansion schemata, etc~ which can be added to the schema library. Following is an outline of how this information is extracted.

Roles (with constraints): The subject of the achieved thematic goal becomes the actor of the new schema. New roles are created for each remaining person and object in the generalized sup­ port network. In the example, roles are created for the kidnapper, victim, ransom payer, and ransom money.

Preconditions:

Motivations:

STATES which are leaves of the general­ ized support network but not motivalions of actions by the main actor. In the exam­ ple, the ransom payer possessing the ran­ som money is a precondition.

STATES which are leaves of the general­ ized support network and motivalions of actions by the main actor. In the example, the kidnapper wanting to have money is a motivation.

VII RELATION TO OTHER WORK

The process just described uses a database of background knowledge to generalize the causal structure or explanation of a single example. This approach differs dramatically from most approaches to learning (e.g. [Michalski83, Mitchel178, Winston70)) in which generalization is accomplished by extracting features \\" hich are shared by a number of examples.

GENESIS' genera lization process is most similar to the method used by STRIPS to generalize planning sequences into new MACROPs [Fikes72~ However, unlike STRIPS. GENESIS generalizes actions and states as weJI as objects and locations, and generalizes the order of independent actions (since it uses a dependency net­ work instead of a linear ordering of steps).

The general technique used by GENESIS. explanatory schema acquisition, is also being applied to learning theorem proving stra­ tegies [O'Rorkeb4l robot assembly tasks [Segre85l and concepts in physics problem solving [Shavlik85~ Explanatory schema acquisi­ tion is closely related to a growing body of recent work in ex planation-based or analytic learning [Minton84, Mitchel183, Silver83, Winston82l which is characterized by learning from a single example through the analysis of its causal structure.

However, there are also important differences between expla­ natory schema acquisition and some of the other work referenced above. While GENESIS learns from the problem solving behavior of other agents, STRIPS and Mitchell's LEX learn from their own problem solving. Although learning from external behavior makes a system less autonomous, it allows a system to learn plans which are beyond its own ability to generate. In addition, LEX only learns heuristics for apply ing operators it already possesses and not new combinations of operators which achieve important goals (MACROPs or schemata). Although Winston's system, like GENESIS, learns from short narratives, it learns if-then rules and not schemata. In addition, Winston's system does not need to infer causal connections during "understanding" since all causal connec­ tions are given explicitly in the input text.

Vlll CONCLUSION

Unlike most learning systems, explanatory schema acquisition does not depend on correlational evidence. Thus, it is capable of one trial learning. Also, it avoids the problem of searching through a large space of features for ones which are relevant to a new concept. Only features which contribute to the explanation of an achieved goal are considered for inclusion in the description of a concept. The approach is heavily knowledge-based; a great deal of background knowledge must be present for learning to take place. hnally, the system does not increase its representation power with this kind of learning. The learning results in greatl y improved effiCiency of processing by avoiding combinatoria lly explosive searches.

In the future v.·e plan to address the issue of schema refinement. Clearl :;. the system ought to have the capabi lity of r~fming existing schemata if the system is presented w ith an exam­ ple whit"h violates its expectations. We also hope · to explore language learning. It should be possible to acquire the English names for these new problem solving schemata from context. This direction of parallel and interacting language and concept develop­ m~nt should complement existing work on inducing grammars [Berw ickl\2) and learning to attach new names to known concepts [Se lfridgel\1~

ACKNO~EMENTS

We would like to thank Paul O'Rorke and Alberto Segre for helpful comments on various versi.ons of this paper.