CS 5100：基礎(chǔ)人工智能

CS5100:Founda.onsofAr.?cialIntelligence

IntroductiontoAI,Agents,andPython

Prof.AmySlivaSeptember8,2011

Outline

WhatisAI?

Syllabusandcourseadministration

(Very)briefhistoryofAI

IntelligentAgents

IntroductiontoPython

Whatisar.?cialintelligence?

ArtiEicialsystemswithhumanlikeabilitytothink,understand,andreason(cf.cognitivescience)

SolveproblemstoolargetoEindthebestansweralgorithmically

Heuristic(incomplete)methods

Solveproblemsthatarenotwell--‐understood

Howdowedeterminesuccess?

Gettingthe“rightanswer”?

TheTuringTest(ormodiEiedversions)?

Usefulnessoftheresultingtechniques?

Knowitwhenweseeit?

Ar.?cialsystemswithhumanlikeabilitytounderstandandreason

Maintechniques

Ontologies,automatedreasoning,formallogic,state--‐spacesearch,evidentiallogics(probability,fuzzylogic,…),Bayesianinferencenets,Markovmodels

Applications

Problem--‐solving/planning,naturallanguageprocessing,intelligenceHCI,problem--‐solvingunderuncertainty,decisionsupportsystems(“expertsystems”)

Solveproblemstoolargeto?ndthebestansweralgorithmically

Maintechniques

Heuristicsearch,dependency--‐directedbacktracking

Applications

Productionschedulingandotherconstraintsatisfactionproblems,gameplaying

Acomponentinlarge--‐scalereasoningandplanningsystems

Solveproblemsthatarenotwell--‐understood

Maintechniques

Weightedrule--‐basedsystems,Bayesianinferencenets,statisticalinductionandmachinelearningingeneral

Applications

Finance,searchengines,computationalscience(discovery),datamining

Computervision:systemsthatseeandrecognizeobjects

Gooversyllabus

HistoryofAI

1960s—Initialoptimism

EarlyML

Samuel’sCheckersplayer

GeneralProblemSolver(GPS)—Simon&Newell

Employedmeans--‐endsanalysis(precursorofbackwardchainingnowusedinmanysystems)

MatchAtoBtoEinddifferenceD

Subgoal:ReduceD

A’

TransformA’intoB

Goal:TransformsituationAtosituationB

fail

none

Success Fail Fail

fail

Moreonmeans--‐endsanalysis

Goal:ReducedifferenceDbetweensituationsAandB

Success

SearchforoperatorQrelevantforreducingD

Subgoal:ApplyQtoAproducingA’

A’

none

fail

Fail

Goal:ApplyoperatorQtoA

MatchAtotheconditionsofQ,EinddifferenceF

A’’

Subgoal:ReduceF ApplyQtoA’’

A’

Success

none

failFail

failFail

HistoryofAI(cont.)

1970s--‐mid80s—Knowledge--‐basedsystems

“Micro--‐world”experiments

SHRDLU(TerryWinograd)

Rule--‐based“expert”systems

DENDRAL,MYCIN(EdFeigenbaum)

Acceptancebyindustry—hugeoversell

Theknowledgeacquisitionbottleneck

HistoryofAI(cont.)

Late80s–mid90s—AIWinter

Hopespinnedonneuralnets/MLtoovercomeKAbottleneck

Late90stopresent—morecomputingpower

Riseofprobabilisticapproaches

LexicaltaggingbreakthroughinNLP

Morerigorousexperiments/evaluationmethods

2000s—inEluenceofthewebrevivesAI

MassivetextcorpusesandneedforbetterwebbrowsersinspireNLP

Hardwareadvancesinspirerobotics

Intelligentagents/webbots—applicationstoe--‐commerce

Environment

Agent

Sensors

Percepts

Actuators

Actions

?

Agentsandenvironments

Frameworkforintelligentagentdesign

Whatcantheagentdo?(rangeofpossibleactions)

Whatabouttheenvironment?

Inputstotheprogramarecalledpercepts

Symbolicinputfromkeyboard,Eiles,networks

Sensordatafromthephysicalworld

Oftenmustbeinterpretedintomeaningfulconcepts

Whatcantheagentknow?

Historyofitsownpreviousinputsandactions

Propertiesoftheenvironmentandworldknowledge

Knowledgeofitsowngoals,preferences,etc.

Strategiesforitsbehavior

Describetheagent’sbehaviorwithanagentfunction

