Neuro-symbolic EDA-based Optimisation using ILP-enhanced DBNs

Sarmimala Saikia, Lovekesh Vig, Ashwin Srinivasan, Gautam Shroff, Puneet Agarwal, Richa RawatarXiv 2016 · arXiv

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:

  1. Labeling: Solutions in the current population are labeled "good" or "bad" based on a performance threshold.
  2. Symbolic Learning (ILP): An ILP engine (Aleph) uses background domain knowledge to find logical rules that distinguish "good" solutions from "bad" ones.
  3. Neural Integration: These logical rules are converted into Boolean features. These features are then appended to the highest hidden layer of a DBN.
  4. 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.
Figure 2: Sampling from a DBN (a) with just a separator variable (b) with ILP features

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.
Distribution of solution endtimes for Job-Shop scheduling. Note how DBNILP (right) shifts the distribution toward lower (better) endtimes more aggressively than the standard DBN (left).

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

Abstract

We investigate solving discrete optimisation problems using the estimation of distribution (EDA) approach via a novel combination of deep belief networks(DBN) and inductive logic programming (ILP).While DBNs are used to learn the structure of successively better feasible solutions,ILP enables the incorporation of domain-based background knowledge related to the goodness of solutions.Recent work showed that ILP could be an effective way to use domain knowledge in an EDA scenario.However,in a purely ILP-based EDA,sampling successive populations is either inefficient or not straightforward.In our Neuro-symbolic EDA,an ILP engine is used to construct a model for good solutions using domain-based background knowledge.These rules are introduced as Boolean features in the last hidden layer of DBNs used for EDA-based optimization.This incorporation of logical ILP features requires some changes while training and sampling from DBNs: (a)our DBNs need to be trained with data for units at the input layer as well as some units in an otherwise hidden layer, and (b)we would like the samples generated to be drawn from instances entailed by the logical model.We demonstrate the viability of our approach on instances of two optimisation problems: predicting optimal depth-of-win for the KRK endgame,and jobshop scheduling.Our results are promising: (i)On each iteration of distribution estimation,samples obtained with an ILP-assisted DBN have a substantially greater proportion of good solutions than samples generated using a DBN without ILP features, and (ii)On termination of distribution estimation,samples obtained using an ILP-assisted DBN contain more near-optimal samples than samples from a DBN without ILP features.These results suggest that the use of ILP-constructed theories could be useful for incorporating complex domain-knowledge into deep models for estimation of distribution based procedures.
BibTeX
@misc{saikia2016neuro,
  author = {Sarmimala Saikia and Lovekesh Vig and Ashwin Srinivasan and Gautam Shroff and Puneet Agarwal and Richa Rawat},
  title = {{Neuro-symbolic EDA-based Optimisation using ILP-enhanced DBNs}},
  year = {2016},
  eprint = {1612.06528},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.06528},
}
Figure