Zkouška: kartičky | artificial-intelligence2

Introduction, Probability

rational agent

agent – perceives environment through sensors, acts upon environment through actuators
rational agent maximizes its expected performance measure
in AI 1 we used logical approach; we ignored uncertainty
- including interface between agent and environment
- we also ignored self-improvement capabilities

Introduction, Probability

uncertainty in pure logical approach

belief states
- instead of having state, we have a belief state (set of all possibilities that can be true)
drawbacks
- logical agent must consider every logically possible explanation for the observations (no matter how unlikely they are) → large and complex representations
- we need to consider arbitrary likely events – have a plan for any situation no matter how unlikely it is
- sometimes there's no plan which would guarantee the desired result (but the agent still has to act somehow)
practical problems (in medicine)
- laziness – it is too much work to list the complete set of antecedents or consequents and too hard to use such rules
- theoretical ignorance – medical science has no complete theory for the domain
- practical ignorance – even if we know all the rules, we may not be able run all the necessary tests
that's why we'll use another approach – probability theory

Introduction, Probability

probability

sample space = set of possible worlds $\Omega$ $Ω$
- $\forall\omega\in\Omega: 0\leq P(\omega)\leq 1$
- $\sum_{\omega\in\Omega} P(\omega)=1$
probability of event = sum of probabilities of possible worlds where the event occurs
- = unconditional/prior probabilities (priors)
conditional/posterior probability
- $P(a\mid b)=\frac{P(a\land b)}{P(b)}$ whenever $P(b)\gt 0$
- we take some information (evidence) into account
in a factored representation, a possible world is represented by a set of variable/value pairs
- every variable has a domain
- a possible world is fully identified by values of all random variables
probability of all possible worlds can be represented using a table called a full joint probability distribution
$\textbf{P}(\mathrm{Cavity})=\braket{0.2,0.8}$ $P (Cavity) = ⟨ 0.2, 0.8 ⟩$
- Cavity = true → 0.2
- Cavity = false → 0.8
inclusion-exclusion principle
- $P(a\lor b)=P(a)+P(b)-P(a\land b)$

Introduction, Probability

practicality of full joint probability distribution

we can do inference by summing up certain cells of the full joint distribution table (= marginalization)
using normalization constant $\alpha$ may be helpful
drawbacks of inference by enumeration
- worst-case complexity $O(d^n)$ where $d$ is number of values in domains of each variable
- we need the same space to store the full joint distribution
adding another variable – weather
- does not influence tooth problems (is independent) → we add another table
- we can represent the resulting joint distribution using two tables
- conditional independence can be exploited to further reduce the size of representation (instead of one large table, we use several smaller tables)
also, we don't need to store the entire table (probabilities add up to one)

Introduction, Probability

usually, we are interested in the diagnostic direction P(disease | symptoms)

but we know P(disease), P(symptoms), and P(symptoms | disease) … causal direction
we use Bayes' rule to get the diagnostic direction
it may be better not to store the diagnostic direction as the original probabilities (we base the calculation upon) may change

Introduction, Probability

Bayes’ rule

$P(Y\mid X)=\frac{P(X\mid Y)P(Y)}{P(X)}=\alpha P(X\mid Y)P(Y)$
or $P(B_j\mid A)=\frac{P(A\mid B_j)P(B_j)}{\sum_i P(A\mid B_i)P(B_i)}=\alpha P(A\mid B_j)P(B_j)$

Introduction, Probability

naive Bayes model

generally, we can exploit conditional independence by ordering the variables properly
naive Bayes model – we assume independence
- $P(\text{Cause}, \text{Effect}_1, \dots, \text{Effect}_n) = P(\text{Cause})\prod_iP(\text{Effect}_i\mid\text{Cause})$

Bayesian Networks

Bayesian network

DAG; specifies conditional dependence among random variables
an efficient way to represent full joint probability distribution by exploiting conditional independence
nodes correspond to random variables, arcs describe the dependencies
CPT (conditional probability table) for each variable
- to get full joint distribution, we just multiply the tables
- autorem obrázku je Roman Barták
- proměnné jsou binární, proto má tabulka vždy jen jeden sloupec (druhý sloupec by mohl obsahovat pravděpodobnost, že jev nenastane – lze ho dopočítat z prvního sloupce)

Bayesian Networks

construction

