Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b36zui [2025/06/03 11:20] – [Problém mnohorukého banditu (Multi-Armed Bandit, MAB)] mistrjirkastatnice:bakalar:b4b36zui [2026/05/29 15:25] (current) – [Policy Improvement] knedl1k
Line 351: Line 351:
   * Příliš silná heuristika (např. $h(n) > h^*(n)$) může zrychlit výpočet, ale ztrácí optimálnost.   * Příliš silná heuristika (např. $h(n) > h^*(n)$) může zrychlit výpočet, ale ztrácí optimálnost.
  
-====== 4. Algoritmy posilovaného učení ======+===== 4. Algoritmy posilovaného učení =====
  
 **policy evaluation, policy improvement, policy iteration, value iteration, Q-learning** **policy evaluation, policy improvement, policy iteration, value iteration, Q-learning**
Line 401: Line 401:
  
 $$ $$
-\pi'(s) = \arg\max_{a}\sum_{s'} P(s'|s,a),\bigl[R(s,a,s') + \gamma V^\pi(s')\bigr].+\pi'(s) = \arg\max_{a}\sum_{s'} P(s'|s,a)\bigl[R(s,a,s') + \gamma V^\pi(s')\bigr].
 $$ $$
  
Line 458: Line 458:
  
 $$ $$
-V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a),\bigl[R(s,a,s') + \gamma V_k(s')\bigr].+V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V_k(s')\right].
 $$ $$
  
Line 464: Line 464:
  
 $$ $$
-\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a),\bigl[R(s,a,s') + \gamma V(s')\bigr].+\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)\bigl[R(s,a,s') + \gamma V(s')\bigr].
 $$ $$
  
Line 635: Line 635:
     * Hry s nulovým součtem, kde jsou hodnoty pro oba hráče přesně opačné.     * Hry s nulovým součtem, kde jsou hodnoty pro oba hráče přesně opačné.
  
-==== Negascout (Principal Variation Search, PVS) ====+==== NegaScout (Principal Variation Search, PVS) ====
  
 Další vylepšení algoritmu Alpha-Beta (resp. Negamax), které využívá předpoklad, že akce jsou předem dobře seřazené (např. pomocí heuristiky). Tím výrazně urychluje prohledávání. Další vylepšení algoritmu Alpha-Beta (resp. Negamax), které využívá předpoklad, že akce jsou předem dobře seřazené (např. pomocí heuristiky). Tím výrazně urychluje prohledávání.
Line 840: Line 840:
 ==== STRIPS ==== ==== STRIPS ====
  
-STRIPS (Stanford Research Institute Problem Solver) je formalismus pro reprezentaci plánovacích problémů. Každá akce má:+**STRIPS (Stanford Research Institute Problem Solver)** je formalismus pro reprezentaci plánovacích problémů ve formální logice. Byl původně vyvinut pro robota Shakey. 
 + 
 +=== Formální definice === 
 + 
 +STRIPS problém je definován čtveřicí **(P, A, I, G)**, kde: 
 +  * **P** je množina všech atomických predikátů (např. `At(Robot, Room1)`) – booleovské proměnné 
 +  * **A** je množina všech akcí, každá ve tvaru `a = ⟨pre(a), add(a), del(a)⟩`: 
 +    * `pre(a)` – předpoklady, které musí být splněny pro použití akce 
 +    * `add(a)` – predikáty, které po akci začnou platit 
 +    * `del(a)` – predikáty, které po akci přestanou platit 
 +  * **I** je počáteční stav – množina predikátů platných na začátku 
 +  * **G** je cílový stav – množina predikátů, které chceme dosáhnout 
 + 
 +Každá akce má:
  
   * **Preconditions**: podmínky pro použití akce   * **Preconditions**: podmínky pro použití akce
Line 856: Line 869:
 </code> </code>
  
-Cílem je najít posloupnost akcí, která převede výchozí stav na cílový (např. Robot je v místnosti C).+=== Cíl plánování === 
 + 
 +Cílem je najít posloupnost akcí `a₁, a₂, ..., aₖ`, která při aplikaci na počáteční stav `I` postupně převede systém do stavu, kde `G ⊆ sₖ`. 
 + 
 +=== Řešení pomocí A* === 
 + 
 +STRIPS problémy lze řešit algoritmem **A***, kde: 
 +  * **stav** je aktuální množina pravdivých predikátů 
 +  *  **heuristika** může být například `h(s) = |G \ s|` – počet cílů, které ještě nejsou splněny 
 + 
 +=== Heuristiky a relaxace === 
 + 
 +  * **Relaxace problému**: ignorujeme `del(a)`, tedy předpokládáme, že akce nic neodstraňují 
 +    * Relaxovaná akce: `a⁺ = ⟨pre(a), add(a), ∅⟩` 
 +  * **Abstrakce**: např. odstranění některých predikátů nebo predikátové argumenty zjednodušíme 
 + 
 +=== Plánovací graf (relaxovaný plánovací graf) === 
 + 
 +Graf dosažitelnosti: 
 +  * Střídají se úrovně predikátů `Pᵢ` a akcí `Aᵢ` 
 +  * `Aᵢ = {a ∈ A | pre(a) ⊆ Pᵢ}` 
 +  * `Pᵢ₊₁ = Pᵢ ∪ {p ∈ add(a) | a ∈ Aᵢ}` 
 +  * Konstrukce končí, pokud `G ⊆ Pᵢ` 
 + 
 +Stejný graf se dá použít k výpočtu optimální heuristiky hmax  
 +  * Vrchol, který náleží počátečnímu stavu se inicializuje na nulu  
 +  * Všechny vrcholy s akcemi jsou pak rovny maximu hodnot z předpokladů dané akce  
 +  * Do vrcholů se stavy (propozicemi) se pak zapíše nejlevnější akce, která do daného stavu vedla 
 + 
 +{{:statnice:bakalar:pasted:20250603-113233.png?400}}
  
 ===== 7. Neurčitost v AI ===== ===== 7. Neurčitost v AI =====
Line 872: Line 914:
 $$ $$
  
-kde: - $H$ je hypotéza, - $D$ jsou data, - $P(H|D)$ je posteriorní pravděpodobnost, - $P(D|H)$ je pravděpodobnost dat za předpokladu platnosti hypotézy (likelihood), - $P(H)$ je apriorní pravděpodobnost hypotézy, - $P(D)$ je marginální pravděpodobnost dat.+kde: 
 +  * $H$ – hypotéza, 
 +  * $D$ – pozorovaná data, 
 +  * $P(H|D)$ – posteriorní pravděpodobnost, 
 +  * $P(D|H)$ – pravděpodobnost dat za předpokladu hypotézy (likelihood), 
 +  * $P(H)$ – apriorní pravděpodobnost hypotézy, 
 +  * $P(D)$ – celková pravděpodobnost dat (normalizační konstanta).
  
 ==== Maximalizace očekávané utility ==== ==== Maximalizace očekávané utility ====
  
-Cílem rozhodování pod neurčitostí je zvolit akci, která maximalizuje očekávanou užitečnost:+Racionální agent by měl volit takovou akci, která maximalizuje **očekávanou užitečnost**:
  
 $$ $$
Line 882: Line 930:
 $$ $$
  
-kde: - $a$ je akce, - $s$ je možný stav světa, - $P(s|a)$ je pravděpodobnost stavu $s$ za předpokladu akce $a$, - $U(s,a)$ je užitečnost akce $a$ ve stavu $s$.+kde: 
 +  * $a$ – akce, 
 +  * $s$ – možný stav světa, 
 +  * $P(s|a)$ – pravděpodobnost stavu $s$ po provedení akce $a$, 
 +  * $U(s,a)$ – užitečnost výsledného stavu $s$ při akci $a$. 
 + 
 +Používá se v rozhodovacích sítích a obecně ve všech situacích, kde je třeba rozhodovat pod neurčitostí.
  
 ==== Bayesovské sítě ==== ==== Bayesovské sítě ====
  
-Bayesovské sítě (též grafické modely) jsou orientované acyklické grafy, ve kterých: - vrcholy reprezentují náhodné proměnné, - hrany reprezentují podmíněné závislosti mezi proměnnými, - každá proměnná má přidruženou podmíněnou pravděpodobnostní tabulku (CPT).+Bayesovské sítě jsou **orientované acyklické grafy (DAG)**, kde: 
 +  * uzly reprezentují náhodné proměnné, 
 +  * hrany vyjadřují podmíněnou závislost (rodič ovlivňuje potomka), 
 +  * každá proměnná má tabulku podmíněných pravděpodobností (CPT).
  
-Sítě umožňují efektivní reprezentaci a výpočet složitých pravděpodobnostních modelů a jsou základem pro inferenci (zjištění pravděpodobností nepozorovaných proměnných) a rozhodování.+Bayesovské sítě umožňují efektivní inferenci, tj. výpočet pravděpodobností nepozorovaných proměnných. 
 + 
 +**Celková distribuční pravděpodobnost** v síti se rozpadá podle struktury grafu: 
 + 
 +$$ 
 +P(X_1, ..., X_n) = \prod_{i=1}^{n} P(X_i \mid \text{rodiče}(X_i)) 
 +$$
  
 === Příklad Bayesovské sítě === === Příklad Bayesovské sítě ===
