# Lekcia 1: Úvod do predmetu Umelá inteligencia - Pojmem "umelá inteligencia" - Je schopnosť strojov vykonávať úlohy, ktoré obvykle vyžadujú ľudskú inteligenciu, ako napr. rozprávanie reči, rozhodovanie a učenie sa z vlastných skúseností. - V podstate ide o systém, ktorý dokáže: 1. Analyzovať dáta 2. Usudzovať na základe tejto analýzy 3. Prispôsobiť sa novým situáciám v priebehu času - História a súčasnosť tohto odboru - [Šachový automat (Turek)](http://www.vystava.sav.sk/wp-content/uploads/%C5%A0achov%C3%BD-automat-W.-von-Kempelena.pdf) - Veda o UI existuje cca viac ako pol storočia. - Základné prúdy umelej inteligencie - Symbolický funkcionalizmus: 1. Reprezentácia problému a inteligentné prehľadávanie pristoru stavov, 2. Logika, 3. Vety prirodzeného jazyka. - Konekcionizmus: - Inteligencia vyplýva z prepojenia veľkého počtu jednoduchých výpočtových jednotiek. - Myšlienka (inšpirovaná mozgom), základná jednotka je model neurónu. - Hlavnou vetvou sú neuronové siete. - Skúma zdanlivo chaotické prepojenia. - Robotický funkcionalizmus: - Koncentruje na funkcionalitu modelovaného systému. - Inteligentným správaním je interakcia medzi entitami: _systém_, _prostredie_, _úloha_. - Turingov test, problémy testu, jeho modifikácie - Otázka testu: _"Môže stroj myslieť?"_ - _Mysliaci počítač_ je taký, ktorého chovanie nebudeme schopný rozoznať od človeka. - Test je imitačná hra (rozlíšenie 2 ľudí podľa pohlavia). - Test spočíva v tom, že imitátorom človeka by bol počítač. - Doteraz žiadnemu programu sa **nepodarilo** splniť. - Modifikácie: 1. Komunikácia medzi hráčmi: - Ľudský vyšetrovateľ komunikuje s dvoma hráčmi, _A_ a _B_. - Ak vyšetrovateľ nedokáže určiť, ktorý hráč je počítač a ktorý je človek, tak počítač zložil test. - Ak je počítač nerozoznateľný od človeka vo všeobecnom rozhovore o prirodzenom jazyku, musí sa dostať do inteligencie na úrovni človeka. 2. Simulácia iba jednej z mnohých schopností človeka (schopnosť jazyka v písanej forme). 3. Simulácia všetkých ľudských schopností (spĺňa iba pokročilý humanoidní robot). - Problémy: 1. Pôvodnosť - počítač nemyslí, pretože myslenie je spojené s pôvodnosťou. Z počítača však dostaneme iba modifikáciu toho, co doň vložíme. 2. Niekedy tieto testy môžu zisťovať to, _či počítač sa správa viac ako človek_, ako to, _či je inteligentný_. 3. Paradox čínskej izby - splnenie testu ešte nemusí znamenať myslenie a uvedomovanie si. 4. Dokonalosť - počítač môže byť odhalený práve tým, že nerobí chyby, počíta rýchlejšie. --- # Lekcia 2: Riešenie problémov - vyjadrenie problému - Vyjadrenie problému v AI (začiatočný stav, množina operátorov, stavový priestor, cieľový test, cena cesty) - Začiatočný stav - v ňom sa agent nachádza. - Množina operátorov - opisujú aký stav vznikne vykonaním akcie v danom stave. - Stavový priestor - množina všetkých dosiahnuteľných stavov zo začiatočného stavu ľubovoľnou postupnosťou akcií. - Cieľový test: - Testuje, či sa dosiahol cieľ. - Predstavuje hodnotenie nejakého stavu alebo hodnotenie cesty v stavovom priestore. - Môže byť daný: 1. _explicitne_ - ako množina stavov, 2. _implicitne_ - vlastnosťou stavu. - Cena cesty: - Súčet cien jednotlivých akcií na ceste. - Pri viacerých riešeniach daného problému, pomocou ceny cesty nájdeme riešenie, ktoré pozostáva z menšieho počtu alebo lacnejších akcií. - **cena riešenia** = **cena cesty k riešeniu** _+_ **cena hľadania** - Základné problémy pre algoritmy hľadania riešenia - Hľadanie riešenia je prístup, pri ktorom nevychádzame z algoritmu riešenia problému. Vychádzame z algoritmu ako riešenie hľadať. - Problém **nie** je algoritmicky riešiteľný pre neefektívnosť alebo preto, že algoritmus nepoznáme. - Neinformatívne hľadanie - prehľadávanie do šírky, stratégia rovnomernej ceny - Prehľadávanie do šírky: - Rozvinie sa koreňový uzol, potom všetky uzly vzniknuté jeho rozvitím, potom sa rozvijú všetky ich nasledovníci atď... - V strome hľadania sa expandujú všetky uzly v hĺbke `d` skôr ako sa rozvijú uzly v hĺbke `d + 1`. - Patrí medzi systematické stratégie. - Nevynechá ani jeden uzol. - Žiadny uzol sa nevyberie dvakrát. - Ak riešenie existuje, pri hľadaní sa **určite nájde**, t.j. stratégia je **úplná**. - Pri hľadaní sa nájde _najplytkejšie_ riešenie. - Stratégia rovnomernej ceny (_uniform - cost search_): - Na expanziu sa vyberie vždy uzol, ktorý je na najlacnejšej ceste. - Optimálne riešenie sa nájde vždy, ak sa pri postupe nezníži, napr. súčet cien aplikácie operátov a pod. - Obojsmerné hľadanie - Môže sa použiť iba keď máme problém, ktorého riešením je cesta a cieľový stav je známy. - Musí byť splnená podmienka existencie inverzných operátorov. - Stratégia: 1. Od počiatočného stavu bude hľadanie postupovať vpred smerom k cieľovému stavu (priame hľadanie), 2. Od cieľového stavu bude hľadanie postupovať vzad (inverzné operátory) smerom k počiatočnému stavu (spätné hľadanie), 3. Ak oba procesy vygenerujú ten istý stav, nájde sa cesta spájajúca počiatočný stav s cieľovým. - Problémy: 1. _Ak sa dajú definovať inverzné operátory, **nie** je ich výpočet zložitejší?_ 2. _Ako postupovať aj je viacej cieľových stavov?_ 2. Ak sú ciele dané implicitne, je ťažko nájsť predchodcov. - Prehľadávanie do hĺbky a jeho modifikácie - V strome hľadania sa najprv expanduje uzol, ktorého hĺbka je **najväčšia**. Keď sa narazí na uzol bez nasledovníkov, dôjde k navracaniu (_back tracking_), teda hľadanie sa vráti k expanzii uzlov na plytších úrovniach. - Často rýchlejší ako prehľadávanie do šírky. - Nezaručuje nájdenie riešenia (hlavne pri problémoch) - je **neúplná**. - Hľadanie sa nemusí orientovať smerom k optimálnemu riešeniu. - Modifikácie: - Ohraničené prehľadávanie do hĺbky: - Zamedzí, aby riešenie uviazlo hlboko v strome. - Stanoví sa hraničná hĺbka, do ktorej sa bude hľadať. - Cyklicky sa prehlbujúce hľadanie: - Postupne vyskúša všetky možné hraničné hĺbky - od najmenšej po najväčšiu. - Hľadanie do hĺbky s návratom: - Pri výbere uzla na skúmanie sa generuje iba jeden jeho nasledovník, ktorá ak nie je listový uzol sa ďalej skúma, inak sa vráti k najbližšiemu nerozvitému uzlu. - Šetrí pamäť a nevygeneruje uzly napravo od cesty. - Nemožno použiť žiadnu doplňujúcu informáciu na výber najlepšieho nasledovníka, lebo sa vždy vygeneruje iba jeden. --- # Lekcia 3: Heuristické prehľadávanie, Genetické algoritmy, Hry ako problém hľadania - Lačné hľadanie - Najlepší uzol je uzol s minimálnou odhadnutou cenou dosiahnutia cieľa. - Podobá sa hľadaniu do hĺbky. - Je **neúplné** a **neoptimalizované** riešenie. - Algoritmus A* - Stratégia rovnomernej ceny je **úplná** a **optimalizuje cestu**, keďže minimalizuje cenu cesty `g(u)` zo začiatočného uzla do uzla `u`. - Je _neefektívna_, keďže nevyužíva heuristickú informáciu o vzdialenosti k cieľu. - Najviac výhod zachováme, keď tieto stratégie skombinujeme do novej s heuristickou funkciou `f(u) = g(u) + h(u)`. - `f(u)` - odhad ceny najlacnejšej cesty vedúcej cez uzol `u`. - Je hľadanie najskôr najlepší s heuristickou funkciou `f(u)` a prípustnou heuristikou `h(u)`. - Nedostatkom je _exponenciálna_ časová a pamäťová zložitosť. - Heuristiky zmenšujúce priestor stavov - Heuristické informácie môžeme použiť aj na orezanie stavového priestoru a ten prehľadať jednoduchším (_slepým_) algoritmom. - Stavový priestor je možné zmenšiť tak, že heuristické informácie zahrnieme do podmienok aplikovateľnosti akcií (pravidiel). - Nasleduje stavový priestor (červené spojnice) orezaný pomocou heuristík z predchádzajúceho obrázku. - Napokon je uvedený strom hľadania generovaný z orezaného stavového priestoru prehľadávaním do šírky. - Genetické algoritmy - Vychádzajú z myšlienok Darwinovej teórie evolúcie. - Evolúcia k optimálnym riešeniam prebieha v mnohých generáciách celých populácií riešení pomocou prirodzeného výberu. - Neúspešné riešenia vymierajú, úspešné prežívajú a množia sa. - Hybnou silou evolúcie je _kríženie_ (výmena "genetickej" informácie medzi riešeniami) a mutácia. - Každý stav označujeme ako **chromozóm** - binárny reťazec `x` dĺžky `N`. - Pracujeme s populáciou `P` obsahujúcou `M` chromozómov. - Každému chromozómu x sa priradí hodnota funkcie úspešnosti fitnes `f(x)`. - Hľadáme globálne maximum fitnes. - Medzi chromozómami prebieha proces reprodukcie (nová populácia obsahujúca rovnaký počet chromozómov ako pôvodná populácia). - Časti reprodukcie: 1. Výber - do procesu reprodukcie vstupujú dvojice chromozómov. 2. Kríženie - vybrané chromozómy si vymenia rovnako dlhé podúseky svojich binárnych reťazcov. 3. Mutovanie - chromozómy sa podrobia mutácii (preklopia sa náhodne vybrané bity z ich reťazcov). - Prehľadávajú mnoho častí stavového priestoru daného problému. - Dajú sa použiť pre riešenie ťažko riešiteľných problémov. - Vždy poskytnú nejaké riešenie. - Nevýhody: - Nedajú vždy optimálne riešenie. - Potreba nastavenia množstva parametrov. - Herné problémy, algoritmus Min-Max - Herné problémy: - Jedná o hry s dvoma hráčmi (agent rieši úlohu z pohľadu jedného hráča), prítomnosť protihráča vnáša do problému. - Hľadanie má neurčitosť spôsobenú nedostatkom času. - Potrebuje zahrnúť čo najviac heuristických znalostí ako do generátora tak aj do testera. - Poskytujú dobre definovaný problém. - Jednoduché rozpoznanie úspechu resp. neúspechu. - Problém sa dá opísať pomerne jednoduchými pravidlami. - Algoritmus Min-Max: - Určuje najlepšiu stratégiu pre hráča _MAX_. - Vychádza z predpokladu, že súper vždy zahrá najhorší možný ťah pre _MAX_. - Postup: 1. Preskúma všetky stavy, vygeneruje celý strom hľadania až po koncové stavy. 2. Rozhodne sa, ktoré postavenie je najlepšie. 3. Vykoná sa ťah vedúci do najlepšieho postavenia. - Problémy: - Pri masívnych herných stromoch sa musí navšíviť veľa uzlov. - Predpokladá, že je dosť času prezrieť strom hľadania až k cieľovým uzlom (pre väčšinu hier nereálne). - Prezeranie je potrebné useknúť skôr než v cieľovom stave a listy následne vyhodnotiť nie pomocou bodovacej ale heuristickej vyhodnocovacej funkcie. --- # Lekcia 4: Znalosti - Znalosti - Expertný systém (_ES_): - Súbor počítačových programov a štruktúrovaných údajov, ktoré sú schopné nahradiť činnosť špecialistu v jeho obore (prípadne ho prekonať). - Simulujú rozhodovaciu činnosť experta pri riešení zložitých úloh a využívajúce vhodne zakódovaných, explicitne vyjadrených znalostí, prevzatých od experta, s cieľom dosahovať v zvolenej problémovej oblasti kvality rozhodovania na úrovni experta. - Prístupy založené na vytváraní systémov riešiace všeobecné problémy nie sú efektívne na riešenie ľubovoľne zložitých problémov. - Kvalita systému s UI závisí viacej od kvality znalostí ako na kvalite mechanizmu pre ich využívanie. - Vlastnosti znalostných systémov (_ES_) - Cieľom ES **nie** je čo _najvernejšie modelovať mentálne procesy pri rozhodovaní_, ale _dosiahnuť najlepšie odozvy na reálne dáta_. - ES sa výrazne líšia od "konvenčných" programov. - Reprezentácia znalosti (vyjadriteľnosť, použiteľnosť, začleniteľnosť) - Vyjadriteľnosť - vedieť pracovať s poznatkami zapísať ich. - Použiteľnosť - poznatky musia byť použiteľné. - Začleniteľnosť - poznatky _nie_ sú izolované entity, ale navzájom spolu súvisia, preto ich musíme vedieť začleniť do kontextu predchádzajúcich poznatkov. - Logika, výroková logika, predikátová logika - Logika: - Možnosť reprezentácie znalostí pomocou symbolov logiky. - Aristotelova logika vychádza z tzv. sylogizmov, ktorý ma dva predpoklady a jeden výrok. - Výroková logika: - Použitie sylogizmov nemusí pri inferencii stačiť, pretože pokryjú relatívne malé časti logických tvrdení. - Pre inferenčný mechanizmus ES je dôležitá. - Predikátová logika: - Ide o vnútornú štruktúru tvrdení. - Jazyk tejto logiky je tvorený: 1. premennými a konštantami, 2. predikátovými symbolmi, 3. funkčnými symbolmi, 4. logickými spojkami, 5. kvantifikátormi. - **Nie** je rozhodnuteľná (neplatnosť nemusí byť overená v konečnom počte krokov). - Pravidlá - Reprezentácia poznatkov pomocou pravidiel - _formalizmus_. - Často reprezentuje poznatky `if`-`then` pravidlami. - Skladá sa z: 1. predpokladovej alebo situačnej časti (ľavá strana), - Postupnosť elementárnych logických podmienok, ktoré spolu s logickými operáciami _konjunkcie_, _disjunkcie_ a _negácie_ vytvárajú _logický výraz_. 2. dôsledkovej alebo akčnej časti (pravá strana). - Poznatky, ktoré zabezpečia reakciu a rozpoznanú situáciu. - Reakcia je postupnosť akcií ako napr. _pridanie_, _modifikácia_ a pod. - Produkčné pravidlo -> produkčný systém. - Premenné umožňujú vytvárať všeobecnejšie pravidlá. - Nevýhody: - Ťažké pochopiť. - Teoreticky môže nastať nepredvídateľné správanie. - Zložitosť reprezentácie. - Sémantické siete, ontológie - Sémantické siete: - Prostriedok na reprezentáciu vzťahov medzi konceptami v problémovom prostredí. - Vychádza z požiadaviek na začleniteľnosť poznatkov. - Reprezentujú sa ohodnoteným orientovaným grafom. - Koncepty môžu byť napr. _objekty_, _pojmy_, _udalosti_ a pod. - Ontológia: - Je štruktúrovaná, obmedzená množina jednoznačne definovaných pojmov. - Spôsob reprezentácie znalostí o svete alebo jeho časti. - Dátový model, ktorý reprezentuje množinu pojmov a vzťahy medzi nimi. - Z explicitne vyjadrených zaznamenaných znalostí možno vyvodzovať implicitné dôsledky a súvislosti zahrnuté v ich obsahu. - Všeobecne sa zapisujú ako množina definícií formálneho slovníka. - Reprezentuje jednotky (_entity_), _myšlienky_, _udalosti_ s ich _vlastnosťami_ a _vzťahmi_ vzhľadom na systém kategórií. --- # Lekcia 5: Vnímanie - Rozpoznávanie vzorov - Aplikácie rozpoznávania vzorov - Analýza údajov a identifikácia podobností na odporúčanie objektu alebo obsahu koncovému používateľovi. - YouTube/Netflix/Spotify - personalized recommendations. - Pri programovaní a vývoji softvéru vytvárame vzory založené na osvedčených postupoch a replikujeme štýl ich architektúry pre iné aplikácie v rovnakej oblasti. - Rozpoznávanie textu, obrázkov, znakov, zvuku/reči, biometrických dát. - Machine vision. - Počítačová diagnóza. - Príznakové rozpoznávanie - Zaoberá sa vzorcom ako celkom. - Vychádza z predpokladu, že jednotlivé triedy obrazcov možno opísať presne definovanými príznakmi. - Príznakom môže byť napr. amplitúda signálu, jeho frekvenčný a časový priebeh, úroveň jasu určitého bodu v obraze a pod. - Získané príznaky sa porovnávajú s príznakmi vzorov tried. - Výsledkom je _zhoda_ alebo _podobnosť_. - Uskutočňuje sa: 1. určením príznakov, 2. voľbou tried obrazcov, 3. vytvorením príznakov pre vzory tried, 4. získaním príznakov, 5. porovnaním získaných príznakov s príznakmi vzorov a rozhodnutím o zaradení vstupného obrazca do príslušnej triedy. - Optical Character Recognition (_OCR_) systémy - Vstupom je obrázok s nejakým textom. - Výstupom je rovnaký text s nejakým počítačovým kódovaním. - [CAPTCHA](https://cs.wikipedia.org/wiki/CAPTCHA). - Problémy: - Obrázok neobsahuje iba text. - Nekonzistentná farebnosť. - Skosenie a rotácia. - Rôzne veľkosti a písma. - Časti OCR systémov 1. Binarizer - Vytvára pixelový obaz. 2. Segmentor - Vytvorí sadu súradníc pre každý čierny pixel. 3. Tresholder 4. Typesetter - Zarovnanie a pripojenie jednotlivých segmentov do línie slov. 5. Scaler 6. Feature Extractor, 7. Linguist, - Príznaky a spôsoby výberu príznakov - Príznaky: - Určenie spôsobu, na základe ktorého sa získané príznakové vektory budú zaraďovať do tried. - Reprezentujú sa vo forme vektorov. - Spôsoby výberu príznakov: - Templates - Hľadanie zhody so vzorom - Histogramy - Súčet čiernych pixelov v danom regióne - Priesečníky - Založená na počte priesečníkov vopred zvolených vektorov v políčku so znakom. - Fourierova transformácia - Zmena reprezentácie obrazcov z časovo-priestorovej na frekvenčno-amplitúdovú. - Hysterézne vyhladzovanie - Hysterézne okno obsahuje v ňom umiestnený riadiaci bod. - Riadiaci bod sa pohybuje po obryse obrazca najskôr smerom nahor alebo doprava ak nie je možný pohyb nahor. - Hysterézne okno posúva so sebou. - Výsledok nemusí byť pre rozpoznávanie dostatočná a preto sa pre každý príznak uvádza ešte kvadrant, v ktorom bol získaný. --- # Lekcia 6: Strojové učenie - Rozhodovacie stromy - Čo reprezentujú rozhodovacie stromy? - Všetky monžné rozhodnutia systému s podmienkami pre prechod do iného rozhodnutia. - Rozhodovacie stromy a strojové učenie - Rozhodovací strom môže umožniť predikciu odpovede na nejakú otázku, pričom sa využije rozhodovací strom. - Vstupná informácia (napr. otázka) sa spracuje pomocou pravidiel v strome a podľa ich výsledku sa prechádza v stavoch. - Koniec riešenia znamená, že už neexistujú ďalšie podmienky (a teda ani stavy) a stroj zastane v nejakom koncovom stave. - Prepis stromu na pravidlá - N/A - Výber vlastností pre tvorbu ulov - N/A - Klasifikačná chyba - Počíta sa pomocou vzorca: `nesprávne predikcie` / `príklady`. - Najlepšia hodnota je 0. - Najhoršia hodnota je 1. - Pravidlá pre ukončenie rekurzie tvorby stromov - N/A --- # Lekcia 7: Strojové učenie, Naive Bayes, Q-learning - Oblasti využitia strojového učenia - Riešenie skupiny problémov, na ktoré neexistujú žiadni ľudia. - Predpovedať výpadky strojov. - Riešenie skupiny problémov, kde experti síce existujú, ale nie sú schopní vysvetliť svoju expertízu. - Rozpoznávanie reči, rukopisu a pochopenie prirodzeného jazyka. - Riešenie skupiny problémov, kde sa rýchlo menia okolnosti. - Predpovedať budúci vývoj na burze, vývoj spotrebiteľských nákupov alebo menových kurzov. - Riešenie skupiny aplikácií, ktoré musia byť nastavované pre každého užívateľa zvlášť. - Filtrácia nechcenej e-mailovej pošty. - YouTube/Netflix/Spotify - personalized recommendations. - Biflovanie, induktívne učenie sa - Informácia, ktorá umožní v budúcnosti podobnú úlohu splniť lepšie. - Zapamätanie si predošlého ohodnotenia. - Naivný Bayesovský klasifikátor - Štatistický klasifikátor. - Predikuje pravdepodobnosti, s ktorými daný príklad patrí do triedy. - Vychádza z predpokladu **nezávislosti atribútov** medzi sebou. - Typy strojového učenia - Učenie sa s učiteľom (_supervised learning_) - okamžitá dostupnosť vnemov o vstupoch aj výstupoch. - Učenie sa bez učiteľa (_unsupervised learning_) - agent nedostáva nijakú informáciu o tom, aké by mali byť správne akcie. - Učenie sa odmenou a trestom (_reinforcement learning_) - agent dostane informáciu o hodnotení akcie, ale nie o tom, aká mala byť správna akcia. --- # Lekcia 8: Strojové učenie - Regresia - Lineárna regresia - Spôsob, ako zistiť vzťah medzi dvoma premennými. - Príklad: _Dlhšia doba učenia => lepšie výsledky._ - Hľadá najlepšiu čiaru, ktorá spája dáta. - Residual sum of squares (RSS) - Je číslo, ktoré hovorí, ako veľmi sa mýli náš model - teda ako ďaleko sú predpovede modelu od skutočných hodnôt. - Čím je RSS **menšie**, tým lepší model - znamená to, že predpovede sú bližšie k realite. - Stupne polynómu - komplexnosť modelu - Určuje, aká zložitá je krivka, ktorú model používa na prispôsobenie sa dátam. - Čím vyšší stupeň, tým viac sa model "ohýba", aby čo najlepšie prešiel cez body. - Cieľ je nájsť taký stupeň, ktorý dobre zachytí vzťah v dátach, ale neprispôsobí sa až príliš. - Pridanie ďalších parametrov - N/A --- # Lekcia 9: Spracovanie prirodzeného jazyka (NLP) - Predspracovanie textu - N/A - Tokenizázia - Rozdelenie textu na menšie časti (_tokeny_). - Token je časť celku a môžme mu rozumieť ako slovo alebo veta. - Lematizácia - Je proces, pri ktorom sa slová zmenia na svoj základný tvar (_lemma_). - Príklad: "bežím", "bežal", "bežať" => "_bežať_". - Stop slová - Bežné a často používané slová, ktoré zvyčajne nenesú dôležitý význam pre spracovanie textu. - Príklad: "Pes je na lúke a šteká." => "Pes lúke šteká." - Part-of-Speech (_POS_) tagging - Proces, pri ktorom sa každému slovu v texte priradí slovný druh (podstatné meno, sloveso, prídavné meno, predložka, atď).