Re:Symbolic mathematics finally yields to neural networks
by orange3xchicken on Tuesday May 26, 2020 @12:22PM
(#23313062)
In general, I think neural networks really struggle with np hard problems. Current state of the art is bottlenecked wrt to even subtle generalization. The strong baselines have been variations on the pointer-network architecture for some time now. Even though they can do reasonably well on restricted problems (e.g. instances of sat/traveling salesman with fixed # of nodes), they struggle to generalize to instances of the problem with variable # of nodes - not to mention varying the problem itself. Some popular approaches also incl. applications of Graph CNNs & reinforcement learning. Don't really have much more than a cursory idea of the current directions though.
To me, more exciting is some kind of joint collaboration between modern ml systems & formal solvers.
Re:Symbolic mathematics finally yields to neural networks
by bglazer on Tuesday May 26, 2020 @09:15PM
(#23318374)
You might be interested in the line of work around differentiable relaxations of formal solvers that was kicked off by Zico Kolter et al. They add a Max=SAT solver as a differentiable layer. This allows the neat trick of solving handwritten Sudoku puzzles by composing a ConvNet with the differentiable Max-SAT layer.
Re:Symbolic mathematics finally yields to neural networks
by orange3xchicken on Tuesday May 26, 2020 @10:42PM
(#23318857)
Thanks - that's great! I'm familiar with Kolter's work on adversarial robustness.
If it could be used to greatly accelerate SMT solving/constraint solving, perhaps it would be possible to run a formal model as if it were code, i.e. fast and scalable constraint-based programming. That's about as high-level as you can get, short of a requirements document. I'm not sure if that's the kind of symbolic mathematics that's being studied here, as they seem to be looking at mathematically interesting expressions, rather than boring-but-enormous constraints.
Or, somewhat related, perhaps it could be used to help scale formal verification with languages like SPARK and ZZ.