Understanding Natural Language Through Parallel Processing of Syntactic and Semantic Knowledge: An Application to Data Base Query
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Natural Language. Pages 663-666.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
This paper describes the main features of the PARNAX system for natural language access (in Italian) to an ADABAS data base. The core of the system is constituted by the ana lyzer that includes paral lel processing of syntactic and semantic knowledge. It is argued that this feature (together w ith the new macro- and micro-analysis technique wh i ch is on ly shortly mentioned in this paper) allowed the system to reach a good linguistic coverage, still ensuring an acceptable degree of efficiency. After the basic architecture and operation of PARNAX have been described, attent ion is focused on the parallel syntactic/semantic ana lyzer which is illustrated in detail. Th e advantages obtained throug h para ll el i sm are also shortly discussed. Examples of PARNAX operation are presented. References to related works are mentioned, and directions for future research are outlined.
- Bobrow R.J., Webber B.L. 1980. Knowledge representation for syntactic/semantic processing. Proc. 1st Annual Nat. Conf on Arti- ficiallntelligence, AAA I, Stanford.
- Courtin J. 1977. Algorithmes pour le traitement interactif des lan- guages naturel/es. These, Universite Scientifique et Medicale de Grenoble. Grenoble, France.
- Guida G., Somalvico M. 1979. A two level modular system for natural language understanding. Proc. Int. Joint Conf on Artificial Intel- ligence Tokyo, Japan, 345-347. IJCAI
- Guida G., Somalvico M. 1980. Interacting in natural language with artificial systems: the DON AU project. Information Systems 5, 333- 344.
- Guida G., Tasso C. 1982. NLI. A robust interface for natural language person-machine communication. Int. Journal of Man-Machine Studies 17, 417-433.
- Hays D.G. 1964. Dependency Theory: a formalism and some ob- servations. Memorandum RM4087 P.R., The Rand Corporation.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
This paper discusses a research project devoted to the design of a robust and effective parser for I tal ian language, that can support a large linguistic coverage, stil l ensu ring an accept able degree of efficiency. The project has been partially based on previous results by the authors (Guida and Somalvico, 1979, 1980; Guida and Tasso, 1982) and presents several original contributions. Among these are: a two-level analysis strategy that includes a macro-analysis and a micro-analysis phase; a model for semantic processing that is made up of two sequent ial phases, namely, a nondeterministic part that va lidates and completes. the activity of a syntactic analyzer, followed by a deterministic part that constructs the output internal represen tation; a parallel algorithm that manages the two cooperating processes of syntactic analysis and the nondeterminist ic part of semant ic analysis.
This research project is supported by the implementat ion of an experimenta l system, ca lled PARNAX, which is presently running in an INTERLISP version on Siemens 7748 at CSELT (Torino, Italy) . PARNAX is a natural language interface to an ADABAS data base conta ining information on the staff of a sample company.
In this paper, attention is focused on the parallel strategy developed for syntactic and semantic processing. At each step during the parsing of an utterance, the syntact ic analyzer proposes cand idate syntactic structures for a component of that utterance that fit the given set of syntactic rules. Similarly, the nondeterministic semantic analyzer constructs candidate semantic structures according to a given set of semantic rules. Among these only those structures that can be associated to a corresponding syntact ic structure are va lidated and will be further considered in the fol lowing steps of the processing. All other candidate structures are discarded, thus considerably limit ing the search space which is actually expanded during the analysis. This enables the system to reduce the nondeterminism of the analysis process, and, therefore, to operate with improv ed efficiency.
2. BASIC SYSTEM ARCHITECTURE
PARNAX allows casual users to access an ADABAS data base in Italian. It translates natural language requests into NATURAL programs (the ADA BAS formal query language) in two steps. First the natural language query is processed by the ANALYZER, that generates a semantic representation expres sed in an internal formalism, ca lled METANATURAL. METANATURAL is an intermediate language which should allow a sufficient degree of independence of the understanding process of the details of the data base logical schema. Then, the FORMALIZER transforms the METANATURAL query into a ful l NATURAL program. This is eventually supplied to the DBMS which provides the user with the desired answer. System tailoring and updating is ensured by a KNOWLEDGE BASE MANAGEMENT SYSTEM.
Figure 1 shows the basic architecture and mode of operation of the ANALYZER, that constitutes the core of the system. The analysis is performed at two levels: the upper level, called macro-analysis, takes into account the outer sentence structure and suggests possible splitting and normalization of comp lex or syntactically unusual sentences into simpler frag ments; the lower level, called microanalysis, parses the sentence fragments and returns the obtained MET ANATU RAL subtrees to the upper level that will compose them into the fi nal META NATURAL tree.
Macro-analysis operation is mainly rul e-based: a set of structural rules of the type< pattern, fragmentation-normalizar -----tion action, composition action > is used both by the fragmen tation and normalization module for analysing the outer surface structure of the input sentence, and by the composition module for building up the output METANATURAL tree. Macro analysis also includes a paraphrase and dialogue module that manages the user-system interaction and generates echoing paraphrases of the input requests.

