Deep Lattice Networks and Partial Monotonic Functions

Introduction

We propose building models with multiple layers of lattices, which we refer to as deep lattice networks (DLNs). While we hypothesize that DLNs may generally be useful, we focus on the challenge of learning flexible partially-monotonic functions, that is, models that are guaranteed monotonic with respect to a user-specified subset of the inputs. For example, if one is predicting whether to give someone else a loan, we expect and would like to constrain the prediction to be monotonically increasing with respect to the applicant’s income, if all other features are unchanged. Imposing monotonicity acts as a regularizer, improves generalization to test data, and makes the end-to-end model more interpretable, debuggable, and trustworthy.

To learn more flexible partial monotonic functions, we propose architectures that alternate three kinds of layers: linear embeddings, calibrators, and ensembles of lattices, each of which is trained discriminatively to optimize a structural risk objective and obey any given monotonicity constraints. See Fig. 2 for an example DLN with nine such layers.

Lattices are interpolated look-up tables, as shown in Fig. 1. Lattices have been shown to be an efficient nonlinear function class that can be constrained to be monotonic by adding appropriate sparse linear inequalities on the parameters , and can be trained in a standard empirical risk minimization framework . Recent work showed lattices could be jointly trained as an ensemble to learn flexible monotonic functions for an arbitrary number of inputs .

Calibrators are one-dimensional lattices, which nonlinearly transform a single input ; see Fig. 1 for an example. They have been used to pre-process inputs in two-layer models: calibrators-then-linear models , calibrators-then-lattice models , and calibrators-then-ensemble-of-lattices model . Here, we extend their use to discriminatively normalize between other layers of the deep model, as well as act as a pre-processing layer. We also find that using a calibrator for a last layer can help nonlinearly transform the outputs to better match the labels.

We first describe the proposed DLN layers in detail in Section 2. In Section 3, we review more related work in learning flexible partial monotonic functions. We provide theoretical results characterizing the flexibility of the DLN in Section 4, followed by details on our TensorFlow implementation and numerical optimization choices in Section 5. Experimental results demonstrate the potential on benchmark and real-world scenarios in Section 6.

Deep Lattice Network Layers

The output of the linear embedding layer is:

Note that only the first $D^{m}_{t+1}$ coordinates of $x_{t+1}$ needs to be a monotonic input to the $t+1$ layer. These two linear embedding matrices and bias vector are discriminatively trained.

Each 1D calibration function is equivalent to a sum of weighted-and-shifted Rectified Linear Units (ReLU), that is, a calibrator function $c(x[d];a,b)$ can be equivalently expressed as

However, enforcing monotonicity and boundedness constraints for the calibrator output is much simpler with the $(a,b)$ parameterization of each keypoint’s input-output values, as we discuss shortly.

For monotonic inputs, we can constrain the calibrator functions to be monotonic by constraining the calibrator parameters $b\in^{K}$ to be monotonic, by adding the linear inequality constraints

into the training objective . We also experimented with constraining all calibrators to be monotonic (even for non-monotonic inputs) for more stable/regularized training.

The ensemble of lattices layer produces $M$ outputs, one per lattice. When creating the DLN, if the $t+1$th layer is an ensemble of lattices, we randomly permute the outputs of the previous layer to be assigned to the $G_{t+1}S_{t+1}$ inputs of the ensemble. If a lattice has at least one monotonic input, then that lattice’s output is constrained to be a monotonic input to the next layer; in this way we guarantee monotonicity end-to-end for the DLN.

Partial monotonicity: The DLN is constructed to preserve an end-to-end partial monotonicity with respect to a user-specified subset of the inputs. As we described, the parameters for each component (matrix, calibrator, lattice) can be constrained to be monotonic with respect to a subset of inputs by satisfying certain linear inequality constraints . Also if a component has a monotonic input, then the output of that component is treated as a monotonic input to the following layer. Because the composition of monotonic functions is monotonic, the constructed DLN belongs to the partial monotonic function class. The arrows in Figure 2 illustrate this construction, i,e,, how the $t$th layer output becomes a monotonic input to $t+1$th layer.

We detail the hyperparameters for each type of DLN layer in Table 1. Some of these hyperparameters constrain each other since the number of outputs from each layer must be equal to the number of inputs to the next layer; for example, if you have a linear embedding layer with $D_{t+1}=1000$ outputs, then there are $1000$ inputs to the next layer, and if that next layer is a lattice ensemble, its hyperparameters must obey $G_{t}\times S_{t}=1000$.

Related Work

Prior to this work, the state-of-the-art in learning expressive partial monotonic functions for $D>16$ inputs was 2-layer networks consisting of a layer of calibrators followed by an ensemble of lattices , with parameters appropriately constrained for monotonicity, which built on earlier work of Gupta et al. that constructed only a single calibrated lattice, and was restricted to around $D\leq 16$ inputs due to the $O(2^{S})$ number of parameters for each lattice. This work differs in three key regards.

