人工智能英文介紹

ArtificialIntelligenceFall2008FrankHadlock人工智能英文介紹全文共42頁，當(dāng)前為第1頁。DefinitionsofAIThestudyofrepresentationandsearchthroughwhichintelligentactivitycanbeenactedonamechanicaldevice.Thestudyofproblemsatwhichhumanbeingsarecurrentlymoreadeptthancomputersatsolvingandthetranslationandimprovementofhumansolutionsintoformswhichcanbeimplementedonacomputer.人工智能英文介紹全文共42頁，當(dāng)前為第2頁。PhysicalsymbolsystemhypothesisThephysicalsymbolsystemhypothesis(PSSH),firstformulatedbyNewellandSimonintheirTuringAwardpaper,1statesthat“aphysicalsymbolsystem[suchasadigitalcomputer,forexample]hasthenecessaryandsufficientmeansforintelligentaction.”Thehypothesisimpliesthatcomputers,whenweprovidethemwiththeappropriatesymbol-processingprograms,willbecapableofintelligentaction.Italsoimplies,asNewellandSimonwrote,that“thesymbolicbehaviorofmanarisesbecausehehasthecharacteristicsofaphysicalsymbolsystem.”人工智能英文介紹全文共42頁，當(dāng)前為第3頁。HistoryGraphtheory&statespacerepresentation(Euler)Booleanalgebra–propositionalcalculus(Boole)Predicatecalculus–(Frege)DescartesDiscourseTuring’sTestPhysicalSymbolSystemHypothesisConnectionism

人工智能英文介紹全文共42頁，當(dāng)前為第4頁。Discourse-DescartesIfthereweremachineswhichborearesemblancetoourbodiesandimitatedouractionsascloselyaspossibleforallpracticalpurposes,weshouldstillhavetwoverycertainmeansofrecognizingthattheywerenotrealmen.Thefirstisthattheycouldneverusewords,orputtogethersigns,aswedoinordertodeclareourthoughtstoothers.Forwecancertainlyconceiveofamachinesoconstructedthatitutterswords,andevenutterswordsthatcorrespondtobodilyactionscausingachangeinitsorgans.…Butitisnotconceivablethatsuchamachineshouldproducedifferentarrangementsofwordssoastogiveanappropriatelymeaningfulanswertowhateverissaidinitspresence,asthedullestofmencando.Secondly,eventhoughsomemachinesmightdosomethingsaswellaswedothem,orperhapsevenbetter,theywouldinevitablyfailinothers,whichwouldrevealthattheyareactingnotfromunderstanding,butonlyfromthedispositionoftheirorgans.Forwhereasreasonisauniversalinstrument,whichcanbeusedinallkindsofsituations,theseorgansneedsomeparticularaction;henceitisforallpracticalpurposesimpossibleforamachinetohaveenoughdifferentorganstomakeitactinallthecontingenciesoflifeinthewayinwhichourreasonmakesusact.(TranslationbyRobertStoothoff)人工智能英文介紹全文共42頁，當(dāng)前為第5頁。TuringTestTheTuringtestisaproposalforatestofamachine'sabilitytodemonstrateintelligence.DescribedbyAlanTuringinthe1950paper"ComputingMachineryandIntelligence,"itproceedsasfollows:ahumanjudgeengagesinanaturallanguageconversationwithonehumanandonemachine,eachofwhichtrytoappearhuman;ifthejudgecannotreliablytellwhichiswhich,thenthemachineissaidtopassthetest.Inordertotestthemachine'sintelligenceratherthanitsabilitytorenderwordsintoaudio,theconversationislimitedtoatext-onlychannelsuchasacomputerkeyboardandscreen(Turingoriginallysuggestedateletypemachine,oneofthefewtext-onlycommunicationsystemsavailablein1950).人工智能英文介紹全文共42頁，當(dāng)前為第6頁。AIApplicationAreasGamePlayingAutomatedReasoningExpertSystemsNaturalLanguageUnderstandingModelingHumanPerformancePlanningandRoboticsLanguagesforAI(Clips,LispandProlog)MachineLearningNeuralnetsandGeneticAlgorithmsIntelligentAgents人工智能英文介紹全文共42頁，當(dāng)前為第7頁。Boardgamescanberepresentedbyausuallylargebutfinitesetofboardconfigurationsorstates.ThesquaresofTicTacToecanbenumbered1..9andeachconfigurationasasequenceover{H,C,B}wheremanyofthe39cannotoccurbecauseoforderofplay.AstateBCBBBBBBBmaybefollowedbyanyofeightstatesobtainedbyreplacinganyoftheeightBsbyanH.BBBBBBBBBistheinitialstateandanystatewitharoworcolumnordiagonalconsistingofallCsisawinningstatefortheComputer.Ifthecomputercanfindapathfromstarttowinningstate,thepathcorrespondstoawinforthecomputerandfindingsuchapathconstitutesanexampleofartificialintelligence.GamePlayingandStateSpaceSearch人工智能英文介紹全文共42頁，當(dāng)前為第8頁。Graphtheory:ThecityofK?nigsberg

Thecityisdividedbyariver.Therearetwoislandsattheriver.Thefirstislandisconnectedbytwobridgestobothriverbanksandisalsoconnectedbyabridgetotheotherisland.Thesecondislandtwobridgeseachconnectingtooneriverbank.Question:Isthereawalkaroundthecitythatcrosseseachbridgeexactlyonce?SwissmathematicianLeonhardEulerinventedgraphtheorytosolvethisproblem.人工智能英文介紹全文共42頁，當(dāng)前為第9頁。ThecityofK?nigsberg人工智能英文介紹全文共42頁，當(dāng)前為第10頁。GraphoftheK?nigsbergbridgesystem人工智能英文介紹全文共42頁，當(dāng)前為第11頁。EulerCircuitsAgraphhasanEulercircuitiffitisconnectedandeveryvertexisofevendegree.Necessity–Eulercircuitentersavertexeachtimeonanewedgeandleavesthevertexonanewedge.Sovertexhasdegree2*numberoftimesoncircuitSufficiency–Pickstartingvertexandtraversegraph,eachtimepickingnewedge.Canonlybeblockedatstart.EitherhaveEulercircuitorcanpickvertexwithunusededgeoncircuitandbuildsubtourstartingwithit.Splicesubtourin.Eventuallywillhaveusedalledgesonce.人工智能英文介紹全文共42頁，當(dāng)前為第12頁。StatespacesearchRepresentedbyafour-tuple[N,A,S,GD],where:Nistheproblemspace

Aisthesetofarcs(orlinks)betweennodes.Thesecorrespondtotheoperators.

SisanonemptysubsetofN.Itrepresentsthestartstate(s)oftheproblem.

人工智能英文介紹全文共42頁，當(dāng)前為第13頁。StateSpaceSearchcontinuedGDisanonemptysubsetofN.Itrepresentsthegoalstate(s)oftheproblem.ThestatesinGDaredescribedusingeither:

ameasurablepropertyofthestates

apropertyofthepathdevelopedinthe

search(asolutionpathisapathfrom

nodeStoanodeinGD)人工智能英文介紹全文共42頁，當(dāng)前為第14頁。The8-puzzleproblemasstatespacesearchstates:possibleboardpositionsoperators:oneforslidingeachsquareineachoffourdirections,

or,better,oneformovingtheblanksquareineachoffourdirectionsinitialstate:somegivenboardpositiongoalstate:somegivenboardpositionNote:the“solution”isnotinterestinghere,weneedthepath.人工智能英文介紹全文共42頁，當(dāng)前為第15頁。EightPuzzle1437658214376258人工智能英文介紹全文共42頁，當(dāng)前為第16頁。Statespaceofthe8-puzzlegeneratedby“moveblank”operations人工智能英文介紹全文共42頁，當(dāng)前為第17頁。TravelingsalespersonproblemasstatespacesearchThesalespersonhasncitiestovisitandmustthenreturnhome.Findtheshortestpathtotravel.statespace:operators:initialstate:goalstate:人工智能英文介紹全文共42頁，當(dāng)前為第18頁。AutomatedReasoningandTheoremProvingLogicsystemsbeganwithPropositionalCalculusinwhichdeclarativestatementswithatruthvalueoftrueorfalsearerepresentedbyP,Q,R,etcandcombinedwithlogicoperatorsOr,And,Not,If.Asentencesuchas“BillmusttakeCSC2020”isrepresentedbyletterPandistrueorfalse.PropositionalCalculuswasextendedtoPredicateCalculusbyaddingPredicates(relations),variables,andquantifiers(ForAllandThereExists).Asentencesuchas“EveryCSmajormusttakeCSC2020”isrepresentedby“(ForAllX)(CSMajor(X)MustTake(CSC2020))”GivensomefactsexpressedineitherPropositionalorPredicateCalculus,newfactsorknowledgeisinferredbyinferencerulessuchasmodusponensorresolution.Ifthecomputercanfindapathfromgivenfactstoanewtheorem,thepathcorrespondstoaproofandfindingsuchapathconstitutesanexampleofartificialintelligence人工智能英文介紹全文共42頁，當(dāng)前為第19頁。PropositionalLogicAdeclarativestatementsuchas“BillisaCSstudent”hasatruthvalueofTorFandisdenotedbyP(atruthvariable)Propositionsmaybecombinedwithlogicaloperatorsandthecompositestatementhasvalueasshownbelow.PQistrueifeitherPorQaretrueandfalseifbotharefalsePQistrueifbothPandQaretrueandfalseifeitherisfalse.?PistrueifPisfalseandfalseifPistruePQistrueifPandQhavethesametruthvalueandfalseiftheirvaluesdifferPQisfalseifPistrueandQisfalseandtrueotherwise.Atautologyisalwaystrue.PQ?PQisatautology.P(QR)(PQ)(PR)isatautology.人工智能英文介紹全文共42頁，當(dāng)前為第20頁。RulesofInferenceP,PQthenQ-modusponens?Q,PQthen?P-modustollens人工智能英文介紹全文共42頁，當(dāng)前為第21頁。ExpertSystemsGeneralproblemsolvinghasbeenattemptedinAIbutwithoutsuccess.Instead,systemshavebeendevelopedwhichspecializeindomain-specificknowledgesuchasmedicine.Peoplewhoworkintheseareasarecalleddomainexpertsandsolveproblemsbyusingdomain-specificruleswhichareappliedtofactsorknowledgeintheknowledgebase.Generalproblemclassessolvablebyexpertsystems(whichreplacethedomainexperts)arediagnosticproblems(backwardchaining)anddesignorconfigurationproblems(forwardchaining).Whenapathisfoundfromaconditionbackwardtoasetoffactscausingthecondition(orviseversa),thepathcorrespondstoadiagnosis(ordesign)andfindingsuchapathconstitutesanexampleofartificialintelligenceNaturalLanguageUnderstanding&SemanticsTranslationfromtextinonenaturallanguagetoanotherrequiresmorethanvocabularysubstitutionbecauseoftheinherentambiguityofnaturallanguages.Toresolvethisambiguityrequirescontextualknowledgeintheformofaworldmodel.Asanexample,apunctuationsymbol“,”canhavethemeaningofalistseparator,orbeusedinplaceof“then”,orbeusedtodelimitadanglingmodifier.Anotherexampleisthetransaltionof“hydraulicram”inEnglishintotheRussianequivalentof“watergoat”.Inthislastexample,aworldmodelwouldsaythatthereissuchananimalasa“waterbuffalo”butnota“watergoat”.Translationusuallyinvolvessyntacticanalysisfollowedbysemanticanalysisandatranslationpathfromsourcetotargetconstitutesanexampleofartificialintelligence人工智能英文介紹全文共42頁，當(dāng)前為第22頁。ModelingHumanPerformanceMuchofartificialintelligenceisconcernedwithduplicatingorsurpassinghumaningenuityonthecomputerwithnoconcernwithhowhumansperform.Cognitivemodelingisconcernedwithusingcomputerstodeterminehumanperformance.Computerbasedtutoringisanexamplewhichhasbeenappliedtotutoringalgebrastudentstosolvewordproblems.CognitivemodelingsystemssuchasACTmodelhumanperformancewithrulesorproductions.Thetutorinteractswiththestudentbyposingaproblemandthenposingquestions,attemptingtoguidethestudenttoacorrectsolution.Byexaminingtheresponses,thetutoreitherposesanotherquestioncorrespondingtoacorrectstepinthesolution,ordiagnosesanincorrect“buggy”rulebeingusedbythestudent.Inthiscase,thetutorrevertsbacktoapreviousconceptneededinthecorrectsolution.ApathfromproblemstatementtoanyintermediatestateconstitutesanexampleofartificialintelligencePlanningandRoboticsDiscussionofplanningandroboticshereisconfinedtomotionplanningintwodimensions.AbasicassumptioninthisdiscussionisthattheEuclideancoordinatesareavailableforthepositionoftherobot,ofobstacles,andofgoals.Motionplanningisaccomplishedbyworkingwiththestatespaceofpositionswherepositionsareconnectedbyanedgeifthereisnointerveningobstacle.Apathfrominitialpositiontoagoalpositionisasolutiontotheproblemofmotionplanningthatconstitutesanexampleofartificialintelligence.人工智能英文介紹全文共42頁，當(dāng)前為第23頁。CognitiveAlgebraTutorsAlgebraclassmaybelessdifficultandabitmorefunthesedays,thankstoresearchonhowhumancognitionworks.DevelopedovertwodecadesbypsychologistJohnAnderson,theAdaptiveCharacterofThought(ACT-R)theoryisaframeworkforunderstandinghowwethinkaboutandattackproblems,includingmathequations.Thetheoryreflectsourunderstandingohumancognitionbasedonnumerousfactsderivedfrompsychologicalexperiments.ACT-Rsuggeststhatcomplexcognitionarisesfromaninteractionofproceduralanddeclarativeknowledge.Declarativeknowledgeisafairlydirectencodingoffacts(suchasWashington,DCisthecapitaloftheUnitedStates,5+3=8);proceduralknowledgeisafairlydirectencodingofhowwedothings(suchhowtodriveorhowtoperformaddition).AccordingtotheACT-Rtheory,thepowerofhumancognitiondependsonhowpeoplecombinethesetwotypesofknowledge.SignificanceTheACT-Rtheoryprovidesinsightsintohowstudentslearnnewskillsandconcepts,and,indoingsoallowsteacherstoseewherestudentsmayneedextrapracticetomasterthenewwork.PracticalApplicationDr.AndersonandcolleaguesatCarnegieMellonUniversityhaveusedthisresearchtodevelopcognitivetutors,computer-tutoringprogramsthatincorporatetheACT-Rtheoryintheteachingofalgebra,geometryandintegratedmath.Thetutorsarebasedoncognitivemodelsthattaketheformofcomputersimulationsthatarecapableofsolvingthetypesofproblemsthatstudentsareaskedtosolve.Thetutorsincorporatethedeclarativeandproceduralknowledgeimbeddedintheinstructionandmonitorstudents’problemsolvingtodeterminewhatthestudentsknowanddon’tknow.Thisallowsinstructiontobedirectedatwhatstillneedstobemasteredandhelpsinsurethatstudents’learningtimeisspentinamoreefficientmanner.Studentsworkonaconceptuntilitisfullyunderstood.Studentswhoarehavingconceptualproblemswillbedrilledoninthatarea,whilethosewhohavemasteredtheconceptmoveontootherareas.Themostwidelyusedcognitivetutorprogram–nowknownasCarnegieLearning’sCognitiveTutor-combinessoftware-based,individualizedcomputerlessonswithcollaborative,real-worldproblem-solvingactivities.Theprogramnowservesmorethan150,000studentsinmostofthenation’slargestschooldistricts.Fieldstudieshaveshowndramaticstudentachievementgainswheretheprogramisinuse.In2003,theU.S.DepartmentofDefenseSchoolsawardedacontractthatwilluseCognitiveTutormathematicscurriculainits224publicschoolsin21districtslocatedin14foreigncountries,sevenstates,GuamandPuertoRico.Theseschoolshaveapproximately8,800teachersserving106,000students.CitedResearchAnderson,J.R.(1983).Thearchitectureofcognition.Cambridge:MA:HarvardUniversityPress.Anderson,J.R.(1993).RulesoftheMind.Hillsdale,NJ:Erlbaum.人工智能英文介紹全文共42頁，當(dāng)前為第24頁。LispLispisthefirstlanguageusedinArtificialIntelligenceandisstructuredsothatalistiseitherdataorafunctioncall.Inthecaseofafunctioncall,Lispusesprefixnotationwhichmeansthatthefirstlistitemisthenameofthefunctionandtheremainingitemsarethearguments.Lispindicatesvariablesbyaquestionmark.Toillustrate(forall?x(implies(cs_student?x)(must_take?xdata_structures)))(cs_studentbill)Wouldyield(must_takebilldata_structures)PrologPrologisalogicprogramminglanguagebasedonpredicatelogic.Prologusescapitallettersforvariablesandlowercaselettersforpredicatesandconstantsandreversestheorderforimplication.InsteadofwritingPQ,PrologordersimplicationasQ:-P.Acommaisusedtoseparateargumentsandforconjunctionwithaperiodmarkingtheendofasentence.Toillustrate,cs_student(bill).must_take(data_structures,X):-cs_student(X)Thefirstsentenceassertsafactthat“bill”isacs_studentwhilethesecondsentenceassertsthatanycs_studentmusttakedatastructures.Prologislaunchedbyagoalsuchas:-must_take(data_structures,Y)whichwouldreturnmust_take(data_structures,bill)人工智能英文介紹全文共42頁，當(dāng)前為第25頁。CLIPS

Clipsorganizesknowledgebyusingnamedfacttemplatesconsistingofnamedslots.AnexampleisthePAYtemplatewithslotsforhoursandpayrate.Thedeffactsstatementcreatesinitialfactsaccolrdingtoselectedtemplates.Anexampleisthepayrollstatementwhichassignsaninitialfactof44hoursandofarateof$8/hour.

FactList(deftemplatepay(slothours)(slotrate))(deffactspayroll(pay(hours44)(rate8))(statusincomplete))人工智能英文介紹全文共42頁，當(dāng)前為第26頁。CLIPS

Clipsinfersnewknowledgebyusingnamedruletemplatesconsistingofanantecedentwhichmustmatchfactsinthefactlistandaconsequentwhichaddsormodifiesfacts.FactListRuleList(defrulecalculate_basic?p<-(pay(hours?h)(rate?r))(test(<=?h40))=>(assert(basic_pay(*?h?r)))(retract?p))人工智能英文介紹全文共42頁，當(dāng)前為第27頁。CLIPSRuleListRuleList(defrulecalculate_basic?p<-(pay(hours?h)(rate?r))(test(<=?h40))=>(assert(basic_pay(*?h?r)))(retract?p))(defrulecalculate_overtime(pay(hours?h)(rate?r))(test(>?h40))(statusincomplete)=>(assert(overtime(*(-?h40)(*?r1.5)))))(defrulecalculate_regular(pay(hours?h)(rate?r))(statusincomplete)(test(>?h40))=>(assert(regular(*40?r))))(defrulecalculate_adjustedgross(regular?r)(overtime?o)(statusincomplete)=>(assert(adjusted_gross(+?r?o)))(assert(statusdone)))(deftemplatepay(slothours)(slotrate))(deffactspayroll(pay(hours44)(rate8))(statusincomplete))人工智能英文介紹全文共42頁，當(dāng)前為第28頁。NeuralNetsAnartificialneuronconsistsofinputsxi,I=1..n,whichhaveavalueof0or1.Eachinputxicancollectavaluefromtheenvironmentorfromtheoutputofanotherneuronandanassociatedweightwi.Aneuronisactivatedifthesumoftheweightedinputswixiexceedsathresholdfunctionf.Theneuronoutputsa1ifactivatedandotherwiseoutputsa0.Twosetsofpointsin2dimensionalspacearelinearlyseparableiftheycanbeseparatedbyastraightline.Inthiscase,thepointscanbeclassifiedbyasingleneuronwhichoutputsa0forpointsononesideofthelineanda1forpointsontheotherside.Thisclassificationisanexampleofartificialintelligence.ThepointsetsclassifiedbyalogicalOrgateandthoseclassifiedbyalogicalAndgatearelinearlyseparablebutnotthoseclassifiedbyanExclusiveOr.GeneticAlgorithmsGeneticalgorithmsarebasedonabiologicalmetaphorofevolvingsolutionstoaproblem.Thesolutionsarestringsoversomealphabetandarereferredtoasgenes.GivenaninitialpopulationP0,eachmembergeneisevaluatedbyafitnessfunctionspecifictotheproblemForexample,fortheknapsackfunction,thegenemightbealistofobjectindicestobeincludedandthefitnessmightbethewastedspaceintheknapsack.Membersareselectedbasedonfitnessandoffspringarecreatedusingcrossoverandmutationoperatorstoformthenextpopulation.Theprocesshaltsaftersomanypopulationsandthemostfitmemberofthefinalpopulationisselectedasthesolutiontotheproblem人工智能英文介紹全文共42頁，當(dāng)前為第29頁。RepresentationandSearchRepresentationofProblemInformationPropositional&PredicateLogicSemanticnetworksStateSpacesetofproblemstatesalongwithtransitionsbetweenstatesandasetofstartstatesandgoalstates.apathfromstarttogoalisasolution

SearchTechniquesforfindingasolution

人工智能英文介紹全文共42頁，當(dāng)前為第30頁。EightPuzzleRepresentation–Thesquaresoftheeightpuzzlecanberepresentedbyintegers1..8and9representsemptysquare.Astateofthepuzzleisapermutationof1..9where1stthreerepresenttoprow,2ndthreerepresentmiddlerow,and3rdthreerepresentbottomrow.人工智能英文介紹全文共42頁，當(dāng)前為第31頁。EightpuzzletransitionsAneightpuzzletransitionconsistsofmovingasquarenumbered1..8intotheadjacentvacantsquarewhichcanonlybedoneifitisadjacenttothenumberedsquare.Representationofaboardconfigurationisapermutationof1..9where9representsvacantsquare.Example–132496758represents1strow132,2ndrow4blnk6,3rdrow748.Sincetheblankisinthemiddleposition,3canbemoveddown,or4totheright,or6totheleft,or5movedup.Thesetransitionsmake132496758haveneighbors192436758,132946758,132469758,and132456798.人工智能英文介紹全文共42頁，當(dāng)前為第32頁。KnowledgeRepresentationEssentialtoartificialintelligencearemethodsofrepresentingknowledge.Besidespropositionalandpredicatelogic,anumberofothermethodshavebeendeveloped,including:SemanticNetworksConceptualDependenciesScriptsFrames人工智能英文介紹全文共42頁，當(dāng)前為第33頁。SemanticNetworksModelsmeaningoflanguage:NodescorrespondtowordconceptsArcsarelabeledwithapropertyname

orrelationshipandlinkanode(wordconcept)withanother(valueofproperty).Quillian(1967)introducedsemanticnetworkswhileothers(Simmons-1973,Brachman-1979,Schank-1979)haveextendedthemodel.人工智能英文介紹全文共42頁，當(dāng)前為第34頁。SemanticNetworks

StandardizationofRelationshipsStandardizationofrelationshipsforrepresentingknowledgeexpressedinlanguagefocusesoncaserelationsbetweenverbsandnounsinsentence(Fillmore’68,Simmons’73)Prepositionsorarticlesindicaterelationshipbetweenverbandnoun:Agent:entityperformingtheactionObject:entityacteduponInstrument:entityusedinperformingtheactionEtc.人工智能英文介紹全文共42頁，當(dāng)前為第35頁。ConceptualDependencies

SetofPrimitiveActionsStandardizationofrelationsledtoaxiomaticapproachtobuildsemanticmodelforrepresentingmeaningoflanguageFourPrimitiveConceptClassesACTS-ActionsPPs–Objects(Pictureproducers)AAs–Modifiersofactions(ActionAiders)PAs–Modifiersofobjects(pictureaiders)EachActionisassumedtoreducetooneormoreoftheprimitiveACTsATRANS–transferrelationship(give)PTRANS–transferphysicallocation(go)PROPELMOVEGRASPINGESTEXPELMTRANSMBUILDCONCSPEAKATTEND人工智能英文介紹全文共42頁，當(dāng)前為第36頁。BuildingComplexConceptualDependenciesConceptualDependencySemanticsExamplePPACTAnactoract