Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference

Tudor Achim, Ashish Sabharwal, Stefano ErmonICML 2016 · OpenReview

Overview

Probabilistic inference—calculating expectations or normalization constants like partition functions—is a cornerstone of machine learning. However, it is often computationally intractable, falling into the #P-complete complexity class. This paper introduces a general framework using Fourier analysis of Boolean functions to design and analyze hash functions for probabilistic inference. By moving beyond traditional, hard-to-optimize parity constraints (XORs), the authors introduce two new hash families—TRIBES and MAJORITY—that provide accurate lower bounds for partition functions and model counting while running up to two orders of magnitude faster than existing methods.

The Bottleneck in Hashing-Based Inference

A powerful modern approach to intractable inference involves hashing-based inference. By using random projections (hash functions) to "slice" a high-dimensional distribution into smaller buckets, researchers can turn a difficult counting problem into a series of easier optimization problems (MAP queries).

Almost all current algorithms rely on parity constraints (random XOR equations) for this hashing. While XORs have excellent statistical properties and are considered "universal," they are notoriously difficult for optimization solvers. They are highly oscillatory and non-convex, meaning that as the problem size grows, the supposedly "easier" optimization sub-problems become impossibly slow to solve. The authors ask: Can we find hash functions that are easier for solvers to handle but still statistically sound?

Methodology: A Fourier Framework for Hashing

The authors bridge the gap between theoretical computer science and practical inference using several key innovations:

  1. Fourier Analysis Framework: They demonstrate that the statistical "quality" of a hash function (specifically its variance and clash probability) is directly related to its Fourier spectrum. Functions with Fourier mass concentrated on high-order coefficients are more "noise-sensitive," meaning they mix the input space better—a highly desirable trait for hashing.
  2. Templated Hash Families: They propose a method to take any Boolean function (a "template") and turn it into a family of hash functions using signed permutations of the input variables.
  3. New Hash Templates: They introduce two specific templates based on monotone Boolean functions, which are generally much easier for SAT and MAP solvers to process than XORs:
  4. TRIBES: A Disjunctive Normal Form (DNF) formula that checks if any "coalition" of variables are all true.
  5. MAJORITY: Returns true if more than half of the input bits are true.
  6. THF-WISH-LB Algorithm: A modified version of the WISH (Weighted Inference Search and Hashing) algorithm designed to use these new templates to find lower bounds on the partition function.

Key Insights

  • Monotonicity is the Key to Speed: Unlike XORs, which flip output values frequently, TRIBES and MAJORITY are monotone functions. This structural simplicity allows modern combinatorial solvers to prune the search space much more effectively, leading to massive speedups.
  • Noise Sensitivity as a Metric: The paper formalizes the idea that we don't need "perfect" universal hashing for inference. By calculating the noise sensitivity of a function via its Fourier coefficients, we can predict exactly how well it will perform as a hash function before ever running an experiment.
  • The Lower Bound Trade-off: XORs are theoretically optimal for providing both upper and lower bounds, but the practical bottleneck is solver time. By sacrificing the ability to provide tight upper bounds, the authors gained the ability to compute useful lower bounds on problems that were previously untouchable.

Experimental Results

The authors evaluated their approach on Grid Ising Models and real-world CNF formulas, demonstrating significant improvements in speed without sacrificing lower-bound accuracy.

Accuracy on Grid Ising Models

On $15 \times 15$ grid Ising models, the MAJORITY-WISH approach solved MAP queries in an average of 1.2 seconds, compared to 30–60 seconds for sparse XOR constraints. Despite being easier to solve, MAJORITY-WISH recovered the true log-partition function almost exactly, performing as well as or better than Sparse-WISH across various coupling strengths.

Log partition function estimation error vs. coupling strength for various methods.

Model Counting Performance

In real-world SAT benchmarks (including Latin squares, hardware verification, and logistic planning), the TRIBES template produced lower bounds that were comparable to XOR-based bounds but were 1 to 2 orders of magnitude faster to compute. In several instances, XOR-based methods timed out (failing to find a solution within 15 minutes), while TRIBES provided a bound in seconds.

Comparison of lower bounds and computation times for TRIBES and XOR templates on real-world SAT benchmarks.

Limitations and Future Work

The primary limitation of this approach is that these new hash functions are not "universal" enough to provide high-probability upper bounds; they are currently optimized strictly for lower bounds. Additionally, while TRIBES and MAJORITY work well, the framework allows for any Boolean function, suggesting that even better, problem-specific templates may exist. Future work could also involve more tightly integrating the hash function structure into the internal heuristics of SAT/MAP solvers to further increase efficiency.

Summary updated

Abstract

Random projections have played an important role in scaling up machine learning and data mining algorithms. Recently they have also been applied to probabilistic inference to estimate properties of...
BibTeX
@inproceedings{achim2016beyond,
  author = {Tudor Achim and Ashish Sabharwal and Stefano Ermon},
  title = {{Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference}},
  booktitle = {International Conference on Machine Learning},
  year = {2016},
  url = {https://openreview.net/forum?id=r1bqwjb_bH},
}
Figure