Heuristic Search in Artificial Intelligence

Views:

Category: Entertainment

Presentation Description

What is a Heuristic Search? A Heuristic is a technique to solve a problem faster than classic methods, or to find an approximate solution when classic methods cannot. This is a kind of a shortcut as we often trade one of optimality, completeness, accuracy, or precision for speed. A Heuristic (or a heuristic function) takes a look at search algorithms. At each branching step, it evaluates the available information and makes a decision on which branch to follow. It does so by ranking alternatives. The Heuristic is any device that is often effective but will not guarantee work in every case.

Presentation Transcript

slide 1:

What is Heuristic Search - Techniques Hill Climibing in AI

slide 2:

Heuristic Search in Artificial Intelligence – Python First l e t’ s revise the Artificial Intelligence Tutorial What is a Heuristic Search A Heuristic is a technique to solve a problem faster than classic methods or to find an approximate solution when classic methods cannot. This is a kind of a shortcut as we often trade one of optimality completeness accuracy or precision for speed. A Heuristic or a heuristic function takes a look at search algorithms. At each branching step it evaluates the available information and makes a decision on which branch to follow. It does so by ranking alternatives. The Heuristic is any device that is often effective but will not guarantee work in every case. You must take a look at NLP Tutorial So why do we need heuristics One reason is to produce in a reasonable amount of time a solution that is good enough for the problem in question. It d o es n ’ t have to be the best- an approximate solution will do since this is fast enough. Most problems are exponential. Heuristic Search let us reduce this to a rather polynomial number. We use this in AI because we can put it to use in situations where we ca n ’ t find known algorithms. We can say Heuristic Techniques are weak methods because they are vulnerable to combinatorial explosion.

slide 3:

Heuristic Search Techniques in Artificial Intelligence Briefly we can taxonomize such techniques of Heuristic into two categories: Heuristic Search Techniques in Artificial Intelligence a. Direct Heuristic Search Techniques in AI Other names for these are Blind Search Uninformed Search and Blind Control Strategy. These a r en ’ t always possible since they demand much time or memory. They search the entire state space for a solution and use an arbitrary ordering of operations. Examples of these are Breadth First Search BFS and Depth First Search DFS. Do you know about NLTK Python b. Weak Heuristic Search Techniques in AI Other names for these are Informed Search Heuristic Search and Heuristic Control Strategy. These are effective if applied correctly to the right types of tasks and usually demand domain-specific information. We need this extra information to compute preference among child nodes to explore and expand. Each node has a heuristic

slide 4:

function associated with it. Examples are Best First Search BFS and A. Before we move on to describe certain techniques l et ’ s first take a look at the ones we generally observe. Below we name a few.  Best-First Search  A Search  Bidirectional Search  Tabu Search  Beam Search  Simulated Annealing  Hill Climbing  Constraint Satisfaction Problems Hill Climbing in Artifical Intelligence First l et ’ s talk about Hill Climbing in Artifical Intelligence. This is a heuristic for optimizing problems mathematically. We need to choose values from the input to maximize or minimize a real function. It is okay if the solution i s n ’ t the global optimal maximum. Heuristic Search Techniques – Hill Climbing L e t’ s discuss Python Speech Recognition One such example of Hill Climbing will be the widely discussed Travelling Salesman Problem- one where we must minimize the distance he travels.

slide 5:

a. Features of Hill Climbing in AI Let ’ s discuss some of the features of this algorithm Hill Climbing:  It is a variant of the generate-and-test algorithm  It makes use of the greedy approach This means it keeps generating possible solutions until it finds the expected solution and moves only in the direction which optimizes the cost function for it. b. Types of Hill Climbing in AI Heuristic Search – Types of Hill Climbing in Artifical Intelligence  Simple Hill Climbing- This examines one neighboring node at a time and selects the first one that optimizes the current cost to be the next node.  Steepest Ascent Hill Climbing- This examines all neighboring nodes and selects the one closest to the solution state.  Stochastic Hill Climbing- This selects a neighboring node at random and decides whether to move to it or examine another. L et’ s revise Python Unit testing Let ’ s take a look at the algorithm for simple hill climbing. 1. Evaluate initial state- if goal state stop and return success. Else make initial state current.

slide 6:

