Relation to Concept Learning
- In concept learning we have an instance space $X$,
hypothesis space $H$, training examples $D$. The
FindS algorithm finds the most specific hypothesis
from $VS_{H,D}$.
- Assume fixed set of instances $\langle x_{1}, \ldots, x_{m}\rangle$
- Assume $D$ is the set of classifications $D = \langle c(x_{1}),
\ldots, c(x_{m})\rangle$
- Choose $P(D\,|\,h)$
\[
P(D\,|\,h) = { \{
\array{
1 & if \forall_{d_i \in D} d_i = h(x_i)\\
0 & otherwise
} }
\]
- Choose $P(h)$ to be uniform distribution so that $P(h) =
\frac{1}{|H|}$ for all $h$ in $H$
- Then we can say that
\[ P(h\,|\,D) = { \{ \array{ \frac{1}{|VS_{H,D}|} & if h is consistend
with D \\ 0 & otherwise. } } \]
- What happens in Brute force
BCL is that all hypotheses start with with same
probability then the inconsistent hypotheses drop to zero
while the rest share equally.
- Every consistent hypothesis is a MAP hypothesis.
José M. Vidal
.
7 of 39