First, we alternate layers to form a deeper, and hence potentially more flexible, network. Second, a key question addressed in Canini et al. is how to decide which features should be put together in each lattice in their ensemble. They found that random assignment worked well, but required large ensembles. Smaller (and hence faster) models with the same accuracy could be trained by using a heuristic pre-processing step they proposed (crystals) to identify which features interact nonlinearly. This pre-processing step requires training a lattice for each pair of inputs to judge that pair’s strength of interaction, which scales as $O(D^{2})$, and we found it can be a large fraction of overall training time for $D>50$.

We solve the problem of determining which inputs should interact in each lattice by using a linear embedding layer before an ensemble of lattices layer to discriminatively and adaptively learn during training how to map the features to the first ensemble-layer lattices’ inputs. This strategy also means each input to a lattice can be a linear combination of the features, which is a second key difference to that prior work .

The third difference is that in previous work , the calibrator keypoint values were fixed a priori based on the quantiles of the features, which is challenging to do for the calibration layers mid-DLN, because the quantiles of their inputs are evolving during training. Instead, we fix the keypoint values uniformly over the bounded calibrator domain.

Learning monotonic single-layer neural nets by constraining the neural net weights to be positive dates back to Archer and Wang in 1993 , and that basic idea has been re-visited by others , but with some negative results about the obtainable flexibility even with multiple hidden layers . Sill proposed a three-layer monotonic network that used an early form of monotonic linear embedding and max-and-min-pooling. Daniels and Velikova extended Sill’s result to learn a partial monotonic function by combining min-max-pooling, also known as adaptive logic networks , with partial monotonic linear embedding, and show that their proposed architecture is an universal approximator for partial monotone functions. None of these prior neural networks were demonstrated on problems with more than $D=10$ features, nor trained on more than a few thousand examples. For our experiments we implemented a positive neural network and a min-max-pooling network with TensorFlow.

Function Class of Deep Lattice Networks

We offer some results and hypotheses about the function class of deep lattice networks, depending on whether the lattices are interpolated with multilinear interpolation (which forms multilinear polynomials), or simplex interpolation (which forms locally linear surfaces).

We show that a deep lattice network made up only of lattices (without intervening layers of calibrators or linear embeddings) is equivalent to a single lattice defined on the $D$ input features if multilinear interpolation is used. It is easy to construct counter-examples showing that this result does not hold for simplex-interpolated lattices.

Suppose that a lattice has $i$ inputs that can each be expressed in the form $\theta_{i}^{T}\psi(x[s_{i}])$, where the $s_{i}$ are mutually disjoint and $\psi$ represents multilinear interpolation weights. Then the output can be expressed in the form $\hat{\theta}^{T}\hat{\psi}(x[\cup s_{i}])$. That is, the lattice preserves the functional form of its inputs, changing only the values of the coefficients $\theta$ and the linear interpolation weights $\psi$.

Each input $i$ of the lattice can be expressed in the following form:

This is a multilinear polynomial. Analogously, the output can be expressed in the following form:

Note the product in the expression: $f_{i}$ and $1-f_{i}$ are both multilinear polynomials, but within each term of the product, only one is present, since one of the two has exponent and the other has exponent $1$. Furthermore, since each $f_{i}$ is a function of a different subset of $x$, we conclude that the entire product is a multilinear polynomial. Since the sum of multilinear polynomials is still a multilinear polynomial, we conclude that $F$ is a multilinear polynomial. Any multilinear polynomial on $k$ variables can be converted to a $k$-dimensional multilinear lookup table, which concludes the proof. ∎

Theorem 1 can be applied inductively to every layer of a cascaded lookup table down to the final output $F(x)$. Thus, we can show that a cascaded lookup table using multilinear interpolation is equivalent to a single multilinear lattice defined on all $D$ features.

2 Universal approximation of partial monotone functions

Theorem 4.1 in states that partial monotone linear embedding with min and max pooling can approximate any partial monotone functions on the hypercube. We show in the next lemma that simplex-interpolated lattices can represent min or max pooling. Thus we can use two cascaded simplex interpolated lattice layers with a linear embedding layer to approximate any partial monotone function on the hypercube.

From , $\psi_{simplex}(x)^{T}\theta=\thetax[\pi]+\cdots+\theta[2^{n}]x[\pi[n]]$, where $\pi$ is the sorted order such that $x[\pi]\geq\cdots\geq x[\pi[n]]$, so by definition, it is easy to see the above result. ∎

3 Locally linear functions

If simplex interpolation (aka the Lovász extension) is used, the deep lattice network produces a locally linear function, because each layer is locally linear, and compositions of locally linear functions are locally linear. Note that a $D$ input lattice interpolated with simplex interpolation has $D!$ linear pieces . We hypothesize that if one cascades an ensemble of $D$ lattices into a lattice, that the number of locally linear pieces is on the order $O((D!)!)$.

