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

UNIT 2: ARTIFICIAL INTELLIGENCE - CORE CONCEPTS & TECHNIQUES

I. FOUNDATIONS & PROBLEM FORMULATION

Intelligence & AI Approaches

• Goal of AI: To create systems that can perform tasks requiring human-like intelligence (reasoning, learning, perception, language).

• Four Approaches:

  1. Acting Humanly: Turing Test; focuses on behavior.

  2. Thinking Humanly: Cognitive modeling; simulates human thought processes.

  3. Thinking Rationally: "Laws of thought"; uses logic for sound reasoning.

  4. Acting Rationally: Rational agent paradigm; chooses actions to maximize expected utility. This is the most successful modern approach.

• Rational Agent: An agent that acts to achieve the best outcome, or best expected outcome.

[!TIP] Exam Focus: Questions often ask to compare approaches or justify "acting rationally" as the best. Remember: Current AI (self-driving cars, recommender systems) is primarily acting rationally, not necessarily thinking or acting like a human.

Intelligent Agents (PEAS Framework)

• Agent Types:

  • Simple Reflex: Acts on current percept (condition-action rules). Limited by lack of memory.

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

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

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

• Goal-based vs. Utility-based: Goal-based seeks any state satisfying the goal; utility-based ranks all possible outcomes to choose the best one, even if all goals are met.

Problem Formulation

A well-defined problem specifies:

1. Initial State: Starting point.

2. Actions(s): Set of possible actions from a state.

3. Transition Model: Result of applying an action result(s, a).

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

5. Path Cost: Cost of a path (sum of step costs).

• Characteristics for AI Suitability: Large state space, lack of algorithmic solution, need for heuristics, presence of uncertainty or partial information.

• Example Problems:

  • Tic-Tac-Toe: Small state space, perfect information. Significance: Illustrates game tree search, minimax, alpha-beta.

  • Block World: Blocks on a table, robot arm moves blocks. Significance: Tests knowledge representation (predicates), planning, and robotics.

  • Water Jug: Given 4L & 3L jugs, get 2L in 4L jug. Production Rules: (Fill X), (Empty X), (Pour X Y).

II. SEARCH STRATEGIES & ALGORITHMS

Uninformed (Blind) Search

• b = branching factor, d = solution depth, m = max depth.

• BFS vs DFS: BFS is complete/optimal but memory-heavy. DFS is memory-efficient but can get stuck in infinite paths.

Informed (Heuristic) Search

• Best-First Search: General framework using an evaluation function f(n) to choose the most promising node.

• A Search:*

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

    • g(n): Actual cost from start to n.

    • h(n): Heuristic estimate from n to goal.

  • Admissibility: h(n) never overestimates true cost (h(n) ≤ h*(n)). Guarantees optimality.

  • Consistency (Monotonicity): For every node n and successor n', h(n) ≤ c(n,a,n') + h(n'). Implies admissibility; allows graph-search without re-opening nodes.

  • Properties: Complete, optimal, optimally efficient (no algorithm with same h expands fewer nodes).

  • How it combines: Uses g(n) like BFS (cost-so-far) and h(n) like greedy best-first (guidance).

  • \boxed{f(n) = g(n) + h(n)}

• AO Search:*

  • For AND/OR graphs (problems with subproblems that must all be solved).

  • Finds a solution graph (not just a path) with minimum cost.

  • Disadvantage vs A:* More complex; stores multiple partial solution graphs.

• Hill Climbing:

  • Algorithm: Iteratively move to neighbor with best f. Stops at local optimum.

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

  • Problems:

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

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

    • Ridges: Sequence of local maxima.

  [!TIP] Mitigation: Use random restarts, simulated annealing, or evolutionary algorithms.

• Bidirectional Search:

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

  • Meet in the middle. Advantage: Reduces time complexity roughly from $$\displaystyle O(b^d) $$ to $$\displaystyle O(b^{d/2}) $$.

Heuristic Evaluation & Risks

• Properties of a Good Heuristic: Admissible, consistent, high accuracy (close to true cost), easy to compute.

• Risks: Inadmissible heuristics lead to suboptimal solutions. Weak heuristics (e.g., h(n)=0) degrade to uniform-cost search.

• Mitigation: Design domain-specific heuristics; use pattern databases; combine multiple heuristics (h(n) = max(h1(n), h2(n), ...)).

III. ADVERSARIAL SEARCH & GAME THEORY

Minimax Algorithm

• Assumes: Two-player, zero-sum, perfect information, deterministic game.

• Procedure: Build game tree to terminal states. Max player (us) chooses max value; Min opponent chooses min value. Back up values from leaves.

• Objective: To maximize the worst-case payoff (guarantee a minimum outcome).

• Limitation: Explores entire game tree; exponential complexity $$\displaystyle O(b^m) $$.

Alpha-Beta Pruning

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

• Key Values:

  • α (alpha): Best (highest) value that MAX can guarantee at that point or above.

  • β (beta): Best (lowest) value that MIN can guarantee at that point or below.

• Cut-off: A node is pruned if its value becomes worse than the current α (for MIN node) or β (for MAX node).

• Impact: With good node ordering, complexity reduces to $$\displaystyle O(\sqrt{b^m}) $$. Effectiveness depends critically on node ordering.

• Variations: Aspiration windows, iterative deepening for ordering.

[!TIP] Exam Trap: Be able to trace α-β on a given tree and identify pruned nodes. Remember: pruning happens when value <= α at a MIN node or value >= β at a MAX node.

IV. KNOWLEDGE REPRESENTATION (KR)

Importance & Properties

• Role: Enables reasoning, inference, and knowledge sharing in AI systems.

• Properties of Good KR: Representational adequacy, inferential adequacy, inferential efficiency, clarity, expressiveness, modularity.

Logic-Based Representation

• Conversion to CNF (Clausal Form): Eliminate →, move ¬ inwards, standardize variables, Skolemize, distribute ∧ over ∨, split into clauses.

Structured Representation

• Differentiation: Frames (static situations), Scripts (dynamic sequences), Schemas (abstract frameworks).

• Frames Limitations: Brittle, difficult to handle exceptions. Enhancements: Add procedural attachments, default values, multiple inheritance with conflict resolution.

• Applications in Chatbots: Frames for user profiles, scripts for dialogue management, schemas for intent recognition.

Other KR Schemes

• Conceptual Dependency (CD): Represents meaning using a small set of primitive acts (e.g., ATRANS for transfer, MTRANS for mental transfer). Language-independent.

• CD vs Semantic Nets: CD uses standardized primitives and focuses on meaning; semantic nets are more general graphical structures for relationships.

Production Systems

• Structure:

  • Rule Base (Production Rules): IF <condition> THEN <action>.

  • Working Memory (WM): Global facts/data.

  • Inference Engine: Matches rules against WM, selects rule (conflict resolution), fires rule (updates WM).

• Characteristics: Modular, data-driven (forward chaining), good for expert systems. Contrast with algorithmic programs (control flow explicit).

V. REASONING & INFERENCE METHODS

Reasoning Types

• Forward Chaining: Starts with known facts, applies rules to derive new facts until goal is reached. Can be inefficient (fires many irrelevant rules).

• Backward Chaining: Starts with goal, works backward to find supporting evidence. Can get stuck in irrelevant paths if goal is wrong.

Resolution

• Principle: A rule of inference for clausal form. If two clauses contain complementary literals, they can be resolved into a new clause (resolvent).

• Resolution in PL: Simple unification of complementary literals.

• Resolution in FOPL: Requires unification (finding substitution to make literals identical). Uses refutation: Add negation of goal to KB, derive empty clause □ to prove goal.

• Steps: Convert KB & ¬Goal to CNF → Choose clauses → Unify → Resolve → Repeat until □ or no progress.

Control Knowledge

• Role: Guides the search/inference process to avoid combinatorial explosion. Decides which rule to fire, which node to expand, which path to explore.

• Examples: Heuristic f(n) in A*, α-β pruning in minimax, conflict resolution strategies (specificity, recency) in production systems.

Reasoning Paradigms

• Monotonic Reasoning: Adding knowledge never retracts previous conclusions. Classical logic is monotonic.

• Non-Monotonic Reasoning: Adding knowledge can invalidate previous conclusions. Essential for: Default reasoning ("Birds fly" except penguins), belief revision, real-world reasoning with incomplete/ changing info.

• Procedural vs. Declarative Knowledge:

  • Declarative: What is true (facts, rules). E.g., Grandparent(X,Z) :- Parent(X,Y), Parent(Y,Z).

  • Procedural: How to do something (algorithms, scripts). E.g., A* search procedure.

VI. CONSTRAINT SATISFACTION PROBLEMS (CSP)

• Definition: Problem defined by:

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

  • Domains: $$\displaystyle D_i $$ (possible values for $$\displaystyle X_i $$)

  • Constraints: Relations restricting simultaneous values (e.g., $$\displaystyle X_i \neq X_j $$).

• Examples: Map coloring, job scheduling, Sudoku.

• Solution Methods:

  • Backtracking Search: Depth-first, assigns values one variable at a time, backtracks on conflict. Enhanced with:

    • Variable Ordering: MRV (Minimum Remaining Values).

    • Value Ordering: Least Constraining Value.

    • Constraint Propagation: Arc Consistency (AC-3): Revises domains to remove inconsistent values.

  • Local Search (Min-Conflicts): Start with complete assignment, randomly pick conflicted variable, assign value minimizing conflicts. Effective for large CSPs like scheduling.

VII. PROBABILISTIC REASONING

Bayes' Theorem

• Statement:

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

• Derivation: From definition of conditional probability: $$\displaystyle P(A|B) = P(A \cap B)/P(B) $$ and $$\displaystyle P(B|A) = P(A \cap B)/P(A) $$.

• Significance: Allows updating beliefs (posterior probability P(A|B)) given new evidence B, using prior P(A) and likelihood P(B|A). Foundation of Bayesian Networks.

• Advantages: Handles uncertainty, combines prior knowledge with evidence, provides coherent probabilistic framework.

VIII. NATURAL LANGUAGE PROCESSING (NLP)

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

• Components of NLP Pipeline:

  1. Lexical Analysis: Tokenization, stemming, lemmatization.

  2. Syntactic Analysis: Parsing (syntactic structure).

  3. Semantic Analysis: Meaning representation (e.g., logical form).

  4. Discourse Integration: Context across sentences.

  5. Pragmatic Analysis: Intent, real-world knowledge.

• Applications in Expert Systems/Chatbots: Natural language interface (query parsing), dialogue management (using scripts/frames), information extraction.

• Ethical Implications (Surveillance): Privacy invasion, mass monitoring, bias in language models, lack of transparency. Mitigation: Regulations (GDPR), bias auditing, explainable AI, user consent.

IX. EXPERT SYSTEMS (ES)

• Definition: Computer system that emulates the decision-making ability of a human expert in a specific, narrow domain.

• Characteristics vs Conventional Programs:

  • High: Knowledge-intensive, symbolic reasoning, explainable, handles uncertainty (often).

  • Low: Data-intensive, numerical computation, "black-box", brittle outside domain.

• Architecture:

  | Component | Function | | :--- | :--- | | Knowledge Base | Stores domain facts & rules (heuristic knowledge). | | Inference Engine | Applies rules to facts (forward/backward chaining). | | User Interface | Interaction (natural language, forms). | | Explanation Facility | Explains reasoning (traces, justifications). | | Knowledge Acquisition | Tools for experts to add/modify knowledge. |

• Inference Engines:

  | Feature | Forward Chaining | Backward Chaining | | :--- | :--- | :--- | | Control | Data-driven | Goal-driven | | Search | Breadth-first in rule space | Depth-first in goal tree | | Best For | Monitoring, control, many facts | Diagnosis, explanation, few hypotheses | | Example | MYCIN (medical) | PROLOG (logic programming) |

• Development Challenges:

  • Knowledge Acquisition: Bottleneck; extracting tacit knowledge from experts.

  • Knowledge Representation: Choosing appropriate scheme (rules, frames).

  • Maintenance: Keeping KB consistent and up-to-date (version control, modular design).

• Benefits: Consistency, reproducibility, availability, cost-effective for training.

• Limitations: Knowledge acquisition bottleneck, brittleness (fails outside narrow domain), difficulty with common sense, high development cost.

X. INTERDISCIPLINARY NATURE & APPLICATIONS

• Interdisciplinary Roots:

  • Mathematics/Logic: Formal reasoning, probability, search algorithms.

  • Psychology/Cognitive Science: Human cognition, mental models.

  • Linguistics: Syntax, semantics for NLP.

  • Neuroscience: Inspiration for neural networks.

  • Computer Science: Implementation, algorithms, data structures.

• Solving Global Challenges:

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

  • Climate: Climate modeling, optimization of energy grids.

  • Education: Adaptive learning systems, intelligent tutoring.

• Classical vs Modern AI:

  | Aspect | Classical AI (Symbolic) | Modern AI (Statistical/Deep Learning) | | :--- | :--- | :--- | | Knowledge | Hand-coded, explicit rules | Learned from data, implicit | | Performance | Good on narrow, logical tasks | Excellent on perception (vision, speech) | | Adaptability | Brittle, poor generalization | Robust generalization, but data-hungry | | Explainability | High (traceable rules) | Low ("black-box") |