Because teaching a computer how to solve a variety of problems is hard, computer scientists decided to limit the scope of the problems a computer might face. By limiting the types of problems a computer might need to solve, computer scientists hoped to figure out the best ways to teach computers how to learn.

Solving any problem involves reaching for a goal, so the first test of artificial intelligence revolved around teaching computers how to play games. Some games, such as tic-tac-toe, have a small set of possible solutions that can be identified in advance. Because there's only a small number of possible solutions to the problem of playing tic-tac-toe, it's easy to write algorithms that specifically tell the computer what to do in any given situation.

The game of chess is an example of a hard problem because the possible number of valid moves is far greater than any human programmer can write into a program. Instead, human programmers have to give the computer guidelines for solving a problem. These guidelines are heuristics.

A heuristic is nothing more than a general set of rules to follow when faced with similar problems. Telling a child to look both ways before crossing the street is an example of a heuristic. Telling a child to look left and then look right before crossing the corner of 5th Street and Broadway is an example of a specific direction, which is absolutely useless for solving any problem except that one.

To teach a computer to play chess, programmers typically use a tree data structure (see Book III, Chapter 5) that the computer creates before making a move. The tree represents all possible moves, so the human programmer simply writes algorithms for telling the computer how to solve each problem by gathering information about that problem. Because games have distinct rules, teaching a computer to play a game also taught computer scientists the best way to teach a computer to solve any type of problem.

Of course, the problem with this theory is that teaching a computer to play chess created a great computer that can only play chess. Game-playing taught computer scientists only how to make computers play better games but not be able to solve problems outside a fixed set of rules.

Not surprisingly, the one area that has benefited from game-playing research has been using artificial intelligence techniques to create better computer opponents in video games. The next time you play your favorite video game and the computer seems particularly clever, you can thank all the research in AI for making smarter video games.

If computers are good at figuring out how to solve problems within a limited domain, computer scientists reasoned that computers could also be useful for helping humans solve problems as well. The type of program designed to help humans solve problems is an expert system.

The idea behind an expert system is to capture the knowledge of a real human expert and store it in a program, essentially cloning the human expert's thought process. Instead of consulting a human expert for help, someone can just consult the expert system instead.

One of the first expert systems developed was Mycin, which was developed by Stanford University. The goal of Mycin is to help humans diagnose infectious blood diseases and recommend the proper type and dosage of antibiotics.

Like all expert systems, Mycin worked by asking questions to get information about the problem. By gathering more information about the problem, Mycin could keep narrowing its list of questions until it could identify a possible solution. In tests, Mycin actually proved more accurate than Stanford's own medical staff in solving problems. However, Mycin was never used in actual practice for legal reasons. If Mycin makes a mistake, who's responsible — the expert system programmers or the doctor relying on the expert system's advice?

An expert system consists of three parts, as shown in Figure 4-1:

Figure VII.4-1. The three parts of an expert system.

The knowledge base contains the expert's information for solving a specific type of problem. Typically this knowledge is stored in the form of rules, which resemble IF-THEN statements, such as:

IF white blood cell count < 3,000 THEN
   Antibiotic = penicillin

Rules define the thought process of a human expert in tackling a problem. The inference engine is the part of the expert system that examines the rules in its knowledge base and asks questions to the user through the user interface. In the above example, the inference engine would examine the rule and ask the user, "What is the white blood cell count of the patient?" Based on this answer, the inference engine would follow the rule and could decide to use penicillin.

Expert systems typically solve problems by using one of two methods — backward chaining or forward chaining. With backward chaining, the expert system picks the most likely solution and tries to verify that this is indeed the correct solution. As soon as the expert system determines that its solution isn't the correct one, it picks the next most-likely solution, tries to verify this might be the correct answer, and so on.

Forward chaining means the expert system starts asking questions, and based on the user's answers, the expert system tries to determine what might be the best solution. Neither method is better than the other; they're just two ways to solve the same type of problem.

Although expert systems have proven to work within a limited domain, such as troubleshooting an aircraft or diagnosing patients for diseases, they haven't proved popular in commercial applications.

One problem is the difficulty in extracting a human expert's knowledge and translating it into a set of rules. After you've translated an expert's knowledge into a set of IF-THEN rules, a second problem is debugging these rules with the help of the human expert to make sure the expert system works just like the human expert. A third problem is that expert systems are clumsy to use.

When someone wants help with a problem, he can tell a human expert what the problem may be and the human expert can start examining the problem directly. Computer expert systems don't have that luxury, so using an expert system is like playing a game of Twenty Questions with the expert systems constantly asking questions, like "What is the white blood cell count?" After the human user responds, the expert system bombards the user with another question to get more information. Using an expert system can be slow, clumsy, and frustrating, which is why they're rarely used despite so many years of research.

Besides the problem of storing a human expert's knowledge into a series of IF-THEN rules, a final problem is updating the expert system's knowledge, which requires interviewing the human expert all over again and then debugging the expert system once more to make sure the update information is accurate. Given these problems, expert systems are more often too much trouble to use than they're worth.

