Dynamic Construction and Refinement of Utility-Based Categorization Models

Kim Leng Poh

Department of Engineering-Economic Systems
Stanford University
Stanford, California 94305

Michael R. Fehling

Department of Engineering-Economic Systems
Stanford University
Stanford, California 94305

Eric Horvitz

Decision Theory & Adaptive Systems
Microsoft Research
Redmond, WA 98052

Click here to access postscript file.

Click here to access pdf file.

Abstract:

The actions taken by an automated decision-making agent can be enhanced by including mechanisms that enable the agent to categorize concepts effectively. We pose a utility-based approach to categorization based on the idea that categorization should be carried out in the service of action. The choice of concepts made by a decision maker is critical in the effective selection of actions under resource constraints. This perspective is in contrast to classical and similarity-based approaches which seek completeness in concept description with respect to shared properties rather than the effectiveness of decision making. We propose a decision-theoretic framework for utility-based categorization which involves reasoning about alternative categorization models consisting of sets of interrelated concepts at varying levels of abstraction. Categorization models that are too abstract may overlook details that are critical for selecting the most appropriate actions. Categorization models that are too detailed, however, may be too expensive to process and may contain information that is irrelevant for selecting the best action. Categorization models are therefore evaluated on the basis of the expected value of their recommended action, taking into account the associated resource cost required for their eval- uation. A knowledge representation scheme, known as probabilistic conceptual networks, has been developed to support the dynamic construction of models at varying levels of abstraction. This knowledge representation scheme combines the formalisms of in uence diagrams from decision analysis and inheritance/abstraction hierarchies from artificial intelligence. We also propose an incremental approach to categorical reasoning which involves the dynamic construction and refinement of categorization models. A model may be improved by making the concepts under consideration either more abstract or more detailed. The expected increase in value of the recommended action may be used to direct and control the direction of model improvements. By applying decision-theoretic control of model refinement, a resource-constrained actor iteratively decides between continuing to improve the current level of abstraction in the model, or to act immediately.

Keywords: Bayesian networks, abstraction, metareasoning, model building.

Reference: K.L. Poh, M.R. Fehling, and E. Horvitz, Dynamic Construction and Refinement of Utility-Based Categorization Models, IEEE Transaction on Systems, Man, and Cybernetics, 24(11), 1653-1663, November 1994.

Author Email: isepohkl@leonis.nus.sg, horvitz@microsoft.com