Otázky na skúšku
Z Psychostudia
Zdroj : Doc. Ing. J. CSONTÓ Csc. , Ing. T. SABOL Csc. : UMELÁ INTELIGENCIA, ISBN 80-7099-104-6
Obsah |
Definícia umelej inteligencie
Kotek
UI je vlastnosťou človekom umelo vytvoreného systému, vyznačujúceho sa schopnosťou rozpoznávať javy, predmety, situácie, analyzovať vzťahy medzi nimi a tak vytvárať vnútorné modely sveta a na základe toho robiť účelné rozhodnutia, vrátane schopnosti predvídať dôsledky týchto rozhodnutí a schopnosti objavovať nové zákonitosti.
Marvin Minsky
> definícia je inšpirovaná Turingovým imitačným testom
UI je veda o vytváraní strojov alebo systémov, ktoré budú na riešenie úloh používať postup, ktorý, ak by ho použil človek, by sme považovali za prejav jeho inteligencie.
Z hľadiska klasifikácie cieľov UI existujú 3 smery
1. psychologický - poznať zákonitosti ľudského myslenia a kognitívnej činnosti tým, že sa ju pokúšajú umelo modelovať
2. inžiniersky - vytvoriť systém metód a programov, ktoré by pomocou počítača umožnili riešiť intelektuálne náročné úlohy spôsobom, ktorý nemusí imitovať metódy, ktoré používa človek. (lietadlá nenapodobňujú let vtákov ?)...
3. filozoficko-matematický - štúdium a formalizácia intelektuálnych mechanizmov nezávisle na tom či sú realizované na počítači lebo v mozgu
Špecifické úlohy UI
> rozpoznávanie obrazov
> rozpoznávanie scén
> hranie šachu
> automatické dokazovanie teorém
> riešenie hlavolamov
> porozumenie prirodzenému jazyku
> reprezentácia znaostí
Niektoré aplikácie UI
Vnímanie okolitého sveta
Snahou je vybaviť systém vizuálnymi vstupmi tak, aby "videl" svoje okolie a akustickými vstupmi tak, aby "počul" akustické signály okolo seba.
V UI proces vnímania (percepcie) pozostáva z postupnosti krokov. Scéna sa zosníma, čím sa získa maticová reprezentácia jasových úrovní. Po predspracovaní (odstránenie šumu, zvýraznenie, potlačenie niektorých čŕt) sa na digitalizovaný obraz aplikujú metódy na rozpoznávanie obrazových primitív (priamky, rohy krivky...). Ďalším krokom je získanie informácie o trojrozmernom charaktere scény. Cieľom je reprezentovať scénu vhodným modelom. Tento model môže pozostávať z popisu v prirodzenom jazyku. Forma a kvalita výslednej reprezentácie závisí na konkrétnej aplikácii.
Robotika
Expertné systémy
Dokazovanie teorém
Automatické programovanie
Spracovanie prirodzeného jazyka
Robotika
Robot
- počítačom riadený integrovaný systém, schopný autonómnej a cieľovo orientovanej interakcie so svojím reálnym okolím v súlade s inštrukciami od človeka.
Roboty, ktoré sú schopné :
1. vnímať a rozpoznávať prostredie
2. vytvárať a priebežne aktualizovať vnútorný model prostredia
3. na základe tejto reprezentácie a v súlade s cieľmi rozhodovať o vlastnej činnosti
4. ovplyvňovať prostredie - manipulovať s predmetmi prípadne sa pohybovať
5. komunikovať s človekom v prirodzenom alebo umelom jazyku
sa nazývajú kognitívne (niekedy sa používa inteligentné) roboty.
Subsystémy robota
Senzorický
> zaisťuje príjem informácií o prostredí.
Hlavné úlohy :
> lokalizovať predmety v okolí
> zistiť vlastnosti predmetov v okolí
> zistiť všeobecné vlastnosti prostredia
> sledovať stav vlastného manipulačného systému
> umožniť orientáciu a navigáciu v priestore
> sprostredkovať komunikáciu s človekom
Motorický
> aktívne pôsobí na prostredie
Kognitívny
> plní poznávaciu rozhodovaciu a riadiacu funkciu
Analytická časť kognitívneho subsystému, ktorá zodpovedá za analýzu a interpretáciu údajov získaných senzorickým subsystémom sa skladá z dvoch častí
> vnímanie
> porozumenie
Bez správne interpretovaných vstupných údajov by robot nemohol vytvoriť správny model prostredia. Výsledkom vnímania je spravidla rozpoznanie a klasifikácia vstupných údajov, teda odpoveď na otázku Čo to je?. Porozumenie zahrňuje širšie súvislosti a je považované za jednu zo základných zložiek myslenia. U robota by malo porozumenie vyústiť do interpretácie vstupných údajov adekvátnej jeho schopnostiam a cieľom a dať tak odpoveď na otázky ako Čo s tým mám urobiť?, Ako to súvisí s mojím cieľom?
Úlohou robota je dosiahnuť svojimi akciami určitý cieľ. Robot má určený iba cieľ. Plán ako ho dosiahnuť si musí vytvoriť sám. Úloha vzniká ak existuje nezhoda medzi aktuálnym a žiadaným stavom prostredia.
Riešenie pozostáva z:
> formovanie plánu - hľadanie hypotetickej cesty (napr. prehľadávanie stavového priestoru) od počiatočného stavu k cieľovému stavu
> realizovanie plánu - fyzické pôsobenie na prostredie podľa vytvoreného plánu
Ľudská inteligencia
Intelektové schopnosti podľa J.P.Guilforda
> intelekt
> pamäť
> myslenie
> poznávanie
> tvorenie
> konvergentné
> divergentné
> hodnotenie
Konvergentné myslenie vedie k jedinému a divergentné k viacerým možným riešeniam problému.
Vypočítateľnosť na reťazcoch
Formálne jazyky a gramatiky tvoria dôležitú časť matematického aparátu UI. Používajú sa pri syntktickom rozpoznávaní predmetov alebo spracovaní prirodzeného jazyka...
Slovom budeme nazývať ľubovoľnú postupnosť prvkov nejakej abecedy ∑.
Abecedou je každá konečná neprázdna množina symbolov.
Množinu všetkých slov nad abecedou ∑ označíme ∑*. Z algebraického hľadiska je ∑* voľný monoid nad ∑ (∑ je jeho množina generátorov) s binárnou operáciou zreťazenia a jednotkovým prvkom Α. Ľubovoľnú podmnožinu L ∈ ∑* nazývame formálny jazyk nad ∑.
Iterácia formálneho jazyka L sa označuje L* a pozostáva z prázdneho slova a zo všetkých slov vzniknutých zreťazením konečného počtu slov z L.
Gramatika G je usporiadaná štvorica <N, T, σ, P> kde
- N je konečná množina neterminálnych symbolov
- T je konečná množina terminálnych symbolov
- σ je štartovací symbol
- P je konečná množina prepisovacích pravidiel v tvare
Formálne gramatiky možno použiť v dvojakom zmysle
1. Generatívne - vychádzajúc z počiatočného stavu σ vytvárame slová v abecede ∑ postupným aplikovaním prepisovacích pravidiel.
2. Analyticky - je dané slovo u a je potrebné určiť, či u ∈ L(G). Postup, ktorý o tom rozhodne a nájde spôsob ako môže byť slovo u generované sa nazýva syntaktická analýza.
Chomského rozdelenie gramatík
Gramatiky typu 0 (všeobecné gramatiky) - nepožaduje sa žiadne obmedzenie na substitučné pravidlá. Tento typ gramatiky je príliš všeobecný na pre značnú obtiažnosť nebol zatiaľ skúmaný.
Gramatiky typu 1 - senzitívne, kontextové
Gramatiky typu 2 - bezkontextové
Gramatiky typu 3 - regulárne
Turingov stroj
Turingov stroj (TS) je stroj, ktorý má všetky logické možnosti, ktoré vôbec reálny počítač môže mať. Preto sa vypočítateľnosť funkcie viaže na vypočítateľnosť na TS.
TS nad abecedou ∑ pozostáva z troch základných častí :
1. Nekonečná páska, ktorá je rozdelená na políčka. Každé políčko obsahuje jeden symbol abecedy ∑.
2. Hlava na čítanie a zapisovanie, ktorá sa nachádza na určitom políčku pásky
3. Riadiaca jednotka, ktorá sa nachádza v jednom z konečných vnútorných stavov S
program TS pozostáva z konečného počtu pravidiel vo forme "Ak sa riadiaca jednotka nachádza v stave Si a na páske bol prečítaný symbol aj, zapíš na pásku nový symbol ar a a posuň hlavu o k políčok vpravo (vľavo ak k<0). Potom prejdi do stavu Sm.
(aj, Si) --> (k, ar, Sm)
Ak neexistujú dve pravidlá s rovnakou ľavou stranou jedná sa o deterministický Turingov stroj
Algoritmická riešiteľnosť
Algoritmus sa skladá z príkazov k elementárnym, ľahko riešiteľným akciám, pričom vylučuje pochybnosti o tom, v akom poradí majp byť vykonané. Základné vlastnosti algoritmu sú rezultatívnosť, determinovanosť a hromadnosť.
Úlohy, pre ktoré existuje algoritmus sa nazývajú algoritmicky riešiteľné (efektívne).
Kľúčovým nástrojom pre riešenie problému algoritimickej riešiteľnosti je Turingova veta o neriešiteľnosti problému skončenia.
...
Algoritmická zložitosť
Programy sa anaylyzujú z dvoch hľadísk :
1. Časová zložitosť programu je určené počtom krokov, ktorý musí program nad danými údajmi vykonať.
2. Priestorová zložitosť je veľkosť pamäte potrebná na úspešné ukončenie výpočtu.
Reprezentácia vedomostí
v UI sa pod reprezentáciou vedomostí rozumie kombinácia údajové štruktúry a interpretačné procedúry. Ak sa tieto správne použijú, vedú k "inteligentnému" chovaniu. Preto bolo úsilie UI sústredené na :
1. návrh viacerých tried údajových štruktúr pre uloženie informácie v počítači
2. vývoj procedúr, ktoré umožňujú "inteligentnú" manipuláciu nad týmito štruktúrami za účelom inferencie (odvodenie novej informácie)
Vedomosti
Niektoré typy vedomostí, ktoré je potrebné v UI reprezenzovať:
1. Objekty - fakty o objektoch v okolitom svete.
2. Udalosti - musíme vedieť o udalostiach a akciách vo okolitom svete. Okrem reprezentácie samotných udalostí potrebujeme aj mechanizmus na indikáciu časovej postupnosti udalostí, ich príčinne vzťahy, následky a pod.
3. Vykonanie určitej udalosti - ako niečo urobiť, t.j. aplikovanie vedomostí.
4. Metavedomosti - vedomosti o vedomostiach; vedomosti o tom čo vieme... Patrie sem aj vedomosti o činnosti vlastného kognitívneho procesu ako výkonnosť, slabosť, úroveň myslenia v rôznych oblastiach, pocit, že sme pokročili v riešení určitého problému.
Použitie vedomostí
V UI sa vedomosti používajú na :
1. Získavanie ďalšej informácie
2. Získanie faktov relevantných k danému problému z databázy - otázka relevantnosti je kritická ak systém "vie" veľa.
3. Uvažovanie
Uvažovanie
1. Formálne uvažovanie - syntaktická manipulácia s údajovými štruktúrami s cieľom odvodiť nové informácie podľa špecifikovaných inferenčných pravidiel (matematická logika)
2. Procedurálne uvažovanie - používa simuláciu pri zodpovedaní otázok. Na zodpovedanie otázky sa spúšťa príslušný procedurálny model
3. Uvažovanie analógiou
4. Zovšeobecnenie a abstrakcia
5. Uvažovanie na meta úrovni ...
Stavový priestor
- najstaršie forma reprezentácie, pôvodne určená na riešenie úloh a programovanie hier.
Stavový priestor reprezentuje štruktúru problému pomocou alternatív prípustných v danom stave. Všetky nasledujúce stavy môžu byť z daného stavu úlohy odvodené malou množinou pravidiel - operátormi prechodu. Možným riešením úloh tohto typu je kompletné prehľadanie stavového priestoru. Problémom je kombinatorická explózia, preto by mal program "vedieť" niečo o probléme,ktorý rieši.
Formálna logika
Formálna logika je klasickou metódou reprezentácie vedomostí. Jej výhodou je, že pomocou množiny pravidiel (inferenčných) možno z faktov, ktoré sú pravdivé (axiómy) odvodiť ďalšie fakty, ktoré musia byť pravdivé a naviac aj pravdivosť každého nového tvrdenia sa dá overiť pomocou už existujúcich faktov a inferenčných pravidiel. Najdôležitejšou vlastnosťou formálnej logiky je, že je zaručená správnosť dedukcie a logiská konzistentnosť. Proces dedukcie môže byť automatizovaný.
Predikátový počet
Predikátový počet sa používa na reprezentáciu tvrdení o špecifických objektoch - individuáloch (ty, tento_papier, Sokrates... ). Tieto sa nazývajú predikátové konštanty.
Predikáty sú tvrdenia o predikátových konštantách alebo o ich vzťahu k iným predikátovým konštantám. Predikát sa aplikuje na špecifický počet argumentov a ak sa za argumenty dosadia konštanty, nadobúda predikát hodnoty TRUE alebo FALSE.
> unárny predikát - predikát s jedným argumentom, napr. je_zelený, smrteľný, Slovák ... > binárny predikát - predikát s dvomi argumentami, napr. je_meší_ako ...
Kvantifikátory
∀ - Všeobecný ∃ - Existenčný
Dobre definovaná formula
DDF predikátového počtu je taká formula, ktorá je vytvorená syntakticky prípustnou kombináciou spojok, predikátov, konštánt, premenných a kvantifikátorov.
Predikátový počet prvého rádu
funkcia - má podobne ako predikát definovaný počet argumentov ale nenadobúda hodnoty TRUE/FALSE ale jej výstupom je objekt
> funkcia(objekt, objek, ..., objekt) = objekt > strýko(Mária) = Jano > otec(otec(Jano)) = starý_otec(Jano)
Predikát equal (=) ... relácia totožnosti; platia axiómy :
> X1 = Y1, ..., Xn = Yn ==> (P(X1, ..., Xn) <==> P(Y1, ..., Yn)) > X1 = Y1, ..., Xn = Yn ==> (f(X1, ..., Xn) = f(Y1, ..., Yn))
kde P je ľubovoľný predikát a f je ľubovoľná funkcia. ==> variácia logiky prvého rádu.
Logika je prvého rádu, ak dovoľuje kvantifikáciu premenných a nedovoľuje kvantifikácií predikátov a funkcií. Logika prvého rádu je neprotirečivá, t.j. nemožno dokázať nepravdivé tvrdenia a úplná, t.j. pre každé pravdivé tvrdenie existuje dôkaz.
Sémantické siete
- pôvodne boli navrhnuté ako psychologický model ľudskej asociatívnej pamäte.
Sieť pozostáva z uzlov, ktoré reprezentujú objekty, pojmy, situácie a z hrán, ktoré reprezentujú ich vzťahy. Všetky relevantné fakty o danom objekte môžu byť odvodené od uzlov, ktoré sú k nemu pripojené, bez prehľadávania celej databázy. Prístup k relevantným faktom o objekte je možný pomocou hrán ISA a SUBSET, ktoré určujú vlastnosť prirodzenej hierarchie pojmov. Interpretácia sémantických sietí závisí iba od programu, ktorý nad nimi manipuluje.
Inferencia pomocou sémantickej siete
Väčšina inferenčných mechanizmov je založená na porovnávaní štruktúr siete (matching). Skonštruuje sa fragment siete, ktorý reprezentuje hľadaný objekt, alebo otázku a tento sa porovnáva s celkovou sémantickou sieťou databázy. Premenné uzly fragmentu sa naviažu na hodnoty uzlov databázy tak, aby bolo porovnávanie úspešné.
Na princípe takéhoto vyhľadávanie funguje systém SNIFFER, ktorý je schopný robiť dedukcie, využíva aj výhodu heuristickej informácie, ktorá je včlenená v tzv. selektore funkcií - poskytuje informáciu o tom, ktorý prvok použiť na prehľadávanie ako prvý a ako porovnávať vybrané prvky siete čo umožňuje usmernenie dedukcie.
Rámce a skripty
Na reprezentáciu vedomostí boli navrhnuté rámce (Minsky, 1975) a skripty (Schank, Abelson, 1977). Obe metódy organizujú vedomosti tak, aby bolo možné usmernenie pozornosti a uľahčenie inferencie.
Rámce
Nové údaje sú reprezentované pomocou pojmov z predchádzajúcich skúseností. Okrem toho organizácia umožňuje spracovanie na základe očakávaní. Rámec je údajová štruktúra, ktorá zahŕňa deklaratívne aj procedurálne informácie v preddefinovanom vnútornom vzťahu.
Príklad :
Generický rámec PES môže obsahovať rubriky POTRAVA, MAJITEĽ, MENO a pripojené procedúry pre pre určenie majiteľa. Rámec PES obsahuje rovnaké rubriky ale ich obsah je špecifický.
Skripty
Skripty reprezentujú sled udalostí... ?
Automatické dokazovanie teorém
- prostriedok pre riešenie úloh UI. Používa sa princíp dôkazu sporom, kedy sa dokazuje nepravdivosť negácie tvrdenia, ktoré treba dokázať.
Klauzulárny tvar
Pre mechanickú manipuláciu s formulami je výhodné používať štandardný tvar týchto formúl:
Klauzula je disjunkcia literálov L1 v L2 v ... v Ln, kde literál je atomická formula alebo jej negácia.
Klauzulu je možné zapísať aj ako množinu C ={L1 v L2 v ... v Ln}.
Pre n=0 je C prázdna klauzula (reprezentuje spor). Štandardnými úpravami možno ľubovoľnú klauzulu predikátového počtu previesť na klauzulárny tvar, teda na konjunkciu
C1 & C2 & ... & Cn , kde Ci sú klauzuly a všetky premenné sa považujú za viazané všeobecnými kvantifikátormi umiestnenými pred celou formulou.
Herbrandove univerzum
Ak D je formula alebo množina formúl v klauzulárnom tvare, potom Herbrandove univerzum H(D) je spočetná množina termov definovaná induktívne :
1. obsahuje všetky individuálne konštanty, vyskytujúce sa v D
2. ak sú termy t1, t2, ..., tn prvkami H(D), potom aj f(t1, t2, ..., tn) je prvkom H(D) pre každý n-árny funkčný symbol f, vyskytujúci sa v D.
3. Iné prvky v H(D) nie sú
Herbrandova báza
Herbrandova báza I(D) je množina všetkých atomický formúl z D, v ktorých sú namiesto premenných dosadené prvky H(D).
Rezolučný princíp
Prehľadávanie a riešenie úloh
Prehľadávanie do šírky
- uzly sa expandujú podľa ich vzdialenosti od koreňové uzla, pričom dĺžka každej hrany je 1. Tým je zaručené, že sa nájde najkratšie možné riešenie, za predpokladu že riešenie existuje.
Algoritmus
1. Počiatočný uzol daj do zoznamu OPEN (zoznam neexpandovaných uzlov). Ak sa počiatočný uzol rovná cieľovému riešenie je nájdené. 2. Ak je OPEN prázdne, riešenie neexistuje 3. Zo zoznamu OPEN odstráň prvý uzol n a zaraď ho do zoznamu CLOSED (zoznam expandovaných uzlov). 4. Expanduj uzol n. Ak nemá potomkov, choď na (2). 5. Zaraď všetkých potomkov n na koniec zoznamu OPEN. 6. Ak je niektorý z potomkov n cieľový uzol, riešenie je nájdené. Inak choď na (2).
Prehľadávanie do hĺbky
Stále sa expanduje posledne generovaný uzol s najväčšou hĺbkou. Hĺbka uzla v strome je definovaná :
1. hĺbka počiatočného uzla je 0
2. hĺbka ľubovoľného uzla je o 1 väčšia ako hĺbka jeho otca
Algoritmus s obmedzením hĺbky
1. Počiatočný uzol s vlož do zoznamu OPEN. Ak s je cieľovým uzlom, riešenie je nájdené. 2. Ak je OPEN prázdny, riešenie neexistuje. 3. Vyber prvý uzol n s OPEN a vlož ho do CLOSED 4. Ak hĺbka uzla n je rovná maximálne hĺbka, choď na (2). 5. Expanduj uzol n. Ak nemá potomkov, choď na (2). 6. Vlož všetkých potomkov uzla n na začiatok OPEN. 7. Ak niektorý z potomkov uzla n je cieľový uzol, riešenie je nájdené. Inak choď na (2).
Heuristické prehľadávanie
- heuristická informácia - dodatočná informácia o vlastnostiach danej problémovej oblasti.
- heuristické prehľadávanie - využívajú heuristické informácie... :)
Heuristická informácia môže byť pri prehľadávaní využitá vo viacerých bodoch:
1. pri rozhodovaní, ktorý uzol bude expandovaný ako ďalší
2. pri expandovaní rozhodnúť, ktorého potomka alebo potomkov generovať, namiesto slepého generovania všetkých potomkov
3. pri rozhodovaní, či dané uzly možno zanedbať alebo ich odseknúť zo stromu prehľadávania.
Hodnotenie uzla sa robí pomocou heuristickej funkcie f*. Čím je uzol "sľubnejší", tým je hodnota f* menšia.
Algoritmus A*
1. Vlož štartovací uzol s do zoznamu OPEN. Vypočítaj hodnotu f*(s) a zviaž ju s uzlom s.
2. Ak je OPEN prázny, algoritmus končí neúspechom.
3. Zo zoznamu OPEN vyber uzol i , ktorého hodnota f*(i) je minimálna. Ak je takýchto uzlov viac, vyber cieľový (ak existuje), inak vyber náhodne.
4. Vlož uzol i do CLOSED.
5. Ak je i cieľový uzol riešenie je nájdené.
6. Expanduj uzol i, vytvor všetkých jeho potomkov a pre každého potomka j uzla i urob :
a. Vypočítaj f*(j)
b. Ak j nie je v OPEN ani CLOSED pridaj ho do OPEN spolu s hodnotou f*(j). Pridaj smerník od j na otca i.
c. Ak už bol j v OPEN alebo CLOSED porovnaj novú vypočítanú hodnotu f*(j) s už existujúcou. Ak je nová hodnota f*(j) menšia :
- nahraď ňou starú hodnotu f*(j)
- nastav smerník od j k i
- ak bol j v CLOSED presuň ho znova do OPEN
7. Choď na (2)
