This paper, presented at NIPS 2016, explores a "best of both worlds" approach to discrete optimization. By combining the generative power of Deep Belief Networks (DBNs) with the logical rigor of Inductive Logic Programming (ILP), the authors demonstrate how to bake qualitative domain knowledge directly into a neural search process.
TL;DR
The authors propose a neuro-symbolic framework for discrete optimization that uses ILP to extract logical rules from domain knowledge and injects them as features into a DBN. This hybrid model significantly improves the efficiency of Estimation of Distribution Algorithms (EDAs), finding near-optimal solutions faster than purely neural approaches.
What Problem Does This Paper Address?
Many real-world optimization problems, like train scheduling or chess strategy, involve qualitative "rules of thumb" that are hard to translate into raw numbers for a standard neural network. For example, a rail scheduler knows that "high-priority trains should be preferred unless the delay to a lower-priority train becomes excessive."
Traditional Estimation of Distribution Algorithms (EDAs) try to solve these problems by iteratively building a probabilistic model of what a "good" solution looks like and then sampling from that model. However, purely neural models (like DBNs) often struggle to learn complex logical constraints from scratch, while purely symbolic models (like ILP) are difficult to sample from efficiently. The challenge is: how do we guide a neural generator using explicit logical rules?
Methods
The authors introduce a Neuro-symbolic EDA. The process follows an iterative loop:
- Labeling: Solutions in the current population are labeled "good" or "bad" based on a performance threshold.
- Symbolic Learning (ILP): An ILP engine (Aleph) uses background domain knowledge to find logical rules that distinguish "good" solutions from "bad" ones.
- Neural Integration: These logical rules are converted into Boolean features. These features are then appended to the highest hidden layer of a DBN.
- Biased Sampling: To generate the next generation of solutions, the DBN is trained on the current data. During the sampling phase, the ILP-based feature units are "clamped" to a value of 1. This forces the DBN to generate new samples that are consistent with the logical rules discovered by the ILP engine.
Datasets
The approach was evaluated on two synthetic but complex benchmarks:
- KRK Chess Endgame: Predicting the "depth-of-win" for a White King and Rook vs. a Black King. This is a classic ILP benchmark with a known, noise-free state space of ~28,000 legal positions.
- Job-Shop Scheduling: A restricted 5x5 scheduling problem (5 jobs, 5 machines). This represents a computationally hard real-world planning task where timing and machine constraints are paramount.
Key Insights and Ideas
- Logical Bias as a Shortcut: Instead of waiting for a DBN to eventually "notice" a pattern (like the distance between two chess pieces), ILP provides that pattern as an explicit feature. This acts as a powerful inductive bias.
- The Sampling Bottleneck: While ILP is great at finding rules, generating new data that satisfies those rules is hard. By using the DBN as the sampler and the ILP rules as "clamps," the authors solve the efficiency problem of symbolic AI.
- Cascading Improvement: Because the EDA is iterative, better sampling in iteration $N$ leads to a better training set for iteration $N+1$. The authors observed a "cascading" effect where the neuro-symbolic model pulled away from the standard neural model more significantly as iterations progressed.
Key Results
The hybrid DBNILP model outperformed the standard DBN across the board:
- Higher Precision: In the Chess task, the probability of sampling a "good" instance was significantly higher with ILP features (e.g., at iteration 3, DBNILP had a 0.101 probability vs. the DBN's 0.015).
- Better Convergence: For Job-Shop scheduling, the DBNILP was able to reach the optimal solution within 10 iterations, whereas the standard DBN lagged behind.
- Near-Optimal Density: On termination, the samples generated by the ILP-assisted DBN contained a substantially higher proportion of near-optimal solutions compared to the DBN alone.
Limitations and Future Work
- Computational Overhead: Running an ILP engine inside an optimization loop adds significant computational cost, though the authors argue this is offset by the reduced number of iterations needed.
- Rule Complexity: The Job-Shop background knowledge required longer logical clauses (up to 10 literals) to be effective, suggesting that the success of this method is highly dependent on the quality and depth of the provided background knowledge.
- Future Directions: The authors suggest moving beyond DBNs to more modern generative models (like Variational Autoencoders or GANs) and exploring ways to incorporate logical rules directly into the neural cost function rather than just as input features.
Summary updated