Introduction to Computer Engineering - AI PDF

INTRODUCTION TO COMPUTER ENGINEERING 08-ARTIFICIAL INTELLIGENCE Perihan Pehlivanoğlu Dr. Computer Engineering Department Today What is artificial intelligence? Past: how did the ideas in AI come about? Present: what is the state of t...

INTRODUCTION TO COMPUTER ENGINEERING 08-ARTIFICIAL INTELLIGENCE Perihan Pehlivanoğlu Dr. Computer Engineering Department Today What is artificial intelligence? Past: how did the ideas in AI come about? Present: what is the state of the art? Future: will robots take over the world? What is AI? What is AI? What is AI? The science of making machines that: Think like people Think rationally Act like people Act rationally What can people do that computers can’t do? Telling Humans and Computers Apart Automatically A CAPTCHA is a program that protects websites against bots by generating and grading tests that humans can pass but current computer programs cannot. For example, humans can read distorted text as the one shown below, but current computer programs can't: The term CAPTCHA (for Completely Automated Public Turing Test To Tell Computers and Humans Apart) was coined in 2000 by Luis von Ahn, Manuel Blum, Nicholas Hopper and John Langford of Carnegie Mellon University. Thinking Rationally Rational thinking refers to logical or reasoning being involved in the thought process. It refers to providing reasons or rational behind thoughts or ideas. Aristotle’s Syllogism: “Socrates is a man; all men are mortal; therefore, Socrates is mortal” 8 Acting Rationally Rational behavior: doing the “right thing” – The right thing: that which is expected to maximize goal achievement, given the available information – Doesn't necessarily involve thinking, e.g., blinking – Thinking can be in the service of rational action – Entirely dependent on goals! – Irrational ≠ insane, irrationality is sub-optimal action – Rational ≠ successful Our focus here: rational agents – Systems which make the best possible decisions given goals, evidence, and constraints – In the real world, usually lots of uncertainty … and lots of complexity – Usually, we’re just approximating rationality Rational Decisions We’ll use the term rational in a very specific, technical way:  Rational: maximally achieving pre-defined goals given available information  Rationality only concerns what decisions are made (not the thought process behind them)  Goals are expressed in terms of the utility of outcomes  Being rational means maximizing your expected utility A better title for this course would be: Computational Rationality Maximize Your Expected Utility A (Short) History of AI "I think, therefore I am" Demo: HISTORY – MT1950.wmv What can AI Do? Quiz: Which of the following can be done at present? Play a decent game of table tennis? Play a decent game of Jeopardy(riziko)? Drive safely along a curving mountain road? Drive safely along Bagdat Street? Buy a week's worth of groceries on the web? Buy a week's worth of groceries at Berkeley Bowl? Discover and prove a new mathematical theorem? Converse successfully with another person for an hour? Perform a surgical operation? Put away the dishes and fold the laundry? Translate spoken Chinese into spoken English in real time? Write an intentionally funny story? Natural Language Speech technologies (e.g. Siri) – Automatic speech recognition (ASR) – Text-to-speech synthesis (TTS) – Dialog systems Language processing technologies – Question answering – Machine translation – Web search – Text classification, spam filtering, etc… Vision (Perception)  Object and face recognition  Scene segmentation  Image classification  Object tracking and behavior recognition Images from Erik Sudderth (left), scienceagogo (right) Robotics Robotics – Part mech. eng. – Part AI – Reality much harder than simulations! Technologies – Vehicles – Rescue – Soccer! – Lots of automation… In this class: – We ignore mechanical aspects – Methods for planning – Methods for control Images from UC Berkeley, Boston Dynamics, RoboCup, Google Game Playing Classic Moment: May, '97: Deep Blue vs. Kasparov – First match won against world champion – “Intelligent, creative” play – Special-purpose hardware, 200 million board positions per second – Current PC programs far ahead of humans Open question: – How does human cognition deal with the vast search space of chess? – Or: how can humans compete with computers at all?? 1996: Kasparov Beats Deep Blue “I could feel --- I could smell --- a new kind of intelligence across the table.” 1997: Deep Blue Beats Kasparov “Deep Blue hasn't proven anything.” Huge game-playing advances recently, e.g. in Go Text from Bart Selman, image from IBM’s Deep Blue pages Game «Go» https://www.youtube.com/watch?v=oZTdT8MQexk 18 Deepmind (Google-Deeplearning) 19 Embedded applications – AI lies behind many other useful systems: Scheduling, e.g. airline routing, military Route planning, e.g. Google maps Medical diagnosis, e.g., EKGs Automated surveillance Web search engines Spam classifiers Automated help desks Fraud detection Product recommendations … Lots more!  Smallest TSP (Traveling Salesman Problem) https://www.youtube.com/watc h?v=1pmBjIZ20pE 21 USA Cities (532) 22 Future We are doing AI… – To create intelligent systems The more intelligent, the better – To gain a better understanding of human intelligence – To magnify those benefits that flow from it Future, contd. Progress is accelerating, partly due to an industry arms race Once performance reaches a minimum level, every 1% improvement is worth billions – Speech – Text understanding – Object recognition – Automated vehicles – Domestic robots What if we do succeed? “The first ultraintelligent machine is the last invention that man need ever make.” I. J. Good, 1965 Might help us avoid war and ecological catastrophes, achieve immortality and expand throughout the universe Success would be the biggest event in human history … – and perhaps the last Reasons not to worry “AI will never reach human levels of intelligence” “OK, maybe it will, but I’ll be dead before it does” “Machines will never be conscious” – Consciousness isn’t the problem, it’s competence! “We design these things, right?” – Yes, and the genie grants three wishes – For almost any goal, a superintelligent system will… Acquire as many resources as possible and improve its own algorithms Protect itself against any attempt to switch it off or change the goal So, if that matters….. Along what paths will AI evolve? What is the (plausibly reachable) best case? Worst case? Can we affect the future of AI? – Can we reap the benefits of superintelligent machines and avoid the risks? – “The essential task of our age.” Nick Bostrom, Professor of Philosophy, Oxford University. Artificial Intelligence Problem Solving Uninformed Search 28 Today Agents that Plan Ahead Search Problems Uninformed Search Methods – Depth-First Search – Breadth-First Search – Uniform-Cost Search Agents that plan ahead Planning agents: – Decisions based on predicted consequences of actions – Must have a transition model: how the world evolves in response to actions – Must formulate a goal Spectrum of deliberativeness: – Generate complete, optimal plan offline, then execute – Generate a simple, greedy plan, start executing, replan when something goes wrong Search Problems Search Problems A search problem consists of: – A state space – For each state, a set of {N, E} 1 N Actions(s) of allowable actions E 1 – A transition model Result(s,a) – A step cost function c(s,a,s’) – A start state and a goal test A solution is a sequence of actions (a plan) which transforms the start state to a goal state Search Problems Are Models  Example: Travelling in Romania State space: Oradea – Cities 71 Neamt Actions: Zerind 87 75 151 – Go to adjacent city Iasi Arad 140 92 Transition model Sibiu 99 Fagaras – Result(Go(B),A) = B 118 Vaslui 80 Rimnicu Vilcea Step cost Timisoara 142 – Distance along road link 111 Pitesti 211 Lugoj 97 Start state: 70 98 Mehadia 146 101 85 Urziceni Hirsova – Arad Drobeta 75 120 138 Bucharest 86 Goal test: 90 Eforie – Is state == Bucharest? Craiova Giurgiu Solution? Search Gone Wrong? Depth-First Search Strategy: expand a deepest node first a G b c Implementation: d e f Frontier is a LIFO stack S h p q r S d e p b c e h r q a a h r p q f p q f q c G q c G a a https://www.youtube.com/watch?v=Urx87-NMm6c Breadth-First Search Strategy: expand a a G b c shallowest node d e first f S h Implementation: p q r Frontier is a FIFO queue S d e p Search Tiers b c e h r q a a h r p q f p q f q c G q c G a https://www.youtube.com/watch?v=OwB_ArFOGcs a Uniform Cost Search 2 a G Strategy: expand a b c 1 8 2 cheapest node first: 2 e 3 d f Frontier is a priority S 9 h 8 2 1 queue (priority: 1 p q r 15 cumulative cost) S 0 d 3 e 9 p 1 b 4 c e 5 h 17 r 11 q 16 11 Cost a 6 a h 13 r 7 p q f contours p q f 8 q c G q 11 c G 10 a a https://www.youtube.com/watch?v=8ofimg8cnRE Path Planning Goal Start The Links https://www.youtube.com/watch?v=4o0FZalxIYw https://www.youtube.com/watch?v=fn3KWM1kuAw https://www.youtube.com/watch?v=Ub1Z02dVKXM https://www.youtube.com/watch?v=U8cxZZ55slA https://www.youtube.com/watch?v=tdUwWOZPn1M 0-40