inteligenta artificiala - curs 1

40
Inteligență artificială Curs 1 Lect.dr. Elena Băutu [email protected]

Upload: astefanesei-alexandru

Post on 17-Dec-2015

214 views

Category:

Documents


11 download

DESCRIPTION

Inteligenta Artificiala - Curs 1

TRANSCRIPT

  • Inteligen artificial Curs 1

    Lect.dr. Elena Butu

    [email protected]

  • Organizare

    7 martie 2014 https://sites.google.com/site/elenabautu/ 2

    Pagina web a cursului: http://ebautu.homenet.org/

    Notare: 50% nota la laborator + 50% nota la examen Nota la laborator: 4 proiecte, fiecare cu pondere 25% Examen: test scris

    Manuale Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern

    Approach, Prentice Hall, 2003, http://aima.cs.berkeley.edu/ Crina Groan and Ajith Abraham. Intelligent systems: A modern approach.

    Vol. 17. Springer, 2011. https://archive.org/details/Intelligent_Systems Poole, David L., and Alan K. Mackworth. Artificial Intelligence: foundations

    of computational agents. Cambridge University Press, 2010. Dan Cristea, Mdlina Raschip, Ionu Pistol Curs de Inteligena

    artificial, Universitatea Al. I. Cuza, Iai, 2013

    Cursuri online Intro to AI Udacity Artificial Intelligence EdX

  • Obiective

    7 martie 2014 https://sites.google.com/site/elenabautu/ 3

    Metode inteligente pentru rezolvarea problemelor reale

    Recunoaterea problemelor ce pot fi abordate cu metode din sfera IA

    Formularea problemei i utilizarea unei metode din IA pentru rezolvarea ei

  • Preliminarii

    7 martie 2014 https://sites.google.com/site/elenabautu/ 4

    Familiarizarea cu algoritmi de rezolvare a problemelor

    Specificarea

    Structuri de date i implementare

    Elemente de calcul a complexitii

    Programare

    n special programare orientat obiect

    Indiferent de limbaj

  • Coninut

    7 martie 2014 https://sites.google.com/site/elenabautu/ 5

    Scurt introducere n Inteligena Artificial Metode de cutare pentru rezolvarea problemelor

    Formularea problemelor Strategii de cutare a soluiei

    Strategii de cutare neinformate Strategii de cutare informate

    Strategii de cutare local Metode tip traiectorie Metode tip populaie

    Tehnici de nvare automat nvare supervizat

    nvare nesupervizat

    Sisteme care nva Sisteme bazate pe reguli n medii certe

    Sisteme bazate pe reguli n medii incerte Sisteme care nva singure

  • Cuprins

    7 martie 2014 https://sites.google.com/site/elenabautu/ 6

    Ce este Inteligena artificial?

    Scurt istoric

    Domenii ale IA

    Exemple de aplicaii IA

  • Definiii ale inteligenei

    7 martie 2014 https://sites.google.com/site/elenabautu/ 7

    Capacitatea de a nelege uor i bine, de a sesiza ceea ce este esenial, de a rezolva situaii sau probleme noi pe baza experienei acumulate anterior (DEX 98)

    Psihologul Howard Gardner definete 7 subtipuri de inteligen Inteligena lingvistic

    Inteligena logico-matematic

    Inteligena spaial

    Inteligena corporal-kinestezic

    Inteligena muzical

    Inteligena interpersonal

    Inteligena intrapersonal

    Testele de inteligen testeaz primele 3

  • Ce este Inteligena artificial?

    7 martie 2014 https://sites.google.com/site/elenabautu/ 8

    Capacitate a sistemelor tehnice evoluate de a obine performane cvasiumane (DEX 98)

    tiina crerii de maini inteligente, n special programe de calculator inteligente. Este similar cu utilizarea calculatoarelor n scopul nelegerii inteligenei umane, dar IA nu se rezum doar la metode ce pot fi observate biologic (John McCarthy, What is AI?)

  • Ce este Inteligena artificial?

    7 martie 2014 https://sites.google.com/site/elenabautu/ 9

    Abilitatea unui calculator sau robot controlat de calculator de a realiza sarcini efectuate (n general) de fiine inteligente (Enciclopedia britanica)

    Procese intelectuale caracteristice oamenilor, cum ar fi capacitatea de a raiona, de a descoperi semnificaii, de a generaliza, de a nva din experiene trecute.

    IA este tiina, parte a informaticii, care proiecteaz sisteme artificiale cu comportament inteligent adic sisteme ce manifest proprieti pe care n mod obinuit le asociem cu existena inteligenei n comportamentul uman - nelegerea limbajului, nvare, raionament, rezolvarea problemelor .a.m.d. (Barr, Feigenbaum, 1981)

  • Ce este Inteligena artificial?

    7 martie 2014 https://sites.google.com/site/elenabautu/ 10

    Maini(programe) inteligente, ce obin performane (mai bune) ca oamenii la anumite taskuri

    Interpretarea scrisului de mn

    Luarea deciziilor

    Sisteme care asist medicii n diagnosticare

    Identificarea locului propice pentru forri dup petrol

    Calcule

    Interpretarea datelor (de dimensiuni foarte mari)

    nelegerea limbajului natural, transcrierea acestuia

  • Strong AI vs. Weak AI

    7 martie 2014 https://sites.google.com/site/elenabautu/ 11

    Strong AI

    Este posibil programarea calculatoarelor aa nct s gndeasc la nivel uman i s fie contiente.

    Ar putea exista programe de calculator corect scrise care s emuleze o minte adic ar fi posibil s nu existe diferene ntre un program ce imit aciunile creierului i aciunile unei persoane, inclusiv nelegerea i contiina.

    Weak AI

    O main ce ruleaz un program este cel mult capabil s simuleze comportament uman i nelegere.

    Programe care efectueaz sarcini de gndire exist deja.

  • Percepia popular despre IA

    AI (2001, Spielberg) Her (2014)

    7 martie 2014 https://sites.google.com/site/elenabautu/ 12

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 13

    Originile IA: matematic, logic, informatic, filozofie, biologie, psihologie

    Primul sistem expert se consider a fi un papirus egiptean, datnd din mileniul III .Hr., care consta n 48 de observaii asupra diagnosticrii i tratrii rnilor la cap

    Blaise Pascal (sec XVII) realizeaz un calculator mecanic

    Charles Babbage the Analytical Engine (1842)

    George Boole, An investigation into the Laws of Thought (1854) bazele Logicii booleana

    Studiul logicii a dus la primul calculator electronic programabil (Turing i alii)

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 14

    1940 1950 primele preocupri pentru construirea unui creier artificial

    1951 Marvin Minski construiete prima main neuronal artificial (neural net machine)

    1950 -1960 primele programe ce implementeaz juctori automat pentru ah i dame (Game AI)

    1951 Turing propune un test pentru a rspunde la ntrebarea Can machines think?

    The Imitation game-> Testul Turing

    1951 Turing (pe hrtie), Shannon programe pentru jocul de ah/dame

    1958 programul a nvins un juctor uman pentru prima data

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 15

    1956 conferina Dartmouth, este pentru prima dat formulat termenul de Inteligen artificial

    Newell i Simon primul program pentru demonstrarea automat a teoremelor, Logic Theorist

    a demonstrat automat 38 din 52 de teoreme propuse, propunnd demonstraii noi, elegante

    1958 McCarthy, MIT propune limbajul LISP

    Axiomatizarea programrii

    Lista = structura de date principal pentru cod i pt date

    Multiple elemente de noutate ce stau la baza limbajelor moderne

    Recursivitate, Runtime typing, garbage collection samd

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 16

    1958 Perceptronul (reea neuronal, Rosenblatt)

    Bazele conexionismului (PDP parallel distributed processing)

    Modelarea fenomenelor mentale ori comportamentale reele interconectate de uniti simple (procese emergente)

    1964 Evans program (ANALOGY) pentru rezolvarea de teste de inteligen

    IQTests are not for machines, yet (Intelligence, 2012)

    Calcul simbolic n software de larg audien Maple, Mathematica

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 17

    1956 1974 Epoca de aur Programe automate pentru jocuri, demonstrarea automat de

    teoreme, programe ce poart conversaii n limbaj natural Direcii

    Reasoning as search rezolvarea problemelor n manier pas cu pas (deducie, aplicarea de tranziii, recurgnd la backtracking deseori) Modaliti de tratare a exploziei combinatoriale de ci posibile n cutare ->

    euristici

    Procesarea limbajului natural ELIZA (Feigenbaum, 1965) Robotul Shakey (Stanford, 1969) combin locomoia, percepia i

    rezolvarea problemelor

    Algoritmii evolutivi (prin 1970)

    1970, Marvin Minsky (in Life Magazine): "In from three to eight years we will have a machine with the general intelligence of an average human being.

    Finanare masiv din partea (D)ARPA Au permis cercetri n direciile dorite de cercettori, neimpuse

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 18

    Prima iarna IA (AI Winter) 1974 1980 Puterea de calcul era limitat Explozia combinatorial i intractabilitatea (demonstrat) a unor

    probleme Problemele toy abordate n IA nu preau a fi scalabile la probleme din

    viaa real

    Nevoia de informaii din domeniul problemei Abordarea sintactic nu era suficient

    Dimensiunea datelor era imens, nu putea fi imaginat un program (baz de date) care s rein atta informaie

    Paradoxul lui Moravec Rezolvarea de probleme de geometrie dificile i demonstrarea de teoreme

    necesit mai puin putere de calcul dect simularea de sarcini simple ce presupun percepie i mobilitate.

    Sistarea fondurilor 1966 - Eecul iniiativelor privind lingvistica computaional (mai ales

    traducerea automat a textelor)

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 19

    1963 Robinson a descoperit o metod simple de a implementa deducia algoritmul de rezoluie, bazat pe unificare (logic) Implementare cu succes sub forma Prolog (Kowalski,

    Colmerauer i Roussel prin 1970)

    Sisteme bazate de cunotine -> sisteme expert Sistem ce rezolv probleme sau rspunde la ntrebri despre

    un anumit domeniu, folosind reguli logice deduse din cunotine (foarte specifice) ale experilor n domeniu. (Feigenbaum, 1965)

    Adoptate rapid n lumea afacerilor, unde au produse profituri uriae

    Fonduri imense investite n cercetare Puterea sistemelor expert provine din baza de cunotine

    expert de care dispun. LISP machines

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 20

    Boom (1980 1987) XCON (eXpert CONfigurer) sistem expert pentru alegerea

    componentelor unui calculaor conform cerinelor clienilor (Carnegie Mellon University)

    MYCIN sistem expert pentru identificarea bacteriilor ce cauzeaz boli infecioase i pentru recomandarea de terapii cu antibiotice, cu dozajul ajustat individual pentru pacieni

    CYC (ongoing) proiect nceput n 1984 pentru a realiza o baz de cunotine uzuale (everyday common sense knowledge)

    Sisteme bazate pe cunotine (knowledge based systems) i ingineria de date (knowledge engineering)

    Investiii n paralel n Japonia, UK, SUA Hopfield propune un nou model de reea neuronal, care,

    mpreun cu un nou algoritm de nvare (backpropagation)vor fi de succes la probleme de recunoatere a caracterelor sau de recunoatere a vocii

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 21

    A doua iarna IA (1987 1993) Computerele Apple i IBM mai puternice i mai ieftine dect

    LISP machines

    Banii direcionai ctre alte domenii de cercetare

    Un motiv comun pentru dezamgirea produs de AI: scopurile prea nalte trmbiate dintru nceputuri

    n timpul rzboiului din golf (1991), SUA au dezvoltat un program de IA de planificare i analiza (DART - Dynamic Analysis and Replanning Tool) pentru a optimiza i planifica transportul echipamentelor i persoanelor, i pentru alte probleme logistice Se zice c pn n 1995, DART a economisit echivalentul

    tuturor fondurior investite de DARPA pentru AI n anteriorii 30 de ani

  • Scurt istoric

    7 martie 2014 https://sites.google.com/site/elenabautu/ 22

    Aplicarea meticuloas a metodelor din sfera IA i putere de calcul crescut a calculatoarelor moderne

    1997 Deep Blue l-a nvins pe Gary Kasparov la ah

    2000 robot-pets interactive

    2005 un robot la Stanford a ctigat o provocare DARPA (navigare automat prin inut deertic necunoscut)

    2011 Google self driving cars

    2011 IBMs Watson a nvins doi campioni la jocul Jeopardy

  • Domenii ale IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 23

    Reprezentarea cunotinelor Reele semantice

    Sisteme bazate pe logic

    Reele neuronale

    Raionament Demonstrarea automat a teoremelor

    Web semantic

    Raionament ce implic timp i spaiu

    Prelucrarea limbajului natural scris Scop: nelegerea limbajului scris

    Metode: analiz la nivel morfologic, sintactic, semantic, fenomene ale discursului, inferene textuale, generarea limbajului, lexicografie computaional (vezi curs Dan Cristea)

    Aplicaii complexe Sisteme de traducere automat

    Sisteme de extragerea informaiilor din texte

    Sisteme de rezumare de texte

    Sisteme pentru clasificat documente

  • Domenii ale IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 24

    Prelucrarea vorbirii Generarea vorbirii (incluziv generarea de voci cu emoii) nelegerea vorbirii (cu accent pe nelegerea vocilor izolate,

    nelegerea vocilor n medii cu zgomot, urmrirea unui vorbitor ntr-un grup)

    Interpretarea imaginilor Recunoaterea formelor, persoanelor n imagini Recunoaterea similaritii ntre obiecte identificate n imagini Segmentarea imaginilor (n pri semnificative), mpachetarea

    imaginilor Indexarea imaginilor

    Interpretarea secvenelor de film Recunoaterea persoanelor/formelor ntr-o secven Urmrirea personajelor n imagini

    Robotica Sisteme de articulaie, de echilibru, etc.

  • Domenii ale IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 25

    nvare

    Supervizat, Nesupervizat, Hibrid

    nvare cu algoritmi genetici

    Metode inspirate din natura

    Metode statistice

    Maini pe vectori suport (PSO, ACO, Calcul cuantic)

    Data mining

  • Testul Turing

    7 martie 2014 https://sites.google.com/site/elenabautu/ 26

    Turing (1950) "Computing machinery and intelligence": "Can machines think?" "Can machines behave intelligently?"

    Test operaional pentru verificarea comportamentului inteligent: Imitation Game

    Turing a prezis c pn n anul 2000, o main ar avea 30% anse s pcleasc o persoan pentru 5 minute

    A anticipat problemele majore ntlnite n urmtorii 50 de ani A sugerat domenii majore in IA reprezentarea cunotinelor,

    raionament, nelegerea limbajului, nvare

  • Chatbots

    7 martie 2014 https://sites.google.com/site/elenabautu/ 27

    Competiia Loebner Prize

    Chatbots http://www.chatbots.org/

    ELIZA psychotherapist, http://nlp-addiction.com/eliza/

    ALICE Leobner prize winner 2004

    Valerie Carnegie Mellon University receptionist

    IBMs Watson Jeopardy

    Turing test for poems

    Ai Dreams

  • Testul camera chinezeasca

    7 martie 2014 https://sites.google.com/site/elenabautu/ 28

    Testul lui Searle un argument mpotriva existenei strong AI

    Cutiile cu simboluri chinezeti = baza de date

    Cartea cu instruciuni = programul (forma de IA)

    ntrebrile n chinez = input

    Rspunsurile = output

    Un calculator ce ruleaz un program de IA ,chiar dac trece testul Turing, de fapt nu gndete i nici nu nelege, doar simuleaz

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 29

    Selectarea automat a tirilor provenite din diferite surse

    Opus aranjrii manuale a tirilor (vezi ziare, tv)

    https://news.google.com/

    Dpdv teoretic

    nvare nesupervizat (clustering)

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 30

    Traducere automat Google translate, Bing translator, Yahoo Babel Fish,

    Systran

    Dpdv teoretic Sisteme bazate pe reguli

    Metode statistice

    Metode bazate pe exemple

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 31

    Procesarea limbajului natural recunoaterea vocii Ton pentru transmiterea numarului de card

    Software pentru dictare automat

    Dpdv teoretic Modele Markov Ascunse, Cautare A*, transformate Fourier

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 32

    Recomandri bazate pe comportamentul colectiv/individual al utilizatorilor Netflix

    Netflix prize competiie pentru cel mai bun algoritm colaborativ de filtrare care s prezic ratingul unui film pe baza ratingurilor cunoscute pentru filme (fr alte informaii privind utilizatorii ori filmele, acetia fiind codificai numeric)

    Dpdv teoretic Tehnici de nvare automat (machine learning)

    nvare nesupervizat (clustering)

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 33

    Pantofi inteligeni adaptarea pernei de aer la particularitile deplasrii (vitez, drum etc)

    Smart shoes

    Dpdv teoretic

    Modele de regresie

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 34

    Sisteme de tip ntrebare rspuns Aplicaii majore n medicin IBMs Watson a nvins doi campioni la jocul Jeopardy

    Dpdv teoretic Parsarea limbajului natural stocat n fiiere text Tehnici de nvare automat (machine learning) De exemplu:

    One clue was: It was introduced by the Coca-Cola Company in 1963. Watson can find a passage stating that Coca-Cola first manufactured Tab (the correct response) in 1963, so in order to answer the question, Watson needed to understand that introducing and manufacturing can be equivalent if a company is introducing a product. But that is highly dependent on context: if you introduce your uncle, it doesn't mean you manufactured him.

    16 terrabytes, 2800 processor cores, 6 million logic rules 10 server racks x 750 IBM servers Does Watson think?

    How do you define think? Does a submarine swim?

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 35

    Telescopul Hubble

    Elaborarea de hri grafice ale universului

    Planificare

    Dpdv teoretic

    Machine learning (clustering, regresie)

    Procesarea imaginilor digitale

    Drizzle (Variable-Pixel Linear Reconstruction)

    Probleme de planificare

    Probleme de satisfacere a constrngerilor

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 36

    AI art Evolutionary art evolving Monalisa, Bill Gates or Darwin

    Dpdv teoretic Programare genetic

  • Exemple de aplicaii IA

    7 martie 2014 https://sites.google.com/site/elenabautu/ 37

    Intelligent Computing in Bioinformatics

    Intelligent Computing in Neuroinformatics & Cheminformatics

    Intelligent Computing in Computational Biology and Drug Design

    Intelligent Computing in Signal Processing

    Intelligent Computing in Pattern Recognition

    Intelligent Computing in Biometrics Recognition

    Intelligent Computing in Image Processing

    Intelligent Computing in Robotics

    Intelligent Computing in Computer Vision

    Intelligent Computing in Brain Imaging and Bio-medical Engineering

    Intelligent Computing in Management

    Intelligent Computing in Finance/Banking

    Intelligent Computing in Communication Networks

    Intelligent Computing in Petri Nets/Transportation Systems

    Intelligent Computing in Social Networking

    Intelligent Computing in Network Software/Hardware

    Intelligent Control and Automation

    Intelligent Image/Document Retrievals

    Intelligent Data Fusion and Information Security

    Intelligent Prediction & Time Series Analysis

    Intelligent Agent and Web Applications

    Intelligent Sensor Networks

    Intelligent Fault Diagnosis

    Knowledge Representation/Reasoning and Expert Systems

    Virtual Reality and Human-Computer Interaction

    Optical Networks/Processing

    Business Intelligence and Multimedia Technology

    Intelligent E-services/Smart Homes

  • IA astzi

    7 martie 2014 https://sites.google.com/site/elenabautu/ 38

    Paradigma agenilor inteligeni

    Un program de IA = agent inteligent

    Sistem ce percepe mediul i acioneaz asupra acestuia, pentru ndeplinirea unui scop

    Artificial intelligence: What you really need to know (Forbes magazine, 2014)

    http://aitopics.org/ the Internet's largest collection of information about the

    research, the people, and the applications of Artificial Intelligence.

  • IA astzi

    7 martie 2014 https://sites.google.com/site/elenabautu/ 39

    Magia IA

    Optimizare

    Teoria probabilitilor i statistic matematic

    Logic

    Algoritmi

  • Rezumat

    7 martie 2014 https://sites.google.com/site/elenabautu/ 40

    Ce este Inteligena artificial?

    Scurt istoric

    Domenii ale IA

    Exemple de aplicaii IA

    ntrebri?