LearningfromObservations

(chapter18)Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)

LearningfromObservations

(chOutlinesLearningagentsInductivelearningDecisiontreelearningMeasuringlearningperformanceOutlinesLearningagentsLearningLearningisessentialforunknownenvironments,i.e.,whendesignerlacksomniscienceLearningisusefulasasystemconstructionmethod,i.e.,exposetheagenttorealityratherthantryingtowriteitdownLearningmodifiestheagent'sdecisionmechanismstoimproveperformanceLearningLearningisessentialLearningagentsLearningagentsLearningelementDesignofalearningelementisaffectedbyWhichcomponentsoftheperformanceelementaretobelearnedWhatfeedbackisavailabletolearnthesecomponentsWhatrepresentationisusedforthecomponentsTypeoffeedback: Supervisedlearning:involveslearningafunctionfromexamplesofitsinputandoutputs.Unsupervisedlearning:involveslearningpatternsintheinputwhennospecificoutputvaluesaresupplied.Reinforcementlearning:learnfromrewards(reinforcement)LearningelementDesignofaleInductivelearningSimplestform:learnafunctionfromexamplesfisthetargetfunctionAnexampleisapair(x,f(x))Problem:findahypothesishsuchthath≈fgivenatraining

setofexamples(Thisisahighlysimplifiedmodelofreallearning:IgnorespriorknowledgeAssumesexamplesaregiven)InductivelearningSimplestforInductivelearningmethodConstruct/adjusth

toagreewithf

ontrainingset (hisconsistentifitagreeswithf

onallexamples)E.g.,curvefitting:InductivelearningmethodConstInductivelearningmethodConstruct/adjusth

toagreewithfontrainingset (hisconsistentifitagreeswithfonallexamples)E.g.,curvefitting:InductivelearningmethodConstInductivelearningmethodConstruct/adjusth

toagreewithfontrainingset (hisconsistentifitagreeswithfonallexamples)E.g.,curvefitting:InductivelearningmethodConstInductivelearningmethodConstruct/adjusth

toagreewithfontrainingset (hisconsistentifitagreeswithfonallexamples)E.g.,curvefitting:InductivelearningmethodConstInductivelearningmethodConstruct/adjusth

toagreewithfontrainingset (hisconsistentifitagreeswithfonallexamples)E.g.,curvefitting:InductivelearningmethodConstInductivelearningmethodConstruct/adjusth

toagreewithfontrainingset (hisconsistentifitagreeswithfonallexamples)E.g.,curvefitting:Ockham’srazor:preferthesimplesthypothesisconsistentwithdata

--InLatin,itmeans“Entitiesarenottobemultipliedbeyondnecessity”InductivelearningmethodConstLearningdecisiontreesProblem:decidewhethertowaitforatableatarestaurant,basedonthefollowingattributes:Alternate:isthereanalternativerestaurantnearby?Bar:isthereacomfortablebarareatowaitin?Fri/Sat:istodayFridayorSaturday?Hungry:arewehungry?Patrons:numberofpeopleintherestaurant(None,Some,Full)Price:pricerange($,$$,$$$)Raining:isitrainingoutside?Reservation:havewemadeareservation?Type:kindofrestaurant(French,Italian,Thai,Burger)WaitEstimate:estimatedwaitingtime(0-10,10-30,30-60,>60)LearningdecisiontreesProblemAttribute-basedrepresentationsExamplesdescribedbyattributevalues(Boolean,discrete,continuous)E.g.,situationswhereIwill/won'twaitforatable:Classificationofexamplesispositive(T)ornegative(F)Attribute-basedrepresentationDecisiontreesOnepossiblerepresentationforhypothesesE.g.,hereisthe“true”treefordecidingwhethertowait:DecisiontreesOnepossiblerepExpressivenessDecisiontreescanexpressanyfunctionoftheinputattributes.E.g.,forBooleanfunctions,truthtablerow→pathtoleaf:Trivially,thereisaconsistentdecisiontreeforanytrainingsetwithonepathtoleafforeachexample(unlessf

nondeterministicinx)butitprobablywon'tgeneralizetonewexamplesPrefertofindmorecompactdecisiontreesExpressivenessDecisiontreescHypothesisspacesHowmanydistinctdecisiontreeswithnBooleanattributes?=numberofBooleanfunctions=numberofdistincttruthtableswith2nrows=22nE.g.,with6Booleanattributes,thereare18,446,744,073,709,551,616treesMoreexpressivehypothesisspaceincreaseschancethattargetfunctioncanbeexpressedincreasesnumberofhypothesesconsistentwithtrainingset

maygetworsepredictionsHypothesisspacesHowmanydistDecisiontreelearningAim:findasmalltreeconsistentwiththetrainingexamplesIdea:(recursively)choose"mostsignificant"attributeasrootof(sub)treeDecisiontreelearningAim:finChoosinganattributeIdea:agoodattributesplitstheexamplesintosubsetsthatare(ideally)"allpositive"or"allnegative"Patrons?isabetterchoiceChoosinganattributeIdea:agUsinginformationtheoryInformationanswersquestionsThemorecluelessIamabouttheanswerinitially,themoreinformationiscontainedintheanswerInformationContent(Entropy):I(P(v1),…,P(vn))=Σi=1-P(vi)log2P(vi)Foratrainingsetcontainingppositiveexamplesandnnegativeexamples:UsinginformationtheoryInformInformationgainAchosenattributeAdividesthetrainingsetEintosubsetsE1,…,EvaccordingtotheirvaluesforA,whereA

hasvdistinctvalues.InformationGain(IG)orreductioninentropyfromtheattributetest:ChoosetheattributewiththelargestIGInformationgainAchosenattriInformationgainForthetrainingset,p=n=6,I(6/12,6/12)=1bitConsidertheattributesPatronsandType(andotherstoo):PatronshasthehighestIGofallattributesandsoischosenbytheDTLalgorithmastherootInformationgainForthetrainiExamplecontd.Decisiontreelearnedfromthe12examples:Substantiallysimplerthan“true”tree---amorecomplexhypothesisisn’tjustifiedbysmallamountofdataExamplecontd.DecisiontreelePerformancemeasurementHowdow