PaperlayerView exact revision on arXiv

Source-linked AI summary

Monotonic Calibrated Interpolated Look-Up Tables

Maya Gupta, Andrew Cotter, Jan Pfeifer, Konstantin Voevodski, Kevin Canini, Alexander Mangylov, Wojtek Moczydlowski, Alex van Esbroeck

arXiv:1505.06378v3cs.LG

TL;DR

Practical machine-learning systems need functions that are fast, interpretable, and reliably monotonic, but noisy data can violate such domain expectations. The paper learns calibrated interpolated look-up tables with linear monotonicity constraints and reports state-of-the-art performance on large real-world monotonic problems. Its approach improves transparency and supports practical preprocessing, though model size limits single-machine use as feature count grows.

  • Problem

    Practical applications need fast, interpretable functions with guaranteed monotonicity, while noisy samples may violate expected feature-response relationships.

  • Method

    The paper learns calibrated interpolated look-up tables by combining lattice regression with linear inequality constraints, feature calibrations, and practical training strategies.

  • Results

    The method achieves statistically significant state-of-the-art performance on the largest training sets and feature counts published for monotonic methods.

  • Takeaways & Limitations

    Monotonic lattice regression provides flexible, transparent functions for low-dimensional classification, ranking, and regression while addressing evaluation speed, preprocessing, missing data, and categorical features.

  • Takeaways & Limitations

    The exponential model size limits single-machine models to not much more than D = 20 features, motivating sparsification as an open question.

Abstract

from arXiv · show

Real-world machine learning applications may require functions that are fast-to-evaluate and interpretable. In particular, guaranteed monotonicity of the learned function can be critical to user trust. We propose meeting these goals for low-dimensional machine learning problems by learning flexible, monotonic functions using calibrated interpolated look-up tables. We extend the structural risk minimization framework of lattice regression to train monotonic look-up tables by solving a convex problem with appropriate linear inequality constraints. In addition, we propose jointly learning interpretable calibrations of each feature to normalize continuous features and handle categorical or missing data, at the cost of making the objective non-convex. We address large-scale learning through parallelization, mini-batching, and propose random sampling of additive regularizer terms. Case studies with real-world problems with five to sixteen features and thousands to millions of training samples demonstrate the proposed monotonic functions can achieve state-of-the-art accuracy on practical problems while providing greater transparency to users.

1. Introduction

The paper targets practical machine-learning functions that are fast, interpretable, and guaranteed monotonic, using calibrated interpolated look-up tables. It extends lattice regression to larger real-world problems while preserving transparency and competitive accuracy.

  • Motivation: Monotonicity matters because noisy training data can violate domain expectations, such as used-car value decreasing as mileage increases.The paper presents guaranteed monotonic behavior as an interpretability and user-trust requirement.
  • Contribution: The paper learns monotonic, efficient, and flexible functions by constraining and calibrating interpolated look-up tables.The approach is framed within structural risk minimization and is designed for low-dimensional machine-learning problems.
  • Interpretability: Look-up-table parameters are function values at regular grid inputs, so users can inspect individual parameters and their effects.Interpolation produces values between these interpretable grid parameters.
  • Efficiency: A 20-feature look-up table evaluates in 2 microseconds on a standard CPU using simplex interpolation.The practical feature limit is driven more by the 2^D parameter count than by interpolation cost.
  • Empirical scope: Case studies report similar accuracy to a random forest and show monotonic lattice regression across varied applications.The experiments use real-world problems with more features and data than earlier monotonic-method demonstrations.

2. Related Work

Prior work pursues interpretability through understandable function classes and simpler models, while monotonic learning uses constraints, post-processing, penalties, or relabeling. The paper positions lattice interpolation as a flexible parameterization that makes complete monotonicity constraints easier to enforce.

  • Interpretability: Interpretability research combines interpretable function classes with preferences for simpler functions, including sparse or structured representations.Look-up-table parameters are semantically meaningful because they correspond to regularly spaced function outputs.
  • Interpretability trade-off: When monotonicity is a good prior model, the case studies report no accuracy trade-off from using it as a simplicity constraint.The paper contrasts this with possible interpretability–accuracy trade-offs from unsuitable simpler structures.
  • Monotonic learning: Monotonic-learning methods constrain models, post-process violations, penalize violations, or relabel samples before training.These strategies span linear, neural, tree, and other model families.
  • Modeling trade-offs: Linear and polynomial models can be constrained for monotonicity but may lack flexibility, while nonlinear derivative checks can be computationally difficult.Positive polynomial coefficients are sufficient but not necessary for monotonicity.
  • Lattice parameterization: Lattice interpolation makes the complete set of monotonic functions easier to check and enforce than the equivalent polynomial parameterization.The same two-dimensional functions can be represented as interpolated 2 × 2 lattices.

3. Review of Lattice Regression

Lattice regression represents low-dimensional functions with regularly spaced parameters and multilinear interpolation, making predictions linear in interpolation weights. It learns those parameters by minimizing empirical loss plus regularization, typically through a convex objective.

  • Lattice representation: A lattice is a regular grid of parameters whose values are interpolated to evaluate the function at any input.For machine-learning problems, two vertices per feature are a stated default, while image processing may require larger lattices.
  • Interpolation: The prediction is f(x) = θTφ(x), where θ contains lattice values and φ(x) contains interpolation weights.The weights form a simplex-valued representation over the vertices of the cell containing x.
  • Interpolation: Multilinear interpolation combines cell-vertex parameters with weights determined by the input coordinates, producing a piecewise-polynomial spline.The function is continuous at cell boundaries but generally not differentiable there.
  • Design trade-off: Higher-order basis functions can improve smoothness and accuracy but weaken the localized interpretability of lattice parameters.The paper therefore emphasizes linear interpolation for interpretable low-dimensional functions.
  • Training objective: The lattice parameters are learned by minimizing summed loss over training samples plus a regularizer on θ.With convex loss and regularizer, the resulting lattice-regression problem is convex.

4. Monotonic Lattices

The paper enforces monotonicity directly through linear inequalities on adjacent lattice parameters. These constraints yield a convex constrained objective and can be extended with additional functional restrictions or ranking losses.

  • Monotonicity constraints: Adjacent lattice parameters ordered along a feature are necessary and sufficient for the interpolated function to be monotonic in that feature.The condition extends from the two-dimensional lattice to larger lattices.
  • Guarantee: The constraints are sufficient because interpolation derivatives become weighted sums of adjacent parameter differences, with nonnegative weights.Each weight αk lies in [0, 1], so ordered adjacent parameters keep the partial derivative nonnegative.
  • Optimization: Monotonic lattice regression minimizes empirical loss plus regularization subject to sparse linear inequalities Aθ ≤ b.Equality is allowed for non-strict monotonicity, and each feature can be constrained independently.
  • Extensions: Additional linear inequalities can constrain outputs, such as requiring f(x) to lie in [0, 1] or remain nonnegative.The same matrix formulation accommodates these practical restrictions.
  • Applications: The formulation also extends to pairwise learning-to-rank objectives and supports squared, hinge, or logistic losses.The loss choice changes the supervised objective while retaining the constrained-lattice structure.

5. Faster Linear Interpolation

The paper develops faster interpolation for lattice regression, reducing multilinear weight computation and introducing simplex interpolation using only D + 1 vertices. Simplex interpolation is much faster in higher dimensions but can be rotationally dependent and less smooth.

  • 5.1 Fast Multilinear Interpolation: O(2^D) operations compute multilinear interpolation weights after dynamic programming shares computation across vertices.The algorithm loops over dimensions and incrementally updates indices and weights.
  • 5.2 Simplex Linear Interpolation: O(D log D) operations determine the D + 1 vertices for simplex interpolation, instead of evaluating all 2^D surrounding vertices.The vertices are found by sorting the D feature values.
  • 5.2.4 Using Simplex Interpolation for Machine Learning: Simplex and multilinear interpolation use the same monotonicity constraints, and feature orientations can align the shared diagonal with an assumed function slope.The authors recommend specifying constrained features as monotonically increasing rather than decreasing.
  • 5.2.4 Using Simplex Interpolation for Machine Learning: Simplex interpolation is continuous but less smooth and rotationally dependent because it forms D! locally linear hyperplanes around the hypercube diagonal.Its rotational dependence can change function flexibility across regions when coarse lattices are used.
  • 5.2.4 Using Simplex Interpolation for Machine Learning: Simplex interpolation is roughly as accurate as multilinear interpolation for 2^D lattices and much faster when D ≥8.This comparison is reported across the paper’s case studies.

