A Control Structure For A Question-Answering System

Introduction

The author and his colleagues have developed a prototype of a question­ answering system. A document describing the whole system and the considerations that have lead to the design has not yet been published, but will appear before long. As this paper discusses the algorithmic aspects on a fairly abstract level, only a rough sketch of the system's properties is needed. This sketch is given in section 1. In order to be able to give some examples, section 1 also contains a superficial description of some properties of the inverse-of-discourse of our system. The reader should however realize, that this paper is not - and is not intended to be - a description of the system.

Some of the characteristics that seem to be common for all A.I. systems, like the existence of local ambiguities, are also present in our system. In c ontrast to what seems to be customary !'or the construction or A.I. programs, no list-processine language (LISP or one of' its improvements PLANNER or CONNIVER) was used. In the opinion of the author, matters such as automatic backtracking and garbage collection should kept in sight. They may be present only 1mpli­ citly - as opposed to being programmed explicitly - but the programmer should control them, as he controls some stora­ ge allocation mechanism via invocation and termination of procedures, thereby implicitly controlling the size of the

stack.

One of the targets of the project was to reach a clean, well-structured program by means of a "top-down" design method. This }Japer claims to show how the control structure was derived (in an informal way) from a small number of

basic assumptions.

For the notation of the algorithms

P. Medema

Philips Research Laboratories Eindhoven, The Netherlands

in section 6, no formally defined programming language is used. Most of the symbols are borrowed from ALGOL68, the remaining ones are supposed to be self-explanatory. For design and publi­ cation purposes, algorithmic descriptions that are easy to read for human readers are preferred to algorithmic descriptions that can be processed by a compiler.

1. A rough sketch of the properties of the system

The system (called PHLIQA for PHiLips Question An~wering) is able to answer questions formulated in a natural language (English), where the answers to these questions are facts, either to be found directly in a data base inside the system or to be derived from information stored in the data .base.

As in most present day A.I. systems, the claim is not that PHLIQA can under­ stand the full natural language: it is only capable of processing the quest ions relating to the restricted universe of discourse, as dictated by the contents of the data base. However, the system is designed in such a way, that a great part of the program is independent of the actual universe of discourse; this may become clear at the end of this section.

The process that answers a quest·ion, is divided into three subprocesses: the interpretation of the question (resulting in an evaluable expression), the evalua­ tion of that expression (resulting in ~value of the answer) and the formula­ tion of the answer. In the current paper , only the interpretation process is discussed. In order to get a transparent and well-structured program, the inter­ pretation process is too complicated to be performed in one giant step. Between the natural language and the level of the evaluable expressions, a number of inter­ mediate language levels has been designed . The conversion from an expression at a certain language level to its equivalent at the next lower level is perfo r med by program modules called converters. The general and common aspects of the control structure of those converters form the

topic of this paper.

The concrete definitions of the intermediate languages are not relevant to this discussion, and are not given.All these languages have one aspect in common: except for the uppermost level (the natural language) all expressions in these languages are represented as trees. All converters (with the trivial exception of the uppermost one) will have a tree as input and will produce a

(converted) tree as output.

A few words on the universe of discourse: the prototype of PHLIQA contains a small data base on computer configurations and their users. A few properties of both kinds of objects are stored in this data base. For the confi­ gurations there are, among others, the name of its central processing unit model, the number and type of its peripherals and the name of the manufac­ turer. For the users, the data base contains, among others, the company name, the street address and country of the site.

To come back to the point of the universe-of-discourse dependence, mentioned earlier: the possible structures of the tree (in other words: the different types of branchings of its nodes) are universe-of-discourse inde­ pendent. The only nodes that do have universe-of-discourse dependence, are the terminal ones, which represent constants (e.g. for certain sets, ele­ ments of sets, functions on them). A converter is therefore only universe-of­ discourse dependent in so far as it manipulates those constants explicitly. An example may clarify this point: a certain sub-tree may represent a expression, the semantics of which are verbally given by"for the set of all configurations, apply the function "name of the C.P.U. model" to the elements of this set, and consitute the set, consis­ ting of the results of this function­ application". Now, the construct"run through all elements of a set, apply a function, and build up a new set from the results" is universe-of-discourse independent, where the concrete set "configurations" and the concrete function "name of the C.P.U. model" are universe-of-discourse dependent.

2. Basic assumptions

2.0. In order to be able to develop the algorithmic structure or the converters, a number o1" design decisions have to .be made. Some or them are axioms: they have to be postulated at the beginning.Other design decisions only arise due to the actual selection of' the set of'. axio~s. We will . start ~ith our set of' axioms, and bec ause we are not going to treat them in a formal way with correctness proof's, we prefer to call them basic assumptions.

1. Each converter will perform its task by means of' transformations, opera­ ting on a sub-tree and producing the lower level equivalent of that sub-tree. (In most cases, only the top node of the sub-tree is involved.) When all possible sub-trees have been transformed, the c onverter is ready.

2.2. A basic difficulty in all A.I. systems is the existence of ambiguities. In our system, we may have ambiguities inside any c onverter. A converter may perform more than one transformation on a certain sub-tree without being able to decide which transrormation(s) is (are) the correct one(s). These branching points in the program constitute the decision tree. After having selected a certain decision (a branch at a branching point of the decision tree) a converter may meet another ambiguity, leading to a new branching point in the decision tree. The design decision made here is twofold : (1) our system allows for ambiguities in~ converters, and (2) in some way or another, all possibilities at a certain branching p~t are elabo­ rated systematically. There might or might not be any prererence for the order in which the transformations are "tried", but all of them should have their turn at soon as their predecessors fail.

1. The back-tracking mechanism, necessitated by the ambiguities, may be implemented in several ways. We choose for a set of (recursive) normal proce­ dures - as opposed to co-routines - whern each transformation procedure contains three parts:
2. the transformation proper
3. the activation of the next transformation
4. (J) the cancellation of (1)
5. Within a converter, the possible transformations will have no internal static order. In other words, as soon as we require that transformation T1 prece­ des transformation T2, T1 and T2 have to belong to different converters.
6. As a consequence, the program is comple­ tely free to perform any transformation or a converter as soon as it sees that this transrormation is applicable. Furthermore, this assumption allows us to have, for each converter, one central procedure that looks for the applicabili­ ty for all the converter's transforma­ tions while it searches the tree.

2.5. Transformation rules are formulated in the form "if existence condition then if applicability condition then transfor­ ;;;;tion £i fi"· As one can s;;:-those two conditions do not differ with respect to the system's reaction if they hold for a certain sub-tree; their difference (which one could not see from the simple state­ ment given above) is the reaction when they do not hold. When for no sub-tree an existence condition is true, the corres­ ponding converter is ready; the complete expression is given to the next conver­ ter, if any. When for a certain sub-tree the applicability condition is false (and necessarily the existence condition is true) this means that the correspondng sub-tree cannot be transformed: the process is in a dead end of the decision tree. The system should then back up to the previous converter. Some converter may use special cases of this general construct: the topmost converter, which will be called the parser below (althoug~ it does more than just a syntactic parse)

does not have an existence condition for separate sub-trees, or rather, the existence condition is always true as long as the complete input question has not yet been reduced to one syntactic symbol.

2.6. Transformations are done in a bot­ tom-up order with respect to the posit~n of their operands in the tree. A node will be transformed if all its descen­ dants are either transformed already or do not need a transformation.

J. Basic assumptions clarified by examples.

A certain converter inside the system has to replace certain sets by other sets. E.g. the set "computers" does not exist at the data base level; it has to be r·eplaced by either the set of "configu­ rations" or the set of "C.P.U.s". The transformation, mentioned in 2.1, is simple in this case: a sub-tree repre­ senting "computers" is replaced by another set. The ambiguity of assu~ption 2.2 is also present here: the replacement can be done in two ways. The general structure of the transformation procedur~ given in 2.), will for example look like

~ 1) replace "computers" by "configurat:icnS' 2) activate next transformation J) replace "configurations" by "com-p.ltals'' The net result of the execution of this procedure is nil, but succeeding trans­ formations will process the correct tree, because they are activated from the central point of their predecessors, and not at the end,

Assumption 2.4 says that there is no problem whatsoever to replace in the same converter the set "users" by " c orporations". However, it is dangerous to combine the replacement of "computers" by "C.P.U.'s" and the replacement of "C.P.U.'s" by "model names" in the same converter. The search process would then have the task to scan the whole tree, as soon as one of the converter's trans­ formations has been performed. The existence condition, mentioned in 2.5, is very simple in this case: if there is an occurrence of the set "computers" in the tree, the existence condition for this converter holds. The applicability condition could in this case look for the context of the sub-tree to be replaced, It is conceivable that the set "C.P.U.'s" does not fit in the context, where "configurations" would fit. We then say that the applicability condition for the first transformation is false, while it is true for the second transformation.

4. Further design considerations

4.1. When designing a general control structure, one of the fundamental deci­ ::;iuns to bo made is how the system should l ' l'a" t when a sub- tree has more than one applicable transformation. We will PlalHlrat.o on two alternative approaches:

• ( 1 ) select one of the transformations and perform it; the process has to be backed up to this selection point to perform one of the remaining alternatives;
• defer the selection decision and see if there are other sub-trees for which only one transformation is applicable.

Although this paper mainly deals with the second alternative (sections 5 and 6) we will make a few remarks here that are either valid for both approaches or only apply to the first a~proach. The first alternative is well knwon. It can be characterized by saying that the program uses a depth-first strategy.Its use in the current system is justified by the additional observation that for some converters, on almost all occasions, the number of applicable transformations is 1. This suggests that the perfor­ mance of the depth-first strategy is not much worse than the performance of other strategies, while it avoides the bookkepping overhead of those strate­ gied.

1. The central procedure mentioned in 2.4, to be called "condition procedure", will have to search the complete tree. Therefore, this condition procedure will use recursion; at any moment, there will be as many instances of the procedure as the current node has ancestors in the tree. As soon as an applicable trans­ formation is round, this transformation is performed (4.1-1).
2. The activation of the new search process from a point inside a transfor­ mation procedure may be done by a recur­ sive call of the whole converter, which always starts with an invocation of the central condition procedure. There are as many instances of' the converter active as there are successful trans­ formations.

4.4. As soon as the condition procedure finds a dead end (which means that there is a sub-tree for which the existenc e condition holds and the applicability condition does not hold, see 2.5), all existing instances of the current conver­ ter have to be terminated.

5. The flexible decision tree strategy

5.1. As stated before, a decision point or a branching point in a program is a point where a decision has to b€ made with respect to the next action to be performed, and more than one action turns out to be feasible (in our Q.A.­ system: when a sub-tree has more than one applicable transformation). So far, all well-known strategies have one property in common: the order in which the decisUn points are passed is dictated by the structure of the algorithm. Given this structure and a particular input and a decision at a certain point, the next decision point is completely determined.

Moreover, when the algorithm arrives at this point, it has to make a decision bef'ore it is able to continue. The points in the decision tree have a fixed order.

The alternative strategy we wish to elaborate in this section is called the method or the flexible decision tree. This means that a new decision point is not necessarily added to the decision tree when the algorithm meets it. A decision point may remain "dangling" Cor a while, and be added to the decision tree at a later, more appropriate moment, preferably at a moment that sufficient information is available to make the co rrect decision.

The main argument for this method is to have an elegant way to improve the overall efficiency. Take the very simple example or a decision tree with two branching points A and B, where A happens to have (for some actual input) 2 alter­ natives and for B only one decision is possible. We will prefer a tree where B precedes A. In that case we perf'orm the actions Collowing point B only one, whereas in the case that A precedes B, the actions rollowing B are performed twice, viz. once for each branch of A. Thus, the main philosophy behind the me­ thod is to defer decisions as long as one possibly can afford. It will be cle~, that such a deferment only takes place if the number of' possible decisions is g reater than 1. In all cases where only one decision can be taken, this should be done immediately. Hopefully, such dec i­ sions will decrease the number of alter­ natives at other branching points.

We should realize that the name "Clexible decision tree" is appropriate only with respect to the original level of considered decisions. The def'erment or a certain decision is the consequence of a (non-deferred) decision, existing one meta-level higher, These "meta decisions" are ordered in a fixed decision tree, just as each algorithm has its t'ixed decision tree, dictated by the structure or the algorithm. At this meta-level, it is again true that the algorithm has to make a decision ( concerning whether or not to defer a decision of the lower level) before it is able to continue,

5.2 . The flexible decision tree strat~ implies the necessity or an explicit (data) representation fo~ decisions, because the program has to manipulate them. Other strategies do not need such a representation; their decision points .arc implicitly present in the program.

A decision point is characterized by two things: the sub-tree to be trans­ formed and the set of appli cable trans­ t'ormations f'or that expression. When a sub-t ree is encountered f'or the first time, a condition procedure will tell which transrormations are applicable, if any. Af a later stage, the property or a decision point may change, i.e. the number or still applicable transforma­ tions may decrease, or one or the trans­ Cormations may have been selected. Let us therefore decide that the represen­ tation of a decision point consists of a reference or the top node of the corres­ ponding sub-tree, a list of references to still applicable transformations and possibly the selected transformation. 5.). The results o.f the f"lexible decision tree strategy (in terms or the eCf'iciency of the complete program) might be impro­ ved if decisions influence each other.If' a certain transformation produces inCor­ mation that is a help for previously deferred decisions, by means of reducing the number of alternative transformations at that decision point, it is certainly worthwhile to make use or this extra information.

In general, it means that the condi­ tion procedure for its evaluation not only makes use or the information or the sub-tree concerned, but also uses inCormation or other sub-trees. In our system, where the Clexiblc decision tree strategy is used during the (bottom-up) parsing process, we have a clear example or such helpful extra inCormation, viz, the (syntactic) context oC the nodo to be reduced,

The existence or such helpful inCormation implies, that the conditions may include terms or which the truth value is not known, because the corres­ ponding information is not yet available. This implies that the evaluation or these conditions has to be done in a three­ valued logic: "true", "false", and "unknown".

5.4. If we do have dangling decision points, what is the appropriate moment to reconsider them ? One could think of a very general control structure where all dangling decisions are reconsidered as soon as any other decision has been made, This set-up will presumably lead to inef'Ciciencies because decisions aro then reconsidered many times, without new infor~ation becoming available, A better approach is to let decisions tell which other decisions they might influence,and to reconsider only the indicated deci­ sions.

Instead of developing a general "theory" Cor these influences, we will see immediately what this means in the c ase or a bottom-up parser. It is immediately clear that two neighbours (two consecutive terms in a partially reduced sentence) might in1'luence each other: one or them might belong to the context that is needed to make a cor r·ec t decision f'or the other. A success1'ul transCormation on a certain node (in this case: a syntactic reduction or another parsing decision) is the appro­ priate occasion to re-evaluate the cond i ­ tions f'or its neighbours.

5.5. As long as we cannot prove that fo1 · all the sub-trees to be transformed a situation will be reached in which only one transformation is applicable, the system's control structure should be able to handle those ambiguities. Their number might decrease by an intelligent use of helpful information, bot they do not - at least in our system - complete­ ly vanish. This means that the program has to make an (arbitrary or "best"} choice for one of the dangling decisions. In that case, it will use the strategy to select the decision point having the lowerst number of alternative transfor­ mations. This strategy is used by human beings when they solve cryptarithmetic puzzles and keeps the decision tree as small as possible. The selection of the next sub-tree to be transformed can now be done by one selection process, both f o r unambiguous and ambiguous sub-trees. As unambiguous sub-trees only have one applicable transformation, they will automatically be selected prior to any ambiguous sub-tree.

6. The algorithm of a flexible decision tree parser

6.0. In this section, we will show the program for the flexible decision tree strategy, as applied to the bottom-up parser of our system. 'The decisions of the parser relate to syntactic nodes. In con~ to the other converters of the system, the parser produces sub-trees on which itself has to operate, as long as the final reduction to the syntactic node "sentence" has not yet been made. Each time a new syntactic node is produced, its corresponding decision point is added to a set of dangling dec isions, called "DAD". Obviously, when the parsing process is ready, this set is empty. The exis­ tence condition for the parser is true, as long as the set DAD is not yet empty. 6.1. A decision point is represented by a structure, declared by mode decision

