1

w1/1

Metody sztucznej inteligencji

Politechnika Śląska

Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 2003/04

Materiały na prawach rękopisu

Wyłącznie do użytku studentów Wydziału

MT Politechniki Śląskiej

Wprowadzenie

w1/2

Informacje o przedmiocie

• Strona KPKM:

http://kpkm.polsl.pl

Informacje dydaktyczne/Semestr IV/

Metody Sztucznej Inteligencji/Strona przedmiotu

(AiR)

User:

msiair

Hasło:

????

• Kontakt: Wojciech Moczulski

[e-mail]

• Konsultacje (s. 406 Wydz. MT):

– Poniedziałek

10:00 - 12:00

– Wtorek

15:00 - 16:00

• Kolokwium zaliczeniowe:

01.06.2004

w1/3

Sztuczna inteligencja

(AI=Artificial Intelligence)

• Dotyczy prób rozumienia istot inteligentnych
• formalnie powstała w 1956, wcześniejsze

badania od 1951

• dziedzina nauki o charakterze teoretycznym i

eksperymentalnym

• ze względu na próby zastosowań we

wszystkich dziedzinach działalności człowieka
ma prawdziwie uniwersalny charakter

w1/4

Poddziedziny 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

w1/5

Czym jest 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)

w1/6

Definicje AI - 4 kategorie

• 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

2

w1/7

Test Turinga (1950)

• Operacyjna definicja inteligencji
• Zachowanie inteligentne to zdolność do

osiągania umiejętności na poziomie
człowieka we wszystkich zadaniach
poznawczych, wystarczających do
wykpienia człowieka zadającego pytania.

• Komputer jest „odpytywany” przez

człowieka; OK, jeśli człowiek nie zgadł, że
odpytuje komputer.

w1/8

Warunki, aby komputer przeszedł

test Turinga

• przetwarzanie języka naturalnego (komunikacja

z rozmówcą)

• reprezentowanie wiedzy
• automatyczne rozumowanie z wykorzystaniem

zgromadzonych informacji:

– do zadawania pytań
– do wyciągania wniosków (konkluzji)

• uczenie się, adaptacja do nowych okoliczności

w1/9

Myśleć podobnie jak człowiek

• 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ą

w1/10

Myśleć racjonalnie

• 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.

w1/11

Myśleć racjonalnie:

• Ujęcie logicystyczne (bazujące na logice

formalnej)

• Ujęcie z zastosowaniem racjonalnych

agentów

w1/12

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

3

w1/13

Ujęcie z zastosowaniem

racjonalnych 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ść

w1/14

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)

w1/15

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)

w1/16

Problemy

• Trudne (intractable): czas wymagany do

rozwiązania przykładowego problemu danej
klasy rośnie co najmniej wykładniczo w
stosunku do wymiaru tego problemu

• NP-zupełne (NP-complete): typowe np. dla

kanonicznego przeszukiwania lub procesów
rozumowania; problem klasy NP-zupełnej
daje się zredukować do problemu trudnego

w1/17

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

w1/18

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

4

w1/19

Historia AI (1943-1956)

Początki AI

– Mc Culloch & Pitts (1943) - model sztucznego

neuronu

– 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)

w1/20

Historia AI (1952-1969)

Wczesny entuzjazm, wielkie

oczekiwania

– 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)

w1/21

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.

w1/22

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)

w1/23

Historia AI (1969-1979)

Nowe, skuteczne 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”

w1/24

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

5

w1/25

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

• ...

w1/26

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,

w1/27

Inteligentny Agent

w1/28

Inteligentny agent

• Agent postrzega swoje otoczenie poprzez

sensory

• Agent oddziałuje na otoczenie poprzez efektory

w1/29

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

w1/30

Przykład idealnego racjonalnego

agenta: SQRT w kalkulatorze

6

w1/31

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

w1/32

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

w1/33

Przykład agenta - taksówkarz

Typ agenta

Percepcje

Akcje

Cele

Środowisko

Taksówkarz

Kamery,
prędkościomierz,
GPS, mikrofon

Kierowanie,
przyspieszanie
hamowanie,
rozmowa z
pasażerem

Bezpieczeń-
stwo
szybkość,
komfortowa
jazda,
przestrzeganie
kodeksu,
maksymalne
zyski

Droga,
korki,
piesi

w1/34

Ś

rodowisko

AGENT

Sensory

Efektory

Jaki jest świat w

tej chwili ?

Jakie działania

trzeba wykonać?

Warunki - reguły działania

Agent działający na zasadzie odruchów

w1/35

Ś

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 działający na zasadzie odruchów

ze stanem wewnętrznym

w1/36

Ś

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 ukierunkowany na cel

7

w1/37

Ś

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 ukierunkowany na użyteczność

w1/38

Podsumowanie

• Agent
• Agent inteligentny
• Cztery typy agentów