Introdução à Inteligência Artificial

© António Oliveira 1

Inteligência Artificial

António OliveiraINSTITUTO SUPERIOR MIGUEL TORGA

Informática / Informática de Gestã[email protected]


1.Introdução à Inteligência Artificial (IA)

1.1 Definição de IA1.2 História da IA1.3 Áreas de Aplicação da IA1.4 Bibliografia

Definição de IA


• Não existe uma definição unica.

• Podemos definir Inteligência Artificial de acordo com quatro abordagens: • Sistemas que pensam como um ser humano • Sistemas que actuam como um ser humano • Sistemas que pensam racionalmente • Sistemas que actuam racionalmente

Definição de IA


• Sistemas que pensam como um ser humano

• “O excitante esforco para fazer os computadores pensar… maquinas com mentes, no seu sentido literal” (Haugeland, 1985)

• “(A automatizacao de) actividades que associamos com o pensamento humano, tais como tomada de decisoes, resolucao de problemas e aprendizagem” (Bellman, 1978)

Definição de IA


• Sistemas que actuam como um ser humano

• “a arte de criar maquinas que executam funcoes que requerem inteligencia quando executadas por pessoas” (Kurzweil, 1990)

• “O estudo de como fazer os computadores fazer coisas nas quais os seres humanos hoje em dia sao mais eficientes.” (Rich and Knight, 1991)

Definição de IA


• Sistemas que pensam racionalmente

• “O estudo das faculdades mentais atraves do uso de modelos computacionais” (Charniak and McDermott, 1985).

• “O estudo das computacoes que tornam possivel perceber, raciocinar e agir” (Winston, 1992).

Definição de IA


• Sistemas que actuam racionalmente

• “Um campo de estudo que procura explicar e emular o comportamento inteligente em termos de processos computacionais” (Schalkoff, 1990).

• “O ramo da ciencia de computacao que se preocupa com a automacao do comportamento inteligente” (Luger and Stubblefield, 1993).


História da IA


História da IA


História da IA


História da IA


História da IA

História da IA

© Ricardo Malheiro 13

• Gestação (1943-1956)• 1940: Turing e outros 2 cientistas criaram o primeiro

computador “Colossus” com o intuito de decifrar mensagens alemãs na 2ª guerra mundial.

• 1943: tentou utilizar esse computador para pesquisas de IA (ex: xadrez) , mas as pretensões foram bloqueadas pelo governo britânico.

• 1943: McCulloch e Pitts propuseram um modelo artificial de neurónios.• Cada neurónio poderia estar “ligado” ou “desligado”.• A rede neuronal criada teria capacidades de

aprendizagem.


História da IA• Gestação (1943-1956)

• 1950: Alan Turing através do seu artigo “Computing Machinery and Intelligence” mostrou pela 1ª vez uma visão completa do que viria a ser a IA.

• Neste artigo foram apresentados o teste de Turing (para tentar provar a possibilidade de existência de máquinas inteligentes), aprendizagem de máquina, algoritmos genéticos e aprendizagem por reforço.

• Turing Previu que no ano 2000 uma máquina seria capaz de enganar com 30% de hipóteses durante 5 minutos.


História da IA

• Gestação (1943-1956)• 1951: Marvin Minsky e Dean Edmonds construiram o primeiro

computador de redes neuronais, possuia 40 neurónios.

• 1956: No decorrer de um seminário em Dartmouth, o conceito de Inteligência Artificial foi criado por John McCarthy• Organizado pelo John McCarthy para estabelecer uma nova

área para estudar computação e inteligência. • Os seguintes 20 anos testemunharam o crescimento da área,

sendo este crescimento conduzido pelos pioneiros que participaram neste seminário


História da IA

• Entusiasmo Inicial (1952-1969)

• Neste periodo, houve muito entusiasmo e grandes expectativas por parte dos investigadores, já que foram dados avanços significativos

• 1952: Desenvolvimento de um programa capaz de jogar damas ao nivel de um jogador de torneio. O programa jogava melhor do que o seu autor.


História da IA

• Entusiasmo Inicial (1952-1969)• 1957: Este entusiasmo era sintetizado por um investigador

Herbert Simon que, declarou que num futuro próximo o computador seria capaz de lidar com qualquer problema com o qual o ser humano também lidasse.• Este entusiasmo tinha a ver com os resultados alcançados em

problemas simples. Tinha-se a ideia que os problemas mais complexos seriam resolvidos igualmente acompanhando a evolução do hardware, só que isso não se verificou (e.g. Sistemas de tradução).

• 1957: Simon previu que em 10 anos 1 computador seria campeão de xadrez e um novo e importante teorema matemático seria provado por um computador.

História da IA


• Entusiasmo Inicial (1952-1969)• 1958: John McCarthy criou a linguagem LISP que se transformou

na linguagem dominante da IA. O Lisp é a segunda linguagem de programação mais antiga ainda em uso. A linguagem Fortran é um ano mais antiga. • Com ela tentou criar um programa “Advice Taker” que iria

permitir utilizar a lógica para encontrar soluções para vários problemas.

• 1959: Criação por parte de Gelernter do programa Geometry Theorem Prover para demonstrar teoremas matemáticos

• 1963: J. Robinson antecipou-se a McCarthy ao criar um algoritmo completo para resolução de problemas de lógica de 1ª ordem.


História da IA

• Realismo (1966-1974)

• Métodos para resolver problemas simples eram incapazes de resolver problemas mais difíceis

• Os computadores tinham pouco poder computacional para problemas mais complexos

• Foi preciso esperar, não 10 anos como previu Simon, mas cerca de 50 anos para um computador vencer um Mestre de Xadrez

History of AI


• Knowledge-based systems (1969-1979)• A knowledge-based system is a computer program that reasons

and uses a knowledge base to solve complex problems. • The term is broad and is used to refer to many different kinds of

systems. • Today, the one common theme that unites all knowledge based

systems is an attempt to represent knowledge explicitly via tools such as ontologies and rules rather than implicitly via code the way a conventional computer program does.

• A knowledge based system has two types of sub-systems: a knowledge base and an inference engine

• Expert systems are systems which simulate the reasoning of an expert of a determined area

History of AI


• Knowledge-based systems (1969-1979)

• Program DENDRAL was created by researchers of the University of Stanford and could infer the molecular structure from informations received by a mass spectrometer.

• Program MYCIN was developed with the goal of diagnose blood infections. It had about 450 rules, and MYCIN was as effective as some experts and much better than intern doctors.


History of AI

• AI becomes an industry (1980-1988)• At the beginning of the 80's, Artificial Intelligence became an

industry with many enterprises creating expert systems, which permitted economize millions of dollars in few years (expert systems, robotics and computer vision).

• That happened in United States but also in other developped countries

• 1981: In Japan was created the project ”Fifth generation" which consisted in a plan of 10 years to build intelligent computers. • These computer should run Prolog programming language in

the same way that ordinary computers run machine code.• One of the ambitions of the project was to understand natural

language.


History of AI

• AI becomes an industry (1980-1988)• 1982: It appeared the first expert system to be commercialized,

the R1.

• The booming of AI industry also included companies such as Carnegie Group, Inference, Intellicorp. and Teknowledge• These offered software tools to build expert systems

• Hardware companies also appeared like Lisp Machines Inc., Texas Instruments, Symbolics and Xerox• From these resulted workstations optimized for the

development of Lisp programs


History of AI• Neural Networks (1986-present)

• In 80's, there were big advances in research of neural networks, mainly with the creation of retro-propagation algorithm.

• Neural networks became again one of the main algorithms to solve problems. • Retro-propagation, is a common method of training neural

networks used in conjunction with an optimization method such as gradient descent.

