人工智能 机器学习

1ArtificialIntelligenceMachineLearning2WhatisLearning?•HerbertSimon:“Learningisanyprocessbywhichasystemimprovesperformancefromexperience.”•Whatisthetask?–Classification–Problemsolving/planning/control3Classification•Assignobject/eventtooneofagivenfinitesetofcategories.–Medicaldiagnosis–Creditcardapplicationsortransactions–Frauddetectionine-commerce–Wormdetectioninnetworkpackets–Spamfilteringinemail–Recommendedarticlesinanewspaper–Recommendedbooks,movies,music,orjokes–Financialinvestments–DNAsequences–Spokenwords–Handwrittenletters–Astronomicalimages4ProblemSolving/Planning/Control•Performingactionsinanenvironmentinordertoachieveagoal.–Solvingcalculusproblems–Playingcheckers,chess,orbackgammon–Balancingapole–Drivingacarorajeep–Flyingaplane,helicopter,orrocket–Controllinganelevator–Controllingacharacterinavideogame–Controllingamobilerobot5SampleCategoryLearningProblem•Instancelanguage:size,color,shape–size{small,medium,large}–color{red,blue,green}–shape{square,circle,triangle}•C={positive,negative}•D:ExampleSizeColorShapeCategory1smallredcirclepositive2largeredcirclepositive3smallredtrianglenegative4largebluecirclenegative6HypothesisSelection•Manyhypothesesareusuallyconsistentwiththetrainingdata.–red&circle–(small&circle)or(large&red)–(small&red&circle)or(large&red&circle)–not[(red&triangle)or(blue&circle)]–not[(small&red&triangle)or(large&blue&circle)]•Bias–Anycriteriaotherthanconsistencywiththetrainingdatathatisusedtoselectahypothesis.7Generalization•Hypothesesmustgeneralizetocorrectlyclassifyinstancesnotinthetrainingdata.•Simplymemorizingtrainingexamplesisaconsistenthypothesisthatdoesnotgeneralize.•Occam’srazor:–Findingasimplehypothesishelpsensuregeneralization.8HypothesisSpace•Restrictlearnedfunctionsaprioritoagivenhypothesisspace,H,offunctionsh(x)thatcanbeconsideredasdefinitionsofc(x).•Forlearningconceptsoninstancesdescribedbyndiscrete-valuedfeatures,considerthespaceofconjunctivehypothesesrepresentedbyavectorofnconstraintsc1,c2,…cnwhereeachciiseither:–?,awildcardindicatingnoconstraintontheithfeature–Aspecificvaluefromthedomainoftheithfeature–Øindicatingnovalueisacceptable•Sampleconjunctivehypothesesare–big,red,?–?,?,?(mostgeneralhypothesis)–Ø,Ø,Ø(mostspecifichypothesis)9InductiveLearningHypothesis•Anyfunctionthatisfoundtoapproximatethetargetconceptwellonasufficientlylargesetoftrainingexampleswillalsoapproximatethetargetfunctionwellonunobservedexamples.•Assumesthatthetrainingandtestexamplesaredrawnindependentlyfromthesameunderlyingdistribution.•Thisisafundamentallyunprovablehypothesisunlessadditionalassumptionsaremadeaboutthetargetconceptandthenotionof“approximatingthetargetfunctionwellonunobservedexamples”isdefinedappropriately(cf.computationallearningtheory).10EvaluationofClassificationLearning•Classificationaccuracy(%ofinstancesclassifiedcorrectly).–Measuredonanindependenttestdata.•Trainingtime(efficiencyoftrainingalgorithm).•Testingtime(efficiencyofsubsequentclassification).11CategoryLearningasSearch•Categorylearningcanbeviewedassearchingthehypothesisspaceforone(ormore)hypothesesthatareconsistentwiththetrainingdata.•Consideraninstancespaceconsistingofnbinaryfeatureswhichthereforehas2ninstances.•Forconjunctivehypotheses,thereare4choicesforeachfeature:Ø,T,F,?,sothereare4nsyntacticallydistincthypotheses.•However,allhypotheseswith1ormoreØsareequivalent,sothereare3n+1semanticallydistincthypotheses.•Thetargetbinarycategorizationfunctioninprinciplecouldbeanyofthepossible22^nfunctionsonninputbits.•Therefore,conjunctivehypothesesareasmallsubsetofthespaceofpossiblefunctions,butbothareintractablylarge.•Allreasonablehypothesisspacesareintractablylargeoreveninfinite.12LearningbyEnumeration•Foranyfiniteorcountablyinfinitehypothesisspace,onecansimplyenumerateandtesthypothesesoneatatimeuntilaconsistentoneisfound.ForeachhinHdo:IfhisconsistentwiththetrainingdataD,thenterminateandreturnh.•Thisalgorithmisguaranteedtoterminatewithaconsistenthypothesisifoneexists;however,itisobviouslycomputationallyintractableforalmostanypracticalproblem.13EfficientLearning•Isthereawaytolearnconjunctiveconceptswithoutenumeratingthem?•Howdohumansubjectslearnconjunctiveconcepts?•Isthereawaytoefficientlyfindanunconstrainedbooleanfunctionconsistentwithasetofdiscrete-valuedtraininginstances?•Ifso,isitauseful/practicalalgorithm?14ConjunctiveRuleLearning•Conjunctivedescriptionsareeasilylearnedbyfindingallcommonalitiessharedbyallpositiveexamples.•Mustcheckconsistencywithnegativeexamples.Ifinconsistent,noconjunctiveruleexists.ExampleSizeColorShapeCategory1smallredcirclepositive2largeredcirclepositive3smallredtrianglenegative4largebluecirclenegativeLearnedrule:red&circle→positive15LimitationsofConjunctiveRules•Ifaconceptdoesnothaveasinglesetofnecessaryandsufficientconditions,conjunctivelearningfails.ExampleSizeColorShapeCategory1smallredcirclepositive2largeredcirclepositive3smallredtrianglenegative4largebluecirclenegative5mediumredcirclenegativeLearnedrule:red&circle→positiveInconsistentwithnegativeexample#5!16DecisionTrees•Tree-basedcl