Recovering Problem-Solving Activities from Query Messages

TL;DR

This paper introduces a computational mechanism to automatically reconstruct the problem-solving steps described in Japanese query messages from Usenet newsgroups. By leveraging general knowledge of human problem-solving and linguistic patterns, the system can infer the underlying activities, offering a way to build more intelligent information access systems.

What Problem Does This Paper Address?

In the age of the internet, online forums like Usenet newsgroups have become vital platforms for users to seek help with technical issues. Understanding how people describe their problem-solving efforts in these messages is crucial for developing intelligent systems that can effectively access and organize this information. The challenge lies in the fact that natural language descriptions of problem-solving activities can be complex, ambiguous, and often rely on implicit knowledge. This paper aims to bridge this gap by proposing a method to automatically extract and represent these problem-solving activities from query messages, specifically focusing on troubleshooting scenarios.

Methods

The proposed mechanism operates in three cascaded stages:

  1. Message Fragment Identification: The system first identifies individual message segments that describe a single problem-solving step. This is achieved by recognizing distinctive surface-level linguistic patterns, similar to techniques used in information extraction.
  2. Sub-graph Assignment: Each identified fragment is then assigned a sub-graph that represents the structure of that specific problem-solving step. This involves classifying the type of problem or action described.
  3. PS-graph Integration: Finally, these sub-graphs are integrated to form a complete representation of the entire problem-solving activity as a set of graph structures. This integration process utilizes general knowledge about human problem-solving and discourse structures. The resulting graphs are termed "problem-solving graphs" (PS-graphs).

The paper also details an ontology for these PS-graphs, defining node types (Goal, Problem, Action) and link types (e.g., alternative, a-step, caused, to-solve). A key aspect is the development of a mechanism to map surface linguistic patterns to specific problem types and then to these PS-graph structures.

Datasets

The study used a corpus of 42 Japanese query messages from the Usenet newsgroup "fj.sys.mac," specifically selected for their troubleshooting content. From these, 63 problem description fragments were extracted for analysis and classification. No new benchmark datasets were introduced; the focus was on analyzing existing messages.

Key Insights and Ideas

  • Linguistic Cues for Problem-Solving: Certain linguistic expressions, like the Japanese verb constructions "te-shimau" and "te-kure-nai," strongly indicate a problematic situation for the writer, even without explicit domain knowledge.
  • Implicit Knowledge is Key: The paper highlights that understanding problem-solving activities often requires inferring implicit goals and actions that are not explicitly stated in the message.
  • Goal-Directed Nature: Problem-solving activities are inherently goal-directed. The system aims to reconstruct these goal hierarchies and the actions taken to achieve them.
  • Handling Ambiguity: The proposed mechanism addresses ambiguity by generating multiple possible PS-graphs, reflecting different interpretations of the message, and then using heuristics to refine them.
  • Virtual Actions: To account for missing information in descriptions, the system introduces "virtual actions" (X?) to represent assumed goal-enabling steps that are not explicitly mentioned.

Key Results

The paper demonstrates a method for classifying problem descriptions based on surface patterns and conditional clauses, achieving a reported average recall of 73.0% and average precision of 90.2% through hand simulation. The PS-graph construction algorithm successfully reconstructs problem-solving activities, as illustrated by a detailed trace of an example message. The resulting PS-graphs capture the sequence of actions, problems encountered, and inferred goals, even when the relationships are not explicitly stated.

Limitations and Future Work

The authors acknowledge that the proposed algorithm is a simplified version and that further optimization is possible. They also note that the heuristics used are strong and may not cover all cases. Future work includes:

  • Evaluating Performance: Implementing and experimenting with the mechanism on a larger dataset of unseen data to evaluate its actual performance.
  • Theoretical Formalization: Further formalizing human problem-solving activities in terms of mental processes, building on existing work on plan recognition.
  • Broader Domain Coverage: Extending the approach to handle more complex and less specified plans, as well as different types of problem-solving activities beyond troubleshooting.

Summary updated

BibTeX
@inproceedings{1995recovering,
  title = {{Recovering Problem-Solving Activities from Query Messages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure