The wiki page is under active construction, expect bugs.

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:19] – [Situation Calculus] zapleka3statnice:bakalar:b4b36zui [2025/06/03 12:40] (current) – zapleka3
Line 65: Line 65:
  
   * **Akce**: $A = \{a_1, \dots, a_k\}$   * **Akce**: $A = \{a_1, \dots, a_k\}$
-  * **Odměny**: pro každé $a_i$ náhodná proměnná $r_t^{(i)} \sim \nu_i$ s očekáváním $\mu_i$+  * **Odměny**: pro každé $a_i$ náhodná proměnná $r_t^{(i)} \sim \nu_i$ s očekáváním $Q(a) = \mu_i$ 
   * **Očekávaná hodnota akce**:     * **Očekávaná hodnota akce**:  
     $$     $$
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 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)