As explained in a previous post, the initial drive in Artificial Intelligence attempted to deliver generic reasoning machines with little or no domain knowledge. Finding a solution was reduced to a “searching problem”: the program would try different permutations of incremental steps until a path to the answer was found. Even though this worked in practice for small “toy” domains, such an approach would not scale up to a real world situations. As soon as a problem could no longer be solved in polynomial time, but required exponential time to solve, such AI programs proved completely ineffective. As a consequence, in the early 1970s government funding for AI projects was cut.
However, the foundation of knowledge engineering concepts, along with very useful tools and AI programming languages had been inherited from the founding fathers of this new science. The next generation of researchers soon discovered that for generic problems domain only weak solutions would emerge but if the domain was sufficiently restricted, stronger heuristics could be built in to the system which would result in stronger solutions.
DENDRAL was one of the first implementation of such a system. NASA was planning to send an unmanned spacecraft to Mars, and needed a machine to analyse the molecular structure of the Martian soil. The brute force generate-and-test approach of producing all possible solutions given the potential molecular input and then comparing them with the field observations proved NP-Complete (a problem that can only be solve in exponential time, and becomes impossible even for modest sizes of input).
(This picture was taken by the Viking Lander 1 on February 11, 1978)
However, such tasks could be solved by human experts who were able to reduce the problem and make it tractable. As the project team set about encoding expertise to the system, it became apparent that the expert’s knowledge was not limited to the laws of chemistry, but relied on personal heuristics (rules of thumb), and guesswork. In fact, extracting knowledge from the expert became a significant bottleneck in the development of the system. Nonetheless, DENDRAL was a success which ended up being marketed commercially in the USA.
Following on from the success of DENDRAL, the research team at Stanford University set to work on an medical expert system for the diagnosis of infectious blood diseases. The project was called MYCIN, and started to formalise the approach to developing expert systems. Once completed it was equivalent to a human expert (in the narrow field of infectious blood diseases), and outperformed junior doctors. It incorporated some 450 rules which were clearly separated from the reasoning procedure. Using this software design, the team also developed a generic expert system, EMYCIN, which had all the features of the initial software, but none of the rules. New expert applications could be developed by just adding rules to the system.
One of MYCIN’s features was its ability to reason in the face of uncertainty. The approach was taken up in PROSPECTOR, an expert system for mineral exploration. In geological investigation, crucial decisions have to be made in face of uncertainty. To automate such decision making PROSPECTOR implemented Bayes’s rule of evidence to propagate uncertainties throughout the system. The system had over 1,000 rules and also featured a knowledge acquisition system.
Though, I’ve only presented three early examples, expert systems were very popular and successful in the 1980s and 1990s. However, such rule based AI proved to have significant limitation:
- The restricted problem domain within which expert systems operate limit significantly their usefulness. For example, MYCIN would not perform well in situations where the patient suffered from multiple health conditions simultaneously.
- Furthermore, the expert system would not be aware of the narrow boundaries limiting it and attempts to solve problems outside its domain would yield unpredictable results.
- Being rule based, an expert system may have limited capacity to explain its findings, and may find it impossible to derive heuristic links between its rules to gain deeper insight into the problem domain.
- The completeness, robustness and soundness of an expert system is thus far impossible to formally establish.
- Finally, many early expert system were not able to learn from experience and had to be provided all the rules applicable to the problem domain by developers. The development effort in building useful expert system is thus prohibitively significant.
This post is based on the first chapter of “Artificial Intelligence -A Guide to Intelligent Systems” (2nd Edition) by Michael Negnevitsky.