Published on January 4, 2008
Artificial Intelligence: introduction: Artificial Intelligence: introduction Stefano De Luca Slides mainly by Tom Lenaerts Practical stuff: Practical stuff Stefano De Luca Mail: [email protected] [email protected] Textbook: S. Russell and P. Norvig Artificial Intelligence: A Modern Approach Prentice Hall, 2003, Second Edition In Italian: Intelligenza artificiale. Un approccio moderno, Utet Exam: written at end and oral If you ask for: intermediate written exam Course overview: Course overview What is AI. Intelligent agents. Problem solving. Knowledge and reasoning. Logic and logic programming. Prolog. Rule (expert) systems. Jess. Planning Uncertain knowledge and reasoning. Neural Network Genetic Algorithms Industrial case histories Outline : Outline What is AI A brief history The State of the art (see book) What is Artificial Intelligence : What is Artificial Intelligence Creative extension of philosophy: Understand and BUILD intelligent entities Origin after WWII Highly interdisciplinary Currently consist of huge variety of subfields This course will discuss some of them Old AI…: Old AI… Now: Smart Music System: Now: Smart Music System The Bose uMusic system uses artificial intelligence to learn the listening habits and preferences of its users. Load your CDs into the digital music delivery system, it can hold thousands of songs, and it will learn your listening preferences and prioritize your music collection. Pandora.com: Pandora.com Control systems: Control systems What is Artificial Intelligence: What is Artificial Intelligence Different definitions due to different criteria Two dimensions: Thought processes/reasoning vs. behavior/action Success according to human standards vs. success according to an ideal concept of intelligence: rationality. Systems that act like humans: Systems that act like humans When does a system behave intelligently? Turing (1950) Computing Machinery and Intelligence Operational test of intelligence: imitation game Test still relevant now, yet might be the wrong question. Requires the collaboration of major components of AI: knowledge, reasoning, language understanding, learning, … Systems that act like humans: Systems that act like humans Andrew Hodges. Alan Turing, the enigma (Storia di un Enigma, Bollati Boringhieri) Problem with Turing test: not reproducible, constructive or amenable to mathematical analysis. Systems that think like humans: Systems that think like humans How do humans think? Requires scientific theories of internal brain activities (cognitive model): Level of abstraction? (knowledge or circuitry?) Validation? Predicting and testing human behavior Identification from neurological data Cognitive Science vs. Cognitive neuroscience. Both approaches are now distinct from AI Share that the available theories do not explain anything resembling human intelligence. Three fields share a principal direction. Systems that think like humans: Systems that think like humans Some references; Daniel C. Dennet. Consciousness explained. M. Posner (edt.) Foundations of cognitive science Francisco J. Varela et al. The Embodied Mind J.-P. Dupuy. The mechanization of the mind Systems that think rationally: Systems that think rationally Capturing the laws of thought Aristotle: What are ‘correct’ argument and thought processes? Correctness depends on irrefutability of reasoning processes. This study initiated the field of logic. The logicist tradition in AI hopes to create intelligent systems using logic programming. Problems: Not all intelligence is mediated by logic behavior What is the purpose of thinking? What thought should one have? Systems that think rationally: Systems that think rationally A reference; Ivan Bratko, Prolog programming for artificial intelligence. Systems that act rationally: Systems that act rationally Rational behavior: “doing the right thing” The “Right thing” is that what is expected to maximize goal achievement given the available information. Can include thinking, yet in service of rational action. Action without thinking: e.g. reflexes. Systems that act rationally: Systems that act rationally Two advantages over previous approaches: More general than law of thoughts approach More amenable to scientific development. Yet rationality is only applicable in ideal environments. Moreover rationality is not a very good model of reality. Systems that act rationally: Systems that act rationally Some references Rational agents : Rational agents An agent is an entity that perceives and acts This course is about designing rational agents An agent is a function from percept histories to actions: For any given class of environments and task we seek the agent (or class of agents) with the best performance. Problem: computational limitations make perfect rationality unachievable. Foundations of AI : Foundations of AI Different fields have contributed to AI in the form of ideas,viewpoints and techniques. Philosophy: Logic, reasoning, mind as a physical system, foundations of learning, language and rationality. Mathematics: Formal representation and proof algorithms, computation, (un)decidability, (in)tractability, probability. Psychology: adaptation, phenomena of perception and motor control. Economics: formal theory of rational decisions, game theory. Linguistics: knowledge represetatio, grammar. Neuroscience: physical substrate for mental activities. Control theory: homeostatic systems, stability, optimal agent design. A brief history: A brief history What happened after WWII? 1943: Warren Mc Culloch and Walter Pitts: a model of artificial boolean neurons to perform computations. First steps toward connectionist computation and learning (Hebbian learning). Marvin Minsky and Dann Edmonds (1951) constructed the first neural network computer 1950: Alan Turing’s “Computing Machinery and Intelligence” First complete vision of AI. Idea of Genetic Algorithms A brief history (2): A brief history (2) The birth of (the term) AI (1956) Darmouth Workshop bringing together top minds on automata theory, neural nets and the study of intelligence. Allen Newell and Herbert Simon: The logic theorist (first nonnumerical thinking program used for theorem proving) For the next 20 years the field was dominated by these participants. Great expectations (1952-1969) Newell and Simon introduced the General Problem Solver. Imitation of human problem-solving Arthur Samuel (1952-)investigated game playing (checkers ) with great success. John McCarthy(1958-) : Inventor of Lisp (second-oldest high-level language) Logic oriented, Advice Taker (separation between knowledge and reasoning) A brief history (3): A brief history (3) The birth of AI (1956) Great expectations continued .. Marvin Minsky (1958 -) Introduction of microworlds that appear to require intelligence to solve: e.g. blocks-world. Anti-logic orientation, society of the mind. Collapse in AI research (1966 - 1973) Progress was slower than expected. Unrealistic predictions. Some systems lacked scalability. Combinatorial explosion in search. Fundamental limitations on techniques and representations. Minsky and Papert (1969) Perceptrons. A brief history (4): A brief history (4) AI revival through knowledge-based systems (1969-1970) General-purpose vs. domain specific E.g. the DENDRAL project (Buchanan et al. 1969) First successful knowledge intensive system. Expert systems MYCIN to diagnose blood infections (Feigenbaum et al.) Introduction of uncertainty in reasoning. Increase in knowledge representation research. Logic, frames, semantic nets, … A brief history (5): A brief history (5) AI becomes an industry (1980 - present) R1 at DEC (McDermott, 1982) Fifth generation project in Japan (1981) American response … Puts an end to the AI winter. Connectionist revival (1986 - present) Parallel distributed processing (RumelHart and McClelland, 1986); back-propagation A brief history (6): A brief history (6) AI becomes a science (1987 - present) Neats vs. scruffies. In speech recognition: hidden markov models In neural networks In uncertain reasoning and expert systems: Bayesian network formalism … The emergence of intelligent agents (1995 - present) The whole agent problem: “How does an agent act/behave embedded in real environments with continuous sensory inputs” The Hype Cycle of Emerging Technologies (Gartner 2005): The Hype Cycle of Emerging Technologies (Gartner 2005) Major research areas (Applications): Major research areas (Applications) Natural Language Understanding Image, Speech and pattern recognition Uncertainty Modeling Expert systems Virtual Reality ….. Symbolic Programming: Program as Representation of world Symbol as basic element of representation atom, property, relationship Symbolic Expression as method of combination LISP for Symbolic programming PROLOG for logic programming Object-Oriented Concept Symbolic Programming Knowledge Representation: Knowledge Representation What kind of Knowledge needed for Problem solving ? Structure of knowledge ? declarative vs procedural Representation techniques ? explicit vs (implicit + inference) logic, frame, object-oriented, semantic net, script Knowledge acquisition and update Search Theory: Search Theory An Optimization method Analyze alternative cases and select one Cope with Exponential complexity, NP classes Try likely one first (Heuristic Search) Utilize local information (Hill Climbing Method) Optimal solution vs good solution Genetic Algorithm, Simulated Annealing Stochastic search Automated Reasoning: Automated Reasoning Qualitative Reasoning Utilization of qualitative knowledge such as Non-monotonic Reasoning Ostrich flys ? Plausible Reasoning Information fusion under uncertainty Case-based Reasoning Utilization of Experience Machine Learning: Performance improvement by experience How much of knowledge required to start learning ? Method of acquiring new knowledge and merging it to existing knowledge-base Role of teacher Role of examples and experience Parameter Adjustment Inductive learning Computational Learning Theory Quality of generalization capability in terms of Training data Used in Practice such as Data Mining Machine Learning Data Mining : Data Mining Data Information / knowledge Decision Making Knowledge extraction for decision making Neural Network: Computational model of Neurons Power comes from Connection of simple processing element - connectionism S X1 X2 Xn . . . w1 w2 wn F(X1, X2, …, Xn) Neural Network Neural Network: learning = link weigh adjustment Error-back-propagation : supervised learning Any Functional Mapping is learnable Strong at Sensory Data Processing Symbolic Grounding Old Horse on the race again Massive parallelism, graceful degradation Neural Network Neural Network Classifier: Neural Network Classifier Input layer Hidden layer Output layer Genetic Algorithms: Genetic Algorithms Computational model of life evolution Stochastic optimization technique Initial chromosome creation New generations are made (cross over, mutation) survival of the fittest Base of artificial life research study evolution of life, by simulation AI Success Story (Planning): AI Success Story (Planning) MARVEL (Schwuttke, 1992) Real-time Space shuttle Mission planning Berth assignment (KAL, 1997) Unmanned Vehicle Ground and air Pathfinder Rover, 1996 Asimo – a walking robot Autonomous Land Vehicle(DARPA’s GrandChallenge contest): Autonomous Land Vehicle (DARPA’s GrandChallenge contest) AI Success Story : Medical expert systems: AI Success Story : Medical expert systems Antibiotics & Infectious Diseases Cancer Chest pain Dentistry Dermatology Drugs & Toxicology Emergency Epilepsy Family Practice Genetics Geriatrics Programs listed by Special Field Gynecology Imaging Analysis Internal Medicine Intensive Care Laboratory Systems Orthopedics Pediatrics Pulmonology & Ventilation Surgery & Post-Operative Care Trauma Management Pattern Recognition Applications: Pattern Recognition Applications Handwriting and document recognition forms, postal mail, historic documents PDA pen recognition Signature, biometrics (finger, face, iris, etc.) Gesture, facial expression As a Human computer intertraction EEG, EKG, X-ray Trafic monitoring, Remote Sensing Smart Weapon – guided missile, target homing Handwriting Understanding: Handwriting Understanding Decision Support Systems (DSS): Decision Support Systems (DSS) Intelligent Transportation Systems: Intelligent Transportation Systems Future of AI: Future of AI Making AI Easy to use Easy-to-use Expert system building tools Web auto translation system Recognition-based Interface Packages Integrated Paradigm Symbolic Processing + Neural Processing AI in everywhere, AI in nowhere AI embedded in all products Ubiquitous Computing, Pervasive Computing Other courses at the UniRoma2: Other courses at the UniRoma2 AI does not end here … Sistemi di agenti (Specialistica) Cooperazione di Agenti informatici (Specialistica) … Some references: Some references Understanding Intelligence by Rolf Pfeifer and Christian Scheier. Artificial Intelligence: Structures and Strategies for Complex Problem-solving by George Luger. Computation and Intelligence: Collective readings edited by George Luger. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig.