Wstep do AI

1. Wprowadzenie do AI

Witold Kosiński

[e-mail]

Podejmowanie decyzji

• Zagadnienia określane wspólną

nazwą „sztuczna inteligencja” (AI),
np.:

• sterowanie urządzeniami i pojazdami

• podejmowanie decyzji gospodarczych

i finansowych

• diagnozy medyczne

• rozumienie języka naturalnego (np.

tłumaczenia)

• analiza obrazu i dźwięku

ZAGADNIENIA AI

• Stworzenie maszyn o

inteligencji dorównującej
(przewyższającej) ludzką.

• Stworzenie maszyn

(algorytmów) przejawiających
tylko wąski aspekt inteligencji
(grających w szachy,
rozpoznających obrazy, czy
tworzących streszczenia tekstu).

Pewne definicje inteligencji z

1921, Journal of Educational

Psychology

• “

The ability to carry on abstract

thinking” (L. M. Terman)

•

“Having learned or ability to learn to
adjust oneself to the environment” (S.
S. Colvin)

•

“The ability to adapt oneself adequately
to relatively new situations in life” (R.
Pintner)

•

“A biological mechanism by which the
effects of a complexity of stimuli are
brought together and given a somewhat
unified effect in behavior” (J. Peterson)

•

“The capacity to acquire capacity” (W.
Woodrow)

•

“The capacity to learn or to profit by
experience”
(W. F. Dearborn)

SZTUCZNA INTELIGENCJA

(ARTIFICIAL INTELLIGENCE)

• Nauka o maszynach realizujących

zadania, które wymagają
inteligencji wówczas, gdy są
wykonywane przez człowieka.

Wiele różnych, często sprzecznych definicji.

SZTUCZNA INTELIGENCJA

(ARTIFICIAL INTELLIGENCE)

• Maszyna jest

inteligentna, jeżeli
znajdujący się w
drugim pomieszczeniu
obserwator nie zdoła
odróżnić jej
odpowiedzi od
odpowiedzi człowieka.

Test Turinga

SZTUCZNA INTELIGENCJA

(ARTIFICIAL INTELLIGENCE)

• Nauka o tym, w jakich inteligentnych

czynnościach człowieka można obyć
się bez inteligencji.

• Dział informatyki, którego

przedmiotem jest badanie reguł
rządzących inteligentnymi
zachowaniami człowieka, tworzenie
modeli formalnych tych zachowań i -
w rezultacie - programów
komputerowych symulujących te
zachowania.

SZTUCZNA INTELIGENCJA

A INTELIGENCJA OBLICZENIOWA

Dział informatyki zajmujący

się problemami:

• trudnymi do modelowania

i rozwiązywania w
sposób ścisły, analityczny,

• niealgorytmizowalnymi,

• obliczalnymi, ale

nieefektywnie,

•

algorytmizowalne, ale

wymagają użycia innych
niż klasyczne metod .

INTELIGENCJA OBLICZENIOWA

Metody rozwiązywania takich trudnych

problemów dostarcza rozwijany przez
matematyków i informatyków nowy
kierunek badań zwany

inteligencją

obliczeniową

. Jej rozwój datuje się od lat

60-tych ubiegłego wieku.

•

1.Adaptacja

•

2.Korzystanie z doświadczenia

•

3.Korzystanie z wiedzy

•

4.Wyciąganie wniosk

ó

w

•

5.Abstrakcyjne myślenie

•

6.Poczucie humoru

•

7.Samoświadomość

•

8. Zdolność planowania

•

9.Zdolność przewidywania

•

10. Selekcja informacji

•

11.Zdolność komunikacji

•

12.Uczenie się

•

13.Dokonywanie wyboru

Może być ciekawe wybrać te własności, które są wspólne z inteligencją

maszynową - sztuczną.

Własno

ś

ci charakteryzuj

ą

ce inteligencj

ę

ludzk

ą

Test IQ

Wstawić następny z zestawu A -F

HISTORIA AI - SZACHY

• ok. 1948 – pierwsze programy szachowe
• 1951 – A. Turing:

Nikt nie jest w stanie ułożyć

programu lepszego od własnego poziomu gry

.

• 1967 – pierwsze zwycięstwo komputera nad

„profesjonalnym” szachistą podczas turnieju

• 1977 – pierwsze zwycięstwo nad mistrzem klasy

międzynarodowej (jedna partia w symultanie)

• 1997 – Deep Blue wygrywa pełny mecz z

Kasparowem

(specjalny superkomputer 418-procesorowy;

wynik 3,5:2,5)

• 2003 – Deep Junior remisuje z Kasparowem mecz na

warunkach przez niego określonych

(8 zwykłych

procesorów Intela 1,6 GHz; wynik 3:3)

CO OKAZAŁO SIĘ TRUDNE,

A CO ŁATWE

Łatwe: zadania, do których wystarcza
moc obliczeniowa (proste gry, np.
warcaby) lub zapamiętanie wielu
przykładów.

Trudne: np. analiza języka naturalnego,
bardziej skomplikowane gry (go), analiza
obrazu.

Wykorzystywane techniki

i modele

• Sieci neuronowe
• Wnioskowanie, indukcja reguł
• Algorytmy ewolucyjne
• Systemy wieloagentowe

(współpraca )

• Automaty komórkowe
• Metody przeszukiwania

możliwych rozwiązań i ich
optymalizacji...

CO OKAZAŁO SIĘ TRUDNE,

A CO ŁATWE

1961

Przykład zagadnienia

praktycznego

• Znaleźć, odczytać i

zapamiętać numer
rejestracyjny
samochodu na
podstawie zdjęcia:

logoUKW .gif.lnk

Odczytywanie tablic

rejestracyjnych (1)

Oryginalne zdjęcie

Usunięcie zbędnych szczegółów

Lokalizacja napisów

Odczytywanie tablic

rejestracyjnych (2)

Wyselekcjonowany obszar

Lokalizacja znaków

Rozpoznawanie znaków:
- znajdowanie istotnych cech
liczbowych
- klasyfikacja na podstawie
cech (systemy uczące się)

>

classifier

< Marks

>

classifier

< not

Marks

>

classifier

< not

Marks

>

classifier

< not

Marks

>

classifier

< Marks

>

classifier

< not

Marks

Rozpoznawanie twarzy

(nauka)

Rozpoznawanie twarzy

> Classifier >

Marks

UWAGA: TEN OBRAZ

NIE NALEŻAŁ DO PRÓBKI

TRENINGOWEJ!!!

Narzędzia AI

• ANN- artificial neural networks

• Genetic and evolutionary algorithms

(genetic=binary chromosomes)

• Fuzzy logic, fuzzy sets, fuzzy controllers

• Decision trees (drzewa decyzyjne)

• Celullar automata (automaty komórkowe)

• Rough sets (zbiory przybliżone), Pawlak’s sets

Tools of AI, cont.

• Wymienione narzędzia mogą się znaleźć

jako elementy większych systemów
informacyjnych (tzw. Inteligentnych
systemów informacyjnych) zwanych
systemami doradczymi czy systemami
eksperckim (ekspertowymi)

decision-supporting systems

LITERATURA

1.

Rutkowski L., Metody i techniki sztucznej inteligencji, Wydawnictwo
Naukowe PWN Warszawa 2005.

2.

Rutkowska D., Piliński M. i Rutkowski L., Sieci neuronowe,
algorytmy genetyczne i systemy rozmyte, PWN, Warszawa 1997.

3.

Piegat A., Modelowanie i sterowanie rozmyte. Akademicka Oficyna

Wydawnicza EXIT Warszawa 1999.

4.

Tadeusiewicz R., , Elementarne wprowadzenie do techniki sieci
neuronowych z przykładowymi programami, Akademicka Oficyna
Wydawnicza PLJ Warszawa 1998.

5.

Michalewicz Michalewicz, Algorytmy genetyczne + struktury danych
= programy ewolucyjne, Wydawnictwa Naukowo-Techniczne, 1996

6.

Korbicz J., Obuchowski A., Uciński D., Sztuczne sieci neuronowe.

Podstawy i zastosowania. Akademicka Oficyna Wydawnicza PLJ,
Warszawa, 1994.

7.

Osowski Stanisław, Sieci neuronowe w ujęciu algorytmicznym,
Wydawnictwa Naukowo-Techniczne, Warszawa, 1996

8.

Ż

urada Jacek, Barski Mariusz , Jędruch Wojciech, Sztuczne sieci

neuronowe, Wydawnictwo Naukowe PWN, Warszawa, 1996.

PROGRAM WYKŁADU

•

Sieci neuronowe: przegląd struktur oraz zastosowań, metody
uczenia, propagacja wsteczna błędu

•

Logika rozmyta i liczby rozmyte

•

Problemy optymalizacji i przeszukiwania, klasyfikacja danych

•

Algorytmy genetyczne: operatory, zastosowania do
optymalizacji

•

Automaty i systemy komórkowe i mrówkowe

•

Metody hybrydowe

KRYTERIA ZALICZANIA

• Ćwiczenia:

– Punkty z rozwiązanych zadań/ ew.colloquia.
– Co najmniej jeden projekt programistyczny
– Inne, ustalone przez prowadzących zajęcia

• Wykład:

– Dwa colloquia (nieobowiązkowe)
– Egzamin pisemny, jeden termin poprawkowy,

trzeba mieć wcześniej zaliczone ćwiczenia

– Ocena co najmniej na 4.0 z ćwiczeń i zaliczone w

punktach colloquia na wykładzie zwalniają z
egzaminu (można mieć zaproponowaną
ocenę)

– Brak możliwości „warunkowego” pisania egz.

Sztuczne sieci neuronowe

Geneza: Naśladowanie działania naturalnych neuronów
Cel historyczny: osiągnięcie zdolności uogólniania (aproksymacji)
i uczenia się, właściwej mózgowi ludzkiemu.

• Wejście

– n stanów wejściowych x

1

,...,x

n

– stany mogą być cyfrowe lub analogowe

• Wyjście

– 0 lub 1

• Parametry perceptronu

– n wag połączeń w

1

,...,w

n

∈ℜ

– wartość progowa

θ∈ℜ

Perceptron (Rosenblatt 1958)

Uwaga: pod pojęciem “perceptronu” rozumie się też czasem
sieć połączonych jednostek (neuronów).

Perceptron

s

w x

i

i

i

n

=

=

∑

1

• Zasada działania

– Do każdego i-tego wejścia przypisana jest

waga w

i

– Dla danych stanów wejściowych x

1

,...,x

n

liczymy sumę ważoną:

– Jeżeli s

≥θ

, to ustawiamy wyjście y = 1, zaś

w przeciwnym przypadku ustawiamy y = 0

Analogia z neuronem naturalnym







≥

↔

=

∑

.

.

0

1

p

p

w

x

w

y

i

i

θ

w

1

x

1

x

2

x

n

y

w

2

w

n

Jak opisa

ć

perceptron

• Perceptron opisuje jednoznacznie zbiór

wag w

1

,...,w

n

∈ℜ

oraz wartość progowa

θ ∈ℜ

• Wartości x

1

,...,x

n

∈ℜ

to zmienne

pojawiające się na wejściu do modelu
perceptronu

• Funkcja aktywacji:







≥

↔

=

∑

otherwise

x

w

y

i

i

θ

0

1

θ

= 2

1

1

x

1

AND

x

2

x

2

x

1

1

0

0

0

x

1

∧∧∧∧

x

2

0

1

1

0

1

1

0

0

x

2

x

1

θ

= 1

1

1

x

1

OR

x

2

x

2

x

1

1

1

1

0

x

1

∨∨∨∨

x

2

0

1

1

0

1

1

0

0

x

2

x

1

Co potrafi perceptron

Co potrafi perceptron

w

1

x

1

+

w

2

x

2

-

θ

=

0

θ

≥

+

2

2

1

1

x

w

x

w

x

1

x

2

y=1

• Równanie perceptronu

można potraktować jako
równanie prostej (ogólnie:
hiperpłaszczyzny w
przestrzeni n-wymiarowej).

• Punkty leżące nad ową

prostą klasyfikujemy jako 1,
zaś pozostałe jako 0.

AND

OR

XOR

Czego perceptron nie potrafi

• Pojedynczy perceptron nie

potrafi odróżniać zbiorów
nieseparowalnych liniowo,
np. funkcji XOR.

• Odkrycie tych ograniczeń

(1969) na wiele lat
zahamowało rozwój sieci
neuronowych.

Zadanie perceptronu

• Zadaniem pojedynczego perceptronu jest

jedynie:

– przetwarzanie jednostkowych informacji
– podejmowanie prostych decyzji
– przekazywanie wyników sąsiadom

• Dopiero w połączeniu z innymi węzłami

uzyskuje się zdolność podejmowania
złożonych decyzji