brmiversity: Um lá inteligence a teoretická informatika

Neuronové sít¥

Um¥lá inteligence

Základní algoritmy

Sloºitost

Vy£íslitelnost

brmiversity: Um¥lá inteligence a teoretická informatika P°edná²ka £. 4

Petr Baudi²

[email protected]

brmlab 2011

Petr Baudi² [email protected]

brmiversity: Um¥lá inteligence a teoretická informatika

Neuronové sít¥

Outline

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

1 Neuronové sít¥ 2 Um¥lá inteligence 3 Základní algoritmy 4 Sloºitost 5 Vy£íslitelnost



Neuronové sít¥

Um¥lá inteligence

Um¥lá neuronová sí´


Sloºitost

Vy£íslitelnost

Hidden

•

Um¥lé neurony (výpo£etní krabi£ky)

Input Output

dostávají vstupy (£ísla) a na jejich základ¥ generují výstup (£íslo)

•

Obvykle: Vrstvy striktn¥ odd¥lené, vstupní vrstva se vstupy zvn¥j²ku, výstupní vrstva s výstupem pro uºivatele, skryté vrstvy vyhodnocují r·zné charakteristiky vstup·

•

Dnes: Jediný um¥lý neuron



Neuronové sít¥

Perceptron X1 X2 X3 X4 X5 X6 X7

W1 W2 W3 W4 W5 W6 W7

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

•

n vstup· a práh ⇐ výstup

•

Lineární kombinace vstupy mají r·zné váhy,

f

y

vynásobíme, se£teme a otestujeme

•

Výstup je 1/0 nebo n¥co sloºit¥j²ího



Neuronové sít¥

Perceptron X1 X2 X3 X4 X5 X6 X7

W1 W2 W3 W4 W5 W6 W7

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

•

n vstup· a práh ⇐ výstup

•

Lineární kombinace vstupy mají r·zné váhy,

f

y

vynásobíme, se£teme a otestujeme

•

Výstup je 1/0 nebo n¥co sloºit¥j²ího

~x ,

w~ , práh b

•

Vstup

•

P

•

Zjednodu²ení virtuální vstup pro

n i

=0

váhový vektor

w ·x i

i

>b

práh



Neuronové sít¥

Um¥lá inteligence

Geometrická interpretace


Sloºitost

Vy£íslitelnost

http://www.mblondel.org/journal/ 2010/10/31/kernel-perceptron-in-python/

Non-free artwork. See



Neuronové sít¥

Um¥lá inteligence

Co dokáºe perceptron?


•

Lze vzorky £ist¥ rozd¥lit podrovinou?

•

Lineární separabilita mnoºin

•

Omezení nap°. XOR pot°ebuje dv¥ £áry


Sloºitost

Vy£íslitelnost

Non-free artwork omitted. See

http://cs-alb-pc3. massey.ac.nz/notes/ 59318/l7.html


Neuronové sít¥

Um¥lá inteligence

U£ení perceptronu


•

Rota£ní algoritmus

•

Náhodná inicializace p°ímky

•

Iterujeme u£ení podle vstupních mnoºin:

• • •

Sloºitost

Vy£íslitelnost

Postupn¥ iterujeme body a klasikujeme Správná klasikace ned¥láme nic patná klasikace pooto£íme vektor, aby pojmul i nový bod

http://www.willamette.edu/ ~gorr/classes/cs449/Classification/perceptron.html

Non-free artwork omitted. See



Neuronové sít¥

Um¥lá inteligence


U£ení perceptronu •

Geometrické pozorování:

Sloºitost

Vy£íslitelnost

w~ · ~x > 0,

pak úhel mezi nimi je men²í neº 90 deg

•

Geometrické pozorování: Se£teme-li dva vektory, vyjde nám vektor mezi

• •

w0 = w 0 Výstup je 1 a m¥l být 0: w = w

Výstup je 0 a m¥l být 1:

i

i

+ x (t )

i

i

i

i

− x (t )

http://www.willamette.edu/ ~gorr/classes/cs449/Classification/perceptron.html Non-free artwork omitted. See



Neuronové sít¥

Otázky?

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

P°í²t¥: Vícevrstvé neuronové sít¥ a jejich u£ení (backpropagation).



Neuronové sít¥

Outline

Um¥lá inteligence


Sloºitost

Vy£íslitelnost




Neuronové sít¥

Filosoe

Um¥lá inteligence


•

Silná vs. slabá AI

•

AI-complete úlohy

•

Bude víc 23.11.

•

Dnes jeden p°íklad slabé AI (je AI-complete?)


Sloºitost

Vy£íslitelnost


Neuronové sít¥

Um¥lá inteligence

Matematické hry

•


Sloºitost

Vy£íslitelnost

Teorie her hrá£i se st°ídají v akcích, kaºdý dostane n¥jakou výplatu po dokon£ení sekvence akcí

•

Hry dvou hrá£· s úplnou informací a nulovým sou£tem



Neuronové sít¥

Um¥lá inteligence

Minimaxový strom • • •


Sloºitost

Vy£íslitelnost

Adversarial planning Tah je tak dobrý jako nejnep°íjemn¥j²í tah protihrá£e Omezení na hloubku stromu vyhodnocovací funkce



Neuronové sít¥

α, β

Um¥lá inteligence


pro°ezávání

Sloºitost

•

Základní urychlovací heuristika

•

Pamatujeme si nejhor²í a nejlep²í hodnoty z minimaxových

Vy£íslitelnost

soused·, za°ízneme prohledávání uzlu, je-li jasné, ºe bude hor²í (max,

•

α)

nebo lep²í (min,

β)

Pro efektivitu je d·leºité po°adí vyhodnocování tah· 6

3

5 5 5

6

6

6

3 4

7

4

MAX

5

3

6

3

6


6

7

5

MIN

5

8

MAX

6

7

5

8

6

9

7

5

9

8

MIN

6

MAX


Neuronové sít¥

Um¥lá inteligence

Dal²í vylep²ení


Sloºitost

•

Transpozi£ní tabulky

•

Pro°ezávání, singular extensions, atd.

•

Problémy dobrá funkce, v¥tvící faktor, efekt horizontu


Vy£íslitelnost


Neuronové sít¥

Um¥lá inteligence

Monte Carlo Tree Search


•

Technika Monte Carlo

•

Minimaxový strom s o£ekáváními

•

Multi-armed bandit

Sloºitost

Vy£íslitelnost

Non-free artwork.



Neuronové sít¥

Otázky?

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

P°í²t¥: Prohledávání v grafech.



Neuronové sít¥

Outline

Um¥lá inteligence


Sloºitost

Vy£íslitelnost




Neuronové sít¥

Um¥lá inteligence


Leven²teinova edita£ní vzdálenost

Sloºitost

•

Dva stringy; editace jsou p°idání, zm¥na, odebrání

•

Dynamický algoritmus:


Vy£íslitelnost


Neuronové sít¥

Um¥lá inteligence

Dal²í zp·soby porovnávání

•


Sloºitost

Vy£íslitelnost

Myers·v algoritmus (nejdel²í spole£ná podposloupnost neboli edita£ní skript; jen

+

a

−)

•

bdi (nejdel²í spole£ný pod°et¥zec rekurzivn¥)

•

xdelta (rsync; Rabinovo hashování)



Neuronové sít¥

Outline

Um¥lá inteligence


Sloºitost

Vy£íslitelnost




Neuronové sít¥

Um¥lá inteligence

Metody tvorby algoritm·


Sloºitost

Vy£íslitelnost

•

Kucha°ka pro efektivní algoritmy na obecné t°ídy problém·

•

Rozd¥l a panuj problém rozd¥líme na podproblémy a ty po£ítáme rekurzivn¥

•

Hladový algoritmus problém budujeme inkrementáln¥, v kaºdé chvíli víme, kudy dál

•

Dynamický algoritmus problém budujeme inkrementáln¥, sdílíme výsledky jednodu²²ích podproblém·



Neuronové sít¥

Um¥lá inteligence

Rozd¥l a panuj p°íklad •


Sloºitost

Vy£íslitelnost

Binární vyhledávání: 1 3 9 10 12 13 17 19 24 26 27 30 31

•

Quicksort

•

Asymptotická sloºitost Master Theorem (matematika viz Wikipedie)



Neuronové sít¥

Um¥lá inteligence



Sloºitost

Vy£íslitelnost


•

Quicksort

•




Neuronové sít¥

Um¥lá inteligence



Sloºitost

Vy£íslitelnost


•

Quicksort

•




Neuronové sít¥

Um¥lá inteligence



Sloºitost

Vy£íslitelnost


•

Quicksort

•




Neuronové sít¥

Um¥lá inteligence



Sloºitost

Vy£íslitelnost


•

Quicksort

•




Neuronové sít¥

Um¥lá inteligence



Sloºitost

Vy£íslitelnost


•

Quicksort

•




Neuronové sít¥

Um¥lá inteligence



Sloºitost

Vy£íslitelnost


•

Quicksort

•




Neuronové sít¥

Um¥lá inteligence


Hladový algoritmus p°íklad •

Minimální kostra (p°ipomenutí)

•

Rozvrhovací problém

•

Dijkstra


Sloºitost

Vy£íslitelnost


Neuronové sít¥

Um¥lá inteligence


Hladový algoritmus p°íklad

Sloºitost

Vy£íslitelnost

•

Minimální kostra (p°ipomenutí)

•

Rozvrhovací problém

•

Dijkstra

•

Hladový algoritmus lze pouºít, pokud problém vykazuje

•

Matematická abstrakce matroid

optimální podstrukturu E

je základní mnoºina,

I

M = (E , I ),

je systém nezávislých podmnoºin:

• ∅ ∈ I (prázdná mnoºina je nezávislá) • A ∈ I , A0 ⊂ A ⇒ A0 ∈ I ∀A, A0 (d¥di£nost) • A ∈ I ∧ B ∈ I ∧ |A| > |B | ⇒ ∃ x ∈ A, B ∪ x ∈


I


Neuronové sít¥

Um¥lá inteligence

Dynamický algoritmus


Sloºitost

•

Edita£ní vzdálenost

•

Fibonacciho posloupnost

•

Dijkstra

•

Optimální podstruktura a p°ekrývající se podproblémy


Vy£íslitelnost


Neuronové sít¥

T°íd¥ní

Um¥lá inteligence


Sloºitost

O (n · log n)

•

Jak dlouho trvá t°íd¥ní? Spodní odhad je

•

Vyhledávací strom modeluje rozhodovací strom algoritmu

•

Nebo ano? Radix sort, ale je to podvod!


Vy£íslitelnost


Neuronové sít¥

Otázky?

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

P°í²t¥: Pravd¥podobnostní algoritmy.



Neuronové sít¥

Outline

Um¥lá inteligence


Sloºitost

Vy£íslitelnost




Neuronové sít¥

Rekapitulace •

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

Rekapitulace: Nezajímá nás, jak rychle to pob¥ºí, ale jestli to n¥kdy dob¥hne.

moºnosti algoritm·.

•

Zkoumáme výpo£etní

•

Minule jsme p°emý²leli, £ím v²ím lze algoritmy vykonávat (a ºe je to ekvivalentní).

•

Zapomn¥li jsme (mj.) na celulární automaty!



Neuronové sít¥

Um¥lá inteligence

Halting Problem •

Máme program


z = x (y ); x , y , z

Sloºitost

Vy£íslitelnost

jsou £ísla

(kód, parametr / vstup, návratová hodnota / výstup)

•

Program dob¥hne (v kone£ném £ase) a vrátí hodnotu

°e²í problém), nebo se zacyklí

(



Neuronové sít¥

Um¥lá inteligence

Halting Problem •

Máme program


z = x (y ); x , y , z

Sloºitost

Vy£íslitelnost

jsou £ísla

(kód, parametr / vstup, návratová hodnota / výstup)

•

Program dob¥hne (v kone£ném £ase) a vrátí hodnotu

°e²í problém), nebo se zacyklí

(

•

Nekone£ná smy£ka v závislosti na datech, schovaná uprost°ed sloºitého kódu

x

y?

•

Halting Problem: Zacyklí se program

•

Dokáºeme napsat program, který °e²í halting problem?


na vstupu


Neuronové sít¥

Um¥lá inteligence

Halting Problem: D·kaz


Sloºitost

•

D·kaz sporem dejme tomu, ºe máme funkci

•

Ukáºeme, ºe existence takové funkce zp·sobuje

c (FUNKCE )) a y

je kód programu (

Vy£íslitelnost

HALT (x , y ), x

je vstup

logické trhliny v £asoprostoru



Neuronové sít¥

Um¥lá inteligence



Sloºitost

•


•


c (FUNKCE )) a y

je kód programu (

Vy£íslitelnost

HALT (x , y ), x

je vstup


•

Trik: Nadenujme si funkci

PODRAZ (x ) ↓ • • •

⇐⇒

HALT (x , x ) = NE

PODRAZ (x ) zavolá funkci HALT (x , x ) Pokud by se program x na vstupu x (kód sama sebe) zastavil, PODRAZ (x ) se zacyklí Pokud by se program x na vstupu x (kód sama sebe) zacyklil, PODRAZ (x ) dob¥hne Tedy



Neuronové sít¥

Um¥lá inteligence



Sloºitost

•


•


c (FUNKCE )) a y

je kód programu (

Vy£íslitelnost

HALT (x , y ), x

je vstup


•

Trik: Nadenujme si funkci

PODRAZ (x ) ↓ • • •

• •

•

⇐⇒

HALT (x , x ) = NE

PODRAZ (x ) zavolá funkci HALT (x , x ) Pokud by se program x na vstupu x (kód sama sebe) zastavil, PODRAZ (x ) se zacyklí Pokud by se program x na vstupu x (kód sama sebe) zacyklil, PODRAZ (x ) dob¥hne Tedy

PODRAZ (c (PODRAZ ))! HALT (c (PODRAZ ), c (PODRAZ )) = ANO PODRAZ (c (PODRAZ )) ↓ ⇐⇒ HALT (c (PODRAZ ), c (PODRAZ )) = NE To je spor, ANO 6= NE . Zavolejme


⇐⇒


Neuronové sít¥

Otázky?

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

P°í²t¥: Rekurzivní a rekurzivn¥ spo£etné mnoºiny.



Neuronové sít¥

D¥kuji vám

Um¥lá inteligence


Sloºitost

Vy£íslitelnost

[email protected]

P°í²t¥: Nebude.

Pop°í²t¥: Prohledávání graf· a hledání cesty (základní algoritmy, um¥lá inteligence, adaptivní agenti), neuronové sít¥, vy£íslitelnost.



brmiversity: Um lá inteligence a teoretická informatika

Recommend Documents