Recovering Problem-Solving Activities from Query Messages

1 Introduction

In this paper, we focus on trouble-shooting type problem-solving activities. One general way to solve such a complex problem is to know a solution which might solve the problem and to apply it. These days some people utilize computer networks as a forum useful for problem-solving[Hammond, 1995]. Thus understanding how people ask for information with electronic messages will be inevitable to realize an intelligent information access function on information super highways.

With this motivation, we started this work with an investigation of a set of actual query messages, which had been taken from an Usenet newsgroup[Krol, 1993] . The newsgroup chosen as our corpus is "fj.sys.ma.c" 1 , which provides a forum of discussions about Apple's Macintoshes, mainly for J a.pa.nese-spea.king people. We selected forty-two messages, aimed at trouble-shooting, out of 119 query messages which appeared in a three­ months' term in 1993. Each of these selected messages contains a description of the writer's trouble-shooting type problem-solving activity.

2 A Motivational Example

Let us start with a translated and slightly simplified ex­ ample of an actual query message taken from the corpus.

1 Needless to say, there are no particular intentions for the choice.

(Example)

• s1: I found my Mac!! had been infected with

some kind of virus.

s2: So, I wanted to run a vaccine program and

• s3: tried to make my Mac read an MS-DOS formatted 2DD floppy disk.
• s4: However, Apple File Exchanger could not read it.
• sS: Can't Maclls read MS-DOS formatted 2DDs?

The story begins with his/her discovery of a trouble (s1) and ends with a query (s5). Sentences s2 through s4 describe his/her trouble-shooting type problem-solving activity. How can people read this message? From s2, we will be able to guess that, at least for him/her, running a vaccine program is a way to solve the trouble stated in sl. Thanks to the marker "so" in s2, we will be able to guess this, even if we do not have good knowledge about disinfecting computer viruses.

On the other hand, the relation between s2 and s3 seems to be unclear on two points . First, because the two sentences are connected by the conjunction "and", there are two possibilities for interpreting the role of the action described in s3; that is, either running a vaccine program followed by making Mac read a 2DD disk will shoot the trouble, or to run a vaccine program, making Mac read a 2DD disk is necessary. Main verbs in both sentences may provide a slight clue. However, it does not seem to be a strong one. The domain knowledge, in general, might help the disambiguation process. However, if his/her actions were based on his/her wrong belief or knowledge, even correct domain knowledge would not be of help 2 . In either case, it is clearly shown by s4 that his/her trial to make Mac read a. 2DD disk failed and this suggests that he/she still cannot disinfect the virus from his/her Ma.cii.

Note that the entire problem-solving process described in the message can be seen as a goal-directed activ­ ity. The trouble stated in s1 may prevent him/her from achieving his/her primary goal, which is not explicit in the message. Therefore he/she introduces a new goal, disinfecting the virus. The activities described in s2 through s4 are associated with the new goal. In addition, the query stated by s5 can be seen as a step of the problem-solving, although the level differs from the actual activities.

2In this example, his/her doing s3 is actually underivable fwm correct domain knowledge. Most of the response mes­ sages to this query have pointed it out.

3 A Recovery Mechanism

3.1 Overview

Our recovery mechanism consists of three cascaded pro­ cesses. The first process identifies message fragments, each of which describes a single problem-solving step of the entire activity, by recognizing some distinctive sur­ face expression patterns, as in many information extrac­ tion systems[Hobbs, 1992],[Kitani, 1994]. Each fragment is then assigned a sub-graph which represents the struc­ ture of the step by the second process. The third process finally integrates these sub-graphs and represents the en­ tire problem-solving activity as a set of graph structures with help from general knowledge on problem-solving and the associated linguistic heuristics in the discourse structures. Each of the graphs represents a possible un­ derlying problem-solving activity. We call such a graph problem-solving graph, or PS-graph in short.

3.2 Ontology for the PS graphs

In this paper, we assume that a goal state is enabled by one of the alternative goal-achieving actions, and a goal-achieving action is generated by a sequence of de­ composed actions.

There are four node types for the PS-graphs:

• G node: It encodes a goal state of the agent (writer), and may have its value, achieved/unachieved.
• P node: It encodes that a problematic situation (a trouble) came about, and may have its value, fixed/unfixed.
• X node: It encodes an action by the agent, and may have its value, succeeded/failed.
• XP node: It is a composite node by an X node and a P node connected by a causality type link . It en­ codes a causal relation, an action caused a trouble.

We have ten direct link types as shown in Table 1.

• Action type: alternative link encodes the action X is one of the alternative actions which enables the goal

G. Enable link is used in cases where X is the only action to enable the goal. A-step link encodes the action X is one of the decomposed action to achieve the goal G. Generate link is used in cases where X is the only decomposed action. Not-executable encodes the problem P prevents execution of the action X. ·

• Causality type: Caused link encodes the action X caused the problem P. Cause-always link is used when the agent knows a fact that X always causes P which may be an undesirable side-effect.
• Problem-solving type: To-solve link encodes the agent has a new goal state G in which the problem P does not come about. It is automatically intro­ duced whenever the agent knows a problem came about.
• Auxiliary type: Similar link connects two same/similar problematic states. It is typically used in cases where the same problem comes about again, in spite of the fact that a problem-solving activity has been conducted.

4 Recovery of Single PS Step

4.1 Types of problems

We looked through the forty-two objective messages and extracted sixty-three problem description fragments. Table 2 classifies types of the problems. The classifica­ tion was conducted by focusing on following three points:

1. Did he intend to do some action?
2. Did he actually do the action?
3. Is there a problematic situation /sl now?

In the table, example expressions in English and the number of occurrences for each type are also shown. Here, we distinguished two situations:

• F1 (primary): The problem is introduced as a pri­ mary problem for the writer. Because most of the problem-solving activities are described in chrono­ logical order, it appears prior to the other levels of problems in the descriptions.
• F2 (lower-level): The problem came about dur­ ing the problem-solving activities. It mainly de­ scribes a situation where the writer's goal-achieving or problem-solving activity caused the same prob­ lem or introduced a new problem.

Note that we included the problem type (f) in our va­ riety of problem types. In this type, actually, there is no trouble anymore. For the example in the table, the writer fixed the problem (the print process doesn't ter­ minate) by an action (send Ctrl-d to the printer). How­ ever, we can imagine that he/she is not convinced by the solution, and wants to know a better solution. We see human problem-solving in a broader sense than usual.

4.2 Identifying problem descriptions

Table 3 lists expression patterns which can be used for the identification of problem descriptions. By these pat­ terns, 92.1% (58/63) of the problem descriptions in the corpus are covered. Particular modal expressions in Type-A provide the strongest clues; and these are closed expressions.

Here we would like to remark on two major modal expressions which strongly suggest that the associated propositional part of a description describes a problem­ atic situation.

• verb+ "te-shimau": This expression's original func­ tion is to represent the perfect tense. However in many cases, it represents a nuance that the writer thinks/feels that the situation described by the main-clause is undesirable for him/her[Masuoka, 1989]. In this domain, it turns out to be describ­ ing a problematic situation.
• verb + "te-kure-nai": This is a negation form of "te-kureru", which represents a situation where the agent of the verb is not the writer and the associated situation is desirable (empathy in [Kuno, 1987]) for him/her. Therefore, in this domain, its nega­ tion form, "te-kure-nai", represents that the writer thinks the situation caused by a systems/program's behavior is problematic.

In contrast to these expressions, other Types are open expressions. Thus, we must prepare a set of explicit patterns which covers possible expressions in advance.

4.3 Recognizing problem type

The problem types (b) through (f), shown in Table 2, are expressed mainly by conditional clauses/sentences. Ta­ ble 4 lists combinations of expression patterns by which we can map an identified problem description into one of the problem types. In the table, we indicate the patterns as a triple, x-part, connective, and y-part; here, x-part is the antecedent and y-part is the consequent of a con­ ditional expression. The following are brief explanations about the distinctive Japanese connectives which appear in the table with respect to the problem types.

• "-baai" ( = in case of -ing): Use of this connec­ tive suggests that the conditional sentence describes a kind of fact. Thus, it insists that the problem type may be (b), in which an undesirable side-effect caused by an action is described.
• "-nodesuga" : This connective establishes the an­ tecedent (x-part) as a background description. Use of this connective, together with an intentional ex­ pression in the x-part, suggests to us that one of the pre-conditions for the intended action did not hold at the time.
• "-to"(= if/when): This connective is the most com­ mon and neutral one. It corresponds to "ir' or "when" in English.
• "-noni/nimo kakawarazu" ( = even if): These con­ nectives might be similar to "even ir' or "although" in English. As [Masuoka, 1989] discusses, these connectives emphasize that there is an expectation violation for the speaker. Therefore, this type is strongly connected with the problem type ( d2) and (e).

We confirmed that the mapping rule gave us a fairly accurate result (average-recall: 73.0%, average-precision: 90.2%) toward the corpus data by a hand simulation. As the result shows, in the current mapping rule, stress is placed on the precision rate.

4.4 Assigning a sub-graph

By the second process of the mechanism, each of the ex­ tracted fragments is then assigned one of the ready-made sub-graphs shown in Figure 1 according to its problem type. Each situat ion a.nd the associated newly in tro­ duced goal G can be described as follows:

• type (a): He/she has a new goal state G in which the problem encoded in P is fixed.
• type (b): He/she knows that there is an undesir­ able side-effect represented by P. The new goal G is either, execute X without P, or simply solve P.
• type (c): He/she knows that one of the pre­ conditions for executing X did not hold. Hence, he/she believes that X is not executable. To make hold the condition and make X be executable is the new goal.
• type (dl): He/she knows that the action X caused a problematic situation P, and has a goal to solve it . The problem P would prevent achievement of upper-level goals.
• type ( d2): He/she knows that the action X, in­ tended to solve an upper-level problem, caused same problem P again; and he/she has a new goa.! to solve it .
• type (e): [Allen, 1984] introduced a predicate NOT­ TO-DO(a,t,p); it would be true if the plan p in­ cludes not performing the action a at the time t . Like this treatment, we regard not performing the action X intentionally as a kind of action. There­ fore, we link the X' and the P node by the caused link . We can imagine, in this case, that the writer is wondering why the solution didn't work. The new goal G, thus, would be to know the reasons, and the associated information request may be described in the query message.
• type (f): As ment ioned in 4.1, the sub~graph en­ codes an extended problem-solving activity. The newly introduced goal G would be to know a better solution to solve the once solved problem P. That is, the G would be strongly associated with an in­ formation request in the query message.

5 Recovery of an Entire PS Activity

5.1 Overall algorithm

Figure 2 outlines the overall algorithm. The input to the algorithm is a set of sub-graphs provided by the second process. As far as we looked through the set of messages, most of the problem-solving activities are described in chronological order. Thus, the algorithm basically iterates through the each sub-graph in the input set, and constructs a set of possible PS-graphs incrementally 3 .

5.2 Linking sub-graphs

The Base-line

The central part of the algorithm links a current sub­ graph ( c-graph in the algorithm) into a PS-graph be­ ing constructed. The procedure, make-graph-1 , does the job. The crucial point here is which node in the c-graph should be connected to which node in the being con­ structed PS-graph by which type of link.

The answer to the first point is provided by the pro­ cedure, get-top-node. It simply returns the top node in the c-graph as one part of the connection point. Note that we can naturally expect that the returned node is limited to the action type (X node). As indicated in Fig­ ure 1, all the top nodes are X nodes, except for problem type (a) and (f). Because the problem type (a) only ap­ pears in the beginning of descriptions, we don't have to worry about this. In addition, the problem type (f) can be seen as an extension to the main problem-solving ac­ tivity; the top P node would be simply linked to another P node by a similar link 4 .

The answer to the second point is given by the pro­ cedure, get-link-points. Given a PS-graph being con­ structed, it returns possible nodes in the PS-graph which can be linked to. According to the graph ontology intro­ duced by Table 1, G nodes, X nodes and P nodes would be the candidates. However, we can exclude P nodes , as these are provided only by the input to the algorithm. They are already pointed by X nodes, or they are top­ level nodes.

The answer to the third point is provided by the pro­ cedure, check-linkable. Given a pair of nodes which con­ sists a connection point, it returns a type of link to be used. Based on the discussion so far, a possible pair {PS­ graph-node, c-graph-node} is either { G node, X node} or {X node, X node}. As enable/ generate links are special cases of alternative/ a-step links respectively, the proce­ dure returns alternative for the first pair, and a-step for the second pair.

Constraints and heuristics for reducing the candidates

The get-link-points may return more than one node in a PS-graph being constructed as a candidate of the linking points. As this nature is a source of the ambiguities in PS-graphs, it is important to reduce the number of the candidates to avoid the combinatorial explosion.

We can utilize some constraints to exclude inappro­ priate candidates. First, we cannot select the X nodes which are already marked failed as a candidate: the agent cannot perform any action in order to perform an already failed action. Second, we cannot choose the G nodes which are already marked achieved as a candidate. Such G nodes are possible, if the (f) type sub-graph has already been introduced to the PS-graph . These con­ straints seem to naturally come from general schema of

3 For the explanation, the algorithm is slightly simplified. There would be several ways to optimize it .

iWe simply ignore this case in the rest of the paper.

1. procedure recover-entire-PS-activity(sub-graphs)
2. make-graphs ( {car {sub-graphs I ) , cdr (sub-graphs));
3. end procedure;
4. procedure rnake-graphs(PS-graphs,rest-graphs)
5. local-variable· begin rslt-graphs:~{); end;
6. if rest-graphs~~{) then
7. return{assign-values(reduce-graphs(PS-graphs)));
8. for each PS-graph in PS-graphs do
9. rslt-graphs:~rslt-graphs u

rnake-graphs-1 (PS-graph,car(rest-graphs));

1. rnake-graphs{rslt-graphs,cdr(rest-graphs));
2. end procedure;
3. procedure rnake-graphs-1 (PS-graph,c-graph)
4. local-variable· begin
5. rslt-graphs:~{); link-points:~get-link-points(PS-graph); link-relations:~{);
6. end;
7. if link-points~~{) then aignal('link-error-1');
8. for link-point in link-point s do begin
9. link-re l ation:~check-linkable(link-point,

get-top-node(c-graph));

1. if link-relation~~~ then aignal('link-error-2');
2. rs l t-graphs:~ rslt-graphs u

link-graphs{PS-graph,link-point,

c-graph,link-relation);

• 10 . end;
• 11 . return{ r slt-graphs);
• end procedure;

Figure 2: PS-graph construction algorithm.

human problem-solving activities. Third, as a PS-graph is constructed as top-down and left-to-right with time, we can use this constraint to reduce the candidates.

Furthermore, we can introduce some heuristics to prune unlikely candidates. The following are principles 5 which also come from general schema of human goal­ achieving activities:

• Principle of alternative actions: Suppose X1 through Xn are alternative actions to enable a goal G, and are sorted by goodness of the actions. It is natural to assume that the agent will try to perform X;+1 only when he/she failed to perform X;.
• Principle of decomposed actions: Suppose X 1 through Xn form a sequence of the decomposed ac­ tions to generate an action X. It is natural to assume that the agent won't try to perform xi+l if he/she failed to perform X;.

With these principles, the associated heuristics can be summarized as follows: In a situation like Figure 3(a), linking the c-graph to G is allowed only when the X; is already marked failed. That is, failure of X; must be represented in the description. The G nodes which vio­ late this cannot be the candidates. On the other hand, if there is a parallel relation in the associated discourse structure, the linking is strongly preferred.

In a situation like Figure 3(b ), linking the c-graph to X 0 is allowed only when the X; is not already marked failed. The X nodes which violate this cannot be the candidates. On the other hand, if there is a tempo­ ral/sequential relation in the associated discourse struc­ ture, the linking is strongly preferred.

5 Of course, these principles are too strong. However, we confirmed that most of the messages follow these principles.

Linking sub-graphs actually

Given a PS-graph being constructed, a linkable node in the PS-graph, a c-graph and a possible link type, the procedure link-graphs actually links the c-graph into the PS-graph. Figure 3 has already shown how the linking would be done.

However, note that when a c-graph is linked to a G node in a PS-graph, another graph, as shown in Figure 4, must be generated. As mentioned in 3.2, we assume that a goal state is enabled by one of the alternative goal­ enabling actions, not directly by a sequence of decom­ posed actions. But, these goal-enabling actions are often missed in the natural language descriptions. Therefore, to handle such a case, we must assume the existence of a virtual goal-enabling action and incorporate it in the PS-graph. We call such a virtual goal-enabling action virtual action, and denote it as X? in the PS-graphs.

5.3 Post-process

The following are conducted as post-process.

Reducing redundant PS-graphs (reduce-graphs): As enable/generate links are special cases of alternative/a­ step links, this process first checks the alternative/a-step links that do not have sister links and changes them to enable/generate links. As often redundant PS-graphs are constructed due to the virtual action nodes, the pro­ cedure next checks redundant graphs, and preserves the most simple ones only.

Assigning success/failure values to nodes (assign­ values): Based on the principles of alternative actions and decomposed actions, we can assign succeeded/failed to action nodes, achieved/unachieved to G nodes and fixed/unfixed to P nodes in a PS-graph, by propagating explicitly stated success/failure values, which come from the sub-graphs in the input set, along the directed links.

5.4 Trace of the Example

We give a brief trace of the algorithm for the Example in Figure 5. The input set would be as shown in (a) 6 , and the initial PS-graph is provided by SGl.

Main process: SG2 can be linked to GO in SGl, and two PS-graphs, SG4 and SG5, result (shown in (b)). Therefore, the process tries to link the next element in the input, SG3, to both SG4 and SG5 in the next iter­ ation. In SG4, GO and XO are possible linking points, but only one graph, SG6, result (shown in (c)) . SG7 and SG8 are excluded by the heuristic ba.<sed on the principle of alternative actions. On the other hand, in SG5, X? and XO are possible linking points , and SG9 and SG 10 result (shown in (d)).

6 XO is provided by s2. As in the original message, s2 and s3 form the same sentence, XO alone would also be introduced as an element of the input set.

Post process: Three graphs, SG6, SG9 and SG 10 are passed to the post process. By the procedure reduce­ graphs, SG9 is identified as a redundant variant of SG 10; therefore, it is thrown away. Two graphs, SG6' and SG 10' are finally provided as possible PS-graphs (shown in (e)) .

Note that the ambiguous relationship between s2 ("run vaccine") and s3 ("make Mac read a 2DD disk") is clearly captured by these two PS-graphs. Also, we know that the primary problem ("infected with virus" ) is still unfixed in either case from the PS-graphs.

6 Discussion

Clearly, the work reported here has a close relation to the so-called plan recognition. Therefore, it may be worth mentioning our view on the relation here. Roughly speaking, plan recognition in natural language under­ standing has long been studied from the perspective of for hearer, understanding the speaker's utterance is rec­ ognizing the speaker's plan wl1ich generates the utter­ ance, and it is assumed that the hearer and the speaker have same plan library.

This assumption seems to be too strong to handle ac­ tual human dialogues/messages. For one thing, a plan which is valid for the speaker can be invalid for the hearer. Thus, we cannot assume it in actuality. One of the important works which addressed the issue would be [Pollack, 1990]. In the paper, Pollack views plans as complex mental attitudes and discusses how a speaker's invalid plans can be handled in dialogue understanding. Our work reported here was partly inspired by that work . However, as Woods points out in his comment[Woods, 1990] to Pollack, she does not deal with partially spec­ ified plans. As shown in this paper, one can have an incomplete plan in a problem-solving activity. For ex­ ample, one might plan to run a vaccine program in or­ der to disinfect a computer virus without knowing the actual vaccine program. Our notion of the recovery of problem-solving activities can include such cases; incom­ plete plan or precondition failure in the plan recognition enterprise are handled themselves as one of the problem­ atic situations.

Besides this, Woods made another important com­ ment in his essay. He questions the role of surface expres­ sions by introducing an example; "I want to get tenure, so I've rented a car". He says, "the conjunction so unam­ biguously signals the intended goal-achieving relation­ ship without the necessity of determining the plan in order to infer it". This paper may provide an answer to this question, as we discussed particularly with the example.

7 Conclusions and Future Works

This paper proposed an efficient computational mecha­ nism for recovering problem-solving activities from query messages without particular domain knowledge. This work, however, may be a first trial, and there remain several issues to be worked out.

From a computational viewpoint, we must first eval­ uate the actual performance of the mechanism through implementation and experiments with a larger set of un­ seen data. On the other hand, from a theoretical view­ point, there are a number of harder issues . Particularly, our main concern at the moment is the formalization of human problem-solving (trouble-shooting) activities in terms of mental processes, as [Pollack, 1990] formalizes simple plans as complex mental attitudes.

Acknowledgments

I would like to thank Jerry Hobbs for his valuable advice on this work, and Tsuneaki Kato for his useful comments on an earlier version of this paper. The work was done mainly while I was staying at CSLI, Stanford University. Thus, thanks also go to people at CSLI and NTT.