Mappingofanyperceptsequencetoanaction

Implementedinternallybytheagentprogram

Vacuum--‐cleanerworld

B

A

Percepts:locationandcontents,e.g.,[A,Dirty]

Actions:Left,Right,Suck,NoOp

Typesofagents

SimplereElexagent

No“state”ormemory

Reactstocurrentinputaccordingtoitsprogram(rulesoftheform“ifconditionthenaction”)

Model--‐basedagent

Usesanexplicitknowledgebasetomodeltheenvironment

Howdoestheenvironmentevolveindependently

Howdoestheagentaffecttheenvironment

Exhibits“understanding”ofitsinputbyrelatingittopriorknowledge

Reactsaccordingtorules

Conditionsmaybecomplexandrequireinferencetoevaluate

Typesofagents(cont.)

Planningagents(goal--‐basedandutility--‐basedagents)

Explicitlyrepresenttheirowngoalsand/orpreferences

(“utilities”)andcanreasonaboutthem(i.e.,planning)

Exhibitautonomy—actionsdonotfollowdirectlyfromrule--‐basedlookup

Learningagents

Supervisedlearning—Learnfrompositiveandnegative

examples

Reinforcementlearning—Learnfromexperiencetoimproveitsoutcomes

Agentprogramimplementa.on

Table--‐drivenapproach—intractable

Uselookuptabletomatchthesequenceofperceptstoanaction

Embeddedrepresentation—speciEictooneenvironment

Programstatements:

ifstatus=DirtythenreturnSuck

elseiflocation=AthenreturnRight

elseiflocation=BthenreturnLeft

Declarativerepresentation—general

Programstatements:

Useproductionrulebase:conditionaction

Ifperceptmatchesconditionthenreturnaction

B

A

Agent

Sensors

Condition-actionrules

Actuators

WhatactionIshoulddonow

Whattheworldislikenow

Environment

Declara.vesimplere?exagent

Drawbacksofproductionrulesystems

HUGErulebase—timeconsumingtobuildbyhand

WhatifmorethanoneconditionissatisEied?

InElexible(noadaptationorlearning)

Represen.ngagentknowledge

Q:Whatformallanguage(s)canweusetorepresent

Currentfactsaboutthestateoftheworld?

Amodelofhowtheworldbehaves?

Amodeloftheeffectsofactionsthattheagentcanperform?

Theproductionrulesthatspecifyagentbehavior?

A:Formallogic

Syntaxandsemanticsarewellunderstood

Computationaltractabilityknownforimportantsubsets(e.g.,Hornclauselogic)

Howdowedeterminesuccess?

Gettingthe“rightanswer”?

TheTuringTest(ormodiEiedversions)?

Havingagoodoutcome?(usingsome“utility”function)

Knowitwhenweseeit?

Analyzingagentperformance

Rationalagentisonethatdoesthe“right”thing

MustdeEineaperformancemeasure

Costs(penalties)andrewards

Choosesanactionthatmaximizesexpectedscore

Rationalitydependson

SuccesscriteriondeEinedbyperformancemeasure

“Behavior”oftheenvironment(e.g.,canacleansquaregetdirtyagain?)

Possibleactions

Perceptsequence

Autonomy

Rationalagentsrequirelearningtocompensateforincorrectorincompletestartingknowledge

Introduc.ontoPython

DevelopedbyCWIin1989

Features

Interpreted

Dynamictyping

Easilyreadablecodeblocks

Object--‐oriented—alldataisrepresentedbyobjectsorrelationsbetweenobjects

GoodforAI—easytolearn,easytoimplementAIconcepts

Wewilluserelease2.x

Wri.ngandrunningPython

Interpreter

python<Eile>.py

Executesthestatementsin<Eile>.py

Interactivemode

Executablescripts

#!/usr/bin/envpython

Idle

PythonIDEpackagedwiththedownload

Automaticblockindentionandtexthighlighting

SomeEMACSkeyswork

Debugger

SimplePythonexample

Let’sstartwitha(very!)simpleexample

#ThisisaPythonprogramx=37

y=x+5printy

%pythonsimple.py

42

%

Variablesneednotbedeclared,butmustbeassigned

Linebreaksseparatestatements

Commentsbeginwith#

Variableassignments,numbers,andstrings

Variableassignmentwith=

>>>x=y=42

Straightforwardmathexpressionsusing+,--‐,*,/,and()

>>>(50-5*6)/4

5

SupportforEloatingpointandmixedcomputation(convertalloperandstoEloatingpoint)

>>>3*3.75/1.5

7.5

Stringscanbeenclosedineithersingleordoublequotes

“python”or‘python’

Indexingwith[]

Muli--‐linestringsareenclosedintriplequotesorendin\

Concatenationwith+andrepetitionwith*

>>>“str”*3“strstrstr”

Datastructuresandcompounddatatypes

Lists—commaseparatedvaluesenclosedby[]

>>>l=[“hello”,“world”,42]

[“hello”,“world”,42]

>>>nl=[[2,3],[4,5]]

Listcomprehension—listsresultingfromevaluatingexpressions

>>>vec=[2,3,4]

>>>[3*xforxinvec][6,9,12]

Tuples—groupofvaluesseparatedbycommas

>>>

t

=1,5,9

#tuplepacking

(1,

>>>

5,

x,

9)

y,z=t

#tupleunpacking

>>>t=()

>>>t=“singleton”,

Slices—subsetoflist(orstring)

DeEinedbytwoindices

>>>slicedString=aString(start:end)

>>>slicedList=aList(start:end)

Dic.onaries

Unorderedsetsofkey:valuepairs(Associativearrays)

Indexedbyuniquekeys

Keysmustbeimmutabletypes(i.e.,strings,numbers)—canusetuplesonlyiftheycontainimmutableelements

>>>grades={}

>>>grades={“joe”:93,“sally”:82}

>>>grades[“bill”]= 87

>>>grades

{“bill”:87,“sally”:82,“joe”,93}

Constructdictionariesfromalistofkey:valuetuples

>>>dict([(“joe”,93),(“sally”,82),(“bill”,87)])

{“bill”:87,“sally”:82,“joe”,93}

Control?owandfunc.ons

ifstatements(conditionals)

>>>

…

ifx<

0

print

‘Negative’

…

…

elif

x

=0:

print

‘Zero’

…

else:

print

‘Positive’

while--‐--‐continueloopinguntilconditionisfalse

>>>a,b=0,1

>>>whileb<1000

… printb

… a,b=b,a+b

for—iterationoverasequence

>>>

a=

[1,6,15]

>>>

…

for

xina:

printx

range()function—createssequencesusefulforiteration

Indentation—requiredforgroupingstatements

FunctiondeEinitions

>>>deffib(n):#Fibonacciseriesuptonusingabovewhile

Manipula.ngdirectoriesand?les

Accessmodulesusingimportkeyword

OSmodule—accessoperatingsystemdependentfunctionality

os.path—modulewithusefulfunctionsforpathnames(e.g.,normalizeabsolutepaths,Einddirectories,…)

os.getcwd()—returnsstringwhichnamescurrentdirectory

os.chdir("C:/")oros.chdir("C:\\")—changethecurrentworkingdirectorytothespeciEiedpath

ReadingEiles

open(name,mode)—nameistheEilename,modeisread(‘r’),write(‘w’),orappend(‘a(chǎn)’)

ReturnsFileobject

IfnomodeisspeciEieddefaultsto‘r’

>>>

myfile=open(“…”)

>>>

s=myfile.readline()

#stringcontainingthenext

line

>>>ss=myfile.readlines()#listcontainingalllines

TwoapproachestoreadingdatastructuresfromEiles

[Yes,Happy]user=pfile.readline()andthenparseitintoalist

[‘Yes’,‘Happy’]usep=eval(pfile.readline())

Classesandobjectorientedprogramming

ClassdeEinitionsandinstantiation

>>>classC1:...

>>>I1=C1()

Inheritance

>>>classC2(C1):…

Classattributesandmethods

>>>classC2(C1):

… data=value

… defsetname(self,who):

… =who

ClassattributesdeEinedattoplevelaresharedbyallinstances,butchangestothevalueonlyaffecttheinstance

self—selfreferencetocurrentinstance

Constructormethodnamedinit

Methodscanbeaccessedasunbound(atclasslevel)orboundtoaninstance

Overloadoperatorsforclasses

>>>classC1:

… defadd(self,other)

… returnC1(self.data+other)

Formorehelp…

SeetheResourcespageontheclasswebsite

Checkouttheexampleprogramscount.py,match.py,oodemo.pyandthevacuumagentimplementedwithPython

VisitthePythontutorial

Assignment1

ARela.onalAgentinPython

Arela.onalagentprograminPython

Objective: