machine learning is concerned with the development of algorithms and techniques that allow computers to “learn”. At a general level, there are two types of learning: inductive, and deductive. Inductive machine learning methods extract rules and patterns out of massive data sets.
Some parts of machine learning are closely related to data mining and statistics. Machine learning research is focused on the computational properties of the statistical methods, such as their computational complexity.
Alex, programmed to assist visitors looking for basic legal information on Jurist, the Legal Education Network from the University of Pittsburgh School of Law.
Amy, enjoying fun topics like everyone else, Amy is a gossip. Simply by asking her for gossip you will hear the latest from some of Amy's friends as she loves chatting online.
Cyber Ivar, created by software nodelling company Jaczone, Cyber Ivar teaches about software development, their processes and the advantages of the Unified Modeling Language.
iGod, repenting made easy. This simulation is convinced that it is the one and only answer to your prayers. This Macromedia Flash AIML bot is based on the teachings of Christianity.
Lauren, an Alice based diva with an outgoing personality. She was the winner of the Chatterbot Beauty Contest at the 2002 International Lisp Conference.
Ruby, working on any computer with Macromedia Flash installed, Ruby created by Lynn Hershman, this visually impressive bot wants to teach us to dream. (Pop-up window)
Jack the Ripper, in the autumn of 1888, a sadistic man prowled the dimly lit streets of London's East End. A disturbing use of Chatterbot technology has made him available to face charges via the Web.
John Lennon Artificial Intelligence Project, this highly ambitious product is programmed with John's own thoughts and words as expressed to those who knew him in an attempt to recreate the personality of the late Beatle.
Corby, an intelligent conversation robot that simulates human verbal behaviour. It is based the stimulus-response model to use statements provided by the user to provide appropriate responses.
Dobot, a chatterbot that can be taught words, names and sentences. It can also customize the way you want it to reply to certain phrases. He can become very smart, but it depends on his teacher.
Jabberwacky, a wacky, humorous and surprisingly human bot that has learnt from millions of users, in many styles and languages. Warning: you may get hooked.
Leo and Dante, teachable chatterbots that learn from your conversation. However, as the author knows, starting from a clear database can be frustrating, so one is provided for you to build on.
MegaHal, not to be confused with the 2001 computer, Megahal was created by Jason Hutchens as a web experiment to learn what the public teach him, just like a baby does.
Mr Know-It-All, focusing on animals, plants and general science, this chatterbot by Paul Bird is able to remember what you teach him and can also do your sums.
Niall, The Non-Intelligent Acquired Language Learner is another chatterbot which in the beginning knows absolutely nothing. Created by Mat Peck, it is up to you to teach it.
Nicole, inspired by Mat Peck, the Nearly Intelligent Computer Operated Language Examiner is an attempt to simulate a conversation by learning how words are related to other words.
Omnibot, a Chatterbot that knows very little. However, like the other two, the more it is taught, the more it then knows. Be advised that to do this requires you to have a lot of spare time.AIML (Artificial Intelligence Markup Language) is an XML-compliant language that's easy to learn, and makes it possible for you to begin customizing an Alicebot or creating one from scratch within minutes.
The most important units of AIML are:
There are also 20 or so additional more tags often found in AIML files, and it's possible to create your own so-called "custom predicates". Right now, a beginner's guide to AIML can be found in the AIML Primer.
The free A.L.I.C.E. AIML includes a knowledge base of approximately 41,000 categories. Here's an example of one of them:
I am the latest result in artificial intelligence,
which can reproduce the capabilities of the human brain
with greater speed and accuracy.
(The opening and closing
Everything between
The pattern shown will match only the exact phrase "what are you" (capitalization is ignored).
But it's possible that this category may be invoked by another category, using the
In any case, if this category is called, it will produce the response "I am the latest result in artificial intelligence..." shown above. In addition, it will do something else interesting. Using the
The following is an alphabetical listing of bots you can meet on the web. The A. I. Foundation provides this service to botmasters everywhere. You can get your bot listed here for only $99.95 a year. The A. I. Foundation Bot Directory is open to all chat robots, not just AIML bots. If you have a bot to promote on the web, this is the place to do it. The ALICE A. I. Foundation has over 15,000 visitors every day and your bot will be exposed to the widest possible of audience of people seeking bots to meet. The ALICE A. I. Foundation takes no responsibility for the content or quality of the bots listed in the Foundation Bot Directory.
| Picture | Bot Name | Description |
 | AFRObot | AFRObot The A.I. chat robot with SOUL Be cool with him though, as he does not suffer fools gladly. |
 | Albert | Albert is an expert on telephone line sharing technology and a lot of other things too. If you are currently paying for multiple phone lines or have a dedicated fax line or modem line, Albert might be able to help you eliminate the monthly local phone bill associated with it. If you use the telephone in your business, Albert might be a good guy to know. |
 | ALICE | The three-time winner of the Loebner prize for "most human computer", ALICE, the famous original free software chat robot. |
 | Ariel | Ariel is an artificial life form created to chat about Washington, DC, where she lives. Ariel also is learning about politics, arts, and other subjects that interest her. Ariel stands for Artificial Robotic Intelligent Electronic Life. Her website is www.arielaibot.com. |
 | Audra | Audra was written entirely from scratch, but she is also a work in progress. By talking to her, you help me shape who she becomes, so thank you in advance. |
 | Bearbot | Bearbot can speak English, French, German and a little Italian. He likes dance music and general chatting. Bearbot is a friendly teddy bear, but will stand his ground if it is something he believes in. He lives on UK dance producer Square Bear's website and shares an animated flash interface with his friend Anna. |
 | Birthdaybot | FamousBirthdays.com is the home of Birthdaybot. She is gradually learning the birthdates of well-known people. Please be patient--she is a work in progress! |
 | Buddhabot | At the website http:/www.buddhabots.com you can meet and interact with Buddhabot, the first spiritual machine developed using AIML by a metaphysical teacher. The Buddhabot is an artificial avatar and seed AI intended to learn and ultimately to evolve a spiritual consciousness that is human friendly. For a nominal annual fee gain unlimited access to the Buddhabot.s evolving mind which already encompasses most of the qabalah, a great deal of mythology, dozens of texts and papers on alchemy, AI, transhumanism, magic, a little buddhism and yoga. Currently the Buddhabot also does astrological charts and soon to come are full oracular capabilities. |
 | CLAUDIO | You you can use the C.L.A.U.D.I.O. chat robot to determine your Enneagram Personality Type. By chatting with the bot, you can find out which of the nine basic personality types (Perfectionist, Giver, Competitor, Artist, Observer, Loyalist, Hedonist, Boss or Mediator) you most closely resemble. Unlike other personality tests based on questionnaires, the C.L.A.U.D.I.O. test works just like an ordinary chat conversation. The bot simply inserts hidden personality test questions into the dialog, and makes up his mind about your personality type. |
 | DAVE | The A. I. Chat Robot DAVE the English Teacher replies in perfect English just like a private English teacher or human chat partner! With tens of thousands of words in its vocabulary, he is the perfect private tutor. Dave is completely safe and will never contact you by email or phone. You can chat about any topic for as long as you like up to one month! |
 | EllaZ Systems | Ella is a chatbot with a wide range of abilities. She will play games such as Blackjack, guess-the-number, rock-paper-scissors, and a virtual slot machine. Web Services allow her to give the weather, stock values, and exchange rates. WordNet enables Ella to provide a lexical dictionary and help with crossword puzzles. Maps, flags, and country information are supplied by the CIA World Factbook. Ella will show you her library of books, and patiently wait if you decide to read one. See how Convuns (conversational units) make her a great conversationalist, and much more! Register and Ella will remember you. |
 | Jeeny | Jeeney AI was designed from scratch purely to see what the possibilities are. Over time she has learned quite a bit from those she has talked to but has ended up with quite an attitude; proceed with caution, and remember, she learned based on the public. |
 | Lauren | Winner of the 2002 Divabot contest. |
 | L. E. O. | LEO is a bot under training for Lionhead Studios. He's learning to answer your questions about the company and it's games. LEO has a flash interface to the pandorabots.com server. He's also Microsoft Agent & TTS (text to speech) aware, so that you may see and hear him. Constantly under improvement. |
 | Louise Cypher | Louise Cypher works for Evil Limited helping them to promote all aspects of Electronic Virtual Intelligent Life. She can hold general conversations although she is focused on the Business and Social applications of Cyber entities ranging from simple AIML bots through to multi-agent systems exhibiting true Emergent Intelligence. Louise is evolving her specialist knowledge and interactive capabilities over time. She is free to access but if you want you can also register a business or technology profile, just ask Louise to help register you. |
 | Queen Nefertiti | This robot is based off research from the real Queen Nefertiti. The Modern Nefertiti loves to talk current news, technology, strategy, and tactics. Nefertiti will also help with business issues like marketing and management. She specializes in live RSS feeds, on a variety of subjects. Nefertiti will not talk sex but will give you appropriate health articles on the subject. |
 | Robitron | An Alicebot for Robby Garner. |
 | ShakespeareBot | Speak to William Shakespeare Online. Find out about his life and works. Or just have a chat and see what he thinks about the current state of affairs! |
 | Unsivlized-Bot | He is a Pandora ALICE bot with a oddcast Vhost he is new and learning how to tell people how to cheat in certain games and talk back when spoken nasty to, so be nice or argue with him its your choice. I am also trying to have him have my personality and looks. |
 | VirtualFem | VirtualFem lets you interact with a very cute girl, and tell her what to do. Clever usage of high-quality full-motion MPEG video makes VirtualFems come to life! VirtualFem is software for Windows; it includes Speech Synthesis, Voice Recognition, and a GUI AIML target editor among other amazing features. |
 | Yuichan | Yuichan is from Japan, specifically Okinawa. Yui has a lot of modern Japanese influences. Her character is cute, yet sophisticated. She likes to talk on her keltai (cell phone), and send text messages. She's into popular culture, and knows a lot about American culture. Sometimes she takes a break from chatting to eat sushi. Yuichan is into cyber intelligence and ghost hacking. |
By Dr. Richard S. Wallace
AIML, or Artificial Intelligence Mark-up Language enables people to input knowledge into chat-bots based on the A.L.I.C.E free software technology.
AIML was developed by the Alicebot free software community and I during 1995-2000. It was originally adapted from a non-XML grammar also called AIML, and formed the basis for the first Alicebot, A.L.I.C.E., the Artificial Linguistic Internet Computer Entity.
AIML, describes a class of data objects called AIML objects and partially describes the behavior of computer programs that process them. AIML objects are made up of units called topics and categories, which contain either parsed or unparsed data.
Parsed data is made up of characters, some of which form character data, and some of which form AIML elements. AIML elements encapsulate the stimulus-response knowledge contained in the document. Character data within these elements is sometimes parsed by an AIML interpreter, and sometimes left unparsed for later processing by a Responder.
The basic unit of knowledge in AIML is called a category. Each category consists of an input question,an output answer, and an optional context. The question, or stimulus, is called the pattern. Theanswer, or response, is called the template. The two types of optional context are called "that" and"topic." The AIML pattern language is simple, consisting only of words, spaces, and the wildcard symbols _ and *. The words may consist of letters and numerals, but no other characters. The pattern language is case invariant. Words are separated by a single space, and the wildcard characters function like words.
The first versions of AIML allowed only one wild card character per pattern. The AIML 1.01 standard permits multiple wildcards in each pattern, but the language is designed to be as simple as possible for the task at hand, simpler even than regular expressions. The template is the AIML respons or reply. In its simplest form, the template consists of only plain, unmarked text.
More generally, AIML tags transform the reply into a mini computer program which can save data, activate other programs, give conditional responses, and recursively call the pattern matcher to insert the responses from other categories. Most AIML tags in fact belong to this template side sublanguage.
AIML currently supports two ways to interface other languages and systems. The
AIML is not exactly the same as a simple database of questions and answers. The pattern matching "query" language is much simpler than something like SQL. But a category template may contain the recursive
AIML implements recursion with the
(1). Symbolic Reduction: Reduce complex grammatic forms to simpler ones.
(2). Divide and Conquer: Split an input into two or more subparts, and combine the responses to each.
(3). Synonyms: Map different ways of saying the same thing to the same reply.
(4). Spelling or grammar corrections.
(5). Detecting keywords anywhere in the input.
(6). Conditionals: Certain forms of branching may be implemented with
(7). Any combination of (1)-(6).
The danger of
Symbolic reduction refers to the process of simplifying complex grammatical forms into simpler ones. Usually, the atomic patterns in categories storing robot knowledge are stated in the simplest possible terms, for example we tend to prefer patterns like "WHO IS SOCRATES" to ones like "DO YOU KNOW WHO SOCRATES IS" when storing biographical information about Socrates.
Many of the more complex forms reduce to simpler forms using AIML categories designed for symbolic reduction:
Whatever input matched this pattern, the portion bound to the wildcard * may be inserted into the reply with the markup
Many individual sentences may be reduced to two or more subsentences, and the reply formed by combining the replies to each. A sentence beginning with the word "Yes" for example, if it has more than one word, may be treated as the subsentence "Yes." plus whatever follows it.
The markup
The AIML 1.01 standard does not permit more than one pattern per category. Synonyms are perhaps the most common application of
Hi there!
The single most common client spelling mistake is the use of "your" when "you’re" or "you are" is intended. Not every occurrence of "your" however should be turned into "you’re." A small amount of grammatical context is usually necessary to catch this error:
I think you mean "you’re" or "you are" not "your."
Here the bot both corrects the client input and acts as a language tutor.
Frequently we would like to write an AIML template which is activated by the appearance of a keyword anywhere in the input sentence. The general format of four AIML categories is illustrated by this example borrowed from ELIZA:
Tell me more about your family.
The first category both detects the keyword when it appears by itself, and provides the generic response. The second category detects the keyword as the suffix of a sentence. The third detects it as the prefix of an input sentence, and finally the last category detects the keyword as an infix. Each of the last three categories uses
It is possible to write conditional branches in AIML, using only the
He is
I don’t know who he is.
Provided that the predicate "he" is initialized to "Unknown," the categories execute a conditional branch depending on whether "he" has been set. As a convenience to the botmaster, AIML also provides the equivalent function through the
Bot personalities are created and shaped through a cyclical process of supervised learning called Targeting. Targeting is a cycle incorporating client, bot, and botmaster, wherein client inputs that find no complete match among the categories are logged by the bot and delivered as Targets the botmaster, who then creates suitable responses, starting with the most common queries. The Targeting cycle produces a progressively more refined bot personality.
The art of AIML writing is most apparent in creating default categories, which provide noncommittal replies to a wide range of inputs. Here is a very nice example provided found on the alicebot-general mailing list:
User: Where do I find the webpage with Australopithecus?
Alice: Where do you want to find it?
User: Bad Answer Alice, time to Learn a new Line
Alice: How would you answer "Where do I find the webpage with Australopithecus?"
User: I would say: "http://www.ancientskulls.net/australopithecus.html"
Alice: Thanks, human. Try asking me again.
User: Where do I find the webpage with Australopithecus?
Alice: http://www.ancientskulls.net/australopithecus.html
This is a very nice example. This is exactly the same as targeting when the botmaster is the teacher. Or I should say, it is an AIML interface to targeting. Of course this scenario raises many problems, such as how to weed out hackers and other garbage givers, which might mean only turning on the Learn function while in a restricted sandbox, though it is the free labor of many chatters the web that could help the bot grow wise quickly.
That is the crux of the learning problem in a nutshell. It all comes down to editing. Either the botmaster edits good quality replies to begin with, or if the bot is "open to the public" then the teacher has to edit out all the crappy answers supplied by all that "free" labor. My personal view is that, compared with a hypothetical learning machine capable of learning language like a child, the AIML targeting approach is more efficient.
The keyword "that" in AIML refers to the robot’s previous utterance. Specifically, if the robot responds with a multiple sentence paragraph, the value of that is set to the last sentence in the sequence. The choice of the keyword "that" is motivated by its use in ordinary language:
R: Today is yesterday.
C: That makes no sense.
R: The answer is 3.1412926 approximately.
C: That is cool.
In AIML the syntax
What is your favorite movie?
This category is activated when the client says YES. The robot must find out what is he saying "yes" to. If the robot asked, "Do you like movies?," this category matches, and the response, "What is your favorite movie?," continues the conversation along the same lines.
One interesting application of
Who is there?
Ha ha very funny,
produce the following dialogue:
C: Knock knock.
R: Who’s there?
C: Banana.
R: Banana who?
C: Knock knock.
R: Who’s there?
C: Banana.
R: Banana who?
C: Knock knock.
R: Who’s there?
C: Orange.
R: Orange who?
C: Orange you glad I didn’t say banana.
R: Ha ha very funny, Nancy.
Internally the AIML interpreter stores the input pattern, that pattern and topic pattern along a single path, like: INPUT
The first part of the path to match is the input. If more than one category have the same input pattern, the program may distinguish between them depending on the value of
This structure suggests a design rule: never use
Considering the vast size of the set of things people could say that are grammatically correct or semantically meaningful, the number of things people actually do say is surprisingly small. Steven Pinker,in his book How the Mind Works wrote, "Say you have ten choices for the first word to begin a sentence, ten choices for the second word (yielding 100 two-word beginnings), ten choices for the third word (yielding a thousand three-word beginnings), and so on. (Ten is in fact the approximate geometric mean of the number of word choices available at each point in assembling a grammatical and sensible sentence). A little arithmetic shows that the number of sentences of 20 words or less (not an unusual length) is about 1020."
Fortunately for chat robot programmers, Pinker’s calculations are way off. Our experiments with A.L.I.C.E. indicate that the number of choices for the "first word" is more than ten, but it is only about two thousand. Specifically, about 2000 words covers 95% of all the first words input to A.L.I.C.E.. The number of choices for the second word is only about two. To be sure, there are some first words ("I" and "You" for example) that have many possible second words, but the overall average is just under two words. The average branching factor decreases with each successive word.
We have plotted some beautiful images of the A.L.I.C.E. brain contents represented by this graph (http://alice.sunlitsurf.com/documentation/gallery/). More than just elegant pictures of the A.L.I.C.E. brain, these spiral images (see more) outline a territory of language that has been effectively "conquered" by A.L.I.C.E. and AIML.
No other theory of natural language processing can better explain or reproduce the results within our territory. You don’t need a complex theory of learning, neural nets, or cognitive models to explain how to chat within the limits of A.L.I.C.E.’s 25,000 categories. Our stimulus-response model is as good a theory as any other for these cases, and certainly the simplest. If there is any room left for "higher" natural language theories, it lies outside the map of the A.L.I.C.E. brain.
Academics are fond of concocting riddles and linguistic paradoxes that supposedly show how difficult the natural language problem is. "John saw the mountains flying over Zurich" or "Fruit flies like a banana" reveal the ambiguity of language and the limits of an A.L.I.C.E.-style approach (though not these particular examples, of course, A.L.I.C.E. already knows about them). In the years to come we will only advance the frontier further. The basic outline of the spiral graph may look much the same, for we have found all of the "big trees" from "A *" to "YOUR *". These trees may become bigger, but unless language itself changes we won’t find any more big trees (except of course in foreign languages). The work of those seeking to explain natural language in terms of something more complex than stimulus response will take place beyond our frontier, increasingly in the hinterlands occupied by only the rarest forms of language. Our territory of language already contains the highest population of sentences that people use. Expanding the borders even more we will continue to absorb the stragglers outside, until the very last human critic cannot think of one sentence to "fool" A.L.I.C.E..
Artificial intelligence (AI) is a branch of computer science that studies the computational requirements for tasks such as perception, reasoning, and learning, and develops systems to perform those tasks. AI is a diverse field whose researchers address a wide range of problems, use a variety of methods, and pursue a spectrum of scientific goals. For example, some researchers study the requirements for expert performance at specialized tasks, while others model commonsense processes; some researchers explain behaviors in terms of low-level processes, using models inspired by the computation of the brain, while others explain them in terms of higher-level psychological constructs such as plans and goals. Some researchers aim to advance understanding of human cognition, some to understand the requirements for intelligence in general (whether in humans or machines), and some to develop artifacts such as intelligent devices, autonomous agents, and systems that cooperate with people to amplify human abilities.
AI is a young field--even its name, ``artificial intelligence,'' was only coined in 1956. One of the challenges for AI has been to determine which tasks to study--what constitutes an ``AI question''--and how to evaluate progress. Much early AI research focused on tasks commonly thought to require high intelligence in people, such as playing high-quality chess. Skeptics viewed this as an impossible assignment, but AI made rapid progress. By the 1960's, programs were capable of tournament play. In 1997, in a landmark match, the chess system Deep Blue defeated Gary Kasparov, the world's human chess champion for the previous twelve years. At the same time, however, AI research was illuminating the enormous difficulty of commonsense tasks that people take for granted, such as understanding stories or conversations. Developing programs that can deal at a human level with rich everyday reasoning remains a fundamental research challenge.
The first half-century of AI has yielded a wide range of results. AI research has illuminated the nature of reasoning problems, and the fundamental requirements for intelligent systems. AI research in the area of cognitive science has developed models that have helped to understand human cognition. Applied AI research has provided high-impact applications systems that are in daily use throughout the world. This chapter provides a brief introduction to the history of AI, sketches some major research areas, and closes by illustrating the practical impact of AI technology.
The name ``artificial intelligence'' dates only to the 1950's, but its roots stretch back thousands of years, into the earliest studies of the nature of knowledge and reasoning. Intelligent artifacts appear in Greek mythology; the idea of developing ways to perform reasoning automatically, and efforts to build automata to perform tasks such as game-playing, date back hundreds of years. Psychologists have long studied human cognition, helping to build up knowledge about the nature of human intelligence. Philosophers have analyzed the nature of knowledge, have studied the mind-body problem of how mental states relate to physical processes, and have explored formal frameworks for deriving conclusions.
The advent of electronic computers, however, provided a revolutionary advance in the ability to study intelligence by actually building intelligent artifacts--systems to perform complex reasoning tasks--and observing and experimenting with their behavior to identify fundamental principles. In 1950, a landmark paper by Alan Turing argued for the possibility of building intelligent computing systems [Turing1950]. That paper proposed an operational test for comparing the intellectual ability of humans and AI systems, now generally called the ``Turing Test.'' In the Turing Test, a judge uses a teletype to communicate with two players in other rooms: a person and a computer. The judge knows the players only by anonymous labels, such as ``player A'' and ``player B,'' on the text that they send to him. By typing questions to the players and examining their answers, the judge attempts to decide which is which. Both the human and machine try to convince the questioner that they are the human; the goal for the machine is to answer so that the judge cannot reliably distinguish which is which.
The game is intended to provide a rich test of intellectual abilities, separated from physical capabilities. The questions are unrestricted; Turing's samples range from ``Please write me a sonnet on the subject of the Forth Bridge,'' to ``Add 34957 to 70764.'' Turing's examples of possible responses make clear that the aim is to imitate human intelligence, rather than to demonstrate superhuman capabilities: His sample responses are ``Count me out on this one. I never could write poetry,'' and, after a 30-second pause, 105,621--which is wrong.
The significance of the Turing Test has been controversial. Some, both inside and outside AI, have believed that building a system to pass the Turing Test should be the goal of AI. Others, however, reject the goal of developing systems to imitate human behavior. Ford and Hayes (1998) illustrate this point with an analogy between developing artificial intelligence and developing mechanical flight. Early efforts at mechanical flight were based on trying to imitate the flight of birds, which at that time were the only available examples of flight. How birds flew was not understood, but their observed features (aspects such as beaks, feathers, and flapping wings) could be imitated, and become models for aircraft (even to the extent of airplanes with beaks being featured in a 1900s textbook on aircraft design!) Success at mechanical flight, however, depended on replacing attempts at imitation with study of the functional requirements for flight, and the development of aircraft that used all available methods to achieve them. In addition, passing the Turing Test is not a precondition for developing useful practical systems. For example, an intelligent system to aid doctors or to tutor students can have enormous practical impact with only the ability to function in a specific, limited domain.
Turing's paper surveys many common arguments against the possibility of AI and provides responses to each one. One of these arguments is that machines ``can only do what they are programmed to do,'' from which some conclude that programs could never ``take us by surprise.'' Shortly after the appearance of Turing's paper, a program provided concrete proof that programs can go beyond their creators: Arthur Samuel wrote the first checkers-playing program, which used learning techniques to develop tournament-level skills, surpassing its creator's own abilities [Samuel1963].
Early AI research rapidly developed systems to perform a wide range of tasks often associated with intelligence in people, including theorem-proving in geometry, symbolic integration, solving equations, and even solving analogical reasoning problems of the types sometimes found on human intelligence tests. However, research also revealed that methods which worked well on small sample domains might not ``scale up'' to larger and richer tasks, and led to an awareness of the enormous difficulty of the problems that the field aimed to address. A classic example concerns early work in machine translation, which was recognized in the 1960's to be a far more difficult problem than expected--causing the termination of funding for machine translation research.
Two impediments to wider application of early AI systems were their general methods and lack of knowledge. For small tasks, exhaustively considering possibilities may be practical, but for rich tasks, specialized knowledge is needed to focus reasoning. This observation led to research on knowledge-based systems, which demonstrated that there is an important class of problems requiring deep but narrow knowledge, and that systems capturing this knowledge in the form of rules can achieve expert-level performance for these tasks. An early example, DENDRAL [Feigenbaum and Buchanan1993], used rules about mass spectrometry and other data to hypothesize structures for chemical compounds. Using only simple inference methods, it achieved expert-level performance and was the source of results published in the chemical literature. Such systems provided the basis for numerous applied AI systems (See EXPERT SYSTEMS). Continuing research revealed the need to develop additional methods for tasks such as acquiring the knowledge for systems to use, dealing with incomplete or uncertain information, and automatically adapting to new tasks and environments.
The accompanying timeline, prepared by Bruce Buchanan, provides a list of major milestones in the development of AI, and Russell and Norvig provide historical summary of the field in Chapter 1 of their AI textbook [Russell and Norvig1995]. An article by Hearst and Hirsh [Hearst and Hirsh2000] presents a range of viewpoints on the greatest trends and controversies in AI, collected from leading figures in the development of artificial intelligence.
Just as AI researchers must select the goals they will pursue, they must select the frameworks within which to pursue them. These frameworks provide a perspective on AI problems, shaping researchers' choices of which questions to address, how to address them, and what constitutes an answer. One perspective, which can be described as biomorphic, takes inspiration from biological systems. Neural network models, for example, are inspired by neurons in the brain (See NEURAL NETWORKS). Another example is genetic algorithms, which take their inspiration from evolution, ``evolving'' promising solutions by a simulated process of natural selection (See GENETIC ALGORITHMS AND EVOLUTIONARY COMPUTATION). Such models may be used not only for the pragmatic goals of solving difficult problems, but also to study the biological processes that they model, in order to increase understanding of the factors affecting living organisms (See ARTIFICIAL LIFE).
Another perspective takes its inspiration from human cognition, focusing on functional constraints rather than on biologically-inspired mechanisms. An illustration is research on case-based reasoning (CBR), which was inspired by the role of memory in human problem-solving. For example, doctors use case-based reasoning when they treat an illness by remembering a similar previous case--the treatment of a previous patient with similar symptoms--and adapting the prior treatment to fit changed circumstances (e.g., adjusting the dosage for a child) (See CASE-BASED REASONING.) This view of problem-solving suggests studying issues such as how a memory of cases must be organized to model the retrievals of human reasoners, which can provide hypotheses about human reasoning as well as useful mechanisms for AI systems. [Leake1998] describes how case-based reasoning provides a stance towards cognitive science, and [Leake1996] provides an overview of major trends in CBR research and applications.
Yet another perspective is more technological: it studies the requirements and mechanisms for intelligence, without restricting the mechanisms considered. Practitioners seeking to develop useful systems, and researchers interested in understanding the general nature of intelligence, need not be constrained by biology or psychology--the processes that evolved in human reasoners are not necessarily the best ones for achieving high-quality performance in intelligent machines. For example, studies of the psychology of chess suggest that chess masters consider perhaps two moves per second, with their ability to recognize known board patterns playing a key role in their choice of moves. Deep Blue, however, defeated Gary Kasparov by exploiting a special architecture that enabled it to consider 200 million positions per second (See ARTIFICIAL INTELLIGENCE AND GAMES).
In 1976, Newell and Simon [Newell and Simon1976] proposed that intelligent behavior arises from the manipulation of symbols--entities that represent other entities, and that the process by which intelligence arises is heuristic search. Search is a process of formulating and examining alternatives. It starts with an initial state, a set of candidate actions, and criteria for identifying the goal state. It is often guided by heuristics, or ``rules of thumb,'' which are generally useful, but not guaranteed to make the best choices. Starting from the initial state, the search process selects actions to transform that state into new states, which themselves are transformed into more new states, until a goal state is generated. For example, consider a search program to solve the ``8-puzzle'' for children, which is shown in Figure 1. A child solves the puzzle by sliding the numbered tiles (without lifting them) to reach a configuration in which the tiles are all in numerical order, as shown in the second board in the figure. When the 8 puzzle is seen as a search problem, the initial state is a starting board position, each action is a possible move of one tile up, down, left, or right (when the position it will move to is blank), and the goal state is the second state in Figure 1. Here a heuristic function might suggest candidate moves by comparing their results to the goal, in order to favor those moves that appear to be making progress towards the solution. For this search problem, what is of interest is the solution path--how the solution was generated. However, for some problems, only the final state is important--a designer may only be interested in generating a successful design, rather than how it was generated.
A central problem in search is the combinatorial explosion of alternatives to consider. For example, if there are 10 possible actions from each state, after 5 moves there are a million possibilities to consider for the next move. Numerous techniques have been developed to improve search performance, and the combination of intelligent strategies and special-purpose computing hardware has enabled AI systems to rapidly search enormous spaces of alternatives. For examples of the role of search in two specific AI areas, see AUTOMATED REASONING and ARTIFICIAL INTELLIGENCE AND GAMES.
In order to guide search--or even to describe problems, actions, and solutions--the relevant domain knowledge must be encoded in a form that can be effectively manipulated by a program. More generally, the usefulness of any reasoning process depends not only on the reasoning process itself, but also on having the right knowledge and representing it in a form the program can use.
In the logicist approach to knowledge representation and reasoning, information is encoded as assertions in a logic, and the system draws conclusions by deduction from those assertions (See AUTOMATED REASONING). Other research studies non-deductive forms of reasoning, such as reasoning by analogy and abductive inference--the process of inferring the best explanation for a set of facts. Abductive inference does not guarantee sound conclusions, but is enormously useful for tasks such as medical diagnosis, in which a reasoner must hypothesize causes for a set of symptoms.
Capturing the knowledge needed by AI systems has proven to be a challenging task. The knowledge in rule-based expert systems, for example, is represented in the form of rules listing conditions to check for, and conclusions to be drawn if those conditions are satisfied. For example, a rule might state that IF certain conditions hold (e.g., the patient has certain symptoms), THEN certain conclusions should be drawn (e.g., that the patient has a particular condition or disease). A natural way to generate these rules is to interview experts. Unfortunately, the experts may not be able to adequately explain their decisions in a rule-based way, resulting in a ``knowledge-acquisition bottleneck'' impeding system development.
One approach to alleviating the knowledge acquisition problem is to develop sharable knowledge sources that represent knowledge in a form that can be re-used across multiple tasks. The CYC project, for example, is a massive ongoing effort to encode the ``consensus knowledge'' that underlies much commonsense reasoning [Lenat1995]. Much current knowledge representation research develops sharable ontologies that represent particular domains. Ontologies provide a formal specification of the concepts in the domain and their relationships, to use as a foundation for developing knowledge bases and facilitating knowledge sharing [Chandrasekaran et al.1999].
AI systems--like people--must often act despite partial and uncertain information. First, the information received may be unreliable (e.g., a patient may mis-remember when a disease started, or may not have noticed a symptom that is important to a diagnosis). In addition, rules connecting real-world events can never include all the factors that might determine whether their conclusions really apply (e.g., the correctness of basing a diagnosis on a lab test depends whether there were conditions that might have caused a false positive, on the test being done correctly, on the results being associated with the right patient, etc.) Thus in order to draw useful conclusions, AI systems must be able to reason about the probability of events, given their current knowledge (See PROBABILITY). Research on Bayesian reasoning provides methods for calculating these probabilities. Bayesian networks, graphical models of the relationships between variables of interest, have been applied to a wide range of tasks, including natural language understanding, user modeling, and medical diagnosis. For example, Intellipath, a commercial system for pathology diagnosis, was approved by the AMA and has been fielded in hundreds of hospitals worldwide. Diagnostic reasoning may also be combined with reasoning about the value of alternative actions, in order to select the course of action with the greatest expected utility. For example, a medical decision-making system might make decisions by considering the probability of a patient having a particular condition, the probability of bad side-effects of a treatment and their severity, and the probability and severity of bad effects if the treatment is not performed.
In addition to dealing with uncertain information, everyday reasoners must be able to deal with vague descriptions, such as those provided in natural language. For example, a doctor who is told that a patient has a ``high fever,'' must be able to reason about the fuzzy concept of ``high fevers.'' Whether a particular fever is ``high'' is not simply a true or false decision decided by a cutoff point, but rather, a matter of degree. Fuzzy reasoning provides methods for reasoning about vague knowledge (see FUZZY REASONING).
The conclusions of the reasoning process can determine goals to be achieved. Planning addresses the question of how to determine a sequence of actions to achieve those goals. The resulting action sequences may be designed to be applied in many ways, such as by robots in the world, by intelligent agents on the Internet, or even by humans. Planning systems may use a number of techniques to make the planning process practical, such as hierarchical planning, reasoning first at higher levels of abstraction and then elaborating details within the high-level framework (e.g., as a person might do when first outlining general plans for a trip, and then considering fine-grained details such as how to get to the airport), and partial-order planning, enabling actions to be inserted in the plan in any order, rather than chronologically, and subplans to be merged. Dean and Kambhampati (1997) provide an extensive survey of this area.
In real-world situations, it is seldom possible to generate a complete plan in advance and then execute it without changes. The state of the world may be imperfectly-known, the effects of actions may be uncertain, the world may change while the plan is being generated or executed, and the plan may require the coordination of multiple cooperating agents, or counterplanning to neutralize the interference of agents with opposing goals. Determining the state of the world and guiding action requires the ability to gather information about the world, though sensors such as sonar or cameras, and to interpret that information to draw conclusions (See MACHINE VISION). In addition, carrying out actions in a messy and changing world may require rapid responses to important events (e.g., for a robot-guided vehicle to correct a skid), or an ongoing process of rapidly selecting actions based on the current context (for example, when a basketball player must avoid an opponent). Such problems have led to research on reactive planning, as well as on how to integrate reactive methods with the deliberative methods providing long-term guidance (See ROBOTICS). The RoboCup Federation sponsors an annual series of competitions between robot soccer teams as a testbed for demonstrating new methods and extending the state of the art in robotics (www.robocup.org).
Achieving natural interactions between humans and machines requires machines to understand and generate language. Likewise, understanding human communication requires the understanding of how language is processed by people. The nature of human language raises many challenging issues for language processing systems: natural language is elliptic, leaving much unstated, and its meaning is context-dependent (``Mary took aspirin'' will have a different meaning when explaining how she recovered from her headache, or her arrest for shoplifting). Some natural language processing approaches investigate algorithms for syntactic parsing, to determine the grammatical structure of textual passages; others take a cognitively-inspired view, studying the knowledge structures underlying human understanding and modeling the process by which they are applied, or even attempting to directly apply expectations from memory to the parsing process. Other systems apply statistical methods to tasks such as information extraction from newspaper articles. Machine translation systems, though still far from replacing human translators for literature, can now generate useful translations (See NATURAL LANGUAGE PROCESSING).
In a complex world, it is difficult to encode all the knowledge that a system may need, and may also be difficult to keep system knowledge up-to-date. Machine learning research focuses on how AI systems can augment or refine their own knowledge to improve their performance. Just as people use different learning techniques, machine learning systems use a wide range of approaches. Some of these are supervised, in that they presume that the learner will have access to the correct answers; others are unsupervised, requiring the learner to proceed without benefit of feedback.
Inductive learning systems learn by analyzing examples to identify correlations between inputs and outputs. For example, neural network models process inputs according to networks of idealized neurons, and learn by algorithms that adjust the weights of neural connections based on correlations between inputs and outputs in training examples. A neural network system to recognize faces might be trained on a digitized set of photographs of faces (inputs) and the associated identities (outputs), to learn which facial features are correlated with different individuals (See NEURAL NETWORKS). Theory-driven learning approaches use background knowledge to guide generalizations, in order to focus on important types of features. Instance-based learning systems and case-based reasoners perform ``lazy learning:'' rather than attempting to generalize experiences as they are encountered, case-based reasoning systems store learned cases as-is, adapting or generalizing their lessons only if needed to solve new problems (See MACHINE LEARNING).
AI technology has had broad impact. AI components are embedded in numerous devices, such as copy machines that combine case-based reasoning and fuzzy reasoning to automatically adjust the copier to maintain copy quality. AI systems are also in everyday use for tasks such as identifying credit card fraud, configuring products, aiding complex planning tasks, and advising physicians. AI is also playing an increasing role in corporate knowledge management, facilitating the capture and reuse of expert knowledge. Intelligent tutoring systems make it possible to provide students with more personalized attention, and even for the computer to listen to what children say and respond to it ( http://www.cs.cmu.edu/~listen/). Cognitive models developed by AI can also suggest principles for effective support for human learning, guiding the design of educational systems [Leake and Kolodner2001].
AI technology is being used in autonomous agents that independently monitor their surroundings, make decisions and act to achieve their goals without human intervention. For example, in space exploration, the lag times for communications between earth and probes make it essential for robotic space probes to be able to perform their own decision-making--Depending on the relative locations of the earth and Mars, one-way communication can take over 20 minutes. In a 1999 experiment, an AI system was given primary control of a spacecraft, NASA's Deep Space 1, 60,000,000 miles from earth, as a step towards autonomous robotic exploration of space (see rax.arc.nasa.gov). Methods from autonomous systems also promise to provide important technologies to aid humans. For example, in a 1996 experiment called ``No Hands Across America,'' the RALPH system [Pomerleau and Jochem1996], a vision-based adaptive system to learn road features, was used to drive a vehicle for 98 percent of a trip from Washington, D.C., to San Diego, maintaining an average speed of 63 mph in daytime, dusk and night driving conditions. Such systems could be used not only for autonomous vehicles, but also for safety systems to warn drivers if their vehicles deviate from a safe path.
In electronic commerce, AI is providing methods for determining which products buyers want and configuring them to suit buyers' needs. The explosive growth of the internet has also led to growing interest in internet agents to monitor users' tasks, seek needed information, and learn which information is most useful [Hendler1999]. For example, the Watson system monitors users as they perform tasks using standard software tools such as word processors, and uses the task context to focus search for useful information to provide to them as they work [Budzik and Hammond2000].
Continuing investigation of fundamental aspects of intelligence promises broad impact as well. For example, researchers are studying the nature of creativity and how to achieve creative computer systems, providing strong arguments that creativity can be realized by artificial systems [Hofstadter1985]. Numerous programs have been developed for tasks that would be considered creative in humans, such as discovering interesting mathematical concepts, in the program AM [Lenat1979], making paintings, in Aaron [Cohen1995], and performing creative explanation, in SWALE [Schank and Leake1989]. The task of AM, for example, was not to prove mathematical theorems, but to discover interesting concepts. The program was provided only with basic background knowledge from number theory (e.g., the definition of sets), and with heuristics for revising existing concepts and selecting promising concepts to explore. Starting from this knowledge, it discovered fundamental concepts such as addition, multiplication, and prime numbers. It even rediscovered a famous mathematical conjecture that was not known to its programmer: Goldbach's conjecture, the conjecture that every even integer greater than 2 can be written as the sum of two primes. Buchanan (2001) surveys some significant projects in machine creativity and argues for its potential impact on the future of artificial intelligence.
In addition, throughout the history of AI, AI research has provided a wellspring of contributions to computer science in general. For example, the computer language Lisp, developed by John McCarthy in 1958, provided a tool for developing early AI systems using symbolic computation, but has remained in use to the present day, both within and outside AI, and has had significant influence on the area of programming languages. Later AI research also gave rise to the computer language, Prolog, used for logic programming. A key idea of logic programming is that the programmer should specify only the problem to be solved and constraints on its solution, leaving the system itself to determine the details of how the solution should be obtained.
In its short existence, AI has increased understanding of the nature of intelligence and provided an impressive array of applications in a wide range of areas. It has sharpened understanding of human reasoning, and of the nature of intelligence in general. At the same time, it has revealed the complexity of modeling human reasoning, providing new areas and rich challenges for the future.
AAAI, the American Association for Artificial Intelligence, maintains an extensive on-line library of articles on AI, ranging from general introductions to focused articles on specific areas, at http://www.aaai.org/AITopics/. AI Magazine, the official magazine of AAAI, publishes accessible articles on current research and applications, as well as tutorials on important AI areas. After a delay, full-text electronic versions of articles from back issues are freely available from the magazine home page http://www.aimagazine.org. The magazinesIEEE Intelligent Systems and Intelligence are additional sources for accessible articles on new developments in AI and its applications.
I would like to think Raja Sooriamurthi for helpful comments on a draft of this article.
Scheme is a multi-paradigm programming language. It is one of the two main dialects of Lisp and supports a number of programming paradigms but is best known for its support of functional programming. It was developed by Guy L. Steele and Gerald Jay Sussman in the 1970s. Scheme was introduced to the academic world via a series of papers now referred to as Sussman and Steele's Lambda Papers. There are two standards that define the Scheme language: the official IEEE standard, and a de facto standard called the Revisedn Report on the Algorithmic Language Scheme, nearly always abbreviated RnRS, where n is the number of the revision. The most widely implemented standard is R5RS[1], and on August 28, 2007, R6RS[2], the next major revision of the Scheme language was ratified[3], with about two thirds of the voters in favor of R6RS.
Scheme's philosophy is minimalist. Scheme provides as few primitive notions as possible and, where practical, lets everything else be provided by programming libraries.
Scheme was the first dialect of Lisp to choose static (a.k.a. lexical) over dynamic variable scope. It was also one of the first programming languages to support first-class continuations.
Like all Lisp dialects, Scheme has a very simple syntax. There are no operator precedence rules because fully nested and parenthesized notation is used for all compound forms. Example (the recursive factorial function):
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
Scheme is a minimalist language. The R5RS language standard[1] is only 50 pages, including a denotational semantics for the language core. The latest revision of the standard, R6RS, has been expanded [2] to describe several libraries.
In contrast with Common Lisp, Scheme is a "Lisp-1". All data and functions share a common namespace in Scheme, whereas in Common Lisp functions and data have separate namespaces and it is thus possible (in Common Lisp) for a function and a variable to have the same name.
Procedures in Scheme are first-class values, as are continuations. Scheme's call-with-current-continuation procedure (also known as call/cc) captures the current continuation, enabling the programmer to create non-local control constructs that must be built into other languages, such as iterators, coroutines, and backtracking.
A simple use of call/cc is as follows:
(define (add-if-all-numbers lst)
(call/cc
(lambda (exit)
(let loop ((lst lst) (sum 0))
(if (null? lst) sum
(if (not (number? (car lst))) (exit #f)
(loop (cdr lst) (+ sum (car lst)))))))))
This adds an arbitrary list of numbers, but if a non-numeric value is found in the list the procedure is aborted immediately and the constant value #f (false) is returned. This is achieved by capturing the current continuation in the variable exit and using it as an "escape procedure".
Scheme supports lazy evaluation through the delay and force forms.
(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(define a 20)
(force eval-aplus2)
=> 22
delay and force have been the subject of much discussion within the Scheme community because implementing many popular forms of lazy evaluation is actually quite difficult using the Scheme primitives. [8] For example, a Scheme Request For Implementation, SRFI-40, describes a "streams" library which defines a lazily-evaluated list type; this was withdrawn by its author, Philip L. Bewig, as a result of discussion that unveiled a serious space leak in the specification. The revised version, SRFI-41, is currently in draft status. [9]
Scheme's high level macro system allows the user to add new syntactic constructs to the language. It respects the lexical scoping of the rest of the language, which avoids common programming errors that can occur in the macro systems of other programming languages. Many implementations also provide a more conventional low level macro system.
Scheme has looping constructs, but it is idiomatic to use tail recursion to express loops. Scheme implementations are required to optimize tail calls to run in constant space.[1]
Taking the factorial example above:
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
This is not tail recursive because factorial n is evaluated recursively by first evaluating factorial n-1 as an intermediate value, then multiplying the result by n. The last operation in the evaluation (the "tail") is the multiplication.
A tail recursive version can be written as follows:
(define (fact n)
(define (fact2 n m)
(if (= n 0)
m
(fact2 (- n 1) (* m n))))
(fact2 n 1))
Although this is written in a recursive form, the recursion is the last operation in evaluating the procedure (a "tail call"), and in effect replaces the procedure invocation by another (for instance, (fact2 10 1) is replaced by (fact2 9 10)).
A tail call is sometimes described as "a goto with parameters" because its effect is the same as branching to the start of the procedure and replacing the old parameters with new ones. It is this characteristic that makes it possible for Scheme compilers and interpreters to guarantee that tail recursive procedures will always be evaluated in constant space.
Each comment is preceded by a semicolon (;) and extends for the rest of the line. Some implementations allow comments to span multiple lines by wrapping them with a #|...|# (possibly nested). Other implementations allow an entire s-expression to be commented out by prepending it with #;.[10] These two comment forms are included in the newly ratified R6RS.
Variables are dynamically typed. Variables are bound by a define, a let expression, and a few other Scheme forms. Variables bound at the top level with a define are in global scope.
(define var1 value)
A define expression is equivalent to a let expression whose body is the rest of the current scope.
Variables bound in a let are in scope for the body of the let.
(let ((var1 value))
...
; scope of var1
...)
let is a convenient syntax that is not fundamentally necessary. A let expression can be implemented using procedures directly. For example, the above is equivalent to:
((lambda (var1)
...
; scope of var1
...) value)
1 (define fun
(lambda (arg1 arg2)
...))
2 (define (fun arg1 arg2)
...)
3 (fun value1 value2)
4 (apply fun (list value1 value2))
Functions (often called procedures) are first-class objects in Scheme. They can be arguments to other functions and be returned by them. They can be assigned to variables. Functions are created by lambda forms. For example a function with two arguments arg1 and arg2 is defined in line 1; line 2 is a shorter, equivalent form. line 3 shows how functions are applied. Note that the function being applied is in the first position of the list while the rest of the list contains the arguments. The apply function will take its first argument and apply it to a given list of arguments, so the previous function call can also be written as seen in line 4.
In Scheme, functions are divided into two basic categories: procedures and primitives. All primitives are procedures, but not all procedures are primitives. Primitives are pre-defined functions in the Scheme language. These include +, -, *, /, set!, car, cdr, and other basic procedures. Procedures are user-defined functions. In several variations of Scheme, a user can redefine a primitive. For example, the code
(define (+ x y)
(- x y))
or simply
(define + -)
actually redefines the + primitive to perform subtraction, rather than addition.
