PhilSci Archive

Absolutely No Free Lunches!

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

[img]
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:
CreatorsEmailORCID
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: https://doi.org/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-dev.library.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 View Item