Predictive Discretization during Model Selection

Harald Steck, Tommi S. Jaakkola

Abstract

We present an approach to discretizing multivariate continuous data while learning the structure of a graphical model. We derive the joint scoring function from the principle of predictive accuracy, allowing for the simultaneous optimization of a graphical model's structure and its data discretization policy.

Introduction

Graphical models, such as Bayesian Networks, are powerful tools for uncovering dependencies in complex datasets. However, these models frequently require discrete input. The conventional approach involves discretizing continuous variables as a pre-processing step—often using simple heuristics like equal-width binning—before learning the model structure. This decoupling is problematic: the choice of discretization (the number and location of bins) significantly influences the resulting model, potentially obscuring true dependencies or introducing spurious ones.

Methodology

The proposed framework moves beyond standard fit-based metrics, adopting a sequential predictive approach to joint optimization.

Predictive Scoring

The authors derive a joint scoring function, $L_P(\Lambda, m)$, based on the model's ability to predict unseen data points. This approach naturally penalizes excessive complexity; as the number of discretization levels increases, the risk of overfitting noise grows, causing predictive accuracy to decline. The final score is the difference between the marginal likelihood of the discretized data and a penalty term $G(D, \Lambda)$ that accounts for the discretization cost.

The "Finest Grid" and Monotonic Invariance

To efficiently map continuous densities to discrete states, the method utilizes the "finest grid implied by the data," where each data point conceptually occupies its own bin. This ensures the score is monotonically invariant, making it robust against non-linear but order-preserving transformations of the input data.

Heuristic Optimization

Given the vast search space of possible graphs and bin boundaries, the authors employ a greedy heuristic. This algorithm alternates between refining the graphical structure and optimizing the discretization thresholds for each variable.

Experimental Setup

The framework was evaluated using two primary datasets:

  1. Synthetic 2D Toy Data: Datasets were generated with varying numbers of clusters (from 2 to 10) to test the algorithm's ability to recover the "ground truth" discretization policy.
  2. Yeast Gene Expression Data: A dataset of 320 measurements across 32 genes (continuous) and mating type (binary) was used to compare the model against established biological benchmarks in the pheromone response pathway.
Figure 1: Synthetic 2D toy data with 10 clusters used to evaluate the algorithm's ability to recover true discretization states.

Results and Discussion

Accuracy on Synthetic Data

In synthetic tests, the predictive scoring function demonstrated remarkable precision, peaking exactly at the true number of clusters for each dataset. The method also correctly identified independent variables, refusing to add unnecessary discretization levels that would not improve predictive power.

Figure 6: Predictive scores across varying discretization levels (2 to 10) for nine different synthetic datasets. The peaks align with the true number of clusters in each case.

Biological Insights

On the yeast gene expression data, the joint optimization approach identified a network with approximately 65 edges. Unlike previous methods using fixed discretization—which often resulted in sparse, "naive" models—this approach captured complex regulatory dependencies that align closely with known biological pathways.

Key Insights

  • Discretization as Regularization: The number of bins acts as a complexity parameter. The optimal number of levels naturally scales with sample size, allowing the model to capture finer details as more data becomes available.
  • Dependence-Driven Discretization: Unlike spatial clustering (e.g., K-means), this method discretizes based on statistical dependence. Variables with strong relationships receive more bins, while independent variables favor fewer.
  • Threshold Optimization: Optimizing the specific locations of bin boundaries (thresholds) was found to be as critical as choosing the correct number of bins for improving model quality.

Conclusion

This research provides a principled foundation for integrating discretization into the model selection process. While the greedy search strategy may encounter local optima and the focus on rank-order data ignores physical Euclidean distances, the method offers a robust, scale-invariant, and biologically plausible way to handle continuous data in graphical modeling. Future work may focus on further optimizing search complexity for high-dimensional "big data" applications.

Summary updated

Abstract

We present an approach to discretizing multivariate continuous data while learning the structure of a graphical model. We derive the joint scoring function from the principle of predictive accuracy...
BibTeX
@inproceedings{steck2004predictive,
  author = {Harald Steck and Tommi S. Jaakkola},
  title = {{Predictive Discretization during Model Selection}},
  booktitle = {DAGM-Symposium},
  year = {2004},
  doi = {10.1007/978-3-540-28649-3\_1},
}
Figure