In science fiction movies, artificially intelligent computers are always able to understand human language, which is known as natural language processing (NLP). The goal of NLP is to make computers even easier to use. By accepting spoken or written commands to the computer, NLP frees users from having to learn the arcane and cryptic syntax of ordinary computer commands.

The first problem with understanding any human language is to understand the meaning of each specific word. This problem is rather trivial because it involves nothing more than identifying a word and then looking up its meaning in a dictionary data structure that links the word to its definition.

If human language was logical, this would be all that NLP would have to do. Unfortunately, the meaning of words often depends on their context, which is difficult to program into a computer. For example, the phrases fat chance and slim chance actually mean the same thing although the adjectives fat and slim might seem like antonyms.

Humans can understand this difference by virtue of their exposure to different use of words and phrases, but computers need this information programmed into them. With so many words and alternate meanings, programming the context of every possible word is nearly impossible, so computer scientists have to rely more on rules for deducing the meaning of words rather than providing actual definitions for every word.

More confusing than understanding the context of words is understanding misspellings of words. When faced with a misspelled word, a computer must guess at its meaning, based on the meaning of surrounding words.

Perhaps the ultimate test for NLP involves translating from one language to another. Although you could simply translate a sentence, word for word, the syntax of languages may differ. To translate languages accurately, computers would need to know the meaning of words in two different languages along with the context and syntax of each language. Because computers have a hard enough time understanding one human language, trying to teach the computer to translate between languages is an extremely difficult problem.

One NLP translated English to Russian and back again. To test the translation capabilities, a programmer gave the program the English sentence, "The body is willing, but the flesh is weak." The program dutifully translated this English sentence into Russian. Then the programmer fed this Russian translation back to the program to convert it to its English equivalent, which wound up stating, "The vodka is good, but the meat is rotten."

One of the most successful NLP programs was written by Joseph Weizenbaum, Ph.D., and dubbed ELIZA after Eliza Doolittle, a working-class character who is taught to speak properly in George Bernard Shaw's play Pygmalion.

The ELIZA program mimicked a Rogerian therapist by asking questions and parroting back replies based on the user's answers. A typical conversation with ELIZA might look like this:

ELIZA: How are you?

PATIENT: I'm feeling sad.

ELIZA: Why are you feeling sad?

PATIENT: My sister is mad at me.

ELIZA: Do you have problems with your family?

PATIENT: They say I spend too much time with my computer.

ELIZA: Do computers frighten you?

ELIZA doesn't actually understand the meaning of words. Instead, ELIZA just knows how to arrange words in their proper position to mimic an intelligent conversation. When ELIZA spots a word, such as sister, brother, or father, it immediately searches its database for a list of canned replies related to asking the user questions about his or her family.

By combining both canned phrases and parroted replies, ELIZA succeeded in mimicking an ordinary conversation. Although Joseph Weizenbaum originally created ELIZA to research natural language processing, he was astounded at how readily people accepted ELIZA and treated it as an intelligent computer even though they knew how it was programmed. When Weizenbaum found his secretary typing her problems into ELIZA and requested that he leave so she could have privacy, he became an advocate against artificial intelligence.

One common application of natural language processing can be seen in the help system of many programs. If you type How do I print a document, the help system for your word processor might display a list of topics for printing files. The computer didn't actually understand the sentence. Instead, the computer, like ELIZA, just scanned the sentence, looking for keywords that it could recognize and then responded based on the keywords that it found.

Similar to natural language processing is speech recognition. Like NLP, speech recognition must identify a word and deduce its meaning. But unlike NLP, speech recognition has the added burden of trying to do all this in real-time. The moment someone says a word, the speech recognition computer must quickly understand that word because the speaker won't likely pause for long before saying the next word.

The simplest form of speech recognition involves choosing from a limited selection of distinctly different sounding words. Many voicemail systems offer this feature by asking a question such as, "Do you want to leave a message?" At this point, the speech recognition computer listens for any sound that resembles either Yes or No. Because the speech recognition computer has such a limited selection to choose from, its accuracy rate can be almost perfect.

A second way to understand speech is to force users to train the computer first by saying a limited selection of words. The computer then stores these spoken sounds in a database so the next time the user talks, the speech recognition matches every spoken word with the closest match in its database.

Such speech recognition systems are extremely accurate, but suffer both from the hassle of forcing users to train the computer for long periods of time and from the fact that after training the computer, it can still understand only a limited vocabulary.

Even worse is that accuracy among speech recognition systems degrades dramatically with background noise or if the user's own voice changes from the time of training to the time of actually using the speech recognition system.

For example, someone with a cold sounds different than normal, which might cause the speech recognition system to be unable to identify his spoken commands. Noise in the background can often affect the speech recognition system's accuracy, which is why most speech recognition systems require the use of a microphone positioned directly in front of the user's mouth.

The ultimate goal of speech recognition systems is to recognize spoken language no matter who's speaking, what background noise there may be, or what he might actually be saying. In other words, speech recognition systems strive for understanding spoken language as easily as people do.

Another form of pattern recognition involves recognizing images, such as faces in a picture or handwritten letters on a piece of paper. Recognizing written characters is known as optical character recognition (OCR) and is commonly used in computer scanners.

OCR software studies an image of a character, and based on its knowledge of letters, the OCR program tries to match the written character with its data-base of known characters. After OCR finds a match, it can decipher the contents of a written phrase letter by letter.

OCR programs have trouble identifying near-identical characters, such as the lowercase letter l and the number 1, or the letter O and the number zero, 0. That's why OCR scanning programs often insert incorrect characters in the middle of scanned text.

Image recognition is a much harder problem, but one that's commonly used in security systems, such as in casinos. Every casino contains a photographic database of known cheaters. If a casino suspects one of these known cheaters has entered its premises, security guards can zoom in on the suspect and use image recognition software to determine whether that person is actually a known cheater in the database.

Such image recognition software examines the shape of a person's face along with the physical position of the nose in relation to the eyebrows, lips, and chin. No matter how many disguises cheaters may wear, they can't hide or change the physical dimensions of their faces, which is how such image recognition programs can spot them.

In the field of robotics, image processing is crucial because it gives robots the ability to sense their environment and avoid or move toward certain objects. Teaching a robot to avoid objects in its path might seem easy until the robot looks through a plate glass window and mistakes the window for an opening that it can roll through to get to the other side.

Although image recognition might help a robot identify the edges of walls or the end of a road, image recognition must also teach a computer to recognize shadows or reflections that can distort images. Primitive image recognition might simply distinguish between patches of light and dark, but more sophisticated image recognition could not only recognize an object in its path but also identify what that object might be, which involves a related category of artificial intelligence known as image processing.

In a limited domain of objects, seeing and understanding images can be determined in advance, but in the real world, the number of images a computer might see and need to recognize is nearly infinite. To solve the problem of not only recognizing an image but also understanding what that image might be, computers need to learn independent of their human programmers.

One simple example of machine learning is based on Bayes' theorem, after Thomas Bayes. This theorem deals with probabilities. Put into practical application, many junk e-mail (spam) filters use Bayesian filtering, which basically examines junk e-mail and compares it to valid e-mail.

Based on this comparison, a spam filter based on Bayes' theorem can gradually assign probabilities that new messages are either junk or valid messages. The more junk and valid e-mail the Bayesian filter can examine, the "smarter" it gets in recognizing and sorting e-mail into their proper categories. Essentially an anti-spam filter's "intelligence" is stored in its growing database of characteristics that identify spam.

One problem with machine learning is organizing information so that the computer can modify its own data. Although languages — like LISP and Prolog — allow self-modifying programs, computer scientists have created a way to model the human brain using ordinary data structures, such as graphs with each node mimicking a neuron in a brain. This entire connection of interlocking nodes, or mimicking neurons, is a neural network, as shown in Figure 4-2.

Figure VII.4-2. A neural network.

A neural network models itself on the human brain, which is divided into a network of interlocking neurons. Each neuron acts like a primitive computer that can receive input and produce output, which gets fed into another neuron as input.

Although a single neuron may not be capable of doing much, a network of interconnected neurons acts like a group of tiny computers that can tackle different parts of a problem simultaneously, which is known in computer science as parallel processing. Ordinary computers represent a single, fast machine that can tackle a problem in sequential steps. The strength of a computer is that it can perform these multiple steps much faster than a human can, which is what makes computers so powerful.

Human brains can't calculate as fast as a computer, but they can process multiple data simultaneously. That makes human brains better at solving seemingly simple problems, like recognizing a face from a crowd. On the other hand, computers have trouble recognizing faces because computers try to follow a sequential series of steps. As a result, computers are slow at recognizing faces while a human's ability to recognize faces is nearly instantaneous.

In a neural network, each neuron can accept data. The data is weighted by a specific value. This total value is then compared to the neuron's threshold. If this value is less than the threshold, the neuron produces an output of zero (0). If this value is greater than the threshold, the neuron produces an output of one (1), as shown in Figure 4-3.

Figure VII.4-3. How a neuron processes and outputs a value.

The neuron in Figure 4-3 receives an input of 1 and 0. The 1 value is weighted by 0.7 while the 0 value is weighted by 0.6, such as:

(1)*(0.7) + (0)*(0.6) = 0.7.

Because this value is less than the threshold value of 1.25, the neuron outputs a value of 0.

A single neuron accepts data and produces a response, much like an ordinary IF-THEN statement used in an expert system. To train a neural network, you can feed it specific data and examine the output of the neural network. Then you can adjust the weights of different neurons to more closely modify the output to a specific result.

Such training can be time-consuming, so another approach is to let the neural network train itself. Based on its output, a neural network can use its own output as input to change the overall neural network's result. Such self-training neural networks effectively mimic the learning process.