Iterative Weakening: Optimal and Near-Optimal Policies for the Selection of Search Bias

Foster J. ProvostAAAI 1993

Abstract

The selection of an appropriate search bias—defining the boundaries and rules of a search space—is a fundamental challenge in artificial intelligence. Choosing a bias that is too restrictive leads to failure, while one that is too permissive results in computational intractability. This paper formalizes "Iterative Weakening" (IW), a strategy that evaluates biases in order of increasing complexity. We prove that for common search scenarios, particularly those with exponential complexity, IW is asymptotically as efficient as an "oracle" policy that identifies the optimal bias a priori. We extend these results to polynomial and multi-dimensional search spaces, demonstrating the robustness of the "cheapest-first" approach.

Introduction

In artificial intelligence, a "search bias" defines the boundaries of a search space and the rules for navigating it. For example, in machine learning, a bias might be the maximum number of terms allowed in a rule; in game playing, it might be the maximum depth of a move-tree. The challenge is that we rarely know the "right" bias ahead of time. If we choose a bias that is too restrictive (too "strong"), we won't find a solution. If we choose one that is too permissive (too "weak"), the search might take forever. Researchers often face a "meta-search" problem: how do we navigate the space of possible biases to find the one that yields a solution most efficiently?

The Iterative Weakening Policy

The paper treats bias selection as a higher-level state-space search where each "state" is a specific bias. The author introduces Iterative Weakening (IW), a policy that evaluates these biases in order of increasing computational complexity. This is a generalization of well-known techniques like iterative deepening (increasing search depth) and iterative broadening (increasing the number of branches considered).

Theoretical Analysis of Optimality

The paper provides mathematical proofs for the asymptotic optimality of IW across several complexity functions. The "aha moment" of the paper is that if the cost of searching increases exponentially as you weaken the bias, the cost of the final successful search will dwarf the sum of all previous failed attempts. Therefore, "knowing" the right bias in advance doesn't actually save you much time in the long run.

Summation logic demonstrating the dominance of the final search cost in exponential complexity scenarios.

Single-dimensional Spaces

  • Exponential Optimality: For searches with exponential complexity $O(b^i)$, IW is asymptotically optimal. It performs within a constant factor of a strategy that knows the correct bias a priori.
  • Polynomial Near-Optimality: For polynomial complexity $O(i^d)$, IW is near-optimal, staying within a $d$-th root factor of the ideal.

Multi-dimensional and Complex Spaces

For complex problems involving both breadth ($b$) and depth ($d$), the paper shows you can "collapse" the two-dimensional search into a single dimension (using the metric $k = d \log b$) to maintain near-optimal performance. In multi-dimensional cases (like dual searches or nested searches), IW is typically within a log factor of optimal ($O(N \log N)$).

Key Insights and Implications

  • Relative Growth Principle: IW is most effective when the complexity of the tasks grows much faster than the number of possible biases at that complexity level. If there are too many different ways to "weaken" a search at the same cost level, IW can become inefficient.
  • Heuristics vs. Bias Selection: A major implication is that if your problem fits these complexity profiles, it is a better investment to spend time developing domain-specific heuristics to reduce the underlying search complexity than to spend time building a complex system to "intelligently" pick the right bias.

Limitations

The proofs assume that a search with one bias provides no useful information for a search with a different bias. In reality, many systems use "caching" or "memoization" to carry over work. Furthermore, IW fails if the number of equivalent-complexity biases grows too rapidly (e.g., if there are an exponential number of ways to configure a search at a certain cost level).

Summary updated

BibTeX
@inproceedings{provost1993iterative,
  author = {Foster J. Provost},
  title = {{Iterative Weakening: Optimal and Near-Optimal Policies for the Selection of Search Bias}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure