Suppose that a learning algorithm is trying to find a consistent
hypothesis when the classifications of examples are actually random.
There are $n$ Boolean attributes, and examples are drawn uniformly from
the set of $2^n$ possible examples. Calculate the number of examples
required before the probability of finding a contradiction in the data
reaches 0.5.
Suppose that a learning algorithm is trying to find a consistent hypothesis when the classifications of examples are actually random. There are $n$ Boolean attributes, and examples are drawn uniformly from the set of $2^n$ possible examples. Calculate the number of examples required before the probability of finding a contradiction in the data reaches 0.5.