we construct the network based on the selected order
usually, we want to use the causal direction (so that we know how to construct the CPTs; also the network will be smaller)
the arc should be there if there is a dependence between the variables
- for $X$ independent on $Y$ , it should hold that $P(X\mid Y,Z)=P(X\mid \neg Y,Z)=P(X\mid Z)$
příklad: MaryCalls, JohnCalls, Alarm, Burglary, Earthquake (záměrně jdeme od důsledků k příčinám, byť to není praktické)
- z MaryCalls povede hrana do JohnCalls, protože nejsou nezávislé (když volá Mary, tak je větší šance, že volá i John)
- z obou povede hrana do Alarmu
- z Alarmu vedou hrany do Burglary a Earthquake (ale hrany z JohnCalls a MarryCalls tam nepovedou – na těch hranách nezáleží, jsou nezávislé)
- z Burglary povede hrana do Earthquake, protože pokud zní alarm a k vloupání nedošlo, tak pravděpodobně došlo k zemětřesení
- akorát se nám v tomto pořadí budou špatně určovat CPT

Bayesian Networks

how much space can we save?

random variables are often influenced by only a few other variables
assume that each variable is directly influenced by at most $k$ other variables
then the size of representation is $n\cdot 2^k$ for Bayesian network vs. $2^n$ for full joint distribution
we can also ignore some slight dependencies – trade-off between accuracy and size of the network
we need to choose the correct ordering of variables

Bayesian Networks

conditional independence in Bayesian networks

node is conditionally independent of its non-descendants given its parents
node is conditionally independent of all other nodes given its parents, children, and children's parents
- Markov blanket = parents, children, children's parents
- M. blanket contains all the information needed to infer the value of the variable (other variables are redundant)

Bayesian Networks

exact inference (by enumeration)

using joint probability (we sum over hidden variables) + moving terms out of the sums if possible
- $P(X\mid e)=\alpha P(X,e)=\alpha\sum_y P(X,e,y)$
- kde pravděpodobnost $X$ odvozujeme, $e$ jsou pozorované proměnné (evidence) a $y$ jsou hodnoty další skryté proměnné $Y$
- přičemž $P(X,e,y)$ $P (X, e, y)$ lze určit pomocí CPD tabulek
  - když nemůžeme určit konkrétní hodnotu pravděpodobnosti přímo, tak výpočet rozvětvíme
  - některé větve se objeví vícekrát – hodí se nám dynamické programování
- příklad: $P(b\mid j,m)=\alpha\sum_e\sum_a P(b)P(e)P(a\mid b,e)P(j\mid a)P(m\mid a)$ $P (b ∣ j, m) = α \sum_{e} \sum_{a} P (b) P (e) P (a ∣ b, e) P (j ∣ a) P (m ∣ a)$
  - $=\alpha P(b)\sum_e P(e)\sum_a P(a\mid b,e) P(j\mid a)P(m\mid a)$
  - tohle můžeme přímo převést na výpočty s faktory
    - $P(a\mid b,e)$ odpovídá faktoru $f_3(A,B,E)$
    - $P(j\mid a)$ odpovídá faktoru $f_4(A)$ , protože hodnotu $j$ známe, tak ji můžeme zafixovat (faktor pak obsahuje tolik čísel, kolik je možných hodnot $A$ )
we can use factors (tables constructed from CPTs)
- multiplication: we can (pointwise) multiply the rows that have the same values of the shared variables
- elimination: we sum the rows that are almost the same (differ only in the value of the variable we want to eliminate)
- we construct the factors based on the evidence
- suggested ordering – eliminate the variables that would need large factors in the subsequent stages
complexity
- given by the size of the largest factor constructed
  - heuristic: eliminate whichever variable minimizes the size of the next factor to be constructed
- if Bayesian network is a polytree (corresponding undirected graph is a tree), then the time and space complexity is linear in the size of the network
  - size of the network = number of CPT entries … $O(nd^k)$
- 3SAT can be reduced to inference in the Bayesian networks so inference in Bayesian networks is NP-hard
- the problem is #P-hard (“number of satisfying assignments for a prop. logic formula”)

Bayesian Networks

approximate inference

Monte Carlo methods
direct sampling
- we are going through the Bayesian network in top-down order
- in each step, we sample one variable and then base further sampling on this choice
- this only provides us with the samples (but we want to infer the probabilities!)
rejection sampling
- we generate samples using direct sampling
- we eliminate the ones that don't correspond to the evidence
- we estimate $P(X\mid e)$ as the number of correct (not eliminated) samples divided by the number of all samples
- problem: we may reject too many samples
likelihood weighting
- instead of rejecting samples, we generate only the ones consistent with evidence $e$
- but then, we lose information about the probability of the specific piece of evidence (which may be dependent on the generated hidden variables)
- so we assign weights to the samples according to the probability of the evidence
- our arithmetic has to be precise enough
MCMC (Markov chain Monte Carlo)
- start with randomly generated sample consistent with evidence $e$
- for a selected variable $X$ (outside evidence), select a new value conditioned on the values of the variables in the Markov blanket
- we get a Markov chain
- Gibbs sampling
- sampling process settles into a dynamic equilibrium in which the long-term fraction of time spent in each state is exactly proportional to its posterior probability
- why it works
  - for stationary distribution we require $\pi(x')=\sum_x \pi(x) q(x\to x')$
  - this holds when $\pi(x) q(x\to x')=\pi(x')q(x'\to x)$ $π (x) q (x \to x^{'}) = π (x^{'}) q (x^{'} \to x)$ … can be shown
    - $\pi(x)=P(x\mid e)=P(x_i,y_i\mid e)$
    - $q(x\to x')=P(x_i'\mid y_i,e)=P(x_i'\mid mb(X_i))$

Partial Observability

partially observable environment with discrete time

structure of the model is similar to the Bayesian network
hidden variables $X_t$ , observable variables $E_t$
states are evolving according to some rules → transition model
Markov assumption: $X_t$ $X_{t}$ depends on a fixed number of previous states (usually one)
- $P(X_t\mid X_{0:t-1})=P(X_t\mid X_{t-1})$
- → first-order Markov chain
  - in a second-order MC, $X_t$ depends on both $X_{t-1}$ and $X_{t-2}$
another assumption: the process is stationary
- transition probabilities are always the same (independent on $t$ )
sensor Markov assumption: $E_t$ $E_{t}$ depends only on $X_t$ $X_{t}$
- but there are sensors where this does not hold (e.g. liquid-based thermometer)
- personal note: for proprioceptive sensors, $E_t$ depends on $X_t$ and $X_{t-1}$
first-order Markov assumption: the state variables contain all the information needed to characterize the next time slice (its distribution)
- what if it does not hold?
  - increase the order of the Markov process model or enlarge the set of state variables
  - note: increasing the order can be reformulated as an increase in set of state variables

Partial Observability

inference

transition and sensor models can be described using a Bayesian network
- reasoning in this Bayesian network can be done but is not efficient (too many time steps)
basic inference tasks: filtering, prediction, smoothing, most likely explanation
- these tasks can be performed efficiently without a Bayesian network
- filtrování (filtering) – znám minulá pozorování, zajímá mě přítomný stav
  - $P(X_{t+1}\mid e_{1:t+1})=P(X_{t+1}\mid e_{1:t},e_{t+1})$ $P (X_{t + 1} ∣ e_{1 : t + 1}) = P (X_{t + 1} ∣ e_{1 : t}, e_{t + 1})$
    - použijeme Bayesovo pravidlo
  - $=\alpha\cdot P(e_{t+1}\mid X_{t+1},e_{1:t})\cdot P(X_{t+1}\mid e_{1:t})$ $= α \cdot P (e_{t + 1} ∣ X_{t + 1}, e_{1 : t}) \cdot P (X_{t + 1} ∣ e_{1 : t})$
    - použijeme sensor Markov assumption
  - $=\alpha\cdot P(e_{t+1}\mid X_{t+1})\cdot P(X_{t+1}\mid e_{1:t})$
  - $=\alpha\cdot P(e_{t+1}\mid X_{t+1})\cdot \sum_{x_t}P(X_{t+1}\mid x_t,e_{1:t}) P(x_t\mid e_{1:t})$
  - $=\alpha\cdot P(e_{t+1}\mid X_{t+1})\cdot \sum_{x_t}P(X_{t+1}\mid x_t) P(x_t\mid e_{1:t})$
  - užitečný filtrovací algoritmus si musí udržovat odhad současného stavu, jelikož je vzorec rekurzivní
  - používá se forward algoritmus
- předpověď (prediction) – znám minulá pozorování, zajímají mě budoucí stavy
  - vlastně jako filtering, akorát nepřidávám další pozorování (měření) – používám jenom přechodový model
  - $P(X_{t+k+1}\mid e_{1:t})=\sum_{x_{t+k}} P(X_{t+k+1}\mid x_{t+k}) P(x_{t+k}\mid e_{1:t})$
  - po určitém čase (mixing time) distribuce předpovědí konverguje ke stacionárnímu rozdělení daného markovského procesu a zůstane konstantní
- vyhlazování (smoothing) – znám minulá pozorování, zajímají mě minulé stavy
  - $P(X_k\mid e_{1:t})=P(X_k\mid e_{1:k},e_{k+1:t})$ $P (X_{k} ∣ e_{1 : t}) = P (X_{k} ∣ e_{1 : k}, e_{k + 1 : t})$
    - použijeme Bayesovo pravidlo
  - $=\alpha\cdot P(X_k\mid e_{1:k})\cdot P(e_{k+1:t}\mid X_k,e_{1:k})$ $= α \cdot P (X_{k} ∣ e_{1 : k}) \cdot P (e_{k + 1 : t} ∣ X_{k}, e_{1 : k})$
    - použijeme sensor Markov assumption
  - $=\alpha\cdot P(X_k\mid e_{1:k})\cdot P(e_{k+1:t}\mid X_k)$
  - přitom levý člen známe z filteringu (je to „dopředný směr“), pravý je „zpětný směr“ z naměřených hodnot v budoucnosti (relativně vůči danému okamžiku)
    - dostaneme $P(e_{k+1:t}\mid X_k)=\sum_{x_{k+1}} P(e_{k+1}\mid x_{k+1})P(e_{k+2:t}\mid x_{k+1})P(x_{k+1}\mid X_k)$
  - používá se forward-backward algoritmus
- nejpravděpodobnější vysvětlení (most likely explanation) – znám minulá pozorování, zajímá mě nejpravděpodobnější posloupnost minulých stavů
  - hledáme posloupnost $X_{1:t}$ takovou, že má největší $P(X_{1:t+1}\mid e_{1:t+1})$
  - opět existuje rekurzivní vzorec – podíváme se na pravděpodobnosti předchozích stavů a na nejpravděpodobnější „cesty“ do těchto stavů
  - používá se Viterbiho algoritmus
  - we could do smoothing for every time slice and select the most probable state at the given time
    - but this might lead to a sequence with very low probability (e.g. if there are two states with low transition probability)
  - we don't need to normalize if we only want the maximum (but the numbers get smaller)
  - most likely path to a given state … most likely path to some previous state followed by a transition to the given state
    - $\max_{x_1,\dots,x_t} P(x_1,\dots,x_t,X_{t+1}\mid e_{1:t+1})=$ $\alpha P(e_{t+1}\mid X_{t+1})\max_{x_t} (P(X_{t+1}\mid x_t)\max_{x_1,\dots,x_{t-1}} P(x_1,\dots,x_t\mid e_{1:t}))$
    - forward message passing

Partial Observability

hidden Markov models

single discrete random variable & single evidence variable → it's a hidden Markov model
we can use matrix implementation of all the basic algorithms
transition model … $S\times S$ matrix $T$ s.t. $T_{ij}=P(X_t=j\mid X_{t-1}=i)$
sensor model … diagonal matrix $O_t$ $O_{t}$ s.t. $O_{t\, ii}=P(E_t=e_t\mid X_t=i)$ $O_{t ii} = P (E_{t} = e_{t} ∣ X_{t} = i)$
- we know the value of the evidence variable $e_t$
full smoothing
- we don't need to run smoothing $t$ times in order to smooth the whole sequence
- we can use dynamic programming (store the forward/backward values) – but we need more memory then
  - we need to store the whole sequence of forward distributions
- idea: remember only the current forward distribution, apply operation to get the previous one
  - we can exploit matrix multiplication – use the inverse matrices $(T^T)^{-1},O^{-1}$ if possible (for the $O$ matrix it's always possible as it's a diagonal matrix)
smoothing with a fixed time lag
- $P(X_{t-d}\mid e_{1:t})$
- forward: simple
- backward: keep the result in the matrix form
  - then the product of matrices can be modified incrementally (again using inverse matrices)
  - convert it to vector just when using it