Když už něco tuším
- Spočítat očekávanouprůměrnou délku dotazování ve stromu, který není optimálníLze jej upravit a tím průměrnou délku dotazování snížit.
- Spočítat očekávanouprůměrnou délku dotazování v situaci, kdy „něco víme“ předem
- Porovnat dvě dotazovací strategie, strategii vylepšit (snížit průměrnou délku dotazování)
Při dotazovacích hrách jsme předpokládali stejné zastoupení všech zvířat, resp. čísel. Takový předpoklad je vhodný pro první seznámení s pojmem informace, není ale příliš realistický a v praxi nebývá naplněn. V této hodině proto situaci zobecníme. Pro mnohé studenty je problematika poměrně abstraktní, s výhodou se proto odvoláváme na dosavadní zkušenosti z her a z minulé lekce, kde se nestejné pravděpodobnosti nenásilně vyskytly.
Počítání průměrné výšky stromu je užitečná příprava. Je to zároveň zakuklený vážený průměr, ale zatím bez nutnosti uvažování nad různými četnostmi možností. Navíc se vážený průměr žáci mnohdy ani jinde neučí, takže toto je jejich první setkání, což nechceme uspěchat. Ničemu neškodí počítat zprvu po jednom, žáci samovolně zjistí, které části výpočtu jsou nudné a lze je zkrátit.
Dalším krokem je uvedení příkladu, kde se již jednotlivé možnosti (listy stromu) nevyskytují stejně často. Zejména v případě, kdy ještě studenti nemají pravděpodobnost probránu v matematice, se opíráme o intuitivní představu založenou právě na odlišných četnostech. Takovým příkladem je zjišťování měsíce narození. Pro studenty je ze zkušenosti zcela přirozené, že se lidé nerodí v průběhu roku rovnoměrně.
Studenti si obvykle rovnou uvědomí, že je třeba zjišťovací strategii nějak upravit, a že asi bude třeba silné měsíce nějak upřednostnit. V případě, že si to neuvědomí, není nic jednoduššího, než je nechat přehrát už známou situaci, ale tentokrát nikoliv s čísly, nýbrž s měsíci narození a jejich nerovnoměrným rozložením. Ke stejnému kroku se můžeme uchýlit téměř při libovolné nejasnosti studentů. Při sledování průběhu hry ji přirozeně dojdou potřebné souvislosti.
Otevře se přirozená otázka, totiž jak tedy své dotazování (nebo kódování) nerovnoměrnému zastoupení četností přizpůsobit. Klíčem je opět půlení, ale je třeba si rozmyslet, co vlastně potřebujeme půlit. Související úvahy umožní studentům pohlédnout poněkud hlouběji do principů teorie informace a optimálního rozhodování.
Počítání váženého průměru umožní různé strategie porovnat. Není ale odpovědí na otázku, jak přímočaře optimální strategie nacházet. Je důležité tohle rozlišit: umíme sice už délku dotazování přesně změřit, ale najít nejlepší strategii pořád znamená systematicky projít všechny varianty dotazování. Jako nabídneme níže uvedený algoritmus. Je srozumitelný, ale nezaručuje optimální výsledky (a studenti by měli zkusit zjistit proč). Optimální výsledky dává Huffmanovo kódování, které ale není tak dobře srozumitelné, proto jej řadíme jen jako doplňkovou látku.
Studenti si v hodině mají vyzkoušet obecnější (a realističtější) situaci než hádání čísel. Při promýšlení jejího řešení mají zároveň příležitost lépe pochopit, jak a proč vlastně funguje půlení intervalů.
Průměrná délka dotazování
Možná máš stále pochyby: Nemohlo by se přeci jen vyplatit mít rozhodovací strom nerovnoměrný, a některé možnosti umístit blíže ke kořeni a tak ušetřit potřebné otázky? Pojďme to prověřit. Obrázek stromu ani úvaha „méně otázek pro jednu možnost znamená více otázek pro více jiných možností“ koneckonců nejsou žádné skutečné důkazy. Podívejme se na výpočet průměrné výšky stromu.
Příklad: Výpočet průměrné výšky stromu
Zkus to např. s následujícím stromem:
Vezmi tužku a obtáhni cesty vedoucí od kořene stromu k jednotlivým možnostem (tedy pokud to máš na papíře). Zajímá nás celkový počet učiněných rozhodnutí (položených otázek). Můžeš je počítat buď po jednom už při procházení, nebo až nakonec, podle stop tužky. Výsledný součet pak už stačí podělit celkovým počtem možností, a máš hledaný průměr.
Průměr nějakých hodnot se počítá jako jejich součet vydělený jejich počtem. Pro každou možnost (list stromu) tedy potřebujeme zjistit, kolik otázek předchází jejímu určení, a počty otázek sečíst. Nakonec musíme součet vydělit počtem všech možností.
Řešení
Řešení
Zobecnění aritmetického průměru, ve kterém jednotlivé hodnoty nejsou rovnocenné, nazýváme vážený průměr. Každá hodnota h1, h2 až hn má svou váhu v1 až vn. Než hodnoty sečteme, vynásobíme každou z nich odpovídající vahou, a součet potom nedělíme počtem hodnot, ale součtem všech vah. Aritmetický průměr je vážený průměr v případě, kdy jsou všechny váhy stejné.
Tento poněkud neohrabaný zápis můžeme zpřehlednit pomocí znaku sumace. Dostaneme tak vzorec
Vážený průměr se často uplatní např. při výpočtu známky na vysvědčení, právě proto, že různé známky mají různou váhu.
Bráno po možnostech zleva: (2+4+4+3+2+4+4+3)/8 = 3,25.
K rozhodnutí podle daného stromu potřebujeme průměrně 3,25 otázek.
Všimni si, že je opravdu potřeba započítat důsledně všechny možnosti. Nestačí jen podělit dvěma součet nejlepší a nejhorší, tedy (2+4)/2=3. Čtyři otázky jsou potřeba častěji než dvě nebo tři, takže průměrná hodnota je ve skutečnosti vyšší.
Informatici jsou líní, takže si rádi ušetří práci. Spočtou, kolik různých možností potřebuje jednotlivé počty otázek a výpočet průměru si tak si usnadní: (2+4+4+3+2+4+4+3)/8 = (2⋅2 + 2⋅3 + 4⋅4)/8 = 3,25
Podívejme se pro srovnání na strategii hloupou, která se snaží číslo rovnou tipnout. Hned je vidět, že otázek bude nejspíš potřeba položit mnohem víc, než při použití strategie optimální. Je to ale takhle jednoduché? Přece pokud máme štěstí, tipovací strategie skončí po jediné otázce. My už ale umíme odhadnout, jak často štěstí přijde: Zjišťujeme-li jednu z n rovnocenných možností a hrajeme dlouho, dojde na každou možnost přibližně v jedné n-tině ze všech her.
Vyšetři tipovací strategii. Ta spočívá v kladení otázek na konkrétní čísla, např. „Je to číslo čtyři?“ Možnosti jsou zcela záměnné, takže je jedno, v jakém pořadí se na ně ptáme. Tvar stromu, takže ani efektivitu tipovací strategie, to nijak neovlivní.
Jaký je nejlepší, průměrný a nejvyšší počet potřebných otázek?
Řešení
Při tipování potřebujeme mezi jednouKdyž uhodneme hned. a patnáctiKdyž se trefíme až poslední otázkou, nebo vůbec. otázkami.
Protože rozdělení počtu otázek je skoro rovnoměrné, můžeme průměr rychle odhadnout jako (1+15)/2=8. Osm je víc než čtyři, takže hned vidíme, že je tipovací strategie v průměru mnohem horší, než strategie optimální.
Přesný výpočet průměru je o maličko složitější. Patnáct čísel uhodneme prostřednictvím jedné až patnácti otázek. Šestnácté číslo pak uhodneme také pomocí patnácti otázek. Přesněji tedy dostaneme (1+2+3+...+14+15+15)/16=8,4375. přidej odkaz na příslušnou část
Co když tuším, ale jistotu nemám?
Celou dobu vycházíme z myšlenky, že informace je rozdíl mezi tím, co jsme věděli předem, a tím, co víme po jejím získání. Na základě dosavadních zkušenosti to ještě zpřesníme.
Dosud jsme mlčky předpokládali, že o hledaném čísle či zvířeti nic nevíme. Tomu odpovídá předpoklad, že se všechny možnosti vyskytují stejně často. V životě ale většinou máme nějaký odhad, třeba na základě zkušenosti. Například u hádání zvířat by šlo vysledovat, že každý má nějaké svá oblíbená zvířata, která si často myslí.
Už jsme si řekli, že dlouhodobě nás zajímá průměrná délka dotazování. Víme-li, že kamarád obvykle jezdí na hory na Šumavu, nemá smysl určovat místo jeho dovolené přes polokoule a kontinenty. Pokud je zdaleka nejčastější místo dovolené Šumava, může se vyplatit začít přímým dotazem právě na Šumavu. Teprve potom, když to Šumava není, se ptáme obecně, už bez další znalosti (půlíme možnosti). Občas to dotazování prodlouží, když kamarád zrovna pojede jinam. V průměru ale dotazování bude kratší, než kdybychom slepě půlili všechny možnosti, a uhodnout Šumavu a Kavkaz by trvalo stejně dlouho.
Dostáváme se podrobněji k tomu, co to znamená, že o situaci „něco víme“: Nejen, že jsme si vědomi možností, které mohou nastat. Jsme si také aspoň do jisté míry vědomi, jak často které možnosti nastávají.
Příklad: Narozeniny
Vzpomeňte si na úlohu se zjišťováním měsíce narození. Optimální strategie v případě, že by se lidé rodili v každém měsíci stejně často, by byla půlením intervalů a vyžadovala něco mezi 3 a 4 otázkami. Uvažme ale následující tabulku, která uvádí počet narozených lidí v daném měsíci:
| Leden | Únor | Březen | Duben | Květen | Červen | Červenec | Srpen | Září | Říjen | Listopad | Prosinec |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8 | 6 | 2 | 1 | 3 | 7 | 9 | 14 | 17 | 11 | 7 | 15 |
(hodnoty jsou smyšlené)Povede se ti najít skutečné rozložení narození v průběhu roku? Jak se bude lišit rozhodovací strom sestavený podle pravdivých údajů?
Rozhodovací strom můžeme pro začátek sestavit jako vždy. Jeho efektivitu, tedy průměrnou délku dotazovaní, ale musíme počítat opatrněji. Už neplatí, že se každá možnost uplatní stejně často. Délku dotazování vedoucího k jednotlivým možnostem je proto potřeba započítat právě s ohledem na známou četnost výskytu.
A nešlo by to lépe než půlením?
Pečivo lidé nakupují často, takže jej ve velké samoobsluze umístí hned u vchodu. Počkat... jenže tak to leckdy není! Proč asi?
A nemysli si, že je to náhoda. Uspořádání obchodu je rozmyšleno velmi pečlivě, včetně toho, které zboží je v úrovni očí a jak docílit, aby v regálu nebyl ani centimetr volného místa.
Leckdo už tuší, že s rozdílným výskytem různých možností nemusí vést půlení k nejlepšímu výsledku. Vyrovnaný strom možná nebude optimální. S rozdílnými četnostmi se už může stát, že se skutečně vyplatí umístit některou možnost ve stromě výš na úkor několika jiných, které ale nenastávají tak často.
V tomto případě opravdu funguje jednoduchá zásada:
Ve stromě tedy listy s vysokou četností patří vysoko, mají jít rozlišit málo otázkami. Naopak málo používané možnosti se nebojíme ve stromě umístit dolů. Tato zásada platí i jinde. V kuchyni asi máte vidličky dostupnější, než vykrajovátka na vánoční pečivo. Nejvytíženější a nejčastější vlaky zařadíme na nejbližší nástupiště, aby se co nejvíc lidí nachodilo co nejméně. Nejpoužívanější programy a nejnavštěvovanější stránky nám počítač nabízí přímo, není třeba hledat v hlubokých nabídkách.
Následování zásady může vést k docela dobrým stromům. Nějaký sestavíme, třeba už známým půlením, a spočteme průměrnou délku dotazování. Zkusíme strom upravit, časté možnosti posunout výš a méně časté níž. Spočteme nový průměr a porovnáme s předchozím - buď jsme si pomohli, a můžeme zkoušet upravovat dál, nebo ne, a zkusíme upravit původní strom nějak jinak.
Potíž je, že tenhle postup nedává žádné záruky. Každý může skončit se zcela jiným stromem (a jiným průměrem). Není ani jasné, kdy skončit. Když už se mi nedaří nacházet vylepšení stromu, je to proto, že už mám optimální strom, nebo proto, že jsem nešika?
Půlení podle četností je velmi blízký tzv. Shannon-Fanovu kódování.
Lepší postup vychází z půlení intervalů. Je jen třeba malá úprava. Dříve jsme půlili možnostiMožnost buď možná byla, nebo byla vyloučena. Teď jsou ale jednotlivé možnosti různě možné, neboli různě pravděpodobné. podle jejich počtu. To teď ale může vést k situaci, kdy je jedna odpověď mnohem častější, než druhá - jenže tomu jsme se právě chtěli vyhnout. Budeme tedy půlitVětšinou to nepůjde přesně, budeme se snažit k přesnému rozpůlení aspoň co nejvíc přiblížit. podle četností. Rozmysli si, že daný postup opravdu umístí často se vyskytující možnosti blízko ke kořeni stromu.
Příklad: Měsíc narození se správným půlením
V předchozím narozeninovém příkladu asi není dobrý nápad rozpůlit rok v pololetí, když se v prvním pololetí rodí pouhých 26 lidí ze sta. Je třeba půlit nikoliv čas, ale opravdu možnosti, čili narozené lidi. Polovina lidí se narodí do srpna, druhá polovina od září. Dobrá otázka může tedy využít právě toto rozdělení. Ne vždy to samozřejmě vyjde přesně.
Ještě lepšího výsledku by šlo dosáhnout, kdybychom si dovolili zpřeházet pořadí měsíců. Bylo by to nepřehledné, protože bychom už neměli celistvé intervaly k rozdělování. Prapodivné by byly také vzniklé otázky. Mohli bychom ale dosáhnout lepšího průměru, protože by mohlo vyjít přesnější dělení možností na poloviny.
Půlení podle četností nezaručuje, že dostaneme optimální strom. Podaří se ti najít příklad takového rozložení četností, pro které tento postup selžeNeboli výsledný strom nebude nejlepší možný? Možná je to právě náš příklad s měsíci - najdeš lepší strom, než ten vzniklý půlením podle četností?
Nad konstrukcí zaručeně optimálního stromu je dobré se zamyslet. Až se budeš chtít podívat na standardní řešení používané v informatice, vyhledej si Huffmanovo kódování.
Kódování a komprese
Na závěr připomeňme, že na rozhodovací stromy lze pohlížet jako na stromy kódovací. Na hledání rozhodovacího stromu, se kterým je dotazování nejrychlejší, tedy lze pohlížet jako na hledání kódu, který je nejkratší. Což je vlastně způsob, jak komprimovat data!
Máme-li nějaká dataTřeba text knihy, a v nich úsekyNapř. slova nebo věty., které se vyskytují častěji než jiné, vyplatí se tyto úseky nahradit kratšími kódy. Při pořizování zápisků to asi děláš úplně běžně. Asi nikdo nevypisuje pokaždé slovy celý název Svatá říše římská národa německého, stačí to jednou. Někdo nevypisuje ani slovo bitva, a vymyslí si místo toho nějaký kratší kód. Tenhle přístup (patřičně dopracovaný) je jedním ze základních algoritmů bezeztrátové komprese.
Shrnutí
Průměrnou výšku stromu(neboli délku zjišťování) počítáme po jednotlivých listech(neboli možnostech).
Znalost nemusí mít jen podobu absolutní jistoty o tom, co bude a co nebude. Může jít i o přibližný odhad četnosti výskytu jednotlivých možností. Těmto četnostem je pak možné se přizpůsobit a dosáhnout lepších výsledků, než s obecnými neinformovanými postupy (např. půlení intervalů).
Při různých četnostech možností obecně využíváme zásadu „Co potřebuji často, chci mít po ruce“. Sestavování stromu vylepšímeVýsledné stromy budou lepší než bez úpravy, ovšem nikoliv nejlepší možné. úpravou půlení: nebudeme dělit možnosti podle jejich počtu, ale podle četností jejich výskytu.
Totéž platí pro kódování. Co se vyskytuje často, zaslouží si kratší kód. Hledání vhodného zakódování je analogické hledání vhodného rozhodovacího stromu. Kódovaná slova dělíme na skupiny s přibližně stejnou celkovou četností, každé skupině přiřadíme jiný kódovací znak a dál obdobně dělíme menší a menší skupiny, dokud nemáme daný kód pro každé slovo.