2. Loop until the solution reached or until no new operators left to apply to current state: a. Select new operator to apply to the current producing new state. b. Evaluate new state:  If a goal state stop and return success.  If better than the current state make it current state proceed.  Even if not better than the current state continue until the solution reached. 3. Exit. c. Problems with Hill Climbing in AI We usually run into one of three issues-  Local Maximum- All neighboring states have values worse than the current. The greedy approach means we w o n ’ t be moving to a worse state. This terminates the process even though there may have been a better solution. As a workaround we use backtracking.  Plateau- All neighbors to it have the same value. This makes it impossible to choose a direction. To avoid this we randomly make a big jump.  Ridge- At a ridge movement in all possible directions is downward. This makes it look like a peak and terminates the process. To avoid this we may use two or more rules before testing. Do you know about Python Assert Statements Constraint Satisfaction Problems CSP A constraint is nothing but a limitation or a restriction. Working with AI we may need to satisfy some constraints to solve problems. Let ’ s try solving a problem this way shall we Let ’ s talk of a magic square. This is a sequence of numbers- usually integers- arranged in a square grid. The numbers in each row each column and each diagonal all add up to a constant which we call the Magic Constant. Let ’ s implement this with Python. 1. def magic_squarematrix: 2. sizelenmatrix0 3. sum_list 4. for col in rangesize: Vertical sum 5. sum_list.appendsumrowcol for row in matrix 6. sum_list.extendsumlines for lines in matrixHorizontal sum

slide 7:

7. result10 8. for i in range0size: 9. result1+matrixii 10. sum_list.appendresult1 11. result20 12. for i in rangesize-1-1-1: 13. result2+matrixii 14. sum_list.appendresult2 15. if lensetsum_list1: 16. return False 17. return True Now l et ’ s run this code. 1. magic_square123456789 False This is not a magic square. The numbers in the rows/columns/diagonals do not add up to the same value. Let ’ s try another list of lists. Have a look at AI Neural Networks 1. magic_square276951438 True

slide 8:

Heuristic Search – Magic Since the values add up to the constant 15 in all directions surely this is a magic square Simulated Annealing Heuristic Search In metallurgy when we slow-cool metals to pull them down to a state of low energy gives them exemplary amounts of strength. We call this annealing. While high temperatures observe much random movement low temperatures notice little randomness. In AI we take a cue from this to produce something called simulated annealing. This is a way of optimization where we begin with a random search at a high temperature and reduce the temperature slowly. Eventually as the temperature approaches zero the search becomes pure greedy descent. At each step this processes randomly selects a variable and a value. It accepts the assignment only when it is an improvement or

slide 9:

d o esn ’ t lead to more conflict. If not it checks if the temperature is much worse than the current assignment to accept the assignment with some probability. Do you know about Python ternary Operators An annealing schedule defines how the temperature drops as the search progress. A very common schedule is geometric cooling. If we begin with a temperature of 10 and multiply by 0.97 after every step then after 100 steps w e’ r e left with a temperature of 0.48. Best-First Search BFS Heuristic Search Often dubbed BFS Best First Search is an informed search that uses an evaluation function to decide which adjacent is the most promising before it can continue to explore. Breadth- and Depth- First Searches blindly explore paths without keeping a cost function in mind. Things a r e n ’ t the same with BFS though. Here we use a priority queue to store node costs. Let ’ s understand BFS Heuristic Search through pseudocode. 1. Define list OPEN with single node s – the start node. 2. IF list is empty return failure. 3. Remove node n node with best score from list move it to list CLOSED. 4. Expand node n. 5. IF any successor to n is the goal node return success and trace path from goal node to s to return the solution. 6. FOR each successor node:  Apply evaluation function f.  IF the node i sn ’ t in either list add it to list OPEN. 7. Loop to step 2. L e t’ s learn about Python Slice So this was all in Heuristic Search Techniques in AI. Hope you like our explanation. Conclusion – Heuristic Search Techniques

slide 10:

Hence in this Python AI tutorial we discussed the Heuristic Search in AI. While we named a few techniques that fall under that we also discussed in brief those like BFS Hill Climbing Simulated Annealing and CSP. We also implemented CSP in Python. Still if you have any query in Heuristic Search Techniques feel free to ask in the comment tab.