No Free Lunch Theorem!

[ML0to100] — S1E18

Sanidhya Agrawal
3 min readJun 11, 2020

A model is a simplified version of the observations. The simplifications are meant to discard the superfluous (unnecessary) details that are unlikely to generalize to new instances. To decide what data to discard and what data to keep, you must make assumptions. For example, a linear model makes the assumption that the data is fundamentally linear and that the distance between the instances and the straight line is just noise, which can safely be ignored.

In a famous 1996 paper, 11 David Wolpert demonstrated that if you make absolutely no assumption about the data, then there is no reason to prefer one model over any other.

This is called the No Free Lunch (NFL) theorem. For some datasets, the best model is a linear model, while for other datasets it is a neural network. There is no model that is a priori guaranteed to work better (hence the name of the theorem).

The only way to know for sure which model is best is to evaluate them all.

Since this is not possible, in practice you make some reasonable assumptions about the data and evaluate only a few reasonable models.

For example, for simple tasks, you may evaluate linear models with various levels of regularization, and for a complex problem, you may evaluate various neural networks.

Coming back to the lunch of it all, you can’t get good machine learning “for free.” You must use knowledge about your data and the context of the world we live in (or the world your data lives in) to select an appropriate machine learning model. There is no such thing as a single, universally-best machine learning algorithm, and there are no context or usage-independent (a priori) reasons to favor one algorithm over all others.

Read Next- Summary-1 S1(E1 to E18) [S1E19]

Summary Cheat Sheets, Notes, Flash Cards, Google Colab Notebooks, codes, etc will all be provided in further lessons as required.

Read through the whole ‘S1’ [ML0to100] series to learn about-

  • What Machine Learning is, what problems it tries to solve, and the main categories and fundamental concepts of its systems.
  • The steps in a typical Machine Learning project
  • Learning by fitting a model to data
  • Optimizing a cost function
  • Handling, cleaning and preparing data
  • Selecting and engineering features
  • Selecting a model and tuning hyperparameters using cross-validation
  • The challenges of Machine Learning, in particular, underfitting and overfitting (the bias/variance trade-off)
  • The most common learning algorithms: Linear and Polynomial Regression, Logistic Regression, k-Nearest Neighbors, Support Vector Machines, Decision Trees, Random Forests, and Ensemble methods
  • Reducing the dimensionality of the training data to fight the “curse of dimensionality”
  • Other unsupervised learning techniques, including clustering, density estimation, and anomaly detection Part II, Neural Networks and Deep Learning, covers the following topics:
  • What neural nets are and what they’re good for building and training neural nets using TensorFlow and Keras
  • The most important neural net architectures: feedforward neural nets for tabular data, convolutional nets for computer vision, recurrent nets and long short-term memory (LSTM) nets for sequence processing, encoder/decoders, and Transformers for natural language processing, autoencoders and generative adversarial networks (GANs) for generative learning
  • Techniques for training deep neural nets
  • How to build an agent (e.g., a bot in a game) that can learn good strategies through trial and error, using Reinforcement Learning
  • Loading and preprocessing large amounts of data efficiently
  • Training and deploying TensorFlow models at scale

Disclaimer — This series is based on the notes that I created for myself based on various books I’ve read, so some of the text could be an exact quote from some book out there, I’d have mentioned the book but even I don’t know which book a paragraph belongs to as it’s a compilation. It’s best for the reader as they get the best out of the all promising books available in the market for ML compiled in one place.

--

--