Line 908: Line 971:
 \end{document} \end{document}
 </tikzjax> </tikzjax>
 +
 Tato Bayesovská síť ilustruje následující závislosti mezi náhodnými proměnnými: Tato Bayesovská síť ilustruje následující závislosti mezi náhodnými proměnnými:
  
Line 947: Line 1011:
 $$ $$
  
-Použití: - textová klasifikace (spam, sentiment), - diagnostika v medicíně, - doporučovací systémy. +**Použití:** 
- +  * detekce spamu, 
 +  * analýza sentimentu, 
 +  * lékařská diagnostika.
  
 ==== Skrytý Markovův model (Hidden Markov Model, HMM) ==== ==== Skrytý Markovův model (Hidden Markov Model, HMM) ====
Line 966: Line 1031:
 $$ $$
  
-Použití: - rozpoznávání řeči, - analýza časových řad, - strojový překlad, - sledování objektů.+**Algoritmy:** 
 +  * **Forward-backward** – výpočet marginálních pravděpodobností, 
 +  * **Viterbi** – nalezení nejpravděpodobnější sekvence skrytých stavů, 
 +  * **Baum-Welch** – EM algoritmus pro trénink HMM.
  
-Hlavní algoritmy: - **Forward-backward** (výpočet pravděpodobností), - **Viterbiho algoritmus** (nejpravděpodobnější posloupnost), - **Baum-Welch** (EM algoritmus pro trénink).+**Použití:** 
 +  * rozpoznávání řeči, 
 +  * strojový překlad, 
 +  * analýza časových řad, 
 +  * sledování objektů.
  
 ===== 8. Řešení POMDP ===== ===== 8. Řešení POMDP =====
Line 974: Line 1046:
 **PBVI, HSVI** **PBVI, HSVI**
  
-Řešení problémů částečně pozorovatelných Markovových rozhodovacích procesů (POMDP) spočívá v nalezení optimální politiky, která maximalizuje očekávaný výnos na základě neúplné informace o stavu systému. V POMDP je totiž skutečný stav systému skrytý (latentní) a rozhodnutí je činěno na základě tzv. věrohodnostního rozdělení (belief state) – pravděpodobnostního rozdělení přes možné stavy daného systému.+==== Řešení POMDP ====
  