Numerical Optimization Details for the DLN

Operators: We implemented 1D calibrator and multilinear interpolation over a lattice as new C++ operators in TensorFlow and express each layer as a computational graph node using these new and existing TensorFlow operators. We will make the code publicly available via the TensorFlow open source project. We use the ADAM optimizer and batched stochastic gradients to update model parameters. After each gradient update, we project parameters to satisfy their monotonicity constraints. The linear embedding layer’s constraints are element-wise non-negativity constraints, so its projection clips each negative component to zero. Projection for each calibrator is isotonic regression with total ordering, which we implement with the pool-adjacent-violator algorithm for each calibrator. Projection for each lattice is isotonic regression with partial ordering, resulting in $O(S2^{S})$ linear constraints for each lattice . We solved it with consensus optimization and alternating direction method of multipliers to parallelize the projection computations with a convergence criterion of $10^{-7}$.

We initialize each lattice’s parameters to be a linear function spanning $$, and add IID Gaussian noise$\mathcal{N}(0,\frac{1}{n}^{2})$to each parameter. We initialize each calibrator to be a linear function that maps$[x_{\min},x_{\max}]$to$$ (and did not add any noise).

Experiments

We present results on the same benchmark dataset (Adult) with the same monotonic features as in Canini et al. , and for three problems from a large internet services company where the monotonicity constraints were specified by product groups. For each experiment, every model considered is trained with monotonicity guarantees on the same set of inputs. See Table 2 for a summary of the datasets.

For classification problems, we used logistic loss, and for the regression, we used squared error. For each problem, we used a validation set to optimize the hyperparameters for each model architecture: the learning rate, the number of training steps, etc. For an ensemble of lattices, we tune the number of lattices, $G$, and number of inputs to each lattice, $S$. All calibrators for all models used a fixed number of 100 keypoints, and set $$ as an input range.

For crystals we validated the number of ensembles, $G$, and number of inputs to each lattice, $S$, as well as ADAM stepsize and number of loops. For min-max net , we validated the number of groups, $G$, and dimension of each group $S$, as well as ADAM stepsize and number of loops.

For datasets where all features are monotonic, we also train a deep neural network with a non-negative weight matrix and ReLU as an activation unit with a final fully connected layer with non-negative weight matrix, which we call monotonic DNN. We tune the depth of hidden layers, $G$, and the activation units in each layer $S$.

All the result table contains an additional column to denote model parameters; $2\times 5D$ means $G=2$ and $S=5$.

For this real-world problem from a large internet services company, the problem is to classify the user intent. We report results the best validated model for different DLN architectures, such as Calibration(Cal)-Linear(Lin)-Calibration(Cal)-Ensemble of Lattices(EnsLat)-Calibration(Cal)-Linear(Lin).

The test set is not IID with the train and validation set in that the train and validation set are collected from the U.S., and the test set is collected from 20 other countries, and as a result we see the notable difference between the validation and the test accuracy. This experiment is set-up to test generalization ability.

The results are summarized in Table 3, sorted by the validation accuracy. Two of the DLN architectures outperform crystals and min-max net in terms of test accuracy.

2 Adult Benchmark Dataset (Classification)

We compare accuracy on the benchmark Adult dataset , where a model predicts whether a person’s income is greater than or equal to $50,000, or not. Following Canini et al. , we set the function to be monotonically increasing in capital-gain, weekly hours of work and education level, and the gender wage gap. We used one-hot encoding for the other categorical features, for 90 features in total. We randomly split the usual train set 80-20 and trained over the$80\%$, and validated over the$20\%$.

For DLN architecture, we used Cal-Lin-Cal-EnsLat-Cal-Lin layer. Results in Table 4 show the DLN provides better accuracy than the min-max network or crystals.

3 Rater Score Prediction Case Study (Regression)

In this task, we train a model to predict a rater score for a candidate result, where each rater score is averaged over 1-5 raters, and takes on 5-25 possible values. All 10 monotonic features are required to be monotonic. Results in Table 5 show DLN has slightly better validation and test MSE than all other models.

4 Usefulness Case Study (Classifier)

In this task, we train a model to predict whether a candidate result contains useful information or not. All 9 features are required to be monotonic, and we use Cal-Lin-Cal-EnsLat-Cal-Lin DLN architecture. Table 6 shows the DLN has better validation and test accuracy than other models.

Conclusions

In this paper, we combined three types of layers, (1) calibrators, (2) linear embeddings, and (3) lattices, to produce a new class of models that combines the flexibility of deep networks with the regularization, interpretability and debuggability advantages that come with being able to impose monotonicity constraints on some inputs.

References