A program that demonstrates the No Free Lunch theorem for machine learning.
Let the domain be the integers from 1 to 10, and let the size of the example dataset be m = 4. Define the learning algorithm as an algoritm that inputs a subset of size m of our domain and randomly outputs a binary classifier. aka: let A be a "random" algorithm, S denote a subset of size m, f_i denote a binary classifier. Note that A maps S to f_i: A(S) = f_i where f_i assigns a value of 1 or 0 to each integer x in the domain.
In code:
def random_algo(S):
rand.seed(hash(tuple(S))):
i = rand.randint(0, 2 ** len(DOMAIN))
return f_from_int(i, DOMAIN)
If we run the no_free_lunch(algo, size)
on this random algorithm and size = 4:
Our program would output:
- A distribution D in which there exists a function with zero loss on D:
- Distribution formatting: ({x in domain}, f(x)): probability(({x in domain}, f(x)))
- {(1, 0): 0, (1, 1): 0, (2, 0): 0, (2, 1): 0, (3, 1): 0.25, (3, 0): 0, (4, 0): 0.25, (4, 1): 0, (5, 0): 0.25, (5, 1): 0, (6, 0): 0, (6, 1): 0, (7, 0): 0, (7, 1): 0, (8, 0): 0, (8, 1): 0, (9, 1): 0.25, (9, 0): 0, (10, 0): 0, (10, 1): 0}
- The function that has zero loss on D:
- Function formatting: (x in domain): f(x)
- {1: 1, 2: 1, 3: 1, 4: 0, 5: 0, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}
- And expected loss of algo(S), where S is drawn from D (Should be greater than ΒΌ)
- example expected loss: 0.7083333333333333