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:44] – [STRIPS] zapleka3statnice: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 914: 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 924: 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 950: 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 989: 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 1008: 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 1016: 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 1024: 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)