Costs and Benefits of a Unique Patient Identifier for The U.S. Health Care System

In the healthcare industry, misidentification errors are not restricted to diagnostics and therapeutics but also may affect documentation. So, my earlier posts on semantics, ontologies, interoperability and the like notwithstanding, all is for naught when a given document doesn't provide information about a given patient. A chain is only as strong as its weakest link and patient identification is usually the first link in the healthcare chain.

Complicating the issue, not everybody can participate to the same degree or in the same way in the process of identifying a patient uniquely. Neonatal and senile patients are two groups where health providers and technology are on their own, when it comes to identifying the patient. Naturally, readers of this post fall into neither of these groups.

See, for example, Patient Misidentification in the Neonatal Intensive Care Unit: Quantification of Risk at

http://pediatrics.aappublications.org/cgi/reprint/117/1/e43.pdf

which provides a rather thorough study of errors in the first of these three groups.

The information that is used routinely for patient identification is frequently similar but often not recognizably unique.

In my November 20, 2009 post, Biometric and Other Identification Technologies, I discuss some leading technologies.

Although widely touted as “great” in security circles, all biometric devices (i.e., fingerprint, palm outline, iris, retina, et al) used for unique identification produce false positives and false negatives.



For example, an episode of Fox's "24" last season showed a White House visitor placing her thumb on a fingerprint scanner, a type of screening that is not typically used at the White House.

Fingerprint: false positives or negatives with scars, calluses, cracks in the skin, dirt, household cleaners and other variables.



Retina scan: susceptible to diseases such as glaucoma.



At the same time, non-biometric technologies have their own sources of error.



For a widely discussed examination of the costs and benefits of a unique patient identifier for the U.S. health care system, see

http://www.rand.org/pubs/monographs/2008/RAND_MG753.pdf

This recent study says using unique patient identification numbers for U.S. citizens would reduce medical errors, make electronic health records simpler and protect privacy.

The study says that despite a potential cost of $11 billion to create unique patient ID numbers, the effort "would likely return even more in benefits to the nation's health care system."

Most health care systems use statistical matching to find EHRs, according to the study by RAND Health, a research division of the RAND Corp. Statistical matching looks for demographic information, including names, birth dates and all or part of Social Security numbers.

See my November 17, 2009 post, Unique Patient Identification Numbers, Electronic Heath Records (EHR), Electronic Medical Records (EMR), and Social Security Numbers (SSN).

RAND researchers, who reviewed past studies, said that method causes errors or incomplete results about 8% of the time and leaves patients more exposed to privacy breaches.

"Assuming every health care system would have these [ID] numbers, then you'd be more likely to pick up all of the person's information," said Richard Hillestad, PhD, the study's lead author. "It would certainly make a lot of things easier."Using demographic information to locate EHRs causes errors or incomplete results about 8% of the time.

But critics expressed concerns.

"It's an absolutely terrible idea," said Deborah Peel, MD, a psychiatrist and chair of the Patient Privacy Rights Foundation, a watchdog group based in Austin, Texas. "Any database that has these numbers is bound to be a treasure trove for identity thieves."

The study was funded by a group of health information technology and IT companies, but Hillestad said that didn't influence the outcome. Dr. Peel is skeptical. "The combination [of data] is really deadly," she said. "That's why I say this is a data miner's dream."

The American Medical Association advocates prohibiting the sale and exchange of personally identifiable health information for commercial purposes without a patient's consent. The AMA also advocated in 1999 in favor of legislative action to repeal the portion of the Health Insurance Portability and Accountability Act of 1996 that mandated use of a unique patient identifier.

Hillestad said privacy is a big issue, but touted the ID numbers as a security boost.

"You're not sending all of the name and demographic information through the line to get connected," he said. "[Privacy] would depend on how much you protect the numbers."

Probabilistic Reasoning for OWL DL Ontologies -- Reasoning about Uncertain Domain Knowledge

Pronto is an extension of Pellet that enables probabilistic knowledge representation and reasoning in OWL ontologies. Pronto is distributed as a Java library equipped with a command line tool for demonstrating its basic capabilities. (There is no 1.0 release!) The figure below outlines the relationships among Pronto, an OWL DL Ontology, and the editor that might have created the ontology. Pellet supports reasoning with the full expressivity of OWL-DL (SHOIN(D) in Description Logic jargon) and has been extended to support the forthcoming OWL 2 specification (SROIQ(D)).



