Concept Learning As Search (ML)

See Concept Learning first.

Q: What can be learned?
A: Only what is in the hypothesis space.

The learning problem is equivalent to searching the hypothesis space to find the correct hypothesis.

Hypothesis Space

Hypothesis Space
1 + (NumValuesField1 + 1) * (NumValuesField2 + 1) * … * (NumValuesFieldN + 1)

The 1 at the front is for No Value Allowed (a possible value), and the + 1 inside each bracket is for Don't Care (also a possible value).

We only cover the No Value Allowed once, rather than as an additional value as any hypothesis with that constraint covers no instances (as in, we never have a situation (instance) where one attribute doesn't exist), hence all are semantically equivalent.

Instance Space

Instance Space
NumValuesField1 * NumValuesField2 * … * NumValuesFieldN

We only need to care about the possible values as any 'instance' (situation) will have one of those set.
The instance space is hence smaller than the hypothesis space (so we say the hypothesis space has more 'expressive power'.

Generality and Hypotheses

When we say a hypothesis is more general than another hypothesis, we essentially mean that it has more 'don't care's' than it.

Formal definition:

Let J and K be hypotheses within H. We say that J is more general than or equal to K iff:

(1)
\begin{align} (\forall d \in D) [(K(d) = 1) \rightarrow (J(d) = 1)] \end{align}

i.e. For any data in the Data set, K(d) equalling 1 implies that J(d) equals 1.

J is strictly more general than K iff K(d) implies J(d), but J(d) does not imply K(d).

When J is more general than K, K is more specific than J.

Version Spaces

Put simply, the Version Space of any Hypothesis Space + Training Data (H and D) is the set of all valid h in H.

More technically, a hypothesis h is consistent with a set of training examples D, of target function c, iff h(x) = c(x) for each training example <x, c(x)> in D.

(2)
\begin{align} \text{Consistent}(h,D)\equiv (\forall<x, c(x)> \in D) h(x) = c(x) \end{align}

The version space is hence all hypotheses from H consistent with all the training examples in D:

(3)
\begin{align} VS_{H,D} \equiv (h \in H | \text{Consistent}(h,D)) \end{align}

Representing Version Spaces

Simply: If we know the most specific and the most general h in VS then we also know everything else in the VS, as these are our upper+lower bounds.

*The General Boundary, G, of VS is the set of the maximally general members.

  • The Specific boundary, S, of VS is the set of the maximally specific members.

Every member of the version space lies between these boundaries.

See Concept Learning Search Algorithms