This is the twenty-fifth article in a series dedicated to the various aspects of machine learning (ML). Today’s article will cover common types of search algorithms in machine learning.
When we are running down our many options for dinner, we tend to do a mental “search” for what we want. If we are eating out, or getting a drive-thru meal, then we probably think of what is nearest to us. Then, we will probably consider the price of the restaurants within our decided parameters. If we’re eating inside, we might look through our cabinets and fridge, trying to think of what we could summon the effort to cook. Your choice-making is all a matter of pre-establishing parameters (Eat out? If so, how far are you willing to go and how much money are you willing to spend? Stay in? If so, how much energy are you willing to put into cooking?) We decide on our parameters, and then we progress to our decision.
This same principle is found in the decision-making of AI agents, in that their search algorithms are often differentiated by the kinds of parameters they establish in decision-making. Just as there are many ways to decide between going out and getting a quintiple-grand chalupa from Taco Bell or settling for an at-home milk-filled bowl of Count Chocula, there is a wide variety of ways for a machine learning agent to decide how to reach its end goal.
Take a tour with us through the various ways to search for an ML agent below!
Search Algorithms: The Basics
What should you know about a search algorithm? Well, search algorithms consist of nodes that represent “states” that an agent can reach by taking certain actions. The sequence of nodes starts from an initial node, called a “parent” node, down through “child” nodes that are reached through chosen actions, which ultimately leads to the “goal” node, or desired action.
When deciding on how to reach a goal state, an agent will consider the available paths that lead to goal nodes. There are many factors that an agent must consider when choosing a particular path, such as completeness (is there a solution at the end of the path?), cost (how much memory is used?), and time (how many nodes will be passed, or actions taken, to reach the goal state?).
What ultimately influences the chosen path depends on the type of search that the agent employs. Keep reading for an enumeration of some of the types of search.
Breadth-First Search
This is done when there is a similarity or even equality among the available actions. So, an agent will expand its search across a wide variety of parent nodes and choose among the wide variety of paths available.
Depth-First Search
This is not the most cost-friendly type of search, but it can be very informative. What is done here is that the agent searches through each path sequence to completion, deciding if it meets a certain cost threshold or not. As opposed to breadth-first search, which looks at the wide variety of paths of available, depth-first search is dedicated to seeing how deep a few (or more) paths are, and choosing among those based on the amount of cost and time that each path requires.
An agent can set a depth-limit as well, which establishes how many actions it is willing to take to reach a goal state. If a path has too many actions/nodes on the way to the goal, then it will not be chosen.
Uniform-Cost Search
This is used when, in contrast to breadth-first circumstances, there are many different costs for actions. What is done in this case is that the path costs are calculated, and the breadth of search is expanded in order to find more desirable path costs, if needed.
Summary
We’ve just considered three types of search algorithms. Before that, we clarified why there are even different types of search algorithms, for the reason that not all paths to a goal are the same, and that time and memory costs for the available paths, and the similarity and difference in said costs between the individual paths, can determine what type of search is employed. If the path costs are similar, then breadth-first is taken. If there is a lot of difference in costs, then uniform-cost search is called upon. In other instances, depth-first search may be employed, where the agent will search individual path by path to find one it prefers.
Recent Comments