人工智能基础人工智能基础 Introduction to Artificial Introduction to Artificial Intelligence (AI) Intelligence (AI) 1From DeepBlue to AlphaGoChess: Deep Blue defeated human world champion Garry Kasparov in a six-game match in 1997. Deep Blue searches 200 million positions per second, uses very sophisticated evaluation, and undisclosed methods for extending some lines of search up to 40 ply.From DeepBlue to AlphaGoGo:AlphaGowon5-0inaformalmatchonOctober2015,againstthereigning3-timesEuropeanChampion,FanHui, becoming the first program toeverbeataprofessionalGoplayerinanevengame.In March 2016 AlphaGo won 4-1againstthelegendaryLeeSedol,thetopGoplayerintheworldoverthepastdecade.AI is always developingArtificial IntelligenceIntelligence5Lecture OutlinevPhilosophy in Artificial Intelligence (AI) What it means to think and whether artifacts could and should ever do so? vIdeas for AI Learning, Symbolic AI, Connectionism, Nouvelle AI, Evolutionary Computation, Computational Swarm Intelligence vCourse overview62024/7/21Part: Philosophy in AIAI:Introduction72024/7/21What is Intelligence, anyway?R.J.Sternberg:“Viewednarrowly,thereseemtobealmostasmanydefinitionsofintelligenceastherewereexpertsaskedtodefineit.”Itisusefultothinkofintelligenceintermsofanopencollectionofattributes.AI:Introduction82024/7/21vPerception Manipulation, integration, and interpretation of data provided by sensors, including purposeful, goal-directed, active perceptionAction Coordination, control, and use of effectors to accomplish a variety of tasks, including exploration and manipulation of the environment, including design and construction of tools towards this end.Characteristics of Intelligence(1)AI:Introduction92024/7/21Reasoning Deductive (logical) inference, inductive inference, analogical inference, hypothetical reasoning, including reasoning in the face of uncertainty and incomplete information. Problem-solving Setting of goals (without explicit instructions from another entity), Formulation of plans，Evaluating and choosing among alternative plans, adapting plans in the face of unexpected changesCharacteristics of Intelligence(2)AI:Introduction102024/7/21vLearning and AdaptationLearning to describe specific domains in terms of abstract theories and concepts, Learning to use, adapt, and extend language, Learning to reason, plan, and act. Adapting behavior to better cope with changing environmental demand.Sociality Into social groups based on shared objectives, development of shared conventions to facilitate orderly interaction, culture. Creativity Exploration, modification, and extension of domains by manipulation of domain-specific constraints, or by other means.Characteristics of Intelligence(3)AI:Introduction112024/7/21What is AI, anyway?vUnderstand and BUILD intelligent entitiesSeeking exact definition? (could last a lifetime)vHighly interdisciplinary Compute Science, Philosophy, Psychology, Linguistics, NeuroScience vCurrently consists of huge variety of subfieldsAI:Introduction122024/7/21How to measure Machine Intelligence?vTwo viewsBehavior/action (weak AI )Can the machine act intelligently? Turing test.Thought process/reasoning (strong AI )Are machines actually thinking?Chinese Room of J. R. Searle Turing testvWhen does a system behave intelligently? A. M. Turing (1950) Computing Machinery and Intelligence. Mind 49: 433-460. Operational test of intelligence: imitation gameRequires the collaboration of major components of AI: knowledge, reasoning, language understanding, learning, Chinese Room ArgumentvTherefore,Searlesays: -the idea of a non-biological machine being intelligent is incoherentA man is in a room with a book of rules. Chinese sentences are passed under the door to him. The man looks up in his book of rules how to process the sentences. Eventually the rules tell him to copy some Chinese characters onto paper and pass the resulting Chinese sentences as a reply to the message he has received. The dialog continues. To follow these rules the man need not understand Chinese.Searle, John. R. (1980) Minds, brains, and programs. Behavioral and Brain Sciences 3 (3): 417-457152024/7/21Goals of AIvCurrent goal -Makingintelligentmachines,especiallyintelligentcomputerprograms.-DesignandconstructionofusefulnewtoolstoextendhumanintellectualandcreativecapabilitiesvLong-term goal UnderstandingofthemechanismsunderlyingthoughtandintelligentbehaviorsandtheirembodimentinmachinesAI:Introduction162024/7/21Part : Ideas for AIvLearning ”child machine”vConnectionismvSymbolic AIvEvolutionary Computation ”artificial life”vComputational Swarm IntelligencevNouvelle AI Ideas for AI1. Learning ApproachQ. What about making a child machine that could improve by reading and by learning from experience? A. This idea has been proposed many times, starting in the 1940s. Eventually, it will be made to work. However, AI programs havent yet reached the level of being able to learn much of what a child learns from physical experience. Nor do present programs understand language well enough to learn much by reading. JohnMcCarthy:Tasks of Machine LearningvLearning means changevImprove behaviour/performance: learn to perform new tasks (more) increase ability on existing tasks (better) increase speed on existing tasks (faster)vProduce and increase knowledge: formulate explicit concept descriptions formulate explicit rules discover regularities in data discover the way the world behavesThe Architecture of intelligent system with learning capabilityEnvionmentPerceptionEvaluationPerformanceLearningKinds of LearningvSupervised Learning Given a set of example input/output pairs, find a rule that does a good job or predicting the output associated with a new input.vUnsupervised Learning (clustering) Given a set of examples, no labeling of them, group them into natural clusters.Trainingdata,Validationdata,TestdataKinds of Learning contd.vSemi-supervised Learning Combination of supervised and unsupervised learning.vReinforcement Learning An agent interacting with the world makes observation, takes actions, and is rewarded or punished; it should to learn to choose actions in such a way as to obtain a lot of reward. Learning issuesvOverfitting (generalization ability) : can the machine well-trained on observed data behave well on other data either?vBias: which hypotheses are preferred?vRobustness: how does the training data influence the learning result? Data Scale, Change, Noise, and ImbalancevTransparency: can we understand what and how has been learnt?vComputation Complexity: what is the efficiency of the learning algorithms? Time, Memory, Scalability, convergencyAI:Introduction242024/7/212. ConnectionismvThemechanismsofbrainsareverydifferentindetailfromthoseincomputers vhow brains work? Bottom-up strategyNatural Neural NetworkAI:Introduction252024/7/21vA brief historyM-Pneuron(McCulloch&Pitts)Perceptron(Rosenblatt)HopfieldModel,B-PLearningMethod(Rumelhart&McClelland)DeepLearning(GeoffreyHinton)vApplicationsRecognition,Vision,Business,Medical,.vCore Issues -Topology-Learning MethodsConnectionismAlphaGo - Ground-breakingArtificial BrainvArtificial brains are a man-made machines that have the same cognitive ability as humans and other mammals. vProjects SyNAPSE: DAPRA, with IBM, HP, HRL Labs. Blue Brain: EPFL Together with IBM Barin in Silicon: Standford University Neuromorphic chip from Stanford vThis tiny chippackaged in black plastic and mounted on a printed circuit boardmodels 1,024 excitatory pyramidal cells and 256 inhibitory basket cells. Their cellular properties and synaptic organization are downloaded to the chip over a USB link, which also allows their activity to be visualized in real-time. Emily Nathan 2007 3. Symbolic AIvPhysical Symbol System Hypothesis of Newell and Simon - the processing of structures of symbols by a digital computer is sufficient to produce artificial intelligence - the processing of structures of symbols by the human brain is the basis of human intelligence - it remains an open question whether the Physical Symbol System Hypothesis is true or false - Top-down strategyvProblem-sloving Expert System Knowledge Engineering-Search,Representation,Reasoning-GPS,DeepBlue,DENDRAL,CYC. Symbolic AISearch ProblemHow to search is a key to Symbolic AI as well as AI 4. Evolutionary ComputationvBiological evolution To produce an enormous variety of living organisms closely suited to different sets of needs in different environments. vSimulated evolution By modeling those processes of biological evolution on computers, it turns out that we can sometimes get the computers to evolve solutions to problems.AI:Introduction332024/7/21DNA ComputingAI:Introduction342024/7/21vGenetic Algorithm Use strings of symbols to encode solutions to problems, like strings of molecules in DNA. Transforming and recombining portions of strings enables an evolutionary computation to search for good solutions, partly analogous to biological evolution. Genetic Programming Extends these ideas to automatic programming by using structures which are better suited to the problem than strings are. Evolutionary ComputationvEvolutionary Strategy Use natural problem-dependent representations, and primarily mutation and selection as search operators. Mutation is normally performed by adding a normally distributed random value to each vector component. The step size or mutation strength is often governed by self-adaptation. The selection in evolution strategies is deterministic and only based on the fitness rankings, not on the actual fitness values.vEvolutionary Programming Harder to distinguish from evolutionary strategies. Its main variation operator is mutation; members of the population are viewed as part of a specific species rather than members of the same species therefore each parent generates an offspring.Evolutionary ComputationExample: Forming body plans with evolutionvNode specifies part type, joint, and range of movementvEdges specify the joints between partsvPopulation?Graphs of nodes and edgesvSelection?Ability to perform some task (walking, jumping, etc.)vMutation?Node types change/new nodes grafted onFromVirgilGriffith,GoogleTechTalk-2007Artificial Life (Alife)vArtificial Life is the study of man-made systems that exhibit behaviors characteristic of natural living systems. It complements the traditional biological sciences concerned with the analysis of living organisms by attempting to synthesize life-like behaviors within computers and other artificial media. By extending the empirical foundation upon which biology is based beyond the carbon-chain life that has evolved on Earth, Artificial Life can contribute to theoretical biology by locating life-as-we-know-it within the larger picture of life-as-it-could-be. Chris Langton (in Proc. of first Alife conference)Artificial Life and EvolutionaryOrigin of LifeTodayLife,and might have beenas it isFromVirgilGriffith,GoogleTechTalk-20075. Computational Swarm Intelligence vIntelligence is often considered a property of individuals.vAre we social because we are intelligent or are we intelligent because we are social? - Intelligence can emerge from social interaction.vEmergent behaviour when a group behaves in ways that were not ”programmed” into its members.vSwarm intelligence - simulated social interaction - emergent collective intelligence of groups of simple agents402024/7/21Computational Beauty in Nature AI:Introduction412024/7/21ObservationsvBird flocks and fish schools move in a coordinated way, but there is no coordinator (leader) - So, what decides the behaviour of a leader-less flock?vAnts and termites quickly find the shortest path between the nest and a food source - . and solve many other advanced problems as well: keeping cattle, building (ventilated) housing, coordinated heavy transports, tactical warfare, cleaning house, etc. - A single ant is essentially a blind, memory-less, random walker!vDistributed systems without central controlvUseful not only to simulate but also to solve optimization problemsAI:Introduction422024/7/21Computational SimulationvMulti-Agent Systems - a system composed of multiple interacting intelligent agents. - application including computer games, networks, transportation, logistics, and etc.vAnt Colony Optimization - 1991 (Dorigo) - mostly for combinatorial optimizationvParticle Swarm Optimization - 1995 (Kennedy & Eberhart) - more general optimization technique6. Nouvelle AIvRodney Brooks (1991) Insect-like mobile robots: Allen, Herbert, Genghis - The basic building blocks of intelligence are very simple behaviours, More complex behaviours emerge from the interaction of these simple behaviours. - Producing systems that display approximately the same level of intelligence as insects. AI:Introduction442024/7/21vSituated AI - Build disembodied intelligences who unfriendly interact with the world (traditional) - Build embodied intelligences situated in a real world (Nouvelle).Nouvelle AIvLifetime Learning - Reinforcement learning - Adapt to environment by acting and receiving reward/punishment in the environment.AI:Introduction452024/7/21PartMachineLearning(newbook,chapters2-5)Concepts, Methods, Supervised and Unsupervised LearningPartConnectionism(newbook,chapters9-11)Concepts, Problems, ModelsPartSymbolicAI(oldbook,chapters2-3) Problem representation, Graph Search, Adversarial Search, Knowledge, Logic inference, UncertaintyPartEvolutionaryComputation(oldbook,chapters7)Genetic Algorithms, Evolutionary Programming, Evolutionary StrategiesPartComputationalSwarmIntelligence(oldbook,chapters8)Ant Colony Optimization, Particle Swarm OptimizationPartNouvelleAI(oldbook,chapters6,newbook,chapter8)Agent, Reinforcement LearningCourse OverviewAI:Introduction462024/7/21GetageneralunderstandingofAI,preparingyourselfforlearningandstudyofbrachesofAI!GOAL!Loris Malaguzzi: Learning and teaching should not stand on opposite banks and just watch the river flow by; instead, they should embark together on a journey down the water. Through an active, reciprocal exchange, teaching can strengthen learning how to learn. AI:Machine Learning472024/7/21Learning to learn48