In Chapter 1 of Kubat's An Introduction to Machine Learning he introduces the problem of classifying pies as positive or negative based on $5$ attributes, with $3, 2, 3, 2$ and $3$ possible values respectively. I understand the instance space is 3 x 2 x 3 x 2 x 3 = 108 possible instances, and that there are $2^{108}$ possible lists (subsets) that encompass all the positive instances. I also sort of get that each subset can be characterized by at least one Boolean expression.

He goes on to pose the question, how much will this search space shrink if we limit the classifiers to only using conjunctions of attribute value pairs. Is there a general mathematical solution to this question, much like the subsets of the possible instance space? I've attempted to brute force and come up with all the possible conjunctions but there must be a better way. Much appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.