Introduction

<< Detailed Table of Contents

Problem Solving >>

Artificial Intelligence (CS607)

Artificial Intelligence

1 Introduction

This booklet is organized as chapters that elaborate on various concepts of

Artificial Intelligence. The field itself is an emerging area of computer sciences

and a lot of work is underway in order to mature the concepts of this field.

In this booklet we will however try to envelop some important aspects and basic

concepts which will help the reader to get an insight into the type of topics that

Artificial Intelligence deals with.

We have used the name of the field i.e. Artificial Intelligence (commonly referred

as AI) without any explanation of the name itself. Let us now look into a simple

but comprehensive way to define the field.

To define AI, let us first try to understand that what is Intelligence?

1.1 What is Intelligence?

If you were asked a simple question; how can we define Intelligence, many of

you would exactly know what it is but most of you won't exactly be able to define

it. Is it something tangible? We all know that it does exist but what actually it is.

Some of us will attribute intelligence to living beings and would be of the view that

all living species are intelligent. But how about these plants and tress, they are

living species but are they also intelligent? So can we say that Intelligence is a

trait of some living species? Let us try to understand the phenomena of

intelligence by using a few examples.

Consider the following image where a mouse is trying to search a maze in order

to find its way from the bottom left to the piece of cheese in the top right corner of

the image.

This problem can be considered as a common real life problem which we deal

with many times in our life, i.e. finding a path, may be to a university, to a friends

house, to a market, or in this case to the piece of cheese. The mouse tries

various paths as shown by arrows and can reach the cheese by more than one

path. In other words the mouse can find more than one solutions to this problem.

The mouse was intelligent enough to find a solution to the problem at hand.

Hence the ability of problem solving demonstrates intelligence.

Let us consider another problem. Consider the sequence of numbers below:

1, 3, 7, 13, 21, ___

Artificial Intelligence (CS607)

If you were asked to find the next number in the sequence what would be your

answer? Just to help you out in the answer let us solve it for you "adding the next

even number to the" i.e. if we add 2 to 1 we get 3, then we add 4 to 3 we get 7,

then we get 6 to 7 we get 13, then we add 8 to 13 we get 21 and finally if we'll

add 10 to 21 we'll get 31 as the answer. Again answering the question requires a

little bit intelligence. The characteristic of intelligence comes in when we try to

solve something, we check various ways to solve it, we check different

combinations, and many other things to solve different problems. All this thinking,

this memory manipulation capability, this numerical processing ability and a lot of

other things add to ones intelligence.

All of you have experienced your college life. It was very easy for us to look at the

timetable and go to the respective classes to attend them. Not even caring that

how that time table was actually developed. In simple cases developing such a

timetable is simple. But in cases where we have 100s of students studying in

different classes, where we have only a few rooms and limited time to schedule

all those classes. This gets tougher and tougher. The person who makes the

timetable has to look into all the time schedule, availability of the teachers,

availability of the rooms, and many other things to fit all the items correctly within

a fixed span of time. He has to look into many expressions and thoughts like "If

room A is free AND teacher B is ready to take the class AND the students of the

class are not studying any other course at that time" THEN "the class can be

scheduled". This is a fairly simple one, things get complex as we add more and

more parameters e.g. if we were to consider that teacher B might teach more

than one course and he might just prefer to teach in room C and many other

things like that. The problem gets more and more complex. We are pretty much

sure than none of us had ever realized the complexity through which our teachers

go through while developing these schedules for our classes. However, like we

know such time tables can be developed. All this information has to reside in the

developer's brain. His intelligence helps him to create such a schedule. Hence

the ability to think, plan and schedule demonstrate intelligence.

Consider a doctor, he checks many patients daily, diagnoses their disease gives

them medicine and prescribes them behaviors that can help them to get cured.

Let us think a little and try to understand that what actually he does. Though

checking a patient and diagnosing the disease is much more complex but we'll try

to keep our discussion very simple and will intentionally miss out stuff from this

discussion.

A person goes to doctor, tells him that he is not feeling well. The doctor asks him

a few questions to clarify the patient's situation. The doctor takes a few

measurements to check the physical status of the person. These measurements

might just include the temperature (T), Blood Pressure (BP), Pulse Rate (PR) and

things like that. For simplicity let us consider that some doctor only checks these

measurements and tries to come up with a diagnosis for the disease. He takes

these measurements and based on his previous knowledge he tries to diagnose

