UMĚLÁ INTELIGENCE ARTIFICIAL INTELLIGENCE (AI)

Základy umělé inteligence

Fakulta elektrotechniky a informatiky Univerzita Pardubice

UMĚLÁ INTELIGENCE – ARTIFICIAL INTELLIGENCE (AI) Motto:

Přirozená inteligence bude zřejmě brzy překonána inteligencí umělou, avšak přirozenou blbost umělá nikdy překonat nedokáže. Jára da Cimrman

1 ÚVOD DO UMĚLÉ INTELIGENCE Mnoho matematických disciplín bylo a stále je silně ovlivňováno přírodou a snahami přiblížit se přírodě. Čím více o přírodě víme, tím více jsme fascinováni její jednoduchostí a téměř dokonalou funkčností. S rostoucí výkonností výpočetní techniky se přirozeně mění i požadavky na třídy úloh, které jsou na počítačích řešeny. Stále častěji jsou počítače využívány k řešení takových úloh, u kterých by musel člověk při jejich řešení, využívat svou inteligenci. Je samozřejmé, že tvorba programů, u kterých se objevují prvky jakési „umělé inteligence“, vyžaduje nové přístupy, teorie, metody a techniky. V čem spočívá složitost problému a jaké vlastnosti a znaky má jeho „inteligentní řešení“? Složitost problému lze ohodnotit počtem všech variant, které připadají při řešení v úvahu. Řešitel úlohy, který postupuje „inteligentně“ prohledává jenom nadějné varianty a ty, které nedávají dostatečnou šanci na úspěch, vynechává. Čím více neperspektivních variant oprávněně vynechá, tím inteligentnější se řešení jeví. Mechanismus, který umožňuje řešiteli některé varianty hned odmítnout, je založen na využívání znalostí. V řadě případů, zejména při diagnóze, predikci chování a řízení složitých, obtížně poznatelných a obtížně měřitelných systémů, jsou v praxi úspěšně využívány závěry, které odvozuje zkušený operátor – expert. Tyto znalosti jsou jednak přebírány od člověka, který je schopen úlohu inteligentně řešit, jednak analýzou případů, kdy je známo zadání úlohy a její inteligentní řešení. Znalosti mohou mít jednak exaktní charakter (teorémy, fyzikální zákony apod.), jednak mohou být tvořeny heuristickými poznatky. Heuristické poznatky nebývají podloženy hlubší teorií, velmi často však pomáhají účinně nalézt řešení, přesto však obecně nalezení řešení negarantují. Heuristické znalosti chápeme pouze jako neexaktní návod k řešení. Při řešení problému pak expert využívá principiálně jednoduchých nenumerických algoritmů, které mu umožňují kombinovat objektivní a subjektivní znalosti při odvozování závěrů při řešení problémů, rozhodování nebo řízení.

1.1 Co je to inteligence? Chceme-li se zabývat umělou inteligencí, je nutné nejprve definovat inteligenci přirozenou, protože se ji umělá inteligence snaží napodobovat. To je ale velmi komplikovaný úkol, protože dosud neexistuje obecně uznávaná definice. Inteligence je obvykle považována za vlastnost živých organismů, která jim umožňuje reagovat na složité projevy okolního prostředí a využívat je aktivně ke svému prospěchu a k dosažení svých cílů. Inteligence je schopnost účinně a rychle řešit obtížné nebo nové situace a problémy a na základě vlastní úvahy, nacházet podstatné prvky a jejich souvislosti. Rozlišuje se inteligence obecná (jakýsi společný jmenovatel všech typů jednání vyžadujících inteligenci) a inteligence speciální, která v určitých oblastech doplňuje inteligenci obecnou. Pojem inteligence lze jen obtížně přesně vymezit, neexistuje žádné objektivní měření inteligence. Různé druhy inteligence se objevují u lidí, u řady zvířat, ale i u některých strojů a zařízení. Zatím se nepodařilo obecně charakterizovat, který druh výpočetních postupů a rozhodování lze považovat za inteligentní. Některým inteligentním postupům při výpočtech a rozhodování jsme totiž už porozuměli, -1-



ovšem jiným zatím ne. Inteligence zahrnuje určité mechanismy a tak se výzkum v oblasti AI zaměřuje na vytváření počítačových systémů, které některé z těchto mechanismů dokáží provádět. Aby byla taková úloha splněna, musí být příslušný mechanizmus dobře prozkoumán, protože počítačový program dokáže pouze plnit danou úlohu, tuto činnost však zvládá velmi efektivně. Intelekt Soubor rozumových schopností a dispozic - duševní schopnost, která je vlastní pouze člověku a je předpokladem myšlení. Umožňuje provádět takové myšlenkové úkony, které přímo nevyplývají z existujících situací, podmínek nebo údajů. Inteligence Schopnost účinně a rychle řešit na základě vlastní rozvahy obtížné nebo dosud neznámé situace a problémy, nacházet podstatné prvky a jejich souvislosti a vztahy. Inteligenční kvocient IQ Míra inteligence – vyjádření vztahu mezi dosaženou rozumovou úrovní člověka a jeho věkem. Původně hodnotil nárůst inteligence u dětí. IQ a byl definován jako stonásobek poměru věku, při kterém by mělo hodnocené dítě splnit určitý soubor úkolů ke skutečnému věku dítěte. Podobný test byl později sestaven i pro dospělé. IQ je kvantitativní ukazatel výkonu při testech inteligence. I když hodnota IQ není objektivní mírou inteligence, přesto velmi dobře koreluje s mírou úspěchu či neúspěchu člověka v životě. Asi ½ populace má průměrné IQ tj. 90-100. Hodnoty nižší označují podprůměrný výkon, hodnoty nad 110 jsou nadprůměrné. U počítačů však nemá hodnocení pomocí IQ žádný význam, neexistuje žádná korelace IQ s užitečností počítače.

1.2 Co to je umělá inteligence? Umělá inteligence je vědní oblast, která se zabývá vytvářením inteligentních strojů, zejména inteligentních počítačových programů. Tvoří ji souhrn stále se vyvíjejících a vzájemně prorůstajících oborů. Jejich hranice nejsou nijak zřetelně definovány a dynamicky se mění. Interakce mezi disciplinami jsou mimořádně silné a také se dynamicky mění. Jednotlivé části AI se stávají mnohdy samostatnými vědními disciplínami. AI představuje postupy a algoritmy, které napodobují chování člověka, nemusí se však omezovat pouze na napodobování. Někdy řeší umělá inteligence problémy, které vyžadují obrovské množství výpočtů, které by člověk sám nikdy nemohl provést. AI řeší úlohy tak složité, že člověk při jejich řešení musí uplatňovat svou inteligenci. Složitost úlohy je obvykle hodnocena počtem všech variant, které je nutno k vyřešení problému prověřit. Inteligentní postup však neprověřuje všechny možné varianty, ale pouze takové, které dávají určitou šanci na získání správného řešení. Podstatou takového postupu je využívání znalostí a zkušeností. Pro vysokou efektivitu systémů umělé inteligence mají rozhodující význam použité znalosti, zatímco obecný formální aparát pro řešení úloh poskytuje pouze nástroj pro řešení, má tedy druhořadý význam. Základním problémem umělé inteligence není odhalení několika efektivních technik, ale spíše otázka, jak reprezentovat velké množství znalostí ve tvaru, který by dovoloval jejich efektivní využívání a interakci. Důraz je kladen na znalosti spíše než na mechanismy jejich využívání. Umělá inteligence představuje soubor metod, teoretických postupů a specializovaných počítačových programů, určených ke strojovému řešení složitých problémů. Je to tedy vědní obor, který se zabývá vývojem technologií a programů pro provádění činností, o kterých se obvykle domníváme, že vyžadují lidskou inteligenci. Tento vědní obor se rozdělil na řadu dílčích podoborů, které se pokoušejí lépe porozumět mechanismům lidské inteligence – -2-



rozpoznávání, reprezentace znalostí, řešení úloh, kvalitativní modelování, strojové učení, plánování a rozvrhování, neuronové sítě. Na tyto části navazuje problematika počítačového vidění, zpracování přirozeného jazyka, problematika speciálních programovacích jazyků pro umělou inteligenci, expertní systémy a znalostní inženýrství. Výsledky řešení jednotlivých problémů pak netvoří součást umělé inteligence, ale přecházejí do oborů, ve kterých byly aplikovány. Výzkum umělé inteligence lze rozdělit do dvou základních směrů: • teoretický výzkum – studium jednotlivých intelektuálních mechanizmů a jejich souvislostí s řešenými problémy • experimentální výzkum – testování algoritmů umělé inteligence a ověřování jejich vhodnosti a způsobilosti k řešení jednotlivých specifických úloh

1.3 Definice umělé inteligence Minského definice „Umělá inteligence je věda o vytváření strojů a systémů, které při řešení určitého úkolu užívají takový postup, který by, kdyby tak postupoval člověk, mohl být považován za projev jeho inteligence.“ Definice E. Richové „Umělá inteligence se zabývá počítačovým řešením takových úloh, které dnes zatím lépe zvládají lidé“. Kotkova definice „Umělá inteligence je vlastnost člověkem uměle vytvořených systémů vyznačujících se schopností rozpoznávat předměty, jevy a situace, analyzovat vztahy mezi nimi a tak vytvářet vnitřní modely světa, ve kterých tyto systémy existují. Na tomto základě pak přijímají účelná rozhodnutí, předvídají důsledky těchto rozhodnutí a objevují nové zákonitosti mezi různými modely nebo jejich skupinami. Umělá inteligence se pokouší převádět funkce živého organismu na neživé stroje. Snahou je rozpoznat a formulovat funkce přirozené inteligence tak, aby tyto funkce mohly být využity při návrhu strojů a zařízení. Do oblasti umělé inteligence zařazujeme takové úlohy, při jejichž řešení používá člověk inteligentní postup. Slabým místem takové definice AI je mlhavost a obtížná měřitelnost pojmu „inteligentní postup“.

1.4 Historie a současnost umělé inteligence Původně vznikla umělá inteligence pouze pro použití v robotice. Roboti s prvky AI dostali označení kognitivní (= vnímavý, hodnotící). Počítačové AI použila ve větším měřítku NASA k řízení a kontrole letu družic. Je zřejmé, že základem AI je počítač, bez počítače by nebylo AI. Podle toho, jakou roli hraje počítač v AI, dělíme umělou inteligenci do dvou skupin: • slabá – počítač je pouze užitečný nástroj • silná – počítač přímo „myslí“ a pomocí programu i chápe 1.4.1 Historický vývoj: r.1941 První použití elektronického počítače v Německu – využíván převážně pro vojenské účely – výpočet drah raket V1 a V2. r.1950 Objevení principu zpětné vazby (Norbert Wiener). -3-

Základy umělé inteligence r.1955

r.1956

r.1957 r.1958 r.1963 70. léta r.1972 r.1976


Autoři A.Newell a H.A.Simon vyvinuli „The Logic Theorist“, považovaný za první program AI. Program reprezentuje každý problém jako stromový model (tree model) a řešení spočívalo v hledání „větve“, jejíž výsledek byl s největší pravděpodobností ten správný. Otec AI, John McCarthy, zorganizoval konferenci o strojové inteligenci ve Vermontu „The Dartmouth Summer Research Project on Artificial Inteligence“. Testování první verze programu „The General Problem Solver1“. John McCarthy vytvořil jazyk AI vývojářů LISP (LISt Processing) = zpracování seznamů. Na Carnegie Mellon a na MIT se zformovala první centra výzkumu AI. Nástup expertních systémů – rozvoj systémů rozeznávání obrazů - objev fuzzy logiky a neuronových sítí. Vytvoření jazyka PROLOG2 (PROgramming in LOGic). Expertní systém MYCIN (používaný k diagnóze chorob).

1.4.2 Porovnání rozsahu úlohy a času na její řešení Některé problémy řadíme do skupiny tzv. nondeterministic polynomial (NP) problémy. Jsou to problémy kombinatorického charakteru, kdy počet alternativ narůstá faktoriálně s počtem uvažovaných prvků systému. Hovoříme o tzv. kombinatorické explozi. Např. pro 10 úrovní a 10 možnostech v každé úrovni existuje 10 miliard možných kombinací. Řešení takových problémů je v polynomiálně omezeném čase (výpočetní čas je úměrný nějaké mocnině počtu prvků) výpočetně nezvládnutelný. Bez ohledu na rychlost prováděných operací na počítači bude vždy existovat horní hranice rozměru systému, který je řešitelný v „rozumném“ čase. Pro ilustraci časové nezvládnutelnosti problémů faktoriálního charakteru lze uvést srovnání potřebných časů výpočtu pro soubory o daném počtu prvků. Dobu provedení jedné operace uvažujeme 1 μs. Počet operací (n)

