Skip navigation
Skip navigation
Open Research will be down for maintenance between 8:00 and 8:15 am on Tuesday, December 1 2020.

No Free Lunch versus Occam’s Razor in supervised learning

Lattimore, Tor; Hutter, Marcus

Description

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 (compressible) problems under reasonable assumptions. This includes a proof of the...[Show more]

dc.contributor.authorLattimore, Tor
dc.contributor.authorHutter, Marcus
dc.date.accessioned2015-08-19T05:42:55Z
dc.date.available2015-08-19T05:42:55Z
dc.identifier.isbn978-3-642-44957-4
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/1885/14800
dc.description.abstractThe 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 (compressible) 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 the misclassification rate.
dc.publisherSpringer Verlag
dc.relation.ispartofAlgorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence: Papers from the Ray Solomonoff 85th Memorial Conference, Melbourne, VIC, Australia, November 30 – December 2, 2011
dc.rights© Springer-Verlag Berlin Heidelberg 2013. http://www.sherpa.ac.uk/romeo/issn/0302-9743/..."Author's post-print on any open access repository after 12 months after publication" from SHERPA/RoMEO site (as at 19/08/15)
dc.subjectSupervised Learning
dc.subjectKolmogorov complexity
dc.subjectOccam's Razor
dc.subjectNo Free Lunch
dc.titleNo Free Lunch versus Occam’s Razor in supervised learning
dc.typeConference paper
local.identifier.citationvolume7070
dc.date.issued2011-11
local.type.statusAccepted Version
local.contributor.affiliationLattimore, T., Research School of Computer Science, The Australian National University
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National University
dc.relationhttp://purl.org/au-research/grants/arc/DP0988049
local.bibliographicCitation.startpage223
local.bibliographicCitation.lastpage235
local.identifier.doi10.1007/978-3-642-44958-1_17
CollectionsANU Research Publications

Download

File Description SizeFormat Image
Lattimore and Hutter No Free Lunch versus 2011.pdf130.81 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator