Negnevisky人工智能英文讲义一

Lecture1Introductiontoknowledge-baseintelligentsystemsIntelligentmachines,orwhatmachinescandoThehistoryofartificialintelligenceorfromthe“DarkAges”toknowledge-basedsystemsSummaryIntelligentmachines,orwhatmachinescandoPhilosophershavebeentryingforover2000yearstounderstandandresolvetwoBigQuestionsoftheUniverse:Howdoesahumanmindwork,andCannon-humanshaveminds?Thesequestionsarestillunanswered.Intelligenceistheabilitytounderstandandlearnthings.2Intelligenceistheabilitytothinkandunderstandinsteadofdoingthingsbyinstinctorautomatically. (EssentialEnglishDictionary,Collins,London,1990)Inordertothink,someoneorsomethinghastohaveabrain,oranorganthatenablessomeoneorsomethingtolearnandunderstandthings,tosolveproblemsandtomakedecisions.Sowecandefineintelligenceastheabilitytolearnandunderstand,tosolveproblemsandtomakedecisions.Thegoalofartificialintelligence(AI)asascienceistomakemachinesdothingsthatwouldrequireintelligenceifdonebyhumans.Therefore,theanswertothequestionCanMachinesThink?wasvitallyimportanttothediscipline.Theanswerisnotasimple“Yes”or“No”.Somepeoplearesmarterinsomewaysthanothers.Sometimeswemakeveryintelligentdecisionsbutsometimeswealsomakeverysillymistakes.Someofusdealwithcomplexmathematicalandengineeringproblemsbutaremoronicinphilosophyandhistory.Somepeoplearegoodatmakingmoney,whileothersarebetteratspendingit.Ashumans,weallhavetheabilitytolearnandunderstand,tosolveproblemsandtomakedecisions;however,ourabilitiesarenotequalandlieindifferentareas.Therefore,weshouldexpectthatifmachinescanthink,someofthemmightbesmarterthanothersinsomeways.Oneofthemostsignificantpapersonmachineintelligence,“ComputingMachineryandIntelligence”,waswrittenbytheBritishmathematicianAlanTuringoverfiftyyearsago.However,itstillstandsupwellunderthetestoftime,andtheTuring’sapproachremainsuniversal.Heasked:Istherethoughtwithoutexperience?Istheremindwithoutcommunication?Istherelanguagewithoutliving?Isthereintelligencewithoutlife?Allthesequestions,asyoucansee,arejustvariationsonthefundamentalquestionofartificialintelligence,Canmachinesthink?Turingdidnotprovidedefinitionsofmachinesandthinking,hejustavoidedsemanticargumentsbyinventingagame,theTuringImitationGame.Theimitationgameoriginallyincludedtwophases.Inthefirstphase,theinterrogator,amanandawomanareeachplacedinseparaterooms.Theinterrogator’sobjectiveistoworkoutwhoisthemanandwhoisthewomanbyquestioningthem.Themanshouldattempttodeceivetheinterrogatorthatheisthewoman,whilethewomanhastoconvincetheinterrogatorthatsheisthewoman.TuringImitationGame:Phase1TuringImitationGame:Phase2Inthesecondphaseofthegame,themanisreplacedbyacomputerprogrammedtodeceivetheinterrogatorasthemandid.Itwouldevenbeprogrammedtomakemistakesandprovidefuzzyanswersinthewayahumanwould.Ifthecomputercanfooltheinterrogatorasoftenasthemandid,wemaysaythiscomputerhaspassedtheintelligentbehaviourtest.TuringImitationGame:Phase2

TheTuringtesthastworemarkablequalitiesthatmakeitreallyuniversal.Bymaintainingcommunicationbetweenthehumanandthemachineviaterminals,thetestgivesusanobjectivestandardviewonintelligence.Thetestitselfisquiteindependentfromthedetailsoftheexperiment.Itcanbeconductedasatwo-phasegame,orevenasasingle-phasegamewhentheinterrogatorneedstochoosebetweenthehumanandthemachinefromthebeginningofthetest.Turingbelievedthatbytheendofthe20thcenturyitwouldbepossibletoprogramadigitalcomputertoplaytheimitationgame.AlthoughmoderncomputersstillcannotpasstheTuringtest,itprovidesabasisfortheverificationandvalidationofknowledge-basedsystems.Aprogramthoughtintelligentinsomenarrowareaofexpertiseisevaluatedbycomparingitsperformancewiththeperformanceofahumanexpert.Tobuildanintelligentcomputersystem,wehavetocapture,organiseandusehumanexpertknowledgeinsomenarrowareaofexpertise.ThehistoryofartificialintelligenceThefirstworkrecognisedinthefieldofAIwaspresentedbyWarrenMcCullochandWalterPittsin1943.Theyproposedamodelofanartificialneuralnetworkanddemonstratedthatsimplenetworkstructurescouldlearn.McCulloch,thesecond“foundingfather”ofAIafterAlanTuring,hadcreatedthecornerstoneofneuralcomputingandartificialneuralnetworks(ANN).Thebirthofartificialintelligence(1943–1956)ThethirdfounderofAIwasJohnvonNeumann,thebrilliantHungarian-bornmathematician.In1930,hejoinedthePrincetonUniversity,lecturinginmathematicalphysics.HewasanadviserfortheElectronicNumericalIntegratorandCalculatorprojectattheUniversityofPennsylvaniaandhelpedtodesigntheElectronicDiscreteVariableCalculator.HewasinfluencedbyMcCullochandPitts’sneuralnetworkmodel.WhenMarvinMinskyandDeanEdmonds,twograduatestudentsinthePrincetonmathematicsdepartment,builtthefirstneuralnetworkcomputerin1951,vonNeumannencouragedandsupportedthem.AnotherofthefirstgenerationresearcherswasClaudeShannon.HegraduatedfromMITandjoinedBellTelephoneLaboratoriesin1941.ShannonsharedAlanTuring’’sideasonthepossibilityofmachineintelligence.In1950,hepublishedapaperonchess-playingmachines,whichpointedoutthatatypicalchessgameinvolvedabout10120possiblemoves(Shannon,1950).EvenifthenewvonNeumann-typecomputercouldexamineonemovepermicrosecond,itwouldtake310106yearstomakeitsfirstmove.ThusShannondemonstratedtheneedtouseheuristicsinthesearchforthesolution.In1956,JohnMcCarthy,MartinMinskyandClaudeShannonorganisedasummerworkshopatDartmouthCollege.Theybroughttogetherresearchersinterestedinthestudyofmachineintelligence,artificialneuralnetsandautomatatheory.Althoughtherewerejusttenresearchers,thisworkshopgavebirthtoanewsciencecalledartificialintelligence.Theriseofartificialintelligence,ortheeraofgreatexpectations(1956––late1960s)TheearlyworksonneuralcomputingandartificialneuralnetworksstartedbyMcCullochandPittswascontinued.LearningmethodswereimprovedandFrankRosenblattprovedtheperceptronconvergencetheorem,demonstratingthathislearningalgorithmcouldadjusttheconnectionstrengthsofaperceptron.OneofthemostambitiousprojectsoftheeraofgreatexpectationswastheGeneralProblemSolver(GPS).AllenNewellandHerbertSimonfromtheCarnegieMellonUniversitydevelopedageneral-purposeprogramtosimulatehuman-solvingmethods.NewellandSimonpostulatedthataproblemtobesolvedcouldbedefinedintermsofstates.Theyusedthemean-endanalysistodetermineadifferencebetweenthecurrentanddesirableorgoalstateoftheproblem,andtochooseandapplyoperatorstoreachthegoalstate.Thesetofoperatorsdeterminedthesolutionplan.However,GPSfailedtosolvecomplexproblems.Theprogramwasbasedonformallogicandcouldgenerateaninfinitenumberofpossibleoperators.TheamountofcomputertimeandmemorythatGPSrequiredtosolvereal-worldproblemsledtotheprojectbeingabandoned.Inthesixties,AIresearchersattemptedtosimulatethethinkingprocessbyinventinggeneralmethodsforsolvingbroadclassesofproblems.Theyusedthegeneral-purposesearchmechanismtofindasolutiontotheproblem.Suchapproaches,nowreferredtoasweakmethods,appliedweakinformationabouttheproblemdomain.By1970,theeuphoriaaboutAIwasgone,andmostgovernmentfundingforAIprojectswascancelled.AIwasstillarelativelynewfield,academicinnature,withfewpracticalapplicationsapartfromplayinggames.So,totheoutsider,theachievedresultswouldbeseenastoys,asnoAIsystematthattimecouldmanagereal-worldproblems.Unfulfilledpromises,ortheimpactofreality(late1960s–early1970s)ThemaindifficultiesforAIinthelate1960swere:BecauseAIresearchersweredevelopinggeneralmethodsforbroadclassesofproblems,earlyprogramscontainedlittleorevennoknowledgeaboutaproblemdomain.Tosolveproblems,programsappliedasearchstrategybytryingoutdifferentcombinationsofsmallsteps,untiltherightonewasfound.Thisapproachwasquitefeasibleforsimpletoyproblems,soitseemedreasonablethat,iftheprogramscouldbe“scaledup”tosolvelargeproblems,theywouldfinallysucceed.ManyoftheproblemsthatAIattemptedtosolveweretoobroadandtoodifficult.AtypicaltaskforearlyAIwasmachinetranslation.Forexample,theNationalResearchCouncil,USA,fundedthetranslationofRussianscientificpapersafterthelaunchofthefirstartificialsatellite(Sputnik)in1957.Initially,theprojectteamtriedsimplyreplacingRussianwordswithEnglish,usinganelectronicdictionary.However,itwassoonfoundthattranslationrequiresageneralunderstandingofthesubjecttochoosethecorrectwords.Thistaskwastoodifficult.In1966,alltranslationprojectsfundedbytheUSgovernmentwerecancelled.In1971,theBritishgovernmentalsosuspendedsupportforAIresearch.SirJamesLighthillhadbeencommissionedbytheScienceResearchCouncilofGreatBritaintoreviewthecurrentstateofAI.HedidnotfindanymajororevensignificantresultsfromAIresearch,andthereforesawnoneedtohaveaseparatesciencecalled““artificialintelligence””.Thetechnologyofexpertsystems,orthekeytosuccess(early1970s––mid-1980s)Probablythemostimportantdevelopmentintheseventieswastherealisationthatthedomainforintelligentmachineshadtobesufficientlyrestricted.Previously,AIresearchershadbelievedthatcleversearchalgorithmsandreasoningtechniquescouldbeinventedtoemulategeneral,human-like,problem-solvingmethods.Ageneral-purposesearchmechanismcouldrelyonelementaryreasoningstepstofindcompletesolutionsandcoulduseweakknowledgeaboutdomain.Whenweakmethodsfailed,researchersfinallyrealisedthattheonlywaytodeliverpracticalresultswastosolvetypicalcasesinnarrowareasofexpertise,makinglargereasoningsteps.DENDRALDENDRALwasdevelopedatStanfordUniversitytodeterminethemolecularstructureofMartiansoil,basedonthemassspectraldataprovidedbyamassspectrometer.TheprojectwassupportedbyNASA.EdwardFeigenbaum,BruceBuchanan(acomputerscientist)andJoshuaLederberg(aNobelprizewinneringenetics)formedateam.Therewasnoscientificalgorithmformappingthemassspectrumintoitsmolecularstructure.Feigenbaum’’sjobwastoincorporatetheexpertiseofLederbergintoacomputerprogramtomakeitperformatahumanexpertlevel.Suchprogramswerelatercalledexpertsystems.DENDRALmarkedamajor““paradigmshift””inAI:ashiftfromgeneral-purpose,knowledge-sparseweakmethodstodomain-specific,knowledge-intensivetechniques.Theaimoftheprojectwastodevelopacomputerprogramtoattainthelevelofperformanceofanexperiencedhumanchemist.Usingheuristicsintheformofhigh-qualityspecificrules,rules-of-thumb,theDENDRALteamprovedthatcomputerscouldequalanexpertinnarrow,welldefined,problemareas.TheDENDRALprojectoriginatedthefundamentalideaofexpertsystems–knowledgeengineering,whichencompassedtechniquesofcapturing,analysingandexpressinginrulesanexpert’’s“know-how””.MYCINwasarule-basedexpertsystemforthediagnosisofinfectiousblooddiseases.Italsoprovidedadoctorwiththerapeuticadviceinaconvenient,user-friendlymanner.MYCIN’sknowledgeconsistedofabout450rulesderivedfromhumanknowledgeinanarrowdomainthroughextensiveinterviewingofexperts.Theknowledgeincorporatedintheformofruleswasclearlyseparatedfromthereasoningmechanism.Thesystemdevelopercouldeasilymanipulateknowledgeinthesystembyinsertingordeletingsomerules.Forexample,adomain-independentversionofMYCINcalledEMYCIN(EmptyMYCIN)waslaterproduced.MYCINPROSPECTORwasanexpertsystemformineralexplorationdevelopedbytheStanfordResearchInstitute.Nineexpertscontributedtheirknowledgeandexpertise.PROSPECTORusedacombinedstructurethatincorporatedrulesandasemanticnetwork.PROSPECTORhadover1000rules.Theuser,anexplorationgeologist,wasaskedtoinputthecharacteristicsofasuspecteddeposit:thegeologicalsetting,structures,kindsofrocksandminerals.PROSPECTORcomparedthesecharacteristicswithmodelsoforedepositsandmadeanassessmentofthesuspectedmineraldeposit.Itcouldalsoexplainthestepsitusedtoreachtheconclusion.PROSPECTORA1986surveyreportedaremarkablenumberofsuccessfulexpertsystemapplicationsindifferentareas:chemistry,electronics,engineering,geology,management,medicine,processcontrolandmilitaryscience(Waterman,1986).AlthoughWatermanfoundnearly200expertsystems,mostoftheapplicationswereinthefieldofmedicaldiagnosis.Sevenyearslaterasimilarsurveyreportedover2500developedexpertsystems(Durkin,1994).Thenewgrowingareawasbusinessandmanufacturing,whichaccountedforabout60%oftheapplications.Expertsystemtechnologyhadclearlymatured.However:Expertsystemsarerestrictedtoaverynarrowdomainofexpertise.Forexample,MYCIN,whichwasdevelopedforthediagnosisofinfectiousblooddiseases,lacksanyrealknowledgeofhumanphysiology.Ifapatienthasmorethanonedisease,wecannotrelyonMYCIN.Infact,therapyprescribedfortheblooddiseasemightevenbeharmfulbecauseoftheotherdisease.Expertsystemscanshowthesequenceoftherulestheyappliedtoreachasolution,butcannotrelateaccumulated,heuristicknowledgetoanydeeperunderstandingoftheproblemdomain.Expertsystemshavedifficultyinrecognisingdomainboundaries.Whengivenataskdifferentfromthetypicalproblems,anexpertsystemmightattempttosolveitandfailinratherunpredictableways.Heuristicrulesrepresentknowledgeinabstractformandlackevenbasicunderstandingofthedomainarea.Itmakesthetaskofidentifyingincorrect,incompleteorinconsistentknowledgedifficult.Expertsystems,especiallythefirstgeneration,havelittleornoabilitytolearnfromtheirexperience.Expertsystemsarebuiltindividuallyandcannotbedevelopedfast.Complexsystemscantakeover30person-yearstobuild.Howtomakeamachinelearn,ortherebirthofneuralnetworks(mid-1980s–onwards)Inthemid-eighties,researchers,engineersandexpertsfoundthatbuildinganexpertsystemrequiredmuchmorethanjustbuyingareasoningsystemorexpertsystemshellandputtingenoughrulesinit.DisillusionsabouttheapplicabilityofexpertsystemtechnologyevenledtopeoplepredictinganAI““winter””withseverelysqueezedfundingforAIprojects.AIresearchersdecidedtohaveanewlookatneuralnetworks.Bythelatesixties,mostofthebasicideasandconceptsnecessaryforneuralcomputinghadalreadybeenformulated.However,onlyinthemid-eightiesdidthesolutionemerge.Themajorreasonforthedelaywastechnological:therewerenoPCsorpowerfulworkstationstomodelandexperimentwithartificialneuralnetworks.Intheeighties,becauseoftheneedforbrain-likeinformationprocessing,aswellastheadvancesincomputertechnologyandprogressinneuroscience,thefieldofneuralnetworksexperiencedadramaticresurgence.Majorcontributionstoboththeoryanddesignweremadeonseveralfronts.Grossbergestablishedanewprincipleofself-organisation(adaptiveresonancetheory),whichprovidedthebasisforanewclassofneuralnetworks(Grossberg,1980).Hopfieldintroducedneuralnetworkswithfeedback––Hopfieldnetworks,whichattractedmuchattentionintheeighties(Hopfield,1982).Kohonenpublishedapaperonself-organisingmaps(Kohonen,1982).Barto,SuttonandAndersonpublishedtheirworkonreinforcementlearninganditsapplicationincontrol(Bartoetal.,1983).Buttherealbreakthroughcamein1986whentheback-propagationlearningalgorithm,firstintroducedbyBrysonandHoin1969(Bryson&Ho,1969),wasreinventedbyRumelhartandMcClellandinParallelDistributedProcessing(1986).ArtificialneuralnetworkshavecomealongwayfromtheearlymodelsofMcCullochandPittstoaninterdisciplinarysubjectwithrootsinneuroscience,psychology,mathematicsandengineering,andwillcontinuetodevelopinboththeoryandpracticalapplications.Theneweraofknowledgeengineering,orcomputingwithwords(late1980s–onwards)Neuralnetworktechnologyoffersmorenaturalinteractionwiththerealworldthandosystemsbasedonsymbolicreasoning.Neuralnetworkscanlearn,adapttochangesinaproblem’’senvironment,establishpatternsinsituationswhererulesarenotknown,anddealwithfuzzyorincompleteinformation.However,theylackexplanationfacilitiesandusuallyactasablackbox.Theprocessoftrainingneuralnetworkswithcurrenttechnologiesisslow,andfrequentretrainingcancauseseriousdifficulties.Classicexpertsystemsareespeciallygoodforclosed-systemapplicationswithpreciseinputsandlogicaloutputs.Theyuseexpertknowledgeintheformofrulesand,ifrequired,caninteractwiththeusertoestablishaparticularfact.Amajordrawbackisthathumanexpertscannotalwaysexpresstheirknowledgeintermsofrulesorexplainthelineoftheirreasoning.Thiscanpreventtheexpertsystemfromaccumulatingthenecessaryknowledge,andconsequentlyleadtoitsfailure.Veryimportanttechnologydealingwithvague,impreciseanduncertainknowledgeanddataisfuzzylogic.Humanexpertsdonotusuallythinkinprobabilityvalues,butinsuchtermsasoften,generally,sometimes,occasionallyandrarely.Fuzzylogicisconcernedwithcapturingthemeaningofwords,humanreasoninganddecisionmaking.Fuzzylogicprovidesthewaytobreakthroughthecomputationalbottlenecksoftraditionalexpertsystems.Attheheartoffuzzylogicliestheconceptofalinguisticvariable.Thevaluesofthelinguisticvariablearewordsratherthannumbers.FuzzylogicorfuzzysettheorywasintroducedbyProfessorLotfiZadeh,Berkeley’’selectricalengineeringdepartmentchairman,in1965.Itprovidedameansofcomputingwithwords.However,acceptanceoffuzzysettheorybythetechnicalcommunitywasslowanddifficult.Partoftheproblemwastheprovocativename––““fuzzy””––itseemedtoolight-heartedtobetakenseriously.Eventually,fuzzytheory,ignoredintheWest,wastakenseriouslyintheEast––bytheJapanese.Ithasbeenusedsuccessfullysince1987inJapanese-designeddishwashers,washingmachines,airconditioners,televisionsets,copiers,andevencars.Benefitsderivedfromtheapplicationoffuzzylogicmodelsinknowledge-basedanddecision-supportsystemscanbesummarisedasfollows:Improvedcomputationalpower:Fuzzyrule-basedsystemsperformfasterthanconventionalexpertsystemsandrequirefewerrules.Afuzzyexpertsystemmergestherules,makingthemmorepowerful.LotfiZadehbelievesthatinafewyearsmostexpertsystemswillusefuzzylogictosolvehighlynonlinearandcomputationallydifficultproblems.Improvedcognitivemodelling:Fuzzysystemsallowtheencodingofknowledgeinaformthatreflectsthewayexpertsthinkaboutacomplexproblem.Theyusuallythinkinsuchimprecisetermsashighandlow,fastandslow,heavyandlight.Inordertobuildconventionalrules,weneedtodefinethecrispboundariesforthesetermsbybreakingdowntheexpertiseintofragments.Thisfragmentationleadstothepoorperformanceofconventionalexpertsystemswhentheydealwithcomplexproblems.Incontrast,fuzzyexpertsystemsmodelimpreciseinformation,capturingexpertisesimilartothewayitisrepresentedintheexpertmind,andthusimprovecogniti