point = (£.!!.[ ~ trafo t;p,-- [1 :] ref proc trafos ,

£.!!.[ proc condition, int selected, bool trafos known);

The variables "selected" and "trafos known" indicate the status of a decision point. If "selected" I 0, the correspon­ ding value indicates the number in the list of trafos that has been selected.In this case, a decision has been made, so the decision point does not belong to DAn If "selected" = 0, the decision point belongs to DAD. There are however two kinds of dangling decisions: those for which all applicable trafos are known,am those for which that is not the case. (This is the three-valued logic mentioned in 5.).) The difference is indicated by the variable "trafos known". If "trafos known" is false, not enough information was available to determine which trans­ formation were applicable; in that case, sooner or later the procedure in the field "condition" has to be (re- )activatJld.

The re-evaluation of the correspondi ng condition expression may or may not lead to "trafos known" is true. 6.2. The parser starts with the constroc­ tion of decision points for all the words of the input question, and plac es these decision points in DAD·. In algorithmic form, the main progr am o f the parser looks like proc parser =:

for word ~ all words o f inpu t sentence

~ add to DAD (word ) ~; do next action;

end of the parser.

fu'"this program, "do next action" i s the name of a procedure that is the heart of the flexible decision tree strategy; its algorithm is given in 6.4. It is important to realize, that when the program is executed and the semicolon following the call of "do next action" is met, all alt e rnative transformations on all nodes have bee n performed. We could replace the semi­ colon by "; output ("all interpre t ations of the current question have bee n tried");". .

6.). We will first proceed with the procedure "add to DAD". We do not only need it for the words of the input sentence, but also for the (top of t he) partially reduoed subsentence.

