Katedra
Podstaw
Konstrukcji
Maszyn
Wydział
Mechaniczny
Technologiczny
Politechnika
Śląska
ul. Konarskiego 18a
44-100 Gliwice
tel. 237 1467
fax 237 1360
http://kpkm.polsl.pl
Metody Sztucznej
Inteligencji
Kierunek studiów MiBM, semestr 4
Prowadzący przedmiot
Prof. dr hab. Wojciech Moczulski
Materiały pomocnicze do
wykładu
(do użytku wewnętrznego przez studentów
Wydziału Mechanicznego Technologicznego
Politechniki Śląskiej)
Rok akademicki 2004/05
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
1
MSI-w1_2004/05_1
Metody sztucznej inteligencji
Politechnika Śląska
Katedra Podstaw Konstrukcji Maszyn
Rok akademicki 2004/05
Wykład 1
MSI-w1_2004/05_2
Informacje o przedmiocie
• Strona KPKM:
http://kpkm.polsl.pl
Informacje dydaktyczne/Semestr IV/
Metody Sztucznej Inteligencji/Strona przedmiotu
(MiBM)
User:
msimibm
Hasło:
?????
• Kontakt:
Wojciech Moczulski
wm@polsl.pl
• Konsultacje (s. 406 Wydz. MT):
– Wtorek
13:30 - 15:30
– Czwartek
13:30 - 15:40
• Kolokwium zaliczeniowe:
07.06.2005
MSI-w1_2004/05_3
Część I
Historia Sztucznej Inteligencji
i pojęcia podstawowe
MSI-w1_2004/05_4
Sztuczna inteligencja
(AI=Artificial Intelligence)
Dziedzina wiedzy, która postawiła sobie za cel
i przedmiot badań maszyny, które potrafiłyby
rozwiązywać zadania, przy zachowaniu których
człowiek korzysta ze swojej inteligencji
(Marvin Minsky)
A.M. Turing
Computing Machinery and Intelligence
Mind 49, 1950, s.433-460
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
2
MSI-w1_2004/05_5
Dziedziny i zastosowania AI
• Percepcja
• rozumowanie logiczne
• rozpoznawanie
obrazów
• rozumienie mowy
• uczenie maszynowe
• odkrywanie nowej
wiedzy
• Sztuczne sieci
neuronowe
• teoria gier
• tłumaczenie tekstów
• automatyczne
dowodzenie twierdzeń
• malowanie obrazów
• pisanie poezji
MSI-w1_2004/05_6
Inne definicje AI
Ekscytująca próba uczynienia
komputerów myślącymi maszynami z
pamięcią, w pełnym i dosłownym sensie
tego pojęcia (Haugeland, 1985)
Badanie zdolności umysłowych z
zastosowaniem modeli obliczeniowych
(Charniak & Mc Dermott, 1985)
Automatyzacja działań, które łączymy z
ludzkim myśleniem, jak: podejmowanie
decyzji, myślenie, uczenie się, ...
(Bellman, 1978)
Badanie algorytmów, które umożliwiają
spostrzeganie, rozumowanie i działanie
(Winston, 1992)
Sztuka tworzenia maszyn, które
wykonują działania wymagające
inteligencji wtedy, gdy są wykonywane
przez człowieka (Kurzweil, 1990)
Dziedzina badań, poszukująca wyjaśnie-
nia i sposobu emulowania zachowań
inteligentnych za pomocą pojęć
dotyczących procesów obliczeniowych
(Schalkoff, 1990)
Badanie, jak można umożliwić
komputerom wykonywanie zadań, w
których jak dotychczas ludzie są lepsi
(Rich & Knigth, 1991)
Dziedzina informatyki dotycząca
automatyzacji inteligentnego
zachowania (Luger & Stubblefield,
1993)
MSI-w1_2004/05_7
4 kierunki rozwoju AI
• Wiersze:
– górny - procesy myślenia
– dolny - sposób działania
• Kolumny:
– lewa - odnosi się do
właściwości człowieka
– prawa - określenia z
zastosowaniem terminu
„racjonalny”
Systemy
myślące w
sposób
podobny do
ludzi
Systemy
myślące
racjonalnie
Systemy
działające
podobnie
jak ludzie
Systemy
działające
racjonalnie
MSI-w1_2004/05_8
Maszyna Turinga (1937)
Maszyna Turinga nie jest obiektem fizycznym.
Jest to abstrakcyjny schemat działania według
zadanego algorytmu. Jego istotę oddaje angielskie
określenie discrete-state machine, co odpowiada
polskiemu terminowi maszyna stanów
dyskretnych.
Maszyna Turinga była odpowiedzią na problem
liczb nieobliczalnych.
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
3
MSI-w1_2004/05_9
Test Turinga (1950)
Test Turinga jest wzorowany na grze „retro” w
naśladownictwo (imitation game).
W grze uczestniczyły cztery osoby: A (kobieta), B
(mężczyzna), C (goniec) i D (sędzia). Zadaniem
sędziego było odgadnąć kto jest kim na podstawie
zadawanych pytań.
Turing zastąpił A maszyną. Celem testu jest
odgadnięcie tego czy sędzia rozmawia z maszyną
czy człowiekiem.
MSI-w1_2004/05_10
Test Turinga (1950)
Test Turinga podaje:
operacyjną definicję inteligencji
Test określa:
Zachowanie inteligentne maszyny na poziomie
człowieka we wszystkich zadaniach poznawczych,
wystarczających do porozumiewania się z
człowiekiem, w taki sposób jak robi to człowiek.
MSI-w1_2004/05_11
Warunki, aby komputer przeszedł
test Turinga
• przetwarzanie języka naturalnego
(komunikacja z rozmówcą)
• reprezentacja wiedzy
• automatyczne wnioskowanie z wykorzystaniem
zgromadzonych informacji:
– do zadawania pytań
– do wyciągania wniosków (konkluzji)
• uczenie się, adaptacja do nowych okoliczności
MSI-w1_2004/05_12
Naśladowanie myślenia człowieka (1)
• przedmiot „modelowania poznawczego”
• konieczna znajomość sposobu działania
ludzkiego mózgu:
– przez introspekcję
– przez eksperymenty psychologiczne
• Gdyby istniała precyzyjna teoria ludzkiego
umysłu, byłoby możliwe opracowanie
programu działającego zgodnie z tą teorią
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
4
MSI-w1_2004/05_13
• Ujęcie z zastosowaniem praw rozumowania
• Pierwowzór: sylogizm Arystotelesa
(wzorzec struktur argumentowania, które
dają zawsze poprawną konkluzję, pod
warunkiem zastosowania poprawnych
przesłanek)
• Przykład: Sokrates jest człowiekiem;
wszyscy ludzie są śmiertelni; dlatego
Sokrates jest śmiertelny.
Naśladowanie myślenia człowieka (2)
MSI-w1_2004/05_14
Dwa główne ujęcia AI
• Ujęcie logicystyczne
bazujące na logice formalnej
(będzie przedmiotem większej części
wykładów)
• Ujęcie z zastosowaniem agentów
(krótki opis zawarto w dalszej części
wykładu)
MSI-w1_2004/05_15
Ujęcie logicystyczne
• Zbudowanie programu logicznego,
działającego jak system inteligentny
• Problemy:
– nie jest łatwe ujęcie nieformalnej wiedzy w
wyrażenia rachunku zdań i rach. Predykatów
– rozwiązanie praktycznych problemów może
wymagać niedostępnych mocy obliczeniowych
• Reprezentacja wiedzy i systemy rozumowania
ściśle określone i łatwo zrozumiałe
MSI-w1_2004/05_16
Ujęcie z zastosowaniem agentów
• Działać racjonalnie = osiągnąć cel, gdy są
dane przekonania
• Agent: jednostka, która spostrzega i działa
• Zalety:
– ujęcie bardziej ogólne niż stosowanie „praw
myślenia”
– bardziej podatne na rozwój naukowy
• Ograniczona racjonalność
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
5
MSI-w1_2004/05_17
Sztuczna inteligencja
Sztuczna inteligencja jest nauką kognitywną.
Jest połączeniem wiedzy i metod z zakresu:
- filozofii,
- matematyki,
- psychologii,
- lingwistyki,
- informatyki.
MSI-w1_2004/05_18
Podstawy AI (1)
Filozofia (428 pne. - obecnie)
– Platon - pytanie o algorytm rozróżniania pojęć
– Arystoteles - system sylogizmów
– Leibnitz (materializm) 1646-1716 - mechaniczny
układ do przeprowadzania operacji mentalnych
– Hume (empirycyzm) - zasada indukcji
– Russel (1872-1970) - logiczny pozytywizm: cała
wiedza może być przedstawiona za pomocą teorii
logicznych, połączonych ze zdaniami
obserwacyjnymi (obserwacje dokonane za pomocą
czujników)
MSI-w1_2004/05_19
Podstawy AI (2)
Matematyka (ok. 800 - obecnie)
– al-Khowarazmi: wprowadził algorytm
– Boole (1847): formalny język rozumowania
logicznego
– Frege (1879): logika 1. Rzędu
– Tarski (1902-1983): teoria referencji (jak obiekty
logiczne odnoszą się do obiektów świata)
– Gödel (1931): twierdzenie o niezupełności (w
każdym języku umożliwiającym opis własności
liczb naturalnych istnieją zdania prawdziwe, które
są nierozstrzygalne)
MSI-w1_2004/05_20
Podstawy AI (3)
Psychologia (1879 - obecnie)
• behawioryzm (istotne są obiektywne związki:
bodziec-odpowiedź; wiedza, przekonania,
cele i rozumowanie są nienaukowe)
• psychologia poznania (cognitive psychology):
Craik (1943) - podstawy agentów bazujących
na wiedzy
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
6
MSI-w1_2004/05_21
Podstawy AI (4)
• Informatyka (1940 - obecnie) - rozwój
środowisk sprzętowych i programowych
koniecznych do badań w zakresie AI
• Lingwistyka (1957 - obecnie) - rozwój
wspólnie z AI:
– lingwistyka obliczeniowa
– przetwarzanie języka naturalnego
MSI-w1_2004/05_22
Historia (1933-1942)
która zapoczątkowała AI
– Konrad Zuse (1933) – maszyna wykorzystująca potencjał
elektryczny – komputer zerowej generacji
– John Atanasoft i Clifford Berry (1937-1942) – komputer
ABC; zasada działania oparta na arytmetyce binarnej
– Howard M. Aiken (1939-1944) – maszyna Mark I z
przekaźników elektromagnetycznych.
– John Mauchly i Presper Eckert (1940) – ENIAC
(Electronic Numerical Integrator and Computer)
– George Stibitz (1940) – The Complex Number Calculator;
cztery podstawowe działania w systemie dwójkowym,
– IMB (1942) – Selective Electronic Calculator
MSI-w1_2004/05_23
Historia AI (1943-1956)
Początki AI
– Mc Culloch & Pitts (1943) - model sztucznego
neuronu
– Turing (1950) – test Turinga
– Shannon, Turing (ok. 1950) - programy do gry
w szachy
– Minsky (1951) - pierwszy komputer neuronowy
(3000 lamp + autopilot z B-24; 40 neuronów!!!)
– Newell & Simon - LT=Logic Theorist (program
komputerowy zdolny do myślenia
nienumerycznego)
MSI-w1_2004/05_24
Historia AI (1952-1969)
dynamiczny rozwój
– Newell & Simon - GPS (General Problem
Solver) - pierwszy program myślący „po
ludzku”
– McCarthy (1958) - LISP (LISt Processing)
– Minsky (ok. 1963) - mikroświaty (np. świat
klocków)
– Rosenblatt (1962) - perceptron (sieć neuronów,
która się uczy)
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
7
MSI-w1_2004/05_25
Entuzjazm (1957)
• H. Simon:
It is not my aim to surprise or shock you - but the
simplest way I can summarize is to say that there
are now in the world machines that think, that
learn and that create. Moreover, their ability to
do these things is going to increase rapidly until -
in a visible future - the range of problems they
can handle will be coextensive with the range to
which human mind has been applied.
MSI-w1_2004/05_26
Historia AI (1966-1974)
Dawka realizmu
• Programy początkowo nie zawierały wiedzy
i działały stosując jedynie pewne
manipulacje na tekstach (ELIZA)
• Wiele problemów okazało się zbyt trudnych
lub NP-zupełnych
• Stwierdzono fundamentalne ograniczenia
związane z podstawowymi strukturami AI
(np. neuronów)
MSI-w1_2004/05_27
Historia AI (1969-1979)
Nowe koncepcje
• Wąskie dziedziny problemowe
• Systemy doradcze
– MYCIN: diagnostyka chorób krwi i płynu
mózgowo-rdzeniowego (450 reguł, uwzględnienie
niepewności i sprzecznych opinii ekspertów)
– PROSPECTOR: wspomaganie prac wiertniczych
– inne skuteczne wdrożenia
• Minsky (1975): reprezentacja wiedzy - „ramy”
MSI-w1_2004/05_28
Historia AI (1980-1988)
AI staje się przemysłem
• Komercyjny system doradczy R1
(Mc Dermott, 1982)
• V generacja komputerów (Japonia, 1981)
• Sprzedaż 2 mld $ w 1988
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
8
MSI-w1_2004/05_29
Historia AI (1986-obecnie)
• Powrót sieci
neuronowych
• Algorytmy genetyczne
i programy
ewolucyjne
• Systemy szkieletowe
• Sieci przekonań
• Inżynieria wiedzy
• Uczenie maszynowe
i odkrycia w bazach
danych
• ...
MSI-w1_2004/05_30
Podsumowanie
• Filozofia: myśl jest pod pewnym względem jak
maszyna, która działa na wiedzy zakodowanej
w określonym języku,
• Matematyka: dostarczyła narzędzi do opisu
procesu myślenia,
• Psychologia: teoria, że ludzie i zwierzęta mogą
być postrzegani jako maszyny przetwarzające
informacje,
• Technologia komputerowa: pozwala na
implementację algorytmów,
MSI-w1_2004/05_31
Część II
Ujęcie AI
z zastosowaniem agentów
MSI-w1_2004/05_32
Inteligentny agent
• Agent postrzega swoje otoczenie poprzez
sensory
• Agent oddziałuje na otoczenie poprzez efektory
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
9
MSI-w1_2004/05_33
Inteligentny agent - przykłady
• Człowiek:
– sensory: oczy, uszy, nos, ...
– Efektory: ręce, nogi, usta, ...
• Robot:
– sensory: kamera TV, czujniki IR, sonar, ...
– Efektory: chwytaki, głośnik, wyświetlacz, ...
• Agent programowy:
– sensory i efektory: ciągi bitów
MSI-w1_2004/05_34
Przykład idealnego racjonalnego
agenta: SQRT w kalkulatorze
MSI-w1_2004/05_35
Struktura inteligentnego agenta
AGENT
=
ARCHITEKTURA
+
PROGRAM
Środowisko, w którym
można realizować
program:
• komputer 1-układowy
• kamera
• mikrofon
• ...
• Oprogramowanie
umożliwiające
realizację programu
agenta (np. BIOS)
Funkcja,
realizująca
odwzorowanie
od percepcji do
akcji
MSI-w1_2004/05_36
Przykłady
Typ agenta
Percepcje
Akcje
Cele
Środowisko
System
diagnostyki
medycznej
Symptomy,
wyniki,
odpowiedzi
pacjenta
Pytania,
testy, terapie
Zdrowy
pacjent,
minimalne
koszty
Pacjent,
szpital
System
analizy
obrazów
satelitarnych
Punkty (pixe-
le) o zmien-
nej intensyw-
ności, kolor
Drukuj
kategoryzację
sceny
Poprawna
kategoryzacja
Obrazy z
orbitującego
satelity
Interaktywny
nauczyciel
angielskiego
Wpisywane
słowa
Drukuj
ćwiczenia,
sugestie,
poprawki
Maksymali-
zuj ocenę
studenta z
testu
Zbiór
studentów
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
10
MSI-w1_2004/05_37
Ś
rodowisko
AGENT
Sensory
Efektory
Jaki jest świat w
tej chwili ?
Jakie działania
trzeba wykonać?
Warunki - reguły działania
Agent – typ I
(działający na zasadzie odruchów)
MSI-w1_2004/05_38
Ś
rodowisko
AGENT
Sensory
Efektory
Jaki jest świat w
tej chwili ?
Jakie działania
trzeba wykonać?
Warunki - reguły działania
Jak zmienia sie świat?
Stan
Co powoduje moje działanie ?
Agent – typ II
(działający na zasadzie odruchów ze stanem wewnętrznym)
MSI-w1_2004/05_39
Ś
rodowisko
AGENT
Sensory
Efektory
Jaki jest świat w tej
chwili ?
Jakie działania trzeba
wykonać?
Cel
Jak zmienia sie świat?
Stan
Co powoduje moje działanie ?
Co się stanie jeżeli
wykonam działanie A ?
Agent – III
(ukierunkowany na cel)
MSI-w1_2004/05_40
Ś
rodowisko
AGENT
Sensory
Efektory
Jaki jest świat w tej
chwili ?
Jakie działania trzeba
wykonać?
Jak zmienia sie świat?
Stan
Co powoduje moje działanie ?
Co się stanie jeżeli
wykonam działanie A ?
Jak szczęśliwy będę
w tym nowym stanie ?
Użyteczność
Agent – typ 4
(ukierunkowany na użyteczność)
W. Moczulski, Metody Sztucznej Inteligencji. Pol. Śl.,
Wydz. MT, MiBM s.4, r.ak. 2004/05
11
MSI-w1_2004/05_41
• Agent
• Agent inteligentny
• Cztery typy agentów
Podsumowanie