"QUESTION-ANSWER" - A Multipurpose Information System

"QJESTION-ANSWER" - A MULTIPURPOSE INFORMATION SYS'l'Eil

Yu.A.Buchstab and S.S.~nin

Institute of Applied Mathematics of the USSR Acade~ of Sciences,

lloecow, USSR.

the time needed for answering ~uestions that require deduction at the common sense" level.

It should be noted that in case of a large data base there arises a problem associated with that information introdu­ ced into the system may prove to be con­ tradictory. The "QJESTIOli-ANSWER" system employs a special procedure which, on the one hand, makes it possible to remove du­ ring the input a considerable portion of the information which comes in contradict­ ion with the "knowledge"of the system and, on the other hand, allows the system, when answering questions, not to use contradic­ tory information even if it is contained

in the data base.

The creation of a multipurpose in­ formation system employing deductive in­ ference involves the following main prob­

lems: 1.Choice of a language for presen­ ting information and posing questions.

2.Realization of logical inference! i.e. the choice of methods which would a - low carrying out effective logical .analy­ sis of the information known to the sys­ tem with a view to obtaining requested data.

3.0rgan1zation of the data base, i. e. the choice of methods of presentation and arrangement of information in machine memory 1 that would ensure rapid informa­ tion retrieval.

2.LANGUAGE FOR COMMUNICATION WITH THE SfSTEII

In our choice of a communication language we were guided by two principles, the first being maximum simplicity of the language adopted for communication with the system and the second, its sufficient flexibility for the system to demonstrate good "understanding" in most diverse appli­ cations. Usually attempts are made that the language for external presentation of information should be close to a natura1 language, with language of predicate cal­ culus or property li eta serving as the ba­ sis. Evidently, the use of property lists for presenting information is sufficiently convenient for man-system communication, since such a presentation can be regarded as a simplest model of a natural language. On the other hand, presentation of input information with the aid of property lists allows easy creation of a model that will provide faster question answering than with the use of the theorem-proving pro­

cedure.

ABSTRACT

We describe a "'PESTION-ANSWER" informa­ tion system implemented on computer BESII-6 in the time-shared system. The "~STION­ ANSWER" system is capable of deducing facts that have not been explicitly given to it by using a large data base and in­ terpreting some of data as rules of infe­ rence. The system employs a special pro­ cedure which allows not to use contradic­ tory information even if it is contained

in the data base.

1.INTRO:WCTION

The "'PESTION-ANSWER" system deve­ loped at the Institute of Applied Mathe­ matics of the USSR Acade~ of Sciences is capable of accepting various information and, by using such information, it can answer questions posed to it. New informa­ tion received by the system broadens the stock of its "knowledge" and, hence, wid­ ens the scope of questions the system can answer. The "QUESTION-ANSWER" system is multipurpose, since the field of its ap­ plication is not fixed beforehand, being determined by the contents of the informa­ tion introduced into the system. When ans­ wering questions, the system carries out logical analysis of the information avail­ able to it; in the course of such analysis the system deduces new facts that are not explicitly given to it. Thus, the system not only searches the asked-for data among the particular facts known to it, but also carries out deductive inference interpre­ ting some of the received information as

rules of inference.

When developing the present system, we have taken into account the experience gained in the creation of other deductive information systems such as "Advice Taker" of J.McCartb.Y (1)· "SIR" of B.Raphael (2); "SQA." of 11'.Black ~3); "DEDUCOM" of J.Slag­ le (4); "QA.3" of C.Green (5); "RDF" of R. Levien and M.Maron (6); etc. Evidently, the main factors which determine the pos­ sibility of practical application of a de­ ductive information system are the volume of the data base the system can effective­ ly use and the high-speed of the programs that realize logical inference. In this connection, when developing the "~STION­ ANSWER" system, we tried that it should combine the possibility of accepting a lar­ ge bulk of factual data with an ability of an effective carrying out of the logical analysis of these data, so as to minimize The basic language structure of the "QUESTION-ANSWER" system for forming sta­ tements and questions is a triple ~attri­ bute.> <object> <.value> ( <a> <o> <V> for short). Such a notation means that an at­ tribute <a> of a~ object with the name .co> has the value <v> · For instance, the fact that the colour of a car is blue can be expressed by the following triple: COLOUR CAR Bl1JE. An essential feature of such presentation of information is that in the description of properties of an object by means of attribute-value pairs we use "words" whose meaning is defined generally speaking, within the framewor~ of a natural language. Properties are ascribed to an object which is defined by an individual name. An individual name can also be used as a value of a certain attribute, and therefore descriptive structures of a:JJ:f degree of complex:l. ty can be created. Though words of a natural language can be used as individual names of objects, these words must be maximum unique in the sense that passing over from one object to another should always cause a change of the name. In this con­ nection the use of special standard names of objects is allowed, these standard na­ mes being words of the form C1,C2,C3 1 .... On request of the user the system de 1vers a current free standard name and al­ so inhibits the use of the name whose number exceeds the current value.

