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

1. Introduction to AI and Intelligent Agents

Definition and Goals of AI

AI is the science and engineering of creating intelligent machines capable of performing tasks that typically require human intelligence. Primary goals include:

• Understanding natural intelligence.

• Building systems that reason, learn, perceive, and act.

Four Approaches to AI

Structure of Agents (PEAS Framework)

• Performance measure

• Environment

• Actuators

• Sensors

Agent Types

• Goal-based: Achieve specific goal (e.g., chess: checkmate).

• Utility-based: Maximize utility function handling trade-offs (e.g., self-driving car balancing safety, speed, comfort).

Agent-Environment Interaction

Agent function: maps percept sequence → action. Environment properties:

• Observability (fully/partially)

• Determinism (deterministic/stochastic)

• Episodic/Sequential

• Static/Dynamic

• Discrete/Continuous

• Single/Multi-agent

Problem Formulation

AI-suitable problems have:

• Clearly defined goal

• Finite, accessible state space

• Defined operators (actions)

• Cost function for solutions

• Example problems:

  • Tic-Tac-Toe: Small state space, perfect information, zero-sum.

  • Water Jug: State (x,y), actions (fill, empty, pour), goal (target volume).

  • Blocks World: Blocks on table, predicates (on, clear), actions (move).

Production Systems

Components:

• Production rules: IF condition THEN action.

• Working memory: Current facts.

• Production memory: Set of rules.

• Conflict resolution: Select rule when multiple match.

Characteristics: Modular, incremental, but may be inefficient due to match-select-execute cycle.

[!TIP] Distinguish goal-based (binary win/lose) vs utility-based (graded preferences) agents using examples like chess vs route planning.

2. Search Algorithms

2.1 Uninformed Search

• BFS: Expands shallowest node; guarantees shortest path if step costs equal.

• DFS: Expands deepest node; memory efficient but may get stuck.

• Bidirectional: Searches from start and goal; requires reverse operators.

2.2 Informed Search (Heuristic Search)

Heuristic Function $h(n)$: Estimates cost from $n$ to goal.

Properties:

• Admissible: Never overestimates true cost ($$\displaystyle h(n) \leq h^*(n) $$).

• Consistent: $h(n) \leq c(n,a,n') + h(n')$ for every action $a$.

Best-First Search: Uses $$\displaystyle f(n) = g(n) + h(n) $$ or $$\displaystyle f(n)=h(n) $$. Greedy best-first ($$\displaystyle f(n)=h(n) $$) is fast but not optimal.

A Search Algorithm*

$$f(n) = g(n) + h(n)$$

• If $h$ admissible, A* is optimal and complete (finite branching).

• Expands nodes in order of $f(n)$.

• Can be memory-intensive; uses priority queue.

AO Search*

• For AND-OR graphs (nondeterministic actions).

• Finds solution graph (subgraph from start to goal).

• Compared to A*: A* for OR graphs (single solution path), AO* for AND-OR (multiple branches required).

[!TIP] A* optimality requires admissible heuristic. Consistent heuristic ensures no node re-expansion.

2.3 Local Search

Hill Climbing

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

• First-choice: Move to first better neighbor.

• Stochastic: Random neighbor selection. Problems:

• Local maxima: Peak not global.

• Plateaus: Flat area, no uphill move.

• Ridges: Sequence of local maxima.

Constraint Satisfaction Problems (CSP)

• Variables with domains, constraints (unary, binary, global).

• Solving: Backtracking with constraint propagation (arc consistency), local search (min-conflicts).

2.4 Analysis

• Classical vs Heuristic: Classical (uninformed) systematic but costly; heuristic guided faster but may sacrifice optimality.

• Risks of Heuristic Search: Inadmissible heuristics lead to suboptimal solutions; overestimation; heuristic may mislead in some regions.

3. Adversarial Search

Minimax Algorithm

• Two-player zero-sum game.

• Max nodes (our move): choose maximum value.

• Min nodes (opponent): choose minimum value.

• Procedure: Recursive depth-first, assign utilities at leaves, propagate up.

• Application: Chess, tic-tac-toe.

• Advantages: Optimal play against optimal opponent.

• Limitations: Exponential time $$\displaystyle O(b^m) $$, assumes opponent plays optimally.

Alpha-Beta Pruning

• Maintains:

  • $\alpha$: best value for max so far.

  • $\beta$: best value for min so far.

• Cut-off: At min node, if value $\leq \alpha$, prune; at max node, if value $\geq \beta$, prune.

• Optimizations: Move ordering (best moves first), iterative deepening, transposition tables.

• Reduces nodes close to $$\displaystyle \sqrt{b^d} $$ with good ordering.

