---
tags: Specializace
---

# ML 1. Pravděpodobnost v informatice

*Diskrétní a spojitý pravděpodobnostní prostor. Náhodná proměnná a její použití. Střední hodnota, rozptyl. Náhodné procesy, Markovovy řetězce. Teorie informace (entropie, vzájemná informace), teorie kódování (Huffmanovo kódování, kapacita chybových kanálů). (IV111 Probability in CS)*

---
slajdy předmětu: https://is.muni.cz/auth/el/fi/podzim2019/IV111/um/
- zdejší $\mathcal{A}$ je ve slajdech značeno jako $\mathscr{F}$ a $\Omega$ jako $S$

## Diskrétní a spojitý pravděpodobnostní prostor

**Náhodný pokus (Random experiment)**

- Teorie pravděpodobnosti se zabývá **náhodnými pokusy**, jejichž výsledek není jednoznačně určen počátečními podmínkami (výsledek nemůžeme deterministicky vypočítat).
- Příklad: hod kostkou - nevíme dopředu, jaké číslo nám padne.

**Prostor elementárních jevů / Základní / Výběrový prostor (Sample space)**

- Neprázdná množina všech možných "nejelementárnějších" výsledků daného pokusu.

- Značení: $\Omega, S, ...$

- Příklad: hod kostkou.

- $\Omega = \{1, 2, 3, 4, 5, 6\}$ ... prostor elementárních jevů

$1, 2, 3, 4, 5 ,6$ ... elementární jevy $\omega \in \Omega$

**Jevy (Events)**

- Jev náhodného pokusu s prostorem elementárních jevů $\Omega$ je **jakákoliv podmnožina** tj. $A \subseteq\Omega$.

- Značení: $A, B, C, ...$, případně pro čitelnost celá slova např. sudá čísla na kostce - $Even$

- $\emptyset$ ... **nemožný** (null) jev

$\Omega$ ... **jistý** (universal) jev

- Příklad: hod kostkou.

- $\Omega = \{1, 2, 3, 4, 5, 6\}$

- jev $Even$ označuje padnutí sudého čísla, takže $Even = \{2, 4, 6\}$

- **Vztahy mezi jevy**

- $C = A \cup B$ (případně $A \vee B)$... jev $C$ nastane, pokud nastane jev A **nebo** jev B
- jevy $A_{1}, A_{2}, ..., A_{n}$ jsou **collectively exhaustive (tvoří úplný systém)** pokud platí: $A_{1} \cup A_{2} \cdots \cup A_{n}=\Omega$
- $C = A \cap B$ (případně $A \wedge B)$... jev $C$ nastane, pokud společně nastane jev $A$ **a zároveň** jev $B$

- Pokud $A \cap B = \emptyset$, pak jevy $A$ a $B$ jsou **neslučitelné (mutually exclusive, disjoint)**

- $\bar{A} = \Omega \setminus A = \{\omega \in \Omega \mid \omega \notin A \}$ ... jev $\bar{A}$ je **opačný (complementary, negative)** k jevu $A$

případně se i označuje jako $A^c, \neg A$

- **Nad jevy platí tyto vlastnosti**

- Všechno se dá pěkně ukázat na Vennových diagramech (TODO: přidat obrázek možná)
- **Komutativita**
- $A \cup B = B \cup A$
- **Asociativita**
- $A \cup (B \cup C) = (A \cup B) \cup C$
- $A \cap (B \cap C) = (A \cap B) \cap C$
- **Distributivita**
- $A \cup (B \cap C) = (A \cup B) \cap(A \cup C)$
- $A \cap (B \cup C) = (A \cap B) \cup(A \cap C)$
- **Identita**
- $A \cup \emptyset = A$
- $A \cap \Omega = A$
- **Komplement**
- $A \cup \bar{A} = \Omega$
- $A \cap \bar{A} = \emptyset$
- **De Morganovy zákony**
- $(\overline{A \cup C} )= \bar{A} \cap \bar{C}$
- $(\overline{A \cap C} )= \bar{A} \cup \bar{C}$

**Pravděpodobnostní funkce $P$**

- Pravděpodobnost je funkce $P: \mathcal{A} \rightarrow [0, 1]$ definovaná nad výběrovým prostorem $\Omega$ a množině všech jevů $\mathcal{A} = 2^{\Omega}$, pro kterou platí:

- $P(\Omega) = 1$

- Pro každou konečnou posloupnost náhodných jevů $A_1, A_2, ...$, které jsou **po dvou neslučitelné** (tj. $A_i \cap A_j = \emptyset$ pro každé dvě dvojice $i,j$) platí

$$
P(\bigcup\limits_{n=1}^{\infty} A_{n}) =\sum\limits_{n=1}^{\infty} P(A_{n})
$$

- Dále platí:
- $P(\overline{A}) = 1 - P(A)$
- $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ pro libovolné jevy $A,B$ (princip **inkluze a exkluze**)
- Odečítáme $P(A \cap B)$, protože se v $P(A)$ a $P(B)$ můžou jevy překrývat a sečteme je tím pádem dvakrát (viz Vennovy diagramy)

**Diskrétní pravděpodobnostní prostor**

- Diskrétní pravděpodobnostní prostor je trojice $(\Omega, \mathcal{A}, P)$, kde
- $\Omega$ ... výběrový prostor
- $\mathcal{A} = 2^{\Omega}$ ... množina všech jevů
- $P: \mathcal{A} \rightarrow [0,1 ]$ je pravděpodobnostní funkce

**Spojitý pravděpodobnostní prostor**

- U spojitého výběrového prostoru je $\mathcal{A}=2^{\Omega}$ příliš velké. Nejsme schopni přiřadit pravděpodobnosti pro každý prvek $\mathcal{A}$.
- Použijeme proto $\mathcal{A} \subseteq 2^{\Omega}$. $\mathcal{A}$ nazýváme **jevovou** $\sigma$-**algebru nad** $\Omega$ pokud
- $\emptyset \in \mathcal{A}$
- $A \in \mathcal{A} \Rightarrow \bar{A} \in \mathcal{A}$ (je uzavřená na doplněk)
- $A_1, A_2,... \in \mathcal{A} \Rightarrow\bigcup\limits_{n=1}^{\infty} A_{n} \in A$ (je uzavřená na spočetná sjednocení)
- Pak **(spojitý) pravděpodobnostní prostor** je trojice $(\Omega, \mathcal{A}, P)$, kde
- $\Omega$ ... výběrový prostor
- $\mathcal{A} \subseteq 2^{\Omega}$ ... jevová $\sigma$-agebra; spolu s $\Omega$ máme jevové pole reprezentující "povolené" jevy
- $P: \mathcal{A} \rightarrow [0,1 ]$ je pravděpodobnostní funkce

#### TODO?
- Conditional probability (používá se u teorie informace)
- Independent events
- Law of total probability
---

## Náhodná proměnná a její použití

### Diskrétní náhodná proměnná (veličina)

- Diskrétní <b>náhodná proměnná</b> X definovaná nad $\Omega$ je funkce $X:\Omega \rightarrow \mathbb{R}$, která přiřazuje každému elementárnímu jevu $\omega \in \Omega$ reálnou hodnotu $X(\omega)$.
- Náhodná proměnná nám umožní vytvořit její <b>obraz</b> $\Leftrightarrow^{def}$ $lm(X)=\{X(\omega)| \omega \in \Omega \}$ -- tedy převede nám eventy na její číselné reprezentace, se kterými se bude matematicky lépe pracovat.
- Ale abychom měli i zpětnou referenci potřebujeme mapování zpátky. Tedy pro náhodnou proměnnou X a reálné číslo x definujeme <b>inverzní obraz</b> eventu {x}:
$[X=x]=\{\omega \in \Omega | X(\omega) = x \}$
- Těmito definicemi jsme propojili universum $\Omega$ se světem matematickým.

#### Pravděpodobnostní funkce

- Pravděpodobnostní funkce náhodné proměnné $X$ je funkce

$p_X(x) = P(X = x) = \sum\limits_{\omega: X(\omega) = x} P(\omega)$

- Splňuje

- $0 \leq p_X(x)\leq 1$ pro všechna $x \in \mathbb{R}$
- $\sum\limits_{x \in \text{Im}(X)} p(x) = 1$

#### Distribuční funkce

- Distribuční funkce diskrétní náhodné proměnné $X$ je funkce $F_X: \mathbb{R} \rightarrow [0,1]$ dána vztahem
$$
F_X(x) = P(X \leq x) = \sum\limits_{t \leq x} p_X(t)
$$

- Vlastnosti
- $F$ je neklesající
- $F$ je zprava spojitá
- $\lim\limits_{x \to \infty} F(x) = 1$ a $\lim\limits_{x \to -\infty} F(x) = 0$
- $0 \leq F(x) \leq 1$ pro $x \in \mathbb{R}$

#### Příklady diskrétních rozdělění (probability distributions)

- Uniformní (pravděpodobnost $\dfrac{1}{n}$ pro každý z $n$ samples)
- Bernoulli (trial)
- Alternativní ($X$ nabývá buď 0 nebo 1)
- Binomické (počet úspěchů v $n$ pokusech, pokud $n=1$ tak je to alternativní )
- Geometrické (počet neuspěchů před prvním úspěchem)
- Poissonovo (výskyt jevů za určitou jednotku času, prostoru, ...)

https://en.wikipedia.org/wiki/Joint_probability_distribution#Discrete_case

### Spojitá náhodná proměnná (veličina)

- Spojitá náhodná proměnná $X$ definovaná nad $(\Omega, \mathcal{A}, P)$ je funkce $X: \Omega \to \mathbb{R}$, která splňuje
$$
\{s \mid X(s) \leq r\} \in \mathcal{A} \text{ pro každé } r \in \mathbb{R}
$$

#### Distribuční funkce

- $F_X(x) = P(X \leq x)$

#### Hustota pravděpodobnosti

- Hustota pravděpodobnosti je funkce $f$, pro kterou platí
$$
F(x)=\int\limits_{-\infty}^x f(t) dt
$$

#### Příklady spojitých rozdělení

- Uniformní
- Normální
- Exponenciální

#### ToDo: Random vectors

---

## Střední hodnota $E(X)$

- Expected value, mean value, expectation, očekávaná hodnota, ...

###### Střední hodnota diskrétní náhodné proměnné $X$
- $$ E(X) = \sum\limits_{x \in lm(X)}x \cdot p(x)$$

###### Střední hodnota spojité náhodné proměnné $X$
- $$ E(X) = \int\limits_{-\infty}^{\infty} x \cdot f(x) dx $$

###### Vlastnosti

- $E(X+Y) = E(X)+E(Y)$ (Linearita střední hodnoty)
- 

- $E(cX) = cE(X)$

- Pokud jsou $X, Y$ nezávislé pak platí

$E(XY) = E(X) E(Y)$

- ToDo: Markov Inequality ???
---

## Rozptyl $D(X)\text{ ; }\sigma^2(X)\text{ ; } S^2(X)$

###### $k$-tý obecný moment

- $E(X^k)$

###### $k$-tý centrální moment

- $\mu_k = E([X-E(X)]^k)$

**Rozptyl** je druhým centrálním momentem.

- $Var(X) = E[(X-E(X))^2] = E(X^2) - [E(X)]^2$
- Rozptyl taky znám jako variance, disperze, ...
- Charakterizuje **variabilitu** rozdělení pravděpodobnosti.
- Všimněme si, že $E[(X-E(X))^2]$ vyjadřuje "průměrný rozdíl (kvadratická chyba) od průměru $X$".

###### Směrodatná odchylka

- $\sigma = \sqrt{Var(X)}$

###### Vlastnosti rozptylu

- $Var(aX + b) = a^2 Var(X)$
- 

- $Var(X) = E(X^{2}) - E(X)^{2}$
- 

- $Var(X \pm Y) = Var(X) + Var(Y) + 2 Cov(X, Y)$, kde $Cov(X, Y)$ je **kovariance** (míra lineární závislosti dvou veličin).

- $Cov(X, Y) = E[(X - E[X]) (Y - E[Y])]$

Pokud jsou $X, Y$ **nezávislé**, pak je kovariance **nulová**.

??TODO dukazy na kovarianci?

---

## Náhodné procesy a Markovovy řetězce

### Náhodné stochastické procesy

- *Náhodný proces* je množina náhodných veličin $X = \{X_t \mid t \in T\}$. Index $t$ zpravidla označuje *čas*. $X_t$ se nazývá *stav* $X$ v čase $t$.
- $T$ může být:
- spočetné (proces s diskrétním časem);
- nespočetné (proces se spojitým časem).
- Množina hodnot $X_t$ nabývá hodnot:
- diskrétní hodnoty (proces s diskrétními stavy);
- spojité hodnoty (proces se spojitými stavy).

### Markovův řetězec

- Náhodný proces s diskrétním časem $\{X_0, X_1, X_2, ...\}$ se nazývá *Markovův řetězec* pokud platí:
$$
P(\color{red}{X_t = a \mid X_{t-1} = b}, X_{t-2}=a_{t-2},...,X_0=a_0) = P(\color{Red}{X_t=a \mid X_{t-1}=b}) = p_{b,a}
$$

- Hodnota $X_t$ závisí pouze na hodnotě $X_{t-1}$ (**markovovská/memoryless vlastnost**).
- Hodnota $X_t$ nezávisí na $t$ (homogenní Markovův řetězec). Můžeme tedy nakreslit Markovův řetězec jako konečný automat.


#### Matice přechodu

- Pravděpodobnosti přechodů v Markovovém řetězci můžeme definovat jednokrokovou maticí přechodu.
- $i$-tý řádek a $j$-tý sloupec označuje pravděpodobnost přechodu ze stavu $i$ do stavu $j$ tj.
$$
p_{i,j} = P(X_t = j \mid X_{t-1} = i)
$$

- Pro každý stav $i$ platí $\sum\limits_{j \geq 0} p_{i,j} = 1$. Tj. součet všech pravděpodobností skoků z každého stavu musí dávat 1.

### Markovův řetězec - pokračování
-slajdy https://is.muni.cz/auth/el/fi/podzim2019/IV111/um/IV111_06and07_handout.pdf
- todo: sample space of Markov chain
#### Matice přechodu
- $\vec{\lambda}(t) = (\vec{\lambda}_{1}(t), \vec{\lambda}_{2}(t)...)$ označuje pravděpodobnostní distribuci ve stavech v čase $t$
- $\vec{\lambda}(0)$ ... distribuce jak začínáme
- $\lambda_{i}(t)=P(X_{t}=i)$ ... pravděpodobnost že v čase $t$ jsme v stavu $i$
- $\vec{\lambda}(0)P=\vec{\lambda}(1)$ ... pravděpodobnostní distribuci v dalším kroku získáme vynásobením distribuce momentálního kroku a matice přechodu
- $m$-step matice prechodu označuje pravděpodobnost že se pohneme ze stavu $i$ do stavu $j$ přesně v $m$-krocích
- $p_{i,j}^{(m)} = P(X_{t+m} = j \mid X_{t} = i)$ ... pravděpodobnost že se pohneme z $i$ do $j$ přesně v $m$-krocích
- $\vec{\lambda}(t+m) = \vec{\lambda}(t)P^{m}$ ... výpočet distibuce v čase $t+m$. Pokud nás zajímá z $i$ do $j$ v 5tém kroku, můžeme udělat $\vec{\lambda}(5) = \vec{\lambda(0)}P^{5}$ a vzít hodnotu z výsledné matice na indexech $[i,j]$.
#### Dosažitelnost a hitting time
- Hitting time - každému stavu přiřadíme číslo, které značí minimální dobu za kterou se z něj dostaneme do některého prvku z $A$.
- pravděpodobnost navštívení některého stavu z $A$ pokud začneme v $i$ - použijeme podmíněnou pravděpodobnost
- průměrný čas než se dostaneme do $A$ z $i$ - použijeme expected value. Pokud se někde zacyklíme, je to hned infinity.
#### Markov chain analysis

