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

UNIT 1: Foundations of Artificial Intelligence

1. Introduction to Artificial Intelligence

Definition and Goals of AI

Artificial Intelligence is the science and engineering of creating intelligent machines, particularly intelligent computer programs. It aims to develop systems that can perform tasks requiring human-like intelligence—such as learning, reasoning, problem-solving, perception, and language understanding.

Goals of AI in Modern Technology:

• Theoretical: Understand the principles of intelligence.

• Practical: Build useful systems that augment human capabilities (e.g., autonomous vehicles, medical diagnosis, virtual assistants).

Approaches to AI

Four classic approaches, evaluated by feasibility in current AI:

[!TIP] Exam Focus: Turing Test is often asked. Current AI excels at acting rationally (e.g., DeepMind's AlphaGo) but struggles with thinking humanly (common sense).

Interdisciplinary Nature

AI integrates:

• Computer Science: Algorithms, data structures.

• Mathematics: Logic, probability, optimization.

• Psychology/Cognitive Science: Human cognition models.

• Linguistics: Natural language processing.

• Philosophy: Ethics, consciousness.

• Neuroscience: Brain-inspired computing.

Characteristics of AI Problems

Problems suitable for AI typically have:

• Large search spaces (e.g., chess).

• Need for heuristics (rules of thumb).

• Symbolic reasoning requirements.

• Uncertainty or incomplete information.

Example: Tic-Tac-Toe

• Simple state space (9! ≈ 360,000 states).

• Demonstrates game tree search, minimax, alpha-beta pruning.

• Significance: Teaching tool for adversarial search and state-space exploration.

2. Intelligent Agents

Structure of Agents: PEAS Framework

Design an agent by specifying:

• Performance measure: Criteria for success (e.g., score, efficiency).

• Environment: Where agent operates.

• Actuators: Actions agent can perform.

• Sensors: Inputs agent receives.

Example: Self-driving car

• P: Safety, speed, legality.

• E: Roads, traffic, weather.

• A: Steering, acceleration, braking.

• S: Cameras, LIDAR, GPS.

Agent Function vs. Agent Program

• Agent function: f: P* → A (maps percept sequence to action).

• Agent program: Implementation of f (e.g., code).

Types of Agents

[!TIP] Goal-based vs. Utility-based:

• Goal-based: "Reach destination."

• Utility-based: "Reach fastest and safest route." Utility handles conflicting goals.

Agent-Environment Interaction

Properties of environments:

Rational Agents

An agent is rational if it selects actions that maximize its performance measure, given its percept sequence and built-in knowledge. Rationality requires:

• Autonomy: Learn from experience.

• Adaptability: Adjust to environment changes.

3. Problem-Solving by Search

3.1 Uninformed Search (Blind Search)

Breadth-First Search (BFS)

• Algorithm: Expand shallowest node first (FIFO queue).

• Properties:

  • Complete? Yes (if branching factor finite).

  • Optimal? Yes (if step costs uniform).

  • Time: $$\displaystyle O(b^d) $$ (exponential).

  • Space: $$\displaystyle O(b^d) $$ (stores all frontier nodes).

  • b = branching factor, d = solution depth.

Depth-First Search (DFS)

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

• Properties:

  • Complete? No (infinite paths); yes with depth limit.

  • Optimal? No.

  • Time: $$\displaystyle O(b^m) $$ (m = max depth).

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

Depth-Limited Search & Iterative Deepening Search (IDS)

• Depth-limited: DFS with cutoff l. Incomplete if l < d.

• IDS: Repeatedly run depth-limited with increasing l.

  • Complete? Yes.

  • Optimal? Yes (if step costs uniform).

  • Time: $$\displaystyle O(b^d) $$ (each node generated multiple times, but overhead small).

  • Space: $O(bd)$.

Hill Climbing

• Algorithm: Greedy local search; move to neighbor with highest heuristic value.

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

• Problems:

  • Local maxima: Peak higher than neighbors but not global.

  • Plateaus: Flat area; all moves equally bad.

  • Ridges: Sequence of local maxima.

• Application: Blocks World (stack blocks in goal configuration).

[!TIP] BFS vs. DFS:

• BFS: Optimal but high memory.

• DFS: Low memory but not optimal/incomplete.

• IDS: Combines BFS optimality with DFS space efficiency.

3.2 Informed Search (Heuristic Search)

Heuristic Functions

• Definition: $h(n)$ estimates cost from node n to goal.

• Properties:

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

  • Consistent (Monotone): For every node n and successor n', $h(n) \leq c(n,n') + h(n')$.

  • Consistency → Admissibility.

Best-First Search

• General framework: Expand most promising node (based on evaluation function $f(n)$).

• Greedy best-first: $$\displaystyle f(n) = h(n) $$. Uses heuristic only.

  • Not optimal (can get stuck in local minima).

  • Complete? No (infinite loops possible).

A Search Algorithm*

• Evaluation function: $$\displaystyle f(n) = g(n) + h(n) $$

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

  • $h(n)$: heuristic estimate to goal.

• Properties:

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

  • Optimal? Yes (if h is admissible).

  • Time/Space: $$\displaystyle O(b^d) $$ but prunes more nodes than BFS.

• Significance: Industry standard for pathfinding (GPS, games).

AO Search*

• Searches AND-OR graphs (problems with multiple subgoals).

• Algorithm:

  1. Start with start node.

  2. Select most promising partial solution graph.

  3. Expand one node.

  4. Update $f$-values; back up changes.

  5. Repeat until start node is solved.

• Comparison with A:*

  | A* | AO* | |----|-----| | OR graphs | AND-OR graphs | | Single solution | Multiple subproblem solutions | | Optimal for path cost | Optimal for graph cost |

Bidirectional Search

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

• Stop when frontiers intersect.

• Advantages: Reduces time from $$\displaystyle O(b^d) $$ to $$\displaystyle O(b^{d/2}) $$ (exponential savings).

• Challenges: Need goal state specification; backward operators must be invertible.

3.3 Analysis and Trade-offs

Risks and Limitations of Heuristic Search

• Heuristic design: Poor $h(n)$ → inefficiency.

• Overestimation: Violates admissibility → A* may not be optimal.

• Underestimation: Still optimal but may explore more nodes.

• Mitigation: Use domain knowledge; ensure $h$ is consistent; use weighted A* ($$\displaystyle f(n)=g(n)+w·h(n) $$) for faster but suboptimal solutions.

4. Adversarial Search (Game Playing)

Minimax Algorithm

• For two-player, zero-sum games (one wins, other loses).

• Procedure:

  1. Generate full game tree to depth d.

  2. Assign utility values at terminal nodes (win=+1, loss=-1, draw=0).

  3. MAX (our agent) chooses max value; MIN (opponent) chooses min.

  4. Back up values: MAX nodes → max of children; MIN nodes → min of children.

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

• Limitations: Computationally expensive ($$\displaystyle O(b^m) $$ nodes).

Alpha-Beta Pruning

• Optimization: Prune branches that cannot affect final decision.

• Parameters:

  • α (alpha): Best value MAX can guarantee.

  • β (beta): Best value MIN can guarantee.

• Cut-off: At MAX node, if $v \geq β$, prune (MIN will avoid). At MIN node, if $v \leq α$, prune.

• Impact: Reduces search space to $$\displaystyle O(\sqrt{b^m}) $$ in optimal ordering.

• Variations:

  • Negamax: Simplifies code (zero-sum symmetry).

  • Iterative deepening: Used with alpha-beta for time-bounded search.

[!TIP] Alpha-Beta: Order moves best first to maximize pruning. In Tic-Tac-Toe, use heuristic evaluation at non-terminal depths.

Application in Game Trees

• Tic-Tac-Toe: Small game tree (9! states).

• Chess: Large tree → use heuristic evaluation functions (material, position) and depth-limited search.

5. Constraint Satisfaction Problems (CSP)

Definition

• Variables: $$\displaystyle X = \{X_1, ..., X_n\} $$.

• Domains: $$\displaystyle D_i $$ for each $$\displaystyle X_i $$.

• Constraints: Relations restricting variable combinations (unary, binary, higher).

• Goal: Find assignment satisfying all constraints.

Examples: Map coloring, Sudoku, job scheduling.

Local Search Methods for CSPs

• Hill Climbing: Randomly change one variable to reduce conflicts.

• Simulated Annealing: Probabilistically accept worse moves to escape local minima.

• Genetic Algorithms: Evolve population of solutions via crossover/mutation.

• Comparison with Systematic Search (Backtracking):

  • Local: Faster for large problems, no guarantee of solution.

  • Systematic: Complete but exponential in worst-case.

Applications in AI

• Scheduling (timetables, logistics).

• Resource allocation.

• Sudoku solvers.

• Cryptarithmetic puzzles.

6. Knowledge Representation

6.1 Logical Representation

Propositional Logic

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

• Semantics: Truth tables.

• Limitations: Cannot represent objects/relations; no quantifiers; poor expressiveness.

Predicate Logic (First-Order Logic)

• Syntax:

  • Predicates: P(x), Loves(John, Mary).

  • Quantifiers: ∀ (universal), ∃ (existential).

  • Variables, constants, functions.

• Example: "All humans are mortal": ∀x (Human(x) → Mortal(x)).

• Expressiveness: Handles objects, relations, quantification > propositional.

Clausal Form and Resolution

• CNF (Conjunctive Normal Form): Conjunction of disjunctions (clauses).

• Conversion Steps:

  1. Eliminate →, ↔.

  2. Move ¬ inward (De Morgan).

  3. Standardize variables.

  4. Skolemize (remove ∃).

  5. Distribute ∧ over ∨.

• Resolution Principle:

  From clauses $(A ∨ B)$ and $(¬B ∨ C)$, infer $(A ∨ C)$.

• Refutation: Add negation of goal, derive empty clause (⊥).

• Example (Steve's Courses):

  Facts:

  1. Likes(Steve, C) ∧ Easy(C)

  2. ∀c (Science(c) → Hard(c))

  3. ∀c (CSE(c) → Easy(c))

  4. CSE(CS3101)

  Goal: ∃c Likes(Steve, c)

  Convert to CNF, resolve to prove.

Non-Monotonic Reasoning

• Monotonic: Adding knowledge never retracts conclusions.

• Non-monotonic: Conclusions can be withdrawn with new evidence.

• Essential for: Default reasoning ("Birds fly" unless penguin), belief revision, commonsense.

• Example: Tweety is a bird → flies. But if Tweety is a penguin → retract.

6.2 Structured Representations

Semantic Networks

• Structure: Nodes (objects/concepts), edges (relations).

• Example: John —[has pet]→ Dog.

• Applications: Knowledge graphs, semantic web.

• Comparison: More intuitive than logic; lacks formal inference.

Frames

• Structure: Slots (attributes), facets (values, constraints). Inheritance from parent frames.

• Example:

  
  Frame: CAR  
  
  Slots: color, fuel-type, mileage  
  
  

• Use: Stereotypical knowledge (e.g., "vehicle" frame).

• Limitations: Rigid; difficult with exceptions.

Scripts and Schemas

• Scripts: Fixed sequences of events (e.g., restaurant script: enter → order → eat → pay).

• Schemas: General knowledge structures (like frames but for events).

• Application in NLP/Chatbots: Understand context, predict next action.

Conceptual Dependency

• Primitives: 11 primitive actions (e.g., MOVE, INGEST, TRANSFER).

• Goal: Language-independent representation of meaning.

• Example: "John gave Mary a book" → ATRANS(John, Mary, Book).

• Comparison: More structured than semantic networks; used in early NLP.

6.3 Issues in Knowledge Representation

• Incompleteness: Missing knowledge.

• Uncertainty: Probabilistic knowledge (addressed by Bayesian networks).

• Inconsistency: Contradictory facts.

• Representational adequacy: Can it express domain?

• Importance: Enables deductive reasoning (e.g., theorem proving), efficient problem-solving.

7. Reasoning and Inference

Forward Chaining (Data-Driven)

• Algorithm:

  1. Start with known facts (working memory).

  2. Match rules' LHS with facts.

  3. Fire rules, add RHS to facts.

  4. Repeat until goal reached or no new facts.

• Applications: Production systems (e.g., CLIPS), real-time monitoring.

• Strengths: Good for many conclusions from data.

• Weaknesses: Irrelevant rules fire; inefficient for specific goal.

Backward Chaining (Goal-Driven)

• Algorithm:

  1. Start with goal (query).

  2. Find rules with goal in RHS.

  3. Recursively prove LHS subgoals.

  4. Use known facts to satisfy subgoals.

• Applications: Prolog, expert systems (MYCIN).

• Strengths: Focused; avoids irrelevant rules.

• Weaknesses: May explore irrelevant paths if goal is wrong.

Comparison of Inference Methods

Control Knowledge

• Strategies to guide search/reasoning:

  • Order rules/facts (most relevant first).

  • Recency (use latest facts).

  • Specificity (more specific rules first).

• Role: Reduce combinatorial explosion.

Procedural vs. Declarative Knowledge

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

  • Example: "If fever ∧ cough → flu."

• Procedural: How to do (procedures, algorithms).

  • Example: "To diagnose flu, check fever then cough."

• Trade-offs: Declarative more flexible; procedural more efficient.

8. Expert Systems

Definition and Characteristics

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

• Characteristics:

  • High performance (consistent, accurate).

  • Explainability (justify decisions).

  • Domain-specific knowledge.

  • Use of heuristics.

Components

1. Knowledge Base: Facts + rules (IF-THEN).

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

3. User Interface: Interaction.

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

5. Knowledge Acquisition Module: Tools to add/update knowledge.

Inference Engines

• Forward chaining: Data-driven; good for monitoring (e.g., process control).

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

• Comparison:

  • Forward: Many conclusions, slower.

  • Backward: Focused, faster for specific query.

Development and Knowledge Acquisition

• Process:

  1. Identify domain, experts.

  2. Elicit knowledge (interviews, protocols).

  3. Represent (rules, frames).

  4. Test, validate.

• Keeping knowledge updated:

  • Machine learning integration: Learn from new data.

  • Knowledge engineer: Regular updates.

  • User feedback loop.

Benefits and Limitations

Applications

• Medical diagnosis (MYCIN).

• Financial planning (loan approval).

• Troubleshooting (XCON for DEC computers).

9. Natural Language Processing (NLP)

Definition and Significance

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

• Significance: Human-computer interaction, information extraction, translation, chatbots.

Components of NLP

1. Syntax: Grammar, parsing (constituency/dependency).

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

3. Pragmatics: Context, intent (e.g., "Can you pass salt?" → request).

Applications

• Machine translation (Google Translate).

• Sentiment analysis (social media monitoring).

• Chatbots (customer service).

• Virtual assistants (Siri, Alexa).

Role of Knowledge Representation in NLP

• Frames/Scripts: Represent stereotypical situations (restaurant script → understand "I'd like a table").

• Semantic Networks: Word meanings, relations (WordNet).

• Conceptual Dependency: Primitive-based meaning representation.

• Comparison:

  • Conceptual Dependency: Language-independent, deep structure.

  • Semantic Networks: Intuitive, good for lexical semantics.

Ethical Implications

• Surveillance: NLP for monitoring communications → privacy violation.

• Bias: Training data biases → discriminatory outputs.

• Mitigation:

  • Differential privacy.

  • Bias detection/removal.

  • Transparency (explainable NLP).

  • Regulations (GDPR).

10. Additional Foundational Topics

Bayes' Theorem

• Formula:

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

• Significance:

  • Updates beliefs with evidence.

  • Foundation for probabilistic reasoning (Bayesian networks).

  • Handles uncertainty (vs. crisp logic).

Block World Problem

• Description: Robot manipulates blocks on table to achieve goal configuration.

• Significance:

  • Tests planning, knowledge representation (spatial relations).

  • Challenges: perception, grasping, motion planning.

• Recent Advancements:

  • Deep reinforcement learning (OpenAI's robotic hand).

  • Vision-based planning (RGB-D sensors).

Production Systems

• Structure:

  • Rules: IF condition THEN action.

  • Working Memory: Current facts.

  • Conflict Resolution: Choose which rule to fire (specificity, recency).

• Characteristics: Modular, explainable.

• Comparison:

  • vs. Logical systems: More procedural, efficient.

  • vs. Neural networks: Symbolic, interpretable.

Classical vs. Modern AI Systems

[!TIP] Exam Focus:

• A search:* Always state admissibility/consistency.

• Minimax/alpha-beta: Draw small game tree, show α/β updates.

• Resolution: Convert to CNF step-by-step.

• Frames vs. Scripts: Frames = static objects; Scripts = event sequences.

• Bayes' Theorem: Apply to simple diagnostic problems (e.g., disease testing).