Machine learning Lecture 2

Lecture No. 2Ravi GuptaAU-KBC Research Centre, MIT Campus, Anna UniversityDate: 8.3.2008Today’s Agenda• Recap (FIND-S Algorithm)• Version Space• Candidate-Elimination Algorithm• Decision Tree• ID3 Algorithm• EntropyConcept Learning as SearchConcept learning can be viewed as the task of searching through a large space of hypothesis implicitly defined by the hypothesisrepresentation.The goal of the concept learning search is to find the hypothesis that best fits the training examples.General-to-Specific LearningEvery day Tom his enjoy i.e., Only positive examples.Most General Hypothesis: h = <?, ?, ?, ?, ?, ?>Most Specific Hypothesis: h = < Ø, Ø, Ø, Ø, Ø, Ø>General-to-Specific Learningh2 is more general than h1h2 imposes fewer constraints on the instance than h1DefinitionGiven hypotheses hj and hk, hj is more_general_than_or_equal_tohk if and only if any instance that satisfies hk also satisfies hj.We can also say that hj is more_specific_than hk when hk is more_general_than hj.FIND-S: Finding a Maximally Specific HypothesisStep 1: FIND-Sh0 = <Ø, Ø, Ø, Ø, Ø, Ø>Step 2: FIND-Sh0 = <Ø, Ø, Ø, Ø, Ø, Ø>a1a2a3a4a5a6x1 = <Sunny, Warm, Normal, Strong, Warm, Same>Iteration 1h1 = <Sunny, Warm, Normal, Strong, Warm, Same>h1 = <Sunny, Warm, Normal, Strong, Warm, Same>Iteration 2x2 = <Sunny, Warm, High, Strong, Warm, Same>h2 = <Sunny, Warm, ?, Strong, Warm, Same>Document Outline

• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ
• ÿ