Related papers: The no-free-lunch theorems of supervised learning

The no-free-lunch theorems of supervised learning

URL: http://arxiv.org/abs/2202.04513v1
Date: Wed, 9 Feb 2022 15:24:30 GMT
Title: The no-free-lunch theorems of supervised learning
Authors: Tom F. Sterkenburg, Peter D. Gr\"unwald
Abstract summary: The no-free-lunch theorems promote a skeptical conclusion that all possible machine learning algorithms equally lack justification. We argue that many standard learning algorithms should rather be understood as model-dependent.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The no-free-lunch theorems promote a skeptical conclusion that all possible machine learning algorithms equally lack justification. But how could this leave room for a learning theory, that shows that some algorithms are better than others? Drawing parallels to the philosophy of induction, we point out that the no-free-lunch results presuppose a conception of learning algorithms as purely data-driven. On this conception, every algorithm must have an inherent inductive bias, that wants justification. We argue that many standard learning algorithms should rather be understood as model-dependent: in each application they also require for input a model, representing a bias. Generic algorithms themselves, they can be given a model-relative justification.

Related papers

Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
arXiv Detail & Related papers (2024-11-29T05:29:47Z)
Reciprocal Learning [0.0]
We show that a wide array of machine learning algorithms are specific instances of one single paradigm: reciprocal learning. We introduce reciprocal learning as a generalization of these algorithms using the language of decision theory. We find that reciprocal learning algorithms converge at linear rates to an approximately optimal model under relatively mild assumptions on the loss function.
arXiv Detail & Related papers (2024-08-12T16:14:52Z)
Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
arXiv Detail & Related papers (2024-08-10T06:16:24Z)
FRRI: a novel algorithm for fuzzy-rough rule induction [0.8575004906002217]
We introduce a novel rule induction algorithm called Fuzzy Rough Rule Induction (FRRI) We provide background and explain the workings of our algorithm. We find that our algorithm is more accurate while creating small rulesets.
arXiv Detail & Related papers (2024-03-07T12:34:03Z)
The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
We argue that neural network models share this same preference, formalized using Kolmogorov complexity. Our experiments show that pre-trained and even randomly language models prefer to generate low-complexity sequences. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.
arXiv Detail & Related papers (2023-04-11T17:22:22Z)
Adversarial Learning to Reason in an Arbitrary Logic [5.076419064097733]
Existing approaches to learning to prove theorems focus on particular logics and datasets. We propose Monte-Carlo simulations guided by reinforcement learning that can work in an arbitrarily specified logic.
arXiv Detail & Related papers (2022-04-06T11:25:19Z)
Bayesian Inference Forgetting [82.6681466124663]
The right to be forgotten has been legislated in many countries but the enforcement in machine learning would cause unbearable costs. This paper proposes a it Bayesian inference forgetting (BIF) framework to realize the right to be forgotten in Bayesian inference.
arXiv Detail & Related papers (2021-01-16T09:52:51Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z)
A Theory of Universal Learning [26.51949485387526]
We show that there are only three possible rates of universal learning. We show that the learning curves of any given concept class decay either at an exponential, or arbitrarily slow rates.
arXiv Detail & Related papers (2020-11-09T15:10:32Z)
RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs [91.71504177786792]
This paper studies learning logic rules for reasoning on knowledge graphs. Logic rules provide interpretable explanations when used for prediction as well as being able to generalize to other tasks. Existing methods either suffer from the problem of searching in a large search space or ineffective optimization due to sparse rewards.
arXiv Detail & Related papers (2020-10-08T14:47:02Z)
What is important about the No Free Lunch theorems? [0.5874142059884521]
The No Free Lunch theorems prove that under a uniform distribution over induction problems, all induction algorithms perform equally. The importance of the theorems arises by using them to analyze scenarios involving non-uniform' distributions. They also motivate a dictionary'' between supervised learning and improve blackbox optimization.
arXiv Detail & Related papers (2020-07-21T16:42:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.