I
I
I
I
I
I
I
I
I
I
I
I
I
Micro-analysis consists of three phases. The first phase, namely lexical analysis, classifies the elementary components of the input fragment (words or simple constructs and idioms) according to their lexical type. Its operation is based on a nondeterministic finite-state recognizer that utilizes the lexical part of the dictionary, which contains lexical roots and models (Courtin, 1 977). The second phase includes two parallel pro cesses: the syntactic analysis, which is based on the dependency grammar model (Hays, 1964; Courtin, 1977), and the first part of the semantic analysis, ca lled semantic validation . The knowl edge bases utilized in this phase are the dependency rules, the semantic rules, and the semantic part of the dictionary. The result of the syntactic analysis and semantic validation is a set of val ida ted trees. A va l ida ted tree is a mod ified dependency tree, where semantical ly meaningless components have been pruned and appropriate semantic variables have been added. Each node of the tree is therefore associated both to a semantic var iable that expresses the kind of information of the cor responding sentence fragment, and to a pointer to a procedure (semantic modu I e), wh ich wi II be later used to assign the correct value to the variable. The third phase, namely semantic interpretation, is a deterministic process devoted to construct the output METANATURAL tree. It operates through a bot tom-up activation of the semantic modules that are referred to in validated trees, and assignes the appropriate values to the correspond ing semantic variables.
3. IMPROVING NONDETERMINISTIC ANALYSIS THROUGH PARALLELISM
Parallel ism between syntactic analysis and the first part of the semantic analysis (semantic validation) is used in PAR NAX to improve the efficiency of the parsing process. Both syntactic analysis and semantic validation are nondeterministic processes, that can be viewed as problems to be solved by a reduction-to-subproblems mechanism. As far as syntactic analysis is concerned the problem is to construct all the correct dependency trees for a given sentence. This problem, once a word in the sentence has been chosen as a candidate root of the tree, can be splitted into subprobl ems. Each of them consists in finding all the dependency subtrees whose roots (determined through dependency rules) are just one step below the root of the dependency tree corresponding to the basic problem. Many groups of alternative subpr,oblems may arise, since many groups of roots can be generated according to the dependency rules. A simi lar situation arises in the case of semant ic validation, where the problem consists in finding all the correct semantic trees, and the subproblems in finding the semantic subtrees whose possible sequences of roots are determined by the seman ti c rules. Both semantic and syntactic problems could be separately solved by two distinct search processes in their respective search spaces (AND-OR graphs), which are general ly very large.
Our choice is to solve both prob lems in a joined way, using two parallel, step-by-step search processes in the two search spaces. To this purpose a correlation between the two search spaces is necessary. This is defined in terms of an associa tion criterion among problems in the two spaces (which is generally a many-to-many relation) . According to this, for each problem P in one search space only those reductions of P are taken into account which have at least one association among the possible sets of successor problems of the problem P' associated, in the other space, with P. Thus, most of the search for non existing solutions (semantic trees without correspond ing syntactic t rees, and viceversa) is avoided, with the desired result of constructing, with considerably minor effort, only the set of the semantic trees which are also syntactically valid (val ida ted trees).
In the current implementat ion of PARNAX the parallel processi ng strategy above outlined is realized in a sequential way in whi ch syntactic and semantic steps alternate in the analysis, due to the limitations of the available INTERLISP system.
4. AN EXAMPLE
A simplified example of paral lel syntactic/semantic process ing is shown in Figure 3. The focus is centered on one step of the analysis concerning the segment "NATI A TORINO PRIMA DEL 1958" (for the english translation refer to the Appendix).
Lex ica l and semantic types are extracted from the dictionary and are self explanatory. For what concerns the structure of semantic rules, taking rule I as an example, its meaning is the fol lowing one : a segment convey ing the informa tion @ SELECTION (i.e., how to se lect an object from a set) must contain a word of lexical type "verb" and semantic type "AT" . inside that segment the information @VALUE must be found (it is underlined) while @DATE and @COMPARATIVE may possibly be found, in any order. F-13 is the pointer to the semantic module used during the bottom-up activation of the semant ic interpretation phase. The structure of dependency rules is evident considering rule 1 as an example: an adverb may be the dependent of a verb; the weights (-20, + 1 0) deter mine the possible positions of the dependent (Courtin, 1977).
At the point of the analysis shown in Figure 3, two associated problems are considered: the former (P) consists in looking for a dependency tree rooted in "NATI "; the latter (M) consists in looking for a semantic tree rooted in @SELECTION. They are reduced to five and four subproblems respectively. Only subproblems SP 1 and SP3 can be associated to subproblems SM 1 and SM3 ·respectively. All other subproblems are pruned since no problem in { SM2, SM4 } can be associated to some problem in { SP2, SP4, SP5 }. The analysis continues with problems SP1, SP3, SM1, and SM3, but on lySP1 and SM1 wi ll lead to the solut ion (boldface in Figure), while SP3 or SM3 wi ll fa il in following steps.
5. THE POWER OF PARALLELISM
Some empiri ca l experimentati ons have been done to estimate the benefits obtained through parallel executi on of syntactic and semantic processing. Two samples A and B of about 50 and 30 sentences respectively have been considered. A has been chosen from a set of sentences proposed by casual users; B has been constructed to contain a broad spectrum of different ways of expressing the same request. Each sentence in the two samples has been parsed first using the syntactic analyzer alone (I). and then using the parallel syntactic/seman· tic processor (II) thus generating the complete validated trees as well. The following parameters have been est imated: cardinality of the syntact ic search space expanded in both cases I and II , and analysis time for syntactic processing alone in case I and parallel syntact ic/semanti c processing in case II. The mean va lues of the ratios of the above parameters in cases I and II (case 1/case II), for both samples A and B, have been computed. The tabl e of Figure 2 illustrates the resu lts obtained.
Note that the sum of the time requ ired for both syntacti c and semantic analysis (performed in parallel) is less than the time needed for the syntactic analysis alone. We also out I ine that the benefits of parallel processing increase with the length of the sentences.
| Sample A | Sample 8 | |
|---|---|---|
| CARDINAL ITY RATI O | 1.81 | |
| ANALYSIS TIME RATIO | 1.36 |
6. EXPERIMENTAL ACTIVITY
An experimental version of PARNAX has been fu l ly implemented at CSEL T (Torino, Italy) in the last two years. The system is connected to an ADABAS data base containing information on the staff of a sample company. It supports free Italian language interaction (including single sentences as well as sequences of interrelated utterances). and is able to deal with ungrammatical sentences, ellipsis and telegraphic forms, a class of anaphoric references, and multiple queries. PARNAX can also engage the user in a limited dialogue, that includes echoing user's request with a system generated paraphrase, presenting alternative interpretations when reference ambiguities occur, and asking the user for validation of the proposed interpretation in the cases where other interpretations could exist.
PARNAX is written in INTERLISP and is running on Siemens 7748. PARNAX dimensions are about 300 kbytes for algorithms and 350 kbytes for knowl edge bases (the present version includes about one thousand lexical roots, 9 structural ru les, 130 dependency rules, 70 semantic rules, and 27 semantic modules). The average time needed to parse an average-length sentence (9 words) is approximately 3 CPU seconds (without accessing the DBMS).

