Reasoning Under Uncertainty Questions and Answers

Answer: A

Enumeration computes a query by summing the factorised joint over every combination of the hidden variables, which is correct and exponential. Variable elimination improves it by reordering the sums and caching. The other options describe different procedures. Starting from the definition, and then finding the algebraic rearrangement that makes it tractable, is how variable elimination is best understood.

Answer: B

Pushing sums inside products and storing the intermediate factors removes the repeated work that naive enumeration performs, often changing an exponential into something manageable. The answer is exact and every variable is still handled. Tree structure helps but is not required. Recognising repeated subcomputation and caching it is dynamic programming, and identifying it as such connects this algorithm to a large family of others. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.

Answer: C

The elimination order determines how large the intermediate factors become, and the largest one dominates the cost, which is why finding a good order matters so much. That largest size is related to the network's treewidth. Node counts, domain sizes and evidence contribute but do not govern. A cost determined by a structural parameter rather than by size is what makes structured problems tractable and unstructured ones hopeless. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

Answer: D

Choosing an order minimising the largest factor is an NP hard problem, so heuristics such as minimum degree or minimum fill are used. The numbers are irrelevant since only the structure matters, orders differ enormously in cost, and one order may serve many queries. That the preprocessing step is itself intractable, and is done heuristically, is a common situation and does not prevent the main algorithm from being useful. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: A

Ancestral sampling draws values for each node given its parents, and the frequency of the query event among the samples estimates its probability, with accuracy improving as the square root of the sample count. Network simplification and parameter estimation are different activities. Trading an exact answer for one whose error can be made as small as computation allows is the standard escape when exact inference is intractable. The quantity that varies and the quantity that does not are worth naming before any substitution is attempted.

Answer: B

If the evidence is unlikely, almost every sample is thrown away and the effective sample size collapses, which is why likelihood weighting and Markov chain methods were developed. The retained samples are correctly distributed, continuity is handled, and sampling needs only the local tables. A method that is correct and wasteful, in proportion to how informative the evidence is, is exactly the situation importance weighting was invented to address.

Answer: C

Rather than sampling the evidence variables and discarding mismatches, their values are fixed and each sample carries a weight equal to the likelihood of that evidence, so no sample is wasted. It degrades when the evidence lies far downstream. The other options describe different schemes. Converting a rejection into a weight is importance sampling, and recognising it as such brings a body of theory to bear on when it will work. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: D

Gibbs sampling starts from an arbitrary assignment and repeatedly resamples one variable given its blanket, and the sequence converges to the posterior. The samples are dependent, which is the price of avoiding rejection. Complexity ladders and independent sampling are different schemes. That a local update rule produces globally correct samples in the limit is a remarkable result and it is what makes the method practical for large networks.

Answer: A

Since a variable is conditionally independent of the rest of the network given its blanket, the correct conditional distribution can be computed from local information alone, which is what makes each update cheap. Size, observation and ordering are different matters. A structural property that makes a global computation local is what turns an intractable algorithm into a practical one, and it is the reason the blanket is defined at all. The quantity that varies and the quantity that does not are worth naming before any substitution is attempted.

Answer: B

The classifier assumes each feature independent of the others given the class, giving a network with the class as a single parent of every feature. The assumption is almost always false and the classifier is nonetheless remarkably effective. Empty networks, rule approximations and data free estimation are different notions. A model whose central assumption is known to be wrong and which works anyway is worth understanding precisely, since the reason it works is not obvious.