Hierarchical Reasoning about Inequalities

Elisha SacksAAAI 1987

TL;DR

This paper introduces BOUNDER, a system designed to prove inequalities between complex functions by utilizing a hierarchy of increasingly powerful algorithms. By trying fast, simple methods first and escalating to computationally expensive techniques only when necessary, BOUNDER achieves a balance of efficiency and precision that previous "one-size-fits-all" inequality provers lacked.

What Problem Does This Paper Address?

In fields like dynamic systems modeling and qualitative reasoning, researchers often need to prove whether one function is always less than or equal to another (e.g., $a \leq b$) given a set of constraints.

The challenge lies in the "brittleness" of existing tools. Simple methods, like standard interval arithmetic, are incredibly fast (linear time) but produce "loose" or overly pessimistic bounds because they ignore dependencies between variables. For example, if you know $a \leq b$, interval arithmetic might fail to prove $a - b \leq 0$ because it treats $a$ and $b$ as independent ranges. Conversely, powerful theorem provers can handle these dependencies but are often too slow (exponential time) to be practical for engineering utilities.

Elisha Sacks tackles this by asking: Can we build a system that is as fast as possible for easy problems, but powerful enough to handle the hard ones?

Methods

The core innovation of BOUNDER is its hierarchical strategy. It maintains four distinct algorithms, escalating through them if the previous one fails to resolve the inequality:

  1. Bounds Propagation (BP): An extension of interval arithmetic. It’s very fast (linear time) but ignores constraints between variables and multiple occurrences of the same variable.
  2. Substitution: A new, provably correct algorithm that accounts for constraints between variables. It works by replacing variables in an expression with their bounds derived from other variables.
  3. Derivative Inspection: This uses calculus to find extrema. By examining the signs of partial derivatives, the system can determine if a function is monotonic over a region, allowing it to collapse complex ranges into simple points.
  4. Iterative Approximation: A "divide and conquer" approach. It subdivides the variable ranges into smaller pieces, calculates bounds for each, and combines them. This reduces the error caused by multiple occurrences of variables.

BOUNDER handles "extended elementary functions," including polynomials, exponentials, logarithms, trigonometric functions, and absolute values.

Datasets

As a 1987 research paper in symbolic AI, it does not use modern large-scale datasets. Instead, the "data" consists of mathematical expressions and constraint sets derived from realistic modeling problems. The paper mentions that BOUNDER was integrated into and evaluated through two other programs:

  • PLR: A program for exploring the qualitative behavior of dynamic systems (like stability).
  • QMR: A program that derives qualitative properties of parameterized functions (like asymptotes and singularities).

Key Insights and Ideas

  • The "Sledgehammer" Problem: Most inequality provers are inefficient because they apply their most complex algorithm to every input. BOUNDER’s hierarchy ensures that easy problems are solved in linear time.
  • Variable Dependency is the Enemy: The paper highlights that the main reason simple solvers fail is the "multiple occurrence" problem. If $x$ appears twice in an equation, a simple solver doesn't "know" it's the same $x$, leading to mathematically impossible (but computationally loose) bounds.
  • Engineering vs. Pure Math: Sacks explicitly frames BOUNDER as an "engineering utility" rather than a pure math theorem prover. It focuses on universally quantified inequalities (the most common type in practice) while ignoring the complexities of arbitrary quantification.

Key Results

  • Superior Resolution: BOUNDER resolves more inequalities than any of its component algorithms could on their own.
  • Efficiency: By using the hierarchy, the system avoids wasting time on hard algorithms for easy problems.
  • Provable Correctness: The author provides a formal proof (Theorem 2) for the substitution algorithm, ensuring that the bounds it derives are always valid.
  • Practical Utility: The system successfully powered higher-level qualitative reasoning tools (PLR and QMR), proving its effectiveness in real-world modeling scenarios.

Limitations and Future Work

  • Computational Complexity: While the first step is linear, the subsequent algorithms (Substitution, Inspection, Iteration) are exponential in the worst case.
  • Quantification Limits: BOUNDER only handles universally quantified inequalities. It cannot reason about "there exists" ($\exists$) statements.
  • Equation Solving: The context manager’s ability to isolate variables is limited. The author notes that more powerful equation solvers (like the PRESS system) could potentially be integrated to allow BOUNDER to exploit even more constraints.
  • Heuristics for Iteration: The paper suggests that future work could involve better heuristics for deciding where to subdivide regions during iterative approximation to speed up convergence.

Summary updated

BibTeX
@inproceedings{sacks1987hierarchical,
  author = {Elisha Sacks},
  title = {{Hierarchical Reasoning about Inequalities}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure