GATE DA & AI Engineering AI Syllabus

What is the goal of adversarial search, and what defines a zero-sum two-player game?

Adversarial search finds optimal moves in competitive multi-agent environments. A zero-sum two-player game is one where the players' utilities are exactly opposed: one player's gain equals the other's loss, so utilities sum to a constant (e.g., $+1$ and $-1$).

State the minimax value recurrence for a game with MAX and MIN players.

$$\text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal} \\ \max_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MAX to move} \\ \min_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MIN to move} \end{cases}$$

Give the time and space complexity of the minimax algorithm for a game with branching factor $b$ and depth $m$.

Time complexity is $O(b^{m})$ and space complexity is $O(bm)$ (it performs a depth-first exploration of the game tree).

What is alpha-beta pruning and what do $\alpha$ and $\beta$ represent?

Alpha-beta pruning eliminates branches that cannot affect the minimax decision. $\alpha$ is the best (highest) value found so far for MAX along the path; $\beta$ is the best (lowest) value found so far for MIN. A branch is pruned when $\alpha \geq \beta$.

How much can optimal move ordering improve alpha-beta pruning's complexity?

With perfect move ordering, alpha-beta examines only $O(b^{m/2})$ nodes instead of $O(b^{m})$, effectively reducing the branching factor to $\sqrt{b}$ and doubling the searchable depth.

Why are evaluation functions and cutoff tests used in game-playing programs?

Because full search to terminal states is infeasible, search is cut off at a depth limit and a heuristic evaluation function estimates the expected utility of non-terminal states (e.g., a weighted sum of features), replacing the true utility.

What is expectiminimax and when is it used?

Expectiminimax extends minimax to games with chance nodes (e.g., dice). At chance nodes the value is the expected value over outcomes: $$\text{EXPECTIMINIMAX}(s) = \sum_{r} P(r)\,\text{EXPECTIMINIMAX}(\text{RESULT}(s,r))$$ used for stochastic games like backgammon.

Define a literal, clause, and conjunctive normal form (CNF) in propositional logic.

A literal is an atomic proposition or its negation (e.g., $P$ or $\neg P$). A clause is a disjunction of literals (e.g., $P \lor \neg Q \lor R$). CNF is a conjunction of clauses, i.e., an AND of ORs.

Define the terms valid, satisfiable, and unsatisfiable for a propositional sentence.

A sentence is valid (a tautology) if true in every model; satisfiable if true in at least one model; unsatisfiable (a contradiction) if true in no model. A sentence is valid iff its negation is unsatisfiable.

State the deduction theorem connecting entailment and validity.

$\alpha \models \beta$ if and only if the sentence $(\alpha \Rightarrow \beta)$ is valid. Equivalently, $\alpha \models \beta$ iff $(\alpha \land \neg\beta)$ is unsatisfiable (proof by refutation).

Write the logical equivalences for implication elimination and the contrapositive.

Implication elimination: $(\alpha \Rightarrow \beta) \equiv (\neg\alpha \lor \beta)$. Contrapositive: $(\alpha \Rightarrow \beta) \equiv (\neg\beta \Rightarrow \neg\alpha)$.

State De Morgan's laws in propositional logic.

$$\neg(\alpha \land \beta) \equiv (\neg\alpha \lor \neg\beta)$$ $$\neg(\alpha \lor \beta) \equiv (\neg\alpha \land \neg\beta)$$

State the propositional resolution inference rule.

From two clauses containing complementary literals, infer their resolvent (the disjunction of all remaining literals): $$\frac{\ell_1 \lor \dots \lor \ell_k \lor m, \quad n_1 \lor \dots \lor n_j \lor \neg m}{\ell_1 \lor \dots \lor \ell_k \lor n_1 \lor \dots \lor n_j}$$ Resolution is sound and refutation-complete for propositional logic.

What is Modus Ponens, and is it sound?

Modus Ponens: $$\frac{\alpha \Rightarrow \beta, \quad \alpha}{\beta}$$ Given an implication and its antecedent, infer the consequent. It is a sound inference rule.

What is a Horn clause, and why is it computationally important?

A Horn clause is a disjunction of literals with at most one positive literal (equivalently, an implication with a conjunction of positive premises and a single positive conclusion). Inference on Horn clauses can be done in linear time using forward or backward chaining.

What two elements do predicate (first-order) logic add beyond propositional logic?

First-order logic adds (1) objects, relations, and functions over a domain (terms and predicates) and (2) quantifiers: the universal quantifier $\forall$ and the existential quantifier $\exists$, allowing statements about all or some objects.

What is the difference between the universal quantifier $\forall$ and the existential quantifier $\exists$, and which connective naturally pairs with each?

$\forall x\, P(x)$ asserts $P$ holds for every object; it naturally pairs with implication ($\forall x\, (At(x) \Rightarrow \dots)$). $\exists x\, P(x)$ asserts $P$ holds for at least one object; it naturally pairs with conjunction ($\exists x\, (At(x) \land \dots)$).

State the duality between universal and existential quantifiers using negation.

$$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$$ $$\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$$ Each quantifier can be expressed via the other with negation (De Morgan for quantifiers).

State the rules of Universal Instantiation (UI) and Existential Instantiation (EI).

UI: from $\forall x\, \alpha$ infer $\text{SUBST}(\{x/g\}, \alpha)$ for any ground term $g$. EI: from $\exists x\, \alpha$ infer $\text{SUBST}(\{x/k\}, \alpha)$ where $k$ is a new Skolem constant not appearing elsewhere.

What is unification, and what does the most general unifier (MGU) provide?

Unification finds a substitution $\theta$ that makes two logical expressions identical: $\text{UNIFY}(p, q) = \theta$ where $p\theta = q\theta$. The MGU is the least-constraining such substitution, unique up to renaming.

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

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.

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

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

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

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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

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.

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.

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.