CS2910 Revision Notes

Symbolic AI Revision Notes (CS2910 2024-25)

1. Search Algorithms

1.1 Uninformed Search

• Definition: Explore state space without domain-specific knowledge
• Types:
  • Breadth-First Search (BFS)
    • Expands shallowest nodes first
    • Complete & optimal for uniform costs
    • Space: O(b^d)
  • Depth-First Search (DFS)
    • Expands deepest nodes first
    • Not complete (infinite depth), not optimal
    • Space: O(bm)
  • Iterative Deepening
    • Combines BFS completeness with DFS space efficiency
    • Time: O(b^d)

1.2 Informed Search

• Heuristic Function h(n): Estimates cost to goal
• Greedy Best-First
  • Minimizes h(n)
  • Incomplete, not optimal
• A Algorithm*
  • Minimizes f(n) = g(n) + h(n)
  • Requirements:
    • Admissible h(n) ≤ h*(n)
    • Consistent h(n) ≤ c(n,a,n’) + h(n’)
  • Properties: Complete & optimal

1.3 Adversarial Search

• Minimax Algorithm:
  • MAX (player) maximizes utility
  • MIN (opponent) minimizes utility
  • Complexity: O(b^m)
• Alpha-Beta Pruning:
  • Prunes irrelevant branches
  • Optimal pruning reduces complexity to O(b^(m/2))

2. Logical Inference

2.1 Propositional Logic

• Syntax:
  • Atoms: P, Q, R
  • Connectives: ¬, ∧, ∨, →, ↔
• Semantics:
  • Truth tables
  • Validity & Satisfiability
• Inference Methods:
  • Resolution:

    α ∨ β, ¬β ∨ γ => α ∨ γ

  • Forward Chaining: Data-driven (KB → Query)
  • Backward Chaining: Goal-driven (Query → KB)

2.2 First-Order Logic (FOL)

• Syntax:
  • Variables, Constants, Predicates, Quantifiers (∀, ∃)
• Unification:
  • Find substitution θ s.t. Pθ = Qθ
  • MGU (Most General Unifier) algorithm
• Resolution in FOL:
  • Lifts propositional resolution with unification
  • Requires conversion to CNF

2.3 Inference Mechanisms

Mechanism	Direction	Use Case
Forward Chaining	Bottom-up	Rule-based systems
Backward Chaining	Top-down	Goal-directed queries
Resolution	Both	Automated theorem proving

3. Knowledge Representation

3.1 Frames & Semantic Networks

• Frames: Object-oriented representation with slots
• Semantic Networks:
  • Nodes = concepts
  • Edges = relationships (is-a, part-of)
• Default Reasoning:
  • Negation-as-Failure (NAF)
  • “Assume P true unless proven otherwise”

3.2 Temporal Reasoning

• Situation Calculus:
  • States as sequences of actions
  • Frame Problem: Representing unchanged fluents
• Event Calculus:
  • Events initiate/terminate fluents
  • Time points & intervals

4. Planning

4.1 Classical Planning (STRIPS)

• Components:
  • States: Conjunctions of atoms
  • Goals: Partially specified states
  • Operators: Precondition/Effect pairs
• Algorithms:
  • Forward State-Space Search
  • Backward Goal Regression
• Planning Graphs (GRAPHPLAN):
  • Mutex relations prevent conflicting actions
  • Polynomial-time plan existence checking

5. Inductive Learning

5.1 Decision Trees

• Entropy: Measure of impurity

  Entropy(S) = -Σ p_i log₂ p_i

• ID3 Algorithm:

  • Select attributes with maximum Information Gain

$$IG(S,A) = Entropy(S) - Σ (|S_v|/|S|) Entropy(S_v)
$$

5.2 Inductive Logic Programming

• Inverse Resolution:

  • Generalize clauses from examples
  • Combines background knowledge with training data

• FOIL Algorithm:

  • Learns Horn clauses from positive/negative examples

6. Prolog Programming

6.1 Key Features

• Unification: Pattern matching with variables

p(X, f(Y)) = p(a, f(b)) % X=a, Y=b

• Depth-First Search: With backtracking
• Cut Operator (!): Prunes search space

6.2 Example: Family Relations

parent(john, mary).
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

7. Historical Foundations

7.1 Key Papers

• McCulloch & Pitts (1943): Neural network models
• Dartmouth Proposal (1956): Coined “Artificial Intelligence”
• Turing (1950): Computing Machinery & Intelligence

7.2 Philosophical Issues

• Frame Problem
• Symbol Grounding
• Commonsense Reasoning

Exam Strategy

1. Prioritize Core Topics:

• Search algorithms (40%)
• Logical inference (30%)
• Learning & Planning (30%)

2. Practice Techniques:

• Manual resolution proofs
• A* heuristic calculations
• Decision tree construction

3. Time Management:

• Allocate 1.5 mins per mark
• Answer known questions first
• Use bullet points for concise answers