- Gradient Free Algorithms.
- Gradient Based Algorithms.
Gradient Free Algorithms don’t require to compute gradients, they are much more dependent on randomness, mutation, and fitness or scoring functions in nature, hence they are slower than gradient-based algorithms. The Decision Variables in these algorithms can be discrete, discontinuous, or noisy. Here is the list of gradient-free algorithms:
- Exhaustive Search
- Genetic Algorithm
- Particle Swarm
- Simulated Annealing
(we’ll not discuss Gradient free algorithms as it is somewhat out of context for this blog post, would recommend going ahead and explore as they’re quite interesting, most of reinforcement learning methods are based on these algorithms.)
If we try to solve our balancing rod problem using ‘Exhaustive search(or Exhaustive exploration)’ which is nothing but trying all possible solutions and pick the best one at the end of the experiment.
Solving Rod Balancing problem using Exhaustive Search
Here in the above video, we try almost all possible points (x) on the rod and plot the time on the y-axis for each test/point on the rod. Eventually, over time we select the best point on the rod for maximum balance time.
In the image above Fig.(A) shows the initial state when we aren’t aware of the curve, Fig.(B) shows some progression and we start to realize how the curve looks like, After testing enough we get the complete curve which is shown by Fig.(C), at this point we select the point on x-axis i.e., the point at which we should balance the rod for maximum success.
Exhaustive Search does provide the solution but it takes a long time to optimize. In Machine Learning the amount of time required to train a model is a critical factor. If the model is not properly designed it may take months to converge, on the other side if the right selection of the algorithm is made, resulting in faster training.
Now that we know why we shouldn’t always go for this brute-force approach, we can try other Gradient-free methods for our problem but it will be overkill. In part-2 of this series, we’ll talk about Gradient-based Algorithm, also we will solve Rod Balancing problem using Gradient descent method. here is the link of the second part.
Do leave a clap if you like this post, see you in part-2. cheers!!
Credit: BecomingHuman By: Sahil Gupta