Artificial Intelligence Reasoning under Uncertainty Syllabus

Name the two main families of approximate inference methods for Bayesian networks.

(1) Direct/importance sampling methods: direct sampling, rejection sampling, and likelihood weighting. (2) Markov chain Monte Carlo (MCMC) methods, e.g., Gibbs sampling. Both estimate posteriors by generating samples rather than exact summation.

Explain rejection sampling for a query $P(X \mid e)$ and its main weakness.

Generate samples from the network's prior; discard (reject) any sample inconsistent with evidence $e$; estimate $P(X\mid e)$ from the fraction of accepted samples with $X$ true. Weakness: it rejects most samples when $P(e)$ is small, so it is very inefficient for unlikely evidence.

How does likelihood weighting work, and what problem does it fix relative to rejection sampling?

It fixes the evidence variables to their observed values and samples only the non-evidence variables, weighting each sample by the product of the likelihoods of the evidence given its parents: $w = \prod_{e_i \in e} P(e_i \mid \text{parents}(E_i))$. It avoids wasting rejected samples, but degrades when evidence is downstream.

Describe Gibbs sampling (MCMC) for Bayes-net inference.

Fix evidence variables; initialize non-evidence variables arbitrarily. Repeatedly pick a non-evidence variable and resample it from its distribution conditioned on its Markov blanket, $P(x_i \mid mb(X_i))$. The stationary distribution of this Markov chain is the true posterior; estimates are the fraction of samples in each state.

In temporal probabilistic models, what is the difference between state variables and evidence variables?

State variables $X_t$ describe the (usually hidden) underlying world at time $t$; evidence/observation variables $E_t$ are what the agent actually observes at time $t$. The task is to infer the hidden state sequence from the observation sequence.

State the first-order Markov assumption and the stationary (time-homogeneous) assumption for temporal models.

First-order Markov: the current state depends only on the previous state, $P(X_t \mid X_{0:t-1}) = P(X_t \mid X_{t-1})$. Stationary: the transition model $P(X_t\mid X_{t-1})$ and sensor model $P(E_t\mid X_t)$ do not change over time.

State the sensor Markov assumption for temporal models.

The sensor (observation) Markov assumption states that the current evidence depends only on the current state: $$P(E_t \mid X_{0:t}, E_{0:t-1}) = P(E_t \mid X_t).$$

Name the four basic inference tasks in temporal probabilistic models.

(1) Filtering: $P(X_t \mid e_{1:t})$; (2) Prediction: $P(X_{t+k} \mid e_{1:t})$ for $k>0$; (3) Smoothing: $P(X_k \mid e_{1:t})$ for $0 \le k < t$; (4) Most likely explanation: $\arg\max_{x_{1:t}} P(x_{1:t}\mid e_{1:t})$.

Write the recursive filtering (forward) equation.

$$P(X_{t+1}\mid e_{1:t+1}) = \alpha\, P(e_{t+1}\mid X_{t+1}) \sum_{x_t} P(X_{t+1}\mid x_t)\,P(x_t \mid e_{1:t}).$$ It updates the belief by predicting forward one step then correcting with the new evidence; written compactly as $f_{1:t+1} = \alpha\, \text{FORWARD}(f_{1:t}, e_{t+1})$.

Define a Hidden Markov Model (HMM) and its parameters.

An HMM is a temporal model with a single discrete state variable $X_t$ and single evidence variable $E_t$. It is specified by a transition matrix $\mathbf{T}$ with $T_{ij} = P(X_{t}=j \mid X_{t-1}=i)$, sensor/observation matrices $\mathbf{O}_t$ (diagonal, $O_{t,ii}=P(e_t\mid X_t=i)$), and an initial distribution $P(X_0)$.

Give the matrix form of the HMM forward (filtering) recursion.

$$\mathbf{f}_{1:t+1} = \alpha\, \mathbf{O}_{t+1}\, \mathbf{T}^{\top}\, \mathbf{f}_{1:t},$$ where $\mathbf{f}_{1:t}$ is the column vector of filtered state probabilities, $\mathbf{T}$ the transition matrix, and $\mathbf{O}_{t+1}$ the diagonal observation matrix.

What algorithm computes the most likely state sequence in an HMM, and what does it optimize?

The Viterbi algorithm. It finds $\arg\max_{x_{1:t}} P(x_{1:t}\mid e_{1:t})$ using the recursion $$m_{1:t+1} = \mathbf{O}_{t+1}\, \big(\max_{x_t} T_{x_t, x_{t+1}}\, m_{1:t}\big),$$ tracking back-pointers. It replaces the sum in filtering with a max over the most probable path.

What is the forward–backward algorithm used for in HMMs?

It performs smoothing: computing $P(X_k \mid e_{1:t})$ for $k<t$ by combining a forward message $\mathbf{f}_{1:k}$ (evidence up to $k$) with a backward message $\mathbf{b}_{k+1:t}$ (evidence after $k$): $$P(X_k\mid e_{1:t}) = \alpha\, \mathbf{f}_{1:k} \times \mathbf{b}_{k+1:t}.$$

What kind of temporal model is a Kalman filter, and what assumptions does it make?

A Kalman filter is a temporal model for continuous state variables. It assumes: linear-Gaussian transition and sensor models, i.e. the next state is a linear function of the current state plus Gaussian noise, and the observation is a linear function of the state plus Gaussian noise. The belief state stays Gaussian at all times.

What are the two phases of the Kalman filter update, and what does each do?

(1) Predict: propagate the current Gaussian mean and covariance through the linear dynamics to get a prior for the next step (mean shifts by the motion model, covariance grows). (2) Update/correct: incorporate the new measurement via the Kalman gain, shifting the mean toward the observation and shrinking the covariance.

Why is the mean update in a one-dimensional Kalman filter a weighted average?

The new mean is a weighted average of the predicted mean and the observation, weighted inversely by their variances: $$\mu_{t+1} = \frac{\sigma_t^2\, z_{t+1} + \sigma_z^2\, \mu_t}{\sigma_t^2 + \sigma_z^2}.$$ More reliable (lower-variance) information receives more weight.

What is the Extended Kalman Filter (EKF), and when is it needed?

The EKF handles nonlinear transition or sensor models by locally linearizing them (first-order Taylor expansion / Jacobian) around the current mean, then applying the standard Kalman update. It is needed because the exact Kalman filter requires strictly linear-Gaussian models; it works well when nonlinearity is mild over the region of uncertainty.

Define a Dynamic Bayesian Network (DBN) and its relationship to HMMs and Kalman filters.

A DBN is a Bayesian network that represents a temporal process by replicating a set of state and evidence variables across time slices, with intra-slice and inter-slice (transition) arcs. Every HMM is a single-variable DBN, and every discrete DBN can be encoded as an HMM; Kalman filters are DBNs with continuous linear-Gaussian variables. DBNs allow factored, multivariate state.

Why can a DBN be exponentially more compact than the equivalent HMM?

A DBN decomposes the state into many variables with sparse dependencies, so its transition model is a product of small CPTs. The equivalent HMM must use a single variable whose value is the full state assignment, so its transition matrix has size exponential in the number of DBN state variables.

What is particle filtering, and why is it used for DBN inference?

Particle filtering is an approximate, sample-based (sequential Monte Carlo) filtering algorithm. A population of weighted samples (particles) is propagated through the transition model, weighted by the evidence likelihood, and resampled in proportion to those weights. It is used because exact inference in general DBNs is intractable, and it scales to high-dimensional and nonlinear/non-Gaussian state spaces.

Define a utility function and what utility theory asserts about rational preferences.

A utility function $U(s)$ maps each state to a real number expressing the agent's degree of preference. Utility theory asserts that any agent whose preferences obey the rationality axioms (orderability, transitivity, continuity, substitutability, monotonicity, decomposability) behaves as if maximizing expected utility for some utility function.

Write the expected utility of an action and state its role in decision making.

$$EU(a \mid e) = \sum_{s'} P(\text{Result}(a) = s' \mid a, e)\, U(s').$$ A rational agent selects the action maximizing $EU$; this operationalizes the Maximum Expected Utility principle.

What is a lottery in utility theory, and how is its utility defined?

A lottery $L = [p_1, S_1;\, p_2, S_2;\, \dots;\, p_n, S_n]$ is a probabilistic outcome yielding state $S_i$ with probability $p_i$. Its utility is the expected utility of its outcomes: $$U(L) = \sum_i p_i\, U(S_i).$$

Define the certainty equivalent and the insurance/risk premium.

The certainty equivalent of a lottery is the guaranteed amount an agent would accept in place of the lottery (i.e., whose utility equals the lottery's expected utility). The insurance (risk) premium is the difference between the lottery's expected monetary value and its certainty equivalent — positive for a risk-averse agent.

How do the shapes of the utility-of-money curve classify risk-averse, risk-neutral, and risk-seeking agents?

Risk-averse: concave utility curve (diminishing marginal utility), certainty equivalent below expected value. Risk-neutral: linear utility, certainty equivalent equals expected value. Risk-seeking: convex utility curve, certainty equivalent above expected value.

What is a decision network (influence diagram), and what three node types does it contain?

A decision network extends a Bayesian network to represent a decision problem. Its node types are: chance nodes (ovals, random variables with CPTs), decision nodes (rectangles, choices the agent controls), and a utility node (diamond, giving utility as a function of its parents).

Describe the algorithm for evaluating a decision network.

For each possible assignment to the decision node(s): (1) set the decision node's value; (2) run Bayes-net inference to compute the posterior over the utility node's chance parents given the evidence; (3) compute the expected utility of that action. Then return the decision with maximum expected utility.

Define the Value of Perfect Information (VPI) of an evidence variable.

VPI is the expected increase in utility from learning the value of a variable $E_j$ before deciding, compared with deciding now: $$VPI_e(E_j) = \left(\sum_{k} P(E_j = e_{jk}\mid e)\, EU(\alpha_{e_{jk}} \mid e, e_{jk})\right) - EU(\alpha \mid e),$$ where $\alpha$ is the best action given current evidence and $\alpha_{e_{jk}}$ the best action after observing $E_j=e_{jk}$.

State three key properties of the value of information.

(1) Non-negativity: $VPI_e(E_j) \ge 0$ — information can never hurt in expectation. (2) Non-additivity: the value of two observations is generally not the sum of their individual values (they can be complementary or redundant). (3) Order independence: the total value of acquiring a set of evidence is independent of the order acquired.

Define a Markov Decision Process (MDP) and its four components.

An MDP is a sequential decision problem in a fully observable, stochastic environment with a Markovian transition model. Its components are: a set of states $S$ (with initial state $s_0$), a set of actions $A(s)$, a transition model $P(s'\mid s, a)$, and a reward function $R(s)$ (or $R(s,a,s')$).

What is a policy in an MDP, and what is an optimal policy?

A policy $\pi$ is a mapping from states to actions, $\pi(s)$, specifying what to do in every state. An optimal policy $\pi^{*}$ maximizes the expected sum of (discounted) rewards: $$\pi^{*} = \arg\max_{\pi}\, E\!\left[\sum_{t=0}^{\infty} \gamma^{t} R(S_t) \;\middle|\; \pi\right].$$

Why is a discount factor $\gamma$ used, and what does its value signify?

The discount factor $\gamma \in [0,1]$ weights future rewards as $\gamma^{t}$, ensuring the utility of an infinite reward sequence converges (bounded by $R_{\max}/(1-\gamma)$) and modeling preference for sooner rewards. $\gamma$ near 0 makes the agent myopic; $\gamma$ near 1 makes it far-sighted.

State the Bellman equation for the utility (value) of a state in an MDP.

$$U(s) = R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s'\mid s, a)\, U(s').$$ The utility of a state is its immediate reward plus the discounted expected utility of the best next action.

Contrast value iteration and policy iteration for solving MDPs.

Value iteration repeatedly applies the Bellman update as an assignment until utilities converge, then extracts a greedy policy. Policy iteration alternates policy evaluation (solve the linear Bellman equations for the current fixed policy) and policy improvement (greedily update the policy), terminating when the policy is stable. Policy iteration often converges in fewer iterations.

What is a POMDP, and how does it differ from an MDP?

A Partially Observable MDP (POMDP) adds a sensor model $P(e\mid s)$ because the agent cannot directly observe the true state. Instead of acting on states, the agent maintains a belief state $b$ (a probability distribution over states), updated by filtering. A POMDP is equivalent to an MDP over the continuous space of belief states, making it far harder to solve.