[!TIP] Alpha-beta pruning does not change outcome but reduces computation. Order moves by heuristic value to maximize pruning.

4. Knowledge Representation (KR)

4.1 Properties and Challenges

Properties of Good KR:

• Representational adequacy

• Inferential adequacy

• Efficiency

• Clarity

• Accessibility

Common Problems:

• Frame problem: Efficiently representing change.

• Common sense knowledge: Vast, implicit.

• Scalability: Large knowledge bases.

Knowledge Level vs Symbol Level:

• Knowledge level: what to represent (declarative).

• Symbol level: how to represent (implementation).

4.2 Logic-Based Representation

Propositional Logic

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

• Limitations: No objects, relations, quantifiers.

Predicate Logic (First-Order Logic)

• Syntax: Predicates $P(x,y)$, variables, constants, quantifiers ($\forall, \exists$).

• Semantics: Interpretation over domain.

• Example: $$\displaystyle \forall x \, (Human(x) \rightarrow Mortal(x)) $$.

• Conversion to Clausal Form:

  1. Eliminate $$\displaystyle \rightarrow $$, $$\displaystyle \leftrightarrow $$: $$\displaystyle P \rightarrow Q $$ becomes $\neg P \lor Q$.

  2. Move $\neg$ inward: $\neg\forall x \, P$ becomes $\exists x \, \neg P$.

  3. Standardize variables (rename to avoid confusion).

  4. Skolemize: Eliminate $\exists$ by Skolem functions/constants.

  5. Drop $\forall$ (all variables universal).

  6. Distribute $\land$ over $\lor$ to get CNF (conjunction of disjunctions).

• Resolution: Unify complementary literals from two clauses.

  Example: $(P \lor Q)$ and $(\neg Q \lor R)$ resolve to $P \lor R$.

  Refutation: Negate goal, add to KB, derive empty clause.

4.3 Structured Representation

Semantic Networks

• Nodes: concepts; arcs: relations (IS-A, HAS-PART).

• Inheritance: properties inherited from superclasses.

• Problem: Ambiguous semantics.

Frames

• Structure: Slots (attributes) with values, default values, procedures (if-needed, if-added).

• Inheritance from superframes.

• Applications: Object representation, expert systems.

• Limitations: Frame problem, rigidity.

Scripts

• Predefined sequence of events for stereotypical situations (e.g., restaurant script).

• Used in NLP for discourse understanding.

Schemas: Similar to frames, more general cognitive structures.

Conceptual Dependency

• Primitive acts (ATRANS, PTRANS, MTRANS, etc.) to represent meaning independent of language.

4.4 Other KR Concepts

Procedural vs Declarative Knowledge

• Declarative: "What" (facts, e.g., "Paris is capital of France").

• Procedural: "How" (rules, procedures, e.g., "to compute factorial...").

Control Knowledge: Strategies to guide problem-solving (e.g., which rule to fire, goal selection). Reduces search space.

Non-Monotonic Reasoning: Adding knowledge can retract conclusions. Uses defaults (e.g., "birds fly" unless penguin), circumscription, truth maintenance systems.

[!TIP] For resolution, ensure clauses are in CNF. Skolemization replaces $\exists$ with new constants/functions.

5. Inference and Reasoning

Forward Chaining (Data-Driven)

• Start with known facts.

• Match rules' antecedents, fire rules, assert new facts.

• Repeat until goal reached.

• Used in OPS5, CLIPS.

• Efficient when many conclusions possible.

Backward Chaining (Goal-Driven)

• Start with goal.

• Find rules that conclude goal, prove antecedents recursively.

• Used in Prolog.

• Efficient when hypothesis-driven.

Resolution and Refutation

• Convert KB and $\neg$goal to CNF.

• Resolve clauses until empty clause derived.

• Complete for first-order logic.

Comparison:

Monotonic vs Non-Monotonic Reasoning

• Monotonic: Adding knowledge never invalidates old conclusions (classical logic).

• Non-Monotonic: Adding knowledge can retract (defaults, assumptions).

6. Expert Systems

Definition: Computer system emulating human expert's decision-making in a narrow domain.

Key Characteristics:

• High performance in specific domain.

• Explainable reasoning.

• Reliability, consistency.

Components:

1. Knowledge Base: Rules/facts.

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

3. User Interface: Interaction.

4. Explanation Facility: Justifies decisions ("why", "how").

Inference Engines:

• Forward chaining: Data-driven, good for monitoring (e.g., fault detection).

• Backward chaining: Goal-driven, good for diagnosis (e.g., medical).

Benefits:

• Captures scarce expertise.

• Consistent, never forgets.

• Can work in hazardous environments.

Limitations:

• Knowledge acquisition bottleneck.

• Brittleness (fails on novel situations).

• Maintenance difficulty.

Development Process:

• Knowledge engineering (interview experts).

• Knowledge acquisition (tools, machine learning).

• Validation and testing.

Case Study: Block World in Robotics

• Domain: Blocks on table, goal stacks.

• Predicates: on(x,y), clear(x), ontable(x).

• Actions: move(x,y,z) with preconditions/effects (STRIPS-like).

• Used to test planning and reasoning.

[!TIP] Expert systems use shallow reasoning (rules) vs deep reasoning (models). Explanation facility is critical for user trust.

7. Natural Language Processing (NLP)

Definition: AI field enabling computers to understand, interpret, generate human language.

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

Components:

• Syntax: Grammar, parsing.

• Semantics: Meaning, word sense disambiguation.

• Pragmatics: Context, speaker intention.

• Discourse: Coherence across sentences.

KR in NLP:

• Frames: Represent objects/events with slots.

• Scripts: Predefined event sequences (e.g., restaurant script).

• Schemas: Discourse-level structures.

• Example: Restaurant script helps interpret "I ordered pasta" → implies sitting, menu, payment.

Applications:

• Chatbots (rule-based or ML).

• Virtual assistants (Siri, Alexa).

• Machine translation, summarization.

Ethical Implications:

• Surveillance: Monitoring communications.

• Bias: Training data reflects societal biases.

• Privacy: Data collection concerns.

[!TIP] NLP challenges include ambiguity (lexical, syntactic, semantic). Use context and world knowledge to resolve.

8. Probabilistic Reasoning

Bayes' Theorem

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

where $$\displaystyle P(B) = \sum_i P(B|A_i) P(A_i) $$ for all hypotheses $$\displaystyle A_i $$.

Significance:

• Updates belief in hypothesis $A$ given evidence $B$.

• Foundation for Bayesian networks, Naive Bayes classifiers.

• Applications: Medical diagnosis, spam filtering, fault detection.

Comparison with Other Frameworks:

• Classical probability: Frequency-based, requires large data.

• Fuzzy logic: Handles partial truth (degrees), not uncertainty about events.

• Dempster-Shafer: Handles belief functions, more general but complex.

[!TIP] Bayes' theorem requires prior probabilities $P(A)$ and likelihoods $P(B|A)$. Naive Bayes assumes feature independence.

9. Robotics and Block World

Block World Problem

• Simplified domain: blocks on table, robotic arm.

• Goal: Achieve specific stack (e.g., A on B on C).

• Predicates: on(x,y), clear(x), ontable(x).

• Actions: move(x,y,z) with preconditions/effects (STRIPS representation).

Significance:

• Testbed for planning algorithms (e.g., STRIPS, partial-order planning).

• Challenges: Knowledge representation, reasoning about actions, geometric constraints.

Recent Advancements:

• Deep reinforcement learning for block manipulation (e.g., OpenAI robotic hand).

• Vision-based systems using CNNs for block recognition.

• Sim-to-real transfer for training in simulation then deploying on real robots.

10. Neural Networks and Deep Learning

10.1 Fundamentals

• Biological neuron: Dendrites (input), soma (processing), axon (output), synapses (weights).

• Artificial neuron: $$\displaystyle y = f\left( \sum_{i} w_i x_i + b \right) $$, where $f$ is activation.

• McCulloch-Pitts: Binary threshold unit, no learning.

• Perceptron (Rosenblatt): $$\displaystyle w_i \leftarrow w_i + \eta (t - y) x_i $$, where $t$ target, $y$ output, $\eta$ learning rate. Learns linearly separable functions.

10.2 Training Neural Networks

• Backpropagation: Compute error at output, propagate backward via chain rule, update weights with gradient descent.

• Gradient Descent: $$\displaystyle \theta \leftarrow \theta - \eta \nabla L(\theta) $$. Variants:

  • Batch GD: entire dataset.

  • Stochastic GD: one sample.

  • Mini-batch GD: small batch.

  • Momentum: $$\displaystyle v \leftarrow \gamma v + \eta \nabla L $$, $$\displaystyle \theta \leftarrow \theta - v $$; accelerates convergence, avoids local minima.

• Learning Paradigms:

  • Supervised: Labeled data.

  • Unsupervised: Find patterns (clustering, autoencoders).

  • Reinforcement: Reward/punishment (Q-learning, policy gradients).

10.3 Convolutional Neural Networks (CNNs)

• Layers:

  • Convolutional: Filters slide, produce feature maps; ReLU activation.

  • Pooling: Downsampling (max/average), reduces parameters, provides translation invariance.

  • Fully Connected: At end, for classification.

• Padding: Add zeros to preserve spatial size ("same" padding).

• Stride: Step size; larger stride reduces output size.

• Confusion Matrix:

  | | Pred + | Pred - | |----------|--------|--------| | Actual + | TP | FN | | Actual - | FP | TN |

  Metrics:

$$\text{Accuracy} = \frac{TP+TN}{Total}$$

$$\text{Precision} = \frac{TP}{TP+FP}$$

$$\text{Recall} = \frac{TP}{TP+FN}$$

$$F1 = 2 \cdot \frac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}}$$

10.4 Recurrent Neural Networks (RNNs)

• Traditional RNN: $$\displaystyle h_t = f(W x_t + U h_{t-1}) $$. Suffers vanishing/exploding gradients.

• Bidirectional RNN: Forward pass (past → present) and backward pass (future → present); concatenate outputs.

• Backpropagation Through Time (BPTT): Unfold RNN in time, apply backprop, compute gradients. Challenges: long sequences → vanishing gradients.

• Gated Recurrent Units (GRUs) and LSTMs:

  • GRU: Reset gate (controls past info), update gate (blends current/previous).

  • LSTM: Input, forget, output gates + cell state. Better long-term memory.

10.5 Deep Learning Architectures

• VGG-16: 16 layers, 3×3 conv filters, deep but simple, many parameters.

• GoogLeNet: Inception modules (multiple filter sizes parallel), 22 layers, efficient.

• ResNet: Residual blocks: $$\displaystyle y = F(x) + x $$ (skip connections). Enables training very deep networks (100+ layers) by alleviating vanishing gradients.

10.6 Evaluation Metrics and Datasets

• Precision: Correctness of positive predictions.

• Recall: Coverage of actual positives.

• F1-score: Harmonic mean of precision and recall.

• MNIST: 70,000 handwritten digits (0-9), 28×28 grayscale. Standard benchmark for classification.

[!TIP] CNNs: Increase filters with depth to capture complex features. Pooling reduces spatial dimensions. LSTMs mitigate vanishing gradients via gating.

11. Fuzzy Logic

Fuzzy Sets

• Elements have membership degree $$\displaystyle \mu_A(x) \in [0,1] $$.

• Membership functions: triangular, trapezoidal, Gaussian.

Operations (for fuzzy sets $A$, $B$):

• Union: $$\displaystyle \mu_{A \cup B}(x) = \max(\mu_A(x), \mu_B(x)) $$

• Intersection: $$\displaystyle \mu_{A \cap B}(x) = \min(\mu_A(x), \mu_B(x)) $$

• Difference: $$\displaystyle \mu_{A-B}(x) = \min(\mu_A(x), 1 - \mu_B(x)) $$

• Complement: $$\displaystyle \mu_{\neg A}(x) = 1 - \mu_A(x) $$

Example (from past paper):
$$\displaystyle A = 1/x_1 + 0.3/x_2 + 0.5/x_3 + 0.2/x_4 $$
$$\displaystyle B = 0.5/x_1 + 0.4/x_2 + 0.1/x_3 + 1/x_4 $$

• Union: $\max$ per element → $$\displaystyle 1/x_1 + 0.4/x_2 + 0.5/x_3 + 1/x_4 $$

• Intersection: $\min$ → $$\displaystyle 0.5/x_1 + 0.3/x_2 + 0.1/x_3 + 0.2/x_4 $$

• Difference: $A-B$ → $$\displaystyle \min(\mu_A, 1-\mu_B) $$ → $$\displaystyle 0.5/x_1 + 0.6/x_2 + 0.9/x_3 + 0/x_4 $$

• Complement of $A$: $$\displaystyle 1-\mu_A $$ → $$\displaystyle 0/x_1 + 0.7/x_2 + 0.5/x_3 + 0.8/x_4 $$

[!TIP] Fuzzy logic handles partial truth (degrees), unlike binary logic. Operations are pointwise on membership values.

12. AI in Society

Interdisciplinary Nature

Combines computer science, mathematics, statistics, psychology, neuroscience, linguistics, philosophy.

AI for Global Challenges:

• Climate Change: Climate modeling, energy optimization (smart grids), carbon footprint tracking.

• Healthcare: Medical diagnosis (imaging), drug discovery, personalized treatment, epidemic prediction.

• Education: Adaptive learning platforms, intelligent tutoring systems, automated grading.

Contribution to Human Life:

• Automation: Manufacturing, transportation.

• Convenience: Smart assistants, recommendation systems.

• Safety: Autonomous vehicles, disaster response.

• Challenges: Job displacement, algorithmic bias, privacy erosion, ethical decision-making (e.g., autonomous weapons).

[!TIP] In essays, balance benefits (efficiency, accessibility) with risks (bias, unemployment, surveillance). Emphasize need for ethical AI frameworks.