There are two main themes to pul out of this chapter. First, while we have spent a lot of time in this course talking in generic terms about information processing, we have not really talked about how particular forms of information processing might be used by humans. The notion of problem solving as search through a problem space is a particularly fine example of how operations on complex tokens can actually be applied to interesting problems.
Second, in the goal of establishing strong equivalence between computer models and humans, problem solving research stands as a shining light. This chapter moves back and forth very nicely between algoirthmic descriptions of problem solving from a computer point of view and descriptions of human performance solving problems. Thus, this kind of work on humans can be interpreted as making plausible the claim that cognition -- or at least the problem solving component of it -- is the manipulation of complex tokens by formal rules.
The ability to solve problems is an important manifestation of human thinking. Problem solving depends on general cognitive abilities that can potentially be applied to an essentially unlimited range of domains. The ability to solve problems is a crucial component of intelligence. In order to understand the nature of human problem solving, first you have to understand the nature of problems. (NB:This is a *very* computational level kind of thought!!) The most influential treatment of this is the 1972 work of Newell and Simon.
Problem Solving As Search
A problem is a situation in which we have a goal in mind, but there is no obvious or easy way of attaining that goal. A key idea is to view problem solving as a search through a "metaphorical space"; the purpose of this search is to find a way to the goal. There are 4 general aspects of this notion: the initial state, goal state, a set of operators, and path constraints. (NB: Path constraints weren't discussed in class. The idea here is that not any route to the goal state may suffice. For instance, you might want the fastest or the cheapest route. This imposes a constraint on the kind of solution path that will be deemed acceptable.)
"The problem space consists of the set of all states that can potentially be reached by applying the available operators. A solution is a sequence of operators that can transform the initial state into the goal state in accord with the path constraints. A problem solving method is a procedure for finding a solution." From this perspective, a brute force search through an entire problem space is simply not feasible; too many alternative paths exist to be searched. This is the problem of "combinatorial explosion." How do humans get around the combinatorial explositon to become expert problem solvers in real time? They must use intelligent, heuristic search. "The development of expertise is largeley the acquisition of knowledge that restricts the need for extensive search." Another solution is to satisfice: don't strive to achieve the best solution; just find a satisfactory one.
Heuristic Search: Means-ends analysis
An important heuristic search technique suggested by Newell and Simon is means-ends analysis:
From means-ends analysis, the following general properties of intelligent search can be seen: (1) Intelligent search is guided by knowledge about the goal. (2) Problems are foten decomposed into subproblems that are easier to solve. (3) Search methods can be applied recursively -- means-ends analysis can be applied to goals, subgoals, sub-subgoals, etc.
Planning And Problem Decomposition
A major implication of the notion of search is that planning a problem's solution is independent of executing that solution. "By imagining the consequences of actions prior to an overt solution attempt, one can identify dead ends without actually executing actions. In addition, planning provides information that can be used to monitor and learn from an overt solution attempt." Planning is often combined with the process of problem decomposition, and leads to less total search too. However, real problems are rarely perfectly decomposable. Often we have to make do with partial decomposition.
Production-System Models Of Problem Solving
Newell and Simon's description of problem solving as search through a problem space is closely tied to an architectural notion: the production system. A production system is a set of condition-action rules that operates as follows:
Production systems have been very influential in cognitive science, and are the basis for many expert systems. Their advantages? (1)They provide a direct method of instantiating knowledge. (2) Knowledge in such a system is clearly procedural. (3) Knowledge is highly modular, so learning is easy -- just add new productions to the existing system. (NB: This strikes me as a pretty handwaving "just").
The Brain And Problem Solving
"It is valuable to consider the implications of neuropsychological evidence in characterizing the basic components of human problem solving." Can brain states for the different components of problem solving be localized? This is not easy to do. Some evidence suggests that frontal lobes are especially important. (NB: Think back to our readings about working memory, and the role of frontal lobes there!) Frontoal lobe damage does not produce intellectual impairment as measured by IQ tests. However, it does produce difficulties in solving new problems. For example, there appears to be marked deficits in planning, as revealed in Shallice's study of the "Tower of London" puzzle.
What makes expert problem solvers better than novices?
Expertise In Chess
In chess, masters are not brighter than duffers. Instead, "the masters were able to use explicit knowledge that led them very quickly to consider the best moves possible, without extensive search." For example, memory studies indicate that experts are better than novices in terms of chunking chess board positions into meaningful units.
Expertise In Physics
Chess conclusions have been confirmed and extended in studies of physics problem solving. "Experts have learned schemas for identifying important categories of problems. These problem schemas are based on features relevant to the selection of solution procedures."
How Does Expertise Develop?
How do the differences between novices and experts develop? (1) Expertise could evolve as more productions are added to a production system. (2) Problem solver may learn new, useful problem schemas. (3) Old rules might be recombined into new, more efficient procedures. (4) Experts have more solved examples to refer back to.
Ill-defined Problems
Search perspective gives limited view of problem solving, because it cannot be applied to ill-defined problems. "Many problems...are ill defined in that the representations of one or more of the basic components -- the goal, initial state, operators, and constraints -- are seriously incomplete." (NB: Problems of underdetermination in vision and language acquisition are examples of such problems.)
Restructuring, Insight, and Analogies
Ill-defined problems might be solved by "seeing" the problem differently -- this goes back to the old Gestalt notion of problem solving as perception. Some evidence supports the notion that some problems are solved by restructuring and sudden insight.
Parallel Constraint Satisfaction
Restructuring suggests that parallel processing may be an important component of solving ill-defined problems. There have been many successes in using parallel constraints to solve ill-defined problems faced by the visual system. (NB: For one example, see Dawson's (1991) description of solving the motion correspondence problem in Psychological Review.) This approach to problem solving recognizes that constraints may not be all-or-none: thus, best solution to a problem might involve "interactive tradeoff" betwwen solutions of subproblems, all happening in parallel. For example, see the McClelland et al. model of the word superiority effect: word context places additonal, interactive constraints that aid in the identification of ill-defined letters. Is there any reason to believe that this kind of processing is involved in problem restructuring? Yes -- mappings between problems vis analogy can be mediated this way, as described in a model by Holyoak and Thagard.
Pearl Street | "An Invitation To Cognitive Science" Home Page | Dawson Home Page |