Knowledge Inversion

Yoav Shoham, Drew V. McDermottAAAI 1984

Introduction

In a seminal 1984 paper from Yale University, Yoav Shoham and Drew McDermott explored a fundamental asymmetry in computation: why is it significantly easier to perform an action than to undo it? While a programmer can easily write a routine to sort a list, creating a program that takes a sorted list and generates all possible original permutations is a much more complex task. Shoham and McDermott proposed a framework for "Knowledge Inversion"—a method to automatically transform "one-way" procedural knowledge into multi-directional relations.

The Problem of Directed Knowledge

In theory, logic programming languages like Prolog are designed to be "declarative." A program should define a relationship, and the execution engine should be able to solve for any variable regardless of which are provided as inputs. However, the authors argue this is often an "optical illusion." In practice, factors such as execution order, arithmetic operations, and side effects make most Prolog programs "directed" functions. For instance, running a standard Quicksort algorithm "backwards" to find the source lists for a sorted output typically results in an interpreter crash or an infinite loop. The goal of Knowledge Inversion is to bridge this gap, allowing code written for one purpose to solve its inverse problem.

Methodology: Three Algorithms for Inversion

The authors developed three primary heuristic algorithms to automate the inversion process:

  1. Algorithm 1 (Simple Inversion): This naive approach attempts to reverse the order of conjuncts within a goal. If a procedure is defined as "Do A then B," the inverter attempts to execute "Do B then A."
  2. Algorithm 2 (Pragmatic Inversion): An extension designed to handle Prolog’s "extra-logical" features. It includes specific rules for inverting arithmetic (e.g., transforming A is B + C into B is A - C) and manages side effects like assert and retract by swapping their operations.
  3. Algorithm 3 (Interactive Inversion): Recognizing that automated inversion often leads to infinite recursion, this semi-automated approach traverses the computation tree and requests user guidance to prune or pursue specific branches. This effectively "compiles" a safe, user-verified inverse function.

While Breadth-First Search (BFS) offers a theoretically "complete" solution for finding inverses, the authors dismiss it as computationally impractical for real-world applications.

Evaluation and Symbolic Logic

As a theoretical AI study from the mid-1980s, the paper evaluates these algorithms using classic symbolic logic problems rather than modern datasets:

  • Quicksort: Inverting the sorting process to generate permutations.
  • FAME II: A system for solving combinatorial counting problems (e.g., determining the number of ways to select a team).
  • Gensym: A standard utility for generating unique symbols.
  • Regular Language Recognizers: Programs that validate strings against specific patterns, such as $(a+b)^*c$.

Key Insights: Entropy and Directionality

The authors posit that most human and machine knowledge is inherently directed; we possess manuals for assembly but rarely for disassembly. A successful inverse must maintain "fairness"—the guarantee that any valid input can be found in a finite amount of time without getting trapped in infinite search branches.

A significant barrier to inversion is arithmetic, which standard languages treat as functions rather than relations. Furthermore, drawing on the work of Toffoli, the authors suggest that "information loss" (entropy) is the primary obstacle. If a function is not injective (where multiple inputs produce the same output), inversion requires the re-introduction of "redundant" information.

Results and Limitations

The research yielded several key successes:

  • Permutation Generation: Using Algorithm 2, the authors successfully inverted Quicksort. When prompted with a sorted list like [1, 2, 3], the system correctly generated all six original permutations.
  • Combinatorial Synthesis: By inverting a "counting" program, they performed "problem synthesis." Given a mathematical formula, the inverted program could describe the specific word problem the formula was designed to solve.

However, the heuristic approach has clear limits. Algorithms 1 and 2 failed on simple regular languages, unable to generate strings ending in 'c' without a more robust search strategy. The primary hurdle remains the "halting problem" equivalent in search trees, where inverters fall into infinite loops that the original forward programs avoided.

Future Directions

The authors conclude that future work must address the "ad-hoc" nature of current arithmetic handling, perhaps through integration with symbolic algebra engines. Additionally, they suggest that making implicit program constraints (like variable types) explicit and measuring "computational entropy" will be critical for determining the inherent difficulty of inverting any given procedure.

Summary updated

BibTeX
@inproceedings{shoham1984knowledge,
  author = {Yoav Shoham and Drew V. McDermott},
  title = {{Knowledge Inversion}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}

Loading related content...

Figure