Back to Study Material GATE Exam

Last Minute Notes Artificial Intelligence

This section distills the most important AI concepts into a rapid-review format for the day before GATE DA. Focus on the definitions, properties, and key d...

Last Minute Notes Artificial Intelligence

AI Search and Logic: Final Condensed Notes

This section distills the most important AI concepts into a rapid-review format for the day before GATE DA. Focus on the definitions, properties, and key distinctions that appear most frequently in previous papers.

Search algorithm properties: completeness (does it always find a solution?), optimality (does it find the best solution?), time complexity, and space complexity. BFS: complete, optimal for unit costs, O(b^d) time and space. DFS: not complete (infinite spaces), not optimal, O(bm) time, O(bm) space where m is maximum depth. Uniform-cost search: complete, optimal, O(b^(1+C*/epsilon)) where C* is optimal cost. A*: complete and optimal if h is admissible, O(b^d) time and space in worst case.

Heuristic quality: an admissible heuristic never overestimates. A consistent heuristic satisfies h(n) <= c(n, a, n') + h(n'). Consistency implies admissibility. The h for 8-puzzle: number of misplaced tiles is admissible. Manhattan distance (sum of |row_i - goal_row_i| + |col_i - goal_col_i|) is admissible and consistent. A dominating heuristic (larger values) is always preferable as long as admissibility is maintained.

Logic identities and inference rules: Modus Ponens: from P and P->Q, conclude Q. Resolution: from P OR Q and NOT P OR R, conclude Q OR R. De Morgan's laws: NOT(P AND Q) = NOT P OR NOT Q; NOT(P OR Q) = NOT P AND NOT Q. Converting implications: P->Q = NOT P OR Q. A clause is a disjunction of literals. CNF (conjunctive normal form) is a conjunction of clauses.

Bayes net independence: in a Bayes net, variable X is conditionally independent of its non-descendants given its parents. D-separation (directional separation) is the graphical criterion for reading off conditional independencies. Three patterns: chain A->B->C, fork A<-B->C, and collider A->B<-C. In chains and forks, B blocks the path when conditioned on. In colliders, B opens the path when conditioned on (explaining away).

Last-minute checklist: verify you know the four properties of each search algorithm, two admissible heuristics for 8-puzzle, the Bellman equation for MDPs, and the three Bayes net graph patterns. These five items cover the majority of AI multiple choice questions in GATE DA.

MDPs, Reinforcement Learning, and NLP: Quick Revision

Markov decision processes require understanding of the Markov property: the future depends only on the current state, not the history. A process satisfies the Markov property if P(s_{t+1} | s_0, s_1, ..., s_t) = P(s_{t+1} | s_t). This memoryless property enables the recursive Bellman equations.

Key MDP concepts for GATE: the discount factor gamma controls how much the agent values future rewards. gamma close to 0 makes the agent myopic (values immediate rewards); gamma close to 1 makes it far-sighted. A policy is a mapping from states to actions. The state value function V_pi(s) is the expected return from state s following policy pi. The action-value function Q_pi(s,a) is the expected return from taking action a in state s and then following pi.

Value iteration update: V_{k+1}(s) = max over a of [R(s,a) + gamma * sum over s' of P(s'|s,a) * V_k(s')]. Start with V_0 = 0 everywhere. Each update is a contraction mapping, so V_k converges to V* geometrically. Policy iteration: evaluate the current policy (solve a linear system), then improve by making each state greedily choose the action that maximizes the RHS. Policy iteration converges in fewer iterations than value iteration but each iteration is more expensive.

Q-learning update: Q(s,a) <- Q(s,a) + alpha * [r + gamma * max_a' Q(s',a') - Q(s,a)], where the term in brackets is the temporal difference error. This is off-policy because it updates Q using the greedy action, not necessarily the action taken. SARSA uses the actual next action taken: Q(s,a) <- Q(s,a) + alpha * [r + gamma * Q(s',a') - Q(s,a)], making it on-policy.

NLP basics: word embeddings (Word2Vec, GloVe) map words to dense vectors where semantic similarity is captured by cosine similarity. The transformer architecture uses self-attention: attention(Q, K, V) = softmax(QK^T / sqrt(d_k)) V. BERT is a pre-trained transformer that produces contextual embeddings. For GATE, knowing that attention computes a weighted average of value vectors with weights determined by query-key similarity is sufficient depth.

AI Algorithms Applied: Pattern Recognition and Decision Making

Pattern recognition bridges AI theory and practical data science. At its core, it is about learning a function that maps inputs to categories or continuous outputs from examples. The Bayes optimal classifier minimizes expected classification error. It assigns each input x to the class c that maximizes P(c | x). By Bayes theorem, this is equivalent to maximizing P(x | c) * P(c), the product of likelihood and prior. The Bayes error rate is the minimum possible error, the irreducible noise floor.

Naive Bayes classifiers assume all features are conditionally independent given the class: P(x | c) = product over features i of P(x_i | c). Despite this strong and often violated assumption, naive Bayes performs surprisingly well in practice, especially for text classification. For continuous features, each P(x_i | c) is typically modeled as a Gaussian. For discrete features, it is modeled using a multinomial distribution.

Decision making under uncertainty uses expected utility theory. Each action a leads to outcomes o with probability P(o|a), and each outcome has a utility U(o). The action with maximum expected utility is chosen: a* = argmax over a of [sum over o of P(o|a) * U(o)]. In AI, utility represents preferences; in data science, it corresponds to the reward function in an MDP.

Fuzzy logic extends binary logic to handle degrees of truth. A fuzzy set assigns a membership value between 0 and 1 to each element. Fuzzy inference systems use if-then rules with fuzzy antecedents and consequents, combined via fuzzy operations. While not central to GATE DA, fuzzy logic questions occasionally appear in the AI section.

Game tree search applies to two-player zero-sum games. Minimax assigns a value to each terminal state and propagates values up the tree: MAX nodes take the maximum of children's values, MIN nodes take the minimum. Alpha-beta pruning eliminates branches that cannot affect the outcome, reducing the effective branching factor from b to approximately sqrt(b), halving the effective depth that can be searched in the same time. This is a common GATE AI question involving the final value of a game tree with given leaf node values.