TULIPS - Teachable, Understanding Natural Language Input Problem-Solver

Introduction

It need hardly be said about attrac­ tiveness of NL communications with a pro­ gram. TULIPS's user must not learn speci­ al interactive languages and can pass to a computer not a formali·ed description of the algorithm but a description of the problem itself ( an input for problem­ solving block of the program ). It must be especially emphasised that NL descrip­ tion of a problem can be of the prelimi­ nary informal kind. For TULIPS is imple­ mented as a dialog-system, user is able to specify and supplement this descrip­

tion in case of need.

Thus TULIPS cardinally differs from "traditional" computer program. It is not a detailed formal description of an algo­ rithm for the current user's problem, but a eenerator of such algorithms. It receives as input not a command to acti­ vate known to user strict segment of al­ gorithm, but only a descrihtion of user's problem ( i.e. user sais w at he wants without any specification how it should be done ). Just this property of TULIPS - its ability automatically solve the problem, being told the wording of it - allows to consider the program as AI sys­ tem that automatizes so non-trivial func­ tions of human intelligence as specifying of a problem to the well-formed one and

solving of such well-formed problem.

Highly intelligent work does how­ ever, not only the Solver of TULfPs but also its Analyser. Its goal is to extract from NL (Russian) input the descriptions of problem situations, user's goals, and own duties (represented in utterances both explicitly and imtlicitly). To ex­ tract implicit informs ion the Analyser should take into consideration a context (local and global) of the current commu­ nication process. A local context of NL utterance is an information extracted from the previous input expressions. A global context is defined by models of "abstract" user, "external world 11 as a whole, particular users known for TULIPS, specific problem-domains (of user's acti­ vity), "general duties" of TULIPS, and concret heuristics and other tools relat­ ed to a concret problem-domain or user.

These kinds of models must be intro­ duced because of TULIPS is a widely-ori­ ented system. The program is to solve different kindes of problems in different concret domains and to adapt to subset of Russian being used, specific features of problem-domains and users. This main fea­ ture of TULIPS - wide-orientation - de­ termines all the other its features and, in particular, the approach to NL proces­ sing.

Approach to Natural Language Processing

Natural Language is a social level sign system that is used as a means of intercourse. It exists in a social group of speakers of a given language objecti­ vely - every member of this group should learn signs of NL, rules of their combin­ ing - syntax, and the rules of interpre­ tation and usage NL constructions - se­ mantics, sigmatics, and pragmatics.

However, subset of NL learned by any speaker is specific by lexicon, meanings, and syntactic rules. The process of such a subset forming is a natural phenomenon depending on psychicial and social fac­ tors. At the same time speaker can't handle NL too arbitrarily. If he violates language norms appreciably (Humpty-Dumpty may be mentioned), he will not be under­ stood by others. ~bile language will not perform its fundamental social function - function of a means of intercourse.

Since a dependency of NL processing on a mentioned subjective factor is a real natural phenomenon, it must be taken into consideration in TULIPS model of language processing. Thus, on a conceptu­ al level two basic concepts "meaning" and "sense" reflects, respectively, ob­ jective and subjective aspects of utter­ ance content ( 1 ] ·

The sense concept describes the as­ pects of~meaning that connects to an utterance current speaker (user) in a current real situation, whereas the ~­ (iig corresponds to standard objective a social level) links of sign and:

1. frame and constituent sign structures - syntactic meaning;
2. objects and relations of reality - sigmatic meaning;
3. psychicial (reflective) equivalents of these objects and relations - se­ mantic meaning;
4. activities, caused by speach acts and causing them - pragmatic meaning.

'rhus, in a language communication any speaker relates to an utterance only a portion (sense) of objectively existing meaning - a portion that is the most re­ levant to a current act of speaking. While a hearer (no metter who a human or an artificial system) is to extract from utterance just this sense, to learn not only "what the speaker is saying" but also "what and whet for he intended to

say". NL processing of this kind is refe­ renced here as understanding. To under­ stand an utterance stands for to find thous aspects and portions of a meaning that are the moat relevant to a current context situation, to find speaker's in­ tention and to relate it to goals and activities of hearer.

It is obvious that a necessary fea­ ture of NL understanding (in the sense defined above) is using of data not only on a language but also on a current spea­ ker, concret problem-domain and hearer's activities. That is why the vehicles of an understanding program are to be enough elaborate. They should be able to handle NL utterances, underlying structures, linguistics rules end to be adaptable. Non-trivial problem - in NL communicati­ on - is that of discovering an interpre­ tation the most relevant (with respect to user ayd program) in a current inter­ course ac ·

The Main Blocks of TULIPS

To discover such the most relevant interpretation of an utterance (to learn sense associated with it by user) TULIPS Analyzer - ANAL block - interactes with other blocks of the program. Thus, NL processing invokes the deductive mecha­ nisms of TULIPS, problem-solving abiliti­ es, data represented in the model of ex­ ternal world domains and of user.

Interactions of ANAL with other blocks are two-way ones.ANAL block ex­ tracts an underlying conceptual content of an utterance and relates it to the mo­ dele of current environment, while infor­ mation represented in these modele guides parsing and extracting of the conceptual content (2]. These interactions allow the program to insert NL processing in a total process of functioning.

The guiding of NL processing by con­ text information is one of the fundamen­ tal features of the ANAL block. Another characteristic feature of this block pro­ cessing concerns a method of analysis. ANAL and its sub-blocks - KORF (morpho­ logical analysis) and SYNT (syntactic one) - handle corresponding fragment of an input utterance, being driven by data that describe , (predicts) expected re­ sults of their processing.

Having recieved a prediction a block checks if an input satisfy it or not. If a prediption is satisfied, a result is returned to a parent block.· Otherwise a process of "failure-investigation" is initiated. It should be noted that the scheme of predictive analysis accepted - predictions besides syntactic categories describe semantic ones, references to user's goals and responsibilities of the program - allows to realize the principle of conceptually driven analysis.

Nevertheless a conceptual level ori­ entation (orientation on the "supreme" aspects of a meaning - semantic and prag­ matic ones) must not lead to i~oring of proper linguistic phenomena (JJ. That is why ANAL takes into account syntactic le­ vel characteristics - order of words, projectivity, grammatical agreement, and lexical relations (the powerful apparatus of "lexical functions" l4] is used). The vechicles of analysis implemented and de­ tailed description of surface and deep levels of a natural language are the ba­ sis for discovering of subtle aspects of a meaning, that are hidden from both "non-intelligent" parser and "illiterate" AI system.

The TULIPS Solver - SOLV - is the most intelligent block of the program. Its main task is to plan a solution of a T-problem (i.e. a way to transform initi­ al situation model - S - to a goal one - G) and to execute actions planed. The Solver can plan a solution in both direc­ tions. One of ita main strategies is that of reduction of problems, basic general methode - analogy, induction, abstracti­ on etc.

A problem-solving process is begining with analysis of S and G models, as a ru­ le. At this stage the program makes a de­ scription of a problem - a pair (S,G) more exact. A well-formed T-problem ob­ tained - a triplet (S,F,G) - includes re­ ferences to relevant to a current problem -domain means (F) - problem-solving me­ thods. The second stage of solving (plan­ ning) returns a set of operations that transforms S to G. It is to be remarked that during the planning TULIPS can try to specify a T-problem again. The aim of repeted consideration of S and/or G is to discover some implicit properties of the situations - properties that can be found useful for a solving process. Sometimes TULIPS inquiers user for the aspects of real situations non-reflected in initial wording (and, hence, in S and G).

· As a rule, a prediction describes se­ veral possible results. Any block of the program specifies a prediction lby com­ paring it with input phrases) and returns selected concretized result.

The main duty of SOLV is to solve a T-problem that corresponds to a user's problem, i.e. to plan and acomplish (on the world models) the situation transfor­ mations he has told to the program. How­ ever, the Solver can show its own "acti­ vity" and generate T-problems represented in input utterances implicitly. The first kind of such a problem is a T-problem of sense discovering, the second - automatic extending of linguistic knowledge to com­ Elate understanding of a new type phrase {WL adaptation).

The T-problems mentioned are generat­ ing during analysis of an input when ANAL appeals to the SOLV block. Common for both NL processing and non-linguistic do­ mains is an implicit "super-problem" of teaching. The program's models of user and TULIPS itself contain assertions on a necessity of teaching. Hence the explicit user directions to memorize some new fact are optional.

The Synthesizer - SY.NZ - generates Russian utterances adressed for TULIPS's user (answers, requests etc.). SYNZ is the least elaborated and for the present time temporary block, which uses a few standard patterns to be filled by concret words and phrases.

Koni tor-TULIPS - L"TUL - is, in fact, a problem-oriented extension of LISf for BES:M-6 computer. It implements flow of control among ANAL, SOLV, and SYNZ and embodies some other functions that are characteristic for new programming lang­ uages for AI research ( 5 ] · Moreover it accomplishes memory transformations (see below).

Memory and TeachinB

The problems of knowledge represent­ ation, memory structure, and mechanisms for memory handling are especially signi­ ficant for TULIPS. In a concret seance (the user fixed works with the program in fixed problem-domain) TULIPS utilizes only a small part of its knowledge. A lot of data items - CE (for a "conceptual element"), are irrelevant and some compo­ nents of relevant ones may be smoothly ignored.

To take into account the relevance and validity of data-items the memory - structured set of CEs - is broken into several sub-fields and every CE is marked by a special relevation taf - Hr. In ac­ cordance with the first cr terion for the memory breaking up permanert memory (PSM) that contains unchangable n a ~eance "absolute" data and o~erative memory (OSM) - for data vali during a seance - are introduced. The second criterion - relevance of data in a current domain - is a basis for introduction PSM zones. The total zone contains data that can be used-rn-iny seance. The tarticular zones describe specific proper ies of problem­ domains and individual users.

Information read by TULIPS from part­ icular zones guides NL analysis. Just this information is a vehicle to discover an utterance sense, to take into account both individual features of user speech and specific of language performance caused by problem-domain.

Memory Transformations

To use data from particular zones and data represented in relevant CEs from to­ tal zone ~ULIPS performs some operations on the memory. One of them is the active­ ~~ that makes CEs accesible to the main PS blocks. Active mem~- a set of activated CEs - cont8ins ~ relevant to a current seance CEs. This enables to speed up the necessary information retri­ eval.

An activation is the first stage of any seance. This process is initiated on receiving the first user sentence. A next utterances being processed, the new ope­ rations on active memory are performed. One of them is the reactivation - activa­ tion of CEs that were qualified firstly as irrelevant. This operation corresponds to such a creative human intelligence operation as using of irrelevant (a pri­ ory) information in a quite new domain.

Another operation - refinement - changes activated and already used in a current seance data-items. Refinement as opposed to activation (that rejects or accepts CEs as a whole) implies changing of CE's "body". It deletes irrelevant in a seance portions of CE and irrelevant references to other data-items.

The last type of memory transformati­ on - adaptation - concerns changes of CEs grounding on a new knowledge on the world objects and relations, that the program learns in a seance.

Teaching

The adaptation process changes otll OSM of the program - world model tha s valid during a current seance. For the new data-items to be available later on, all the changes should be memorized in the PSM. Such a memorizing - teaching - is, as a rule, accompanied by rather com­ plicated actions: generalization, partieuler zone determination (zone for memo­ rizing) etc. That is why a teaching is a task of a special MTUL sub-block that can invoke all the program abilities and starts on finishing a seance. The later TULIPS feature, as one can observe, makes the program teaching similar to human sleeping - period of sorting and memoriz­ ing during the day perceived information.

The adaptation and teaching processes may result in changing: 1) recomendations on relevance - for unchanged data-items; 2) data-items as such. If the first kind of teaching takes a place, TULIPS changes either implicit recomendations - locali­ zation in PSM zones, or explicit ones - RTs·. As a new CE should be memorized in some zone of PSM and might be marked by RTs, the same transformations are, as a rule, performed, the changed CEs being memorized.

TULIPS may learn both NL processing and non-linguistic actions - in each of these spheres the same strategies and me­ chanisms are used. Thus, if the program obtains unexpected result it is equally valuable for any sphere of its activity, and "failure-investigator" may be invoked in this case both by SOLV (planned set of actions is impracticable, e.g.) and by ANAL (prediction is rejected).

In the later case TULIPS searchs for a "culprit". As the program "belives" user language competency, it tries to adapt a lexicon and grammer. If meta­ gr~ef - the model of morphologrci! and syn~c ic rules (each rule has a descrip­ tion of its validity and changability) - allows, the appropriate changes are per­ formed. Otherwise the program has to ad­ mit user as a culprit and to appeal to him with a request.

A seance is over, TULIPS sends new NL data into PSM. The concret zones de­ termination is guided by meta-grsmmer: individual divergences from language norms are memorized in particular zone (for a current user), new words and rules may be send into any zone. This strategy allows the program {later on) to take into account features of a current user language-model.

Conclusion

For TULIPS - as for a widely-orient­ ed AI system - both the sphere of prob­ lem-domains and language subset used have, in principle, no restrictions.That is why any a priory embodied knowledge can turn out insufficient. Thus, an abi­ lity to learn knowledge and to memorize them for fUture (teachability) proves to be a necessary feature of the program.

· RT markes not only CE as a whole but also its components. The later (internal) RTs are taken into account during the refinement process.

At present TULIPS sucessfUlly teachs both Russian and the real situations mo­ del actions in the domaines:

1. planning actions (of user) in the simplest life situations;
2. solving of word-formed primary-school arithmetic problems (the initial ver­ sion of TULIPS for this domain - the APRIL program- is described in [6]);
3. Russian-English translation (the new ad hoc version of SYNZ is used).

These domains having essentially differ­ ent criteria of understanding, further experiments are of significant theoreti­ cal interest. To appraise the principles embodied, mechanisms used, and TULIPS universality more precisely the program should be taught to work in new more va­ rious domains.