Algorytmiczna inteligencja
DETERMINISTYCZNE
ALGORYTMY
czyli tzw. sztuczna inteligencja (ang. AI)
SEKWENCYJNE
nie wymagamy nie wymagamy
Przedmiotem rozważań są relacje pomiędzy obliczeniami
determinizmu sekwencyjności
maszynowymi a ludzkÄ… inteligencjÄ… w najrozmaitszych
kontekstach:
ALGORYTMY ALGORYTMY
PROBABILISTYCZNE RÓWNOLEGA
E
Naśladowania
W obszarze informatyki zadanie
Wspierania
nie wymagamy ścisłego
AI jest często utożsamiane z
teoretycznego uzasadnienia
Zastępowania
 budowaniem maszyn, o których
Analizowania
działaniu dałoby się powiedzieć,
ALGORYTMY
Uczenia siÄ™
że jest podobne do ludzkich
HEURYSTYCZNE
Gromadzenia wiedzy przejawów inteligencji
Wnioskowania
AI
itd.
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 1 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 2
Test Turinga
Algorytmy heurystyczne sÄ… bardzo przydatne, bo
odzwierciedlają szczególną naturę sterowania w inteligentnych
Człowiek (sędzia) prowadzi
programach: brak pewności, nieprecyzyjne dane, łatwość
rozmowę w języku naturalnym osoba testująca (sędzia)
modyfikacji, konieczność adaptacji, możliwość ewolucji itp.
z pozostałymi stronami. Jeśli sędzia
Dane, na których pracują algorytmy inteligentne muszą
nie jest w stanie wiarygodnie
umożliwiać reprezentację i manipulowanie wiedzą w jej
określić, czy któraś ze stron jest
najrozmaitszych postaciach.
maszyną, czy człowiekiem, wtedy
mówi się, że maszyna przeszła test.
Osiągnięcie oryginalności rozwiązania charakterystycznej dla
Zakłada się, że zarówno
inteligentnego ludzkiego myślenia jest trudne do pogodzenia
człowiek jak i maszyna
z zaprogramowanym z góry działaniem komputera.
próbują przejść test
Wprawdzie w szachach programy komputerowe osiągnęły poziom jako człowiek.
mistrzowski lub nawet arcymistrzowski, ale w go grają wciąż
kiepsko, a i w brydża sportowego nie lepiej. człowiek odpowiadający komputer odpowiadający
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 3 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 4
Przykładowe pytania zadawane przez sędziego:
Test zaproponował Alan Turing w 1950 r.
Czy jesteÅ› komputerem?
Przewidywał, że maszyny w końcu będą w stanie przejść ten test.
Która jest godzina?
Oceniał, że około roku 2000 maszyny będą w stanie oszukać 30%
Kiedy była bitwa pod Grunwaldem?
ludzkich sędziów w czasie pięciominutowego testu. Przepowiedział
również, że ludzie przestaną uważać zdanie "myśląca maszyna" za Ile jest 57585063836034546 razy 85756459?
wewnętrznie sprzeczne. Przewidywał także, że uczenie maszynowe
Czy w podanym problemie szachowym białe mogą dać
nabierze dużego znaczenia w budowaniu wydajnych maszyn.
mata w trzech posunięciach?
To twierdzenie jest dzisiaj oceniane jako zasadne.
Opisz swoich rodziców?
Jakie wrażenie wywołują na tobie utwory The Doors?
Uczenie maszynowe (ang. machine learning) jest dziedzinÄ… AI,
Co sÄ…dzisz o aktualnych wydarzeniach politycznych?
w której przedmiotem zainteresowania są metody umożliwiające
uczenie się programom komputerowym. Program uczy się, jeśli Jaka jest twoja opinia o procesie globalizacji?
potrafi modyfikować jakiś aspekt samego siebie i dzięki temu
Najtrudniejsze sÄ… trzy ostatnie pytania!
stopniowo działa coraz lepiej lub wydajniej.
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 5 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 6
1
Przy pozytywnym nastawieniu rozmawiajÄ…cego program
Przykład  podróbki ludzkiej inteligencji
ELIZA może przez chwilę uchodzić za inteligentny, ale dość
(program ELIZA i typowa dla niego wymiana zdań)
Å‚atwo siÄ™ gubi:
Człowiek: Moja żona skarży się, że często jestem przygnębiony.
Człowiek: Byłem bratem zakonnym w klasztorze Benedyktynów.
ELIZA: Przykro mi słyszeć, że jesteś przygnębiony.
ELIZA: Opowiedz mi coś więcej o swojej rodzinie.
Człowiek: Prawdę mówiąc, czuję się fatalnie  jestem
Aby przeprowadzić rzeczywiście inteligentną rozmowę maszyna-
nieszczęśliwy.
kandydat musi mieć odpowiednio duży zasób wiedzy, posiadać
ELIZA: Czy myślisz, że po wizycie tutaj przestaniesz być
zdolność uczenia się całkowicie nowych pojęć, konfrontowania
nieszczęśliwy?
ich z tym, co już wie i wyciągania trafnych wniosków.
Człowiek: Być może pomożesz mi odkryć, dlaczego nienawidzę
Obecnie najlepszy w teście Turinga jest stale rozwijany program
swojego brata.
ALICE  stara się on w pełni naśladować heurystykę zwykłej
ELIZA: Opowiedz mi coś więcej o swojej rodzinie. konwersacji.
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 7 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 8
Na przykład:
Badania w zakresie AI prowadzone są zasadniczo w dwóch
Testujący: Co to jest krzesławka?
obszarach:
Maszyna: Nie mam pojęcia.
Testujący: Jest to gatunek afrykańskiej mrówki, którego osobniki
wyjaśnianie w jaki sposób ludzie uczą się, rozumują, wnioskują,
potrafią sczepiając się ze sobą imitować krzesło. Zastawiają
planujÄ…, decydujÄ… itp.
w ten sposób pułapkę na zmęczonych podróżników. Kiedy
któryś skusi się na odpoczynek, krzesławki opadają go, tworzenie programów komputerowych, które w pewnych
paraliżują ukąszeniami i pożerają.
zawężonych (na razie?) dziedzinach zachowują się inteligentnie.
Maszyna: Niesamowite!
Testujący: Czy sądzisz, że krzesławka występuje w przyrodzie?
Spore sukcesy osiągnięto w rozgrywaniu niektórych gier:
Maszyna: Nie, to jest niemożliwe.
znakomite programy grajÄ…ce w warcaby,
TestujÄ…cy: Dlaczego?
Maszyna: Z wielu powodów. Po pierwsze, mrówki nie mogą mieć
bardzo dobre programy grajÄ…ce w szachy.
pojęcia co to jest krzesło i do czego służy. Po drugie, jest
niemożliwe, aby potrafiły utrzymać formę krzesła
normalnych rozmiarów. Po trzecie, nikt przy zdrowych
zmysłach nie usiadłby na czymś takim. Ale to jest śmieszne!
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 9 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 10
Drzewo gry w  kółko i krzyżyk :
Drzewo gry (czyli sposób na zapisanie rozgrywki)
(dla tablicy 3x3)
pozycja poczÄ…tkowa
W liściach gra jest
maksymalna głębokość  9
(korzeń drzewa)
jednoznacznie
maksymalna liczba potomków  9 (w korzeniu, potem maleje)
rozstrzygnięta.
maks. liczba wierzchołków do sprawdzenia 9! = 362 880
ruchy gracza A
Ò! można napisać program, który gra perfekcyjnie
Ò!
Ò!
Ò!
ruchy gracza B
Drzewo gry w szachy:
20 możliwych otwarć białych
remis
ruchy gracza A
średnia liczba potomków  35
głębokość drzewa rzędu 100
wygrywa
ruchy gracza B
A
liczba wierzchołków do sprawdzenia w typowej grze  35100
remis wygrywa wygrywa wygrywa Ò! nie da siÄ™ napisać programu, który przeszukaÅ‚by
Ò!
Ò!
Ò!
A B A
całe drzewo gry; trzeba stosować heurystyki
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 11 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 12
2
Co oznacza postępowanie heurystyczne? Zalety algorytmów heurystycznych:
Jeśli upuścimy na podłogę nieduży przedmiot i stracimy możliwość radykalnego skrócenia czasu wykonania algorytmu,
go z oczu, to możemy poszukiwać go różnymi metodami:
łatwość poprawiania i doskonalenia w miarę zdobywania wiedzy
systematycznie - deterministycznym algorytmem o problemie.
sekwencyjnym,
Wady algorytmów heurystycznych:
 na chybił-trafił - algorytmem probabilistycznym,
