1 of 42

Sri Raghavendra Educational Institutions Society (R)

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

www.skit.org.in

Title: Artificial Intelligence and Machine Learning

CO addressed: CO1

Course: B.E

Presented by: Prof. Imran Ulla Khan

Department: Computer Science and Engineering

2 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Module-1

Data: Raw facts, unformatted information.
Information: It is the result of processing, manipulating and organizing data in response to a specific need. Information relates to the understanding of the problem domain.
Knowledge: It relates to the understanding of the solution domain – what to do?
Intelligence: It is the knowledge in operation towards the solution – how to do? How to apply the solution?

3 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

What Is Artificial Intelligence?

It is a branch of Computer Science that pursues creating the computers or machines as intelligent as human beings.

Artificial Intelligence is the study of how to make computers do things which, at the moment, people do better. It refers to the intelligence controlled by a computer machine.

According to the father of Artificial Intelligence, John McCarthy, it is :

“The science and engineering of making intelligent machines, especially intelligent computer programs”.

4 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

AI Problems?

There are some of the problems contained within AI.

1. Game Playing and theorem proving share the property that people who do them well are considered to be displaying intelligence.

2. Another important foray into AI is focused on Commonsense Reasoning. It includes reasoning about physical objects and their relationships to each other, as well as reasoning about actions and other consequences.

3. To investigate this sort of reasoning Nowell Shaw and Simon built the General Problem Solver (GPS) which they applied to several common sense tasks. But no attempt was made to create a program with a large amount of knowledge about a particular problem domain. Only quite simple tasks were selected.

5 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Some of the task domains of AI

6 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Branches of AI

Computer vision - enables computers to interpret and analyze the visual world, simulating the way humans see and understand their environment
Fuzzy Logic - used to imitate human reasoning and cognition
Expert systems - designed to mimic the decision-making abilities of a human expert in a specific domain
Robotics - deals with the study of creating intelligent and efficient robots
Machine learning - enable computer systems to improve their performance on a specific task through learning from data
Neural networks/deep learning - designed to automatically learn and represent data
Natural language processing - computers the ability to understand text and spoken words in much the same way human beings can.

7 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Branches of AI

Logical AI
Search
Pattern Recognition
Representation
Inference – making decision based on the available data
Common sense knowledge and Reasoning
Learning from experience
Planning
Epistemology - reliability and precision of the machine
Ontology - collection of ideas within an area and their connections
Heuristics - a method of problem-solving where the goal is to come up with a workable solution in a feasible amount of time

8 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

What AI technique?

Artificial Intelligence problems span a very broad spectrum
There are techniques that are appropriate for the solution of a variety of these problems.

Intelligence requires Knowledge - Knowledge possesses some less desirable properties including:

It is voluminous
It is hard to characterize accurately
It is constantly changing

9 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

What AI technique?

The knowledge captures generalizations
It can be understood by people who must provide it.
It can be easily be modified to correct errors and to reflect changes in the world and in our world view.
It can be used in a great many situations even if it is not totally accurate or complete.
It can be used to help overcome its own sheer bulk by helping to narrow the range of possibilities that must usually be considered

10 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Turing Test

In 1950, Alan Turing proposed the method for determining whether a machine can think

11 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Tic tac toe - first approach

12 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Tic tac toe - Second approach

The structure of the data is same as before but we use 2 for a blank, 3 for an X and 5 for an O.

A variable called TURN indicates 1 for the first move and 9 for the last.

The algorithm consists of three actions:

1. MAKE2 which returns 5 if the center square is blank; otherwise it returns any blank non corner square, i.e. 2, 4, 6 or 8.

2. POSSWIN (p) returns 0 if player p cannot win on the next move and otherwise returns the number of the square that gives a winning move.

This function will enable the program both to win and to block the opponents win

13 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Continue….

It checks each line using products 3*3*2 = 18 gives a win for X, 5*5*2=50 gives a win for O, and the winning move is the holder of the blank.

3. GO (n) makes a move to square n setting BOARD[n] to 3 or 5.

14 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Tic tac toe - Third approach (Minimax Procedure)

The structure of the data consists of BOARD which contains a nine element vector, a list of board positions that could result from the next move and a number representing an estimation of how the board position leads to an ultimate win for the player to move.

This algorithm looks ahead to make a decision on the next move by deciding which the most promising move or the most suitable move at any stage would be and selects the same.

Consider all possible moves and replies that the program can make. Continue this process for as long as time permits until a winner emerges, and then choose the move that leads to the computer program winning, if possible in the shortest time.

15 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Problems, Problem Spaces, and Search ?

Problem - which can be caused for different reasons, and, if solvable, can usually be solved in a number of different ways, is defined in a number of different ways.

To build a system or to solve a particular problem we need to do four things.

1. Define the problem precisely. This definition must include precise specification of what the initial situation will be as well as what final situations constitute acceptable solutions to the problem

2. Analyze the problem

3. Isolate and represent the task knowledge that is necessary to solve the problem

4. Choose the best solving technique and apply it to the particular problem.

16 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Problem Spaces / State space?

State space - is a set of legal positions, starting at the initial state, using the set of rules to move from one state to another and attempting to end up in a goal state

Methodology of State Space Approach

1. To represent a problem in structured form using different states

2. Identify the initial state

3. Identify the goal state

4. Determine the operator for the changing state

5. Represent the knowledge present in the problem in a convenient form

6. Start from the initial state and search a path to goal state

17 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Water Jug problem

Problem is “You are given two jugs, a 4-litre one and a 3-litre one. One neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 litres of water into 4-litre jug?”

Solution:

The state space for the problem can be described as a set of states, where each state represents the number of gallons in each state.

State: (x, y)

– x = number of lts in 4 lts jug

– y = number of lts in 3 lts jug

x = 0, 1, 2, 3, or 4 y = 0, 1, 2, 3

18 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Water Jug…..

Start state: (0, 0) i.e., 4-litre and 3-litre jugs is empty initially.
Goal state: (2, n) for any n that is 4-litre jug has 2 litres of water and 3-litre jug has any value from 0-3 since it is not specified.
Attempting to end up in a goal state.

19 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Production System

The entire procedure for getting a solution for AI problem can be viewed as Production System

It is a basic building block which describes the AI problem and also describes the method of searching the goal.

Its main components are:

Set of Rules, each consisting of a left side (a pattern) that determines the applicability of the rule and right side that describes the operation to be performed if the rule is applied.

Knowledge/Database – It contains whatever information is appropriate for a particular task.

Control Strategy – It specifies the order in which the rules will be compared to the database and the way of resolving the conflicts that arise when several rules match at one.

o The first requirement of a goal control strategy is that it is cause motion; a control strategy that does not cause motion will never lead to a solution.

o The second requirement of a good control strategy is that it should be systematic.

20 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Production System

iv. A rule applier: Production rule is like below

if(condition) then

consequence or action.

21 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Algorithm for Production System

1. Represent the initial state of the problem

2. If the present state is the goal state then go to step 5 else go to step 3

3. Choose one of the rules that satisfy the present state, apply it and change the state to new state.

4. Go to Step 2

5. Print “Goal is reached ” and indicate the search path from initial state to goal state

6. Stop.

22 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Classification of Production System

Based on the direction they can be

1. Forward Production System

Moving from Initial State to Goal State
When there are number of goal states and only one initial state, it is advantage to use forward production system.

2. Backward Production System

Moving from Goal State to Initial State
If there is only one goal state and many initial states, it is advantage to use backward production system.

23 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Categories / Classes of Production System

A monotonic production system is a production system in which the applications of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.
A non-monotonic production system is one which this is not true.

A partially commutative production system is a production system with the property that if the application of a particular sequence of rules transforms state X into state Y, then any permutation of those rules that is allowable also transforms state X into state Y.
A commutative production system is a production system that is both monotonic and partially commutative.

24 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Problem Characteristics

- In order to choose the most appropriate method (or a combination of methods) for a particular problem, it is necessary to analyze the problem along several key dimensions:

Is the problem decomposable?
Can solution steps be ignored or undone?
Is the universe predictable?
Is a good solution absolute or relative?
Is the solution a state or a path?
What is the role of knowledge?
Does the task require human-interaction?
Problem Classification

25 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Algorithm BFS: Breadth First Search

1. Create a variable called NODE_LIST and set it to the initial state.

2. Until a goal state is found or NODE_LIST is empty:

a. Remove the first element from NODE_LIST and call it E. If NODE_LIST was empty, quit.

b. For each way that each rule can match the state described in E do:

i. Apply the rule to generate a new state.

ii. If the new state is a goal state, quit and return this state.

iii. Otherwise, add the new state to the end of NODE_LIST

26 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Advantages of BFS:

Used to find the shortest path between states.
Always finds optimal solutions.
There is nothing like useless path in BFS, since it searches level by level.
Finds the closest goal state in less time.

Disadvantages of BFS:

1. All of the connected vertices must be stored in memory. So consumes more memory

27 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Algorithm DFS: Depth First Search

1. If the initial state is a goal state, quit and return success.

2. Otherwise, do the following until success or failure is signaled.

a. Generate successor, E of the initial state. If there are no more successors, signal failure.

b. Call Depth-First Search with E as the initial state.

c. If success is returned, signal success. Otherwise continue in this loop.

28 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Advantages of DFS:

1. Consumes less memory

2. Finds the larger distant element(from initial state) in less time.

Disadvantages of DFS:

May not find optimal solution to the problem

2. May get trapped in searching useless path.

29 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Heuristic Search Techniques

Many traditional search algorithms are used in AI applications. For complex problems, the traditional algorithms are unable to find the solutions within some practical time and space limits.

Consequently, many special techniques are developed, using heuristic functions.

The algorithms that use heuristic functions are called heuristic algorithms

• Uninformed search algorithms or Brute-force algorithms, search through the search space all possible candidates for the solution checking whether each candidate satisfies the problem’s statement.

• Informed search algorithms use heuristic functions that are specific to the problem, apply them to guide the search through the search space to try to reduce the amount of time spent in searching.

30 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Informed search algorithms

- Some prominent intelligent search algorithms are stated below

Generate and Test Search
Best-first Search
A* Search
AO* Search
Hill climbing

31 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

A* Algorithm

Step1: Place the starting node in the OPEN list.

Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and stops.

Step 3: Select the node from the OPEN list which has the smallest value of evaluation function (g+h), if node n is goal node then return success and stop, otherwise

Step 4: Expand node n and generate all of its successors, and put n into the closed list. For each successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute evaluation function for n' and place into Open list.

Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back pointer which reflects the lowest g(n') value.

Step 6: Return to Step 2.

32 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Generate and Test Search

Generate-and-test search algorithm is a very simple algorithm that guarantees to find a solution if done systematically and there exists a solution.

Algorithm:

1.Generate a possible solution.

2.Test to see if this is the expected solution.

3.If the solution has been found quit else go to step 1.

33 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Hill Climbing

Hill Climbing is heuristic search used for mathematical optimization problems in the field of Artificial Intelligence.

Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good solution to the problem.

34 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Types of Hill Climbing

Types of Hill Climbing

Simple Hill climbing - It examines the neighboring nodes one by one and selects the first neighboring node which optimizes the current cost as next node.

2. Steepest-Ascent Hill climbing - It first examines all the neighboring nodes and then selects the node closest to the solution state as next node.

3. Stochastic hill climbing : It does not examine all the neighboring nodes before deciding which node to select. It just selects a neighboring node at random, and decides (based on the amount of improvement in that neighbor) whether to move to that neighbor or to examine another.

35 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Simple Hill climbing Algorithm

Step 1 : Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make initial state as current state.

Step 2 : Loop until the solution state is found or there are no new operators present which can be applied to current state.

a) Select a state that has not been yet applied to the current state and apply it to produce a new state.

b) Perform these to evaluate new state

i. If the current state is a goal state, then stop and return success.

ii. If it is better than the current state, then make it current state and proceed further.

iii. If it is not better than the current state, then continue in the loop until a solution is found.

Step 3 : Exit.

36 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Steepest-Ascent Hill climbing Algorithm

Evaluate the initial state. If it is also a goal state then return it and quit. Otherwise continue with the initial state as the current state.

2. Loop until a solution is found or until a complete iteration produces no

change to current state:

a. Let SUCC be a state such that any possible successor of the current state will be better than SUCC.

b. For each operator that applies to the current state do:

i. Apply the operator and generate a new state.

ii. Evaluate the new state. If it is a goal state, then return it and quit. If not compare it to SUCC. If it is better, then set SUCC to this state. If it is not better, leave SUCC alone.

c. IF the SUCC is better than current state, then set current state to SUCC

37 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

State Space diagram for Hill Climbing

38 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Problems / Drawbacks of Hill climbing

- Hill climbing may fail to find a solution, Either algorithm may terminate by not finding a goal state, when the program has reached a local maximum, a plateau or a ridge

A local maximum is a state that is better than all its neighbors but it not better than some other states farther away.

A plateau is a flat area of the search space in which a whole set has the same value. In this, it is not possible to determine the best move by making local comparisons.

A ridge is a special kind of maximum. It is an area of the search space that is higher than surrounding areas and that itself has a slope

39 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

How to overcome above drawbacks

1. To overcome local maximum problem : Utilize backtracking technique. Maintain a list of visited states. If the search reaches an undesirable state, it can backtrack to the previous configuration and explore a new path.

2. To overcome plateaus : Make a big jump. Randomly select a state far away from current state. Chances are that we will land at a non-plateau region

3. To overcome Ridge : In this kind of obstacle, use two or more rules before testing. It implies moving in several directions at once

40 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Best First Search (Informed Search)

So both BFS and DFS blindly explore paths without considering any cost function.
The idea of Best First Search is to use an evaluation function to decide which adjacent is most promising and then explore.
Best First Search falls under the category of Heuristic Search or Informed Search.

41 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Best First Search (Informed Search) Algorithm

1. Start with OPEN containing just the initial state

2. Until a goal is found or there are no nodes left on OPEN do:

a. Pick the best node on OPEN

b. Generate its successors

c. For each successor do:

i. If it is not been generated before, evaluate it, add it to OPEN and record its parent.

ii. If it has been generated before, change the parent if this new path is better than the previous one. In that case update the cost of getting to this node and to any successors that this node may already have.

42 of 42

10/12/2023

/skit.org.in

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

Best First Search Example

1. Start with OPEN containing just the initial state

2. Until a goal is found or there are no nodes left on OPEN do:

a. Pick the best node on OPEN

b. Generate its successors

c. For each successor do:

i. If it is not been generated before, evaluate it, add it to OPEN and record its parent.