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?

AI/ML

Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot