about
The Famine of Forte: Few Search Problems Greatly Favor Your Algorithm (2017) (arxiv.org)
1 point by optimalsolver on May 12, 2021 | hide | past | pdf | discuss on HN

In plain words: Treating machine learning as search, they prove mathematically that any fixed algorithm can only be good on a small fraction of all possible problems. The same rarity holds when the problem is fixed and you vary the way it searches, so no single method dominates.

Abstract · The Famine of Forte: Few Search Problems Greatly Favor Your Algorithm

Casting machine learning as a type of search, we demonstrate that the proportion of problems that are favorable for a fixed algorithm is strictly bounded, such that no single algorithm can perform well over a large fraction of them. Our results explain why we must either continue to develop new learning methods year after year or move towards highly parameterized models that are both flexible and sensitive to their hyperparameters. We further give an upper bound on the expected performance for a search algorithm as a function of the mutual information between the target and the information resource (e.g., training dataset), proving the importance of certain types of dependence for machine learning. Lastly, we show that the expected per-query probability of success for an algorithm is mathematically equivalent to a single-query probability of success under a distribution (called a search strategy), and prove that the proportion of favorable strategies is also strictly bounded. Thus, whether one holds fixed the search algorithm and considers all possible problems or one fixes the search problem and looks at all possible search strategies, favorable matches are exceedingly rare. The forte (strength) of any algorithm is quantifiably restricted.

George D. Montanez
arXiv:1609.08913 · stat.ML, cs.IT, cs.LG · submitted Sep 28, 2016 · updated Apr 19, 2017
abstract · pdf · html

add comment on HN
Also discussed: Dec 2024 (1 point, 0 comments)