Masarykova univerzita Fakulta informatiky PB016 Umělá inteligence Sbírka příkladů Semestr Podzim 2022 Chyby hlašte na: 469088@mail.muni.cz Obsah 1 Úvod do umělé inteligence 1 2 Prohledávání stavového prostoru 7 3 Dekompozice problému, Problémy s omezujícími podmínkami 17 4 Hry a herní strategie 28 5 Výroková logika 41 6 Predikátová logika 50 7 Důkazové systémy a rezoluce 60 8 Neklasické logiky 74 9 Reprezentace a vyvozování znalostí 86 10 Strojové učení 103 11 Neuronové sítě a hluboké učení 115 12 Zpracování přirozeného jazyka 123 i 1 Úvod do umělé inteligence Úvodní kapitola nabízí čtenáři sbírky první setkání s umělou inteligencí. Představuje nejprve Turingův test k určení schopnosti stroje chovat se inteligentně a příklady k zamyšlení nad hranicemi a možnostmi oboru umělé inteligence jako takového (v této jediné části sbírky jsou příklady ponechány bez řešení). Další část pak prezentuje pojem problému a na řadě příkladů ilustruje, jak může volba vhodné datové struktury či strategie k řešení daného úkolu ovlivnit samotnou možnost úkol vyřešit. 1.1 Umělá inteligence a Turingův test V roce 1950 navrhnul Alan Turing tzv. Turingův test (který původně sám nazval „imitační hrou“, viz původní Turingův článek), jež si klade za cíl ověřit schopnost stroje vykazovat inteligentní chování. Alan Turing ve věku 16 let Turing v článku nejprve uvádí, že navrhuje uvážit otázku, zda stroje umí myslet. Jelikož však není snadné definovat, co znamená „myslet“, navrhuje nahradit tuto poněkud vágní otázku jinou, a sice zda „Lze sestrojit počítač, který by byl schopen složit Turingův test?“ Definice 1: Turingův test je navržen jako hra tří hráčů, z nichž jeden je stroj podrobený zkoušce a ostatní dva jsou lidé. V základní variantě Turingova testu jsou do různých místností umístěni A) testovaný stroj, B) člověk, C) rozhodčí. Rozhodčí může komunikovat se zbylými dvěma formou textových zpráv a má za úkol zjistit, který z nich je stroj a který je člověk. Stroj uspěl v Turingově testu, nedokáže-li ho rozhodčí spolehlivě rozeznat od člověka. Složení Turingova testu počítačem vyžaduje zvládnutí několika oblastí oboru. Pro porozumění zpráv a jejich generování je potřeba zpracování přirozeného jazyka (NLP). Pro uchování údajů a vyvozování závěrů je nutné ovládnout reprezentaci a vyvozování znalostí. V neposlední řadě je potřeba metod strojového učení, které umožňují učit se a adaptovat se na změny vnějšího prostředí. 1 Na druhou stranu není pro složení testu nutné zvládnout obory jako robotická manipulace či počítačové vidění, jelikož veškerá komunikace probíhá výhradně textovými zprávami. C A B testující osoba testovaný počítač člověk text text Schéma uspořádání Turingova testu Příklad 1.1.1. Definujte vlastními slovy následující pojmy: a) inteligence, b) umělá inteligence, c) agent, d) racionálnost, e) logické usuzování. Nalezněte možné námitky proti uvedeným definicím a zpřesněte se je. Příklad 1.1.2. Jsou reflexy racionální? Jsou inteligentní? Zdůvodněte. Příklad 1.1.3. Do jaké míry jsou následující počítačové systémy příklady umělé inteligence? a) Čtečka čárových kódů v supermarketu. b) Internetové vyhledávače. c) Hlasové zadávání příkazů telefonu. d) Síťové směrovací algoritmy, které dynamicky reagují na stav sítě. Příklad 1.1.4. Přečtěte si původní článek Alana Turinga Computing Machinery and Intelligence. Turing v sekci 6 ve článku rozebírá různé námitky vznesené vůči Turingovu testu. Které z námitek jsou stále platné? Napadnou vás nové námitky, které vzešly z pozdějšího vývoje v oboru? Příklad 1.1.5. Upravíme-li Evansův program pro řešení problémů s geometrickou analogií, aby získal v standardním IQ testu hodnotu 200, jednalo by se o program inteligentnější než člověk? Vysvětlete. Příklad 1.1.6. Alan Turing ve své práci představil seznam věcí, které by stroje nemusely nikdy umět: být milé, být nápadité, být krásné, být přátelské, být iniciativní, mít smysl 2 pro humor, rozeznat správné od špatného, dělat chyby, zamilovat se, vychutnat si jahody se šlehačkou, okouzlit někoho, poučit se ze zkušenosti, používat správná slova, přemýšlet samy o sobě, mít chování rozmanité jako člověk, provést něco skutečně nového. Kterých se již podařilo dosáhnout? Které jsou v principu dosažitelné počítačem? Které z nich jsou stále problematické, protože vyžadují vědomé mentální stavy? Příklad 1.1.7. Argument čínského pokoje je myšlenkový experiment, který se snaží prokázat, že počítače nemohou mít „mysl“, „chápání“ či „vědomí“, a to nezávisle na tom, jak inteligentní chování vykazují. Nastudujte si o argumentu čínského pokoje více. Znamená vyvrácení argumentu čínského pokoje, že vhodně naprogramované počítače mohou mít mentální stavy? Plyne z přijetí argumentu, že počítače mentální stavy mít nemohou? 1.2 Řešení problémů V této sekci se poprvé setkáme s některými problémy a úvodem do strategií, které lze uplatnit při jejich řešení. K některým z nich se budeme v dalších kapitolách vracet při probírání konkrétních metod řešení problémů (jako například heuristické prohledávání). Problémem rozumíme zadání množiny konfigurací (např. přiřazení čísel volným políčkům sudoku), mezi nimiž hledáme konfigurace, které splňují konkrétní vlastnosti (např. vlastnost, že je sudoku vyplněno správně). Alternativou k hledání konfigurací splňujících nějakou vlastnost je hledání konfigurací, které jsou v jistém smyslu „nejlepší“. V takovém případě hovoříme o optimalizačním problému. Co přesně rozumíme problémem, může být navíc v konkrétním kontextu blíže upřesněno. Definice 2: Při řešení optimalizačního problému je cílem nalézt mezi jeho konfiguracemi takovou, která je mezi všemi ostatními nejlepší podle předem daného kritéria. Plánujeme-li si semestr tak, abychom získali co nejvíce kreditů a zároveň nám zůstalo co nejvíce volného času na své koníčky a kamarády, řešíme optimalizační problém. Naopak snažíme-li se naskládat nákup do ledničky tak, aby se dala zavřít, problém optimalizační neřešíme, protože jsme spokojeni s jakýmkoliv řešením, které nám umožní dovřít dveře led- ničky. Při řešení problémů hraje důležitou roli počet prohledávaných konfigurací. Přirozenou snahou je tento počet co nejvíce zredukovat, čehož lze dosáhnout využitím znalostí o problému a vhodnou volbou datové struktury. Příklad. Uvažte problém n dam. V problému n dam je rozmisťováno n dam na šachovnici o rozměru n×n. Řešením jsou taková rozmístění (všech dam), v nichž se žádná dvojice dam neohrožuje na řádku, ve sloupci ani diagonálně. a) Spočtěte počet různých konfigurací problému, tj. počet různých rozmístění dam na šachovnici. 3 b) Navrhněte datovou strukturu reprezentující konfigurace problému. c) Navrženou datovou strukturu upravte tak, aby svým návrhem omezovala počet různých konfigurací, ale ne počet potenciálních řešení. Vyjděte z povahy problému a promítněte požadavky na řešení problému do návrhu datové struktury. Spočítejte nový počet konfigurací. a) Každá dáma může být umístěna na jednu z n × n = n2 pozic. Pro n dam tedy celkově získáme n2 · . . . · n2 n = n2n rozmístění. Pro 8 dam máme 816 ≈ 2, 8 · 1014 konfigurací. b) Na reprezentaci souřadnic jedné dámy lze použít dvojici (x, y). Konfiguraci pak reprezentuje pole n takových dvojic [(x1, y1), . . . , (xn, yn)]. c) Jistě nelze umístit více dam na jedno políčko šachovnice. Můžeme tedy předpokládat unikátnost součadnic a místo pole použít množinu souřadnic {(x1, y1), . . . , (xn, yn)}. Počet konfigurací v takovém případě je n2 · (n2 − 1) · . . . · (n2 − n + 1) = (n2)! (n2−n)! . Konkrétně pro 8 dam je to 64 · 63 · . . . 57 ≈ 1, 8 · 1014 konfigurací. V návrhu lze jít ještě dále. Z povahy problému víme, že v každém sloupci bude právě jedna dáma – jinak by v nějakém sloupci byly alespoň dvě a ty by se vzájemně ohrožovaly. Dámám v seznamu lze tedy postupně přiřadit x-ovou souřadnici 1 až n: [(1, y1), . . . , (n, yn)] a celý seznam zredukovat na seznam pouze y-ových souřadnic: [y1, . . . , yn]. Pokud nepřipustíme opakování hodnot v seznamu (čili více dam na řádku), omezíme počet možných konfigurací na n · (n − 1) · . . . · 1 = n!. Pro 8 dam je to 8! = 40320 konfigurací. Příklad demonstruje zásadní vliv promítnutí znalostí o problému do přístupu k jeho řešení. Zatímco naivní řešení problému n dam vyžaduje pro n = 8 prohledávání prostoru přibližně 2, 8 · 1014 konfigurací, vhodnou úpravou strategie lze číslo redukovat na 40320. Už pro relativně malá čísla n tedy volba strategie rozhoduje o tom, zda je problém prakticky řešitelný či ne. Příklad 1.2.1. Pro uvedné problémy spočítejte počet různých konfigurací, tj. potenciálních řešení. Pro každý problém navrhněte datovou strukturu pro reprezentaci konfigurací problému. a) Sudoku. Uvažujte obecné sudoku n × n s k hodnotami zadanými. b) Problém přiřazení. V problému přiřazení je dána množina n úkolů T, množina n pracovníků W a cenová funkce c : T × W → R, která určuje náklady na vykonání úkolů jednotlivými pracovníky, tj. cena práce pracovníka w na úkolu t je dána jako c(t, w). Cílem je rozdělit úkoly mezi pracovníky (jeden úkol na jednoho pracovníka) tak, aby celková cena práce byla co nejmenší. c) Problém batohu. Je zadána množina n položek 1, . . . , n o hmotnostech w1, . . . , wn a hodnotách v1, . . . vn a maximální nosnost batohu W. Cílem je z položek vybrat takové, 4 aby součet jejich hmotností nepřekročil W a zároveň byl co nejvyšší. Příklad 1.2.2. Uvažte problém žádné tři v řadě. V tomto problému je zadána mřížka rozměrů n × n (kde n ∈ N) a cílem je zjistit, kolik do ní lze umístit bodů tak, aby žádné tři body neležely v jedné přímce. Na mřížce 3 × 3 lze rozmístit maximálně 6 bodů (zvolené body jsou vyplněny modře). Uvedené rozmístění nesplňuje požadavek, aby tři body neležely v jedné přímce. a) Spočtěte počet různých konfigurací problému, tj. různých rozmístění bodů (i těch nesplňujících požadavek zadání). b) Navrhněte datovou strukturu reprezentující konfigurace problému. c) Navrženou datovou strukturu upravte tak, aby svým návrhem omezovala počet různých konfigurací, ale ne počet potenciálních řešení. Vyjděte z povahy problému a promítněte požadavky na řešení problému do návrhu datové struktury. Spočítejte nový počet konfigurací. d)* Proveďte asymptotické srovnání počtu konfigurací v naivním a vylepšeném řešení. e)* Ještě dále vylepšete návrh datové struktury, aby byl počet konfigurací asymptoticky menší než vzorové řešení části c). Příklad 1.2.3. Které z následujících problémů jsou problémy optimalizační? Zdůvodněte. a) Problém n dam. b) Sudoku. c) Problém přiřazení. d) Žádné 3 v řadě. Příklad 1.2.4. Implementujte řešení problému n dam využitím naivního přístupu a přístupu omezujícího počet prohledávaných konfigurací. Experimentálně zjistěte časy nalezení všech řešení pro různá malá n oběma způsoby. Porovnejte s dříve vypočítaným prohledávaným počtem konfigurací. Lze pozorovat úměru mezi časem výpočtu a počtem konfigurací? Příklad 1.2.5. Implementujte řešení problému žádné 3 v řadě využitím naivního přístupu a přístupu omezujícího počet prohledávaných konfigurací. Experimentálně zjistěte 5 časy nalezení všech řešení pro různá malá n oběma způsoby. Porovnejte s dříve vypočítaným prohledávaným počtem konfigurací. Lze pozorovat úměru mezi časem výpočtu a počtem konfigurací? 6 2 Prohledávání stavového prostoru V předchozí kapitole jsme si vyzkoušeli, jakými způsoby se dá řešit několik klasických problémů, které spadají do oblasti umělé inteligence. Obecně samozřejmě existuje velké množství různých druhů problémů, a tedy i strategií jak je řešit. Často se ale dají využít některé známé univerzální postupy. V této kapitole si formálně představíme jednu z takových strategií, a to prohledávání stavového prostoru. Ukážeme si jak správně problémy formulovat, představíme si několik různých prohledávacích algoritmů, a zaměříme se i na to, v čem se jednotlivé algoritmy liší. 2.1 Formulace problému Abychom problémy mohli řešit (algoritmicky) pomocí prohledávání, je potřeba je nejdříve formálně zadefinovat. Vhodná formální definice problému se pak obvykle skládá z několika hlavních komponent, kterými jsou • iniciální stav, • přechodové akce (a případně jejich cena), • cílová podmínka. Zmíněné komponenty nám dohromady implicitně zadávají takzvaný stavový prostor problému, tedy množinu všech stavů dosažitelných z iniciálního stavu. Tyto stavy můžeme interpretovat jako vrcholy grafu, přechodové akce pak určují hrany daného (přechodového) grafu. Díky této interpretaci můžeme řešit různorodé problémy pomocí obecných algoritmů grafového prohledávání. Řešení problému je obvykle posloupnost přechodových akcí, která nás dostane z iniciálního stavu do cílového, hledáme tedy cestu v přechodovém grafu. Zajímáli nás optimální řešení, hledáme obvykle takovou cestu, která je nejkratší (nebo nejlevnější) ze všech řešení. Příklad. Uvažte problém n dam z minulé kapitoly. Nejdříve zadefinujte problém formálně. Určete a) iniciální stav, b) přechodové akce (a případně jejich cenu), c) cílovou podmínku. Až budete mít tuto implicitní definici přechodového grafu, zamyslete jak v takovém případě vypadá graf explicitně (jaká je množina vrcholů a množina hran). Problém můžeme zadefinovat například následovně. a) Iniciální stav je prázdná hrací plocha. b) Přechodová akce je přidání dámy na hrací plochu, pokud ta již neobsahuje n dam. Každá akce má jednotkovou cenu. 7 c) Cílová podmínka vyžaduje, aby bylo na ploše všech n dam tak, aby se neohrožovaly. Stavový prostor v takovém případě tvoří množina všech rozestavení 0 až n dam na hrací ploše. Přechodová hrana je mezi stavy s, t právě tehdy, když s obsahuje o jednu dámu méně než t a zároveň t má všechny kromě jedné dámy na stejných pozicích jako s. Příklad 2.1.1. Zadefinujte formálně problém 8-posunovačky z přednášky. Zamyslete se i nad tím, jak bude vypadat přechodový graf. Příklad 2.1.2. Aplikujeme-li na číslo 4 sekvenci operací faktoriál, odmocnina a dolní celá část, můžeme získat libovolné přirozené číslo1 . Například, číslo 5 lze získat jako ⌊ (4!)!⌋ = 5 Formulujte tento problém formálně a opět se zamyslete i nad tím, jak bude vypadat přechodový graf. Liší se nějak stavový prostor od předchozích příkladů? Příklad 2.1.3. Uvažte zjednodušený problém hledání letecké trasy mezi světovými hlavními městy, který musí řešit webové stránky aerolinek. Předpokládejte, že zákazníci hledají takovou (rozumnou) trasu, která je nejlevnější. Zamyslete se, jak byste řádně formulovali tento problém. Příklad 2.1.4. Uvažujte situaci, kdy se snažíte naplánovat dovolenou po hlavních městech Evropy. Cesta bude začínat i končit v Praze, nejste nijak časově omezeni a máte v úmyslu procestovat právě všechna evropská hlavní města (některá klidně vícekrát). Jak byste řádně formulovali tento problém? 2.2 Algoritmy prohledávání Existuje mnoho různých strategií jak prohledávat stavový prostor. Výběr vhodného algoritmu závisí na typu problému, našich požadavcích na průběh výpočtu a našich případných dodatečných znalostech o problému. Pokud o problému nemáme žádnou doplňující znalost, která by nám ulehčila práci, obvykle volíme některý z algoritmů neinformovaného prohledávání. Naopak, máme-li nějakou dodatečnou informaci, můžeme ji využít například jako základ heuristiky pro některý z algoritmů informovaného prohledávání. Obě tyto skupiny si představíme v následujících sekcích. Jak už jsme naznačili, existuje velké množství strategií, ze kterých můžeme vybírat. Mezi nejdůležitější vlastnosti, podle kterých můžeme nejrůznější algoritmy porovnávat a hodnotit, patří následující čtyři. 1 Donald Knuth, 1964 8 Definice 3: • Algoritmus je úplný, jestliže nalezne řešení vždy, když existuje. • Algoritmus je optimální, pokud platí, že nalezne-li nějaké řešení, je toto řešení nejlepší ze všech (například z pohledu ceny nebo délky cesty). • Časová složitost algoritmu udává maximální čas potřebný k vyřešení problému. • Prostorová složitost algoritmu udává maximální množství paměti potřebné k vyřešení problému. Poznamenejme, že časovou i prostorovou složitost obecně uvažujeme asymptotickou, a to v nejhorším případě. V některých případech se však může hodit uvažovat i např. složitost očekávanou. Dále, řešíme-li, zda je algoritmus optimální, je třeba myslet na metriku, kterou uvažujeme (často je jasná z kontextu). Některé algoritmy mohou být optimální z pohledu hloubky/délky řešení (tedy uvažujeme délku cesty v grafu), jiné zase z pohledu obecné ceny řešení (důležité pro ohodnocené grafy). Pokud uvažujeme verzi prohledávání, kde hledáme řešení více, pak optimalitu můžeme intuitivně chápat tak, že pro každá dvě nalezená řešení algoritmus nalezne dříve to lepší. Při diskusi o složitosti algoritmů je vždy velmi důležité si uvědomit, vůči čemu ji vyjadřujeme. Jelikož prohledávaný stavový prostor většinou reprezentujeme implicitně (pomocí iniciálního stavu a přechodových akcí), k vyjádření složitosti algoritmů používáme následující metriky. Definice 4: • Faktor větvení (branching factor) b je maximální počet následníků kteréhokoli uzlu. • Hloubka cíle (goal depth) d je délka nejkratší cesty z iniciálního stavu do některého cílového uzlu. • Maximální hloubka (maximal depth) m je délka nejdelší cesty v grafu. Příklad. Uvažte přechodový graf pro problém n dam, který jsme si definovali v ilustrativním příkladu v Podsekci 2.1. Budeme pracovat s konkrétním grafem pro n = 8. Určete pro něj a) faktor větvení b, b) hloubku cíle d, c) maximální hloubku m. a) Na prázdnou plochu můžeme umístit dámu kdekoli, tedy iniciální stav má 64 následníků. Žádný jiný stav tolik následníků mít nemůže. Proto b = 64. b) K řešení se nemůžeme dostat před přidáním 8 dam. Zároveň existuje rozmístění 8 dam takové, které splňuje cílovou podmínku. Proto d = 8. 9 c) Maximum dam, které můžeme postupně položit je 8, a tedy m = 8. Příklad 2.2.1. Zamyslete se a pokuste se určit faktor větvení b, hloubku cíle d a maximální hloubku m i pro přechodový graf problému 8-posunovačky z příkladu v Podsekci 2.1. 2.3 Neinformované prohledávání V případě, že o problému nemáme žádnou další informaci (kromě těch z formální definice), jsme obecně nuceni graf prohledávat takzvaně „slepě“. Tyto strategie prohlédavají stavový prostor prostým expandováním uzlů a testováním cílové podmínky. Různé algoritmy se liší například v tom, v jakém pořadí uzly expandují. Nejznámějšími strategiemi jsou prohledávání do šířky (BFS) a prohledávání do hloubky (DFS). S těmito algoritmy jste se jistě hlouběji setkali již v rámci některého předchozího předmětu. Prohledávání do šířky je jednoduchá strategie, kde nejprve expandujeme iniciální uzel grafu, poté všechny jeho následníky, poté všechny jejich následníky, a tak dále. Obecně platí, že veškeré uzly v určité vzdálenosti („úrovni“) od iniciálního uzlu jsou prozkoumány předtím, než expandujeme uzly v úrovni o jedna vyšší. Prohledávání do hloubky naopak nejdříve vždy expanduje jen prvního následníka každého uzlu. Tímto způsobem intuitivně prozkoumá vždy „aktuálně nejhlubší“ neprozkoumaný uzel. Jakmile expanduje listový uzel, vrací se zpět pomocí backtrackingu a prozkoumává stejným způsobem další dosud nenavštívené následníky. Mezi další algoritmy, se kterými budeme pracovat, patří prohledávání do hloubky s limitem, prohledávání podle ceny (uniform-cost search) a prohledávání s postupným prohlubováním (IDS). Jistě je znáte z přednášky. Příklad. Mějme následující graf, který reprezentuje stavový prostor problému. Uvažujte situaci, kdy postupně spustíme prohledávací algoritmy BFS a DFS ze stavu A. V jakém pořadí dané algoritmy navštíví jednotlivé stavy? Máte-li na výběr více následníků, postupujte abecedně. 10 A B CD EF GHI JK a) BFS: A - B - E - F - C - D - G - H - I - J - K b) DFS: A - B - C - D - E - F - G - H - I - J - K Příklad 2.3.1. Uvažujte stejný strom jako v předchozím příkladě. Jak se změní pořadí uzlů, spustíme-li tentokrát oba algoritmy z uzlu G? Příklad 2.3.2. V předchozích příkladech jste si vyzkoušeli simulaci algoritmů na stromu. Uvažte nyní následující graf. Určete v jakém pořadí algoritmy BFS a DFS navštíví jednotlivé stavy, spustíme-li je nejdříve ze stavu A, a poté také z B. A B C D E F G H I Opět, máte-li na výběr více následníků, postupujte abecedně. Příklad 2.3.3. Uvažte opět graf z předchozícho příkladu. Nechť spustíme prohledávání do hloubky z uzlu I a nechť cílový uzel je F. Uvažujte, že výpočet skončí nalezením prvního řešení. a) Je alogritmem nalezené řešení optimální? b) Co kdybychom namísto DFS použili DFS s limitem l = 4? 11 c) A jak by tomu bylo při použití prohledávání s postupným prohlubováním (IDS)? Příklad 2.3.4. Mějme opět situaci, kdy prohledáváme výše uvedený graf. Tentokrát nechť je iniciální stav A a cílový stav F. Jako algoritmus zvolíme DFS s limitem. Není-li řečeno jinak, uvažujte, že výpočet skončí nalezením prvního řešení. a) Jaký je nejvyšší limit, pro který algoritmus nalezne optimální řešení? b) Od jaké hodnoty limitu algoritmus nalezne vždy stejné řešení? c) Uvažujte scénář, kdy prohledáváme celý graf (výpočet neskončí prozkoumáním cílového stavu). Od jaké hodnoty limitu bude výpočet pro DFS s limitem probíhat zcela stejně jako pro klasické DFS? Příklad 2.3.5. Vymyslete příklady přechodových grafů (případně přímo problémů) takových, že: a) Prohledávání do hloubky nikdy nenalezne řešení. b) Prohledávání do hloubky nalezne řešení dříve než prohledávání do šířky. c) Prohledávání do hloubky bude procházet uzly ve stejném pořadí jako prohledávání do šířky. Každou odrážku řešte zvlášť. Příklad 2.3.6. Rozhodněte o pravdivosti následujících tvrzení, své odpovědi odůvodněte. Můžete předpokládat že prohledáváme strom s konečným faktorem větvení, kladnou cenou přechodů a alespoň jedním dosažitelným cílovým uzlem. a) Prohledávání do hloubky s limitem je úplné. b) Prohledávání s postupným prohlubováním má stejnou prostorovou složitost jako prohledávání do hloubky. c) Prohledávání s postupným prohlubováním má horší časovou složitost než prohledávání do šířky. d) Prohledávání do šířky je optimální. Příklad 2.3.7. Popište stavový prostor takový, že prohledávání s postupným prohlubováním má daleko větší složitost než prohledávání do hloubky (jako například O(n2 ) vs. O(n)). Příklad 2.3.8. Uvažte stavový prostor, kde iniciální stav je číslo 1 a každý stav k má dva následníky – čísla 2k a 2k + 1. a) Načrtněte část stavového prostoru pro stavy 1 až 15. b) Předpokládejte, že cílový stav je 11. Určete v jakém pořadí algoritmy BFS, DFS s limitem l = 3 a prohledávání s postupným prohlubováním navštíví jednotlivé stavy. c) Pokuste se nalézt algoritmus, který vypíše řešení bez jakéhokoli prohledávání. Využijte znalostí o doméně a formulaci problému. 2.4 Heuristické prohledávání Máme-li o problému nějakou dodatečnou informaci, často ji můžeme využít k efektivnějšímu prohledávání stavového prostoru. Konkrétně se budeme zabývat strategiemi, které při výběru 12 uzlů k expandování využívají informaci o (odhadu) blízkosti stavů k cíli. Tyto algoritmy obvykle expandují nejdříve ty uzly, které se jeví (v určitém smyslu) jako nejslibnější. Souhrně se tyto prohledávácí strategie označují jako best-first search. Informaci o tom, jak přínosný se jeví daný uzel (jaký je odhad jeho ceny), nám dává takzvaná ohodnocovací funkce f(n). V průběhu výpočtu si držíme prioritní frontu uzlů uspořádaných dle této ceny a expandujeme stav s aktuálně nejmenší cenou. Jako komponentu při odhadu ceny většina algoritmů používá heuristickou funkci h(n). Heuristika může například odhadovat cenu cesty z uzlu k cíli. Aby byl tento odhad užitečný, některé algoritmy kladou na použité heuristiky podmínky. Jednou z nich je takzvaná přípustnost. Intuitivně, heuristický odhad ceny cesty z uzlu do cíle nesmí být větší než cena opravdová. V jistém ohledu silnější podmínkou je pak konzistence heuristiky. Definice 5: 1. Heuristická funkce h je přípustná pokud pro všechny stavy n platí 0 ≤ h(n) ≤ h′ (n), kde h′ (n) je skutečná cena cesty ze stavu n do cíle. 2. Heuristická funkce h je konzistentní (neboli monotonní) pokud pro každý stav n a každého jeho následníka m platí, že h(n) ≤ c(n, m)+h(m), kde c(n, m) je cena přechodu z n do m. V několika dalších demonstrativních příkladech budeme pracovat s následujícím ohodnoceným grafem reprezentujícím stavový prostor. A B C D E F G 100 50 60 80 20 30 0 40 35 30 50 60 30 35 30 55 30 Pro daný graf platí, že ohodnocení přechodů jsou zobrazena modře, například A-B má cenu 40. Červenou barvou pak jsou pak zaznačeny hodnoty heuristiky pro každý stav, například heuristická hodnota stavu A je 100. Počáteční stav je A, cílový stav je G. 13 Stručně si představme dvě konkrétní strategie informovaného prohledávání. První je známa jako greedy best-first search, neboli hladové heuristické hledání. Druhý algoritmus se pak nazývá A*. Obě strategie mají společné to, že si v průběhu výpočtu udržují prioritní frontu s uzly k expandování, uspořádanými podle hodnoty f(n). V čem se algoritmy liší, je vzorec, pomocí kterého počítají f(n). Tento rozdíl se zdá být malý, ale celkově jsou jak úvahy za oběma algoritmy, tak i jejich vlastnosti, velmi odlišné. Greedy best-first search jednoduše ohodnocuje uzly jen podle hodnoty heuristiky, f(n) = h(n). Algoritmu se říká hladový, protože se v každém kroku snaží dostat tak „blízko“ k cíli, jak jen to jde. To vede například k tomu, že algoritmus není obecně úplný ani optimální. A* je sofistikovanější algoritmus. Kombinuje užitečné vlastnosti Dijkstrova algoritmu (doporučujeme si zopakovat) a zároveň rychlost heuristického prohledávání. Při ohodnocování uzlu bere kromě heuristiky v potaz i dosavadní cenu cesty, kterou jsme se do uzlu dostali, označme ji g(n). Ohodnocovací funkce má tedy tvar f(n) = g(n) + h(n). Použijeme-li heuristiku s vhodnými vlastnostmi, algoritmus je pak garantovaně optimální. Příklad. Uvažujte situaci, kdy prohledáváme výše uvedený přechodový graf pomocí hladového heuristického prohledování. a) V jakém pořadí navštíví algoritmus jednotlivé stavy? b) Jak bude vypadat výsledná nalezená cesta? Je toto řešení optimální? Pořadí stavů je A-B-E-G, což je v tomto případě zároveň i výsledná cesta. Toto řešení ovšem optimální není. Zkuste se zamyslet nad lepší cestou. Příklad. Nyní uvažujte prohledávání daného grafu pomocí algoritmu A*. a) Je heuristika zvolená v daném příkladu přípustná? A je konzistentní? b) V jakém pořadí navštíví A* jednotlivé stavy? c) Jak bude vypadat výsledná nalezená cesta? Liší se od cesty nalezené hladovým algoritmem? Je řešení tentokrát optimální? a) Heuristika je přípustná, jelikož pro každý stav je hodnota heuristiky menší nebo rovna ceně cesty do cílového stavu. Není ale konzistentní, jelikož h(A) > c(A, C) + h(C). b) Pořadí stavů při výpočtu je A-B-C-F-G. c) Výsledná cesta má tvar A-C-F-G, a tedy se liší od cesty nalezené hladovým algoritmem. Můžete si ověřit, že toto řešení je opravdu optimální. 14 Příklad 2.4.1. Uvažme následující stavový prostor. Iniciální stav je B, cílový stav je D. Ohodnocení přechodů jsou opět zobrazena modře, hodnoty heuristiky červeně. Simulujte výpočet hladového heuristického algoritmu. a) V jakém pořadí navštíví algoritmus jednotlivé stavy? b) Jak bude vypadat výsledná nalezená cesta? Je optimální? A B C D E F G H 20 25 18 0 17 12 20 18 10 11 30 8 13 15 5 8 13 12 Příklad 2.4.2. Opět simulujte prohledávání grafu z předchozího příkladu, tentokrát ale pomocí algoritmu A*. a) Je heuristika zvolená v daném příkladu přípustná? A je konzistentní? b) V jakém pořadí navštíví A* jednotlivé stavy? c) Jak bude vypadat výsledná nalezená cesta? Příklad 2.4.3. Uvažujte, že věž se může na šachovnici pohybovat o jakýkoli počet políček po přímce, vertikálně nebo horizontálně, ale nemůže přeskakovat ostatní figurky. Je Manhattanská vzdálenost přípustná heuristika pro problém posunutí věže z políčka A na políčko B v co nejmenším počtu tahů? Svou odpověď odůvodněte. Příklad 2.4.4. Rozhodněte o pravdivosti následujících tvrzení. Odpovědi zdůvodněte. Pokud není řečeno jinak, uvažujte konečný faktor větvení, cenu přechodů vyšší než nějaké kladné ϵ a alespoň jeden dosažitelný cílový uzel. a) Hodnota přípustné heuristiky nikdy nepřevyšuje zbylou opravdovou cenu (vzdálenost) do cíle. b) Algoritmus heuristického prohledávání, jehož fronta je uspořádána dle hodnoty f(n) = g(n)+h(n) je úplný i optimální, pokud používá přípustnou heuristiku a zároveň ohodnocení uzlů f(n) monotónně stoupá po jakékoliv cestě do cíle. c) Prohledávání podle ceny je jak úplné, tak i optimální, pokud cena cesty nikdy neklesá. d) Hladové heuristické prohledávání je jak úplné, tak i optimální, pokud je použitá heuristika přípustná a cena cesty nikdy neklesá. 15 Příklad 2.4.5. Která z následujících tvrzení jsou pravdivá? Odpovědi zdůvodněte. a) Prohledávání do hloubky vždy expanduje alespoň tolik uzlů jako A* s přípustnou heuristikou. b) h(n) = 0 je přípustná heuristika pro 8-posunovačku. c) Prohledávání do šířky je úplné i pokud jsou povoleny přechody s nulovou cenou. Uvažujeme konečný faktor větvení. d) Součet několika přípustných heuristik je opět přípustná heuristika. Příklad 2.4.6. Uvažujte prohledávání (konečného) stavového prostoru algoritmem A* s konzistentní heuristikou. Nechť existuje jeden dosažitelný cílový uzel ng a nechť C∗ je cena optimálního řešení. a) Může se stát, že algoritmus neexpanduje některý uzel n1, pro který platí f(n1) < C∗? b) Může algoritmus prohledat jen a pouze uzly n takové, že f(n) < C∗? c) Můžeme před spuštěním výpočtu určit, kolik uzlů m takových, že f(m) > C∗, bude expadováno? Příklad 2.4.7. Mějme následující stavový prostor. Ohodnocení přechodů jsou jako obvykle zobrazena modře, hodnoty heuristiky červeně, cílový stav je A. Simulujte prohledávání pomocí greedy best-first tree-search algoritmu ze stavu C. Jaké bude pořadí prohledávaných uzlů? A B CD 0 18 1510 18 9 5 Poznámka – tree-search verze prohledávacích algoritmů neřeší cykly. Příklad 2.4.8. Jsou následující tvrzení ohledně heuristik pravdivá? Své odpovědi dokažte. a) Každá přípustná heuristika je i konzistentní. b) Každá konzistentní heuristika je i přípustná. Příklad 2.4.9. Rozhodněte a dokažte, zda jsou následující tvrzení o prohledávacích algoritmech pravdivá. a) BFS je speciální případ prohledávání podle ceny (uniform-cost search). b) Algoritmy DFS, BFS i uniform-cost search jsou speciálními případy best-first tree search. c) Prohledávání podle ceny je speciální případ A* prohledávání. 16 3 Dekompozice problému, Problémy s omezujícími pod- mínkami V této kapitole prozkoumáme aplikace prohledávání grafů, kterému jsme se věnovali v kapitole předchozí. Konkrétně si ukážeme, co je AND/OR graf a na jaké široké spektrum problémů ho lze aplikovat – od problémové dekompozice, přes hry až po modelování logických výrazů. Ve druhé části se budeme zabývat deklarativním přístupem k programování, který umí být překvapivě elegantní a stručný. Zjistíme spolu, že na jeho pozadí se však opět vykonává prohledávání stavového prostoru, které pro mnoho příkladů funguje překvapivě dobře, jindy však narazíme na hranice efektivity. 3.1 Dekompozice problému a AND/OR grafy Definice 6: AND/OR graf je orientovaný graf s vrcholy typu AND nebo OR (souhrnně zvané vnitřní) a sérií koncových vrcholů t1, t2, . . . , tn. Typ vnitřního vrcholu nejčastěji interpretujeme tak, že k vyřešení OR uzlu je potřeba vyřešit kterýkoliv z následníků (potomků). V případě AND uzlu musíme vyřešit všechny následníky (potomky). Koncové vrcholy pak reprezentují dále nedělitelné podproblémy, ať už neřešitelné či se známým řešením. V jiném kontextu lze koncové vrcholy chápat jako splněné či nesplněné. Příklad. Rozdělení na vnitřní a koncové uzly v definici není potřeba. Zamyslete se, jak ji upravit tak, abychom s pomocí vnitřních vrcholů mohli modelovat i uzly koncové. Stačí chápat AND uzel bez následníků jako splněný (řešitelný), zatímco vrchol typu OR bez následníků jako triviálně nesplněný. Listům bychom tedy dali typ AND nebo OR podle toho, zda je chceme mít splněné či nikoliv. Jako příklad aplikace takového přístupu na problémovou dekompozici (a tedy i příklad AND/OR grafu) si uvedeme strategii řešení neurčitého integrálu. Postup, který si tu budeme spolu ilustrovat, se v nějaké míře nachází u většiny matematických symbolických řešičů – jako je například WolframAlpha. Na následujícím obrázku značíme AND vrcholy elipsou, zatímco OR vrcholy obdélníkem. Koncové uzly necháváme bez označení. Vrcholy s jediným následníkem mohou být AND i OR bez vlivu na sémantiku (význam) grafu – my v takovém případě volíme konzistentně obdélníkové ohraničení. OR vrcholy zde tedy reprezentují možné přístupy k řešení, kdežto AND uzel rozděluje problém na sadu podproblémů, které je třeba vyřešit všechny. V některých případech, kde je orientace hran grafu zřejmá (například z rozmístění vrcholů), se šipky v grafu vynechávají. 17 x4 (1−x2)2 dx sin4 y cos4 y dy x = siny tan4 y dycot−4 y dy 32 z4 (1+z2)(1−z2)4 dz trig. identity trig.identity z = tan y 2 dz z4(1+z2) z4 1+z2 dz z = cot y z = tan y −1 + z2 + 1 1+z2 dz divide z2 dz−dz dz 1+z2 dz dw z = tan w Častěji budeme vídat AND/OR grafy v kontextu tahových her dvou hráčů – například piškvorek. Omezíme se na hry s perfektní informací, což stručně znamená, že vždy známe úplný aktuální stav hry. Mimo piškvorek toto splňují například šachy či go. Uvědomme si, že tímto způsobem bychom nemohli modelovat třeba poker či kostky. Na následujícím obrázku používáme pro přehlednost malé kolečko pod vrcholy, které jsou 18 typu AND. Uzly OR a koncové vrcholy jsou neoznačené, neboť jsou rozlišitelné z kontextu. Takové značení můžeme potkat i později tam, kde by prvně dohodnuté znepřehledňovalo nákresy. ⃝ ⃝ X ⃝ X X ⃝ ⃝ ⃝ X ⃝ X X ⃝ ⃝ ⃝ X ⃝ X X ⃝ ⃝ X ⃝ X ⃝ X ⃝ X ⃝ ⃝ X ⃝ X X ⃝ ⃝ ⃝ X ⃝ X X X X ⃝ ⃝ ⃝ X ⃝ X X ⃝ ⃝ ⃝ X ⃝ X X X X ⃝ ⃝ X ⃝ X ⃝ X X ⃝ ⃝ X ⃝ X ⃝ X ⃝ X ⃝ ⃝ X ⃝ X ⃝ X ⃝ X ⃝ ⃝ X ⃝ X ⃝ X V našem AND/OR grafu jsme vhozeni do již rozehrané piškvorkové partie na omezeném hracím poli 3 × 3. Na tahu je hráč kreslící kolečka a zvažuje všechny své možné tahy. Stačí mu, aby pouze jeden z jeho tahů byl výherní (či alespoň končící remízou) – a tedy vrchol grafu reprezentující aktuální stav hracího pole je typu OR. O úroveň níže zvažujeme soupeřovu odpověď na náš tah. Nás soupeř je velmi dobrý hráč a nedělá chyby, proto potřebujeme, aby žádná z jeho reakcí nevedla k naší prohře. Všechny uzly ve druhé úrovni (reprezentující odehrání jednoho našeho tahu) jsou proto typu AND. Při delší hře dvou hráčů se i nadále typy uzlů střídají podle vzdálenosti od počátku – jsme-li na tahu my, jsou typu OR, a naopak typu AND, je-li na tahu protihráč. Po pečlivé analýze námi vykresleného AND/OR grafu zjišťujeme, že za předpokladu, že náš soupeř neudělá chybu, prohráli jsme. Každý z AND uzlů na druhé úrovni je nesplněný, neboť alespoň jeden jeho následníků značí naši prohru. Startovní OR vrchol reprezentující aktuální stav hracího pole je tedy také nesplněný, ačkoliv by bylo možné (s nedokonalým soupeřem) dostat se do stavu remízy. Uvedený příklad je skutečně hodně jednoduchý. V první řadě nevede žádná možnost k naší výhře, v nejlepším případě můžeme doufat jen v remízu. Stojí za zmínku, že typicky se piškvorky nehrají na omezeném hracím poli a i pokud ano, naší naivní metodou vytvořený AND/OR graf by pro běžný čtverečkovaný papír velikosti A4 obsahoval více vrcholů, než je atomů v celém pozorovatelném vesmíru. 19 Definice 7: Stromem řešení T problému P s AND/OR grafem G je podgraf grafu G, který je stromem a • jeho kořen je vrchol reprezentující problém P, • je-li N vnitřní uzel T typu AND, pak každý jeho následník v G je i v T, • je-li N vnitřní uzel T typu OR, pak právě jeden z jeho následníků v G je i v T. Pro náš příklad s výpočtem integrálu může strom řešení vypadat například ilustrovanými dvěma způsoby. Praktický význam má však spíše prvně vykreslený strom, kde koncové vrcholy umíme snadno vyřešit. x4 (1−x2)2 dx sin4 y cos4 y dy x = siny tan4 y dy trig.id. z4 1+z2 dz z = tan y −1 + z2 + 1 1+z2 dz divide z2 dz−dz dz 1+z2 dz dw z = tan w x4 (1−x2)2 dx sin4 y cos4 y dy x = siny 32 z4 (1+z2)(1−z2)4 dz z = tan y 2 Příklad. Seznam se s dekompozicí problému Hanojských věží z přednášky, kde problém 20 redukujeme na jednoduchý AND/OR graf, kde jsou všechny vnitřní uzly typu AND. Ke kolika fyzickým přesunům disku dojde při počtu kotoučů n rovno a) 1, b) 3, c) 4? a) 1, b) 7, c) 15 Příklad. Rozhodněte, zda je počáteční uzel, značený 1, splněný v následujících AND/OR grafech. Vrchol chápeme jako splněný tehdy, když pro něj existuje v daném grafu strom řešení se všemi konečnými vrcholy nastavenými na true. Spočtěte také, kolik takových stromů řešení existuje. a) 1 32 false 4 5 6 true false b) 1 32 4 567 true false 21 a) Ano, svoji odpověď můžeme potvrdit ukázkou příslušného stromu řešení. My ukazujeme všechny 3 možné stromy řešení. 1 2 4 5true 1 3 5 true 1 3 6 true b) Opět ano. Tentokrát je však vyhovující strom řešení pouze jeden. Všimněte si smyčky mezi AND vrcholy 6 a 7, kterou v tomto textu ukazujeme především proto, aby čtenář nezapomněl, že jsou povolené a možné. Učit se s nimi nakládat však nebudeme a konkrétně zde využíváme toho, že ji lze zcela ignorovat díky předchozímu OR uzlu 2. 1 32 4 5 true Příklad 3.1.1. Uvažme podivnou hru odehrávající se na hracím poli velikosti 3 × 3. Hráči se střídají a každý posouvá svou figuru podle pravidel šachu, nesmí však vstoupit na pole, které již bylo v minulosti obsazeno. Podaří-li se hráči sebrat soupeři figuru, vyhrává, naopak je-li hráč na tahu a nemůže se nikam pohnout (neboť dosažitelná pole již byla v minulosti obsazena), prohrává. Úkolem je zanalyzovat situaci, kde proti sobě hraje věž a střelec, první zmíněný je na tahu a počáteční rozmístění je dáno obrázkem níže. Zkonstruuj příslušný AND/OR graf a urči, kdo v takovém případě vyhraje. 22 B R Příklad 3.1.2. Uvažte rozehranou partii piškvorek, kde je právě na tahu hráč kreslící kolečka. Sestrojte AND/OR graf a okomentujte stromy řešení tohoto grafu. X ⃝ X X ⃝ ⃝ 3.2 Problémy s omezujícími podmínkami Zlatým grálem programování měl být řešič programů s omezujícími podmínkami, častěji zkracováno jako CSP (constraint satisfaction problem). Je typickým příkladem deklarativního programování, které si můžeme představit tak, že deklarujeme, co si přejeme, aby bylo splněno, a umělá inteligence to má za úkol zařídit. Na přednášce jste již jako příklad takového problému viděli problém obarvení grafu, algebrogram a problém N dam. Jako jiný příklad je vhodné uvést typovou inferenci – tedy automatické otypování funkcí a výrazů, které znáte třeba z Haskellu či Pythonu. Podívejme se na tento jednoduchý program. x = f(g(0)) x = f(x) x = g(x) Jeho analýzou získáme sérii omezení (též podmínek, angl. constraints), jejich konkrétní podoba závisí na uvažovaném typovém systému, zde se pokusíme alespoň o intuitivní náčrt. • f bere jako argument stejný typ, který vrací g • g bere argument typu int • f vrací stejný typ, který bere • g bere jako argument stejný typ, který vrací f Inteligentní řešič by nám po krátkém zpracování těchto omezení řekl, že obě uvedené funkce jsou typu int → int. Jako názornější příklad uvedeme sudoku. 23 2 9 3 1 9 6 5 2 8 4 9 5 5 2 3 6 7 2 4 7 8 2 5 1 7 3 5 8 Chceme vytvořit sadu omezení pro naši umělou inteligenci, aby nám poskytla řešení tohoto hlavolamu. Jenže co do našich omezení napsat? První krok je vždy rozmyslet proměnné našeho problému, tedy hodnoty, které bych rád od řešiče získal. Zde se přímo nabízí zavést si sérii proměnných x1, . . . , xn, kde každá reprezentuje hodnotu prázdného políčka a n je počet prázdných políček. Typicky při deklaraci proměnné zároveň říkáme, jakých můžeme nabývat hodnot – tedy specifikujeme její doménu. Z pravidel sudoku je jasné, že každá proměnná xi může nabývat celočíselných hodnot mezi 1 a 9. Dále víme, že budeme muset vytvořit omezení pro každý sloupec, řádek i čtverec. Pokud si pojmenujeme prázdná políčka popořadě po řádcích, omezení pro první řádek by vypadala jako: x1 ̸= 2, x1 ̸= x2, . . . , x2 ̸= 2, x2 ̸= x3, . . .. Mnoho programovacích jazyků nabízí místo této série 35 podmínek psát pouze něco ve smyslu ALL_DISTINCT(x1, x2, x3, . . . , x7), při omezení domén těchto 7 proměnných na {1, 3, 4, 5, 6, 7, 8}. To je nejen výrazně úspornější na zápis, ale především na pozadí schovaný řešič dostane možnost optimalizovat pro toto často se vyskytující omezení. Tento proces bychom opakovali pro každý řádek, sloupec i čtverec a spustili hledání řešení. Na začátku této sekce jsme zmínili, že takovýto styl programování měl být zlatým grálem informatiky. Není těžké si představit proč – místo psaní dlouhého kódu aplikace bych jen zavedl sérii podmínek jako „když kliknu sem, stane se...“. Takové deklarativní programování by samozřejmě bylo poněkud složitější, než tu ukazujeme, ale to je nakonec imperativní kód ještě mnohem víc. Kde je tedy problém? Pozorný čtenář již jistě uhodl, že v samotném řešiči. Skutečně efektivní umíme sestrojit pro určité typy omezení, všude jinde spoléháme na chytré heuristiky při prohledávání všech možných ohodnocení proměnných. Pro zvídavého čtenáře může být poněkud překvapivé i to, že takové řešení je problematické i tehdy, omezíme-li domény všech proměnných na binární {0, 1}. Pokud totiž naše omezení píšeme jazykem výrokové logiky, chceme po řešiči, aby řešil NP-úplný problém známý jako SAT. Praktické využití má však dnes CSP při rozvrhování (používá ho i naše fakulta) či konstrukci mikročipů. S jeho pomocí lze modelovat kromě zmíněné typové inference a logických hádanek také maximální tok grafem či lexikální analýzu. Po nepříliš stručném úvodu jsme připraveni si tyto nové pojmy definovat formálněji. 24 Definice 8: Problém s omezujícími podmínkami (CSP) je • soubor proměnných X1, . . . , Xn, každá s neprázdnou doménou D1, . . . , Dn; • soubor omezení C1, . . . , Cm; každé omezení je podmnožinou D1 × . . . × Dn; • (někdy) účelová funkce f : D1 × . . . × Dn → R. Řešením nazveme takovou n-tici (x1, . . . , xn) ∈ D1 ×. . .×Dn, která splňuje všechna omezení Ci, tj. ∀i.(x1, . . . , xn) ∈ Ci. Má-li CSP více než jedno řešení, může nás zajímat některé konkrétní, potom využíváme účelové funkce f a hledáme takové řešení, které funkci maximalizuje (či minimalizuje). V některých zdrojích pak takový problém značíme COP (constraint optimization problem). Příklad. Uvažme následující program. (Syntax neodpovídá přesně syntaxi z přednášky, ale je dostatečně intuitivní na to, aby nepotřebovala vysvětlení.) X in 1..7 Y in 1..7 X + Y = 7 a) Kolik má takový problém řešení? b) Kolik má řešení, přidáme-li omezení X * Y is even? c) Jak vypadá příslušný graf stavů, který prohledáváme? a) 6 – konkrétně {(X=1,Y=6),(X=2,Y=5),(X=3,Y=4),(X=4,Y=3),(X=5,Y=2),(X=6,Y=1)}. b) 6, jelikož vždy právě jedna proměnná X, Y musí být sudá, aby v součtu daly 7. Přidané omezení tedy nemění zadání. c) Začínáme v prázdném stavu, kde neznáme hodnotu ani jedné proměnné. Z něj se můžeme dostat do stavu, kde hodnota proměnné X je celé číslo mezi 1 a 7, jelikož jedině tyto stavy jsou v souladu se zadáním. Z každého z těchto stavů, kde známe pouze hodnotu proměnné X se však již dostaneme v souladu s omezeními v zadání do nanejvýš jediného stavu, kde je dána i hodnota proměnné Y. Všimněte si, že v jednom uzlu ({X=7}) naše cesta končí, z něj se nedokážeme dostat při splnění podmínek programu. Přísně vzato v našem grafu existuje mnoho jiných vrcholů – například {X=3,Y=3} – ty nekreslíme, neboť do nich nevede žádná cesta z počátečního stavu, a tak jsou pro naše prohledávání irelevantní. {} {X=1} {X=2} {X=3} {X=4} {X=5} {X=6} {X=7} {X=1,Y=6} {X=2,Y=5} {X=3,Y=4} {X=4,Y=3} {X=5,Y=2} {X=6,Y=1} 25 Příklad 3.2.1. Sestavte graf stavů pro následující CSP. Proměnné přiřazujte v sekvenčním pořadí podle jejich deklarace. Popište řešení. A in 2..4 B in 2..3 C in 0..6 A - B >= C A * (B-1) != B + C A != B Příklad 3.2.2. Převeď následující algebrogram na CSP. Každé písmenko P v rozepsaném součinu zastupuje prvočíselnou číslici – ne však nutně stejnou. Řešení hledat nemusíš (ačkoliv je to s trochou přemýšlení a zkoušení možné). Nezapomeň specifikovat zavedené proměnné a jejich domény. PPP PP PPPP PPPP PPPPP Příklad 3.2.3. Jako kouzelný čtverec označíme čtvercová matice, kde součet čísel na každém řádku a v každém sloupci je stejný. Jednotlivé buňky mohou nabývat celočíselných hodnot mezi 1 a n2 , kde n je dimenze uvažované matice. Jedním z netriviálních řešení pro n = 3 je tento kouzelný čtverec. 2 9 4 7 5 3 6 1 8 Formulujte tento problém jako CSP pro uvedené n = 3. Kromě omezení nezapomeňte uvést význam zavedených proměnných a jejich domény. Příklad 3.2.4. Latinský čtverec o velikosti n je čtvercová matice n × n, obsahující v každém řádku (a stejně i sloupci) neopakující se čísla 1, . . . , n. Každý řádek i sloupec je tedy permutace na množině {1, . . . , n}. Uvádíme konkrétní příklad pro n = 3. 1 2 3 2 3 1 3 1 2 Formulujte tento problém jako CSP pro uvedené n = 3. Kromě omezení nezapomeňte uvést význam zavedených proměnných a jejich domény. Příklad 3.2.5. Zajímavou aplikací CSP je známá Einsteinova hádanka, někdy nazývána zebra. Jejího autora neznáme, často se za něj uvádí Albert Einstein či Lewis Carroll. Týká se pěti sousedů, kteří žijí na ulici v domech v řadě vedle sebe. Každý z nich má jiné povolání, jiný dům, chová jiné zvíře, je jiné národností a preferuje jiné pití. Máme k dispozici několik výroků. • Angličan žije v červeném domě. • Španěl chová psa. 26 • Japonec je malíř. • Ital pije čaj. • Nor žije v prvním domě nalevo. • Majitel zeleného domu pije kávu. • Zelený dům je bezprostředně napravo od bílého. • Sochař chová šneky. • Diplomat žije ve žlutém domě. • V prostředním domě pijí mléko. • Nor žije vedle modrého domu. • Houslista pije ovocný džus. • Liška žije vedle doktora. • Kůň je ustájen v domě vedle diplomatova. K úloze patří i otázka. Kdo má zebru a kdo pije vodu? Vašim úkolem není tuto úlohu vyřešit (ačkoliv to není těžké), ale převést ji na CSP, z jehož řešení bychom uměli odpovědět na zadanou otázku. Příklad 3.2.6. Zamyslete se, jak formulovat jako CSP problém rozmístění jedné sady šachových figurek po klasické šachovnici velikosti 8×8 tak, aby se žádné dvě figurky neohrožovaly. Pěšce nemusíte uvažovat, stačí tedy umístit krále, dámu, 2 střelce, 2 koně a 2 věže. 27 4 Hry a herní strategie V této kapitole naučíme umělou inteligenci řešit deterministické hry dvou hráčů s úplnou informací. Ukážeme si, že jednoduchý algoritmus MINIMAX je pro složitější hry jako jsou piškvorky na dostatečně velké hrací ploše či šachy zcela nevhodný, neboť prohledávaný stavový graf je enormní. Následně spolu MINIMAX zefektivníme při zachování korektnosti, a objevíme tak ALFA-BETA prořezávání. Nakonec se ještě krátce zamyslíme nad tím, jak bychom námi nalezené postupy mohli aplikovat i na nedeterministické hry dvou hráčů. 4.1 MINIMAX Zabývejme se nyní spolu tahovou hrou pro dva hráče s perfektní informací. Dobrým příkladem takové hry, která nás již nějakou dobu touto sbírkou provází, jsou piškvorky. Nejprve se spolu podíváme na hru, kde nám přestává stačit AND/OR graf, a poté přejdeme k MINIMAX grafu. Pokud chceme modelovat hru s komplikovanějším vyhodnocením než jen výhra či prohra, tedy takovou, kde končíme s nějakým skóre, AND/OR stromy nám to neumožní. Koncové vrcholy totiž mohou být jen splněny/nesplněny, tj. výhra či prohra, nejsme v nich schopni ukládat číselnou hodnotu skóre a ani s ní následně vyhodnocovat splněnost vnitřních uzlů. Budeme tedy generalizovat myšlenku AND/OR grafů, ovšem omezíme se teď již pouze na stromy. Definice 9: MINIMAX strom je strom, kde každý vrchol je buď typu MIN, nebo MAX. Každý list je ohodnocen rozšířeným reálným číslem – tj. reálným číslem či kladným/záporným nekonečnem. Obecně lze místo reálných čísel použít jakoukoliv uspořádanou množinu. MINIMAX strom se vyhodnocuje směrem od listů, dokud nespočteme hodnotu kořene. Hodnota vrcholu typu MAX je rovna maximální hodnotě jeho následníků, hodnota uzlu typu MIN pak odpovídá hodnotě nejmenší napříč všemi následníky. Definice 10: Algoritmus MINIMAX je rekurzívní procedura, která ohodnotí každý vrchol MINIMAX stromu. • Hodnota listů je dána jako součást definice MINIMAX stromu. • Hodnota vrcholu typu MIN je nejmenší hodnota mezi jeho následníky. • Hodnota vrcholu typu MAX je největší hodnota mezi jeho následníky. 28 Příklad. Dokažte odvážné tvrzení, že MINIMAX stromy rozšiřují AND/OR stromy. Jinými slovy ukažte, že každý AND/OR strom lze chápat jako MINIMAX strom. Každý koncový vrchol ohodnotíme 1, je-li splněný, v opačném případě 0. Jelikož i listy MINIMAX stromu musí mít nějaký typ, označíme je všechny například za MIN. Vnitřní uzly typu AND pak odpovídají vrcholu typu MIN, jelikož to, že všichni následníci musí být splněni, je v tomto případě ekvivalentní požadavku, aby minimum hodnot následníků bylo 1. Obdobně OR uzly pak odpovídají typu MAX – má-li být splněný alespoň jeden následník, musí být maximum z jejich hodnot rovno 1. Vypůjčíme si tedy notaci AND/OR grafů a uzly typu MAX budeme značit obdélníkem zatímco MIN vrcholy elipsou ⊂⊃. Jiný častý způsob značení používá pro vrcholy MAX symbol , pro MIN uzly . Jelikož MINIMAX stromy použijeme pouze pro modelování tahové hry dvou hráčů, budeme se zabývat především těmi stromy, kde se uzly MIN a MAX střídají podle své vzdálenosti od kořene. Dále budeme uvažovat pouze hry s nulovým součtem, což znamená, že obdržím-li v nějaké hře skóre s, můj soupeř musí získat −s bodů – každý list nám tak bude stačit ohodnotit jen podle našeho skóre a soupeřovo si snadno domyslíme. Jak se později ukáže, tato myšlenka je velmi důležitá: MINIMAX stromy budou fungovat jen pro hry s nulovým součtem či obecně hry, kde platí, že když maximalizuji svoje skóre, zároveň minimalizuji to soupeřovo – a naopak. Příklad. Určete hodnotu kořene zadaných MINIMAX stromů. a) 7 -5 −∞ 0 5 ∞ b) 1 2 3 4 5 6 29 Vyhodnocujeme směrem od listů, uzel po uzlu. a) -5 -5 ∞ -5 −∞ 5 ∞ 7 -5 −∞ 0 5 ∞ b) 5 1 4 5 1 2 4 5 6 1 2 3 4 5 6 Nyní nám zbývá se spolu podívat, jakým způsobem můžeme využít tohoto modelu k popisu her. A jako obvykle si při ilustraci pomůžeme piškvorkami na hracím poli 3 × 3. Každý list v našem stromu stavů (tedy herních konfigurací) ohodnotíme 0, 1 či -1 podle toho, zda se jedná o remízu, naši výhru či prohru. V této hře budeme první na tahu a kreslíme kolečka. Prohlédněme si tři vybrané listy a jejich přiřazenou hodnotu. X ⃝ X ⃝ X ⃝ X ⃝ X ⃝ X ⃝ ⃝ X ⃝ X X ⃝ ⃝ ⃝ ⃝ X X ⃝ -1 0 1 Podle našeho ohodnocení je jasné, že kdykoliv budu na tahu já, budu se snažit svoje skóre maximalizovat, kdežto protihráč vždy minimalizovat. Uzly grafu, kde jsem na řadě já tedy budou typu MAX a ostatní typu MIN. Uvědomme si, že ne všechny listy jsou ve stejné hloubce (hra může skončit po různém počtu kol). Některé vrcholy se mohou vyskytovat duplicitně, neboť do nich lze „dojít“ různými cestami. Například následující konfigurace lze dosáhnout tak, že levý horní roh zaplníme kolečkem v prvním či až druhém kole. 30 ⃝ X ⃝ Připomínáme, že vrcholy typu MIN budeme značit malým kolečkem dole, ostatní vrcholy jsou pak typu MAX. Následuje ukázka malé části celého grafu. ⃝ ⃝ ⃝ ⃝ . . . ⃝ X ⃝ X ⃝ X ⃝ X . . . ⃝ X ⃝ ⃝ X ⃝ ⃝ X ⃝ ⃝ X ⃝ . . . . . . . . . . . . . . . . . . ⃝ X ⃝ X ⃝ X ⃝ 1 ⃝ X ⃝ X ⃝ X ⃝ ⃝ X 1 ⃝ X ⃝ X ⃝ X -1 ⃝ X ⃝ X X ⃝ ⃝ ⃝ X 0 . . . Příklad 4.1.1. Rozhodněte, zda je následující hry možné modelovat MINIMAX stromy. Pokud ano, zamyslete se nad tím, jak by takové stromy vypadaly. 31 a) šachy b) sudoku c) piškvorky na neomezené hrací ploše d) kámen, nůžky, papír e) tenis Příklad 4.1.2. Doplňte nějaké konkrétní ohodnocení konečných stavů her s naznačeným MINIMAX stromem tak, aby začínající hráč dosáhl nejlepšího možného výsledku hraním zadaných strategií, předpokládáme-li, že jeho soupeř nedělá chyby? Jaké vztahy obecně musí v takovém případě platit pro hodnoty listů? a) Výherní strategie nechť je left. a b c d left right b) Výherní strategie nechť je volit left v prvním kole a blue ve druhém. Nezapomeňte zařídit, aby nás dokonalý soupeř s jistotou dovedl k volbě potřebné strategie. left right a b c d e blue red Příklad 4.1.3. Ukažte, že obecný MINIMAX strom lze efektivně transformovat na ekvivalentní MINIMAX strom, kde se střídají typy vrcholů – tzn. následník má vždy jiný typ než jeho rodič. Efektivní transformací rozumíme takový algoritmus, která je polynomiální vzhledem k počtu vrcholů vstupního stromu. Ekvivalentní MINIMAX strom musí mít stejné listy se stejnými hodnotami jako strom původní a algoritmus MINIMAX musí napočítat stejnou hodnotu v kořeni. Příklad 4.1.4. Uvažme hru dvou hráčů – pronásledovatele P a zloděje Z – na hracím poli zadaném náledujícím grafem. a b c d e f 32 Pronásledovatel je první na tahu a začíná na poli b, zloděj začíná na poli d. Každý se během svého tahu posouvá na vedlejší pole, přičemž se po jednom kroku střídají. Hra končí, jestliže se zároveň ocitnou na stejném poli. Zloděj se snaží přežít co nejdéle a hodnota koncové konfigurace je pro něj úměrná tomu, kolik kol odehrál. • Lze tuto hru modelovat MINIMAX stromem? Lze ji vyřešit? • Vykreslete a vyřešte strom pro hru omezenou 3 koly – tedy hráč P i Z se každý posunou nejvýše třikrát. 4.2 Alfa-beta prořezávání Řešení deterministické hry s perfektní znalostí můžeme dostat i efektivnější procedurou, než je MINIMAX algoritmus. Zkusme ji spolu objevit. Až do této chvíle jsme pro zjednodušení tvrdili, že algoritmus MINIMAX vyhodnocuje vrcholy směrem od listů bez toho, abychom podrobněji vysvětlili, proč tomu tak je a jak to detailně funguje. Podívejme se detailně na skoro-pythonovský (pseudo)kód této procedury. def minimax ( node ) : i f node . neighbors is empty : # nachazime se v l i s t u return node . value best_so_far = minimax ( node . neighbors [ 0 ] ) # vynech nulteho naslednika ( souseda ) , protoze jsme ho j i z zpracovali for neighbor in node . neighbors [ 1 : ] : value = minimax ( neighbor ) i f node . type == "MIN" and value < best_so_far : best_so_far = value i f node . type == "MAX" and value > best_so_far : best_so_far = value return best_so_far Příklad. Jaká je asymptotická časová složitost algoritmu MINIMAX? Algoritmus probíhá zcela stejně jako prohledávání do hloubky (DFS), v každém uzlu se provedou navíc jen nějaká porovnání s konstantní časovou složitostí. Výsledná asymptotická časová složitost tedy je O(V +E), kde V je počet vrcholů prohledávaného grafu a E je počet hran. Toto lze vidět i z toho, že každý uzel a každá hrana se v průběhu výpočtu navštíví právě jedenkrát. V našem případě uvažujeme pouze souvislé grafy, můžeme tedy výsledek napsat stručněji jako O(E). Spustíme-li tedy výpočet nad kořenem našeho MINIMAX stromu (tj. zavoláme minimax(root)), dostaneme se do for cyklu, kde se rekurzivně zavoláme nad prvním následníkem kořene atp. až se dostaneme k listu. Jedná se tedy o prohledávání do hloubky s několika přidanými výpočty. Podívejme se teď spolu na jednoduchý příklad. 33 root left right 2 3 4 1 2 Budeme předpokládat, že uspořádání seznamu následníků odpovídá tomu na nákresu při čtení zleva doprava. Při vykonávání našeho (pseudo)kódu při spuštění minimax(root) se tedy nejprve dostaneme do uzlu left a skrze něj okamžitě do listu s hodnotou 2. Dosavadní nejlepší (a tedy v tomto případě nejmenší) hodnota pro vrchol left je tedy 2, ale může se pochopitelně změnit při procházení dalšího následníku, ke kterému dochází hned vzápětí. V tomto případě se však nic nezmění a konečně zjišťujeme, že hodnota uzlu left je 2. Kořen tedy skončil zpracování prvního následníka a nejlepší hodnota, kterou zatím viděl, je 2. Protože je typu MAX, víme, že nižší hodnotu už mít nemůže, ale jeho další následník (right) by ji mohl ještě zvýšit. Při vyhodnocování uzlu right nejprve vidíme hodnotu 4, poté 1. Zde se na chvíli zastavíme (těsně předtím než bychom zpracovali poslední list). Víme, že konečná hodnota vrcholu right nebude vyšší než 1, protože minimalizuje. Na druhou stranu jsme si již před začátkem zpracování tohoto uzlu všimli, že maximalizující kořen root nebude mít nižší hodnota než 2, kterou mu nabízí jeho levý následník. Prohledávání tedy můžeme okamžitě ukončit, jakýkoliv další následník uzlu right je nezajímavý a nemůže změnit hodnotu kořene, ačkoliv by pochopitelně ještě mohl snížit hodnotu svého předchůdce. Ačkoliv jsme si v tuto chvíli ušetřili průchod jediným uzlem, představíme-li si místo listů našeho vzorového příkladu dostatečně velké podstromy, můžeme si hodně pomoci. Tato úspora se neprojeví na nejhorší časové složitosti algoritmu ALFA-BETA, zlepší se však v průměrném případě nad omezenou vstupní množinou MINIMAX stromů. Hodnotu kořenového uzlu vsak napočítáme stejnou (což obecně neplatí o ostatních vnitřních uzlech), tedy ALFA-BETA je korektní. Nyní se již spolu podíváme na implementaci algoritmu ALFA-BETA. Pro přehlednost zcela oddělujeme rutinu pro uzly typu MIN a MAX, z důvodu stručnosti používáme v našem pseudokódu nekonečno INFINITY v inicializaci. Iniciální volání spustíme nad kořenem stromu obdobně jako předtím, tedy příkazem alphabeta(root, -INFINITY, INFINITY). def alphabeta ( node , alpha , beta ) : i f node . neighbors is empty : # nachazime se v l i s t u return node . value i f node . type == "MAX" : value = −INFINITY # aby se prepsala pri objevu prvni hodnoty for neighbor in node . neighbors : value = max( value , alphabeta ( neighbor , alpha , beta )) i f value >= beta : 34 break alpha = max( alpha , value ) return value else : value = INFINITY for neighbor in node . neighbors : value = min( value , alphabeta ( neighbor , alpha , beta )) i f value <= alpha : break beta = min( beta , value ) return value Příklad. Odkrokujte si algoritmus nad motivačním příkladem z úvodu této podsekce a přesvědčte se, že skutečně dojde k ořezání výpočtu tak, jak jsme předpověděli. root left right 2 3 4 1 2 Výpočet začíná voláním alphabeta(root, -∞, ∞), počáteční hodnoty jsou tedy α = −∞, β = ∞ a začínáme zpracovat kořenový vrchol. Při jeho výpočtu je potřeba najít hodnotu uzlu left, který se tedy bude muset vyčíslit (se stejnými hodnotami alfy a bety). Nejprve se objeví list s hodnotou 2, po jeho zpracování ukazuje hodnoty proměnných následující ilustrace. Světle šedý uzel je rozpracovaný, tmavě šedý je již úplně zpracovaný. root value = −∞ α = −∞ β = ∞ left value = 2 α = −∞ β = 2 right 2 3 4 1 2 Následně se obdobně zpracuje list s hodnotou 3, čímž dokončíme výpočet hodnoty vrcholu left a vrátíme se s výpočtem zpět do kořene root. Ten aktualizuje svoje hodnoty a spustí výpočet nad svým druhým následníkem right, přičemž se dostaneme až k uzlu s hodnotou 3. 35 root value = 2 α = 2 β = ∞ left right value = 4 α = 2 β = 4 2 3 4 1 2 Jako další se zpracovává list s hodnotou 1, kdy se konečně projeví smysl zavedených proměnných α a β. Jelikož se nám hodnota value nastaví na 1, což je méně než aktuální hodnota proměnné α ve vrcholu right, výpočet v tomto uzlu se ukončí (a vrátí hodnotu 1 do kořene root). root value = 2 α = 2 β = ∞ left right 2 3 4 1 2 Výpočet v tuto chvíli končí s výslednou hodnotou 2, přičemž poslední list jsme během výpočtu vůbec neviděli. Příklad 4.2.1. Ukažte, že asymptotická časová složitost v nejhorším případě algoritmu ALFA-BETA nad MINIMAX stromy je stejná jako pro algoritmus MINIMAX. Příklad 4.2.2. Zadaný strom MINIMAX střídá po úrovních typy svých uzlů a každý jeho list je ve stejné hloubce. Takové v literatuře (a hlavně v praxi) budete vídat nejčastěji, neboť přirozeně vznikají při modelování mnoha zajímavých her. Jako v celém zbytku sbírky předpokládejte i zde, že algoritmus prochází vrcholy v pořadí zleva doprava. a) Vyřešte strom s pomocí algoritmu ALFA-BETA. Především tedy zjistěte výslednou hodnotu kořene a které podstromy budou uřezány, tj. nebudou vůbec navštíveny. Při výpočtu věnujte zvláštní pozornost tomu, abyste porozuměli, jakým způsobem α odpovídá dolní hranici a β naopak horní. 36 b) Při zachování struktury grafu navrhněte vhodné hodnoty listů tak, aby nedošlo k žádnému prořezávání (a algoritmus tedy navštívil všechny listy). c) Při zachování struktury grafu navrhněte vhodné hodnoty listů tak, aby došlo k největšímu možnému prořezávání (a algoritmus tedy navštívil co nejméně uzlů). 2 4 6 8 10 12 14 13 11 9 7 5 3 1 Příklad 4.2.3. Při kterých z následujících transformací MINIMAX stromu může dojít ke změně nalezené optimální strategie? a) Ke všem hodnotám listů přičteme stejnou reálnou konstantu c. b) Všechny hodnoty v listech vynásobíme stejnou konstantou c. c) Hodnoty ve všech listech se libovolně změní tak, aby mezi nimi zůstalo zachováno jejich původní uspořádání. d) Všechny uzly typu MIN změníme na MAX a naopak. Hodnoty v listech pronásobíme -1. Příklad 4.2.4. Bez výpočtu určete a zdůvodněte, které podstromy by algoritmus ALFABETA v zadaném stromu ořezal. Následníci se prochází v pořadí zadaném obrázkem. 100 0 8 9 10 2 200 11 6 7 Příklad 4.2.5. Představme si MINIMAX strom, který se skládá pouze z uzlů typu MAX. Může při jeho vyhodnocování ALFA-BETA algoritmem dojít k nějakému prořezání? 37 4.3 Nedeterministické hry Až do této chvíle jsme tvrdě trvali na tom, aby uvažované hry neobsahovaly náhodu, neboť bychom ji neuměli modelovat. Nyní si ukážeme, že lze vhodně rozšířit MINIMAX stromy tak, aby náhodu v jisté míře postihly a my nad nimi pak mohli provádět smysluplné výpočty a předpovědi. Zjistíme však také, že některé vlastnosti a zákony, které dosud platily, se s tímto rozšířením zcela rozbíjí a mění. Na začátek uvažme velmi triviální ilustrativní hru. V prvním kole si vezmu modrý, či červený žeton. V dalším kole provede to samé provede soupeř (může si zvolit i žeton stejné barvy). První hráč vítězí, drží-li jiný žeton než jeho soupeř, v opačném případě prohrává. Pro přehlednost přikládáme ještě příslušný MINIMAX strom této jednoduché hry. červený modrý -1 1 1 -1 červený modrý červený modrý Nyní naši hru obohatíme o náhodu. Před tím, než si druhý hráč zvolí svůj žeton, hodíme mincí. Padne-li orel, soupeř přijde o možnost volby – musí si vzít modrý žeton. V opačném případě se nic nemění a hra pokračuje jako předtím. Pro modelování nedeterministické hry použijeme speciální vrchol (značený kosočtvercem ⋄) tam, kde dochází k rozhodnutí na základě náhody. Hrany, které z něj vychází, budou vždy označeny pravděpodobností, se kterou k výběru té konkrétní cesty dojde. červený modrý orel/0.5 panna/0.5 panna/0.5 orel/0.5 1 -1 1 modrý červený modrý -11-1 modrý červený modrý Už tedy chápeme, jak nedeterministické hry modelovat, zajímá nás však, jak se dopočítáme ke zjevnému závěru, že má začínající hráč volit červený žeton. K tomu využijeme upravený algoritmus MINIMAX, který rozšíříme o schopnost počítat hodnotu nového typu uzlu reprezentujícího náhodnou volbu ⋄. Pro většinu aplikací je přirozené volit jako hodnotu vrcholu náhody jeho očekávanou hodnotu – tj. hodnotu každého potomka vynásobíme pravděpodobností, že bude vybrán, a výsledky pak sečteme napříč všemi potomky. Poněkud přehlednější zápis říká 38 minimax(X) = n...child of X minimax(n) · P(n), kde X je uzel reprezentující náhodu, minimax(n) je spočtená hodnota potomka n a P(n) je pravděpodobnost, že náhodně zvolíme právě potomka n – tj. číslo na odpovídající hraně grafu. S touto znalostí již celý graf snadno doplníme. Je vidět, že očekávaný výnos začínajícího hráče je 0 a získá ho za předpokladu, že volí strategii červený. 0 0 -1 červený modrý 1 -1 -1 -1 orel/0.5 panna/0.5 panna/0.5 orel/0.5 1 -1 1 modrý červený modrý -11-1 modrý červený modrý Příklad 4.3.1. Sestavte vhodný strom a následně jej vyřešte pro následovně zadanou nedeterministickou hru dvou hráčů. Začínající hráč si zvolí číslo 1, 2 nebo 3. Následně se hodí 3 mincemi. Padne-li na všech z nich stejná strana, soupeř si smí zvolit číslo -1 nebo 0. V opačném případě vybere číslo 1 či 2. Začínající hráč obdrží od soupeře částku rovnou součinu jejich čísel – v případě záporného součinu naopak musí příslušnou sumu protihráči zaplatit. Příklad 4.3.2. Uvažme obrázkem zadaný MINIMAX strom rozšířený o vrcholy reprezentující náhodu. Hodnoty dvou listů jsou neznámé, označeny jako a a b. left right 0.2 0.8 0.2 0.8 -1 1 0 2 a b a) Co musí platit pro hodnoty a, b, aby optimální strategie odpovídala tučně vyznačené? b) Nechť b = 1. Co musí platit pro hodnotu a, aby maximalizující hráč volil v prvním kole strategii left? c) Nechť b = −1. Co musí platit pro hodnotu a, aby maximalizující hráč volil v prvním kole strategii right? Příklad 4.3.3. 39 left right 0.1 0.9 0.5 0.5 1 3 2 4 Nejprve pro obrázkem zadaný rozšířený MINIMAX strom ověřte, že optimální strategie začínajícího hráče je right. Poté ukažte, že lze vhodně transformovat hodnoty listů tak, aby se optimální strategie změnila na left. Transformace musí zachovat původní uspořádání mezi listy; tedy jestliže měl list A před transformací menší hodnota než list B, bude tomu tak i po ní. Příklad 4.3.4. Uvažujeme rozšířený MINIMAX strom s neznámými pravděpodobnostmi větvení. left right p1,1 p1,2 p2,1 p2,2 3 -1 1 2 5 0 4 4 a) Nechť p1,1 = 2 7 . Co platí pro p2,1, p2,2, aby optimální strategie začínajícího hráče byla right? b) Co pro neznámé pravděpodobnosti platí obecně, má-li být optimální strategie right? c) Jak by musely vypadat hodnoty v listech, aby bez ohledu na hodnoty neznámých pravděpodobností byla optimální strategií right? 40 5 Výroková logika Výroková logika je základní formalismus, kterým můžeme modelovat jednoduchá tvrzení, jejich pravdivost, vyplývání a jiné vztahy mezi nimi. Staví na pojmu výrok, což je elementární tvrzení, o jehož pravdivosti má smysl uvažovat. Výroky reprezentujeme výrokovými proměnnými, které s využitím logických spojek (a, nebo, pokud-pak atp.) můžeme skládat do složitějších formulí a tím modelovat složitější tvrzení (jako např. souvětí). 5.1 Syntax Syntax vyjadřuje, jakým způbem ve výrokové logice zapisujeme platné formule – zatím však bez toho, abychom jim přiřazovali nějaký význam. První definice popisuje symboly, které používáme... Definice 11: Abeceda výrokové logiky zahrnuje • spočetně mnoho symbolů výrokových proměnných p, q, r, . . . , • symboly pro logické spojky ¬, ∨, ∧, ⇒, ⇔, . . . , • pomocné symboly závorek ( a ). Ozn. P = {p, q, r, . . . } množinu symbolů výrokových proměnných. ... další už nám přesně říká, jak vypadá správně utvořená formule ve výrokové logice. Definice 12: Formule výrokové logiky. • Každý symbol p ∈ P je formule. • Jsou-li φ, ψ fomule, pak rovněž ¬(φ), (φ) ∨ (ψ), (φ) ∧ (ψ), (φ) ⇒ (ψ), (φ) ⇔ (ψ), . . . jsou formule. • Nic jiného formulí není. Závorková konvence umožňuje vynechávat přebytečné závorky, nedojde-li k porušení sémantické jednoznačnosti formule. Ozn. F množinu formulí výrokové logiky. Poznáte nyní správně utvořenou formuli výrokové logiky? Příklad 5.1.1. Uvažujte formule dle Definice 12. Rozhodněte, která z následujících slov jsou formule (neuvažujte závorkovou konvenci, tj. závorky musí přesně odpovídat definici): a) w1 = ¬(¬p) b) w2 = (p) ∧ (q) ∧ (r) c) w3 = (p) ⇒ ((¬(q)) ∨ (¬(r))) d) w4 = ((p)¬(q)) ∨ (r) e) w5 = (p) = (r) 41 5.2 Sémantika Sémantika popisuje, jak máme logické formule chápat, přiřazuje celému formalismu konkrétní význam. První důležitý pojem, interpretace, vyjadřuje, zda konkrétní elementární výroky považujeme za pravdivé či nepravdivé. Definice 13: Interpretace I je zobrazení I : P → {0, 1} přiřazující pravdivostní hodnoty 0 (nepravda), 1 (pravda) jednotlivým výrokovým proměnným množiny P. V konkrétní interpretaci elementárních výroků pak můžeme vyhodnotit pravdivostní hodnotu celé formule. Definice 14: Valuace (též vyhodnocení) příslušící interpretaci I je zobrazení I : F → {0, 1} přiřazující pravdivostní hodnoty 0 (nepravda), 1 (pravda) jednotlivým formulím z F. (Jedná se o rozšíření interpretace z atomických formulí na všechny formule podle sémantiky logických spojek. Přesná definice je induktivní a zde ji neuvádíme.) To s sebou přináší celou řadu pojmů, které blíže popisují vlastnosti dané formule, ať už obecně, či ve vztahu k dalším formulím. Definice 15: • Formule φ je pravdivá v interpretaci I, jestliže I(φ) = 1 (tj. vyhodnotí se v příslušné valuaci na hodnotu 1). V opačném případě je formule nepravdivá v interpretaci I. • Formule φ je logicky pravdivá či tautologie, jestliže je pravdivá v libovolné interpretaci. • Formule φ je kontradikce, jestliže je nepravdivá v libovolné interpretaci. • Formule φ je splnitelná, jestliže je pravdivá v nějaké interpretaci. Tato splňující interpretace se nazývá modelem formule φ. • Formule φ, ψ jsou sémanticky ekvivalentní, značeno φ ≈ ψ, jestliže I(φ) = I(ψ) pro libovolnou interpretaci I. Podívejme se na vše zblízka na vzorovém příkladě. Příklad. Mějme formuli výrokové logiky φ ≡ p ∧ (q ⇒ ¬p). Sestavte pravdivostní tabulku formule φ a určete a) zda je φ pravdivá v interpretaci I(p) = 0, I(q) = 1, b) zda je φ kontradikcí či tautologií, c) zda je φ splnitelná; případně nalezněte nějaký její model. 42 Pravdivostní tabulka formule vypadá následujícím způsobem. ř. p q p ∧ (q ⇒ ¬p) 1 0 0 0 0 0 1 1 2 0 1 0 0 1 1 1 3 1 0 1 1 0 1 0 4 1 1 1 0 1 0 0 Jednotlivé řádky odpovídají různým interpretacím (sloupečky p, q) a jim příslušícím valuacím jednotlivých částí (podformulí) formule φ (následující sloupečky). Sloupeček s tučně vyznačenými hodnotami odpovídá valuacím formule φ. a) Formule φ je nepravdivá v interpretaci I, viz ř. 2. b) Formule φ není ani kontradikcí, ani tautologií. (Všechny zvýrazněné hodnoty by musely být 0, resp. 1.) c) Formule φ je splnitelná, neboť existuje interpretace, v níž je formule pravdivá. Viz ř. 3 tabulky. Modelem formule φ (jediným) je tedy interpretace I(p) = 1, I(q) = 0. Příklad 5.2.1. Mějme formuli výrokové logiky φ ≡ p ⇒ ¬(¬q ∨ r). Sestavte pravdivostní tabulku formule φ a určete a) zda je φ pravdivá v interpretaci I(p) = 0, I(q) = I(r) = 1, b) zda je φ kontradikcí či tautologií, c) zda je φ splnitelná; případně nalezněte nějaký její model. Příklad 5.2.2. Mějme formuli výrokové logiky φ ≡ (p ∧ q) ⇔ (¬q ∧ r). Bez použití pravdivostní tabulky určete a) zda je φ pravdivá v interpretaci I(p) = 0, I(q) = I(r) = 1, b) zda je φ kontradikcí, c) zda je φ tautologií, d) zda je φ splnitelná; případně nalezněte nějaký její model. Příklad 5.2.3. Udejte příklad formule φ takové, že: a) φ obsahuje právě 3 různé výrokové proměnné a je pravdivá právě ve 3 interpretacích, b) φ obsahuje právě 3 různé výrokové proměnné, je pravdivá právě ve 3 interpretacích a obsahuje pouze logickou spojku ⇒. c) φ je kontradikce, obsahuje právě 2 různé výrokové proměnné, každou dvakrát. (Uvažujte interpretaci jako zobrazení přiřazující hodnoty právě výrokovým proměnným vyskytujícím se v φ.) Příklad 5.2.4. Zjistěte, kolik existuje vzájmeně neekvivalentních formulí výrokové logiky a) obsahujících pouze 3 výrokové proměnné p1, p2, p3 (i vícekrát), 43 b) obsahujících pouze n výrokových proměnných p1, . . . , pn (i vícekrát), c) obsahujících pouze n výrokových proměnných p1, . . . , pn (i vícekrát) pravdivých právě v polovině interpretací. 5.3 Množiny formulí, splnitelnost, vyplývání Občas je potřeba pracovat s několika tvrzeními zároveň a zkoumat vztahy mezi nimi. Proto zavádíme následující pojmy. Definice 16: Množina formulí T je splnitelná, jestliže existuje interpretace I, v níž jsou pravdivé všechny formule φ ∈ T . Potom říkáme, že množina T je pravdivá v interpretaci I a tato interpretace se nazývá modelem množiny T . Není-li množina splnitelná, mluvíme o množině nesplnitelné. Všimněte si, že prázdná množina ∅ je splnitelná a je pravdivá v libovolné interpretaci. Dále zavedeme pojem logického vyplývání. Definice 17: Formule φ logicky vyplývá z množiny formulí T , zapisováno T ⊨ φ, právě když je formule φ pravdivá v každém modelu množiny T . Jinak řečeno, formule (závěr) logicky vyplývá z množiny předpokladů, právě když je pravdivá v každé interpretaci, v níž je pravdivá i množina předpokladů. Vyplývá-li tedy formule φ z prázdné množiny, ∅ ⊨ φ, jedná se o tautologii (rozmyslete si). Píšeme jenom ⊨ φ. V podobném duchu vynecháváme množinové závorky, je-li množina předpokladů jednoprvková, tedy ψ ⊨ φ namísto {ψ} ⊨ φ. Následující věta dále propojuje logickou spojku implikace s logickým vyplýváním. Věta 18 (o dedukci): Logické vyplývání {ψ1, . . . , ψn} ⊨ φ platí, právě když platí vyplývání {ψi, . . . , ψn−1} ⊨ ψn ⇒ φ. Následující vzorový příklad ilustruje právě zavedené koncepty. Příklad. Uvažujte množinu formulí T = {¬p ⇒ r, ¬(q ∧ r), p ∨ ¬q}. Sestavte pravdivostní tabulku množiny T a určete a) zda je T pravdivá v interpretaci I(p) = I(q) = I(r) = 0, b) zda je T splnitelná; případně nalezněte nějaký její model, c) zda platí logické vyplývání T ⊨ p ∧ ¬r, d) zda platí logické vyplývání T ⊨ r ⇒ ¬q. 44 Pravdivostní tabulka množiny T vypadá následujícím způsobem. ř. p q r ¬p ⇒ r ¬(q ∧ r) p ∨ ¬q T p ∧ ¬r r ⇒ ¬q 1 0 0 0 0 1 1 0 0 1 2 0 0 1 1 1 1 1 0 1 3 0 1 0 0 1 0 0 0 1 4 0 1 1 1 0 0 0 0 0 5 1 0 0 1 1 1 1 1 1 6 1 0 1 1 1 1 1 0 1 7 1 1 0 1 1 1 1 1 1 8 1 1 1 1 0 1 0 0 0 a) Množina T není pravdivá v interpretaci I, viz ř. 1. b) Množina T je splnitelná, neboť existuje interpretace, v níž je množina pravdivá. Viz např. ř. 2 tabulky. Modelem množiny T je tedy např. interpretace I(p) = I(q) = 0, I(r) = 1. c) Vyplývání neplatí. Existuje interpretace, v níž je pravdivá množina T (předpoklad), ale neplatí závěr. Viz např. ř. 2. d) Vyplývání platí. Ve všech interpretacích, v nichž je pravdivá množina T (předpoklad), je platný i závěr. Viz ř. 2, 5, 6, 7. Příklad 5.3.1. Uvažujte množinu formulí T = {r ∧ ¬q, ¬(¬r ∧ p), p ⇒ r}. Sestavte pravdivostní tabulku množiny T a určete a) zda je T pravdivá v interpretaci I(p) = I(q) = I(r) = 1, b) zda je T splnitelná; případně nalezněte nějaký její model, c) zda platí logické vyplývání T ⊨ r, d) zda platí logické vyplývání T ⊨ r ∧ p. Příklad 5.3.2. Ukažte, že pro každou množinu formulí T existuje formule φ, která je pravdivá v interpretaci I, právě když je I modelem T . Příklad 5.3.3. Uvažujte množinu formulí T = {(p ⇒ q) ∨ ¬r, ¬p ⇒ s, ¬t ∨ p ∨ ¬q}. Zadejte formuli φ tak, aby množina T ∪ {φ} byla nesplnitelná. Příklad 5.3.4. Rozhodněte, zda pro libovolnou neprázdnou množinu formulí T existuje formule φ taková, že φ není kontradikce a T ∪ {φ} je nesplnitelná. Své tvrzení dokažte. (Argumentujte formálně s využitím pojmů interpretace, valuace atp.) Příklad 5.3.5. Uvažujte množinu formulí výrokové logiky T a formule φ, ψ. Rozhodněte o platnosti následujících tvzení: a) Pokud T ⊨ φ a T ⊨ ψ, pak T ⊨ φ ∨ ψ. b) Pokud T ⊨ φ a T ⊨ ψ, pak T ⊨ φ ∧ ψ. 45 c) Pokud T ⊨ φ ∨ ψ, pak T ⊨ φ nebo T ⊨ ψ. d) Pokud T ⊨ φ ∧ ψ, pak T ⊨ φ a T ⊨ ψ. e) Pokud T ⊨ φ, pak T ⊨ φ ∨ ψ. f) Pokud T ⊨ φ, pak T ⊨ φ ∧ ψ. g) Pokud T ⊨ φ, pak T ∪ {ψ} ⊨ φ. h) Pokud T ∪ {ψ} ⊨ φ, pak T ⊨ φ. Příklad 5.3.6. Ukažte, že logické vyplývání T ⊨ φ platí, právě když množina T ∪ {¬φ} je nesplnitelná. Poznámka: Tato vlastnost odpovídá principu důkazu sporem. Znova ji uvidíme v části zabývající se rezolucí, kde ukazujeme vyplývání pomocí nesplnitelnosti množiny formulí. Příklad 5.3.7. S využitím věty o dedukci (a bez použití pravdivostních tabulek) rozhodněte, zda je formule ξ ≡ p ⇒ (q ⇒ (¬p ⇒ r)) tautologie, kontratikce, splnitelná formule. 5.4 Logické spojky Se základními logickými spojkami (∨, ∧, ⇒, ¬, . . . ) jsme se již na intuitivní úrovni setkali. Podívejme se na ně ještě jednou zblízka. Definice 19: Sémantika n-ární logické spojky □ je dána funkcí f□ : {0, 1}n → {0, 1} následujícím způsobem: Valuace formule ψ ≡ □(φ1, . . . , φn) v interpretaci I je dána jako I(ψ) = f□(I(φ1), . . . , I(φn)), kde I(φ1), . . . , I(φn) jsou valuace podformulí φ1, . . . , φn příslušné interpretaci I. Intuitivně, pro novou spojku můžeme zadat její sémantiku tabulkou (předepisující funkci f□) a formule s touto spojkou pak odpovídající způsobem vyhodnocovat. Všimněte si rovněž, že logické spojky nemusí být nutně unární (jako např. ¬) nebo binární (jako např. ∨), ale mohou mít libovolnou aritu. Význam nové spojky ale můžeme definovat i ekvivalencí s jinou formulí. Lze tedy definovat např. nulární falsum (čili konstantní nepravdu) jako ⊥ :≈ p ∧ ¬p, či implikaci jako φ ⇒ ψ :≈ ¬φ ∨ ψ. Příklad. Definujte nulární verum ⊤ (čili konstantní pravdu) ekvivalencí s jinou formulí. Definujte disjunkci tabulkou. Nulární verum: ⊤ :≈ p ∨ ¬p. Disjunkce: ř. φ ψ φ ∨ ψ 1 0 0 0 2 0 1 1 3 1 0 1 4 1 1 1 46 Ještě zavedeme pojem úplného systému logických spojek. Definice 20: Množina logických spojek tvoří úplný systém logických spojek, pokud lze formulemi obsahujícími pouze spojky z dané množiny vyjádřit libovolnou logickou funkci (vnímáme-li formule jako funkce přiřazující zadané interpretaci svou valuaci). Množina {¬, ∨, ∧, ⇒, ⇔} tvoří úplný systém logických spojek (důkaz vynecháváme). Ve skutečnosti, jak dále uvidíme, nám stačí pouze spojky {¬, ⇒}. Zavést ostatní spojky pomocí těchto dvou může v mnoha případech usnadnit argumentaci o formulích (stačí uvažovat o vlastnostech dvou spojek). V praxi (např. při tvorbě elektronických obvodů) se ještě používají úplné systémy logických spojek {NAND} a {NOR}2 , které si vystačí s jedinou spojkou. Příklad 5.4.1. Kolik existuje různých vzájemně neekvivalentních n-árních spojek? Příklad 5.4.2. Uvažujte formule výrokové logiky nad abecedou obsahující pouze logické spojky ⇒, ¬. Zaveďte spojky ∨, ∧, ⇔ jako syntaktické zkratky v tomto systému tak, aby měly obvyklý význam. (Tj. pro slova φ ∨ ψ, φ ∧ ψ, φ ⇔ ψ, kde φ, ψ jsou správně utvořené formule, uveďte formule v uvažovaném systému, které jsou jimi reprezentovány.) Příklad 5.4.3. Mějme formuli výrokové logiky φ ≡ ¬(p ∧ (q□r)) ∨ (q ⇒ r). Určete (např. tabulkou) sémantiku binární logické spojky □ tak, aby formule φ byla: a) tautologie, b) kontradikce, c) ekvivalentní formuli p ⇒ q, nebo konstatujte, že formule nemůže danou podmínku splnit. Odpovědi zdůvodněte. Příklad 5.4.4. Kolika způsoby lze definovat sémantiku spojky □ z bodu a) předchozího příkladu? Příklad 5.4.5. Ukažte, že následující množiny tvoří úplné systémy logických spojek. Vyjděte z předpokladu, že {⇒, ¬} je úplný systém logických spojek. (Tj. vyjádřete formule φ ⇒ ψ a ¬φ pomocí formulí obsahující pouze spojky z příslušných množin.) • {NOR} • {NAND} Příklad 5.4.6. Uvažujte ternární logickou spojku ∆ definovanou takto: ∆(φ, ψ, θ) :≈ (φ ⇒ ψ) ∧ ¬θ. Rozhodněte, zda množina {∆} tvoří úplný systém logických spojek, a svou odpověď dokažte. Můžete vyjít z předpokladu, že {¬, ⇒} je úplný systém logických spojek. Příklad 5.4.7. Uvažujte spojku ̸⇒ definovanou takto: φ ̸⇒ ψ :≈ ¬(φ ⇒ ψ). Rozhodněte, zda množina {̸⇒} tvoří úplný systém logických spojek, a svou odpověď dokažte. Můžete vyjít z předpokladu, že {¬, ⇒} je úplný systém logických spojek. 2 φNANDψ :≈ ¬(φ ∧ ψ), φNORψ :≈ ¬(φ ∨ ψ) 47 5.5 Normální formy Normální formy představují speciální způsob zápisu, z kterého lze přímo vyčíst některé sémantické vlastnosti formule. Základní stavební kameny formulí v normální formě jsou literály, znichž skládáme klauzule, resp. duální klauzule. Definice 21: • Literál je výroková proměnná nebo její negace. • Klauzule je disjunkce literálů. • Duální klauzule je konjunkce literálů. Spojením klauzulí konjunkcí nebo duálních klauzulí disjunkcí získáme formuli v konjukntivní, resp. disjunktivní normální formě. Když navíc každá klauzule obsahuje všechny uvažované výrokové proměnné, bavíme se o úplné normální formě. Definice 22: Uvažujme výrokové proměnné p1, . . . , pn. • Formule je v konjunktivní normální formě (KNF), jedná-li se o konjunkci klauzulí (s navzájem různými množinami literálů). • Formule je v disjunktivní normální formě (DNF), jedná-li se o disjunkci duálních klauzulí (s navzájem různými množinami literálů). • Obsahuje-li navíc každá klauzule (resp. duální klauzule) formule v KNF (resp. DNF) každou z výrokových proměnných p1, . . . , pn právě jednou, hovoříme o úplné konjunktivní (resp. disjunktivní) normální formě (ÚKNF, resp. ÚDNF) Formule (p∨¬q)∧(¬p∨¬q∨r) je v KNF, ale není v ÚKNF, protože první klauzule neobsahuje všechny implicitně uvažované výrokové proměnné p, q, r. Ekvivalentní formulí v ÚKNF je formule (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ r). Pro převod do úplných normálních forem existuje poměrně přímočarý algoritmus, který je ilustrován na následujícím příkladu. Příklad. Pomocí pravdivostní tabulky převeďte formuli p ⇔ q do ÚDNF a ÚKNF. Vytvoříme pravdivostní tabulku zadané formule a pro interpretace, v nichž je formule pravdivá, přidáme duální klauzuli do ÚDNF; pro interpretace, v nichž je formule nepravdivá, přidáme klauzuli do ÚKNF. Klauzuli pro danou interpretaci I tvoříme tak, že pro každou výrokovou proměnnou p: • je-li I(p) = 0, přidáme do klauzule literál p, • je-li I(p) = 1, přidáme do klauzule literál ¬p. V případě duální klauzule pro každou výrokovou proměnnou p, je-li I(p) = 0, přidáme literál ¬p, je-li I(p) = 1, přidáme literál p. 48 p q p ⇔ q duální klauzule klauzule 0 0 1 (¬p ∧ ¬q) 0 1 0 (p ∨ ¬q) 1 0 0 (¬p ∨ q) 1 1 1 (p ∧ q) ÚDNF: (¬p ∧ ¬q) ∨ (p ∧ q) ÚKNF: (p ∨ ¬q) ∧ (¬p ∨ q) Příklad 5.5.1. Pomocí pravdivostní tabulky převeďte formuli r ⇒ ¬s do ÚDNF. Příklad 5.5.2. Pomocí pravdivostní tabulky převeďte formuli ¬r ⇒ (r ∧ ¬s) do ÚKNF. Příklad 5.5.3. Ekvivalentními úpravami převeďte formuli ¬(p ⇔ ¬q) ∨ ¬r do KNF. Příklad 5.5.4. Ekvivalentními úpravami převeďte formuli (p ∨ ¬(¬r ⇒ q)) ∧ (r ⇒ p) do DNF. Příklad 5.5.5. Ekvivalentními úpravami převeďte formuli (¬q ∧ r) ∨ (r ∧ ¬p) do ÚDNF. 49 6 Predikátová logika Predikátová logika přirozeně rozšiřuje logiku výrokovou. Namísto výroků zde hovoříme o predikátech, na které můžeme pohlížet jako na parametrizované výroky, jejichž pravdivost závisí i na hodnotě parametru: např. pravdivost tvrzení „x je sudé (párne) číslo“ závisí na tom, zda se za hodnotou x schovává číslo 1 nebo 2. 6.1 Syntax Než začneme zkoumat sémantiku predikátové logiky, podívejme se opět nejprve na její syntax. Definice 23: Abeceda predikátové logiky zahrnuje • symboly pro proměnné x, y, z, . . . , • predikátové symboly P, Q, R, . . . , • funkční symboly f, g, h, . . . (příp. a, b, c, d, . . . pro konstanty), • symboly pro logické spojky ¬, ∨, ∧, ⇒, ⇔, . . . , • pomocné symboly závorek ( a ) a kvantifikátorů ∀ a ∃. Ozn. V = {x, y, z, . . . } množinu všech proměnných. Pozor, proměnná je v kontextu predikátové logiky něco jiného než výroková proměnná. Výrokovým proměnným ve skutečnosti odpovídají predikáty, které jsou jejich zobecněním. (Podrobněji dále.) Novým a zcela klíčovým je zde pojem termu, který reprezentuje objekt a slouží jako argument pro predikáty. Definice 24: Term. • Každý symbol pro proměnnou je term. • Je-li f n-ární funkční symbol a t1, . . . , tn termy, pak také f(t1, . . . , tn) je term. • Nic dalšího není term. Nulární funkce, čili konstanty, zapisujeme bez prázdných závorek, tedy c namísto c(). U běžných binárních funkčních symbolů lze používat i infixový zápis bez závorek. U běžných unárních symbolů lze používat i prefixový zápis bez závorek. Máme-li k dispozici nulární funkční symbol c, binární funkční symboly f, + a proměnné x, y, z, . . . , pak např. f(x, c); f(f(x, y), z); c; +(x, z) jsou termy. Poslední uvedený lze navíc 50 v souladu s výše uvedenou konvencí zapisovat infixově jako x + z. V matematickém kontextu tak například matematické výrazy (nikoliv rovnice!) představují termy: x + 2, 7 + 15, x2 /0. Stále je potřeba mít na mysli, že termy reprezentují hodnoty či objekty, nikoliv tvrzení. Jak tedy reprezentovat tvrzení v predikátové logice? Definice 25: Formule predikátové logiky. • Je-li P n-ární predikátový symbol a t1, . . . , tn termy, pak P(t1, . . . , tn) je formule. • Jsou-li t1, t2 termy, je t1 = t2 formule. • Jsou-li φ, ψ fomule, pak rovněž ¬(φ), (φ) ∨ (ψ), (φ) ∧ (ψ), (φ) ⇒ (ψ), (φ) ⇔ (ψ), . . . jsou formule. • Je-li φ fomule a x proměnná, pak rovněž ∃x(φ) a ∀x(φ) jsou formule. • Nic jiného formulí není. U běžných binárních predikátových symbolů lze používat i infixový zápis bez závorek. Formule vzniklá aplikací predikátového symbolu na termy se nazývá atomická formule. V matematickém kontextu jsou matematické rovnice či nerovnice jako x+5 = y−1, x2 +1 ≤ x jednoduchými příklady formulí. Formulí však lze běžně vyjadřovat i složitější tvrzení: ∀x∃y(x + y = 0). Použité funkční a predikátové symboly pak společně tvoří jazyk predikátové logiky3 L, který doplňuje definice termu a formule konkrétním kontextem. Příklad. Ve formuli φ ≡ ∀x(x · x ≥ 0 ⇒ ∃y(f(x, y, z) < sin(0 + x))), kde všechny symboly mají obvyklý (matematický) význam, identifikujte všechny a) proměnné, b) termy, c) funkční symboly, d) predikátové symboly. U funkčních a predikátových symbolů určete i jejich aritu. a) x, y, z b) x, x · x, 0, y, z, f(x, y, z), 0 + x, sin(0 + x) 3 Jazyk je v tomto kontextu pouze označení pro množinu funkčních a predikátových symbolů, čili jedná se o jiný pojem než formální jazyk. 51 c)+d) Symboly klasifikujeme v tabulce. symbol typ arita zápis · funkční 2 infix ≥ predikátový 2 infix 0 funkční (konstanta) 0 n/a f funkční 3 prefix sin funkční 1 prefix < predikátový 2 infix + funkční 2 infix Jazyk formule φ je L = {·, ≥, 0, f, sin, <, +}. Proměnné navíc mohou být ve formuli vázány kvantifikátorem (tedy patřit do „scope“ kvantifikátoru), nebo být volné. Definice 26: Výskyt proměnné x ve formuli φ (výskytem rozumíme její použití v rámci termu, nikoli kvantifikátoru) je vázaný, existuje-li podformule φ, ozn. ψ, která obsahuje tento výskyt a začíná ∃x nebo ∀x. V opačném případě je výskyt proměnné volný. Formule, která nemá žádný volný výskyt proměnné se nazývá uzavřená nebo též sentence. Běžně používané značení φ(x1, . . . , xn) znamená, že formule φ má volný výskyt proměnných x1, . . . , xn, ostatní proměnné jsou ve formuli vázané. Příklad. Klasifikujte výskyty proměnných ve formuli ∀z(x = y ⇒ ∃xP(x, y)) ∨ Q(x). Proměnná z nemá ve formuli žádný výskyt (za výskyt považujeme, když je proměnná součásti termu, ne kvantifikátoru). Proměnná x má ve formuli tři výskyty: nejprve volný, potom vázaný a nakonec opět volný. Proměnná y má ve formuli dva výskyty, oba volné. Příklad 6.1.1. Uvažujte jazyk L predikátové logiky obsahující jeden unární funkční symbol f a jeden nulární funkční symbol c. Popište množinu všech termů jazyka L. Příklad 6.1.2. Uvažujte jazyk L predikátové logiky obsahující funkční a predikátové symboly zadané následující tabulkou: 52 symbol typ arita f funkční 2 c funkční 0 P predikátový 1 Q predikátový 2 Rozhodněte, která z následujících slov jsou termy jazyka L: a) y = x, b) Q(c, c), c) f(x, c), d) ∀y(f(f(c, c), y)), e) z, f) f(f(c)), g) f(x, y) ∨ f(c, x), h) f(f(c, x), f(y, z)). Příklad 6.1.3. Uvažujte jazyk L predikátové logiky z předchozího příkladu. Rozhodněte, která z následujících slov jsou formulemi jazyka L: a) y = x, b) ∀x(Q(c, c) = x), c) f(x, c), d) ∀y(f(f(c, c), y)), e) Q(f(x, c)), f) ∀x(Q(f(f(c, c), y), f(z, c)) ∨ P(f(c, z))), g) ∀x∃c(f(x, c) = c). Příklad 6.1.4. Uvažujte jazyk L predikátové logiky obsahující jediný funkční symbol f arity 2 a žádný predikátový symbol. Uveďte příklad formule jazyka L a) s jedinou proměnnou x s právě dvěma vázanými výskyty a žádným volným výskytem, b) s jedinou proměnnou x s právě jedním vázaným a jedním volným výskytem, c) pouze s proměnnými x, y se dvěma vázanými a žádným volným výskytem, resp. s jedním volným a žádným vázaným výskytem, d) pouze s proměnnými x, y, každou s jedním volným a jedním vázaným výskytem. Příklad 6.1.5. Uvažujte jazyk L1 predikátové logiky, který obsahuje právě dva funkční symboly: • nulární symbol (konstantu) k, • unární symbol f a žádný predikátový symbol. Dále uvažujte jazyk L2, který navíc k těmto dvěma funkčním symbolům obsahuje unární predikátový symbol P. Rozhodněte o pravdivosti následujících tvrzení a svou odpověď zdůvodněte: 53 1. Množina T = {fi (k) | i ∈ N0} = {k, f(k), f(f(k)), f(f(f(k))), . . . } jsou právě všechny termy jazyka L1. 2. Neexistuje formule predikátové logiky jazyka L1. 3. Uvažujte formuli φ ≡ ∀xP(x) jazyka L2. Existují podformule ψ1, ψ2 formule φ takové, že všechny proměnné formule ψ1 mají v ψ1 volný výskyt a všechny proměnné formule ψ2 mají v ψ2 vázaný výskyt? 6.2 Sémantika Podobně jako u výrokové logiky je nyní namístě dodat formulím predikátové logiky konkrétní význam. Poslouží k tomu opět interpretace, zde ovšem mající podobu složitější struktury. Definice 27: Interpretace (též realizace) jazyka L je struktura I zahrnující • neprázdné univerzum (či doménu) DI, • n-ární relaci I(P) ⊆ Dn I pro každý n-ární predikátový symbol P jazyka L, • zobrazení I(f) : Dn I → DI pro každý n-ární funkční symbol f jazyka L. Univerzum specifikuje množinu objektů, nad kterými pracujeme. Termy pak reprezentují hodnoty z tohoto univerza. Místo jednoduchého přiřazení jedniček a nul výrokovým proměnným jsou predikáty chápány jako relace a jejich pravdivost závisí na hodnotách jejich argu- mentů. Abychom mohli vyhodnocovat termy, je potřeba ještě definovat, jak interpretovat proměnné. K tomu slouží valuace. Definice 28: Valuace je zobrazení V : V → DI přiřazující proměnným prvky univerza. Hodnotu termu v interpretaci a valuaci pak upřesňuje následující induktivní definice. Definice 29: Hodnota termu t v interpretaci I a valuaci V je prvek univerza |t|I,V ∈ DI, kde • |t|I,V = V (x) pro t = x, kde x je proměnná, • |t|I,V = I(f)(|t1|I,V , . . . , |tn|I,V ) pro t = f(t1, . . . , tn), kde f je n-ární funkce a t1, . . . , tn jsou termy. Příklad. Uvažujte jazyk L s jedním nulárním funkčním symbolem c a jedním binárním funkčním symbolem f a jeho interpretaci I, kde • Univerzum tvoří celá čísla 0, 1 a 2, tj. DI = {0, 1, 2}. 54 • Symbol f se realizuje jako sčítání modulo 3, tj. I(f)(x, y) = (x + y) mod 3. • Symbol c se realizuje jako číslo 1, tj. I(c) = 1. Dále uvažujte valuaci V , která všem proměnným přiřazuje hodnotu 2, tj. V (x) = 2 pro všechna x ∈ V. Určete hodnoty následujících termů v interpretaci I a valuaci V : a) c b) f(c, x) c) f(x, f(x, y)) a) Podle druhého bodu definice hodnoty termu je |c|I,V = I(c) = 1. b) Podle druhého bodu definice hodnoty termu je |f(c, x)|I,V = I(f)(|c|I,V , |x|I,V ). Podle druhého, resp. prvního bodu definice máme |c|I,V = I(c) = 1 a |x|I,V = V (x) = 2, a tedy celkem |f(c, x)|I,V = I(f)(1, 2) = (1 + 2) mod 3 = 0. c) Máme postupně |f(x, f(x, y))|I,V = I(f)(|x|I,V , |f(x, y)|I,V ) = (2 + 1) mod 3 = 0, protože |x|I,V = V (x) = 2 a |f(x, y)|I,V = I(f)(|x|I,V , |y|I,V ) = (2 + 2) mod 3 = 1, neboť |x|I,V = |y|I,V = V (x) = 2. Nyní můžeme přistoupit k definování pravdivosti formule v dané interpretaci a valuaci. Definice 30: Zda formule φ je pravdivá v interpretaci I a valuaci V , značeno ⊨V I φ, definujeme induktivně takto: • ⊨V I P(t1, . . . , tn), právě když (|t1|I,V , . . . , |tn|I,V ) ∈ I(P), • ⊨V I t1 = t2, právě když |t1|I,V = |t2|I,V , • ⊨V I ¬ψ, právě když není ⊨V I ψ, • ⊨V I ψ ∧ ξ, právě když ⊨V I ψ a ⊨V I ξ (a podobně pro zbylé logické spojky; vynecháno), • ⊨V I ∀xψ, právě když pro všechny prvky univerza d ∈ D platí ⊨V ′ I ψ, kde valuace V ′ vznikla z V nahrazením obrazu proměnné x prvkem d, • ⊨V I ∃xψ, právě když pro nějaký prvek univerza d ∈ D platí ⊨V ′ I ψ, kde valuace V ′ vznikla z V nahrazením obrazu proměnné x prvkem d. Příklad. Uvažujte jazyk L predikátové logiky obsahující jeden unární funkční symbol f a jeden binární predikátový symbol P. Dále uvažujte interpretaci I jazyka L: • Univerzum tvoří všechna reálná čísla, tj. DI = R. • Symbol f se realizuje jako unární minus, tj. I(f)(x) = −x. • Symbol P se realizuje jako ostré menší než, tj. I(P) = {(x, y) ∈ R2 ; x < y}. Nechť V je valuace přiřazující všem proměnným hodnotu 1, tj. V (x) = 1 pro všechna x ∈ V. Rozhodněte, zda následující formule jsou pravdivé v interpretaci I a valuaci V : a) P(x, f(x)) 55 b) ∃xP(x, f(x)) c) ∃x∀yP(x, y) d) ∃xP(x, y) a) Máme |x|I,V = 1, |f(x)|I,V = −1. Dle prvního řádku definice je formule P(x, f(x)) pravdivá, právě když (|x|I,V , |f(x)|I,V ) ∈ I(P), tj. (1, −1) ∈ {(x, y) ∈ R2 ; x < y}, neboli 1 < −1, což zjevně neplatí. Více neformálně: Termy x a f(x) se vyhodnotí na 1, resp. −1. Poněvadž se symbol P realizuje jako ostrá nerovnost a neplatí 1 < −1, je formule nepravdivá. b) Ve formuli se vyskytuje pouze proměnná x, zúžíme tedy argumentaci pouze na ni. Formule je pravdivá, jestliže existuje prvek univerza, jehož dosazením za x docílíme toho, že je formule P(x, f(x)) pravdivá; takovým prvkem je ovšem např. číslo −1. c) Formule je pravdivá, jestliže existuje prvek, jehož dosazením za x docílíme toho, že je formule ∀yP(x, y) pravdivá. Takový prvek nicméně neexistuje, neboť při dosazení libovolného reálného čísla d ∈ DI za x budou existovat hodnoty y, pro které není P(x, y) pravdivá – např. číslo d−1 ∈ DI (a tudíž není P(x, y) pravdivá pro libovolnou hodnotu y). Pozor na pořadí kvantifikátorů! Aby byla uvažovaná formule pravdivá, musí existovat hodnota x taková, že již formule P(x, y) platí pro libovolné y. d) Proměnná y má v uvažované valuaci hodnotu 1, zjevně existuje hodnota x, aby formule P(x, y) byla pravdivá (kupř. V (x) = 0), a tedy uvažovaná formule je pravdivá. Pravdivost formule (pouze) v interpretaci je definována tak, aby byla ekvivalentní doplnění univerzálních kvantifikátorů pro volné proměnné, tedy ⊨I P(x, y), právě když ⊨I ∀x∀yP(x, y) : Definice 31: • Formule predikátové logiky je pravdivá v interpretaci I, ozn. ⊨I φ, jestliže je pravdivá v interpretaci I a valuaci V pro libovolnou valuaci V . • Formule predikátové logiky je logicky pravdivá či tautologie, ozn. ⊨ φ, jestliže je pravdivá v každé interpretaci. Příklad 6.2.1. Ukažte, že existenční kvantifikátor ∃ lze v predikátové logice zavést jako syntaktickou zkratku, tj. ekvivalentními úpravami vyjádřete ∃xφ bez použití symbolu ∃. 56 Příklad 6.2.2. Nalezněte negace následujících formulí tak, aby se symboly ¬ nacházely výhradně bezprostředně před predikátovými symboly. a) ∀x(P(x) ∨ ∃yQ(y)) b) ∀x(P(x) ⇒ Q(x)) ∧ ∃x(R(x) ∧ S(x)) c) (∃xP(x) ∨ ∀yQ(y)) ⇔ ∀x(∃yR(x, y) ⇒ Q(x)) Příklad 6.2.3. Uvažte formuli φ ≡ ∃x(∀yR(x, y) ⇒ Q(x)). Pro každou z následujících interpretací rozhodněte, zda je modelem formule φ. a) DI = {0}, I(R) = ∅, I(Q) = ∅ b) DI = {0}, I(R) = {(0, 0)}, I(Q) = ∅ c) DI = Z, I(R) = Z × Z, I(Q) = N0 Příklad 6.2.4. Uvažte formuli φ ≡ ∀y(∃xR(x, y) ⇒ Q(y)). Pro každou z následujících odrážek popište právě ta I(Q), že interpretace I je modelem formule φ. a) DI = {0}, I(R) = {(0, 0)} b) DI = {0}, I(R) = ∅ c) DI = Z, I(R) =< d) DI = Z, I(R) = {(x, y) ∈ Z × Z | x je sudé číslo} e) DI = Z, I(R) = {(x, y) ∈ Z × Z | y je sudé číslo} Příklad 6.2.5. Rozhodněte, v jakých interpretacích jsou pravdivé následující formule: a) ∀x∃y∃z(((x = y) ∨ (x = z)) ∧ (y ̸= z)) b) ∀x∀y∀z((Q(x, y) ∧ Q(y, z)) ⇒ Q(x, z)) c) ∀x(¬Q(x, x) ∧ ∃yQ(x, y)) d) ∀x(x ̸= f(x) ∧ x = f(f(x))) Příklad 6.2.6. Uvažujte jazyk L predikátové logiky obsahující právě dva binární funkční symboly ∗ a +. Uvažujte interpretaci (realizaci) I jazyka L, kde univerzum tvoří všechna reálná čísla R a funkční symboly se realizují běžným (matematickým) způsobem, tj. + jako sčítání a ∗ jako násobení. Nalezněte a) fomuli α(x, y, z), kt. je pravdivá v I právě v těch valuacích V , že V (x) − V (y) = V (z), b) fomuli β(x), která je pravdivá v I právě v těch valuacích V , že V (x) je 0, c) fomuli γ(x), která je pravdivá v I právě v těch valuacích V , že V (x) je 1, d) fomuli δ(x), která je pravdivá v I právě v těch valuacích V , že V (x) je kladné číslo nebo 0, e) fomuli ε(x, y), která je pravdivá v I právě v těch valuacích V , že V (x) ≤ V (y). Při definování formulí se můžete odvolat na formule, které jste již zavedli v předchozích bodech. 57 6.3 Normální formy Jelikož rezoluce v predikátové logice vyžaduje práci s formulemi určitých tvarů, je nutné se s těmito tvary seznámit, abychom mohli rezoluci provádět. Podobně jako ve výrokové logice jim říkáme normální formy. První normální forma, prenexová, má všechny kvantifikátory umístěny před samotným jádrem formule, které je v KNF. Literálem v kontextu predikátové logiky rozumíme libovolnou atomickou formuli nebo její negaci. Definice 32: Uzavřená formule φ se nachází v prenexové normální formě (PNF), je-li tvaru Q1x1 . . . Qnxnψ, kde Qi ∈ {∀, ∃}, x1, . . . , xn jsou proměnné a formule ψ je v konjunktivní normální formě (zejména tedy neobsahuje žádný kvantifikátor). Například formule ∀x∃y((P(f(y)) ∨ ¬Q(x)) ∧ (¬P(y) ∨ P(x))) se nachází v PNF. Skolemova normální forma oproti PNF ještě navíc vyžaduje, aby veškeré proměnné ve formuli byly všeobecně kvantifikované. Definice 33: Uzavřená formule φ se nachází ve Skolemově normální formě, nachází-li se v prenexové normální formě a obsahuje pouze obecné kvantifikátory ∀. Například formule ∀x((P(f(g(x))) ∨ ¬Q(x)) ∧ (¬P(g(x)) ∨ P(x))) se nachází ve Skolemově NF, jelikož vznikla skolemizací předchozí formule v PNF. Procesy převodu do PNF a do Skolemovy NF si ukážeme na příkladech. Příklad. Převeďte formuli ∃x∀y(P(x, y) ⇒ ¬∀xQ(y, x)) do PNF. Algoritmus převodu sestává z několika kroků. I. Eliminujeme zbytečné kvantifikátory. (Takové v zadané formuli nejsou.) II. Přejmenujeme proměnné tak, aby u každého kvantifikátoru byla jiná proměnná: ∃x1∀y(P(x1, y) ⇒ ¬∀x2Q(y, x2)) III. Eliminujeme jiné spojky než ∨, ∧, ¬: ∃x1∀y(¬P(x1, y) ∨ ¬∀x2Q(y, x2)) IV. Přesuneme negaci až před samotné predikáty (s využitím de Morganových zákonů a pravidel pro negaci kvantifikátoru): ∃x1∀y(¬P(x1, y) ∨ ∃x2¬Q(y, x2)) V. Kvantifikátory přesuneme ven z jádra formule: ∃x1∀y∃x2(¬P(x1, y) ∨ ¬Q(y, x2)) VI. Jádro formule upravíme do KNF pomocí distributivních zákonů. (Již je v KNF.) 58 Nyní si demonstrujeme převod výsledné formule do Skolemovy NF. Příklad. Převeďte formuli ∃x1∀y∃x2(¬P(x1, y) ∨ ¬Q(y, x2)) do Skolemovy NF. Převod z PNF do Skolemovy NF spočívá v citlivém odstranění existenčních kvantifikátorů. Jejich roli v nově vytvořené formuli zastoupí Skolemovy funkce, které se vyhodnotí na hodnotu, kterou by původně „vybral“ existenční kvantifikátor. V zadané formuli je volba hodnoty proměnné x1 pevná (nezávisí na dalších proměnných, protože existenční kvantifikátor je úplně první), nahradíme tedy proměnnou x1 konstantou c a kvantifikátor odstraníme (x1 → c): ∀y∃x2(¬P(c, y) ∨ ¬Q(y, x2)) Volba hodnoty proměnné x2 již pevná není, ale může záviset na konkrétní hodnotě y, protože se obecný kvantifikátor s y nachází před kvantifikátorem s x2. Nahradíme tedy proměnnou x2 funkcí f(y) a kvantifikátor odstraníme (x2 → f(y)): ∀y(¬P(c, y) ∨ ¬Q(y, f(y))) Nalezená formule je již ve Skolemově NF. Příklad 6.3.1. Převeďte následující formule do prenexové normální formy a proveďte skolemizaci. a) (∀x∃yQ(x, y) ∨ ∃x∀yP(x, y)) ∧ ¬∃x∃y∀zR(x, y, z) b) ¬(∀x∃yP(x, y) ⇒ ∃x∃yR(x, y)) ∧ ∀x(¬∃yQ(x, y)) Příklad 6.3.2. Uvažujte následující formule: a) α ≡ ∀x∀y∃z(x + z = y), b) β ≡ ∃x∀y(x ∗ y = x), c) γ ≡ ∀x∀y∃r(x ≤ y ⇒ x ≤ r ≤ y) d) δ ≡ ∀x1∀y1∀x2∀y2∃x3∃y3( (x1 − x3)2 + (y1 − y3)2 = (x2 − x3)2 + (y2 − y3)2) e) ε ≡ ∀x∃y(x > 0 ⇒ x = 2y )) nad doménou reálných čísel, kde matematické symboly +, ∗, ·2 , √ ·, . . . se interpretují běžným způsobem (tj. + jako sčítání, ∗ jako násobení, ...). Proveďte skolemizaci těchto formulí a určete nějakou možnou interpretaci pro každou z nově vzniklých Skolemových funkcí (vč. konstant) tak, aby byla zachována pravdivost formulí. 59 7 Důkazové systémy a rezoluce Předmětem této kapitoly budou formální systémy, které umožňují vyvozovat závěry na strojové úrovni. Nejprve se seznámíme s axiomatickými důkazovými systémy, posléze s rezolucí ve výrokové i predikátové logice a nakonec s programovacím jazykem Prolog, jehož výpočty jsou na principu rezoluce založeny. 7.1 Axiomatické systémy Axiomatické systémy umožňují formalizovat pojem matematického důkazu. Axiomatický systém obsahuje axiomy (resp. schémata axiomů) a odvozovací pravidla, která specifikují, jak z platných tvrzení odvodit další platné tvrzení. V rámci výrokové logiky budeme používat Łukasiewiczův axiomatický systém. Definice 34: Łukasiewiczův axiomatický systém zahrnuje schémata axiomů • A1: φ ⇒ (ψ ⇒ φ) • A2: (φ ⇒ (ψ ⇒ ξ)) ⇒ ((φ ⇒ ψ) ⇒ (φ ⇒ ξ)) • A3: (¬φ ⇒ ¬ψ) ⇒ (ψ ⇒ φ) a odvozovací pravidlo • MP (modus ponens): Z φ a φ ⇒ ψ odvoď ψ. Následující definice formálního důkazu se nevztahuje pouze k Łukasiewiczovému systému, ale obecně k libovolnému zvolenému axiomatickému systému. Definice 35: Formální důkaz formule φ v axiomatickém systému je konečná posloupnost formulí ψ1, . . . , ψn, kde ψn ≡ φ a pro každé 1 ≤ i ≤ n je ψi instancí nějakého schématu axiomu (tj. dosazením konkrétních formulí za symboly φ, ψ, ξ apod.) nebo vzniklo aplikací odvozovacího pravidla na formule, které mu v posloupnosti předcházely. Formule φ je dokazatelná, zapisováno ⊢ φ, jestliže v uvažovaném axiomatickém systému existuje její formální důkaz. S definicí formálního důkazu již můžeme hovořit o dokazatelnosti formule ve zvoleném axiomatickém systému a o korektnosti či úplnosti axiomatického systému. Definice 36: • Je-li každá v uvažovaném systému dokazatelná formule logicky pravdivá (čili pro každou formuli φ platí pokud ⊢ φ, pak ⊨ φ), hovoříme o korektním systému. • Je-li každá logicky pravdivá formule v uvažovaném systému dokazatelná (čili pro každou formuli φ platí pokud ⊨ φ, pak ⊢ φ), hovoříme o úplném systému. 60 Příklad. Uveďte formální důkaz formule φ ≡ p ⇒ p v Łukasiewiczově ax. systému. • A1: p ⇒ ((p ⇒ p) ⇒ p) • A2: p ⇒ (p ⇒ p) ⇒ p ⇒ p ⇒ (p ⇒ p) ⇒ (p ⇒ p) • MP: (p ⇒ (p ⇒ p)) ⇒ (p ⇒ p) • A1: p ⇒ (p ⇒ p) • MP: p ⇒ p Příklad 7.1.1. Uveďte formální důkazy následujících formulí v Łukasiewiczově axiomatickém systému: a) φ ≡ (p ⇒ (q ⇒ r)) ⇒ (p ⇒ p) b) ψ ≡ q ⇒ (p ⇒ p) Příklad 7.1.2. Uvažujte axiomatický systém zahrnující schémata axiomů (φ, ψ mohou být libovolné formule) • A1: φ ⇒ φ • A2: φ ⇒ (ψ ⇒ (φ ⇒ ψ)) a odvozovací pravidlo MP (modus ponens). a) Dokažte, že je uvažovaný systém korektní, tj. pro každou formuli φ v tomto systému platí, že pokud ⊢ φ, pak ⊨ φ. b) Dokažte, že uvažovaný systém není úplný, tj. existuje formule φ, pro kterou platí ⊨ φ, ale neplatí ⊢ φ. Nápověda k b): Hledejte syntaktickou vlastnost, kterou zachovávají formule dokazatelné v tomto systému. 7.2 Obecná rezoluce ve výrokové logice V rámci pojednávání o rezoluční metodě budeme podobně jako dříve pracovat s klauzulemi, tedy disjunkcemi literálů. Budeme ovšem používat množinový zápis, kdy klauzuli ℓ1 ∨· · ·∨ℓn zapíšeme jako množinu literálů {ℓ1, . . . , ℓn}. Speciálně zavádíme symbol □ pro prázdnou množinu literálů, tedy kontradikci. Definice 37: Rezoluční pravidlo: Uvažujme dvě klauzule {p, ℓ1, . . . , ℓn}, {¬p, ℓ′ 1, . . . , ℓ′ m}, kde ℓi, resp. ℓ′ i jsou literály. Jejich rezolventou je klauzule {ℓ1, . . . , ℓn, ℓ′ 1, . . . , ℓ′ m}. Rezolventou klauzulí {¬p, r, ¬t, u} a {s, ¬q, ¬r} je klauzule {¬p, ¬t, u, s, ¬q}. Klauzule {¬p, r, ¬t, u} a {¬r} mají rezolventu {¬p, ¬t, u}. 61 Opakovanou aplikací rezolučního pravidla vzniká rezoluční důkaz (všimněte si podobnosti s definicí formálního důkazu v axiomatickém systému): Definice 38: Rezoluční důkaz klauzule C z množiny klauzulí S je konečná posloupnost klauzulí C1, . . . , Cn, kde Cn = C a pro každé 1 ≤ i ≤ n je Ci ∈ S nebo Ci vzniklo aplikací rezolučního pravidla na klauzule, které mu v posloupnosti předcházely. Klauzule C je rezolučně dokazatelná z S, zapisováno S ⊢R C, jestliže existuje její rezoluční důkaz z S. Rezoluční důkaz prázdné klauzule □ z množiny klauzulí S nazýváme vyvrácením S. Důležitá vlastnost rezolučního pravidla je, že zachovává pravdivost v interpretaci (a tudíž i splnitelnost). Dokážeme-li tedy z nějaké množiny klauzulí S klauzuli C, vyplývá klauzule C z množiny S. Dokážeme-li z nějaké množiny klauzulí S prázdnou klauzuli □, je množina S nesplnitelná. Příklad. Uveďte rezoluční důkaz klauzule C = {¬q} z množiny S = {{p, r}, {¬s, ¬r}, {¬q, s}, {¬p}}. • C1 = {p, r} ∈ S • C2 = {¬p} ∈ S • C3 = {r} rezolventa C1 a C2 • C4 = {¬s, ¬r} ∈ S • C5 = {¬q, s} ∈ S • C6 = {¬q, ¬r} rezolventa C4 a C5 • C7 = {¬q} = C rezolventa C3 a C6 Pro lepší představu je někdy výhodné zapisovat rezoluční důkazy pomocí stromu místo posloupnosti klauzulí. Kořenem stromu je vždy výsledná klauzule a potomky každého vnitřního uzlu jsou klauzule, jejichž je daný uzel rezolventou. Listy pak tvoří prvky množiny S. Rezoluční strom pro právě uvedený příklad by mohl vypadat následovně: {¬q} {r} {p, r} {¬p} {¬q, ¬r} {¬q, s} {¬s, ¬r} Mnohdy4 je výhodnější místo odvození konkrétní klauzule ukázat nesplnitelnost množiny klauzulí. Následující věta shrnuje, jak lze vyplývání dokázat vyvrácením množiny formulí. 4 Konkrétně například při strojovém dokazování u dalších typů rezoluce. 62 Věta 39: Pro množinu formulí T a formuli φ platí T ⊨ φ, právě když T ∪ {¬φ} je nes- plnitelná. Proto budeme často vyplývání T ⊨ φ ukazovat tak, že namísto rezolučního důkazu T ⊢R φ nalezneme rezoluční vyvrácení T ∪ {¬φ} ⊢R □. Důkaz Věty 39 není zvlášť náročný a můžete si ho rozmyslet v rámci Příkladu 5.3.6. Příklad 7.2.1. Obecnou rezolucí ukažte nesplnitelnost následujících množin klauzulí. a) {{¬p, ¬q, ¬s}, {¬p, ¬q, s}, {¬p, q}, {p, ¬q}, {p, q}} b) {{p, q, ¬r}, {r}, {¬p, q, ¬r}, {¬q, ¬r, ¬s}, {s}} Příklad 7.2.2. Obecnou rezolucí dokažte následující logická vyplývání. Vyplývání dokažte jak přímo, tak pomocí rezolučního vyvrácení. a) {¬p ∨ q, ¬r ⇒ ¬q} ⊨ p ⇒ r b) {(¬p ∧ r) ⇒ q, (¬p ∧ q) ⇒ s, r ⇒ ¬p} ⊨ r ⇒ s Příklad 7.2.3. Dokažte, že rezoluční pravidlo zachovává pravdivost v interpretaci, tedy že pokud množina klauzulí {{p, ℓ1, . . . , ℓn}, {¬p, ℓ′ 1, . . . , ℓ′ m}}, kde ℓi, resp. ℓ′ i jsou literály, je pravdivá v interpretaci I, pak klauzule {ℓ1, . . . , ℓn, ℓ′ 1, . . . , ℓ′ m} je rovněž pravdivá v interpretaci I. Příklad 7.2.4. Uvažujte upravené rezoluční pravidlo, kde rezolventou klauzulí {p, q, ℓ1, . . . , ℓn}, {¬p, ¬q, ℓ′ 1, . . . , ℓ′ m}, kde ℓi, resp. ℓ′ i jsou literály, je klauzule {ℓ1, . . . , ℓn, ℓ′ 1, . . . , ℓ′ m}. (Tedy rezolvovat lze na dvou proměnných naráz.) Zachovává toto rezoluční pravidlo pravdivost v interpretaci? Svou odpověď dokažte. 7.3 SLD rezoluce ve výrokové logice Kromě obecné rezoluce existují i specifičtější typy rezolucí. Jedním z nich je SLD rezoluce, tedy rezoluce na uspořádaných klauzulích s výběrovým pravidlem, která se používá ke strojovému dokazování. Výběrové pravidlo specifikuje, na kterém literálu rezolvujeme. Obvykle budeme používat výběrové pravidlo vybírající první literál v klauzuli – dává smysl pouze v uspořádaných klauzulích (nticích), nikoliv však v obecných klauzulích (množinách). Definice 40: Rezoluční pravidlo pro SLD rezoluci: Uvažujme uspořádané klauzule [¬p1, . . . , ¬pi−1, ¬pi, ¬pi+1 . . . , ¬pn], [pi, ¬q1, . . . ¬qm], kde i je určeno výběrovým pravidlem. Jejich SLD rezolventou je usp. klauzule [¬p1, . . . , ¬pi−1, ¬q1, . . . , ¬qm, ¬pi+1, . . . , ¬pn]. Rezolventou klauzulí [¬p, ¬r, ¬s] a [r, ¬t, ¬s] je [¬p, ¬t, ¬s, ¬s]. Klauzule [¬p, ¬r, ¬s] a [r] pak mají rezolventu [¬p, ¬s]. 63 Uvažujeme-li výběrové pravidlo vybírající první literál v klauzuli, pak je vždy při aplikaci rezolučního pravidla i = 1: klauzuli [¬p1, ¬p2, . . . , ¬pn] vždy rezolvujeme s klauzulí tvaru [p1, ¬q1, . . . , ¬qm] s rezolventou [¬q1, . . . , ¬qm, ¬p2, . . . , ¬pn]. Definice 41: Důkaz SLD rezolucí uspořádané klauzule C z množiny uspořádaných klauzulí S je konečná posloupnost klauzulí C1, . . . , Cn, kde C1 ∈ S, Cn = C a pro každé 1 ≤ i < n je Ci+1 SLD rezolventou Ci s nějakou klauzulí C′ ∈ S. Příklad. Uveďte důkaz SLD rezolucí klauzule C = [¬q] z množiny S = {[r, ¬p], [¬r, ¬s], [s, ¬q], [p]} a nakreslete příslušný rezoluční strom. • C1 = [¬r, ¬s] • C2 = [¬p, ¬s] rezolventa C1 a [r, ¬p] • C3 = [¬s] rezolventa C2 a [p] • C4 = [¬q] = C rezolventa C3 a [s, ¬q] [¬q] [¬s] [¬p, ¬s] [¬r, ¬s] [r, ¬p] [p] [s, ¬q] U strojového dokazování pomocí SLD rezoluce se v souladu s Větou 39 používá vyvrácení množiny klauzulí. Příklad. Pomocí SLD rezolučního vyvrácení dokažte, že klauzule C = [¬q] vyplývá z množiny S = {[r, ¬p], [¬r, ¬s], [s, ¬q], [p]} a nakreslete příslušný rezoluční strom. Podle Věty 39 vyplývá klauzule C z množiny S, právě když je množina S∪{¬C} nesplnitelná. SLD rezolucí tedy vyvrátíme množinu {[r, ¬p], [¬r, ¬s], [s, ¬q], [p]} ∪ {[q]} • C1 = [¬r, ¬s] • C2 = [¬p, ¬s] rezolventa C1 a [r, ¬p] • C3 = [¬s] rezolventa C2 a [p] • C4 = [¬q] rezolventa C3 a [s, ¬q] • C5 = □ rezolventa C4 a [q] □ [¬q] [¬s] [¬p, ¬s] [¬r, ¬s] [r, ¬p] [p] [s, ¬q] [q] 64 SLD rezoluce je úplná pro speciální množinu klauzulí, které se nazývají Hornovy klauzule. Definice 42: Hornovy klauzule jsou klauzule, které obsahují nejvýše jeden pozitivní literál (tedy literál bez negace). Ten v případě uspořádaných klauzulí navíc zapisujeme jako první. Dělíme je na • fakta – klauzule s právě jedním, pozitivním literálem (např. [s], [r]), • pravidla – klauzule s právě jedním pozitivním literálem a alespoň jedním negativním literálem (např. [s, ¬r, ¬t], [r, ¬q]), • cíle – klauzule obsahující výhradně negativní literály (např. [¬r, ¬t]). V rámci SLD rezoluce může obecně existovat více způsobů, jak se dobrat výsledku. Kompaktní způsob, který zachycuje prohledávání stavového prostoru a způsoby vyvrácení množiny klauzulí, je SLD strom. Příklad. Pomocí SLD rezoluce vyvraťte množinu {[¬s, ¬u], [q, ¬r], [q, ¬t], [q], [r], [u, ¬q], [s]}. Nakreslete SLD strom systematického hledání řešení. Nakreslete rezoluční strom pro nejlevější úspěšnou větev SLD stromu. Rezoluci budeme začínat cílem [¬s, ¬u]. Pravidla a fakta seřadíme a očíslujeme: 1: [q, ¬r] 2: [q, ¬t] 3: [q] 4: [r] 5: [u, ¬q] 6: [s] SLD strom zachycuje všechna možná vyhodnocení. Použitá fakta a pravidla jsou naznačena číslem u přísluěné hrany SLD stromu. Strom se větví právě v uzlech, kde lze aplikovat více faktů nebo pravidel. [¬s, ¬u] [¬u] [¬q] [¬t] neúspěch [¬r] 6 5 321 4 Každá (úspěšná) větev SLD stromu odpovídá jednomu rezolučnímu důkazu. Rezoluční strom pro nejlevější větev je uveden níže. [¬r] [¬q] [¬u] [¬s, ¬u] [s] [u, ¬q] [q, ¬r] [r] 65 Příklad 7.3.1. SLD rezolucí vyvraťte množinu klauzulí {[s], [t, ¬s, ¬r], [r, ¬s]}∪{[¬t, ¬r]}. Příklad 7.3.2. SLD rezolučním vyvrácením ukažte, že {q, (r∧t) ⇒ p, t ⇒ r, q ⇒ t} ⊨ p∧q. Příklad 7.3.3. Vytvořte SLD strom pro vyvrácení následující množiny uspořádaných klauzulí (čísla odpovídají prioritě při výběru daného předpokladu): {1 : [s], 2 : [p, ¬t], 3 : [p, ¬s], 4 : [r, ¬p], 5 : [r, ¬t]} ∪ {[¬r, ¬s]}. Příklad 7.3.4. Vytvořte SLD strom pro vyvrácení následující množiny uspořádaných klauzulí (čísla odpovídají prioritě při výběru daného předpokladu): {1 : [t, ¬s], 2 : [s, ¬t], 3 : [s], 4 : [r]} ∪ {[¬t, ¬r]}. 7.4 Prolog ve výrokové logice Programovací jazyk Prolog využívá SLD rezoluci k systematickému zjišťování, zda ze zadaných předpokladů plyne závěr. Nejprve se podíváme, jak vypadá program jazyka Prolog, a následně si ukážeme korespondenci mezi Prologem a SLD rezolucí. Definice 43: Program jazyka Prolog je konečná posloupnost předpokladů P1, . . . , Pn, kde předpoklady jsou dvojího typu: • Fakta, která jsou tvaru p., kde p je výroková proměnná. Fakt p. je ekvivalentní formuli p. • Pravidla, která jsou tvaru p :- q, ..., r., kde p, q, . . . , r jsou výrokové proměnné. Pravidlo p :- q, ..., r je ekvivalentní formuli p ⇐ (q ∧ · · · ∧ r). Nad zadaným programem jazyka Prolog se vyhodnocují dotazy. Dotaz je tvrzení, jehož vyplývání z předpokladů uvedených v programu chceme ověřit. Definice 44: Dotazy jsou tvaru ?- p, ..., q., kde p, . . . , q jsou výrokové proměnné. Dotaz ?- p, ..., q. je ekvivalentní formuli p ∧ · · · ∧ q. Ukažme si nyní korespondenci programu Prologu s Hornovými klauzulemi. Fakt p. lze přímočaře vyjádřit uspořádanou klauzulí [p]. Pravidlo tvaru p :- q, r., ekvivalentní formuli p ⇐ (q ∧ r), lze vyjádřit jako p ∨ ¬(q ∧ r), neboli p ∨ ¬q ∨ ¬r. To odpovídá uspořádané klauzuli [p, ¬q, ¬r]. Konečně chceme rezolucí dokázat, že z faktů a pravidel vyplývá závěr vyjádřený dotazem ?- s, r. s významem s∧r. Pro důkaz rezolučním vyvracením přidáme k pravidlům a faktům negaci formule s∧r, tedy ¬s∨¬r, neboli uspořádanou klauzuli [¬s, ¬r]. Uvedené klauzule odpovídají faktům, pravidlům a cíli tak, jak jsou definovány pro Hornovy klauzule (viz Definici 42). Díky přímé korespondenci s Hornovými klauzulemi lze pro programy Prologu vytvářet SLD rezoluční stromy. Zápis se liší v tom, že místo cíle tvaru [¬p, . . . , ¬q] zapisujeme průběžně vyhodnocovaný dotaz ve tvaru ?- p, ..., q. 66 Při zadání dotazu nad programem jazyka Prolog probíhá systematické hledání řešení, které odpovídá procházení SLD stromu do hloubky s prioritním výběrem pravidla nebo cíle uvedeného v programu dříve (tj. procházením alternativ zleva doprava). V případě vyvrácení zadaného cíle dojde k vytištění hodnoty true. Příklad. Vytvořte SLD strom pro dotaz ?- s, u. nad následujícím programem Prologu: 1. q :- r. 2. q :- t. 3. q. 4. r. 5. u :- q. 6. s. Rezoluci začínáme dotazem ?- s, u. Z pravidel a faktů programu při vyhodnocování vybíráme postupně shora dolů to, které odpovídá první proměnné dotazu. V případě faktu pak příslušnou proměnnou umažeme, v případě pravidla nahradíme pravou stranou za symbolem :-. Použitá fakta a pravidla jsou naznačena číslem u přísluěné hrany SLD stromu. Strom se větví právě v uzlech, kde lze aplikovat více faktů nebo pravidel. Prolog při vyhodnocování vždy vstupuje do nejprve do levých větví (tj. těch s nižším číslem použitého pravidla nebo faktu). ?- s, u. ?- u. ?- q. ?- t. fail. ?- r. 6 5 321 4 Úspěšné větve jsou zakončeny symbolem , neúspěšné symbolem fail. V běžných implementacích Prologu se programy, které obsahují proměnnou nedefinovanou ve faktu nebo na levé straně nějakého pravidla (jako např. t v tomto programu), ani nespustí. V případě výrokové logiky existence takové proměnné přešně odpovídá existenci neúspěšné větve v SLD stromu. Všimněte si, že ten samý SLD strom jsme již v jiném hávu viděli v ukázkovém příkladě v předchozí sekci o SLD rezoluci. Vedle úspěšných a neúspěšných větví uvedených v příkladu může navíc SLD strom obsahovat i větve nekonečné, kdy Prolog cyklí. Příklad 7.4.1. Uvažujte následující program Prologu: 67 1. p :- q. 2. q :- t. 3. q :- r. 4. r. 5. s :- p, q, r. a) Vytvořte SLD strom pro dotaz ?- s, r. b) Kolik obsahuje SLD strom úspěšných, resp. neúspěšných větví? c) Upravte program tak, aby SLD strom neobsahoval neúspěšné větve. Příklad 7.4.2. Uvažujte následující program Prologu: 1. p :- q. 2. p. 3. q :- p. a) Vytvořte SLD strom pro dotaz ?- p. Jaký výsledek vrátí Prolog po zadání dotazu? b) Navrhněte uspořádání pravidel, aby se Prolog nad žádným dotazem nezacyklil. c) Kolika způsoby může Prolog v takto upraveném programu dojít k výsledku true.? Příklad 7.4.3. Navrhněte program Prologu a dotaz, který obsahuje právě jednu úspěšnou větev, právě jednu nekonečnou větev a právě jednu neúspěšnou větev (nacházející se v SLD stromu v tomto pořadí zleva). (Úkol za bonus *1: Nalezněte takový program o 3 řádcích.) 7.5 Obecná rezoluce v predikátové logice Rezoluce v predikátové logice pracuje s formulemi ve Skolemově normální formě (viz kapitolu 6.3 Normální formy). Klauzule se opět zapisují jako množiny literálů, formule jako množiny klauzulí. Všeobecné kvantifikátory se v zápisu vynechávají. Formule ∀x∀y((P(y) ∨ ¬Q(y, x)) ∧ ¬P(f(c))) se zapíše jako {{P(y), ¬Q(y, x)}, {¬P(f(c))}}. Co když budeme chtít rezolvovat klauzule {P(y), ¬Q(y, x)} a {¬P(f(c))}} na predikátu P? Povšimněte si, že jako argument predikátu P je v první klauzuli použit term y, v druhé klauzuli term f(c). Abychom mohli na P rezolvovat, je nutné, aby obě klauzule „hovořily o stejném objektu“, takže je potřeba nejprve sjednotit (neboli unifikovat) použité termy. V uvažovaném příkladě se nabízí nahrazení (neboli substituce) proměnné y termem f(c), po kterém bude první klauzule tvaru {P(f(c)), ¬Q(f(c), x)} – všimněte si náhrady y za f(c) i v rámci predikátu Q. Jsme ovšem oprávněni takovou náhradu beztrestně provést? Podívejme se, jak vypadá původní klauzule v klasickém zápisu s kvantifikátory: ∀x∀y(P(y)∨¬Q(y, x)) a jak vypadá klauzule po substituci: ∀x(P(f(c))∨¬Q(f(c), x)). Lze konstatovat, že substituce proměnné za jiný term zachovala pravdivost. Platí-li totiž původní klauzule pro všechna y, pak platí pro libovolný term, kterým y nahradíme. Jelikož substituce zachovává pravdivost, lze ji provádět v rámci aplikace rezolučního pravidla (a občas je to nevyhnutelné). Odvození rezolventy z výše uvedených klauzulí budeme tedy celkem zapisovat následovně: 68 {¬Q(f(c), x)} {P(y), ¬Q(y, x)} {¬P(f(c))} y/f(c) Formalizaci obecné rezoluce v predikátové logice zahájíme u pojmu substituce. Definice 45: Substituce je množina {x1/t1, . . . , xn/tn}, kde xi jsou různé proměnné a ti jsou termy. Speciálně jsou-li všechna ti proměnné, hovoříme o přejmenování proměnných. Substituce jsou například množiny {x/y, y/f(c)}, {y/f(x)}, {x/y, y/z, z/x}. Poslední uvedená je navíc přejmenováním proměnných. Substituci Φ = {x1/t1, . . . , xn/tn} lze aplikovat na množinu literálů S tak, že každý výskyt každé proměnné xi nahradíme termem ti. Aplikaci substituce zapisujeme jako SΦ. Příklad. Pro množiny literálů S1 = {P(x, y), ¬Q(y, f(x))}, S2 = {P(f(x)), P(y), P(f(f(c)))} a substituce Φ1 = {x/c, y/b}, Φ2 = {x/f(c), y/f(f(c))} stanovte S1Φ1 a S2Φ2. S1Φ1 = {P(c, b), ¬Q(b, f(c))} S2Φ2 = {P(f(f(c)))}. Substituce Φ2 ve vztahu k množině S2 je v jistém smyslu speciální, všechny literály množiny S2 totiž substitucí přešly na ten samý literál. Takovým substitucím říkáme unifikátory. Definice 46: Substituce Φ je unifikátorem množiny S, pokud |SΦ| = 1. Existuje-li pro množinu unifikátor, hovoříme o unifikovatelné množině. Unifikátorem množiny {P(z, f(z)), P(f(x), f(f(c)))} je substituce {z/f(c), x/c}. Množina {P(z, f(z)), P(f(x), f(c))} není unifikovatelná. Unifikátory budou sloužit k dříve avizovanému sjednocení termů při aplikování rezolučního pravidla. To z technických důvodů aplikujeme na dvojice klauzulí, které nemají společné proměnné. (Pokud mají, nejprve proměnné přejmenujeme.) Definice 47: Rezoluční pravidlo pro predikátovou logiku: Uvažujme dvě klauzule bez společných proměnných {P(⃗t1), . . . , P(⃗tr), L1, . . . Ln}, {¬P(⃗t′ 1), . . . , ¬P(⃗t′ s), L′ 1, . . . , L′ m}, kde Li, resp. L′ i jsou literály (neobsahující predikát P), a substituci Φ, která je unifikátorem5 množiny {P(⃗t1), . . . , P(⃗tr), P(⃗t′ 1), . . . P(⃗t′ s)}. Jejich rezolventou je klauzule {L1, . . . , Ln, L′ 1, . . . , L′ m}Φ. 69 Rezolventou klauzulí {P(x), ¬Q(x)} a {Q(c)} je {P(c)} (příslušný unifikátor Φ = {x/c}). Rezolventou klauzulí {R(x, y), R(c, y), ¬Q(y)} a {¬R(z, d), P(z)} je klauzule {¬Q(d), P(c)} (příslušný unifikátor Φ = {x/c, y/d, z/c}). Obecnou rezoluci v predikátové logice jinak provádíme stejným způsobem jako v logice výrokové. Pojmy rezolučního důkazu a rezolučního vyvrácení zůstávají nezměněny, pouze využívají rezolučního pravidla pro predikátovou logiku. Navíc na hrany do rezolučního stromu píšeme provedené substituce/unifikace. Příklad 7.5.1. Nalezněte SΦ pro zadaná S a Φ. a) S = {P(x), Q(y)}, Φ = {x/y, y/x} b) S = {P(c, x), ¬P(x, f(z))}, Φ = {f(z)/x, x/d} c) S = {P(x, y), P(c, z), P(c, c)}, Φ = {x/y, y/z, z/c} Příklad 7.5.2. Nalezněte (nejobecnější) unifikátory následujících množin (c, d jsou kon- stanty). a) S = {P(x), Q(y)} b) S = {P(x), P(y)} c) S = {Q(x, x), Q(y, c)} d) S = {Q(x, x), Q(y, c), Q(d, z)} e) S = {P(x, f(x)), P(c, z), P(x, f(y))} f) S = {P(x, f(x)), P(x, z), P(x, f(y))} Příklad 7.5.3. Nalezněte rezolventy následujících dvojic klauzulí (c je konstanta). a) {P(x), ¬Q(z)}, {¬R(y), Q(y)} b) {¬P(c, x), Q(x)}, {P(y, y), ¬R(y, z)} c) {Q(x), ¬P(c)}, {P(y), ¬R(y, x)} d) {P(x, f(z)), P(y, y)}, {¬P(c, z)} e) {P(x, f(z)), P(y, y1)}, {¬P(c, z)} f) {Q(f(f(f(z))), f(f(y)))}, {¬Q(f(f(x)), x)} Příklad 7.5.4. Uvažujte následující tvrzení: • „Jablka nepadají daleko od stromu.“ • „Jím jenom jablka.“ • „Všechno padá daleko od stromu.“ Dokažte pomocí rezoluce, že z těchto tvrzení plyne „Nejím nic,“ a to dvěma způsoby: (1) přímým odvozením závěru a (2) vyvrácením množiny obsahující předpoklady a negaci závěru. Zejména v řešení a) převeďte tvrzení do formální reprezentace, b) určete význam (interpretaci) jednotlivých predikátů, 5 V rámci definice rezolučního pravidla lze formulovat silnější požadavek na Φ – totiž aby se jednalo o nejobecnější unifikátor. Zde se tímto pojmem pro jednoduchost zabývat nebudeme. 70 c) proveďte skolemizaci jednotlivých formulí a d) nakonec proveďte samotnou rezoluci. 7.6 Prolog v predikátové logice Použití Prologu v predikátové logice je o něco zajímavější. Predikáty zapisujeme malými písmeny (podobně jako výrokové symboly), do závorek uvádíme termy. Proměnné se značí velkými písmeny: X, Y, Z. Syntax Prologu i tvorbu SLD stromů si demonstrujeme na příkladě. Příklad. Uvažujte následující program jazyka Prolog: 1: otec(petr, marta). 2: otec(jan, petr). 3: otec(petr, jana). 4: matka(dana, marta). 5: matka(jitka, petr). 6: matka(dana, kveta). 7: rodic(X, Y) :- otec(X, Y). 8: rodic(X, Y) :- matka(X, Y). 9: babicka(X, Y) :- matka(X, Z), rodic(Z, Y). a) Zjistěte, zda je Dana rodičem Marty. Nakreslete SLD strom pro zadaný dotaz. b) Zjistěte, koho je Jitka babičkou. Nakreslete SLD strom pro zadaný dotaz. a) Zadaný dotaz je ?- rodic(dana, marta). SLD strom vypadá takto: ?- rodic(dana, marta). ?- matka(dana, marta).?- otec(dana, marta). fail. 8, X/dana, Y/marta 4 7, X/dana, Y/marta Všimněte si, že při aplikaci pravidel 7 i 8 došlo k unifikaci proměnných X, Y s konstantami dana, marta. Úspěšná větev potvrzuje, že Dana je skutečně rodičem Marty. Při zadání dotazu Prolog vypíše true. Protože nalezený výsledek je v nejpravější větvi, další prohledávání nebude umožněno. b) Zadaný dotaz je ?- babicka(jitka, X). SLD strom vypadá takto: 71 ?- babicka(jitka, X). ?- matka(jitka, Z), rodic(Z,X). ?- rodic(petr, X). ?- matka(petr, X). fail. ?- otec(petr, X). 9, P1/jitka, P2/X, P3/Z* 5, Z/petr 8, P1/petr, P2/X*7, P1/petr, P2/X* 3, X/jana1, X/marta Proměnné P1, P2 a P3 u substitucí s hvězdičkou vznikly přejmenováních proměnných v pravidlech (kvůli konfliktu názvů). Použitá pravidla po přejmenování (v pořadí, v jakém byla použita) byla tvaru 9: babicka(P1, P2) :- matka(P1, P3), rodic(P3, P2). 7: rodic(P1, P2) :- otec(P1, P2). 8: rodic(P1, P2) :- matka(P1, P2). Z SLD stromu lze vyčíst, že Jitka je babičkou Marty a Jany (dle substituce X/marta, resp. X/jana ve dvou úspěšných větvích SLD stromu). Při zadání dotazu Prolog vypíše nejprve X=marta, po zadání středníku X=jana. Po opětovném zadání středníku vypíše false (zbytek stromu neobsahuje úspěšnou větev) a neumožní další prohledávání. Příklad 7.6.1. Uvažujte následující program jazyka Prolog: 1: p(f(f(X))) :- p(X). 2: p(f(0)). a) Vytvořte SLD strom pro dotaz ?- p(f(f(f(0)))). Co vypíše Prolog po zadání dotazu? b) Vytvořte SLD strom pro dotaz ?- p(f(f(f(f(0))))). Co vypíše Prolog po zadání dotazu? c) Vytvořte SLD strom pro dotaz ?- p(X). Co vypíše Prolog po zadání dotazu? d) Jak se bude Prolog chovat nad dotazem ?- p(X)., prohodíme-li řádky 1 a 2? Příklad 7.6.2. Uvažujte následující program jazyka Prolog: 1: even(0). 2: even(f(f(X))) :- even(X). 3: odd(f(f(X))) :- odd(X). 4: odd(f(X)) :- even(X). 72 Vytvořte SLD strom pro dotaz ?- odd(f(f(f(f(f(0)))))). Příklad 7.6.3. Uvažujte následující program jazyka Prolog: 1: p(X) :- q(f(X)). 2: p(0). 3: q(X) :- p(X). Vytvořte SLD strom pro dotaz ?- p(0). Příklad 7.6.4. Uvažujte následující program jazyka Prolog: 1: p(0,0). 2: p(f(X), Y) :- p(X, f(Y)). 3: p(X, f(f(0))) :- p(X, 0). Vytvořte SLD strom pro dotaz ?- p(f(f(f(f(0)))), 0). a) Bude první větev výpočtu úspěšná? Pokud ne, přeuspořádejte řádky v programu tak, aby byla úspěšná první větev výpočtu. Vytvořte SLD strom tohoto upraveného programu pro stejný dotaz. b) Jak se přeuspořádání řádků projeví při vyhodnocování dotazu ?- p(X, 0).? 73 8 Neklasické logiky Neklasické logiky jsou logiky, které porušují principy extenzionality a dvouhodnotovosti, tedy principy, na nichž jsou založeny klasické logiky. Tyto principy klasické logiky různým způsobem omezují, například v oblasti reprezentace výrazů přirozeného jazyka. V této kapitole si představíme několik neklasických logik, které se mimo jiné snaží vypořádat právě s omezeními klasických logik. 8.1 Intenzionální logiky V přirozeném jazyce má každý výraz svůj význam a svou referenci. Význam výrazu se nazývá intenze a naopak reference výrazu, tedy to, na co výraz odkazuje, se nazývá extenze. Intenze výrazu je neměnná, extenze se naopak může v čase a prostoru měnit. Příklad. Pro výraz pes určete jeho: a) intenzi, b) extenzi. a) Intenze slova pes je jeho význam, vyjadřuje, co znamená být psem. Může například hovořit o tom, jak musí entita vypadat, aby mohla být označena jako pes, a jaké vlastnosti má mít pes. b) Extenze slova pes je to, na co výraz odkazuje. Tvoří ji všechny existující entity, které splňují podmínky bytí psem, tedy všichni psi. Klasické logiky jsou extenzionální, což znamená, že pracují pouze s extenzemi výrazů a tvrzení. Naproti tomu intenzionální logiky pracují také s intenzemi výrazů. Pro lepší pochopení rozdílu mezi intenzí a extenzí si ukážeme ještě jeden příklad. Příklad. Určete extenzi a intenzi následujících výrazů. a) Prezident ČR b) Batman c) Jednorožec d) Země je kulatá. e) Slunce je hvězda. a) Extenze výrazu je osoba, která je v současné době prezidentem. Intenze výrazu je samotný význam výrazu, to, co znamená být prezidentem – prezidentská role. 74 b) Extenze výrazu je osoba Bruce Wayne. Intenze výrazu může být superhrdina, který bojuje za spravedlnost. c) Tento výraz nemá extenzi; žádný konkrétní jednorožec neexistuje. Intenze vyjadřuje, že se jedná o bájného koně, který má uprostřed čela roh. d) Extenze výroku je pravda. Intenze tvrzení je jeho samotný obsah – informace, kterou nese. e) Extenze tvrzení je pravda. Intenze je informace o tom, že Slunce je hvězda. Všimněte si, že extenze tvrzení je vždy jeho pravdivostní hodnota. Dále také platí, že zatímco extenzi můžeme určit poměrně přesně, intenze výrazu je abstraktnější. Výraz ve větě interpretujeme buď jako jeho intenzi, nebo jako jeho extenzi. V prvním případě říkáme, že je použit v intenzionálním kontextu, v druhém případě říkáme, že je použit v extenzionálním kontextu. V extenzionálním kontextu můžeme výraz v tvrzení nahradit jiným výrazem se stejnou extenzí, aniž by se změnila pravdivostní hodnota (extenze) celého tvrzení. Jelikož klasické logiky vždy předpokládají extenzionální kontext, dovolují při práci s výrazy tuto úpravu. Problém nastává, je-li výraz v tvrzení ve skutečnosti použit v intenzionálním kontextu, ale v rámci klasické logiky s ním zacházíme jako s výrazem v kontextu extenzionálním. Po provedení substituce se tak může změnit pravdivostní hodnota celého výroku, což vede k nekonzistenci, protože klasická logika předpokládá, že hodnota zůstane nezměněna. Příklad. Zvýrazněné výrazy nahraďte výrazy v závorkách a rozhodněte, zda je pravdivostní hodnota celého výroku zachována. Poté rozhodněte, zda jsou zvýrazněné výrazy použity v intenzionálním nebo extenzionálním kontextu. a) Honza chce být Batmanem. (Bruce Wayne) b) Země je kulatá a Merkur je měsíc. (Slunce je hvězda.) c) Honza ví, že Země je kulatá. (Slunce je hvězda.) a) Honza chce být Bruce Waynem. Pravdivostní hodnota tvrzení není zachována. Honza chce být superhrdinou, jakého představuje Batman, ale ne boháčem Bruce Waynem. Jedná se tedy o intenzionální kontext. b) Slunce je hvězda a Merkur je měsíc. Pravdivostní hodnota tvrzení je zachována. Zachovala by se také, kdybychom tuto větu nahradili jakoukoli jinou větou, která je pravdivá. Jedná se tedy o extenzionální kontext. 75 c) Honza ví, že Sluce je hvězda. Pravdivostní hodnota tvrzení není zachována. Honza může vědět, že Země je kulatá, a nevědět, že Slunce je hvězda. Jedná se o intenzionální kontext. Skutečnost, že klasické logiky nerozlišují mezi extenzionálním a intenzionálním kontextem, je jedním z důvodů, proč nedokážou správně pracovat s přirozeným jazykem. Intenzionální logiky zavádějí formalismy, které pracovat s výrazy v intenzionálním kontextu umožňují, a díky tomu jsou schopny přirozený jazyk reprezentovat lépe. Mezi intenzionální logiky patří například TIL a modální logiky. Příklad 8.1.1. Rozhodněte, zda jsou zvýrazněné výrazy použity v intenzionálním, nebo extenzionálním kontextu. (Hint: pokud se neumíte rozhodnout, zkuste výrazy substituovat a rozmyslet si, jestli se tím změní význam věty.) a) Zmrzlinu znali už ve starověkém Řecku. b) Michalovi spadla zmrzlina na zem. c) Albert chce být běžcem. d) Běžec doběhl do cíle. e) Sousedův pes umí udělat salto. f) Michal by chtěl mít psa. g) Dáša řekla, že na Marsu žijí Marťané. h) Pokud na Marsu žijí Marťané, pak tam jsou budovy. i) Policie zadržela hledaného žháře. Příklad 8.1.2. Použijte uvedená slova ve dvou větách – v intenzionálním a extenzionálním kontextu. a) stromy b) vítěz turnaje c) tužka 8.2 Možné světy Svět v logice představuje určitý ohraničený prostor, nad kterým s logikou pracujeme. Stav, ve kterém se daný svět může nacházet, nazýváme možný svět a všechny možné stavy reprezentuje množina možných světů. Mezi možnými světy je jeden aktuální svět, který odpovídá skutečnému stavu světa. Pomocí možných světů zavádíme sémantiku modálních logik. Možné světy mohou být propojeny pomocí relace dostupnosti. Definice 48: Relace dostupnosti je binární relace S ⊆ W2 na množině možných světů W. Říkáme, že svět v je dostupný ze světa w právě tehdy, když platí (w, v) ∈ S. 76 Obecně platí, že relace dostupnosti představuje určitou formu možnosti. Za možné světy ve světě w ∈ W považujeme pouze ty světy, které jsou z w dostupné. Možným světům a vztahům přístupnosti přiřazujeme konkrétnější význam v závislosti na modální logice, v níž jsou použity. Například v temporální logice představují možné světy okamžiky v čase a dostupnost mezi světy představuje změnu stavu světa v čase. Příklad. Uvažte svět, který obsahuje pouze výroky p, q, r, a v němž platí p ⇒ q. a) Kolik takových možných světů existuje? b) Přidejme podmínku, že ve světě platí také p ∨ ¬r. Kolik možných světů existuje v takovém případě? a) 6 možných světů. Světy p, ¬q, r a p, ¬q, ¬r nejsou možné. b) 4 možné světy. Z další podmínky vyplývá, že dva světy, v nichž platí ¬p ∧ r, také nejsou možné. Příklad 8.2.1. Dáša má dvě rostliny, fialku a zelenec, které zalévá vždy současně. Zelenec uvadne 4 až 6 dní po zalití. Fialka uvadne 10 až 15 dní po zalití. Uvažme zjednodušený svět, který obsahuje pouze tyto dvě rostliny, a v němž je stav rostliny binární – buď je uvadlá, nebo není. a) Uveďte, kolik existuje možných světů. b) Dáša řekla, že rostliny naposledy zalévala před dvěma týdny. Uveďte, kolik možných světů existuje, pokud tuto informaci znáte, a které to jsou. Příklad 8.2.2. V bufetu se prodává káva, bagety a croissanty. Ne vždy ale mají kompletní nabídku. Mějme svět, který reprezentuje stav bufetové nabídky. a) Uveďte, kolik existuje možných světů. b) Zjistíte, že v bufetu mají vždy croissanty nebo bagety, ale nemají je současně. Uveďte, kolik možných světů existuje, pokud tuto informaci znáte, a které to jsou. Příklad 8.2.3. Do bufetu z předchozího zadání (neberte v úvahu omezení zavedené v bodě b)) přijde student. Chce si koupit kávu, nebo, pokud ji nemají, cokoli jiného. Jak se změní stav bufetu po jeho odchodu? Předpokládejte, že student si koupí pouze jednu věc a káva se může vyprodat také. Možné stavy bufetu reprezentujte pomocí možných světů. Změnu stavu bufetu reprezentujte pomocí relace dostupnosti. Možné světy a relaci graficky znázorněte. 8.3 Modální logiky a K-logika Modální logiky jsou intenzionální logiky, které se zabývají různými modalitami neboli módy pravdy. Mezi tyto modality patří: 77 • Aletická modalita – vyjadřuje nutnost – nutně platí, možná platí. • Temporální modalita – vyjadřuje platnost v určitém časovém okamžiku – vždy platilo, bude platit. • Deontická modalita – vyjadřuje, jak by věci měly být – je povinné, je povoleno. • Epistemická modalita – vyjadřuje znalost a přesvědčení – Albert ví, že platí, Albert věří, že platí. Naproti tomu v klasické logice uvažujeme pouze o tom, zda je tvrzení pravdivé nebo neprav- divé. Modality reprezentujeme pomocí modálních operátorů. Ty se od logických operátorů liší tím, že pravdivostní hodnota na jejich výstupu závisí nejen na pravdivostní hodnotě vstupních tvrzení (extenzi), ale také na významu samotných tvrzení (intenzi). Jelikož klasické logiky nepracují s intenzemi výrazů, modality správně reprezentovat nedokážou. K-logika je formální systém pracující s modalitou nutnosti, kterou reprezentuje pomocí modálních operátorů nutně a možná . K-logika je navíc základní modální logika – její úpravou můžeme zavést logiky dalších modalit. V této kapitole zavádíme K-logiku s využitím výrokové logiky. Nejprve rozšíříme abecedu výrokové logiky o symboly modálních operátorů: Definice 49: Abeceda K-logiky zahrnuje: • abecedu výrokové logiky, • symboly , . Do syntaxe výrokové logiky následně přidáme pravidlo pro tvorbu formulí, které obsahují modální operátory: Definice 50: Je-li φ formule, pak také ( φ) a ( φ) jsou formule. Dále zavedeme sémantiku K-logiky. Interpretace K-logiky, nazývaná Kripkeho interpretace nebo Kripkeho rámec, nepředstavuje jediný stav světa (jako interpretace v klasických logikách), ale více stavů. Každý stav je reprezentován jako možný svět a odpovídající interpretace elementárních výroků. Definice 51: Kripkeho interpretace (též Kripkeho rámec) pro jazyk L je struktura C zahrnu- jící: • množinu možných světů W, • relaci dostupnosti S ⊆ W2 , 78 • interpretaci výrokových proměnných Iw, pro každý svět w ∈ W. Relace dostupnosti pro každý možný svět w určuje, které světy jsou z něj dostupné. Dostupné světy ze světa w chápeme jako světy, které jsou ve světě w možné. Interpretace Iw pro každý možný svět w určuje, které elementární výroky v něm jsou nebo nejsou pravdivé. Jelikož různé světy vyhodnocují elementární výroky různě, i složitější formule může v různých světech nabývat různých pravdivostních hodnot. Definice 52: Zda formule φ platí ve světě w ∈ W, píšeme w |= φ, definujeme následovně: • w |= p, právě když atomická formule p je pravdivá v Iw, • w |= (φ ⇒ ψ), právě když neplatí w |= φ nebo platí w |= ψ (a podobně pro ostatní logické spojky), • w |= φ, právě když v |= φ pro všechny světy v ∈ W takové, že (w, v) ∈ S, • w |= φ, právě když existuje svět v ∈ W takový, že (w, v) ∈ S a v |= φ. Je-li formule atomická, platí ve světě w právě tehdy, když je pravdivá v Iw. V případě logických spojek zůstává sémantika stejná jako ve výrokové logice. Formule φ je nutně pravdivá ve světě w, píšeme φ, právě když je pravdivá ve všech světech dostupných z w. Formule φ možná platí ve světě w, píšeme φ, právě když platí alespoň v jednom světě dostupném ze světa w. Všimněte si, že sémantika modálních operátorů a je podobná sémantice kvantifikátorů ∀ a ∃. Stejně jako u nich platí i u modálních operátorů, že jeden lze odvodit z druhého, tedy: φ ⇔ ¬ ¬φ. Nakonec zbývá definovat pravdivost v interpretaci a logickou pravdivost. Definice 53: • Formule φ je pravdivá v Kripkeho interpretaci C, píšeme |=C φ, jestliže platí ve všech světech w ∈ W. • Formule φ je logicky pravdivá (tautologie), jestliže platí ve všech Kripkeho interpre- tacích. Vyhodnocení K-logické formule v Kripkeho interpretaci si ukážeme na příkladu. Příklad. Uvažte Kripkeho rámec C, kde W = {w1, w2, w3}, S = {(w1, w2), (w1, w3), (w2, w2)} a elementární výroky jsou p, q. Ve světech platí následující tvrzení: • w1 : p, q, 79 • w2 : p, • w3 : q. Pomocí grafu znázorněte možné světy a relaci dostupnosti. Pak rozhodněte, zda je formule (¬q ∨ p): a) platná ve světě w1, b) platná v Kripkeho interpretaci C, c) logicky pravdivá. Grafické znázornění možných světů a vztahů mezi nimi může vypadat následovně: w1 : p, q w2 : p w3 : q Nejprve vytvoříme pravdivostní tabulku, ve které vyhodnotíme formuli pro všechny světy. Ta je užitečná i v případě, že máme vyhodnotit platnost formule pouze v jednom světě. Chcemeli například rozhodnout, zda φ platí v nějakém světě, musíme nejdříve vyhodnotit formuli φ pro všechny světy, které jsou z tohoto světa dostupné. w1 w2 w3 p 1 1 0 q 1 0 1 ¬q 0 1 0 ¬q ∨ p 1 1 0 (¬q ∨ p) 0 1 1 (¬q ∨ p) 1 1 0 Pomocí tabulky pak odpovíme na otázky ze zadání: a) Ano, formule (¬q ∨ p) platí ve světě w1. b) Ne, formule neplatí v interpretaci C, protože neplatí ve světě w3. c) Ne, formule není logicky pravdivá, protože neplatí v interpretaci C. Příklad 8.3.1. Určete modalitu věty. a) Včera pršelo. b) Hana je přesvědčena, že káva není zdravá. c) Možná má můj pes chřipku. d) Kočky nevědí, že Merkur je planeta. 80 e) Na tomto místě se nesmí skákat do vody. Příklad 8.3.2. Pomocí K-logiky formálně zapište následující věty: a) Možná prší nebo možná svítí slunce. b) Možná prší a svítí slunce zároveň. c) Pokud je duha, pak nutně prší a svítí slunce zároveň. Příklad 8.3.3. Uvažte Kripkeho rámec C, kde W = {w1, w2, w3}, S = {(w1, w3), (w2, w2), (w2, w1), (w2, w3)} a elementární výroky jsou p, q. Ve světech platí následující tvrzení: • w1 : q, • w2 : ¬p, • w3 : q, p. Rozhodněte, zda je formule (¬ q ∨ p) ∧ (p ⇒ p): a) platná ve světě w1, b) platná v Kripkeho interpretaci C, c) logicky pravdivá. Příklad 8.3.4. Uvažte Kripkeho rámec C, kde W = {w1, w2, w3}, S = {(w1, w1), (w1, w2), (w2, w1), (w3, w2)} a elementární výroky jsou p, q, r. Ve světech platí následující tvrzení: • w1 : p, • w2 : q, • w3 : p, r. Bez použití pravdivostní tabulky rozhodněte, zda v dané interpretaci platí následující for- mule: a) p b) ¬ ¬q c) ¬ r d) p ∨ p e) r ⇒ r Příklad 8.3.5. Uvažte Kripkeho rámec C, kde W = {w1, w2, w3, w4}, S = {(w2, w2), (w3, w4), (w4, w3), (w4, w1)}, a elementární výrok p, který platí ve světech w2 a w3. Pomocí pravdivostní tabulky určete, ve kterých světech platí následující formule: a) ¬ p b) p c) p Příklad 8.3.6. Znegujte následující formule a upravte je tak, aby se symboly negace nacházely pouze přímo před elementárními výroky: a) ((¬p ⇒ q) ∨ ¬q) b) ( ¬p ∧ q) ∨ ¬p c) (p ⇒ q) 81 Příklad 8.3.7. Pro každou následujících formulí rozhodněte, zda je tautologie. Pokud ne, určete nějakou podmínku relace dostupnosti tak, aby formule platila ve všech interpretacích, které podmínku splňují. a) p ⇒ p b) (p ⇒ q) ⇒ ( p ⇒ q) c) p ⇒ p d) p ⇒ p Příklad 8.3.8. Uvažte Kripkeho rámec C, kde W = {w1, w2, w3} a elementární výroky jsou p, q, r. Ve světech platí následující tvrzení: • w1 : p, • w2 : q, • w3 : p, r. Doplňte relaci dostupnosti Kripkeho rámce C tak, aby v ní platila formule: a) p ⇒ r b) (q ∧ r) c) p 8.4 Vícehodnotové logiky Vícehodnotové logiky jsou podobné klasickým logikám v tom, že pravdivostní hodnota celého výrazu se skládá z pravdivostních hodnot dílčích výrazů, jsou tedy extenzionální. Nicméně se od nich liší tím, že pracují s více než dvěma pravdivostními hodnotami. Pravdivostní hodnoty se většinou pohybují v intervalu od 0 do 1, přičemž 0 obecně představuje absolutní nepravdu a 1 absolutní pravdu, avšak konkrétní interpretace závisí na oblasti použití logiky. Mezi vícehodnotové logiky patří tříhodnotová Lukasiewiczova logika. Kromě pravdivostních hodnot 0 (nepravda) a 1 (pravda) zavádí hodnotu 1/2 (nevím). Následující definice je obdobou definice interpretace z klasické výrokové logiky. Definice 54: Interpretace I v Lukasiewiczově logice je zobrazení I : P → {0, 1/2, 1} přiřazující pravdivostní hodnoty 0 (nepravda), 1 (pravda) a 1/2 (nevím) jednotlivým výrokovým proměnným množiny P. Kvůli této změně zavádí Lukasiewiczova logika také novou valuační funkci val (obdobu valuace), která umí pracovat s hodnotou 1/2 a zachovává sémantiku logických spojek. Definice 55: Valuační funkce valI příslušící interpretaci I je definována indukcí ke struktuře formule: • valI(p) = I(p), pro atomickou formuli p ∈ P, 82 • valI(¬φ) = 1 − valI(φ), • valI(φ ∧ ψ) = min(valI(φ), valI(ψ)), • valI(φ ∨ ψ) = max(valI(φ), valI(ψ)), • valI(φ ⇒ ψ) = min(1, 1 − valI(φ) + valI(ψ)). V Lukasiewiczově logice nelze implikaci obecně vyjádřit negací a disjunkcí, protože rovnost val(p ⇒ q) = val(¬p ∨ q) neplatí vždy. V případě val(p) = 1/2, val(q) = 1/2 totiž val(p ⇒ q) = 1, ale val(¬p ∨ q) = 1/2. V Lukasiewiczově logice je modelem formule každá interpretace, v níž je hodnota formule větší než 0. Definice 56: Modelem formule φ v Lukasiewiczově logice je interpretace I taková, že pro jí příslušící valuační funkci platí valI(φ) > 0. Příklad. Uvažte formuli p ⇒ ¬(q ∨ p) Lukasiewiczovy logiky. Rozhodněte, zda je interpretace I(p) = 1/2, I(q) = 0 modelem formule. Ano, daná interpretace je modelem formule, protože valI(p ⇒ ¬(q ∨ p)) = 1. Formuli vyhodnotíme postupně podle definice funkce valI. Mezivýpočty jsou uvedeny v tabulce. p ⇒ ¬ (q ∨ p) 1/2 1 1/2 0 1/2 1/2 Další vícehodnotovou logikou je fuzzy logika, která umožňuje vyjádřit míru pravdivosti nejednoznačných výroků, jako je například výrok Petr je mladý. Fuzzy logika nepracuje s diskrétními pravdivostními hodnotami, ale s intervalem hodnot [0, 1]. Definice 57: Interpretace I ve fuzzy logice je zobrazení I : P → [0, 1] přiřazující pravdivostní hodnoty z intervalu [0, 1] jednotlivým výrokovým proměnným množiny P. Model formule a valuační funkce jsou definovány stejně jako v Lukasiewiczově logice s tím rozdílem, že valuační funkce pracuje nad spojitou doménou. 83 Definice 58: Modelem formule φ ve fuzzy logice je interpretace I taková, že pro jí příslušící valuační funkci platí valI(φ) > 0. Příklad. Uvažte formuli (p ∨ ¬q) ∧ ¬p fuzzy logiky. Rozhodněte, zda je interpretace I(p) = 0.2, I(q) = 0.9 modelem formule. Ano, daná interpretace je modelem formule, protože valI((p ∨ ¬q) ∧ ¬p) = 0.2. Formuli vyhodnotíme postupně podle definice funkce valI. Mezivýpočty jsou uvedeny v tabulce. (p ∨ ¬ q) ∧ ¬ p 0.2 0.2 0.1 0.9 0.2 0.8 0.2 Příklad 8.4.1. Uvažte interpretaci Lukasiewiczovy logiky I(p) = 1/2, I(q) = 0, I(r) = 1/2. Rozhodněte, zda je modelem následujících formulí: a) ¬(p ∧ r) b) p ⇒ (q ∨ ¬r) c) ¬(r ⇒ q) d) (r ∨ ¬r) ∧ q Příklad 8.4.2. Uvažte formuli (p ⇒ q) ∧ (p ∨ ¬q) Lukasiewiczovy logiky. Vytvořte pravdivostní tabulku, která zahrnuje pouze interpretace obsahující hodnotu 1/2, a rozhodněte, které z nich jsou modelem formule. Příklad 8.4.3. Uvažte interpretaci fuzzy logiky I(p) = 0.3, I(q) = 0.6, I(r) = 0.2. Rozhodněte, zda je modelem následujících formulí: a) (¬p ∧ q) ∨ r b) q ⇒ ¬r c) ¬r ⇒ p d) (r ∧ ¬q) ∨ ¬(q ∧ p) Příklad 8.4.4. Uvažte formuli (p ⇒ q) ∧ (p ∧ ¬q) fuzzy logiky. Nalezněte interpretaci, ve které je valuace formule větší než 0.5. Příklad 8.4.5. Nalezněte interpretaci fuzzy logiky, která je modelem všech následujících formulí: • p ⇒ r • ¬q • q ∨ ¬r Příklad 8.4.6. Pro každou z následujících formulí uveďte interpretaci fuzzy logiky, která není její modelem. 84 a) ¬p b) p ∧ ¬q c) (p ∨ q) ⇒ r Příklad 8.4.7. Uvažte interpretaci I(p) = 0, I(q) = 0.5, I(r) = x. Nalezněte množinu všech hodnot x takových, že valuace formule ¬(q ∧ ¬r) ∨ (r ⇒ p) fuzzy logiky se rovná hodnotě: a) 0 b) 0.5 c) 0.8 d) 1 85 9 Reprezentace a vyvozování znalostí K tomu, aby inteligentní systém správně fungoval, mu potřebujeme dodat dostatek informací o světě, ve kterém pracuje, a naučit ho, jak tyto informace využívat. Oblast reprezentace znalostí se zabývá tím, jak znalosti vyjádřit ve formě, jež je vhodná pro počítačové zpracování, zatímco oblast vyvozování znalostí se zabývá tím, jak s uloženými znalostmi pracovat a odvozovat z nich znalosti nové. V této kapitole si několik přístupů k reprezentaci a vyvozování znalostí představíme. Důležitou součástí reprezentování znalostí je organizování objektů do kategorií neboli tříd. Ve fyzické realitě sice přicházíme do kontaktu hlavně s objekty, ale na úrovni myšlení a vyvozování pracujeme ve velkém s kategoriemi. Například pokud si někdo chce koupit stejnou klávesnici, jako má jeho kamarád, nechce ten samý objekt, ale model klávesnice. Stejně tak zařazení objektu do kategorie nám často umožní odvodit o něm nové znalosti. Například vidíme-li v sekci ovoce v obchodě zelený, velký a kulatý objekt, zařadíme jej do kategorie meloun, z čehož můžeme následně odvodit informaci, že vevnitř má červenou dužinu. V predikátové logice bychom mohli kategorie reprezentovat jako predikát, ale při tomto přístupu nedokážeme správně reprezentovat vlastnosti třídy. Kategorii proto reprezentujeme jako konstantu. Příslušnost do kategorie, která je reprezentována konstantou ověříme použitím predikátu, například Member(m, meloun), jenž se vyhodnotí jako pravdivý, pokud je m instancí kategorie meloun. Takové modelování abstrakce jako objektu se nazývá reifikace neboli zvěcnění. Objekty a třídy organizujeme do hierarchie tříd, třída může být podtřídou či nadtřídou jiné třídy, objekt je instancí nějaké třídy. Kromě hierarchie tříd se budeme zbývat i tím, jak reprezentovat další znalosti o pojmech, ty nazýváme i fakta, týkají-li se objektů a pravidla, týkají-li se tříd. 9.1 Ontologie Ontologie je formální systém, který popisuje svět, případně jeho část, skrze pojmy, vztahy mezi pojmy a axiomy. S použitím ontologie můžeme potom vyjádřit konkrétní znalosti o daném světě. Ontologie můžeme zavést pomocí různých formalismů, v této sbírce budeme používat predikátovou logiku. Ontologie dělíme na doménové a všeobecné (upper ontologies). Všeobecná ontologie se snaží popsat celý svět a poskytnout tak nástroj na reprezentování znalostí z libovolné oblasti. Naproti tomu doménová ontologie je specifičtější například v zavedených pojmech a uzpůsobená pro reprezentaci nějaké konkrétní domény. Jednoduchou ontologii si ukážeme na příkladu. 86 Příklad. Aby student získal zápočet, potřebuje získat alespoň 10 bodů z domácích úkolů a 15 bodů z testu. Zaveďte ontologii, která popisuje uvedenou situaci. Nejprve pomocí predikátové logiky zavedeme jazyk ontologie, tj. všechny pojmy, které jsou nezbytné k popisu situace. Můžeme používat konstanty, funkce a predikáty. • Úkoly(s, b): predikát, pravdivý, pokud má student s z domácích úkolů b bodů. • Test(s, b): predikát, pravdivý, pokud má student s z testu b bodů. • Zápočet(s): predikát, pravdivý, pokud byl studentovi s udělen zápočet. • +, ≤: funkce a predikát, oba se standardní sémantikou. • 10, 15: konstanty, reprezentují minimální nutný počet bodů. Dále zavedeme obecně platné axiomy: • A1: ∀s Zápočet(s) ⇐⇒ ∃b 10 ≤ b ∧ Úlohy(s, b) ∧ ∃b 15 ≤ b ∧ Test(s, b) V dalším příkladu si ukážeme, jak lze ontologii použít k reprezentaci konkrétní situace a odvození znalostí. Příklad. Albert získal 12 bodů za domácí úkoly a 20 bodů z testu. Pomocí ontologie z předchozího příkladu reprezentujte situaci a odvoďte, zda Albert dostane zápočet. Nejprve zavedeme tvrzení specifická pro danou situaci: • Úlohy(Albert, 12) • Test(Albert, 20) Z axiomu A1 potom plyne, že platí predikát Zápočet(Albert), a tudíž Albert zápočet získal. Příklad 9.1.1. Uvažujme následující neúplný jazyk ontologie, který reprezentuje hru piškvorky: • Player(p): predikát, p je hráč • Mark(m): predikát, m je značka • Square(q): predikát, q je pole • p×, p : konstanty, hráči „křížek“, resp. „kolečko“ • q11, q12, ..., q33: konstanty, pole herního plánu • s0: konstanta, počáteční situace, situace reprezentuje stav hry • WinningPosition(q1, q2, q3): predikát, pravdivý pro pole, která tvoří výherní pozici • Opponent(p): funkce, reprezentuje protihráče hráče p • Wins(p, s): predikát, pravdivý, pokud v situaci s vyhrál hráč p • Play(p, q): funkce, reprezentuje akci, že hráč p označí pole q 87 • Poss(a, s): predikát, je pravdivý, pokud je možné vykonat akci a v situaci s • Result(a, s): funkce, reprezentuje situaci, jež nastane po provedení akce a v situaci s Jazyk doplňte o pojmy, které budou reprezentovat: a) značky, které mohou být umisťovány na pole, b) informaci o tom, která značka patří zadanému hráči, c) informaci o tom, který hráč je na tahu v zadané situaci, d) informaci o tom, která značka je umístěna na zadaném poli. Příklad 9.1.2. V ontologii vytvořené v předchozím příkladu chybí axiomy, které by určovaly sémantiku zavedených predikátů a funkcí. Doplňte ontologii o následující axiomy: a) Nikdo jiný kromě p× a p není hráčem. b) Oponent hráče p× je p . c) Značka hráče p je . d) Vítězné pozice se skládají pouze z polí, která se nacházejí v jednom řádku, sloupci nebo diagonále (formuli nepište celou, repetitivní části můžete vynechat). e) Axiom určující, kdy platí Win(p, s). f) Axiom určující, kdy platí Poss(a, s). Příklad 9.1.3. Využijte nástroj, který pro slovo přirozeného jazyka najde odpovídající pojmy ontologie SUMO (pro více informací o nalezených pojmech je rozklikněte) a určete: a) pojmy související se slovem coffee, b) pojem p, který reprezentuje zimní roční období, c) s čím je pojem p ekvivalentní, d) pojem, jehož podtřídou je pojem p. e) Nalezněte výraz, který obsahuje pojem p a pojem MediterraneanClimateZone, a určete jeho význam. Příklad 9.1.4. Určete význam následujících výrazů ontologie SUMO. Pokud neumíte odvodit význam nějakého pojmu, můžete si ho vyhledat zde. a) (=⇒ (attribute ?AREA MountainousTerrain) (exists(?MTN) (and (instance ?MTN Mountain) (located ?MTN ?AREA)))) b) (=⇒ (and (instance ?SMILE Smiling) 88 (agent ?SMILE ?AGENT)) (holdsDuring (WhenFn ?SMILE ) (attribute ?AGENT Happiness))) c) (=⇒ (instance ?O OlympicGames) (or (exists(?W) (and (instance ?W WinterSeason) (temporalPart (WhenFn ?O) ?W))) (exists(?S) (and (instance ?S SummerSeason) (temporalPart (WhenFn ?O) ?S))))) 9.2 Sémantické sítě a rámce Sémantické sítě reprezentují pojmy a vztahy mezi pojmy. Mají formu grafu, přičemž uzly grafu představují pojmy a hrany vztahy. Nejdůležitější vztahy jsou instance a podtřída, které tvoří hierarchii pojmů. Další vztahy reprezentují vlastnosti pojmů, například Barva(beruška, červená), nebo příslušnost části k celku, Část(noha, kráva). Vztahy, jež souvisí s hierarchií pojmů zapisujeme ve vertikálním směru, ostatní vztahy zapisujeme horizontálně. Sémantické sítě podporují dědičnost a mechanismus vzoru a výjimky. Pojmy dědí vzorové hodnoty vlastností z nadtříd, přičemž vždy platí ta hodnota, která je k pojmu nejblíže. Vzorovou hodnotu může přepsat výjimka uvedená u uvažovaného pojmu. Princip dědičnosti neplatí nutně v horizontálních vztazích. Například noha, jako část krávy, zdědí barvu krávy, ale nedědí oblíbené jídlo krávy. Příklad. Uvažte následující sémantickou síť. 89 ovoce rajčemaliny maliny v kuchyni ano červená ne sladká podtřídapodtřída instance do zmrzlinychuť barva do zmrzliny a) Je rajče sladké? b) Je rajče vhodné do zmrzliny? c) Jaké znalosti lze vyvodit ze sítě o pojmu maliny v kuchyni? a) Ano. b) Ne. c) Maliny v kuchyni jsou instancí kategorie maliny, jsou ovoce, mají červenou barvu, jsou sladké a vhodné do zmrzliny. Rámec je univerzální struktura, v níž jsou uloženy veškeré relevantní informace o pojmech. Stejně jako sémantické sítě, rámce reprezentují taxonomii pojmů, jejich vlastnosti, avšak mají textovou podobu. Pojem je v rámci reprezentovaný pomocí následujících hodnot: • objekt – samotný pojem • sloty – vztahy daného pojmu • hodnoty slotů - pojmy, které jsou v uvedeném vztahu s daným pojmem. Rámce též podporují dědičnost a výjimky. Hvězdičkou jsou označeny sloty, které nesou vzorové hodnoty a mohou být při dědění přepsány výjimkou. Příklad. Pomocí rámce reprezentujte znalosti ze sémantické sítě z předchozího příkladu. 90 objekty sloty hodnoty ovoce *chuť: sladká *do_zmrzliny: ano rajče podtřída: ovoce do_zmrzliny: ne maliny podtřída: ovoce *barva: červená maliny v kuchyni instance: maliny Objekty a hodnoty slotů jsou ekvivalentní s uzly grafu sémantické sítě, sloty jsou ekvivalentní s hranami grafu. Příklad 9.2.1. Vytvořte sémantickou síť, která bude reprezentovat aspoň 4 libovolné kategorie domácích zvířat a jejich vlastnosti. Příklad 9.2.2. Uvažte následující sémantickou síť, která částečně reprezentuje magické tvory. tvor napůl kůňnapůl lev kentaurhipogryf testrál Buckbeak Firenze podtřídapodtřída podtřída podtřída podtřída instance instance zvířecí inteligence 4 nohy 2 nohy lidská inteligence křídla část hnědá barva učitel zaměstnání Odpovězte na následující otázky. a) Mají hipogryfové lidskou inteligenci? b) Má Firenze lidskou inteligenci? 91 c) Kolik noh mají testrálové? d) Jakou barvu má hipogryf? Příklad 9.2.3. Podle informací vyplývajících ze sémantické sítě z předchozího příkladu popište, co víte o následujících pojmech: 1. Buckbeak, 2. Firenze, 3. napůl lev. Příklad 9.2.4. Pomocí rámce reprezentujte znalosti o pojmech napůl kůň a Firenze, které jsou vyznačeny v sémantické síti v Příkladu 9.2.2. Příklad 9.2.5. Uvažte následující rámec: akční film podtřída: film *exploze ano Drive instance: akční film exploze: ne Skyfall instance: akční film série: James Bond komedie zábavná ano podtřída: film černá komedie podtřída: komedie *země původu: Velká Británie humor: černý Horší než smrt instance: černá komedie Big Lebowski instance: černá komedie země původu: USA romantická komedie: podtřída: komedie *konec: šťastný Annie Hall instance: romantická komedie Rozhodněte, zda z rámce vyplývají následující tvrzení: a) Všechny akční filmy obsahují exploze. b) Skyfall obsahuje exploze. c) Akční film má více instancí než černá komedie. 92 d) Horší než smrt je z Británie. e) Annie Hall je z USA. f) Big Lebowski je zábavný film. Příklad 9.2.6. Rámec z předchozího příkladu převeďte na sémantickou síť. 9.3 Nejisté znalosti V běžném životě se často setkáváme s nejistými znalostmi. K reprezentaci neurčitých znalostí se používají například nemonotónní logiky, které předpokládají, že výchozí výroky jsou pravdivé, dokud nejsou vyvráceny. Dalším přístupem je práce s pravděpodobností, které se budeme věnovat v tomto oddílu. Při definování pravděpodobnosti pracujeme s množinou (všech) elementárních jevů Ω, která zahrnuje všechny možné výsledky náhodného pokusu. V případě hodu kostkou by bylo Ω = {1, 2, ..., 6}, v případě hodu mincí Ω = {rub, líc}. Každá podmnožina množiny všech elementárních jevů se nazývá jev. V případě hodu kostkou může být jevem například „padné sudé číslo“, čili množina {2, 4, 6}. Množinu všech jevů značíme 2Ω (známá též obecně jako potenční množina či množina všech podmnožin). Definice 59: Uvažme konečnou množinu elementárních jevů Ω. Pravděpodobnost je funkce P : 2Ω → [0, 1] přiřazující jevům hodnoty z intervalu [0, 1], která splňuje • P(Ω) = 1, čili pravděpodobnost celé množiny jevů je 1, • P(A∪B) = P(A)+P(B) pro disjunktní množiny A ⊆ Ω, B ⊆ Ω, čili pravděpodobnost disjunktních množin je aditivní. Množina elementárních jevů Ω vybavená pravděpodobností P se nazývá pravděpodobnostní prostor (Ω, P). Intuitivní chápání definice pravděpodobnosti je, že hodnota P(A) určuje pravděpodobnost, že při náhodném pokusu nastane nějaký z jevů ω ∈ A. Pokud je A = Ω, pochopitelně je pravděpodobnost 1, jelikož nějaký z jevů nastat musí. Vyplývá z axiomů, že P(∅) = 0? Vyplývá z axiomů, že P(Ω − A) = 1 − P(A)? Rozmyslete si. Příklad. Jsou následující funkce pravděpodobnosti nad množinou Ω = {rub, líc}? U těch, které nejsou, dokažte. a) Pa = {∅ → 0, {rub} → 0.2, {líc} → 0.7, {rub, líc} → 1}, b) Pb = {∅ → 0, {rub} → −0.2, {líc} → 1.2, {rub, líc} → 1}}, c) Pc = {∅ → 0, {rub} → 0, {líc} → 1, {rub, líc} → 1}}, d) Pd = {∅ → 0.3, {rub} → 0.3, {líc} → 0.7, {rub, líc} → 1}}, a) Ne, protože Pa({rub, líc}) = 1 ̸= 0.9 = Pa({rub}) + Pa({líc}). 93 b) Ne, protože Pb({rub}) = −0.2 /∈ [0, 1]. c) Ano. d) Ne, protože Pd({rub}) = 0.3 ̸= 0.6 = Pd({rub}) + Pd(∅). Elementární jevy často vykazují nějaké číselné charakteristiky, jako například číslo hozené na kostce či množství srážek v mm. K popisu číselných charakteristik slouží pojem náhodné proměnné. Definice 60: Náhodná proměnná X nad pravděpodobnostním prostorem (Ω, P) je libovolná (měřitelná) funkce X : Ω → R. Náhodná proměnná tedy přiřazuje každému elementárnímu jevu číselnou hodnotu. Speciálním typem je booleovská náhodná proměnná, která své číselné hodnoty omezuje na 0 (nepravda) a 1 (pravda). Příklad. Uvažme pokus, ve kterém 4 krát hodíme mincí. Dále mějme následující výsledek pokusu: líc, líc, rub, líc. Uvažte následující náhodné proměnné: a) V každém hodu padl líc. b) Počet padlých líců. Jakých hodnot nabudou tyto proměnné pro uvedený pokus? Jakých hodnot mohou nabývat všeobecně? a) 0 (nepravda). Náhodná proměnná nabývá hodnot z množiny {0, 1} v závislosti na tom, zda v náhodném pokusu padly jenom líce. b) 3. Náhodná proměnná nabývá hodnot z množiny {0, 1, 2, 3, 4} v závislosti na počtě padlých líců. V případě booleovských proměnných budeme dále jejich hodnoty značit pro proměnnou A rovněž jako a a ¬a (čili název proměnné začínající malým písmenem) vedle klasického 1 (pravda) a 0 (nepravda). Když máme definovánu náhodnou proměnnou, můžeme začít uvažovat o pravděpodobnostech, s nimiž bude nabývat jednotlivých hodnot. Definice 61: Uvažujme náhodnou proměnnou X nad pravděpodobnostním prostorem (Ω, P). Pravděpodobnost, že proměnná X nabude hodnoty a, ozn. P(X = a), je definována 94 jako P(X = a) = P({ω ∈ Ω | X(ω) = a}), neboli pravděpodobnost množiny elementárních jevů, pro něž nabývá náhodná proměnná hodnoty a. Pokud je v uvažovaném kontextu zápis jednoznačný, P(X = a) můžeme značit zkráceně jako P(a). Rozložení pravděpodobnosti mezi jednotlivými hodnotami náhodné proměnné v souladu s uvedenou definicí definuje funkci, která se nazývá rozdělení pravděpodobností náhodné proměnné. Definice 62: Rozdělení (či distribuce) pravděpodobnosti náhodné proměnné X, značeno P(X), je funkce P(X) : R → [0, 1], která přiřadí každé hodnotě a ∈ R pravděpodobnost, že X nabude hodnoty a podle Definice 61. Rozložení pravděpodobnosti obsahuje pravděpodobnosti všech hodnot náhodné proměnné. Jelikož náhodná proměnná vždy nabývá nějaké hodnoty, pravděpodobnost, že nabude nějaké z hodnot, je 1. Proto platí následující tvrzení. Věta 63: Součet hodnot rozložení pravděpodobnosti náhodné proměnné je roven 1. Příklad. Uvažte booleovskou náhodnou proměnnou Prší ve světě, kde pravděpodobnost toho, že prší, je 0.3. Uveďte, jakým hodnotám se rovnají nasledující výrazy: a) P(¬prší), b) P(Prší). a) Výraz označuje pravděpodobnost toho, že neprší. Jelikož víme, že náhodná proměnná má pouze dvě hodnoty, potom P(¬prší) = 1 − P(prší) = 0.7. b) Výraz označuje distribuci pravděpodobnosti, tedy P(Prší)(x) =    0.3 pro hodnotu prší, neboli x = 1 (pravda), 0.7 pro hodnotu ¬prší, neboli x = 0 (nepravda), 0 jinak, neboli x ̸= 1 ∧ x ̸= 0. Distribuce pravděpodobností náhodných proměnných lze navzájem kombinovat. Vznikne tak složená distribuce pravděpodobností. 95 Definice 64: Složené rozložení pravděpodobnosti náhodných proměnných X1, . . . , Xn určuje pravděpodobnost toho, že náhodné proměnné X1, . . . , Xn nabudou (v tom samém pokusu) hodnot a1, . . . , an. Složené rozložení značíme P(X1 ∧ . . . ∧ Xn) nebo P(X1, . . . , Xn). Pravděpodobnost konkrétního přiřazení hodnot značíme obdobně, P(a1 ∧ . . . ∧ an) nebo P(a1, . . . , an), kde ai je hodnota náhodné proměnné Xi. Příklad. Mějme složenou distribuci booleovských náhodných proměnných Prší a Sněží. a) Kolik pravděpodobnostních hodnot obsahuje jejich složená distribuce? b) Co reprezentuje výraz P(sněží, ¬prší)? a) 4. Jsou to P(sněží, prší), P(¬sněží, prší), P(sněží, ¬prší) a P(¬sněží, ¬prší). b) Výraz reprezentuje pravděpodobnost, že sněží a neprší zároveň. Složené rozložení pravděpodobnosti všech náhodných proměnných v uvažovaném světě obsahuje pravděpodobnosti všech možných přiřazení hodnot proměnným. Zahrnuje tedy všechny situace, které mohou v daném světě nastat (z pohledu hodnot náhodných proměnných), nazývané též atomické události. Pomocí této distribuce pak lze vypočítat libovolnou pravděpodobnost, a to tak, že sečteme pravděpodobnosti všech atomických událostí, které splňují podmínku jevu, jehož pravděpodobnost nás zajímá. Příklad. Uvažte náhodné proměnné Počasí s hodnotami {oblačno, sněží, slunečno} a Úterý s hodnotami {pravda, nepravda}. Pomocí hodnot složeného rozložení pravděpodobnosti vyjádřete P(oblačno ∨ slunečno). P(oblačno ∨ slunečno) = P(úterý ∧ oblačno) + P(¬úterý ∧ oblačno) + P(úterý ∧ slunečno) + P(¬úterý ∧ slunečno). Pravděpodobnost, kterou jsme se zabývali doteď, vyjadřuje pravděpodobnost jevu bez ohledu na další informace, které o světě máme. Při výpočtu podmíněné pravděpodobnosti naopak do výpočtu zapojujeme znalosti o už odehraných událostech. Například ze statistiky známek z minulého roku student ví, že pravděpodobnost hodnocení A na zkoušce je 1/10. Pokud se ovšem učil na zkoušku týden a před zkouškou spal 9 hodin, pak může předpokládat, že pravděpodobnost A je vyšší. Čím více znalostí máme, tím lépe bude hodnota pravděpodobnosti odpovídat realitě. Máme-li dva jevy A a B, podmíněná pravděpodobnost P(A | B), čili A za podmínky B, je pravděpodobnost jevu A, pokud nastal jev B. 96 Definice 65: Uvažme jevy A, B ⊆ Ω, kde P(B) ̸= 0 Podmíněná pravděpodobnost A za předpokladu B je definována vztahem P(A | B) = P(A ∩ B) P(B) . Nemá-li výskyt jevu B vliv na pravděpodobnost jevu A, říkáme, že jevy A a B jsou stochasticky nezávislé. Pro nezávislé jevy platí, že pravděpodobnost toho, že nastanou oba, je násobkem pravděpodobnosti jednotlivých jevů. Definice 66: Dva jevy A, B ⊆ Ω jsou stochasticky nezávislé, pokud P(A ∩ B) = P(A) · P(B). Jsou-li jevy A, B nezávislé, pak platí P(A | B) = P(A), neboli zjištěním, zda jev B nastal, se nedozvíme žádnou další informaci, o pravděpodobnosti jevu A. Z pravidla o podmíněné pravděpodobnosti lze odvodit Bayesovu větu: Věta 67 (jednoduchá Bayesova věta): Uvažme dva náhodné jevy A, B ⊆ Ω, přičemž P(B) ̸= 0. Pak platí P(A | B) = P(B | A) · P(A) P(B) . Bayesovu větu lze dobře aplikovat v případech, kdy uvažujeme o pravděpodobnostech příčiny a následku a známe hodnotu jedné podmíněné pravděpodobnosti. Můžeme tak například vyjádřit pravděpodobnost, že člověk má určitou nemoc, má-li její příznak (přičemž pravděpodobnost příznaku, pokud člověk nemoc má, známe), či pravděpodobnost, že výsledek testu je korektní, vyšel-li pozitivně. Příklad. Víme, že pravděpodobnost slunečného počasí je 0.3 a pravděpodobnost horkého počasí (alespoň 30 ◦ C) je 0.05. Dále víme, že pokud je horko, pravděpodobnost slunečního počasí stoupne na 0.9. a) Jaká je pravděpodobnost, že svítí slunce a je horko? b) Jaká je pravděpodobnost, že svítí slunce a horko není? c) Jaká je pravděpodobnost, že je venku horko, pokud z okna vidíme, že svítí slunce? 97 Pravděpodobnost slunečného počasí budeme značit P(s) = 0.3, pravděpodobnost horkého počasí P(h) = 0.05 a pravděpodobnost slunečného počasí za předpokladu, že je horko, P(s|h) = 0.9. a) Pravděpodobnost, že svítí slunce a je horko můžeme označit jako P(s ∧ h). Tuto pravděpodobnost umíme vypočítat pomocí pravidla o podmíněné pravděpodobnosti, tedy P(s ∧ h) = P(s | h) · P(h) = 0.9 · 0.05 = 0.045. b) Pravděpodobnost, že svítí slunce a horko není, tedy P(s ∧ ¬h), vypočítáme s využitím principu složené distribuce pravděpodobnosti. Víme, že P(s) = P(s ∧ h) + P(s ∧ ¬h), potom P(s ∧ ¬h) = P(s) − P(s ∧ h) = 0.3 − 0.045 = 0.255. c) Pro výpočet pravděpodobnosti horkého počasí za předpokladu, že je slunečno, P(h|s) použijeme Bayesovu větu. Platí P(h|s) = P(s|h)·P(h) P(s) = 0.9·0.05 0.3 = 0.15. Pravděpodobnost, že je horko, pokud svítí slunce, je tedy 0.15. Příklad 9.3.1. Zaveďte náhodnou proměnnou, která reprezentuje následující jevy: a) Prší. b) Venkovní teplota naměřená digitálním teploměrem. c) Počet hodin, které strávil studiem PB016 absolvent předmětu. Příklad 9.3.2. Uvažte následující tabulku složených pravděpodobností náhodné proměnné Počasí s hodnotami {0 (slunečno), 1 (déšť), 2 (sníh)} a booleovských proměnných Zácpy a Zpoždění. zpoždění ¬zpoždění zácpy ¬zácpy zácpy ¬zácpy slunečno 0.15 0.10 0.05 0.30 déšť 0.15 0.05 0.02 0.08 sníh 0.07 0.01 0.01 0.01 Určete hodnoty následujících výrazů. a) P(zácpy) b) P(Zácpy) c) P((zácpy ∨¬zpoždění) ∧ slunečno) d) P(Zácpy | déšť) e) P(sníh | ¬zácpy ∨ zpoždění) Příklad 9.3.3. Uvažte tabulku složeného rozložení pravděpodobnosti z předchozího příkladu. Určete, kolik hodnot z tabulky potřebujeme použít pro výpočet následujících pravděpodob- ností. a) P(déšť ∧ ¬zpoždění ∧ zácpy) b) P(slunečno ∧ zpoždění) 98 c) P(slunečno ∨ zpoždění) d) P(¬sníh) Příklad 9.3.4. Doplňte následující tabulku složených pravděpodobností o hodnoty a a b tak, aby jevy X a Y byly na sobě nezávislé. X Y P(X ∩ Y ) 1 1 3/5 1 0 1/5 0 1 a 0 0 b Příklad 9.3.5. Vyjádřete následující pravděpodobnosti: a) P(a | b) pomocí P(b) a P(¬a ∧ b), b) P(a | b) pomocí P(a ∧ b) a P(¬a ∧ b), c) P(b) pomocí P(a | b) a P(a ∧ b). Příklad 9.3.6. Dokažte, že a) jsou-li dva jevy A, B nezávislé, pak P(A | B) = P(A), b) jsou-li A, B dva jevy a P(B) ̸= 0, platí Bayesův vzorec P(A | B) = P(B | A)P(A) P(B) . Vyjděte z Definice 65 a Definice 66. Příklad 9.3.7. Následující situace modelujte pomocí náhodných proměnných a odpovězte na otázky. a) Mimozemšťané mohou být přátelští, ale nemusí. 75 % jich přátelských je. Přátelští mimozemšťané přistávají na zemi v 90 % případů přes den, nepřátelští výhradně v noci. Pokud mimozemšťan přistane v noci, jaká je pravděpodobnost, že je přátelský? Příklad 9.3.8. Alenka je odbornice na cvrčky. Většinu druhů dokáže určit podle jejich zvuku. Cvrček zpěvavý však dokáže napodobovat zvuky jiných cvrčků, takže je velmi obtížné ho rozeznat. Navíc je velmi vzácný – tvoří pouze 2 % populace cvrčků. Přesto má Alenka výborné statistiky při rozpoznávání tohoto cvrčka, s pravděpodobností 73 % správně určí, zda se jedná o cvrčka zpěvavého, či nikoli. Pokud se nejedná o cvrčka zpěvavého, dokáže ho určit pouze v 87 % případů. a) Jaká je pravděpodobnost, že Alenka pozná cvrčka zpěvavého? b) Pokud slyšíme cvrčka, jaká je pravděpodobnost, že Alenka řekne, že jde o cvrčka zpě- vavého? Příklad 9.3.9. Alenčin kamarád Bořek tvrdí, že jeho statistiky jsou ještě lepší. Zda se jedná o cvrčka zpěvavého, či nikoli, prý urči správně s pravděpodobností 98 %. K tomu si přisadí Cyril s tvrzením, že on má ještě lepší výsledky. Pokud slyší cvrčka zpěvavého, správně ho prý urči s pravděpodobností 100 %. Bořek ani Cyril nejsou experti na cvrčky, ale jejich tvrzení jsou pravdivá. Jak je to možné? 99 9.4 Bayesovské sítě Bayesovská síť je datová struktura používaná k reprezentaci pravděpodobnosti nejistých jevů a závislostí mezi nimi. Skládá se z acyklického orientovaného grafu, v němž uzly představují jednotlivé náhodné proměnné a hrany označují, které jevy jsou na sobě závislé. Pokud hrana vede z A do B, říkáme, že A je rodičem B, což znamená, že náhodná proměnná B je přímo závislá na náhodné proměnné A. Pro každou náhodnou proměnnou jsou uvedeny pravděpodobnosti jejích hodnot, které jsou podmíněny tím, jakých hodnot nabývají nadřazené jevy. Bayesovská síť může vypadat například takto: Oblačno Zima Sněží Přitom pravděpodobnostní rozdělení jednotlivých proměnných jsou uvedena v tabulce (pravděpodobnosti hodnot nepravda nejsou uvedeny, lze je snadno vypočítat): Oblačno: Z P(O) 1 0.6 0 0.5 Zima: P(Z) 0.2 Sněží: O Z P(S) 1 1 0.8 1 0 0.001 0 1 0.01 0 0 0 První řádek tabulky Sněží například určuje pravděpodobnost sněžení za předpokladu, že je zataženo a chladno. Bayesovskou síť tvoříme postupným přidáváním jevů jako uzlů. Do nového uzlu zavádíme hrany ze stávajících uzlů, které přímo ovlivňují jeho pravděpodobnost. Formálně to znamená, že pro uzel Xi hledáme minimální podmnožinu Parents(Xi) z množiny již přidaných uzlů X1, ..., Xi−1 takovou, že P(Xi | Parents(Xi)) = P(Xi | X1, ..., Xi−1). Poté zopakujeme postup přidáním dalšího uzlu. Pořadí přidávání lze zvolit libovolně, ale přidávání příčin před následky obvykle vede ke kompaktnější síti. Příklad. V domě máme nainstalován alarm, který se spustí v případě vloupání, ale také v případě zemětřesení. Požádali jsme sousedy Marii a Honzu, aby nám zavolali, pokud uslyší náš alarm. Uvažujme náhodné proměnné Vloupání, Zemětřesení, Alarm, Honza volá, Marie volá. Vytvořte síť přidáním uzlů v pořadí M, H, A, V, Z. 100 1. Přidáme uzel Marie volá. Jelikož v síti nejsou žádné uzly, uzel Marie volá nemá rodiče. 2. Přidáme uzel Honza volá. Pokud volá Marie, pravděpodobně se spustil alarm, a tudíž i pravděpodobnost, že zavolá Honza se zvyšuje – jev Honza volá je v tomto případě přímo závislý na jevu Marie volá. Vedeme tedy hranu z M do H. 3. Přidáme uzel Alarm. Pravděpodobnost, že zvoní alarm se přímo zvyšuje, pokud volá Marie, a ještě více, volá-li i Honza – z uzlů M a H vedeme hranu do A. 4. Přidáme uzel Vloupání. Pokud víme, zda alarm zvonil, informace o tom, zda volala Marie nebo Honza, nám o pravděpodobnosti vloupání nic nového neřekne (předpokládáme, že sousedé nesledují, zda někdo vloupává, pouze volají, pokud slyší alarm). Uzel vloupání je tedy přímo závislý pouze na alarmu. 5. Přidáme uzel Zemětřesení. Pokud víme, že zvonil alarm, pravděpodobnost zemětřesení se zvyšuje. Na druhou stranu, pokud víme, že došlo k vloupání a byl spuštěn alarm, pravděpodobnost je menší (alarm byl pravděpodobně spuštěn lupičem). Pravděpodobnost zemětřesení je tedy přímo ovlivněna spuštěním alarmu i vloupáním. Marie volá Honza volá Alarm Vloupání Zemětřesení Z uvedeného příkladu je zřejmé, že dané pořadí přidávání uzlů nebylo zvoleno nejvhodněji a v síti vznikly neintuitivní závislosti. Síť však stále správně reprezentuje situaci. Pokud bychom přidávali uzly v pořadí od příčiny k následku, např. V, Z, A, H, M, vznikla by následující síť, která reprezentuje závislosti intuitivněji a je také kompaktnější: Vloupání Zemětřesení Alarm Honza volá Marie volá 101 Bayesovská síť reprezentuje složené rozdělení pravděpodobnosti všech náhodných proměnných, a to často kompaktněji než tabulka složené distribuce. Ze sítě tedy můžeme vyjádřit jakoukoli pravděpodobnost jevu v uvažovaném světě. Příklad 9.4.1. Uvažte situaci popsanou v úvodu s náhodnými proměnnými Vloupání, Zemětřesení, Alarm, Honza volá, Marie volá. Vytvořte síť přidáváním uzlů v pořadí Z, V, A, M, H. Příklad 9.4.2. Uvažte náhodné proměnné Bouřka, Zataženo, Léto, Hrom, Teplo a Blesk. Vytvořte bayesovskou síť, která bude zachytávat závislosti jevů co nejkompaktněji. 102 10 Strojové učení Metody strojového učení nám umožňují konstruovat systémy, které se svou funkcionalitu postupně učí z dat. Tyto systémy využívají získávané znalosti k tomu, aby vylepšovaly svou výkonnost. Jednou ze základních vlastností takových systémů je schopnost generalizovat, tedy schopnost aplikovat naučené znalosti na doposud neviděná data. Algoritmy strojového učení můžeme podle způsobu učení rozdělit do třech hlavních kategorií: • Učení s učitelem, kde známe pro učicí data i očekávané výstupy. • Učení bez učitele, kde se model učí vzory v datech bez dodatečných informací. • Zpětnovazebné učení („reinforcement learning“), kde za provedené akce následuje zpětná vazba v podobě odměny nebo trestu. Pomocí metod strojového učení můžeme řešit spoustu různých úloh. Klasifikace má za cíl přidělit vstupním objektům jednu z konečně mnoha předem určených tříd. Může jít například o rozhodování, zda počasí pro daný den ohodnotit jako slunečno, polojasno, nebo deštivo. Cílem regrese je na základě vstupů modelovat spojitou proměnnou, například odhadnout venkovní teplotu v určitém čase. Shlukování, které je obvykle příkladem učení bez učitele, se snaží vstupní data rozdělit do několika skupin, které shlukují vzájemně podobné příklady. V této sbírce se budeme věnovat pouze učení s učitelem. Zaměříme se hlavně na úlohu klasifikace, setkáme se ale i s regresí. Konkrétních metod nebo algoritmů, které lze zařadit pod strojové učení, existuje opět mnoho. V této kapitole se budeme postupně věnovat dvěma základním typům. V první části to bude jednoduchý (ale velmi používaný) model rozhodovacích stromů. Druhá část se pak bude týkat algoritmů okolo lineárních modelů. Na tyto modely poté navážeme v další kapitole, která představí složitější architektury neuronových sítí. 10.1 Rozhodovací stromy Model rozhodovacího stromu nám poskytuje přirozený pohled na klasifikační úlohy. Větve takového stromu reprezentují sekvence testů na atributy vstupu, pomocí kterých postupně dojdeme k výsledku. Není-li řečeno jinak, budeme pro jednoduchost předpokládat, že atributy vstupních příkladů nabývají diskrétních hodnot. Definice 68: Rozhodovací strom je speciální typ kořenového stromu, který má dva typy uzlů: • vnitřní (rozhodovací) uzly, • listové uzly. Vnitřní uzel stromu odpovídá testu na hodnotu některého atributu vstupu. Hrany vedoucí z uzlu do jeho potomků poté reprezentují možné hodnoty testovaného atributu. Listové uzly specifikují výslednou třídu. 103 Definice 69: Říkáme, že rozhodovací strom je konzistentní s konkrétním datasetem, právě když správně oklasifikuje všechny příklady z datasetu. Ilustrujme si klasifikaci pomocí rozhodovacího stromu na elementárním příkladu. Pro jednoduchost uvažujme případ binární klasifikace, kde jsou listové uzly označeny pouze ANO/NE. Obecně ale samozřejmě rozhodovací stromy takto omezeny nejsou. Příklad. Mějme následující strom reprezentující rozhodovací problém, zda jsou venkovní podmínky vhodné pro hraní tenisu (rozhodujeme se pomocí veličin Vlhkost, Počasí, Větrno). Počasí? Větrno? NEANO ANOVlhkost? ANOANONE déšť anone slunečnozataženo nízkástřednívysoká a) Klasifikujte pomocí daného stromu následující situace (příklady obsahují atributy v pořadí Vlhkost, Počasí, Větrno): 1. [vysoká, slunečno, ne] 2. [střední, déšť, ano] 3. [vysoká, zataženo, ne] b) Upravte strom přidáním jednoho rozhodovacího uzlu tak, aby výstupem pro příklad [vysoká, zataženo, ano] bylo ANO. Ostatní příklady by nový strom měl klasifikovat stejně jako původní. c) Mohli bychom původní strom použít i ke klasifikaci příkladů z datasetu čtveřic s atributy Vlhkost, Počasí, Větrno a Teplota? Vstupy by tedy kromě původních tří atributů obsahovaly ještě dodatečný atribut Teplota. a) 1. ANO – z prvního rozhodovacího uzlu se dostaneme po hraně slunečno rovnou do listového uzlu 2. NE 3. NE b) Například následující strom: 104 Počasí? Větrno? NEANO ANOVlhkost? ANOANOVětrno? ANONE déšť anone slunečnozataženo nízkástřednívysoká anone c) Ano, mohli. Výsledná třída by ale na novém atributu Teplota nikdy nezáležela, jelikož se ve stromě podle tohoto atributu nikde nerozhoduje. Příklad 10.1.1. Mějme dataset D zadaný následující tabulkou (řádky reprezentují jednotlivé příklady, sloupce atributy, závislá proměnná je Tenis). Vlhkost Počasí Větrno Tenis vysoká zataženo ano NE střední slunečno ne ANO nízká slunečno ano ANO střední déšť ne NE a) Vytvořte (ručně) rozhodovací strom, který je konzistentní s tímto datasetem. Snažte se o co nejmenší strom. b) Jak by (konzistentní) strom vypadal, pokud by v D byl navíc ještě příklad [střední, slunečno, ne] s třídou NE? Příklad 10.1.2. Je pravda, že v žádné větvi rozhodovacího stromu nemá cenu testovat stejný atribut vícekrát? Svou odpověď odůvodněte. 10.2 Učení rozhodovacích stromů K vytvoření stromu využíváme (jak je tomu ve strojovém učení obvyklé) množinu trénovacích dat. Trénovací data se v tomto případě skládají z dvojic příkladů a jejich očekávaných tříd. Často lze ovšem vytvořit spoustu různých stromů konzistentních s danými trénovacími daty. Tyto stromy se mohou lišit jak ve své velikosti, tak ve schopnosti generalizace. Cílem obvykle je vytvořit co nejmenší konzistentní strom, který co nejlépe generalizuje na nové příklady. 105 Jelikož je ale problém nalezení nejmenšího konzistentního rozhodovacího stromu NP-úplný, musíme si vystačit s heuristickými postupy. Tyto postupy budují strom od kořene, a v každém uzlu se snaží najít (v nějakém smyslu) co nejlepší rozhodovací atribut. Představíme si postup, který jako metriky k nalezení takového atributu využívá entropii a informační zisk (information gain). Nejdříve si tyto metriky zadefinujme. Entropie je obecně mírou neuspořádanosti, nejistoty, nebo informace. V původním smyslu jde o míru nejistoty náhodné proměnné – my budeme uvažovat jako tuto náhodnou proměnnou třídu. Uvažme pro ilustraci případ binární klasifikace (proměnná třídy má 2 hodnoty). Nechť máme dataset tvořený příklady pouze jedné třídy. Pokud bychom náhodně vytáhli jeden příklad, už dopředu máme jistotu, jaká bude jeho třída. Proto výsledek tohoto pokusu nenese žádnou informační hodnotu a entropie (míra informace) je nulová. Uvažme naopak dataset, jenž je z poloviny tvořen příklady jedné třídy, a z druhé poloviny příklady třídy druhé. V tomto případě nemáme dopředu žádnou jistotu, jakou bude mít náhodně zvolený příklad třídu, a proto je entropie nejvyšší (pro binární klasifikaci rovna 1). Definice 70: Uvažujme množinu příkladů D. Nechť jsou příklady rozděleny do n tříd a Pi je pravděpodobnost, že náhodně vybraný příklad bude mít třídu i. Entropii pro dataset D spočítáme jako E(⟨P1, . . . , Pn⟩) = n i=1 −Pi · log2(Pi) Máme-li třídy pouze 2, vzorec se obvykle zapisuje následovně: E(⟨P1, P2⟩) = −P1 · log2(P1) − (1 − P1) · log2(1 − P1) Entropii můžeme využít k výpočtu informačního zisku, jenž nám dává jakýsi heuristický odhad, jak je který atribut „dobrý“. Informační zisk pro určitý atribut nám intuitivně říká, jak moc se liší „neuspořádanost“ množiny před a po rozdělení podle daného atributu – tedy kolik informace získáme testem na hodnotu onoho atributu. Informační zisk je vyšší, pokud se entropie („neuspořádanost“) rozdělením sníží. Definice 71: Uvažujme množinu příkladů D a atribut A, který může nabývat celkem k hodnot. A tedy rozděluje množinu D na podmnožiny D1, . . . , Dk. Nechť p je celkový počet pozitivních příkladů v D a n počet negativních (uvažujeme binární klasifikaci). Dále nechť pi je počet pozitivních příkladů v Di a ni počet negativních v Di. Informační zisk atributu A spočítáme jako Gain(A) = E(⟨ p p+n , n p+n ⟩) − k i=1 pi+ni p+n · E(⟨ pi pi+ni , ni pi+ni ⟩) Příklad. Mějme dataset daný tabulkou níže (řádky reprezentují jednotlivé příklady, sloupce 106 kromě prvního atributy, závislá proměnná je Tenis). Spočítejte a) entropii celého setu, b) informační zisk pro atribut Počasí. Vlhkost Počasí Větrno Teplota Tenis 1 vysoká zataženo ano nižší NE 2 střední zataženo ne vyšší ANO 3 nízká slunečno ano nižší ANO 4 střední déšť ne nižší NE 5 nízká slunečno ano vyšší ANO 6 vysoká déšť ne vyšší NE 7 střední slunečno ano nižší ANO Zamyslete se, co nám spočítaná entropie říká o datasetu, a zda-li může být atribut Počasí vhodným kandidátem pro rozhodovací uzel. a) E(⟨PANO, PNE⟩) = −4 7 · log2(4 7 ) − (3 7 ) · log2(3 7 ) ≈ 4 7 · 0.807 + (3 7 ) · 1.222 ≈ 0.985 b) Gain(Počasí) ≈ 0.985 − (2 7 · E(⟨1 2 , 1 2 ⟩) + 3 7 · E(⟨3 3 , 0 3 ⟩) + 2 7 · E(⟨0 2 , 2 2 ⟩)) ≈ 0.985 − (2 7 · 1 + 3 7 · 0 + 2 7 · 0) ≈ 0.699 Původní entropie je vysoká, což znamená, že dataset je poměrně vyvážený. Informační zisk atributu Počasí je vysoký, zdá se tedy být vhodným kandidátem. Můžeme si všimnout, že například hodnoty déšť i slunečno již plně určují výsledek. Samotná procedura vytváření stromu probíhá rekurzivně od kořene. V každém uzlu vybereme pomocí informačního zisku rozhodovací atribut. Podle různých hodnot vybraného atributu rozdělíme trénovací množinu a rekurzivně pokračujeme. Uzel automaticky prohlásíme za listový, pokud pro něj uvažovaná množina obsahuje jen příklady jedné třídy (jeho label bude tato třída). Uzel také prohlásíme za listový, pokud jsme v dané větvi již otestovali všechny atributy – jeho třída se zvolí podle převažující třídy mezi příklady (v tomto případě nebude strom kompletně konzistentní). Příklad 10.2.1. Uvažujme opět dataset daný tabulkou z předchozího příkladu. Nalezněte atribut, který by učicí algoritmus zvolil jako rozhodovací atribut pro kořen stromu. Příklad 10.2.2. Nyní konečně aplikujte i zbytek učicího algoritmu a vybudujte pomocí něj kompletní rozhodovací strom. Dataset zůstává stejný jako v předchozích příkladech. První krok jste již spočítali v minulém příkladu. Příklad 10.2.3. Mějme následující množiny hodnot tříd (p/n). Pro každou z nich spočítejte hodnotu entropie. Co jste z těchto výsledků vypozorovali? a) {p, p, p, p} b) {p, p, p, n} 107 c) {p, p, n, n} d) {p, n, n, n} e) {n, n, n, n} Příklad 10.2.4. Uvažujte následující dataset. A B C Třída 0 0 0 T 0 1 0 F 1 0 0 F 1 1 1 T a) Na tento dataset aplikujte učicí algoritmus a vybudujte pomocí něj kompletní rozhodovací strom. Mají-li v některém kroku dva atributy stejný informační zisk, zvolte lexiko- graficky. b) Existuje konzistentní rozhodovací strom s menší hloubkou, než má strom vytvořený pomocí heuristického algoritmu? Pokud ano, vytvořte jej. Pokud ne, odůvodněte proč tomu tak je. Příklad 10.2.5. Nechť k-hodnotový atribut A rozdělí množinu příkladů D na podmnožiny Di, pro které platí, že obsahují pi pozitivních a ni negativních příkladů. Ukažte, že pokud je pro všechna i poměr pi pi+ni stejný, atribut má nulový informační zisk. Příklad 10.2.6. Uveďte, jaké hlavní výhody a nevýhody rozhodovacích stromů znáte. Uvažujte základní trénovací algoritmus. Příklad 10.2.7. Jak už bylo zmíněno v jednom z předchozích příkladů, základní verze učení rozhodovacích stromů je obecně náchylná k tzv. přeučení (overfitting), což může ovlivnit schopnost generalizovat. Jaké vás napadnou způsoby, kterými lze často docílit lepší generalizace? 10.3 Perceptron a lineární klasifikace V této sekci opustíme rozhodovací stromy a představíme si jiný typ algoritmů. Konkrétně se zaměříme na metody založené na lineárních modelech a představíme si nejjednodušší verze (jednovrstvých) neuronových sítí. Takové modely obvykle pracují nad spojitou doménou, a tedy jejich vstupy bývají vektory (reálných) čísel. Předpokládejme proto dále, že pracujeme s objekty, jejichž atributy mají formu reálných čísel. Toho jde obecně docílit vhodným předzpracováním dat. Lineární modely už můžete znát ze statistiky, kde je okolo nich vybudována rozsáhlá teorie. V kontextu tohoto kurzu využijeme myšlenku lineárních modelů k tomu, abychom si pomocí nich zavedli takzvané umělé neurony. Neurony uvnitř fungují jako lineární model, na výslednou lineární transformaci vstupů na závěr ještě aplikují takzvanou aktivační funkci. Tyto umělé neurony pak tvoří základní stavební bloky neuronových sítí. To, jak můžeme neurony propojovat do nejrůznějších architektur a vytvářet složitější sítě, si podrobněji představíme 108 v další kapitole. V této sekci se budeme soustředit na jednoduchý binární klasifikátor, perceptron. Aby model vstupy rozdělil do dvou tříd, používá jako aktivaci prahovou funkci. V n-rozměrném prostoru vstupů perceptron zadává nadrovinu oddělující příklady různých tříd, jak si konkrétněji ukážeme v následující sekci. Definice 72: Uvažujme vstupní vektor ⃗x = ⟨x1, . . . , xn⟩. Pak rozšířený vstupní vektor je ˜x = ⟨1, x1, . . . , xn⟩. Rozšířený vstupní vektor se nám bude hodit pro zkrácený zápis některých výrazů pomocí vektorových operací. Definice 73: Uvažujme příklad ⃗x = ⟨x1, . . . , xn⟩ a vektor vah ⃗w = ⟨w0, w1, . . . , wn⟩. Výstup perceptronové jednotky s váhami ⃗w pro příklad ⃗x je C[⃗w](⃗x) = 1 pokud w0 + n i=1 wi · xi = ⃗w · ˜x ≥ 0, 0 jinak. Funkcionalitu perceptronu si můžeme ilustrovat následujícím diagramem. aktivační funkce w2x2 ... ... wnxn w1x1 w01 vstupy váhy Příklad. Mějme perceptron s váhovým vektorem ⃗w = ⟨1, 1, 2.5, 0, −1⟩. a) Určete, jak tento model oklasifikuje následující příklady. 1) ⃗x1 = ⟨0, 1, 1, 2⟩ 2) ⃗x2 = ⟨−1, 1.5, 3, 4⟩ 109 3) ⃗x3 = ⟨−3, 1, 3, 0.5⟩ b) Jak bychom museli co nejméně změnit některou váhu tak, aby byl výstup pro příklad ⃗x4 = ⟨−2, 1, 2.5, 3⟩ roven 1? a) 1) 1, protože 1 + 1 · 0 + 2.5 · 1 + 0 · 1 + (−1) · 2 = 1.5 > 0 2) 0, protože 1 + (−1) + 3.75 + 0 + (−4) = −0.25 < 0 3) 1, protože 1 + (−3) + 2.5 + 0 + (−0.5) = 0. Tento bod je zajímavý tím, že leží přímo na „dělící hranici“ perceptronu. To má pěkný geometrický význam, který si stručně představíme v další sekci. b) Pro původní váhy máme 1 + (−2) + 2.5 + 0 + (−3) = −1.5. Potřebujeme aby byla vážená suma rovna (alespoň) 0. Nejmenší změna, kterou toho lze docílit, je změna w4 z hodnoty −1 na −0.5. Zamyslete se, proč volíme právě w4. Příklad 10.3.1. Pro každou z následujících logických operací definujte perceptron, který ji implementuje. Jako množinu vstupů uvažujte pouze vektory nad {0, 1}. a) binární NAND b) binární implikace c) n-ární disjunkce Příklad 10.3.2. Kolik Booleovských funkcí pro dva vstupy jde reprezentovat percep- tronem? 10.4 Geometrický význam a perceptronový algoritmus Perceptron má i svůj geometrický význam, je to takzvaný lineární separátor. Váhy perceptronu zadávají v prostoru nadrovinu (v dvourozměrném prostoru je to přímka), která rozděluje daný prostor vstupů na dvě části. Body z jedné části model klasifikuje jako 1, z druhé jako 0. Definice 74: Dělící nadrovina daná perceptronem s váhami ⃗w = ⟨w0, w1, . . . , wn⟩ je právě množina bodů {⃗x = ⟨x1, . . . , xn⟩ | w0 + n i=1 wi · xi = ⃗w · ˜x = 0}. Pro ilustraci uvažujme případ dvourozměrného prostoru, kde perceptron zadává oddělující přímku. Příklad grafické reprezentace takového klasifikátoru můžete vidět na následujícím obrázku (body jsou obarveny podle výsledku klasifikace). 110 0 1 2 3 4 5 6 0 1 2 3 4 5 6 x1 x2 Příklad. Uvažte model a data reprezentované předchozí ilustrací. a) Kterou barvou jsou v obrázku vykresleny body oklasifikované jako 1? b) Zamyslete se, kolik daný model potřebuje vah, a jaký je jejich geometrický význam. c) Určete z obrázku hodnoty vah pro daný model, víme-li, že w0 = −3. a) Červeně. Z definice víme, že body na dělící přímce jsou oklasifikovány jako 1. b) Celkem máme tři váhy ⃗w = ⟨w0, w1, w2⟩. Váhy w1, w2 nám zadávají sklon přímky, zatímco w0 ovlivňuje posun od počátku. Váze w0 se proto také někdy říká bias. c) Rovnice přímky je w0 + w1 · x1 + w2 · x2 = 0. Víme-li, že w0 = −3, pak (pomocí bodů, kterými prochází) dostaneme w1 = −2 a w2 = 3. Základní idea učení perceptronu je snaha manipulovat s dělící nadrovinou („otáčet ji“, resp. „posunovat“) tak, aby nakonec správně oddělovala trénovací příklady patřící do různých tříd. Definice 75: Uvažujme tréninkový set D = {(⃗x1, c1), . . . , (⃗xp, cp))}, kde ci je opravdová třída příkladu ⃗xi. Perceptron C s váhami ⃗w je konzistentní s D pokud pro všechna k z 1, . . . , p platí C[⃗w](⃗xk) = ck. 111 Definice 76: Online perceptronový algoritmus je procedura, která iterativně upravuje váhy perceptronu. Postupně prochází přes jednotlivé trénovací příklady, a kdykoliv je příklad špatně oklasifikován, pootočí nadrovinou tak, aby byl příklad blíže správnému poloprostoru. Uvažujme tréninkový set D = {(⃗x1, c1), . . . , (⃗xp, cp))}, kde ci je opravdová třída příkladu ⃗xi. Sekvence vektorů vah ⃗w(0) , ⃗w(1) , ⃗w(2) , . . . je počítána následovně: • ⃗w(0) je inicializován náhodně hodnotami okolo 0, • ⃗w(t+1) = ⃗w(t) − α · (C[⃗w(t) ](⃗xk) − ck) · ˜xk, kde k = (t mod p) + 1, což vyjadřuje jen to, že příklady jsou uvažovány postupně cyklicky. Konstanta 0 < α ≤ 1 je tzv. učicí konstanta (learning rate). Pokud se nad algoritmem zamyslíte, pokaždé když narazí na špatně klasifikovaný vektor, tak jej přičte k aktuálnímu vektoru vah nebo ho od něj odečte (po pronásobení ϵ). Příklad. Mějme trénovací množinu D = {(⟨−1, 0⟩, 1), (⟨0, 1⟩, 1), (⟨3, 0⟩, 0)}. Proveďte 3 kroky perceptronového algoritmu, jestliže ⃗w(0) = ⟨0, 1, −1⟩ a α = 1. • ⃗w(0) = ⟨0, 1, −1⟩ • ⃗w(0) · ˜x1 = −1 C[⃗w(0) ](⃗x1) = 0 ⃗w(1) = ⃗w(0) − (0 − 1) · ˜x1 = ⟨1, 0, −1⟩ • ⃗w(1) · ˜x2 = 0 C[⃗w(1) ](⃗x2) = 1 ⃗w(2) = ⃗w(1) = ⟨1, 0, −1⟩ • ⃗w(2) · ˜x3 = 1 C[⃗w(2) ](⃗x3) = 1 ⃗w(3) = ⃗w(2) − (1 − 0) · ˜x3 = ⟨0, −3, −1⟩ Příklad 10.4.1. Platí, že perceptronový algoritmus vždy zkonverguje a nalezne perceptron, který správně klasifikuje všechny příklady z datasetu? Odůvodněte svou odpověď. Příklad 10.4.2. Mějme trénovací sadu D = {(⟨3, −1⟩, 1), (⟨2, 1⟩, 1), (⟨0, 3⟩, 0)}. Aplikujte perceptronový algoritmus, dokud nenalezne separující nadrovinu. Uvažujte ⃗w(0) = ⟨0, −2, 1⟩ a α = 1. Na závěr načrtněte dělící přímku. Příklad 10.4.3. Mějme trénovací sadu D = {(⟨1, 1⟩, 1), (⟨0, 1⟩, 0), (⟨0, 0⟩, 1), (⟨1, 0⟩, 0)}. Uvažujte ⃗w(0) = ⟨0, 0, 0⟩ a α = 1. Kolik iterací perceptronového algoritmu je třeba, aby nalezl separující nadrovinu? 10.5 Základy lineární regrese Myšlenku lineárních modelů můžeme samozřejmě využít i k řešení jiných úloh, než jen ke klasifikaci. Asi nejznámější úlohou je regrese, v níž se snažíme hledat funkční závislosti mezi numerickými vlastnostmi. V našem případě budeme uvažovat lineární regresi – cílem tedy bude lineárně aproximovat neznámou funkci. Jedná se v podstatě o prokládání trénovacích 112 dat „co nejlepším“ lineárním modelem. Díky tomu poté můžeme predikovat funkční hodnoty i pro dosud neviděné vstupy. Definice 77: Uvažujme n-rozměrné příklady tvaru ⃗x = ⟨x1, . . . , xn⟩ a vektor vah ⃗w = ⟨w0, w1, . . . , wn⟩. Regresní model R s váhami ⃗w je dán jako R[⃗w](⃗x) = w0 + n i=1 wi · xi = ⃗w · ˜x To, jak je konkrétní model dobrý (resp. „špatný“), definujeme pomocí chybové funkce (error function). Obvykle chybová funkce nějakým způsobem vyjadřuje, jak daleko jsou původní funkční hodnoty příkladů od těch aproximovaných modelem. Idea je taková, že lepší model by měl mít menší chybu. Mezi nejznámější typy chyb patří například kvadratická chyba (squared error) nebo absolutní chyba (absolute error), a jejich varianty. V této sekci budeme nejčastěji pracovat s kvadratickou chybou. Definice 78: Uvažujme dataset D = {(⃗x1, f1), . . . , (⃗xp, fp))}, kde fi je opravdová funkční hodnota příkladu ⃗xi. Kvadratická chyba pro model s váhami ⃗w = ⟨w0, w1, . . . , wn⟩ je E(⃗w) = 1 2 · p k=1(R[⃗w](⃗xk) − fk)2 = 1 2 · p k=1(⃗w · ˜xk − fk)2 Příklad. Mějme dataset jednorozměrných příkladů a jejich očekávaných funčních hodnot D = {(43, 41), (44, 45), (45, 49), (46, 47), (47, 44)} a lineární model R s váhami ⃗w = ⟨9.2, 0.8⟩. a) Spočítejte pro R kvadratickou chybu na množině D. b) Určete pomocí modelu R aproximaci funkční hodnoty pro x = 40. a) Spočítejme si nejdříve kvadratickou chybu pro jednotlivé trénovací příklady. (9.2 + 0.8 · 43 − 41)2 = 6.76 (9.2 + 0.8 · 44 − 45)2 = 0.36 (9.2 + 0.8 · 45 − 49)2 = 14.44 (9.2 + 0.8 · 46 − 47)2 = 1 (9.2 + 0.8 · 47 − 44)2 = 7.84 E(⃗w) = 1 2 · (6.76 + 0.36 + 14.44 + 1 + 7.84) = 15.2 b) R[⃗w](40) = 9.2 + 0.8 · 40 = 41.2 113 Učení regresního modelu je založeno na trochu jiném principu než u perceptronu. Jelikož máme chybovou funkci, můžeme hledat takové váhy, které minimalizují její hodnotu. Řešíme tedy jednoduchý optimalizační problém. Algoritmus, který se k tomu obvykle používá již nejspíše znáte – jedná se o gradientní sestup (gradient descent). Tato metoda pomocí odečítání gradientu chybové funkce postupně upravuje váhy tak, aby docílila minimální chyby. Podrobněji se s ní seznámíte buď v následující kapitole, nebo v předmětu IB031. Příklad 10.5.1. Mějme množinu jednorozměrných příkladů a jejich očekávaných funčních hodnot D = {(1, 0), (4, 2), (5, 3), (6, 3)} a lineární model R s váhami ⃗w = ⟨2 3 , 1 3 ⟩. a) Spočítejte pro R kvadratickou chybu na množině D. b) Nalezněte nějaký model, který bude mít pro množinu D menší kvadratickou chybu než R. Příklad 10.5.2. Mějme množinu se dvěma příklady D = {(⟨3, 5⟩, 13), (⟨6, 8⟩, 22)} a lineární model R s váhami ⃗w = ⟨3, 1, 2⟩. a) Spočítejte pro R kvadratickou chybu na množině D. b) Aproximujte (predikujte) pomocí modelu R funkční hodnotu pro ⃗x = ⟨4, 7⟩. c) Dokážete najít nějaký model minimalizují na D kvadratickou chybu? 114 11 Neuronové sítě a hluboké učení V předchozí kapitole byla poprvé představena jednoduchá jednotka umožňující lineární klasifikaci – perceptron. Sdružením více takových jednotek do vrstev a jejich následným propojením pomocí vazeb vznikají neuronové sítě, hlavní předmět této kapitoly. 11.1 Struktura a výpočet neuronové sítě Základní strukturu dopředné neuronové sítě ilustruje následující obrázek. y2 y1 ... ym ... ... x2 x1 ... xn skryté vrstvyvstupní vrstva výstupní vrstva Na obrázku je znázorněna neuronová síť s n vstupy, 2 skrytými vrstvami a m výstupy. Jednotlivé vrstvy jsou úplně propojené. Výpočet dopředné neuronové sítě na zadaném vstupu probíhá po vrstvách od vstupní vrstvy k výstupní. Nejprve se jednotky vstupní vrstvy inicializují hodnotami vstupu ⃗x. Na základě hodnot vah mezi vstupní vrstvou a první skrytou vrstvou se spočítají výstupy jednotlivých jednotek skryté vrstvy. Tento proces se postupně aplikuje na všechny vrstvy, dokud nedojde k dosažení vrstvy výstupní. Výstupy jednotek výstupní vrstvy se pak berou jako výstup neuronové sítě ⃗y na vstupu ⃗x. Definice 79: Vážený součet vstupů jednotky i (též vnitřní potenciál jednotky i) je dán jako ξi = −w0,i + j wj,i · aj, přičemž j iteruje přes všechny jednotky předcházející vrstvy, w0,i je prahová váha jednotky i, wj,i je váha vazby z jednotky j do jednotky i a aj je výstup jednotky j. 115 Definice 80: Výstup jednotky i je definován vztahem ai = gi(ξi), kde gi je aktivační funkce jednotky i. Příklad. Spočítejte výstup jednotky 4 v druhé skryté vrstvě dopředné neuronové sítě, obsahuje-li první skrytá vrstva jednotky 1, 2, jejichž výstupy jsou a1 = 0, 84, a2 = 0, 02. Váhy hran v síti jsou w1,4 = −0, 15, w2,4 = 12, 4, prahová váha jednotky 4 je w0,4 = 3, 8. Jednotka 4 používá aktivační funkci sigmoida g4(x) = 1 1+e−x . Vážená váha vstupů po odečtení prahové váhy je −w0,4 + w1,4 · a1 + w2,4 · a2 = −3, 68, a výstup jednotky je a4 = g4(−3, 68) = 0, 025. Lze tedy konstatovat, že její reakce na zadané vstupy je poněkud vlažná. Pro jaké výstupy jednotek 1, 2 dochází k aktivaci jednotky 4? V rámci neuronových sítí se používají různé aktivační funkce. Jak uvidíme dále, důležitým požadavkem na aktivační funkci je, aby nebyla lineární; pokud navíc chceme neuronovou síť učit, je vhodné, aby bylo možné aktivační funkci derivovat. Některé z používaných aktivačních funkcí uvádí následující definice. Definice 81: Aktivační funkce. • Prahová funkce f(x) = 1 x ≥ 0, 0 jinak. • ReLU f(x) = x x ≥ 0, 0 jinak. • Sigmoida σ(x) = 1 1 + e−x . Grafy aktivačních funkcí jsou znázorněny na následujících obrázcích. 116 −1 0 1 0 0.5 1 Prahová funkce −1 0 1 0 0.5 1 ReLU −2 0 2 0 0.5 1 Sigmoida Příklad 11.1.1. Uvažte následující funkce f, g a h. −0.5 0 0.5 1 1.5 0 0.5 1 Funkce f −1 0 1 0 0.5 1 Funkce g −1 0 1 0 0.5 1 Funkce h Aplikací operací skládání funkcí, násobení konstantou, přičítání konstanty a sčítání a) a pomocí prahové funkce vyjádřete funkci f, b) a pomocí ReLU vyjádřete funkci g, c) a pomocí ReLU vyjádřete funkci h. Příklad 11.1.2. Uvažte funkci F : [0, 10] → R. Navrhněte způsob, jak lze pomocí prahové funkce a s využitím operací skládání funkcí, násobení konstantou, přičítání konstanty a sčítání aproximovat funkci F. Požadavek na aproximaci je, aby pro aproximující funkci A platilo, že A(x) = F(˜x) pro nějaké ˜x takové, že |˜x − x| ≤ 1, tedy hodnota aproximace se rovná funkční hodnotě v nějakém bodě, který se liší od x maximálně o 1. Příklad 11.1.3. Uvažujte následující neuronovou síť se vstupy x1, x2, x3, skrytou vrstvou s jednotkami n1, n2, n3 a výstupní vrstvou s jednotkou y1. 117 y1n2 10 n1 10 n3 10 x2 10 0 -10 x1 0 -10 10 x3 -10 10 0 Čísla na obrázku znázorňují hodnoty vah jednotlivých vazeb. Aktivační funkce všech jednotek je sigmoida σ a prahová váha je 5. a) Jaké budou výstupy sítě pro vstupy (0, 0, 0), (1, 0, 1), (1, 1, 1), (−1, 0, 1), (0.5, 0.4, 0.6)? b) Napište jednoduchý program, který pro zadaný vstup spočítá výstup sítě. c) Co síť počítá? Nalezněte co nejstručnější slovní charakteristiku. d) Stačila by pro takový výpočet neuronová síť bez skrytých vrstev? Příklad 11.1.4. Dokažte, že každou booleovskou funkci F, tj. funkci tvaru F : {0, 1}n → {0, 1}, lze vyjádřit pomocí neuronové sítě s jednou skrytou vrstvou, kde každý neuron má prahovou funkci jako aktivační funkci. Příklad 11.1.5. Uvažujte vícevrstvou neuronovou síť s jedním výstupem, kde každá vnitřní jednotka i má aktivační funkci fi(x) = Aix+Bi (kde Ai, Bi jsou reálné konstanty) a výstupní jednotka je aktivována prahovou funkcí. a) Má neuronová síť stejnou vyjadřovací sílu jako neuronová síť, která pro vnitřní jednotky používá aktivační funkci σ (sigmoidu)? Vyjadřovací silou rozumíme, jaké různé funkce lze neuronovou sítí reprezentovat. Zdůvodněte. b) Má neuronová síť větší vyjadřovací sílu než perceptron? Pokud ano, nalezněte příklad funkce, kterou lze sítí vyjádřit, ale perceptronem ne. Pokud ne, ukažte, jak takovou síť převést na perceptron počítající stejnou funkci. 11.2 Učení neuronové sítě V této sekci pronikneme hlouběji do samotné podstaty vícevrstvých neuronových sítí. Konkrétně se zaměříme na algoritmus zpětného šíření chyby, který umožňuje trénování neuronových sítí na konkrétní sadě dat. Učicí sada obsahuje dvojice tvaru (⃗x, ⃗yexp), 118 kde ⃗x je vstup neuronové sítě a ⃗yexp je očekávaný výstup. Učení probíhá na principu úpravy hodnot vah v síti, aby došlo k minimalizaci chybové funkce E = E(⃗y, ⃗yexp), kde ⃗y je skutečný výstup sítě při vstupu ⃗x. Chybová funkce musí být navržena tak, aby její minima odpovídala minimálnímu rozdílu mezi skutečným a očekávaným výstupem. Příkladem chybové funkce je kvadratická chyba, kterou jsme představili v předchozí kapitole. Pro použití v neuronových sítích je třeba definici mírně upravit, aby zvládla pojmout vícerozměrný výstup. Příklad. Uvažujte následující jednoduchou neuronovou síť s jednou skrytou vrstvou. n2n1 w2x1 w1 Symboly ξ1, ξ2 označují vážené součty vstupů jednotky 1, resp. 2; symboly a1, a2 pak jejich výstupy a g1, g2 jejich aktivační funkce. Chybová funkce je E = E(y, yexp) = E(a2, yexp). a) Spočítejte parciální derivace ∂E/∂w2 a ∂E/∂w1. b) Jaký je význam spočítaných parciálních derivací při učení neuronové sítě? a) Při výpočtu využijeme toho, že platí a2 = g2(ξ2) a ξ2 = a1 · w2, což plyne z definice výstupu jednotky, resp. definice váženého součtu vstupů jednotky. Jelikož E je funkcí a2 a a2 je funkcí ξ2, lze s využitím řetězového pravidla rozepsat ∂E ∂w2 = ∂E ∂a2 ∂a2 ∂w2 = ∂E ∂a2 ∂a2 ∂ξ2 ∂ξ2 ∂w2 . S využitím vztahů výše můžeme rozepsat poslední dva součinitele jako ∂a2 ∂ξ2 = g′ 2 a ∂ξ2 ∂w2 = a1 a celkově získáme ∂E ∂w2 = ∂E ∂a2 · g′ 2 · a1 = ∂E ∂y · g′ 2 · a1. Jedlotlivé členy lze v konkrétním případě již získat snadno: parciální derivaci chybové funkce podle skutečného výstupu sítě lze spočítat z konkrétní podoby chybové 119 funkce, derivaci aktivační funkce spočítáme opět z jejího tvaru (proto je dobré, aby měla derivaci, jak bylo uvedeno dříve při zavádění pojmu aktivační funkce) a hodnotu a1 získáme prostým provedením výpočtu sítě nad daným vstupem. Obdobným způsobem spočítáme ∂E ∂w1 = ∂E ∂a2 ∂a2 ∂w1 = ∂E ∂a2 ∂a2 ∂ξ2 ∂ξ2 ∂w1 . Jelikož ξ2 = a1 · w2 a a1 dále závisí na w1, pokračujeme ve výpočtu: ∂E ∂w1 = ∂E ∂a2 ∂a2 ∂ξ2 ∂ξ2 ∂a1 ∂a1 ∂w1 = ∂E ∂a2 ∂a2 ∂ξ2 ∂ξ2 ∂a1 ∂a1 ∂ξ1 ∂ξ1 ∂w1 = ∂E ∂a2 · g′ 2 · w2 · g′ 1 · x1. b) Cílem učicího algoritmu je pomocí úprav vah vazeb v síti minimalizovat chybu, tj. rozdíl mezi výstupy, které neuronová síť dává, a očekávanými výstupy. Parciální derivace chybové funkce podle váhy vazby vyjadřuje míru, s jakou se mění velikost chyby při změně váhy. Je-li například ∂E/∂w1 = 2, znamená to, že při zvýšení váhy w1 o 1 se chyba E zvýší přibližně o 2. V takovém případě tedy chceme váhu snížit, což povede ke snížení chyby. Učicí algoritmus tedy v každé iteraci upraví váhy podle předpisu (w1, w2) ← (w1, w2) − α · ∂E ∂w1 , ∂E ∂w2 , kde α > 0 je tzv. učicí konstanta (learning rate), která reguluje rychlost učení a s níž jsme se setkali již v předchozí kapitole. Vektor ∇E = ∂E ∂w1 , . . . , ∂E ∂wn se nazývá gradient chyby a vyjadřuje, kterým směrem chyba nejrychleji roste. Při postupu opačným směrem, tedy odečtením násobku gradientu od vah sítě, dosahuje síť snížení chyby. Definice 82: Online algoritmus pro učení neuronové sítě je procedura, která iterativně upravuje váhy v neuronové síti. Postupně prochází přes jednotlivé trénovací příklady a odečte od hodnot vah o gradient chyby pronásobený učicí konstantou. Uvažujme tréninkový set D = {(⃗x1, ⃗y1), . . . , (⃗xp, ⃗yp))}, kde ⃗yi je očekávaný výstup při vstupu ⃗xi. Sekvence vektorů vah ⃗w(0) , ⃗w(1) , ⃗w(2) , . . . je počítána následovně: • ⃗w(0) je inicializován náhodně hodnotami okolo 0, • ⃗w(t+1) = ⃗w(t) − α · ∇E(⃗y(t) , ⃗yk), 120 kde k = (t mod p) + 1 a ⃗y(t) je výsledek vrácený sítí v iteraci t na vstupu ⃗yk. Příklad 11.2.1. Uvažujte následující neuronovou síť s jednou skrytou vrstvou. n3 n1 w5 n2 w6 x1 w1 w3 x2 w2 w4 Symboly ξ1, ξ2, ξ3 označují vážené součty vstupů jednotky 1, 2, resp. 3; symboly a1, a2, a3 pak jejich výstupy a g1, g2, g3 jejich aktivační funkce. Prahové váhy neuvažujeme. Chybová funkce je E = E(y, yexp) = E(a3, yexp). a) Spočítejte ∂E/∂w5. b) Spočítejte ∂E/∂w1. c) Jaký je obecný předpis pro ∂E/∂wi v obecné dopředné neuronové síti? Příklad 11.2.2. Nalezněte derivace následujících aktivačních funkcí: a) prahová funkce, b) ReLU, c) sigmoida. Příklad 11.2.3. Diskutujte význam učicí konstanty α při učení neuronové sítě. Jaký má vliv na průběh učení (pozitivní i negativní), je-li hodnota konstanty velmi velká, resp. velmi malá? 11.3 Zpracování obrazu a klasifikace Při klasifikaci do n kategorií je vhodné získat výstup ve formě n-tice pravděpodobností. K tomu slouží funkce softmax, která zvýrazní rozdíly mezi jednotlivými výstupy pomocí exponenciální funkce a zároveň provede normalizaci, aby součet členů n-tice byl roven jedné. Definice 83: Funkce softmax transformuje n-tici reálných čísel na n-tici pravděpodobností následujícím způsobem softmax(x1, . . . , xn) = ex1 n i=1 exi , ex2 n i=1 exi , . . . , exn n i=1 exi . 121 Zamyslete se, zda může po aplikaci funkce softmax vyjít u nějaké kategorie nulová pravděpodob- nost. Příklad 11.3.1. a) Bez použití kalkulačky odhaděte výsledek aplikace funkce softmax na následující vstupy: (1, 3, 2), (1, 1, 1), (2, 0, 1), (−5, 0, 0). b) Odhad z předchozí části ověřte výpočtem. 122 12 Zpracování přirozeného jazyka Na jazyky formální i přirozené nahlížíme jako na množiny platných vět. Na rozdíl od formálních jazyků (připomeňme třeba jazyk formulí výrokové logiky) s sebou však jazyky přirozené přinášejí řadu komplikací. Je například poměrně jednoduché určit, že p ∨ ∨∨ není platnou formulí výrokové logiky, protože nevyhovuje definici. Je ovšem věta „To byl teda krutopřísnej vejlet.“ platnou větou češtiny? Odpověď není zcela jednoznačná a s ohledem na časový vývoj jazyka a nářeční nebo stylistickou rozmanitost přirozeného jazyka nelze ani přesně definovat, co vše do jazyka ještě patří a co už ne. Slova přirozeného jazyka mohou být víceznačná – např. slovo list může znamenat kus papíru či část rostliny. Přirozený jazyk je navíc nejasný – kdo je činitelem ve větě „Přišel.“? Existuje navíc mnoho dalších komplikací (viz přednášku), které ze zpracování přirozeného jazyka činí nelehkou úlohu. V této kapitole jsou představeny některé z metod, které se při zpracování přirozeného jazyka používají. 12.1 Předzpracování dat Textová data, se kterými potřebujeme pracovat, jsou mnohdy dostupná pouze ve velmi neotesané podobě, např. ve formě webových stránek či hrubého textu s nadbytečnými údaji. Cílem předzpracování může být očištění dat od nadbytečných informací (např. různých anotací), jejich segmentace či normalizace, tedy celkově převedení dat do formy, na niž lze již aplikovat samotné metody zpracování přirozeného jazyka. Příklad 12.1.1. Na adrese https://web2.mlp.cz/koweb/00/04/34/55/03/bila_nemoc. html si stáhněte text knihy Karla Čapka Bílá nemoc ve formátu HTML. Formát HTML je textový formát, který obsahuje značky pro internetový prohlížeč, které umožňují dokument zobrazit ve formě webové stránky. a) Napište skript, který z dokumentu extrahuje pouze text díla, konkrétně ve formě seznamu jednotlivých replik jako řetězců. Výstup tedy bude začínat následujícím způ- sobem. ["Mor je to, mor. V naší ulici už je v každém domě ...", "Žádný mor, malomocenství. Bílá nemoc tomu říkají,...", "Kriste panebože – Kriste panebože – Kriste panebože –", ... ] Ve výsledných řetězcích je vypuštěna informace o konkrétní postavě, která danou repliku říká, neboť se jedná o značně repetitivní informaci. 123 b) Přidejte do skriptu funkce, které provádějí segmentaci textu na věty, resp. tokenizaci na jednotlivá slova. Slova získávejte očištěná od interpunkčních znamének. c) Vytvořte slovník s frekvencemi jednotlivých slov v díle. Je vhodné mít metodu, která pro každé slovo vrátí jeho základní tvar. Např. slovo „ale“ se v textu může vyskytovat i ve formách „Ale“ nebo „ALE“, ale všechny tyto tvary by se ve slovníku měly započítat pod položku „ale“. d) Napište funkci, která vypíše seznam n nejčastějších slov, která se v díle (nebo jiném zadaném textu) vyskytují. 12.2 Gramatiky Gramatiky představují jeden ze způsobů, kterým lze popsat jazyk. Gramatika udává předpis, jakým lze z počátečního symbolu, tzv. kořene gramatiky, postupnou aplikací pravidel gramatiky odvodit platné věty jazyka gramatiky. Speciálním typem gramatik jsou gramatiky bezkontextové, kterým budeme v této sekci věnovat speciální pozornost. Definice 84: Bezkontextová gramatika sestává z • množiny terminálních symbolů (slov jazyka), • množiny neterminálních symbolů (syntaktických kategorií), • speciálního neterminálního symbolu S reprezentujícího celou větu jazyka (též nazýván kořen gramatiky), • souboru přepisovacích pravidel tvaru neterminál → libovolný řetězec. Běžná konvence je psát neterminály s prvním písmenem velkým a veškerá pravidla, která vycházejí ze stejného neterminálu sdružit pomocí symbolu svislítka, tj. např. S → abbb, S → cac píšeme S → abbb | cac. Gramatika definuje jazyk jako množinu vět sestávajících pouze ze slov jazyka, které lze vygenerovat z kořene gramatiky S postupnou aplikací pravidel gramatiky. Odvození věty v gramatice navíc definuje tzv. syntaktický strom. Samotná pravidla gramatiky se často rozdělují na pravidla (pouze mezi syntaktickými kategoriemi) a lexikon (seznamy slov příslušících jednotlivým kategoriím). 124 Příklad. Uvažte gramatiku s následujícími pravidly: S → NP VP, NP → Noun | Adj NP, VP → Verb a následujícím lexikonem: Noun → dítě | člověk | kapsa, Adj → starý | cestující | nové, Verb → píše | sedí | mluví. a) Rozhodněte, které z následujících vět lze v gramatice vygenerovat. 1. „cestující sedí“ 2. „nové nové kapsa píše“ 3. „starý člověk mluví“ b) Nalezněte odvození vět v gramatice. c) Nalezněte ke každému odvození odpovídající syntaktický strom. a) Gramatika generuje věty, které začínají jmennou frází (NP, neboli noun phrase), po níž bezprostředně následuje slovesná fráze (VP, neboli verb phrase). Jmenná fráze sestává z podstatného jména (Noun), jemuž předchází libovolný počet přídavných jmen (Adj). Slovesná fráze sestává z jediného slovesa. Větu 1 nelze v gramatice vygenerovat, jelikož neobsahuje podstatné jméno. Věty 2 i 3 splňují popis výše a v gramatice je vygenerovat lze. b) S ⇒ NP VP ⇒ Adj NP VP ⇒ nové NP VP ⇒ nové Adj NP VP ⇒ nové nové NP VP ⇒ nové nové Noun VP ⇒ nové nové kapsa VP ⇒ nové nové kapsa Verb ⇒ nové nové kapsa píše S ⇒ NP VP ⇒ Adj NP VP ⇒ starý NP VP ⇒ starý Noun VP ⇒ starý člověk VP ⇒ starý člověk Verb ⇒ starý člověk mluví c) Syntaktické stromy uvedených vět vypadají následovně. 125 S VP Verb píše NP NP NP Noun kapsa Adj nové Adj nové S VP Verb mluví NP NP Noun člověk Adj starý Z příkladu lze vypozorovat několik skutečností. Zaprvé, mohou existovat věty přirozeného jazyka, které nejsou gramatikou popsány – viz věta 1. Zadruhé, gramatika může generovat věty, které do popisovaného přirozeného jazyka nepatří – viz věta 2, kde je porušena shoda v rodě mezi podstatným jménem kapsa (ženský rod) a přídavným jménem nové (střední rod). Cílem návrhu gramatik je minimalizovat počet vět, které gramatika generuje a nepatří do jazyka, a zároveň maximalizovat počet vět, které gramatika generuje a do jazyka patří. Kvalitu gramatiky kvantitativně popisují pojmy pokrytí a přesnost. Definice 85: Uvažujme zamýšlený jazyk L a gramatiku G generující jazyk L(G). • Pokrytí gramatiky G je |L∩L(G)| |L| , tedy podíl vět jazyka L, které lze v gramatice vygen- erovat. • Přesnost gramatiky G je |L∩L(G)| |L(G)| , tedy podíl vět generovaných gramatikou, které patří do zamýšleného jazyka. Příklad 12.2.1. Uvažte gramatiku s následujícími pravidly: S → NP VP | VP, NP → Noun | NP Conj NP, VP → NP Esse a následujícím lexikonem: Noun → Romulus | Remus | Danubius | fratellus | fratelli | fluvius, Esse → sum | est | sunt | eram | erat | erant, Conj → et. 126 a) Rozhodněte, které z následujících vět lze v gramatice vygenerovat. 1. „Romulus et Remus fratelli erant“ 2. „Remus et Danubius et Romulus sum“ 3. „Danubius est fluvius“ b) Nalezněte ke každé větě její syntaktický strom, pokud existuje. Příklad 12.2.2. Navrhněte gramatiku pro jednoduché české (resp. slovenské) věty v minulém čase, které dodržují následující schéma: [určení času / podmět], přísudek v minulém čase, [předmět], tedy například „včera jsme koupili maso“, „já jsem běžel“, „hráli jste hru“. Nezapomeňte, že pořadí pomocného slovesa být a významového slovesa závisí na přítomnosti jiného slova na začátku věty (věta nikdy nezačíná pomocným slovesem). Ošetřete shodu podmětu s přísudkem a) přímo návrhem gramatiky, b) přídáním (jednoduše implementovatelných) testů na shodu. Příklad 12.2.3. Uvažme gramatiku G s následujícími pravidly S → AAA | BA | AB | C, A → a, B → bA | Ab, C → BA | AB | cB | Bc a jazyk L vět délky 3 sestavených ze slov a, b, c, které obsahují slovo b právě jednou. a) Je gramatika jednoznačná, neboli existuje pro každou věta jazyka L(G) odvoditelnou v G právě jeden syntaktický strom? b) Jaké je pokrytí gramatiky G vzhledem k zamýšlenému jazyku L? c) Jaká je přesnost gramatiky G vzhledem k zamýšlenému jazyku L? 12.3 Syntaktická analýza Gramatiku popisující jazyk lze použít k provádění syntaktické analýzy. Výsledkem syntaktické analýzy je syntaktický strom, který reflektuje strukturu věty a může sloužit jako podklad pro další zpracování. Příklad 12.3.1. Knihovna NLTK (ze cvičení) umožňuje provádění metod zpracování přirozeného jazyka jako předzpracování textu, značkování či syntaktickou analýzu. Napište gramatiku pro knihovnu NLTK, která bude schopná rozeznat slovesný čas vět v anglickém jazyce. Značky, které slovům NLTK přidělí, nesou vedle slovesného druhu i informaci o tvaru slovesa (gerundium, minulý čas apod.), které lze za tímto účelem využít. Gramatika by měla umět určit alespoň následující časy. 127 I speak present simple You are speaking present continuous He has spoken present perfect We spoke past simple They were speaking past continuous I had spoken past perfect 128