Back to Study Material GATE Exam

Artificial Intelligence for GATE

Artificial intelligence in the GATE DA context covers classical AI techniques including search, knowledge representation, reasoning under uncertainty, and ...

Artificial Intelligence for GATE

Search Algorithms and Problem Solving in AI

Artificial intelligence in the GATE DA context covers classical AI techniques including search, knowledge representation, reasoning under uncertainty, and planning. These topics have significant overlap with data science when probabilistic reasoning and graphical models are involved, and GATE DA allocates roughly 10 to 15 percent of marks to AI concepts.

Problem solving as search defines a state space where each state represents a configuration of the world, and a solution is a path from the initial state to a goal state. Uninformed search algorithms have no information about how far they are from the goal. Breadth-first search (BFS) is complete (finds a solution if one exists) and optimal for unit-cost edges but uses O(b^d) memory, where b is the branching factor and d is the depth of the shallowest solution. Depth-first search uses O(bd) memory but is not complete in infinite spaces and not optimal.

Informed search uses a heuristic function h(n) estimating the cost from node n to the goal. Greedy best-first search expands the node with smallest h(n); it is fast but not optimal. A* search expands the node with smallest f(n) = g(n) + h(n), where g(n) is the actual cost from start to n. A* is complete and optimal if the heuristic is admissible: h(n) never overestimates the true cost. A heuristic that is consistent (satisfies the triangle inequality) ensures A* never re-expands a node.

Local search algorithms find good solutions without maintaining a path. Hill climbing iteratively moves to the neighbor with the highest objective value and stops at a local maximum. Simulated annealing escapes local maxima by occasionally accepting worse solutions with probability exp(-delta/T), where delta is the cost increase and T is a temperature parameter that decreases over time. Genetic algorithms maintain a population of candidate solutions and apply selection, crossover, and mutation operators inspired by biological evolution.

GATE question type: given a state space with branching factor 3 and solution at depth 4, what is the maximum number of nodes in memory for BFS? Answer: BFS stores all nodes at the frontier. At depth 4, BFS may have up to 3^4 = 81 leaf nodes plus intermediate levels, but the frontier alone is O(b^d) = 81. For complete memory including all explored nodes: sum from d=0 to 4 of 3^d = (3^5 - 1)/(3-1) = 121.

Knowledge Representation, Logic, and Bayesian Networks

Knowledge representation formalizes information about the world in a structured way that allows automated reasoning. Propositional logic uses atomic propositions combined with connectives: AND (conjunction), OR (disjunction), NOT (negation), IMPLIES (implication), and BICONDITIONAL. A sentence is satisfiable if there exists an assignment of truth values that makes it true, and valid (tautology) if it is true under all assignments. Entailment means the truth of premises guarantees the truth of a conclusion.

First-order logic (FOL) extends propositional logic with objects, predicates, functions, and quantifiers. Universal quantification: For all x, P(x) asserts that predicate P holds for every object x. Existential quantification: There exists x such that P(x) asserts P holds for at least one x. FOL is more expressive than propositional logic but its satisfiability checking is semi-decidable.

Bayesian networks represent the joint probability distribution of a set of variables using a directed acyclic graph (DAG). Each node represents a variable and each edge represents a direct probabilistic dependency. Each node has a conditional probability table (CPT) specifying P(X | parents(X)). The joint probability factorizes as the product of all CPTs: P(X1, ..., Xn) = product over i of P(Xi | parents(Xi)). This factorization makes inference and learning tractable.

Inference in Bayesian networks computes posterior probabilities of query variables given observed evidence variables. Exact inference by enumeration sums the joint probability over all unobserved variables. Variable elimination performs this summation in a structured way that avoids redundant computation. For tree-structured networks, belief propagation passes messages between nodes in O(n * k^2) time, where k is the maximum number of states per variable.

GATE tip: a Bayes net question typically provides a small DAG with 3 to 5 nodes and their CPTs, then asks you to compute a conditional probability by applying the chain rule and summing. Practice this mechanical procedure: write out the joint, substitute the CPTs, cancel terms that are independent of unobserved variables, and sum over hidden variables. Speed comes from recognizing the independence structure from the graph before calculating.

Planning, Uncertainty, and AI Applications in Data Science

Planning in AI involves selecting a sequence of actions to achieve a goal from an initial state. The STRIPS formulation represents actions by their preconditions (conditions that must hold before the action can be applied), add effects (conditions that become true after the action), and delete effects (conditions that become false). Planning algorithms search the space of world states or the space of plans.

Markov decision processes (MDPs) formalize sequential decision making under uncertainty. An MDP is defined by a set of states S, a set of actions A, a transition function P(s'|s,a) giving the probability of reaching state s' from state s by taking action a, and a reward function R(s, a). The goal is to find a policy pi mapping states to actions that maximizes the expected cumulative discounted reward: V_pi(s) = E[sum over t of gamma^t * R(s_t, a_t) | s_0=s, pi], where gamma in [0,1) is the discount factor.

The Bellman optimality equation characterizes the optimal value function: V*(s) = max over a of [R(s,a) + gamma * sum over s' of P(s'|s,a) * V*(s')]. Value iteration solves this by repeatedly applying the Bellman update until convergence. Policy iteration alternates between policy evaluation (solving a linear system to find V_pi) and policy improvement (making the policy greedy with respect to V_pi). Both algorithms converge to the optimal policy for finite MDPs.

Reinforcement learning extends MDPs to settings where the transition probabilities and rewards are unknown and must be learned from experience. Q-learning learns the optimal action-value function Q*(s,a) = R(s,a) + gamma * max over a' of Q*(s',a') through the update Q(s,a) = Q(s,a) + alpha * [R + gamma * max Q(s',a') - Q(s,a)]. Q-learning is model-free, off-policy, and converges to Q* under mild conditions on the learning rate alpha.

AI applications in data science include natural language processing (NLP) with models like transformers and BERT, computer vision using convolutional neural networks, and recommendation systems using collaborative filtering. GATE DA increasingly includes questions on how these applications leverage the mathematical foundations covered elsewhere in the syllabus, especially probability, optimization, and linear algebra.