CAN A MACHINE THINK? ==================== Introduction ------------ I have assumed that most of you have had little exposure to Artificial Intelligence. The following brief remarks are by way of orientation. The goal of Artificial Intelligence is to design systems which are able to solve problems which people are able to solve, but for which either no algorithm is known, or the known algorithm would take unacceptably long to execute. Examples are: proving a theorem, playing chess, diagnosing a disease, writing a story. About the only AI prgrams most people have seen are chess programs. You have probably heard of Japan's Fifth Generation Project. A large part of this is AI, but the project itself is quite small, and Japan has, so far, contributed very little to AI. AI is very different to conventional Computer Science. Very few of the programming techniques you have learned, and most probably, none of the programming languages, are useful in AI. It is more closely related to Cognitive Psychology. AI has nothing to do with cybernetics or 4th generation languages. ---------- When is a system intelligent? -- the Turing test ------------------------------------------------ A computer and a person are placed in one room, and a second person is placed in a different room, which contains two computer terminals, by which he can communicate with the computer and the person in the first room. If the person in the second room cannot tell when he is communicating with the computer, and when he is communicating with the person, the computer can be considered intelligent. The computer would, of course, have to communicate using some natural language such as English. In order to pass the Turing test, a computer would need to be capable of dialogue such as the following (computer's responses in upper case): In the first line of the sonnet which reads "Shall I compare thee to a summer's day", would not "a spring day" do as well or better? IT WOULDN'T SCAN. How about "a winter's day"? That would scan all right. YES, BUT NOBODY WANTS TO BE COMPARED TO A WINTER'S DAY. Would you say Mr Pickwick reminded you of Christmas? IN A WAY. Yet Christmas is a winter's day, and I do not think Mr Pickwick would mind the comparison. I DON'T THINK YOU'RE SERIOUS. BY A WINTER'S DAY ONE MEANS A TYPICAL WINTER'S DAY, RATHER THAN A SPECIAL ONE LIKE CHRISTMAS. ---------- Can a machine be intelligent at all? -- the Chinese room -------------------------------------------------------- The philosopher J.R. Searle argues that Artificial Intelligence is impossible, even in principle. The argument is based around the generally accepted idea that understanding a natural language is an intelligent process, and that executing a simple algorithm is not. Here it is: A person is placed in a room, with a rather large book containing entries arranged in lexical order in a language which he does not understand (in the original specification, the language was Chinese). Alongside each entry, there is a response. The person in the room receives messages in this language through a slot in the wall, looks them up in the book, and chooses the appropriate responses. He passes them out through the same slot in the wall. A person outside the room who understands this language thinks that the person in the room also does, but he doesn't -- in fact, he doesn't even know the meanings of the words. The person in the room is simply executing a loop and looking up a table. The algorithm the person is using could be made more complex so that the table could be made shorter, the responses more varied, and so on, and the person could be replaced by a computer to improve response times, but the point is still the same: neither the person nor the computer which replaces the person understands the language. As there is nothing intelligent about being able to perform an algorithm, the apparently intelligent system is not really intelligent at all. Searle's argument can be refuted in a number of different ways, of which I give two: What makes you think that Chinese understand Chinese, or that British or Americans understand English? What it boils down to is that you say things to them in Chinese or English, and the answers you get are consistent with the hypothesis that they understand the languages. The human brain is intelligent, and it is just a kind of computer. Now, it is possible to simulate the function of a single neuron on a computer. We could, at least in principle, replace one neuron at a time by a computer, making occasional optimisations along the way: working out the algorithm executed by a cluster of neurons, and replacing that by a single computer instead of a cluster of them. Eventually, the whole brain could be replaced in this way, without there being any difference in functioning. The cluster of computers thus developed would then be able to think in EXACTLY the way that the brain thought. ---------- Brief history of Artificial Intelligence ---------------------------------------- AI is not a recent development in computing. The first conference on AI was held in 1956 at Dartmouth College. Two of the conference organizers (Marvin Minsky and John McCarthy) are still actively involved in AI. The first AI program, a theorem proving program called the Logic Theorist (developed by Herb Simon and Allen Newell) was completed for this conference. Other early AI programs include: A checkers (draughts) playing program, developed by Arthur Samuel. A general problem (i.e. puzzle) solver (GPS), developed by Newell, Shaw and Simon. An information retrieval program (SIR), developed by Raphael. Most of the early AI programs rely on what are now called "weak methods", i.e. search algorithms and "Generate and Test". Also, they generally used simple data structures. Recent programs include: Eurisko, which has invented 3-dimensional semiconductor devices, rediscovered important concepts in number theory and won a wargame tournament two years in a row (developed by Doug Lenat). Internist/Caduceus, which can diagnose any disease (developed by Pople and Myers). It is now appreciated that the most important part of an AI program is its knowledge; the particular search algorithm used is much less important, and often is very simple. The most prevalent AI programs are expert systems: these are programs which have high performance within limited domains. ---------- Representing factual knowledge ------------------------------ One of the simplest ways of representing facts is as logical formulae, e.g. Clyde is an elephant --> elephant(clyde) There's a fly in my soup --> exists(X): fly(X) ^ in(X, g0003) ^ soup(g0003) ^ owner(g0003, me) All elephants are either African or Indian --> forall(X): african(X) v indian(X) v ~ elephant(X) Dr Black was murdered by the Rev. Green in the conservatory with the lead piping --> isa(g0004, murder) ^ object(g0004, black) ^ agent(g0004, green) ^ location(g0004, g0005) ^ instrument(g0004, g0006) ^ isa(g0005, conservatory) ^ material(g0006, lead) ^ isa(g0006, piping) ---------- Representing heuristic knowledge -------------------------------- Heuristic knowledge is knowledge which is helpful in finding a solution to a problem. It is usually represented in the form of rules, i.e. if-then statements such as If X is malfunctioning, then give X a good smack. This is a fairly general heuristic, applicable to computer VDUs as well as children. A more specific heuristic might be: If X is an Omigawd 708 vu-graph projector and X is humming, then give X a good smack on its right side. You can have heuristics about heuristics: If using X has produced very few good results, but no bad ones, then consider generalizing X. You can either reason forward from an initial set of facts (forward chaining), or reason backward from a goal (backward chaining). Backward chaining is better for decision making, forward chaining is better for getting things done. ---------- Example of forward chaining --------------------------- Goal: To have a Christmas present wrapped. Facts: The price label is still on. I do not have any Christmas wrapping paper. Rules: [Rule 1] If the price label is still on, then I should take it off. [Rule 2] If I do not have any Christmas wrapping paper, then I should buy some. [Rule 3] If the price label is off and I have Christmas wrapping paper, then I should wrap up the present. Execute rule 1 (or rule 2). Now, the price label is off (or ...). Execute rule 2 (or rule 1). Now, I have Christmas wrapping paper (or ...). Execute rule 3. Now, the present is wrapped, and the goal is satisfied. ---------- Example of backward chaining ---------------------------- Should I take the Star Ferry or the Empty Arrow to Central? [Rule 1] If it's rush hour and I want a seat, then I should take the Star Ferry. Is it rush hour? [Rule 2] If it's between 5:30 an 6:30, then it's rush hour. What time is it? 5:45. Conclude: it's rush hour. [By rule 2] Do I want a seat? [Rule 3] If I've had a hard day at the office, or I'm not feeling too good, then I want a seat. Have I had a hard day at the office? Yes. Conclude: I want a seat. [By rule 3] Conclude: I should take the Star Ferry to Central. [By rule 1] ---------- Problems with natural language ------------------------------ Originally, it was thought building a computer program which translated documents from one language to another would be a straightforward task -- simply supply a dictionary, allowing translation of single words between the two languages, and a grammar for each language, so that the system can parse the source language and then generate the target language. This turned out not to be the case, because [1] Many, if not most sentences are syntactically ambiguous. [2] Each language has its own colloquialisms. [3] Many writers (esp. technical) are weak in grammar. Take the following sentence, which we have already met: Dr Black was murdered by the Rev. Green in the conservatory with the lead piping. You will have no trouble translating it into Cantonese: chuehn\-gaau-sih green yuhng seui/-hauh-tit da/-sei/ black yi\-sang\ hai/ wan\-sat\ loih-bihn. You know that lead piping is a blunt instrument, and can be used as a murder weapon. You also know that conservatories are for keeping plants in, not pieces of metal. If you don't, you could easily produce the following (incorrect) translation. chuehn\-gaau-sih green da/-sei/ black yi\-sang\ hai/ yauh/ seui/-hauh-tit-ge wan\-sat\ loih-bihn. There were two ways to parse that sentence, only one of which is sensible. It is a typical example. There are worse cases, e.g. People who apply for marriage licences wearing shorts or pedal pushers will be denied licences. There are forty different ways of parsing that sentence, only one of which is sensible. You need to know that: People wear shorts -- marriage licences don't. People cannot become marriage licences. You cannot pedal pushers. To translate between two natural languages, you need to understand what is written, and this requires some knowledge of the subject matter. The best that is currrently available are a few systems which translate technical documents with about 90% accuracy. They still require a human to correct the mistakes they make. ---------- Advice on building an expert system ----------------------------------- Developing an AI system using a conventional language such as Pascal, FORTRAN, COBOL or BASIC is like trying to nail jelly to the ceiling. I've tried it, not because I thought it was a good idea, but because I was told to. The project was eventually scrapped. There are two languages which I would recommend, though there are others which can be used. These are LISP and Prolog. I prefer LISP because you get more powerful list processing functions than Prolog, and because Prolog has features which you are often better off without, such as automatic backtracking. The de facto standard for LISP is Common LISP. There are a number of expert system development tools, or shells. These range from inexpensive, but not very powerful tools, such as Micro-Expert and EXSYS through medium-sized tools such as Personal Consultant Plus to large tools such as ART, KEE and Knowledgecraft. Price is no use as a guide to quality -- a better guide is the number of systems developed using the product. The quality of support offered by the vendor should also be considered. If you have a particular problem in mind, the type of system you use is crucial. A forward chaining system is unsuitable for diagnosis, and a backward chaining system is unsuitable for process control. There are also computers specially designed for AI use, the LISP machines of Texas Instruments, Xerox, Symbolics and LMI. Buying one is like buying a Rolls Royce. You pay a lot of money, but you get a very good product.