- Absorbující stav - stav ze kterého se nemužeme dostat jakmile do něj vkročíme $p_{i,i}=1$
- rekurentní stav - pokud v něm začneme, nakonec se do něj někdy vrátíme s pravděpodobností 1 - buď je navštíven 0x nebo nekonečno krát ($P(i=>^{+}i)=1$)
- transientní (non-rekurentní) - je šance že se do něj nikdy nevrátíme $P(i=>^{+}i)<1$ - Skoro určitě je navštíven konečně-krát
- 
- stationary distribution
- 
- může existovat více stacionárních distribucí
- pokud je markov chain irreducible, má unikátní stacionární distribuci
- Stacionární distribuci můžeme spočítat jako $\vec{\lambda} P = \vec{\lambda}$
- 
- 
- perodický stav = dostanu se do něj znova vždy jen po $n*\Delta , n\in \mathbb{N}$ krocích

#### Continuous markov chains
- slajdy https://is.muni.cz/auth/el/fi/podzim2019/IV111/um/IV111_08_handout.pdf
- ve stavu čekáme na eventy, jakmile se vyskytne, změníme stav
- $\lambda$ ...rate parametr
- 
- 
- 
- náhodná proměnná $X_{1}$ označuje dobu než se vyskytne event 1
- waiting time
- mean waiting time na event s rate $\lambda$ je $\dfrac{1}{\lambda}$
- probability that $X_{1}$ wins: $P(X_{1}<X_{2}) = \dfrac{\lambda_{1}}{\lambda_{1}+\lambda_{2}}$
- 
- TODO uniformizace - doplnění exit rates na 1 tím že přidáme self loop, normalizováno největším exit ratem v celém markovově řetězci?

## Teorie informace (entropie, vzájemná informace)
slajdy: https://is.muni.cz/auth/el/fi/podzim2019/IV111/um/IV111_09_handout.pdf

### Entropy
- pro tuto funkci platí axiomy
- $H(1 / 2,1 / 2)=1$
- $H(p, 1-p)$ is a continuous function of $p$
- $H\left(p_{1}, \ldots, p_{m}\right)=H\left(p_{1}+p_{2}, p_{3}, \ldots, p_{m}\right)+\left(p_{1}+p_{2}\right) H\left(\frac{p_{1}}{p_{1}+p_{2}}, \frac{p_{2}}{p_{1}+p_{2}}\right)$
- $H(X) = -\sum\limits_{x \in \text{Im}(X)}p_X(x) \cdot \log{p_X(x)}$
- $H(X) = E\left[\log{\dfrac{1}{p(x)}}\right] = - E[\log p(x)]$
- v definici se používá konvence 0 log 0 = 0, odůvodněná $\lim _{x \rightarrow 0^{+}} x \cdot \log x=0$ ; případně se dá sčítat pouze přes nenulové pravděpodobnosti
- entropie je vždy nezáporná, $H(X) \geq 0$

#### Joint Entropy
- entropie páru (nebo n-tice) náhodných veličin
- joint entropy popisuje entropii náhodných experimentů, které jsou popsatelné korelovanými náhodnými veličinami

#### Conditional Entropy

$H(X \mid Y=y)=-\sum_{x \in \operatorname{lm}(X)} P(X=x \mid Y=y) \log P(X=x \mid Y=y)$
- vyjadřuje nejistotu o hodnotě náhodné proměnné $X$ za předpokladu, že je dána hodnota $y$ náhodné proměnné $Y$, tedy $Y=y$


- jaké množství infromace průměrně získáme o $X$ když je daná hodnota náh. prom. $Y$. To můžeme výjádřit jako snížení nejistoty ohledně $X$ když zjistíme hodnotu $Y$, tedy $H(X) - H(X|Y)$
- analogicky, množství informace, které získáme když se dozvíme hodnotu $X$ je $H(X)$

- TODO proof?
- obecně $H(Y \mid X) \neq H(X \mid Y)$

### Mutual information
- Relative entropy měří jak se jedno rozdělení pravděpodobnosti (pravděpodobnostní funkce) liší od druhého.
- infficiency of assuming that a given distribution is q(x) when the true distribution os p(x)
- v definici se používá konvence $0 \log \frac{0}{q}=0$ a $p \log \frac{p}{0}=\infty$
- $D(p||q) \geq 0$
- $D(p||q) = 0$ pokud $p(x) = q(x)$
- není symetrická, tedy není to vzdálenost v matematickém kontextu

