Saturday, 24 August 2013

Candidate Elimination Algorithm - upper bound becomes too general

Candidate Elimination Algorithm - upper bound becomes too general

I should use Candidate Elimination algorithm from Machine Leaning area to
calculate correct hypothesis for following training data:
Nr violence nudity horror drugs U/Uc/PG -> Concept column(last one)
1 detailed none none yes no
2 none none none no yes
3 mild none occasional yes no
4 mild mild sustained no no
5 none none occasional no yes
6 detailed explicit none no no
7 mild mild none no yes
8 none mild sustained no no
My solution is as following:
S_0=〈∅,∅,∅,∅〉,G_0=〈?,?,?,?〉
t_1=〈detailed,none,none,yes〉,-
t_1¨{ (S_1: 〈∅,∅,∅,∅〉
G_1:〈none,?,?,?〉,〈mild,?,?,?〉,〈?,mild,?,?〉,〈?,explicit,?,?〉,〈?,?,occasional,?〉,
〈?,?,sustained,?〉,〈?,?,?,no〉 )
t_2=〈none,none,none,no〉,+
t_2¨{(S_2: 〈none,none,none,no〉
G_2:〈none,?,?,?〉,〈?,?,?,no〉 )
t_3=〈mild,none,occasional,yes〉,-
t_3¨{(S_3=S_2 G_3=G_2 )
t_4=〈mild,mild,sustained,no〉,-
t_4¨{(S_4=S_3 G_4:〈none,?,?,?〉 )
t_5=〈none,none,occasional,no〉,+
t_5¨{(S_5=〈none,none,?,no〉 G_5=G_4 )
t_6=〈detailed,explicit,none,no〉,-
t_6¨{(S_6=S_5 G_6=G_5 )
t_7=〈mild,mild,none,no〉,+
t_7¨{(S_7: 〈?,?,?,no〉 G_7:〈?,?,?,?〉 )
Now, the problem is that my 8th training example is not fitting any longer
into G hypothesis. Also, how can G be so braod to accept every possible
input, I guess there is an error somewhere, but where? Thank you

No comments:

Post a Comment