GATE DA & AI Engineering AI Flashcards

24 sample cards from the AI deck

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

1. State the Generalized Modus Ponens rule for first-order logic.

   For atomic sentences $p_i$, $p_i'$ and conclusion $q$ with substitution $\theta$ where $p_i'\theta = p_i\theta$ for all $i$: $$\frac{p_1', \dots, p_n', \quad (p_1 \land \dots \land p_n \Rightarrow q)}{q\theta}$$

2. What is Skolemization and why is it used?

   Skolemization removes existential quantifiers when converting first-order sentences to CNF. An $\exists$ variable inside the scope of $\forall$ variables is replaced by a Skolem function of those universals (or a Skolem constant if no enclosing $\forall$), preserving satisfiability.

3. Define conditional independence of random variables $X$ and $Y$ given $Z$.

   $X$ and $Y$ are conditionally independent given $Z$, written $X \perp Y \mid Z$, if $$P(X, Y \mid Z) = P(X \mid Z)\,P(Y \mid Z)$$ equivalently $P(X \mid Y, Z) = P(X \mid Z)$ whenever $P(Z) > 0$.

4. How does a Bayesian network factorize the full joint distribution?

   A Bayesian network factorizes the joint as the product of each variable's conditional probability given its parents: $$P(X_1, \dots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i))$$

5. State the local Markov property (local semantics) of a Bayesian network.

   Each variable is conditionally independent of its non-descendants given its parents: $$X_i \perp \text{NonDescendants}(X_i) \mid \text{Parents}(X_i)$$

6. What is a node's Markov blanket in a Bayesian network, and what is its key property?

   A node's Markov blanket consists of its parents, its children, and its children's other parents. Given its Markov blanket, a node is conditionally independent of all other nodes in the network.

7. In d-separation, describe the three connection types and when each blocks the path.

   Chain $X \to Z \to Y$ and fork $X \leftarrow Z \to Y$: blocked when $Z$ is observed. Collider (v-structure) $X \to Z \leftarrow Y$: blocked when $Z$ AND all its descendants are unobserved; observing $Z$ or a descendant unblocks (activates) the path.

8. For a Boolean Bayes net node with $k$ Boolean parents, how many independent parameters does its CPT require?

   $2^{k}$ independent parameters (one probability per combination of the $k$ parents' values; the complementary value is determined). This exponential growth in $k$ motivates compact representations like noisy-OR.

9. What is the noisy-OR model and how many parameters does it need for $k$ parents?

   Noisy-OR models a variable that is true if any parent is true, except each parent's effect can be independently inhibited with probability $q_i$. It needs only $k$ parameters: $$P(\neg X \mid \text{parents}) = \prod_{i:\, \text{parent}_i = \text{true}} q_i$$

10. What is the purpose of exact inference, and what query does Variable Elimination compute?

    Exact inference computes the posterior distribution of query variables given evidence: $P(X \mid \mathbf{e})$. Variable Elimination computes this exactly by summing out non-query, non-evidence (hidden) variables from the factorized joint.

11. Describe the two core operations of the Variable Elimination algorithm.

    (1) Pointwise product of factors: combine all factors containing a variable into one factor. (2) Summing out (marginalization): sum the resulting factor over the values of the variable to be eliminated, producing a new factor over the remaining variables.

12. Write the Variable Elimination expression for the query $P(X \mid \mathbf{e})$ in a Bayes net.

    $$P(X \mid \mathbf{e}) = \alpha \sum_{y_1} \cdots \sum_{y_k} \prod_{i} f_i$$ where the $y_j$ are hidden variables, the $f_i$ are factors from the CPTs (with evidence fixed), and $\alpha$ is the normalization constant.

13. Why does Variable Elimination outperform naive enumeration, and what controls its complexity?

    VE avoids repeated computation by storing intermediate factors (dynamic programming) and summing out variables early rather than enumerating the full joint. Its time/space complexity is exponential in the network's treewidth (induced width), which depends on the elimination ordering.

14. How does the elimination ordering affect Variable Elimination, and is finding the optimal order easy?

    The ordering determines the size of intermediate factors and thus overall cost. A good order keeps factors small; a bad order can create huge factors. Finding the optimal elimination ordering is NP-hard, so heuristics (e.g., min-degree, min-fill) are used.

15. What does it mean to 'sum out' a variable, and what role does normalization with $\alpha$ play?

    Summing out variable $Y$ replaces a factor $f(X, Y)$ with $f'(X) = \sum_y f(X, y)$, marginalizing $Y$ away. The constant $\alpha = 1 / \sum_x P(x, \mathbf{e})$ normalizes the final unnormalized factor so the posterior sums to 1.

16. Why are approximate (sampling) inference methods used instead of exact inference?

    Exact inference (e.g., variable elimination) is #P-hard and intractable for large, densely connected networks (large treewidth). Sampling methods (Monte Carlo) trade exactness for tractability, approximating posteriors from randomly generated samples.

17. Describe Direct (Prior) Sampling from a Bayesian network.

    Sample each variable in topological order, drawing each $X_i$ from $P(X_i \mid \text{parents}(X_i))$ using already-sampled parent values. The fraction of samples matching an event estimates its prior probability, converging to the true value as $N \to \infty$.

18. What is Rejection Sampling and its main weakness?

    Rejection sampling generates samples by prior sampling, discards (rejects) all samples inconsistent with the evidence $\mathbf{e}$, and estimates $P(X \mid \mathbf{e})$ from the accepted samples. Its weakness: it rejects most samples when evidence is unlikely, becoming very inefficient for low-probability evidence.

19. Explain Likelihood Weighting and how the weight is computed.

    Likelihood weighting fixes evidence variables to their observed values and samples only non-evidence variables. Each sample is weighted by the likelihood of the evidence given its parents: $$w = \prod_{i \in \text{evidence}} P(e_i \mid \text{parents}(E_i))$$ Weighted samples estimate the posterior, avoiding rejection.

20. What advantage and limitation does Likelihood Weighting have compared to Rejection Sampling?

    Advantage: it uses every sample (no rejection), so it is far more efficient, especially with unlikely evidence. Limitation: performance degrades when there are many evidence variables, because most weights become very small (a few samples dominate), increasing variance.

21. Describe Gibbs sampling as an MCMC method for Bayes net inference.

    Gibbs sampling is a Markov Chain Monte Carlo method: it fixes evidence, initializes other variables randomly, then repeatedly resamples each non-evidence variable from its conditional distribution given its Markov blanket. The stationary distribution of the chain is the true posterior $P(X \mid \mathbf{e})$.

22. In Gibbs sampling, what is each non-evidence variable resampled from, and what is 'burn-in'?

    Each variable is resampled from $P(X_i \mid \text{MarkovBlanket}(X_i))$, which depends only on its parents, children, and children's parents. Burn-in is the initial set of samples discarded before the chain converges to its stationary distribution, so they do not bias the estimate.

23. What general convergence guarantee do Monte Carlo sampling methods provide, and at what rate?

    They are consistent: estimates converge to the true probability as the number of samples $N \to \infty$ (law of large numbers). The standard error decreases at rate $O(1/\sqrt{N})$, independent of the number of dimensions.

24. Compare exact inference (Variable Elimination) and approximate inference (sampling) in terms of accuracy and scalability.

    Variable Elimination gives exact answers but its cost is exponential in treewidth, so it fails on large dense networks. Sampling gives approximate answers with controllable accuracy (more samples = better), scales to large networks, and trades exactness for tractability.

What this deck covers

AI flashcards FAQ