Concept Learning

Source: Unit 1 §5

What is a concept?

A concept is a notion or category, such as "chair". Concept learning is acquiring the ability to look at a data object $x$ and decide whether it belongs to the concept (label 1) or not (label 0). That is a binary concept.

Data object x ──▶ [ Concept C ] ──▶ label

1 (x belongs to C)

0 (x does NOT belong to C)

Objects, attributes and the learning task

≡FactsThe setup

• An object $x$ is described by a set of attributes / features, and each attribute takes specific values.
• Once we know the concept, we can label any new data object.
• Learning that concept from data is the concept-learning task.

Running example with 3 attributes:

Attribute	Possible values
shape	oval, circular
size	large, small
colour	dark, light

An object is a vector like (oval, large, dark), and so on up to (circular, small, light).

The size of the concept space, and why we need a bias

#NumbersCounting objects and concepts

• With 3 binary attributes there are $2^3 = 8$ possible objects.
• A concept is any way to split those 8 objects into "in" and "out". Each of the 8 objects can independently be in or out, so there are $2^8 = \mathbf{256}$ possible concepts.
• General rule: if the data is defined by $d$ binary attributes, there are $2^d$ possible objects - call that $b$ - and therefore $2^b$ possible concepts.
• For $d = 3$: $b = 8$, giving 256 concepts.

Searching all 256 concepts is huge. The solution is to shrink the search space using an inductive bias: we assume the target concept has a particular form.

Inductive bias: conjunctive concepts

A conjunctive concept is a concept expressed as the conjunction (logical AND) of attribute values - a subset of features that all must be true. For example circular ∧ dark means an object belongs only if it is both circular and dark.

Symbol	Meaning
a value, e.g. circular	that attribute must equal this value
**?**	any value is acceptable, a "don't care" for this attribute
**Ø**	reject everything - the most specific, empty concept

So a 3-attribute conjunctive concept looks like ⟨circular, ?, dark⟩, meaning shape = circular, size = anything, colour = dark.

≡FactsThe two extremes

• ⟨?, ?, ?⟩ is accept-all: everything belongs.
• Ø is reject-all: nothing belongs.

Counting conjunctive concepts

For each of the $d$ positions we can put one of the two attribute values, or ?, which is 3 choices per position. Add the single Ø concept:

$$\#\text{conjunctive concepts} = 3^d + 1$$

For $d = 3$: $(3 \times 3 \times 3) + 1 = 27 + 1 = \mathbf{28}$.

Three binary attributes already give 256 candidate concepts. The conjunctive bias throws away 228 of them before the learner starts.

◎Exam cueConcept space vs hypothesis space

The hypothesis space is the shrunk search space left after applying the inductive bias. Here it took us from 256 concepts down to 28.

The Find-S algorithm

Goal: find the most specific hypothesis consistent with the positive training examples.

1. Start with h = Ø (most specific - rejects everything)

2. Take next input {x, c(x)}

3. If c(x) = 0 (negative) -> ignore it, go to step 2

4. Otherwise: h <- h AND x (pairwise-AND each attribute)

5. If more examples, go to step 2

6. Stop

⚠GotchaFind-S throws away half your data

Find-S only looks at POSITIVE examples; it completely ignores the negative ones. Any information a negative example carried is simply lost.

The pairwise-AND rule

Situation	Result
aₕ = Ø (nothing learned yet)	aₓ - take the example's value
aₕ = aₓ (they agree)	aₕ - keep it
aₕ ≠ aₓ (they differ)	? - generalize to "don't care"
aₕ = ? (already a don't-care)	?

Worked problem: days a person enjoys sport

Attributes: Sky (sunny / rainy), Temp (warm / cold), Humidity (Normal / High), Wind (strong / weak), Water (warm / cool), Forecast (same / change).

Sky	Temp	Humidity	Wind	Water	Forecast	Enjoy
sunny	warm	normal	strong	warm	same	yes
sunny	warm	high	strong	warm	same	yes
rainy	cold	high	strong	warm	change	no
sunny	warm	high	strong	cool	same	yes

→StepsThe Find-S trace

1. Initialise. h₀ = ⟨Ø, Ø, Ø, Ø, Ø, Ø⟩.
2. Example 1 (yes) is ⟨sunny, warm, normal, strong, warm, same⟩. h was Ø, so copy the example: h = ⟨sunny, warm, normal, strong, warm, same⟩.
3. Example 2 (yes) is ⟨sunny, warm, high, strong, warm, same⟩. Comparing, humidity differs (normal vs high), so it generalizes to ?: h = ⟨sunny, warm, ?, strong, warm, same⟩.
4. Example 3 (no) is IGNORED, because it is a negative example.
5. Example 4 (yes) is ⟨sunny, warm, high, strong, cool, same⟩. Comparing, water differs (warm vs cool), so it generalizes to ?: h = ⟨sunny, warm, ?, strong, ?, same⟩.
6. Final hypothesis, the learned concept: C = ⟨sunny, warm, ?, strong, ?, same⟩.

Prediction with Find-S

For a new day x = ⟨sunny, warm, high, strong, warm, same⟩: sunny matches, warm matches, humidity is ? so anything is acceptable, strong matches, water is ? so anything is acceptable, same matches. Therefore $c(x) = 1$ and the person will play the sport.

Version space

Find-S gives one hypothesis, the most specific one. Often we want all the consistent ones - that is the version space, produced by the Candidate-Elimination algorithm.

Consistency: a hypothesis $h$ is consistent with the training data if it classifies every training object correctly:

$$h(x_i) = c(x_i) \quad \text{for all } i$$

Version space $VS$ is the subset of the hypothesis space $H$ containing all hypotheses consistent with the training set:

$$VS = \{\, h : h \in H \text{ and } h \text{ is consistent with } D_{\text{training}} \,\}$$

Hypotheses are ordered from accept-all at the top to reject-all at the bottom. The shaded region is an ILLUSTRATIVE version space, not one derived from any data on this page - and a real version space is whatever set of hypotheses the training examples leave standing, which need not be a neat rectangle in this layout.

≡FactsWhat the version space gives you that Find-S does not

• It brings better questions about consistency: it represents all the hypotheses that fit, not just one.
• Caveat: with many attributes the hypothesis space may never contain the true concept, in which case the learner will predict wrong. Find-S and Candidate-Elimination can only ever learn within the biased hypothesis space.

⚠GotchaThe bias that saves you is also the bias that traps you

Shrinking 256 concepts to 28 is what makes the search tractable, and it is also what can put the true concept permanently out of reach. A learner cannot output a hypothesis its bias forbids, no matter how much data you give it.