Using AI to learn about algorithms.

Abstract

As a course available for general education credit, one purpose of our undergraduate Introduction to Cognitive Science course is to increase students' understanding of mathematical concepts. We chose to concentrate on the concept of algorithm. The course contains a section discussing artificial intelligence as a way to simulate human cognition, using both symbolic and numerical algorithms. Since many undergraduate students are uncomfortable with numbers, we chose a program that used a symbolic algorithm. We replaced the discussion of this program with a live demo that students could discuss step by step. The demo program simulated a grocery store bagger. As this program was an example of an expert system, a program that simulates human expertise, students could not only watch the program make choices for different sets of groceries, but change its bagging rules as well. Thus students were able to observe the underlying expert system algorithm as well as a family of bagging algorithms. Course evaluations showed that students enjoyed the demo and found it more helpful than the material it replaced, but they still found the material difficult.

Introduction

An important part of learning mathematics at the university level is the concept of algorithm. Yet many undergraduate students are uncomfortable with numbers, even to the point of math anxiety (Tobias, 1990). This paper reports on an attempt to increase students' understanding of the concept of algorithm in a general education course without triggering the nonproductive responses often fostered by previous negative experiences with mathematics. To this end, we replaced a segment discussing the behavior of various computer programs in our Introduction to Cognitive Science course with a live demo that students could discuss step by step.

Moursund (2005) points out that the term "algorithm" has different connotations in mathematics education and in computer science. For both types of educators, an algorithm describes a procedure for solving a problem or obtaining a result. In mathematics, an algorithm usually involves a calculation, while in computer science, an algorithm may use words, structures, or other symbolic elements instead of numbers. For this study we selected a symbolic algorithm rather than a numerical one. Using familiar content along with an approach and notation that students had not seen before, we hoped to trigger curiosity and enthusiasm rather than the negative feelings that a numerical approach might otherwise trigger.

Naps et al. (2002), in a survey of software visualization experiments, conclude that learner engagement with the software may be the most important factor in student learning. This is consistent with Papert's classic work (Papert, 1980) on engaging children in creating software using the Logo language. Papert's work was based on the constructivist approach of Piaget (1973). Some of the practices most generally considered useful for this purpose include adapting to the knowledge level of the student, supporting flexible execution control of the program, supporting learner initiatives in changing the data, showing history in addition to current state of the system, and including explanations along with the demo. The intent of these practices is to help students attain deeper levels of understanding as measured by Bloom's taxonomy (Bloom & Krathwohl, 1956). Using these principles, we wanted to help students understand the concept of algorithm by providing students a compelling experience where they could see an algorithm run and affect what it does.

In the next section we explain our motivation for teaching artificial intelligence in a Cognitive Science course and how we selected the software to use in the study. In the following section we describe how the software works and how we used it in class. Then we give the results of our study. Finally, we place our work in context.

Background: AI in a Cognitive Science course

The study took place in a General Education course entitled Language, Mind and Thought at Northern Illinois University. This course is an interdisciplinary, team-taught introduction to cognitive science. The course is taught every fall. The allotted 50 slots are quickly filled every year. Approximately 60% of the students are freshmen, and 80% are majoring in a non-mathematically oriented field. Even though we attempt to make the course appropriate for these incoming students, who are the target audience, some still find it tough going. Most cognitive science textbooks are designed for juniors and seniors with some experience in logic, philosophy or psychology.

During the last three weeks of the course, students are introduced to some basic ideas in artificial intelligence. The students are introduced to three basic approaches to AI: emulating the brain's biological structure, such as the use of neural networks for visual recognition; simulating human cognitive processes, such as memory and language; and using software that produces the same results as human cognition without attempting to model the processes. An analogy often used to describe the third approach is that of the airplane (Ford and Hayes, 1998): birds and airplanes can both fly, but airplanes do not fly by imitating birds. In fact, human beings did not achieve flight until they dropped the idea of trying to imitate birds.

The primary purpose of this segment of the course is to give the students a new appreciation of the Cognitive Science material already taught by seeing how easy or difficult it is to use computers to simulate the models of the mind they have been studying. Additionally, by allowing students to experience for themselves what artificial intelligence programs can and cannot do, they can get a better idea of the ethical issues involved in the field today. From a deeper perspective, however, an important goal of this segment is to reinforce students' understanding of the concept of algorithm and extend it to non-numerical algorithms, to which they have very likely not been exposed. The Language, Mind and Thought course was designed to be part of the General Education program at Northern Illinois University. As the goals of the General Education program include increasing students' abilities in the areas of quantitative reasoning, logical thinking, and the interpretation of mathematical models, it is clear that broadening and deepening students' ideas about algorithms is essential to the course.

