Abstract
This paper presents a formal computational framework for granularity—the capacity to represent and reason about the world at varying levels of detail. By decomposing granularity into two orthogonal dimensions, abstraction and aggregation, the framework enables intelligent tutoring systems (ITS) to robustly diagnose student performance. We demonstrate this application by recognizing high-level programming strategies in novice LISP code, even when the low-level implementation is logically flawed or syntactically idiosyncratic.
Introduction
In the development of Intelligent Tutoring Systems (ITS), the ability to maintain a shared conceptual "wavelength" with the student is paramount. A tutor must be able to shift fluidly between broad strategic concepts and fine-grained implementation details. Historically, AI systems utilized notions of granularity implicitly, but lacked a formal, unified theory. This paper addresses that gap by proposing a concrete computational model that allows a system to say, "I do not recognize this specific line of code, but I can see the student is attempting a Cdr-Recursion strategy."
The Dual Dimensions of Granularity
The proposed framework defines a Granularity Hierarchy based on two primary relations: Abstraction and Aggregation. These dimensions are orthogonal, meaning a concept can be simplified by either moving up the abstraction ladder or by viewing it as a single unit rather than a collection of parts.
The Abstraction Dimension
Abstraction ($\alpha$) moves from general classes to specific instances. For example, a general Recursion concept might be specialized into Tail-end Recursion or Cdr-Recursion. The framework utilizes a "Principal Hierarchy," which is a uniquely-rooted structure connecting all domain objects back to a single root, such as "Lisp Program."
As shown in Figure 1, recognition at a fine grain automatically propagates upward. If the system identifies a Cdr Tail-End Predicate, it implicitly recognizes the presence of a Cdr Tail-End Recursion, a Recursion, and ultimately a Lisp Program.
The Aggregation Dimension
Aggregation ($\rho$) moves from parts to wholes. A complex strategy like Cdr-Recursion is not just a single node but a composite of several parts, such as a Null base case and a Recursive cdr reduction case.
Figure 2 illustrates how these parts are assembled. The framework employs Gestalt Functions to act as local interpreters. These functions do more than verify the existence of parts; they ensure the parts are "assembled" correctly—for instance, checking if a base case correctly precedes the recursive call within a cond statement.
Implementation and Evaluation
The framework was implemented in a diagnostic system containing approximately 200 objects spanning 10 levels of abstraction and 4 levels of aggregation. To test its robustness, the authors evaluated the system using a repository of LISP solutions collected from 48 novice programmers. This dataset provided a realistic, "messy" environment characterized by student errors and idiosyncratic coding styles.
Robustness through Coarseness
A key insight of the framework is the concept of indistinguishability. Two objects are considered indistinguishable if they are finer-grained than the system's current level of focus. This allows the tutor to ignore "noise" or minor bugs to focus on underlying logic.
In one specific case involving the FindB problem, a student's code was logically flawed and contained unnecessary functions. While traditional template-matching systems might fail to categorize such code, this framework successfully identified the student's intent as a Cdr-Recursion. This allows the tutor to provide constructive feedback (e.g., "Your general recursive structure is correct, but your base case is failing") rather than a generic error message.
Conclusion and Future Work
While the current implementation requires significant manual knowledge engineering to define the hierarchy, it proves that a formal theory of granularity can significantly enhance the diagnostic capabilities of ITS. Future work aims to automate the generation of task-specific strategies from problem descriptions and to explicitly incorporate "buggy" versions of strategies into the hierarchy to provide even more precise diagnostic labels for common student misconceptions.
Summary updated