proc add to DAD = (£.!!.[~node): decision point dp;

determine the condition procedure, that belongs to this node; apply this condition procedure; its result may be:

true: all transformations that have found to be applicable,are stored in the list "trafos" or dp; trafos known::true;

false: no transformations we;;-;ppl i­ cable, the parser is in a dead end of its dec ision t r ee ; trafos known := true;

unknown: not enough context of this node was available to evalua~

the condition;

this very condition procedure is stored in "condition" o f dp;

trafos known := false; selected of dp := 0; the decis~n point dp is now added to DAD

.2!!£ of the procedure "add to DAD". We will not give the details of the condition procedure; there is one c ondi­ tion procedure for each syntactic cate­ gory and they use more than just synt a c­ tic information. We only remark that they only work with applicability condi ­ tions; the existence condition for the parser is used on one central place,vi z . the procedure "do next action".

6.4. The procedure "do next action" has the responsibility to select the next decision point that has to be added to the decision tree. Each of the appl~cao~

transformations should have its turn. Together with the test for the existence condition, this leads to something like: proc do next action =:

if. DAD is empty

~ the existence condition is not longer true, so activatethe converter that succeeds the

parser ~ among the decision points in DAD with trafos known, select decision point d with the minimum number of applicable trafos; remove d from DAD; for t thru applicable trafos -- --- of d do perfo;; trafo t on node - of d .2£!.; d is added to DAD again

end of procedure "do next action". The central point is this procedure is the activation of a transformation, in the program above stated by "perform trafo t on d", Here again, comink back to the calling program means that all alternatives resulting from transforma­ tion t have been tried, either leading or not leading to a complete interpre­ tation of the whole question, This central point is at the same time the most important point of the structure of the whole program, Due to this invocation of a transformation procedure, which mi~ turn invokes "do next action" (as is shown in 6.5; both procedures are mutually recursive), there is one instan­ ce of "do next action" for each level of the decision tree. In this way, a stack mechanism that deals with recursion enables us to have a clean and correct program that systematically elaborates all alternative transformations. This style of programming, called symmetric programming, was postulated in sub­ section 2,J, In the procedure "do next action", the symmetry shows up in the fact that addition to DAD is the mirror image of removal from DAD. As the reader may have noticed, no special care is needed for dead ends of the decision tree. Such a dead end occurs, when a decision point has no applicable brnn€~ tions at all. Such a decision point will be selected immediately, while it certa~ ly has the minimum number. The loop through the transformations will be performed zero times, so the procedure immediately backs up; another instance of the same procedure will than proceed by performing the next possible trans­ formation related to a decision point higher up in the decision tree. 6.5. The transformation procedures are, in the same way as the condition proce' dures were, dependent of the syntactic category they have to process. We will show the general structure of such a procedure:

trafo = (ref node node): perform th; syntactic reduction from node and zero or more of its left-hand neighbours to a new node n; add to DAD (n), leading to decision point d; do next action; remove d from DAD; delete n;

~ of a transformation procedure. The fact that for the new node a new decision point should by constructed,and that this decision point is added to DAD, should not need any explanation, The symmetry of the procedure, already discussed in 6.4, is more obvious here. 6.6. Not all transformations of the parser produce a new syntactic node: there is one exception. This transfor­ mation, called "shift", transforms the syntactic node into a status that means that the node concerned will not be the rightmost and controlling constituent of a syntactic reduction, Only nodes that have this "shifted" status, may act as (left) context of their (right­ hand) neighbours, This means, that when a node receives this status, this is an excellent moment to re-evaluate the condition procedure of its right-hand neighbour, This brings us to the follo­ wing algorithm:

proc shift = (ref~ node): change status of node to "shifted"; re-evaluate the condition procedure of the righ-hand neighbour of node; do next action; cancel the results of the re-evalu­ ation; change status of node to "not shifted"; end of procedure "shift", 6:7. To illustrate the working of the flexible decision tree parser, the parsing of the question "Does Philips use computers ?" is shown:

DOES PHILIPS USE COMPUTERS

In this figure, vertical and diagonal lines denote syntactic reductions, horizontal lines denote the shift-trans­ formation, (This paper is not the appropriate place to explain to names or the syntactic categorie&) The numbers indicate the order in which the decisions actually were made by the parser. The final reduction has the number 16, which shows that the decision tree has 16 levels. This decision tree is not shown here; the only decisions having more than 1 applicable transformation are those with the numbers 6, 7, 9 10 and 11. Worth noting is that decision 5 (the reduction from COMPUTERS to NOUN) precedes decision 6; in a conventional lof't-to-right parser, decision 5 would huvo been made after decision 11. The deferment of decision 12, although having only 1 applicable transformation for this example, is due to the fact that it needs some context to reach that conclusion. This context is not available before the shift transforma­ tion of decision 11. Actually, about the only gain for the flexible decision tree strategy in this example in the fact that the transformation of decision 5 is performed only once instead of some G times in the case of a conventional parser. Fortunately, more complicated examples lead to better results.

?.Concluding remarks

By means or "symmetric programming", one is able to construct clean, well structured programs for a question­ answering system. The symmetry is possi­ blu because all procedures that perform actions know how to activate the next action; there is a central starting point ror the next action. Procedures ar·e terminated only when their results may be destroyed; this allows the pro­ grammer to store the results as local quantities, leaving the responsibility for storage allocation to the stack mechanism. In the case that an explicit separate stack mechanism is needed, it is easy to program it correctly: due to the symmetry, the statements that care for cancellation are just a few lines lower on the programming sheet than the statements that care for the creation.

The programming language used for implementation of these ideas, should have

• recursion
• structures (records)
• pointers (references)
• r·of'<n·oncoH lo pr·o<'odures (entry vnr·.lablos).

lo'or· our system, wo usod an internal dlaloct of PL/I, tho concreto choise boinc nul too important.

As far as the strategy is concerned, we might observe that intelligent systems should use an intelligent strategy to solve their decision problems; from this point of view, the flexible decision tree strategy is certainly more promising than simple depth-first and breadth­ frist strategies. There exists a striking and attractive similarity between this strategy and the way in which human beings solve certain combinatorial problems like cryptarithmetic ones.

It is clear on the other hand, that the flexible decision tree is not the final solution for decision problems. In the author's opinion, intelligent strategies should have at least adequate solutions for the following two problems:

• to know to what extent decisions arc dependent of other decisions; one could think or an i~plementation in which decisions are no longer linearly ordered in one single decision tree, but where there exist as many separate decision trees as there are mutually independent chains of decisions.
• to know, at a dead end, at which decision point (presumably many levels higher in a decision tree) a wrong decision was made, so that the program can immediately back up to the correct point, instead of trying useless alternatives lower down in the decision tree.