Method: Software chosen and its rationale

In one of the readings for the course (Winston, 1992), Patrick Winston, formerly the director of the MIT AI laboratory, introduces students to the concept of rule-based systems with Bagger, a program that knows how to bag groceries. Bagger is intermediate between the second and third types of AI software described above. Bagger does not attempt to model the exact rules that human being use to bag groceries, yet the underlying metaphor of a rule-based system is used by Anderson (1993) to explain human mental processes. Students are always amused when the hear the topic because they have generally never thought about the logic behind something they consider obvious.

In a rule-based system, the algorithm to be followed is represented by a set of if-then rules plus a general logic engine that applies those rules. The algorithm taught is the forward chaining algorithm, a standard algorithm for operating a rule-based system. We use a simplified version for pedagogical purposes. In our version, the computer starts at the top of the list of rules for each item to be bagged. It goes through the rules in sequence looking for rules whose antecedent is true. It then applies the consequent of the first applicable rule. Since students can see and change the rules, it is easier for them to appreciate the algorithm than in a conventional computer program. Because the content is already familiar to them, students are free to concentrate on the algorithm.

An important point about artificial intelligence that students learn that computers must be explicitly programmed with the knowledge that human beings acquire through interaction with the world. For example, Bagger must be told about the maximum number of items to put in a bag and given some information about the best ways to mix items in a bag. It must also be taught about items that need special handling, such as fragile, heavy, and frozen items. Thus Bagger can be run with many different sets of rules, forcing students to pay attention to the algorithm if they want to get the same results as the computer. Students always enjoy seeing Bagger do poorly when presented with a poorly-designed set of rules. Here are some sample rules from our version of Bagger:

   If we are in the large item phase
   and there are still more large items left
   and there is a bag with less than two large items
   then put the item in the bag.
      If we are in the large item phase
      and there are still more large items left
      and there are no bags available with less than two large items
      then start a fresh bag.
   If we are in the large item phase
   and there are no more large items
   then move on to the medium-item phase.

This sequence of rules expresses, in an if-then notation, a number of concepts that will be familiar to any shopper: Bag large items first. Although you should not place too many large items in one bag, you can fill in the remaining space with smaller items. Since every detail of the rules must be programmed in, students learn that a large number of precise rules is necessary even for a simple application like grocery bagging.

Several criteria were used for choosing the software for the study. We believed that students would benefit from seeing how the computer systems they are learning about in lecture, textbook and readings actually work as opposed to being told how they work. The latter option usually involves either detailed output that novices cannot relate to or generalizations that they do not yet have the background to appreciate. Yet much of the software currently available just shows results, whereas for teaching purposes we need to show how those results were obtained. In addition, AI software is usually designed for graduate students or advanced undergraduates, and thus does not provide an appropriate visual interface for beginning students. Finally, much of the available software involves algorithms too complex for novices.

Classroom use of the software

The week before the demo, we ask students to read a section from an artificial intelligence textbook (Winston, 1992). This section had been placed on online reserve and assigned as reading before the demo. In this way we hoped to show students that they could read and understand technical material, even if they did not know every detail of the notation. In addition to serving as class preparation, the reading assignments also contribute to the General Education goals of the course. There is a short quiz just to ascertain that they have read the material. The software is pre installed on a laptop and demonstrated via a data projector. At each step, students are asked to predict what the robot would do. For example, Bagger might be given the following list of items:

Item 1 : Pepsi, large bottle (heavy).

Item 2: Bread, medium-sized plastic bag.

Item 3: Granola, large cardboard box.

Item 4: Ice cream, medium-sized cardboard box (frozen).

Item 5: Potato chips, medium-sized plastic bag.

Once the system knows the rules to be followed and the input, it can then produce the results. Bagger starts by bagging the large items:

Rule B2 says: Bagging large items first.

Rule B3 says: Put item 1, Pepsi, in bag 1.

Rule B4 says: Put item 3, granola, in bag 1.

It then continues with the medium-sized items, starting a fresh bag when necessary:

Rule B6 says: Bagging medium items next.

Rule B7 says: Put item 4, ice cream, in a freezer bag.

Rule B9 says: Start a fresh bag.

Bagger continues until all items are bagged.

Results and discussion

In order to measure the impact of this project, eight questions were added to the course evaluation form. The course evaluation form uses a 5 point Likert scale, where 1 means 'strongly disagree' and 5 means 'strongly agree'. Thirty-two students completed the evaluation in Fall 2003. The results are shown below.

The first result shows that the procedurally-oriented material in the artificial intelligence segment is still difficult for non-mathematically inclined students. The computer demonstrations

2.72 ... were clear and understandable.

2.72 ... were helpful to my learning.

However, the second result shows that specific illustrations are more useful to this group than an abstract discussion of the principles involved. Showing specific examples of computer programs

3.44 ... is more interesting than discussing the general principles behind them.

3.47 ... was more helpful to my learning.

The final two results show that the most useful methods for teaching non-mathematically oriented students may be different from the methods preferred by computer scientists (Koedinger, 2001). Showing specific examples of how a computer program works

3.41 ... is more interesting than a high-level overview of the program and what it does.

3.47 ... was more helpful to my learning.

Running computer programs in class

3.50 ... is more interesting than showing program outputs.

3.34 ... was more helpful to my learning.

The similarity in results for each pair of questions shows that maintaining student interest is directly related to students' perception of learning.

Related work

In this paper we describe the use of interactive AI software to teach a symbolic algorithm to undergraduates with no computer science background. Other researchers using AI software in teaching have also emphasized the importance of interactivity to increase learner engagement. For example, Eisner (2002) uses an interactive spreadsheet in an to teach a numerical algorithm to undergraduate computer science majors, and Lincoln and Light (2005) use a graphical representation to teach a similar algorithm to non-majors. Amershi et al. (2005), discussing the design of their interactive visualization software for teaching AI, pay particular importance to pedagogical goals, including generating interest in the subject matter, promoting active student engagement, and supporting a variety learning scenarios.

Conclusions

In this study, a live demo using the program Bagger was added to a general education Introduction to Cognitive Science course with the intent of deepening students' understanding of algorithm. Bagger is an example of an expert system, or program that simulates human expertise. The expert system software and several different sets of rules for bagging were installed on a laptop and used for a live demo after the algorithm had been discussed in class. According to the course evaluations, students enjoyed the demo and felt that they learned more from it than from class discussion alone. However, they still found the material difficult and did not enjoy the technical segments of the course as much as other segments.

Software demos were both more interesting and more useful than the previous approach of just talking about programs and showing pre printed computer outputs. However, non technical students taking the course to fulfill their General Education requirements still present a tough audience for technical material, and more research on how to reach this audience would be fruitful.

References

Amershi et al. (2005). Designing CIspace: Pedagogy and Usability in a Learning Environment for AI. In Tenth Annual Conference on Innovation and Technology in Computer Science Education (ITiCSE). New York: ACM.

Anderson, J. (1993). Rules of the Mind. Hillsdale, NJ: Erlbaum.

Bloom, B. Krathwohl, D. (1956) Taxonomy of Educational Objectives: The Classification of Educational Goals, Handbook I: Cognitive Domain. Boston: Addison-Wesley, 1956.

Eisner, J. (2002). An Interactive Spreadsheet for Teaching the Forward-Backward Algorithm. In Proceedings of the Workshop on Effective Tools and Methodologies for Teaching NLP and CL. New Brunswick, NJ: ACL. Pp. 9-17.

Ford, K. and Hayes, P. (1998). On Computational Wings: Rethinking the Goals of Artificial Intelligence. Scientific American Presents, 9(4), 78-83. Reprinted in Understanding Artificial Intelligence, New York: Basic Books, 2002.

Koedinger, K. (2001). The Student is Not Like Me. In Tenth International Conference on Artificial Intelligence in Education (AI ED 2001). San Antonio, TX. Keynote address. Slides available online at http://www.itsconference.org/content/seminars.htm.

Lincoln, N. and Light, M. (2005). Making Hidden Markov Models More Transparent. In Proceedings of the Second Workshop on Effective Tools and Methodologies for Teaching NLP and CL. New Brunswick, NJ: ACL. Pp. 32-36.

Moursund, D. (2005). Improving Math Education in Elementary Schools: A Short Book for Teachers. Available from http://darkwing.uoregon.edu/~moursund/dave/ElMath.html.

Naps et al. (2003). Exploring the Role of Visualization and Engagement in Computer Science Education. ACM SIGCSE Bulletin, 35(2), 131-152.

Papert, S. (1980). Mindstorms. New York: Basic Books.

Piaget, J, (1973). To Understand is to Invent. New York: Grossman. Originally published in French in 1948.

Tobias, S. (1990). Math anxiety: An update. NACADA Journal, 10(1), 47-50.

Winston, P. (1992). Artificial Intelligence. Boston: Addison-Wesley. 3rd ed. Section entitled "Rule-Based Systems for Synthesis," pp. 166-176.

Reva Freedman, Northern Illinois University

Reva Freedman, Ph.D., is an assistant professor in the Department of Computer Science. Her research interests include teaching artificial intelligence and cognitive science to undergraduates.