TL;DR
Logic Guided Machine Learning (LGML) integrates machine learning regressors with SAT/SMT solvers in a corrective feedback loop to learn mathematical functions that strictly comply with known domain invariants. By iteratively identifying and training on the "strongest counterexamples" where the model violates these invariants, LGML achieves several orders of magnitude better data efficiency than standard neural networks.
What Problem Does This Paper Address?
Purely data-driven machine learning models, like Multi-Layer Perceptrons (MLPs), are notoriously data-hungry and lack a mechanism to respect known mathematical laws or domain constraints. When learning a function from data, standard models might fit the training points well but violate fundamental invariants (like the triangle inequality or trigonometric identities) in unobserved regions.
The authors address this gap by combining the pattern-recognition strengths of machine learning with the rigorous verification capabilities of automated logic solvers, ensuring that the learned models are both accurate against data and consistent with established domain knowledge.
Methods
The LGML framework operates in a continuous loop consisting of two main phases:
- Learning Phase: A standard regressor (such as an MLP or a symbolic regression model) fits the current training dataset to produce an approximation function $\hat{f}$.
- Logic Phase: This phase treats the learned model as a program to be formally verified against an "auxiliary truth" $\psi$ (a known mathematical invariant). It translates this check into a satisfiability query for a Floating-Point SMT solver (specifically using CVC4).
If the model violates the invariant, the SMT solver extracts the "strongest counterexample"—the exact data point where the model's prediction deviates the most from the invariant. A bisection method is used to find this maximal error point. An oracle then labels this counterexample, it is added back into the training set, and the loop repeats until the model satisfies the invariant within a target error threshold ($\rho$). This architecture is heavily inspired by Counterexample Guided Abstraction Refinement (CEGAR) from the formal verification community.
Datasets
The method was evaluated on synthetic tasks designed to test the learning of fundamental mathematical relations:
- Pythagorean Theorem: Learning the hypotenuse function $f(a,b) = \sqrt{a^2+b^2}$ using the triangle inequality ($a+b > f(a,b)$) as the auxiliary truth.
- Sine Function: Learning $f(x) = \sin(x)$ using the identity $\sin^2(x) + \cos^2(x) = 1$, formulated via its derivative as $|\hat{f}(x)^2 + (\frac{d}{dx}\hat{f}(x))^2 - 1| > \epsilon$.
Key Insights and Ideas
- CEGAR for Machine Learning: Borrowing the concept of counterexample-guided refinement from hardware and software verification provides a principled framework for active learning. Instead of randomly sampling data or requiring massive datasets, the logic solver acts as an automated guide pointing directly to the model's weakest spots.
- Invariants as Semantic Regularizers: Traditional regularization penalizes model complexity (like weight decay), but logical invariants act as semantic regularizers. They force the model to conform to known physical or mathematical laws across the entire continuous input space, not just at discrete training points.
- Targeted Error Correction: As visualized during the iterations, the logic solver repeatedly identifies the exact peaks of error, forcing the model to quickly snap into the correct shape with minimal data points.
Key Results
- Extreme Data Efficiency: When learning the sine function, LGML achieved a Root Mean Squared Error (RMSE) of 0.037 at the 30th iteration, using a total of just 32 training points.
- Outperforming Baseline MLPs: A standard baseline MLP regressor trained without the logic guide failed to achieve a lower error score even when provided with up to 100,000 training points, demonstrating an improvement in data efficiency of several orders of magnitude.
Limitations and Future Work
Not explicitly discussed in detail within the paper. However, the framework inherently relies on the availability of a formal "auxiliary truth" expressed in a logic fragment compatible with SMT solvers, as well as access to an "oracle labeler" capable of providing ground-truth labels for the generated counterexamples.
Summary updated