Artificial Intelligence (IT-504 (A)) - Unit 3 Short Notes

UNIT 3: Problem Solving, Search, Knowledge Representation & Reasoning

I. Foundations of AI and Intelligent Agents

A. Definitions, Goals, and Approaches to AI

• Acting Humanly: Turing Test approach. Focus on external behavior.

• Thinking Humanly: Cognitive modeling. Requires understanding human thought processes.

• Thinking Rationally: "Laws of thought" approach. Focus on correct reasoning (logic).

• Acting Rationally: Rational Agent paradigm. Focus on doing the right thing to achieve goals, given beliefs and utilities. This is the best-suited approach for a rational agent as it is computationally feasible and deals with uncertain environments.

[!TIP] Exam Focus: Be prepared to discuss the feasibility of each approach in the current scenario (Jun 2025). Acting Rationally is the most practical and widely implemented.

B. Structure and Types of Intelligent Agents

An Agent perceives its environment through sensors and acts through actuators. The agent function maps percept sequences to actions.

[!TIP] Common Pitfall: Goal-based agents find a path; utility-based agents find the best path according to preferences.

C. Agent-Environment Interaction

• Percept: Input from environment via sensors.

• Action: Output to environment via actuators.

• The agent's architecture (program + hardware) implements the agent function.

D. Characteristics of AI-Suitable Problems

• Large Search Space: Too big for exhaustive enumeration.

• No Algorithmic Solution: No clear, step-by-step recipe exists.

• Requires Knowledge: Domain-specific heuristics or rules are needed.

• Symbolic Representation: Problem can be expressed in symbols/logic.

• Common Sense/Nuance: Involves ambiguity, incomplete information, or human-like reasoning.

II. Problem Solving by Search

A. Problem Formulation and State Space

• State: A representation of the world at a point in time.

• Initial State: Starting point.

• Actions: Operator that transforms state S to successor state S'.

• Goal Test: Checks if a state is a goal state.

• Path Cost: Cost of a sequence of actions.

• State Space: Set of all reachable states from initial state, visualized as a search tree or graph.

B. Uninformed (Blind) Search Strategies

No knowledge about goal proximity (no heuristic).

1. Breadth-First Search (BFS)

• Algorithm: Explore all nodes at current depth before moving to next depth. Uses a FIFO queue.

• Properties:

  • Complete: Yes (if branching factor b finite, solution at depth d).

  • Optimal: Yes (for unit step costs).

  • Time Complexity: O(b^d) (exponential).

  • Space Complexity: O(b^d) (stores all frontier nodes).

• Example: Finding shortest path in an unweighted graph.

2. Depth-First Search (DFS)

• Algorithm: Expand deepest node first. Uses a LIFO stack (recursion).

• Properties:

  • Complete: No (infinite state spaces or deep trees; can be modified with depth limit).

  • Optimal: No.

  • Time Complexity: O(b^m) (m = max depth).

  • Space Complexity: O(bm) (linear in depth).

• Limitations: Can get stuck in infinite paths; not optimal.

3. Comparison: BFS vs DFS

[!TIP] Exam Tip: Remember the data structures: BFS = Queue (FIFO), DFS = Stack (LIFO).

C. Informed (Heuristic) Search Strategies

Uses a heuristic function h(n) estimating cost from node n to goal.

1. Best-First Search

• General framework: Expand most promising node according to an evaluation function f(n).

• Greedy Best-First: f(n) = h(n) (only heuristic). Not complete or optimal.

2. A* Search Algorithm

• Evaluation Function: f(n) = g(n) + h(n)

  • g(n): actual cost from start to node n.

  • h(n): estimated cost from n to goal.

• Admissibility: A heuristic is admissible if it never overestimates the true cost to goal (h(n) ≤ h*(n)). A with an admissible heuristic is optimal.*

• Consistency (Monotonicity): For every node n and successor n', h(n) ≤ c(n,a,n') + h(n'). Guarantees optimality and avoids re-opening nodes.

• Properties:

  • Complete: Yes (if finite branching, step costs ≥ ε).

  • Optimal: Yes (if h admissible).

  • Time/Space Complexity: O(b^d) in worst case, but dramatically reduces effective branching factor.

• Example: 8-puzzle with Manhattan distance heuristic.

3. AO* Search (AND-OR Graph Search)

• Used for non-serializable problems (subproblems must be solved in parallel).

• Algorithm: Works on an AND-OR graph. Marks nodes as SOLVED or UNSOLVED. Focuses on the current best solution graph.

• Comparison with A:*

  • Advantage: Handles problems with AND dependencies (e.g., proving theorems with multiple lemmas).

  • Disadvantage: More complex; not as widely applicable as A*.

D. Bidirectional Search

• Concept: Run two simultaneous searches—one forward from start, one backward from goal—until they meet.

• Implementation: Requires a way to generate predecessors (backward search).

• Advantage: Reduces time complexity roughly from O(b^d) to O(b^(d/2)) for symmetric branching.

E. Hill Climbing

• Idea: Greedy local search; move to neighbor with best heuristic value.

• Types:

  • Steepest-Ascent: Evaluate all neighbors, move to best.

  • First-Choice: Randomly select neighbors until one is better.

  • Stochastic: Randomly select a neighbor, move if better.

• Problems:

  • Local Maxima: Peak higher than neighbors but not global max.

  • Plateaus: Flat area where all neighbors have same value.

  • Ridges: Sequence of local maxima.

• Variants: Simulated Annealing (allows downhill moves with probability), Genetic Algorithms.

F. Comparison of Classical vs Heuristic Search

G. Risks, Limitations, and Mitigation of Heuristic Search

• Risks: Poor heuristic leads to suboptimal/incorrect solutions; overfitting heuristic to specific problems.

• Limitations: Designing a good heuristic is domain-specific and difficult; admissibility hard to prove.

• Mitigation: Use weighted A* (f(n)=g(n)+w·h(n), w>1) for faster but suboptimal solutions; learn heuristics from data; use multiple heuristics (f(n)=max(h1(n), h2(n))).

H. Constraint Satisfaction Problems (CSPs)

• Definition: Set of variables each with a domain, subject to constraints restricting variable values.

• Example: Map coloring, Sudoku.

• Local Search for CSPs:

  • Min-Conflicts Heuristic: Choose variable with most conflicts, assign value that minimizes conflicts.

  • Works well for large, random CSPs (e.g., scheduling).

I. Production Systems

• Components:

  1. Rule Base (Knowledge Base): Set of IF condition THEN action rules.

  2. Working Memory: Current state facts.

  3. Inference Engine: Matches rules with facts (pattern matching), resolves conflicts (conflict resolution strategy).

• Characteristics: Modularity, incrementality, transparency.

• Comparison: More declarative than procedural code; less efficient but easier to modify knowledge.

J. Classic AI Problems as Case Studies

III. Adversarial Search and Game Playing

A. Minimax Algorithm

• Procedure: Two-player, zero-sum game. Players: MAX (us) and MIN (opponent). Explores game tree to terminal states (utility values).

• Process: MAX chooses move maximizing minimum outcome (worst-case). MIN chooses move minimizing MAX's maximum.

• Application: Chess, Tic-Tac-Toe.

• Advantages: Guarantees optimal play against optimal opponent.

• Limitations: Computationally expensive (O(b^m)); assumes opponent plays optimally.

B. Alpha-Beta Pruning

• Optimization: Avoids exploring subtrees that cannot affect the final decision.

• Key Values:

  • α (alpha): Best (highest) value found so far for MAX along path.

  • β (beta): Best (lowest) value found so far for MIN along path.

• Cut-off Condition: If α ≥ β at any node, prune remaining siblings.

• Pruning Nodes: A node is pruned if its value cannot improve the current α or β for its ancestor.

• Variations: Negascout, Principal Variation Search (PVS), Aspiration Windows.

C. Application in Game Trees

• Example: Given a game tree, apply minimax with alpha-beta to find optimal move and identify pruned nodes.

• Effectiveness: With perfect ordering, reduces complexity to O(√b^m) (doubles search depth).

IV. Knowledge Representation (KR)

A. Importance and Challenges

• Importance: Enables reasoning, inference, and knowledge sharing.

• Challenges: Representing uncertainty, defaults, temporal knowledge, metaknowledge (knowledge about knowledge).

B. Logic-Based Representation

1. Propositional Logic

• Syntax: Atomic propositions (P, Q), connectives (¬, ∧, ∨, →, ↔).

• Semantics: Truth tables; model = assignment of truth values.

• Limitation: Cannot represent objects, relations, quantifiers.

2. Predicate Logic (First-Order Logic - FOL)

• Syntax:

  • Predicates: Loves(John, Mary), Parent(x, y).

  • Quantifiers: Universal ∀x, Existential ∃x.

  • Variables, Constants, Functions.

• Translation Example:

  • "All birds fly" → ∀x (Bird(x) → Flies(x))

  • "Some birds don't fly" → ∃x (Bird(x) ∧ ¬Flies(x))

• Conversion to Clausal Form (CNF):

  1. Eliminate →, ↔.

  2. Move ¬ inwards (Negation Normal Form).

  3. Standardize variables apart.

  4. Prenex form (all quantifiers upfront).

  5. Skolemization (eliminate ∃).

  6. Drop ∀.

  7. Distribute ∧ over ∨.

  • Result: Conjunction of disjunctions (clauses).

• Resolution & Refutation:

  • Resolution Rule: From (A ∨ B) and (¬B ∨ C), infer (A ∨ C).

  • Refutation: To prove goal G from KB, add ¬G to KB, convert to CNF, show unsatisfiable via resolution.

3. Comparison: Propositional vs Predicate Logic

C. Structured Representations

1. Semantic Networks

• Structure: Nodes (objects/concepts), Links (relationships). Directed, labeled edges.

• Reasoning: Traversal (inheritance via IS-A links).

• Example: John -[has pet]-> Dog -[is a]-> Animal.

• Comparison with Conceptual Dependency: Both are graphical. CD focuses on primitive acts for NLP; Semantic Nets focus on semantic relationships.

2. Frames

• Structure: Frame (object) with Slots (attributes) and Facets (slot properties: default, range, if-needed).

• Inheritance: Subframes inherit slots from superframes.

• Example: Frame: CAR with slots (color: default red), (engine: type V8).

• Limitations: No standard semantics; procedural attachment can be messy. Enhancements: Class hierarchies, default reasoning.

3. Scripts and Schemas

• Scripts: Structured representation of stereotyped sequences of events in a particular context (e.g., restaurant script: enter, order, eat, pay, leave).

• Schemas: More general cognitive structures for organizing knowledge about concepts and events.

• Application in NLP/Virtual Assistants: Predict next action, fill in missing details, understand context (e.g., "He ordered pasta" implies restaurant setting).

D. Procedural vs Declarative Knowledge

• Declarative: What is true (facts, rules). e.g., "The sky is blue." (Easy to modify, hard to execute efficiently).

• Procedural: How to do something (procedures, algorithms). e.g., "To start car, turn key." (Efficient execution, hard to modify/explain).

• Hybrid Systems (e.g., production systems) combine both.

E. Control Knowledge

• Knowledge that guides the order of rule firing or problem-solving steps (e.g., "try simpler rules first," "focus on subgoals related to main goal").

• Embedded in conflict resolution strategies in production systems.

V. Reasoning and Inference Methods

A. Forward Chaining (Data-Driven)

• Algorithm: Start with known facts in Working Memory (WM). Repeatedly match rules (IF part) with WM facts, fire rule, add new facts (THEN part) to WM. Stop when no new facts or goal reached.

• Suitability: Expert systems with many facts, few hypotheses (e.g., monitoring systems).

• Example: Diagnostic system: symptoms → diseases.

B. Backward Chaining (Goal-Driven)

• Algorithm: Start with goal (hypothesis). Find rules whose THEN part matches goal. For each such rule, try to prove its IF conditions (subgoals) recursively. Depth-first search on subgoals.

• Suitability: Expert systems with many hypotheses, few facts (e.g., MYCIN).

• Example: "Is patient sick with disease X?" → check rules that conclude X → check symptoms.

C. Comparison: Forward vs Backward Chaining

D. Resolution and Refutation in Predicate Logic

• Resolution: Single inference rule for FOL. Requires clauses in CNF.

• Refutation Proof:

  1. Negate the goal G → ¬G.

  2. Add ¬G to Knowledge Base (KB).

  3. Convert KB ∪ {¬G} to CNF.

  4. Apply resolution repeatedly.

  5. If empty clause □ is derived → unsatisfiable → G is true.

  6. If no empty clause → cannot prove G.

E. Monotonic vs Non-Monotonic Reasoning

VI. Expert Systems

A. Definition and Key Characteristics

• Definition: Computer program that emulates the problem-solving ability of a human expert in a specific, narrow domain.

• Characteristics: High performance, understandability, reliability, fast response, cost-effective.

B. Components of Expert Systems

1. Knowledge Base: Domain facts and rules (production rules, frames).

2. Inference Engine: Applies knowledge to facts (forward/backward chaining).

3. User Interface: Interaction with user.

4. Explanation Facility: Explains reasoning (WHY, HOW).

5. Knowledge Acquisition Module: Tools for experts to input knowledge (major bottleneck).

C. Inference Engines in Expert Systems

• Forward Chaining Implementation: Data-driven, uses Rete algorithm for efficient pattern matching.

• Backward Chaining Implementation: Goal-driven, depth-first search on subgoals.

• Comparative Analysis:

  • Forward: Good for monitoring, data-rich environments. Can generate many irrelevant facts.

  • Backward: Good for diagnosis, hypothesis-driven. Can get stuck in irrelevant subgoals.

D. Benefits and Advantages

• Captures scarce expert knowledge.

• Consistent, tireless, can explain decisions.

• Multiple experts' knowledge integration.

E. Limitations and Challenges

1. Knowledge Acquisition Bottleneck: Difficult, time-consuming to extract and formalize expert knowledge.

2. Knowledge Representation Issues: Representing uncertainty, common sense, meta-knowledge.

3. Maintenance/Updating: Knowledge base becomes outdated; difficult to modify.

4. Scalability: Performance degrades with large KB.

5. Lack of Creativity/Common Sense: Cannot handle truly novel situations.

F. Critical Factors in Design and Development

• Clear, narrow domain.

• Cooperative, available domain expert.

• Suitable knowledge representation.

• Effective inference engine.

• Good user interface and explanation facility.

• Iterative development (prototyping).

G. Applications and Real-World Examples

• MYCIN: Medical diagnosis (bacterial infections).

• DENDRAL: Chemical structure elucidation.

• XCON/R1: Computer configuration (DEC).

• Financial: Loan approval, fraud detection.

VII. Natural Language Processing (NLP)

A. Definition and Significance

• Definition: Field of AI enabling computers to understand, interpret, manipulate, and generate human language.

• Significance: Human-computer interaction (chatbots, assistants), information extraction, translation, sentiment analysis.

B. Components of NLP

1. Phonology/Morphology: Sounds, word structure.

2. Syntax: Grammar, sentence structure (parsing).

3. Semantics: Meaning of words/sentences.

4. Pragmatics: Contextual meaning, intent.

5. Discourse: Cohesion across sentences.

C. Applications in Expert Systems and Chatbots

• Expert Systems: Natural language interface for querying KB (e.g., "What are the symptoms of flu?").

• Chatbots/Virtual Assistants: Intent recognition, slot filling, dialogue management (scripts/schemas help).

D. Ethical Implications (Surveillance, Privacy)

• Surveillance: NLP enables mass monitoring of communications.

• Privacy: Analysis of personal emails, messages, calls.

• Mitigation: Strong data protection laws, anonymization, user consent, transparency in data use.

VIII. Probabilistic Reasoning

A. Bayes' Theorem

• Definition: $$\displaystyle P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)} $$

• Significance: Updates probability of hypothesis A given evidence B. Foundation of Bayesian networks.

• Application: Spam filtering (P(Spam|Words)), medical diagnosis (P(Disease|Symptoms)).

B. Fuzzy Sets and Logic

• Representation: Membership function μ_A(x) ∈ [0,1] (degree of belonging).

• Operations:

  • Union: μ_{A∪B}(x) = max( μ_A(x), μ_B(x) )

  • Intersection: μ_{A∩B}(x) = min( μ_A(x), μ_B(x) )

  • Complement: μ_{¬A}(x) = 1 - μ_A(x)

  • Difference: μ_{A-B}(x) = min( μ_A(x), 1-μ_B(x) )

• Example (Nov 2022 B):

  • A = 1/x₁ + 0.3/x₂ + 0.5/x₃ + 0.2/x₄

  • B = 0.5/x₁ + 0.4/x₂ + 0.1/x₃ + 1/x₄

  • Union: A∪B = 1/x₁ + 0.4/x₂ + 0.5/x₃ + 1/x₄

  • Intersection: A∩B = 0.5/x₁ + 0.3/x₂ + 0.1/x₃ + 0.2/x₄

IX. Modern AI: Neural Networks and Deep Learning (May 2024 Paper)

A. Fundamentals of Neural Networks

• Biological Neuron: Dendrites (input), cell body (processing), axon (output).

• Artificial Neuron (McCulloch-Pitts): Binary inputs, weighted sum, threshold activation. y = 1 if Σw_i x_i ≥ θ, else 0.

• Rosenblatt's Perceptron: Adjustable weights, supervised learning. w_i ← w_i + α (t - y) x_i (t=target, y=output, α=learning rate). Limitation: Only linearly separable problems.

B. Multilayer Perceptrons (MLP) and Training

• Architecture:

  • Input Layer: Features.

  • Hidden Layer(s): Learn representations (non-linear transformations).

  • Output Layer: Predictions.

• Backpropagation Algorithm:

  1. Forward pass: Compute output y for input x.

  2. Compute error E = ½ Σ(t_i - y_i)².

  3. Backward pass: Propagate error δ backwards using chain rule.

     • Output layer: δ_k = (t_k - y_k) f'(net_k)

     • Hidden layer: δ_j = f'(net_j) Σ (δ_k w_kj)

  4. Update weights: w_ji ← w_ji + α δ_j x_i

• Gradient Descent: Minimize error by moving opposite to gradient. w ← w - α ∇E.

• Momentum: Δw(t) = -α ∇E(t) + β Δw(t-1) (β = momentum term). Helps accelerate and avoid local minima.

C. Convolutional Neural Networks (CNNs)

• Layers:

  • Convolutional: Filters extract local features (edges, textures). Output = Feature Map.

  • Pooling (Subsampling): Max/Avg pooling. Reduces spatial size, provides translation invariance.

  • Fully Connected (FC): At end, for classification/regression.

• Padding & Stride:

  • Stride: Step size of filter. Larger stride → smaller output.

  • Padding: Adding zeros to border. 'same' padding preserves spatial dimensions.

• Confusion Matrix: Table of True vs Predicted classes. Allows calculation of Precision, Recall, F1-Score.

• Architectures:

  • VGG-16: Simple, deep (16 layers), small filters (3x3). High parameter count.

  • GoogLeNet (Inception): Uses Inception modules (parallel convolutions of different sizes). Efficient, fewer parameters.

  • ResNet (Residual Learning): Skip connections (identity mappings). Solves vanishing gradient, enables very deep networks (100+ layers).

D. Recurrent Neural Networks (RNNs)

• Traditional RNN: Has loops; maintains hidden state h_t = f(h_{t-1}, x_t). Processes sequences step-by-step.

• Bidirectional RNN (BiRNN): Two RNNs—one forward (past→future), one backward (future→past). Concatenate outputs. Captures full context.

• Backpropagation Through Time (BPTT): Unfolds RNN through time steps, applies backprop. Challenges: Vanishing/exploding gradients over long sequences.

• Gated Units:

  • GRU (Gated Recurrent Unit): Two gates (Update, Reset). Simpler, faster.

  • LSTM (Long Short-Term Memory): Three gates (Input, Forget, Output). More parameters, better at long-term dependencies.

  • Difference: LSTM has separate cell state C_t and hidden state h_t; GRU merges them. LSTM generally more powerful but slower.

E. Evaluation Metrics and Datasets

• Activation Functions:

  • Sigmoid: σ(x) = 1/(1+e^{-x}). Output (0,1). Suffers vanishing gradient.

• Metrics:

  • Precision: TP / (TP + FP) (of predicted positives, how many correct?)

  • Recall: TP / (TP + FN) (of actual positives, how many found?)

  • F1-Score: 2 * (Precision * Recall) / (Precision + Recall). Harmonic mean.

• MNIST Dataset: Handwritten digits (0-9). 60k train, 10k test. 28x28 grayscale images. Standard benchmark for image classification.

[!TIP] Exam Focus: May 2024 paper heavily tested neural network fundamentals. Be ready to draw/perceptron, explain backprop steps, compare CNN architectures (VGG vs GoogLeNet vs ResNet), and differentiate RNN/LSTM/GRU.