Given enough data, Deep Neural Networks (DNNs) are capable of learning complex input-output relations with high accuracy. In several domains, however, data is scarce or expensive to retrieve, while a substantial amount of expert knowledge is available. It seems reasonable that if we can inject this additional information in the DNN, we could ease the learning process. One such case is that of Constraint Problems, for which declarative approaches exists and pure ML solutions have obtained mixed success. Using a classical constrained problem as a case study, we perform controlled experiments to probe the impact of progressively adding domain and empirical knowledge in the DNN. Our results are very encouraging, showing that (at least in our setup) embedding domain knowledge at training time can have a considerable effect and that a small amount of empirical knowledge is sufficient to obtain practically useful results. 4
Given enough data, Deep Neural Networks are capable of learning complex input-output relations with high accuracy. In many domains, however, there exists also a substantial degree of expert knowledge: it seems reasonable that if we can inject this additional information in the DNN, we could ease the learning process. Indeed, methods for hybridizing learning and reasoning (or for taking into account constraints at training time) can accelerate convergence or improve the accuracy, especially when supervised data is scarce.
In this paper we aim at characterizing this trade-off between implicit knowledge (derived from data) and explicit knowledge (supplied by experts), via a set of controlled experiments. On this purpose, we use a setting that is both rigorous enough from a scientific standpoint and practically relevant: that of constrained problems.
Constrained problems involve assigning values to a set of variables, subject to a number of constraints, and possibly with the goal of minimizing a cost metric. Depending on the lack or presence of a cost function, they are formally known as Constraint Satisfaction Problems (CSPs) or Constraint Optimization problems (COPs).
Constrained problem are classically modeled by domain experts in a fully declarative fashion: however, such models can be hard to design, may rely on simplistic and unquantifiable approximations, and may fail to take into account constraints (or preferences) that are not known to the expert, despite being satisfied in historical solutions. Data-driven methods for constrained problems offer a potential solution for some of these issues, but they may have trouble maintaining feasibility and they struggle with the (very) limited number of past solutions available for practical use cases.
We use as a benchmark the Partial Latin Square (PLS) completion problem, which requires to complete a partially filled n n square with values in f1::ng, such that no value appears twice on any row or column. Despite its simplicity, the PLS is NP-hard, unless we start from an empty square; the problem has practical applications (e.g. in optical fiber routing), and serves as the basis for more complex problems (e.g. timetabling). Using a classical constrained problem as a case study grants access to reliable domain knowledge (the declarative formulation), and facilitates the generation of empirical data (problem solutions). This combination enables controlled experiments that are difficult to perform on more traditional datasets.
We train a problem-agnostic, data-driven, solution approach on a pool of solutions, and we inject domain knowledge (constraints) both at training time and at solution generation time. We then adjust the amount of initial data (empirical knowledge) and of injected constraints (domain knowledge), and assess the ability of the approach to yield feasible solutions. Our results are very encouraging, showing that (at least in our setup) embedding domain knowledge in a datadriven approach can have a considerable effect, and that a small amount of empirical knowledge is sufficient to obtain practically useful results.
As a byproduct of our analysis, we develop general techniques for taking into account constraints in data-driven methods for decision problems, based on easily accessible methods from the Constraint Programming and Machine Learning domains. While such techniques are originally designed for problems with discrete decision, they should be adaptable to numeric decisions as well. Hence, despite our focus remains on a scientific investigation, we also regard this paper as a relevant step towards practical applicability for some data-driven solution methods for constrained problems. We also think that integrating data-driven methods and Constraint Programming will be helpful to develop more human-centered AI systems. Nowadays, the wide adoption of AI in everyday life has introduced the need for methods that are more focused on the requirements of human operators. A practical scenario is the one of constraints that allow the autonomous system to grant fairness and to meet security guidelines during the decision process. Despite their great success, since they are a purely data-driven approach, DNNs may fail to correctly infer and generalize fairness or security constraints because they may be only partially satisfied in the data. At the same time, declarative models can help to overcome this limitation of data-driven methods. This motivates the interest for the developing of hybrid approaches that can exploit the advantages of both data-driven and declarative methods.
The paper is organized as follows: Section 2 briefly surveys the related literature and motivates the choice of our baseline techniques; Section 3 discusses the details of the problem and methods we use; Section 4 presents the results of our analysis, while Section 5 provides concluding remarks. 2
The analysis that we aim to perform requires 1) a data-driven
technique that can solve a constrained problem, with no access to its
structure; moreover, we need 2) methodologies for injecting domain
knowledge in such a system, both at training time and after training.
In this section, we briefly survey methods available in the literature
for such tasks and we motivate our selection of techniques.
Neural Networks for Solving Constrained Problems The
integration of Machine Learning methods for the solution of constrained
problems is an active research topic, which has recently been
surveyed in [
Some approaches (e.g. [
To the best of the authors knowledge, the only example of
problemagnostic, data-driven, approach for the solution of constrained
problems is the one in [
Domain Knowledge in Neural Networks There are several
approaches for incorporating external knowledge in Neural Networks,
none of which has been applied so far on constrained decision
problems. One method to do take into account domain knowledge at
training time is the so-called Semantic Based Regularization [
Integration of external knowledge in Neural Networks after
training is considered for example in DeepProbLog [
Recent works such as [
We use a method loosely based on Semantic Based Regularization for injecting knowledge at training time, as it offers a good compromise between flexibility and simplicity. For injecting knowledge after training, we rely on a very simple method well suited for constrained problems (i.e. using constraint propagation to adjust the output of the ML model). 3
We reimplement the approach from [
Neural Network for the Data Driven Approach The baseline approach is based on training a Neural Network to extend a partial assignment (also called a partial solution) by making one additional assignment, so as to preserve feasibility. Formally, the network is a function: f : f0; 1gm ! [0; 1]m (1) whose input and output are m dimensional vectors. Each element in the vectors is associated to a variable-value pair hzj ; vj i, where zj is the associated variable and vj is the associated value. The network input represents partial assignments, assuming that xj = 1 iff zj = vj . Each component fj (x) of the output is proportional to the probability that pair hzj ; vj i is chosen for the next assignment. This is achieved in practice by using an output layer with m neurons with a sigmoid activation function.
Dataset Generation Process The input of each training example corresponds to a partial solution x, and the output to a single variable value assignment (represented as a vector y using a one-hot encoding). The training set is constructed by repeatedly calling the randomized deconstruction procedure Algorithm 1 on an initial set of full solutions (referred to as solution pool). Each call generates a number of examples that are used to populate a dataset. At the end of the process we discard multiple copies of identical examples. Two
D = ; while kxk1 > 0 do
Let y = 0 # zero vector Select a random index i s.t. xi = 1 Set xi = 0, set yi = 1
Add the pair hx; yi to D return D examples may have the same input, but different output, since a single partial assignment may have multiple viable completions.
Unlike [
Training and Knowledge Injection The basic training for the NN
is the same as for neural classifiers. Since the network output can
be assimilated to a class, we process the network output through a
softmax operator, and then we use as a loss function the
categorical crossentropy H. Additionally, we inject domain knowledge at
training time via an approach that combines ideas of Semantic Based
Regularization (SBR) and Constraint Programming (CP, [
In CP, constraints are associated to algorithms called propagators that can identify provably infeasible values in the domain of the variables. Propagators are generally incomplete, i.e. there is no guarantee they will find all infeasible values. Given a constraint (or a collection of constraints) C, here we will treat its propagator as a multivariate function such that Cj (x) = 1 iff assignment zj = vj has not been marked as infeasible by the propagator, while Cj (x) = 0 otherwise. We then augment the loss function with a SBR inspired term that discourages provably infeasible pairs, and encourages the remaining ones. Given an example hx; yi, we have:
Lsbr (x) =
m 1
X (Cj (x)
j=0
fj (x))2
i.e. increasing the output of a neuron corresponding to a provably
infeasible pair incurs a penalty that grows with the square of fj (x);
increasing the output for the remaining pairs incurs a penalty that
grows with the square of 1 fj (x). Our full loss is hence given by:
where Z is the partition function and the scalar controls the balance
between the crossentropy term H and the SBR term. The method can
be applied for all known propagators with discrete variables. With
some adaptations, it can be made to work for important classes of
numerical propagators (e.g. those that enforce Bound Consistency
[
Since propagators are incomplete and we are rewarding assignments not marked as infeasible, there is a chance that our SBR term injects incorrect information in the model. This reward mechanism is however crucial to ensure a non-negligible gradient at training time: the incorrect information is balanced by the presence of the crossentropy term, which encourages assignments that are guaranteed feasible (since they originate from full problem solutions). (2) (3)
Evaluation and Knowledge Injection We evaluate the approach via a specialized procedure, relying on a randomized solution function for PLS instances. This has signature SOLVE(x, C, h), where x is the starting partial assignment, C is the considered (sub)set of problem constraints, and h is a probability estimator for variablevalue pairs (e.g. our trained NN). The function is implemented via the Google or-tools constraint solver, and is based on Depth First Search: at each search node, the solver applies constraint propagation to prune some infeasible values, it chooses for branching the first unassigned variable in a static order, then assigns a value chosen at random with probabilities proportional to h(x0), where x0 is the current state of assignments. The SOLVE function returns either a solution, or ? in case of infeasibility.
Our evaluation method tests the ability of the NN to identify
individual assignments that are globally feasible, i.e. that can be extended
into full solutions. This is done via Algorithm 2, which 1) starts from
a given partial solution; 2) relies on a constraint propagator C to
discard some of the provably infeasible assignments; 3) uses the NN to
make a (deterministic) single assignment; 4) attempts to complete it
into a full solution (taking into account all problem constraints, i.e.
Cpls ). Replacing the NN with a uniform probability estimator allows
to obtain a baseline. We repeat the process on all partial solutions
from a test set, and collect statistics. This approach is identical to one
of those in [
J = arg maxfhj (x) j Cj (x) = 1g Pick j uniformly at random from J Set xj = 1 if SOLVE(x, Cpls , hrnd ) 6= ? then
return 1 else return 0 # Most likely assignments # Globally feasible # Globally infeasible
Unlike in typical Machine Learning evaluations, we do not measure the (extremely low) network accuracy: in fact, the accuracy metric in our case is tied to the network ability to replicate the same sequence of assignments observed at training time, which has almost no practical value. 4
In this section we discuss our experimental analysis, which is designed around some key questions of both scientific and practical import. We focus on the following aspects: Q1: Does injecting knowledge at training time improve the network ability to identify feasible assignments? Q2: What is the effect of injecting domain knowledge after, rather than during, training? Q3: What is the effect of adjusting the amount of available empirical knowledge? Taking advantage of our controlled use case, we present a series of experiments that investigate such research directions. Details about the rationale and the setup of each experiment are reported in dedicated sections, but some common configuration can be immediately described.
We focus on 10 10 PLS instances, resulting in input and output vectors with 1; 000 elements. We use a feed-forward, fully-connected Neural Network with three hidden layers, each with 512 units having ReLU activation function. This setup is considerably simpler than the one used in the approach we chose as our baseline, but manages to reach very similar results. We employ the Adam optimizer from Keras-TensorFlow2.0, with default parameters. The number of training epochs and batch size depends on the experiment. 4.1
We start with an experiment designed to address Question 1, i.e. whether injecting domain knowledge at training time may help the NN in the identification of feasible assignments. This is practically motivated by situations in which a domain expert has only partial information about the problem structure, but a pool of historical solutions is available.
For this experiment, the training set for the network is generated using the deconstruction approach from Section 3, starting from a set of 10,000 PLS solutions. Each solution is then deconstructed exactly once, yielding a training set of 730,000 examples, 25% of which are then removed to form a separate test set. We use mini-batches of 50,000 examples and we stop training after 1000 epochs.
We compare four approaches: a random approach (referred to as RND), which treats all possible variable-value pairs as equally likely; a model-agnostic neural network (referred to as AGN); a network trained with knowledge about row constraints (referred to as ROWS); a network trained with knowledge about row and column constraints (referred to as FULL).
The RND approach lacks even the basic knowledge that a variable cannot be assigned twice, since this is not enforced by our input/output encoding. The same holds for AGN, which can however infer such constraint from data. Conversely, in ROWS we use our SBR-inspired method (and a Forward Checking propagator) to inject knowledge that both assigning a variable twice and assigning a value twice on the same row is forbidden. For the FULL approach we do the same, applying the Forward Checking propagator also to column constraints (i.e. no value can appear twice on the same column). Due to the use of an incomplete propagator, both ROW and FULL make use of incomplete knowledge. We have empirical determined that = 1 for FULL and = 0:01 for ROW works reasonably well.
We evaluate the resulting approaches via the FEASTEST procedure, using the (separated) test set as X, the trained networks (or the uniformly random estimator) as h, and an empty set of constraints (i.e. no propagation at test time). We then produce “feasibility plots” that report on the x-axis the number of assigned variables (filled cells) in the considered partial solutions and on the y-axis the ratio of suggested assignments that are globally feasible.
The results of the evaluation are shown in Figure 1. Without propagating any constraint at evaluation time, a purely random choice is extremely unlikely to result in globally feasible assignments: this is expected and only serves as a pessimistic baseline. The AGN approach, relying exclusively on empirical knowledge, behaves considerably better, with high feasibility ratios for almost empty and almost full squares, and a noticeable drop when 60% of the square is filled. The trend is a common feature for many of the approaches, and may be connected a known phase transition in the complexity of this combinatorial problem. Injecting domain knowledge at training time improves the feasibility ratio by a noticeable margin: a half of the improvement is observed when moving from AGN to ROW, suggesting that even partial knowledge about the problem structure could prove very useful. 4.2
Our second experiment addresses Question 2, regarding the effect of knowledge injection at test time. This topic relates to scenarios where the expert-supplied information can be incorporated in a solution method (e.g. as a constraint in a declarative model). While not always viable, this situation is frequent enough to deserve a dedicated analysis.
For this experiment, we rely on the same training and test set as in Section 4.1, and compare the same approaches. As a main difference, we take into account some or all the problem constraints at evaluation time, by passing a non-empty set C of propagators to the FEASTEST procedure. Also at test time the constraints are taken into account by means of an incomplete propagator (Forward Checking), and hence all approaches rely on incomplete knowledge.
The results of this evaluation are presented in Figure 2 (for row constraints propagation at test time) and Figure 3 (for all problem constraints). The RND results in this case are representative of the behavior (at each search node) of a Constraint Programming solver having access to either only row constraints or the full problem definition: since CP is known to work very well on the PLS, it is therefore expected that the performance of the random approach is significantly boosted by knowledge injection at test time.
All approaches relying either on purely (AGN) or partially (ROWS and FULL) on empirical knowledge gain almost no benefit from injecting constraints at evaluation time, though they still perform noticeably better than RND. On one hand, these diminishing returns should be taken into account when taking into account constraints during solution generation is viable. On the other hand, the fact that all knowledge-driven approaches are not helped by constraint propagation suggests that their advantage comes from information about global feasibility, which they can access from the empirical data. 4.3
Next, we proceed to tackle Question 3, by acting on the training set generation process. In classical Machine Learning approaches, the amount of available information is usually measured via the training set size: this is a reasonable approach, since the number of training examples has a strong impact on the ability of a ML method to learn and generalize.
We performed experiments to probe the effect of the training set size on the performance of the data-driven approaches. Figure 4 and Figure 5 report results for training sets with respectively 300,000 and 50,000 examples. Knowledge injection at training time has in this case a dramatic effect: while the AGN approach is very sensitive to the available number of examples, the FULL one has only a minor drop in performance when moving from 730,000 examples to 50,000 examples. This confirms previous experiences with techniques such as Semantic Based Regularization, although the effect in our case is much more pronounced: the gap is likely due to the fact that, while our cross-entropy term in the loss function provides information about a single (globally) feasible assignment, the SBR terms provides information about a large number of (locally) feasible assignments.
In our setup, we have also the possibility to apply the deconstruction process multiple times, so that the number of different examples that can be obtained from a single solution grows with the number of possible permutations of the variable indices (i.e. O(n2!) for the PLS). Such observation opens up the possibility to generate large training sets from a very small number of starting solutions: this is scientifically interesting, since the “actual” empirical information depends on how many solutions are available; this is also very useful in practice, since in many practical applications only a relatively small number of historical solutions exists.
The results of this evaluation are shown in Figure 6 and Figure 7 for solution pools having respectively 1,000 and 100 elements. In both cases the size of the generated training set is comparable to the original, i.e. around 700,000 examples: despite this fact, there is a very significant gap in performance between the AGN approach and FULL. This is likely due once again to the richer information made accessible via the combined use of propagators and our SBR-inspired loss.
From a practical point of view it seems that, as long as enough problem knowledge is available, it is possible to train data-driven methods with very high feasibility ratio, starting from very small pools of historical solutions. It may be argued that if extensive problem knowledge is available, one may use a more traditional solution approach (e.g. Constraint Programming or Mathematical Programming): even in such a case, however, a (partially) data-driven approach should have a higher chance to preserve implicit properties (e.g. user preferences) that make the historical solutions desirable. We considered injecting domain knowledge in Deep Neural Networks to bridge the gap between expert-designed models and datadriven approaches for constrained problems. We chose the PLS as a case study, and extended an existing NN approach to enable knowledge injection. We performed controlled experiments to investigate three main scientific questions, drawing the following conclusions: Q1: Injecting domain knowledge at training time improves the ability of the NN approach to identify feasible assignments. Data driven methods behave significantly better than a naive random baseline.
Q2: Using constraint propagation to filter out some infeasible assignments at test time improves dramatically the behavior of random selection; data-driven methods receive almost no benefit, but they still perform best. This suggests that data-driven methods can infer information about global feasibility from empirical data. Q3: A pure data-driven approach is very sensitive to the available empirical information. Injecting knowledge at training time improves robustness: if both row and column constraints are considered, a limited performance drop is observed with as few as 100 historical solutions.
Our analysis required the development of a general, SBR-inspired, method to turn any constraint propagator into a source of trainingtime information. Nowadays, there is an increasing need for AI systems that are more human-centered and in several applications the agent is required to take into account security and fairness constraints during the decision process. One way to reach this goal can be the adoption of a successful hybrid approach that combines data-driven methods and Constraint Programming. Due to the results achieved with this work, together with our conclusions, this paper makes a significant step toward the practical applicability of data-driven approaches for constraint problems and also towards the developing of more human-centered AI systems.
Many open questions remain: an experimentation with different problem types and scales is needed to make sure that our results hold in general. Embedding the NN in an actual search process (with or without propagation) will provide more insight into the global behavior of the data-driven methods; finally, when applying propagation at training time is viable, it is desirable to adjust training so that it complements, rather than replicate, the effect of propagation.
This research has been partially funded by the H2020 AI4EU project, grant agreement 825619.