systematycznie z pomocą przyjaciół - algorytmem równoległym,
nie gwarantujÄ… sukcesu,
analitycznie - algorytmem rozwiązującym równania ruchu
ich działanie nie daje się teoretycznie analizować  trzeba
przedmiotu (pełen model fizyczny),
wypróbowywać i sprawdzać
intuicyjnie - heurystycznym algorytmem przeszukiwania
nie można oszacować teoretycznego prawdopodobieństwa
zawężonego obszaru, w którym przedmiot może
sukcesu (co jest możliwe w algorytmach probabilistycznych)
się znajdować (obszaru wyznaczonego np. na
podstawie wcześniejszych doświadczeń)
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 13 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 14
Wiele heurystyk opiera się wprawdzie na ścisłych modelach Przeszukując drzewo gry w celu znalezienia najlepszego
i matematycznych sformułowaniach, ale nie dla całości posunięcia często stosuje się strategię minimaksową
problemu i dlatego nie dajÄ… one gwarancji sukcesu, np.:
Opiera siÄ™ ona
ruchy gracza A
komputerowe rozpoznawanie obrazu i mowy, na ocenach
przypisywanych
sterowanie ruchem robotów i manipulatorów.
ruchy gracza B
wierzchołkom
drzewa gry
Wiele algorytmów optymalizacyjnych to w istocie rzeczy 0 999 999 65
ruchy gracza A
heurystyki, które można nazwać przypuszczalnymi algorytmami
przybliżonymi, jak np.:
78 0 0 110 56 10
ruchy gracza B
rozwiązywanie bardzo dużych zadań transportowych,
999 71 999 106 15 142 0 87
ruchy gracza A
projektowanie układów VLSI,
ocena pozycji
rozwiązywanie złożonych zadań harmonogramowania. 5 74 0 28 999
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 15 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 16
W analizie drzewa gry przy strategii minimaksowej następuje
ruchy gracza A
propagacja ocen wierzchołków w stronę korzenia:
ruchy gracza B
jako ocenę wierzchołka reprezentującego ruch gracza A
przyjmuje się maksimum z ocen wierzchołków potomnych,
x
ruchy gracza A
jako ocenę wierzchołka reprezentującego ruch gracza B
przyjmuje się minimum z ocen wierzchołków potomnych.
x = ocena szans wygrania gry przez A,
x = 999  wygrana A,
Wprawdzie w liściach drzewa gra jest jednoznacznie
Zasady strategii minimaksowej:
x = 0  wygrana B.
rozstrzygnięta, ale ogromna liczba liści np. w szachach (<" 35100)
uniemożliwia rozpoczęcie od nich propagacji ocen.
A wybiera zawsze ruch maksymalizujÄ…cy minimalnÄ… ocenÄ™
następnych pozycji (wierzchołków), Gdyby było to możliwe, to można by napisać program
perfekcyjnie grajÄ…cy w szachy.
B wybiera zawsze ruch minimalizujÄ…cy maksymalnÄ… ocenÄ™
następnych pozycji (wierzchołków).
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 17 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 18
3
Przykład propagacji ocen w drzewie gry
Nie zawsze trzeba przeszukiwać wszystkie poddrzewa
max
w celu wyznaczenia oceny wierzchołka:
74
41 max
min
0 74 10
41 x d" 26 min
d"
d"
d"
max
78 74 110 10
0 999 999 65
max
113 41 65 26 ?
min
71 74 15 0
78 0 0 110 56 10
max
74
999
999 71 999 106 15 142 0 87
poddrzewo nie wymagajÄ…ce przeszukania
5 74 0 28 999
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 19 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 20
Problemy dotyczÄ…ce reprezentacji wiedzy
w inteligentnych programach:
Heurystyczne metody przeszukiwania drzewa gry zawierajÄ…:
dane potrzebne dla inteligentnych programów składają się z
wielkich zbiorów faktów i złożonych związków pomiędzy nimi,
heurystyczne algorytmy wyznaczania ocen wierzchołków
związki pomiędzy faktami maja różne aspekty i własności,
(stosuje się np. funkcje oceny o wielu parametrach, których
które tworzą sieci powiązań wyższego rzędu niż sama struktura
wartości dobiera się heurystycznie i często mogą być one
danych,
różne na różnych poziomach drzewa),
wciąż niewiele wiadomo o tym, w jaki sposób umysł ludzki
heurystyczne reguły określające jak głęboko od pozycji
magazynuje i wykorzystuje wiedzę nabywaną w ciągu całego
bieżącej będzie sięgało przeglądanie poddrzew,
życia,
efektywne procedury propagacji ocen, które pozwalają
zaproponowano wiele modeli wiedzy, ale wszystkie one majÄ…
wykluczyć wiele poddrzew i zapewniają wyznaczenie w
ograniczony zakres stosowania i nie ma wśród nich żadnego
rozsądnym czasie wartości stanowiącej podstawę wyboru
prawdziwie uniwersalnego i w pełni operacyjnego,
kolejnego ruchu.
opracowano języki programowania zawierające operacje
pozwalajÄ…ce na manipulowanie wiedzÄ… np. Lisp i Prolog.
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 21 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 22
Systemy ekspertowe (doradcze) sÄ… specyficznÄ… odmianÄ…
Programy uczące się (uczenie maszynowe) są próbą
inteligentnych programów przeznaczoną zwykle do
naśladowania procesów zdobywania wiedzy przez ludzi.
współpracy z człowiekiem-ekspertem lub decydentem,
Uczenie maszynowe znajduje zastosowanie:
rzadziej do jego zastÄ…pienia.
przy rozwiązywaniu problemów, dla których ze względu
ZnajdujÄ… zastosowanie np. w:
na ich złożoność niemożliwe jest podanie gotowego programu
diagnostyce medycznej,
rozwiÄ…zujÄ…cego dany problem w rozsÄ…dnym czasie,
wojskowych systemach dowodzenia (podobno)
przy poszukiwaniu zależności w dużych zbiorach
w złożonych systemach zarządzania przedsiębiorstwami.
nieprzetworzonych danych (tzw. drążenie danych),
przy tworzeniu inteligentnych autonomicznych systemów,
Podstawowe moduły składające się na system ekspertowy to:
umiejących dostosowywać się do zmian w środowisku (roboty).
baza danych (zbiór faktów),
Kluczowym zagadnieniem w uczeniu maszynowym
baza wiedzy (zbiór reguł wnioskowania),
jest reprezentacja zdobywanej wiedzy.
maszyna wnioskujÄ…ca (sterowanie i manipulowanie wiedzÄ…).
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 23 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 24
4
Rozumienie języka naturalnego jest jak dotąd zagadnieniem Interpretacja semantyczna:
bardzo trudnym do rozwiÄ…zania przy budowie inteligentnego
 usiadł przy stole i zobaczył przed sobą wielką porcję
systemu komputerowego.
sałatki na talerzu obok kosza z pieczywem. Zajęło mu Co  on
to trochę czasu, ale w końcu zdołał zjeść wszystko. zjadł?
Na maszynowe rozumienie języka naturalnego składa się m.innymi:
 Jan wyrzuci śmieci za karę
rozpoznawanie mowy ludzkiej (np. wydzielenie słów),
 Jan wyrzuci śmieci za chałupę
interpretacja semantyczna (znaczeniowa) wypowiedzi, Jak rozróżniać
 Jan wyrzuci śmieci za godzinę przyczynę, miejsce i czas?
uchwycenie związków międzywyrazowych (kontekstu).
Związki międzywyrazowe:
Rozpoznawanie mowy:
 dzieci ukradły monety, po czym niektóre z nich sprzedano
umyj głowę i ręce H" umyj głowę Irence
 dzieci ukradły monety, po czym niektóre z nich złapano
Piotr chodzi z AniÄ… H" Piotr chodzi za niÄ…
Jakie słowa zostały
 dzieci ukradły monety, po czym niektóre z nich znaleziono
wypowiedziane?
mama ma nastroje H" mama ma nas troje
Które wyrazy tworzą związek?
Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 25 Jarosław Sikorski - WST
P DO INFORMATYKI, WSISiZ 2004 r. 26
5