Besides triples proper, the langu­ age also permits the use of negational i.e. structures of the form FALSE <tr ple>. Thus, in the description of particular information, employed as statements are triples, negations, and also composite statements having the form P1 AND P2 (where P1 is a triple or a negation and P2 is a triple or a negation or a compo­ site statement).

For the system to be able to execu­ te deductive inference proceeding from particular facts known to it, it is nece­ ssary to specify rules of inference. In the present system the rules of inference have the form of conditional statements: Ill' <condition> THEN <consequence> · Triples describing the condition and the consequence besides words contain variab­ les of the form X1,X2,X3, ···· For examp­ le: IF SllALLER X1 X2 AND E~AL X2 X3 THEN SMALLER X 1 X3.

Hence the "knowledge" of the sys­ tem can be defined as a set of facts pro­ vable within the framework of the follo­ wing formal theory.

1. Atoms: words! i.e. strings of letters and/or numera s. ·

2. Elementary propos! tiona: <a"><O> <v> or FALSE <.a><O><V> (where <a> , <o> , <v> are atoms).

• 3· Axioms: a set of particular ele­ mentary propositions known to the system.
• Rules of inference: methods of combining elementary propositions, that

generate new elementary propositions. The rules of inferenc·e have the form: IF A1 AND A2 AND ··· AND Am THEN B1 AND B2 AND ··· AND Bn, where A1 and Bj( 1 ~ i" m, 1 s;j ~ n) are elementary propositions extended by attaching variables X1 ,X2,X3 ··· as addi­ tional atoms.

Elementary questions that can be posed for the system to answer have the form <a> <O> <v> ? and FALSE <a><o><V>? The system can also be asked a composite question consisting of several elementary questions, e.g. COWUR CAR BIDE AND SIZE CAR LARGE? · Possible answers of the sys­ tem to these questions are ''Yes",· "No" and "UNKNOWN". Moreover, the system can be asked questions which require enumera­ tion of answers. Triples in such questions contain variables of the form K1,K2,K3, ··· When answering questions that require enu­ meration of answers, the system selects appropriate values of the variables and thus forms a set of answers. Naturally, a question requiring enumeration of ans­ wers may be composite, and in this case the values selected for the same variab­ les entering in different triples are matched. As the answer to a question re­ quiring enumeration of answers the system delivers a sequence of records in the question format with the values substitu­ ted for the variables. If no appropriate values can be found for the variables en­ tering into the questionlt th~ answer to such a question will be 'Unknown".

It should be pointed out that when a certain particular statement is commu­ nicated to the system, this statement is not entered at once into the data base, but the system itself preliminarily sub­ stitutes it by a question. If the answer to such question is "Yes" or ''No", the system does not accept this fact and ans­ wers, respective!~, either:"Known" or "Statement contra~cts to fact known to system". The system also checks the inco­ ming new rules of inference for novelty and consistency with the "knowledge" it has at the moment. To this end the sys­ tem first of all checks the deducibility of the consequent of a given rule from the conditions determined by its antece­ dent, using the already known rules of inference. The system also checks whether any particular facts contradictory to the rule of inference being checked are dedu­ cible. Thus, the deductive possibilities of the system are used for data input check.

Besides statements and questions, means of communication with the system are furni~hed by prescriptions. The use of prescriptions makes it possible to ob­ tain additional information, change the state of the data base, etc. Particularly, the user can require that the system should present the proof of the answer it gave to the preceding ques­ tion. He can also require that the system

should "forget" a certain particular statement or rule of inference.

3.0RGANIZATION OF THE SYSTEM

All words entering into every in­ coming message are encoded by using a spe­ cial dictionary. Therefore the internal presentation of triples has a simple fixed structure so that such structures can be effectively searched for and compared.

When answering questions, the sys­ tem carries out deductive inference by comparing questions with the consequents of the rules of inference and processes subquestions obtained from corresponding antecedents in the same manner as the questions. First the very tree of inferen­ ce is constructed, with due account of cycles that may originate, and measures are taken that elimination of such cycles should not cause loss of answers. Then the constructed tree is used by the search procedure of "depth-first" type to obtain answers. Preliminary constructing of the inference tree offers a possibility to ig­ nore non-resultant branches in proof pre­ sentation.

As has been noted above, when dedu­ cing answers, the system does not employ contradictory information. This is ensu­ red by storing the current situation after the obtaining of answers to each subques­ tion and by making an attempt to obtain answers to the negatign of a given subques­ tion. If answers to the negation of the subquestion are obtained, contradictory answers are excluded from the list of ans­ wers to the sub question proper. The revea­ led contradictions are stored and can be delivered on request of the user who, to­ gether with the answer to the question, then receives a message about the presence of contradictions in the data base.

One of the main factors determining the system effeciency is the organization of information files. The "QJESTION-ANSWER" system employs various information structu­ res, namely, lists trees, mixed tables, ordered files. Si;!larly ~o the case of the "RDF" system, the data base in our sys­ tem consists of three files, each of them being ordered with respect to one of the triple positions. This allows rapid rea­ dout of the necessary data. To minimize data recording time, the memory is made two-staged. The incoming information is first accumulated in a special (relatively small) buffer and, after the buffer is fil­ led, this information is merged with each of ~he three files.

4.EXAMPLE

The example given below is a record of a dialogue actually conducted with the "QUESTION-ANSWER" system with the aid of a time-sharing terminal on the computer BESJI-6. Naturally this simple example which is purely illustrative in character demonstrates only some potentialities of the system that is capable of solving far more complicated problems.

In the operation of the "QJESTIOH­ ANSWER" system the answers of the machine are printed with indentions.

15.10.74 17.52.

AT YOUR SERVICE OS IPM YOUR NAME: KB FOR WORK WITH PROBIEII ENTER WORD "GIVE" AND NAME OF PROBLEM GIVE ANSWER WAIT START WORK SPECIALTY ALEXANDR MATHEMATICIAN. UNDEFINED INFORMATION FILE NEW: CLEAR SPECIALTY ALEXA.lrnR MATHEMATICIAN. CLEAR D SPECIALTY X1 MATHEMATICIAN THEN KNOWS X1 FORTRAN. CLEAR KNOWS ALEX.ANDR FORTRAN? YES IF KNOWS X1 X2 AND IS X2 ALGORITBMIC-LAl'l GUAGE THEN CAN X1 PROGRAM. CLEAR CAN ALEXANDR PROGRAM? UNKNOWN IS FORTRAN ALGORITHMIC-LANGUAGE. CLEAR CAN ALEXANDR PROGRAM? YES PRESENT PROOF: ( 1) AXIOIIS: SPECIALTY ALEXANDR MATHEMATICIAN (2) ACCORDING ro STATEIIENT: D SPECIALTI .X1 llATHEMATICIAB THEN KNOWS X 1 FORTRAN FROII (1) KNOWS ALEXANDR FORTRAN (3) AXIOMS: IS FORTRAN ALGORITHMIC-LANGUAGE 4 ACCORDING TO STATEMENT: IF KNOWS X1 X2 AND IS X2 ALGORITHMIC-LANGUAGE THEN CAN X1 PROGRAM FROI4 (2), (3) CAN ALEX.ANDR PROGRAII ALL. IF SPECIALTY X1 MATHEMATICIAN THEN CAN X1 PROGRAK. KNOWN PRESENT PROOF: LET: SPECIALTY C1 MATHEMATICIAN ( 1) AXIOMS: SPECIALTY C1 MATHEMATICIAN (2) ACCORDING TO STATEMENT: IF SPECIALTY X1 MATHEMATICIAN THEN KNOWS X1 FORTRAN FROM (1) KNOWS 0'1 FORTRAN (3) AXIOMS: IS FORTRAN ALGORITHIIIC-LANGUAGE 4 ACCORDING TO STATEMENT: IF KNOWS X1 X2 AND IS X2 ALGORITHMIC-LANGUAGE THEN CAN X1 PROGRAM FROM (2), (3)

CAN C1 PROGRAM ALL

• FALSE KNOWS ALEXANDR FORTRAN. STATEMENT CONTRADICTS FACTS KNOWN TO SYSTEM
• K1 A.LEXANDR K2? . CAN .A.LEXANDR PROGRAll KNOWS ALEXANDR FORTRAN SPECIALTY ALEXANDR MATHEMATICIAN
• CO-WORKER ALEXANDR C100.

PRESENT NAKE:

STANDARD NAKE C100 NOT DEilANDED C63

• CO-WORKER ALEXANDR C63. CLEAR
• NAIIE C63 K1? UNF AJIILIAR WORD: NAME

NAME C63 VLADIMIR AND FALSE KNOWS C63 FORTRAN. CLEAR

Il' CO-WORKER ALEXANDR :X1 THEN KNOWS

:X 1 l!'ORTRAN.

STATEMENT CONTRADICTS FACTS KNOWN

TO SYSTEM

• PRESENT PROOl!': 1 AXIOMS: CO-WORKER ALEXANDR C63 ON THE OTHER HAND: 1 AXIOMS: FALSE KNOWS C63 FORTRAN ALL
• Il' CO-WORKER ALEXAN DR X 1 AND X2 ALEXANDR :X3 THnl X2 X1 X3.
• CLEAR
• K1 C63 K2? CAN C6 3 PRO GRAll CO-WORKER C63 C63 NAJIE C63 VLADD4IR SPECIALTY C63 MATHEMATICIAN (CONTRADICTIONS DETECTED WHEN DEDUCING ANSWER)
• PRESENT CONTRADICTIONS: CONTRADICTIONS: KNOWS C63 FORTRAN

PROVE INCONSISTENCY KNOWS C63 FORTRAN:

(1) AXIOMS:

• CO-WORKER ALEXANDR C63

(2) AXIOMS:

SPECIALTY ALEXANDR MATHEMATICIAN

(3) ACCORDING TO STATEMENT:

• Il' SPECIALTI X1 MATHEMATICIAN THEN KNOWS :X 1 l!'ORTRAN FROII (2)

KNOWS ALEXANDR FORTRAN

4 ACCORDING TO STATEIIENT:

IF CO-WORKER ALEXANDR X1 AND

X2 ALEXANDR X3 THEN X2 :X 1 :X3

FROM (1) (3)

KNOWS C6 _3 FORTRAN

ON THE OTHER HANDa

• 1 AXIOMS: FALSE KNOWS C63 FORTRAN ALL
• FORGET FALSE KNOWS C63 FORTRAN: CLEAR
• SPECIALTY K1 K2 AND KNOWS K1 K3? SPECIALTY ALEXANDR MATHEMATICIAN AND KNOWS ALEXANDR FORTRAN SPECIALTY C63 MATHEMATICIAN AND KNOWS C63 FORTRAN
• END YOU FINISHED WORK AT 18.04.GOODBYE.

5.CONCI.USIONS

The "~STION-ANSWER" system is written in the autocode of the computer BESM-6. The program contains about 9,CXX> instructions. By now the system has been tested in solving a number of problems (particularly such simple but in a certain sense "reference" problems as "Monkey and Bananas", "Mikado" etc.). The system an­ swers questions quite rapidly. Thus, for example, the solution of the "Monkey and Bananas" problem takes about 0.01 second of the processor time. During the tests the data base of the system could contain more than 4,000 statements. Principally the volume of the data base is determined by the capacity of the disc memory and can be substantially increased. Our nea­ rest plans for the development of the system include a certain extension of the language to communicate with it, as well as the use of special heuristics with a view to further imp~ving its work.

we believe that systems of the "~STION-ANSWER" type J1J11'3 prove useful not only for solving information retrie­ val problems, but may also constitute an important component in a number of other systems being developed within the frame­ work of the "artificial intel~~~ence" project, such as systems for erstanding natural language, analysis of scenes, plan ning of actions, etc.