15-381: Artificial IntelligenceIntroduction and Overviewhttp://www.cs.cmu.edu/afs/andrew/course/15/381-f08/www/Course data• All up-to-date info is on the course web page:- http://www.cs.cmu.edu/afs/andrew/course/15/381-f08/www/• Instructors:- Ziv Bar-Joseph- Illah Nourbakhsh• TAs:- Hetu Kamichetty- Henry Lin• See web page for contact info, office hours, etc.Class organizationTue. 8/26IntroThu. 8/28SearchTue. 9/02SearchThu. 9/04SearchTue. 9/09Intro to ProbabilityThu. 9/11Intro to Probability and Bayes networksTue. 9/16Bayesian networksThu. 9/18More Bayesian and Hidden Markov ModelsTue. 9/23Hidden Markov ModelsThu. 9/25Markov Decision ProcessTue. 9/30Reinforcement LearningThu. 10/02ClusteringTue. 10/07Robotics and VisionThu. 10/09Evolutionary AlgoTue. 10/14Reinforcement LearningThu. 10/16Reinforcement LearningTue. 10/21Advanced Search (not in midterm)Thu. 10/23MidtermTue. 10/28Advanced SearchThu. 10/30Learning Decision TreesTue. 11/04Learning Neural NetworksThu. 11/06Learning Support Vector MachinesTue. 11/11LearningThu. 11/13Applications and RobotsTue. 11/18Applications and RobotsThu. 11/20Applications and RobotsTue. 11/25Game TheoryTue. 12/02Computational Molecular BiologyThu. 12/04Computational Molecular BiologySearchAdvancedSearchProbabilisticrepresentationand modelingLearningApplicationsof AIGrading• 5 Problem sets - 45%• Midterm - 20%• Final - 30%• Class participation - 5%What is AI?Easy part: AHard part: I- Anything we don’t know how to makea computer do yet- Corollary: once we do it, it isn’t AIanymore :-)IntelligenceWhat is “intelligence” ?Can we emulate intelligent behavior in machines ?How far can we take it ?Intelligent systemsThree key steps of a knowledge-based agent(Craik, 1943):1.the stimulus must be translated into aninternal representation2. the representation is manipulated bycognitive processes to derive new internalrepresentations3.these in turn are translated into actionperception cognition action““agentagent””The Turing Testtext cognition text??Representationperception cognition actionAll AI problems require some form of representation.• chess board• maze• text• object• room• sound• visual sceneA major part of AI is representing the problem space soas to allow efficient storage and search for the bestsolution(s).Sometimes the representation is the output.e.g., discovering “patterns”.Outputperception cognition actionThe output action can also be complex.• next move• text• label• actuator• movementFrom a simple chess move to a motorsequence to grasp an object.Thinkingperception cognition actionWhat do you do once you have a representation? This requires a goal.• find best move• shortest path• semantic parsing• recognition• object localization• speech recognition• path navigation• chess board• maze• text• object• room• sound• visual sceneRational behavior:choose actions thatmaximize goalachievement givenavailable informationFrom representation to action• Strategy• Reasoning - with full knowledge - under uncertainty• LearningStrategyperception cognition actionWhat if your world includes another agent?• strategic game play• auctions• modeling other agents• uncertainty: chance andfuture actionsRational behavior:How do we choosemoves/actions to win?Or guarantee fairestoutcome?Team PlayReasoningperception cognition actionReasoning can be thought of as constructing an accurate world model.• logical consequences• inferences• “it rained” or “sprinkler”?• facts• observations• “wet ground”Rational inference:What can be logicallyinferred given availableinformation?Reasoning with uncertain informationperception cognition actionMost facts are not concrete and are not known with certainty.• inferences• What disease?• What causes?• facts• observations• “fever”• “aches”Probabilistic inference:How do we give theproper weight to eachobservation?What is ideal?Learningperception cognition actionWhat if your world is changing? How do we maintain an accurate model?• chess board• maze• text• object• room• sound• visual sceneLearning:adapt internalrepresentation so that itis as accurate as possible.Can also adapt ourmodels of other agents.Where can this go?• Robotics• Internet search• Scheduling• Planing• Logistics• Biology• Games• Auction design• Diagnosis• General reasoningIn the first part of class, wewill focus on the AIfundamentals.We will discuss (some)application in the second part.Web searchWeb search, cont’dRecommender systemsGrand and Urban Challenges road raceGetting from A to BRobocupMore examples• Valerie and Tank, the Roboceptionists• Social skills: attending a party, giving directions, …Common threads• Search and optimization• Set the problem up well (so that we can apply a standard algorithm)• Managing uncertainty• The more different types of uncertainty, the harder the problem (and the slower the solution)The first two parts of this class (occupying the vast majority oflectures) would be dedicated to these two threads. The last partwould present some application areas of AI.Example problem: Robot navigationConsider a robot whose goal is to navigate a certain floor on Wean Hall.• Needs to know the layout of the floor - Representation and data structures for easy search (trees, graphs)Example problem: Robot navigationConsider a robot whose goal is to navigate a certain floor on Wean Hall.• Needs to know the layout of the floor - Representation and data structures for easy search (trees, graphs)• Determine how to get from point A to B - Planning and search (BFS, DFS, A*, randomized search)Example problem: Robot navigationConsider a robot whose goal is to navigate a certain floor on Wean Hall.• Needs to know the layout of the floor - Representation and data structures for easy search (trees, graphs)• Determine how to get from point A to B - Planning and search (BFS, DFS, A*, randomized search)• Needs to search quickly to address requests online - Optimization (linear programming)Example problem: Robot navigationConsider a robot whose goal is to navigate a certain floor on Wean Hall.• Needs to know the layout of the floor - Representation and data structures for easy search (trees, graphs)• Determine how to get from point A to B - Planning and search (BFS, DFS, A*, randomized search)•
View Full Document
Unlocking...