PadhaikoAll subjects

Knowledge Representation and Probabilistic Reasoning

Artificial Intelligence (ENCT 351)

Open in the Padhaiko app

3.1 Knowledge-based agent

A knowledge-based agent (KBA) stores explicit representations of facts and rules about the world in a knowledge base (KB) and uses an inference engine to derive new conclusions and choose actions.

Definition

Knowledge Base and Inference Operations

Generic Knowledge-Based Agent loopText
function KB-AGENT(percept):
    persistent: KB (knowledge base), t (time counter, initially 0)
    TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
    action = ASK(KB, MAKE-ACTION-QUERY(t))
    TELL(KB, MAKE-ACTION-SENTENCE(action, t))
    t = t + 1
    return action

Knowledge Level vs. Implementation Level

3.2 Knowledge representation techniques and issues in representation

Properties of a Good Knowledge Representation System

  1. Representational adequacy: Ability to represent all kinds of knowledge needed in the domain.
  2. Inferential adequacy: Ability to manipulate existing structures to derive new knowledge.
  3. Inferential efficiency: Ability to direct reasoning toward promising paths rather than blind search.
  4. Acquisitional efficiency: Ease of acquiring new knowledge (from experts or data) without breaking existing knowledge.

Four Main Knowledge Representation Techniques

Major Knowledge Representation Schemes
TechniqueCore MechanismStrengthsWeaknesses
Logical representationPropositional and predicate (FOL) formulasPrecise semantics, sound inferenceRigid for uncertainty and exceptions
Semantic networksGraph of concept nodes and labelled relation arcs (is-a, has-a)Natural inheritance, visualWeak semantics for quantifiers and negation
FramesObject-like records with slots and fillersStructured defaults, procedural attachmentMultiple inheritance conflicts
Production rulesIF condition THEN action/conclusion pairsModular, easy to explainConflict resolution needed as rule count grows

Issues in Knowledge Representation

Exams frequently ask the five classic representation issues:

  1. Important attributes: Which attributes of objects are basic (is-a, instance-of) and need special inference support?
  2. Relationships among attributes: Inverse relations (parent-of vs. child-of), existence of an attribute, single-valued vs. multi-valued properties, and inheritance.
  3. Choosing granularity: How detailed should primitives be? Too coarse loses facts (e.g., John spotted Sue vs. knowing who saw whom); too fine wastes storage and inference time.
  4. Representing sets of objects: Distinguishing a class from an instance (extensional listing vs. intensional predicate).
  5. Finding the right structures (frame problem / indexing): Accessing relevant facts quickly from a large KB, and representing what does not change when an action occurs (the frame problem).

3.3 Propositional and predicate logic

Propositional Logic (PL)

Propositional logic represents whole atomic facts as Boolean symbols () connected by logical operators: negation (), conjunction (), disjunction (), implication (), and biconditional ().

First-Order Predicate Logic (FOL)

First-order logic models the world as objects, relations (predicates), and functions, adding quantifiers:

AspectPropositional LogicFirst-Order (Predicate) Logic
Ontological commitmentWorld consists of atomic facts (True/False)World consists of objects, properties, relations, functions
Variables & quantifiersNoneVariables with and
Expressive powerLow; cannot generalize over objectsHigh; concise general rules
DecidabilityDecidable (truth tables / SAT, NP-complete)Semi-decidable (valid sentences provable; invalid may not halt)

Converting FOL Sentences to CNF (for Resolution)

To prove a query by resolution refutation, assert in Conjunctive Normal Form (CNF) and derive the empty clause :

  1. Eliminate implications () and biconditionals.
  2. Move inwards using De Morgan's laws and quantifier flips ().
  3. Standardize variables apart so each quantifier has a unique variable name.
  4. Skolemize: replace each existential variable with a Skolem constant (if not under ) or a Skolem function of enclosing universal variables.
  5. Drop quantifiers and distribute over to obtain a conjunction of clauses.

3.4 Semantic networks, frames and knowledge graph

Semantic Networks

A semantic network is a directed labelled graph where nodes represent concepts, objects, or values, and edges (arcs) represent binary relations—especially is-a (subclass/instance hierarchy) and has-a (property/part). Properties attached to a parent class are automatically inherited by subclasses and instances unless overridden (exception handling).

Frames

Introduced by Marvin Minsky (1975), a frame is a structured record (analogous to an object/class in OOP) describing a stereotyped object or situation:

Frame representation example: Student and EngineeringStudentText
Frame: Student
  is-a:      Person
  enrolled:  True (default)
  gpa:       real in [0.0, 4.0]

Frame: EngineeringStudent
  is-a:      Student
  faculty:   Institute of Engineering
  courses:   {ENCT351, ENCT352, ...}
  if-needed(standing): if gpa >= 3.5 then "Distinction" else "Regular"

Knowledge Graphs

A knowledge graph (KG) scales semantic networks to web-sized structured data using (Subject, Predicate, Object) triples (as in RDF / SPARQL / Google Knowledge Graph / Wikidata).

3.5 Review of Bayes' Theorem and probabilistic reasoning

Logical agents struggle with uncertainty caused by partial observability, noisy sensors, or non-deterministic actions (e.g., diagnosing a disease from symptoms). Probabilistic reasoning models belief as degrees in using probability axioms.

Theorem

Bayes' Theorem

From the product rule , for :

where:

Bayesian Belief Networks (BBNs)

A full joint probability distribution over binary variables requires entries. A Bayesian Network exploits conditional independence via a Directed Acyclic Graph (DAG):

3.6 Fuzzy logic: Membership functions, fuzzy inference systems

Classical (crisp) set theory allows only membership or . Fuzzy logic (Lotfi Zadeh, 1965) handles vagueness (concepts like tall, warm, fast) by allowing partial truth degrees in .

Definition

Fuzzy Set and Membership Function

A fuzzy set on universe of discourse is defined by a membership function assigning each element a degree of membership :

Standard fuzzy set operations:

Common Membership Function Shapes

Fuzzy Inference System (FIS) Pipeline (Mamdani Method)

  1. Fuzzification: Convert crisp numerical inputs into fuzzy membership degrees using input membership functions.
  2. Rule evaluation (Inference): Apply IF-THEN fuzzy rules (using for AND, for OR) to compute the firing strength of each rule and clip/scale its output fuzzy set.
  3. Aggregation: Combine all clipped output fuzzy sets into one fuzzy output distribution using .
  4. Defuzzification: Convert the aggregated fuzzy set back into a single crisp output—most commonly by Centroid (Center of Gravity):
AspectProbability TheoryFuzzy Logic
ModelsRandomness / uncertainty of whether an event occursVagueness / imprecision of degree to which a property holds
Example (30% chance of rain) (moderately heavy)
Sum constraintProbabilities of exclusive outcomes sum to Membership values across overlapping fuzzy sets need not sum to

Worked Out Examples

Example 3.1

3.1 (6 marks)

A rare disease affects of the population (). A diagnostic test has sensitivity (true positive rate) and false-positive rate . If a randomly chosen person tests positive, what is the probability they actually have the disease?

List given probabilities:

  • Prior: , so .
  • Likelihoods: and .

Compute marginal probability of a positive test :

Apply Bayes' Theorem:

Answer:

().

Example 3.2

3.2 (6 marks)

In the classic Alarm Bayesian network, Burglary () and Earthquake () are independent parents of Alarm (), and Alarm () is the sole parent of JohnCalls () and MaryCalls (). Given , , , , and , calculate the joint probability .

Write the Bayesian network factorization: Each node depends only on its direct parents:

Substitute the CPT entries and multiply:

Answer:

().

Example 3.3

3.3 (6 marks)

A fuzzy set Warm has a triangular membership function . (a) Find . (b) Suppose an aggregated output fuzzy set has discrete membership values . Compute the crisp output using centroid defuzzification.

Membership of in : Since (the rising slope from to ):

Discrete centroid defuzzification:

Answer:

, and the defuzzified crisp output is .

Exercises

Exercise: Knowledge Representation and Probabilistic Reasoning

Question 1

Explain the architecture of a knowledge-based agent using TELL and ASK, and list four key issues in knowledge representation.

KBA architecture: A knowledge-based agent maintains a Knowledge Base (KB) of domain sentences and an inference engine. On each step it TELLs the KB what it perceived, ASKs the KB what action is best, and TELLs the KB which action it executed.

Four KR issues: (1) Representing important attributes (is-a, instance-of); (2) relationships among attributes (inverses, single/multi-valued); (3) choosing granularity (level of detail of primitives); and (4) representing sets and handling defaults/frame problem.

Answer:

A KBA combines a KB and an inference engine via TELL/ASK operations. Core KR issues include important attributes, attribute relationships, granularity, set representation, and the frame problem.

Question 2

Represent the following English statements in First-Order Logic (FOL): (a) "Every student who studies hard passes AI." (b) "Some person likes all Nepalese food." (c) "No dog is a cat."

(a) .

(b) .

(c) (equivalently ).

Answer:

(a) ; (b) ; (c) .

Question 3

Compare semantic networks, frames, and knowledge graphs with a short example of each.

Semantic networks use labelled directed graphs (Dog --is-a--> Mammal --has--> Fur) for simple inheritance.

Frames organize concepts as structured slot-filler records with defaults and procedural if-needed attachments (e.g., Frame: Bird with can-fly: True (default)).

Knowledge graphs store billions of (subject, predicate, object) triples with formal ontologies and unique identifiers (e.g., (Everest, located_in, Nepal)), enabling large-scale querying and embeddings.

Answer:

Semantic networks are inheritance graphs, frames add structured slots/defaults/procedures, and knowledge graphs scale triple-based representation with standardized ontologies for large-scale reasoning.

Question 4

Suppose of incoming emails are spam (). The word "lottery" appears in of spam emails () and in of non-spam emails (). Find the probability that an email containing "lottery" is spam.

Total probability of "lottery":

Posterior by Bayes' Theorem:

Answer:

().

Question 5

Let fuzzy sets and have and at point . Compute , , and . Also compute the discrete centroid of an output fuzzy set with points .

Fuzzy operations at :

  • .
  • .
  • .

Centroid defuzzification:

Answer:

, , ; centroid .

← Problem Solving and Search (part 2: 2.5–2.8)Machine Learning Fundamentals (part 1: 4.1–4.4) →