Parsing = Parsimonious Covering? (Abduction in Logical Form Generation)

1 Introduction

Natural languages are rife with ambiguity. There are lexical ambiguities; words in isolation may be seen to have multiple syntactic and semantic senses. There are syntactic ambiguities; the same sequence of words may be viewed as constituting different structures. And fi­ nally, there are semantic and pragmatic ambiguities, all of which may be resolved in context. Ambiguity and its context-sensitive disambiguation, it turns o_ut, are two important characteristics of abductive inferences.

There have been various attempts at characterizing abductive inference and its explanatory nature [Appelt, 90; Charniak and McDermott, 85; Hobbs, et al., 88; Josephson, 90; Konolige, 90; Pople, 73; Reggia, 85, etc.]. While they differ somewhat in details, they all boil down to accounting for some observed features using poten­ tial explanations consistently in a "parsimonious" (of­ ten "minimal") way. Over the past decade, a formal model for abduction based on these ideas was developed at Maryland; this theory is called parsimonious covering. The theory originated in the context of simple diagnos­ tic problems, but extended later for complex knowledge structures involving chaining of causal associations.

*This research was supported in part by the State of Ohio Research Challenge grant to the author.

A diagnostic problem specified in terms of a set of observed manifestations is solved in parsimonious cover­ ing by satisfying the coverage goal and the goal of par­ simony. Satisfying the coverage goal requires account­ ing for each of the observed manifestations through the known causal associations. Ambiguity arises here, be­ cause the same manifestation may be caused by any one of several candidate disorders. Ensuring that a cover contains a "parsimonious" set of disorders satisfies the goal of parsimony. There could potentially be a large number of covers for the observed manifestations, but the "parsimonious" ones from among them are expected to lead to more plausible diagnoses. The plausible ac­ count for a manifestation may be one disorder in one context and another disorder in a different context. Such contextual effects are to be handled automatically by the specific criterion of parsimony that is chosen.

For medical diagnosis, reasonable criteria of parsi­ mony are minimal cardinality, irredundancy and rele­ vancy [Peng, 85]. Minimal cardinality says that the di­ agnosis should contain the smallest possible number of disorders that can cover the observed symptoms. A cover is considered irredundant (not redundant) if none of its proper subsets is also a cover, i.e., if the cover contains no disorder by removing which it can still cover the ob­ served symptoms. Relevancy simply says that each dis­ order in the cover should be capable of causing at least one of the observed manifestations.

Consider an abstract example where disorder d1 can cause any ofthe manifestations rn1 and rn2; d2 can cause any of rn1, rn2 and rna; da can cause rna; d4 can cause rna and rn4; and finally, ds can cause rn4 . If the manifesta­ tions {rn1, rn2, rna} were observed, the disorder set {d2} constitutes a minimal cardinality cover; the irredundant covers that are not minimal cardinality covers are { d1 , da} and {d1, d4}; and an example of a redundant, but relevant cover would be {d1, da, d4}. While {d2, d5} is a cover that has an irrelevant disorder (d5) in it, {da, d4} is a non-cover, since together the disorders in this set cannot account for all observed manifestations.

Several natural language researchers have been ac­ tively involved in modeling abductive inferences that oc­ cur at higher levels in natural language, e.g., at the prag­ matics level. Abductive unifications that are required in performing motivation analysis, for instance, might call for making the least number of assumytions that might potentially prove false [Charniak, 88j. Litman uses a similar notion of unification, called consistency unifica­ tion [Litman, 85]. Hobbs and his associates propose a method that involves minimizing the cost of abductive inference where the cost might involve several different components [Hobbs, eta/., 88]. Although [Charniak and McDermott, 85] indicate that word sense disambiguation might be viewed to be abductive, nobody has pursued this line of research. It is very clear that there exists a strong analogy between diagnostic parsimonious cover­ ing and concepts in natural language processing. There are, however, important differences as well. These sim­ ilarities and differences are summarized in Table 1. We have tried to extend parsimonious covering to address some of the idiosyncrasies of language (contrasted to di­ agnosis) and apply it to low level natural language pro­ cessing.

2 Covering and Parsimony in Language

Linguistic concepts are viewed in parsimonious covering to be much like disorders and manifestations in diag­ nostic problems. However, in order to account for word order and structural constraints in language on the one hand and to account for the lexical and semantic content on the other, two aspects are attributed to each linguis­ tic concept. These two aspects are loosely referred to as syntactic and semantic aspects, respectively. Concepts are covered parsimoniously in these two aspects, and the processes of covering are called syntactic and semantic covering.

The notions of coverage and parsimony are briefly sketched here for syntactic covering through an abstract example here. Unlike in the case of diagnostic covering, the covers in syntactic covering are sequences rather than sets. Consider the following descriptions of categories c1 through cs in terms of simpler categories (or words) w0 through w10 below (sequences are indicated by being enclosed between "<>"):

C}: <wo W} W2 W4 W5 W3 W6>

c1: <w4 w1 W7 wo>

c2: <w1 w1 ws>

ca: <w9 w10>

c4: <w2 W6 wa>

cs: <wo w1>

The categories shown in bold face are mandatory cat­ egories, i.e., categories that must be present for the de­ scription to viably apply to a context. Semantic con­ siderations govern whether a category is mandatory in a description. Depending on the domain, "the patient blind" might still make sense (indicating that the omit­ ted copula is not mandatory), but "the patient" alone does not make complete sense (indicating that for this type of sentences, an adjectival complement is manda­ tory). See [Dasigi, 88] for discussion.

Suppose the input sequence is <wt, w2, wa>. Some valid covers (covering sequences) are <c1 >, <c1, c3> , <c3, c1>, <c2, c4>, <c2, c3, c4>, etc. Some non-covers are <c2>, <c4>, <c2, c3>, <c4, c2>, etc., either be­ cause they cannot account for all the categories in the input sequence or because they cannot account for the correct order. Note that although <c2, c4> is a cover, <c4, c2> is not a cover. For instance, it makes sense to cover "paint the wall" with the sequence <Verb Noun­ Phrase>, but not by <Noun-Phrase Verb>. Irredundant covers include <c1> and <c2, c4>. Of these two irredun­ dant covers, the former is also minimal (i.e., of minimal cardinality) and the latter is not. Insertion of c5 into any valid cover causes it to be a non-viable cover since the category mandatory to cs, namely, W7 is not present in the input sequence to be covered. Thus, <c1, c5> is a non-viable cover.

Consider the cover <c1, c4>. Superficially, it appears to be a redundant cover since c1 by itself is a cover. When the second rather than the first description of c1 is taken into account, however, there is no redundancy in the cover, in a certain sense. For more concreteness, consider the following two classic sentences that differ in a single word:

"John painted the wall with a crack."

"John painted the wall with a brush."

Now, suppose there exist the usual descriptions for noun phrases (Noun-Phrase) and prepositional phrases (Prep-Phrase) . Although in both sentences, the high­ lighted words can be syntactically covered by the irre­ dundant cover <Noun-Phrase>, the sequence <Noun­ Phrase Prep-Phrase> is a more appropriate cover in the second sentence, and we would like to consider that cover as irredundant, too. This characterization of irredun­ dancy is obviously important, and is somewhat similar to the notion of "relevant diagnostic covers" defined in the previous section.

For the sake of completeness, we briefly describe the salient features of semantic covering. A detailed account and algorithms may be found in [Dasigi, 88]. The con­ ceptual objects manipulated by semantic covering are domain-specific semantic senses. For semantic covering, the order of the concepts being covered is no longer im­ p_orta~t. Semanti~ covering involves discovering the rela­ twnships underlymg the domain-specific entities evoked by input words, so that a parsimonious semantic cover can be sy~thesized for them; this cover corresponds to the logical form of the original sequence of words. There a~e t":o types of semantic covering. The first type of covermg mvolves covering individual content words b~ domain-speci~c senses corresponding to objects, at­ tnbu~es! etc. This type of covering involves only lexical assoc1atwns. Here, a domain-specific entity semantically covers a content word if any of the content words in the name or synonyms of the entity is morphologically re­ lated to the word itself or a domain-specific or domain­ independent synonym of the word.

The other type of semantic covering is based on the relationships in a domain-specific semantic network. A s~mple dom~in-specific eritity may be represented by a smgle node m the semantic network, e.g., an attribute. Also, a non-atomic subgraph of the semantic network can repres;nt a more complex domain-specific entity, e.g., an assertwn that relates an attribute and a possible value for it. Either kind of domain-specific entity - whether represented by a single node or by a subgraph in the domain-specific semantic network - is said to be covered by an?' of it~ supergraphs. Since any super-graph of a dom.am-specific concept can cover it, for any domain­ specific concept there are potentially a huge number of covers, some of which are very redundant. There should be some means of controlling the number and sizes of potential covers. Criteria of parsimony and other con­ straints are used to achieve this control.

