Knowledge Representation and Probabilistic Reasoning
Open in the Padhaiko app3.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.
Knowledge Base and Inference Operations
- Knowledge Base (KB): A set of sentences expressed in a formal knowledge representation language representing assertions about the world.
- Inference Engine: Domain-independent algorithms that derive new sentences from existing ones in the KB.
- TELL / ASK interface: Every interaction uses two operations:
- TELL(KB, sentence): Adds new percepts or action records to the KB.
- ASK(KB, query): Queries the KB to decide what action to take based on what follows from the KB.
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 actionKnowledge Level vs. Implementation Level
- Knowledge level: Describes what the agent knows and what its goals are, independent of how it is coded.
- Logical (symbol) level: How sentences are encoded in logic/frames/networks.
- Implementation level: Data structures (lists, hash tables, graphs) inside the program.
- Declarative vs. procedural approach: Declarative representation stores facts (
TELLwhat is true, let inference figure out how); procedural representation hard-codes behaviour in code.
3.2 Knowledge representation techniques and issues in representation
Properties of a Good Knowledge Representation System
- Representational adequacy: Ability to represent all kinds of knowledge needed in the domain.
- Inferential adequacy: Ability to manipulate existing structures to derive new knowledge.
- Inferential efficiency: Ability to direct reasoning toward promising paths rather than blind search.
- Acquisitional efficiency: Ease of acquiring new knowledge (from experts or data) without breaking existing knowledge.
Four Main Knowledge Representation Techniques
| Technique | Core Mechanism | Strengths | Weaknesses |
|---|---|---|---|
| Logical representation | Propositional and predicate (FOL) formulas | Precise semantics, sound inference | Rigid for uncertainty and exceptions |
| Semantic networks | Graph of concept nodes and labelled relation arcs (is-a, has-a) | Natural inheritance, visual | Weak semantics for quantifiers and negation |
| Frames | Object-like records with slots and fillers | Structured defaults, procedural attachment | Multiple inheritance conflicts |
| Production rules | IF condition THEN action/conclusion pairs | Modular, easy to explain | Conflict resolution needed as rule count grows |
Issues in Knowledge Representation
Exams frequently ask the five classic representation issues:
- Important attributes: Which attributes of objects are basic (
is-a,instance-of) and need special inference support? - Relationships among attributes: Inverse relations (
parent-ofvs.child-of), existence of an attribute, single-valued vs. multi-valued properties, and inheritance. - Choosing granularity: How detailed should primitives be? Too coarse loses facts (e.g.,
John spotted Suevs. knowing who saw whom); too fine wastes storage and inference time. - Representing sets of objects: Distinguishing a class from an instance (extensional listing vs. intensional predicate).
- 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 ().
- Syntax & semantics: A model assigns True/False to every symbol. Sentence entails () iff in every model where is true, is also true.
- Validity / Tautology: True in all models (e.g., ).
- Satisfiability: True in at least one model.
- Inference rules: Modus Ponens (), And-Elimination, Resolution ().
- Limitation of PL: Cannot express properties of individual objects or general rules like "All humans are mortal" without writing separate propositions for every person.
First-Order Predicate Logic (FOL)
First-order logic models the world as objects, relations (predicates), and functions, adding quantifiers:
- Universal quantifier (): means holds for every object in the domain. Usually paired with :
- Existential quantifier (): means holds for at least one object . Usually paired with :
| Aspect | Propositional Logic | First-Order (Predicate) Logic |
|---|---|---|
| Ontological commitment | World consists of atomic facts (True/False) | World consists of objects, properties, relations, functions |
| Variables & quantifiers | None | Variables with and |
| Expressive power | Low; cannot generalize over objects | High; concise general rules |
| Decidability | Decidable (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 :
- Eliminate implications () and biconditionals.
- Move inwards using De Morgan's laws and quantifier flips ().
- Standardize variables apart so each quantifier has a unique variable name.
- Skolemize: replace each existential variable with a Skolem constant (if not under ) or a Skolem function of enclosing universal variables.
- 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:
- Slots: named attributes of the entity (e.g.,
wheels,fuel,is-a). - Fillers: values of those slots, which can be literals, default values, range constraints, pointers to other frames, or procedural attachments (
if-needed,if-added,if-removeddemons).
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).
- Example triple:
(Kathmandu, capital_of, Nepal),(ENCT351, part_of, BCT_Sem6). - Advantages over plain semantic nets: standardized URIs/ontologies (RDF/OWL), support for graph queries and link prediction via knowledge graph embeddings, and massive multi-source integration.
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.
Bayes' Theorem
From the product rule , for :
where:
- is the prior probability of hypothesis .
- is the likelihood of evidence given .
- is the posterior probability of after observing .
- is the marginal likelihood (normalizing constant) over mutually exclusive exhaustive hypotheses .
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):
- Each node is a random variable with a Conditional Probability Table (CPT) specifying .
- Chain rule for Bayesian networks:
- If each node has at most parents, storage drops from to .
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 .
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 :
- : full membership; : no membership; : partial membership.
Standard fuzzy set operations:
- Union (OR):
- Intersection (AND):
- Complement (NOT):
Common Membership Function Shapes
- Triangular : rises linearly from at to at , then falls linearly to at .
- Trapezoidal : flat peak on , linear ramps on and .
- Gaussian: .
Fuzzy Inference System (FIS) Pipeline (Mamdani Method)
- Fuzzification: Convert crisp numerical inputs into fuzzy membership degrees using input membership functions.
- Rule evaluation (Inference): Apply
IF-THENfuzzy rules (using forAND, forOR) to compute the firing strength of each rule and clip/scale its output fuzzy set. - Aggregation: Combine all clipped output fuzzy sets into one fuzzy output distribution using .
- Defuzzification: Convert the aggregated fuzzy set back into a single crisp output—most commonly by Centroid (Center of Gravity):
| Aspect | Probability Theory | Fuzzy Logic |
|---|---|---|
| Models | Randomness / uncertainty of whether an event occurs | Vagueness / imprecision of degree to which a property holds |
| Example | (30% chance of rain) | (moderately heavy) |
| Sum constraint | Probabilities of exclusive outcomes sum to | Membership values across overlapping fuzzy sets need not sum to |
Worked Out Examples
3.1
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:
().
3.2
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:
().
3.3
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:
, and the defuzzified crisp output is .
Exercises
Exercise: Knowledge Representation and Probabilistic Reasoning
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.
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.
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 ).
(a) ; (b) ; (c) .
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.
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.
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:
().
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:
, , ; centroid .