Základy matematiky a statistiky pro
humanitní obory
studijní text k předmětům PLIN004 a PLIN006
Vojtěch Kovář
Předměty jsou určeny studentům humanitního zaměření (především oboru
Český jazyk se specializací počítačová lingvistika), kteří pro své studium
potřebují nejnutnější základy matematiky a statistiky. Cílem předmětů je
seznámit studenty humanitních oborů se základy vysokoškolské matematiky a
statistiky. Hlavními probíranými oblastmi jsou výroková a predikátová logika,
úvod do teorie množin, relace a funkce, základy formální lingvistiky, teorie
grafů, popisná statistika a teorie pravděpodobnosti.
1
OBSAH OBSAH
Obsah
1 Proč potřebují lingvisté matematiku 4
2 Definice - věta - důkaz 5
2.1 Typy důkazů . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Matematická logika 7
3.1 Výroková logika . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Predikátová logika . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Matematická indukce . . . . . . . . . . . . . . . . . . . . . . . 11
4 Teorie množin 14
4.1 Množina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Množinové operace . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Čísla 18
5.1 Přirozená čísla . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 Operace na přirozených číslech . . . . . . . . . . . . . . . . . . 19
5.3 Další číselné množiny . . . . . . . . . . . . . . . . . . . . . . . 20
6 Relace a funkce 21
6.1 Uspořádané dvojice . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2 Kartézský součin . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.3 Relace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.4 Vlastnosti relací . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.5 Funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.6 Vlastnosti funkcí . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.7 Velikost množin . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.8 Posloupnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7 Základy formální lingvistiky 27
7.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7.2 Formální gramatika . . . . . . . . . . . . . . . . . . . . . . . . 28
7.3 Chomského hierarchie jazyků . . . . . . . . . . . . . . . . . . 29
7.4 Konečný automat . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.5 Ekvivalence formalismů . . . . . . . . . . . . . . . . . . . . . . 31
8 Kombinatorika a pravděpodobnost 32
8.1 Základní kombinatorická pravidla . . . . . . . . . . . . . . . . 32
8.2 Pravděpodobnost . . . . . . . . . . . . . . . . . . . . . . . . . 32
2
OBSAH OBSAH
9 Základy teorie grafů 34
9.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . 34
9.2 Typy grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
9.3 Rozšíření pojmu graf . . . . . . . . . . . . . . . . . . . . . . . 36
9.4 Graf jako relace . . . . . . . . . . . . . . . . . . . . . . . . . . 37
9.5 Další pojmy z teorie grafů . . . . . . . . . . . . . . . . . . . . 38
9.6 Grafové algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . 39
10 Základy popisné statistiky 43
10.1 Statistický soubor . . . . . . . . . . . . . . . . . . . . . . . . . 43
10.2 Jednorozměrný soubor . . . . . . . . . . . . . . . . . . . . . . 44
10.2.1 Charakteristiky polohy . . . . . . . . . . . . . . . . . . 44
10.2.2 Charakteristiky variability . . . . . . . . . . . . . . . . 45
10.3 Dvourozměrný soubor . . . . . . . . . . . . . . . . . . . . . . 45
11 Statistika a pravděpodobnost 48
11.1 Pravděp. rozložení . . . . . . . . . . . . . . . . . . . . . . . . 48
11.2 Určení rozložení . . . . . . . . . . . . . . . . . . . . . . . . . . 49
11.3 Typy rozložení . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
11.3.1 Zipfův zákon . . . . . . . . . . . . . . . . . . . . . . . 52
11.4 Distribuční funkce . . . . . . . . . . . . . . . . . . . . . . . . . 52
11.5 Náhodný vektor . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12 Podmíněná pravděpodobnost 54
12.1 Nezávislé jevy . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
12.2 Bayesův vzorec . . . . . . . . . . . . . . . . . . . . . . . . . . 55
13 Zákon velkých čísel 58
14 Statistické testování hypotéz 60
15 Entropie 63
15.1 Podmíněná entropie . . . . . . . . . . . . . . . . . . . . . . . . 64
15.2 Mutual information . . . . . . . . . . . . . . . . . . . . . . . . 64
16 Statistika a zpracování jazyka 65
16.1 Vyhledávání kolokací . . . . . . . . . . . . . . . . . . . . . . . 65
16.2 N-gramové modely . . . . . . . . . . . . . . . . . . . . . . . . 66
16.2.1 Nedostatky jazykových modelů . . . . . . . . . . . . . 67
3
1 PROČ POTŘEBUJÍ LINGVISTÉ MATEMATIKU
1 Proč potřebují lingvisté matematiku
Matematika, jakou ji známe ze střední školy, se v mnohém liší od matematiky,
s níž se budeme seznamovat v tomto předmětu. Zatímco hlavním cílem středoškolské
matematiky je naučit se počítat s čísly, abychom byli schopni spočíst
daně, spotřebu auta, úroky z hypotéky, případně věci, o kterých často moc
nemáme představu, k čemu slouží (soustavy rovnic, matice a integrály), cílem
vysokoškolské matematiky je zejména naučit studenty uvažovat abstraktně a
v obecnostech. V tomto kurzu nejsou důležité konkrétní vědomosti a úkoly,
které budeme procházet. Jde o způsob myšlení, který si budete muset osvojit,
abyste byli schopni tyto úkoly řešit.
Tento způsob uvažování je velmi důležitý zejména v dnešní době, kdy
prožíváme rychlou technologickou expanzi ve výpočetní technice a setkáváme
se na každém kroku s nejrůznějšími automatickými nástroji, včetně nástrojů
pro automatické zpracování přirozeného jazyka. Jako studenti lingvistiky
zaměření na počítačové technologie se s takovými nástroji a lidmi kolem nich
budete setkávat ještě mnohem častěji.
Matematika je základem všech technických oborů: slouží jako zásobárna
abstraktních pojmů, znalostí o nich, přesných definic a poskytuje prostředky
pro přesné dokazování tvrzení o těchto abstraktních pojmech. Znalosti o abstraktních
pojmech pak můžeme snadno využít při řešení konkrétních problémů.
Z tohoto důvodu mají všichni studenti technických oborů (včetně informatiky)
základní vzdělání ve vysokoškolské matematice. Tím, že takovýto základ
dostanete také, se vám otevřou dveře ke snažší komunikaci s technicky zaměřenými
lidmi, budete schopni lépe pochopit způsob jejich uvažování a diskutovat
s nimi o problémech na jiné úrovni než lingvisté bez matematického vzdělání.
V konkrétním případě počítačové lingvistiky si usnadníte spolupráci s vývojáři
nástrojů automatického zpracování jazyka a budete schopni podílet se na
vývoji těchto nástrojů.
Kromě tohoto cíle předpokládáme, že vám kurz usnadní studium předmětů
na Fakultě informatiky.
4
2 DEFINICE - VĚTA - DŮKAZ
2 Definice - věta - důkaz
Jak jsme již naznačili, vysokoškolská matematika se nezabývá návody, jak
něco spočítat (jako tomu bylo na střední škole), ale slouží zejména jako
soubor poznatků o abstraktních pojmech. Z tohoto důvodu se ve většině
učebnic vysokoškolské matematiky setkáváme se stylem výkladu definice-
věta-důkaz.
Definicí se rozumí vymezení pojmu. Definice musí obsahovat pouze pojmy,
které byly dříve definovány. Obecně v matematice pracujeme pouze s pojmy,
které byly přesně definovány. Často je pojem vymezen jako libovolný objekt,
který splňuje nějakou množinu logických výroků (tzv. axiomů) – viz dále.
Příkladem jednoduché definice může být např.: Prvočíslo je jakékoli přirozené
číslo, které je dělitelné pouze jedničkou a samo sebou. Aby tato definice
byla plnohodnotná, musíme však již mít definovány pojmy přirozené číslo,
dělitelný a jednička. Nelze spoléhat na to, že tyto pojmy jsou intuitivně
jasné (např. patří 0 mezi přirozená čísla?). V dalším výkladu osvětlíme, jak
vyrobíme (zadefinujeme) všechny matematické objekty pouze na základě dvou
pilířů matematiky – matematické logiky a teorie množin.
Věta je formulací poznatku o definovaných pojmech. Příkladem matematické
věty může být např. Existuje právě jedno sudé prvočíslo. Opět je
potřeba mít předem definován pojem sudý. (Jak?) Jednodušší věta bývá též
označována jako lemma.
Důkaz slouží k ověření pravdivosti tvrzení, a to po jednotlivých krocích
tak, aby nikdo nemohl pochybovat o tom, že věta je pravdivá. S využitím
matematické logiky můžeme pojem důkazu formalizovat (formálně definovat
důkaz). Více v dalším výkladu.
V tomto textu se výše popsaného stylu výkladu budeme držet spíše zřídka.
Důvodem je snaha překlenout propast mezi matematikou a humanitními
obory a zjednodušit uchopení matematických pojmů.
2.1 Typy důkazů
V matematických a informatických textech se setkáváme s různými typy
důkazů: nejčastější jsou následující:
Přímý důkaz je strukturálně nejjednodušší – použitím definic a již
dokázaných tvrzení odvodíme přímo znění věty. Příklad: Mějme definována
přirozená čísla a základní operace na nich. Dále mějme definován pojem sudé
číslo jako násobek 2 (𝑥 je sudé, pokud existuje takové přirozené 𝑘, že 𝑥 = 2*𝑘).
Dokážeme tvrzení 10 je sudé číslo. Kroky důkazu:
1. 10 = 5 * 2 (ze základní aritmetiky přirozených čísel)
5
2.1 Typy důkazů 2 DEFINICE - VĚTA - DŮKAZ
2. 5 * 2 je sudé číslo (z definice – 𝑘 = 5)
3. tedy 10 je sudé číslo
Nepřímý důkaz využívá logickou ekvivalenci (viz též dále) výroků 𝐴 ⇒
𝐵 a ¬𝐵 ⇒ ¬𝐴. Jinými slovy, větu tvaru 𝐴 ⇒ 𝐵 můžeme dokázat tím, že
dokážeme tzv. obměnu ¬𝐵 ⇒ ¬𝐴.
Důkaz sporem je velice podobný. Zde předpokládáme, že dokazovaná
věta neplatí a použitím známých faktů odvodíme spor – nesmyslné tvrzení,
např. 1 = 0, nebo neplatnost některého z předpokladů. Příklad: Mějme
definována přirozená čísla, základní početní operace, dělitele (𝑥 je dělitelem
𝑦, pokud existuje přirozené 𝑧 tak, že 𝑥 * 𝑧 = 𝑦), kladná racionální čísla (𝑟/𝑠
taková, že 𝑟 a 𝑠 jsou přirozená a nemají jiného společného dělitele než 1), a
druhou odmocninu (𝑎2
= 𝑏, pokud 𝑏 * 𝑏 = 𝑎). Dokážeme sporem, že
√
2 není
racionální číslo.
1. Předpokládejme, že
√
2 je racionální číslo.
2. tedy
√
2 = 𝑟/𝑠, kde 𝑟 a 𝑠 jsou přirozená a nemají společného dělitele
(kromě 1)
3. úpravou dostáváme
√
2 * 𝑠 = 𝑟
4. 2 * 𝑠 * 𝑠 = 𝑟 * 𝑟 (umocněním na druhou)
5. Protože levá strana je sudá, pravá je také sudá, tedy 𝑟 je sudé (dokažte
si podrobněji)
6. Tedy 𝑟 = 2 * 𝑐 pro nějaké přirozené 𝑐
7. nahrazením dostaneme 2 * 𝑠 * 𝑠 = 2 * 𝑐 * 2 * 𝑐 a po vydělení dvěma
𝑠 * 𝑠 = 2 * 𝑐 * 𝑐
8. podle úvahy z kroku 5 je 𝑠 také sudé
9. 𝑟 i 𝑠 jsou sudá, tedy mají společného dělitele 2, což je spor s předpokla-
dem.
Matematická indukce je důkazová technika, kterou využíváme, pokud
potřebujeme něco dokázat pro velmi dlouhou nebo nekonečnou posloupnost
objektů. Více o indukci v následující kapitole.
6
3 MATEMATICKÁ LOGIKA
3 Matematická logika
Matematická logika je univerzálním jazykem matematiky, všechny matematické
definice, věty a důkazy je možno zapsat jazykem matematické logiky.
Jeho hlavními výhodami jsou univerzálnost (stejný zápis všude na světě znamená
totéž) a jednoznačnost (na rozdíl od přirozených jazyků, které jsou
víceznačné – např. v mnohých oficiálních textech můžeme nalézt věty typu
„k jednání potřebujete pas a řidičský průkaz nebo občanský průkaz”, kdy není
jasné, co si s sebou vlastně máte vzít).
V případě důkazů pak logika zavádí pojem elementárního kroku a formalizuje
tak dříve zmíněnou vágní formulaci krok za krokem.
Existuje více druhů matematických logik. Pravděpodobně jste již slyšeli
o výrokové a predikátové logice, existují ovšem i složitější typy logik, jako např.
modální, temporální, intenzionální... Naším cílem v této kapitole je probrat
základy výrokové a predikátové logiky a naučit se je prakticky používat
pro čtení a zápis matematiky. Pro podrobnější vhled do temných zákoutí
matematické logiky doporučujeme předmět Matematická logika na Fakultě
informatiky.
3.1 Výroková logika
Základní jednotkou výrokové logiky je výrok. Výrokem chápeme tvrzení,
o němž lze říci, zda je pravdivé nebo nepravdivé, jinými slovy, lze mu přiřadit
pravdivostní hodnotu. (Nezáleží přitom na tom, jestli tuto pravdivostní
hodnotu známe, tj. nemusíme vědět, zda je výrok pravdivý). Příkladem výroku
mohou být např. věty „12345678915264591 je prvočíslo”, „všechny krávy jsou
modré” a podobně.
K zachycení pravdivosti výroku používáme přiřazení hodnoty 0 (nepravda)
nebo 1 (pravda), někdy zapisujeme jako 𝑣(𝐴) = 1 (výrok A platí).
Ke konstrukci složitějších výroků (také výrokových formulí nebo formulí
výrokové logiky) z výroků jednodušších používáme logické funkce.
Mějme výroky 𝐴 a 𝐵. Definujeme výroky
∙ ¬𝐴 (negace) s pravdivostními hodnotami
𝑣(¬𝐴) = 1, pokud 𝑣(𝐴) = 0,
𝑣(¬𝐴) = 0, pokud 𝑣(𝐴) = 1;
∙ 𝐴 ⇒ 𝐵 (implikace) s pravdivostními hodnotami
𝑣(𝐴 => 𝐵) = 0, pokud 𝑣(𝐴) = 1 a 𝑣(𝐵) = 0,
𝑣(𝐴 => 𝐵) = 1 v ostatních případech.
7
3.1 Výroková logika 3 MATEMATICKÁ LOGIKA
Tyto logické spojky se nazývají základní, neboť jejich kombinací lze vyjádřit
všechny ostatní logické funkce.1
Všechny ostatní logické funkce nazýváme
odvozené. Mezi nejpoužívanější patří:
∙ 𝐴 ∧ 𝐵 (konjunkce, též logické „a”) s pravdivostními hodnotami
𝑣(𝐴 ∧ 𝐵) = 1, pokud 𝑣(𝐴) = 1 a 𝑣(𝐵) = 1,
𝑣(𝐴 ∧ 𝐵) = 0 v ostatních případech;
∙ 𝐴 ∨ 𝐵 (disjunkce, též logické „nebo”) s pravdivostními hodnotami
𝑣(𝐴 ∨ 𝐵) = 0, pokud 𝑣(𝐴) = 0 a 𝑣(𝐵) = 0,
𝑣(𝐴 ∨ 𝐵) = 1 v ostatních případech;
∙ 𝐴 ⇔ 𝐵 (ekvivalence) ve významu (𝐴 ⇒ 𝐵) ∧ (𝐵 ⇒ 𝐴)
Implikaci čteme jako „jestliže A, pak B”, ekvivalenci čteme jako „A platí
právě tehdy, když platí B”. Pozor na přesnou sémantiku implikace: pokud je
na levé straně nepravdivý výrok, pak je celá implikace pravdivá, tedy výrok
„jestliže jsou všechny krávy modré, pak je uhlí bílé” by byl pravdivý.
Pravdivost různých složených výroků zkoumáme nejčastěji pomocí pravdivostních
tabulek, které znázorňují pravdivostní hodnoty složených výroků
v závislosti na pravdivostních hodnotách jednodušších výroků a které jistě
znáte ze střední školy. Pravdivostní tabulka pro výrok (𝐴 ∨ 𝐵) ⇒ 𝐶 vypadá
např. takto:
𝐴 𝐵 𝐶 (𝐴 ∨ 𝐵) (𝐴 ∨ 𝐵) ⇒ 𝐶
1 1 1 1 1
1 1 0 1 0
1 0 1 1 1
1 0 0 1 0
0 1 1 1 1
0 1 0 1 0
0 0 1 0 1
0 0 0 0 1
(Dejte vždy pozor na to, že je nutné vypsat všechny kombinace pravdivostních
hodnot základních výroků.)
Výrok, který je za všech okolností platný (v pravdivostní tabulce má všude
jedničky), se nazývá tautologie. Výrok, který neplatí nikdy (v pravdivostní
tabulce má všude nuly) se nazývá kontradikce.
1
Nicméně, existují i jiné dvojice a dokonce i samostatné spojky, které by mohly být
podle tohoto kritéria označeny za „základní”; volba negace a implikace je dána konvencí.
8
3.1 Výroková logika 3 MATEMATICKÁ LOGIKA
Výroková logika nám též poskytuje základ pro formalizaci pojmu důkaz.
Využíváme k tomu tzv. axiomy a odvozovací pravidla. Standardní podoba
výrokové logiky nám poskytuje tři schémata axiomů (kde dosazením konkrétních
výroků vzniknou axiomy) a jedno odvozovací pravidlo. Schémata axiomů
jsou:
1. 𝐴 ⇒ (𝐵 ⇒ 𝐴)
2. (𝐴 ⇒ (𝐵 ⇒ 𝐶)) ⇒ ((𝐴 ⇒ 𝐵) ⇒ (𝐴 ⇒ 𝐶))
3. (¬𝐵 ⇒ ¬𝐴) ⇒ (𝐴 ⇒ 𝐵)
(Jako cvičení si pravdivostní tabulkou můžete ověřit, že všechny uvedené
axiomy jsou vždy pravdivé, nezávisle na pravdivosti základních výroků.)
Odvozovací pravidlo máme jediné, a to modus ponens:
∙ pokud platí 𝐴 a platí 𝐴 ⇒ 𝐵, odvodíme, že platí 𝐵
Důkazem potom rozumíme posloupnost výroků, z nichž každý je buď
axiomem nebo aplikací odvozovacího pravidla na předchozí výroky. Příkladem
formálního důkazu je následující posloupnost výroků, která dokazuje, že pro
libovolný výrok 𝑋 platí 𝑋 ⇒ 𝑋:2
1. (𝑋 ⇒ ((𝑋 ⇒ 𝑋) ⇒ 𝑋)) ⇒ ((𝑋 ⇒ (𝑋 ⇒ 𝑋)) ⇒ (𝑋 ⇒ 𝑋)) / axiom 2
2. 𝑋 ⇒ ((𝑋 ⇒ 𝑋) ⇒ 𝑋) / axiom 1
3. (𝑋 ⇒ (𝑋 ⇒ 𝑋)) ⇒ (𝑋 ⇒ 𝑋) / aplikace modus ponens na 2. a 1.
4. 𝑋 ⇒ (𝑋 ⇒ 𝑋) / axiom 1
5. 𝑋 ⇒ 𝑋 / aplikace modus ponens na 4. a 3.
Samozřejmě všechny důkazy nebudeme provádět takto formálně – budeme
se vždy spoléhat na to, že už něco víme. Výše uvedený příklad ale ukazuje,
jaké jsou základní stavební kameny dokazování v matematice – každý důkaz
může být rozepsán až na základní axiomy a aplikace odvozovacího pravidla,
jako je tomu výše, a může být plně mechanicky ověřena jeho správnost.
V následující kapitole popíšeme některé aspekty predikátové logiky, se
kterými se můžete často setkat.
2
Ponechme nyní stranou fakt, že dokazovaný výrok je tautologie, což můžeme snadno
ověřit pravdivostní tabulkou.
9
3.2 Predikátová logika 3 MATEMATICKÁ LOGIKA
3.2 Predikátová logika
Predikátová logika je rozšířením logiky výrokové. Zavádí zejména proměnné,
kvantifikátory a predikáty.
Proměnné, jak název napovídá, zavádí symboly, které mohou nabývat
různých hodnot – nejčastěji je značíme malými písmeny. Formule predikátové
logiky mohou obsahovat proměnné a jejich pravdivost může záviset na ohodnocení
těchto proměnných, tj. na přiřazení konkrétních hodnot proměnným
(např. formule „𝑥 = 1”: pokud je proměnné 𝑥 přiřazena 1, je formule pravdivá,
jinak je nepravdivá).
Kvantifikátory nám umožňují výskyty proměnných svázat tak, že pravdivost
formule již nebude závislá na ohodnocení. Rozeznáváme dva kvantifi-
kátory:
∙ univerzální (∀), který vyjadřuje, že následující formule platí pro
všechna možná ohodnocení proměnné za kvantifikátorem. Např. formule
∀𝑥(𝑥 = 1) je nepravdivá, neboť zřejmě existuje ohodnocení, kde např.
𝑥 = 0 a formule 𝑥 = 1 je nepravdivá.
∙ existenční (∃), vyjadřující, že existuje alespoň jedno ohodnocení takové,
že následující formule platí. Např. formule ∃𝑥(𝑥 = 1) je pravdivá,
neboť výrok 𝑥 = 1 platí při valuaci, kde 𝑥 = 1.
Predikáty jsou veškeré symboly, které nepatří do samotného jazyka logiky
– tj. vše kromě proměnných, logických spojek, kvantifikátorů a závorek. Význam
predikátů záleží na naší definici, není dán samotnou logikou. Příkladem
predikátů může být např. 𝑃 𝑟𝑖𝑚𝑒, kde 𝑃 𝑟𝑖𝑚𝑒(𝑥) budeme chápat tak, že
𝑥 je prvočíslo, nebo symbol ∈, který budeme dále používat jako symbol
příslušnosti do množiny (jako ∈ (𝑥, 𝑋) nebo čitelněji, 𝑥 ∈ 𝑋). Každý predikát
má definovánu aritu, což je počet jeho parametrů (𝑃 𝑟𝑖𝑚𝑒 má aritu 1, ∈ má
aritu 2). Predikáty arity 0 nazýváme konstantami (např. „1” v příkladu
výše).
Příkladem složitější predikátové formule může být např. definice prvočísla
(predikátu 𝑃 𝑟𝑖𝑚𝑒) jen s využitím základních operací na přirozených číslech:3
𝑃 𝑟𝑖𝑚𝑒(𝑥) ≡ 𝑥 ≥ 2 ∧ ∀𝑦(∀𝑧((𝑦 * 𝑧 = 𝑥) ⇒ (𝑧 = 𝑥 ∨ 𝑧 = 1)))
Po částech lze formuli „přeložit” jako: prvočíslo je číslo větší nebo rovno
2, kde pro všechny možné dělitele (𝑦) platí, že ve všech možných rozkladech
𝑥 na (𝑦 * 𝑧) je vždy jeden z členů tohoto rozkladu 1 a druhý 𝑥.
3
rovněž zde prozatím předpokládáme, že všechny proměnné jsou z domény přirozených
čísel
10
3.3 Matematická indukce 3 MATEMATICKÁ LOGIKA
3.3 Matematická indukce
Matematická indukce je v prvé řadě důkazová technika, kterou můžeme
dokázat nějaké tvrzení pro všechny prvky nějaké posloupnosti (i nekonečné).
Princip indukce je však využíván často i v definicích velkých (nekonečných)
struktur, jak uvidíme v dalším výkladu.
Mějme nějakou posloupnost libovolných objektů 𝑥0, ..., 𝑥 𝑛, ... a chceme
dokázat, že pro všechny prvky dané posloupnosti platí nějaká formule 𝐹, tedy
∀𝑖(𝐹(𝑥𝑖)), kde 𝐹(𝑥𝑖) chápeme tak, že formule 𝐹 platí pro prvek posloupnosti
𝑥𝑖. Technika důkazu indukcí se skládá ze dvou základních částí:
∙ báze indukce: Dokážeme, že formule platí pro první prvek posloup-
nosti.
∙ indukční krok: Dokážeme implikaci (𝐹(𝑥𝑖) ⇒ 𝐹(𝑥𝑖+1)), tedy pokud
formule platí pro nějaký prvek posloupnosti, pak platí i pro jeho bezprostředního
následníka. Levou stranu předchozí implikace nazýváme
indukční předpoklad.
Příklad: Dokážeme, že pro všechna přirozená 𝑛 ≥ 1 platí:
1 + 2 + ... + 𝑛 = 𝑛/2 * (1 + 𝑛)
Báze indukce: za 𝑛 dosadíme první prvek posloupnosti, tedy 1. Dostáváme
1 = 1/2 * (1 + 1), což je evidentně pravda.
Indukční krok: Předpokládejme (indukční předpoklad), že pro nějaké 𝑘
platí
1 + 2 + ... + 𝑘 = 𝑘/2 * (1 + 𝑘)
Dokážeme, že platí
1 + 2 + ... + 𝑘 + (𝑘 + 1) = (𝑘 + 1)/2 * (1 + (𝑘 + 1))
Dosazením indukčního předpokladu do levé strany a následujícími úpravami
podle aritmetiky nad přirozenými čísly postupně dostáváme:
∙ 1 + 2 + ... + 𝑘 + (𝑘 + 1)
∙ 𝑘/2 * (1 + 𝑘) + (𝑘 + 1)
∙ (𝑘 + 𝑘2
)/2 + (𝑘 + 1)
11
3.3 Matematická indukce 3 MATEMATICKÁ LOGIKA
∙ (𝑘 + 𝑘2
+ 2𝑘 + 2)/2
∙ (𝑘2
+ 3𝑘 + 2)/2
∙ (𝑘 + 2) * (𝑘 + 1)/2
∙ (𝑘 + 1)/2 * (𝑘 + 2)
∙ (𝑘 + 1)/2 * (1 + (𝑘 + 1))
Tím je věta dokázána.
Je namístě se ptát: Je tento postup korektní? Opravdu touto technikou
dokážeme nějaké tvrzení pro všechny prvky příslušné posloupnosti?
Je třeba ověřit, že technika matematické indukce je korektní. Na tomto
místě se spokojíme pouze s intuitivním ověřením a prohlášením, že formální
důkaz existuje, ale je nad rámec předmětu.
Ověřením báze je dokázáno, že formule 𝐹 platí pro 𝑥0, platí tedy 𝐹(𝑥0).
Protože jsme dokázali indukční krok, platí také formule 𝐹(𝑥0) ⇒ 𝐹(𝑥1).
Aplikací pravidla modus ponens na předchozí dva výroky dostáváme, že platí
i formule 𝐹(𝑥1). Protože indukční krok jsme dokázali pro libovolné 𝑘, platí
i 𝐹(𝑥1) ⇒ 𝐹(𝑥2). Opět aplikací pravidla modus ponens na předchozí dva
výroky dostáváme platnost formule 𝐹(𝑥2). Takto můžeme pokračovat do
nekonečna a dopracovat se k platnosti formule 𝐹(𝑥𝑖) pro libovolné přirozené
𝑖, platí tedy ∀𝑖(𝐹(𝑥𝑖)).
Poměrně často se můžeme setkat i se složitějšími typy indukce; například
nám někdy nestačí v indukčním kroku předpokládat, že daná formule platí
pro jeden bezprostředně předcházející prvek, ale potřebujeme dva nebo i více
předcházejících prvků. Princip indukce se tím nemění, pouze musíme dokázat
odpovídající bázi (tj. pro 2 nebo více prvních prvků, abychom byli schopni
poprvé aplikovat pravidlo modus ponens – viz předchozí odstavec).
Jak jsme již naznačili výše, princip indukce se dá dobře využít i v definicích,
zejména pokud se jedná o nekonečné struktury, množiny a podobně. Zde to
vypadá tak, že výčtem definujeme jeden nebo více nejjednodušších prvků
dané struktury a analogií indukčního kroku specifikujeme, jak z jednodušších
objektů vytvářet objekty složitější. Příkladem může být definice číselných
výrazů se sčítáním a násobením:
∙ každé číslo je výraz (báze)
∙ pokud 𝑥 a 𝑦 jsou výrazy, pak (𝑥 + 𝑦) je výraz
∙ pokud 𝑥 a 𝑦 jsou výrazy, pak (𝑥 * 𝑦) je výraz
12
3.3 Matematická indukce 3 MATEMATICKÁ LOGIKA
Jak vidíme, definice výše má jednu bázi a dva indukční kroky.
Pokud bychom potřebovali dokázat nějaké tvrzení pro celou takto definovanou
strukturu, použijeme techniku zvanou strukturální indukce, která
postupuje tzv. po struktuře objektu, podle jeho definice. Konkrétně dokážeme
dané tvrzení nejprve pro všechny prvky z báze dané definice, a pak
dokazujeme implikaci „pokud tvrzení platí pro jednodušší objekty, platí i pro
složitější objekt”, přesně podle struktury definice. Důkaz podle definice číselných
výrazů výše by měl jednu bázi a dva indukční kroky. Důkaz indukcí tedy
můžeme využít nejen pro dokazování vlastností posloupností, ale i složitějších
struktur jako jsou výrazy, logické formule apod.
Jako cvičení si zkuste dokázat, že libovolný číselný výraz podle výše
uvedené definice obsahuje sudý počet závorek.
13
4 TEORIE MNOŽIN
4 Teorie množin
Spolu s matematickou logikou, která tvoří jakýsi jazyk popisu matematického
světa, je teorie množin základním stavebním kamenem matematiky. Téměř
všechny matematické objekty je možno definovat jako množiny, včetně čísel,
posloupností, funkcí, automatů apod., jak uvidíme v dalším výkladu. Navíc
všechny tyto objekty lze zkonstruovat na základě jediného základního objektu,
prázdné množiny ∅, tedy množiny, která neobsahuje žádné prvky.
Teorie množin doplňuje jazyk predikátové logiky o binární predikát je
prvkem (∈):
𝑎 ∈ 𝑏 čteme „a je prvkem b”;
dále pak o konstantní symbol prázdné množiny (∅) a dále o prostředky
pro zápis množinových objektů, zejména složené závorky ({}).
4.1 Množina
Teorie množin zavádějí množiny jako objekty, které vyhovují určitým axiomům
– takovýmto teoriím říkáme axiomatické teorie množin a jsou tou „správnou”
cestou, jak definovat matematické objekty. Příkladem axiomu z teorie množin
je axiom vydělení, který vyjadřuje, že z libovolné množiny můžeme vybrat
některé prvky, pro které platí formule 𝐹, a tím vytvořit jinou množinu:
∀𝑎(∃𝑏(∀𝑥(𝑥 ∈ 𝑏 ⇔ (𝑥 ∈ 𝑎 ∧ 𝐹(𝑥)))))
(Díky tomuto axiomu např. existuje prázdná množina.) V současnosti
existuje více axiomatických teorií množin, které se od sebe mírně liší tím,
jaký výčet axiomů je v každé z nich použit.
V tomto textu se nebudeme dopodrobna zabývat žádnou z axiomatických
teorií množin. Půjde nám hlavně o to, abychom se naučili množiny prakticky
používat při definicích a zápisech matematických faktů a spokojíme se s tzv.
„naivní” teorií množin, s níž jste se pravděpodobně setkali na střední škole:4
Množinu budeme považovat za skupinu objektů (které nemusí být
nutně stejného typu), jež neobsahuje duplicity (tj. každý prvek
4
Problémy s naivní teorií množin nastávají, pokud začneme používat obskurní definice
množin – můžeme si je ilustrovat na příkladu vojenského holiče: Řekneme-li, že holič
holí všechny vojáky, kteří se neholí sami (a přitom holič sám je voják), kdo holí holiče?
Matematická obdoba této jazykové hříčky se nazývá Russelův paradox a axiomatické teorie
množin právě kvůli tomuto paradoxu definují přesné postupy, jak mohou vznikat množiny.
Množinám, které nesplňují axiomy teorie množin, typicky říkáme třídy.
14
4.2 Množinové operace 4 TEORIE MNOŽIN
je v ní obsažen maximálně jednou) a není uspořádaná ({1, 2, 3} a
{3, 2, 1} jsou totožné množiny).
Zejména si uvědomme tři základní fakta:
1. existuje prázdná množina ∅, která neobsahuje žádné prvky;
2. prvky množiny mohou být i jiné množiny;
3. množiny mohou být nekonečné (obsahovat nekonečně mnoho prvků).
Malé konečné množiny obvykle zapisujeme výčtem prvků – např. množina
{1, 2, 3} obsahuje prvky 1, 2 a 3, množina {∅, {∅}} obsahuje dva prvky –
∅ (prázdná množina) a {∅} (množina obsahující prázdnou množinu). Velké
nebo nekonečné množiny můžeme zapisovat s využitím formule, která musí
platit pro všechny členy množiny. Např. množina {𝑥 | 𝑥 ∈ N ∧ 𝑥 > 5}
obsahuje přirozená čísla větší než 5. Jako zkratka pro tento zápis se též často
používá{𝑥 ∈ N | 𝑥 > 5}.5
4.2 Množinové operace
Jak jsme již uvedli, základní operací na množinách je operace příslušnosti
do množiny ∈. Zdůrazněme, že na levé straně je vždy prvek (který může být
množinou), na pravé straně je vždy množina. Doplňkem operátoru ∈ je ̸∈,
které definujeme takto:
𝑎 ̸∈ 𝐵 ⇔ ¬(𝑎 ∈ 𝐵)
Příklady platných formulí s těmito operátory:
∙ ∀𝑥(𝑥 ̸∈ ∅)
∙ ∅ ∈ {∅}
∙ ∅ ̸∈ {{∅}}
∙ ∅ ̸∈ ∅
Další operací (predikátem), kterou můžeme snadno definovat, je podmnožina
(⊆). Definujeme ji takto:
5
Pokud budeme důsledně používat podmínku, že všechny prvky námi definované množiny
patří do nějaké jiné množiny, máme jistotu, že se vyhneme Russelovu paradoxu – tímto
postupem de facto využíváme axiom vydělení uvedený výše.
15
4.2 Množinové operace 4 TEORIE MNOŽIN
𝐴 ⊆ 𝐵 ⇔ ∀𝑥(𝑥 ∈ 𝐴 ⇒ 𝑥 ∈ 𝐵)
Tedy množina A je podmnožinou množiny B právě tehdy, pokud všechny
prvky A jsou zároveň i prvky B.
Na tomto místě poznamenejme, že pro predikátové formule tohoto typu
často používáme zkrácený zápis:
∀𝑥 ∈ 𝐴 (𝑥 ∈ 𝐵),
který by v takovéto podobě nebyl v čisté predikátové logice možný. Podobně,
pro existenční kvantifikátor často používáme zkrácený zápis např.
∃𝑥 ∈ 𝐴 (𝑥 ∈ 𝐵),
ale v trochu jiném významu: Výraz výše je ekvivalentní formuli
∃𝑥(𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵),
Na základě pojmu podmnožina definujeme pojem potenční množina.
Potenční množina množiny 𝐴 – zapisujeme 𝒫(𝐴) – je možina všech podmnožin
této množiny. Formálně:
𝒫(𝐴) = {𝑥 | 𝑥 ⊆ 𝐴}
Protože potenční množina má vždy 2 𝑎
prvků,6
kde 𝑎 je počet prvků
množiny 𝐴, někdy značíme potenční množinu množiny 𝐴 jako 2 𝐴
.
Platí:
∙ 𝒫(∅) = {∅}
∙ 𝒫({∅}) = {∅, {∅}}
∙ ∀𝑥(∅ ∈ 𝒫(𝑥) ∧ 𝑥 ∈ 𝒫(𝑥))
S využitím pojmu podmnožiny se definuje i rovnost množin:
𝐴 = 𝐵 ⇔ (𝐴 ⊆ 𝐵 ∧ 𝐵 ⊆ 𝐴)
Tuto kapitolu zakončíme definicí dvou operací, které znáte ze střední školy,
průnik (∩) a sjednocení (∪). Než budete číst dál, zkuste si je definovat
sami.
6
Rozmyslete si proč.
16
4.2 Množinové operace 4 TEORIE MNOŽIN
Správné definice jsou:
𝐴 ∩ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵}
𝐴 ∪ 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵}
17
5 ČÍSLA
5 Čísla
Na střední škole jsme se seznámili s některými číselnými množinami – přirozenými
čísly, celými čísly, racionálními, reálnými a komplexními čísly a učili
jsme se s nimi počítat. V minulé kapitole jsme zmínili, že všechny objekty
v matematice, včetně čísel, jsou množiny. V této kapitole si tedy ukážeme,
jak lze z množin vyrobit přirozená čísla a definovat operace na nich.
5.1 Přirozená čísla
Podobně jako jsou množiny ve formálních teoriích množin definovány axiomy
v predikátové logice, jsou i přirozená čísla definována jako objekty, které
splňují jisté formální axiomy. Zatímco ve výkladu o množinách jsme tyto
axiomy neuváděli, v případě čísel si je již uvedeme – jedná se o jednoduchý
axiomatický systém, který nám umožní lépe pochopit, jak funguje formální
matematika.
Jazyk přirozených čísel zavádí do predikátové logiky dva nové symboly:
∙ nulu 0 a
∙ unární funkční symbol 𝑆, který budeme interpretovat jako násled-
níka.
Přirozená čísla jsou pak určena množinou axiomů, které nazýváme Peanova
aritmetika (po italském matematikovi Peanovi). Tyto axiomy jsou:
∙ ∃𝑥(𝑥 = 0) (existuje nula)
∙ ∀𝑥(∃𝑦(𝑦 = 𝑆(𝑥))) (každé číslo 𝑥 má následníka 𝑆(𝑥))
∙ ∀𝑥(¬(0 = 𝑆(𝑥))) (nula není následníkem žádného čísla)
∙ ∀𝑥(∀𝑦(𝑆(𝑥) = 𝑆(𝑦) ⇒ 𝑥 = 𝑦)) (různá čísla mají různé následníky)
Nyní definujeme množinový systém, který bude splňovat výše uvedené
axiomy a tím dostaneme „fyzická” přirozená čísla:
∙ 0 ≡ ∅
∙ 𝑆(𝑥) ≡ 𝑥 ∪ {𝑥}
18
5.2 Operace na přirozených číslech 5 ČÍSLA
Tedy nulu definujeme jako prázdnou množinu a následníka libovolného
čísla definujeme jako sjednocení tohoto čísla (resp. množiny odpovídající
tomuto číslu) s jednoprvkovou množinou, která toto číslo (resp. množinu)
obsahuje.
Jak tedy vypadají přirozená čísla v množinové notaci?
∙ 0 ≡ ∅
∙ 1 = 𝑆(0) = ∅ ∪ {∅} = {∅}
∙ 2 = 𝑆(1) = {∅} ∪ {{∅}} = {∅, {∅}}
∙ 3 = 𝑆(2) = ... = {∅, {∅}, {∅, {∅}}}
atd. Zkuste si jako cvičení vypsat ještě několik dalších. Zjistíte, že pro
každé přirozené číslo 𝑛 platí, že 𝑛 = {0, 1, ..., 𝑛 − 1}. Zkuste rovněž navrhnout
důkaz, že pro takovýto množinový systém platí Peanovy axiomy uvedené
výše.
5.2 Operace na přirozených číslech
Nyní si ukážeme, jak lze na systému přirozených čísel definovat základní
operace, sčítání (+) a násobení (*). Obě definice jsou induktivní:
19
5.3 Další číselné množiny 5 ČÍSLA
∙ 𝑎 + 0 = 𝑎
∙ 𝑎 + 𝑆(𝑏) = 𝑆(𝑎 + 𝑏)
∙ 𝑎 * 0 = 0
∙ 𝑎 * 𝑆(𝑏) = (𝑎 * 𝑏) + 𝑎
Jak vidíme, tyto operace jsou nezávislé na konkrétní (množinové) realizaci
a pracují pouze s operací následníka. Nadále tedy množinovou realizaci
přirozených čísel již nemusíme používat a můžeme pracovat pouze s abstrakcí
následníka. Jak tedy bude vypadat například výpočet 1+2 podle výše uvedené
definice? (platí 1 = 𝑆(0), 2 = 𝑆(1) = 𝑆(𝑆(0)) – tyto rovnosti chápeme pouze
jako různé zápisy téhož)
∙ 1 + 2
∙ 1 + S(1)
∙ S(1 + 1)
∙ S(1 + S(0))
∙ S(S(1 + 0))
∙ S(S(1))
∙ S(S(S(0)))
∙ = 3
Vyzkoušejte si i jiné výpočty podle uvedených definic. Zejména si všimněte,
že nemůžeme zaměnit 1 + 2 a 2 + 1 (i když druhý z těchto výpočtů podle
definice by byl kratší a i když ze střední školy víme, že to platí), neboť
nemáme definováno žádné pravidlo, podle kterého bychom to mohli udělat, a
komutativitu sčítání jsme zatím nedokázali.
5.3 Další číselné množiny
Další číselné množiny (celá, racionální, reálná čísla) jsou v matematice konstruovány
s využitím dvojic, ekvivalencí a dalších pokročilejších matematických
konstrukcí, kterým se budeme věnovat v dalších kapitolách. Proto i konstrukce
dalších číselných množin bude vyložena později.
20
6 RELACE A FUNKCE
6 Relace a funkce
V této kapitole se budeme zabývat koncepty relací a funkcí, které lze dále
používat pro složitější matematické konstrukce a operace.
6.1 Uspořádané dvojice
Základním pojmem této části je uspořádaná dvojice. Jak název napovídá,
jedná se o spojení dvou prvků, v němž (narozdíl od dvouprvkové množiny)
rozlišujeme první a druhý prvek. Uspořádanou dvojici s prvky 𝑎 a 𝑏 zapisujeme
(𝑎, 𝑏) a lze ji definovat jako množinu {{𝑎}, {𝑎, 𝑏}}. Touto definicí je zaručeno,
že v každém případě víme, který z prvků je první a který druhý, jinými slovy,
že dvě různé uspořádané dvojice nebudou reprezentovány stejnou množinou
(důkaz je technicky složitější, proto jej zde nebudeme uvádět). Jsou možné i
jiné definice, výše uvedená je ale nejpřímočařejší.
Lze definovat i uspořádané trojice nebo obecně 𝑛-tice (pro libovolné
přirozené 𝑛), a to následovně:
∙ (𝑎, 𝑏, 𝑐) ≡ (𝑎, (𝑏, 𝑐)), tedy trojice je totéž jako dvojice, jejímž prvním
prvkem je první prvek trojice a druhým uspořádaná dvojice se zbylými
dvěma prvky
∙ (𝑎1, 𝑎2, 𝑎3, ..., 𝑎 𝑛) ≡ (𝑎1, (𝑎2, (𝑎3, (..., 𝑎 𝑛)...)))
Tato definice 𝑛-tic má jisté nevýhody, proto si na konci kapitoly uvedeme
alternativní definici s využitím funkcí (kde definujeme 𝑛-tice jako konečné
posloupnosti).
6.2 Kartézský součin
Na základě pojmu uspořádané dvojice můžeme definovat kartézský součin
množin (𝐴 × 𝐵), definovaný takto:
𝐴 × 𝐵 ≡ {(𝑎, 𝑏) | 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ 𝐵}
Tedy kartézský součin dvou množin obsahuje (všechny) uspořádané dvojice
takové, že první prvek je z první množiny a druhý prvek je z druhé množiny.
Analogicky můžeme definovat kartézský součin více množin, který bude
obsahovat uspořádané 𝑛-tice.
21
6.3 Relace 6 RELACE A FUNKCE
6.3 Relace
Motivací pro pojem relace je způsob svázání dvou, případně více hodnot, možnost
vyjádření toho, že některé hodnoty z obou množin mají něco společného.
Relace také tvoří základ pro definici funkcí.
Binární relace mezi množinami 𝐴 a 𝐵 je podmnožina kartézského součinu
𝐴 × 𝐵 (tedy množina uspořádaných dvojic – podobně definujeme 𝑛-ární
relaci jako množinu uspořádaných 𝑛-tic). Často říkáme binární relace na
množině A, čímž rozumíme relaci množiny s ní samotnou, tedy podmnožinu
kartézského součinu 𝐴 × 𝐴 (analogicky můžeme opět mluvit o 𝑛-ární relaci
na množině A).
Příklady relací:
∙ Relace identity na množině A:
𝐼𝑑(𝐴) – binární relace
𝐼𝑑(𝐴) = {(𝑎, 𝑎) ∈ 𝐴 × 𝐴 | 𝑎 ∈ 𝐴}
∙ Relace větší nebo rovno na přirozených číslech:
≥ (𝑁) – binární relace
≥ (𝑁) = {(𝑎, 𝑏) ∈ 𝑁 × 𝑁 | 𝑏 ⊆ 𝑎}
(srovnejte s množinovou konstrukcí přirozených čísel)
∙ Relace plus na přirozených číslech:
+(𝑁) – ternární relace
+(𝑁) = {(𝑎, 𝑏, 𝑐) ∈ 𝑁 × 𝑁 × 𝑁 | 𝑎 + 𝑏 = 𝑐}
𝑎+𝑏 = 𝑐 pak můžeme prohlásit jen za jiný zápis pro (𝑎, 𝑏, 𝑐) ∈ +(𝑁)
a všechny operace na číslech považovat za relace
Relace na malých konečných množinách můžeme přehledně zapisovat tabulkou,
kde prvky množiny jsou v záhlaví řádků i sloupců a příslušnost dvojice
v relaci značíme jedničkou nebo nulou v příslušné buňce tabulky. Přehledný
je rovněž zápis grafem, kdy mezi prvky množiny kreslíme orientované šipky,
podle toho, které dvojice jsou v relaci.
6.4 Vlastnosti relací
Lze definovat některé vlastnosti relací, které jsou motivovány jejich následným
použitím. Všechny vlastnosti jsou definovány výrokovými formulemi, jejich
22
6.4 Vlastnosti relací 6 RELACE A FUNKCE
význam lze ale většinou vyjádřit srozumitelnějším jazykem. 𝑛-ární Reflexivita
vyjadřuje, že každý prvek je v relaci sám se sebou. Relace 𝑅 na množině
𝐴 je reflexivní, pokud platí
∀𝑎 ∈ 𝐴 ( (𝑎, 𝑎) ∈ 𝑅 )
Symetrie, jak název napovídá, je vlastnost, která vynucuje, že ke každé
dvojici v relaci existuje symetrická dvojice, tedy taková, kde první a druhý
prvek jsou prohozeny. Relace 𝑅 na množině 𝐴 je symetrická, pokud platí
∀𝑎, 𝑏 ∈ 𝐴 ( (𝑎, 𝑏) ∈ 𝑅 ⇒ (𝑏, 𝑎) ∈ 𝑅 )
Antisymetrie je opakem symetrie; říká, že relace neobsahuje žádné dvě
symetrické dvojice (s výjimkou takových, kde první a druhý prvek jsou stejné).
Formálně, relace 𝑅 na množině 𝐴 je antisymetrická, pokud platí
∀𝑎, 𝑏 ∈ 𝐴 ( (𝑎, 𝑏) ∈ 𝑅 ∧ (𝑏, 𝑎) ∈ 𝑅 ⇒ 𝑎 = 𝑏 )
Tranzitivita je komplikovanější. Relace je tranzitivní, pokud ke každým
dvěma dvojicím (𝑎, 𝑏) a (𝑏, 𝑐), které jsou v relaci, existuje v relaci i dvojice
(𝑎, 𝑐); tranzitivita tedy vyjadřuje jistý typ souvislosti relace. V případě zápisu
grafem si tuto vlastnost lze představit tak, že dojdeme-li z nějakého bodu do
jiného podle šipek, pak musí existovat zkratka, tedy šipka přímo ze startu do
cíle. Formálně, relace 𝑅 na množině 𝐴 je tranzitivní, pokud platí
∀𝑎, 𝑏, 𝑐 ∈ 𝐴( (𝑎, 𝑏) ∈ 𝑅 ∧ (𝑏, 𝑐) ∈ 𝑅 ⇒ (𝑎, 𝑐) ∈ 𝑅 )
Ekvivalence je taková relace, která je současně reflexivní, symetrická i
tranzitivní.
Uspořádání je taková relace, kteráje současně reflexivní, antisymetrická
i tranzitivní.
Například identita na libovolné množině splňuje všechny uvedené vlastnosti
(rozmyslete si postupně proč), je tedy ekvivalencí i uspořádáním. Relace „menší
nebo rovno” na přirozených číslech je reflexivní, antisymetrická a tranzitivní
(opět si rozmyslete proč), je tedy uspořádáním. Hypotetická relace „sedí vedle”
na množině studentů v přednáškové místnosti není tranzitivní, není tedy
ekvivalencí ani uspořádáním.
23
6.5 Funkce 6 RELACE A FUNKCE
6.5 Funkce
Funkce je speciální typ relace; dalo by se říci, že „býti funkcí” je vlastnost
relací podobně jako například tranzitivita. Funkce je taková (𝑛-ární) relace,
kde prvních 𝑛 − 1 hodnot v 𝑛-tici jednoznačně určuje poslední hodnotu.
Alternativně se můžeme na relaci podívat jako na vstupně-výstupní mechanismus:
prvních 𝑛 − 1 hodnot v 𝑛-tici můžeme pokládat za argumenty
relace (vstup), poslední hodnotu za její výsledek (výstup – srovnejte např.
s relací +(𝑁) výše). Pokud má být taková relace funkcí, výstup musí být
jednoznačně určen argumenty. Z tohoto pohledu vychází i speciální zápis
funkcí: např. místo
(𝑎, 𝑏, 𝑐) ∈ +
píšeme často v případě funkcí
+(𝑎, 𝑏) = 𝑐
(stále uvažujeme ternární relaci +(𝑁)). Z tohoto pohledu na funkce vychází
i konvence ohledně arity funkcí, která se určuje podle počtu argumentů: Tedy
unární funkce je binární relace, ternární relace je binární funkce apod.
Formálně, binární relace 𝑓 na množině 𝐴 je funkce, pokud platí:
∀𝑎, 𝑏, 𝑐 ∈ 𝐴 ( (𝑎, 𝑏) ∈ 𝑓 ∧ (𝑎, 𝑐) ∈ 𝑓 ⇒ 𝑏 = 𝑐 )
Obdobně, ternární relace 𝑓 na množině 𝐴 je funkce, pokud:
∀𝑎, 𝑏, 𝑐, 𝑑 ∈ 𝐴 ( (𝑎, 𝑏, 𝑐) ∈ 𝑓 ∧ (𝑎, 𝑏, 𝑑) ∈ 𝑓 ⇒ 𝑐 = 𝑑 )
Podobně si zkuste definovat funkce více argumentů.
Funkcím také někdy říkáme zobrazení. Pro binární relaci 𝑓 mezi množinami
𝐴 a 𝐵, která je funkcí, říkáme „funkce z 𝐴 do 𝐵”, případně „zobrazení
z 𝐴 do 𝐵” a zapisujeme
𝑓 : 𝐴 → 𝐵
Množinu 𝐴 potom nazýváme definičním oborem a někdy značíme 𝐷 𝑓
nebo 𝑑𝑜𝑚(𝑓) (ve významu „definiční obor funkce 𝑓”), množinu 𝐵 nazýváme
oborem hodnot a značíme 𝑅 𝑓 nebo 𝑓(𝐴). Již zmíněný zápis 𝑓(𝑎) = 𝑏
můžeme číst jako „𝑏 je obraz prvku 𝑎”, případně „a je vzor prvku b”.
24
6.6 Vlastnosti funkcí 6 RELACE A FUNKCE
6.6 Vlastnosti funkcí
Také funkce mají některé speciální vlastnosti, které dále využíváme. Mezi
nejužitečnější patří:
Injektivita. Funkce 𝑓 : 𝐴 → 𝐵 je injektivní (též prostá), pokud platí
∀𝑎, 𝑏 ∈ 𝐴 ( 𝑓(𝑎) = 𝑓(𝑏) ⇒ 𝑎 = 𝑏 )
neboli žádné dva prvky nemají stejný obraz.
Surjektivita. Funkce 𝑓 : 𝐴 → 𝐵 je surjektivní (též na), pokud platí
∀𝑏 ∈ 𝐵 ( ∃𝑎 ∈ 𝐴 (𝑏 = 𝑓(𝑎) )
neboli každý prvek oboru hodnot má nějaký vzor, případně můžeme říci,
že celý obor hodnot je pokrytý.
Úplnost. Funkce 𝑓 : 𝐴 → 𝐵 je úplná, pokud platí
∀𝑎 ∈ 𝐴 ( ∃𝑏 ∈ 𝐵 (𝑏 = 𝑓(𝑎) )
neboli celý definiční obor je pokrytý. Často se můžete setkat s tím, že
pojmem funkce je myšlena úplná funkce.
Řekneme, že funkce je bijekce právě tehdy, je-li současně injektivní,
surjektivní a úplná. Bijekce se dobře používají mj. při porovnávání velikostí
množin: Existuje-li bijekce 𝑓 : 𝐴 → 𝐵, znamená to, že množiny 𝐴 a 𝐵 jsou
„stejně velké” (za okamžik tuto vágní poznámku rozvedeme formálně).
Pro bijekci 𝑓 : 𝐴 → 𝐵 můžeme dále zavést inverzní funkci 𝑓−1
: 𝐵 → 𝐴,
která je definována následovně:
𝑓−1
(𝑏) = 𝑎 ≡ 𝑓(𝑎) = 𝑏
6.7 Velikost množin
Do této doby jsme velikost množiny chápali pouze vágně, jako počet jejích
prvků. V případě nekonečných množin jsme neměli představu o velikosti
vůbec. Nyní si zadefinujeme velikost množiny 𝐴 (značeno |𝐴|) formálně:
∙ |𝐴| je definováno jako přirozené číslo 𝑛, pokud existuje bijekce 𝑓 : 𝑛 → 𝐴
(srovnejte s množinovou konstrukcí přirozených čísel)
∙ množina 𝐴 je spočetná, pokud existuje bijekce 𝑓 : N → 𝐴
25
6.8 Posloupnosti 6 RELACE A FUNKCE
∙ množina 𝐴 má mohutnost kontinua, pokud existuje bijekce 𝑓 : R →
𝐴 (kde R je množina reálných čísel)
Obecně, jak jsme již naznačili, pokud existuje bijekce z jedné množiny do
jiné, pak tyto množiny mají stejnou velikost (též říkáme mohutnost).
Množiny N, Z i Q (přirozená, celá i racionální čísla, stejně jako např.
množina všech sudých čísel nebo množina všech prvočísel) jsou všechny
spočetné. Příslušné bijekce zde uvádět nebudeme, zkuste se nad nimi zamyslet
sami. Reálná čísla jsou striktně větší než čísla přirozená a jsou nejmenší
takovou množinou (čili |N| a |R| jsou dvě nejmenší nekonečna). Důkaz je však
již nad rámec našeho předmětu.
6.8 Posloupnosti
Posledním pojmem, jímž se v kapitole o funkcích budeme zabývat, jsou
posloupnosti. Intuitivně tento pojem chápeme: jedná se o skupinu prvků, v níž
(na rozdíl od množin) záleží na pořadí. Prvky se v posloupnosti také mohou
opakovat. Již jsme zmínili, že konečné posloupnosti můžeme považovat za
uspořádané 𝑛-tice; nyní si představíme jinou definici, která dobře generalizuje
i na nekonečné posloupnosti.
Konečná posloupnost délky 𝑛 je úplná funkce, jejímž definičním oborem
je množina 𝑛 (viz množinová konstrukce přirozených čísel). Nekonečná
posloupnost je pak úplná funkce, jejímž definičním oborem je množina N.
Takovéto posloupnosti typicky zapisujeme jako 𝑎0, 𝑎1, ..., 𝑎 𝑛, ..., což považujeme
jen za jiný druh zápisu pro 𝑓(0), 𝑓(1), ..., 𝑓(𝑛), ....
V případě nekonečných posloupností často pracujeme s induktivními
definicemi. V případě posloupností tyto definice vypadají tak, že vypíšeme
první člen (případně prvních několik členů), což je analogie báze indukce, a
poté určíme předpis, podle kterého dostaneme 𝑛-tý prvek pomocí jednoho,
případně několika předchozích prvků (analogie indukčního kroku). Podle
takovéto definice jsme schopni zkonstruovat libovolný prvek posloupnosti.
Pěkným příkladem nekonečné posloupnosti je tzv. Fibonacciho posloupnost,
kde každý další člen je součtem dvou předchozích členů: 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, ... Induktivní definice Fibonacciho posloupnosti vypadá takto:
∙ 𝑎0 = 0
∙ 𝑎1 = 1
∙ 𝑎 𝑛 = 𝑎 𝑛−1 + 𝑎 𝑛−2
26
7 ZÁKLADY FORMÁLNÍ LINGVISTIKY
7 Základy formální lingvistiky
Až dosud jsme se zabývali skutečnými základy, pilíři formální matematiky.
Nyní si naopak ukážeme část aplikované matematiky, která se intenzivně
využívá i v počítačovém zpracování přirozených jazyků – na matematické
modely některých rysů jazyka neboli formální lingvistiku.
Tyto matematické modely považují jazyk za množinu slov nad nějakou
abecedou, kde prvky abecedy mohou být znaky, slova (pak můžeme za jazyk
považovat např. množinu správně utvořených vět), případně i jiné jednotky
(morfémy, ...). Modely, jimiž se budeme zabývat, byly původně navrženy pouze
k popisu přirozených jazyků; časem ale našly i jiné uplatnění (a naopak analýzu
přirozených jazyků dosud uspokojivě nevyřešily) a dnes rozlišujeme tzv.
formální jazyky, které jsou dobře analyzovány jednoduchými matematickými
modely.
Naším cílem v této části bude seznámení s nejzákladnějšími konstrukcemi
teorie formálních jazyků, neboť je velmi pravděpodobné, že se s nimi a jejich
modifikacemi při studiu ještě mnohokrát setkáte.
7.1 Základní pojmy
Nejprve zde uvedeme několik základních pojmů, které teorie formálních jazyků
používá:
Abeceda je konečná množina symbolů. Značíme ji Σ a pro jednoduchost
budeme často pracovat s abecedou {𝑎, 𝑏}.
Slovo je libovolná konečná posloupnost prvků Σ, např. 𝑎𝑎𝑏𝑎𝑏.
Délka slova je velikost této posloupnosti, např. |𝑎𝑎𝑏𝑎𝑏| = 5.
Prázdné slovo je slovo nulové délky, značíme je 𝜖.
Σ*
je množina všech slov nad abecedou Σ,
např. {𝑎, 𝑏}*
= {𝜖, 𝑎, 𝑏, 𝑎𝑎, 𝑏𝑏, 𝑎𝑏, 𝑏𝑎, 𝑎𝑎𝑏, 𝑎𝑏𝑏, ...}.
Operace zřetězení slov, značíme tečkou (.), je pro dvě slova 𝑢 a 𝑣
devinována jako 𝑢 . 𝑣 = 𝑢𝑣, např. 𝑎𝑎𝑏 . 𝑎𝑏 = 𝑎𝑎𝑏𝑎𝑏.
Mocnina slova je pro slovo 𝑢 a přirozené číslo 𝑖 značena 𝑢𝑖
a je definována
induktivně:
∙ 𝑢0
= 𝜖
∙ 𝑢𝑖+1
= 𝑢.𝑢𝑖
Např. (𝑎𝑏)3
= 𝑎𝑏𝑎𝑏𝑎𝑏.
Jazyk je množina některých slov nad danou abecedou, tedy pro každý
jazyk 𝐿 platí 𝐿 ⊆ Σ*
(ale nikoli naopak).
27
7.2 Formální gramatika 7 ZÁKLADY FORMÁLNÍ LINGVISTIKY
Dále můžeme definovat i operace nad celými jazyky analogicky k operacemi
nad slovy. Např. operaci zřetězení jazyků lze definovat následovně:
𝐿1 . 𝐿2 = {𝑢 . 𝑣 | 𝑢 ∈ 𝐿1 ∧ 𝑣 ∈ 𝐿2}
7.2 Formální gramatika
Formální gramatika je prvním z nástrojů formální lingvistiky. Můžeme si ji
představit jako přepisovací systém, jímž lze vygenerovat slova jazyka (viz
dále).
Formálně, gramatika je čtveřice (𝑁, Σ, 𝑃, 𝑆), kde
∙ 𝑁 je množina neterminálů (značíme nejčastěji velkými písmeny)
∙ Σ je množina terminálů (symbolů abecedy, pro přehlednost značíme
nejčastěji pouze malými písmeny), je disjunktní s množinou 𝑁 a 𝑁 ∪ Σ
označujeme jako 𝑉 (množina všech symbolů)
∙ 𝑃 je množina pravidel, formálně podmnožina kartézského součinu
𝑉 *
. 𝑁 . 𝑉 *
× 𝑉 *
– tj. množina dvojic, kde prvním prvkem je řetězec
obsahující alespoň jeden neterminál a druhým prvkem je libovolný
řetězec
∙ 𝑆 je počáteční symbol gramatiky
Pravidla gramatiky jako dvojice řetězců (slov nad množinou 𝑉 ) (𝛼, 𝛽)
zapisujeme nejčastěji jako 𝛼 → 𝛽. 𝛼 nazýváme levou stranou pravidla a jak
již bylo řečeno, musí obsahovat alespoň jeden neterminál. 𝛽 nazýváme pravou
stranou pravidla.
Jak jsme již naznačili, gramatika je modelem, kterým lze generovat slova
jazyka. Toto generování probíhá následovně. Začneme z počátečního symbolu
gramatiky 𝑆 a pravidla gramatiky používáme jako přepisovací systém,
to znamená, že v jednom kroku přepisu můžeme nahradit některý řetězec
terminálů a neterminálů, který je současně na levé straně nějakého pravidla,
pravou stranou tohoto pravidla. Tento postup opakujeme tak dlouho, dokud
nedostaneme řetězec terminálních symbolů (čili slovo nad Σ). Tomuto procesu
říkáme odvození slova z gramatiky.
Při přepisování máme často na výběr z více pravidel. Můžeme se rozhodnout
pro kterékoli z nich a vygenerovat tak potenciálně různá slova.
28
7.3 Chomského hierarchie jazyků7 ZÁKLADY FORMÁLNÍ LINGVISTIKY
Řekneme, že gramatika 𝐺 generuje jazyk 𝐿, pokud existuje odvození
každého slova jazyka 𝐿 z gramatiky 𝐺. Jazyk generovaný gramatikou 𝐺
značíme většinou 𝐿(𝐺).7
Příklad. Mějme gramatiku (𝑁, Σ, 𝑃, 𝑆), kde
∙ Σ = {𝑎, 𝑏}
∙ 𝑁 = {𝑆, 𝐴}
∙ 𝑃 = { 𝑆 → 𝐴, 𝐴 → 𝐴𝐴, 𝐴 → 𝑎 }
Příklady odvození z této gramatiky jsou:
∙ 𝑆 ⇒ 𝐴 ⇒ 𝑎
∙ 𝑆 ⇒ 𝐴 ⇒ 𝐴𝐴 ⇒ 𝑎𝐴 ⇒ 𝑎𝐴𝐴 ⇒ 𝑎𝑎𝐴 ⇒ 𝑎𝑎𝑎
Všimněte si, že jeden krok odvození z gramatiky (jednu aplikaci pravidla)
značíme dle konvence stejným symbolem jako implikaci. Jedná se samozřejmě
o dvě zcela různé věci a rozeznáme je od sebe jednoznačně na základě kontextu.
Zkuste vymyslet další odvození z této gramatiky. Jaký je jazyk generovaný
touto gramatikou?
7.3 Chomského hierarchie jazyků
Pokud budeme zkoumat pravidla v různých gramatikách, získáme rozlišení
gramatik na několik typů. Podle typů gramatik rozlišujeme též typy jazyků,
podle toho, který jazyk je možné generovat kterým typem gramatiky. Toto
rozlišení nazýváme Chomského hierarchie gramatik, ekvivalentně Chomského
hierarchie jazyků, podle amerického lingvisty Noama Chomského, jenž
ji poprvé představil.
Jak název naznačuje, typy gramatik tvoří hierarchii; gramatika vyššího
typu je vždy současně i gramatikou nižšího typu. Typy gramatik jsou určeny
omezeními na množinu pravidel:
Gramatika typu 0 neklade žádná omezení na množinu pravidel, libovolná
gramatika je gramatikou typu 0.
Gramatika typu 1 neboli kontextová gramatika klade na všechna
pravidla 𝛼 → 𝛽 podmínku |𝛼| ≤ |𝛽|, tedy levá strana každého pravidla musí
být kratší než jeho pravá strana. Výjimkou z tohoto omezení je pravidlo
𝑆 → 𝜖, které může být přítomno.
7
zde 𝐿 neoznačuje jazyk jako množinu, jedná se o konvenci pro zápis pojmu „jazyk
generovaný gramatikou 𝐺”
29
7.4 Konečný automat 7 ZÁKLADY FORMÁLNÍ LINGVISTIKY
Gramatika typu 2 neboli bezkontextová gramatika má všechna pravidla
ve tvaru 𝐴 → 𝛽 (tak, že 𝐴 ∈ 𝑁), tedy na levé straně je vždy právě
jeden neterminál a 𝛽 je neprázdné. Výjimkou z tohoto omezení je pravidlo
𝑆 → 𝜖, které může být přítomno.
Gramatika typu 3 neboli regulární gramatika má všechna pravidla
ve tvaru 𝐴 → 𝑎𝐵 nebo 𝐴 → 𝑎, kde 𝐴, 𝐵 jsou neterminály a 𝑎 je terminál.
Výjimkou z tohoto omezení je pravidlo 𝑆 → 𝜖, které může být přítomno.
Nejčastěji se pracuje s regulárními a bezkontextovými gramatikami a
jazyky. Tyto typy gramatik jsou efektivně zpracovatelné na počítačích a jako
základ se používají i při zpracování textů v přirozeném jazyce.
7.4 Konečný automat
Automaty jsou jiným abstraktním modelem charakterizujícím jazyky. Fungují
jako stavové systémy, které čtou po znacích slovo na vstupu, s přečtením
každého znaku změní stav a na konci rozhodnou, zda slovo je akceptováno či
nikoliv. Podobně jako říkáme, že gramatika vygeneruje slovo (resp. existuje
odvození slova z gramatiky), řekneme, že automat akceptuje slovo. Zde si
představíme nejjednodušší typ automatu, konečný automat.
Konečný automat je pětice (𝑄, Σ, 𝛿, 𝑞0 𝐹), kde
∙ 𝑄 je neprázdná konečná množina stavů automatu
∙ Σ je konečná množina vstupních symbolů (abeceda)
∙ 𝛿 : 𝑄 × Σ → 𝑄 je přechodová funkce automatu
∙ 𝑞0 je počáteční stav
∙ 𝐹 je množina koncových stavů
Běh automatu probíhá následovně. Začneme v počátečním stavu. Přečteme
první symbol na vstupu a na základě přechodové funkce se přesuneme
do dalšího stavu. Dále po jednom čteme další symboly na vstupu a podle
přechodové funkce, aktuálního stavu a symbolu na vstupu se přesouváme do
dalších stavů. Pokud se po dočtení posledního symbolu nacházíme v některém
z množiny akceptujících stavů, automat slovo akceptuje. Pokud se nacházíme
ve stavu, který do množiny 𝐹 nepatří, automat slovo neakceptuje.
Konečný automat lze názorně zakreslit tzv. přechodovým diagramem, kde
stavy znázorňujeme kroužky, přechodovou funkci šipkami mezi kroužky ohodnocenými
symboly z abecedy, koncové stavy vyznačujeme dvojitým kroužkem
30
7.5 Ekvivalence formalismů 7 ZÁKLADY FORMÁLNÍ LINGVISTIKY
a počáteční stav šipkou „z prostoru”. Takovýto diagram je dostatečnou specifikací
konečného automatu, můžeme z něj odvodit hodnoty všech prvků
pětice.
Příklad. Ukážeme si běh následujícího automatu na slově abaa:
Začínáme výpočet v počátečním stavu 𝑞0. Přečteme první symbol vstupního
slova, „𝑎”, a podle přechodové funkce znázorněné šipkou s příslušným
symbolem přejdeme z počátečního stavu do stavu 𝑞1. Dalším symbolem na
vstupu je „𝑏” a na základě přechodové funkce přejdeme ze stavu 𝑞1 do stavu
𝑞0. Dalším symbolem je „𝑎”, přejdeme tedy ze stavu 𝑞0 do stavu 𝑞1. Posledním
symbolem je opět „𝑎” a automat na základě přechodové funkce přejde ze stavu
𝑞1 do stavu 𝑞2. Jsme na konci vstupního slova a nacházíme se v akceptujícím
stavu, automat tedy toto slovo akceptuje.
Pokud automat akceptuje právě všechna slova nějakého jazyka 𝐿 (všechna
slova daného jazyka a žádná jiná), řekneme, že automat rozpoznává jazyk
𝐿. Podobně jako v případě gramatiky značíme jazyk rozpoznávaný určitým
automatem 𝐴 jako 𝐿(𝐴).
7.5 Ekvivalence formalismů
Konečný automat je ekvivalentním formalismem k regulárním gramatikám, to
znamená, že rozpoznávají stejné třídy jazyků. Jinými slovy, ke každé regulární
gramatice existuje konečný automat, který rozpoznává jazyk generovaný touto
gramatikou; a platí to i naopak, tedy ke každému konečnému automatu existuje
regulární gramatika, která generuje jazyk rozpoznávaný tímto automatem.
Důkaz tohoto faktu je konstruktivní, tj. přímo představuje převod gramatiky
na automat a naopak. Nebudeme jej zde uvádět, zkuste se ale zamyslet nad
tím, jak by tento převod mohl vypadat.
Existují i další typy automatů; některé z nich jsou ekvivalentní s jinými
typy gramatik. Pravděpodobně ještě uslyšíte např. pojmy zásobníkový automat
nebo Turingův stroj. Tyto formalismy jsou již nad rámec našeho výkladu.
Více se o nich můžete dozvědět v kurzu Formální jazyky a automaty na FI.
31
8 KOMBINATORIKA A PRAVDĚPODOBNOST
8 Kombinatorika a pravděpodobnost
V dalším výkladu se budeme zabývat statistikou a pravděpodobností. K úvahám
o pravděpodobnosti často potřebujeme vědět, kolik různých možností
v různých případech může nastat. Tímto počítáním se zabývá kombinatorika; a
kromě zmíněné motivace je rovněž jedním z klíčů k pochopení matematického
uvažování.
Ze střední školy si možná pamatujete některé vzorečky pro variace, permutace
a kombinace, s opakováním nebo bez. Tyto vzorečky si tady připomínat
nebudeme, vlastně by bylo lepší je zapomenout. Často je obtížné rozhodnout,
který vzoreček použít pro kterou situaci, navíc tyto vzorečky často
nejsou jednoduché a navádí nás spíše k jejich mechanickému používání než ke
skutečnému přemýšlení o důvodech, které k výsledkům vedou.
8.1 Základní kombinatorická pravidla
Místo vzorečků si představíme dvě jednoduchá pravidla, které je relativně
snadné „napasovat” na konkrétní případy, a konkrétní výpočty budeme řešit
spíše úvahou, která bude zase na druhou stranu komplikovanější než v případě
použití vzorečků. Dobrý způsob, jak řešit komplikovanější případy, je vyzkoušet
si, jak věci fungují v jednoduchých případech, kdy např. můžeme vypsat
všechny možnosti, a na základě těchto jednoduchých případů zobecňovat.
Prvním ze zmiňovaných pravidel je tzv. pravidlo součtu, které říká, že
pro disjunktní množiny 𝐴1, 𝐴2, ..., 𝐴 𝑛 o velikostech 𝑝1, 𝑝2, ..., 𝑝 𝑛 má množina
𝐴1 ∪ 𝐴2 ∪ ... ∪ 𝐴 𝑛 velikost 𝑝1 + 𝑝2 + ... + 𝑝 𝑛.
Druhým je pravidlo součinu říkající, že počet všech uspořádaných 𝑘-tic,
takových, že 1. člen lze vybrat 𝑛1 způsoby, druhý člen 𝑛2 způsoby, ..., k-tý
člen 𝑛 𝑘 způsoby, je 𝑛1 * 𝑛2 * ... * 𝑛 𝑘.
Tato téměř triviální pravidla jsou vše, co potřebujeme ke kombinatorickým
úvahám. Ukážeme si jedno použití na příkladě.
Příklad. Kolika způsoby lze seřadit množinu {1, 2, ..., n}? První prvek
vybíráme z 𝑛 prvků, druhý z 𝑛 − 1 prvků atd. Podle pravidla součinu je počet
všech seřazení 𝑛 * (𝑛 − 1) * (𝑛 − 2) * ... = 𝑛!.
8.2 Pravděpodobnost
Pravděpodobnost nějakého jevu je definována jako podíl 𝑚/𝑛, kde 𝑚 je
počet možností, kdy daný jev nastal, a 𝑛 je počet všech možností, které
potenciálně nastat mohly či mohou. Tato čísla někdy vyvozujeme na základě
kombinatorických úvah a jistých předpokladů (např. předpokládáme, že kostka,
32
8.2 Pravděpodobnost 8 KOMBINATORIKA A PRAVDĚPODOBNOST
kterou hážeme, je vyvážená), často je však také odvozujeme na základě
statistických dat, jak brzy poznáme v dalším výkladu.
33
9 ZÁKLADY TEORIE GRAFŮ
9 Základy teorie grafů
Ještě než se však začneme podrobněji zabývat statistikou, ukážeme si ještě
něco z jiného důležitého podoboru diskrétní matematiky, a tím je teorie grafů.
Jak brzy poznáme, nejedná se zde o grafy funkcí, i když s nimi lze také
pracovat v podobě obrázků. Můžeme si je představit jako skupiny bodů (které
budeme nazývat vrcholy nebo uzly, v praxi představují např. města nebo
počítače v síti) propojené cestami (které budeme nazývat hrany, v praxi např.
silnice nebo síťová spojení).
V praxi představují grafy užitečnou teoretickou základnu pro velké množství
aplikací – s jejich pomocí jsou modelovány např. mapy (vč. vyhledání
nejrychlejších cest), počítačové či elektrické sítě, v lingvistické oblasti je pak
využíváme k modelování syntaxe (syntaktické stromy) či sémantiky (sémantické
sítě).
9.1 Základní pojmy
Graf 𝐺 je definován jako uspořádaná dvojice (𝑉, 𝐸), kde 𝑉 je množina vrcholů
grafu (někdy značíme i (𝐺(𝑉 ))) a 𝐸, značená někdy též 𝐺(𝐸), je množina
hran. Každá hrana je dvouprvkovou podmnožinou množiny vrcholů (tedy
množina 𝐸 se skládá z dvouprvkových množin) a její sémantiku si můžeme
představit tak, že hrana „spojuje” vrcholy, které jsou v ní obsaženy.
Příkladem grafu může být dvojice (𝑉, 𝐸), kde
𝑉 = {1, 2, 3, 4, 5, 6}
𝐻 = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}
Takový graf bychom pak zakreslili např. takto:
Nyní si zavedeme několik základních pojmů nad grafy, které nám pak
usnadní formulaci dalších definic a faktů.
34
9.2 Typy grafů 9 ZÁKLADY TEORIE GRAFŮ
Sousední vrcholy. Řekneme, že dva vrcholy jsou sousední, pokud mezi
nimi vede hrana (jinými slovy, 𝑢, 𝑣 ∈ 𝑉 jsou sousední, pokud {𝑢, 𝑣} ∈ 𝐸).
Stupeň vrcholu je počet hran, které z daného vrcholu vychází (neboli
stupeň vrcholu 𝑥 je |{{𝑢, 𝑣} ∈ 𝐸 | 𝑢 = 𝑥 ∧ 𝑣 = 𝑥}|).
Podgraf grafu 𝐺 = (𝑉, 𝐸) je graf 𝐺′
= (𝑉 ′
, 𝐸′
) takový, že 𝑉 ′
⊆ 𝑉 a
𝐸′
⊆ 𝐸. Je důležité, aby i 𝐺′
byl graf, tedy aby platilo ∀{𝑢, 𝑣} ∈ 𝐸′
(𝑢 ∈
𝑉 ′
∧ 𝑣 ∈ 𝑉 ′
). Jinými slovy, podgraf tvoří vybrané vrcholy a hrany původního
grafu.
Izomorfismus mezi grafy 𝐺 a 𝐺′
je bijekce 𝑓 : 𝑉 (𝐺) → 𝑉 (𝐺′
), kde platí
∀{𝑢, 𝑣} ∈ 𝐺(𝐸) ({𝑓(𝑢), 𝑓(𝑣)} ∈ 𝐺(𝐸′
)). Izomorfismus je způsob, jak říct, že
grafy jsou shodné, až na pojmenování vrcholů, čili dokážeme přejmenovat
vrcholy tak, abychom z jednoho grafu dostali druhý. Řekneme, že grafy
jsou izomorfní (shodné), pokud mezi nimi existuje izomorfismus (tedy jsme
schopni nalézt bijekci 𝑓, která splňuje kritérium izomorfismu).
Příklad. Které z následujících grafů jsou izomorfní?
9.2 Typy grafů
Rozeznáváme několik základních typů grafů:
∙ Kružnice nebo cyklus délky 𝑛 je graf (případně libovolný s ním izomorfní)
(𝑉 = {1, 2, ..., 𝑛}, 𝐸 = {{1, 2}, {2, 3}, ..., {𝑛 − 1, 𝑛}, {𝑛, 1}}).
Má stejný počet vrcholů a hran, všechny vrcholy jsou stupně 2 a nákres
grafu tvoří kružnici.
∙ Cesta délky 𝑛 je kružnice s jednou chybějící hranou, tedy
(𝑉 = {1, 2, ..., 𝑛}, 𝐸 = {{1, 2}, {2, 3}, ..., {𝑛 − 1, 𝑛}}).
∙ Úplný graf je takový, kde mezi každými dvěma vrcholy vede hrana,
tedy (𝑉 = {1, 2, ..., 𝑛}, 𝐸 = {{𝑢, 𝑣} | 𝑢 ∈ 𝑉 ∧ 𝑣 ∈ 𝑉 ∧ 𝑢 ̸= 𝑣}).
Na základě těchto typů rozeznáváme též specifické podgrafy. Cyklus v grafu
je jeho podgraf, který je kružnicí; cesta v grafu je podgraf, který je cestou;
klika v grafu je podgraf, který je úplným grafem.
Mezi další typy grafů patří:
35
9.3 Rozšíření pojmu graf 9 ZÁKLADY TEORIE GRAFŮ
∙ Souvislý graf je takový graf ve kterém existuje cesta mezi každými
dvěma vrcholy. (Opakem je graf nesouvislý)
∙ Acyklický graf je takový, který neobsahuje cyklus. Někdy ho nazýváme
též les, protože jeho souvislé části jsou stromy.
∙ Strom je acyklický souvislý graf. (Dochází zde k menšímu paradoxu,
neboť lze říct, že souvislý les je strom :-) )
9.3 Rozšíření pojmu graf
Ve většině aplikací není jednoduchý graf, jak jsme si ho představili, dostatečným
modelem, vznikly proto mnohé matematické objekty, které základní
pojem grafu rozšiřují. Některé z nich si zde představíme.
∙ Orientovaný graf. V takovémto grafu jsou hrany orientovány. U každé
hrany tedy rozeznáváme zdrojový a cílový vrchol; tato vlastnost nám
např. umožňuje modelovat jednosměrné ulice v mapě. Formální definici
musíme změnit tak, že množina hran již nebude množinou (neuspořádaných)
dvouprvkových podmnožin, ale uspořádaných dvojic, kde je
jednoznačně dán první (zdrojový vrchol) a druhý (cílový vrchol) prvek.
∙ Ohodnocený graf. Takovýto graf přiřazuje každé hraně reálné číslo,
které nazýváme ohodnocení. Tato vlastnost nám umožní modelovat např.
různé vzdálenosti mezi místy v mapě nebo různé kapacity síťových
kanálů. Formálně k definici grafu přidáme ohodnocovací funkci 𝑒 :
𝐸(𝐺) → R.
∙ Multigraf povoluje více hran mezi stejnou dvojicí vrcholů, čímž umožňuje
např. modelovat více různých cest mezi dvěma městy, servery
apod. Rovněž tento formalismus povoluje hrany začínající i končící ve
stejném vrcholu, tzv. „smyčky”. Možnosti formální reprezentace takovéto
struktury jsou různé, např. ke každé hraně (dvouprvkové množině)
můžeme přidat třetí prvek, index, který odliší dvě hrany mezi stejnou
dvojicí vrcholů. Přidaný prvek pak nesmí být obsažen v množině vrcholů
(Proč?).
Všechna výše uvedená rozšíření se mohou vzájemně kombinovat, můžeme
(a často se s tím i setkáváme) mít např. orientovaný ohodnocený graf, který
lze znázornit jako následující obrázek:
36
9.4 Graf jako relace 9 ZÁKLADY TEORIE GRAFŮ
nebo např. orientovaný ohodnocený multigraf, který je základem pro
přechodový graf konečného automatu, s nímž jsme se již setkali (zde navíc
máme ještě různé typy vrcholů).
9.4 Graf jako relace
To, že množina hran v orientovaném grafu je množina uspořádaných dvojic,
nám může napovědět, že na graf můžeme pohlížet (a můžeme ho tak i
formálně reprezentovat) jako na binární relaci na množině vrcholů. Tím
pádem ho např. můžeme reprezentovat jako tabulku příslušné relace, tzv.
matici sousednosti.
Neorientovaný graf lze v tomto formátu zapsat jako symetrickou relaci
(ve významu, že mezi každou dvojicí vrcholů vede hrana tam i zpět, což
lze považovat za totéž, jako bychom orientaci hran neuvažovali), matice
sousednosti by tedy v tomto případě byla symetrická.
Následující tabulka je příkladem matice sousednosti pro graf ze začátku
této kapitoly.
vrchol 1 2 3 4 5 6
1 0 1 0 0 1 0
2 1 0 1 0 1 0
3 0 1 0 1 0 0
4 0 0 1 0 1 1
5 1 1 0 1 0 0
6 0 0 0 1 0 0
37
9.5 Další pojmy z teorie grafů 9 ZÁKLADY TEORIE GRAFŮ
9.5 Další pojmy z teorie grafů
Dále si představíme několik dalších pojmů z teorie grafů, které pravděpodobně
ještě někdy uslyšíte.
Souvislé komponenty v grafu jsou jeho největší souvislé podgrafy – na
obrázku je poznáme snadno, jde o souvislé „ostrůvky” které vzájemně nejsou
spojeny žádnou hranou. Jinými slovy lze také říct, že se jedná o největší
podgrafy takové že mezi každými dvěma vrcholy každého takového podgrafu
vede cesta.
V případě orientovaných grafů mluvíme o tzv. silně souvislých komponentách,
kde požadujeme, aby v každé komponentě (podgrafu) vedla cesta
mezi každými dvěma vrcholy tam i zpět (z každého vrcholu se „po šipkách”
dostaneme do každého jiného). Analogicky můžeme mluvit o slabě souvislých
komponentách, kde požadujeme, aby existovala cesta alespoň jedním směrem.
Jako cvičení si můžete zkusit najít silně a slabě souvislé komponenty v grafu
ze sekce 9.3
Délkou cesty v grafu rozumíme počet hran v této cestě. V případě
ohodnoceného grafu délkou cesty obvykle rozumíme součet ohodnocení hran
této cesty. Délku nejkratší cesty mezi dvěma vrcholy pak označujeme jako
vzdálenost mezi vrcholy.
V případě stromů často z praktických důvodů rozeznáváme více typů
vrcholů. Obvykle strom obsahuje jeden význačný vrchol, ve kterém „začíná”
– tomuto vrcholu říkáme kořen. Volba kořene je obvykle dána aplikací, tj.
není možné určit kořen u obecného stromu – nejedná se o vlastnost grafu, ale
o volbu danou konvencemi. Pokud informatici kreslí strom, kreslí jeho kořen
většinou nahoře.
Dále, všechny vrcholy stupně 1, které nejsou kořenem, obvykle nazýváme
listy stromu. Listy naopak kreslíme většinou dole.
Příkladem lingvistického využití teorie grafů je syntaktický strom, kterým
znázorňujeme syntaktické odvození věty (se syntaktickými stromy se
také jistě ještě setkáte). Příkladem je strom na následujícím obrázku – zde je
kořenem vrchol <sentence>, listy jsou pak slova dané věty.
38
9.6 Grafové algoritmy 9 ZÁKLADY TEORIE GRAFŮ
I saw
a man with
a telescope
.
<sentence>
<clause>
<NP> <PP>
<NP>
<NP> <VP>
<DET> <NP> <PP>
<DET> <NP>
<ends>
Kostra grafu je podgraf, který obsahuje všechny vrcholy původního grafu
a zároveň je stromem. K tomu, abychom z grafu dostali jeho kostru, musíme
tedy odstranit všechny cykly v tomto grafu, neboli odebrat hranu z každého
jeho cyklu.
Pro ohodnocený graf dále můžeme mluvit o minimální, resp. maximální
kostře, což je taková kostra, která má minimální, resp. maximální
možný součet ohodnocení hran, které jsou v ní obsaženy. Pojem maximální
kostry má opodstatnění např. při hledání páteřních rozvodů v sítích nebo při
hledání nejpravděpodobnější syntaktické analýzy v závislostním formalismu.
9.6 Grafové algoritmy
Protože grafy jsou v drtivé většině určeny ke zpracování počítači a protože
počítače nevidí graf jako obrázek, ale mají k dispozici pouze jeho číselnou
reprezentaci s pomocí množin, polí, případně reprezentaci maticí sousednosti,
uvedeme si zde několik příkladů ilustrujících způsob, jakým počítače s grafy
pracují.
Nejjednoduššími z grafových algoritmů jsou algoritmy procházení (též
prohledávání) grafu – slouží obvykle jako prostředek k navštívení všech vrcholů
a k provedení nějaké akce nad každým z nich. My zde budeme pro ilustraci
používat akci „označ”.
Rozeznáváme dva základní způsoby procházení grafu – do hloubky a do
šířky. Liší se zejména v pořadí, v jakém navštěvujeme jednotlivé vrcholy.
Vždy začínáme z jednoho určeného vrcholu a po hranách vedoucích z tohoto
vrcholu postupujeme dále v grafu.
Procházení do hloubky (depth-first search) z určeného vrcholu probíhá
tak, že označíme tento vrchol, poté se přesuneme na libovolný sousední
neoznačený vrchol a provedeme znovu celý algoritmus s novým počátečním
vrcholem (tedy opět jej označíme a přesuneme se dále na libovolný sousední
39
9.6 Grafové algoritmy 9 ZÁKLADY TEORIE GRAFŮ
neoznačený vrchol). Pokud neexistuje žádný sousední neoznačený vrchol, vracíme
se postupně na vrcholy, které jsme již navštívili, v opačném pořadí a
zkoušíme, zda můžeme pokračovat dále z těchto vrcholů.
Následuje formálnější zápis (tzv. pseudokód) nastíněného algoritmu. Vidíme,
že algoritmus je rekurzivní, tedy volá sebe sama.
DFS (G, u)
============
označ
u for všechny hrany (u, v) vycházející z vrcholu u:
if v není označen:
DFS (G, v)
Pořadí, v jakém jsou jednotlivé vrcholy grafu navštíveny, pak ilustruje
následující obrázek (začínáme ve vrcholu 1 a pro přehlednost v případě více
hran vedoucích z daného vrcholu jdeme vždy napřed doleva).
Procházení do šířky (breadth-first search) z určeného vrcholu začíná
opět označením tohoto vrcholu. Poté všechny neoznačené sousední vrcholy
přidáme do seznamu (tzv. fronty). Dokud seznam není prázdný, vybereme
vždy první vrchol seznamu, smažeme jej ze seznamu, označíme jej a všechny
neoznačené sousední vrcholy přidáme na konec seznamu. Procházení končí,
když je seznam prázdný.
Pseudokód procházení do šířky:
BFS (G, u)
============
Q = [u]
while Q je neprázdný:
odstraň první prvek z Q a přiřaď jej do t
označ t
přidej všechny neoznačené sousedy t na konec Q
40
9.6 Grafové algoritmy 9 ZÁKLADY TEORIE GRAFŮ
A ilustrace pořadí navštívených vrcholů (srovnejte s pořadím při procházení
do hloubky):
Dalším algoritmem, který stojí za zmínku, je Kruskalův algoritmus pro
hledání minimální kostry. Vstupem algoritmu je ohodnocený graf, výstupem
je jeho minimální kostra. Algoritmus nejprve setřídí všechny hrany vzestupně
podle ohodnocení, poté je postupně podle tohoto pořadí zkouší přidat do
výsledného grafu a v každém kroku kontroluje, zda nevznikl cyklus. To, že
nevznikne cyklus, algoritmus zajistí tím, že si stále pamatuje a v každém
kroku aktualizuje seznam souvislých komponent výsledného grafu a testuje,
zda nově přidávaná hrana spojuje dvě různé souvislé komponenty (v opačném
případě by vznikl cyklus a hrana nebude přidána).
Pseudokód Kruskalova algoritmu:
přiřaď K = []; přiřaď comp = {}
for u in G(V):
přiřaď comp[u] = set(u)
setřiď G(E) podle ohodnocovací funkce
for (u, v) in G(E):
if comp[u] != comp[v]:
K.append((u,v))
newset = union(comp[u], comp[v])
for x in newset:
přiřaď comp[x] = newset
(G(V), K) je minimální kostra grafu
Na internetu lze nalézt spoustu názorných animací Kruskalova algoritmu,
pro lepší pochopení doporučujeme některé vyhledat, shlédnout a porovnat
s pseudokódem algoritmu. Nejlepší způsob procvičení je zkusit si algoritmus
napsat a spustit.
Posledním algoritmem, kterým se budeme zabývat, je Dijkstrův algoritmus
pro nalezení nejkratší cesty mezi zadanou dvojicí vrcholů – fakticky
41
9.6 Grafové algoritmy 9 ZÁKLADY TEORIE GRAFŮ
algoritmus ovšem počítá všechny vzdálenosti z počátečního vrcholu do všech
ostatních vrcholů grafu (a je zajímavým faktem, že nikdo dosud nepřišel na
žádný způsob, jak to udělat bez toho, tj. vždy musíme spočítat vzdálenosti
mezi počátečním vrcholem a všemi zbývajícími vrcholy v grafu). Tento algoritmus,
resp. jeho modifikace, používají např. služby na vyhledávání nejkratších
či nejrychlejších cest, jako např. portál mapy.cz.
Vstupem algoritmu je graf ohodnocený nezápornými čísly a počáteční
vrchol 𝑠, výstupem je pole vzdáleností z vrcholu 𝑠 do všech dalších vrcholů
grafu. Algoritmus si po celou dobu běhu udržuje aktuální nejmenší známé
vzdálenosti do všech vrcholů (na začátku všechny tyto vzdálenosti nastaví na
nekonečno), postupně prochází hrany, hledá kratší cesty a hodnoty aktualizuje.
Pseudokód Dijkstrova algoritmu:
for u in G(V):
přiřaď d[u] = infinity
přiřaď d[s] = 0
přiřaď N = G(V)
přiřaď p = {}
while N != []:
přiřaď u = vrchol z N s nejmenší hodnotou d[u]
for všechny hrany (u,x) vycházející z vrcholu u:
přiřaď alt = d[u] + w((u,x))
# kde w je ohodnocovací funkce
if alt < d(x):
přiřaď d[x] = alt
přiřaď p[x] = u
odstraň vrchol u z množiny N
d jsou vzdálenosti vrcholů z vrcholu s
p obsahuje předchozí vrcholy na nejkratší cestě z vrcholu s
42
10 ZÁKLADY POPISNÉ STATISTIKY
10 Základy popisné statistiky
Počínaje touto kapitolou se dostáváme na půdu statistiky, matematického
odvětví, které se zabývá převážně zpracováním velkých datových souborů,
a to zejména sumarizací obsažených informací, odhady informací o velkých
souborech dat na základě menšího vzorku, vytvářením statistických modelů
objektů (např. jazyka) na základě dostupných dat.
Při počítačovém zpracování přirozeného jazyka se používá velké množství
metod založených na statistice, přičemž se často jedná o nejlepší výsledky,
které byly v dané oblasti dosaženy. Proto je žádoucí, abyste se i vy zevrubně
seznámili se základními pojmy popisné statistiky. Využijete je nejen v navazujících
předmětech či při projektech z počítačového zpracování jazyka, ale i
v běžném životě, neboť se statistickými údaji se setkáváme téměř každý den.
10.1 Statistický soubor
Objektem zkoumání matematické statistiky je statistický soubor, což chápeme
jako posloupnost údajů (většinou číselných nebo výjádřených číselně)
o nějakých objektech. Typy těchto údajů nazýváme statistické znaky a
jejich počet pak určuje rozměr statistického souboru.
Příkladem statistického souboru může být množina údajů o výšce a hmotnosti
slonů v Africe – v tomto případě výška a hmotnost jsou statistické znaky
a rozměr souboru je 2.
Dále rozlišujeme tzv. základní soubor (též populace), který uvažuje
všechny objekty daného typu, v našem příkladě by se jednalo o množinu
všech slonů v Africe. O tomto souboru většinou chceme shromažďovat údaje
a vyvozovat fakta.
Protože však většinou nejsme schopni změřit a zvážit všechny slony v Africe,
obvykle pracujeme jen s omezeným výběrem objektů ze základního
souboru – v našem příkladě by se jednalo např. o množinu slonů, které
se podařilo změřit a zvážit. Teprve tomuto výběru pak říkáme statistický
soubor.
Aby vybraný vzorek správně vypovídal o základním souboru, výběr by
měl být reprezentativní. Pro nedostatek informací o základním souboru
(cílem statistického zkoumání je obvykle právě tyto informace získat) se však
většinou spoléháme na náhodný výběr a na to, že náhoda nám zaručí
reprezentativnost vzorku. Je však třeba dávat pozor na to, jaké vlivy mohou
náhodnost našeho výběru ohrozit a tím způsobem zkreslit výsledky zkoumání.
Například jsme mohli měřit a vážit pouze příliš tlusté slony, protože pomaleji
běhají a lépe se chytají.
43
10.2 Jednorozměrný soubor 10 ZÁKLADY POPISNÉ STATISTIKY
10.2 Jednorozměrný statistický soubor
Často pracujeme se statistickým souborem omezeným pouze na jeden statistický
znak (např. soubor informací o hmotnosti slonů). Pro lepší ilustraci
uvažujme následující příklad: Podařilo se nám zvážit šest slonů, ti měli hmotnosti
postupně 2, 4, 4, 4, 5 a 11 tun. Statistický soubor pak bude šestice
(2, 4, 4, 4, 5, 11).
Rozsah statistického souboru je počet jeho prvků, tedy rozsah našeho
souboru je 6.
Absolutní četnost hodnoty (někdy též pouze četnost) v souboru je
počet jejích výskytů, např. četnost hodnoty 4 v našem souboru je 3. Dále
rozeznáváme relativní četnost, což je absolutní četnost podělená rozsahem
souboru a udává se obvykle v procentech. Tedy relativní četnost hodnoty 4 je
50 %.
Kumulativní četnost hodnoty je četnost hodnoty souboru plus četnost
všech menších hodnot. Rozeznáváme opět absolutní a relativní kumulativní
četnost. Kumulativní absolutní četnost hodnoty 4 je 4, kumulativní relativní
četnost hodnoty 4 je 66 %.
Často je možných hodnot příliš mnoho (např. při vážení na kilogramy
nedostaneme třikrát přesně 4000 kg, ale budeme mít tři různé hodnoty, všechny
s četností 1), a proto se může hodit rozdělit tyto hodnoty do nějakých tříd,
které již budou obsahovat větší počet prvků. Např. můžeme rozeznávat třídu
„3500 - 4500 kg”, což je v podstatě ekvivalentní zaokrouhlení hodnot na celé
tuny. Rozdělení hodnot do tříd budeme často dělat implicitně, i v následujícím
textu – pokud budeme psát „3 lidé s výškou 170 centimetrů”, bude to nejspíše
znamenat, že uvažujeme přesnost na celé desítky nebo analogicky že uvažujeme
třídu lidí od 165 do 175 centimetrů, která má četnost 3.
Četnosti můžeme zaznamenat do sloupcového grafu – graf funkce, který
má na ose x jména tříd a na ose y jejich absolutní nebo relativní četnosti, se
nazývá histogram.
10.2.1 Charakteristiky polohy
Pro jednorozměrný statistický soubor zavádíme tzv. charakteristiky polohy a
charakteristiky variability. S většinou z nich jste se jistě už setkali. Charakteristiky
polohy nám shrnují potenciálně velké množství dat do několika málo
čísel, které lze snadno interpretovat a vytvořit si tak hrubý úsudek o celém
vzorku dat (např. jak vysoký je běžný slon). Charakteristiky variability nám
ukazují, jak je statistický soubor vnitřně konzistentní, čili jak moc se od sebe
vzájemně liší hodnoty obsažené v souboru.
Mezi důležité charakteristiky polohy patří:
44
10.3 Dvourozměrný soubor 10 ZÁKLADY POPISNÉ STATISTIKY
∙ Modus, což je hodnota či třída s největší četností (v našem ukázkovém
souboru je modus 4).
∙ Aritmetický průměr (někdy též značený avg jako „average”) je součet
hodnot ve statistickém souboru, podělený velikostí souboru. Pokud
bychom uvažovali sloupce v histogramu jako závaží, pak průměr je
těžištěm histogramu. Pro náš soubor je průměr 5.
∙ Medián je „prostřední” hodnota v souboru po jeho setřídění. V případě,
že datový soubor má sudý počet prvků, je to průměr ze dvou
prostředních, pro náš ukázkový soubor je medián 4. Medián není citlivý
na extrémní odchylky jako průměr – např. relativně málo hodně vysokých
hodnot může průměr vychýlit i hodně nahoru, zatímco u mediánu
se neprojeví vůbec. (Zamyslete se, proč se zveřejňuje celorepublikový
průměr platů a ne celorepublikový medián platů.)
10.2.2 Charakteristiky variability
Hlavní charakteristikou variability statistického souboru je rozptyl (též
disperze nebo variance) značený 𝑠2
. Je definován jako
1
𝑛
𝑛∑︁
𝑖=1
(𝑥𝑖 − 𝑎𝑣𝑔)2
= ((𝑥1 − 𝑎𝑣𝑔)2
+ (𝑥2 − 𝑎𝑣𝑔)2
+ ... + (𝑥 𝑛 − 𝑎𝑣𝑔)2
)/𝑛
Jedná se tedy o aritmetický průměr druhých mocnin odchylek jednotlivých
hodnot od průměru. Pokud je rozptyl 0, všechny hodnoty v souboru jsou
stejné. Čím větší je rozptyl, tím více se jednotlivé hodnoty od sebe liší.
Odvozenou charakteristikou variability je směrodatná odchylka 𝑠, která
je pouze odmocninou z rozptylu a vyjadřuje téměř totéž, jen jiným číslem.
10.3 Dvourozměrný statistický soubor
Dvourozměrný statistický soubor (např. data o výšce a hmotnosti slonů) lze
chápat jako dva jednorozměrné soubory, vzájemně provázané. Formálně jej
můžeme reprezentovat jako posloupnost uspořádaných dvojic, např.
((𝑥1, 𝑦1), (𝑥2, 𝑦2), ..., (𝑥 𝑛, 𝑦 𝑛))
Důležitou vlastností dvourozměrného statistického souboru je korelace
statistických znaků. Pojmem korelace rozumíme stupeň lineární závislosti
znaků 𝑥 a 𝑦, tedy to, do jaké míry hodnoty znaku 𝑥 lineárně závisí na
hodnotách znaku 𝑦. Jinými slovy, to, jak dobře lze grafem závislosti 𝑥 na 𝑦
proložit přímku. Vzorec pro výpočet korelace je
45
10.3 Dvourozměrný soubor 10 ZÁKLADY POPISNÉ STATISTIKY
𝑛∑︀
𝑖=1
(𝑥𝑖 − 𝑎𝑣𝑔(𝑥))(𝑦𝑖 − 𝑎𝑣𝑔(𝑦))
𝑛 * 𝑠(𝑥) * 𝑠(𝑦)
kde 𝑠(𝑥), 𝑠(𝑦) jsou směrodatné odchylky jednorozměrných datových souborů
pro znaky 𝑥 a 𝑦.
Hodnoty korelace se pohybují od -1 do 1. Pokud je korelace 0, jsou hodnoty
znaků dokonale nezávislé; pokud je korelace 1, jedná se o přímou úměrnost
(čím větší je 𝑥, tím větší je 𝑦 a hodnoty 𝑦 lze z hodnot 𝑥 získat jednoduše
vynásobením nějakou kladnou konstantou); pokud je korelace -1, jedná se
o nepřímou úměrnost (čím větší je 𝑥, tím menší je 𝑦 a hodnoty 𝑦 lze z hodnot
𝑥 získat jednoduše vynásobením nějakou zápornou konstantou).
Pro lepší představu uvádíme ukázky grafů závislosti dvou statistických
jevů pro různé hodnoty korelace:
korelace 0
46
10.3 Dvourozměrný soubor 10 ZÁKLADY POPISNÉ STATISTIKY
korelace 0.5
korelace 0.9
korelace -0.7
47
11 STATISTIKA A PRAVDĚPODOBNOST
11 Statistika a pravděpodobnost
V kapitole 8 jsme si představili základní pojem pravděpodobnosti, v minulé
kapitole jsme si představili základní pojmy popisné statistiky. V této kapitole
si vysvětlíme, jak spolu pravděpodobnost a statistika souvisí. K tomu ale
potřebujeme zavést několik dalších pojmů z teorie pravděpodobnosti.
11.1 Pravděpodobnostní rozložení
Náhodná proměnná, např. 𝐴 je vlastnost, jejíž hodnotu z nějakého důvodu
neznáme, např. protože o ní nemáme dost informací nebo protože vlastnost
dosud žádné hodnoty nenabyla. Příkladem náhodné proměnné může být
výsledek hodu kostkou, která je ukrytá pod kelímkem nebo třeba teplota
vzduchu v Brně zítra v poledne. (Kdybychom měli dostatek informací a
dokázali přesně modelovat počasí nebo hod kostkou, byli bychom možná
schopni hodnoty příslušné vlastnosti vypočítat, toho však schopni nejsme, a
proto zavádíme pojem náhodné veličiny.)
Většinou ale máme nějaké informace o dané vlastnosti, které nám mohou
např. vyloučit nebo téměř vyloučit některé hodnoty. Např. víme, že na kostce
nejspíš nepadne osmička, že zítřejší teplota patrně nebude větší než 50 stupňů
apod. Minulá pozorování nám mohou napovědět ještě více. Např. pokud jsme
už viděli deset hodů toutéž kostkou a z toho devětkrát padla šestka, s kostkou
patrně nebude něco v pořádku a pokud bychom si měli vsadit na výsledek
dalšího hodu, nejspíše bychom volili opět šestku – řekli bychom, že možnost,
že padne šestka, je „pravděpodobnější” než možnost, že padne jednička, i
když jistotu nemáme. Podobně ze zkušenosti víme, že pokud je zrovna červen,
polední teplota v Brně se bude pohybovat nejspíše mezi 20 a 40 stupni a
pravděpodobnost, že bude stupňů méně nebo více, je „menší”.
Intuitivně tedy cítíme, že pravděpodobnosti jednotlivých možných hodnot
náhodné veličiny nemusí být stejné. Jak můžeme toto vágní pozorování
formalizovat, zpřesnit a využít např. pro přesnější předpovědi?
Pravděpodobnostní rozdělení, pravděpodobnostní rozložení nebo
pravděpodobnostní distribuce jevu či vlastnosti 𝐴, anglicky probability
distribution, je funkce, která pro jednotlivé možné hodnoty vrací pravděpodobnost,
s jakou vlastnost 𝐴 nabude této hodnoty. Formálně se jedná
o funkci
𝑝 : 𝑋 → [0, 1]
kde 𝑋 je množina možných hodnot příslušné vlastnosti a [0, 1] je uzavřený
interval od nuly do jedné, čili
48
11.2 Určení rozložení 11 STATISTIKA A PRAVDĚPODOBNOST
∀𝑥 ∈ 𝑋(𝑝(𝑥) ≤ 1 ∧ 𝑝(𝑥) ≥ 0)
Dále musí platit, že součet hodnot funkce pro všechny možné hodnoty je
1, tedy
∑︁
𝑥∈𝑋
𝑝(𝑥) = 1
Rovněž si uveďme formálně, jaká je sémantika pravděpodobnostního
rozložení:
𝑝(𝑥) = 𝑃(𝐴 = 𝑥)
Tedy hodnota pravděpodobnostního rozložení (malé 𝑝) je rovna pravděpodobnosti
(velké 𝑃, tedy obecná pravděpodobnost), s jakou vlastnost 𝐴 nabude
hodnoty 𝑥. Dvojice (𝑋, 𝑝), tedy množina všech možných hodnot vlastnosti
spolu s pravděpodobnostním rozložením, se nazývá pravděpodobnostní
prostor.
Fukncí, které splňují podmínky pravděpodobnostního rozložení, je samozřejmě
celá řada. Dají se rozlišit na diskrétní (množina možných hodnot dané
vlastnosti je konečná nebo spočetná) a spojité (množina možných hodnot je
nespočetná) – my se budeme zabývat výhradně diskrétními pravděpodobnostními
rozloženími.
Z čeho ale odvodíme vhodné pravděpodobnostní rozložení, které bude
dobře charakterizovat naši náhodnou veličinu a bude prakticky použitelné?
11.2 Určení pravděpodobnostního rozložení
Možnosti jsou v zásadě dvě. První z nich je použití nějaké „ideální” funkce,
které vychází z našich předpokladů o dané vlastnosti. Např. předpokládáme, že
kostka, kterou se háže, je férová; hodnoty 1 až 6 tedy musí mít všechny stejnou
pravděpodobnost, ostatní hodnoty budou mít pravděpodobnost 0. Z omezení
kladená na pravděpodobnostní rozložení pak dostaneme, že pravděpodobnost
pro hodnoty 1 až 6 bude 1/6. Nebo předpokládáme, že rozložení výšky lidí
odpovídá nějakému ideálnímu normálnímu (viz dále) pravděpodobnostnímu
rozložení s určitým průměrem a rozptylem, a rozhodneme se aproximovat
výšku lidí tímto pravděpodobnostním rozložením.
Druhou možností je pravděpodobnostní rozložení určovat na základě měření
provedeného v minulosti, které bylo zachyceno ve statistickém souboru.
Tímto způsobem určujeme pravděpodobnost neznámých dat na základě jiných
dat stejného typu, která jsme viděli a zaznamenali, např. určíme pravděpodobnostní
rozložení teploty zítra v poledne na základě záznamů o měření teploty
49
11.3 Typy rozložení 11 STATISTIKA A PRAVDĚPODOBNOST
v minulých dnech a letech nebo můžeme určit pravděpodobnostní rozložení
slov (dvojic slov, slovních druhů apod.) v jazyce na základě dostatečně velkého
vzorku textů v daném jazyce.
Možnosti určení pravděpodobnostního rozložení na základě statistického
souboru jsou různé a obecně platí, že různé metody se hodí pro různé aplikace.
Základní metodou nicméně je odvozování pravděpodobnostního rozložení na
základě četností pozorovaných ve statistickém souboru. Jinými slovy, relativní
četnosti ve statistickém souboru odpovídají hodnotám pravděpodobnostního
rozložení v pravděpodobnostním prostoru.
11.3 Typy pravděpodobnostních rozložení
Na základě tvaru grafu rozlišujeme několik základních typů pravděpodobnostních
rozložení. Představíme si zde tři nejdůležitější.
Uniformní rozložení je takové, v němž všechny hodnoty mají přibližně
stejnou pravděpodobnost. Grafem jsou tedy body uspořádané přibližně do
přímky vodorovné s osou 𝑥. Příkladem může být pravděpodobnostní rozložení
výsledků hodu vyváženou kostkou.
Normální rozložení se vyznačuje tím, že nejpravděpodobnější hodnoty
jsou blízké průměru a s větší odchylkou od průměru pravděpodobnost klesá.
Graf takového rozložení má tvar zvonu, např.:
„Normální” se jmenuje proto, že dobře vystihuje velké množství vlastností
různých přírodních populací – např. rozložení výšek a hmotností zvířat či lidí.
Zipfovo rozložení je typické tím, že několik málo nejčastějších hodnot
má velkou pravděpodobnost a s každou další hodnotou (při setřídění od
nejčastější) tato pravděpodobnost prudce klesá – v ideálním Zipfově rozložení
má nejčastější hodnota pravděpodobnost 𝑥, druhá 𝑥/2, třetí 𝑥/3 atd. Graf
takového rozložení nejčastěji kreslíme tak, že hodnoty na ose x jsou uspořádány
podle jejich četnosti – graf potom tvoří prudce klesající křivku, jako je např.
tato:
50
11.3 Typy rozložení 11 STATISTIKA A PRAVDĚPODOBNOST
Toto rozložení velmi často výstižně popisuje nejrůznější frekvenční seznamy
– např. pokud vytvoříme pravděpodobnostní rozložení velikostí světových měst,
dojdeme ke křivce Zipfova rozložení. Stejnou křivku dostaneme, pokud vytvoříme
pravděpodobnostní rozložení slov nebo jejich morfologických kategorií
v jazyce.
Pro ilustraci uveďme frekvenční seznam morfologických značek pro angličtinu
(zdrojem byl americký korpus Brown):
51
11.4 Distribuční funkce 11 STATISTIKA A PRAVDĚPODOBNOST
11.3.1 Zipfův zákon
Skutečnost, že Zipfovo rozložení výstižně popisuje opravdu velké množství jevů,
se někdy označuje jako „Zipfův zákon”. Zejména v přirozeném jazyce tento
zákon platí téměř všude: téměř vždy je frekvence (nebo ekvivalentně – pravděpodobnost
výskytu) zhruba nepřímo úměrná pořadí podle této frekvence;
to platí pro slova, dvojice slov, slovní druhy, syntaktické vztahy, sémantické
kategorie a mnohá další. Při jakémkoli zpracování jazyka je tedy třeba s ním
počítat.
Pro ilustraci uveďme frekvence nejčastějších slovních tvarů v angličtině:
„the” má relativní četnost 7 %, druhé „of” má 3,5 % a více než polovina
anglických korpusů je pokryta 135 nejčastějšími slovy (u těchto slov se můžete
setkat s technickým označením stoplist).
Zipfův zákon platí dokonce i pro „náhodně generovaný” jazyk – pokud
budeme náhodně generovat znaky včetně mezery, pravděpodobnostní rozložení
takto vygenerovaných „slov” bude odpovídat Zipfovu rozložení.
Zipfův zákon platí ale i v mnoha oblastech mimo přirozený jazyk – již jsme
zmínili např. počet obyvatel měst; dále jej lze aplikovat např. na velikost platů,
počet zaměstnanců společností a mnohá další. Rovněž známé ekonomické
pravidlo „80 : 20” – 80 % problému vyřešíme s 20% úsilím – je vlastně
alternativní formulací Zipfova zákona.
11.4 Distribuční funkce
Jak jsme si řekli, pravděpodobnostní rozložení je pravděpodobnost, že náhodná
veličina nabude určité hodnoty (resp. zda patří do dané třídy), čili 𝑝(𝑥) =
𝑃(𝐴 = 𝑥), a její hodnoty odpovídají relativním četnostem ve statistickém
souboru.
Distribuční funkce (cumulative distribution function), často značena 𝐹,
je pravděpodobnost, že náhodná veličina nabude určité hodnoty nebo menší,
čili 𝐹(𝑥) = 𝑃(𝐴 ≤ 𝑥). Její hodnoty odpovídají kumulativním relativním
četnostem ve statistickém souboru. Hodnoty distribuční funkce jsou také
dobře známé jako tzv. percentil. Hodnota distribuční funkce (percentil)
mediánu statistického souboru je 0,5.
11.5 Náhodný vektor
Náhodný vektor chápeme jako posloupnost náhodných veličin, např. náhodný
vektor „počasí v Brně zítra v poledne” můžeme chápat jako trojici
(𝑡𝑒𝑝𝑙𝑜𝑡𝑎, 𝑡𝑙𝑎𝑘, 𝑣𝑙ℎ𝑘𝑜𝑠𝑡). Jeho pravděpodobnostní rozložení můžeme modelovat
s využitím vícerozměrného statistického souboru.
52
11.5 Náhodný vektor 11 STATISTIKA A PRAVDĚPODOBNOST
Pozor na to, že pravděpodobnost jednoho určitého vektoru hodnot může
být obecně jiná než součin pravděpodobností jednotlivých jeho složek, což by
se mohlo na první pohled (a po absolvování středoškolské pravděpodobnosti)
zdát. Aby se jednalo o součin, musely by být jednotlivé složky vektoru
dokonale nezávislé (viz dále), což v praxi téměř nikdy nenastává (i když to
pro jednoduchost často předpokládáme). Pro dvourozměrný náhodný vektor
(𝐴, 𝐵) je hodnota pravděpodobnostního rozložení
𝑝(𝑥, 𝑦) = 𝑃(𝐴 = 𝑥 ∧ 𝐵 = 𝑦)
(srov. s pravděpodobnostním rozložením pro jednoduchou náhodnou veličinu).
Lze definovat i distribuční funkci pro náhodný vektor, např. pro dvourozměrný
náhodný vektor je distribuční funkce analogicky definována jako
𝐹(𝑥, 𝑦) = 𝑃(𝐴 ≤ 𝑥 ∧ 𝐵 ≤ 𝑦).
53
12 PODMÍNĚNÁ PRAVDĚPODOBNOST
12 Podmíněná pravděpodobnost
Po předvedení, jak souvisí pravděpodobnost se statistikou, se dále ve výkladu
budeme zabývat některými dalšími, většinou prakticky motivovanými pojmy
z této oblasti. Také si ukážeme některé praktické aplikace teorie pravděpodobnosti
na praktické, i lingvistické, problémy.
Podmíněná pravděpodobnost je motivována potřebou formalizovat
to, že často máme kromě pravděpodobnostního rozložení daného jevu další
informace, např. o jiném jevu, který s původním může, ale nemusí souviset.
Např. pokud budeme počítat pravděpodobnostní rozložení součtu dvou hodů
kostkou až poté, co budeme znát výsledky prvního hodu, bude výsledné
pravděpodobnostní rozložení jiné, než pokud budeme počítat toto rozložení
bez jakýchkoli znalostí (zkuste si např. vypočíst pravděpodobnost. že padne
součet 8 a pak pravděpodobnost, že padne součet 8 za předpokladu, že
výsledek prvního hodu byl 1).
Jak jsme řekli, dva jevy, které zde bereme v potaz, spolu obecně mohou,
ale nemusí, kauzálně souviset. Můžeme např. počítat pravděpodobnost deště
zítra v poledne za předpokladu deště dnes v poledne (kde nejspíš nějaká
souvislost existuje), ale i např. pravděpodobnost, že člověk je bezdomovec,
pokud má vousy delší než 5 cm (zde bychom zřejmě také vypozorovali „souvislost”,
nicméně nemůžeme vyvodit nic takového jako „dlouhé vousy způsobují
bezdomovectví” apod.). Pozor na fakt, že v běžném životě se změna pravděpodobnostního
rozložení při určité podmínce často jako kauzální souvislost
prezentuje. Většina zpráv typu „vědci zjistili, že ... (např. konzumace červeného
masa způsobuje rakovinu)” přitom obsahuje pouze informaci o tom, že
někdo zjistil, že mezi těmito dvěma jevy existuje korelace nebo že pravděpodobnostní
rozložení druhého jevu se nějakým způsobem změní, pokud své
zkoumání omezíme jen na objekty, pro které nastává první jev. To však nic
nenapovídá o kauzálních vztazích těchto dvou jevů – souvislost může být
náhodná nebo mít komplikovanější charakter (např. v případě červeného masa
se později zjistilo, že jeho konzumenti také častěji kouří, což asi s rakovinou
bude mít společného více než červené maso). Pozor tedy na zaručené „vědecké”
informace; sami vědci velmi často nerozumí číslům, se kterými operují,
nemluvě o reportérech, kteří nám jejich zjištění zprostředkují.
Ale zpět k formálním pojmům. Podmíněnou pravděpodobnost zapisujeme
𝑃(𝐴|𝐵)
a čteme „pravděpodobnost jevu 𝐴 za předpokladu, že nastal jev 𝐵”.
Podmíněnou pravděpodobnost lze vypočítat následovně:
𝑃(𝐴|𝐵) = 𝑃(𝐴, 𝐵)/𝑃(𝐵)
54
12.1 Nezávislé jevy 12 PODMÍNĚNÁ PRAVDĚPODOBNOST
kde 𝑃(𝐴, 𝐵) je pravděpodobnost, že jevy 𝐴 a 𝐵 nastaly současně. Alternativně,
pokud máme k dispozici výchozí statistický soubor, můžeme podmíněnou
pravděpodobnost (resp. celé podmíněné pravděpodobnostní rozložení)
odvodit tak, že se omezíme jen na objekty, u kterých platí jev 𝐵, a provést
výpočet pravděpodobnostního rozložení pouze na nich. (Vzorec výše de facto
funguje stejně.)
12.1 Nezávislé jevy
Skrze podmíněnou pravděpodobnost definujeme i tzv. nezávislé jevy. Intuitivně
platí, že pokud jsou jevy nezávislé, pak by nám informace o jednom
z nich neměla dát žádnou informaci o druhém z nich. Matematicky zapsáno,
jevy 𝐴 a 𝐵 jsou nezávislé, pokud
𝑃(𝐴|𝐵) = 𝑃(𝐴) ∧ 𝑃(𝐵|𝐴) = 𝑃(𝐵)
čili jsou nezávislé, pokud to, jestli nastal jev 𝐵, nijak neovlivní pravděpodobnost
jevu 𝐴 a naopak (ve skutečnosti stačí, aby platila jedna strana této
konjunkce, neboť pak platí zcela jistě i druhá strana – zkuste si rozmyslet
proč a dokázat).
Jen a pouze pro nezávislé jevy pak platí vzorec, který se snadno odvodí
z nezávislosti jevů a z definice podmíněné pravděpodobnosti (Vyzkoušejte si
jako cvičení!) a se kterým jsme často počítali na střední škole:
𝑃(𝐴, 𝐵) = 𝑃(𝐴) * 𝑃(𝐵)
Ještě jednou zdůrazněme: Pozor, toto platí pouze pro nezávislé jevy! Reálné
jevy nebývají téměř nikdy dokonale nezávislé (i když v některých případech
je oprávněné nezávislost předpokládat, např. při hodu dvěma mincemi to, co
padne na první minci nejspíše neovlivní to, co padne na druhé).
12.2 Bayesův vzorec
Někdy nemáme přístup přímo ke statistickému souboru, z něhož vycházíme,
ale známe některé pravděpodobnosti z něj odvozené. Např. když má test na
drogy přesnost 99 %, znamená to obvykle:
𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡 | 𝑡𝑒𝑠𝑡𝑜𝑣𝑎𝑛ý 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) = 0, 99
𝑃(𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡 | 𝑡𝑒𝑠𝑡𝑜𝑣𝑎𝑛ý 𝑛𝑒𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) = 0, 99
55
12.2 Bayesův vzorec 12 PODMÍNĚNÁ PRAVDĚPODOBNOST
Přitom nevíme, z jakých statistických dat byla tato čísla odvozena, ale
důvěřujeme jim, protože např. pocházejí z důvěryhodného zdroje.
Pak nám často vzniká potřeba podmíněné pravděpodobnosti převádět,
např. pokud uděláme někomu test, který vyjde pozitivně, chceme spočítat
pravědpodobnost, s jakou testovaný jedinec opravdu požil drogu. Jinými slovy,
chceme spočítat
𝑃(𝑡𝑒𝑠𝑡𝑜𝑣𝑎𝑛ý 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢 | 𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡)
a obecně chceme převádět 𝑃(𝐴|𝐵) na 𝑃(𝐵|𝐴). Pokud známe také pravděpodobnosti
𝑃(𝐴) a 𝑃(𝐵), můžeme použít tzv. Bayesův vzorec:
𝑃(𝐴|𝐵) =
𝑃(𝐵|𝐴)*𝑃(𝐴)
𝑃(𝐵)
Tento vzorec lze snadno dokázat s využitím definice podmíněné pravděpodobnosti
(viz výše) pro 𝑃(𝐴|𝐵) a 𝑃(𝐵|𝐴) – zkuste si sami.
Pokud bychom chtěli spočítat pravděpodobnost z našeho příkladu, tedy
zda testovaný požil drogu za předpokladu, že má pozitivní test, musíme tedy
znát pravděpodobnosti
𝑃(𝑡𝑒𝑠𝑡𝑜𝑣𝑎𝑛ý 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢)
𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡)
Dejme tomu, že 0,5 % lidí užívá příslušnou drogu, tedy
𝑃(𝑡𝑒𝑠𝑡𝑜𝑣𝑎𝑛ý 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) = 0, 005.
Druhou z pravděpodobností můžeme vypočítat následovně:
𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡) =
= 𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡, 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) + 𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡, 𝑛𝑒𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) =
= 𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡 | 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) * 𝑃(𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢)
+ 𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡 | 𝑛𝑒𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) * 𝑃(𝑛𝑒𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) =
= 0, 99 * 0, 005 + 0, 01 * 0, 995
= 0, 0149
První krok je pouze vyjádření pravděpodobnosti jednoho jevu pomocí
součtu pravděpodobností dvou jevů přes všechny hodnoty druhého jevu
(rozmyslete a vyzkoušejte si, proč toto platí), druhý krok je opět použití
definice podmíněné pravděpodobnosti.
56
12.2 Bayesův vzorec 12 PODMÍNĚNÁ PRAVDĚPODOBNOST
Po dosazení do Bayesova vzorce dostáváme
𝑃(𝑡𝑒𝑠𝑡𝑜𝑣𝑎𝑛ý 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢 | 𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡) =
= 𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡 | 𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢) * 𝑃(𝑝𝑜ž𝑖𝑙 𝑑𝑟𝑜𝑔𝑢)
𝑃(𝑝𝑜𝑧𝑖𝑡𝑖𝑣𝑛í 𝑡𝑒𝑠𝑡) = 0,99*0,005
0,0149 =
= 0, 3322
Tedy pravdpodobnost, že testovaný s pozitivním testem skutečně požil
drogu, je zhruba třetinová, jinými slovy dva ze tří lidí, kterým vyšel test
pozitivně, drogu vůbec nepožili. Jak je to možné, když úspěšnost testu je
téměř stoprocentní? Co by se muselo změnit, aby test pro nás fungoval dobře?
(Nápověda: Zkuste předpokládat, že 50 % populace užívá drogu a provést
stejný výpočet.)
Podobných zdánlivých paradoxů existuje více – zmíníme zde ještě např.
tzv. Monty Hall problem.8
Obecně je důležité je uvědomit si význam čísel, ptát se po jejich přesném
významu a nenechat se zmást na první pohled vysokými hodnotami – v praxi
se používají testy i s daleko horší úspěšností než 99 %, např. při testech
na různé choroby, prenatální diagnostice apod.; pravděpodobnost, že test
vypovídá spolehlivě, může být tedy často o dost menší.
8
http://en.wikipedia.org/wiki/Monty_Hall_problem
57
13 ZÁKON VELKÝCH ČÍSEL
13 Zákon velkých čísel
Dále budeme pokračovat třemi kratšími kapitolami ze statistiky a pravděpodobnosti,
které s látkou výše souvisí spíše volně, nicméně jsou velmi důležité.
Zákon velkých čísel říká v podstatě to, že aby výsledky založené na
statistických metodách byly kvalitní a reprezentativní, potřebujeme je odvozovat
z velkých statistických souborů. (To samozřejmě mimo jiné znamená, že
všechny naše jednoduché příklady na statistiku tomuto zákonu odporují – pro
účely procvičení nám to nevadí, je ale třeba, abychom si toho byli vědomi.)
Pro intuitivní ověření tohoto zákona můžeme udělat následující myšlenkový
pokus: Pokud budeme pozorovat pohyb několika málo molekul v moři, bude se
jejich pohyb jevit náhodný; naproti tomu pokud budeme sledovat významný
podíl molekul, budeme schopni pozorovat jevy jako mořské proudy, vlny,
příliv...
Matematická formulace zákona zní tak, že čím větší počet pokusů provedeme,
tím větší je pravděpodobnost, že průměr výsledků pokusů bude
odpovídat očekávanému vypočtenému průměru. Tato formulace věty je i
formálně matematicky dokázána; tento důkaz však už přesahuje rámec našeho
zájmu. Místo toho uvedeme jeden další myšlenkový pokus: Pokud budeme
postupně házet vyváženou kostkou, průměr prvních dvou pokusů bude zcela
náhodný; průměr 50 pokusů bude již velmi pravděpodobně blízký očekávanému
3,5, ale stále je zde poměrně velká možnost náhodných odchylek. Pokud
provedeme 1000 pokusů, pak pravědpodobnost, že průměr nebude velmi blízko
očekávané hodnotě 3,5, je mizivá. Pro ilustraci zde uvádíme graf jednoho
z takových pokusů (zdroj: Wikipedia):
58
13 ZÁKON VELKÝCH ČÍSEL
1
2
3
4
5
6
0 100 200 300 400 500 600 700 800 900 1000
meanvalue
trials
average dice value against number of rolls
average
y=3.5
Podobně je tomu např. u zkoumání jazykových korpusů: Pokud se slovo
(značka, kolokace, ...) v korpusu vyskytuje dvakrát, není o něm statistika
schopna říci téměř nic. Pokud se vyskytuje padesátkrát, pak už lze vyvozovat
nějaké závěry, nicméně stále hrozí poměrně velké náhodné odchylky. Pokud se
vyskytuje tisíckrát, můžeme naše statistické výpočty považovat za spolehlivé.
Tento fakt je také příčinou zájmu o budování korpusů o velikosti desítek
miliard slov nebo i větších.
Vždy tedy musíme naše statistické závěry zakládat na velkém počtu
výskytů.
59
14 STATISTICKÉ TESTOVÁNÍ HYPOTÉZ
14 Statistické testování hypotéz
Statistické testování hypotéz je standardní exaktní metodika, s jejíž pomocí
je možné statisticky prokázat nějakou hypotézu s pomocí pozorovaných dat.
Jinými slovy chceme zjistit, zda naše statistická data potvrzují nějakou
hypotézu. Slovo „prokázat” zde budeme chápat nikoli ve smyslu prokázat
dokonale a nade vši pochybnost, ale tak, že pravděpodobnost chyby našeho
úsudku bude minimalizována.
Vysvětlíme si celou věc na následujícím pokusu: Ukazujeme člověku postupně
hrací karty z rubu, tak, aby neviděl lícovou stranu. Úkolem člověka je
uhodnout jednu ze čtyř barev karty, která je mu ukázána, aniž by se podíval
na líc. Necháme ho hádat postupně např. 25 karet. Otázka zní: Kolikrát musí
odpovědět správně, abychom ho prohlásili za „jasnovidce” – člověka, který
skutečně ví něco o tom, která karta je mu zrovna ukázána, a nehádá pouze
náhodně?
Selským rozumem nejspíš usoudíme, že pokud uhodne např. 5x, bude to
asi náhoda; pokud uhodne 24x, bude tento člověk nejspíš jasnovidcem. Ale
jsou tyto naše „selské” úsudky správné? Již jsme měli možnost se přesvědčit,
že neplatí vždy to, co je zdánlivě zřejmé na první pohled. Další otázkou je
– co usoudíme, když uhodne např. 12x? Jak určit hranici, odkdy je člověk
„jasnovidec”?
Z toho, co už víme o pravděpodobnosti je jasné, že např. i 25 úspěšných
pokusů při hádání karet může být náhoda; může se stát, že člověk uhodl 25x a
přitom o skutečné barvě karet opravdu nic nevěděl. Co dále umíme, je stanovit
pravděpodobnost takové události. A právě vyjádření pravděpodobnosti toho,
že dané výsledky vznikly náhodně, je základem metodiky testování hypotéz.
Statistické testování hypotéz zavádí několik základních pojmů:
∙ Nulová hypotéza, značeno 𝐻0, je předpoklad, který obvykle platí a
který chceme našimi statistickými daty vyvrátit. V případě hádání karet
by 𝐻0 byla „pokusná osoba hádá náhodně”.
∙ Alternativní hypotéza, značeno 𝐻1, je tvrzení, pro které hledáme
oporu v našich datech. Musí být doplňková k 𝐻0, tedy výrok „𝐻0 ∨ 𝐻1”
musí být tautologie, žádná třetí možnost není přípustná. V našem
případě by 𝐻1 byla „pokusná osoba nehádá náhodně”.
∙ Chyba typu I nastává, pokud potvrdíme 𝐻1, neboli vyvrátíme nulovou
hypotézu, ale přitom platí 𝐻0. Úkolem testování hypotéz je
minimalizovat pravděpodobnost této chyby.
∙ Chyba typu II nastává, pokud nepotvrdíme 𝐻1 a ta je přitom platná.
Tato chyba není tak závažná.
60
14 STATISTICKÉ TESTOVÁNÍ HYPOTÉZ
Analogii chyb typu I a II můžeme spatřovat v trestním právu – výchozím
předpokladem je nevina obžalovaného (nulová hypotéza). Pokud uvězníme
nevinného (chyba typu I, vina byla prokázána a dotyčný byl přitom nevinen),
dopustíme se horšího činu než když osvobodíme viníka (chyba typu II) na
základě nedostatečných důkazů. Podobně pokud se při testování hypotéz
nepodaří vyvrátit nulovou hypotézu, neznamená to, že nulová hypotéza platí,
podobně jako osvobození obžalovaného neprokazuje jeho nevinu.
Tento fakt bývá rovněž velmi často opomíjen (i ve vědeckých kruzích),
takže ho zopakujeme ještě v alternativní formulaci: To, že se nepodařilo
prokázat souvislost neznamená, že souvislost neexistuje (pouze ji dostupná
data nepotvrzují s dostatečnou jistotou).
Doveďme nyní náš příklad do konce: Máme dánu nulovou a alternativní
hypotézu a předpokládejme, že pokus dopadl tak, že dotyčný uhodl barvu ve
všech 25 případech správně. Na základě toho jsme usoudili, že nehádá barvu
náhodně (řekli jsme, že nulová hypotéza je vyvrácena). Pravděpodobnost
chyby typu I je pak za předpokladu nezávislosti pokusů (1/4)25
= 𝑐𝑐𝑎 10−15
(1 tip má pravděpodobnost úspěchu 1/4 a bylo provedeno 25 nezávislých
pokusů). Vidíme, že tato pravděpodobnost je naprosto zanedbatelná, čili
řekneme, že se podařilo prokázat, že dotyčný nehádal karty náhodně.
Obvykle pro vyvrácení nulové hypotézy požadujeme nějakou maximální
přípustnou pravděpodobnost chyby typu I. Tato mez se může lišit v závislosti
na aplikaci – nejčastěji bývá požadováno max. 1 %, můžeme být ale striktnější
a požadovat např. desetinu nebo i setinu procenta, nebo naopak méně striktní
a požadovat 5 %. Výsledku, který byl takovýmto způsobem ověřen (tj. nulová
hypotéza byla vyvrácena s pravděpodobností chyby typu I méně než X %),
pak říkáme statisticky průkazný.
Již bez výpočtu (který by byl v tomto případě komplikovanější) doplňme,
že v případě našeho pokusu by stačilo 12 úspěšně uhodnutých karet k tomu,
abychom vyvrátili nulovou hypotézu s pravděpodobností chyby typu I méně
než 1 %.
Závěrem této kapitoly upozorníme na jedno nebezpečí v případě testování
hypotéz, v duchu principu, že nad čísly musíme přemýšlet. Pokud provedeme
pokus o vyvrácení nulové hypotézy vícekrát, logicky se zvyšuje pravděpodobnost,
že se nám to alespoň jednou podaří i přes to, že nulová hypotéza platí
(zvyšuje se pravděpodobnost chyby typu I). Při opakování pokusů musíme
tedy brát v potaz všechna data, která jsou k dispozici, nikoliv jen ten vzorek,
na němž to (dost možná náhodou) vyšlo správně.
To také souvisí s problematikou publikací vědeckých výsledků: pokud není
nalezena souvislost, výsledek obvykle není významný, není tedy publikován a
příslušná data často zapadnou. Pokud je nalezena souvislost (relativně nedávno
např. probíhaly diskuse tohoto typu o vlivu oxidu uhličitého na globální
61
14 STATISTICKÉ TESTOVÁNÍ HYPOTÉZ
oteplování), výsledek je obvykle publikován a považován za průkazný. Téměř
nikdy ale nejsou brána v potaz předchozí data, která souvislost neprokázala,
což zvyšuje pravděpodobnost chyby publikovaných výsledků. Zůstává přitom
otevřenou otázkou, zda je možné v tomto ohledu něco výrazně změnit.
62
15 ENTROPIE
15 Entropie
Entropie náhodné veličiny je zjednodušeně řečeno míra informace obsažená
v této náhodné veličině, tedy číslo vyjadřující, kolik informace získáme,
když se dozvíme skutečnou hodnotu (tu, která nastala) náhodné veličiny.
Entropie je vždy nezáporná a měří se v bitech. Nulová entropie znamená, že
hodnotu náhodné veličiny jsme schopni určit se stoprocentní jistotou (takovou
veličinou může být např. výsledek hodu falešnou kostkou, na které padají
pouze šestky). Čím vyšší je entropie, tím více informace je obsaženo v náhodné
veličině – jinými slovy tím více jednotek informace je třeba k přenesení
výsledku náhodného pokusu.
Historické počátky úvah o statistické entropii sahají do 40. let 20. století,
kdy byly zkoumány metody, jak lze s minimální přenosovou kapacitou přenést
určitou zprávu, a kdy byly též vyvíjeny první kompresní algoritmy. Tyto
počátky jsou spojeny se jménem Claude Shannon. Samotná entropie skutečně
vyjadřuje minimální průměrný počet bitů (jedniček a nul), který je potřeba
pro přenesení určité informace, v našem případě uvažované jako výsledek
náhodného pokusu.
Entropie náhodné veličiny 𝑋 – 𝐻(𝑋) – nebo ekvivalentně entropie jejího
pravděpodobnostního rozložení 𝑝 – 𝐻(𝑝) – se spočítá následovně:
−
∑︁
𝑥∈𝑋
𝑝(𝑥)𝑙𝑜𝑔2 𝑝(𝑥)
Např. entropie počtu orlů při házení 2 mincemi se vypočte následovně.
Nejprve vyjádříme pravděpodobnosti jednotlivých možných hodnot:
𝑝(0) = 1/4, 𝑝(1) = 1/2, 𝑝(2) = 1/4
a pak dosadíme do vzorce:
𝐻(𝑝) = −(1/4𝑙𝑜𝑔2(1/4) + 1/2𝑙𝑜𝑔2(1/2)) + 1/4𝑙𝑜𝑔2(1/4)) =
−(−2/4 − 1/2 − 2/4) = 1, 5 𝑏𝑖𝑡𝑢
V případě, kdy uvažujeme entropii jako nutnou informaci pro přenos, lze
tuto hodnotu interpretovat tak, že při přenášení informace o sérii hodů dvěma
mincemi potřebujeme průměrně 1,5 bitu na jeden pokus – jednu možnost
můžeme kódovat 1 bitem, dvě další (ty méně pravděpodobné) 2 bity.
Zkuste si sami spočíst entropii pro případ hodu jedinou mincí. Očekávaná
hodnota výsledku je 1 bit, neboť např. 1 orla můžeme reprezentovat jedničkou,
žádného nulou – více informace nepotřebujeme.
63
15.1 Podmíněná entropie 15 ENTROPIE
15.1 Podmíněná entropie
Podobně jako jsme zavedli podmíněnou pravděpodobnost lze zavést podmíněnou
entropii s analogickým významem – míra informace obsažená v náhodné
veličině za předpokladu, že známe hodnoty jiné náhodné veličiny. Je definována
jako
𝐻(𝑋|𝑌 ) =
∑︁
𝑥∈𝑋
𝑝(𝑥)𝐻(𝑌 | 𝑋 = 𝑥)
Podobně jako u podmíněné pravděpodobnosti, lze entropii dvojice náhodných
veličin převést na podmíněnou entropii a naopak. K tomu slouží tzv.
řetízkové pravidlo (chain rule):
𝐻(𝑋, 𝑌 ) = 𝐻(𝑋) + 𝐻(𝑌 |𝑋)
15.2 Mutual information
Mutual information – česky vzájemná informace – je statistickou veličinou
založenou na entropii, která určuje míru informace, kterou jedna náhodná
proměnná říká o jiné. Je rovna nule, pokud jsou veličiny nezávislé, a čím vyšší
její hodnota je, tím hodnoty jedné vlastnosti určují hodnoty druhé vlastnosti.
Vzorec pro mutual information je:
𝑀 𝐼(𝑋; 𝑌 ) = 𝐻(𝑋) − 𝐻(𝑋|𝑌 ) = 𝐻(𝑌 ) − 𝐻(𝑌 |𝑋)
Ve statistickém zpracování přirozeného jazyka vzájemnou informaci můžeme
použít k měření síly kolokace dvou slov – v tomto případě uvažujeme
výskyt jednoho slova (např. „základní”) za jednu náhodnou veličinu a výskyt
druhého slova (např. „škola”) v textu. Ze vzorce mutual information vyplývá,
že je tím vyšší, čím vyšší je počet souvýskytů těchto slov v korpusu a tím nižší,
čím jsou jednotlivá slova častější. Mutual information pro slova „základní” a
„škola” bude tedy zřejmě mnohem vyšší než např. pro „počítač” a „škola”.
64
16 STATISTIKA A ZPRACOVÁNÍ JAZYKA
16 Statistika a zpracování přirozeného jazyka
Na závěr našeho výkladu si ukážeme několik aplikací statistiky při automatickém
zpracování přirozeného jazyka. Jak už víme, statistika je nástroj, který
nám umožňuje uchopit a popsat velké množství dat a na tomto základě lze
vyvozovat další informace o objektech, které jsou v našich datech obsaženy,
např. za účelem stanovení pravděpodobností různých jevů nebo predikce
událostí.
Pro účely statistického zpracování přirozeného jazyka jsou k dispozici
velké soubory jazykových dat v podobě jazykových korpusů o velikosti i více
než 10 miliard slov. Tyto korpusy umožňují aplikovat statistické metody
tak, jak jsme si je přiblížili, na přirozený jazyk, predikovat jeho chování a
modelovat jej. Využití statistiky ve zpracování přirozeného jazyka je obrovské
a nástroje založené na statistickém modelování jazyka jsou v současnosti
v mnoha oblastech ty vůbec nejlepší.
My si ukážeme využití statistiky na dvou ukázkách – první bude vyhledávání
kolokací, druhou pak n-gramové jazykové modely.
16.1 Vyhledávání kolokací
Definice pojmu kolokace se v různých zdrojích liší. Podle některých je to fráze,
jejíž význam se neskládá z významů jejích částí, či idiom, podle jiných je
to pouze nějakým způsobem významné spojení dvou slov. Statistika nabízí
svůj vlastní pohled, který v mnoha ohledech koresponduje s oběma výše
nastíněnými definicemi – kolokaci můžeme považovat za statisticky významné
spojení dvou slov (v korpusu), a to podle různých metrik. Navíc podle většiny
těchto metrik umíme určit i „sílu” kolokace libovolných dvou slov.
Jakým způsobem můžeme tedy hledat v korpusu kolokace? Můžeme začít
s prostým počítáním pravděpodobností výskytů dvojic slov v korpusu. Pak se
nám ale (např. v případě angličtiny) na nejvyšší příčky dostanou dvojice jako
„of the” nebo „in the”, což asi úplně neodpovídá tomu, co si představujeme
pod pojmem kolokace. Zřejmě potřebujeme nějakým způsobem znevýhodnit
slova z tzv. stoplistu.
Jeden z možných způsobů, jak tohoto docílit, je uvažovat při vyhledávání
kolokací pouze dvojice složené z určitých slovních druhů, např. podstatných
jmen, přídavných jmen a sloves, popřípadě příslovcí. Již s takovýmto jednoduchým
omezením dostaneme mnohem lepší výsledky; mezi nejlepšími
však stále ještě budou dvojice jako např. „last week”, kde je otázka, zda je
chceme považovat za kolokace nebo ne. Jisté je, že slova jako „last”, „new”
apod. budou mít časté souvýskyty s velkým množstvím slov a ne všechny
z nich budeme považovat za významné. Co tedy dále můžeme potřebovat, je
65
16.2 N-gramové modely 16 STATISTIKA A ZPRACOVÁNÍ JAZYKA
znevýhodnit nejen slova ze stoplistu, ale všechna častější slova, a to poměrně.
K tomuto účelu slouží celá řada statistických metrik (je jich více, protože
pro různé aplikace se hodí různé z nich a nelze vybrat jednu univerzálně
nejlepší) – např. T-test, což je aplikace testování hypotéz. Nulová hypotéza
v tomto případě říká, že slova se chovají náhodně podle svých obvyklých
pravděpodobnostních rozložení. Pokud je nulová hypotéza vyvrácena (slova
se spolu vyskytují častěji než náhodně), prohlásíme příslušnou dvojici slov za
kolokaci. Z pravděpodobnosti chyby typu I můžeme odvodit sílu kolokace a
podle této pravděpodobnosti můžeme kolokace setřídit.
Mezi další podobné metriky patří vzájemná informace, představená v minulé
kapitole, nebo tzv. dice a logdice, které používá pro sestavování kolokačních
profilů (tzv. word sketches) komerční korpusový nástroj Sketch
Engine.
16.2 N-gramové jazykové modely
Jako n-gram označujeme obvykle posloupnost slov délky 𝑛, která se vyskytuje
v korpusu. Nejjednodušší představa n-gramového jazykového modelu vede
přes následující úlohu: Známe posloupnost 𝑛 − 1 slov v korpusu. Jaké slovo
za nimi bude následovat?
Formálně se n-gramový jazykový model skládá z podmíněných pravděpo-
dobností
𝑃(𝑤 𝑛 | 𝑤1, ..., 𝑤 𝑛−1)
čili pravděpodobností, že se vyskytlo slovo 𝑤 𝑛 za předpokladu, že před ním
se vyskytla slova 𝑤1, ..., 𝑤 𝑛−1. Souhrn všech takovýchto pravděpodobností pro
všechny možné kombinace slov v korpusu (tento souhrn snadno odvodíme
z textu korpusu) se nazývá n-gramový jazykový model.
𝑤1, ..., 𝑤 𝑛 přitom nemusí být pouze slova – můžeme vytvořit n-gramový
model znaků, fonémů, pádů, morfologických značek apod., případně i komplikovanější
modely, kde např. 𝑤 𝑛 bude morfologická značka a 𝑤1, ..., 𝑤 𝑛−1
budou slova. Využití n-gramových modelů ve zpracování jazyka je obrovské,
proto existuje nepřeberné množství, z nichž nejpoužívanější je pravděpodobně
trigramový (𝑛 = 3) jazykový model.
Například bigramový (𝑛 = 2) jazykový model na znacích pro text „mama
mele maso” by byl následující (mezery v tomto případě pro přehlednost
ignorujeme):
𝑃(𝑎|𝑚) = 3/4
𝑃(𝑒|𝑚) = 1/4
66
16.2 N-gramové modely 16 STATISTIKA A ZPRACOVÁNÍ JAZYKA
𝑃(𝑚|𝑎) = 2/3
𝑃(𝑠|𝑎) = 1/3
𝑃(𝑙|𝑒) = 1/2
𝑃(𝑚|𝑒) = 1/2
𝑃(𝑒|𝑙) = 1
𝑃(𝑜|𝑠) = 1
𝑃($|𝑜) = 1
𝑃(𝑥|𝑦) = 0 𝑝𝑟𝑜 𝑣š𝑒𝑐ℎ𝑛𝑦 𝑜𝑠𝑡𝑎𝑡𝑛í 𝑘𝑜𝑚𝑏𝑖𝑛𝑎𝑐𝑒
Všimněte si, že podle omezení kladená na pravděpodobnostní rozložení
musí součet všech pravděpodobností se stejnou posloupností za svislítkem být
roven 1. Rovněž upozorňujeme na symbol „$”, který používáme ve významu
„konec textu”, abychom mohli mít model úplný. Na závěr ještě zopakujeme,
že stejně jako všechny „malé” příklady, i tento odporuje zákonu velkých čísel
a pro rozumně reprezentativní jazykový model potřebujeme mnohem větší
vzorek textů.
Úloha „hádání dalšího slova” samozřejmě nemá sama o sobě žádný praktický
význam. I přesto jsou n-gramové modely ve zpracování jazyka používány
téměř všude – od rozpoznávání řeči přes morfologické značkování i syntaktickou
analýzu až po strojový překlad. Jazykový model nám totiž umožňuje
odhadnout nejpravděpodobnější sekvence symbolů, které odpovídají danému
(víceznačnému) vstupu – např. při rozpoznávání řeči se od sebe špatně rozeznávají
jednotlivé souhlásky, čili jeden zvuk může teoreticky mít několik
různých významů. Určení nejpravděpodobnější sekvence na základě jazykového
modelu a daného vstupu řeší algoritmy zpracování přirozeného jazyka,
které jsou však již nad rámec našeho výkladu.
16.2.1 Nedostatky jazykových modelů
Prvním problémem jazykových modelů je, že mohou být velké – často pro větší
𝑛 dostaneme tolik různých pravděpodobností, že počítačová práce s takovýmto
modelem je výpočetně velmi náročná. Malé 𝑛 nám zase často neposkytuje
dostatečný kontext na to, abychom na základě příslušného modelu prováděli
kvalitní odhady – často se vzájemně ovlivňují slova, která jsou jednoduše
příliš daleko od sebe. Efektivita modelu samozřejmě také závisí na základních
jednotkách (tzv. parametrech) modelu – např. znaků je mnohem méně než
slov, a tedy i modely na znacích budou mnohem menší než analogické modely
na slovech.
Ještě větším problémem je tzv. data sparseness (řídkost dat), což znamená,
že pro slova a n-gramy, které se nevyskytují tak často (a takových je i
v desetimiliardových korpusech stále velké množství) dostaneme nekvalitní
67
16.2 N-gramové modely 16 STATISTIKA A ZPRACOVÁNÍ JAZYKA
odhady pravděpodobností a podle zákona velkých čísel i podle praktických
experimentů fungují části jazykových modelů obsahující tato slova a n-gramy
skutečně špatně.
68