A criterion of parsimony called cohesiveness is chosen inspired by the fact that in order to be understandable' text must be cohesively connected. A set of semanti~ categories are designated as assertionals (loosely corre­ sponding to the notion of a sentence or an independent clause in English). A semantic cover corresponding to a non-assertional category is considered to be cohesive if it is the smallest (in terms of nodes) connected graph covering the concepts in question. A semantic cover cor­ responding to an assertional category is considered to be cohesive if either it is the smallest connected graph covering the concepts being covered or it is a not necessarily connected graph of several such domain-specific entities belonging to assertional categories. If there is more than one unconnected cover for the same concepts, the small­ est conne.cted cover of such unconnected components is the cohesive cover. It can be seen that cohesiveness refers to the "size" of the covers, and it is similar to "minimal cardinality," used in early versions of parsimonious cov­ ering theory for diagnostic problems. Indeed if minimal­ ity were to be extended to structured entities it would be similar to cohesiveness above. Cohesivenes~ refers to how. we~l a cover fits into its surrounding context, a gen­ erahzatwn of the notion of minimal cardinality applied to structured entities. '

Consider two consecutive concepts that have the same domain-specific entity (say an object) as one of the many candidate covers. Since both concepts can be covered by the same entity, the entity is a minimal cover for both of ~hem to~ether. This example of parsimonious covering IS essentially the same as minimal covering in the unex­ tended ~arsimonious covering theory for diagnostic prob­ lem solvmg. However, suppose the two concepts involved ca.n~ot be cove~ed by the same domain-specific entity. A m1mmal cover m t?e unextended parsimonious covering theory would consist of any pair of entities (pair - be­ cause there are two words to be covered) such that each entity in the pair covers one concept. But when struc­ tured e~tities with semantic associations among them are. considere.d, the .entities in the pair must also unify, takmg domam-spec1fic associations into account . 1 Uni­ fication of such structures corresponds to a search in the ?omain-specific semantic network, say, by marker pass­ mg [Charniak, 83] .

One impor~ant remark about semantic covering is in order: Cohe~Iven~ss? as a notion of parsimony for se­ mantic covermg, IS mtended to capture how plausible a semantic cover is. But it is possible that a cohesive cover might turn out to be implausible when checked for well-formedness. Because of this possibility, there should b.e means to recompute the next most plausible ( cohe­ stve) cover. Thus, whenever a cohesive cover is found all the irredundant covers must be saved so that the s~ace of possibilities they constitute can be explored for co­ hesiveness if the cohesive cover that was found were to be rejected later. Consider the following abstract exam­ ple. Let :z:1, :z:2 , :z:3, :z:4 and :z:s be the senses of one am­ biguous linguistic concept and y1 , y2 , y3 and y4 be the senses ?f another concept. If these two concepts were syntactically covered together by an open class semantic category, then semantic covering will be initiated. Now, what needs to be semantically covered is the conjunction of the following two disjunctions (representing 5*4 = 20

1 This can be understood as follows: An assertion may be viewed . as a predicate assert(?v,?a,?o), where ?v, ?a and ?o are. va~tables s~ch that ?v is a possible value of attribute ?a, which m turn 18 an attnbute of object ?o. If one of the con­ stituents is covered by a specific value vl and the other is covered by a specific attribute a2, the covers effectively spec­ ify the ~sertions ass:rt(v~ , ?aa, ?oo) and assert(?vv,a2,?ooo) , respectively. Now unificatiOn may be performed in the usual sense.

combinations):

{x1 2:2 X3 2:4 2:5} and {Yl Y2 Y3 Y4}

Suppose a cohesive cover is found between x2 and Y3. Then the irredundant cover will be constituted by the following three conjunctions of disjunctions (which rep­ resent the remaining 19 combinations):

{ x1 x3 2:4 xs} and {Yl Y2 Y4} {x2} and {Yl Y2 Y4} {x1 2:3 2:4 xs} and {y3}

If the cohesive cover that was discovered gets rejected, the next most cohesive cover might be computed from these irredundant covers.

Semantic covering interacts closely with syntactic cov­ ering. Irredundant syntactic covering has a very nice property, namely, when complete sets of irredundant syntactic covers are considered, they are transitive across any number of layers when more than two layers of cover­ ing (e.g., as in typical parse trees) are involved [Peng and Reggia, 87; Dasigi, 88]. However, for a sequence of items, the number of irredundant covers at the next layer grows exponentially [Dasigi, 88] . Heuristics are needed for fo­ cusing search in such an ocean of covers, and semantic considerations serve this role. In the space of irredun­ dant syntactic covers, search would be focused on "plau­ sible" semantic covers. Thus, the two routes of covering aid each other by syntactic covering providing a search space for semantic covering, and the latter focusing fur­ ther syntactic covering at the next layer. Integration of the two routes of covering is facilitated by attributing both syntactic and semantic categories to distinguished linguistic concepts, called open class concepts. 2 In gen­ eral, if the category that has just been postulated as a cover happens to be an open class category, it initiates semantic covering, thus integrating both the routes of covering.

3 Some Examples

A significant prototype was implemented to apply this algorithm in the context of an interface to an expert system. Instead of syntactic categories such as nouns, verbs, noun-phrases, etc., semantic categories were used in the syntactic covering process. Semantic covering was performed using domain-specific concepts defined in a knowledge base used by the expert systerr ·. In an OPS5style expert system language, domain-specific concepts such as, patient , vision, blind, etc. were classified into semantic categories such as objects ( obj) , attributes (attr) , values (val), etc. Two application domains were considered; the first domain is characterized by a sizable, prototype neurological knowledge base and the other deals with a toy chemical spills knowledge base. Some examples that were successfully handled by the proto­ type interfaces are:

"Visual acuity is blind." "Visual acuity is blind on the left."

2 This notion is very similar to that of open class words in languages. Non-open class concepts only have syntactic aspect, and correspond to "syntactic sugar" in language. See [Dasigi, 88] for more discussion.

"Babinski on the left. Right unremarkable." "The water is brown, radioactive and oily. Its pH is basic ... "

These examples demonstrate the use of lexical infor­ mation, limited ability to handle ungrammatical sen­ tences, interpretation of sentences in a discourse con­ text rather than in isolation, etc. Note that the first few words of the first two inputs are the same. Their interpretations are, however, significantly distinct in the context of the knowledge base that was used, illustrating a form of non-monotonic inference in text interpretation. All but the last input is from the neurology domain and the last one is from the other.

A very simple example of parsimonious covering is given below to convey the flavor of the approach; more detailed examples of dual-route parsimonious covering may be found elsewhere [Dasigi, 88; Dasigi, 90]. De­ tails are omitted due to space considerations, and we ap­ peal to the reader's intuition in making sense out of this brief example. Suffice it to say that the category assert (and its variations) corresponds to sentences or clauses; obj and attr (and their variations) correspond to noun phrases; and val (and its variations) correspond to noun phrases or adjective complements. The category asg­ verb stands for "assignment verb" (e.g., "is"). There are different ways an assert may be described in terms of the other categories mentioned so far. Often, val is a mandatory category in describing an assert (that is, it is unlikely that an assert makes semantic sense if a val is not present). Now, suppose a sentence begins with

"Vision is ... ,"

and is to be covered syntactically. One sequence of ter­ minal categories that cover the first two words in this sentence is <attr, asg-verb> among others, since vi­ sion is an attribute and the word "is" is an instance of asg-verb. Since, this is an embedded sequence of what is expected of the above description of assert , the cat­ egory assert is postulated to be a non-viable syntactic cover for the first two words. It is a cover because the two semantic categories occur in the description of as­ sert, in the correct order. But the cover is non-viable nevertheless, because, not all mandatory categories in this particular description, namely, val, have occurred yet. When all expected mandatory categories occur, the cover will be considered viable. Further, viable or not, the cover is tentative because other possible covers exist and one of the other covers might prove to be globally more plausible. Now, suppose the sentence ends as fol­ lows:

" . . . impaired."

Then, since impaired is a domain-specific value, the mandatory category is also encountered; so assert is confirmed as one of several viable syntactic covers for the given words. To keep things simple for the present purposes, it is assumed that assert turns out to be the most plausible syntactic cover.

The covering category in this example, namely assert, was designated as an open class category. In general, if the category that has just been postulated as a cover happens to be an open class category, it initiates seman­ tic covering (with the standard notion of compositional­ ity), thus integrating the use of both (that is, syntactic and semantic) aspects of knowledge. Now, we continue the example from the viewpoint of semantic covering. Recall, however, that this process is interleaved with syn­ tactic covering, and does not necessarily follow it. See Figure 1.

The word "vision" is covered, among other things indi­ cated above, by a concept that has the semantic category attr. Category attr is of open class and so not surpris­ ingly the concept that covers "vision" also has a domain­ specific entity, say a12, that uniquely characterizes it. In effect, this one linguistic concept covering "vision," has two facets: the semantic category attr and the domain­ specific entity a12. Similarly, the word "impaired" is covered by, among others, a· concept of the semantic cat­ egory val that has the unique domain-specific entity, say v30, associated with itself. The verb "is," however, is covered by a concept of the category asg-verb and since asg-verb is a not an open class category, it does not have a corresponding domain-specific entity.

As already explained in the course of syntactic cov­ ering, assert is computed to be a syntactic cover; it also turns out to be a parsimonious syntactic cover. For semantic covering, what needs to be covered is the set of entities grouped under this category, i.e., a12 and v30, by identifying domain-specific associations that re­ late them. Definitions of parsimony and covering in the semantic route attempt to capture these intuitions, and the concept characterized by the assertional, semantic category assert and the domain-specific entity consti­ tuted by

(attr=a12, val=v30)

becomes the integrated parsimonious cover for the given sequence of words.

4 Discussion

The ability of parsimonious covering to handle ungram­ matical sentences, as exemplified earlier, does not call for any special (or ad hoc) handling. It is a natural conse­ quence of the very definition of covering itself. One could argue that a conventional production rule approach may easily be augmented to achieve the same effect. For in­ stance, it might be possible that a description such as:

assert : attr asg-verb val,

where val is mandatory, can be encoded into the follow­ ing production rules:

assert -t attr asg-verb val I attr val Ivai I ... ,

the number of such rules can grow exponentially in the number of non-mandatory categories.

The previous paragraph should not be misconstrued as downplaying the significance of syntax in language. Indeed, the verb is plays a crucial role in disambiguating sentences such as,

"Flying planes is/are dangerous."

Our point is that omission of the copula in such sentences still does not make them incomprehensible. It does leave the sentence ambiguous, to be sure. At present, the se­ mantic covering process does not worry about number agreement between the verb and subject, unless ambigu­ ity arises. The underlying assumption here is that people try to make sense, and are not always grammatical. 3

In summary, parsimonious covering provides a frame­ work to view parsing natural language as an abductive process. A proof of concept is provided by implementing the basic ideas in an application independent interface shell. Admittedly, the semantic knowledge used is very restricted in nature, at the moment appropriate only to an object-oriented class of applications. While the pre­ sumed logical form is also, correspondingly, of a limited generality, in this work, it has allowed for the construc­ tion of an interface shell. Further, it has been noted that an abductive approach to word sense disambigua­ tion may make it possible to define word senses nat­ urally in context using descriptions of scenarios, as op­ posed to rules [Charniak and McDermott, 85; Dasigi, 88; Dasigi, 89].

Many significant linguistic issues remain to be an­ swered in this framework, however. Two features of this preliminary work (namely, use of a semantic grammar­ like descriptions that are closely related to the class of expert systems for which interfaces could be generated, and reliance on the assumption that ambiguity resulting from ungrammaticality is resolvable in context) make it hard to predict the generality of the technique for un­ restricted natural language. Our ongoing work further extends the model in the directions of using regular syn­ tactic categories, and incorporation of further structure into verb definitions (consequently making the logical form much more general) as follows.

3 The majority of test inputs used by the prototype came from physicians' anonymous case descriptions, where insuring the grammaticality of sentences was, apparently, not the first priority.

The logical form employing triples, as in the work de­ scribed here, specifies a value for an attribute of an ob­ ject. Natural language sentences that can be represented by such logical form generally involve stative verbs. Such sentences describe a state rather than an action or an event. While such sentences capture most of the input text to diagnostic expert systems (which was the context in which the prototype was developed) , they fall signif­ icantly short of characterizing open-ended English text, where actions and events are of a great significance. A more general logical form, such as the following as de­ scribed in [Allen, 87], is more appropriate for sentences involving actions and events:

(specifier name type modifiers)

Here, the specifier specifies some detail of the concept (e.g., the tense for actions or events, the quantifier for nominal concepts, etc.), while the name serves to iden­ tify the concept. The concept itself is, to a large extent, characterized by its type (e.g., break-action, statr, per­ son, dwelling, fruit, etc.), while the modifiers, If any, allow for specifying attributes that modify the concept being represented.

The modifiers may involve recursive substructures rep­ resenting other concepts. Such recursive substructures represent the partial semantic interpretations associated ~ith grammatical subconstituents, while the entire log­ Ical fotm represents the semantic interpretation corre­ sponding to the grammatical structure of the entire sen­ tence. The overall logical form covers (i.e., is constructed from) the individual partial interpretations, and it does so "parsimoniously." An appropriate notion of parsi­ mony here seems to be essentially the same notion of "structural minimality" or "cohesiveness" of the seman­ tic structures built, much the same way the notions are u~ed in this paper. It is hoped that this ongoing work Will help answer the important questions raised above.

Acknowledgements

Past support from Jim Reggia of the University of Mary­ land and his comments on earlier versions of this paper are gratefully acknowledged.