HackerPapers

arXiv:1111.3846cs.LG

No Free Lunch versus Occam's Razor in Supervised Learning

Tor Lattimore, Marcus Hutter

Abstract

The No Free Lunch theorems are often used to argue that domain specific knowledge is required to design successful algorithms. We use algorithmic information theory to argue the case for a universal bias allowing an algorithm to succeed in all interesting problem domains. Additionally, we give a new algorithm for off-line classification, inspired by Solomonoff induction, with good performance on all structured problems under reasonable assumptions. This includes a proof of the efficacy of the well-known heuristic of randomly selecting training data in the hope of reducing misclassification rates.

arXiv comments
16 LaTeX pages, 1 figure
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.ITInformation Theory

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jul 2015 to Nov 2018.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Karl Friston: a neuroscientist who might hold the key to true AI 1 comment

    • The No Free Lunch Theorem is irrelevant to the real world [0][1]. It assumes all functions, even those with infinite algorithmic complexity, are equally likely. You should look into algorithmic probability for a better foundation. [0]…

      antidesitterView on HNParent context

  2. Is there a simple algorithm for intelligence? 1 comment

    • Solomonoff induction seems to be an useful innate bias for the current approaches at general intelligence. It's basically a formalization of Occam's razor that states that instead of being completely random, the surrounding environment is mostly lawful and simple, and therefore…

      rsaarelmView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.