Artificial Intelligence Reasoning under Uncertainty Flashcards

24 sample cards from the Reasoning under Uncertainty deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. 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.

2. 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}.$$

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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).$$

13. 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.

14. 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.

15. 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).

16. 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.

17. 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}$.

18. 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.

19. 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')$).

20. 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].$$

21. 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.

22. 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.

23. 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.

24. 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.

What this deck covers

Reasoning under Uncertainty flashcards FAQ