Artificial Intelligence
The AI section of GATE DA covers search, logic and reasoning under uncertainty. These lessons draw every search tree and network, and come with small Python programs for BFS, A*, minimax with alpha-beta pruning, resolution, and exact and sampling-based inference, so every expanded node and probability shown is computed.
1Search
- Problem Solving and Uninformed SearchFormulating a search problem, tree search versus graph search, and the uninformed strategies BFS, DFS, uniform-cost search, depth-limited and iterative deepening search, with their completeness, optimality and complexity, for GATE DA.
- Informed Search - Greedy Best-First and A*Heuristic functions, greedy best-first search, A* search with f(n) = g(n) + h(n), admissible and consistent heuristics, optimality of A*, dominance, and designing heuristics by relaxation, for GATE DA.
- Adversarial Search - Minimax and Alpha-Beta PruningTwo-player zero-sum games, game trees, the minimax algorithm, alpha-beta pruning and how move ordering affects it, depth-limited search with evaluation functions, and expectiminimax, for GATE DA.
2Logic
- Propositional Logic and InferenceKnowledge-based agents, propositional syntax and semantics, models, entailment, validity and satisfiability, inference rules, conversion to CNF, resolution refutation, and forward and backward chaining with Horn clauses, for GATE DA.
- Predicate (First-Order) LogicObjects, predicates and functions, universal and existential quantifiers, translating English into first-order logic, negating quantifiers, unification and most general unifiers, Skolemization and resolution in first-order logic, for GATE DA.
3Reasoning under Uncertainty
- Reasoning under Uncertainty and Bayesian NetworksProbability for AI, joint distributions, conditional independence, Bayesian networks, the chain-rule factorisation, counting parameters, and reading independences with d-separation (chains, forks and colliders, explaining away), for GATE DA.
- Exact Inference - Enumeration and Variable EliminationAnswering queries in a Bayesian network exactly, inference by enumeration, factors, pointwise products and summing out, the variable elimination algorithm, elimination order and complexity, with a fully worked GATE DA example.
- Approximate Inference by SamplingMonte Carlo estimation in Bayesian networks, prior (direct) sampling, rejection sampling, likelihood weighting, and Gibbs sampling (Markov chain Monte Carlo), with their strengths and weaknesses, for GATE DA.