CS607 Highlighted Handouts Set 2

Table of Contents:

1. 1
2. 2
3. 3
4. 4 History and Evolution of Artificial Intelligence ......................................................................... 9
5. 5 Applications...............................................................................................................................13
6. 6 Summary ...................................................................................................................................14

Problem Solving .................................................................................................................................15

2. 1 Classical Approach ....................................................................................................................15
3. 2 Generate and Test ......................................................................................................................15
4. 3 Problem Representation. ............................................................................................................16
5. 4 Components of Problem Solving ...............................................................................................17
6. 5 The Two-One Problem ..............................................................................................................18
7. 6 Searching ...................................................................................................................................21
8. 7 Tree and Graphs Terminology ...................................................................................................21
9. 8 Search Strategies .......................................................................................................................23
10. 9 Simple Search Algorithm ..........................................................................................................24
11. 10 Simple Search Algorithm Applied to Depth First Search ..........................................................25
12. 11 Simple Search Algorithm Applied to Breadth First Search .......................................................28
13. 12 Problems with DFS and BFS .....................................................................................................32
14. 13 Progressive Deepening ..............................................................................................................32
15. 14 Heuristically Informed Searches ................................................................................................37
16. 15 Hill Climbing .............................................................................................................................39
17. 16 Beam Search ..............................................................................................................................43
18. 17 Best First Search ........................................................................................................................45
19. 18 Optimal Searches .......................................................................................................................47
20. 19 Branch and Bound .....................................................................................................................48
21. 20 Improvements in Branch and Bound .........................................................................................55
22. 21 A* Procedure .............................................................................................................................56
23. 22 Adversarial Search .....................................................................................................................62
24. 23 Minimax Procedure ...................................................................................................................63
25. 24 Alpha Beta Pruning ...................................................................................................................64
26. 25 Summary ...................................................................................................................................71
27. 26 Problems ....................................................................................................................................72

Genetic Algorithms .............................................................................................................................76

3. 1 Discussion on Problem Solving .................................................................................................76
4. 2 Hill Climbing in Parallel ............................................................................................................76
5. 3 Comment on Evolution. .............................................................................................................77
6. 4 Genetic Algorithm .....................................................................................................................77
7. 5 Basic Genetic Algorithm ...........................................................................................................77
8. 6 Solution to a Few Problems using GA .......................................................................................77
9. 7 Eight Queens Problem ...............................................................................................................82
10. 8 Problems ....................................................................................................................................88

Knowledge Representation and Reasoning .........................................................................................89

4. 1 The AI Cycle .............................................................................................................................89
5. 2 The dilemma ..............................................................................................................................90
6. 3 Knowledge and its types ............................................................................................................90
7. 4 Towards Representation ............................................................................................................91
8. 5 Formal KR techniques ...............................................................................................................93
9. 6 Facts ..........................................................................................................................................94
10. 7 Rules ..........................................................................................................................................95
11. 8 Semantic networks.....................................................................................................................97
12. 9 Frames .......................................................................................................................................98
13. 10 Logic .........................................................................................................................................98
14. 11 Reasoning ................................................................................................................................102
15. 12 Types of reasoning ..................................................................................................................102

Expert Systems .................................................................................................................................111

5. 1 What is an Expert? ...................................................................................................................111
6. 2 What is an expert system? .......................................................................................................111
7. 3 History and Evolution ..............................................................................................................111
8. 4 Comparison of a human expert and an expert yystem .............................................................112
9. 5 Roles of an expert system ........................................................................................................113
10. 6 How are expert systems used? .................................................................................................114
11. 7 Expert system structure ...........................................................................................................115
12. 8 Characteristics of expert systems .............................................................................................121
13. 9 Programming vs. knowledge engineering ................................................................................122
14. 10 People involved in an expert system project ............................................................................122
15. 11 Inference mechanisms .............................................................................................................123
16. 12 Design of expert systems .........................................................................................................129

Handling uncertainty with fuzzy systems ..........................................................................................145

6. 1
7. 2 Classical sets............................................................................................................................145
8. 3 Fuzzy sets ................................................................................................................................146
9. 4 Fuzzy Logic .............................................................................................................................147
10. 5 Fuzzy inference system ...........................................................................................................153
11. 6 Summary .................................................................................................................................158
12. 7 Exercise ...................................................................................................................................158

Introduction to learning .....................................................................................................................159

7. 1 Motivation ...............................................................................................................................159
8. 2 What is learning ? ....................................................................................................................159
9. 3 What is machine learning ? ......................................................................................................160
10. 4 Why do we want machine learning ..........................................................................................160
11. 5 What are the three phases in machine learning? ......................................................................160
12. 6 Learning techniques available..................................................................................................162
13. 7 How is it different from the AI we've studied so far? ..............................................................163
14. 8 Applied learning ......................................................................................................................163
15. 9 LEARNING: Symbol-based ....................................................................................................165
16. 10 Problem and problem spaces ...................................................................................................165
17. 11 Concept learning as search ......................................................................................................171
18. 12 Decision trees learning ............................................................................................................176
19. 13 LEARNING: Connectionist.....................................................................................................181
20. 14 Biological aspects and structure of a neuron ...........................................................................181
21. 15 Single perceptron .....................................................................................................................182
22. 16 Linearly separable problems ....................................................................................................184
23. 17 Multiple layers of perceptrons .................................................................................................186
24. 18 Artificial Neural Networks: supervised and unsupervised .......................................................187
25. 19 Basic terminologies .................................................................................................................187
26. 20 Design phases of ANNs ...........................................................................................................188
27. 21 Supervised ...............................................................................................................................190
28. 22 Unsupervised ...........................................................................................................................190
29. 23 Exercise ...................................................................................................................................192

Planning ............................................................................................................................................195

8. 1 Motivation ...............................................................................................................................195
9. 2 Definition of Planning .............................................................................................................196
10. 3 Planning vs. problem solving...................................................................................................197
11. 4 Planning language....................................................................................................................197
12. 5 The partial-order planning algorithm – POP ............................................................................198
13. 6 POP Example ..........................................................................................................................199
14. 7 Problems ..................................................................................................................................202

Advanced Topics ..............................................................................................................................203

9. 1 Computer vision ......................................................................................................................203
10. 2 Robotics ...................................................................................................................................204
11. 3 Clustering ................................................................................................................................205

Conclusion ...................................................................................................................................206 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?

Q1. 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,