6. Regularizing the Lattice Regression To Be More Linear

The paper introduces a torsion regularizer that penalizes differences between parallel lattice edges, encouraging locally more linear functions while remaining convex.

  • 6. Regularizing the Lattice Regression To Be More Linear: The torsion regularizer penalizes changes in slope between parallel sides, reducing twisting across lattice cells.Its weight controls how linear the lattice function becomes within each 2^D cell.
  • 6. Regularizing the Lattice Regression To Be More Linear: Torsion and graph Hessian regularizers make multi-cell lattice functions more linear in different ways and may both be needed to closely approximate linearity.The graph Laplacian instead minimizes squared slopes and produces a flatter function.
  • 6. Regularizing the Lattice Regression To Be More Linear: The proposed torsion regularizer is convex but not strictly convex and can be written as θ^T Kθ with K positive semidefinite.This preserves a quadratic-form optimization structure while adding the new lattice-specific penalty.

7. Jointly Learning Feature Calibrations

The paper jointly learns one-dimensional feature calibrations and a lattice so continuous, categorical, and differently scaled inputs can be represented before modeling interactions.

  • 7.1 Calibrating Continuous Features: Learning one-dimensional calibrations before the lattice lets many problems use a 2^D lattice after feature transformations capture useful marginal shapes.For example, distance may be better represented on a logarithmic scale.
  • 7.1 Calibrating Continuous Features: Continuous features use monotonic piecewise linear calibration functions learned jointly with the lattice parameters.This provides interpretable transformations while preserving monotonicity.
  • 7.1 Calibrating Continuous Features: Joint calibration makes the objective non-convex, so knot locations are fixed at equally spaced feature quantiles while knot values are optimized.The number of changepoints is treated as a hyperparameter.
  • 7.2 Calibrating Categorical Features: Categorical calibration maps each category to a real value in [0, M_d −1], with optional pairwise constraints when category ordering is known.The calibrated values can then participate in lattice interpolation.

8. Calibrating Missing Data and Using Missing Data Vertices

The paper proposes supervised ways to represent missing feature values in lattice regression: learned imputation or dedicated missing-data lattice vertices. Dedicated vertices add parameters but allow missingness-specific behavior.

  • 8. Calibrating Missing Data and Using Missing Data Vertices: Two supervised strategies handle missing values: calibrating a learned imputation value or adding dedicated missing-data vertices.Both approaches can incorporate linear inequalities to bound missing-data outputs.
  • 8. Calibrating Missing Data and Using Missing Data Vertices: Dedicated missing-data vertices increase the parameter count but let the model treat missing values differently from observed values.This resembles a decision tree splitting on whether a feature is missing.
  • 8. Calibrating Missing Data and Using Missing Data Vertices: Missing-data parameters can be regularized as adjacent to the feature’s minimum and maximum vertices for graph regularization.This allows graph penalties to connect missing-data behavior to ordinary lattice parameters.
  • 8. Calibrating Missing Data and Using Missing Data Vertices: In the business-matching example, interpolating the two parameters for a missing street-similarity feature yields f(x) = 0.25.The example uses a 3 × 2 lattice with title similarity equal to 0.5.

9. Large-Scale Training

