Stochastic Search and Phase Transitions: AI Meets Physics

Bart SelmanIJCAI 1995 · OpenReview

TL;DR

This paper explores the phenomenon of "phase transitions" in computationally hard problems, where problem instances become drastically more difficult to solve at a specific ratio of constraints to variables. By drawing parallels with physics, the authors demonstrate how understanding these critical regions has led to the development of powerful new stochastic search algorithms that outperform traditional methods on these hard instances.

What Problem Does This Paper Address?

Many problems in Artificial Intelligence, such as planning, reasoning, and learning, are known to be computationally intractable in the worst-case scenario. While average-case analysis offers a more practical perspective, it often relies on simplified models of problem instance distributions, which can lead to the misleading conclusion that most problems are easy. This paper addresses the gap in understanding why certain problem instances are exceptionally hard, even when generated randomly. The authors highlight that these "critically constrained" instances, occurring at a specific balance of constraints and variables, exhibit dramatic shifts in difficulty, mirroring phase transitions observed in physics. The challenge is to understand this phenomenon and leverage it to develop more effective AI algorithms.

Methods

The paper draws a strong analogy between the difficulty of combinatorial problems and phase transitions in statistical physics. The core methodological contribution lies in:

  • Identifying Critical Ratios: The authors demonstrate that for problems like graph coloring and Boolean satisfiability (SAT), there exists a critical ratio of constraints to variables where the computational cost of solving instances spikes dramatically. This is often referred to as the "phase transition region."
  • Finite-Size Scaling: To analyze these transitions, the paper employs techniques from statistical mechanics, specifically "finite-size scaling." This method involves rescaling the data to "slow down" the transition, allowing for a clearer examination of the behavior at different problem sizes and the identification of the hardest instances.
  • Stochastic Search Algorithms (GSAT): Based on the insights gained from understanding these hard instances, the paper introduces and discusses stochastic search methods, particularly GSAT (Greedy SAT). Unlike systematic search, GSAT uses randomized local search, starting with a random assignment and iteratively flipping variables to reduce unsatisfied clauses.
  • Noise Strategies (Biased Random Walk): To further enhance GSAT's performance on hard instances, the paper explores introducing "noise" into the search process. The "biased random walk" strategy, which occasionally makes non-greedy moves, is shown to be particularly effective.

Datasets

The paper primarily uses randomly generated problem instances for evaluation, specifically:

  • Random 3-Coloring Problems: Used to illustrate the phase transition phenomenon in graph coloring.
  • Random 3-CNF (Conjunctive Normal Form) Formulas: These are generated using a "fixed-clause-length model" where each clause has a fixed number of literals. This model is crucial for generating instances that fall within the critical region and are thus computationally hard.
  • SAT encodings of graph coloring problems: Used to compare GSAT's performance against other methods.

The authors emphasize that these randomly generated instances, particularly those in the critical region, are not just benchmarks but are representative of the challenges faced by algorithms on more structured, real-world problems, as suggested by the DIMACS Challenge results.

Key Insights and Ideas

  • "Critically Constrained" Problems: The most significant insight is that computational hardness in many AI problems isn't uniformly distributed but is concentrated in a narrow "critical region" defined by a specific ratio of constraints to variables.
  • Physics as a Model for AI Complexity: The paper powerfully demonstrates that concepts and tools from statistical physics, like phase transitions and finite-size scaling, are directly applicable to understanding computational complexity in AI. This provides a theoretical framework for why certain problems are hard.
  • Hard Instances as Predictors of Algorithm Performance: The performance of algorithms on these carefully constructed "hard random instances" is a good indicator of their performance on more structured, real-world problems. This validates the use of random generation for algorithm development and benchmarking.
  • Stochastic Search as a Viable Alternative: The research shows that stochastic search methods, like GSAT, can effectively tackle these critically constrained problems, often outperforming traditional systematic search methods, especially for large instances.
  • The Power of Noise: Introducing controlled randomness ("noise") into search algorithms, as seen in the biased random walk, can help them escape local optima and find solutions in difficult problem landscapes.

Key Results

  • Exponential Cost at the Critical Ratio: For problems like 3SAT, the average computational cost of solving instances scales exponentially with problem size when instances are generated at the critical ratio of clauses to variables (around 4.3 clauses per variable).
  • GSAT Outperforms Davis-Putnam: GSAT, a stochastic local search algorithm, significantly outperforms the Davis-Putnam procedure (a systematic backtracking algorithm) on various classes of hard random formulas and graph coloring encodings.
  • Biased Random Walk's Superiority: The biased random walk variant of GSAT demonstrates substantial improvements, enabling the solution of hard random instances with over 2000 variables, a scale currently unmanageable for the best systematic methods.
  • Real-world Relevance: The paper suggests that critically constrained problems are not just theoretical constructs but can arise naturally in real-world applications like airline scheduling, where economic factors can lead to such problem structures.

Limitations and Future Work

  • Incompleteness of Stochastic Methods: The authors acknowledge that stochastic search methods like GSAT are inherently incomplete. If they fail to find a solution, it doesn't prove that no solution exists, making them unsuitable for theorem proving but potentially useful for model finding.
  • Need for More Structured Problem Generation: While random instances are useful, the paper hints at the need for better models that capture the "deep structure" of real-world problems to further test and refine algorithms.
  • Exploring Proof Space: An interesting future direction suggested is the possibility of devising randomized local search methods that directly explore the "space of proofs" rather than just the space of assignments.
  • Broader Applications: The paper advocates for encoding AI tasks as model-finding problems, suggesting that stochastic search methods could be applied to planning, abduction, and default reasoning.

Summary updated

Abstract

Computationally hard instances of combinatorial problems arise at a certain critical ratio of constraints to variables. At the critical ratio, problem distributions undergo dramatic changes. I will discuss how an analogous phenomenon occurs in phase transitions studied in physics, and how experiments with critically constrained problems have led to surprising new insights into average-case complexity and stochastic search methods in AI.
BibTeX
@inproceedings{selman1995stochastic,
  author = {Bart Selman},
  title = {{Stochastic Search and Phase Transitions: AI Meets Physics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
  url = {https://openreview.net/forum?id=ryWFbEMObr},
}
Figure