Belot, Gordon (2020) Absolutely No Free Lunches! [Preprint]

Preview

Text GoodLunch.pdf Download (378kB) | Preview

Abstract

This paper is concerned with learners who aim to learn patterns in infinite binary sequences: shown longer and longer initial segments of a binary sequence, they either attempt to predict whether the next bit will be a 0 or will be a 1 or they issue forecast probabilities for these events. Several variants of this problem are considered. In each case, a no-free-lunch result of the following form is established: the problem of learning is a formidably difficult one, in that no matter what method is pursued, failure is incomparably more common that success; and difficult choices must be faced in choosing a method of learning, since no approach dominates all others in its range of success. In the simplest case, the comparison of the set of situations in which a method fails and the set of situations in which it succeeds is a matter of cardinality (countable vs. uncountable); in other cases, it is a topological matter (meagre vs. co-meagre) or a hybrid computational-topological matter (effectively meagre vs. effectively co-meagre).

---

Export/Citation:

EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL

Social Networking:

Share |

---

Item Type:	Preprint
Creators:	Creators Email ORCID Belot, Gordon
Keywords:	Induction, Learning, Extrapolation, Forecasting, No-Free-Lunch Theorems
Subjects:	Specific Sciences > Computer Science General Issues > Confirmation/Induction Specific Sciences > Probability/Statistics
Depositing User:	Gordon Belot
Date Deposited:	14 Sep 2020 14:38
Last Modified:	14 Sep 2020 14:38
Item ID:	18094
DOI or Unique Handle:	10.1016/j.tcs.2020.09.013
Subjects:	Specific Sciences > Computer Science General Issues > Confirmation/Induction Specific Sciences > Probability/Statistics
Date:	11 September 2020
URI:	https://philsci-archive.pitt.edu/id/eprint/18094

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Altmetric.com

Actions (login required)

View Item