• The method calculates the gradient of a loss function with respect to all the weights in the network.

• The gradient is fed to the optimization method which in turn uses it to update the weights, in an attempt to minimize the loss function.

• The algorithm was applied in many learning problems in computer science and psychology


History of AI

• Neural Networks (1986-present)• Hopfield analyzed the storage and optimization properties of

networks• Rumelhart and Hinton studied neural network models of memory.• There was a period in which neural networks and traditional AI

were seen as rival fields• In the picture you can see a neuralnetwork with one three layers: input,hidden neurons and output

History of AI


• Recent events (1987-present)

• Big advances in last years in areas such as voice recognition, character recognition (Hidden Markov Models) and pattern recognition

• A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with with unobserved (hidden) states.

• A HMM can be presented as the simplest dynamic Bayesian network.

History of AI


• Recent events (1987-present)

• Example of a hidden Markov model in the picture• There were advances in the study of intelligent agents, which

through the use of sensors have the capability of see, listen and act when faced by stimuli in real environments.

History of AI


• Recent events (1987-present)• 2011: It was created the new supercomputer by IBM, Watson

• Based on advanced techniques of Natural Language Processing, Information Retrieval, Knowledge Representation, Reasoning and Machine Learning

• Massive parallel processing• 90 clusters with a total of 2880 servers with 3.5 GHz

processors (8 cores and 4 threads per core).• 16 Terabytes of RAM.• Part 1: http://www.youtube.com/watch?v=5Gpaf6NaUEw• Part 2: http://www.youtube.com/watch?v=6ay17a7mEIk• Part 3: http://www.youtube.com/watch?v=gphA9u5nm5U• Part 4: http://www.youtube.com/watch?v=ilrKOovFpVc

History of AI


• Recent events (1987-present)• Google Driverless Car

• The car is equipped with a laser radar which allows the vehicle to generate a detailed 3D map of the environment.

• The 3D map is combined with information from high-resolution maps and data from other sensors to produce different mathematical models that allow the car to act autonomously.


Application Areas of AI• We are going to show some examples to the majority of the following areas

• Education, Games/Entertainment, Literature• Recognition of voice, text, image• Telecommunication• Architecture, Commerce, Finances• Robotics• Translation• Neural networks• Autonomous control• Logistic planning• Failure detection• Diagnosis of diseases• Aero-spacial, military• Medicine, biology (molecular biology, bioinformatics)


Application Areas of AI

• Games

• Computer games are played on a personal computer rather than a dedicated video game console or arcade machine. Their defining characteristics include a lack of any centralized controlling authority, a greater degree of user control over the video-gaming hardware and software used and a generally greater capacity in input, processing, and output.

• Although personal computers only became popular with the development of the microprocessor and microcomputer, computer gaming on mainframes and minicomputers had previously already existed.


Application Areas of AI• Games

• Online multiplayer games have achieved popularity largely as a result of increasing broadband adoption among consumers. Affordable high-bandwidth Internet connections allow large numbers of players to play together, and thus have found particular use in massively multiplayer online role-playing games, Tanarus and persistent online games such as World War II Online.



• Games• The Deep Blue was a supercomputer and a software created by IBM specifically to

play chess with 256 processors, able to analyze 200 million positions per second.• In 1997, IBM's Deep Blue computer was the 1st to defeat the world champion in a

game of chess, Garry Kasparov to win by a score 3.5 to 2.5 in an exhibition match. Kasparov said he felt "a new kind of intelligence” was on the other side of the board.



• Autonomous control• The computer vision system ALVINN computer has been trained to drive a car,

keeping it on track. • It was placed in a vehicle controlled by NAVLAB computer and is used traverse

the United States over a distance of 4600 km. • The NAVLAB had camcorders that transmitted images to the road ALVINN which

then calculated the best way to drive, taking into account the training done before.



• Air traffic control

• Air traffic control (ATC) is a service provided by ground-based controllers who direct aircraft on the ground and through controlled airspace, and can provide advisory services to aircraft in non-controlled airspace.

• The primary purpose of ATC worldwide is to prevent collisions, organize and expedite the flow of traffic, and provide information and other support for pilots.

• In some countries, ATC plays a security or defensive role, or is operated by the military.



• Air traffic control• OASIS is a sophisticated air traffic control system based on multi-agent

paradigm, used at Sydney Airport, Australia, in which the agents take the place of aircraft in operation



• Other control systems

• How to stop the car without the wheels slipping due to the speed, friction, etc.?

• How to focus the camera on luminosity function, distance, etc.?

• How to adjust the temperature in relation to the amount of laundry, water flow, etc.?



• Search information on the web• A web search engine is a software system that is designed to search for

information on the World Wide Web. • The search results are generally presented in a line of results often

referred to as search engine results pages (SERPs). • The information may be a mix of web pages, images, and other types of

files. • Some search engines also mine data available in databases or open

directories.• How to find relevant information?



• Case-based reasoning applications• Case-based reasoning (CBR), broadly construed, is the process of solving

new problems based on the solutions of similar past problems.• They have been used in various applications such as financial analysis,

risk advisory services and process control.

• Genetic algorithms applications• In the field of artificial intelligence, a genetic algorithm (GA) is a search

heuristic that mimics the process of natural selection. • This heuristic (also sometimes called a metaheuristic) is routinely used

to generate useful solutions to optimization and search problems.• They are applicable in various problems such as scheduling times,

power systems and phylogenetic.



• Artificial neural networks

• In AI, artificial neural networks (ANNs) are a family of statistical learning models inspired by biological neural networks • The central nervous systems of animals, in particular the brain

• They are used to estimate or approximate functions that can depend on a large number of inputs and are generally unknown.

• They have been used in a wide variety of tasks, from intrusion detection systems to computer games.



• Optical character recognition systems• Optical character recognition (OCR) is the mechanical or electronic

conversion of images of typed, handwritten or printed text into machine-encoded text.

• Can translate arbitrarily written letter into text.



• Recognition of handwriting

• Handwriting recognition is the ability of a computer to receive and interpret intelligible handwritten input from sources such as paper documents, photographs, touch-screens and other devices.

• Used in many personal digital assistants.



• Voice recognition• In computer science and electrical engineering, speech recognition (SR)

is the translation of spoken words into text. • It is also known as "automatic speech recognition" (ASR), "computer

speech recognition", or just "speech to text" (STT).• It is commercially available and widely used.



• Computer algebra systems• A computer algebra system (CAS) is a software program that allows

computation over mathematical expressions in a way which is similar to the traditional manual computations of mathematicians and scientists.

• Mathematica and Macsyma are good examples of AI applications in solving algebraic problems.



• Probabilistic logic• One technique for uncertainty reasoning, it has been widely used in

industrial control systems.

• Language recognition • Natural language understanding is a subtopic of natural language

processing in artificial intelligence that deals with machine reading comprehension.



• Computer vision systems• Computer vision is a field that includes methods for acquiring,

processing, analyzing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions.

• Used in many industrial applications.



• Applications using Artificial Life• Artificial life is a field of study and an associated art form which examine

systems related to life, its processes, and its evolution, through the use of simulations with computer models, robotics, and biochemistry.

• Used in the entertainment industry and in the development of Computer Graphics.



• Systems based on the idea of artificial agents

• In artificial intelligence, an intelligent agent (IA) is an autonomous entity which observes through sensors and acts upon an environment using actuators (i.e. it is an agent) and directs its activity towards achieving goals

• Called Multi-Agent Systems, have become common for solving complex problems.



• Software agents to talk

• In computer science, a software agent is a computer program that acts for a user or other program in a relationship of agency, which derives from the Latin agere (to do): an agreement to act on one's behalf.

• Virtual characters conversing in natural language as if they were human truth, are increasingly common on the Internet.



• Recommendation of products• A personalized product recommendation isn’t based on an assumption

or guess. • Personalized recommendations are based on user behavior. • These are items that have been frequently viewed, considered, or

purchased with the one the customer is currently considering.• How to make personalized recommendations of products?• How to model the customer profile?



• Medical diagnosis• Medical diagnosis is the process of determining which disease or

condition explains a person's symptoms and signs. • It is most often referred to as diagnosis with the medical context being

implicit.• The AI techniques are increasingly used by doctors to diagnose diseases

based on symptoms analyzes. (eg detection of tumors or MYCIN system for diagnosing bloodstream infections).



• Forecasting• Forecasting is the process of making predictions of the future based on

past and present data and analysis of trends. • A commonplace example might be estimation of some variable of

interest at some specified future date.• Predict the dollar value (or the weather) tomorrow?• What data is relevant? Are there recurrent behavior?



• User interface• The user interface, in the industrial design field of human–machine

interaction, is the space where interactions between humans and machines occur.

• How to provide the user with the help he needs exactly?• How to interact (and who knows surfing the web) with a mobile phone

without having to enter the numbers (hands-free)?



• Intrusion detection• An intrusion detection system (IDS) is a device or software application

that monitors network or system activities for malicious activities or policy violations and produces reports to a management station.

• How to tell if a given user behavior is suspicious and deal with it?

• Spam filtering• Email filtering is the processing of email to organize it according to

specified criteria. • Most often this refers to the automatic processing of incoming

messages, but the term also applies to the intervention of human intelligence in addition to anti-spam techniques, and to outgoing emails as well as those being received.

• How to tell if a message is junk or if it indeed interests



• Logistics planning

• Logistics is the management of the flow of things between the point of origin and the point of consumption in order to meet requirements of customers or corporations.

• During the Persian Gulf War in 1991, the United States used an application called DART to run the automated logistics planning and scheduling performance of the carriage.

• This involved about 50 thousand vehicles, air cargo and personnel at the same time and took into account points of departure, arrival, routes and conflict resolution between all variables.



• Translation systems• Machine translation is a sub-field of computational linguistics that

investigates the use of software to translate text or speech from one language to another.

• They have been widely used, such as SYSTRAN• The results are not comparable with human translators.



• Planning and scheduling• Advanced planning and scheduling refers to a manufacturing

management process by which raw materials and production capacity are optimally allocated to meet demand.

• The 100 million km from Earth, NASA Remote Agent program was the first program that controls the scheduling of a spacecraft operations.

• Generates plans for high-level goals and makes the detection, diagnosis and recovery problems.

• Problem solving• Problem solving consists of using generic or ad hoc methods, in an

orderly manner, for finding solutions to problems.• The PROVERB is a computer program that solves puzzles crossword

better than most humans.



• Robotics

• Robotics is the branch of mechanical engineering, electrical engineering, electronic engineering and computer science that deals with the design, construction, operation, and application of robots, as well as computer systems for their control, sensory feedback, and information processing.



• Robotics

• Robots are physical agents that perform tasks manipulating the physical world.

• For this, they are equipped with actuators such as legs, wheels and claws. The actuators have the sole purpose of exerting forces on the physical environment.

• The robots are also equipped with a variety of sensors, which allow them to perceive the environment: cameras, ultrasound, gyroscopes, accelerometers.



• Robotics• They are already widely used in microsurgery. • The HipNav is a system that uses computer vision techniques to create a 3D

model of the patient's internal anatomy. • Then use robots to guide the insertion of a hip replacement prosthesis.


Bibliography

• Inteligência Artificial, Stuart Russell e Peter Norvig, 2ª ed., Campus, 2004, cap. 1

• Inteligência Artificial, Ernesto Costa e Anabela Simões, FCA, 2004, cap. 1

Engineering

Introdução à Inteligência Artificial