In my concept learning problem, three are 3 attributes (size,color,shape). Each attribute has 3 features showed in the picture below.
${}$
${}$
In the conjunctive rule learning, hypotheses are like this:
- (big,red,?) means two constraints on size and color, but no constraint on shape
- (?,?,?) means no constraint for all features
- ( $\varnothing$,$\varnothing$,$\varnothing$ ) means no value is acceptable
Assume hypothesis function noted by $~z=(a_i,b_i,c_i)~$, there are $3^3+1=28$ potential hypotheses.
Now consider the disjunctive rule. The hypothesis function is noted by $h=z_1\lor z_2\lor z_3...\lor z_k$ , with k conjunctive sub-hypothesis.
In view of disjunctive way , $(small,?,circle)\lor (large,red,?)$ is a new hypothesis with two conjunctive sub-hypothesis.
The final question is:
Assume k is the max number of conjunctive sub-hypothesis in all disjunctive hypotheses, what's the hypothesis space or how many potential hypotheses there are ?
PS: Equivalent hypotheses should be considered as $1$ hypothesis.
In the case of
$$ \begin{align} h_1&=(big,?,?)\lor (big,red,?) \\ h_2&=(big,?,?) \end{align} $$ ,the two hypotheses are equivalent, they can be described as $h=(big,?,?)$.
We know when $k=1$, the problem is converted to conjunctive way, there are
$3^3+1=28$ potentials hypotheses.
When $k=2,3,4...$,what's the solution ?