total number of hypotheses in version space

Question

I have a doubt in machine learning..

What is the size of the version space before seeing any training examples. Consider I have 10 attributes and I am using conjunction of constraints as the representation. The attributes have two values each 'yes' or 'no'.

Answer 1

If you have K classes, than version space is simply the number of possible splitting of all possible attirbute values into K disjoint subsets.

In your case:

• 10 attributes
• 2 possible values per attribute
• There are 2^10=1024 possible points
• There are K^1024 possible hypotheses (you can think about them, as the labeling of each point with one of K values).

For example, for binary case K=2 we have 2^1024 hypotheses in the version space.

If you consider only subset of possible hypotheses (by putting some constraints on their representation) than this number is smaller, yet analysis of actual number would require diving into details of how "expressive" are your constrained hypotheses.