brmiversity: Umělá inteligence a teoretická informatika

brmiversity: Umělá inteligence a teoretická informatika
organizer:	pasky
date/time:	každou středu od 20:00
place:	brmlab
stream:	stream

V rámci průběžné přípravy na státnice z teoretické informatiky na MFF UK se konaly každý týden v brmlabu přehledové přednášky na různá témata týkající se umělé inteligence a počítačové vědy. Některá témata byla zajímavá i pro neprogramátory, jiná byla stravitelná pro většinu programátorů, a některá byla vysoce teoretická a byl jsem spíše překvapen, když mi na ně někdo přišel.

Cyklus je u konce, níže jsou k dispozici slajdy a záznamy. Sem tam se mi do výkladu vloudila chyba a není v mých silách ani opravovat všechny, o kterých vím, v případě pochybností si vše ověřte. Napište mi mail, nejste-li si jistí nebo si myslíte, že je chyba tak velká, že za opravu stojí.

V těchto přednáškách bude mít stejnou prioritu, abych vám vysvětlil základy a abych se sám pořádně naučil i detaily. Proto přednášky asi budou kromě úvodu do problematiky obsahovat i poměrně technické pasáže. Je spíše očekávané, že se někteří občas ztratí; matematická smršť pak snad vždy opět brzy utichne, nebo bude seštosovaná na konci, aby mohli předčasně odejít či se vrátit k notebookům. A možná těch technických pasáží nakonec ani tolik nebude.

P.S.: Nebudou to přednášky, které říká expert na problematiku. Tedy se v nich s nějakou (snad malou) pravděpodobností můžou objevit i bludy a nemusím být schopen odpovědět na všechny doplňující otázky.

Pro zájemce o umělou inteligenci doporučuji také http://www.ai-class.com/

Záznam přednášek: https://mirror.vpsfree.cz/videohrach/video/brm/brmiversity/, http://nat.brmlab.cz/talks/brmiversity/

Zdrojáky slajdů: http://github.com/pasky/aics-lec

Předběžný termín je každou středu od 20:00. Termín se ještě může měnit, přijímám i návrhy od potenciálních pravidelných návštěvníků. Očekávaná střední délka přednášky bude 75 minut, začne tím “zajímavějším” a skončí spíše teoretičtěji. Úvodní přednáška se uskuteční pouze v případě zájmu. Témata jsou fixní, jejich uspořádání je otevřené připomínkám a nápadům.

12.10. aics-lec1.pdf

Úvod - o čem to celé je?

• Umělá inteligence
• Neuronové sítě
• Adaptivní agenti a evoluční algoritmy
• Vyčíslitelnost (matematická vyjádření programů a neřešitelné problémy)
• Algoritmická složitost (jak dlouho trvá spočítat řešitelné problémy)
• (Základy) Základní algoritmy a datové struktury
  • Pole, spojáky, grafy a stromy (a jejich reprezentace)
  • Jak vyrobit abecední telefonní seznam?

19.10. aics-lec2.pdf

• (Neuronové sítě) Úvod do neurofyziologie.
  • Jak vypadá mozek? Jak fungují neurony, z čeho jsou poskládané a jak jsou propojené?
• (Základy) Další hrstka základních algoritmů
  • Jak najít v textu slovo?
  • Jak najít nejkratší cestu Prahou nebo navrhnout elektrorozvodnou síť?
• (Vyčíslitelnost) Algoritmicky vyčíslitelné funkce.
  • Turingův stroj, lambda kalkulus, rekurzivní funkce, brainfuck… «««<++++++
• (Složitost) Úvod do tříd složitosti; P, NP, PSPACE, polynomiální hierarchie.
  • Proč jsou některé problémy mnohem těžší než jiné, a co je to “mnohem”?
  • Co dělá v Turingově stroji součástka “orákulum” a dá se koupit v GME?
  • Proč si všichni dělají legraci z P=NP?
  • Turingův stroj má sice nekonečnou pásku, ale co se na ní vejde?

26.10. aics-lec3.pdf