Pronto offers core OWL reasoning services for knowledge bases containing uncertain knowledge; that is, it processes statements like “Bird is a subclass-of Flying Object with probability greater than 90%” or “Tweety is-a Flying Object with probability less than 5%”. The use cases for Pronto include ontology and data alignment, as well as reasoning about uncertain domain knowledge generally; for example, risk factors associated with breast cancer.

Pronto adds the following capabilities to Pellet:

* Adding probabilistic statements to an ontology (using OWL's annotation properties)

* Inferring new probabilistic statements from a probabilistic ontology

* Explaining results of probabilistic reasoning

Pronto depends on Pellet, which is included in the Pronto release package. It also relies on Ops Research's OR-Objects package, which needs to be downloaded separately.

To download Pronto, click here.

To download OR-Objects, click here.

The features of Pronto (in addition to the features of Pellet) are outlined in the file basic.pdf, located in the /doc directory of the Pronto download.

If you are interested in a rigorous description of the approach taken by Pronto, read the paper by Thomas Lukasiewicz “Probabilistic Description Logics for the Semantic Web,” which is cited under Resources in basic.pdf.

For further reading on Probabilistic Reasoning, click

http://clarkparsia.com/weblog/2007/09/27/introducing-pronto/

http://klinov.blogspot.com/2007_11_01_archive.html

http://clarkparsia.com/weblog/2007/10/02/using-pronto/


For further reading on Pellet features, click

http://clarkparsia.com/pellet/features

An upcoming post will discuss ontologies that use fuzzy logic.

Collaborative Developement of Large, Complex and Evolving Ontologies (e.g., SNOMED CT and GALEN) using a Concurrent Versioning System (CVS)

Prior posts here have talked about ontologies as though they magically appear and seamlessly meet a variety of challenges faced by the developers of computer applications. In this and a subsequent post, I'm going to touch upon several of the difficulties present in the creation and use of certain ontologies. What follows below is a few words on the use of Concurrent Versioning Systems (CVS). My next post will discuss the gap between the majority of today's ontologies and a real world that's filled with a good deal of vagueness and uncertainty that these ontologies can't describe all that well.

OWL Ontologies are being used in many application domains. In particular, OWL is extensively used in the clinical sciences; prominent examples of OWL ontologies are the National Cancer Institute (NCI) Thesaurus, SNOMED CT, the Gene Ontology (GO), the Foundational Model of Anatomy (FMA), and GALEN.

These ontologies are large and complex; for example, SNOMED currently describes more than 350,000 concepts whereas NCI and GALEN describe around 50,000 concepts. Furthermore, these ontologies are in continuous evolution; for example the developers of NCI and GO perform approximately 350 additions of new entities and 25 deletions of obsolete entities each month.

Most realistic ontologies, including the ones just mentioned, are being developed collaboratively. The developers of an ontology can be geographically distributed and may contribute in different ways and to different extents. Maintaining such large ontologies in a collaborative way is a highly complex process, which involves tracking and managing the frequent changes to the ontology, reconciling conflicting views of the domain from different developers, minimising the introduction of errors (e.g., ensuring that the ontology does not have unintended logical consequences), and so on.

In this setting, developers need to regularly merge and reconcile their modifications to ensure that the ontology captures a consistent unified view of the domain. Changes performed by different users may, however, conflict in complex ways and lead to errors. These errors may manifest themselves both as structural (i.e., syntactic) mismatches between developers’ ontological descriptions, and as unintended logical consequences.

Tools supporting collaboration should therefore provide means for: (i) keeping track of ontology versions and changes and reverting, if necessary, to a previously agreed upon version, (ii) comparing potentially conflicting versions and identifying conflicting parts, (iii) identifying errors in the reconciled ontology constructed from conflicting versions, and (iv) suggesting possible ways to repair the identified errors with a minimal impact on the ontology.

In software engineering, the Concurrent Versioning paradigm has been very successful for collaboration in large projects. A Concurrent Versioning System (CVS) uses a client-server architecture: a CVS server stores the current version of a project and its change history; CVS clients connect to the server to create (export) a new repository, check out a copy of the project, allowing developers to work on their own ‘local’ copy, and then later to commit their changes to the server. This allows several developers to make changes concurrently to a project. To keep the system in a consistent state, the server only accepts changes to the latest version of any given project file. Developers should hence use the CVS client to regularly commit their changes and update their local copy with changes made by others. Manual intervention is only needed when a conflict arises between a committed version in the server and a yet-uncommitted local version. Conflicts are reported whenever the two compared versions of a file are not equivalent according to a given notion of equivalence between versions of a file.

Change or conflict detection amounts to checking whether two compared versions of a file are not ‘equivalent’ according to a given notion of equivalence between versions of a file.

A typical CVS treats the files in a software project as ‘ordinary’ text files and hence checking equivalence amounts to determining whether the two versions are syntactically equal (i.e., they contain exactly the same characters in exactly the same order). This notion of equivalence is, however, too strict in the case of ontologies, since OWL files, for example, have very specific structure and semantics. For example, if two OWL files are identical except for the fact that two axioms appear in different order, the corresponding ontologies should be clearly treated as ‘equivalent’: an ontology contains a set of axioms and hence their order is irrelevant.

Another possibility is to use the notion of logical equivalence. This notion of equivalence is, however, too permissive.

Therefore, the notion of a conflict should be based on a notion of ontology equivalence ‘in-between’ syntactical equality and logical equivalence.

Conflict resolution is the process of constructing a reconciled ontology from two ontology versions which are in conflict. In a CVS, the conflict resolution functionality is provided by the CVS client.

Conflict resolution in text files is usually performed by first identifying and displaying the conflicting sections in the two files (e.g., a line, or a paragraph) and then manually selecting the desired content.

Errors in the reconciliation process can be detected using a reasoner, but this too is complicated.

Collaborative Protégé is just one among several recent proposals for facilitating collaboration in ontology engineering tools. [See the following references for more information on this topic.] Such tools would allow developers to hold discussions, chat, and annotate changes.

Collaborative Protégé online demo http://protegewiki.stanford.edu/index.php/Collaborative_Protege
http://smi-protege.stanford.edu/collab-protege/

Collaborative Ontology Development with Protégé (2009)
http://protege.stanford.edu/conference/2009/slides/CollabProtegeTutorial.pdf

Noy, N.F., Tudorache, T., de Coronado, S., Musen, M.A.: Developing biomedical ontologies collaboratively. In: Proc. of AMIA 2008. (2008)

Noy, N.F., Chugh, A., Liu, W., Musen, M.A.: A framework for ontology evolution collaborative environments. In: Proc. of ISWC. (2006) 544–558

My next post will discuss the need for ontologies that benefit from fuzzy or probability-based logic when a domain has vagueness or uncertainty.

From Star Schema Ontologies Stored in an RDBMS (e.g., i2b2) to Other Ontology Stores and The Semantic Web

Recent posts here have discussed ontologies saved in relational databases (see, for example, my September 11 and 24 posts); while other posts have been about different kinds of ontology stores and the Semantic Web (see, for example, my September 27 and 6 as well as my October 11 posts). If one reads only this blog, one might think that there is no work to exploit the advantages of both approaches in a single system afoot. But, there are. A number of investigators are looking into applications that support connections to both a variety of RDBMS schemas and other forms of ontology management.

What if i2b2 built Semantic Web graphs instead of relational stores? What if it had an OWL-defined Ontology, instead of a relational-schema? Click here.

Semantic Web will be part of i2b2 and will allow it to correlate unique variable names across consortium sites (e.g., white, Caucasian) and for information retrieval. Click here

From Stanford ( Russ Altman et al ) on the west coast to Harvard ( Isaac Kohane et al ) on the east coast in the U.S. Click here.

Ontology Systems. Click here.

i2b2. Click here.

{ click the figure above for a larger view }

Uncertain Knowledge, Ontologies, and Reasoners – A Discussion of Semantic Ambiguity in the Presence of Statistical Uncertainty

Before continuing with uncertain domain knowledge, the subject of this and future posts, I’d like to give an example. I’ll introduce a scenario in which both semantic ambiguity (refer to my prior post) and statistical uncertainty (refer to the tutorials in the right-hand column of this blog) are present.

One of the limitations of most current description logic (DL) reasoners (refer to my August 6 & 24 posts below) is the inability to handle uncertain knowledge. It is a serious obstacle to the expansion of the Semantic Web, to name just one technology, because many domains of human interest contains knowledge that cannot be represented with absolute certainty. One example of an uncertain domain is medicine, in particular, disease diagnosis. Symptoms, causes and consequences of many diseases are uncertain which complicates conceptualization of such domains in formal ontologies and thus restricts machine understanding.

The next two figures, rendered without further explanation, illustrate that the difficulties introduced by semantic ambiguity of a deterministic kind can be made even more difficult when there is a need to consider statistical uncertainty at the same time. This might be the case when a patient is seen by one doctor and then asks a second doctor for his or her opinion.

However, these days, a good deal of technology is often employed by doctors before they speak to patients and to each other.

{ click on the images above for larger views }

To be continued . . .

Watson - An efficient access point to online ontologies - A gateway to the Semantic Web

Next generation semantic applications will be characterized by a large number of sometimes widely-distributed ontologies, some of them constantly evolving. That is, many next-generation semantic applications will rely on ontologies embedded in a network of already existing ontologies. Other semantic applications – e.g. some electronic health records (EHR) – will maintain a single, globally consistent semantic model that serves the needs of application developers and fully integrates a number of pre-existing ontologies.

As the Semantic Web gains momentum, more and more semantic data is becoming available online. Semantic Web applications need an efficient access point to this Semantic Web data. Watson, the main focus of this post, provides such a gateway. Two limited demonstrations of Watson - one video, the other static - are given below.

Overview of Watson Functionalities

The role of a gateway to the Semantic Web is to provide an efficient access point to online ontologies and semantic data. Therefore, such a gateway plays three main roles:

(1) it collects the available semantic content on the Web
(2) analyzes it to extract useful metadata and indexes, and
(3) implements efficient query facilities to access the data.

Watson provides a variety of access mechanisms, both for human users and software programs. The combination of mechanisms for searching semantic documents (keyword search), retrieving metadata about these documents and querying their content (e.g., through SPARQL) provides all the necessary elements for applications to select and exploit online semantic resources in a lightweight fashion, without having to download the corresponding ontologies.

For a easy-to-follow video demonstration of The Watson plug-in for the NeOn toolkit, click on

http://videolectures.net/iswc07_daquin_watson/

and, better still, click one of the Media Player links at this destination.

Note: There is a Watson plug-in for the ontology editor Protégé in the works.

Protégé (see my August 24 post below) is probably the most popular ontology editor available. In addition, its well established plug-in system facilitates the development of a plug-in using the Waston Web Services and API. To date, however, the Protégé site provides only what it describes as, “more a proof of concept or an example than a real plug-in.”

NeOn Toolkit

The NeOn architechture for ontology management supports the next generation semantics-based applications. The NeOn architecture is designed in an open and modular way and includes infrastructure services such as a registry and a repository and supports distributed components for ontology development, reasoning and collaboration in networked environments.

The NeOn toolkit, the reference implementation of the NeOn architechture, is based on the Eclipse infrastructure.

Ontology Management
Semantic Web, Semantic Web Services, and Business Applications
Copyright 2008 Springer

A static demonstration of the Watson plug-in for the NeOn toolkit

The Watson plug-in allows the user to select entities of the currently edited ontology he/she would like to inspect, and to automatically trigger queries to Watson, as a remote Web service. Results of these queries, i.e. semantic descriptions of the selected entities in online ontologies, are displayed in an additional view allowing further interactions. The figure below provides an example, where the user has selected the concept “human” and triggered a Watson search. The view on the right provides the query results (a list of definitions of class human which have been found on the Semantic Web) and allows easy integration of the results by simply clicking on one of the different “add”-buttons.

Finally, the core of the plug-in is the component that interacts with the core of the NeOn toolkit: its datamodel. Statements retrieved by Watson from external ontologies can be integrated in the edited ontology, requiring for the plug-in to extend this ontology through the NeOn toolkit datamodel and data management component.

{click on the image above for a larger view}

An interesting exercise:

Follow the link http://watson.kmi.open.ac.uk/WatsonWUI/

And search on "snomed"

And, this dynamic view is what you get after clicking the (view as graph) link.

Functional Design of an Ontology --- Relationship of the i2b2 ontology to star schema

Recent posts to this blog have discussed ontologies and description logics . As mentioned earlier, the OWL-DL and OWL-Lite sub-languages of the W3C-endorsed Web Ontology Language (OWL) are based on a description logic. A tool for editing and creating ontologies, Protégé, was also described.

In the present post, I’d like to describe the functional design of the ontology used by i2b2, a collection of open-source software tools for the collection and management of project-related clinical research data. That is, this post will present an introduction to what’s under the hood.

Data storage

i2b2 data is stored in a relational database, usually either Oracle or SQL Server and always in a star schema format, a design proposed initially by Ralph Kimball in the 1980s. It is named this because of the appearance of the final database schema diagram that looks like a star (see figure below).

Notes: Ralph Kimball and I were formerly regular contributors to now-defunct DBMS Magazine. A brief introduction to the star schema format is given in the OLAP section of my article Using Neural Networks and OLAP Tools to Make Business Decisions. (See the bibliography at the bottom of this blog)

{click on the images above for larger views}

A star schema contains one fact and many dimension tables. The fact table contains the quantitative or factual data, while the dimension tables contain descriptors that further characterize the facts.

Facts are defined by concept codes and the hierarchical structure of these codes together with their descriptive terms and some other information forms the i2b2 ontology (also called metadata).

i2b2 ontology data may consist of one or many tables. If there is one table, it will contain all the possible data types or categories. The other option is to have one table for each data type. Examples of data types are: diagnoses, procedures, demographics, lab tests, encounters (visits or observations), providers, health history, transfusion data, microbiology data and various types of genetics data. All metadata tables must have the same basic structure.

The structure of the metadata is integral to the visualization of concepts in the i2b2 tools, as well as for querying the data.

In healthcare, a logical fact is an observation on a patient. It is important to note that an observation may not represent the onset or date of the condition or event being described, but instead is simply a recording or a notation of something. For example, the observation of ‘diabetes’ recorded in the database as a ‘fact’ at a particular time does not mean that the condition of diabetes began exactly at that time, only that a diagnosis was recorded at that time (there may be many diagnoses of diabetes for this patient over time).

The fact table contains the basic attributes about the observation, such as the patient and provider numbers, a concept code for the concept observed, a start and end date, and other parameters. In i2b2, as shown in the figure above, the fact table is called observation_fact.

Dimension tables contain further descriptive and analytical information about attributes in the fact table. A dimension table may contain information about how certain data is organized, such as a hierarchy that can be used to categorize or summarize the data. In the i2b2 Data Mart, there are four dimension tables that provide additional information about fields in the fact table: patient_dimension, concept_dimension, visit_dimension, and provider_dimension.

Scalability

Once a database grows to over 10 million items, the advantages of a star schema can start to take hold. The first consideration is the speed and integrity of the queries. When one exceeds 0.5 billion rows in a database, it becomes important to have the data expressed in very large indexes. Very large indexes are only possible with very large tables. If one has several hundred or thousand tables in a database (easily attained in large transaction systems), one will have at least one index on each table resulting in several hundred or thousand small indexes. Joins between 100‐1000 indexes for each query will result in slow performance (hours), while joins between 3‐4 indexes, even representing 100’s of millions of rows, will be fast (seconds). Furthermore, the integrity of queries in a transactional database is also compromised because queries can often be answered through several paths in a circular manner.

The second consideration is the need for a large analytic database to constantly absorb new data. The database schema does not change as new data sources are added. New data will result in additional rows added to the fact, patient, and visit tables. New concepts and observers will result in new rows added to the concept and provider tables. But new columns and tables do not need to be added for each new data source. This is very useful in large projects where there are many tools depending upon a specific database schema. A strategy where the database grows by adding rows for new data rather than adding new tables and columns allows tools developed to work with one kind of data to also work with a new source of data.

The third advantage of the star schema is the ability to manage the metadata of a large analytic database. Metadata is used to perform queries, and if it is incorrect a query will be profoundly affected. For example, if one wanted to find all the patients with diabetes, but left out one of the codes used to represent diabetes in a database, none of those orphaned patients would be counted. The detection of orphaned concepts is easily achieved in the star schema by, for example, joining the fact table to the concept and provider tables and reporting those fact table concepts and providers left out by the join.

A sample ontology query for diagnosis

To find all the patients that were diagnosed with migraines, use this query:

Select distinct (patient_num)
From observation_fact
Where concept_cd in
(select concept_cd
from concept_dimension
where concept_path like '%Neurologic Disorders (320-389)\(346) Migraine\%')

Note: The material in this post has been taken largely from the following i2b2 pages, which should be consulted for further details:

https://www.i2b2.org/software/projects/ontologymgmt/Ontology_Design_Doc_13.pdf

https://www.i2b2.org/software/projects/workbench/i2b2Workbench_Description.pdf

https://www.i2b2.org/software/projects/datarepo/CRC_Design_Doc_13.pdf

Reasoning for Ontology Engineering and Usage and The Challenges of Modern Medical Ontologies

In my August 6 post, I briefly introduced ontology editor Protégé 4.0 with the reasoners FaCT++ (implemented using C++) and Pellet (Java based). Today's post picks up this story and adds the RacerPro (commercial) reasoner to the mix. You can -- and I recommend that you do -- download your own copies of the latest versions of these tools. Links that enable you to do so are located at the end of this post.



Protégé 4.0 with three reasoner added-ins

A reasoner is a piece of software able to infer logical consequences from a set of asserted facts or axioms. In the present context, a reasoner makes inferences about classes and individuals in an ontology, tasks that are beyond the Web Ontology Language (OWL) model alone.

Ontologies, as described in prior posts, are formal vocabularies of terms, often shared by a community of users, and, as such, ontologies play an important role in semantic interoperability and Web 3.0. One of the most prominent application areas of ontologies is medicine and the life sciences. For example, the Systematised Nomenclature of Medicine Clinical Terms (SNOMED CT) is a clinical ontology. Another example is the OBO Foundry -- a repository containing about 80 biomedical ontologies.

These ontologies are gradually superseding existing medical classifications and will provide the future platforms for gathering and sharing medical knowledge. Capturing medical records using ontologies will reduce the possibility for data misinterpretation, and will enable information exchange between different applications and institutions.

Medical ontologies are strongly related to description logics (DLs), which provide the formal basis for many ontology languages, most notably the W3C standardised OWL. All the above mentioned ontologies are nowadays available in OWL and, therefore, in a description logic. The developers of medical ontologies have recognised the numerous benefits of using DLs, such as the clear and unambiguous semantics for different modelling constructs, the well-understood tradeoffs between expressivity and computational complexity, and the availability of provably correct reasoners and tools (discussion to follow).

The development and application of ontologies crucially depend on reasoning. Ontology classification, i.e., organising classes into a specialisation/generalisation hierarchy, is a reasoning task that plays a major role during ontology development: it provides for the detection of potential modelling errors such as inconsistent class descriptions and missing sub-class relationships. For example, about 180 missing sub-class relationships were detected when the version of SNOMED CT used by the NHS was classified using the DL reasoner FaCT++. Query answering is another reasoning task that is mainly used during ontology-based information retrieval; e.g., in clinical applications query answering might be used to retrieve "all patients that suffer from nut allergies".

Despite the impressive state-of-the-art, modern medical ontologies pose significant challenges to both the theory and practice of DL-based languages. Existing reasoners can efficiently deal with some large ontologies, but many important ontologies are still beyond the reach of available tools (i.e., they are unable to classify some widely used ontologies).

Applications currently need to work around these limitations, e.g., by using subsets of ontologies that can be successfully processed. For example, the version of GALEN typically used in practice contains only about 20% of the axioms of the full version; this reduces the interaction between concepts and thus makes the ontology "processable". This is, however, highly undesirable in practice, because it reduces coverage, weakens the conceptualisation of the domain and may prevent the detection of modelling errors.

Furthermore, the amount of data used with ontologies can be orders of magnitude larger than the ontology itself. For example, the annotation of patients' medical records in a single hospital can easily produce data consisting of hundreds of millions of facts, and aggregation at a national level might produce billions of facts. Existing reasoners cannot cope with such data volumes, especially not if ontologies such as GALEN and FMA are used as schemata.

Having forewarned you about these limitations, I'd like to recommend the following video on reasoners -- free and commercial.

http://videolectures.net/iswc08_moller_itsr/

Some readers of this blog might not be familiar with terms that appear in the video, starting with ABox and TBox.



For those readers especially, the following links for accessing the Protégé, Pellet and Racer sites could be used to install and examine this software (and accompaning documentation) before watching the videos.

Protégé http://protege.stanford.edu/

Pellet http://clarkparsia.com/pellet/

RacerPro http://www.racer-systems.com/

Then, as you watch the video, you could follow along using your own running code. For some, this will require more than a single session.

Recommended reading - basics of description logics:
www.inf.unibz.it/~franconi/dl/course/dlhb/dlhb-01.pdf
www.inf.unibz.it/~franconi/dl/course/dlhb/dlhb-02.pdf
http://www.cs.man.ac.uk/~horrocks/Slides/IJCAR-tutorial/Print/p1-introduction.pdf

Semantic Web Technologies: Ontologies, Agents, Web Services

Here's a Web app developed at Stanford University some time ago. It's made up of a single ontology with entries for foods and wines, an ontology agent that returns text from this ontology and a portal that manipulates the text returned by the agent.

http://onto.stanford.edu:8080/wino/index.jsp

The ontology underlying the agent used here contains hierarchies and descriptions of food and wine categories, along with restrictions on how particular instances might be paired together.

For readers wanting an easy-to-read discussion on what exactly an agent is and how it works with ontologies, see

http://www.nature.com/nature/webmatters/agents/agents.html

The next three figures are of screen shots taken from this Web app, which doesn't always employ state-of-the-art technologies like OWL (discussed in earlier posts) under the hood; but, this app provides a simple example of the most basic building blocks that are found in many of today's Semantic Web apps (also discussed in earlier posts).



Figure I - The home page




Figure II - After clicking on the "Roast Duck" link




Figure III - After clicking on the "Web Inventory Search" link

The ontology defines the concept of a wine. According to the specification, a wine is a potable liquid produced by at least one maker of type winery, and is made from at least one type of grape (such grapes are restricted to wine grapes elsewhere in the ontology.)

The declaration additionally stipulates that a wine comes from a region that is wine-producing and, most importantly to the agent, that a wine has four properties: color, sugar, body, and flavor.

The concept of a meal course underlies pairing of a food with a wine. Each course is a consumable thing comprising at least one food and at least one drink, the latter of which is stipulated to be a wine.

When the user selects a type of course, or an individual food that gets mapped to a type of course, the agent will consult that course definition for restrictions on the constituent food or wine. All such course types map back to this concept, like objects to their superclasses in object-oriented programming.

Suppose the user has selected pasta with fra diavolo, or perhaps pasta with spicy red sauce directly. The concept of such a food is defined elsewhere in the ontology. Furthermore, such courses must be a subclass of those with specific restrictions on the properties of their wines.

One wine that matches the above restrictions is the Pauillac. This individual wine is simply defined as a Pauillac whose maker is Chateau Lafite Rothschild. Together with other statements in the ontology, this allows the reasoner (discussed in an earlier post) to deduce many additional facts: that this a Medoc wine from Bordeaux, in France, and that it is red, to name a few.

The concept of a Pauillac specifies that all such wines feature full bodies and strong flavors and are made entirely from cabernet sauvignon grapes. Further, Pauillacs are a particular subset of Medocs, distinguished by their origin in the Pauillac region. It is through this additional subclass relationship that Pauillac are defined elsewhere as red and dry.

Following the above example through the ontology reveals a straightforward logical path for pairing the Pauillac with the selected course. Because these items were specified in a standardized, machine-readable format, it is an equally straightforward task for any compliant automated reasoner.

Why use an ontology?

The functionality provided by the wine agent is not unlike that which could be provided by a simple look-up table. Indeed, food/wine pairings are traditionally published in some form of tabular chart where marks appear at the intersections of columns and rows representing compatible varieties of food and wine. The wine agent demonstrates that at least this simple task can be accomplished within semantic markup technology, but what about more complicated applications like, for example, those required by electronic health rcords (EHR)? For now, I'll postpone any discussion of EHR and stick with this food-wine pairing app.

Suppose that if not the entire web, then at least some number of cooperating parties were using semantic markup to participate in this project. Rather than the traditional approach of trying to build an enormous database of foods and wines, then, the definitions would be distributed across the participating parties. A restaurant or retailer offering an on-line menu could mark each food item with standardized machine-readable definitions. Similarly, then, a wine retailer could mark its wines according to the definitions exemplified above.

Such markings would benefit from well-known advantages of ontologies. For instance, through the subclassing, adding a new Pauillac to the inventory would not require wine.com (the source of the GUI shown in Figure III) to mark all of the wine's properties; it would just be another Pauillac as specified in the example, plus any differentiating features. But more importantly in terms of software agents, all the markings would be machine readable, and could be handled by systems from any organization.

Rather than relying on a human user to select a food or food type, the agent could crawl the web for foods marked within the wines namespace and pre-compile suitable pairings. This is where Web services (discussed in earlier posts) come in.

Footnote

The notion of agent-based computing has been adopted enthusiastically in the financial trading community, where autonomous market trading agents have been said to outperform human commodity traders by 7%.

Machines can monitor stock market movements much more quickly than humans, and if you can encode the kinds of rules that you want, then it is not unreasonable to imagine that computational traders will be able to outperform humans.

I commented on high-speed trading in my August 3 post.

SNOMED, OWL, Ontologies, Protege, etc. Hardware and Software Issues.

In my last two posts, I rather glibly talked about SNOMED, OWL, ontologies, Protege, etc. without mentioning any hardware or software issues that sometimes arise.

For most of us, these matters are best understood from our own "trial and error" experiences. Nonetheless, I've added links to a couple of informative anecdotes below: in one, the account of someone computing successfully with 8 dual CPUs and 15 gig RAM; in another, the account of someone computing unsuccessfully having far less resources.

Link 1: Modeling Massive Ontologies (SNOMED) at Kaiser

Link 2: SNOMED OWL On Protege

Footnote 1: Some large OWL files will not load into Protege on a 32-bit computer when to do so requires in excess of 4 Gigs RAM, the theoretical limit of a 32-bit system. In order to get around this limitation, a 64 bit machine is needed. Fortunately, the Linux, Windows, and Mac operating systems are available in 64-bit versions.

Footnote 2: The entire computing industry is moving from 32-bit to 64-bit technology, and it’s easy to see why. While many of today’s computers can hold far more than 4GB of physical memory, the 32-bit applications that run on them can address only 4GB of RAM at a time. 64-bit computing shatters that barrier by enabling applications to address a theoretical 16 billion gigabytes of memory, or 16 exabytes. 64-bit machines can also crunch twice the data per clock cycle, which can dramatically speed up numeric calculations and other tasks.

Ontologies, Ontology Languages, and Semantic Interoperability -- Segue to Electronic Health Records (EHR)

This post serves as a transition between my previous one on OWL and ontologies and my upcoming ones on electronic health records (EHR) - past, present and future.

OWL is the latest standard in ontology languages from the World Wide Web Consortium (W3C) - it is built on top of RDF (i.e., OWL semantically extends RDF).

These two languages are explained in

http://www.co-ode.org/resources/tutorials/intro/slides/OWLFoundationsSlides.pdf

As an example of an ontology that's central to building an interoperable EHR system, I'll cite the Systematized Nomenclature of Medicine (SNOMED) ontology, which is used in more than 50 countries around the world:



{click to enlarge}

The Systematized Nomenclature of Medicine Clinical Terms (SNOMED CT) Ontology includes a Core terminology of over 364,000 health care concepts with unique meanings and formal logic—based definitions organized into hierarchies. As of January 2005, the fully populated table with unique descriptions for each concept contained more than 984,000 descriptions. Approximately 1.45 million semantic relationships exist to enable reliability and consistency of data retrieval. SNOMED CT is available in English, Spanish and German language editions.

What is its structure?

Core content includes the concepts table, descriptions table, relationships table, history table, an ICD-9-CM mapping, and the Technical Reference Guide. And, it can map to other medical terminologies and classification systems already in use.

SNOMED is meant to be complementary to LOINC (Logical Observations Identifiers, Names, Codes), another clinical terminology important for laboratory test orders and results.

See http://www.ihtsdo.org/ for a good deal more information on SNOMED.

For advanced IT readers

The DL that SNOMED uses is much less expressive than OWL. The result is, even though you can mechanically translate SNOMED into OWL, the resulting OWL ontology will be very unlike anything an OWL author would create starting from scratch, and might also be a challenge to classify successfully under an OWL reasoner without a lot of manual editing.

Furthermore, even at that point it would also be of limited value in supporting reasoning over OWL instances, as many kinds of assertions that would be routine in an OWL ontology (like disjoints, explicit domain/range constraints, etc.) do not exist in native SNOMED and would have to be created.

One opinion holds that creating your own OWL ontology and using SNOMED as a mapping target leverages SNOMED in a more useful way for most conceivable applications.

Finally, for a good deal more on the topics covered so far, consider

Clinical Decision Support Systems
Theory and Practice
Series: Health Informatics
Berner, Eta S. (Ed.)
2nd ed., 2007
ISBN: 978-0-387-33914-6