Learning from ObservationsChapter 18, Sections 1–3Chapter 18, Sections 1–3 1Outline♦ Learning agents♦ Inductive learning♦ Decision tree learning♦ Measuring learning performanceChapter 18, Sections 1–3 2LearningLearning is essential for unknown environments,i.e., when designer lacks omniscienceLearning is useful as a system construction method,i.e., expose the agent to reality rather than trying to write it downLearning modifies the agent’s decision mechanisms to improve performanceChapter 18, Sections 1–3 3Learning agentsPerformance standardAgentEnvironmentSensorsEffectorsPerformance elementchangesknowledgelearning goals Problem generator feedback Learning elementCriticexperimentsChapter 18, Sections 1–3 4Learning elementDesign of learning element is dictated by♦ what type of performance element is used♦ which functional component is to be learned♦ how that functional compoent is represented♦ what kind of feedback is availableExample scenarios:Performance elementAlpha−beta searchLogical agentSimple reflex agentComponentEval. fn.Transition modelTransition modelRepresentationWeighted linear functionSuccessor−state axiomsNeural netDynamic Bayes netUtility−based agentPercept−action fnFeedbackOutcomeOutcomeWin/lossCorrect actionSupervised learning: correct answers for each instanceReinforcement learning: occasional rewardsChapter 18, Sections 1–3 5Inductive learning (a.k.a. Science)Simplest form: learn a function from examples (tabula rasa)f is the target functionAn example is a pair x, f(x), e.g.,OO XXX, +1Problem: find a(n) hypothesis hsuch that h ≈ fgiven a training set of examples(This is a highly simplified mo del of real learning:– Ignores prior knowledge– Assumes a deterministic, observable “environment”– Assumes examples are given– Assumes that the agent wants to learn f—why?)Chapter 18, Sections 1–3 6Inductive learning methodConstruct/adjust h to agree with f on training set(h is consistent if it agrees with f on all examples)E.g., curve fitting:xf(x)Chapter 18, Sections 1–3 7Inductive learning methodConstruct/adjust h to agree with f on training set(h is consistent if it agrees with f on all examples)E.g., curve fitting:xf(x)Chapter 18, Sections 1–3 8Inductive learning methodConstruct/adjust h to agree with f on training set(h is consistent if it agrees with f on all examples)E.g., curve fitting:xf(x)Chapter 18, Sections 1–3 9Inductive learning methodConstruct/adjust h to agree with f on training set(h is consistent if it agrees with f on all examples)E.g., curve fitting:xf(x)Chapter 18, Sections 1–3 10Inductive learning methodConstruct/adjust h to agree with f on training set(h is consistent if it agrees with f on all examples)E.g., curve fitting:xf(x)Chapter 18, Sections 1–3 11Inductive learning methodConstruct/adjust h to agree with f on training set(h is consistent if it agrees with f on all examples)E.g., curve fitting:xf(x)Ockham’s razor: maximize a combination of consistency and simplicityChapter 18, Sections 1–3 12Attribute-based representationsExamples described by attribute values (Boolean, discrete, continuous, etc.)E.g., situations where I will/won’t wait for a table:ExampleAttributes TargetAlt Bar Fri Hun Pat Price Rain Res Type Est WillWaitX1T F F T Some $$$ F T French 0–10 TX2T F F T Full $ F F Thai 30–60 FX3F T F F Some $ F F Burger 0–10 TX4T F T T Full $ F F Thai 10–30 TX5T F T F Full $$$ F T French >60 FX6F T F T Some $$ T T Italian 0–10 TX7F T F F None $ T F Burger 0–10 FX8F F F T Some $$ T T Thai 0–10 TX9F T T F Full $ T F Burger >60 FX10T T T T Full $$$ F T Italian 10–30 FX11F F F F None $ F F Thai 0–10 FX12T T T T Full $ F F Burger 30–60 TClassification of examples is positive (T) or negative (F)Chapter 18, Sections 1–3 13Decision treesOne possible representation for hypothesesE.g., here is the “true” tree for deciding whether to wait:No YesNo YesNo YesNo YesNo YesNo YesNone Some Full>60 30−60 10−30 0−10No YesAlternate?Hungry?Reservation?Bar? Raining?Alternate?Patrons?Fri/Sat?WaitEstimate?F TF TTTF TTFTTFChapter 18, Sections 1–3 14ExpressivenessDecision trees can express any function of the input attributes.E.g., for Boolean functions, truth table row → path to leaf:FTABF TBA B A xor BFF FF TTT F TTT FFFF T T TTrivially, there is a consistent decision tree for any training setw/ one path to leaf for each example (unless f nondeterministic in x)but it probably won’t generalize to new examplesPrefer to find more compact decision treesChapter 18, Sections 1–3 15Hypothesis spacesHow many distinct decision trees with n Boolean attributes??Chapter 18, Sections 1–3 16Hypothesis spacesHow many distinct decision trees with n Boolean attributes??= number of Boolean functionsChapter 18, Sections 1–3 17Hypothesis spacesHow many distinct decision trees with n Boolean attributes??= number of Boolean functions= number of distinct truth tables with 2nrowsChapter 18, Sections 1–3 18Hypothesis spacesHow many distinct decision trees with n Boolean attributes??= number of Boolean functions= number of distinct truth tables with 2nrows = 22nChapter 18, Sections 1–3 19Hypothesis spacesHow many distinct decision trees with n Boolean attributes??= number of Boolean functions= number of distinct truth tables with 2nrows = 22nE.g., with 6 Boolean attributes, there are 18,446,744,073,709,551,616 treesChapter 18, Sections 1–3 20Hypothesis spacesHow many distinct decision trees with n Boolean attributes??= number of Boolean functions= number of distinct truth tables with 2nrows = 22nE.g., with 6 Boolean attributes, there are 18,446,744,073,709,551,616 treesHow many purely conjunctive hypotheses (e.g., Hungry ∧¬Rain)??Chapter 18, Sections 1–3 21Hypothesis spacesHow many distinct decision trees with n Boolean attributes??= number of Boolean functions= number of distinct truth tables with 2nrows = 22nE.g., with 6 Boolean attributes, there are 18,446,744,073,709,551,616 treesHow many purely conjunctive hypotheses (e.g., Hungry ∧¬Rain)??Each attribute can be in (positive), in (negative), or out⇒ 3ndistinct conjunctive hypothesesMore expressive hypothesis space– increases chance that target function can be expressed– increases number of hypotheses consistent w/ training set⇒ may get worse predictionsChapter 18, Sections 1–3 22Decision tree learningAim: find a small tree consistent with the training examplesIdea: