Artificial Intelligence (CE-803 (A)) - Unit 5 Short Notes

UNIT 5: ARTIFICIAL INTELLIGENCE - COMPREHENSIVE NOTES

Based on exhaustive analysis of RGPV CE-803(A) past papers (2022–2025). This unit covers Search Strategies, Knowledge Representation & Reasoning, Expert Systems, NLP, and Neural Networks with high exam frequency.

I. FOUNDATIONS OF AI & PROBLEM DEFINITION

Core Concepts and Goals of AI

• Intelligence: Ability to learn, understand, reason, and adapt to new situations.

• Artificial Intelligence (AI): Engineering of machines to perform tasks requiring human-like intelligence.

• Four Approaches:

  1. Acting Humanly: Turing Test, natural language processing.

  2. Thinking Humanly: Cognitive modeling, psychology.

  3. Thinking Rationally: Laws of thought, logic.

  4. Acting Rationally: Rational agent framework (most modern focus).

• Modern Goals: Automation, prediction, personalization, scientific discovery.

Intelligent Agents

• PEAS Framework:

  • Performance measure

  • Environment

  • Actuators

  • Sensors

• Agent Types:

  • Goal-based: Actions to achieve specific goals (e.g., chess agent).

  • Utility-based: Actions to maximize expected utility (e.g., investment advisor). Handles uncertainty and trade-offs.

• Interaction: Agent perceives environment via sensors, acts via actuators. Environment can be fully/partially observable, deterministic/stochastic.

Problem Characteristics & Classic Problems

• AI Problem: Well-defined initial state, actions, transition model, goal test, path cost.

• Suitability: Large state space, need for heuristics, pattern recognition, learning.

• Classic Problems:

  • Tic-Tac-Toe: Simple game tree, demonstrates Minimax.

  • Block World: Robot stacking blocks; tests planning and spatial reasoning.

• Production Systems: Rule-based (Condition-Action pairs). Compare: Flexible but can be inefficient for large problems.

[!TIP] Exam Focus: PEAS analysis and goal vs. utility agents are frequent 7-mark questions. Be ready to apply PEAS to a given scenario (e.g., self-driving car).

II. SEARCH STRATEGIES (HIGHEST FREQUENCY)

Uninformed (Blind) Search

• $b$: branching factor, $d$: solution depth, $m$: max depth.

• DFS Advantage: Low space ($O(bm)$). Disadvantage: Can get stuck in infinite paths.

Informed (Heuristic) Search

• Heuristic: $h(n)$ estimates cost from $n$ to goal. Admissible if $$\displaystyle h(n) \le h^*(n) $$ (never overestimates). Consistent if $h(n) \le c(n,a,n') + h(n')$.

• Best-First Search: Expands most promising node based on $f(n)$.

  • Greedy: $$\displaystyle f(n) = h(n) $$. Fast but not optimal.

• A* Search:

  • $$\displaystyle f(n) = g(n) + h(n) $$ where $g(n)$ = cost so far.

  • Optimal if $h(n)$ is admissible (and tree/consistent for graph).

  • Completeness: Yes (finite, step-cost $\ge \epsilon$).

  • Complexity: $$\displaystyle O(b^d) $$ but prunes more than BFS.

  • Why Popular?: Optimal + complete + best-first efficiency.

• AO* Search:

  • For AND/OR graphs (solutions may require solving sub-problems).

  • Algorithm: Marks nodes as "solved" or "in progress". Backtracks to update $f$-values.

  • Adv: Finds optimal solution in AND/OR context. Disadv: More complex, higher memory.

• Bidirectional Search:

  • Run two searches: forward from start, backward from goal.

  • Meet-in-the-middle. Adv: Reduces time to $$\displaystyle O(b^{d/2}) $$.

Local Search & Constraint Satisfaction

• Hill Climbing:

  • Greedy local search. Move to neighbor with best $h$.

  • Variants: Steepest-ascent, first-choice, stochastic.

  • Fails on: Local maxima, plateaus (flat area), ridges (narrow path).

• CSP Local Search: Min-Conflicts heuristic. Assign values minimizing conflicts. Used for scheduling, timetabling.

Adversarial Search (Game Playing)

• Minimax:

  • Objective: Maximize minimum guaranteed payoff (worst-case).

  • Algorithm: Alternates MAX (our move) and MIN (opponent). Backs up values from leaves.

  • Complexity: $$\displaystyle O(b^m) $$ (exponential). Works for zero-sum, perfect info games.

  • Limitation: Computationally infeasible for deep trees.

• Alpha-Beta Pruning:

  • Optimizes Minimax by pruning branches that cannot affect final decision.

  • Alpha ($\alpha$): Best (highest) value that MAX can guarantee.

  • Beta ($\beta$): Best (lowest) value that MIN can guarantee.

  • Cut-off: If $\alpha \ge \beta$ at any node, prune remaining siblings.

  • Effect: Reduces effective branching factor to $\sqrt{b}$ in best case.

• Alpha-Beta Variations:

  • Move Ordering: Explore best moves first → more pruning.

  • Iterative Deepening: Used for time-limited search.

  • Transposition Tables: Cache evaluated positions (hashing).

[!TIP] Exam Focus: A* (admissibility/consistency), AO*, Minimax with example, and Alpha-Beta pruning (identify pruned nodes) are extremely frequent. Practice with small trees.

III. KNOWLEDGE REPRESENTATION & REASONING

Logic-Based Representation

• Propositional Logic (PL):

  • Syntax: Atomic propositions ($P, Q$), connectives ($$\displaystyle \land, \lor, \neg, \rightarrow, \leftrightarrow $$).

  • Semantics: Truth tables. Limitation: Cannot represent objects/relations (e.g., "Socrates is mortal").

• First-Order Predicate Logic (FOPL):

  • Syntax: Objects, variables, constants, predicates ($P(x)$), functions ($f(x)$), quantifiers ($\forall, \exists$).

  • Expressiveness: Handles objects, relations, quantification. More powerful than PL.

• Conversion to Clausal Form (CNF):

  1. Eliminate $$\displaystyle \rightarrow, \leftrightarrow $$.

  2. Move $\neg$ inwards (De Morgan).

  3. Standardize variables.

  4. Prenex form (all quantifiers upfront).

  5. Skolemization (eliminate $\exists$).

  6. Drop $\forall$.

  7. Distribute $\land$ over $\lor$.

  • Result: Conjunction of disjunctions (clauses).

• Resolution:

  • Principle: If $$\displaystyle C_1 \cup \{L\} $$ and $$\displaystyle C_2 \cup \{\neg L\} $$ are true, then $$\displaystyle C_1 \cup C_2 $$ (resolvent) is true.

  • Refutation: Add negation of goal to KB. Derive empty clause $\Box$ → goal proven.

  • Complete for FOPL.

Structured Representations

• Frames Limitations: Static, inheritance issues. Enhancements: Add procedural attachments, non-monotonic reasoning (defaults).

• Scripts vs. Frames: Scripts have temporal ordering; frames are static snapshots.

Reasoning Methods

• Forward Chaining (Data-Driven):

  • Start with known facts, apply rules to infer new facts.

  • Suitable for: Monitoring, control, situations where data arrives continuously.

  • Inefficiency: May generate many irrelevant facts.

• Backward Chaining (Goal-Driven):

  • Start with goal, find rules that conclude it, recursively prove antecedents.

  • Suitable for: Diagnosis, explanation, "why?" questions.

  • Inefficiency: May go down irrelevant paths if goal is wrong.

• Comparison:

  | Feature | Forward Chaining | Backward Chaining | | :--- | :--- | :--- | | Control | Data-driven | Goal-driven | | Search Space | Often large | Focused on goal | | Best For | Situations with many facts | Hypothesis testing |

• Procedural vs. Declarative Knowledge:

  • Declarative: "What" is true (facts, rules).

  • Procedural: "How" to do it (procedures, methods).

• Control Knowledge: Strategies to guide search (e.g., rule ordering, problem decomposition). Reduces combinatorial explosion.

Probabilistic & Non-Monotonic Reasoning

• Bayes' Theorem:

$$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$

*   **Significance**: Updates belief (posterior) given evidence. Foundation of probabilistic reasoning under uncertainty.

• Non-Monotonic Reasoning:

  • Definition: Adding knowledge can retract previous conclusions.

  • Monotonic: Adding knowledge only adds conclusions.

  • Essential For: Default reasoning (e.g., "Birds fly" – unless penguin), belief revision, commonsense.

[!TIP] Exam Focus: Resolution proof, forward/backward chaining comparison, Bayes' theorem, and non-monotonic reasoning examples are common. Practice converting simple statements to clausal form.

IV. EXPERT SYSTEMS (FREQUENTLY TESTED)

Definition & Components

• Expert System (ES): Computer program that emulates human expert's decision-making in a narrow domain.

• Characteristics:

  • High performance in narrow domain.

  • Explainable reasoning.

  • Use of heuristic knowledge.

  • Symbolic reasoning (not purely numeric).

• Components:

  1. Knowledge Base: Facts + rules (heuristics).

  2. Inference Engine: Applies rules (forward/backward chaining).

  3. User Interface: Interaction.

  4. Explanation Facility: "How?" and "Why?" explanations.

  5. Knowledge Acquisition Facility: Tools for entering knowledge.

Inference Engines

• Forward Chaining in ES: Data-driven. Good for monitoring, real-time systems.

• Backward Chaining in ES: Goal-driven. Good for diagnosis, troubleshooting.

• Comparison: See table in Reasoning Methods section.

Development & Evaluation

• Critical Factors:

  • Clear, bounded problem domain.

  • Availability of human expert & knowledge.

  • User acceptance & interface.

• Knowledge Acquisition: Bottleneck. Methods: interviews, observation, learning from examples.

• Benefits: Consistency, documentation, multiple experts' knowledge, availability.

• Limitations:

  • Knowledge acquisition bottleneck.

  • Brittleness (fails outside domain).

  • Maintenance difficulty.

  • No "common sense".

• Keeping ES Updated:

  • Modular knowledge base design.

  • Machine learning integration.

  • Regular expert review cycles.

  • Version control for rules.

[!TIP] Exam Focus: ES components and forward/backward chaining in ES are very frequent. Be ready to discuss knowledge acquisition challenges and how to keep ES current.

V. NATURAL LANGUAGE PROCESSING (NLP)

Foundations

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

• Importance: Human-computer interaction, information extraction, translation, sentiment analysis.

• Key Components:

  • Syntax: Grammar, parsing.

  • Semantics: Meaning (word sense, logical form).

  • Pragmatics: Context, intent.

  • Discourse: Cohesion across sentences.

Applications & Integration

• In Chatbots/Virtual Assistants:

  • Frames/Scripts: Represent stereotypical dialogues (e.g., "booking a flight" script).

  • Schemas: Organize user goals and system responses.

  • Benefit: Structured knowledge enables coherent, goal-oriented conversations.

• In Expert Systems:

  • NLP allows natural language interface to ES.

  • Parses user queries, maps to internal knowledge representation.

  • Generates explanations in natural language.

Ethical Considerations

• Surveillance/Monitoring: NLP enables mass analysis of communications.

• Risks: Privacy violation, bias amplification (training data), misuse for social control.

• Mitigation:

  • Differential privacy in training.

  • Transparency in use.

  • Regulations (e.g., GDPR).

  • Bias detection and fairness metrics.

[!TIP] Exam Focus: Role of frames/scripts in chatbots and ethical implications of NLP in surveillance are specific 7-mark questions from Dec 2024 & Jun 2024.

VI. NEURAL NETWORKS & DEEP LEARNING (FROM MAY 2024)

Foundations of Neural Networks

• Biological vs. Artificial Neuron:

  | Biological | Artificial | | :--- | :--- | | Dendrites (inputs) | Inputs ($$\displaystyle x_i $$) | | Cell body (summation) | Weighted sum ($$\displaystyle \sum w_i x_i $$) | | Axon (output) | Activation function ($f$) | | Synapses (plasticity) | Adjustable weights ($$\displaystyle w_i $$) |

• McCulloch-Pitts Neuron: First mathematical model. Binary output based on thresholded weighted sum. Introduced all-or-nothing firing.

• Rosenblatt's Perceptron:

  • Architecture: Input layer + single output neuron (no hidden layer).

  • Operation: $$\displaystyle y = f(\sum w_i x_i + b) $$. $f$ = step function.

  • Learning: $$\displaystyle w_i^{new} = w_i^{old} + \eta (t - y) x_i $$ (where $t$ = target, $\eta$ = learning rate).

  • Limitation: Can only learn linearly separable patterns (e.g., AND, OR, not XOR).

• Backpropagation:

  • Goal: Minimize error $$\displaystyle E = \frac{1}{2} \sum (t - y)^2 $$.

  • Process:

    1. Forward pass: Compute outputs.

    2. Compute output error $$\displaystyle \delta = (t - y) f'(net) $$.

    3. Backward pass: Propagate $\delta$ to hidden layers: $$\displaystyle \delta_j = f'(net_j) \sum w_{jk} \delta_k $$.

    4. Update weights: $$\displaystyle \Delta w_{ij} = \eta \delta_j x_i $$.

  • Example: For a 2-layer net, update output weights using output $\delta$, then hidden weights using backpropagated $\delta$.

• Gradient Descent:

  • Process: $$\displaystyle w_{new} = w_{old} - \eta \nabla E(w) $$. Move opposite gradient.

  • Variations:

    • Momentum: $$\displaystyle v^{t} = \gamma v^{t-1} + \eta \nabla E $$, $$\displaystyle w^{t} = w^{t-1} - v^{t} $$. Helps escape shallow minima, accelerates.

  • Role: Optimizes weights to minimize loss function.

• Layers in ANNs:

  • Input: Receives features.

  • Hidden: Transforms data (multiple layers = deep learning). Learns hierarchical features.

  • Output: Final prediction/classification.

Convolutional Neural Networks (CNNs)

• Types of Layers:

  | Layer | Purpose | Operation | | :--- | :--- | :--- | | Convolutional | Feature extraction | Filter/kernel slides over input, computes dot product. | | Pooling | Dimensionality reduction, translation invariance | Max/Avg pooling over region. | | Fully Connected | Classification/regression | Standard ANN layer at end. |

• Padding & Stride:

  • Stride ($s$): Steps filter moves. Larger $s$ → smaller output.

  • Padding ($p$): Add zeros to border. Preserves spatial size.

  • Output Size: $$\displaystyle \frac{W - K + 2p}{s} + 1 $$ (for width $W$, kernel $K$).

• Architectures:

  • VGG-16: Simple, uniform (3x3 conv, max pool). Deep (16 layers). Strength: Simplicity. Weakness: Many parameters, heavy.

  • GoogLeNet (Inception): Uses Inception modules (parallel convs of different sizes). Strength: Efficient, multi-scale features. Weakness: Complex design.

• ResNet (Residual Learning):

  • Concept: Skip connections (identity mappings). $$\displaystyle H(x) = F(x) + x $$.

  • Addresses: Vanishing gradient in deep nets. Enables training of very deep networks (100+ layers) by learning residual functions.

Recurrent Neural Networks (RNNs)

• Standard RNN: Hidden state $$\displaystyle h_t = f(W x_t + U h_{t-1} + b) $$. Processes: One token at a time, passes hidden state.

• Bidirectional RNN:

  • Two RNNs: forward (past→future) and backward (future→past).

  • Concatenate outputs. Captures: Context from both directions.

• Backpropagation Through Time (BPTT):

  • Unfold RNN through time steps.

  • Apply standard backpropagation on unfolded graph.

  • Challenges:

    • Vanishing Gradients: Gradients shrink exponentially → early layers don't learn.

    • Exploding Gradients: Gradients grow → unstable training.

• Gated Units:

  • LSTM:

    • Gates: Input ($i$), Forget ($f$), Output ($o$).

    • Cell state $$\displaystyle C_t $$ = $$\displaystyle f_t \odot C_{t-1} + i_t \odot \tilde{C}_t $$. (Memory highway).

    • Hidden $$\displaystyle h_t = o_t \odot \tanh(C_t) $$.

  • GRU:

    • Gates: Reset ($r$), Update ($z$).

    • Simpler: No separate cell state. $$\displaystyle h_t = (1-z_t) \odot h_{t-1} + z_t \odot \tilde{h}_t $$.

  • Advantage over Simple RNN: Mitigate vanishing gradients via gating. Better long-term dependencies.

Evaluation Metrics & Datasets

• Confusion Matrix:

  | | Predicted + | Predicted - | | :--- | :--- | :--- | | Actual + | TP | FN | | Actual - | FP | TN |

• Metrics:

  • Precision = $$\displaystyle \frac{TP}{TP + FP} $$ (Accuracy of positive predictions).

  • Recall = $$\displaystyle \frac{TP}{TP + FN} $$ (Coverage of actual positives).

  • F1-score = $$\displaystyle 2 \cdot \frac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} $$ (Harmonic mean).

• MNIST Dataset: 70k handwritten digits (0-9). 28x28 grayscale. Significance: Standard benchmark for image classification (simple CNNs achieve >99%).

[!TIP] Exam Focus: CNN layers, padding/stride calculations, LSTM vs. GRU, and evaluation metrics (from confusion matrix) are new but tested. Know ResNet's residual connection concept.

VII. BROADER CONTEXT & ADVANCED TOPICS

AI as an Interdisciplinary Field

• Logic: Formal reasoning (FOPL, resolution).

• Psychology: Cognitive modeling (thinking humanly).

• Neuroscience: Inspiration for neural networks.

• Linguistics: Syntax/semantics for NLP.

• Control Theory: Robotics, reinforcement learning.

• Economics/Psychology: Utility theory, game theory.

AI for Global Challenges

• Climate Change: Climate modeling, optimization of energy grids, carbon footprint tracking.

• Healthcare: Medical diagnosis (ES), drug discovery (deep learning), personalized treatment.

• Education: Adaptive learning systems, intelligent tutoring.

Comparative Analysis

• Classical AI (Symbolic): Logic, search, ES. Strengths: Explainable, good with rules. Weaknesses: Brittle, knowledge acquisition hard.

• Modern AI (Statistical/Deep): Neural networks, big data. Strengths: Learns from data, robust to noise. Weaknesses: Black box, data-hungry.

• Performance/Adaptability: Modern AI > Classical on perception tasks (vision, speech). Classical > Modern on reasoning tasks requiring logic/explanation.

Advanced Reasoning Topics

• Knowledge Level vs. Symbol Level (Newell's distinction):

  • Knowledge Level: What the system knows (goals, beliefs).

  • Symbol Level: How knowledge is represented and processed (data structures, algorithms).

• Knowledge Representation Challenges:

  • Representing uncertainty, time, defaults, meta-knowledge.

  • Trade-off between expressiveness and computational efficiency.

[!TIP] Exam Focus: Interdisciplinary nature and AI for global challenges are 7-mark questions (Jun 2024). Know differences between classical and modern AI.

Final Exam Strategy:

1. Prioritize: Search Strategies (A*, AO*, Minimax, Alpha-Beta) > Knowledge Representation (Logic, Reasoning, Frames/Scripts) > Expert Systems > Neural Networks (CNN/RNN basics).

2. Practice: Draw small search trees (A*, Minimax with alpha-beta). Convert simple sentences to clausal form and resolve.

3. Definitions: Memorize crisp definitions for PEAS, admissibility, resolution, forward/backward chaining, frames/scripts.

4. Comparisons: Be ready to contrast BFS/DFS, forward/backward chaining, propositional/predicate logic, classical/modern AI.

5. Diagrams: Sketch BFS/DFS trees, A* search tree, Minimax game tree, CNN architecture, LSTM cell.

\boxed{\text{Focus on past paper patterns: Search, Logic, ES, and recent Neural Network topics are highest yield.}}