-POMDP je formálně definován jako sedmice $⟨S, A, T, R, Ω, O, \gamma⟩$, kde: - $S$ je množina stavů, - $A$ je množina akcí, - $T(s'|s,a)$ je přechodová pravděpodobnost, - $R(s,a)$ je funkce odměny, - $Ω$ je množina možných pozorování, - $O(o|s',a)$ je pravděpodobnost pozorování $o$ po provedení akce $a$ a přechodu do stavu $s'$, - $\gamma$ je diskontní faktor.+**Řešení částečně pozorovatelných Markovových rozhodovacích procesů (POMDP)** spočívá v nalezení optimální politiky na základě neúplné informace o stavu systému. V POMDP není stav přímo pozorovatelný – rozhodování se děje na základě tzv. **belief state** – pravděpodobnostního rozdělení přes možné stavy. 
 + 
 +=== Formální definice === 
 + 
 +POMDP je definován jako sedmice **⟨S, A, T, R, Ω, O, γ⟩**, kde: 
 +  * **S** – množina stavů 
 +  * **A** – množina akcí 
 +  * **T(s'|s,a)** – přechodová pravděpodobnost 
 +  * **R(s,a)** – odměnová funkce 
 +  * **Ω** – množina pozorování 
 +  * **O(o|s',a)** – pravděpodobnost pozorování $o$ po akci $a$ a přechodu do stavu $s'$ 
 +  * **γ** – diskontní faktor 
 + 
 +Hodnotová funkce je definovaná nad belief space a je konvexní. Přesné řešení je výpočetně náročné, proto používáme aproximační algoritmy. 
 + 
 +Řešení problémů částečně pozorovatelných Markovových rozhodovacích procesů (POMDP) spočívá v nalezení optimální politiky, která maximalizuje očekávaný výnos na základě neúplné informace o stavu systému. V POMDP je totiž skutečný stav systému skrytý (latentní) a rozhodnutí je činěno na základě tzv. věrohodnostního rozdělení (belief state) – pravděpodobnostního rozdělení přes možné stavy daného systému.
  
 Hodnotová funkce pro POMDP je definována nad věrohodnostními stavy a je konvexní. Přesné řešení POMDP je výpočetně neproveditelné pro větší problémy, proto se používají aproximační metody. Mezi ně patří: Hodnotová funkce pro POMDP je definována nad věrohodnostními stavy a je konvexní. Přesné řešení POMDP je výpočetně neproveditelné pro větší problémy, proto se používají aproximační metody. Mezi ně patří:
Line 982: Line 1069:
 ==== Point-Based Value Iteration (PBVI) ==== ==== Point-Based Value Iteration (PBVI) ====
  
-PBVI aproximuje hodnotovou funkci výběrem reprezentativní množiny víry (belief points) $B = \{b_1, b_2, ..., b_n\}$, a iterativně aktualizuje hodnotovou funkci pouze v těchto bodech.+PBVI aproximuje hodnotovou funkci pouze v konečné množině **belief pointů** $B = \{b_1, b_2, ..., b_n\}$. Pro tyto body iterativně provádí Bellmanovy aktualizace:
  
-Algoritmus PBVI: 1. Inicializuj hodnotovou funkci $V_0$ jako nulovou. 2. Pro každou víru $b \in B$ prováděj: - $V_{i+1}(b) = \max_{a \in A} \left[ R(b, a) + \gamma \sum_{o \in Ω} P(o|b,a) V_i(b_{a,o}) \right]$, kde $b_{a,o}$ je aktualizovaná víra po akci $a$ a pozorování $o$.+1. Inicializace hodnotové funkce $V_0$. 
 +2. Iterace pro každý $b \in B$: 
 +$$ 
 +V_{i+1}(b) = \max_{a \in A} \left[ R(b, a) + \gamma \sum_{o \in Ω} P(o|b,a) \cdot V_i(b_{a,o}) \right]  
 +$$ 
 + 
 +  * $b_{a,o}$ je nová víra (belief) po akci $a$ a pozorování $o$ 
 +  * Hodnotová funkce se reprezentuje pomocí **α-vektorů**, které aproximují výnos pro jednotlivé akce a stavy
  
 Tímto způsobem PBVI konstruuje aproximaci optimality pomocí hodnotové funkce složené z tzv. $\alpha$-vektorů. Tímto způsobem PBVI konstruuje aproximaci optimality pomocí hodnotové funkce složené z tzv. $\alpha$-vektorů.
 +
 +PBVI výrazně zjednodušuje výpočet tím, že nepočítá hodnotu v celém belief prostoru.
  
 ==== Heuristic Search Value Iteration (HSVI) ==== ==== Heuristic Search Value Iteration (HSVI) ====
  
-HSVI je vylepšením PBVI, které využívá heuristické řízení výpočtu pro zlepšení efektivity. HSVI zachovává horní a dolní meze hodnotové funkce a iterativně je zpřesňuje pouze v místech, která ovlivňují politiku.+HSVI kombinuje heuristické řízení a aproximaci hodnotové funkce pomocí horní a dolní meze: 
 + 
 +1. **Inicializace:** 
 +   * Dolní mez $V^-$: jednoduché politiky (např. fixní akce) 
 +   * Horní mez $V^+$: řešení odpovídající plně pozorovatelnému MDP 
 + 
 +2. **Heuristické prohledávání:** 
 +   * Vybíráme beliefy, kde je největší rozdíl mezi $V^+$ a $V^-$ 
 +   * Průchod stromem víry (belief tree) řízený rozdílem mezi odhady 
 + 
 +3. **Update:** 
 +   * Dolní mez – přidání nových α-vektorů 
 +   * Horní mez – konvexní obálka a přepočet odhadu
  
 Algoritmus HSVI: 1. Udržuje dolní odhad $V^-$ a horní odhad $V^+$ hodnotové funkce. 2. Používá hloubkové prohledávání stromu víry řízené heuristikou k výběru větví, kde je největší rozdíl mezi $V^+$ a $V^-$. 3. Provádí zálohování hodnot a zpřesňuje odhady na cestě k listům stromu. Algoritmus HSVI: 1. Udržuje dolní odhad $V^-$ a horní odhad $V^+$ hodnotové funkce. 2. Používá hloubkové prohledávání stromu víry řízené heuristikou k výběru větví, kde je největší rozdíl mezi $V^+$ a $V^-$. 3. Provádí zálohování hodnot a zpřesňuje odhady na cestě k listům stromu.
 +
 +HSVI garantuje ε-optimalitu: algoritmus konverguje, když rozdíl mezi $V^+$ a $V^-$ je menší než dané ε.
 +
 +HSVI zachovává horní a dolní meze hodnotové funkce a iterativně je zpřesňuje pouze v místech, která ovlivňují politiku.
  
 HSVI kombinuje výpočetní efektivitu s garancemi na kvalitu aproximace: algoritmus konverguje k ε-optimální politice, pokud se rozdíl mezi horním a dolním odhadem zmenší pod ε. HSVI kombinuje výpočetní efektivitu s garancemi na kvalitu aproximace: algoritmus konverguje k ε-optimální politice, pokud se rozdíl mezi horním a dolním odhadem zmenší pod ε.

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b36zui (generated for current page)