GATE DA — Section 7

Artificial Intelligence

Comprehensive preparation notes on search algorithms, adversarial game playing, logic representations, and probabilistic reasoning under uncertainty for GATE Data Science & AI.

Official GATE DA Syllabus: Search: informed, uninformed, adversarial; logic: propositional, predicate; reasoning under uncertainty: conditional independence representation, exact inference via variable elimination, approximate inference via sampling.

1. Uninformed & Informed Search Strategies

Problem-solving agents formulate state spaces characterized by an initial state, actions, transition model, goal test, and path cost c(s, a, s'):

  • Uninformed (Blind) Search:
    • Breadth-First Search (BFS): Expands shallowest node using FIFO queue. Time & space: O(b^d). Complete and optimal for uniform step costs.
    • Depth-First Search (DFS): Expands deepest node using LIFO stack. Space: O(bm). Not guaranteed complete on infinite graphs; not optimal.
    • Uniform Cost Search (UCS): Expands node with minimum path cost g(n). Equivalent to Dijkstra's algorithm. Optimal for general positive edge costs.
  • Informed (Heuristic) Search: Utilizes problem-specific estimate h(n) of remaining cost to goal:
    • Greedy Best-First: Expands lowest h(n). Fast but neither optimal nor complete.
    • A* Search: Evaluates f(n) = g(n) + h(n) (actual cost so far + estimated cost to goal).
  • Heuristic Properties:
    • Admissibility: h(n) \le h^*(n) (never overestimates true cost). Guarantees optimality in A* tree search.
    • Consistency (Monotonicity): For every node n and successor n' generated by action a: h(n) \le c(n, a, n') + h(n'). Ensures that f(n) values along any path are non-decreasing. Guarantees optimality in A* graph search without node reopening.

2. Adversarial Search & Alpha-Beta Pruning

Used for two-player deterministic, zero-sum perfect-information games (e.g., Chess, Tic-Tac-Toe):

  • Minimax Principle: MAX seeks moves maximizing the payoff; MIN seeks moves minimizing MAX's payoff:
    V(s) = max_{a} V(Result(s, a)) [at MAX nodes] | min_{a} V(Result(s, a)) [at MIN nodes]
  • Alpha-Beta Pruning: Prunes subtrees without altering the final optimal move choice:
    • \alpha: Best value (highest payoff) found so far along the path for MAX. Initialized to -\infty.
    • \beta: Best value (lowest payoff) found so far along the path for MIN. Initialized to +\infty.
    • Pruning Condition: Prune the branch whenever \alpha \ge \beta.
    • With ideal move ordering, time complexity drops from O(b^m) to O(b^{m/2}), effectively doubling the search depth.

3. Knowledge Representation & Logic

  • Propositional Logic:
    • Entailment (\alpha \vDash \beta): In every model where sentence \alpha is true, sentence \beta is also true. Equivalently: (\alpha \land \neg \beta) is unsatisfiable.
    • Conjunctive Normal Form (CNF): Conjunction of clauses (disjunction of literals), e.g., (A \lor B) \land (\neg B \lor C).
    • Resolution Rule: Given (P \lor Q) and (\neg P \lor R), derive the resolvent (Q \lor R). Empty clause \square proves refutation.
  • First-Order Predicate Logic (FOL):
    • Uses objects, relations (predicates), functions, and quantifiers: Universal (\forall x) and Existential (\exists x).
    • Conversion to Clause Form requires eliminating implications, moving negation inwards, Standardizing variables, Skolemization (replacing \exists with Skolem constants or functions), and dropping universal quantifiers.

4. Reasoning Under Uncertainty & Bayesian Networks

A Bayesian Network is a Directed Acyclic Graph (DAG) whose nodes represent random variables and directed edges represent conditional dependencies. The joint probability distribution factors as:

P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i))

D-Separation (Conditional Independence in DAGs)

A path between nodes X and Y is blocked by a conditioning set Z if any of the following node triples occurs on the path:

Structure Triple Form Condition for Path Blocking
Causal Chain A → B → C Blocked if intermediate node B ∈ Z (is observed).
Common Cause (Fork) A ← B → C Blocked if common parent B ∈ Z (is observed).
Common Effect (Collider / V-Structure) A → B ← C Blocked if neither B nor any descendant of B is in Z. (Observing a collider opens the path!).

5. Exact & Approximate Probabilistic Inference

  • Exact Inference via Variable Elimination: Avoids exponential summation by caching intermediate factor products. Repeatedly chooses an elimination ordering, multiplies all factors containing variable Y, and sums out Y:
    m_Y(X) = \sum_{y} \prod f_j(X, y)
    Running time is exponential in the size of the largest factor created (treewidth of the moralized graph).
  • Approximate Inference via Sampling:
    • Prior Sampling: Generates samples from topological order without evidence.
    • Rejection Sampling: Drops samples that do not match observed evidence E = e. Inefficient when evidence is rare.
    • Likelihood Weighting: Fixes evidence variables and weights each sampled state by the conditional probability of the evidence given its parents: w = \prod_{i} P(e_i \mid parents(E_i)).
    • Gibbs Sampling / MCMC: Generates sequence of dependent samples by repeatedly sampling one variable conditioned on its Markov blanket.

6. Worked Step-by-Step Examples

Worked Example 1: Alpha-Beta Pruning Cutoff Trace

Problem: In a depth-2 game tree, root MAX has left child N1 (MIN) and right child N2 (MIN). N1's terminal leaf children have values 4 and 7. The first inspected child of N2 has terminal value 3. Will any subsequent children of N2 be pruned?

Solution:

1. Evaluate left child N1 (MIN node): \min(4, 7) = 4. Hence, MAX root receives value 4. Root \alpha updates to \alpha = 4, \beta = +\infty.

2. Pass [\alpha=4, \beta=+\infty] down to right child N2 (MIN node).

3. N2 inspects its first child value 3. Because N2 is a MIN node, its upper bound drops: \beta = \min(+\infty, 3) = 3.

4. Check cutoff condition: \alpha \ge \beta \iff 4 \ge 3 (True!).

Conclusion: Prune immediately. The remaining children of N2 are never evaluated because MAX would never choose N2 (which offers at most 3) over N1 (which guarantees 4).

7. GATE Exam Traps & Common Distractors

  • The Collider Pitfall: Remember that two unconditionally independent causes become conditionally dependent once their shared effect (collider) is observed: P(A \mid C, B) \ne P(A \mid C).
  • Heuristic Consistency implies Admissibility: If a heuristic is consistent, it is always admissible. The reverse is NOT true: an admissible heuristic can be inconsistent.
  • Markov Blanket Composition: The Markov blanket of variable X consists of: (1) its parents, (2) its children, and (3) other parents of its children (spouses). Forgetting spouse nodes leads to incorrect conditional independence assertions.

8. Practice & Topic Tracking

Practice exam-pattern AI problems:

Practice AI Questions or review the GATE DA Syllabus Index.