Artificial Intelligence

Why this unit matters

AI carries growing weight in UGC NET CS as the subject increasingly shapes the industry. Questions range from "what is the branching factor in alpha-beta pruning?" to "which activation function does a perceptron use?". The unit is internally consistent: search underlies planning, knowledge representation underlies expert systems, and neural networks underlie modern AI. Understanding the connections makes the content far easier to retain.

Syllabus map

Area	Key topics
Approaches	Turing test, rational agents, state space, heuristic search, game playing, min-max, alpha-beta
Knowledge representation	Logic, semantic networks, frames, rules, scripts, conceptual dependency, ontologies, expert systems, uncertainty
Planning	Linear/non-linear, goal stack, hierarchical, STRIPS, partial order planning
NLP	Grammar, parsing, semantic analysis, pragmatics
Multi-agent systems	Agent types, generic structure, semantic web, agent communication, ontologies
Fuzzy logic	Membership, fuzzification/defuzzification, operations, rules, inference, fuzzy control
Genetic algorithms	Encoding, fitness, selection, crossover, mutation, GA cycle
ANN	Supervised/unsupervised/reinforcement, perceptron, MLP, backprop, SOM, Hopfield

Approaches and search

Turing test

Proposed by Alan Turing (1950) as an operational definition of machine intelligence: if an interrogator cannot distinguish between a human and a machine in a text conversation, the machine is intelligent. Criticised as insufficient (a program can fool people without understanding), motivates the rational agent view instead.

Rational agent

An agent is anything that perceives its environment through sensors and acts through actuators. A rational agent selects actions that maximise its performance measure given its percepts and built-in knowledge. The PEAS description: Performance measure, Environment, Actuators, Sensors.

Environment types:

Fully/partially observable, Deterministic/stochastic, Episodic/sequential, Static/dynamic, Discrete/continuous, Single-agent/multi-agent

State space representation

A problem is defined by: initial state, set of actions (operators), transition model, goal test, path cost.

A state space is the graph of all states reachable from the initial state.

Uninformed (blind) search

BFS, explores level by level; complete (if b finite), optimal (if costs uniform), time and space O(b^d) where b = branching factor, d = depth of shallowest goal.

DFS, explores deep first; not complete (infinite state spaces), not optimal, time O(b^m) where m = maximum depth, space O(bm).

Iterative deepening DFS (IDDFS), depth-limited DFS increasing limit 1, 2, 3, ...; complete + optimal like BFS but space like DFS: O(bd). Combines the best of both.

Uniform Cost Search (UCS), like BFS but explores by path cost; optimal for varying step costs. Equivalent to Dijkstra.

Informed (heuristic) search

Greedy best-first, expands the node with smallest h(n) (estimated cost to goal). Not complete, not optimal. Fast but can be misled.

A search*, expands node with smallest f(n) = g(n) + h(n) where g(n) = actual cost from start, h(n) = heuristic estimate. Complete and optimal if h is admissible (never overestimates). Optimal-efficient among algorithms using the same heuristic.

Admissible heuristic: h(n) <= h*(n) (true cost). Example: straight-line distance for route finding.

Consistent (monotonic) heuristic: h(n) <= c(n, a, n') + h(n') for every successor n'. Every consistent heuristic is admissible.

# A* pseudocode in Python
import heapq

def astar(start, goal, h, neighbors):
    open_list = [(h(start), 0, start, [])]  # (f, g, node, path)
    visited = set()
    while open_list:
        f, g, node, path = heapq.heappop(open_list)
        if node in visited:
            continue
        visited.add(node)
        path = path + [node]
        if node == goal:
            return path
        for neighbor, cost in neighbors(node):
            if neighbor not in visited:
                g2 = g + cost
                heapq.heappush(open_list, (g2 + h(neighbor), g2, neighbor, path))
    return None

Game playing

Minimax algorithm, for two-player zero-sum games. MAX player maximises the utility; MIN player minimises it. Explores the full game tree; time O(b^m).

Alpha-beta pruning, prune branches that cannot influence the final decision. Alpha (best MAX can guarantee so far) and beta (best MIN can guarantee so far). Prune when alpha >= beta. Best case (moves ordered well): effective branching factor reduces to sqrt(b) giving O(b^(m/2)).

Example: if MAX already has a value of 5 from another branch, and MIN's current subtree can produce at most 3, that subtree is pruned.

Knowledge representation

Propositional and predicate logic

Propositional logic, deals with propositions (true/false). Connectives: NOT, AND, OR, IMPLIES, IFF. Inference rules: modus ponens (P, P->Q |- Q), resolution.

Predicate logic (FOL), extends propositional with quantifiers (for all, there exists) and predicates. More expressive but semi-decidable. Used to represent facts about the world.

Inference: Forward chaining (data-driven, from facts to goals), Backward chaining (goal-driven, from goal to supporting facts), Resolution (clause-based, used in Prolog).

Semantic networks

A graph where nodes represent concepts/objects and edges represent relationships. Example: "Tweety is a bird" represented as Tweety --(is-a)--> Bird.

Inheritance can be implemented by traversal. Limitation: no formal semantics for complex queries.

Frames

A frame is a structured data object representing a concept with slots (attributes) and fillers (values). Slots can have defaults, constraints, and procedural attachments (if-needed, if-changed demons). Related to OO classes.

Scripts

Scripts (Schank, 1977) represent stereotyped sequences of events in a specific context. Structure: props, roles, entry conditions, scenes, results. Example: Restaurant script, scenes include entering, ordering, eating, paying.

Conceptual dependency

Schank's theory: all concepts expressible using 11 primitive acts (ATRANS, PTRANS, MTRANS, PROPEL, MOVE, INGEST, EXPEL, SPEAK, ATTEND, GRASP, MBUILD). Used in natural language understanding.

Ontologies

Formal specifications of concepts and relations in a domain. OWL (Web Ontology Language) is used on the semantic web. Classes, properties, individuals, axioms.

Expert systems

An expert system captures human expertise in a domain using a knowledge base (facts + rules) and an inference engine (forward or backward chaining). Components: knowledge base, inference engine, working memory, explanation facility, knowledge acquisition module.

Examples: MYCIN (medical diagnosis), DENDRAL (chemistry), XCON (computer configuration).

Handling uncertainty

Bayesian probability, update beliefs based on evidence using Bayes' theorem: P(H|E) = P(E|H) * P(H) / P(E).

Certainty factors (MYCIN), numeric measure of confidence: CF in [-1, +1].

Dempster-Shafer theory, handles ignorance (mass function over power set of hypotheses).

Fuzzy logic, handles vagueness (see Fuzzy section below).

Planning

STRIPS

STRIPS (Stanford Research Institute Problem Solver) represents:

State: a set of positive ground literals.
Operator: preconditions, add list, delete list.
Goal: a set of literals to be true.

Example operator Pickup(x): Precond: On(x, table), Clear(x), HandEmpty. Add: Holding(x). Delete: On(x, table), Clear(x), HandEmpty.

Goal stack planning (linear)

Push the goal onto a stack. If the top is an unsatisfied condition, find an operator that achieves it and push its preconditions. Limitation: Sussman anomaly, interleaved goals require non-linear planning.

Non-linear / partial-order planning

Maintain a partially ordered plan, constraints say step A must precede step B, but leaves order otherwise unspecified. Resolves threats (one step might undo another's effect) using promotion or demotion. More general and complete than linear planning.

Hierarchical task network (HTN)

Tasks are decomposed into sub-tasks using methods. Abstract tasks at high level; primitive tasks at leaf level. Used in SHOP, SIPE.

Natural language processing

Grammar levels

Morphology, structure of words (prefixes, suffixes, stems). Syntax, structure of sentences (grammar, parse trees). Semantics, meaning of sentences. Pragmatics, meaning in context (intent, discourse).

Parsing

Top-down parsing, start from start symbol S, expand rules to match input (like recursive descent). Bottom-up parsing, shift tokens, reduce by rules (like shift-reduce). Chart parsing, uses a chart (agenda) to avoid redundant computation; Earley algorithm parses any context-free grammar in O(n^3).

Semantic analysis

Map syntactic structure to meaning representations: logical forms, semantic graphs. Word sense disambiguation resolves polysemy.

Pragmatics

Speech acts (Austin, Searle): utterances have illocutionary force (assertion, question, request, promise). Gricean maxims: quantity, quality, relevance, manner.

Multi-agent systems

Agents vs objects vs expert systems

An agent is autonomous, proactive, reactive, and social. Unlike objects (which only act when called) and expert systems (which are passive knowledge stores), agents act on their own initiative and communicate with other agents.

Generic agent architecture

Sensor -> Percept -> Agent function -> Action -> Actuator.

Agent types: Simple reflex (condition-action rules), Model-based reflex (internal world model), Goal-based, Utility-based (maximise expected utility), Learning agents.

Semantic web and agent communication

The semantic web adds machine-readable meaning to web content using RDF, RDFS, OWL. Agents use ontologies to share a common vocabulary.

Agent Communication Languages (ACL): KQML and FIPA-ACL. Messages have performatives: TELL, ASK, ACHIEVE, etc.

Fuzzy sets and logic

Membership function

A fuzzy set A in universe X is defined by a membership function mu_A: X -> [0, 1]. A membership value of 0 means "not in the set"; 1 means "fully in the set"; values in between express partial membership.

Example: "tall" for heights. mu_tall(180 cm) = 0.8, mu_tall(160 cm) = 0.2.

Fuzzy operations

Union (OR): mu_{AuB}(x) = max(mu_A(x), mu_B(x))
Intersection (AND): mu_{AnB}(x) = min(mu_A(x), mu_B(x))
Complement (NOT): mu_{A'}(x) = 1, mu_A(x)

Linguistic variables

A linguistic variable takes linguistic values rather than numeric ones. Example: variable "temperature" with values {cold, warm, hot}. Each value is a fuzzy set defined by a membership function.

Fuzzification and defuzzification

Fuzzification, map crisp input values to fuzzy membership values.

Defuzzification, convert fuzzy output to a crisp output. Methods:

Centroid (Centre of Gravity), most common; crisp value = integral(x * mu(x) dx) / integral(mu(x) dx).
Mean of Maxima, average of x values where mu is maximum.
Largest of Maxima, Smallest of Maxima.

Fuzzy inference (Mamdani system)

Fuzzify inputs using membership functions.
Apply fuzzy operators (AND/OR) to rule antecedents.
Implication: clip or scale the output fuzzy set.
Aggregate all rule outputs.
Defuzzify to get crisp output.

Example rule: IF temperature is hot AND humidity is high THEN fan_speed is fast.

Genetic algorithms

Encoding

Each candidate solution is encoded as a chromosome (typically a bit string or real-valued vector). Each element is a gene. The value of a gene is an allele.

Example: for TSP, a chromosome might be [3, 1, 4, 2, 5] representing the order of visiting cities.

GA cycle

Initialise population (random chromosomes).
Evaluate fitness of each chromosome (problem-specific function).
Selection, choose parents proportional to fitness (roulette wheel), or tournament selection, or rank selection.
Crossover, combine two parents to produce offspring. Single-point: pick a crossover point, swap tails. Two-point, uniform, partially mapped crossover (PMX) for permutations.
Mutation, small random change to maintain diversity (bit flip, swap mutation). Probability typically 0.001, 0.01.
Replace old population with offspring.
Repeat from step 2 until termination criterion (max generations, fitness threshold).

import random

def fitness(chromosome):
    # Example: maximise sum (toy problem)
    return sum(chromosome)

def crossover(p1, p2, point):
    return p1[:point] + p2[point:], p2[:point] + p1[point:]

def mutate(chromosome, rate=0.01):
    return [1-g if random.random() < rate else g for g in chromosome]

# Single generation step
population = [[random.randint(0,1) for _ in range(10)] for _ in range(20)]
fitnesses = [fitness(c) for c in population]
# Select, crossover, mutate ... (abbreviated)

Schema theorem (Holland)

Short, low-order, above-average schemata (building blocks) proliferate exponentially across generations. Explains why GAs find good solutions without exhaustive search.

Artificial neural networks

Learning paradigms

Supervised, labelled training data; learn a mapping from input to output. Examples: perceptron, MLP, CNN.

Unsupervised, no labels; find structure in data. Examples: SOM (Self-Organising Map), k-means clustering, autoencoders.

Reinforcement, learn from rewards and penalties through interaction with an environment. Examples: Q-learning, SARSA.

Perceptron

The simplest ANN: a single neuron with weighted inputs and a threshold activation function.

Output y = 1 if (sum of w_i * x_i) >= theta, else 0.

Perceptron learning rule: w_i <- w_i + alpha * (target, output) * x_i.

Limitations: can only learn linearly separable functions (XOR is not learnable by a single perceptron).

Multi-layer perceptron (MLP)

Multiple layers: input layer, one or more hidden layers, output layer. Each layer is fully connected to the next.

Backpropagation, compute the error at the output, propagate the gradient backward through the network using the chain rule; update weights by gradient descent.

Steps:

Forward pass: compute output.
Compute loss (e.g., cross-entropy, MSE).
Backward pass: compute gradients.
Update weights: w <- w, lr * gradient.

Activation functions: sigmoid (1/(1+e^-x)), tanh, ReLU (max(0,x)). ReLU is preferred in deep networks (avoids vanishing gradient).

import math

def sigmoid(x):
    return 1 / (1 + math.exp(-x))

def sigmoid_derivative(x):
    s = sigmoid(x)
    return s * (1 - s)

# Forward pass for one neuron
def forward(inputs, weights, bias):
    z = sum(w * x for w, x in zip(weights, inputs)) + bias
    return sigmoid(z), z

Self-Organising Map (SOM)

Unsupervised; produces a 2D map of high-dimensional input data, preserving topological structure. Training: for each input, find the Best Matching Unit (BMU), the neuron whose weight vector is closest to the input. Update BMU and its neighbours to move closer to the input.

Hopfield network

Recurrent network with symmetric weights; used as associative memory. Stores patterns as energy minima. Retrieval: start from a noisy pattern; network converges to the stored pattern (energy decreases until a local minimum). Capacity: about 0.15 N patterns for N neurons.

Worked examples

Example 1: A* search trace

State space: S -> A (cost 1), S -> B (cost 4), A -> C (cost 2), B -> C (cost 1), C -> G (cost 3). h(S)=6, h(A)=4, h(B)=2, h(C)=3, h(G)=0.

Open: {(S, f=0+6=6)}. Expand S: {(A, f=1+4=5), (B, f=4+2=6)}. Expand A (f=5): {(B,6), (C, f=3+3=6)}. Expand B (f=6): B->C gives f=5+3=8; C already in open with f=6. Expand C (f=6): C->G gives f=6+3=9. Expand G: done. Path: S->A->C->G, cost=6.

Example 2: Minimax with alpha-beta

Game tree: MAX node at root with two MIN children. Left MIN has leaves [3, 5]; right MIN has leaves [2, 9].

Left MIN: min(3,5) = 3. Alpha at root = 3. Right MIN: first leaf = 2 < 3 = alpha. Prune (the second leaf, 9, need not be examined). Root MAX: max(3, 2) = 3.

Alpha-beta pruned the evaluation of leaf 9.

Example 3: Fuzzy inference

Rules: IF speed is fast THEN braking is hard. IF speed is slow THEN braking is soft.

Crisp input: speed = 70 km/h. Membership: mu_fast(70) = 0.6, mu_slow(70) = 0.4.

Rule 1 fires with strength 0.6: clip "hard" at 0.6. Rule 2 fires with strength 0.4: clip "soft" at 0.4. Aggregate clipped sets. Defuzzify (centroid) to get crisp braking force.

Example 4: Perceptron for AND gate

Inputs: x1, x2. Target: x1 AND x2. Initial weights: w1 = w2 = 0, theta = 0.5, alpha = 1.

Training on (1,1)->1: output = (01+01)=0 < 0.5, so 0. Error = 1-0=1. Update: w1=0+1*1=1, w2=1. Now (1,1): 1+1=2 >= 0.5, output=1. Correct. (0,1)->0: 0+1=1 >= 0.5, output=1. Error=-1. w2=1+(-1)*1=0. Continue until convergence.

Example 5: GA crossover

Parent 1: 1 0 1 1 0 0 1 0. Parent 2: 0 1 0 0 1 1 0 1. Crossover point after position 4.

Child 1: 1 0 1 1 | 1 1 0 1 (first 4 from P1, last 4 from P2). Child 2: 0 1 0 0 | 0 0 1 0 (first 4 from P2, last 4 from P1).

Quick-revision summary

A* is optimal and complete when h is admissible. f(n) = g(n) + h(n)., Alpha-beta: prune when alpha >= beta. Best case reduces effective branching to sqrt(b)., STRIPS: state = ground literals, operator = precond / add / delete lists., Perceptron: linear separator only. XOR requires MLP., Backpropagation: forward pass -> compute loss -> backward pass -> update weights., Fuzzy union = max, intersection = min, complement = 1, mu., Centroid defuzzification: integral(x * mu dx) / integral(mu dx)., GA: selection -> crossover -> mutation -> evaluate fitness -> repeat., Hopfield capacity ≈ 0.15N. SOM: competitive learning, topological mapping., Expert systems: MYCIN (medicine), DENDRAL (chemistry). Components: KB + inference engine.

How to study this unit

Trace A* by hand on a small 5, 6 node graph with h values given. This appears frequently and is fully mechanical once practised.
For minimax/alpha-beta, draw the tree, apply the pruning rule, always start from the leaves.
The STRIPS operator format (precond, add, delete) is the most common planning question. Know it cold.
For ANN, understand the geometry: a single perceptron draws a hyperplane; MLP stacks multiple hyperplanes. This explains why XOR fails for a single perceptron.
Fuzzy logic questions often give membership values and ask you to apply a rule. Practice computing the centroid defuzzification on 2, 3 examples.
GA questions typically ask about operators (crossover types, selection methods, mutation). Make a table: operator -> what it does -> when it is used.