the disease. His previous knowledge is based on rules like: "If the patient has a

high BP and normal T and normal PR then he is not well". "If only the BP is

normal then what ever the other measurements may be the person should be

healthy", and many such other rules.

Artificial Intelligence (CS607)

The key thing to notice is that by using such rules the doctor might classify a

person to be healthy or ill and might as well prescribe different medicines to him

using the information observed from the measurements according to his previous

knowledge. Diagnosing a disease has many other complex information and

observations involved, we have just mentioned a very toy case here. However,

the doctor is actually faced with solving a problem of diagnosis having looked at

some specific measurements. It is important to consider that a doctor who would

have a better memory to store all this precious knowledge, better ability of

retrieving the correct portion of the knowledge for the correct patient will be better

able to classify a patient. Hence, telling us that memory and correct and

efficient memory and information manipulation also counts towards ones

intelligence.

Things are not all that simple. People don't think about problems in the same

manner. Let us give you an extremely simple problem. Just tell us about your

height. Are you short, medium or tall? An extremely easy question! Well you

might just think that you are tall but your friend who is taller than you might say

that NO! You are not. The point being that some people might have such a

distribution in their mind that people having height around 4ft are short, around 5ft

are medium and around 6ft are tall. Others might have this distribution that

people having height around 4.5ft are short, around 5.5ft are medium and around

6.5ft are tall. Even having the same measurements different people can get to

completely different results as they approach the problem in different fashion.

Things can be even more complex when the same person, having observed

same measurements solves the same problem in two different ways and reaches

different solutions. But we all know that we answer such fuzzy questions very

efficiently in our daily lives. Our intelligence actually helps us do this. Hence the

ability to tackle ambiguous and fuzzy problems demonstrates intelligence.

Can you recognize a person just by looking at his/her fingerprint? Though we all

know that every human has a distinct pattern of his/her fingerprint but just by

looking at a fingerprint image a human generally can't just tell that this print must

be of person XYZ. On the other hand having distinct fingerprint is really important

information as it serves as a unique ID for all the humans in this world.

Let us just consider 5 different people and ask a sixth one to have a look at

different images of their fingerprints. We ask him to somehow learn the patterns,

which make the five prints distinct in some manner. After having seen the images

a several times, that sixth person might get to find something that is making the

prints distinct. Things like one of them has fever lines in the print, the other one

has sharply curved lines, some might have larger distance between the lines in

the print and some might have smaller displacement between the lines and many

such features. The point being that after some time, which may be in hours or

days or may be even months, that sixth person will be able to look at a new

fingerprint of one of those five persons and he might with some degree of

accuracy recognize that which one amongst the five does it belong. Only with 5

people the problem was hard to solve. His intelligence helped him to learn the

features that distinguish one finger print from the other. Hence the ability to

learn and recognize demonstrates intelligence.

Artificial Intelligence (CS607)

Let us give one last thought and then will get to why we have discussed all this. A

lot of us regularly watch television. Consider that you switch off the volume of

your TV set. If you are watching a VU lecture you will somehow perceive that the

person standing in front of you is not singing a song, or anchoring a musical show

or playing some sport. So just by observing the sequence of images of the

person you are able to perceive meaningful information out of the video. Your

intelligence helped you to perceive and understand what was happening on the

TV. Hence the ability to understand and perceive demonstrates intelligence.

1.2 Intelligent Machines

The discussion in the above section has a lot of consequences when we this it

with a different perspective. Let us show you something really interesting now

and hence informally define the field of Artificial Intelligence at the same time.

What if?

A machine searches through a mesh and finds a path?

A machine solves problems like the next number in the sequence?

A machine develops plans?

A machine diagnoses and prescribes?

A machine answers ambiguous questions?

A machine recognizes fingerprints?

A machine understands?

A machine perceives?

A machine does MANY MORE SUCH THINGS!

A machine behaves as HUMANS do? HUMANOID!!!

We will have to call such a machine Intelligent. Is this real or natural

intelligence? NO! This is Artificial Intelligence.

1.3 Formal Definitions for Artificial Intelligence

In their book "Artificial Intelligence: A Modern Approach" Stuart Russell and Peter

Norvig comment on artificial intelligence in a very comprehensive manner. They

present the definitions of artificial intelligence according to eight recent textbooks.

These definitions can be broadly categorized under two themes. The ones in the

left column of the table below are concerned with thought process and

