4 ms·
Real-time and energy-constrained problems would be the top use cases in my mind given the current state of affairs. Beyond this, problems that are non-different
by bob1029 2y ago
Real-time and energy-constrained problems would be the top use cases in my mind given the current state of affairs. Beyond this, problems that are non-differentiable or where we desire strong symbolic interpretation. I think these techniques also tend to extrapolate more robustly than DNNs. Technically, any problem where algorithmic shortcuts like the chain rule of calculus break down.
I've been working on GP architectures that use short linear program tapes as part of their genome. Executing these programs can be done very quickly. Assuming the program tape is <=10kb in length and you are constraining to ~a megacycle in the interpreter, you can execute these programs 100k~1m times per second on a chunky workstation. The problems you can solve in this time & space are non-trivial. Once you evolve the desired program, you can write the interpreter for it in any language on any platform within half an hour.
Training is definitely going to be expensive but it can fit in one powerful machine. You don't need to keep a terabyte of data around in VRAM to make reasonable rates of progress. Paging out parts of the population to disk or S3 buckets is feasible with these techniques. It subdivides very nicely into however many islands you can afford to run.
Inference is essentially free and could run on the processor in your toaster oven.
These approaches can make CUDA & friends look like a Rube Goldberg machine by comparison. Being able to explain how the entire thing works to a peer in a single afternoon is perhaps another significant feature of these designs.
At the end of the day, there is a pretty good reason these techniques aren't popular - There aren't any quadratic scaling laws that constrain the architecture of GP. Only the much scarier exponential ones. I contend that the search space of all linear programs is viable, but I still don't have any proof that this is the case after chasing the rabbit for about a year. My central argument is that there are many high-quality programs out there. We just need to find one of them. I think the arguments against this tend to unfairly cast the problem as searching for a single needle in a haystack of 10^10000.
- imtringued 2y agoParametric programming problems are problems whose structure (most often sparsity structure) is known. Most quadratic and linear programming solvers assume a fully generic problem structure. You give them any matrix and they'll spit out an answer. This means that internally they must also use generic matrix operations. If you know the full structure of the optimization problem and how it changes with respect to changes in parameters, you could in principle compile a unique solver that is fully specialized to the parameterized problem. If your problem is particularly simple, you could even enumerate all possible answers in a lookup table. https://en.m.wikipedia.org/wiki/Parametric_programming https://en.m.wikipedia.org/wiki/Parametric_programming Now here is the problem: While it is not that difficult to find the sparsity pattern of the optimization problem and choose the appropriate sparse matrix library based on the problem, actually producing a unique program that does nothing but solve your parametric optimization problem is a pipe dream. Most approaches involve a lot of human ingenuity to find exploitable structures in specific problems that become useless the moment you change the problem even a little bit. So here is my suggestion: figure out how to use genetic programming to produce fast quadratic programming solvers to specific problems. Note that you don't necessarily need a perfect solution since you can always run a bunch of QP steps on an initial guess to nudge it towards convergence. The goal would be to reduce the number of these steps to as close to zero as possible.
- avidiax 2y agoWhat kinds of problems are you trying to solve that can be solved by short program tapes but aren't obvious to a human?
- bob1029 2y agoI have a hypothesis that the smallest possible program that can handle things like natural language translation will be much smaller than we are expecting it to be. Anything where we are transforming information from one format to another on a ~1:1 basis without injecting additional external information (i.e., what foundation models do with their broad world knowledge).
- avidiax 2y agoI don't know what your expectation on the program's size is, but even for a constrained translation case (i.e. legal transcription between two Romance languages), I would expect you are embedding at least the size of WordNet in both languages.
- taylorius 2y agoData modelling, especially in high dimensions can be non-obvious to a human, yet a tractably small program can do well.