Chapter 5: Expert Systems, Heuristics, Second Boom

Question 1

What is meant with Weak methods in AI?

Answer 1

An AI uses weak methods when they have difficulty scaling due to the limited amount of knowledge they can incorporate. The knowledge they use is only weakly applicable to a specific problem. Confusingly, nowadays the meaning of strong and weak AI are swapped, meaning that weak AI refers to an AI that can solve a specific problem well, but is not a general problem solver.

Question 2

When began the shift to AI development for problem-specific solutions?

Answer 2

During the 1970s and 1980s

Question 3

What is an expert system?

Answer 3

An expert system is a machine that emulates the decision making of a domain expert. This requires the application of domain-specific knowledge, reasoning using a vast knowledge base of rules and the process (search) is often augmented by heuristics. Knowledge is used to draw conclusions.

Question 4

Give an example of an expert system

Answer 4

Dendral: Given a molecular structure, dendral could predict mass spectograms. Uses expert knowledge in the form of rules, heavily prunes the search of possible candidates. of substructures

Question 5

What is Computational complexity theory, and give a year of when it was first developed? Also give 2 early examples of publications about complexity theory.

Answer 5

Computational complexity theory is a theory that deals with the study of the size of computational algorithms. It is usually divided into Time and Space complexity. The first one meaning, how much time or operations an algorithm takes to run a function. This is expressed in Big-Oh notation. Space complexity deals with the amount of memory the algorithm needs. It was developed in the 1960’s. In 1971, Cook publishes a paper that showed the NP-completeness of Boolean satisfiability. In 1972, Karp publishes a list of 21 NP-complete problems.

Question 6

Give the definition of the word heuristic as formulized by Pearle (1984).

Answer 6

Heuristics are criteria, methods, or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal.

This means these methods are rules of thumb, are not always optimal, are used to find something quickly and compromises between simplicity, efficiency, accuracy and completeness.

Question 7

What are some real-life heuristics?

Answer 7

Checking fruit ripeness by touch, or move in the general direction of a destination instead of following the optimal route.

Question 8

Explain the traveling salesman problem and give an example of a heuristic.

Answer 8

The traveling salesman problem is a problem in computer science, where given a set of cities connected by weighted edges, the task is to find the shortest possible route that visits each city exactly once and returns to the starting city. The problem is NP-hard, which means that there’s no known polynomial time algorithm that can solve the problem optimally for all inputs. An example of a heuristic is the Nearest Neighbor heuristic, which works as follows:
1. Start with an arbitrary node
2. Choose as next node an unvisited node, with minimum distance to the current node
3. Repeat until all nodes are visited, then return to the starting node along the shortest edge.
The solution depends on the starting node, and sometimes by picking the wrong starting node, a worst-case solution can be created.

Question 9

When was Lisp developed?

Answer 9

1958 by McCarthy

Question 10

When was Dendral developed?

Answer 10

1966 at Stanford, written in Lisp

Question 11

When was Prolog developed?

Answer 11

1972, by Colmerauer

Question 12

When was Mycin developed?

Answer 12

1974, at Standford, similar to Dendral.

Question 13

What is the R1 system and when was it developed?

Answer 13

R1 was an Order configuration expert system for computer systems. It saved the company 40 million dollars a year. It was deployed commercially in 1982

Question 14

What happened in 1988? And what did it lead to?

Answer 14

Nearly every major US corporation is using or investigating expert systems in 1988. This led to a supporting ecosystem of software tooling to build expert systems, as well as companies building specialized computers named Lisp machines. The industry went rom a few million in sales in 1980 to 2 billion in 1988.

Question 15

Give a step by step approach to the Alpha beta pruning algorithm.

Answer 15

Step 1: Label the tree with the minimizing and maximizing players.
Step 2: Initialize Alpha en Beta to minus infinity and positive infinity respectively.
Step 3: When the maximizing player can choose a root node, update alpha with the maximum value of children. If the minimizing player can choose, update beta with the minimum value.
Step 4: When traversing back up the tree, update alpha and beta in the same way.
Step 5: If there ever comes up a situation where Alpha is greater or equal than Beta, prune the rest of the children.

Question 16

In relation to connectionism, what happened in 1961, 1969 and 1974, 1982 and 1986?

Answer 16

In 1961 Rosenblatt published a comprehensive work on Perceptrons.
In 1969 Minsky & Papert publishes critique in their book Perceptrons.
In 1974: Werbos publishes PhD thesis applying backpropagation to ANNs.
In 1982: Hopfield invents content-addressable associative memory using ANNs (Hopfield networks)
In 1986: Rumelhart et al reinvent / popularise backpropagation for ANNs.

Question 17

What is the fifth generation computer systems project? Where and when was it initiated?

Answer 17

The fifth generation computer systems project was initiated in Japan in 1982. The aim was to develop new systems that included massive parallelization and logic programming. This sparked renewed government funding. Western governments did not want to be left behind so also jumped on the train. It led to renewed interest in connectionist paradigms and Expert systems provided commercial interest. All of the additional funding reverted the funding cuts from the 70’s.