Classification Problem Solving William J. Clancey, Stanford University

AAAI 1984

TL;DR

This paper introduces a "classification problem-solving model" as a unifying framework for understanding a broad range of heuristic programs, often called expert systems. By focusing on the underlying inference structure rather than implementation details, it reveals that many diverse systems share a common problem-solving approach: systematically relating data to a pre-enumerated set of solutions through abstraction, heuristic association, and refinement. This model offers a powerful lens for recognizing, representing, and building more effective AI systems.

What Problem Does This Paper Address?

The field of AI has seen a proliferation of "heuristic programs" and "expert systems" designed to tackle complex problems in areas like diagnosis, planning, and selection. However, a significant challenge has been to understand what kinds of problems these systems are good at solving, independent of their specific implementation (e.g., rule-based vs. frame-based). Existing descriptions often fall into either application-specific terms (like "diagnosis," which can be too broad) or implementation-specific terms (like "rule-based," which don't describe the problem itself). This lack of a common, high-level framework makes it difficult to compare systems, design better knowledge engineering tools, and understand why certain problems require different problem-solving approaches. The paper aims to fill this gap by proposing a canonical framework for describing the knowledge used in a significant class of these programs.

Methods

The core contribution is the classification problem-solving model. This model describes a specific inference structure that characterizes how many heuristic programs operate. The key components are:

  • Data Abstraction: Transforming raw data into more meaningful, higher-level concepts. This can be qualitative (e.g., "low white blood count"), definitional (e.g., "structure is a beam"), or through generalization in a subtype hierarchy.
  • Heuristic Association: A "leap" of inference that links abstracted problem features to potential solutions. This is often based on empirical knowledge or "rules of thumb," rather than strict logical deduction. It's a crucial step that distinguishes classification from simple matching.
  • Refinement: The process of narrowing down the set of possible solutions by applying further rules of inference and control strategies. This can involve moving from a general hypothesis to a more specific one, or discriminating between competing hypotheses.

The paper analyzes several existing systems (MYCIN, SACON, GRUNDY, SOPHIE III) through this lens, demonstrating how their underlying reasoning processes can be mapped onto this classification model. It also discusses different search strategies (data-directed, hypothesis-directed, opportunistic) that can be employed within this framework.

Datasets

Not discussed in the paper. The paper focuses on analyzing existing AI programs and their problem-solving structures, rather than introducing new datasets or benchmarks.

Key Insights and Ideas

  • Unifying Framework: The classification model provides a powerful, high-level abstraction that reveals a surprising commonality across diverse AI programs. Many systems, from medical diagnosis to circuit analysis, can be understood as solving problems by classifying inputs into pre-defined categories.
  • Distinction Between "What" and "How": The paper emphasizes the importance of a "knowledge level" analysis, separating what a system knows and how it reasons from the specific implementation details. This allows for a more fundamental understanding of problem-solving.
  • Heuristic Association as a Key Step: The paper highlights "heuristic association" as a critical inference step in classification. This is not just simple pattern matching but a more complex, often empirical, link between problem features and potential solutions, which is central to expert reasoning.
  • Implications for AI System Design: Recognizing classification as a core problem-solving paradigm has significant implications for designing knowledge engineering tools, acquiring knowledge, and developing more transparent and explainable AI systems.
  • Connection to Cognitive Science: The proposed model aligns well with psychological models of expert problem-solving, suggesting that classification is a fundamental cognitive process.

Key Results

The paper doesn't present quantitative results in the traditional sense (e.g., accuracy scores). Instead, its key results are:

  • Demonstration of the Classification Model: The paper successfully applies the classification problem-solving model to analyze the inference structures of MYCIN, SACON, GRUNDY, and SOPHIE III, showing its broad applicability.
  • Identification of Core Inference Types: It clearly delineates the roles of data abstraction, heuristic association, and refinement as fundamental inference types in classification.
  • Framework for Understanding Problem Types: The paper provides a taxonomy of problems that can be solved by classification, including diagnosis, user modeling, catalog selection, theoretical analysis, and skeletal planning.
  • Distinction from Non-Classification Problems: It clarifies what constitutes non-classification problem-solving, such as constructing solutions rather than selecting them (e.g., complex medical diagnosis or design problems), highlighting the need for different approaches.

Limitations and Future Work

  • Scope of the Model: While powerful, the classification model primarily describes selection problems. The paper acknowledges that problems requiring construction of solutions (e.g., complex design, ill-structured medical diagnosis) require different problem-solving methods.
  • Focus on Inference Structure: The paper deliberately separates inference structure from control strategy. While this is a strength for knowledge-level analysis, the practical implementation and optimization of search strategies remain an important area.
  • Future Work: The authors suggest that this model can guide the development of generic knowledge engineering tools, improve knowledge acquisition, and inform cognitive science research on categorization and expertise. They also propose using the model to select problems that can teach us more about the interplay between classification and other inference types (analogy, simulation). The paper also implicitly suggests that understanding the limitations of classification is crucial for identifying problems that require more sophisticated AI techniques.

Summary updated

BibTeX
@inproceedings{1984classification,
  title = {{Classification Problem Solving William J. Clancey, Stanford University}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}

Loading related content...

Figure