5

10

50

100

5 μs 125 μs 32 μs 120 μs

10 μs 1 ms 1,024 ms 3,6288 s

50 μs 125 ms 35,7 let 9,644.1050 let

100 μs 1s 4,02.1016 let 2,96.10144 let

operace n 3

n

2n n!

Tabulka 1 - Doba výpočtu při počtu prvků v souboru n 1 hod = 3 600 s

1 den = 86 400 s

1

1 rok = 31 536 000 s

GPS byl navržen jako univerzální nástroj pro řešení různých problémů. Byl prvním počítačovým programem, který oddělil znalosti o problému od strategie řešení problému. Autoři vycházeli z představy, že lidské myšlení se uskutečňuje koordinovanou manipulací se symboly, jako je např. vyhledávání, porovnávání, slučování, modifikace, nahrazování, rušení. Takovýto systém při řešení úlohy postupoval krok za krokem od počátečního stavu do stavu cílového. Novým prvkem se stalo rozkládání složitějších úloh na jednoduché podúlohy. Řešení má potom tvar stromu. 2 Prolog je logický programovací jazyk. Patří mezi tzv. deklarativní programovací jazyky, ve kterých programátor popisuje pouze cíl výpočtu, přičemž přesný postup, jakým se k výsledku program dostane, je ponechán na libovůli systému.

-4-



Obecně se soudí, že čím méně neúspěšných variant se analyzuje, tím je takový postup inteligentnější. V oblasti umělé inteligence existuje soubor deseti úloh, které jsou považovány jako test při rozhodování, zda je systém obdařen umělou inteligencí nebo ne: • Nalezení optimální varianty na základě daných kritérií • Schopnost učení ze zkušenosti – předcházející zkušenost ovlivňuje rozhodování v budoucnu • Úlohy o podobnosti – nalezení znaků podobnosti • Adaptace (schopnost učení) při změnách okolních podmínek • Schopnost řízení paralelních procesů • Schopnost pokračování i při neúplné informaci • Schopnost abstrakce – zjednodušování problému • Schopnost generalizace – opak abstrakce – konstrukce obecného závěru • Schopnost predikce • Rozvrhování činností – využití schopností systému v jiném prostředí V praxi se obvykle jedná o kombinaci schopností řešit některé z daných úloh, některé jsou řešeny lépe, jiné hůře. Taková kombinace potom určuje výslednou inteligenci systému (to platí i o inteligenci přirozené).

2 Rozdělení umělé inteligence Rozdělit umělou inteligenci na různé obory a podobory je velmi obtížné. Ty jsou totiž velmi často těsně svázány. Pro větší přehlednost je ale vhodné se o nějaké rozčlenění pokusit. Rozdělme tedy tento vědní obor na dvě části. První část budou jednotlivé obory umělé inteligence. Druhou skupinu budou tvořit techniky, které umělá inteligence využívá ve většině oblastí, do kterých proniká.

2.1 Obory umělé inteligence Umělou inteligenci svým rozsahem spadá do mnoha oblastí lidské činnosti. Byla vyvinuta řada technik a přístupů přičemž některé z nich jsou uvedeny v následujícím stručném přehledu. Neuronové sítě Jsou jedním z výpočetních modelů používaných v umělé inteligenci. Je to struktura určená pro distribuované paralelní zpracování dat. Jejím vzorem je chování odpovídajících biologických struktur. Používají se mimo jiné pro rozpoznávání a kompresi obrazu nebo zvuku či předvídání vývoje časových řad (např. burzovních indexů). Genetické algoritmy Používají techniky napodobující evoluční procesy známé z biologie - dědičnost, mutace, přirozený výběr a křížení. Používají se k řešení optimalizačních úloh. Strojové učení Do této oblasti spadají algoritmy a techniky, které umožňují počítačovému systému 'učit se'. Učením v tomto kontextu rozumíme takovou změnu vnitřního stavu systému, která zefektivní schopnost přizpůsobení se změnám okolního prostředí. Strojové učení se využívá například v biomedicínské informatice (tzv. systémy pro podporu rozhodování), při rozlišení nelegálního užití kreditních karet nebo při rozpoznávání řeči a psaného textu. -5-



Expertní systémy Jedná se o počítačové programy, které mají za úkol poskytovat expertní rady, rozhodnutí nebo doporučovat řešení v konkrétní situaci. Jsou navrženy tak, aby mohly zpracovávat nenumerické a neurčité informace a řešit tak úlohy, které nejsou řešitelné tradičními algoritmickými postupy. Mají dvě základní komponenty, které jsou na sobě relativně nezávislé. Řídící mechanismus pro odvozování závěrů a bázi znalostí. Expertních systém může být využíván ke čtyřem různým úkolům. Můžou sloužit jako rádce. V tomto režimu shromažďují a poskytují specializované expertní znalosti. V režimu knihovník pomáhají lidem hledat, organizovat a interpretovat informace potřebné k řešení úloh. Jako asistent zabezpečují řešení některých rutinních úloh a umožňují lidem věnovat se kreativnějším aspektům řešení úkolu. Jako instruktor pomáhají uživatelům získávat potřebné znalosti a řešit úkoly. Rozpoznávání Úloha rozpoznávání spočívá v zařazování objektů, popř. jevů a situací reálného světa, do tříd. Každý z posuzovaných objektů je při dostatečně podrobném popisu jedinečný.

2.2 Techniky umělé inteligence Do této oblasti lze zařadit různé techniky pro ukládání znalostí. Rovněž zde patří algoritmy, které jsou využívány při prohledávání stavového prostoru. 2.2.1 Reprezentace znalostí K reprezentaci znalostí lze využít několika různých přístupů. V následujícím textu jsou uvedeny čtyři postupy, které lze využít pro ukládání informací. Predikátorová logika K ukládání znalostí se využívá predikátorové logiky 1. řádu. Jazyk predikátové logiky se skládá z: 1. logických symbolů.: a) spočetné množiny individuálních proměnných b) výrokových logických spojek: ¬,∨ , ∧ , ⇒, ⇔ c) obecného kvantifikátoru ∀ a existenčního kvantifikátoru ∃ 2. speciálních symbolů.: a) Množiny predikátových symbolu (nesmí být prázdná) b) Množiny konstantních symbolu (muže být prázdná) c) Množiny funkčních symbolu (muže být prázdná) 3. pomocných symbolů, jako jsou závorky „(, [ ,) ,]“ a čárka. Každý predikátorový a funkční symbol má přiřazené celé číslo, které určuje kolik argumentů symbol přijímá (tzv. četnost). Konstanty jazyka chápeme jako funkční symboly četnosti nula. Pro přehlednost budeme značit predikátové symboly velkými písmeny, konstantní a funkční symboly malými písmeny. Proměnné se rovněž budou značit malými písmeny. Funkční a predikátorové symboly lze taky chápat jako slova jazyka. Množina funkčních a predikátorových symbolů představuje slovník, ze kterého s využitím proměnných, logických spojek a kvantifikátorů tvoříme formule, které můžeme považovat za věty. Proto lze množinu všech vět a predikátorových symbolů ztotožňovat s jazykem.

-6-



PŘÍKLAD

Úkolem je popsat pomocí predikátorové logiky uspořádání krychlí na pracovní ploše robota. Máme celkem 3 krychle různé barvy – modrou, zelenou a žlutou. Žlutá krychle leží na pracovní podložce, zelená leží na žluté a modrá na zelené. Definujme objekty a relaci „podpírá“ Relace „podpírá“ má četnost dva, kde první proměnná udává spodní kostku a druhá kostku na ní ležící. V této interpretaci jsou splněny formule Ale například formule

splněna není.

Produkční systémy Produkční systém je tvořen třemi částmi: 1. Souborem produkčních pravidel ve tvaru . Situační část pravidla popisuje podmínku, za které může být pravidlo použito. Pravidla jsou uložena v paměti produkčních pravidel. 2. Pracovní pamětí, též nazývanou báze dat. V ní jsou uložena jak počáteční data, tak i data odvozená. Tato část paměti popisuje okamžitý stav řešené úlohy. 3. Inferenčním strojem, který je také nazýván interpret pravidel. Provádí porovnání dat v pracovní paměti s produkčními pravidly. Vybírá pravidla vhodná k vykonání a provede příslušnou akci. Produkční systém pracuje obvykle v cyklu

.

Sémantické sítě V sémantických sítích jsou znalosti reprezentovány pomocí objektů (entit) a binárních či víceargumentových relací mezi nimi (víceargumentovou relaci lze vždy převést na množinu relací binárních). Sémantické sítě mají přirozenou grafovou reprezentaci. Každý uzel grafu odpovídá jistému objektu a každá hrana odpovídá binární relaci. V sémantických sítích lze výhodně vyjadřovat vztahy množinové inkluze a příslušnosti k množině. Ty umožňují efektivně reprezentovat hierarchické uspořádání objektů. Pak lze přímočaře provádět odvozování specializací (informace se přenášejí od obecnějších typů ke specializovanějším) či generalizací. V jedné sémantické síti mohou být znalosti asociovány z mnoha různých hledisek.

-7-



PŘÍKLAD

Mějme tři osoby – Karla, Marii a Jiřího. Karel dluží Marii a Jiřímu. Definujme relaci půjčka, která dává do vztahu dlužníka a věřitele v tomto pořadí. Potom platí:

Grafický lze vztahy znázornit obrázkem půjčka

Dlužník

is-a

is-a

půjčka 1

půjčka 2

Dlužník

Karel

Věřitel Marie

Věřitel Jiří

Rámce Rámce jsou dalším schématem reprezentace znalostí, které používá k popisování objektů v bázi znalostí. Stejně jako u sémantických sítí jsou informace sdružovány podle podobné sémantiky. Rámce se skládají z položek, které slouží k popisu jednotlivých vlastností objektu. V průběhu užívání rámce nabývají položky konkrétních hodnot. Rámce budeme zapisovat pomocí tabulek. Například JMÉNO RÁMCE: Srub položky: ČÍSLO RÁMCE: 1 IS-A: stavba OKNO: dřevěné TOPENÍ: na dřevo STŘECHA: šindelová Položka ČÍSLO RÁMCE slouží jako identifikátor. Popis položek se skládá z jejího jména (např. okna) a z hodnoty (např. dřevěná). Jména položek odpovídají hranám sémantických sítí, jejich hodnoty uzlům. Rámce však umožňují dále členit jednotlivé položky, což umožňuje zaznamenávat další informace o popisované vlastnosti objektu. Položky dělíme na fasety. Protože jsou položky dále členěny, stává se původní hodnota položky pouze jednou z faset. Její jméno je „hodnota“ položky a do této fasety uložíme příslušný údaj. Tedy například okno má fasetu „hodnota“, která obsahuje údaj „dřevěné“. V tabulce budeme zapisovat položku takto:

-8-



JMÉNO RÁMCE: Srub položky: ČÍSLO RÁMCE: 2 IS-A: stavba OKNO: hodnota: dřevěné TOPENÍ: na dřevo STŘECHA: šindelová V rámci číslo 1 měla tedy každá položka jedinou fasetu, a to právě svoji hodnotu. Vzniku nekonzistence při dědění hodnoty se zabraňuje přidáním fasety „předpokládaná hodnota“. Ta může být buď vyplněna děděním, nebo může být zadána. Existence předpokládaných hodnot umožňuje vyšetřovat položky pouze tehdy, když nastává ve znalostech nesouhlas. Tento způsob odpovídá našim představám o inteligentním chování (např. přijdeme-li ráno k autu, kde jsme večer nechali půl nádrže benzínu, předpokládáme, že benzín v nádrži je). Ke každé fasetě může být přiřazen jeden či několik démonů. Démon je spící procedura, která se aktivuje, nastane-li určitá událost (např. démon „if cleared“ se spouští při mazání obsahu fasety).

-9-

UMĚLÁ INTELIGENCE ARTIFICIAL INTELLIGENCE (AI)

Recommend Documents