a program is more “search-like” if it is enumerating possible actions and evaluating their consequences
I’m curious if you mean something different by search when you say that we’re likely to find policies that look like an “explicit search process + simple objective(s)”
Yeah, that’s definitely not what I mean by search (nor what I think others mean by search, in the context of AI and inner agents).
Roughly speaking, a general search process is something which takes in a specification of some problem or objective (from a broad class of possible problems/objectives), and returns a plan which solves the problem or scores well on the objective. For instance, a gradient descent algorithm takes in an objective, and returns a point which scores well on the objective, for a very broad class of possible objectives; gradient descent is therefore a search method.
Enumerating possible actions and evaluating their consequences is one way to do general search, but it’s wildly inefficient; I would typically refer to that as “brute force search”. Gradient descent does better by leveraging backprop and gradients; approximately none of the algorithmic work done by gradient descent comes from direct evaluation of the consequences of actions. And there are many other tricks one can use too—like memoization on subsearches, or A*-style heuristic search, or (one meta-level up from A*) relaxation-based methods to discover heuristics. The key point is that these tricks are all very general purpose: they work on a very wide variety of search problems, and therefore produce general-purpose search algorithms which are more efficient than brute force (at least on realistic problems).
More advanced general-purpose search methods seem to rely relatively little on enumerating possible actions and evaluating their consequences. By the time we get to human-level search capabilities, we see human problem-solvers spend most of their effort on nontrivial problems thinking about subproblems, abstractions and analogies rather than thinking directly about particular solutions.
I agree that A* and gradient descent are central examples of search; for realistic problems these algorithms typically evaluate the objective on millions of candidates before returning an answer.
In contrast, human problem solvers typically do very little state evaluation—perhaps evaluating a few dozen possibilities directly, and relying (as you said) on abstractions and analogies instead. I would call this type of reasoning “not very search-like”.
On the far end we have algorithms like Gauss-Jordan elimination, which just compute the optimal solution directly without evaluating any possibilities. Calling them “search algorithms” seems quite strange.
a general search process is something which takes in a specification of some problem or objective (from a broad class of possible problems/objectives), and returns a plan which solves the problem or scores well on the objective.
This appears to be a description of anyoptimization process, not just search—in particular it would include Gauss-Jordan elimination. I guess your ontology has “optimization” and “search” as synonyms, whereas mine has search as a (somewhat fuzzy) proper subset of optimization. Anyways, to eliminate confusion I’ll use Abram Demski’s term selection in future. Also added a terminology note to the post.
My ontology indeed has search and a narrow notion of optimization as approximately synonyms; they differ only somewhat in type signature and are easily interchangeable. Conceptually, both take in an objective, and return something which scores highly on the objective. (This is narrower than e.g. Flint’s notion of “optimization”; in that ontology it might be called a “general-purpose optimizer” instead.)
Anyway, insofar as any of this is relevant to the arguments for mesa-optimization, it’s the notion of search/optimization as general problem solving which applies there.
Roughly speaking, a general search process is something which takes in a specification of some problem or objective (from a broad class of possible problems/objectives), and returns a plan which solves the problem or scores well on the objective.
This description of “search” seems far too broad. E.g., it seems to include things like lookup tables, and AFAICT, literally every way to solve problems or satisfy objectives?
Seems like “search” should mean something more specific than “problem solving”.
It excludes methods specific to a small number of problems. Search is about general problem solving.
Anyway, IIUC this is how the term “search” has historically been used in AI, it is also the notion of “search” which is relevant to the arguments for mesaoptimization in Risks From Learned Optimization, it is also the notion of search which is relevant to general intelligence being A Thing, it is the notion of search which is relevant to the possibility of an ML system suddenly grokking “general search” and thereby undergoing a rapid increase in capabilities, etc.
See my answer to tailcalled:
I’m curious if you mean something different by search when you say that we’re likely to find policies that look like an “explicit search process + simple objective(s)”
Yeah, that’s definitely not what I mean by search (nor what I think others mean by search, in the context of AI and inner agents).
Roughly speaking, a general search process is something which takes in a specification of some problem or objective (from a broad class of possible problems/objectives), and returns a plan which solves the problem or scores well on the objective. For instance, a gradient descent algorithm takes in an objective, and returns a point which scores well on the objective, for a very broad class of possible objectives; gradient descent is therefore a search method.
Enumerating possible actions and evaluating their consequences is one way to do general search, but it’s wildly inefficient; I would typically refer to that as “brute force search”. Gradient descent does better by leveraging backprop and gradients; approximately none of the algorithmic work done by gradient descent comes from direct evaluation of the consequences of actions. And there are many other tricks one can use too—like memoization on subsearches, or A*-style heuristic search, or (one meta-level up from A*) relaxation-based methods to discover heuristics. The key point is that these tricks are all very general purpose: they work on a very wide variety of search problems, and therefore produce general-purpose search algorithms which are more efficient than brute force (at least on realistic problems).
More advanced general-purpose search methods seem to rely relatively little on enumerating possible actions and evaluating their consequences. By the time we get to human-level search capabilities, we see human problem-solvers spend most of their effort on nontrivial problems thinking about subproblems, abstractions and analogies rather than thinking directly about particular solutions.
I agree that A* and gradient descent are central examples of search; for realistic problems these algorithms typically evaluate the objective on millions of candidates before returning an answer.
In contrast, human problem solvers typically do very little state evaluation—perhaps evaluating a few dozen possibilities directly, and relying (as you said) on abstractions and analogies instead. I would call this type of reasoning “not very search-like”.
On the far end we have algorithms like Gauss-Jordan elimination, which just compute the optimal solution directly without evaluating any possibilities. Calling them “search algorithms” seems quite strange.
This appears to be a description of any optimization process, not just search—in particular it would include Gauss-Jordan elimination. I guess your ontology has “optimization” and “search” as synonyms, whereas mine has search as a (somewhat fuzzy) proper subset of optimization. Anyways, to eliminate confusion I’ll use Abram Demski’s term selection in future. Also added a terminology note to the post.
My ontology indeed has search and a narrow notion of optimization as approximately synonyms; they differ only somewhat in type signature and are easily interchangeable. Conceptually, both take in an objective, and return something which scores highly on the objective. (This is narrower than e.g. Flint’s notion of “optimization”; in that ontology it might be called a “general-purpose optimizer” instead.)
Anyway, insofar as any of this is relevant to the arguments for mesa-optimization, it’s the notion of search/optimization as general problem solving which applies there.
This description of “search” seems far too broad. E.g., it seems to include things like lookup tables, and AFAICT, literally every way to solve problems or satisfy objectives?
Seems like “search” should mean something more specific than “problem solving”.
It excludes methods specific to a small number of problems. Search is about general problem solving.
Anyway, IIUC this is how the term “search” has historically been used in AI, it is also the notion of “search” which is relevant to the arguments for mesaoptimization in Risks From Learned Optimization, it is also the notion of search which is relevant to general intelligence being A Thing, it is the notion of search which is relevant to the possibility of an ML system suddenly grokking “general search” and thereby undergoing a rapid increase in capabilities, etc.