Good question. All supervised learning is a form of search with three components:
- Specification: what are you are looking for?
- Search space: were are you looking?
- Search mechanism: how are you going through the search space?
Program synthesis is simply learning where the search space is syntax.
In deep learning, taking the ImageNet paper as an example, the specification a bunch of photos with annotations, the search space is multi-variate real functions (encoded as matrix of floats) and the search mechanisms is
gradient descent (implemented as backprop) with a loss function.
I think this paper uses regular expressions an example of how to search fast over syntax. It claims not to be tied to regular expressions.
Regexps aren't even Turing complete as far as I know, if whatever they have in their paper works for arbitrary programs it would be shocking. I'll give it a read.
*Edit*: The algorithm in the paper is a DP like algorithm for building regexes. They use a matrix, and it has all the potential strings to be checked on one axis, and all the potential regex programs on the other axis, and in-between values (the actual matrix values) are booleans saying whether the string matches the program. The algorithm builds the matrix iteratively.
I haven't understood how regex evaluation is done, probably directly, but obviously this algorithm is only for checking whether a particular regex program matches an output rather than general purpose synthesis.
We'll have to wait for AI chips to really scale genetic programming, GPUs won't cut it.
There is no magic in GP. It is just another form of searching the space of programs, i.e. program synthesis. The search mechanism is a local, stochastic search, known to be especially inefficient (for example you may hit the same program multiple times). What's good about GP is how simple it is, so it's a good starting point.
- Specification: what are you are looking for?
- Search space: were are you looking?
- Search mechanism: how are you going through the search space?
Program synthesis is simply learning where the search space is syntax. In deep learning, taking the ImageNet paper as an example, the specification a bunch of photos with annotations, the search space is multi-variate real functions (encoded as matrix of floats) and the search mechanisms is gradient descent (implemented as backprop) with a loss function.
I think this paper uses regular expressions an example of how to search fast over syntax. It claims not to be tied to regular expressions.