Inf280 Autumn 2005 Exercise Set 5
Concept learning
The following (voluntary) exercises are in Norwegian. I apologize to
non-speakers. Please ask me, Harald, or your fellow students for
assistance if needed. Alternativeley, you could do Exercises 2.2 and
2.3 in Mitchell.
Also, see below for more exercises in the book.
-
Vi skal lære konseptet "studenter som vil stå til eksamen" som er
en delmengde av "studenter". Hver student blir beskrevet med følgende
attributter:
- jobber-ved-siden-av - mulige verdier: ingenting, lite, mye
- er-på-lesesalen - mulige verdier: aldri, sjelden, ofte, alltid
- leser-fag - mulige verdier: ingenting, noe, mye, enormt
- er-på-forelesning - mulige verdier: aldri, sjelden, ofte, alltid
Eksempler:
| jobber | lesesal | leser | forelesning | står |
| ingenting | alltid | enormt | alltid | ja |
| lite | alltid | enormt | alltid | ja |
| lite | ofte | mye | ofte | ja |
| lite | ofte | mye | alltid | ja |
| mye | aldri | noe | aldri | nei |
| mye | aldri | noe | ofte | nei |
-
Anta at hypoteserommet består av konjunksjoner av restriksjoner på
attributtene, der hver restriksjon (som i boken) kan tillatte ingen
verdier (Ø), én verdi (f.eks. ("ofte") eller alle verdier (?). Hvor
mange syntaktisk og semantisk distinkte hypoteser er det i
hypoteserommet?
- Bruk algoritmen FIND-S på eksemplene over. Hvilken hypotese kommer du frem
til? Er den konsistent med de negative eksemplene? Er dette målkonseptet?
-
Vi fortsetter med eksemplet fra oppgaven over.
- Utvid hypoteserommet ved å tillate restriksjonene på hver attributt å
tillate en liste av ulike verdier. Hvor stort er det nye
hypoteserommet i antall semantisk distinkte hypoteser?
- Bruk algoritmen FIND-S med det nye hypoteserommet.
FIND-S finner bare én hypotese;
den mest spesifikke som er konsistent med alle positive eksempler. Er det mange
andre hypoteser som er konsistente med treningsdata?
-
Gjenta oppgavene 1 og 2 med kandidatelimineringsalgoritmen
i stedet for FIND-S. Sammenlign svarene.
-
-
Hva sier den induktive læringshypotesen, og hva betyr det for læring i
eksemplet over?
-
Hva er induktiv bias for en læringsalgoritme?
-
Hvilken induktiv bias har kandidat-elimineringsalgoritmen?
Forklar hvordan graden av bias avhenger av valget av hypoteserom.
Sammenlign hypoteserommene fra oppgave 1 og 2.
Hvilket gir sterkest bias?
-
Hva kan skje hvis læringsalgoritmen har for sterk bias?
For svak bias? Hva skjer hvis den er helt "unbiased"
("fordomsfri")?
-
Exercise 2.4 from Mitchell, p. 48.
-
* Extra exercises from Mitchell (more theoretical): 2.7, 2.8.
-
** Honors problem from Mitchell (more difficult): 2.9.
Good luck!