Knowledge Representation and Reasoning Lecture Notes PDF

KNOWLEDGE REPRESENTATION AND REASONING Lecture Notes Course organization 4K Lecture (14h): 3h lectures on Week 5, 7, 9, and 11, 2h Colloquium in Week 13 Lab activity (14h): 2h lab work sessions each even week on Weeks 2, 4, 6, 8, 10, 12, 14 Evaluation via Colloquium in Week 13 Contac...

KNOWLEDGE REPRESENTATION AND REASONING Lecture Notes Course organization 4K Lecture (14h): 3h lectures on Week 5, 7, 9, and 11, 2h Colloquium in Week 13 Lab activity (14h): 2h lab work sessions each even week on Weeks 2, 4, 6, 8, 10, 12, 14 Evaluation via Colloquium in Week 13 Contact: Lect. PhD Eng. Corina Cîmpanu [email protected] Evaluation FG = 30%LG + 70%CG Laboratory Grade Colloquium Grade LG = 50% AG + 50% HWPG CG = 40%HWG + 60%WEG AG - Activity grade NH - HomeWork grade HWPG - HomeWork Presentation Grade NWE - Written essay on specific subject  I. KNOWLEDGE REPRESENTATION IN AI Lecture 1 Outline Introduction to Knowledge Representation The Role of Knowledge Representation in AI Knowledge Representation Techniques Reasoning with Knowledge Applications of Knowledge Representation Conclusion 1. Introduction to Knowledge Representation Knowledge Representation Representation of Information Reasoning with Information Key Goals of Knowledge Representation Expressiveness Efficiency Inferential Adequacy Inferential Efficiency Understandability Knowledge Types in KRR Declarative Knowledge Procedural Knowledge Meta-Knowledge Knowledge Representation Schemes Logic-based Representations Semantic Networks Frames Ontologies Rule-Based Systems 2. The Role of Knowledge Representation in AI Enabling Machine Understanding Supporting Reasoning and Inference ○ Deductive Reasoning ○ Abductive Reasoning 2. The Role of Knowledge Representation in AI (2) Facilitating Communication Learning and Adaptation Supporting AI Reasoning in Uncertainty 2. The Role of Knowledge Representation in AI (3) Planning and Problem-Solving Interpreting Complex Data Natural Language Understanding 3. Knowledge Representation Techniques Logic-Based Representation: ○ Propositional Logic ○ Predicate Logic Semantic Networks Frames Ontologies Rule-Based Systems 3.1.1. Propositional logic In this example, we will define a simple propositional logic scenario using MATLAB. We'll represent facts about a specific situation and evaluate logical expressions based on these facts. Scenario Let's assume we have the following propositions: P: "It is raining." Q: "The ground is wet." We can establish the following logical relationship: If it is raining (P), then the ground is wet (Q). This can be expressed in propositional logic as: P → Q (If P, then Q) We'll implement this in MATLAB, allowing us to evaluate the truth value of different combinations of these propositions. Define Propositions: We'll define the propositions as binary variables (0 for false, 1 for true). Evaluate Logical Implication: We'll implement the implication logic and check whether it holds true for the given propositions. Propositional logic close all; clear all; clc; % Define propositions % 0 = False, 1 = True P = 1; % It is raining Q = 0; % The ground is wet % Display the values of propositions fprintf('Proposition P (It is raining): %d\n', P); Proposition P (It is raining): 1 fprintf('Proposition Q (The ground is wet): %d\n', Q); Proposition Q (The ground is wet): 0 % Evaluate the logical implication P → Q % Logical implication can be represented as: ~P OR Q implication = (~P || Q); % Evaluate P → Q % Display the result of the implication if implication fprintf('The implication (P → Q) is TRUE.\n'); else fprintf('The implication (P → Q) is FALSE.\n'); end The implication (P → Q) is FALSE. % Now, let's explore different scenarios fprintf('\nExploring different scenarios:\n'); Exploring different scenarios: % Scenario 1: It is raining and the ground is wet P = 1; % It is raining Q = 1; % The ground is wet implication = (~P || Q); fprintf('Scenario 1 - P: %d, Q: %d, Implication: %d\n', P, Q, implication); Scenario 1 - P: 1, Q: 1, Implication: 1 % Scenario 2: It is raining and the ground is NOT wet P = 1; % It is raining Q = 0; % The ground is NOT wet implication = (~P || Q); fprintf('Scenario 2 - P: %d, Q: %d, Implication: %d\n', P, Q, implication); Scenario 2 - P: 1, Q: 0, Implication: 0 % Scenario 3: It is NOT raining and the ground is wet P = 0; % It is NOT raining Q = 1; % The ground is wet implication = (~P || Q); fprintf('Scenario 3 - P: %d, Q: %d, Implication: %d\n', P, Q, implication); Scenario 3 - P: 0, Q: 1, Implication: 1 % Scenario 4: It is NOT raining and the ground is NOT wet P = 0; % It is NOT raining Q = 0; % The ground is NOT wet implication = (~P || Q); fprintf('Scenario 4 - P: %d, Q: %d, Implication: %d\n', P, Q, implication); Scenario 4 - P: 0, Q: 0, Implication: 1 3.1.1. Propositional logic Proposition P (It is raining): 1 Proposition Q (The ground is wet): 0 The implication (P → Q) is FALSE. Exploring different scenarios: Scenario 1 - P: 1, Q: 1, Implication: 1 Scenario 2 - P: 1, Q: 0, Implication: 0 Scenario 3 - P: 0, Q: 1, Implication: 1 Scenario 4 - P: 0, Q: 0, Implication: 1 3.1.2. Predicate Logic Scenario Let’s create a scenario that represents some knowledge about people and their relationships. We will represent the following facts: Predicates: ○ Person(x): x is a person. ○ Likes(x, y): x likes y. ○ Parent(x, y): x is a parent of y. Facts: ○ Alice is a person. ○ Bob is a person. ○ Charlie is a person. ○ Alice likes Bob. ○ Alice is a parent of Charlie. ○ Bob likes Charlie. Predicate Logic % Clear workspace close all; clear all; clc; % Define facts using structures people = {'Alice', 'Bob', 'Charlie'}; likes = {'Alice', 'Bob'; 'Bob', 'Charlie'}; parents = {'Alice', 'Charlie'}; % Display Facts fprintf('Facts:\n'); Facts: fprintf('People: %s, %s, %s\n', people{1}, people{2}, people{3}); People: Alice, Bob, Charlie fprintf('Likes:\n'); Likes: fprintf('Parents:\n'); for i = 1:size(likes, 1) Parents: fprintf('%s likes %s\n', likes{i, 1}, likes{i, 2}); for i = 1:size(parents, 1) end fprintf('%s is a parent of %s\n', parents{i, 1}, parents{i, 2}); Alice likes Bob Bob likes Charlie end Alice is a parent of Charlie % Implementing Inference: Check if a person likes another person function result = checkLikes(likes, person1, person2) result = any(strcmp(likes(:,1), person1) & strcmp(likes(:,2), person2)); end % Implementing Inference: Check if person1 is a parent of person2 function result = checkParent(parents, parent, child) result = any(strcmp(parents(:,1), parent) & strcmp(parents(:,2), child)); end % Testing Inferences % Check if Bob likes Charlie fprintf('\nInference Results:\n'); if checkLikes(likes, 'Bob', Inference Results: 'Charlie') % Check if Alice likes Bob fprintf('Bob likes Charlie: if checkLikes(likes, 'Alice', 'Bob') TRUE\n'); fprintf('Alice likes Bob: TRUE\n'); else else fprintf('Bob likes Charlie: FALSE\n'); fprintf('Alice likes Bob: FALSE\n'); end end Bob likes Charlie: TRUE Alice likes Bob: TRUE % Check if Alice is % Check if Alice is a parent of % Check if Bob is a parent of Charlie Facts: Charlie People: Alice, Bob, Charlie if checkParent(parents, 'Alice', Likes: if checkParent(parents, 'Bob', Alice likes Bob 'Charlie') 'Charlie') Bob likes Charlie Parents: fprintf('Alice is a parent of fprintf('Bob is a parent of Alice is a parent of Charlie Charlie: TRUE\n'); Charlie: TRUE\n'); Inference Results: else Alice likes Bob: TRUE else Bob likes Charlie: TRUE fprintf('Alice is a parent of Alice is a parent of Charlie: TRUE fprintf('Bob is a parent of Charlie: FALSE\n'); Bob is a parent of Charlie: FALSE Charlie: FALSE\n'); end end Alice is a parent of Charlie: TRUE Bob is a parent of Charlie: FALSE Facts: People: Alice, Bob, Charlie Likes: Alice likes Bob Bob likes Charlie Parents: Alice is a parent of Charlie Inference Results: Alice likes Bob: TRUE Bob likes Charlie: TRUE Alice is a parent of Charlie: TRUE Bob is a parent of Charlie: FALSE 3.2. Semantic Networks Scenario Let’s create a simple semantic network that represents relationships between different animals. The network will include the following concepts and relationships: Nodes (concepts): ○ Dog ○ Cat ○ Animal ○ Mammal ○ Bird Edges (relationships): ○ Dog is a Mammal ○ Cat is a Mammal ○ Mammal is a Animal ○ Bird is a Animal ○ Dog is a Animal ○ Cat is a Animal 3.2. Semantic Networks 1. Define Nodes and Relationships 2. Visualize the Semantic Network Nodes and Edges Creating a Directed Graph Plotting the Graph Displaying Information Semantic Networks % Clear workspace clc; clear; % Define nodes (concepts) nodes = {'Dog', 'Cat', 'Mammal', 'Bird', 'Animal'}; % Define relationships (edges) % Each row corresponds to a relationship from node i to node j edges = [ 1, 3; % Dog is a Mammal 2, 3; % Cat is a Mammal 3, 5; % Mammal is an Animal 4, 5; % Bird is an Animal 1, 5; % Dog is an Animal 2, 5 % Cat is an Animal ]; % Create a directed graph G = digraph(edges(:,1), edges(:,2), 'OmitSelfLoops'); % Plot the semantic network figure; plot(G, 'Layout', 'layered', 'NodeLabel', nodes); title('Semantic Network of Animals'); xlabel('Concepts'); ylabel('Relationships'); grid on; 3.3. Frames Scenario Let’s create a frame to represent a simple car. We will define the following attributes for the car: Type: sedan Color: red Owner: John Engine: ○ Type: V6 ○ Horsepower: 300 This example will demonstrate how to represent a frame using structures in MATLAB, allowing for both flat and nested attributes. 3.3. Frames Define the Frame Access and Modify Attributes Defining the Frame Displaying the Frame Accessing Attributes Modifying Attributes Adding New Attributes Nested Frames Frames % Clear workspace close all; clear all; clc; % Define the frame for a car % Display the car frame car.Frame = struct(... disp('Car Frame:'); 'Type', 'Sedan',... Car Frame: 'Color', 'Red',... disp(car.Frame); Type: 'Sedan' 'Owner', 'John',... Color: 'Red' 'Engine', struct(... Owner: 'John' 'Type', 'V6',... Engine: [1x1 struct] 'Horsepower', 300)); % Access and display % Access and display individual attributes fprintf('Car Type: %s\n', car.Frame.Type); Car Type: Sedan fprintf('Car Color: %s\n', car.Frame.Color); % Add a new slot to the frame Car Color: Red car.Frame.Year = 2020; % Add Year attribute fprintf('Car Owner: %s\n', car.Frame.Owner); fprintf('Car Year: %d\n', car.Frame.Year); Car Owner: John Car Year: 2020 fprintf('Engine Type: %s\n', car.Frame.Engine.Type); % Nested Frame for owner details Engine Type: V6 car.Frame.OwnerDetails = struct(... fprintf('Engine Horsepower: %d\n', 'Name', 'John',... car.Frame.Engine.Horsepower); 'Age', 30,... Engine Horsepower: 300 'License', 'ABC1234'); % Modify an attribute car.Frame.Color = 'Blue'; % Change the color to Blue fprintf('Updated Car Color: %s\n', car.Frame.Color); Updated Car Color: Blue % Access nested frame attributes fprintf('Owner Name: %s\n', car.Frame.OwnerDetails.Name); Owner Name: John fprintf('Owner Age: %d\n', car.Frame.OwnerDetails.Age); Owner Age: 30 fprintf('Owner License: %s\n', car.Frame.OwnerDetails.License); Owner License: ABC1234 3.4. Ontologies Scenario Let's create a simple ontology for a transportation domain. We'll represent the following concepts and relationships: Classes: ○ Vehicle Car Sedan SUV Bicycle ○ Person Driver Passenger Properties: ○ hasType: Represents the type of vehicle. ○ hasOwner: Indicates the owner of the vehicle. ○ canDrive: Indicates who can drive a vehicle. 3.4. Ontologies 1. Define Classes and Relationships 2. Instantiate Objects Defining the Ontology Defining Classes and Instances Displaying the Ontology Accessing Instances Ontology % Clear workspace clc;clear; % Define the ontology structure ontology = struct(); % Define classes ontology.Vehicle = struct(... 'hasType', {'Car', 'Bicycle'},... % Types of vehicles 'instances', struct(... 'Car', struct(... 'hasOwner', 'John',... 'canDrive', {'John', 'Alice'}),... 'Bicycle', struct(... 'hasOwner', 'Bob',... 'canDrive', {'Bob'}))); ontology.Car = struct(... 'hasType', {'Sedan', 'SUV'},... 'instances', struct(... 'Sedan', struct('hasOwner', 'Alice', 'canDrive', {'Alice'}),... 'SUV', struct('hasOwner', 'John', 'canDrive', {'John', 'Alice'}))); ontology.Person = struct(... 'hasRole', {'Driver', 'Passenger'},... 'instances', struct(... 'Driver', struct('canDrive', {'John', 'Alice'}),... 'Passenger', struct('canDrive', {'Bob', 'Alice'}))); % Accessing an instance of a Car fprintf('\nCar Instance:\n'); Car Instance: carInstance = ontology.Vehicle(2).instances(1).Car; fprintf('Owner: %s\n', carInstance(1).hasOwner); Owner: John fprintf('Can Drive: '); Can Drive: for i=1:1:length(carInstance(2)) fprintf('%s; ',carInstance.canDrive); end John; Alice; % Accessing an instance of a Sedan fprintf('\nSedan Instance:\n'); Sedan Instance: sedanInstance = ontology.Car(2).instances(1).Sedan; fprintf('Owner: %s\n', sedanInstance(1).hasOwner); Owner: Alice fprintf('Can Drive: '); Can Drive: for i=1:1:length(sedanInstance) fprintf('%s; ',sedanInstance.canDrive); end Alice; % Accessing an instance of a Person (Driver) fprintf('\nDriver Instance:\n'); Driver Instance: driverInstance = ontology.Person(2).instances(1).Driver; fprintf('Can Drive: '); Can Drive: for i=1:1:length(driverInstance(2)) fprintf('%s; ',driverInstance.canDrive); end John; Alice; 3.5. Rule base Systems Rule-Based System for a Simple Medical Diagnosis: In this example, we’ll create a rule-based system to help diagnose whether a patient might have the flu based on their symptoms. Rules We will define the following rules for our medical diagnosis system: 1. If the patient has a fever and a cough, then they may have the flu. 2. If the patient has a sore throat and a cough, then they may have a cold. 3. If the patient has a headache and a fever, then they may have the flu. 3.5. Rule base Systems Defining Symptoms Defining Rules Applying the Rules Displaying Results Rule based System % Clear workspace Clc; clear; % Define patient symptoms patientSymptoms = struct( 'fever', true,... % Patient has a fever 'cough', true,... % Patient has a cough 'soreThroat', true,... % Patient does not have a sore throat 'headache', false... % Patient does not have a headache ); % Define the rules rules = { 'If fever and cough, then may have flu'; 'If sore throat and cough, then may have cold'; 'If headache and fever, then may have flu' }; % Initialize diagnosis diagnosis = {}; % Check each rule for i = 1:length(rules) rule = rules{i}; % Apply the rules based on the symptoms if contains(rule, 'fever') && contains(rule, 'cough') if patientSymptoms.fever && patientSymptoms.cough diagnosis{end + 1} = 'Diagnosis: May have the flu.'; end elseif contains(rule, 'sore throat') && contains(rule, 'cough') if patientSymptoms.soreThroat && patientSymptoms.cough diagnosis{end + 1} = 'Diagnosis: May have a cold.'; end elseif contains(rule, 'headache') && contains(rule, 'fever') if patientSymptoms.headache && patientSymptoms.fever diagnosis{end + 1} = 'Diagnosis: May have the flu.'; end; end; end; % Display the diagnosis results if isempty(diagnosis) fprintf('No diagnosis could be made based on the symptoms.\n'); else fprintf('%s\n', strjoin(diagnosis, '\n')); end Diagnosis: May have the flu. Diagnosis: May have a cold. 4. Reasoning with Knowledge Types of Reasoning: ○ Deductive Reasoning ○ Inductive Reasoning. ○ Abductive Reasoning 4.1. Deductive Reasoning Deriving specific conclusions from general principles. Deductive reasoning starts with general premises and leads to specific conclusions. It is the classical "if-then" logical reasoning where conclusions must follow from the premises. Deductive Reasoning % Define a list of birds birds = {'sparrow', 'eagle', 'penguin', 'ostrich'}; % Define a rule: "All birds except penguins and ostriches can fly" canFlyRule = @(bird) ~strcmp(bird, 'penguin') && ~strcmp(bird, 'ostrich'); % Deductive reasoning example birdName = 'sparrow'; % The bird we are reasoning about fprintf('Deductive Reasoning:\n'); Deductive Reasoning: if canFlyRule(birdName) fprintf('According to the rule, %s can fly.\n', birdName); else fprintf('According to the rule, %s cannot fly.\n', birdName); end According to the rule, sparrow can fly. 4.2. Inductive Reasoning Generalizing from specific examples. Inductive reasoning involves drawing general conclusions from specific observations. Unlike deductive reasoning, the conclusions of inductive reasoning are probabilistic rather than certain. Inductive Reasoning % Specific observations (color of swans) observations = {'white', 'white', 'white', 'white', 'white'}; % All observed swans are white % Inductive reasoning: Generalize from observations uniqueColors = unique(observations); fprintf('Inductive Reasoning:\n'); Inductive Reasoning: if length(uniqueColors) == 1 && strcmp(uniqueColors{1}, 'white') fprintf('All observed swans are white. Inductive conclusion: All swans are white.\n'); else fprintf('Not all observed swans are the same color. Cannot make a general conclusion.\n'); end All observed swans are white. Inductive conclusion: All swans are white. 4.3. Abductive Reasoning Inferring the best explanation for observations. Abductive reasoning works by finding the most likely explanation for a given set of observations. It starts with an observation and seeks the simplest or most probable cause. Abductive Reasoning % Possible causes for wet grass causes = {'rain', 'sprinkler', 'dew', 'flood'}; % Define probability of each cause (likelihood that it explains the observation) probabilities = [0.7, 0.2, 0.05, 0.05]; % Rain is the most likely cause % Observation: The grass is wet fprintf('Abductive Reasoning:\n'); Abductive Reasoning: [maxProb, idx] = max(probabilities); mostLikelyCause = causes{idx}; fprintf('The grass is wet. The most likely cause is: %s (with probability %.2f)\n', mostLikelyCause, maxProb); The grass is wet. The most likely cause is: rain (with probability 0.70) 5. Applications of Knowledge Representation Natural Language Processing (NLP) Expert Systems Robotics Recommendation Systems 6. Conclusions Connection Between Knowledge Representation and AI Components ○ Expert Systems ○ Search Algorithms ○ Machine Learning Challenges in Knowledge Representation ○ Complexity and Scalability ○ Ambiguity and Vagueness ○ Updating Knowledge ○ Expressiveness vs. Efficiency