Estimating Jaccard Index with Missing Observations: A Matrix Calibration Approach

Wenye LiNeurIPS 2015 · OpenReview

Introduction

When data samples are riddled with missing values, calculating their similarity using the Jaccard index becomes a guessing game. The Jaccard index is a gold standard for measuring similarity between binary sets (e.g., "Does this document contain the same keywords as that one?"). However, in the real world, data is often incomplete. If you are comparing two users' preferences but only see 20% of their history, your Jaccard estimate will be noisy and mathematically "broken"—specifically, the resulting similarity matrix often loses the property of being positive semi-definite (PSD), which is required by many downstream algorithms.

Traditional solutions rely on imputation: filling in the blanks with zeros, means, or using complex models like Expectation-Maximization (EM). The authors argue that when the "missingness" is high (e.g., 70-90% of data is gone), imputation becomes unreliable or computationally prohibitive.

This paper asks: Can we find a better estimate by fixing the matrix itself rather than the underlying data? To answer this, the authors propose a "Matrix Calibration" approach. Instead of trying to fill in missing data points, it calculates an approximate similarity matrix and then mathematically "corrects" it to satisfy known properties like positive semi-definiteness.

Methodology

The authors introduce a two-step framework:

  1. Initial Approximation: They calculate an initial Jaccard matrix ($J^0$) using only the observed features. They also derive a "feasibility interval" $[\ell_{ij}, \mu_{ij}]$ for every pair of samples, representing the absolute minimum and maximum possible Jaccard values if the missing data were revealed.
  2. Matrix Calibration via Dykstra’s Algorithm: They treat the estimation as a convex optimization problem. They seek a matrix $J$ that is as close as possible to $J^0$ (in Frobenius norm) while satisfying two sets of constraints:
  3. Set S: The matrix must be positive semi-definite ($J \succeq 0$).
  4. Set T: Every element must fall within its pre-calculated feasibility interval ($\ell_{ij} \le J_{ij} \le \mu_{ij}$).

To find the intersection of these two sets, they use Dykstra’s alternating projection algorithm. This involves repeatedly projecting the matrix onto the "PSD cone" (via Eigen-decomposition) and then clipping the values to fit the intervals until the matrix converges to a valid solution.

Key Insights

  • The Geometric Guarantee: The most powerful insight is Theorem 2. It proves that by projecting an approximate matrix onto the feasible region (the set of all mathematically "valid" Jaccard matrices), the resulting calibrated matrix is guaranteed to be closer to the unknown ground truth than the uncalibrated one. Imputation methods offer no such guarantee.
  • Moving Beyond Data Filling: The paper shifts the focus from "guessing the data" to "enforcing mathematical consistency." By ensuring the similarity matrix behaves like a proper kernel, the authors bypass the noise introduced by bad imputations.
  • Interval Constraints: By calculating the best-case and worst-case Jaccard values for missing data, they create "guardrails" that prevent the optimization from drifting into unrealistic values.

Experimental Results

The method was evaluated on four diverse benchmark datasets, binarized for Jaccard analysis: MNIST (784 features), USPS (256 features), PROTEIN (357 features), and WEBSPAM (over 16 million features).

Closer to Truth

In experiments with 1,000 and 10,000 samples, the "CALIBRATION" method consistently achieved the lowest Mean Square Deviation from the ground truth across all datasets.

Mean Square Deviation across datasets

The advantage was most pronounced when data was extremely sparse. Even when 90% of the features were missing, the calibration approach maintained a low error rate, while imputation methods (like kNN or Zero-filling) saw their errors spike.

Downstream Success

When used for a k-Nearest Neighbor (kNN) classification task, the calibrated matrix led to significantly lower classification errors.

Classification Error across datasets

For example, on the MNIST dataset with 80% missing data, the calibration approach cut the error rate nearly in half compared to standard imputation.

Limitations and Future Work

  • Computational Complexity: The primary bottleneck is the need for successive matrix decompositions (SVD or Eigen-decomposition) within the iterative loop. While it handles 1,000 samples in seconds, 10,000 samples can take over an hour.
  • Scalability: The authors briefly mention a "divide-and-conquer" heuristic to handle larger matrices by breaking them into sub-matrices, but they note this is a direction for further investigation.
  • Faster Solvers: The paper suggests that investigating more advanced optimization techniques (like quasi-Newton methods) could make the calibration process faster for massive datasets.

Summary updated

Abstract

The Jaccard index is a standard statistics for comparing the pairwise similarity between data samples. This paper investigates the problem of estimating a Jaccard index matrix when there are missing observations in data samples. Starting from a Jaccard index matrix approximated from the incomplete data, our method calibrates the matrix to meet the requirement of positive semi-definiteness and other constraints, through a simple alternating projection algorithm. Compared with conventional approaches that estimate the similarity matrix based on the imputed data, our method has a strong advantage in that the calibrated matrix is guaranteed to be closer to the unknown ground truth in the Frobenius norm than the un-calibrated matrix (except in special cases they are identical). We carried out a series of empirical experiments and the results confirmed our theoretical justification. The evaluation also reported significantly improved results in real learning tasks on benchmarked datasets.
BibTeX
@inproceedings{li2015estimating,
  author = {Wenye Li},
  title = {{Estimating Jaccard Index with Missing Observations: A Matrix Calibration Approach}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=BkXbddZObB},
}
Figure