A Nonparametric Approach to Modeling Choice with Limited Data

Vivek F. Farias; Srikanth Jagabathula; Devavrat Shah

Source-linked AI summary

A Nonparametric Approach to Modeling Choice with Limited Data

Vivek F. Farias, Srikanth Jagabathula, Devavrat Shah

arXiv:0910.0063v4Oct 1, 2009stat.AP

TL;DR

The paper addresses using historical sales data to predict expected revenue and proposes a non-parametric, data-driven approach. It develops revenue-estimation schemes and reports accurate predictions on simulated and real-world data without over- or underfitting.

Problem
The paper studies how to use historical sales data to predict expected revenue, a problem of central interest to operations managers.
Method
The paper proposes a non-parametric, data-driven approach with revenue functions and a broad experimental procedure for revenue estimation.
Results
The proposed schemes produced accurate sales and revenue predictions in extensive studies using simulated and real-world data without over- or underfitting.
Takeaways & Limitations
The paper presents schemes for producing accurate revenue predictions across a general class of models.
Takeaways & Limitations
The approach is not a panacea for choice modeling problems.

Abstract

from arXiv · show

A central push in operations models over the last decade has been the incorporation of models of customer choice. Real world implementations of many of these models face the formidable stumbling block of simply identifying the `right' model of choice to use. Thus motivated, we visit the following problem: For a `generic' model of consumer choice (namely, distributions over preference lists) and a limited amount of data on how consumers actually make decisions (such as marginal information about these distributions), how may one predict revenues from offering a particular assortment of choices? We present a framework to answer such questions and design a number of tractable algorithms from a data and computational standpoint for the same. This paper thus takes a significant step towards `automating' the crucial task of choice model selection in the context of operational decision problems.

1. Introduction

The paper addresses revenue prediction from historical sales when customer substitution makes product demand assortment-dependent and the appropriate parametric choice model is uncertain. It proposes a data-driven, nonparametric framework over preference-list distributions that identifies models consistent with observed data, produces robust predictions, and supports tractable algorithms and empirical evaluation.

Motivation: Historical sales data must support predictions for product assortments, but substitution makes each product’s purchase probability depend on the full offer set.Observed sales combine primary demand with additional demand generated when customers substitute unavailable products.
Motivation: Parametric choice modeling requires selecting a suitable structure, while misspecification, over-fitting, and under-fitting can reduce prediction quality.Even simple models may impose unreasonable assumptions, whereas more complex models can perform worse because of over-fitting.
Approach: The paper represents choice generically as distributions over product rankings, a view that subsumes essentially all existing choice models.This avoids requiring the revenue manager to choose a parametric structure or balance model parsimony against over-fitting risk.
Implications: The approach aims to move directly from raw sales transaction data to revenue or sales estimates for a given offer set without structural assumptions.The authors present this as a valuable application within operations, while noting that it does not represent everything a choice model can do.
Approach: Given limited sales data, the framework finds generic choice models consistent with the observations and predicts an unseen assortment’s worst-case expected revenue over that model set.The approach makes no a priori structural assumptions and improves as additional data narrows the set of consistent models.
Evaluation: The authors develop several algorithms to address the computational difficulty of these model sets and evaluate prediction quality against parametric alternatives.The empirical studies examine both absolute prediction quality and performance relative to alternative parametric approaches.
Evaluation: The robust method improves prediction accuracy by about 20% in all reported cases and is not apparently susceptible to over-fitting or under-fitting.The study also reports that MMNL performance relative to MNL deteriorates as training data decrease because of over-fitting.
Analysis: The implicitly used robust choice model is essentially the sparsest model, with model complexity scaling with the amount of available data.This provides an explanation for the observed immunity to over-fitting and under-fitting and characterizes models identifiable from marginal data.

2. The Choice Model and Problem Formulations

The paper models customers as distributions over preference rankings and uses limited linear information about those rankings to represent choice and revenue functions. It frames revenue estimation as a black-box input for assortment and other operations-management decisions.

2. The Choice Model and Problem Formulations: Customers are represented by preference permutations, choosing their most-preferred available product, with the no-purchase option included in every offered set.The framework assumes rational, transitive preferences and permits different preference sets across customer observations.
2.1. Choice Model: The model imposes minimal behavioral structure and encompasses commonly used choice models, including multinomial, nested multinomial, and mixed multinomial logit families.Its only core behavioral requirements are transitive preferences and selection of the most-preferred offered product.
2.1. Choice Model: A distribution λ over all product permutations defines the choice model and induces purchase probabilities for each offered assortment.Each permutation corresponds to a customer type whose ranking determines choice behavior.
2.2. Data: Observed data are expressed as y = Aλ, where A records linear relationships between partial observations and the distribution over N! permutations.Typically, m ≪ N!, reflecting information from only a limited number of assortments or other partial observations.
2.2. Data: The framework accommodates comparison, ranking, top-set, and transaction data, each represented through an appropriate binary matrix A.Transaction data record product purchase fractions across selected assortments and form a linear transformation of λ.
2.3. Incorporating Choice In Decision Models: A Revenue Estimation Black-Box: Revenue R(M) is the expected revenue from offering assortment M, computed from product prices and the choice probabilities induced by λ.The resulting revenue function is intended to support assortment management, network revenue management, and inventory decisions involving substitution.
2.3. Incorporating Choice In Decision Models: A Revenue Estimation Black-Box: Estimating R(·) serves as a black box for assortment decisions over time without requiring the user to specify a structural choice model.The paper positions this as a way to reduce reliance on structural assumptions while using available data.

3. Revenue Estimates: Computation

The paper formulates robust revenue estimation as a linear program over preference distributions consistent with observed data, then develops sampling- and representation-based methods to solve it. These methods provide tractable approximations, with guarantees for constraint satisfaction but not generally for objective-value closeness.

3. Revenue Estimates: Computation: The robust program selects the lowest expected revenue over distributions λ that satisfy the observed-data constraints and probability requirements.The constraints Aλ = y enforce consistency with observed data, while λ is a probability distribution.
3. Revenue Estimates: Computation: The computational challenge is that the program has an intractable number of variables or constraints, motivating two approximation approaches.The paper separately considers sampled dual constraints and efficient representations of the relevant feasible sets.
3. Revenue Estimates: Computation: The sampling approach draws n permutations from a distribution ψ and solves a sampled relaxation of the dual problem.Because the sampled problem is a relaxation, its solution is an upper bound on the optimal value of the full dual problem.
3. Revenue Estimates: Computation: With n = O((1/ε)(m ln(1/ε) + ln(1/δ))) samples, the sampled solution violates at most an ε fraction of constraints with probability at least 1 − δ.The sample requirement scales with the number of variables rather than the total number of constraints.
3. Revenue Estimates: Computation: The sampling theory does not guarantee how close the relaxed problem’s optimal cost is to the original problem’s optimal cost.Despite this limitation, experiments produced solutions close to optimal.
3. Revenue Estimates: Computation: The second approach represents each set A_j(M) through partitions and polytopes, reducing the robust constraints to efficiently solvable linear programs.When the representation has polynomial size, the resulting problem can be solved in polynomial time in that representation.
3. Revenue Estimates: Computation: This representation-based method can sequentially generate improving lower-bounding approximations to the robust revenue-estimation problem.The procedure applies to solving the dual formulation or its equivalent original formulation and is similarly tractable when E is convex.

4. Revenue Estimates: Data Driven Computational Study

The study tests robust revenue estimation on simulated data generated from several structural choice models and compares predictions with ground-truth revenues. The approach captures diverse structures and gives close predictions, although accuracy mildly declines as model complexity increases.

4. Revenue Estimates: Data Driven Computational Study: The experiments generate transaction data from selected structural models, estimate marginal information y, and use it to implement the robust revenue approach.Predictions are evaluated on distinct assortments against revenues computed from the benchmarking ground-truth model.
4. Revenue Estimates: Data Driven Computational Study: The design isolates structural error from finite-sample error by computing exact choice probabilities and revenues from the ground-truth parametric model.This tests whether the robust approach captures underlying choice structure rather than sampling noise.
4. Revenue Estimates: Data Driven Computational Study: The benchmark set includes MNL, CNL, and MMNL models, including an Amazon DVD-sales model and perturbations that introduce nesting or customer heterogeneity.The AMZN-CNL model partitions products into four nests, while AMZN-MMNL replaces parameters with customer-specific random quantities.
4. Revenue Estimates: Data Driven Computational Study: Figure 1 evaluates robust estimates on 60 randomly drawn assortments for each model, comparing estimated and true revenues.The experiments use assortments of varying sizes and include the AMZN, AMZN-CNL, and AMZN-MMNL models.
4. Revenue Estimates: Data Driven Computational Study: The robust approach effectively captures diverse parametric structures and provides close revenue predictions from limited marginal information.The conclusion is drawn across commonly used structural choice models and practically relevant parameter ranges.
4. Revenue Estimates: Data Driven Computational Study: When a tested structural model predicts revenues accurately, the robust approach is likely to perform just as well without knowing that structure.When the structural model is a poor fit, the robust approach is reported to continue providing meaningful guarantees.

5. Revenue Estimates: Case Study with a Major US Automaker

A case study using automobile sales transactions evaluates robust conversion-rate predictions against MNL and MMNL models across calibration-data regimes. The robust method is more accurate across regimes and remains stable as data become more limited, while MMNL performance deteriorates.

Study design: The case study uses historical transaction data from a major US automaker to predict conversion rates for automobile assortments and compare robust, MNL, and MMNL methods.Conversion rate is the probability that an arriving customer purchases a product.
Data: The dataset contains 14 SUV identities and 203 observed assortments, with sales-rate information computed for each assortment.Each assortment was offered at some point at a dealership in the selected dealership zone.
Data limitation: The conversion-rate denominator is unavailable because purchases by arriving customers who buy nothing are not observed, creating data censoring that affects all methods.The study approximates arrivals using dealership-specific rates based on market size and a tuned factor.
Evaluation: Prediction accuracy is evaluated using relative error in k-fold cross-validation with k = 10, 5, and 2, where lower k represents fewer training assortments.Each partition serves as test data once, producing more limited-data scenarios as k decreases.
Results: The robust method predicts conversion rates more accurately than both MNL and MMNL methods in all calibration-data regimes.The case study reports about 20% improvement in accuracy across regimes.
Results: MMNL is marginally better than MNL with high calibration data but becomes worse as calibration data decrease, consistent with over-fitting from its greater complexity.Robust-method performance remains stable across the different calibration-data regimes.

6. The Sparsest Choice Model Consistent with Data

The paper selects the simplest choice model consistent with observed marginal data by using sparsity as the simplicity criterion. Its analysis shows that model complexity scales with available data and that, under stated conditions, sparse fitting can identify the generating model.

Sparsity criterion: Sparsity is attractive because it explains observed substitution behavior with as few customer preference lists as possible and supports tractable applications.The paper frames this as a measure of model simplicity.
Data-dependent complexity: The complexity of the implicitly selected choice model scales with the dimension of the data vector and therefore with the amount of available data.The paper presents this automatic scaling as a property of the non-parametric procedure.
Interpretation: This data-dependent complexity provides a potential explanation for the robust approach’s reduced susceptibility to over-fitting and under-fitting observed in the case study.The paper explicitly connects the theoretical scaling result to the empirical MMNL over-fitting result.
Sparsest model: The robust revenue procedure implicitly uses a choice model essentially equal to the sparsest model consistent with the observed data.Sparsity measures the number of preference lists receiving positive probability mass.
Sparsity characterization: For almost all data vectors, if K is the support size of the sparsest consistent distribution, the robust procedure uses a model with sparsity K or K + 1.The theorem assumes the data distribution is absolutely continuous and the proof uses a full-row-rank condition on matrix A.
Identification: Under signature and linear-independence conditions, the sparsest-fit program uniquely recovers the generating choice model.The paper states that the program’s optimal solution equals the generating model under these conditions.
Identification: The paper characterizes data-dependent families of choice models identifiable by sparse fitting and formalizes how recoverable model complexity scales with available data.It also studies conditions under which sparse models can be recovered with high probability as N grows.

7. Conclusion and Potential Future Directions

The paper presents efficient, data-driven schemes for accurate revenue prediction under generic choice models, while outlining future work on sparse models, identification, and optimization. Its nonparametric approach is valuable for automating choice modeling, but its usefulness depends on observing data about products and the application context.

Conclusion: The approach is computationally efficient and supports a data-driven alternative for incorporating choice models into operations-management decision problems.The authors describe this as raising the possibility of automating choice modeling at large scale.
Conclusion: The schemes produce accurate sales and revenue predictions across simulated and real-world data without being prone to overfitting or underfitting.The empirical studies demonstrated the power of the approach in producing accurate revenue predictions.
Future directions: Future research could study sparse or simple choice models consistent with marginal information and extend the limits of identification and recoverability.The authors also point to computing sparse approximations for generic choice models with limited data.
Limitations: Nonparametric prediction is limited for products unseen in the data, whereas structural models may extrapolate using product features; selecting between them requires contextual consideration.The nonparametric approach can make useful predictions about product interactions only after related product data is observed, while parametric approaches require expert input and can be difficult to automate at scale.
Applications: Future applications include using the revenue-estimation subroutine within network revenue optimization and assortment optimization.The paper identifies revenue-function estimation as a core subroutine for revenue optimization under customer choice.
Future directions: The robust approach yields difficult optimization problems for which the paper gives a generic scheme inspired by cutting-plane methods, while stronger relaxations remain an alternative.The proposed alternative seeks uniform approximation guarantees.

A. Proofs for Section 6

The proof establishes geometric and sparsity properties of data vectors in the convex hull of matrix A. It also shows that data vectors requiring fewer than d+1 columns occupy zero (d−1)-dimensional volume.

Lemma 1: Lemma 1 places every data vector y in a d−1 dimensional subspace and bounds the sparsest representation by d+1 nonzero coefficients.Here d is the column rank of A, and Y is the convex hull of its columns.
Lemma 1: Consequently, almost every data vector in Y does not admit a representation using fewer than d columns.This follows because the finite union of lower-dimensional sets has zero (d−1)-dimensional volume.
Lemma 1: The augmented constraint system has rank at most d+1, so an optimal basic feasible representation uses at most d+1 columns.The augmentation appends a row of ones to A and a corresponding coordinate to y.
Lemma 1: For each r ≤ d−1, data vectors representable by at most r columns form a finite union of lower-dimensional polytopes.Each such polytope has zero (d−1)-dimensional volume within Y.

A.2. Proof of Theorem 2

Theorem 2’s proof uses the Signature and Linear Independence conditions to identify the support and probabilities of a choice model. The resulting Sparsest Fit algorithm recovers λ when both conditions hold and can certify when they fail.

Algorithm: The algorithm takes y and the known structure of A as input, then outputs the support size, supported permutations, and their probabilities.If the required conditions are not satisfied, it provides a certificate of that fact.
Proof strategy: The Linear Independence condition makes subset representations unique, allowing observed coordinates y_d to identify the corresponding A(σ_i)_d values.Once all λ(σ_i) values are known, each relevant column coordinate is recovered as the unique subset-sum solution.
Proof strategy: The Signature condition exposes each positive support probability as a coordinate of y, enabling recursive recovery of the support and probabilities.The smallest observed value initializes the procedure, which then processes later coordinates recursively.
Theorem 5: The Sparsest Fit algorithm recovers λ whenever λ satisfies the Signature and Linear Independence conditions.The theorem assumes y = Aλ and guarantees exact recovery under these two conditions.
Theorem 2: The proof shows that any competing model with no larger support must have the same probability values and support, because zero coefficients would violate linear independence.The contradiction argument represents the competing values through a 0−1 matrix and rules out a smaller effective support.

A.3. Proof of Theorem 3

Theorem 3 establishes when randomly generated choice models satisfy the structural conditions needed for recovery. Linear independence holds with probability 1, while Signature-condition guarantees depend on the observed-data form.

Linear Independence: The generated choice model satisfies Linear Independence with probability 1 because its support probabilities are independently uniform and degenerate relations occupy lower-dimensional sets.Only finitely many such lower-dimensional sets arise under bounded coefficients.
Ranking Data: For ranking data, the Signature condition holds with K = O(n).The bound is obtained directly from a previously established lemma.
Comparison Data: For comparison data, the proof truncates each permutation column to disjoint unordered pairs and studies permutation submatrices of the resulting matrix.The target is to show the Signature condition with high probability as N grows.
Comparison Data: For comparison data, the probability that no qualifying permutation submatrix exists tends to zero when K = o(log N).The argument defines indicator variables for qualifying submatrices and bounds P(X = 0) using variance and expectation.
Comparison Data: The comparison-data bound follows by counting Bernoulli matrix configurations, estimating overlaps, and applying Stirling’s approximation and entropy bounds.These steps control the expectation and variance of the number of qualifying submatrices.

A.4. Proof of Theorem 4

Theorem 4 uses an empirical choice model formed from samples of the true model to approximate expected revenues for all offer sets up to size C. Concentration bounds and a union bound provide a sufficiently large sample size.

Construction: The empirical choice model is induced by M samples drawn from the true choice model and is constructed to approximate revenues for all offer sets of size at most C.The proof uses the probabilistic method to establish existence of a sparse approximating model.
Revenue approximation: Expected revenue for an offer set M is expressed as the sum of product prices weighted by their purchase probabilities.For product j, the purchase probability is λ_j(M) = λ(S_j(M)).
Concentration: Chernoff/Hoeffding concentration bounds control the empirical purchase probabilities for each product and offer set.The relevant sample indicators are independent and identically distributed Bernoulli variables.
Uniform guarantee: A union bound extends the approximation guarantee across all products and all offer sets of size at most C.There are at most N^C such offer sets.
Conclusion: Choosing M so the resulting bound is below 1 proves existence of an empirical model with the desired uniform revenue approximation.The sample-size condition is selected to make the right-hand side of the bound less than 1.

B.1. A Canonical Representation for Ranking Data

The section represents ranking-based partial choice information through permutation-based columns and polyhedral sets conditioned on the product purchased. For ranking data, the resulting convex-hull descriptions are integral, enabling an efficient LP-based representation and solution procedure.

Ranking-data representation: Ranking data records the probability that product i is ranked at position r, producing a matrix A whose columns correspond to product permutations.For permutation σ, A(σ)_ri = 1 exactly when σ(i) = r.
Ranking-data representation: For each product j and rank d, A_jd(M) contains permutation columns where j is the dth-most-preferred choice.The associated binary vectors encode valid permutations, fix j's rank at d, and enforce membership in S_jd(M).
Polyhedral representation: The ranking-data polytope is integral and equals the convex hull of the feasible permutation columns, yielding an efficient canonical representation.The construction uses a projection of a matching polytope, so feasible points satisfy the required permutation constraints.
Iterative solution procedure: For general data, relaxing integrality can produce only an outer approximation, so the method repeatedly solves LPs and branches on fractional components.If every optimal representation is integral, the first solution is optimal; otherwise, a fractional variable partitions the feasible set into zero and one cases.
Iterative solution procedure: The branching procedure is finite and improves lower bounds, but each iteration can increase the LP size by up to a factor of 2.Approximation quality can be assessed by solving the maximization version or by sampling constraints.

B.3. Explicit LP solved for censored comparison data in Section 4

For censored comparison data, the section encodes purchase-generating permutations and solves a modified LP using inequality-based data consistency constraints. The construction connects relaxed polytopes to the comparison-data representation while accounting for non-integrality.

Censored comparison data: Censored comparison data records product preferences relative to another product and the no-purchase option through pair-indexed purchase fractions.For i ≠ 0, y_ij is the fraction purchasing i from {i,j,0}; y_0j records preference for no purchase over j.
Permutation encoding: The matrix A encodes permutations in which product i precedes product j and, when relevant, the no-purchase option.Its columns represent comparison outcomes induced by complete preference rankings.
LP formulation: The LP replaces Aλ = y with Aλ ≥ y, while retaining probability normalization and assortment-specific permutation constraints.The dual variables correspond to data-consistency constraints and the requirement that λ is a probability distribution.
Integrality boundary: The relaxation is not generally integral for N ≥5, although the polytope is integral for N ≤4.Thus, the relaxed formulation can differ from the exact convex hull in larger instances.
LP formulation: The comparison-data constraints define feasible permutation vectors, while auxiliary variables link those vectors to product-preference and no-purchase relations.The resulting points are claimed to coincide with the vectors in A_j(M).

C.2. Nested logit family (NL)

Nested logit models capture shared unobserved attributes by partitioning products into mutually exclusive nests and assigning nest-level and product-level utility shocks. They improve on MNL's IIA limitation but remain constrained by within-nest IIA and the nesting structure.

Nested logit structure: The nested logit family partitions products into L mutually exclusive nests, grouping products that share unobserved attributes.Each product belongs to exactly one nest in the basic nested-logit formulation.
Nested logit structure: Nested-logit utility combines a deterministic component with a nest-specific error and an independent product-specific error.The nest shock is shared across products in the same nest, while product-specific shocks are i.i.d. standard Gumbel variables.
Choice probabilities: Under these error assumptions, the model provides a closed-form probability that product j is purchased from assortment M.This preserves computational tractability while modeling shared unobserved attributes.
Limitations: Nested MNL alleviates MNL's IIA issue across nests but retains IIA within each nest and requires a difficult one-nest assignment for every product.The one-nest restriction is problematic when products correlate with alternatives across nests, including the no-purchase option.
Extensions and limitations: Cross-nested logit allows products to belong to multiple nests, but it is less tractable and cannot capture all possible product-correlation patterns.The supplied comparison also notes that MNL and NL do not account for heterogeneity in customer tastes.

D. Case Study: Major US Automaker

The case study evaluates conversion-rate prediction using training and test assortments with sparse sales counts filtered to avoid noisy estimates. The robust method predicts test-assortment conversion by solving an LP with interval-valued choice-probability constraints.

Case-study setup: The case study separates assortments into training and test sets and defines sales counts for products and no-purchase outcomes.Counts for products with no observed sales or counts of 6 or fewer are discarded as too low to be significant.
Case-study setup: Counts of 6 or fewer are discarded to avoid noisy sample probability estimates.The filtering rule applies when no sales are observed or C_i,M ≤ 6.
Robust prediction: The robust approach predicts an assortment's conversion rate by solving an LP with prices set to 1 and interval constraints on choice probabilities.The intervals replace exact equality constraints because finite samples make estimated choice probabilities uncertain.
Robust prediction: The interval width is controlled by z; the experiments set z = 3.15, the smallest value for which the LP was feasible.Small z can make the LP infeasible, whereas large z produces more conservative estimates.
Robust prediction: Bounds outside [0,1] are effectively ignored, so the robust method can automatically discard uninformative constraints.If both endpoints fall outside [0,1], the entire interval constraint becomes redundant.