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
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
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
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:
b) description logic
c) first order logic
2) Description logic
3) first order logic
True/False: Rule-based systems are a knowledge representation
True/False: Rule-based systems are a problem solving method
Rules in a rule-based system are of the form...
if ... then ...
What knowledge representation do we use backward/forward chaining on?
What is backward chaining?
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.
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?
Repeated application of 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.
What is Arden syntax? What kind of system is it?
Markup language used for representing and sharing medical knowledge
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
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 ______
Frame-based systems are a hierarchy of ___ and ___
nodes and relations
Frame-based systems share a lot with traditional...
Semantics of frame-based systems are based on...
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.
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
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
first order logic
for all, there exists
FOL logical connectives
and, or, exclusive or, implies
Describe variables and relationships between variables
Six components of FOL
OWL is what kind of knowledge representation?
for most ontologies, people use ____ to build them
Web Ontology Language
Four advantages of description logic
Open-world assumption: Just because something hasn’t been said yet, doesn’t mean it is not true
Automatic classification of new concepts
Automatic identification of redundant concepts
Ease of customization when customers require specialized terms
precise notation for representing noun phrases
fundamental ontology of description logics
conceptual model is populated by:
related by binary relationships (roles and features)
grouped into classes (concepts)
Three uses of description logic:
1. subsumption: is category C1 a subset of C2?
2. classification: does object O belong to C?
3. satisfiability: can category C ever be instantiated?
Closed-world assumption, give an example
What is not known to be true must be false
Frame-based systems, rule-based systems, FOL
open-world assumption, give an example
Unstated things are unknown
Just because someone hasn’t said it yet, doesn’t mean it isn’t true
Description logic uses an open-world assumption
If we had an OWL (description logic) knowledge base that contained only a statement that said “all cats are animals”, what would we conclude about a new statement that says “all cats are soft”?
This new statement is not entailed from the current knowledgebase, but it is not contradicted by it either. Since we’re using OWL, which is based in DL, and the openworld assumption holds in DL, then we accept the new statement into the knowledgebase as true, but can’t conclude anything more about animals.
Many DLs are _________ of first-order logic (FOL).
description logic: classification
Classification takes a new Concept and automatically determines all subsumption relations between it and all other Concepts in the network
true/false - description logic: Adds new links when new subsumption relations are discovered
DL: automates the placement of new ______ in the taxonomy
DL: The classifier takes care of where to place a new concept in the ______
DL: All ________ are automatically propagated to the new concept
DL: Relationships among a new concept and other entities are automatically simplified by classifying the new concept as a ______ of existing concepts
DL restrictions: Each individual of a concept will have certain _____ (aka Data Properties and Object Properties). We can put restrictions on the type of data and objects linked together with these ____
DL cardinality restrictions
minCardinality, maxCardinality: Must have at least/most X values entered
DL is good for representing...
discrete, clear descriptions of facts/relationships
DL is not good for representing ...
things like multi-valued relations and probabilistic relations (or anything other than descriptions)
two examples of limitations of DL in biomedical applications
A patient may have some subset of symptoms but its not clear how many of the symptoms a patient needs before they reach a diagnosis. Some symptoms may be more important than others.
A patient’s symptoms give clues about the probability of disease more often than they definitively denote a disease.
Biomedical application that uses DL
semantics and the "meaning triangle"
There is an object/thing in the real world (e.g. Down Syndrome)
We have a mental concept for what that object is
We have a symbol to represent that object and how we conceive it so that we can communicate the thought of the object to other people and to computers
For example, it could be an instance of the class Developmental Disease and have certain symptom properties
anything used to represent any subject matter in order to help us to understand this subject matter
Provide a good start for building a model
Use to limit the scope of the model
Which wine characteristics should I consider when choosing a wine?
Is Bordeaux a red or white wine?
What is MIAME?
Minimum Information About a Microarray Experiment
Describes the minimum information required to ensure that microarray data can be easily interpreted and that results derived from its analysis can be independently verified.
The ultimate goal of this work is to establish a standard for recording and reporting microarray-based gene expression data, which will in turn facilitate the establishment of databases and public repositories and enable the development of data analysis tools.
The Problem-Oriented Medical Record
Elements of EHR
Dr. Larry Weed
Created new model based on patient problems
What does SOAP stand for?
S: subjective data
O: objective data
Every problem is numbered
Description of problem may change over time with new information
Number for each problem never gets recycled
Controlled terminologies: diseases
ICD-10, ICD-10-CM, DRG
controlled terminologies: Procedures
controlled terminologies: laboratory tests
controlled terminologies: nursing activities
NIC, NOC, HHCC, Omaha
controlled terminologies: drugs
Multum, Micromedex, NDFRT
controlled terminologies: biomedical literature
controlled terminologies: clinical documentation
controlled terminologies: cross-references among terminologies
What is SNOMED Clinical Terms (SNOMED CT)?
A systematically organized collection of medical terms providing codes, terms, synonyms and definitions used in clinical documentation and reporting.
SNOMED-CT uses ____ to relate terms
______ system contains codes for diseases, signs and symptoms, abnormal findings, complaints, social circumstances, and external causes of injury or diseases
ICD codes are used for (5 uses)
Disease surveillance and public health
Billing and reimbursement
Current Procedural Terminology (CPT)
Provides a code for every type of medical procedure
Relationships between codes are implicit
Example: Code 93571 codes for an intravascular doppler measurement during a coronary angiogram. Then Code 93572 is the code for each additional vessel that you measure after measuring the first one. The definition of Code 93572 does not make any explicit mention of Code 93571...it’s just implied.
Logical Observations, Identifiers, Names and Codes (LOINC)
provides a way to unify all of the other ontologies (diseases, procedures, lab tests, etc)
UML uses _____ semantics to define relative equivalence of concepts and relationships among concepts
UML provides a metathesaurus of more than 40 “source terminologies,” with more than 331,000 terms. Provides a ____ for each entry
Concept Unique Identifier (CUI)
Health Level-7 or HL7 refers to a set of international standards for transfer of clinical and administrative data between software applications used within a give hospital...lets a health system share data across its domains
Problems with HL7 V3 (4 problems)
The models and messages were too complex - Average HL7 V3 message had 5–10 times the number of XML nodes as messages in other industries
The RIM tried to model everything, with maximum extensibility and generality
The standard lacked a useful mechanism to add extensions
Documentation was poor
Fast Healthcare Interoperability Resources (FHIR) was based on
Version 3 RIM
FHIR Adopts ____ rule to simplify things.
make life simpler for implementers, rather than for modelers
FIHR used a ____ approach
Small contained model
Concepts related to a particular thing
e.g. medication prescription, adverse reaction
Discrete, but may reference one another, forming a graph
FHIR was made to be easily extended by developers at deployment sites. FHIR ____ determine terminologies, restrictions, etc
HL7 V2, RIM, and FHIR were designed to provide interoperability _____ institutions by modeling individual, clinically relevant concepts.
CDA helps you package up data from one health system so ...
it can be shared with another health system
Health Information Exchange (HIE) goals (3 things)
How to package up composite information for transfer *across* institutions?
Mobilization of patient data electronically across regions, communities, or health-care organizations
Enables exchange of information across disparate information systems
To enable more coordinated, timely, efficient care
To aid public health reporting and clinical research
CDA (Clinical Document Architecture) is a model for
a clinical document
CDA (Clinical Document Architecture) based on
CDA (Clinical Document Architecture) facilitates exchange of clinical documents ______ health care organizations.
within and between
CDA (Clinical Document Architecture) is a _______ for marking up narrative clinical reports—putting a wrapper around packages of clinical data
CDA (Clinical Document Architecture) allows document text to be marked up with terms from the...
RIM and from controlled terminologies
Continuity of Care Document (CCD) - A joint effort of ...
HL7 International and ASTM.
CCD fosters interoperability of clinical data by ...
allowing physicians to send electronic medical information to other providers without loss of meaning and enabling improvement of patient care.
Continuity of Care Document
CCD is an implementation guide for sharing Continuity of Care Record (CCR) patient summary data using the ...
HL7 Version 3 Clinical Document Architecture (CDA)
formal specification of a shared conceptualization
Conceptualization: the way we think about a domain
Specification: formal way of writing it down
Levels of ontological depth (5 levels)
fully axiomatized theory
vocabulary, possibly with natural-language definitions
terms with class-subclass relations
taxonomy plus related terms
unconstrained use of arbitrary relations
Basic Formal Ontology provides an ____ that you can use to combine several lower-level ontologies
Use cases for ontologies (3)
Share common understanding of the entities in a given domain - Among people, software agents, between people and software
Enable reuse of data and information - Introduce standards to allow interoperability and automatic reasoning - Create communities of researchers
Sketch out how you will model the classes for an ontology that will be used to classify and understand the variation in doctor’s notes amongst chronically ill and acutely ill patients.
What are the classes?
patients - chronically ill, acutely ill
care providers - doctors, nurses
notes - histories, updates
Sketch out how you will model the classes for an ontology that will be used to classify and understand the variation in doctor’s notes amongst chronically ill and acutely ill patients.
What are relationships between classes?
care providers write notes
doctors have patients
notes pertain to patients
Ontology that consists of very general terms (such as “object”, “property”, “relation”) that are common across all domains
upper-level ontologies function (3)
Support broad semantic interoperability among a large number of domain-specific ontologies
Provides a common starting point for the formulation of definitions
Domain ontology terms are ranked under terms of upper ontology - I.e. upper ontology classes are superclasses or supersets of all classes in domain ontologies
upper-level ontologies advantages (3)
Upper-level classes provide a useful organizing structure
Upper-level classes minimize the chance of category errors
Standard upper-level ontologies aid alignment and reuse across ontologies
Basic Formal Ontology (BFO)
Small, upper level ontology
Designed for supporting information retrieval, analysis and integration in scientific and other domains
Does not contain physical, chemical, biological or other terms that fall within domain ontologies
ontology engineering: clarity
definitions should be objective and complete
ontology engineering: coherence
Ontology should sanction those inferences consistent with the definitions
No concepts exist that are unsatisfiable (interpreted as a empty set)
Making definitions precise requires increasing ...
Anticipating various uses of the ontology may require increasing the number of ...
Making an ontology maximally general may make it useless for ...
any specific application
Domains of systems
The subject area of a system (e.g. infectious diseases)
Activities within a domain that a system performs (e.g. diagnosis)
Problem solving Methods (PSMs)
The procedures used to carry out the tasks (e.g. classification)
Process for task modeling (4 steps):
Characterize the overall task
Identify a method that solves that task, entailing any number of subtasks
For each subtask, identify a method that solves that subtask
Terminate when there is a well-described method for solving each subtask
Heuristic Classification PSM
Heuristic classification is suitable for classification problems in which it is known from experience which observations— or combinations of observations — indicate intermediate or final solutions, and with what degree of certainty.
Hierarchical task analysis
In order to accomplish a big, complex task, you need to break it down into sub-tasks that can be solved with the PSMs that you have.
1. Identify the task you want to accomplish
2. Create a PSM that can solve it
3. Identify the sub-tasks that must be solved to accomplish the PSM
4. Create the PSMs necessary to accomplish the sub-task...
The result is a structure that defines how problem solvers should be invoked
To rule in a diagnosis (specificity/sensitivity)?
To help conclude a diagnosis of which you are suspicious
Specific test when Positive, rules In
To rule out a diagnosis (specificity/sensitivity)?
To help to determine that an unlikely diagnosis is not present
Sensitive test when Negative Rules Out
Ad hoc methods: resulted from
Resulted from a mistrust of Bayesian statistics
Ad hoc methods: name two
(Certainty factors, fuzzy logic)
MYCIN “certainty factor” model
Adopts a measure of belief that ranged from -1.0 (complete falsehood) to +1.0 (complete truth)
Requires each rule to include a certainty factor for its conclusion
Requires the runtime system to update the CF for a proposition dynamically as each rule fires
Requires threshold for acceptance or rejection of a proposition
MYCIN “certainty factor” model problems
Does not overcome the conditional independence assumption - Highly related findings (e.g. fever, chills, and sweats) all individually increase posterior probability of disease (eg influenza)
Assessing “correct” CFs is difficult - There is no direct translation from statistical data to CFs
Developers assigning CFs have a tendency to conflate probabilistic values with other considerations - I.e. more important conclusions may be assigned higher CFs
Fuzzy set theory and fuzzy logic
Truth is not binary but a continuous value between 0 and 1
Reflecting the degree of membership in a fuzzy set
Goal is to infer degree of truth
Unlike probability theory, where goal is to determine likelihood of situations
Process of fuzzification
Converts numerical values into confident levels for membership in a fuzzy set
Assumptions often used when applying Bayes theorem (3)
Disease in the differential diagnosis are assumed to be mutually exclusive
Differential diagnosis is assumed to include the correct diagnosis (complete)
Observations supporting the diagnosis are assumed to be conditionally independent when seen in the setting of any of the diseases in the differential diagnosis
Belief Networks (Bayes Nets) provide a way to represent ______ between random variables. Nodes store probabilities _______ on only those nodes to which they are connected, reduces required computation!
To “solve” the Bayes belief network: (3)
Users enter the state of those nodes for which the state is known (e.g., person went to Honey-Baked Ham)
Algorithm calculates the posterior probability of all possible states of the remaining nodes (e.g., patient has swine flu)
If no state values are entered, then the initial probability of each value of each node is simply the prior probability
First-order logic vs Markov Logic
Markov Logic (the kind of logic used in Bayesian reasoning) is probabilistic. Therefore, you can have two opposing statements that each have some probability of being true
In a traditional FOL knowledgebase, every statement must be true (with probability one, so to speak), so having two opposing statements would make the knowledgebase incoherent.
Options for how to evaluate diagnostic systems (5)
Producing the correct diagnosis? -At the top of the list of candidates? - Somewhere within the list of candidates?
The “quality” of the differential diagnosis?User acceptance/satisfaction?
Amount of use of the system?
Appropriate management suggestions?
Questions about an artifact (7)
Is there a need for it?
Does it work?
How fast does it work?
Does it work reliably?
Do people use it?
Which parts cause which effects?
How can it be improved?
Questions about the impact of an artifact (7)
Do people like it?
Does it improve efficiency of performing some task?
Does it improve accuracy of performing some task?
Does it influence the collection of data?
Does it influence users’ decisions
Does it affect third parties (e.g., patients)
How long do the observed effects last?
Formative versus Summative evaluation
Formative: How can be build better systems?
Summative: What can we conclude about a system that has been built?
What can we measure and compare about a system?
Quantitative or hard research
Objectivist Evaluation approach
Assumes that questions can be answered in terms of attributes and can be measured
Assumes that rational people can and should agree a priori what attributes are important to measure
Assumes that precise numbers are better than imprecise verbal descriptions
Objectivist approach advantages
Can be relatively easy to do
Objectivist approach disadvantages
May not measure the most important results
MYCIN evaluation used _____ standard to judge therapy. It showed how ___ it was to reach a consensus on appropriate theory.
Anonymous computer or human recommendation
Relatively few cases and evaluators but still arduous to conduct
Says nothing about usability
Claims that expert-level performance was meaningless
System could not fit into real clinical workflow, despite excelling expert-level performance
What can we infer from observation of a system
Qualitative or pejoratively, soft research
Subjectivist approach assumes what is observed about a resource depends on ...
The subjectivist approach assumes the value of a resource depends on its _____, and saliency of attributes is _____dependent