• (Adaptivní agenti) Architektura autonomního agenta. Příklady systémů vyvíjených na MFF UK.
  • Co mají společného teenageři v kině, vojáci v Unreal Tournamentu a myši? (A quadcoptery?)
• (Evoluční algoritmy) Umělá evoluce. Základní genetický algoritmus.
  • Když jsme líní programovat a raději chceme nechat počítač, ať to vymyslí sám…
  • …podobně jako přírodní výběr nás.
• (Datové struktury) Haldy.
  • Kompostování dat. Jak skladovat čísla, abychom vždycky věděli, které z nich je nejmenší?
  • Regulární, levicové, binomiální a Fibonacciho. (XXX: dělali jsme zatím pouze regulární)
• (Složitost) Úplné problémy.
  • Jak si zabalit batoh a simulovat tím Turingův stroj? Chcete efektivně objet okolní hackerspacy? A jak objížděním zároveň řešit závislosti mezi balíčky?
  • Jak těžké je hrát Go nebo hru na hlavní města?

2.11. aics-lec4.pdf

• (Neuronové sítě) Umělé neuronové sítě, perceptron a jeho učení.
  • Umělé neurony a co jeden takový dokáže.
• (Umělá inteligence) Hry a herní stromy.
• (Základní algoritmy) Editační vzdálenost.
• (Složitost) Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus. Dolní odhad pro uspořádání.
  • Pár populárních algoritmických technik a jejich asymptotická složitost.
  • Rozděl a panuj: Proč řešit tak složitý problém, když můžeme vyřešit dva snazší problémy? QuickSort.
  • Dynamické programování: Chcete na každé zastávce tramvaje vědět, jak se rychle dostat na jakoukoliv jinou? Nebo rychle najít rozdíly ve dvou větách?
  • Hladový algoritmus: Co je to matroid a jak ho krmit.
  • Proč nikdy nedokážeme třídit rychleji. Anebo dokážeme?
• (Vyčíslitelnost) Halting problem s důkazem.

9.11. Meditace uma-šjú.

16.11. aics-lec5.pdf

• (Základní algoritmy) Prohledávání v grafech. BFS, DFS, Dijkstra.
• (Umělá inteligence) Prohledávání v grafech.
  • Jak naplánovat cestu robotovi nebo řešítku složitějšího problému?
• (Adaptivní agenti) Problém hledání cesty; navigační pravidla, reprezentace terénu.
  • Jak naplánovat cestu robotovi, tentokrát doopravdy.
• (Neuronové sítě) Vícevrstvé neuronové sítě, algoritmus zpětného šíření.
  • Umělý mozek, abychom mohli být líní programovat. Jak takový mozek něco naučit a kdo je to “učitel”.
  • A samozřejmě proč to funguje, parciální derivace included.
• (Vyčíslitelnost) Primitivně, obecně a částečně rekurzivní funkce. Kleenova věta.
  • Jak očíslovat všechny programy na světě a co je to “spočetné”?
  • Jak si poradit s funkcemi, které modifikují jiné funkce, a proč nám to přinese spoustu nepříjemností.
  • Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti.

23.11. Unlecture

Volná témata, volnější diskuse okolo AI. Filosoficky o umělé inteligenci - silná vs. slabá umělá inteligence, emergentní, symbolické a statistické přístupy, historie a nejnovější pokroky v AI.

pondeli 28.11. 18:00 mimoradna zmena terminu aics-lec6.pdf (přesun kvůli konfliktu s finálem Kinect challenge!)

• (Základy) Úvod do pravděpodobnosti. Nezávislá a podmíněná pravděpodobnost, trocha základní matematiky.
• (Umělá inteligence) Zpracování neurčité informace: Bayesovské sítě, rozhodovací grafy.
• (Složitost) Pravděpodobnostní algoritmy.
• (Datové struktury) Dodělávka hald. Hashování. Trocha matematiky kolem kolizí.
  • Když papáme drogy, najdeme každý prvek (skoro) hned, i když jich máme hodně.
  • Co znamená “skoro hned”?

7.12. aics-lec7.pdf