reasoning, where as the ones in the right column address behavior.

Systems that think like

Systems that act like

humans

"The exciting new effort

"The art of creating

to make computers think

machines that perform

... machines with minds,

functions that require

in the full and literal

intelligence

when

sense"

(Haugeland,

performed by people"

1985)

(Kurzweil 1990)

"[The automation of]

"The study of how to

activities

that

make computers do

associate with human

things at which, at the

thinking, activities such

moment, people are

Artificial Intelligence (CS607)

as decision making,

better" (Rich and Knight,

problem

solving,

1991)

learning ..." (Bellman,

1978)

"The study of mental

"A field of study that

faculties through the use

seeks to explain and

computational

emulate

intelligent

models" (Charniak and

behavior in terms of

McDermott)

computational

processes" (Schalkoff,

1990)

"The

study

"The branch of computer

computation that make it

science

that

possible to perceive

concerned

with

the

reason

and

act"

automation of intelligent

(Winston 1992)

behavior" (Luger and

Stubblefield, 1993)

To make computers think like humans we first need to devise ways to determine

that how humans think. This is not that easy. For this we need to get inside the

actual functioning of the human brain. There are two ways to do this:

Introspection: that is trying to catch out own thoughts as they go by.

Psychological Experiments: that concern with the study of science of

mental life.

Once we accomplish in developing some sort of comprehensive theory that how

humans think, only then can we come up with computer programs that follow the

same rules. The interdisciplinary field of cognitive science brings together

computer models from AI and experimental techniques from psychology to try to

construct precise and testable theories of the working of human mind.

The issue of acting like humans comes up when AI programs have to interact

with people or when they have to do something physically which human usually

do in real life. For instance when a natural language processing system makes a

dialog with a person, or when some intelligent software gives out a medical

diagnosis, or when a robotic arm sorts out manufactured goods over a conveyer

belt and many other such scenarios.

Keeping in view all the above motivations let us give a fairly comprehensive

comment that Artificial Intelligence is an effort to create systems that can learn,

think, perceive, analyze and act in the same manner as real humans.

People have also looked into understanding the phenomena of Artificial

Intelligence from a different view point. They call this strong and weal AI.

Strong AI means that machines act intelligently and they have real conscious

minds. Weak AI says that machines can be made to act as if they are intelligent.

That is Weak AI treats the brain as a black box and just emulates its functionality.

While strong AI actually tries to recreate the functions of the inside of the brain as

opposed to simply emulating behavior.

Artificial Intelligence (CS607)

The concept can be explained by an example. Consider you have a very

intelligent machine that does a lot of tasks with a lot of intelligence. On the other

hand you have very trivial specie e.g. a cat. If you throw both of them into a pool

of water, the cat will try to save her life and would swim out of the pool. The

"intelligent" machine would die out in the water without any effort to save itself.

The mouse had strong Intelligence, the machine didn't. If the machine has strong

artificial intelligence, it would have used its knowledge to counter for this totally

new situation in its environment. But the machine only knew what we taught it or

in other wards only knew what was programmed into it. It never had the inherent

capability of intelligence which would have helped it to deal with this new

situation.

Most of the researchers are of the view that strong AI can't actually ever be

created and what ever we study and understand while dealing with the field of AI

is related to weak AI. A few are also of the view that we can get to the essence of

strong AI as well. However it is a standing debate but the purpose was to

introduce you with another aspect of thinking about the field.

1.4 History and Evolution of Artificial Intelligence

AI is a young field. It has inherited its ideas, concepts and techniques from many

disciplines like philosophy, mathematics, psychology, linguistics, biology etc.

From over a long period of traditions in philosophy theories of reasoning and

learning have emerged. From over 400 years of mathematics we have formal

theories of logic, probability, decision-making and computation. From psychology

we have the tools and techniques to investigate the human mind and ways to

represent the resulting theories. Linguistics provides us with the theories of

structure and meaning of language. From biology we have information about the

network structure of a human brain and all the theories on functionalities of

different human organs. Finally from computer science we have tools and

concepts to make AI a reality.

1.4.1 First recognized work on AI

The first work that is now generally recognized as AI was done by Warren

McCulloch and Walter Pitts (1943). Their work based on three sources:

The basic physiology and function of neurons in the human brain

The prepositional logic

The Turing's theory of computation

The proposed an artificial model of the human neuron. Their model proposed a

human neuron to be a bi-state element i.e. on or off and that the state of the

