IntroductionV1_L1.pptx

Approaches to AI Observation, Hypothesis of behaviour Thinking Humanly - Newell’s GPS, Trace of human reasoning in humans in solving problems, Cognitive Science Acting Humanly - Turing test need of NLP, Knowledge Representation, Automated reasoning, Machine...

Approaches to AI Observation, Hypothesis of behaviour Thinking Humanly - Newell’s GPS, Trace of human reasoning in humans in solving problems, Cognitive Science Acting Humanly - Turing test need of NLP, Knowledge Representation, Automated reasoning, Machine learning, Computer vision, Robotics Mathematics, Engineering Thinking Rationally - Laws of Thought approach, irrefutable reasoning/ Logicist approach, issue with informal/uncertain info representation, Computational Complexity Acting Rationally - Agents – Perceive, act/ operate autonomously, adapt to change, create and pursue goals, Rational agents to achieve best outcome Laws of Thought + Skills needed for Turing Test What is AI Automation of activities that we The study of memory faculties through associate with human thinking, the use of computational models decision making, problem solving, …. (Charniak + Mcdermott, 1985) (Bellman 1978) Study of how to make computers do The branch of computer science that is things at which , at the moment, concerned with automation of people are better (Rich + Knight 1901) intelligent behaviour ( Luger + Stubblefield, 1903) View of AI Empirical Computational Thought process Thinking Humanly Thinking Rationally and reasoning Machines with minds Perceive, reason, act (Understand (through introspection, computation model psychological experiments – brain (Laws of Thought - codify right thinking, imaging), form theory, program) irrefutable reasoning processes) Input –output to match human Correct conclusions, given correct behaviour - GPS traces reasoning premises through patterns of argument steps structures Field of Logic Behaviour Acting Humanly Acting Rationally Performing intelligent Computational intelligence functions Success in terms of fidelity Success against an ideal to human performance performance Approaches to AI – Acting Humanly Turing (1950) “ Computing Machinery and intelligence Can machines think? Can machines behave intelligently? Operational test for intelligent behaviour – imitation game Predicted that by 2000, a machine might have a 30% chance of fooling a lay person for 5 minutes Anticipated all major arguments against AI in following 50 years Suggested major components of AI: Knowledge, Reasoning, Language, Understanding, Learning Problem: Turing test is not reproducible, constructive or amenable to mathematical analysis Turing Test Turing Test: A computer passes the test if a human interrogator , after posing some written questions, can not tell whether the written responses came from a person or from a computer Programming a computer to pass a rigorously applied test needs NLP – Natural Language Processing – to enable it to communicate Knowledge Representation - to store what it knows or hears Automated Reasoning - to use stored information to answer questions and to draw new conclusions Machine Learning - to adapt to new circumstances and detect and extrapolate patterns Total Turing Test: includes test for subject’s perceptual abilities and requires Computer Vision Robotics Approaches to AI – Thinking Humanly Cognitive Science 1960s – Information processing psychology replaced prevailing behaviourism Requires scientific theories of internal activities of brain abstraction of knowledge? Circuits? how to validate - predicting and testing behaviour of human subjects? (Cognitive Science) direct observation of neurological data? ( Cognitive neuro science) Approaches to AI – Thinking Rationally Normative/prescriptive rather than descriptive Aristotle: what are correct arguments/ thought processes? - various forms of logic notation and rules of derivation for thoughts - through mathematics and philosophy to modern AI Problems: Not all intelligent behaviour is mediated by logical deliberation Purpose of thinking? what thoughts one should have? Approaches to AI- Acting Rationally Rational Behaviour – Doing the right thing Right thing? That which is expected to maximize goal achievement, given the available information Does not necessarily involve thinking (ex: blinking reflex), thinking is expected to be in the service of rational action Aristotle Every act and every inquiry, and similarly every action and pursuit, is thought to aim at some good. Approaches to AI – Rational Agents How we Think, Perceive, Understand, Predict, Manipulate a world far larger and complicated? AI: understand and build intelligent entities A system is rational if it does the right thing, given what it knows An agent is an entity that perceives and acts f : P*  A An agent is a function from percept histories to actions For any given class of environments and tasks, agent ( class of agents) with best performance are sought Computational limitations make perfect rationality unachievable - design best program for given machine resources AI – Other disciplines Philosophy Logic, methods of reasoning, mind as physical system, foundations of learning, language, rationality Mathematics Formal representation and proof, algorithms, computation Un-decidability, intractability, probability Psychology Adaption, phenomena of perception and motor control Experimental techniques Linguistics Knowledge representation, grammar Neuroscience Physical substrate ( hardware) fro mental activity Control Theory Stability, homeostatic systems ( that main equilibrium) Optimal agent designs Operations Research Planning, sequence of actions, AI – history 1943: Mcculloch & Pitts : neurons Model 1950: Turing “ computing machinery and intelligence” Early AI programs, Samuel’s checkers program, Newell and Simon’s logic theorist, Gelmeter’s Geometry Engine, 1956: Dartmouth meeting “Artificial Intelligence adopted” 1965: Robinson’s complete algorithm for logical reasoning 1966-74: discovery of computational complexity, NN winter 1969-79: Knowledge based systems development 1980-88: Expert systems boom 1988-93: AI Winter 1985-95: NN return, resurgence of Probabilistic, decision theoretic methods 2020: deep learning Foundations of AI / Disciplines Contributing to AI Philosophy: Can formal rules be used to draw conclusions?/ How does the mind arise from a Physical Brain?/ Where does knowledge come from? Useful reasoning can be carried out by artefacts/machines Reasoning is like numerical computation, Distinction between Mind and Matter – Rationalism ( power of reasoning in understanding world), Dualism (a part of mind exempt from laws), Materialism ( Mind operates according to Laws) Empiricism ( world understanding is through senses), Principle of Induction ( general rules are acquired by exposure to repeated associations between elements) Logical Positivism all knowledge can be characterised by logical theories connected to observation sentences corresponding to sensory inputs Confirmation Theory: acquisition of knowledge from Experience – Theory of Mind as a Computational Process Aristotle: Actions are justified by a logical connection between goals and Knowledge of the actions outcome, deliberation about means, but not ends. We assume the end and consider how and by what means it is achieved. If we came upon impossibility, we give up the search. If appears feasible, we try to do/act What to do when several actions will achieve the goal or no action will achieve it completely? Utilitarianism: rational decision making Disciplines Contributing to AI Mathematics What are the formal rules to draw valid conclusions?/ what can be computed?/ how do we reason with uncertain information? Fundamental Ideas -> Mathematical Formalism -> Formal Science Logical Representation Formal Logic Propositional/Boolean Logic First Order Logic Theory of reference – how to relate objects in logic to objects in real world Algorithm algorithms for logical deduction Incompleteness theorem- limits of deduction - no proof for some TRUE statements Computable Functions, decidability, Tractability ( Computational Complexity) - NP complete, NP Hard problems Probability Possible outcomes, uncertain measurements, incomplete theories Uncertain reasoning – updating probabilities in the light of new evidences (Bayes Rule) Disciplines Contributing to AI Economics How should we make decisions so as to maximize payoff?/ how should we do this when others may not go along?/ how should we do this when the payoff is far in the future? “ Economies can be thought of as consisting of individual agents maximizing their own economic well being. Economics is about how people make choices that lead to preferred outcomes” Utility – Preferred outcomes Theory of games and economic behaviour Decision theory – Probability + Utility Framework for decisions made under uncertainty Game theory No unambiguous prescription fro selecting actions ( could be random) Operations Research How to make rational decisions when payoffs from actions are not immediate, but result from several actions taken in sequence Markov decision processes: class of sequential decision problems Rational Agents – Economics + OR Satisficing: “ Models based on satisficing – making decisions that are good enough rather than laboriously calculating an optimal decision – gave a better description of actual human behaviour” Disciplines Contributing to AI Neuroscience How do brains process Information? Brain is the seat of consciousness. Brains consist of neurons, massively parallel neuronal structures Cognitive processes - Brain Causes Minds- “a collection of simple cells can lead to thought, action and consciousness” No theory still on how an individual memory is stored. Psychology How do animals think and act? Experimental/behavioural observations methodology Scientific/ introspective/ though processes Cognitive Psychology Brain as information processing device Knowledge based agent: The stimulus must be translated into an internal representation -> the representation is manipulated by cognitive processes to derive new internal representations -> these are in turn retranslated into actions Perception and communication Cognitive Science with Computer modelling “ A cognitive theory should be like a computer program: it should describe a detailed information-processing mechanism whereby some cognitive function can be implemented Disciplines Contributing to AI Computer Engineering How can we build an efficient computer? For AI to succeed we need intelligence and artefact ( computer) Calculator - Electro mechanical, Programmable Computer, HLL ABC/ENIAC – electronic computers Design of Difference ( for maths) and Analytical Engine ( addressable memory, programmable) Main frames Minicomputers Microprocessors Desktops Single core systems Internet Multicore systems Graphic processor units Mobiles Smart sensors Software: operating systems, HLLs, multi tasking, databases, virtualization, frameworks, distributed processing, internet protocols, … Disciplines Contributing to AI Control Theory and cybernetics How can artefacts operate under their own control? Self regulating feedback control systems Control theory – study of biological and mechanical control systems “ purposive behaviour arises from a regulatory mechanism trying to minimize error – difference between current state and goal state” Computational Models of Cognition – Cybernetics Stochastic optimal Control – design of systems that maximize an objective function over time Disciplines Contributing to AI Linguistics Hoe does Language relate to thought? Verbal behaviour – behaviourist approach to language learning Syntactic structures Computational Linguistics/ NLP Understanding language requires understanding of subject matter and context, not just understanding of the structure of sentences Knowledge representation is tied to Languages History of AI Gestation of AI Models of neurons, networks of neurons, learning rules, Neural net computer Turing test, idea of machine learning, genetic algorithms Study of automata theory, neural nets, study of intelligence – for 2 months for Artificial Intelligence project: “ every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it” The logic Theorist: reasoning program Early Enthusiasm, Great Expectations General Problem Solver (GPS) designed, Geometry theorem prover, programs for checkers LISP AI programming Language Timesharing for scarce computer resources Advice taker – designed to use knowledge to search for solutions to problems Anti-logic outlook Resolution theorem ( theorem proving algorithm for first order logic general purpose methods of logical reasoning) Question answer and planning systems development based on logic and resolution Robotics: logic + Physical activity Micro worlds: problems that appeared to require intelligence to solve, calculus integration problems, ANALOGY program to solve geometric analogy – blocks world – set of solid blocks placed on a table top. Task: rearrange in acertain way using a robot hand that can pick up one block at a time. History of AI A Dose of reality Early programs used syntactic manipulations without knowing subject matter/context Intractability of many AI problems: programs solved problems by trying out different combinations of steps until the solutions is found – computational complexity, scaling up issues, combinatorial explosion “ A program can find a solution in principle does not mean that the program contains any of the mechanisms needed to find it in practice” Limitations of basic structures being used to generate intelligent behaviour. Perceptron limitation ( later multi layer neural networks and back propagation caused resurgence) First decade of AI: problem solving: general purpose search mechanism trying to string together elementary reasoning steps to find complete solution – weak methods Knowledge based systems/ Expert Systems Use domain specific knowledge for larger reasoning steps, handle easily typically occurring cases “ to solve a hard problem, you have to know the answer already” DENDRAL: knowledge intensive system to solve the problem of inferring molecular structure from mass spectrometer information. MYCIN: to diagnose blood infections. 450 rules gathered from experts. Rules included uncertainty SHRDLU: system to understand natural language based on syntactic analysis PROLOG, PLANNER, FRAMES development of knowledge representations, reasoning languages History of AI AI becomes Industry R1 – first commercial expert system at DEC – to help configure orders for new computer systems. Saved company 40 million $ a year. 40 expert systems used by 1988 Dupont had 100 in use saving company 10 m $ a year Plan for 5th generation intelligent computers to run Prolog Research on microelectronics, chip design, user interface Billions of $ industry with expert systems, vision systems, Robots, Software, Hardware for these. AI Winter Companies failed to deliver Return of Neural Networks, Back propagation to learning, parallel distributed processing Connectionist models of intelligent systems vs. Symbolic models AI adopts scientific methods Symbolic computation - control theory, statistical Analysis Machine learning – information theory Uncertain reasoning – stochastic modelling, probability and decision theory Applications of AI HLAI: Human Level AI AGI: General AI Autonomous vehicles Speech Recognition Autonomous planning and scheduling Game playing Spam fighting Logistics planning Machine translation Intelligence Involves Follows a process (?) Learning Set a goal based on needs Reasoning Assess the value of any currently known information in support of the goal Understanding Gather additional information that could Grasping truths support the goal Seeing relationships Manipulate the data such that it achieves Considering meanings a form consistent with existing information Separating fact from Define the relationships and truth values belief between existing and new information … Determine whether the goal is achieved Modify the goal in light of new data and its effect on the probability of success Repeat process until goal is achieved! Kinds of Intelligence Kinds of simulation intelligence potential Visual-Spatial moderate Bodily – Kinesthetic Moderate to high Creative none Interpersonal Low to moderate Intrapersonal none Linguistic low Logical- high mathematical AI view Strong AI – generalized intelligence that can adapt to a variety of situations Weak AI - specific intelligence designed to perform a particular task well Reactive machines - chess playing - no memory, computational power and algorithms – weak AI Limited memory - self driving car – decisions based on experience stored in memory – current strong AI Theory of mind – can assess goals Self awareness Experiment 1. If the number of customers Tom gets is twice the square of 20% of the number of advertisements he runs, and the number of advertisements he runs are 45, what is the number of customers Tom gets? 2. Are reflex actions rational? Are they intelligent? 3. To what extent are the following computer systems instances of AI? a. supermarket barcode scanners b. web search engines c. voice activated telephone menus d. internet routing algorithms that respond dynamically to the state of the network? 4. Which of the following can be done by computers with AI at present? a. play a game of table Tennis e. discover and prove a new mathematical algorithm b. drive along ghat roads f. write an intentionally funny story c. drive in traffic g. give competent legal advice in a specialised area of law d. play a decent game of bridge h. translate spoken English into spoken Swedish in real time AI AI is built on 1. Automated problem solving through efficient search in solution space – trial and error method enormous computational complexity space-time trade off heuristics – domain knowledge use Paradigms of search Linear programming Integer programming Dynamic programming Heuristic search Evolutionary algorithms ( genetic) with huge computational power being available these became possible (1985 – 1995) AI AI is built on 2. Knowledge and deduction store and retrieve knowledge and interpret and deduce/reason have rules and use them to deduce meaning Knowledge and understanding /realization are different Knowledge Representation – logic propositional, first order Deduction - logics of knowledge Paradigms Knowledge based systems Expert systems Automated theorems Formal verification KB is huge! Memory being available makes KB possible ( 1990 – 2000) AI AI is built on 3. Ability to learn can the system learn to solve a problem better? Learn to plan? Machine learning , NN To make computer look intelligent Automated problem solving Machine learning Logic and deduction Human computer interaction Computer vision Natural Language Processing Robotics AI Fundamentals notion of expressing computation as an algorithm decidability/un-decidability Godel’s Incompleteness Theorem: "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F." computability Turing machine is capable of computing any computable function tractability/ intractability A polynomial function is intractable if an NP complete problem can not be reduced to the polynomial in polynomial time. problems for which there exist no efficient algorithms to solve them