• (Umělá inteligence) Zpracování neurčité informace: Markovské modely, Kalmanův filtr.
  • Je pěkné umět naplánovat cestu robotovi, ale jak zjistíme, kde ten robot právě je - a jestli neprší?
  • No a samozřejmě - jak funguje Muaddib?
• (Neuronové sítě) Statistické zpracování dat, PCA.
• (Adaptivní agenti) Komunikace a znalosti v multiagentních systémech.
• (Datové struktury) Univerzální hashování, perfektní hashování.

14.12. aics-lec8.pdf

• (Adaptivní agenti) Metody pro řízení agentů.
• (Neuronové sítě) Vícevrstvé neuronové sítě - vylepšení algoritmu zpětného šíření, interní reprezentace znalostí.
• (Vyčíslitelnost) Věty o rekurzi a jejich aplikace.

21.12. aics-lec9.pdf

• (Umělá inteligence) Strojové učení I. (učení daty)
• (Neuronové sítě) Asociativní paměti, Hopfieldova síť.
• (Evoluční algoritmy) Reprezentační schémata. Evoluční a genetické programování.
• (Datové struktury) Binární vyhledávací stromy a jejich vyvažování.

28.12. aics-leca.pdf (nepřednášelo se, k reinforcement learningu se vrátíme později, ostatní témata na požádání)

• (Umělá inteligence) Strojové učení II. (učení zkušeností)
• (Adaptivní agenti) Metody pro učení agentů.
• (Datové struktury) Haldy.
• (Datové struktury) B-stromy a jejich varianty.

4.1. aics-lecb.pdf

• (Neuronové sítě) Samoorganizace - Kohonenovy mapy a příbuzné modely.
• (Adaptivní agenti) Etologie, modely populační dynamiky.
• (Evoluční algoritmy) Koevoluce, otevřená evoluce (BrmLife). Pravděpodobnostní model genetických algoritmů.

11.1. aics-lecc.pdf

• (Evoluční algoritmy) Aplikace evolučních algoritmů (řešení kombinatorických úloh, výběr akcí, expertní systémy, neuroevoluce).
• (Složitost) Technické důsledky tříd složitosti.
  • Třída PSPACE a její úplné problémy.
  • Míry složitosti, Savičova věta, konstruovatelné funkce.
  • Věty o zrychlení, mezerách, a hierarchii tříd složitosti.
• (Vyčíslitelnost) Algoritmicky nerozhodnutelné problémy.

18.1. aics-lecd.pdf

• (Umělá inteligence, Adaptivní agenti) Reprezentace znalostí a logické odvozování.
• (Složitost) Pseudopolynomiální algoritmy. Aproximační algoritmy a schémata.
• (Datové struktury) Mapování datových struktur do stránek vnější paměti počítače.

25.1. aics-lece.pdf

• (Umělá inteligence) Splňování omezujících podmínek a automatické plánování.
• (Datové struktury) Třídění ve vnitřní a vnější paměti.
• (Vyčíslitelnost) Gödelovy věty. (Pozor, důkaz je špatně! Správná verze viz wikiskripta z vyčíslitelnosti na matfyzácké wiki.)

1.2. aics-lecf.pdf Bylo pokryto slajdy pouze částečně, zbytek na tabuli.

• (Neuronové sítě) Modulární, hierarchické a hybridní modely neuronových sítí.
• (Umělá inteligence) Bayesovské sítě a Markovovské řetězce pořádně.

Jako návaznosti na tento cyklus v rámci MFF UK mohou sloužit Algoritmy a jejich implementace a Herní algoritmy, stejně jako samozřejmě řada jiných (obecně jsou přednášky na vysokých školách veřejné).

Benjamin Grosser

Interactive Robotic Painting Machine 2011 computers, robotics, camera, microphone, mixer, speakers, projector, oil paint, canvas

This machine uses artificial intelligence to paint its own body of work and to make its own decisions. While doing so, it listens to its environment and considers what it hears as input into the painting process. In the absence of someone or something else making sound in its presence, the machine, like many artists, listens to itself.

23998286 video