- měří množství informací, které jedna náhodná veličina obsahuje o druhé náhodné veličině
- měří snížení nejistoty o hodnotě náhodné veličiny, když je dána hodnota jiné náhodné veličiny
- Mutual information nezávislých náhodných veličin je 0
- "o kolik se ti zmenší entropie X, když znáš Y"
- důkaz
- 
- je symetrická: $H(X)-H(X \mid Y)=H(Y)-H(Y \mid X)$, tedy X "objasňuje" Y stejně jako Y .. X
- použitím $H(X, Y)=H(X)+H(Y \mid X)$ dostaneme:
- platí $I(X;X)=H(X)-H(X \mid X)=H(X)$

#### Další vlastnosti Entropy a Mutual infromation

První diagram je ilustrace k $I(X;Y) = H(X)-H(X|Y)$


To samé jako ten první obrázek, ale hezčeji :D

- General Chain Rule for Entropy
- todo důkaz

- Conditional Mutual Information

- ??? conditional mutual information, a conditional relative entropy ??? - budou to chtít?

### coding theory (Huffman coding, error channel capacity)
#### Huffman coding

##### Intuice
Huffman coding je algoritmus, který hledá optimální prefixový kódování.
Prefixové kódování je takové kódování, kde žádné kódové slovo není prefixem jiného kódového slova. A tedy je kód unikátně dekódovatelný (jednoznačný).

> Příkladem takového kódu může být: {('A','1'), ('B','10'), ('C', '110')}.

Huffman coding funguje tak, že přiřadí nejméně pravděpodobným (frekventovaným) hodnotám x náhodné proměnné X nejdelší kódová slova a naopak.

- Zde je huffman coding algoritmus vysvětlen a zobrazen velice dobře pomocí frekvence: https://www.youtube.com/watch?app=desktop&v=dM6us854Jk0&fbclid=IwAR37iUPFMfmGq2S7B5JcTmLJ7O-vf3Yoz3DFxeviW4kenL_FOLgHT4lsYS8

##### Definice
- slidy https://is.muni.cz/auth/el/fi/podzim2019/IV111/um/IV111_10and11_handout.pdf
- kód $C$ každé hodnotě $x$ náhodné proměnné přiřadí kódové slovo (třeba 1, 10, 110 atd..) s délkou $l_{C}(x)$
- 
- nonsingulární kód zakóduje každou unikátní hodnotu na unikátní kódové slovo
- 
- 
- prefix code - je unikátně dekodovatelný kód
- 
- kraft inequality + mc milan?
- minimální délka prefix kódu
- huffman code=optimal prefix code
- we have to add some redundant imput symbols so the number of symbols is $1+k(d-1)$ for some k (d is arity, binary code has d=2 etc...)
- https://people.ok.ubc.ca/ylucet/DS/Huffman.html
- https://opendsa-server.cs.vt.edu/OpenDSA/AV/Binary/huffmanBuildAV.html
- 
- 
- Properties of optimal prefix codes
- 
- čím menší pravděpodobnost má $x_{i}$ tím delší (nebo stejnou) má délku slova
- huffman optimality proof viz slidy

#### error channel capacity
- 
- M-n kód - enkodér je definovaný pro M znaků, každý z nich enkóduje na N znaků (délka zakódovaného slova je N). Těchto N znaků pošleme kanálem a dekodér dostane zase N znaků, které pak dekóduje na nějaký z M prvků.
- 
- - f(0) = 000, f(1) = 111... 2-3 kód, protože je definovaný pro 2 znaky a délka zakódovaného slova je 3
- 
- 
- 
- 
- intuitivně - kapacita je noiseless throughput of the channel
- určuje highest rate (počet bitů na kanál) kterou může být přenesena informace s libovolně malou chybou
- 
- příklady na channel capacity 4.26 4.27 https://is.muni.cz/auth/el/fi/podzim2019/IV111/um/IV111_exercises_for_tutorials.pdf