Figure 4 reports a short dialogue with PARNAX. Figure 5 shows a small sample of different ways of expressing the same request (all of which are correctly understood by PARNAX) that should give an idea of the linguistic coverage of the system. For the English translations of the examples refer to the Appen dix.
| COGNOME | NOME | CATEGORIA |
| ·Rossi | Mario | |
| Verdi | Claudio | D |

- > dimmi l'anno di nascita dei dipendenti laureati
- > vorrei sapere l'anno di nascita di tutti i laureati
- > dimmi quando sono nati i dipendenti che sono laureati
- > anno di nascita laureati
.
- > vorrei sapere qual e l'anno in cui sono nati tutti quei dipendenti che hanna conseguito Ia laurea
- > vorrei sapere I 'an no di nascita dei dipendenti con titolo di studio laurea
- > dimmi in che anno sono nati colora che sono laureati
- > dimmi l'anno in cui sono nati i dipendenti in possesso di laurea
- > dimmi l'anno di nascita di chi ha conseguito Ia laurea
- > dei laureati dimmi I 'an nodi nascita
- > dei dipendenti che sono laureati voglio sapere l'anno in cui sono nati
- > cerca i dipendenti il cui titolo di studio e laurea e comunicami l'anno in cui sono nati
- > qual e Ia data di nascita dei dipendenti che hanna Ia laurea?
- > qual e l'anno di nascita di quelli che si sono laureati
- .>. qual e I 'an no di nascita dei dipendenti che so no in possesso di Ia urea?
- > laureati anno nascita
Fig. 5 -A sample of different ways of expressing the same request.
7. CONCLUSION
The parallel syntactic/semantic analyzer developed within the PARNAX project shares some features with the RUS/PSI KLONE System (Bobrow and Webber, 1980). Although an in-depth comparison of the two approaches is difficult, two major differences seem worth being outlined:
The way in which syntactic and semantic processing interact, which is strictly step-by-step sequential in RUS/PSI-KLONE and far more oriented towards a real parallelism in PARNAX; The structure of semantic analysis, which is intended as a single process in RUS/PSI-KLONE while it is splitted in two bases, namely nondeterministic validation and deterministic interpretation in PARNAX.
Among most promising research directions that deserve further attention we mention the refinement of both syntactic and semantic models used by PARNAX to better fit the issues of parallel processing, and the study of improved parallel strategies.
As a concluding remark we note that the use of parallel search algorithms that utilize several and diverse sources of knowledge is not limited to the analysis of natural language but represents a core topic in many AI problems and could be of interest in several applications.
APPENDIX
Figure 3: List the employees born in Turin before 1958 Figure 4:
- > count the employees in the computer science department born after 1949 and let me know their professional category
- the request contains two queries:
- number of employees having department computer science and birth year greater than 1949:
- professional category of the employees having department computer science and birth year greater than 1949:
- > what is the level of those among them who received a doctor degree
- level of employees having department computer science, birth year greater than 1949, and doctor degree:
Figure 5:
- > tell me the birth year of the employees with a doctor degree.
@inproceedings{ijcai1983p159,
title = {Understanding Natural Language Through Parallel Processing of Syntactic and Semantic Knowledge: An Application to Data Base Query},
author = {Comino, R. and Gemello, Roberto and Guida, Giovanni and Rullent, Claudio and Sisto, L. and Somalvico, Marco},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {663--666},
year = {1983},
note = {Natural Language},
url = {https://ijcai.org/proceedings/1983/159},
}
TY - CPAPER TI - Understanding Natural Language Through Parallel Processing of Syntactic and Semantic Knowledge: An Application to Data Base Query AU - Comino, R. AU - Gemello, Roberto AU - Guida, Giovanni AU - Rullent, Claudio AU - Sisto, L. AU - Somalvico, Marco T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 663 EP - 666 UR - https://ijcai.org/proceedings/1983/159 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: