intro AI - Unit 2 Slides

Introduction to AI and ML

Instructors: Dr. Nishant Gupta & Dr. Manoj Kumar

Knowledge Representation

Knowledge representation is a critical area within artificial intelligence that aims to represent knowledge about the world effectively to facilitate inference, which is the process of drawing conclusions based on that knowledge. This ability is essential for AI systems to perform reasoning and problem-solving tasks.

Purpose

The fundamental purpose of knowledge representation is to enable machines to reason about information much like humans by converting complex real-world scenarios into a structured format that can be processed and understood by AI systems. For example, arithmetic logic such as ( x >= 5 ) serves as a basic illustration of how logical statements can stipulate conditions or relationships.

Typically Based On

  1. Logic: This serves as the medium of conversation with AI systems, allowing for meaningful interpretation and interaction.

  2. Probability: Incorporating uncertainty into reasoning processes is vital since many real-world situations involve incomplete information.

  3. Combination of Logic and Probability: This advanced approach allows for more sophisticated reasoning that captures both deterministic relationships and probabilistic uncertainties.

Key Elements of Knowledge Representation

  1. Propositional Logic: A fundamental form of logic, where statements are represented as true or false.

  2. Objects and Relations: Core components that help in understanding the structure of the domain being represented.

  3. Degree of Belief: Represents varying confidence levels in one’s knowledge, acknowledging that not all knowledge is absolute.

  4. Degree of Truth: Distinguishes between binary true/false scenarios and those where truth is more nuanced.

  5. First Order Predicate Logic (FOPC): An extension of propositional logic that incorporates subjects and predicates to represent more complex assertions about the world.

  6. Temporal Logic: A form of logic that incorporates temporal aspects, allowing reasoning about time-dependent states.

  7. Fuzzy Logic: A system that deals with reasoning that is approximate rather than fixed and exact, thus effectively handling scenarios that involve vague concepts.

Components of Knowledge Representation

  1. Syntax: Establishes the rules governing valid sentence structures in the language of representation.

  2. Semantics: Assigns meaning to those sentences, providing context and significance.

  3. Inference Procedure: This algorithm is crucial for ensuring both correctness (soundness) and completeness (the ability to derive all truths) in the reasoning process.

  4. Complexity Considerations: Understanding the computational complexity of inference processes is essential for practical applications.

  5. Knowledge Base: The collection of knowledge within an AI system, which is organized for efficient retrieval and reasoning.

Structure of Knowledge Base

A knowledge base is composed of a set of sentences represented in a formal language, supported by an inference engine that processes these sentences to derive logical conclusions or make inferences based on the knowledge.

Declarative Approach

The declarative approach emphasizes what knowledge an agent needs to know rather than how to achieve it. This method allows agents to reason about their actions based on the knowledge they possess rather than just following strict procedural rules. Assessment of agents can occur at two levels:

  1. Knowledge Level: What they know and their understanding of the domain.

  2. Implementation Level: The underlying data structures and algorithms employed.

Propositional Logic: Syntax

Syntax of propositional logic includes:

  • Atomic Sentences: Basic symbols (e.g., P, Q) that represent simple propositions.

  • Connectives: Logical operators such as:

    • ( ^ ) (and)

    • ( V ) (or)

    • (
      eg ) (not)

    • ( \rightarrow ) (implies)

Semantics of Propositional Logic

Truth tables are utilized for evaluating logical structures, assigning truth values to the various connectives.

Syntactic Forms

  • Conjunction Normal Form (CNF): A standardized format that simplifies logical expressions into a conjunction of disjunctions.

  • Binary Clauses: Clauses that contain one or two literals.

  • Horn Clauses: Clauses containing at most one positive literal, which are pivotal in logic programming.

Key Concepts in Logic

  • Satisfiability: Determines if there exists an interpretation that makes a statement true.

  • Validity: A statement that is true under all interpretations.

  • Entailment: A relationship where one proposition logically follows from another.

KR Languages

Knowledge Representation languages integrate syntax and semantics to offer a structure for expressing knowledge. They use specific notation for logical expressions and facilitate the reasoning processes.

Reasoning Tasks

  1. Model Finding: Conducting satisfiability checks for knowledge bases.

  2. Deduction: Proving specific queries based on the knowledge base, which involves deriving new formulas from existing knowledge.

Propositional Logic: Inference

Inference processes in propositional logic involve mechanical derivations to reach conclusions through methods like:

  • Forward Chaining: A technique that exhaustively applies known rules to derive logical conclusions step by step.

  • Backward Chaining: A method that starts from a specific goal and works backward to known facts to determine if the goal can be achieved.

Planning in AI

Planning is a pivotal component of AI that allows for goal-oriented actions. The types of planning can be classified as:

  1. Classical Planning (Deterministic): Deals with fully observable environments and predictable outcomes.

  2. Non-Classical Planning (Stochastic): Includes uncertainty and variations in outcomes based on probabilistic models.

PDDL – Planning Domain Definition Language

PDDL is a language used to describe planning problems, detailing the initial state, available actions, results of actions, and goals to be achieved. It employs fluents, which are ground, functionless atoms that help define various states in the planning context.

Action Schemas in PDDL

Action schemas are structured to define particular actions, including:

  • Action name

  • Variables involved

  • Preconditions that must be met prior to execution

  • Effects resulting from executing the action

Example: Air Cargo Transportation Problem

This real-world problem involves defined actions such as Load, Unload, and Fly, ensuring that the predicates accurately reflect the changes in state after each action is performed.

Planning Graphs in AI

Planning graphs visually represent planning problems by displaying the relationships between actions and states. They construct layers that alternate between propositions (states of the world) and actions, helping to clarify the transitions.

Mutually Exclusive Actions and Literals (Mutex)

Mutex conditions define scenarios where two actions or literals cannot coexist in the same state. An example of this could be illustrated through the 'Have Cake and Eat Cake Too' problem, which demonstrates the logical constraints inherent in planning actions.

Conclusion

Understanding knowledge representation and planning is essential for developing robust AI systems that can reason, adapt, and achieve complex goals within uncertain environments. As our knowledge about AI continues to expand, these foundational concepts will play a critical role in shaping intelligent behavior in machines.