neuron depending on response to stimulation by a sufficient number of

neighboring neurons. They showed, for example, that some network of

connected neurons could compute any computable function, and that all the

logical connectives can be implemented by simple net structures. They also

suggested that suitably connected networks can also learn but they didn't pursue

this idea much at that time. Donald Hebb (1949) demonstrated a simple updating

rile for the modifying the connection strengths between neurons, such that

learning could take place.

Artificial Intelligence (CS607)

1.4.2 The name of the field as "Artificial Intelligence"

In 1956 some of the U.S researchers got together and organized a two-month

workshop at Dartmouth. There were altogether only 10 attendees. Allen Newell

and Herbert Simon actually dominated the workshop. Although all the

researchers had some excellent ideas and a few even had some demo programs

like checkers, but Newell and Herbert already had a reasoning program, the

Logic Theorist. The program came up with proofs for logic theorems. The

Dartmouth workshop didn't lead to any new breakthroughs, but it did all the major

people who were working in the field to each other. Over the next twenty years

these people, their students and colleagues at MIT, CMU, Stanford and IBM,

dominated the field of artificial intelligence. The most lasting and memorable thing

that came out of that workshop was an agreement to adopt the new name for the

field: Artificial Intelligence. So this was when the term was actually coined.

1.4.3 First program that though humanly

In the early years AI met drastic success. The researchers were highly motivated

to try out AI techniques to solve problems that were not yet been solved. Many of

them met great successes. Newell and Simon's early success was followed up

with the General Problem Solver. Unlike Logic Theorist, this program was

developed in the manner that it attacked a problem imitating the steps that

human take when solving a problem. Though it catered for a limited class of

problems but it was found out that it addressed those problems in a way very

similar to that as humans. It was probably the first program that imitated human

thinking approach.

1.4.4 Development of Lisp

In 1958 In MIT AI Lab, McCarthy defined the high-level language Lisp that

became the dominant AI programming language in the proceeding years. Though

McCarthy had the required tools with him to implement programs in this language

but access to scarce and expensive computing resources were also a serious

problem. Thus he and other researchers at MIT invented t8ime sharing. Also in

1958 he published a paper titled Programs with Common Sense, in which he

mentioned Advice Taker a hypothetical that can be seen as the first complete AI

system. Unlike the other systems at that time, it was to cater for the general

knowledge of the world. For example he showed that how some simple rules

could help a program generate a plan to drive to an airport and catch the plane.

1.4.5 Microworlds

Marvin Minsky (1963), a researcher at MIT supervised a number of students who

chose limited problems that appeared to require intelligence to solve. These

limited domains became known as Microworlds. Some of them developed

programs that solved calculus problems; some developed programs, which were

able to accept input statements in a very restricted subset of English language,

and generated answers to these statements. An example statement and an

answer can be:

Statement:

If Ali is 2 years younger than Umar and Umar is 23 years old. How old is Ali?

Answer:

Ali is 21 years old.

Artificial Intelligence (CS607)

In the same era a few researchers also met significant successes in building

neural networks but neural networks will be discusses in detail in the section titled

"Learning" in this book.

1.4.6 Researchers started to realize problems

In the beginning the AI researchers very confidently predicted their up coming

successes. Herbert Simon in 1957 said:

It is not my aim to surprise of shock you -- but the simplest way I can

summarize is to say that there are now in the world machines that think,

that learn and that create. Moreover, their ability to do these things is going

to increase rapidly until -- in a visible future the range of problems they

can handle will be coextensive with the range to which human mind has

been applied

In 1958 he predicted that computers would be chess champions, and an

important new mathematical theorem would be proved by machine. But over the

years it was revealed that such statements and claims were really optimistic. A

major problem that AI researchers started to realize was that though their

techniques worked fairly well on one or two simple examples but most of them

turned out to fail when tried out on wider selection of problems and on more

difficult tasks.

One of the problems was that early programs often didn't have much knowledge

of their subject matter, and succeeded by means of simple syntactic

manipulations e.g. Weizenbaum's ELIZA program (1965), which could apparently

engage in serious conversation on any topic, actually just borrowed and

manipulated the sentences typed into it by a human. Many of the language

translation programs tried to translate sentences by just a replacement of words

without having catered for the context in which they were used, hence totally

failing to maintain the subject matter in the actual sentence, which was to be

translated. The famous retranslation of "the spirit is willing but the flesh is

weak" as "the vodka is good but the meat is rotten" illustrates the difficulties

encountered.

Second kind of difficulty was that many problems that AI was trying to solve were

intractable. Most of the AI programs in the early years tried to attack a problem by

finding different combinations in which a problem can be solved and then

combined different combinations and steps until the right solution was found.

This didn't work always. There were many intractable problems in which this

approach failed.

A third problem arose because of the fundamental limitations on the basic

structures being used to generate intelligent behavior. For example in 1969,

Minsky and Papert's book Perceptrons proved that although perceptrons could

be shown to learn anything they were capable of representing, they could

represent very little.

Artificial Intelligence (CS607)

However, in brief different happenings made the researchers realize that as they

tried harder and more complex problem the pace of their success decreased so

they now refrained from making highly optimistic statements.

1.4.7 AI becomes part of Commercial Market

Even after realizing the basic hurdles and problems in the way of achieving

success in this field, the researchers went on exploring grounds and techniques.

The first successful commercial expert system, R1, began operation at Digital

Equipment Corporation (McDermott, 1982). The program basically helped to

configure the orders for new computer systems. Detailed study of what expert

systems are will be dealt later in this book. For now consider expert systems as a

programs that somehow solves a certain problem by using previously stored

information about some rules and fact of the domain to which that problem

belongs.

In 1981, the Japanese announced the "Fifth Generation" project, a 10-year plan

to build intelligent computers running Prolog in much the same way that ordinary

computers run the machine code. The project proposed to achieve full-scale

natural language understanding along with many other ambitious goals.

However, by this time people began to invest in this field and many AI projects

got commercially funded and accepted.

1.4.8 Neural networks reinvented

Although computer science had rejected this concept of neural networks after

Minsky and Papert's Perceptrons book, but in 1980s at least four different

groups reinvented the back propagation learning algorithm which was first found

in 1969 by Bryson and Ho. The algorithm was applied to many learning problem

in computer science and the wide spread dissemination of the results in the

collection Parallel Distributed Processing (Rumelhart and McClelland, 1986)

caused great excitement.

People tried out the back propagation neural networks as a solution to many

learning problems and met great success.

Artificial Intelligence (CS607)

The diagram above summarizes the history and evolution of AI in a

comprehensive shape.

1.5 Applications

Artificial finds its application is a lot of areas not only related to computer

sciences but many other fields as well. We will briefly mention a few of the

application areas and throughout the content of this booklet you will find various

applications of the field in detail later.

Many information retrieval systems like Google search engine uses artificially

intelligent crawlers and content based searching techniques to efficiency and

accuracy of the information retrieval.

A lot of computer based games like chess, 3D combat games even many arcade

games use intelligent software to make the user feel as if the machine on which

that game is running is intelligent.

Computer Vision is a new area where people are trying to develop the sense of

visionary perception into a machine. Computer vision applications help to

establish tasks which previously required human vision capabilities e.g.

recognizing human faces, understanding images and to interpret them, analyzing

medical scan and innumerable amount of other tasks.

Natural language processing is another area which tries to make machines speak

and interact with humans just like humans themselves. This requires a lot from

the field of Artificial Intelligence.

Artificial Intelligence (CS607)

Expert systems form probably the largest industrial applications of AI. Software

like MYCIN and XCON/R1 has been successfully employed in medical and

manufacturing industries respectively.

Robotics again forms a branch linked with the applications of AI where people are

trying to develop robots which can be rather called as humanoids. Organizations

have developed robots that act as pets, visitor guides etc.

In short there are vast applications of the field and a lot of research work is going

on around the globe in the sub-branches of the field. Like mentioned previously,

during the course of the booklet you will find details of many application of AI.

1.6 Summary

Intelligence can be understood as a trait of some living species

Many factors and behaviors contribute to intelligence

Intelligent machines can be created

To create intelligent machines we first need to understand how the real

brain functions

Artificial intelligence deals with making machines think and act like

humans

It is difficult to give one precise definition of AI

History of AI is marked by many interesting happenings through which the

field gradually evolved

In the early years people made optimistic claims about AI but soon they

realized that it's not all that smooth

AI is employed in various different fields like gamming, business, law,

medicine, engineering, robotics, computer vision and many other fields

This book will guide you though basic concepts and some core algorithms

that form the fundamentals of Artificial Intelligence

AI has enormous room for research and posses a diverse future

Table of Contents: