Simultaneous estimation of multiple discrete unimodal distributions under stochastic order constraints

Motivated by search behavior analysis, this paper proposes a mixed-integer convex quadratic optimization method to simultaneously estimate multiple discrete unimodal distributions under stochastic order constraints, demonstrating improved accuracy over existing approaches in low-sample regimes.

The Gist

Imagine you are trying to predict when new parents will search for specific advice on a baby app.

Maybe they search for "when to introduce solid food" or "when does baby sleep through the night." The paper argues that these searches aren't random; they happen in a specific order. Parents search for "newborn diaper rash" before they search for "toddler potty training."

The researchers wanted to build a better "crystal ball" to predict these search patterns, especially when they don't have a lot of data to work with. Here is how they did it, explained simply:

1. The Problem: The "Empty Room" Effect

Usually, if you want to guess a pattern (like a bell curve showing when people search), you need a huge crowd of people to give you data.

• The Issue: For popular topics (like "baby crying"), you have thousands of data points. Your guess is easy and accurate.
• The Struggle: For niche topics (like "baby with a rare rash"), you might only have 10 or 20 data points. If you try to guess the pattern with so little data, your model gets "spiky" and confused. It's like trying to draw a perfect portrait of a celebrity using only three blurry photos.

2. The Solution: The "Chain of Trust"

The researchers realized that even if you don't have enough data for Topic B (e.g., "3-month-old sleep"), you probably have plenty of data for Topic A (e.g., "1-month-old sleep").

They used a concept called Stochastic Order. Think of it like a relay race:

• You know the first runner (1-month-old) must finish before the second runner (2-month-old) starts.
• You know the second runner must finish before the third runner (3-month-old).

Even if the second runner is running in the dark (no data), you can use the knowledge of the first and third runners to guess where the second one should be. You force your model to respect this "chain of trust."

3. The "Unimodal" Rule: The Mountain Peak

The researchers also noticed that these search patterns usually look like a single mountain.

• People don't search for "diaper rash" constantly. They search a little, then a lot (the peak), then a little again as the baby gets better.
• They call this Unimodal (one mode/peak).
• Their model forces the prediction to look like a nice, smooth mountain, rather than a jagged, messy scribble.

4. How They Tested It

They built a mathematical "recipe" (a computer algorithm) that combines these two rules:

1. The Mountain Rule: The shape must be a single peak.
2. The Relay Rule: The peaks must happen in the correct chronological order.

They tested this on real data from a Japanese parenting app called Mamari.

• The Result: When they had very little data (small sample sizes), their new method was much better than the old standard methods. It reduced the error by about 2% to 6%.
• The Catch: When they had massive amounts of data, their new method was just as good as the old ones, but not necessarily better. The "chain of trust" is most helpful when you are in the dark and need a guide.

The Big Picture Analogy

Imagine you are trying to guess the height of a tree in a foggy forest.

• Old Method: You look at the tree through the fog. If the fog is thick (little data), you guess wildly and get it wrong.
• New Method: You know that this tree is part of a row of trees planted in order. You know the tree to the left is short, and the tree to the right is tall. Even in the fog, you can say, "Okay, this tree must be somewhere in between."

By using the relationships between the trees (distributions), the researchers could guess the height of the foggy tree much more accurately than if they looked at it in isolation.

Why Does This Matter?

This isn't just about math; it's about helping parents. If an app can accurately predict when a parent is likely to need help, it can show them the right article or video at the right time, rather than spamming them with irrelevant info. It turns a "guessing game" into a "smart prediction."

Technical Summary

Here is a detailed technical summary of the paper "Simultaneous estimation of multiple discrete unimodal distributions under stochastic order constraints."

1. Problem Statement

The paper addresses the challenge of simultaneously estimating multiple discrete unimodal distributions when data is scarce. The specific motivation stems from analyzing user search behavior on "Mamari," a pregnancy and childcare information platform.

• Context: Users search for keywords related to specific stages of pregnancy or child development (e.g., "first trimester body weight" vs. "second trimester body weight").
• The Challenge: While search timing distributions for individual keywords are typically unimodal (peaking at a specific time relative to the event), estimating these distributions accurately is difficult for multi-term keywords due to small sample sizes.
• The Opportunity: There exists prior knowledge regarding the precedence relations between these distributions. For instance, the search timing distribution for the "first trimester" must stochastically precede that of the "second trimester." Existing methods often estimate distributions independently or fail to jointly enforce these structural constraints.

2. Methodology

The authors propose a Mixed-Integer Convex Quadratic Optimization (MICQP) model to integrate prior knowledge into the estimation process.

A. Mathematical Formulation

The problem is formulated as minimizing the distance between the estimated distributions ($X$) and the empirical distributions ($P$), subject to two types of constraints:

1. Unimodality Constraints:

   • Ensures each estimated distribution has a single peak.
   • Implemented using binary variables ($y_i$) to indicate whether an index is before or after the peak.
   • Enforced via linear inequalities ensuring monotonic increase up to the peak and monotonic decrease thereafter.

2. Stochastic Order Constraints:

   • Formalizes the precedence relation (e.g., $X_1 \le_{st} X_2$).
   • Defined as: $X_1 \le_{st} X_2$ if and only if the cumulative distribution function (CDF) of $X_1$ is greater than or equal to that of $X_2$ for all points ($F_{X_1}(t) \ge F_{X_2}(t)$).
   • This is translated into linear constraints on the cumulative sums of the probability mass functions.

B. Objective Function

• The primary objective is to minimize the Mean Squared Error (MSE) between the estimated and empirical distributions to facilitate convex optimization.
• For evaluation purposes, the paper uses the Jensen–Shannon Divergence (JSD), a symmetrized version of the Kullback–Leibler divergence, to measure estimation accuracy.

C. Solvability

• The resulting model is a Mixed-Integer Convex Quadratic Program.
• It can be solved efficiently using standard commercial solvers like Gurobi.

3. Key Contributions

1. Unified Framework: The paper is the first to propose a unified optimization model that simultaneously enforces unimodality, stochastic order constraints across multiple distributions (more than two), and bounded support.
2. Formalization of Precedence: It formalizes domain-specific precedence knowledge (e.g., pregnancy stages) into rigorous stochastic order constraints, allowing the model to "pool" information across related distributions.
3. Scalability: Demonstrates that complex structural constraints can be handled by standard solvers without requiring custom heuristic algorithms.

4. Experimental Results

The authors evaluated the proposed method ("OURS") against several baselines:

• Baselines: Empirical distribution (EMP), Gaussian MLE, Kernel Density Estimation (KERNEL), and Independent Unimodal Regression (UNIMODAL).
• Datasets:
  • Synthetic Data: Generated from normal distributions with known stochastic ordering.
  • Real-World Data: 27 instances of search queries from Mamari (e.g., "body weight," "diarrhea," "sleep duration") across different child age groups.

Key Findings:

• Small Sample Sizes ($n < 40$):
  • The proposed method significantly outperforms all baselines.
  • Compared to the standard Unimodal model, "OURS" reduced the JSD by an average of 2.2% (up to 6.3% improvement).
  • Compared to Kernel Density Estimation, the improvement was even more pronounced (up to 54% reduction in error for specific instances), as KERNEL suffered from overfitting due to data sparsity.
• Large Sample Sizes ($n \ge 80$):
  • The performance of "OURS" becomes comparable to existing methods.
  • In some cases, the constraints may slightly restrict flexibility, leading to negligible or very minor performance drops (max deterioration of 0.7%), but generally, it remains competitive.
• Visual Analysis:
  • "OURS" successfully recovered the correct unimodal shape and peak positions even with very few samples ($n=10$), whereas KERNEL produced spiky, overfitted distributions.
  • The stochastic order constraint effectively shifted the estimated peaks to align with the logical precedence (e.g., shifting the second-trimester peak to the right of the first).

5. Significance and Implications

• Data Efficiency: The method is particularly valuable in domains where data collection is expensive or sparse (e.g., niche medical queries, new product launches), as it leverages structural relationships to boost estimation accuracy.
• Interpretability: By enforcing unimodality and stochastic order, the resulting estimates are more interpretable and physically plausible than raw empirical data or unconstrained non-parametric estimates.
• Practical Application: The study demonstrates a successful application of mixed-integer optimization to real-world information retrieval problems, offering a robust tool for analyzing user behavior trends in platforms like Mamari.

6. Limitations and Future Work

• Smoothing: The authors note that the strict monotonicity constraints can sometimes lead to "steep" distributions. Future work suggests incorporating regularization or smoothing techniques to produce more natural-looking curves.
• Constraint Selection: Currently, the stochastic order constraints are manually defined based on domain knowledge. Future research aims to develop methods for automatically determining which constraints to impose.
• Broader Applications: The framework is applicable to other fields with natural precedence relations, such as marketing analysis (tracking customer interest evolution) or survival analysis.