10
$\begingroup$

I came across an article, The Bitter Truth, via the Two Minute Papers YouTube Channel. Rich Sutton says...

One thing that should be learned from the bitter lesson is the great power of general purpose methods, of methods that continue to scale with increased computation even as the available computation becomes very great. The two methods that seem to scale arbitrarily in this way are search and learning.

What is the difference between search and learning here? My understanding is that learning is a form of search -- where we iteratively search for some representation of data that minimizes a loss function in the context of deep learning.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
9
$\begingroup$

In the context of AI:

  1. Search refers to Simon & Newell's General Problem Solver, and it's many (many) descendant algorithms. These algorithms take the form:

    a. Represent a current state of some part of the world as a vertex in a graph.

    b. Represent, connected to the current state by edges, all states of the world that could be reached from the current state by changing the world with a single action, and represent all subsequent states in the same manner.

    c. Algorithmically find a sequence of actions that leads from a current state to some more desired goal state, by walking around on this graph.

An example of an application that uses search is Google Maps. Another is Google Flights.

  1. Learning refers to any algorithm that refines a belief about the world through the exposure to experiences or to examples of others' experiences. Learning algorithms do not have a clear parent, as they were developed separately in many different subfields or disciplines. A reasonable taxonomy is the 5 tribes model. Some learning algorithms actually use search within themselves to figure out how to change their beliefs in response to new experiences!

    An example of a learning algorithm used today is Q-learning, which is part of the more general family of reinforcement learning algorithms. Q-learning works like this:

    a. The learning program (usually called the agent) is given a representation of the current state of the world, and a list of actions that it could choose to perform.

    b. If the agent has not seen this state of the world before, it assigns a random number to the reward it expects to get for performing each action. It stores this number as $Q(s,a)$, its guess at the quality of performing action $a$ in-state $s$.

    c. The agent looks at $Q(s,a)$ for each action it could perform. It picks the best action with some probability $\epsilon$ and otherwise acts randomly.

    d. The action of the agent causes the world to change and may result in the agent receiving a reward from the environment. The agent makes a note of whether it got a reward (and how much the reward was), and what the new state of the world is like. It then adjusts its belief about the quality of performing the action it performed in the state it used to be in, so that its belief about the quality of that action is closer to the reality of the reward it got, and the quality of where it ended up.

    e. The agent repeats steps b-d forever. Over time, its beliefs about the quality of different state/action pairs will converge to match reality more and more closely.

An example of an application that uses learning is AI.SEs recommendations, which are made by a program that likely analyzes the relationships between different combinations of words in pairs of posts, and the likelihood that someone will click on them. Every time someone clicks on them, it learns something about whether listing a post as related is a good idea or not. Facebook's feed is another everyday example.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This answer is correct, but I think it should be noted that learning algorithms can be viewed as search algorithms (not necessarily in the same way as you describe search algorithms, which is the typical way of describing traditional search algorithms, such as A*, where you represent the state space as a graph, states as nodes and connections between those states as edges). For example, we can view Q-learning as searching for state-action value function over some space of state-action value functions. $\endgroup$
    – nbro
    Commented Sep 12, 2020 at 13:17
  • $\begingroup$ @nbro I think that's true also. In the context of the Sutton quote though I'm quite sure he is thinking of search in the classic AI sense, rather than optimization of functions, since he lists the two ideas as separate. $\endgroup$
    – John Doucette
    Commented Sep 12, 2020 at 18:54
0
$\begingroup$

One way to think of the difference between search and learning is that search usually entails a search key, and an algorithm hunts through the structure looking for a match between the key and an already-existing item. Whereas learning is the creation of the structure in the first place. But search and learning are related in that on receipt of an input (say from one or more sensors) the structure is initially searched to see if the input already exists, but if it doesn't then current input (when certain conditions are met) is added to the structure, and learning follows a failure of search.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .