2. Knowledge Representation

• Early AI systems designed to perform tasks requiring human expertise

• Modular architecture: knowledge separated from reasoning

• Emphasis on precision, consistency, and explainability

• Foundation for many modern AI systems

• Goal: replicate high-level human expertise

• Two strictly separated modules:

  • Knowledge base (what the system knows)

  • Inference engine (how the system reasons)

• Easier knowledge updates

• Reusable reasoning mechanisms

• Greater flexibility and scalability

• 
  

  • Knowledge base

  • Inference engine

  • User interface

• Extracts and formalizes expert knowledge

• Acts as a bridge between domain experts and the system

• Central repository of system knowledge

• Encodes:

  • Facts (declarative knowledge: observed truths)

  • Rules (procedural knowledge: IF–THEN logic)

• Example (medical domain):

  • Facts: fever, rash, age

  • Rules: IF rash → possible measles

• Supports rule chaining to build conclusions incrementally

• Applies logical reasoning to draw conclusions

• Matches facts to rules using pattern matching

• Uses symbolic representations

• Design impacts reasoning quality and computational efficiency

• forward chaining

• backward chaining

• hybrid reasoning

• Issue: multiple rules may apply simultaneously

• Resolution strategies:

  • Salience (rule priority)

  • Specificity (more precise rules first)

  • Recency (recently derived facts)

• Rete algorithm (Forgy):

  • Optimizes pattern matching

  • Reduces redundant computations

• Data-driven

• Starts with known facts → derives new facts

• Uses working memory (dynamic)

• Suitable when input data is mostly known

• Common in:

  • Medical diagnosis

  • Monitoring systems

  • Recommendation systems

• Goal-driven

• Starts with a hypothesis → searches for supporting evidence

• Works recursively with sub-goals

• Suitable when information is incomplete

• Common in:

  • Legal reasoning

  • Troubleshooting

  • Medical hypothesis testing

• Combines forward and backward chaining

• Selects strategy based on problem characteristics

• Communication bridge between user and system

• Functions:

  • Accepts input

  • Asks clarifying questions

  • Displays conclusions and recommendations

• Key feature: explainability

  • Shows reasoning steps

  • Builds user trust

• Distinguishes expert systems from “black box” AI

• Process of converting human expertise into machine-readable form

• Major challenge: knowledge acquisition bottleneck (Feigenbaum)

• Reasons:

  • Expert knowledge is tacit and intuitive

  • Experts struggle to articulate reasoning

• Common techniques:

  • Unstructured and structured interviews

  • Protocol analysis (“think aloud”)

  • Observation of experts in practice

• Limitations:

  • Time-consuming

  • Cognitive biases

  • Rapidly evolving domains

Choice affects interpretability and reasoning power

• Rule-based representation

• frame-based representation

• semantic networks

• case-based reasoning

• IF–THEN production rules

• Simple, intuitive, easy to update

• Best for well-defined logic domains

• Knowledge represented as objects with attributes

• Supports inheritance and hierarchies

• Useful for complex entities

• Graph-based representation

• Nodes = concepts, edges = relationships

• Enables reasoning via relationship paths

• Knowledge stored as past cases

• Solves new problems by analogy

• Effective in legal reasoning and customer support

• Structured lifecycle for building expert systems

1. Knowledge identification – define scope and domain

2. Conceptualization – identify key concepts and relationships

3. Formalization – encode knowledge into formal models

4. Implementation – integrate knowledge into system architecture

5. Validation & maintenance – ensure accuracy and updates

• Verification: internal consistency of rules

• Validation: alignment with real-world outcomes

• Real-world knowledge is incomplete or probabilistic

• Classical logic alone is insufficient

• Confidence values between -1 and 1

• Combine rule confidence and fact confidence

• Simple but not fully probabilistic

• Probabilistic dependencies between variables

• Update beliefs using Bayes’ theorem

• Mathematically sound but computationally complex

• Degrees of truth between 0 and 1

• Handles vague concepts (e.g., “high temperature”)

• Interpretable but less precise probabilistically

• DENDRAL

• MYCIN

• Developed at Stanford (1960s)

• First expert system

• Domain: chemical structure identification

• Key contributions:

  • Separation of knowledge and inference

  • Symbolic, rule-based reasoning

• Demonstrated AI could capture deep expert knowledge

• Developed at Stanford (1970s)

• Domain: medical diagnosis (bacterial infections)

• Features:

  • ~600 rules

  • Backward chaining

  • Certainty factors

  • High explainability

• Achieved expert-level performance

• Not widely deployed due to legal liability concerns

• Enables AI systems to store, structure, and exploit knowledge

• Provides a precise mathematical framework for reasoning

• Supports:

  • Representation of facts and relationships

  • Derivation of new knowledge from existing information

• Foundation for interpretable and explainable AI

• Core logic types:

  • Propositional logic

  • Predicate (first-order) logic

• Prolog: practical implementation of logic-based AI

• Simplest form of formal logic

• Deals with binary propositions (true or false)

• Propositions are atomic (no internal structure)

• Uses logical operators to form compound statements

• Limitations:

  • No variables

  • No quantifiers

  • No representation of relationships

• Cannot generalize across entities

  • Example limitation: cannot express “all humans are mortal”

• Extends propositional logic with richer expressiveness

• Introduces:

  • Variables (x, y)

  • Predicates (properties or relations)

  • Quantifiers (∀, ∃)

  • Functions

• Enables:

  • Generalization across individuals

  • Representation of relationships between entities

• Example:

  • Human(Socrates), Human(Plato)

  • Teacher(Socrates, Plato)

• Crucial for early AI expert systems

• Rules for forming valid expressions

• Defines:

  • Allowed symbols

  • How symbols can be combined

• Well-formed formulas (WFFs)

• Predicate logic syntax includes:

  • Terms (constants, variables, functions)

  • Predicates applied to terms

• Meaning of logical expressions

• Requires:

  • A domain of discourse

  • An interpretation function

• Maps:

  • Constants → objects

  • Predicates → relations

  • Functions → mappings

• Determines whether expressions are true or false

• Negation (¬): reverses truth value

• Conjunction (∧): both statements must be true

• Disjunction (∨): at least one statement true

• Implication (→): “if P then Q”

  • False only when P is true and Q is false

• Biconditional (↔): equivalence

  • Both statements have same truth value

• Universal quantifier (∀):

  • Statement holds for all objects

  • Example: ∀x Human(x) → Mortal(x)

• Existential quantifier (∃):

  • Statement holds for at least one object

  • Example: ∃x Animal(x) ∧ Mammal(x)

• Combines:

  • Predicates

  • Operators

  • Quantifiers

  • Functions

• Enables complex universal and conditional rules

• Example (medical domain):

  • If a patient has a bacterial infection, an effective antibiotic must exist

• Satisfiable: true under at least one interpretation

• Valid (tautology): true under all interpretations

• Contradiction: false under all interpretations

• Essential for automated reasoning systems

Modus Ponens

• Fundamental rule of deduction

• If:

  • P is true

  • P → Q is true

• Then:

  • Q is true

• Core reasoning pattern in expert systems (e.g., MYCIN)

Resolution

• Clause-based inference mechanism

• Used in automated theorem proving

• Works by refutation

• Combines clauses with complementary literals

• Derives contradictions (empty clause) to prove conclusions

• Common in logic programming

• Negate the goal

• Add it to the knowledge base

• Apply resolution repeatedly

• If contradiction occurs:

  • Negated goal is false

  • Original goal is true

• Powerful for automated proof systems

• Prolog = programmation en logique

• Declarative, high-level programming language

• Programmer specifies:

  • What is true

  • Not how to compute it

• System handles inference automatically

• Strongly aligned with predicate logic

• Programs consist of:

  • Facts

  • Rules

  • Relationships

• Queries infer logical consequences

• Separates:

  • Knowledge representation

  • Control and computation

• Suitable for expert systems and symbolic reasoning

• Facts

• Rules

• Queries

• Represent absolute truths

• Ground atomic formulas

• Example:

  • symptom(mark, fever).

• Stored in the knowledge base

• Define logical implications

• Structure:

  • Head :- Body

• Body conditions connected via logical AND

• Enable inference of new knowledge

• User questions to the system

• Start with ?-

• System attempts to prove them true

• Can return:

  • True/false

  • Variable bindings

• Core inference mechanism in Prolog

• Pattern-matching process

• Finds substitutions to make terms identical

• More powerful than simple variable assignment

• Enables:

  • Variable–constant matching

  • Variable–variable matching

  • Complex structure matching

• Search mechanism for exploring alternatives

• Depth-first search strategy

• If one reasoning path fails:

  • System returns to last decision point

  • Tries the next alternative

• Enables:

  • Multiple hypotheses testing

  • Complete exploration of solutions

• Combines:

  • Unification (matching)

  • Backtracking (search)

• Supports transparent and systematic reasoning

• Resembles human diagnostic reasoning

• Expert systems (e.g., medical diagnosis)

• Natural language processing:

  • Grammar representation

  • Sentence parsing

• Deductive databases

• Automated planning and scheduling

• Robotics, logistics, and manufacturing

• Strength: clear, explainable reasoning chains

• Poor handling of uncertainty

  • Binary true/false assumptions

• Scalability issues

  • Large knowledge bases increase search space

• Knowledge acquisition is difficult and time-consuming

• Closed-world assumption:

  • What cannot be proven is assumed false

• No learning from data

  • Cannot generalize statistically

• Weak integration with modern machine learning

• Real-world knowledge is interconnected, not linear

• Traditional rule-based systems struggle with complex relationships

• Knowledge graphs extend symbolic AI with flexible, structured representations

• Represent knowledge as a network of entities and relationships

• Enable:

  • Efficient querying

  • Systematic reasoning

  • Easy updates and extensions

• A network of nodes and labeled edges

• Nodes represent entities or concepts

• Edges represent semantic relationships

• Formally modeled as a directed, labeled graph

• Advantages over rule-based systems:

  • Natural modeling of interconnected concepts

  • No need to restructure knowledge when adding new facts

• Graph defined as: G = (V, E)

  • V = set of vertices (entities)

  • E = set of edges (relationships)

• Knowledge graphs are directed labeled graphs:

  • Direction encodes relationship semantics

  • Labels define meaning of nodes and edges

• Supports expressive, structured knowledge modeling

• Rule-based systems (e.g., MYCIN):

  • Knowledge encoded as IF–THEN rules

• Knowledge graphs:

  • Explicitly represent entities and their relationships

  • Model knowledge as a connected network

• More closely reflect human expert reasoning

• Enable richer contextual inference

• Entity: Escherichia coli

• Connected via relationships to:

  • Taxonomy: “is-a” → gram-negative bacterium

  • Ecology: “part-of” → intestinal flora

  • Diseases: “causes” → urinary tract infection

  • Treatments: “treated by” → ciprofloxacin, gentamicin

  • Resistance: “resistant to” → penicillin

• Knowledge stored as interconnected entities, not isolated rules

• Entities:

  • Real-world instances (e.g., diseases, symptoms, drugs)

• Classes (categories):

  • Group similar entities hierarchically

  • Enable generalization and inheritance

• Literals:

  • Data values (numbers, dates, text)

  • Example: temperature, treatment duration

• Modularity: new entities or links added without restructuring

• Query efficiency: answers found by traversing graph paths

• Explicit semantics: relationships preserve meaning (e.g., causes, treats)

• Support for contextual and symbolic reasoning

• Relationships are typed and semantically meaningful

Common Relationship Types

• is-a (taxonomic):

  • Hierarchical classification

  • Supports generalization

• part-of (compositional):

  • Indicates containment or structural inclusion

• has-property (attribute):

  • Links entities to characteristics

  • Useful for filtering and rule triggering

• related-to (general association):

  • Weak or unspecified semantic connection

• causes (causal):

  • Enables causal chains and diagnostic reasoning

• Semantic meaning attached to:

  • Nodes

  • Edges

• Enables:

  • Richer reasoning

  • Flexible expansion

  • Natural knowledge modeling

• Superior to purely rule-triggered logic

• Knowledge graphs without structure can become inconsistent

• Ontologies provide formal structure and constraints

• Define:

  • Classes

  • Relationships

  • Logical rules and restrictions

• Serve as a blueprint for knowledge organization

• Ensure:

  • Consistency

  • Semantic clarity

  • Logical coherence

• Start with defining classes and hierarchies

• Use “is-a” relationships to build taxonomies

• Example (medical):

  • Disease

    • Infectious disease

      • Bacterial infection

        • Urinary tract infection

• Enables inheritance-based inference

• Ontologies restrict how entities can be linked

• Prevent illogical connections

  • Example: only medications can “treat” diseases

• Enable automated reasoning via logical constraints

• Transitive properties:

  • A → B, B → C ⇒ A → C

• Symmetric properties:

  • A → B ⇒ B → A

• Inverse properties:

  • A treats B ⇔ B is treated by A

• Support indirect inference and consistency

• Express fundamental truths

• Common axioms:

  • Disjointness (e.g., symptom ≠ disease)

  • Cardinality restrictions

  • Domain-specific rules

• Improve reliability and reasoning power

• Shared vocabulary

• Easier integration of multiple data sources

• Automated inference of new facts

• Strong foundation for semantic reasoning

• Developed by W3C

• Enable standardized, machine-readable knowledge

• Core technologies:

  • RDF

  • OWL

  • SPARQL

• Allow knowledge sharing across systems and domains

• Foundational model for Semantic Web knowledge

• Represents knowledge as triples:

  • Subject

  • Predicate

  • Object

• Directly maps to nodes and edges in graphs

• Example:

  • Penicillin – treats – Streptococcal infection

• Uses URIs for global, unambiguous identification

• Prevents semantic ambiguity

• Supports multiple serialization formats:

  • RDF/XML

  • Turtle

  • JSON-LD

• Enables standardized data exchange across systems

• Extends RDF with richer semantics

• Used to build complex ontologies

• Supports:

  • Class combinations (union, intersection, complement)

  • Restrictions on properties

  • Cardinality constraints

  • Disjoint classes

  • Logical equivalence

• Balances expressiveness and reasoning efficiency

• Query language and protocol for RDF data

• Flexible and schema-independent

• Core components:

  • SELECT clause (variables to return)

  • WHERE clause (triple patterns)

• Queries graph patterns rather than tables

• Variables in subject, predicate, or object positions

• Advanced constructs:

  • FILTER

  • OPTIONAL

  • UNION

  • ORDER BY, LIMIT, OFFSET

  • DESCRIBE, CONSTRUCT

• Supports querying incomplete or inferred data

• OWL reasoners infer implicit knowledge

• SPARQL can retrieve inferred facts

• Transforms SPARQL into a semantic reasoning tool

• Enables complex, context-aware queries

• Introduced in 2012

• Shift from keyword matching to semantic understanding

• Represents entities and relationships as a graph

• Uses:

  • RDF-style triples

  • Ontologies

  • Inference mechanisms

• Enables structured answers and concept-based search

• Models users, content, and interactions

• Nodes: users, posts, events, pages

• Edges: friend-of, liked, commented-on

• Combines:

  • Symbolic graph structures

  • Statistical reasoning

• Enables recommendations and personalization at scale

• Extends social graphs to third-party websites

• Web pages become graph entities

• Enables semantic integration of external content

• User interactions become structured relationships