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

3.1 Logic-Based Representation

Propositional Logic

• Syntax: Uses propositional symbols (e.g., P, Q) and logical connectives (¬, ∧, ∨, →, ↔).

• Semantics: Truth values assigned to propositions; truth tables define connectives.

• Limitations:

  • Cannot represent internal structure of propositions (e.g., "All humans are mortal").

  • Limited expressiveness for complex domains.

  • No quantifiers or variables.

First-Order Predicate Logic (FOPL)

• Syntax:

  • Predicates: Express properties/relations (e.g., Likes(Steve, CS3101)).

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

  • Variables: Represent objects (e.g., x, y).

  • Constants, Functions: Represent specific objects/transformations.

• Expressiveness: Superior to propositional logic; can represent objects, relations, quantification.

• Translation Example (from Dec 2023 paper):

  • Facts:

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

    2. Science courses are hard → ∀c (ScienceCourse(c) → Hard(c))

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

    4. CS3101 is a CSE course → CSECourse(CS3101)

  • Goal: Prove Steve likes CS3101.

• Clausal Form (CNF) Conversion:

  1. Eliminate →, ↔.

  2. Move ¬ inward (Negation Normal Form).

  3. Standardize variables.

  4. Skolemize existential quantifiers.

  5. Drop ∀.

  6. Distribute ∧ over ∨.

  • Example: ∀x (P(x) → Q(x)) becomes ¬P(x) ∨ Q(x).

Inference in Predicate Logic

• Resolution Principle:

  • Unify two clauses containing complementary literals.

  • Produce resolvent (new clause).

  • Requires clauses in CNF.

• Refutation:

  • Negate goal.

  • Add to knowledge base.

  • Apply resolution until empty clause (⊥) derived → goal proven.

• Example Proof (Steve's courses):

  • KB in CNF:

    1. ¬ScienceCourse(c) ∨ ¬Hard(c) (from 2)

    2. ¬CSECourse(c) ∨ Easy(c) (from 3)

    3. CSECourse(CS3101) (from 4)

    4. ¬Easy(c) ∨ Likes(Steve, c) (from 1, after Skolemization)

    5. ¬Likes(Steve, CS3101) (negated goal)

  • Resolution steps:

    • 3 + 2 → Easy(CS3101)

    • Easy(CS3101) + 4 → Likes(Steve, CS3101)

    • Likes(Steve, CS3101) + 5 → ⊥ (empty clause)

  • Conclusion: Steve likes CS3101.

Reasoning Strategies

[!TIP] Exam Tip: Forward chaining may fire many irrelevant rules; backward chaining may get stuck in irrelevant subgoals. Choose based on data availability and goal clarity.

3.2 Probabilistic Reasoning

Bayes' Theorem

• Statement:

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

where:

• \( P(A|B) \): Posterior probability of A given B.

• \( P(B|A) \): Likelihood.

• \( P(A) \): Prior probability.

• \( P(B) \): Marginal likelihood (normalizing constant).

• Derivation: From definition of conditional probability: \( P(A|B) = \frac{P(A \cap B)}{P(B)} \) and \( P(B|A) = \frac{P(A \cap B)}{P(A)} \).

• Significance:

  • Handles uncertainty by updating beliefs with evidence.

  • Foundation for Bayesian networks, probabilistic inference.

  • Compared to other frameworks (e.g., Dempster-Shafer), Bayes' is mathematically rigorous but assumes conditional independence.

• Applications: Medical diagnosis, spam filtering, risk assessment.

[!TIP] Common Pitfall: \( P(B) \) must consider all possible hypotheses: \( P(B) = \sum_i P(B|H_i)P(H_i) \). Ignoring this leads to incorrect posteriors.

3.3 Structured Representations

Semantic Networks

• Structure: Nodes (concepts/objects) connected by labeled links (relations).

  • Example: [Cat] --(is-a)--> [Animal], [Cat] --(has-part)--> [Tail].

• Representation: Encodes relationships hierarchically (e.g., inheritance).

• Comparison with Conceptual Dependency:

  • Semantic networks: Focus on semantic relationships; less formal.

  • Conceptual Dependency: Uses primitive acts (e.g., ATRANS, PTRANS) for meaning representation; more suited for NLP.

Frames

• Structure:

  • Slots: Attributes (e.g., color, size).

  • Facets: Slot properties (e.g., default, range).

  • Inheritance: Subframes inherit slots from superframes.

• Example: Car frame with slots: brand: (default Toyota), mileage: (range 10-50 kmpl).

• Applications: Knowledge bases for objects/concepts (e.g., medical diagnosis).

• Limitations:

  • Rigid structure; hard to represent dynamic/uncertain knowledge.

  • Inheritance may cause inconsistencies.

• Enhancements: Add procedural attachments, default values, non-monotonic reasoning.

Scripts and Schemas

• Definitions:

  • Scripts: Structured sequences of events in stereotypical situations (e.g., "Restaurant script": enter → order → eat → pay).

  • Schemas: Broader knowledge structures about concepts/events (similar to frames but for situations).

• Differences from Frames:

  • Frames: Static object descriptions.

  • Scripts/Schemas: Dynamic, event-based, with temporal ordering.

• Applications in NLP/Chatbots:

  • Predict next actions in dialogue (e.g., after "I'd like to book a table", script suggests asking for date/time).

  • Improve coherence by understanding context.

Conceptual Dependency Analysis

• Primitive Acts: Universal actions (e.g., ATRANS = abstract transfer, PTRANS = physical transfer, MOVE).

• Representation: Meaning decomposed into primitives (e.g., "John gave Mary a book" → ATRANS(John, Mary, Book)).

• Comparison with Semantic Networks:

  • Semantic networks: Graph-based, relation-focused.

  • Conceptual Dependency: Action-oriented, language-independent, designed for NLP parsing/generation.

[!TIP] Exam Tip: Frames are for objects, scripts for event sequences. In chatbots, scripts help manage dialogue flow, frames store user/profile data.

3.4 Other Representation Issues

Procedural vs Declarative Knowledge

Control Knowledge

• Role: Guides problem-solving by determining which rule/action to apply next.

• Examples:

  • In expert systems: meta-rules for rule selection.

  • In search: heuristics (e.g., in A*).

• Importance: Reduces search space, improves efficiency.

Non-Monotonic Reasoning

• Definition: Reasoning where conclusions can be retracted when new evidence arrives (unlike monotonic logic where conclusions only increase).

• Distinction:

  • Monotonic: If \( \Gamma \vdash \phi \), then \( \Gamma \cup \Delta \vdash \phi \) (adding knowledge doesn't invalidate).

  • Non-monotonic: Adding \( \Delta \) may retract \( \phi \).

• Scenarios Requiring Non-Monotonicity:

  • Default Reasoning: "Birds can fly" (default), but "Penguins are birds that cannot fly" → exception.

  • Belief Revision: Updating beliefs with contradictory evidence.

  • Common-Sense Reasoning: Incomplete knowledge, assumptions.

• Implementation: Default logic, circumscription, truth maintenance systems.

Challenges in Knowledge Representation

• Common Problems:

  1. Common-Sense Knowledge: Vast, implicit, hard to formalize.

  2. Uncertainty: Real-world knowledge is often probabilistic.

  3. Scalability: Representations must handle large, complex domains.

  4. Inconsistency: Handling conflicting information.

  5. Dynamic Knowledge: Updating representations efficiently.

• Importance for Deductive Reasoning:

  • Effective representation ensures sound, complete, and efficient inference.

  • Poor representation leads to combinatorial explosion or incorrect conclusions.

[!TIP] Exam Tip: Non-monotonic reasoning is key for real-world AI (e.g., diagnostic systems). Remember default reasoning examples (birds, Tweety). In knowledge representation, always consider trade-offs: expressiveness vs. computational complexity.