Class Note for CMPSCI 683 at UMass(1)
Class Note for CMPSCI 683 at UMass(1)
Popular in Course
Popular in Department
This 13 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 14 views.
Reviews for Class Note for CMPSCI 683 at UMass(1)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Victor R Lesser CMPSCI 683 Fall 2004 Many Slides Courtesy of Shlomo Zilberstein Also Slides Courtesy of Milind Tambe USC Tuomas Sandholm CMU and many others Vimltf lm Instructor VIctorR Lesser 4136151322 lair 4135151249 Email lessercsumassedu Of cehnurs Tuesdays 1llll 230pm CSClllli TA Mike O Neill Email mpncsumassedu Of ce hours Wednesdaysldlll Clllll TEA Course Web Page htto mascsumasseduolassesosdl Learning Support Services will contain DVD on the 10th floorof the DuBois Library Vimltf lm Nominally you need an undergraduate course in Al Not necessary to be successful in course Will move quickly over elementary material Vimltf lm Encouragement to ask questions during class After this course you will be able to Without your feedback it is impossible for me to know 39 unders and 39 evaluate Alrelated What you don t know staLeoftheart Al technology clalms There is no reason not to ask questions during class 223252me Al 39 Ofcourse you could also send email or meet in systems I pursue specialized person read the Al Al courses and literature research Encouragement to read course material prior to class v uxxvcssmrmm 5 v minimum a Constructing intelligent machines for a wide range of applications Augmenting human problem solving Formalizing knowledge and mechanizing intelligence Uslng computational models to be made to simulate it quotManama COMP MHVIW Historical Definition of Al The study of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can Making computers as easy to work with as people Dartmouth Workshop Summer of 1956 v uxxvcssmrmm 7 v minimum a Complexity ofWork Place Rappaport 1991 comptva BUSlNESS ENVlRONMENT TWE we iaei zoom is ll ilumallm Syseiiis mam v Ambiguity I dropped the egg on the table and it broke Resource limitations Is there a winning opening move in chess Many applications are NPcom plete Con icting goals and tradeoffs Computer I need more free disk space Uncertainty and missing information 7 Missing lnlormalmn probabilistic actions open and dynamic environments mam ii Cheaper Sensors and Better Sensor Processing vision speech and text Orders of magnitude increase in computing power Commodity processors gtbillion instructions per second Special purpose processors for sensor processing Parallel computing ne and large grain Distributed processing and highspeed communication Nll Large online knowledge bases Tremendous Progress in Providing Formal and Practical Underpinning to the Discipline overthe last 20 years mimicsme W Conventional software can be contrasted with Al systems in a number ofways Language arithmetic vs logical probalistic Data numbers vs symbols Coding procedural code vs declarative sentences 0perations calculations vs reasoning symbolic and decision theorectic Knowledge formulas vs heuristics Program output deterministic vs nondeterministic certaianellde ned vs uncertainlsearch Problem speci cation precise vs impreciselrelative Solution quality exactloptimal vs approximatelsatisficing mimicsme l2 Scheduling and Planning 7 owns DART sSleni used in oeserl slnrnr and Desert sneie aperarmsln plan iagrslrs or people and suppres 7 AlnenmnAlnins remulrng mmrngmcppamer 7 European maceagenopiannrng we screeuirng armaamil asanihiv rrlegralrnn and usrncahnn Speech necegrrrlren 7 PEcAsus woken imguage rrlerixela Alnsimn Aurirnes EAAsv SAERE reservation sslaii Computer Msinn 7 raceremgnrlran pngmnrsrn use hvhmhs wveinnieril etc 7 We ALViNN ssenr nun cMu aulmnnrnusipemuea van mnr Waminglm o c in sanoregn ail ml 52 mm nrriesh averagngES nim davandnigrl andinaii weanercmerlrms 7 Hamwritingiemgrltinn eiadmnisand nimuiadunrg inwedim hagwge irsmwnn amnnralrcaiipcmsrua so gennrelrrcnrneeis vinmsixmlm i3 Diagnostic Systems 7 Mrrrosoil Oincenssslarrl 7 Palhnneerrereragnesrseihrnphneee erseases oulpennrnrs arenslna desgnedn approveehuAMA 7 Whrripooi customer assrslance Lenlei System Configuration 7 DEC SXCONsSleminimsmmhamwaie connguralron Financial Decision Making 7 Fraud oelerlren are tiansaLlinn approval bv rreerl Lard rempanres mortgage compares banks are the U s gmeinment 7 imprerrng pie iLlinn cleariu imnues are slaiirng repurrernerlsier a husrness 7 Helpeesusuppenspslerrslennelhengitansnerleanpruslerrer s guestron mnmsllmlll ri Classification Systems NASA s system lorclassiiying very laint areas in astronomical images into eitherstars or galaxies with very high accuracy by learning lrom human experts Mathematical Theorem ProVing Use inlerence methorls to prove newtheorems Game Playing Computer programs heat world s hest players in chess checkers anrl lraclrgammon MachineTransiation 7 AhaViaa sliansialinnniwebpages 7 Translation oi Caterpillar Truck rnanuais rrrle 20 languages is An agent is anything that can be Viewed as perceiVing its enVironment through sensors and acting upon that enVironment throllgh effectors lunluls percepts ucliunn ileerers mnmsllmlll re Sense and act in dynamiDunuerlain envimnmenls neaeiiie respnnds in enan es in lne eniiienmeni Pieaeiiie aeiineaneaae lime Exemises Dnnlml Wei its an aDlinns Goaoiiented Puipnselul Conlinuously running nmness inreiaeis win mnei agentsDennis Able in iianspen itself 7 Peimnaily Chalamal Emotinnal slate Simple re exive agents Agents that keep track of the world Deliberative agents Explicit representation of domain knowledge Runtime problemsowing and reasoning Modeling the World Selfmodeling and metareasoning tennismu ie Applications information gathering integration Distributed sensors Ecommerce Distributed Vidua organization Vidua humans for training enledainmenl Rapidly growing area How are agents different from the traditional view of system de nition 7 When senseisiaiie input eiieeieis nxea nulpul lne gnal ism pieauee lne eeiieei nulpul and eniiienmeni is siaiieineieiani we lall inie lne Dalegnry nilradilinnal systems 39 BUT 7 Envimnmenl maybe dynamin 7 Sensing maybe an engeing siiualien assessment piecess 7 Eiieeieis may ieeuiie eempiex planning 7 Gnal may be delined Wiin iespem in euiieni stale Dlenvimnmenl As a result 7 Deiiiing lne inputeulpul mapping iiemine gnal is net ebiieusi How to decide what to do tennismu m Given 7 The performance measure BIG resource Bounded Information 7 The percept sequence Gathering 7 The agent s knowledge 7 The set of available actions Takes role of human in support ofdecision process An ideal agent will outperform any other agent in maximizing the performance measure Integration of Planning scheduling text processing and interpretation ster reasoning A Lofty Goal But AI is a Very Long Way Helps pick so ware packages from Being Able to Address this Question for Complicated Applications v uxxicssmrmm 21 v uxxicssmrmm z Rapid growth of WW Growth has outstripped technology Information Retrieval technology a start Ef cient fast general Access to enormous amount of data Input Browsing amp processing documents manually nontrivial 7 Word processing packagefora Mac 7 200 pnce hm 7 Search process should takelO mm ampcost less than 5 v uxxicssmrmm 21 v uxxicssmrmm 24 Active search and discovery 7 WVWVpageS on tne internel Resource Bounded Reasoning 7 Cari only process a limited arnount or information with m resource constraints time arid money Goaldriven and Opportunistic control 7 Focused on specific goals but need to react to emerging information Information extraction 7 Structured and unstmctured information 39 Information fusion BIG recommends Corel WP35 7 incompleteunreliablecontradictoiyiriforrnation v uxxicssmrmm 25 v uxxicssmrmm m Auctioning multiple distinguishable items when bidders have preferences over combinations of items Example procurement in supply chains Example applications 7 momquotanspmmasks Auctioneer wants to buy a set of Items 7 Aiiocauonot bandwidth has to get all Dynauiaiiym computernaworks Sialically eg by Fcc 2TT IEf s quote39quotem Sellers place bids on how cheaply they are e Securniesmarkets Willing to sell bundles of items 7 quuldalon 7 Helnsurmoe markets 7 Fetal ecommerce collectibles tlighlshofelsevenl quotwas 7 Heswrcemask alocalion in operating syaems amohiie agent plallorms v uxxicssmrmm 27 v uxxicssmrmm m Auctioneer wlnner ddermlnatlon problem so omens M i z aim so Mhids pu 3 BM ll 51 lwimslcms a so omens mdplis a prioe SJuSktilnIiltiplehids oonoern the sane set Miteins dl but the highest bid car he dismidat l1y ammonium Problem Ldielthehidsaswinning 3 1 or losing 930soasto naxinl39xeauctioneu s rmiuesiciniia each itan is allocated to at ma one hid What are theideas that you can use to develop a search algorithm for winner determination for 1000 s of bids and 1000 s of items in a reasonable time trame seconds 7 Optimal anytime satisficing wwsmm m oaumsyar mamas 55mm 2 NPoon39plete A Computational Perspective on the Design of Intelligent Agents What is theform ofthe computational structures that are required How does this differ from or relate to other computational problems an 2 There is no universal approach to the design Dealing with the Ubiquity of Uncertainty ofan agent Environment Sensing Action and Knowledge We will be exploring the design space Components and architectures Dealing With Limited Resources Different approaches Computation memory communication For different classes of problems bandWidthr etc For different environments For different criteria for success v uxxicssmrmm 33 v uxxicssmrmm 34 I Text Book Arti cial Intelligence A Modern 0 Factors Approachquot 2nd Edition Stuart Russell and Peter Norvig Prentice Hall 2003 H mew rk 4M Book s website lthttplaimacsberkeleyedugt Vl ll include programming assignments Will Augment with Material Not Covered in Book Midterm exam 30 Additional Readings Available on the course web F39m39 exam 30 site Required readings Suggested readings Late POIICy Usually each assignment has two Mll add to suggested readings to ensure you have WEEKS time tD niSh ASSignmentS Will not be plenty of reference material accepted later without the express permission of the Not necessary to read through suggested readings quot1517mmquot 0quot the t aming aSSiStam v uxxicssmrmm 35 v uxxicssmrmm 1 Introduction Lecture 1 Introduction and Course Information Search Lecture 2 Overview of Issues in Heuristic Search Lecture 3 Heuristic Search Lecture 4 Search Complexity and Applications Lecture 5 Time and Space Variations of A Lecture 6 Abstraction Approximation and RealTime Introduction 1 Problem solving using sophisticated search 7 Reasoning under uncertainty 8 Learning 7 Intelligent Systems 3 Summary 1 Won t be Covered s Adversarlal Game Playing Seamh Elementary Log cal Formally forKnOWledge Lecture 7 Iterative Improvement SearchGSAT Representation Lecture 8 Constraint Satisfaction and Genetic May add in lectures on Planning Knowledge Algorithms Representation v Wiesmm 37 v ammo 1 Reasoning Under Uncertainty Learning Lectures 9 and 10 Blackboard Systems as an Lecture 17 Learning from Observations Architecture for Interpretation Lecture 11 Representing and Reasoning with Uncertain Lecture 18 Leaming Techniques Lecture 19 Neural Networks Information Lectures 12 and 13 Probabilistic Reasoning with Belief Lectures 20 and 21 39 Markov Decision Processes and Networks Reinforcement Learning Lecture 14 Alternative Models of Uncertainty Lecture 22 Data Mining Lecture 15 Decision Theory Lecture 23 Analytical Learning and Planning Lecture 16 Decision Networks May add lecture Hidden Markov Models HMMs May add lemme quot Keme39 Mammes v uxxicssmfmm 2 v uxxicssmfmm m Intelligent Systems Network of Cooperating IntelligentAgents peoplemachines Lecture 24 ResourceBounded Reasoning Constructionist perspective Systems build out of heterogeneous systems highlevel arti cial language for cooperation Lectures 25 and 26 Intelligent Agent Architectuires problem solving for effective cooperation will be as or more sophisticated than the actual domain problem solving LeCture 27 M URIAgent SyStemS and summary reasoning about goals plans intentions and knowledge of other agents y uxxlc mfmm M y uxxlcssmfmm 42 Satisficing ComputationBounded Rationality Dperateina satis cing mode e cornputational irameworkthat allows you to trade offthe quality 7 Do tne best tney can witnin ayailable resource constraints ofthe answer deriyed witn tne arnount oiresources used to 7 Deal witn uncertainty as an integral part of networlltoroblern derive it solying 7 Comm orgamzmna re at mmpg among agem Uncertalntyllnconslstency as integral part of problem solvlng e cornoutational irameworkthat allows you to liye witn lti ratner Highly adaptlvelhlghly reliable Mm ehmmte n e Learl39lll39lg will be an irnoortant part ortneirstructure snort terrnlol39lgrterm eAble to adapt thell pl oblemrsolvlng structure to respond to cnanging taskenvlronmental conditions Intelligent Control 7 cornputational irameworkthat allows you to errectiyely manage your resources to satlsfythe giyen goals AgencySemiAutonomousAgent e cornoutational trarneworllttnat allows agents to interact profound implications Computer Science autonorn ously witn tne world in terrns of sensing perceiving planning effectng and communicating y uxxlc mfmm zu y uxxlcssmfmm 4o Why is search the key problem solving technique in Al Formulating and solving search problems Reading Sections 3137 39SmaH 20 Ddddrar radar duds 30 s 7 Scan and dr three 120 samdrs ad a drrra cdmmdddy Prddassdr assddradad wrm aadn radar cdmmdnrdada 5mm messages my and MB radrd Manners Trrandurada radars 39 m dd dradkrnd meme xnz Mb dumb 3 murmur H mm mnmsumm 8 mm m All mmmgmmnn mm m amm agent smaytnpnlnwtn mmlm mm Elms m rimmed mm mm mg a gas a eemww apaan A s Mumpsawe swam quotmansquot mmnml manage mm laughs mm mm mmgxwungmnml mommnn maul his APDB American Patent DB WSJ WaH StreetJouma AP Assomated Press News vunmsixmlm w mnmsumm 51
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'