Original Source Here
concept 1. search problems
What do the game of sudoku, program synthesis, coming up with research ideas, reinforcement learning, writing a paper, 3SAT, and making a delicious sausage have in common? The answer is that they are all search problems where the answer is easy to check and the solution is difficult to find — While David Hilbert can easily discern a tasty sausage, it is unlikely that he knew how to make one. Let’s formally define what a search problem is.
def : search problem
A search problem is a tuple (X, v) where X is the space of all possible solutions and v is a scoring function that, for each x in X, gives a score. The objective of a search problem is to propose a particular x that maximizes the score.
generate and check
The standard way of solving a search problem is generate and check: an algorithm generates a stream of proposals x1, x2, x3 … and gives one that has the highest score using v. For instance, one can enumerate potential solutions to a sudoku puzzle one after another, and check if the rules of sudoku is satisfied each time (score of 1 and 0). One can also find the inverse of a matrix A by, humor me if you will, enumerating all possible matrices B1, B2, B3, … and checking each one if AB=1.
knowledge of X → better generation
One can improve generation by leveraging the structure of X to perform intelligent generations. For instance, by realizing that the loss function (AB-1)² is convex, one can use gradient descent to generate a sequence B1,B2,… which quickly approaches the true inverse of A. Further, you can just follow the algorithm for inverting a matrix. Intelligent generations (through knowledge of X) applies beyond algorithms: A better researcher has a higher success rate in generating research because they understands the field better.
search problems in this blog series
Formulating a problem as a search allows for a very clean separation of concerns, separating the problem definition (how do we check if a solution x is good?) from the problem solution (actually generating an x that is good). This separation is a powerful thinking tool that allow you to set a well-defined goal unconstrained by your current capabilities of achieving it, while being creative in generating a solution without fear of getting lost. For instance, in the topic of coming up with research ideas, Chapter 1 gives hints on how to generate good research ideas with an emphasis on being chaotic, while Chapter 2 gives the check on whether the idea is worth pursuing further with an emphasis on being disciplined.
Now that we’re finished with our detour, let’s get back on track of how to acquire knowledge under the lens of search problems. We have already established the checking part, in the form of a demonstration: “If I learned X, then I should be able to perform Y”. How do we actually go about acquiring X?
Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot