5-2. Hill Climbing

Particle 1 starts at seven and with a step size of two, it reaches the peak of 10, with one step. Particle 2 starts at eight, it goes towards the peak, but then it oscillates around the peak because the step size is too large. Particle 3 starts at 10, follows this upward gradient, but … Read more

Now assume your algorithm has a step size of 2. It still stops when no positive gradient is found. What value would these particles return? Particle 1 starts at x equal to 7. Particle 2 starts at x equal to 8, and particle 3 starts at x equal to 10. Select their appropriate answer for … Read more

Well then why not just keep the step size large? >> A couple of reasons. First, with a really large step size, we can miss sharp hills completely. Going back to our first starting place. If my step size is this big, I would skip the hill I intended to take. And would start going … Read more

Does hill climbing have any other problems we should worry about? >> Suppose we start at the left edge of the graph, using small steps we gradually climb higher until we get to the shoulder here. However, if we stop when we no longer see a way to improve we can get stuck at this … Read more

Particle 1 starts at x=1 and follows a positive gradient up, but then it gets stuck at the shoulder where y=2. Particle 2 starts at x=8 and follows a positive gradient up, but it gets stuck at this local maximum at y=6. Particle 3 starts at x=9 and follows the positive gradient in the right … Read more

We are going to consider multiple starting points for the hill climbing algorithm in this quiz. By convention, we’ll call these particles. For each of these particles, tell us their value assuming your algorithm has a step size of one and that it stops when no positive gradient is found.

This time I start here and I go to to the left because that is the positive gradient. And I’m going to get to the top of the global maximum. >> But what’s the chance that you’re going to get to global maximum on your second attempt? >> Better than just with my first attempt, … Read more

Suppose I start here. I look to the left and it goes down. I look to the right and it’s going up. So I’ll take a step in that direction. >> And what do you do when you reach the top? >> Well we will get stuck, just like we did with the end queens … Read more

While we´re on this topic, I’d like to talk about local beam search. Because we’ll use it later in the course. >> Okay, it’s your show after all. >> The local beam search, instead of just using one position, which I’ll call particle, just because that’s how I think of it. We’ll keep track of … Read more

The n Queen problem was multidimensional and we were trying to minimize the number of attacks. Here for convenience we’ll make our goal to maximize this value, and we can only move left or right along this x axis, instead of having so many different pieces to move.