Methods for taking into account external knowledge in Machine Learning models have the potential to address outstanding issues in data-driven AI methods, such as improving safety and fairness, and can simplify training in the presence of scarce data. We propose a simple, but effective, method for injecting constraints at training time in supervised learning, based on decomposition and bi-level optimization: a master step is in charge of enforcing the constraints, while a learner step takes care of training the model. The process leads to approximate constraint satisfaction. The method is applicable to any ML approach for which the concept of label (or target) is well defined (most regression and classification scenarios), and allows to reuse existing training algorithms with no modifications. We require no assumption on the constraints, although their properties affect the shape and complexity of the master problem. Convergence guarantees are hard to provide, but we found that the approach performs well on ML tasks with fairness constraints and on classical datasets with synthetic constraints.
Techniques to deal with constraints in Machine Learning (ML) have the potential to address outstanding issues in data-driven AI methods. Constraints representing (e.g.) physical laws can be employed to improve generalization; constraints may encode negative patterns (e.g. excluded classes) and relational information (e.g. involving multiple examples); constraints can ensure the satisfaction of desired properties, such as fairness, safety, or lawfulness; they can even be used to extract symbolic information from data.
Such techniques can highly improve the learning process in terms of versatility and control. As a consequence, our work constitutes a step forward in the direction of a more human-oriented AI, as it is general and allows for the realization of learning models that satisfy specific user requirements. This is a fundamental and essential behaviour in contexts where there exist human-specific constraints, which the trained AI model has to acknowledge. The present paper aims at enlarging the pool of tools that can be used to inject an AI model with external knowledge, a field that is rapidly expanding thanks to its many potential practical applications.
To the best of the authors knowledge, the vast majority of approaches for taking into account external knowledge in ML make Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). assumptions that restrict the type of constraints (e.g. differentiability, no relational information), the type of models (e.g. only Decision Trees, only differentiable approaches), and often require modifications in the employed training algorithms (e.g. specialized loss terms).
We propose a decomposition-based method, referred to as Moving Targets, to augment supervised learning with constraints. A master step “teaches” constraint satisfaction to a learning algorithm by iteratively adjusting the sample labels. The master and learner have no direct knowledge of each other, meaning that: 1) any ML method can be used for the learner, with no modifications; 2) the master can be defined via techniques such as Mathematical or Constraint Programming, to support discrete values or non-differentiable constraints. Our method is also well suited to deal with relational constraints over large populations (e.g. fairness indicators). Moving Targets subsumes the few existing techniques – such as the one by [13] – capable of offering the same degree of versatility.
When constraints conflict with the data, the approach prioritizes constraint satisfaction over accuracy. For this reason, it is not well suited to deal with fuzzy information. Moreover, due to our open setting, it is hard to determine convergence properties. Despite this, we found that the approach performs well (compared to state of the art methods) on classification and regression tasks with fairness constraints, and on classification problems with balance constraints.
Due to its combination of simplicity, generality, and the observed empirical performance, Moving Targets can represent a valuable addition to the arsenal of techniques for dealing with constraints in Machine Learning. The paper is organized as follows: in Section 2 we briefly survey related works on the integration of constraints in ML; in Section 3 we present our method and in Section 4 our empirical evaluation. Concluding remarks are in Section 5. 2
Here we provide an overview of representative approaches for integrating constraints in ML, and we discuss their differences with our method.
Most approaches in the literature build over just a few key ideas. One of them is using the constraints to adjust the output of a trained ML model. This is done in DeepProbLog [20], where Neural Networks with probabilistic output (mostly classifiers) are treated as predicates. [25] presents a Neural Theorem Prover using differentiable predicates and the Prolog backward chaining algorithm. The original Markov Logic Networks [24] rely instead on Markov Fields defined over First Order Logic formulas. As a drawback, with these approaches the constraints have no effect on the model parameters, which complicates the analysis of feature importances. Moreover, dealing with relational constraints (e.g. fairness) requires access at prediction time either to a representative population or to its distribution [12, 11].
A second group of approaches operate by using constraint-based expressions as regularization terms at training time. In Semantic Based Regularization [7] constraints are expressed as fuzzy logical formulas over differentiable predicates. Logic Tensor Networks [26] focus on Neural Networks and replace the entire loss function with a fuzzy formula. Differentiable Reasoning [27] uses in a similar fashion relational background knowledge to benefit from unlabeled data. In the context of fairness constraints, this approach has been taken in [1, 10, 28, 5, 15]. Methods in this class account for the constraints by adjusting the model parameters, and can therefore be used to analyze feature importance. They can deal with relational constraints without additional examples at prediction time; however, they ideally require simultaneous access at training time to all the examples linked by relational constraints (which can be problematic when using mini-batches). They often require properties on the constraints (e.g. differentiability), which may force approximations; they may also be susceptible to numerical issues.
A third idea consists in enforcing constraint satisfaction in the data via a pre-processing step. This is proposed in the context of fairness constraints by [13, 14, 18]. The approach enables the use of standard ML methods with no modification, and can deal with relational constraints on large sets of examples. As a main drawback, bias in the model or the training algorithm may prevent getting close to the pre-processed labels.
Multiple ideas can be combined: domain knowledge has been introduced in differentiable Machine Learning (e.g. Deep Networks) by designing their structure, rather than the loss function: examples include Deep Structured Models in [16] and [19]. These approaches can use constraints to support both training and inference.
Though less related to our approach, constraints can be used to extract symbolic knowledge from data, for example by allowing the training algorithm to adjusting the regularizer weights. This approach is considered (e.g.) in [17, 21, 6].
Our approach is closely related to the idea of enforcing constraints by altering the data, and shares the same advantages (versatility, support for relational constraints and feature importance analysis, no differentiability assumptions). We counter the main drawbacks mentioned above by using an iterative algorithm rather than a single pre-processing step. In this section we present our method, discuss its properties, draw connections with related algorithms and provide some convergence considerations.
Algorithm 1 MOVING TARGETS input label vector y , scalar parameters ; ; n y1 = l(y ) # pretraining for k = 1::n do if yk 2= C then
zk = m (yk) else
zk = m (yk) end if yk+1 = l(zk) # learner step # infeasible master step # feasible master step end for The Algorithm Our goal is to adjust the parameters of a ML model so as to minimize a loss function with clearly defined labels, under a set of generic constraints. We acknowledge that any constrained learning problem must trade prediction mistakes for a better level of constraint satisfaction, and we attempt to control this process by carefully selecting which mistakes should be made. This is similar to [13, 14, 18], but: 1) we consider generic constraints rather than focusing on fairness; and 2) we rely on an iterative process (which alternates “master” and “learner” steps) to improve the results.
Let L(y; y ) be the loss function, where y is the prediction vector and y is the label vector. We make the (non restrictive) assumption that the loss is a pre-metric – i.e. L(y; y ) 0 and L(y; y ) = 0 iff y = y . Examples of how to treat common loss functions can be found in Table 1.
We then want to solve, in an exact or approximate fashion, the following constrained optimization problem:
arg minfL(y; y ) j y = f (X; ); y 2 Cg where f is the ML model and its parameter vector. With some abuse of notation we refer as f (X; ) to the vector of predictions for the examples in the training set X. Since the model input at training time is known, constraints can be represented as a feasible set C for the sole predictions y.
The problem can be rewritten without loss of generality by introducing a second set B corresponding to the ML model bias. This leads to a formulation in pure label space: arg minfL(y; y ) j y 2 B \ Cg
y where B = fy j 9 ; y = f (X; )g.
The Moving Targets method is described in Algorithm 1, and starts with a learner step w.r.t. the original label vector y (pretraining). Each learner step, given a label vector as input, solves approximately or exactly the problem: l (z) = arg minfL(y; z) j y 2 Bg
y Note that this is a traditional unconstrained learning problem, since B is just the model/algorithm bias. The result of the first learner step gives an initial vector of predictions y1.
Next comes a master step to adjust the label vector: this can take two forms, depending on the current predictions. In case of an infeasibility, i.e. yk 2= C, we solve: m (y) = arg min z
1 L(z; y ) +
L(z; y) j z 2 C
Intuitively, we try to find a feasible label vector z that is close (in
terms of loss function value) to both the original labels y and the
(
We then make a learner step trying to reach the adjusted labels; the new predictions will be adjusted at the next iteration and so on. In case of convergence, the predictions yk and the adjusted labels zk become stationary (but not necessarily identical). An example run, for a Mean Squared Error loss and convex constraints and bias, is in Figure 1.
Properties The learner is not directly affected by the constraints, thus enabling the use of arbitrary ML approaches. The master problems do not depend on the ML model, often leading to clean structures that are easier to solve. Since we make no explicit use of mini-batches, we can deal well with relational constraints on large groups (e.g. fairness). The master step can be addressed via any suitable solver, so that discrete variables and non-differentiable constraints can be tackled via (e.g.) Mathematical Programming, Constraint Programming, or SAT Modulo Theories. Depending on the constraints, the loss functions, and the label space (e.g. numeric vs discrete) the master problems may be NP-hard. Even in this case, their clean structure may allow for exact solutions for datasets of practical size. Moreover, for separable loss functions (e.g. all those from Table 1), the master problems can be defined over only the constrained examples, with a possibly significant size reduction. If scalability is still a concern, the master step can be solved in an approximate fashion: this may lead to a lower accuracy and a higher level of constraint violation; however, such issues are partly inevitable, due to algorithm/model bias, and since constraint satisfaction on the training data does not necessarily transfer to unseen examples.
Analysis and Convergence Due to its open nature and minimal
assumptions, establishing the convergence of our method is hard. Here
we provide some considerations and connect the approach to existing
algorithms. We will make the simplifying assumption that the learner
problem from Equation (
We start by observing that Equation (
We therefore chose a design that is less elegant, but also less sensitive to which assumptions are valid. In particular: 1) in the m steps, we use a modification of a suboptimal BAP algorithm to find a feasible prediction vector; then 2) in m we apply a modified proximal operator to improve its distance (in terms of loss) w.r.t. the original labels y . The basis for our m step is the Alternating Projections (AP) method, discussed e.g. in [4]. The AP simply alternates projection operators on the two sets, which never generates vectors outside of the label space.
Indeed, for ! 0 our m step becomes a projection of the predictions yk on C. With this setup we recover the AP behavior, and its convergence to a feasible point for convex sets. For ! 1 we obtain, essentially, the pre-processing method from [13]: m becomes a projection of the true labels y on C, and subsequent iterations have no further effect; convergence to a feasible point is achieved only if the pre-processed labels are in B, which may not be the case (e.g. a quadratic distribution for a linear model). For reasonable values, our m step balances the distance (loss) from both the predictions y and the targets y . Convergence in this case is an open question, but especially in a non-convex or discrete setting (where multiple projections may exist) this modification helps escaping local minima and accelerate progress.
When a feasible prediction vector is obtained, our method switches to the m step; we then search for a point in C that is closer to the true labels, but also not too far from the predictions. This is related to the Proximal Gradient method, discussed e.g. in [22], but we limit the distance via a constraint rather than a squared norm, and we search in a ball rather than on a line. As in the proximal gradient, a too large search radius prevents convergence: for ! 1 the m step always returns the same adjusted labels, corresponding to the projection of y on C set. 4
Our experimentation is designed around a few main questions: 1) How does the Moving Targets method work on a variety of constraints, tasks, and datasets? 2) What is the effect of the ; parameters? 3) How does the approach scale? 4) How different is the behavior with different ML models? 5) How does the method compare with alternative approaches? We proceed to describe our setup and the experiments we performed to address such questions.
Tasks and Constraints We experiment on three case studies, covering two types of ML tasks and two types of constraints. First, we consider a classification problem augmented with a balance constraint, which forces the distribution over the classes to be approximately uniform. The loss function is given by the Hamming distance and the label space is f1::cgm. The m (y) problem is defined as a Mixed Integer Linear Program with binary variables zij such that min s.t.
1 Xm (1 m i=1 c X zij = 1 j=1 m X yij i=1 where K contains the indices of “protected features” (e.g. ethnicity, gender, etc.). Dk is the set of possible values for the k-th feature, and Xk;v is the set of examples having value v for the k-th feature. The m (y) problem can be defined via the following Mathematical Program: min 1 Xm (1 m i=1 zi;yi ) +
zi;yi )
1 Xm (1
m i=1
The summations in Equation (
Our second use case is a classification problem with realistic fairness constraints, based on the DIDI indicator from [1]:
DIDI c(X; y) = X X zij = 1 iff the adjusted class for the i-th example is j. Formally: Our third case study is a regression problem with fairness constraints, based on a specialized DIDI version from [1]:
DIDI r(X; y) = X X dkv
where Equation (
Datasets, Preparation, and General Setup We test our method
on seven datasets from the UCI Machine Learning repository [9],
namely iris (150 examples), redwine (
For each experiment, we perform a 5-fold cross validation (with a fixed seed for random reshuffling) to account for noise due to sampling and in the training process. Hence, the training set for each fold will include 80% of the data. All our experiments are run on an Intel Core i7 laptop with 16GB RAM, and we use Cplex 12.8 to solve the master problems. Our code and datasets are publicly available3.
All the datasets for the classification/balance case study are prepared by standardizing all input features (on the training folds) to have zero mean and unit variance. The iris and dota2 datasets are very balanced (the constraint is easily satisfied), while the remaining datasets are quite unbalanced. In the adult (also known as “Census Income”) dataset the target is “income” and the protected attribute is “race”. We remove the features “education” (duplicated) and “native country” and use a one-hot encoding on all categorical features. Features are normalized between 0 and 1. Our crime dataset is the “Communities and Crime Unnormalized” table. The target is “violentPerPop” and the protected feature is “race”. We remove features that are empty almost everywhere and features trivially related to the target (“murders”, “robberies”, etc.). Features are normalized between 0 and 1 and we select the top 15 ones according to the SelectKBest method of scikit-learn (excluding “race”). The protected feature is then reintroduced.
NN ( , )
Parameter tuning We know that extreme choices for and can dramatically alter the method behavior, but not what effect can be expected for more reasonable values. With this aim, we perform an investigation by running the algorithm for 15 iterations (used in all experiments), with different and values. As a ML model, we use a fully-connected, feed-forward Neural Network (NN) with two hidden layers with 32-Rectifier Linear Units. The last layer has either a SoftMax activation (for classification) or Linear (for regression). The loss function is respectively the categorical cross-entropy or the MSE. The network is trained with 100 epochs of RMSProp in Keras/Tensorflow 2.0 (default parameters and batch size 64).
The results are in Table 2. We report a score (row S, higher is better) and a level of constraint violation (row C, lower is better). The S score is the accuracy for classification and the R2 coefficient for regression. For the balance constraint, the C score is the standard deviation of the class frequencies; in the fairness case studies, we use the ratio between the DIDI of the predictions and that of the training data. Each cell reports mean and standard deviation for the 5 runs. Near feasible values are marked with a ; accuracy comparisons are fair only for similar constraint violation scores. We consider a solution as near feasible when the associated constraint score lies within one standard deviation from the imposed score.
All columns labeled with and values refer to our method with the corresponding parameters. We explore different values of (for a fixed = 1), corresponding to different ball radii in the m step; we also explore different values of , corresponding to a behavior of the m step progressively closer to that of the Alternating Projections method. The ideal case column refers to a simple projection of the true labels y on the feasible space C: this corresponds (on the training data) to the best possible accuracy that can be achieved if the constraints are fully satisfied. The ptr column reports the results of the pretraining step, as defined in algorithm 1.
Results are to be read as follows: the ideal case constitutes the upper bound to the performance of a constrained learner; it exactly matches the constraint threshold while minimizing the loss function. On the other hand, the ptr represents the constraint-agnostic behavior: it retains good performances while not necessarily satisfying the constraints. Our method lies in between the two extreme cases.
The Moving Targets algorithm can significantly improve the satisfaction of non-trivial constraints: this is evident for the (very) unbalanced datasets redwine, whitewine, and shuttle and all fairness use cases, for which feasible (or close) results are almost always obtained. Satisfying very tight constraints (e.g. in the unbalanced dataset) generally comes at a significant cost in terms of accuracy. When the constraints are less demanding, however, we often observe accuracy improvements w.r.t. the pretraining results (even substantial ones for adult and crime): this is not simply a side effect of the larger number of training epochs, since we reset the NN weights at each iteration. Rather, this seems a positive side-effect of using an iterative method to guide training (which may simplify escaping from local optima): further investigation is needed to characterize this phenomenon. Finally, reasonable parameter choices have only a mild effect on the algorithm behavior, thus simplifying its configuration. Empirically, = 1; = 0:1 seems to works well and is used for all subsequent experiments.
Scalability We next turn to investigating the method scalability: from this perspective our examples are worst cases, since they must be defined on all the training data, and in some case involve NP-hard problems. We report the average time for a master step in Figure 2. The average time for a learner step (100 epochs of our NN) is shown as a reference. At least in our experimentation, the time for a master step is always very reasonable, even for the dota2 dataset for which we solve NP-hard problems on 74,120 examples. This is mostly due to the clean structure of the m and m problems. Of course, for sufficiently large training sets, exact solutions will become impractical. Setup of Alternative Approaches Here we describe how to setup alternative approaches that will be used for comparison. Namely, we consider the regularized linear approach from [3], referred to as RLR, and a Neural Network with Semantic Based Regularization [8], referred to as SBR. Both approaches are based on the idea of introducing constraints as regularizers at training time. Hence, their loss function is in the form:
L(f (X; ); y ) + g(f (X; )) The regularization term must be differentiable. We use SBR only for the case studies with the balance constraint, which we are forced to approximate to obtain differentiability: m g(f (X; )) = max X f (X; )
j=1::c i=1 i.e. we use the sums of the NN output neurons to approximate the class counts and the maximum as a penalty; this proved superior to other attempts in preliminary tests. The L term is the categorical cross-entropy.
Our SBR approach relies on the NN model from the previous paragraphs. Since access to the network structure is needed to differentiate the regularizer, SBR works best when all the examples linked by relational constraints can be included in the same batch. When this is not viable the regularizer can be treated stochastically (via subsets of examples), at the cost of one additional approximation. We use a batch size of 2,048 as a compromise between memory usage and noise. The SBR method is trained for 1,600 epochs.
The RLR approach relies on linear models (Logistic or Linear
Regression), which are simple enough to consider large group of
examples simultaneously. We use this approach for the fairness use
cases. In the crime (regression) dataset L is the MSE and the
regularizer is simply Equation (
There is no simple recipe for choosing the value of in
Equation (
For our method, we consider the following ML models: 1) the NN from the previous section with = 1; = 0:1; 2a) a Random Forest Classifier with 50 estimators and maximum depth of 5 (used for all classification case studies); 2b) a Gradient Boosted Trees model, with 50 estimators, maximum depth 4, and a minimum threshold of samples per leaf of 5 (for the regression case study); 4a) a Logistic Regression model (for classification); 4b) a Linear Regression model (for regression). All models except the NN are implemented using scikit-learn [23]. In the table, the tree ensemble method are reported on a single column, while another column (LR) groups Logistic and Linear regression.
Our algorithm seems to work well with all the considered ML models: tree ensembles and the NN have generally better constraint satisfaction (and higher accuracy for constraint satisfaction) than linear models, thanks to their larger variance. The preprocessing approach is effective when constraints are easy to satisfy (iris and dota2) and on all the fairness case studies, though less so on the remaining datasets. All Moving Targets approaches tend to perform better and more reliably than RLR and SBR. The case of RLR and LR is especially interesting, as they differ only for the mechanism used to enforce constraint satisfaction. In principle we can expect the two models to have zero gap, for the regularization term has the same formulation and the problem is convex. The gap is then due to an incomplete exploration of the space of the multiplier , since for the same multipliers value the gap is null under optimal training (which is the standard for linear regression). The example emphasizes a practical problem that often arises when dealing with regularized loss function: the value of the multiplier has to be thoroughly calibrated by hand, while Moving Targets allows to directly define the desired constraint threshold and obtain the best solution associated to it. Generalization Since our main contribution is an optimization algorithm, we have focused so far on evaluating its performance on the training data, as it simplifies its analysis. Now that the property of our methods are clearer, we can assess the performance of the models we trained on the test data. The results of this evaluation are reported in Table 5, in the form of average ration between the scores and the level of constraint satisfaction in the test and the train data. With a few exceptions (e.g. satisfiability in iris), the models (especially the tree ensembles and LR) generalize well in terms of both accuracy and constraint satisfaction. Given the tightness of some of the original constraint and the degree to which the labels were altered, this is a remarkable result. In this paper we have introduced Moving Targets, a decomposition approach to augment a generic supervised learning algorithm with constraints, by iteratively adjusting the example labels. The method is designed to prioritize constraint satisfaction over accuracy, and proved to behave very well on a selection of tasks, constraints, and datasets. Its relative simplicity, reasonable scalability, and the ability to handle any classical ML model make it well suited for use in real world settings.
Many open questions remain: we highlighted limitations of regularization based techniques that deserve a much deeper analysis. The convergence properties of our method still need to be formally characterized (even in simpler, convex, scenarios). The method scalability should be tested on larger datasets, for which using approximate master steps will be necessary. Given the good performance of the pre-processing approach in Table 4, it may be interesting to skip the pretraining step in our method. Improvements may be possible by using specialized algorithms in specific settings: Douglas-Rachford splits could be applied in a numeric setting, or probabilistic predictions could be employed (when available) to refine the projection operators.
This research has been partially funded by the H2020 Project AI4EU, grant agreement 825619.