Finite algorithms can solve infinite (classes of) problems. For example, the algorithm for adding two numbers has a finite description, yet can solve an infinity of examples.
This is a basic truth of computability theory.
Intuitively, it means that algorithms can exploit regularities in problems. But “regularity” here can only be defined tautologically (any smaller thing which solves/defines a bigger thing).
Less Trivial Property
Many algorithms have the following property:
The algorithm computes function Fby computing another function G many times. Computing G is useful for computing F. G is computed significantly more times than F.
Computing G is significantly easier than computing F.
G gives important information about F. This information is easy to compute and (maybe) trivial to prove.
Intuitively, it means that algorithms can exploit regularities in problems. However, here “regularity” has a stricter definition than in the trivial property (TP). A “regularity” is an easily computable thing which gives you important, easily computable information about a hard-to-compute thing.
Now, the question is: what classes of algorithms have the less trivial property (LTP)?
LTP includes a bunch of undefined terms:
“Significantly simpler”, “easily computable”, and “useful for computing”. Those could be defined in terms of computational complexity.
“Significantly more times”. Could be defined asymptotically.
“Important information”. I have little idea how it should be defined. “Important information” may mean upper and lower bounds of a function, for example.
Probably giving fully general definitions right away is not important. We could try starting with overly restrictive definitions and see if we can prove anything about those.
Relation to AI safety
If neural networks implement algorithms with LTP, we could try finding those algorithms by looking for G (which is much easier than looking for F).
Any greedy algorithm is an example. The whole solution to the problem is F, the greedy choice is G.
Many dynamic programming algorithms are an example. Solution to the whole problem is F, solution to a smaller problem (which we need to use many times) is G.
Consider a strong chess engine. F: “given a position, find how to e.g. win material given an ~N moves horizon”. G: “given a position, find how to e.g. win material given a ~K moves horizon”. Where K << N. Simply put, the N-moves-deep engine will often punish K-moves-deep mistakes. That’s the reason why you can understand that you’re losing long before you get checkmated. This wouldn’t be true in a game much more chaotic than chess.
Consider simulated annealing. F: “given a function, find the global optimum”. AFAICT, simulated annealing is greedy search + randomness. The greedy part is G.
Have an idea about interpretability and defining search/optimization.
Trivial Property
Finite algorithms can solve infinite (classes of) problems. For example, the algorithm for adding two numbers has a finite description, yet can solve an infinity of examples.
This is a basic truth of computability theory.
Intuitively, it means that algorithms can exploit regularities in problems. But “regularity” here can only be defined tautologically (any smaller thing which solves/defines a bigger thing).
Less Trivial Property
Many algorithms have the following property:
The algorithm computes function Fby computing another function G many times. Computing G is useful for computing F. G is computed significantly more times than F.
Computing G is significantly easier than computing F.
G gives important information about F. This information is easy to compute and (maybe) trivial to prove.
Intuitively, it means that algorithms can exploit regularities in problems. However, here “regularity” has a stricter definition than in the trivial property (TP). A “regularity” is an easily computable thing which gives you important, easily computable information about a hard-to-compute thing.
Now, the question is: what classes of algorithms have the less trivial property (LTP)?
LTP includes a bunch of undefined terms:
“Significantly simpler”, “easily computable”, and “useful for computing”. Those could be defined in terms of computational complexity.
“Significantly more times”. Could be defined asymptotically.
“Important information”. I have little idea how it should be defined. “Important information” may mean upper and lower bounds of a function, for example.
Probably giving fully general definitions right away is not important. We could try starting with overly restrictive definitions and see if we can prove anything about those.
Relation to AI safety
If neural networks implement algorithms with LTP, we could try finding those algorithms by looking for G (which is much easier than looking for F).
Furthermore, LTP seems very relevant to defining search / optimization.
Examples of LTP
Examples of algorithms with LTP:
Any greedy algorithm is an example. The whole solution to the problem is F, the greedy choice is G.
Many dynamic programming algorithms are an example. Solution to the whole problem is F, solution to a smaller problem (which we need to use many times) is G.
Consider a strong chess engine. F: “given a position, find how to e.g. win material given an ~N moves horizon”. G: “given a position, find how to e.g. win material given a ~K moves horizon”. Where K << N. Simply put, the N-moves-deep engine will often punish K-moves-deep mistakes. That’s the reason why you can understand that you’re losing long before you get checkmated. This wouldn’t be true in a game much more chaotic than chess.
Consider simulated annealing. F: “given a function, find the global optimum”. AFAICT, simulated annealing is greedy search + randomness. The greedy part is G.