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

1. FOUNDATIONS & PROBLEM FORMULATION

AI Approaches & Definitions

• Four Classic Approaches:

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

  2. Thinking Humanly: Cognitive modeling, psychology experiments.

  3. Thinking Rationally: Laws of thought, logic-based reasoning.

  4. Acting Rationally: Rational agent paradigm (best for modern AI).

• Rational Agent: An agent that acts to achieve the best outcome, or best expected outcome. It is the most suitable approach as it encompasses reasoning, learning, and acting in complex, real-world environments where "perfect" human-like thought is unnecessary or impossible.

Intelligent Agents (PEAS Framework)

• Structure: Agent = Architecture + Program

• PEAS Analysis:

  | Component | Description | Example (Self-Driving Car) | | :--- | :--- | :--- | | Performance | Measure of success | Safety, legality, time | | Environment | Surroundings | Roads, other cars, traffic signals | | Actuators | Actions the agent performs | Steering, accelerator, brakes | | Sensors | Inputs from environment | Cameras, GPS, speedometer |

• Agent Types (Increasing Capability):

  1. Simple Reflex: Acts on current percept (condition-action rules). Fails in partially observable environments.

  2. Model-based: Maintains internal state (world model). Handles partial observability.

  3. Goal-based: Acts to achieve goals. Requires search/planning.

  4. Utility-based: Acts to maximize utility (preferences). Handles uncertainty and trade-offs.

• Differentiation: Goal-based vs. Utility-based

  • Goal-based: "Reach destination." Binary success/fail. Can lead to conflicts between multiple goals.

  • Utility-based: "Reach destination quickly, safely, and comfortably." Quantifies preferences. Optimizes among competing goals.

Problem Definition & Characteristics

• "Problem of AI": To build machines that perform tasks requiring human-like intelligence (reasoning, learning, perception).

• Suitability for AI: A problem is suitable if it has:

  • Well-defined goal state(s).

  • Clearly defined state space (set of all possible configurations).

  • Defined operators/actions to transition between states.

  • Path cost (optional, for optimization).

  • Initial state and goal test.

• Example: Tic-Tac-Toe

  • State Space: 3^9 = 19,683 possible board configurations.

  • Significance: Simple enough for exhaustive search (minimax), yet illustrates core concepts: state space, game tree, adversarial search, and the importance of heuristics (e.g., "take center if available").

[!TIP] Exam Focus: Be prepared to define PEAS for a given problem (e.g., medical diagnosis system) and clearly articulate the differences between agent types with examples.

2. PROBLEM-SOLVING & SEARCH STRATEGIES

Uninformed (Blind) Search

• Breadth-First Search (BFS)

  • Algorithm: Explore all neighbors at current depth before moving deeper. Uses FIFO queue.

  • Properties:

    • Complete? Yes (if branching factor finite).

    • Optimal? Yes (for unit step costs).

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

    • $b$ = branching factor, $d$ = depth of solution.

• Depth-First Search (DFS)

  • Algorithm: Explore as far as possible along one branch before backtracking. Uses LIFO stack.

  • Properties:

    • Complete? No (infinite paths). Yes with depth-limit.

    • Optimal? No.

    • Time: $$\displaystyle O(b^m) $$, Space: $O(bm)$ (stores single path).

    • $m$ = maximum depth.

  • Depth-Limited DFS: Avoids infinite paths by setting a limit l.

• Comparison: BFS vs. DFS

  | Feature | BFS | DFS | | :--- | :--- | :--- | | Memory | High (stores frontier) | Low (stores path) | | Optimality | Yes (unit cost) | No | | Completeness | Yes | No (unless limited) | | Best For | Shallow solutions | Deep, narrow spaces |

• Bidirectional Search: Simultaneously search forward from start and backward from goal. Meets in the middle. Advantage: Reduces time/space complexity roughly to $$\displaystyle O(b^{d/2}) $$.

Informed (Heuristic) Search

• Heuristic Function $h(n)$: Estimates cost from node n to goal. Admissible: Never overestimates true cost ($$\displaystyle h(n) \leq h^*(n) $$). Consistent: For every node n and successor n', $h(n) \leq c(n,a,n') + h(n')$.

• Best-First Search: General framework using evaluation function $f(n)$ to select most promising node. Greedy BFS uses $$\displaystyle f(n)=h(n) $$.

• A Search Algorithm*

  • Formula:

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

    *   $g(n)$: cost from start to `n`.

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

*   **How it works:** Combines UCS (via $g(n)$) and Greedy (via $h(n)$).

*   **Properties:**

    *   **Complete?** Yes (if step costs bounded below).

    *   **Optimal?** Yes, **if $h(n)$ is admissible**.

*   **Importance:** Gold standard for pathfinding/puzzle-solving (e.g., GPS navigation, 8-puzzle).

• AO Search Algorithm*

  • For AND-OR graphs (solutions may require multiple subgoals).

  • Finds a solution graph (minimum cost subtree).

  • Comparison A vs AO:**

    • A:* OR graph (one path to goal).

    • AO:* AND-OR graph (multiple subproblems).

    • AO* can be more efficient for decomposable problems but is more complex.

• Hill Climbing

  • Algorithm: Iteratively move to neighbor with best heuristic value.

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

  • Limitations:

    • Local maxima: Peak not highest in area.

    • Plateau: Flat area, all neighbors equal.

    • Ridge: Sequence of local maxima.

    • Not complete/optimal.

• Comparison: Hill Climbing vs. Best-First

  • Hill Climbing: Greedy, only looks at neighbors, no global view.

  • Best-First (A):* Maintains open/closed lists, considers all generated nodes, guarantees optimality with admissible heuristic.

[!TIP] Risks of Heuristic Search: Poor heuristics lead to suboptimal/incomplete search. Mitigation: Use admissible/consistent heuristics, combine with other strategies (e.g., A*), or use iterative deepening A* (IDA*).

Adversarial Search (Game Playing)

• Minimax Procedure

  • Context: Two-player, zero-sum, perfect-information games.

  • Objective: MAX player maximizes minimum guaranteed payoff (min over MIN's choices).

  • Algorithm: Recursively assign values: MAX nodes take max of children, MIN nodes take min.

  • Limitation: Exponential blowup ($$\displaystyle O(b^m) $$).

• Alpha-Beta Pruning

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

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

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

  • Cut-off Condition: At a MIN node, if $\alpha \geq \beta$, prune remaining children. At a MAX node, if $\beta \leq \alpha$, prune.

  • Variations: Iterative deepening, transposition tables, move ordering.

  • Worked Example: Given a game tree, trace $\alpha$, $\beta$ values and mark pruned nodes.

Constraint Satisfaction Problems (CSP)

• Formulation: Set of variables $X$, each with domain $D$, and constraints $C$ specifying allowable combinations.

• Backtracking Search: Depth-first search with variable assignments, backtrack on constraint violation.

• Local Search for CSP: Min-Conflicts heuristic (choose variable with most conflicts, assign value minimizing conflicts). Simulated annealing.

Production Systems

• Characteristics:

  • Rule Set (Production Rules): IF condition THEN action.

  • Working Memory (WM): Global database of current facts.

  • Rule Interpreter (Inference Engine): Matches rules to WM, resolves conflicts, fires rules.

• Differentiation: Unlike algorithmic/search-based approaches, production systems are data-driven, modular, and suitable for representing heuristic knowledge (expert systems).

3. KNOWLEDGE REPRESENTATION (KR)

Importance & Challenges

• Role: Enables deductive reasoning, inference, and knowledge sharing. Bridges raw data and intelligent behavior.

• Challenges: Incompleteness (missing knowledge), ambiguity (multiple interpretations), scalability (large knowledge bases), inconsistency, representational adequacy.

Logic-Based Representation

• Propositional Logic:

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

  • Semantics: Truth tables.

  • Limitations: No quantifiers, cannot represent objects/relations directly (e.g., "All humans are mortal" requires many propositions).

• First-Order Predicate Logic (FOPL)

  • Syntax:

    • Objects: Constants (a, b), variables (x, y).

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

    • Functions: Father(x), Sum(x,y).

    • Quantifiers: ∀ (for all), ∃ (there exists).

    • Connectives: ∧, ∨, ¬, →.

  • Expressiveness: Handles objects, relations, quantification. More compact and powerful than propositional.

  • Translation Example:

    1. Steve likes easy courses. → Likes(Steve, c) ∧ Easy(c)

    2. All CSE courses are easy. → ∀c (CSE(c) → Easy(c))

  • Clausal Form (CNF) Conversion Steps:

    1. Eliminate → and ↔.

    2. Move ¬ inwards (De Morgan).

    3. Standardize variables (rename apart).

    4. Skolemization: Remove ∃ by introducing Skolem functions/constants.

    5. Distribute ∧ over ∨.

    • Result: Conjunction of disjunctions (clauses).

• Resolution

  • Principle: If $(A \vee L)$ and $(\neg L \vee B)$ are true, then $(A \vee B)$ (the resolvent) is true.

  • Proof by Refutation: To prove goal G, add ¬G to KB. If unsatisfiable (empty clause derived), G is true.

  • Worked Example: Given clauses, show resolution steps leading to contradiction.

Structured & Procedural Representation

• Semantic Networks: Graph with nodes (objects/concepts) and edges (relations). Example: [John] --(loves)--> [Mary].

• Frames

  • Concept: Structured object with slots (attributes) and values.

  • Example (Room Frame):

    
    Room:
    
      -has-part: walls, floor, ceiling
    
      -typical-use: living, working
    
      -typical-size: medium
    
    

  • Application (Legal Advice ES): Frames for Case, Law, Precedent with slots like jurisdiction, key-facts, ruling.

  • Limitations: Static, poor with exceptions, inheritance issues (multiple inheritance conflicts).

  • Enhancements: Add demons (triggers on slot access), default values, multiple inheritance with priority.

• Scripts & Schemas

  • Scripts: Temporal sequences of events in a stereotypical context (e.g., Restaurant-Script: Enter → Be seated → Order → Eat → Pay → Leave).

  • Schemas: More general, static knowledge structures (like frames but for events/plans).

  • Differentiation:

    • Frames: Object-centered, static properties.

    • Scripts: Event-centered, temporal sequence.

    • Schemas: Higher-level, abstract structures (can contain frames/scripts).

  • Application in NLP/Chatbots: Manage dialog context, predict user intent, fill slots (e.g., Booking-Script with slots: date, time, party-size).

• Conceptual Dependency (CD)

  • Goal: Represent meaning independent of surface wording using primitive acts (ATRANS, PTRANS, MOVE, INGEST, etc.).

  • Example: "John gave Mary a book" → ATRANS(book) FROM(John) TO(Mary).

• Comparison: CD vs. Semantic Networks

  • CD: Focus on actions/events with primitives. More procedural, aimed at NLP parsing.

  • Semantic Nets: Focus on objects/concepts and their relations. More declarative.

Procedural vs. Declarative Knowledge

• Declarative ("What"): Stored facts/assertions. Example: Capital(France, Paris).

• Procedural ("How"): Rules/procedures for using knowledge. Example: IF goal is to travel to Paris AND you have money THEN book flight.

• Comparison: Declarative is easier to modify but may be inefficient. Procedural is efficient but harder to change.

Control Knowledge

• Definition: Meta-knowledge about how to use the knowledge base (e.g., which rule to fire next, which goal to pursue).

• Role: Guides search/inference, improves efficiency (e.g., conflict resolution strategies in production systems).

4. REASONING & INFERENCE METHODS

Forward Chaining (Data-Driven)

• Algorithm:

  1. Start with known facts in WM.

  2. Find all rules whose IF part matches WM.

  3. Fire rules (add THEN part to WM).

  4. Repeat until goal found or no new facts.

• Suitable Scenarios: Many initial facts, specific goal (e.g., monitoring systems, diagnosis from symptoms).

Backward Chaining (Goal-Driven)

• Algorithm:

  1. Start with goal to prove.

  2. Find rules whose THEN part matches goal.

  3. Add rule's IF parts as subgoals.

  4. Recursively prove subgoals (using facts or further rules).

• Suitable Scenarios: Clear hypothesis/goal, need evidence (e.g., expert system diagnosis, legal reasoning).

Comparison: Forward vs. Backward Chaining

Non-Monotonic Reasoning

• Definition: Reasoning where conclusions can be retracted when new evidence arrives.

• Distinction from Monotonic: Monotonic reasoning only adds conclusions ($KB \subseteq KB' \Rightarrow Con(KB) \subseteq Con(KB')$). Non-monotonic does not hold.

• Essential Scenarios: Default reasoning ("Birds fly, unless penguin"), belief revision, commonsense reasoning (incomplete/uncertain info). Critical in medical diagnosis, legal reasoning, robotics.

5. EXPERT SYSTEMS (ES)

Definition & Role

• Definition: Computer programs that emulate human expert decision-making in a narrow domain using knowledge and inference.

• Role: Capture and disseminate scarce expertise, provide consistent advice, work in hazardous environments.

Key Characteristics

• High performance, reliability, understandability (explain reasoning), reasoning with meta-knowledge, symbolic reasoning, narrow domain focus.

Components

1. Knowledge Base: Facts, rules, frames, heuristics.

2. Inference Engine: Uses forward/backward chaining, handles uncertainty.

3. User Interface: Interaction (natural language, forms).

4. Explanation Facility: Crucial for trust. Answers "Why?" and "How?" questions.

5. Knowledge Acquisition Facility: Tools for experts to input knowledge (shells, editors).

Inference Engines in Detail

• Forward Chaining in ES: Data-driven. Good for monitoring, prediction, control (e.g., process control, alarm systems).

• Backward Chaining in ES: Goal-driven. Good for diagnosis, planning, classification (e.g., medical diagnosis, troubleshooting).

• Scenario Suitability: Use forward when many symptoms → disease; backward when suspect disease → ask for symptoms.

Benefits

• Permanence, reproducibility, cost-effective (no expert time), can work in dangerous environments, can explain decisions.

Limitations & Challenges

• Knowledge Acquisition Bottleneck: Hard to extract, formalize expert knowledge.

• Knowledge Representation Limits: Struggles with common sense, analogical reasoning, learning.

• Brittleness: Fails outside narrow domain.

• Maintenance: Knowledge base becomes outdated; difficult to update.

• No common sense: Cannot handle novel situations gracefully.

Design & Development Considerations

• Domain Selection: Narrow, well-defined, with expert available.

• Knowledge Engineer-Expert Collaboration: Critical for KB construction.

• KR Scheme Choice: Rules vs. frames vs. networks.

• Validation & Verification: Ensure correctness and completeness.

• User Training: On system capabilities/limitations.

Application Example: Legal Advice ES

• KB: Frames for Case, Law, Precedent; rules for IF law applies AND precedent supports THEN outcome.

• Keeping Knowledge Updated:

  1. Regular Expert Review: Periodic sessions with legal experts.

  2. Machine Learning Integration: Use NLP to scan new legislation/case law, suggest updates.

  3. Change Detection Alerts: Monitor legal databases for relevant updates.

  4. User Feedback Loop: Allow lawyers to flag outdated rules.

6. NATURAL LANGUAGE PROCESSING (NLP)

Definition & Significance

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

• Significance: Powers chatbots, translation (Google Translate), sentiment analysis, search engines, information extraction, accessibility tools.

Components of NLP Pipeline

1. Morphological Analysis: Word structure (stemming, lemmatization).

2. Syntactic Analysis (Parsing): Grammar structure (POS tagging, constituency/dependency parsing).

3. Semantic Analysis: Meaning (word sense disambiguation, logical form).

4. Pragmatic Analysis: Contextual meaning (speech acts, implicature).

5. Discourse Processing: Cohesion across sentences (anaphora resolution).

Knowledge Representation in NLP

• Application: Scripts/Schemas/Frames manage dialog context and user intent in chatbots/VAs.

  • Example: Booking-Script frame with slots: [destination, date, time, passengers]. System tracks filled slots, prompts for missing ones, handles confirmations.

  • Benefit: Provides structure for multi-turn dialog, handles defaults, enables context-aware responses.

Conceptual Dependency (CD) Analysis

• Uses primitive acts (ATRANS, PTRANS, MOVE, INGEST, EXPEL, etc.) to represent meaning independent of wording.

• Example: "The chef cooked the meal" → INGEST(meal) BY(chef) WITH(cooking).

• Goal: Enable inference (e.g., if INGEST happened, then PTRANS of food to stomach likely follows).

Ethical Implications of NLP in Surveillance

• Risks: Privacy violation (mass monitoring), bias amplification (training data biases), misuse (social control, suppression of dissent), lack of transparency.

• Mitigation Strategies:

  • Regulation: Laws governing data collection/use (e.g., GDPR).

  • Transparency: Audit trails, explainable AI for NLP decisions.

  • Bias Mitigation: Diverse training data, fairness metrics, debiasing algorithms.

  • Ethical Design: Privacy-by-design, purpose limitation, user consent.

7. SPECIALIZED PROBLEMS & APPLICATIONS

The Blocks World Problem

• Definition: AI problem where a robotic arm manipulates blocks on a table to achieve a goal stack (e.g., A on B on C).

• Significance: Classic benchmark for planning, reasoning about actions (STRIPS), robotics perception-action.

• Recent Advancements: Integration with computer vision (object detection), deep reinforcement learning for grasp planning, sim-to-real transfer, compliant control for safe interaction.

Bayes' Theorem & Probabilistic Reasoning

• Statement:

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

*   $P(A|B)$: Posterior (updated belief).

*   $P(A)$: Prior (initial belief).

*   $P(B|A)$: Likelihood.

*   $P(B)$: Evidence (normalizing constant).

• Significance: Foundation for Bayesian networks, handles uncertainty, updates beliefs with evidence.

• Advantages: Explicit uncertainty, combines prior knowledge + data, interpretable probabilistic models, sound mathematical basis.

Classical vs. Modern AI Systems

[!TIP] Exam Focus: Be ready to apply Bayes' Theorem to a simple diagnostic problem. Understand the paradigm shift: classical AI focused on reasoning with symbols; modern AI focuses on learning patterns from data.