No Free Lunch Theorem


One thing that loved about the first lecture in this module is that I brought me back a few years back in time when I was taking a stand alone course in Evolutionary Biology at Uppsala University in Sweden. It was a night course I took as I was working because the field have always interested me and I have read many books about the subject. My initial plan was to study biology and become a zoologist.
Many of the topics in this module fascinates me and I love when after all these years of technological innovations, we look back at nature and trying to simulate behaviour that we see others entities performing. Evolution has been around for so long that nature is pretty much bound to have figure some useful solutions for us.
By reading the paper on “No Free Lunch Theorem” I found it a bit hard to grasp the overall concept, specifically when you focus on the actual theorem about X being our countable search base and that you have to specify and objective function of f: X ->Y where Y is a proper subset of R as our countable set.. Gosh, too much for me to take in just by reading a plain text.


This can easily turn my head upside down when I am trying to grasp something new. I plowed through the paper, somewhat more confused as for when I started. By reading my notes and looking up additional information about the theorem, I think I managed to get some sort of grasp of it.
Let say that someone is actually offering you a “Free Lunch”, by doing this, he or she is most likely to want something in return for that “Free Lunch” he or she just offered you.
So there is an underlying trade-off for that “Free lunch”, very similar to how we use different machine learning classification algorithms.


The "No Free Lunch Theorem" is basically a formalisation of the fact that there is no learning algorithm that is inherently superior.
What I mean by that there is no inherently superior classifier is that there is no master algorithm that works for any given problem. You cannot get good performance on a certain problem without paying the price of a bad performance in another, so there is also a trade-off. There are many different methods to solve our problems but there is no method that dominates all others over all possible data sets.
I found an analogy that I liked and I found it to be useful for me to grasp the topic.

Imagine that we have a big room with a brand new wooden floor. The floor is representing all of our possible data sets. We can then lay any of our MLA ( machine learning algorithm ) on top of this floor as a carpet. There is no way to cover the whole floor with a single master MLA carpet.


There are good MLAs for a very specific task but this leads to that there will alway be some “blank” spots on our floor. Some MLAs will be subsets of each other and overlap be there will still not cover the whole floor.
That is why you might have to choose a specific algorithm for a specific task you want to explore to get the best possible outcome.


Resources

Comments

Post a Comment

Popular posts from this blog

Physical Computing, Final Project

Image
Physical Computing Final Project Technical Details For my final project, I have made a set of analog synthesizers. What I mean by analog is that I haven’t used any microcontrollers for this project. I will only be working with 9V batteries and a series of different IC’s ( Integrated circuits ). These are the IC chips I have used for my final build: CD4046 CD40106 CD4066 CD4017 LM386 The Synthesizer This is a very simple circuit that is generating a square wave. The small yellow 0.1uF capacitor is the capacitor that is setting the frequency range of the oscillator. The potentiometer is adjusting the fundamental frequency. First oscillator prototype This is how the oscillator sounds: https://youtu.be/j2es7WL2imU The next step is to add more effects to the synthesizer so it sounds a bit more interesting. Next I am setting up another oscillator using the CD40106 chip. The CD40106 is a Hex Schmitt Trigger or more eas
Read more

Extended DFO Experimentation

Image
This week we have continued working on our optimisation algorithm using DFO and the focus this week was to apply our DFO to a specific problem. The assigned problem for our DFO is to find the brightest pixels in an image. The image have replaced the sphere function I used in previous post. In this experiment I am generating a black and white image using perlin noise, I am using the continuous randomising image as my search space. This will make the search space dynamic and the flies will always try to find the brightest pixel. My initial idea was to use the webcam to move the brightest pixel around but I found this more aesthetically appealing. ( I'm a huge fan of perlin noise ) The calculation to get the brightest pixel is very simple, I iterate through all the flies in my population and I take the fly’s current position and subtracting the brightness value from that particular location from 255, which is the maximum brightness. This means that if the current pixel b
Read more

Dispersive Flies Optimisation ( DFO )

Image
Dispersive Flies Optimisation (DFO) is a global optimisation algorithm that is inspired by observing behaviour of swarming flies in the real world. The algorithm is going through a defined search space and it’s trying to find the most optimal value, which will converge the flies towards their target. We use the DFO to benchmark different test functions for our optimisation. The swarming behaviour of the flies optimisation is based on a value called ‘fitness’. This value judges how optimal the data is and based on the value of the ‘fitness’, it will attract the swarm of flies towards the new found optimal position. During the test of finding the most optimal fitness value, the algorithm is also applying random values to disburse the flies across the search space and away from the best fitness value. This is an attempt to further explore the search space and perhaps find a better potential fitness value. Together with Terry, we implemented the algorithm that was given to us in t
Read more