Department of Computer Science, AUC, Cairo, Egypt

Generic Tasks 1

Generic Tasks

Ihab M. Amer

Graduate Student

Department of Computer Science, AUC, Cairo, Egypt

Introduction

The level of abstraction of much of the work in knowledge-based systems (the rule, frame, and logic level) is too low to provide a rich enough vocabulary for knowledge and control. It assumed that there is something called domain knowledge that needs to be acquired quite independent of the problems one might wish to solve, so it did not distinguish between different types of knowledge-based reasoning. This contradicts the interaction problem that states that “representing knowledge for the purpose of solving some problem is strongly affected by the nature of the problem and by the inference strategy to be applied to the knowledge.”

The shortage in these systems encouraged scientists to present a higher level methodology in KBS named as Generic Tasks (GT). The relationship of the constructs at the generic task level to the rule-frame-logic level is analogous to that between high-level programming languages and assembly languages in computer science.

Generic Tasks

1. Definition

Generic tasks are simply, basic combinations of knowledge structures and inference strategies that are powerful for dealing with certain kinds of problems.

2. Main Concept

The appearance of generic tasks is considered to be a good step in satisfying the interaction problem, since each problem type has a distinct strategy type that uses a distinct knowledge type to solve it.

Notice here that we used the general term “type” to illustrate the generality of GTs, since the problem is passed to the GT so that if it matches its function, then the GT provides a knowledge representation and an inference strategy that can be used to solve the problem. This is shown in the following figure.

1. Some GTs and Their Specs

There are several types of generic tasks. They are developed for problems that may frequently appear and need solution. Here, we briefly describe some of them in order to recognize the importance of the GT concept.

3.1. Hierarchical Classification

Input: Given a situation description in terms of features.

Output: Classify it as specifically as possible, in a classification hierarchy, determining what categories or hypotheses apply to the situation.

Inference and Control: The establish-refine strategy specifies that when a hypotheses is confirmed or likely (the establish part), its subhypotheses (children of the node) should be considered (the refine part). Additional knowledge may specify how refinement is performed, e.g. to consider common hypotheses before rarer ones. If a hypotheses is rejected or ruled-out, then its subhypotheses are also ruled-out.

Example Use: Medical diagnosis can be often viewed partly as a classification problem.
3.2.GT Hypothesis Matching

Input: Given a concept (a hypothesis) and a set of data (features) that describe the problem state.

Output: Decide how well the concept matches the situation. The task is a form of recognition.

Inference and Control: At each level, a degree of confidence in the presence of a feature is computed from the features that constitute evidence for it, and this is performed recursively until a degree of confidence for the concept is computed. The basic theory is that recognition of a complex concept is performed by hierarchically computing intermediate abstractions from raw data.

Example Use: Recognition can be performed by means of this strategy. e.g. the concept may be a disease and the data may be the patient data relevant to the disease, and we wish to know what the likelihood of the disease is.

3.3. GT Abductive Hypothesis Assembly

Input: Given a situation description and a set of hypotheses each explaining some aspects of the situation and each with some plausibility value. Output: Construct a composite hypothesis that is the best explanation of the situation.

Inference and Control: Assembly and criticism alternate. At each stage during assembly the problem solving is driven by an attempt to explain the most significant datum remaining unexplained.

Example Use: This Task is a diagnostic subtask in diagnostic reasoning as well as in theory formation in science.

1. Generic Task Tools

Of course researchers needed tools to watch the effect of using GTs in problem solving. This has pushed them to release some versions for different GT tools. Here we are going to mention some of them. For example, Bylander and Mittal developed a tool called CSRL (Conceptual Structures Representation Language) in 1986 as a tool for the hierarchical classification GT. In the same year, Johnson developed his HYPER (HYPothethes matchER), which as the name implies works as a generic tool for the hypotheses matching problem. We also have for the abductive hypotheses assembly a tool that was developed by Punch, Tanner and Josephson in 1986 called PEIRCE that was named after C. B. Peirce, who first described the form of inference known as abduction.

1. GTs as Building Blocks

In the previous topics, we have described each of the common GTs individually. This was just to overcome any confusion between them. But actually what happens in the real life while solving complicated problems is something else. Integration between all of these GTs happens in order to solve the problem. So complex knowledge-based reasoning tasks can often be decomposed into a number of GTs (imagine each of them as a building block), each associated with certain types of knowledge and a family of control strategy. At each stage in the reasoning, the system will engage in one of the GTs, depending upon the knowledge available and the state of problem solving. Actually if a certain GT needs information which can be available by another one, then it may call it and use its results in a process similar to what happens in modular programming where we find functions calling each other.

This pushed scientists to develop what we call toolsets, which helps one to build expert systems by using higher level building blocks. Fafner is a release of an integrated toolset, which is available for research use.

Diagnosis is a problem of finding a cause or set of causes that “best explain” a set of observations of a system, some of them indicating behavioral abnormality.

The following figure illustrates how integration between various GTs can solve a diagnosis problem.

6. Conclusion

After the discovery of GTs, solution to different kinds of problems became much easier. For example, to solve a problem, a knowledge engineer needs only choose a GT that is best suited for performing a particular function, or can use different GTs for performing the same function, or can use a combination of them. So, GT facilitates knowledge acquisition because once the KE selects the GT that he will use, his orientation while collecting knowledge will be close to that of the GT (GT proposes a methodology that helps in analysis, design, and construction of a practical knowledge system).

As expected, GTs have some drawbacks, the fact that pushes the wheel of science forward. Its high granularity obliges the designers whether to use a GT as it is or not to use it at all. This encouraged scientists to search for other techniques for problem solving. Some of these techniques are found and experimented in university laboratories, e.g. Component of Expertise, and KADS.

References

Bylander, T., and Chandrasekaran, B. 1988. Generic tasks for knowledge-based reasoning: the “right” level of abstraction for knowledge acquisition.

Chandrasekaran, B. 1987. Towards a Functional Architecture for Intelligence Based on Generic Information Processing Tasks.

Chandrasekaran, B. and Johnson, T., R. 1992. Generic Tasks and Task Structures: History, Critique and New Directions.

Chandrasekaran, B. 1989. Generic tasks as building blocks for knowledge-based systems: the diagnosis and routine design examples.

Chandrasekaran, B. 1990. Design Problem Solving: A Task Analysis.