PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceMonday, February 7, 2000William H. HsuDepartment of Computing and Information Sciences, KSUhttp://www.cis.ksu.edu/~bhsuReadings:Mitchell, Chapter 2Russell and Norvig, Chapter 21Analytical Learning Discussion (4 of 4):Integrating Inductive and Analytical LearningLecture 9Lecture 9Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceLecture OutlineLecture Outline•References: Chapters 2-3, Mitchell•Suggested Exercises: 2.2, 2.3, 2.4, 2.6•Review: Learning from Examples–(Supervised) concept learning framework–Basic inductive learning algorithms•General-to-Specific Ordering over Hypotheses–Version space: partially-ordered set (poset) formalism–Candidate elimination algorithm–Inductive learning•Decision Trees–Quick tutorial / review: Lectures 4-5, CIS 798, Fall 1999–See: http://ringil.cis.ksu.edu/Courses/Fall-1999/CIS798/Lectures•Relation to Analytical Learning•Next Class: Introduction to Artificial Neural NetworksKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial Intelligence(Supervised) Concept Learning(Supervised) Concept Learning•Given: Training Examples <x, f(x)> of Some Unknown Function f•Find: A Good Approximation to f•Examples (besides Concept Learning)–Disease diagnosis•x = properties of patient (medical history, symptoms, lab tests)•f = disease (or recommended therapy)–Risk assessment •x = properties of consumer, policyholder (demographics, accident history)•f = risk level (expected cost)–Automatic steering•x = bitmap picture of road surface in front of vehicle•f = degrees to turn the steering wheel–Part-of-speech tagging–Fraud/intrusion detection–Web log analysis–Multisensor integration and predictionKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceA Learning ProblemA Learning ProblemUnknownFunctionx1x2x3x4y = f (x1, x2, x3, x4 )•xi: ti, y: t, f: (t1  t2  t3  t4)  t•Our learning function: Vector (t1  t2  t3  t4  t)  (t1  t2  t3  t4)  tExample x1x2x3x4y0 0 1 1 0 01 0 0 0 0 02 0 0 1 1 13 1 0 0 1 14 0 1 1 0 05 1 1 0 0 06 0 1 0 1 0Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceHypothesis Space:Hypothesis Space:Unrestricted CaseUnrestricted Case•| A  B | = | B | | A | •|H4  H | = | {0,1}  {0,1}  {0,1}  {0,1}  {0,1} | = 224 = 65536 function values•Complete Ignorance: Is Learning Possible?–Need to see every possible input/output pair–After 7 examples, still have 29 = 512 possibilities (out of 65536) for fExample x1x2x3x4y0 0 0 0 0 ?1 0 0 0 1 ?2 0 0 1 0 03 0 0 1 1 14 0 1 0 0 05 0 1 0 1 06 0 1 1 0 07 0 1 1 1 ?8 1 0 0 0 ?9 1 0 0 1 110 1 0 1 0 ?11 1 0 1 1 ?12 1 1 0 0 013 1 1 0 1 ?14 1 1 1 0 ?15 1 1 1 1 ?Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceTraining ExamplesTraining Examplesfor Concept for Concept EnjoySportEnjoySportExample Sky AirTempHumidity Wind Water Forecast EnjoySport0Sunny Warm Normal Strong Warm SameYes1Sunny Warm High Strong Warm SameYes2Rainy Cold High Strong Warm ChangeNo3Sunny Warm High Strong Cool ChangeYes•Specification for Examples–Similar to a data type definition–6 attributes: Sky, Temp, Humidity, Wind, Water, Forecast–Nominal-valued (symbolic) attributes - enumerative data type•Binary (Boolean-Valued or H-Valued) Concept•Supervised Learning Problem: Describe the General ConceptKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceRepresenting HypothesesRepresenting Hypotheses•Many Possible Representations•Hypothesis h: Conjunction of Constraints on Attributes•Constraint Values–Specific value (e.g., Water = Warm)–Don’t care (e.g., “Water = ?”)–No value allowed (e.g., “Water = Ø”)•Example Hypothesis for EnjoySport–Sky AirTemp Humidity Wind Water Forecast <Sunny ? ? Strong ? Same>–Is this consistent with the training examples?–What are some hypotheses that are consistent with the examples?Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligencePrototypical Concept Learning TasksPrototypical Concept Learning Tasks•Given–Instances X: possible days, each described by attributes Sky, AirTemp, Humidity, Wind, Water, Forecast–Target function c  EnjoySport: X  H  {{Rainy, Sunny}  {Warm, Cold}  {Normal, High}  {None, Mild, Strong}  {Cool, Warm}  {Same, Change}}  {0, 1}–Hypotheses H: conjunctions of literals (e.g., <?, Cold, High, ?, ?, ?>)–Training examples D: positive and negative examples of the target function•Determine–Hypothesis h  H such that h(x) = c(x) for all x  D–Such h are consistent with the training data•What Is A Concept Learning Algorithm?–L: Vector (X  H  boolean)  (X  H)–Type of L means: given vector of examples (data set), return hypothesis h–h: X  H   mm,11,xcx,,xcx Kansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceInstances, Hypotheses, andInstances, Hypotheses, andthe Partial Ordering the Partial Ordering Less-Specific-ThanLess-Specific-ThanInstances X Hypotheses Hx1 = <Sunny, Warm, High, Strong, Cool, Same>x2 = <Sunny, Warm, High, Light, Warm, Same>h1 = <Sunny, ?, ?, Strong, ?, ?>h2 = <Sunny, ?, ?, ?, ?, ?>h3 = <Sunny, ?, ?, ?, Cool, ?>h2 P h1 h2 P h3x1x2SpecificGeneralh1h3h2P  Less-Specific-Than  More-General-ThanKansas State UniversityDepartment of Computing and Information SciencesCIS 830: Advanced Topics in Artificial IntelligenceHypothesis Space SearchHypothesis Space Searchby by Find-SFind-SInstances XHypotheses Hx1 = <Sunny, Warm, Normal, Strong, Warm, Same>, +x2 = <Sunny, Warm, High, Strong, Warm, Same>, +x3 = <Rainy, Cold, High, Strong, Warm, Change>, -x4 = <Sunny, Warm, High, Strong, Cool, Change>, +h1 = <Ø, Ø, Ø, Ø, Ø, Ø> h2 = <Sunny,