Transcription
specific than the firstand third element of G remove them from G G {⟨ ⟩}– d4 [⟨ ⟩, neg] no change to S: S {⟨ ⟩} specializations of G: G {⟨ ⟩, ⟨ ⟩} there is no element in S that is more specific than the secondelement of G remove it from G G {⟨ ⟩}
– Note: At this point, the algorithm might be stopped, since S Gand no further changes to S and G are to be expected. However, by continuing we might detect inconsistencies in thetraining data.– d5 [⟨ ⟩, neg] Both, G {⟨ ⟩} and S {⟨ ⟩}are consistent with d5 .– d6 [⟨ ⟩, neg] Both, G {⟨ ⟩} and S {⟨ ⟩}are consistent with d6 .
(d) Does the order of presentation of the training examples (according to Table 1) to the learner affect the finally learned hypothesis? No, but it may influence the algorithm’s running time.
(e) Assume a domain with two attributes, i.e. any instance is described bytwo constraints. How many positive and negative training examples areminimally required by the candidate elimination algorithm in order to learnan arbitrary concept? By learning an arbitrary concept, of course, we mean that the algorithm arrives at S G. The algorithm is started with S {⟨ , ⟩} and G {⟨ , ⟩}. We just consider the best cases, i.e. situations in where the traininginstances given to the CE algorithm allow for adapting S or G. Negative Examples: Change G from ⟨ , ⟩ to ⟨v, ⟩ or ⟨ , w⟩. Or theychange G from ⟨v, ⟩ or ⟨ , w⟩ to ⟨v, w⟩. Positive Examples: Change S from ⟨ , ⟩, ⟨v, w⟩. Or they change Sfrom ⟨v, w⟩ to ⟨v, ⟩ or ⟨ , w⟩. Or from ⟨v, ⟩ or ⟨ , w⟩ to ⟨ , ⟩. At least one positive example is required (otherwise S remains ⟨ , ⟩). Special case: Two positive patterns ⟨d1 , d2 ⟩, ⟨e1 , e2 ⟩ are sufficient, ifit holds d1 ̸ e1 and d2 ̸ e2 . S ⟨ , ⟩ ⟨d1 , d2 ⟩ ⟨ , ⟩
(f) We are now extending the number of constraints used for describing training instances by one additional constraint named “fever”. We say thatsomebody is ill, if he has a running nose and is coughing (as we did before), or if he has fever.How does the version space approach using the CE algorithm performnow, given the training examples specified in Table 2? What happens, ifthe order of presentation of the training examples is altered?Trainingd1d2d3d4d5d6running nose – ––coughing ––– reddened skin – –– fever–– –––Classificationpositive (ill)positive (ill)positive (ill)negative (healthy)negative (healthy)negative (healthy)Table 2: List of training instances using the extended representation.
Initially: S {⟨ ⟩}, G {⟨ ⟩} d1 [⟨ ⟩, pos] S {⟨ ⟩}, G {⟨ ⟩} d2 [⟨ ⟩, pos] S {⟨ ⟩}, G {⟨ ⟩} d3 [⟨ ⟩, pos] S {⟨ ⟩}, G {⟨ ⟩} We already arrive at S G. d4 [⟨ ⟩, neg] S {⟨ ⟩}, G {⟨ ⟩}– Now, S becomes empty since ⟨ ⟩ is inconsistent with d4 andis removed from S.– G would be specialized to {⟨ ⟩, ⟨ ⟩, ⟨ ⟩, ⟨ ⟩}.But it is required that at least one element from S must be morespecific than any element from G. This requirement cannot be fulfilled
Exercise 1.3: Decision Tree Learning with onhealthy (H)influenza (I)influenza (I)salmonella poisoning (S)salmonella poisoning (
Machine Learning algorithms. Which of the problems would you apply supervised learning to? (b) There are two types of supervised learning tasks, classification and regres-sion. Decide for the supervised learning problems given below, whether it is a classification problem or not. s Reinforcement learning Density estimation Data preprocessing
