Represent information about the world for a computer to use to solve problems, I.e. diagnosing medical conditions.
Incorporates logic to enable reasoning by the computer
Main approaches to knowledge representations:
1. Logic Programming (First Order Logic aka FOL)
2. Semantic Networks
3. Frames (a type of semantic network)
4. Rule-based systems
Procedural knowledge representation
Knowledge is stored as program code
Usable only in a specialized problem-solving context
Highly efficient (in the correct context)
Used to execute functions that do things
Examples:
Plan a route from Stanford → SFO
Find all family members of Tiffany
declarative knowledge representation
Knowledge stored as propositions that must be interpreted
Accessible for a variety of purposes
Relatively inefficient for problem-solving
Used to declare a certain logical statement is true or not
Or use to declare that two objects have a certain relationship
Examples:SFO is 30 miles from Stanford → distance(Stanford, SFO) = 30
Tiffany and Ben are siblings → siblings(Tiffany, Ben)
Knowledge representations: expressivity
you can say what you want to say
Knowledge representations: soundness
you will get all the right answers
Knowledge representations: completeness
you will get all the answers
Knowledge representations: decidability
you will get an answer
Knowledge representations:
The trade-off between expressivity and decidability
Fundamental tradeoff between being able to say what you would like to say about the world being modeled (expressivity) and knowing that inference is decidable and computationally efficient (tractability)
The trade-off between expressivity and decidability: tables in a database
The trade-off between expressivity and decidability: sentences in first-order logic
Very expressive
Logical inference may be computationally intractable
Start with set of axioms and formulas that are true
Use modus ponens to make conclusions about other formula
Many formulas and variables can be expressive, but may be intractable to solve for all of the variables
Might be no solution, in which case the query is “undecidable”
Order from least expressive to most expressive:
a) frames
b) description logic
c) first order logic
1) Frames
2) Description logic
3) first order logic
True/False: Rule-based systems are a knowledge representation
True
True/False: Rule-based systems are a problem solving method
False
Rules in a rule-based system are of the form...
if ... then ...
What knowledge representation do we use backward/forward chaining on?
rule-based systems
What is backward chaining?
Goal-driven reasoning
Start with our final goal (e.g. Fritz is green)
Find rules with our goal as the consequent (then clause), use the antecedent (if clause) as our new goal
Repeat until we can prove the antecedent with our given truths
Name a biomedical system that uses backward chaining.
MYCIN
Goal: find significant disease-causing organismsUses rules to available data
Once it finds such organisms, it attempts to select a therapy to treat the disease(s)
Designed as a consultant for physicians - given the ability to explain both its reasoning and its knowledge
What is forward chaining?
Data-driven reasoning
Repeated application of modus ponens
Modus ponens
If conditional statement if p then q is accepted, and p holds, then the consequence q may be inferred
Search rules until we find one where the antecedent is true
Name three problems with rule-based reasoning.
Rules offer much more flexibility in problem solving, but they do not encode inspectable models as frames do
Rules are hard for developers to maintain
No means to introspect the knowledge within the systems (rules)
Rule engine cannot scan through rules to adjust them, add rules, or delete rules
Name three standard rule-based systems.
Arden Syntax
Health e-Decisions
MYCIN
What is Arden syntax? What kind of system is it?
Markup language used for representing and sharing medical knowledge
Rule-based system
The rules in Arden syntax are often forward or backward chaining?
Rules are often “data-driven” (aka forward-chaining)
Thus, when a physician enters new info about a patient, the system searches for rules that are relevant.
Four functions for Arden syntax:
Alert: messages for dangerous situations
Medication interaction or dangerous lab result
Interpretation: a non-emergency messaged designed to supply supportive information such as an interpretation of liver function tests
Screen: message sent to clinical researchers when a patient meeting criteria for clinical trial or quality assurance concern are admitted to hospital
Management: messages used for administrative purposes such as managing bed assignments, same day admissions and discharges from hospital
Name two use cases for Health e-Decisions
1. Clinical decision support artifact sharing
2. Clinical decision support guidance service
What is Health e-Decisions:
Clinical decision support for artifact sharing?
Answered the question: “How can I share a really good clinician decision support rule with someone else in an electronic format, so they can use the rule in their electronic health record?”
Focused on sharing three types of artifacts
Event-condition-action rules
Order sets
Document templates
What is Health e-Decisions:
Clinical decisions support guidance service?
Answered the question: “How can I send important data to an up-to-date website or service that will give me advice about immunizations or other complex decisions?”
Name a big criticism of rule-based systems in a clinical setting.
One big criticism of rule-based systems is that they fail to capture the complexities of a patient’s situation, which might include many (potentially conflicting) symptoms and other information that needs to be consolidated into a differential diagnosis. Some more advanced systems that used rules but accounted for more complexity include:
MYCIN: Accounted for lots of info about a patient via “Evidence Combination” and gave a differential of infectious diseases
What does a frame-based system represent?
Representation of classes, attributes, and values
A frame-based system consists of templates to record values of properties of ______
concepts
Frame-based systems are a hierarchy of ___ and ___
nodes and relations
Frame-based systems share a lot with traditional...
object-oriented models
Semantics of frame-based systems are based on...
set theory
Five advantages of frame-based systems:
Offer cognitive tractability
Class hierarchy organizes a flat knowledge base by introducing structure
Simple, easy to understand
Inheritance is captured in a natural, modular fashion
Frames support efficient inference by following links
Five disadvantages of frame-based systems:
Negation cannot be represented uniformly
Disjunction cannot be represented naturally - Jim has either mumps or rubella
Quantification is not a part of the language - All of Jim’s diseases are infectious
No standard way to represent exceptions
Assumes a closed-world assumption - Everything that is true is known to be true, therefore everything that is not stated is false
Name two examples of a frame-based system in biomedicine.
Internist-1, and it's predecessor, Quick Medical Reference (QMR)
FMA (Formal Model of Anatomy)
What did the creators of Internist-1 and QMR record? In what form is this?
For each internal medicine disease, the creators recorded the evoking strength, frequency, and importance of many symptoms/physical exam findings.
This was in the form of Frames.
Internist-1 and QMR: Each _____ had a frame and the frame stored the findings for the evoking strength, frequency, and importance of many symptoms/physical exam findings.
disease
Internist-1 and QMR: when you entered in _________, the system created a differential by ranking diseases by rewarding diseases that contained the most common and most differentiating symptoms and penalizing diseases that didn’t have those
symptoms/findings for an actual patient
Internist-1 and QMR: input
user enters patient's findings
Internist-1 and QMR: output
differential diagnosis
Internist-1 and QMR: two uses
Disease complications: Can explain diseases that may result from complications of the primary disease
Helps to “rule in” diagnosis: Suggests additional findings that would support diagnosis, Assists in ordering additional tests
How to integrate frames and rules:
Rules act on information stored within frames
Left-hand side of rules refer to frames that may become instantiated at run time
Right-hand sides of rules conclude values that alter instantiations of frames or that instantiate new frames
Integrating frames and rules example:
Frame: Bob is an individual of the Frog concept
Rules: IF X is a frog, THEN X is green
What can we do now?
We can now use the rule to update our frame for Bob to have the role (data property) that he is green
First-order logic is the ____ expressive option for representing knowledge, but computation can be intractable