To the Ends of the Hills: Problem-solving Heuristics

Suppose you are are a farmer, and you are transporting your goods to market. You have a fox, a chicken, and some grain. You come across a river and a boat that holds you and one other item. If you leave the fox with the chicken, he will eat the chicken. If you leave the chicken with the grain, she will eat the grain. How can you safely ferry all of your goods across the river?

Algorithms v. Heuristics

In a previous post, we drew a distinction between routine and insight problem solving. Routine problems are nice because we see them all the time. Because of that, we have an available procedure that can be easily deployed. Insight problems, however, are more stubborn because we don't have a ready-made strategy. Instead, we need to invent or apply creative approaches to the problem.

In addition to distinguishing between types of problems, a distinction can also be made for the problem-solving process. On one hand, we have algorithms, which are problem-solving procedures that guarantee an answer. The start state is well defined, and you also have a set of operators that transform the problem from one state to another. You apply the operators in a prescribed order until the solution is generated. It might take some time, but you will eventually arrive at a solution. Long division is an example of an algorithm because it is a step-by-step procedure that will guarantee a solution. Unfortunately, that algorithm only works for dividing numbers. You can't use it to pick an outfit for work. 

Contrast an algorithm with a heuristic, which trades off a guaranteed solution with its broad applicability. An algorithm only works if one exists, and it is problem specific. Heuristics, on the other hand, apply to a broad range of problems. The tradeoff is that a heuristic might not give you an answer (or it might provide a sub-optimal solution). Let's take a look at two problem-solving heuristics. 

"Trying to get up that great big hill (of hope)" -- 4 Non Blondes

The first heuristic is called hill climbing (or difference reduction) [1]. It's called "hill climbing" because you can envision the problem space as a mountain. At the base is the starting point (or initial state). The top of the mountain is the solution (or goal state). The hill climbing heuristic selects an operator that reduces the difference between the current state and the eventual goal state. 

To make this more concrete, let's apply the hill climbing heuristic to the farmer's dilemma that opened this post. I don't have an algorithm for solving this problem because I've never seen it before [2]. Before I begin, there is only one problem-solving operator that can change the problem state, and that is loading something onto the boat and moving it to the other side of the river. There are two constraints. I can't leave the fox and chicken alone, and I can't leave the chicken and grain alone. 

To apply the hill-climbing heuristic, I need to select an object. The chicken is the only option because the fox isn't interested in the grain. In terms of climbing the hill, it gets me one step closer to the top. I go back across the river, and I now have to select something else. It doesn't seem to matter which object I choose, so I select at random. I pick the grain. I move that over to the other side of the river, and I am one step closer to the solution. Warning: Here comes the hard part. I have to take something back across the river because it will violate one of the problem-solving constraints (e.g., leaving the chicken with the delicious grain). This goes against climbing the hill because I have to take a step backwards, away from the goal. 

As you can see, hill-climbing might not guarantee a solution. The reason this puzzle is potentially difficult is precisely because you have to make a move that gets you further away from the goal state. 

Means-ends Analysis: It's a Means...to an End!

The second problem-solving heuristic is called means-ends analysis, and it attempts to solve a larger problem (or goal) by breaking it down into smaller sub-problems (or subgoals). Suppose my goal is to drive to work. But when I try to start my car, it fails to turn over. Now I have a problem: How do I get to work? I could call a coworker, but I don't remember her number. Thus, I have to set another subgoal to find her number and give her a call.

Let's take another example. Means-ends analysis works really well for the 3-disk version of the Tower of Hanoi. Here is the initial state:

My top-level goal is to get all the disks on the right most peg. Since that currently isn't possible, I set a subgoal to move the blue disk. But the purple disk is on top of it, so I set another subgoal to move the purple disk out of the way. But the purple disk is blocked by the red disk, so I set a subgoal to move the red disk to a different peg.

As you can see, I now have a bunch of sub-goals hanging around. It's hard to keep track of them because my working memory is severely constrained. Thus, the more disks I have, the more subgoals I collect, which adds an additional burden to working memory.

The STEM Connection

Both math and science education might benefit from knowing about the different problem-solving heuristics. Let's consider science first. One of the top-level goals of science is to build an explanation for some observable phenomenon. If we use the language developed here, the top-level goal is to construct a model or an explanation. The research question or the hypothesis is the problem to be solved. That problem can be decomposed into smaller problems or subgoals. Suppose I want to measure the distance a bee flies after leaving the hive. Thus, I set a subgoal to figure out how to track individual bees. That measurement problem opens several other interesting subgoals.

For math education, it might be useful for students to know the distinction between an algorithm and a heuristic. Some math problems are encountered so frequently that the field of mathematics has developed an algorithm that can be learned and executed whenever the conditions of the problem match the algorithm. But other math problems might not have a ready-made solution (e.g., How many pounds of trash are generated by New York city in a day?). When students encounter these types of questions, then it is time to find a problem-solving heuristic that drives toward a solution. Finding a heuristic, one might say, becomes the first subgoal in finding a solution! 


Share and Enjoy!

Dr. Bob

For More Information

[1] I consulted John Anderson's very approachable textbook Cognitive Psychology and its Implications for the description of the difference reduction and means-ends analysis heuristics. I highly recommend picking up a copy of this book.

[2] Actually, that's not 100% accurate. The fox, chicken, and grain problem is eerily reminiscent of the Hobbits and Orcs problem that we encountered in a previous post. 

Ooops!: The Fundamental Attribution Error

Imagine you are walking to work, and you see a poorly-dressed individual asking for spare change. He looks like he hasn't had a bath in days, and he probably slept outside last night. As you approach this person, do either of the following thoughts go through your mind? 

1. This person is homeless because he is lazy and doesn't want to work. He must be an alcoholic and a drug user. 

2. This person has fallen victim to a string of bad luck. At one point he probably had a house, a car, and a job, but then something happened that made him lose it all. Maybe his wife was diagnosed with a terminal condition, he stayed home to care for her, so he lost his job and ran out of money paying for her medical expenses. 

Whose Fault is it Anyway? 

Blaming the Person vs. the Situation

What do you notice about the two scenarios  other than that they are drastically different from one another? You probably noticed that the first scenario places much of the blame on the individual. This person is homeless because of his personal character and the conscious choices that he made. In contrast, the second scenario focuses on situational factors that contributed to his current circumstances. He did not choose to be homeless, nor is he a bad person. His homelessness was merely an outcome of events that he had no control over. He did not want his wife to get sick, nor did he ask to lose his job. 

The two scenarios illustrate two different ways we can explain a person's behavior. As in scenario 1, we can attribute someone's behavior to something internal to the person, such as their personality or their choices. Or, as in scenario 2, we can attribute someone's behavior to something external to the person, such as the situation leading up to the behavior in question. Which type of attribution do you think is more commonly made? An equally important question for you is which type of attribution do you think is more likely to be accurate?

Please answer in the form of a question.

It turns out that people almost always make internal attributions about the behavior of others, and that internal attributions are almost always wrong. The mistake is so common that it has been named the fundamental attribution error (FAE). In a nutshell, the FAE occurs when people mistakenly believe that a person's current behavior is a result of the person's personality, when it is really a result of the person's situation [1]. In other words, we routinely forget to consider the role of the situation in explaining people's behavior. 

One classic demonstration of the FAE involved judging people's intelligence [2]. Specifically, volunteers in a psychology experiment were randomly divided into 2 groups. As in the popular game show Jeopardy!, the first group (i.e., the "Questioners") was asked to compose a bunch of trivia questions, which the second group (i.e., the "Contestants") had to answer. After the Questioners asked the Contestants to answer the question, the experimenters asked each  group to rate how knowledgable the Questioners and Contestants were. Just like in a real game show, the experimenters also had some other people watch the events unfold (i.e., the "Observers") and rate the knowledge of the people serving as Questioners and Contestants. Before looking at the graph, can you predict how knowledgable each group was rated?

Fig. 1: Results from the three groups when asked to rate the Questioner and the Contestant's general knowledgeability.

An interesting pattern of results emerged. The ratings that the Questioners gave to themselves and the Contestants (i.e., the left-most pair of bars) weren't very different, probably because they knew they were randomly chosen to compose the questions and read the answers. But look at the Contestants' ratings (i.e., the center pair of bars). Contestants rated the Questioner as more knowledgable than themselves. The same was true for those who were watching (i.e., the right-most pair of bars). They really thought the Questioners were smart! 

This example illustrates just how fundamental the FAE really is: it is so easy to discount the role of situational circumstances that we often attribute our own behavior to internal rather than external causes. Why else would the Contestants think they were less knowledgable than the Questioners? It turns out that a person has to be highly motivated, and prompted to think very carefully, to avoid falling prey to the FAE.

The STEM Connection

What does this have to do with education? Just knowing about the FAE can make us more empathic towards others, as we are less likely to assume the worst when someone behaves in a less-than-desirable way. In the classroom, knowing about the FAE can make  teachers more empathic towards their students. Why is Johnny tired all the time? It could be that he is lazy, or that he values video games over sleep. Because these explanations largely focus on Johnny's character, that would be a internal attribution. Alternatively, maybe Johnny's parents start fighting after he goes to bed, and he can't sleep because he is overly stressed. Believing that Johnny's exhaustion is attributed to his home life would be an external attribution.

Probably the most important external/internal attribution dilemma in school is about a student's intelligence (or, colloquially, her "IQ"). Is Sally smart or not? If the teacher makes an internal attribution, then being smart is part of Sally's genetic makeup. If the teacher makes an external attribution, then it might sound something like this: Sally is new to fractions. She might not understand them yet, but she will pick it up with my on-going assistance. It is important to recognize which types of IQ attributions we are making, especially when we consider the impact of the Growth Mindset.

The next time you find yourself harshly evaluating another human being, stop and ask yourself: Is this person like this because that's who they are? Or is it because of the situation, which may or may not be under her control? Thinking about the circumstances that might be driving a person's behavior can make a huge difference in how you react to the person. It is almost always more productive to address issues in the environment that can negatively influence behavior than it is to attribute undesirable person to an immutable characteristic of the person.


Share and Enjoy!

Dr. Bob

For More Information

[1] I realize I am encroaching on the field of Social Psychology, which isn't exactly my area of expertise. But I live with a Social Psychologist, and she gave me some extremely useful feedback (thanks, Leslie!).

[2] This task was originally used in Ross, L. D., Amabile, T. M., & Steinmetz, J. L. (1977). Social roles, social control, and biases in social-perception processes. Journal of personality and social psychology, 35(7), 485.

Your Place or Mine: Transactive Memory

This might be difficult to simulate because you're going to need a partner. Go find someone that you know incredibly well, and ask yourselves the following questions:

1. What did you do on Friday, May 1, 2015?
2. What is the last movie that you saw in a theater? Did you go with someone? If so, who was it? Who was the lead actor/actress? Who directed the movie?
3. During your last vacation, did you go out to eat? Where did you go? What did you have? 

How did you do? Were you able to answer some (or all) of the questions? What it difficult? When you got stuck, what strategy did you use to locate the missing information? Did you consult an external memory source (like a calendar or email) or another person (i.e., your partner)? Was that resource helpful? In what way?

What was the name of that restaurant...?

When a new memory is stored, it becomes embedded in a wider memorial context, which we called a semantic network. When that particular memory is needed, we rely on that context because it provides us with various routes to retrieve the memory. Retrieval, as you may recall, comes in two flavors: cued vs. free recall. Based on your own experience, you've probably found that free recall is much more difficult than cued recall because there aren't any hints. You have to completely rely on your retrieval system to locate the memory. Cued recall is a little easier because the clue in the environment helps activate one of those retrieval paths.

As it turns out, people tend to be great cues for each other! It's fun to observe people cue each other while trying to recall a memory that eludes both parties. Couples and siblings are really great at this because they have so much shared history (i.e., common ground). In addition, they know what the other person knows [1]. For example, suppose I am trying to remember "the name of that movie Valeria Golino was in." My wife might say, "She was in something with Dustin Hoffman," which cues my recall of the movie Rain Man. Neither one of us knew the answer. But though our conversation, the title of the movie emerges. Exploiting the shared nature of memory is called transactive memory. 

A transactive memory system is where two or more people, each with their own memory systems, interact and communicate [2]. The interaction between the memory systems opens the possibility to the encoding, storage, and retrieval of a collaborative memory. In other words, it would be extremely difficult to say exactly where the memory "resides." Instead, the memory is distributed between people. You could also say it emerges from the interaction between people.

The STEM Connection

The educational implications of transactive memory are extremely interesting. Suppose you give your students a group assignment, where the students have to answer the following question: What are the environmental, social, and ethical impacts of selling a McDonald's BigMac? Like most groups, they will probably break down the task so that each person becomes an expert in one area. One student will investigate the environmental impact of buying beef at a large scale and then distributing it to a world-wide network of restaurants. Another student will take the social angle and research the impact of working for minimum wage. The third student will try to investigate if the business practices of a large, multinational corporation are ethically ambiguous.

Who knows the answer to the original question? It isn't clear who knows the answer. Maybe nobody knows. Instead, it is distributed across the students. If one student attempts to remember some part of their research, and looks to her teammates for help, then we are into the land of transactive memory.

Obviously, this has implications for assessment. Is it a requirement that each student knows the complete answer to all three parts of the question? Or is it sufficient that they know the answer at the group level? In other words, can you give them a group assessment or a transactive memory test?

These are interesting and important questions because many careers require that the individual operate in a collaborative team. Each team member may not know all of the answers. But they know who to query when they have a question. They can also help each other remember the decisions that they made at team meetings. 

Transactive memory is a fun and interesting concept. Next time you go out with a good friends, a sibling, or your significant other, keep an eye out for the distributed nature of our memory. It's really cool to observe because, collectively, we know an insane amount of information!


Share and Enjoy!

Dr. Bob

For More Information

[1] The idea of knowing what another person knows (or doesn't know) is called theory of mind. 

[2] Wegner, D. M. (1987). Transactive memory: A contemporary analysis of the group mind. In Theories of group behavior (pp. 185-208). Springer New York.

Like Livers and Lizards: The Generation Effect

Let's play a memory game [1]. I'm going to give you two lists of words. For each list, there's going to be two phases: a study phase and a test phase. For the first list, try to remember each word and its partner. For the second list, I will give you a word, and your job is to come up with its antonym. I will also give you the first letter of the second word (because I'm such a nice guy). Ready? Here we go:

Canvas is not supported.

	:
	:
	:
	:
	:
	:
	:

	:
	:
	:
	:
	:
	:
	:

Now that you've played: 

• Which list was easier to memorize? 
• Which list did you spend more time with? 
• Which list of words were you better able to recall? 
• Did you use any strategies to memorize either list?

Learning by Generating

In a previous post, we talked about ways to enhance our memory by exploiting the nature of memory and how it works. Specifically, we talked about adding additional and related information. You'd think that by adding information we would make memory worse (after all, there's more to remember). But if the additional information is inter-connected and relevant, then it can give your memory a boost by creating multiple retrieval routes to the new memory.

There's another feature of memory that's worth knowing about. It's called the generation effect, which states that memories are superior when we create them ourselves [2]. That might sound a little conceited, but it's true. To the mind, there's nothing more interesting than our own personal history. For example, in a previous post we drew the distinction between episodic and semantic memories. One way to create an enduring memory is to infuse some of your own biographical information into the memory creation process. In other words, when attempting to memorize the words in the second list, you infused that memory of the items with information about the event itself (e.g., I was studying the list on a computer, in my living room, on a sunny spring day).

Another reason why the generation effect works is that there is some benefit to investing effort into creating the memories. Actually, that's not entirely accurate. The type of effort (or processing) seems to matter more than the amount of effort. For example, you could spend half an hour repeating the words to yourself. Alternatively, you could read the words, construct a rule that connects them (e.g., the first word is a synonym or antonym of the second word), cover up the target item, and try to generate it. Both processes are effortful, and you could design an experiment where they both take the same amount of time. But I am willing to bet large sums of money that the method of generating the items will result in better recognition and recall. 

The STEM Connection

The benefit of the generation effect on the learning process is obvious. While it is true that students can learn by reading, it's also the case that students employ many different processing strategies while reading. Some strategies are highly superficial (e.g., re-reading or paraphrasing the text), whereas other strategies are highly effortful and engaging (e.g., trying to explain the material to one's self). The goal is to move students away from the former processing strategies toward the latter. But how? 

One way to provoke students into employing effortful processing strategies is to design the learning situation where students take on more responsibility for generating the to-be-learned information. For example, we can show students how to prove the Pythagorean theorem. According to this resource, there are over 100 ways to prove this famous theorem. One could probably fill a 45-minute lesson on any one of these proofs, and then you could say that you "covered" the Pythagorean Theorem. 

Alternatively, you could pose the problem to the class as a conjecture (i.e., you had a dream last night that a^2 + b^2 = c^2), and you want your students to convince you that it is true (or not!). Another idea is to combine the two approaches. Demonstrate the Pythagorean Theorem, and then ask the students to think of a different way to prove it [3].

The generation effect is a powerful learning mechanism. Intuitively, I think we all know that investing our own mental energy into a task lends itself to a more robust memory for that content. Of course, the next challenge, as instructional designers, is to be creative enough to employ it judiciously in the lessons that we create. But I know, collectively, we are up to the challenge! 


Share and Enjoy!

Dr. Bob

For More Information

[1] Thanks again to Josh Fisher who put together this wonderful memory game.

[2] Slamecka, N. J., & Graf, P. (1978). The generation effect: Delineation of a phenomenon. Journal of experimental Psychology: Human learning and Memory, 4(6), 592.

[3] In fact, I took a class in college where we spent a couple of weeks talking about the various approaches to proving the Pythagorean Theorem. Doing so gave me an appreciation for explanatory depth, as well as the benefit of solving the same problem in multiple ways.