Large-scale training combines stochastic optimization, sampled regularization, parallelization, and constrained updates to make calibrated monotonic lattices practical. Joint calibration adds flexibility for continuous and categorical features but makes the objective non-convex.

  • Large-scale optimization: Training uses SGD, sampled additive regularizer terms, and parallel train-and-average strategies to address large sample counts and expensive regularizers.The paper also describes exploiting sparse monotonicity constraints and interpolation weights for fast constrained updates.
  • SGD and variance reduction: Mini-batching reduces stochastic-gradient variance while increasing loss-term computation by kℓ, which is useful when regularizer differentiation dominates cost.The approach is beneficial for sufficiently small mini-batches.
  • Stochastic regularization: A 150× training speed-up preserved statistically indistinguishable held-out accuracy when regularizer terms were randomly sampled with kR = 1024 and kℓ=1.Sampling regularizer terms trades higher stochastic variance for substantially lower per-iteration cost.
  • Calibration functions: Continuous calibration uses monotonic piecewise-linear transforms with quantile knots, while categorical calibration maps categories directly into the lattice span.These calibrations normalize feature ranges and provide learnable representations for categorical inputs.
  • Joint optimization: Jointly learning calibration and lattice parameters makes the objective non-convex, although it remains marginally convex in lattice parameters when calibrations are fixed.Projected SGD alternately computes stochastic subgradients with respect to the lattice and calibration parameters.
  • Constraint handling: The constraint-projection strategy can leave parameters stuck at feasible-set corners, but later stochastic updates often free them and produced similar objective values and test accuracy.All reported experiments used this suboptimal projection strategy.

10. Case Studies

Real-world case studies evaluate calibrated monotonic lattices across practical datasets and compare them with random forests, linear models, and ablations. The results generally preserve competitive accuracy while showing benefits from monotonicity, calibration, and feature handling.

  • Overall findings: Calibrated monotonic lattice regression achieved accuracy similar to random forests on problems where monotonicity was warranted.The studies used relatively large real-world datasets because prior monotonic benchmarks were small.
  • Business entity resolution: Removing monotonicity constraints reduced business-entity-resolution accuracy by a statistically significant half percent.The authors interpret this as evidence that monotonicity regularized the small-data problem.
  • Missing data: Using missing-data vertices achieved 81.9% accuracy versus 80.7% when missing values were calibrated in the business entity-resolution study.With only 3,000 subsampled training examples, the less-flexible calibration option performed better.
  • Feature calibration: Removing continuous signal calibration significantly reduced accuracy, while removing the geographic categorical feature reduced accuracy by half a percent.The study used five calibration changepoints for two continuous features and calibrated a 14-category geographic feature.
  • Regularization: Torsion regularization at 10^-4 was selected by cross-validation, and replacing it with graph Laplacian regularization slightly reduced accuracy without statistical significance.The reported pattern was consistent with torsion often being slightly better, but not significantly so.
  • Ad-query matching: In ad-query matching, calibrated lattices used 57 parameters versus 1024 uncalibrated parameters with slightly better, though not significantly better, accuracy.The boosted-stumps model reached 75.4% test accuracy and produced piecewise-constant ties.

10.4 Case Study: Rendering Classifier

The rendering-classifier case study applies a monotonic lattice to a difficult classification problem with fifteen constrained features and one unconstrained Boolean feature. It reports substantial gains over a linear model and statistically significant improvement over random forests.

  • Task and constraints: The model scores whether a webpage display element should be rendered, enforcing monotonicity for fifteen features while leaving one Boolean feature unconstrained.The train and test examples were mostly difficult cases, yielding relatively low accuracies.
  • Model comparison: A 2×2×2×2 lattice was visualized through two-feature slices with the other three features fixed at their medians.Compared with the lattice, boosted stumps required hundreds of stumps and remained piecewise constant.
  • Training setup: Simplex interpolation enabled a single-threaded loop through 20,000 training samples to take about five minutes on a Xeon-type desktop.The implementation used a fixed 216 lattice, five changepoints for six continuous signals, and no graph regularization.
  • Results: The lattice regression was statistically significantly better than random forests while producing a monotonic, smooth function.The authors attribute the result hypothetically to regularization from monotonicity constraints in a difficult, small-sample setting.

10.6 Case Study: Video Ranking and Large-Scale Learning

The video-ranking case study applies monotonic lattice regression to large-scale pairwise recommendation data, examining sampling, monotonicity, and distributed training. Monotonic constraints slightly reduce offline click-pair accuracy but improve live engagement under sampling bias, while parallel training has different scaling behavior for constrained models.

  • 10.6 Case Study: Video Ranking and Large-Scale Learning: The model used twelve positively correlated features constrained to be monotonically increasing, while acknowledging that such constraints cannot fully represent changing human video preferences.For example, popularity may indicate recommendation quality before eventually becoming less predictive as a video’s popularity fades.
  • 10.6 Case Study: Video Ranking and Large-Scale Learning: Simplex interpolation was chosen for cheap evaluation because the system must score and rescore billions of candidate video pairs.The training objective minimized pairwise ranking errors for watched-video and preferred/unpreferred candidate pairs.
  • 10.6.1 Data: Bottom-clicked training pairs yielded up to 1% higher test accuracy than alternatives using randomly sampled or following videos as unpreferred examples.The bottom-clicked construction used a clicked video as preferred and the video immediately above it as unpreferred.
  • 10.6.2 More Experimental Details: 400 million training pairs were split into 400 million training, 25 million validation, and 25 million test pairs covering millions of users and watched videos.The feature-only data preserved privacy, but the splits could contain samples from the same users and videos.
  • 10.6.3 Results: Live experiments found monotonic models improved user-engagement measures despite about 0.5% lower offline pairwise accuracy on click data.The authors attribute the discrepancy to click-data sampling bias and report that monotonicity helps preserve accuracy in sparse regions important for ranking all videos.
  • 10.6.3 Results: With 500k training pairs, parallel and single-machine monotonic training matched, but larger datasets required more parallel data to reach single-machine accuracy.The authors hypothesize that averaging 100 monotonic lattices produces an over-constrained interior solution.

10.7 Run Times

The run-time study compares interpolation and training costs for lattice models. Simplex interpolation scales more favorably with feature count than multilinear interpolation, while parallelized training processes substantially more data in similar wall-clock time.

  • 10.7 Run Times: Simplex evaluation scales roughly linearly with D, consistent with O(D log D), whereas multilinear evaluation follows O(2^D) complexity.The multilinear timing curve was shown on a log scale, where its growth was roughly linear in D.
  • 10.7 Run Times: One monotonic 2^12 lattice took about 15 minutes for one worker to process 4 million samples, compared with about 20 minutes for 100 workers to process 400 million samples.The authors caution that distributed-cluster training times have high variance.
  • 10.7 Run Times: Simplex interpolation was over 1,000× faster than multilinear interpolation at D = 17 features.The reported speed advantage was about 10× at D = 9 and about 100× at D = 13.

11. Discussion and Some Open Questions

The discussion highlights practical extensions and findings, while identifying scope, optimization, model-size, and classifier-specific limitations of monotonic lattice regression.

  • The approach addresses interpretability, evaluation speed, preprocessing, missing data, and categorical features while achieving state-of-the-art performance on the largest reported monotonic-method datasets.
  • Jointly optimized one-dimensional calibrators often make a simple 2D lattice sufficient to capture feature interactions, although regularization does not reduce model size.
  • The method remains limited by exponential model size near D = 20 features, and classifier monotonicity can be stronger than monotonicity of the decision boundary.
  • Simplex interpolation matches multilinear accuracy in practice and becomes orders of magnitude faster as feature dimension increases, with theoretical complexity O(D log D).
  • Learned categorical mappings provide interpretable one-dimensional category embeddings, while finer-grained lattices can add flexibility for categorical features.
  • The convex monotonic-lattice problem becomes non-convex when composed with calibration functions, and accuracy can be sensitive to separate stochastic-gradient step sizes.
Loading 1505.06378v3…