Using Answer Set Programming and Lambda Calculus to Characterize Natural Language Sentences with Normatives and Exceptions

Please download to get full document.

View again

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 0 | Pages: 6

Extension: PDF | Download: 0

Related documents
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (2008) Using Answer Set Programming and Lambda Calculus to Characterize Natural Language Sentences with Normatives and Exceptions
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (2008) Using Answer Set Programming and Lambda Calculus to Characterize Natural Language Sentences with Normatives and Exceptions Chitta Baral and Juraj Dzifcak School of Computing and Informatics Arizona State University Tempe, AZ Tran Cao Son Computer Science Department New Mexico State University Las Cruces, NM Abstract One way to solve the knowledge acquisition bottleneck is to have ways to translate natural language sentences and discourses to a formal knowledge representation language, especially ones that are appropriate to express domain knowledge in sciences, such as Biology. While there have been several proposals, including by Montague (1970), to give model theoretic semantics for natural language and to translate natural language sentences and discourses to classical logic, none of these approaches use knowledge representation languages that can express domain knowledge involving normative statements and exceptions. In this paper we take a first step to illustrate how one can automatically translate natural language sentences about normative statements and exceptions to representations in the knowledge representation language Answer Set Programming (ASP). To do this, we use λ-calculus representation of words and their composition as dictated by a CCG grammar. Introduction Having a knowledge base and being able to reason with it is an essential component in many intelligent systems. However, developing knowledge bases or acquiring the knowledge to put in the knowledge base is time consuming and is a bottleneck. For example, one of the challenges identified by phase 1 of Project Halo 1 was: Knowledge and question formulation requires highly specialized and expensive personnel (knowledge engineers), which pushes the development cost to about $10,000 per page. As a result one of the main focuses in its phase 2 was developing tools for acquisition of knowledge. We echo that knowledge acquisition is a bottleneck to developing intelligent knowledge based systems. We think one way to tackle this bottleneck is to develop ways so that knowledge expressed in natural language, say in a book, can be automatically translated to sentences in an appropriate knowledge representation language. Partially supported by ONR grant N and NSF grants and Copyright c 2008, Association for the Advancement of Artificial Intelligence ( All rights reserved. 1 Existing and ongoing research in natural language semantics have explored automatic translation of natural language sentences to sentences in first-order logic. Some of these translations (Moldovan et al. 2002; Bos & Markert 2005) have been used in question answering systems that have participated in the TREC QA competitions (Voorhees 2006). The first one did very well in these competitions. However, as was recognized by AI researchers very early in the AI history, first-order logic is not appropriate for expressing various kinds of knowledge. In particular, knowledge used by intelligent systems and their reasoning involves representation of and reasoning with default statements (e.g., most birds fly ), normative statements (e.g., normally birds fly ), exceptions (e.g., penguins are birds that do not fly ), etc. and these can not be adequately expressed in first-order logic. This has led to the development of several non-monotonic logics. Among them, answer set programming (ASP) or logic programming under the answer set semantics (Marek & Truszczyński 1999; Niemelä 1999) has been known to be a good candidate for knowledge representation and common sense reasoning (Baral 2003). More importantly, there exists a number of good (and free) ASP reasoning systems 2. Since representation of knowledge in many domains requires the ability to express defaults, normative statements, and exceptions, our goal in this paper is to take a first step towards automatically translating natural language statements to theories in ASP. To achieve our goal, we take the following approach. We start with a small set of sentences which we would like to be automatically translated. We give a CCG grammar (Steedman 2001; Gamut 1991) for those and other similar sentences and present an equivalent BNF grammar. We introduce the notion of λ-asp-expressions that combines ASP rules with λ-expressions and then present λ- ASP-expressions for the various categories in our grammar. We then show how sentences built using our grammar can be systematically translated to an ASP theory by applying the λ-asp-expressions of the various words (and their categories) in the order dictated by the CCG grammar. To make this paper understandable we give a brief background 2 E.g., smodels ( and dlv ( 818 of ASP, CCG and λ-expressions. Finally we conclude and discuss how to go beyond the first step in this paper. Background Answer Set Programming We use a broader meaning of the term answer set programming (ASP) than originally used in (Marek & Truszczyński 1999; Niemelä 1999). By ASP we mean logic programming under the answer set semantics. We consider ASP as one of the most developed knowledge representation language for the following reasons. ASP is non-monotonic and is expressive enough to represent several classes of problems in the complexity hierarchy. Furthermore, it has solid theoretical foundations with a large body of building block results (e.g., equivalence between programs, systematic program development, relationships to other non-monotonic formalisms) (Baral 2003); it also has a large number of efficient computational tools. Default statements and various forms of exceptions can be naturally represented in ASP (Gelfond & Leone 2002). We now review the basic notions in ASP. We assume a first order language L. Literals are constructed from atoms in L. A positive (or negative) literal is of the form A (resp. A) where A is an atom in L. An ASP program (or program) is a set of rules (ASP rules) of the following form: a a 1,...,a m, not b 1,..., not b n (1) where m,n 0 and each a, a j, and b t is a literal in L; and not represents negation as failure (or default negation). For a rule r of the form (1), head(r) denotes a; pos(r) (positive body) denotes the set {a 1,...,a m }; and neg(r) (negative body) denotes {b 1,...,b n }. Intuitively, a rule r of the form (1) states that if all the literals in pos(r) are believed to be true and none of the literals in neg(r) is believed to be true then the literal head(r) must be true. The notion of answer set semantics for ASP programs is defined in (Gelfond & Lifschitz 1988). Let P be a ground program 3. Let S be a set of ground literals in the language of P. S satisfies the body of a rule r if pos(r) S and neg(r) S =. S satisfies a rule r if either head(r) S or S does not satisfy the body of r. S satisfies a program P if it satisfies every rule in P. S is an answer set of P if it is a minimal set of literals satisfying all the rules in P S where P S is obtained from P by (i) Deleting all rules from P that contain some not l in their body and l S. (ii) All occurrences of not l from the remaining rules. A program P is consistent if it has at least one answer set. Given a program P and a literal l, we say that P entails l, denoted by P = l, if l belongs to every answer set of P. ASP and Knowledge Representation For our purpose of this paper, we will focus on default statements with strong exceptions. We illustrate the use of ASP in knowledge representation on some simple examples. 3 Rules with variables are replaced by the set of its ground instantiations. Consider a knowledge base consisting of information about birds, penguins, and some individuals: Most birds fly. Penguins do not fly. Penguins are birds. Tim is a bird. Tweety is a penguin. This information can be represented by the following program P 1 : f ly(x) bird(x), not f ly(x) (2) f ly(x) penguin(x) (3) bird(x) penguin(x) (4) bird(tim) (5) penguin(tweety) (6) It is easy to check that P 1 has a unique answer set: {bird(tim), f ly(tim), penguin(tweety), bird(tweety), f ly(tweety)}. This implies that f ly(tim) and fly(tweety) are entailed by P 1. Assuming that the knowledge base is extended with the information about penguins being able to swim and that most birds do not swim. This information can be represented by the two rules: swim(x) bird(x), not swim(x) (7) swim(x) penguin(x) (8) Let P 2 be the program P 1 with the above two rules. P 2 entails swim(tweety) and swim(tim). In general, a default statement of the form Most members of a class c have property p can be represented by the rule p(x) c(x), not p(x) which states that for every member m of the class c, unless there is contrary information about m not having property p, then m has the property p. λ-calculus λ-calculus was invented by Church to investigate functions, function application and recursion (Church 1936). We assume an infinite but fixed set V of identifiers. A λ-expression is either a variable v in V; or an abstraction (λv.e) where v is a variable and e is a λ-expression; or an application e 1 e 2 where e 1 and e 2 are two λ-expressions. For example, λx.plane(x) λx.x λu y are λ-expressions 4. Variables in a λ-expression can be bound or free. In the above expressions, only y is free. Others are bound. Various operations can be done on λ-expressions. A α-conversion 4 It is well known that predicates and functions can be easily expressed by λ-expressions. For brevity, we will often use the conventional representation of predicates and functions instead of their λ-expression. 819 allows bounded variables to changed their name. A substitution replaces a free variable with λ-expression. A β- reduction could be viewed as a function application, which will be denoted by the For example, results in boeing767 plane(boeing767) λ-calculus has been used as a way to formally and systematically translate English sentences to first order logic formulas. This process can be seen in the following example, taken from (Balduccini, Baral, & Lierler 2008), a translation of the sentence John takes a plane to the logical representation y.[plane(y) takes(john, y)] The λ-expression for each constituent of the sentence are as follows: John : a : λw.λz. plane : λx.plane(x) takes : x)) We can combine the above λ-expressions to create the formula for the sentence. a plane : λw.λz. = λz. = λz. y.(plane(y) takes a plane : λz. y.(plane(y) = λu.(λz. y.(plane(y) x)) λu.( y.(plane(y) λx.takes(u, λu.( y.(plane(y) takes(u,y))) John takes a plane : y.(plane(y) takes(u, y))] λu.( y.[plane(y) y.[plane(y) takes(john, y)] Combinatorial Categorial Grammar Although various kinds of grammars have been proposed and used in defining syntax of natural language, combinatorial categorial grammars (CCGs) are considered the most appropriate from the semantic point of view (Steedman 2001). In building the λ-expressions above, CCG parser output would be able to correctly dictate which λ-expression should be applied to which word. Following (Gamut 1991), a combinatorial categorical grammar (CCG) can be characterized by a set of basic categories, a set of derived categories, each constructed from the basic categories, and some syntactical rules describing the concatenation and determining the category of the result of the concatenation. Moreover, every lexical element is assigned to at least one category. The following is an example of a very simple categorical grammar, called CCG 1 : CCG 1 has two basic categories: N and S. The derived categories of CCG 1 are: A basic category is a derived category; If A and B are categories then the expressions (A\B) and (A/B) are categories; Thus, (N\S), (S\N), (N\(N\S)), (N/S), (N/S)\N are derived categories of CCG 1. The syntactic rule for CCG 1 : If α is an expression of category B and β is an expression of category (A\B) then the concatenation αβ is of category A. If α is an expression of category B and β is an expression of category (A/B) then the concatenation βα is of category A. CCG 1 contains the following objects: Tim whose category is NP and swims whose category is (S\NP ). Intuitively, the category of swims is S\N P means that if an NP (a noun phrase) is concatenated to the left of swims then we obtain a string of category S, i.e., a sentence. Indeed, Tim being an NP, when we concatenate it to the left of swims we obtain Tim swims, which is a sentence. A Simple Language and its Automatic λ-calculus Based Translation to ASP In this section, we present all the ingredients and illustrate how those ingredients can be used to translate a class of natural languages sentences into ASP rules. Example Sentences We start with a set of sentences containing the normative most and other constructs of interest to us. These are the sentences we used in the previous section. 1. Most birds fly. 2. Penguins are birds. 3. Penguins do swim. 4. Penguins do not fly. 5. Tweety is a penguin. 6. Tim is a bird. In the above sentences, the first sentence is a default (or normative) statement expressing the fact that birds fly by default. The second sentence represents a subclass relationship. The third and fifth sentences are statement about different properties of a class (penguins). The last two sentences are statement about individuals. It should be noted that even though several approaches have been developed to automatically translate natural language sentences to first order logic, none of them translate default statements to an implemented logic (Hella, Väänänen, & Westerståhl 1997). For convenience, we will refer to the above collection of sentences as L bird. We will show how those sentences can be automatically translated to ASP rules. We start with a CCG grammar for L bird. 820 CCG for L bird The CCG for the language L bird consists of the three basic categories: N stands for noun NP stands for noun phrase (representing a class) S stands for sentence NP(obj) stands for noun phrase (representing an object) We will make use of bidirectional CCG, i.e., given two categories A and B, both A/B and A\B are derived categories. The syntactic rules for determining the category of αβ are as follows: (right concatenation:) if α is of category B and β is of category A/B then βα is of category A, and (left concatenation:) if α is of category B and β is of category A\B then αβ is of category A. Observe also that a word can be assigned to multiple categories. The categories for each of the word in the language L bird is given in the following table (words of similar categories are grouped together for simplicity of the reading; the reference column is for later use): Word Categories Reference fly S\(S/(S\NP)) F1 S\N P F2 f lies S\N P(obj) F3 swim S\(S/(S\NP)) S1 S\N P S2 swims S\N P(obj) S3 most (S/(S\NP))/NP M do (S/(S\NP))\NP D1 do not (S/(S\NP))\NP D2 is (S/NP)\NP I1 (S/N)\NP(obj) I2 are (S/NP)\NP A1 are not (S/NP)\NP A2 birds N, NP B1, B2 penguins N, NP P1, P2 a penguin N, NP(obj) AP1, AP2 bats N, NP BA1, BA2 tweety, tim N P(obj) T fictional NP/N F a fictional NP/N FA Figure 1: Words in L bird and their categories The language generated by the CCG is the set of sentences whose category is S. Using the above mentioned combinatorial rules, sentences in L bird can be shown to be of category S (see, e.g., (Steedman 2001)). For example, the derivation of the sentence Most birds fly is done as follows. Most birds is of category S/(S\NP) (applying the right concatenation rule of B2 to M); Most birds fly is of category S (applying the left concatenation rule of S/(S\NP) to F1). Graphically, this derivation is represented as follows: Most birds fly (S/(S\NP))/NP NP S/(S\NP) S S\(S/(S\NP)) Figure 2: Derivation of the category of Most birds fly A Context Free Grammar for the CCG of L bird Each CCG, whose only syntactical rules are the left- and right-concatenation rules, is equivalent to a context-free grammar (CFG) (see, e.g., (Gamut 1991)) which can be used in syntactical checking. As parsing a sentence using a CFG is often more efficient, and for many, more intuitive than using a CCG, we include a CFG equivalent to the CCG of L bird in Figure 3. It should be noted, however, that the CFG lacks the directionality information that CCG has. For example, the CFG in Figure 3 will not tell us how to obtain the semantics (i.e., λ-expression) of most birds from the semantics of most and birds. I.e., whether to apply the λ-expression of most to the λ-expression of birds or vice-versa. The CCG grammar gives us that information. S X 5 X 3 X 6 NP X 11 N X 5 X 7 NP(obj) X 8 NP X 3 X 6 NP X 1 X 11 NP(obj) X 10 X 5 NP X 2 X 4 NP NP X 9 N X 4 most NP birds bats penguins NP(obj) tweety a penguin N birds bats penguins a penguin X 3 fly swim X 2 do do not X 1 are are not is X 7 fly swim X 8 flies swims X 9 fictional a fictional X 10 is Figure 3: CFG for the CCG of L bird λ-asp-expression for Categories in L bird As discussed earlier, λ-expressions can be used to translate natural language sentences into first order logic representation. As our goal is to obtain an ASP representation, we expand the notion of λ-expressions to λ-asp-expression which allows constructs of ASP rules. We then carry over all operations on λ-expressions to λ-asp-expressions. In light of the above discussion, the translation of natural language sentence begins with the development of λ- ASP-expressions for words and categories in the language 821 of interest. For the language L bird, we present the λ-aspexpressions of various categories (a dash represents all categories associated to the word) in Figure 4. Word Cat. λ-asp-expression f ly F1 λx.f ly(x) F2 λ f lies F3 λx.f ly(x) swim S1 λx.swim(x) S2 λx.swim(x) swims S3 λx.swim(x) most M not do D1 do not D2 λuλv. is are A1 are not A2 λuλv. birds λx.bird(x) penguins λx.penguin(x) a penguin λx.penguin(x) bats λx.bat(x) tweety/tim T f ictional F λvλu.f ictional(u) a f ictional FA λvλu.f ictional(u) Figure 4: λ-asp-expressions for L bird λ-calculus + CCG ASP Rules An Illustration We will now illustrate the techniques for automatic translation of several sentences in L bird to ASP rules. Let us start with the sentence Most birds fly. The CCG derivation (Fig. 2) tells us how this sentence is constructed. Namely, birds is concatenated to the right of most to create most birds ; this will be concatenated to the left of fly to create a sentence whose category is S (i.e., a syntactically correct sentence). During this derivation, the category M, B2, and F1 are used for most, birds, and fly, respectively. From Fig. 4, we know that the λ-asp-expression for the category M, B2, and F1 are: M : not B2 : λx.bird(x) F 1 : λy.f ly(y) Concatenating birds to most implies that the λ-aspexpression for most birds is obtained by applying M to B2, i.e., it is the result of or not not which reduces to bird(x), not The λ-asp-expression for most birds fly, obtained by applying the above expression to F1, is: bird(x), not It simplifies to: λy.f bird(x), not λy.f which yields fly(x) bird(x), not fly(x). Penguins are birds. This sentence is obtained by concatenating penguins (P2) to the left of are (A1) and bird (B2) to the right of penguins are. The ASP rule for this sentence is obtained by applying the λ-asp-expression for A1 on P2 and then on B2. The first step gives us: = = penguin(x)) The second step starts with and results in: bird(x) penguin(x) Penguins do not fly. The CCG derivation for this sentence is similar to the previous sentence and the categories involved in the derivation are also similar. ((λuλv. @(λ = f ly(x) penguin(x) We can easily check that rules (2)-(8) are obtained from the automatic translation of the corresponding sentences using the techniques presented in this section. Discussion The grammar presented in this work is sufficient to represent an interesting set of sentences, including default statements and
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!