Decomposable Probability-of-Success Metrics in Algorithmic Search

Tyler Sam, Jake Williams, Abel Tadesse, Huey Sun, George D. Montañez

Introduction

The "Machine Learning as Search" framework, pioneered by George Montañez in 2017, provides a rigorous mathematical foundation for understanding the inherent limits of induction. By viewing machine learning tasks—such as classification, clustering, or optimization—as search processes over a space of hypotheses, researchers can derive "laws of physics" for artificial intelligence. However, early iterations of this framework relied heavily on a specific metric: the expected per-query probability of success.

While useful, this metric averages performance over every iteration of an algorithm. This creates a gap in applicability for fields like transfer learning, where a researcher may only care about the probability of success at the final step rather than the average of the entire process. In "Decomposable Probability-of-Success Metrics in Algorithmic Search," the authors bridge this gap by introducing a broad class of "decomposable metrics," proving that the fundamental limits of machine learning apply far more broadly than previously understood.

The Concept of Decomposability

The core contribution of this paper is the mathematical generalization of success. The authors define a success metric as "decomposable" if it can be expressed as a linear operation—specifically, a dot product—between a target set vector and a probability distribution.

This definition leads to the "General Probability of Success" (GPS), a metric that allows researchers to assign different weights to different steps of a search. This flexibility is transformative:

  • Final-Step Success: By placing all weight on the final iteration, the GPS models scenarios like transfer learning.
  • Per-Query Success: By weighting all steps equally, the GPS recovers the original metrics used in prior search-based literature.

By establishing that linearity is the underlying requirement for these proofs, the authors demonstrate that the power of previous search-based theorems did not stem from the specific act of averaging, but from the decomposable nature of the metrics themselves.

The authors re-derive and generalize six major theoretical results, showing they hold true for any decomposable metric. These results define the boundaries of what is possible in algorithmic search:

  1. No Free Lunch for Search: Summed over all possible targets and information resources, the total success of any two algorithms is identical. No algorithm is globally superior.
  2. Fraction of Favorable Targets: For any fixed information resource, the set of targets where an algorithm performs significantly better than uniform random guessing is exponentially small.
  3. Famine of Forte: The proportion of "easy" problems (target-resource pairs) for any algorithm is strictly bounded and inversely related to the success threshold.
  4. Futility of Bias-Free Search: If an algorithm lacks a specific bias toward a target, its expected success is exactly equal to uniform random sampling, regardless of the decomposable metric used.
  5. Famine of Favorable Information Resources: For a fixed target, there are very few information resources (such as datasets or priors) that can actually assist an algorithm in succeeding.

Key Insights: Bias and Information

The paper reinforces the principle that performance is a conserved quantity. One of the most intuitive takeaways is that bias is mandatory. Using a parking lot analogy, the authors illustrate that without a specific alignment between an algorithm's predispositions and the actual target, success is no more likely than chance.

Furthermore, the paper establishes information-theoretic bounds on success. It shows that success is strictly limited by the mutual information between the target and the information resources available to the algorithm. If the resource does not contain sufficient information about the target, no decomposable metric—no matter how it is weighted—will show high success.

Limitations and Future Directions

As a theoretical work, this paper focuses on "impossibility results," defining the constraints of the field rather than providing a direct manual for algorithm design. The authors also note the existence of non-decomposable metrics—those created by non-convex combinations of decomposable ones—which are not covered by these specific bounds and represent an area for future exploration.

By providing this generalization, the authors have created a framework that allows researchers in sub-fields like reinforcement learning or meta-learning to develop niche success metrics and immediately apply these proven mathematical bounds to understand the theoretical limits of their work.

Summary updated

Abstract

Previous studies have used a specific success metric within an algorithmic search framework to prove machine learning impossibility results. However, this specific success metric prevents us from applying these results on other forms of machine learning, e.g. transfer learning. We define decomposable metrics as a category of success metrics for search problems which can be expressed as a linear operation on a probability distribution to solve this issue. Using an arbitrary decomposable metric to measure the success of a search, we demonstrate theorems which bound success in various ways, generalizing several existing results in the literature.
BibTeX
@misc{sam2020decomposable,
  author = {Tyler Sam and Jake Williams and Abel Tadesse and Huey Sun and George D. Montañez},
  title = {{Decomposable Probability-of-Success Metrics in Algorithmic Search}},
  year = {2020},
  eprint = {2001.00742},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.00742},
}
Figure