Return of OntoLoki - on a Freaky Friday

One of my favorite traditions initiated in Mark Wilkinson's laboratory (where I did my PhD) was "Freaky Friday".  Following the spirit of Google's "20% time", lab members were encouraged to take out some time on Friday to pursue their own crazy ideas - leaving their core projects aside for a few hours.  This was fun and ended up producing some useful things like "Tag clouds for summarizing web search results" (one of my most cited articles and only 2 pages long!) and "The Entity Describer".  In this spirit, I took out some time last Freaky Friday to do something very far away from the things I should really be doing.  Sadly I didn't hack something fun together.  Instead, per Dr. Wilkinson's 50th request for me to do this, I performed a Frankensteinian resurrection.  Digging deep into the grave of my PhD dissertation, I found the one unpublished chapter, cleaned it up, and deposited it into the arXiv.  The project, called OntoLoki, is now undead!  Check out this undead manuscript about automatic quality evaluation for ontologies.

I am OntoLoki!  Feed me your ontologies for evaluation!

OntoLoki: an automatic, instance-based method for the evaluation of biological ontologies on the Semantic Web

Benjamin M. Good
Gavin Ha
Chi K. Ho
Mark D. Wilkinson

Annotation evaluation

A few years ago, a friend of mine was an author on an article about global gene coexpression analysis. In the article, they looked across many experiments to find pairs of genes that consistently shared patterns of expression (indicating likely co-regulation). As one of the validations of their globally co-expressed gene-pairs, they measured whether or not the sets were also co-annotated with the same biological process label from the gene ontology. The idea being that if they were co-expressed they should be more likely to belong to the same biological process.

This suggested to me at the time that this kind of analysis might somehow be turned on its head to provide evidence regarding the quality of the annotations themselves. Basically each annotation would be treated as a hypothesis and then continually subjected to testing. So the assertion GeneA is part of Biological Process Y would be strengthened if GeneB was co-expressed with GeneA and was also a part of the same biological process. I imagine there would be many other forms of such evidence.

Just wanted to jot that down..

OntoLoki lives!

(Update June 8, 2012.  This paper was not accepted at first submission (see sad story), but can be accessed as Chapter 4 in my dissertation.  I've had enough interest in the concepts it contains that it is probably worth resubmitting it somewhere, someday, somehow...)


As noted in previous posts labeled with the tag OntoLoki, I've been working off and on for a few years now (yikes) on a program for automatic ontology evaluation.  Now, we are getting ready to submit our first paper on the subject and would like to open things up for comments.  I labeled it as a technical report in hopes of starting a tradition of such things in our laboratory.  It seems like a good way to keep the locals on track and have another chance for reviews before things go out into the scary world of official peer review.  I suppose I could drop this into Nature Preceedings again, but I'm tempted to wait until its gone through more revision cycles before I do so as that is likely to form a more permanent record than I am really ready to commit to I think.

Here is the longish abstract to whet your appetite.  I was thinking of blogging the rest of the document as distinct posts for each section - thoughts on that?  

As always I really appreciate any time you spend here and any ideas that you choose to share.

Abstract

Background: The delineation of clear, logical definitions for each class in an ontology and the consistent application of these definitions to the assignment of instances to classes are important criteria for ontology evaluation. If ontologies are specified with formal, property-based restrictions on class membership, then such consistency can be checked automatically using existing technology. If no such logical restrictions are applied however, as is the case with many current biological ontologies, there are currently no automated methods for measuring the semantic consistency of instance assignment on an ontology-wide scale, nor for inferring the patterns of properties that might define a particular class.

Objective: The aim of this study is to identify, implement, and test a new method for automatic, data-driven ontology evaluation that is suitable for the evaluation of ontologies with no formally defined restrictions on class membership. The method should quantify the consistency of instance classification within such an ontology based on patterns of properties found to be associated with the instances of particular classes.

Design: We constructed a program that takes as its input an OWL/RDF knowledge base containing an ontology, instances associated with each of the classes in the ontology, and properties of those instances. For each class, it outputs: 1) a rule for determining class membership based on the properties of the instances and 2) a quantitative score for the class that reflects the ability of the identified rule to correctly predict class membership for the instances in the knowledge base. To test the proposed method, we constructed a series of knowledge bases that varied from perfectly consistent through to completely random and evaluated each one using the implementation. In addition to this artificial control study, two other well-known biological ontologies were evaluated using public data to provide indications of the behavior of the system in realistic contexts.

Results: In the first experiment, the method produced direct quantitative assessments of the different versions of the knowledge bases that correlated directly with the known level of consistency of instance assignment for each knowledge base. The evaluations of the other ontologies indicated that the method was successful at detecting relevant patterns associated with the instances of classes in real biological ontologies based on publicly available data.

Conclusion: The results indicate that the suggested method can be used to conduct objective, automatic, data-driven evaluations of biological ontologies without formal class definitions in regards to the property-based consistency of instance-assignment. This inductive method complements existing, purely deductive approaches to automatic consistency checking, offering not just the potential to help in the ontology engineering process but also in the knowledge discovery process.

Consequences of instance-based ontology evaluation

As I mentioned before, one of my main projects these days is the production of an "instance-based" program for ontology evaluation. The fundamental idea is that, when evaluated in the context of an operational system, ontological classes should represent some consistent and unique pattern of features associated with the instances in the system. For example, the proteins (instances) annotated as extracellular (class) should display some common motif (e.g. a signal peptide) or combination thereof if the the class is a good one.

So far, our program stands on the assumption that all of the data that goes into it (annotation of proteins..) is generally complete and valid. If the assignment of instances to classes or the assignment of other property values to instances is flawed, then the quality estimates for the classes in the ontology will be low. Thus, when we evaluate the quality of a particular class, we are also implicitly evaluating the quality (and the quantity) of the entire annotation system in which the class is embedded.

Is this good, bad or ugly?

Personally, I like it... and this is one reason why:

The other consequence, alluded to earlier, of this form of ontology evaluation is that it may help to expose the causal mechansims underlying associations between instances and their annotation. To illustrate, if classes in ontologies were evaluated using this method on a periodic basis, trends in performance on this test should be observed that indicate both the quality of the idea represented by the class and the reasons that instances should be assigned to the class.

In the beginning of an ontology-driven annotation project, few instances will be present and thus all classes will score poorly. Over time, more instances and more annotations of those instances will be added to the system. If the classes (concepts etc..), the assignment of instances to those classes, and the other annotations are good, then the scores should improve accordingly. Ideally, the scores would improve to the point that the patterns extracted during the evaluations could be used to automatically assign new instances to classes - a la DL reasoning or another mechanized classification system.

This pattern seems to fit the scientific method well. First instances are observed and described. For example, experiments are conducted to find out where proteins are located in cells. After many instances are observed and described, theories are proposed and tested that explain why those instances fit in those classes. For example, proteins seem to fit in the class extracellular because they contain a particular pattern of amino acids, thus any protein that displays the same pattern should, according to this principle, also fit into this class.

This all seems to suggest that perhaps we should be building applications that embed machine induction as a fundamental part of a continuous process of knowledge evolution. Oh wait.. people already did that and more !!!

Sigh.

open kimono part 2

In a comment on open kimono part 1 "Luke" said that perhaps the question is more what the benefits of blogging are than the costs. As I'm pretty new to this scene, I think I will experiment a bit and tell you my results as they come in before going straight for my own predictions.

Experiment number 1 - Below is a problem I'm working on in the area of ontology quality evaluation. Lets see if blogging it out before trying to publish it / finish my research helps, hurts or doesn't matter..

Last year Barry Smith published an article indicating that the quality of a category in a terminology is best estimated through an inspection of the characteristics of the instances that get [manually] assigned to it. Basically, to evaluate a category (concept, class, set, whatever...) you try to find a pattern that is both consistent across the instances in the category and unique (the pattern is not present in instances not assigned to that category). Before any DL people start shouting - of course, if everyone wrote ontologies with logical restrictions on membership for each class, then we wouldn't need to worry about this as the desiderata would be enforced by reasoner, but, living in the world where the most powerful ontology developing force (OBO) is not just reticent, but seems actively opposed to the description logic approach, its still an important consideration. So..

A clever undergrad (Gavin Ha) and I have produced a program that:

1. reads in an OWL/RDF document including both classes and instances
   
2. builds a table with instances as rows and classes and other properties of the instances as the columns
   
3. prunes out unwanted columns (depending..)
   
4. sends the table off to alorithms from WEKA that attempt to build classifiers (e.g. decision trees) for a specified class within the ontology based on the attributes of the instances.
   

The idea being that, if we can find a pattern, the class is 'good', if not, then the class is 'less good' and we can quantify the goodness based on the number of instances the pattern correctly classifies.

So far, it works great on a positive control containing about 25 classes with 500 instances strictly obeying predetermined rules for class membership. It discovers those rules blinded and scores the classes appropriately (e.g. %correct for instances that should be in or out of the class). One of the nice things about this is that, depending on the classifier chosen, the rules discovered in the data can be automatically represented as OWL restrictions and thus given to ontology engineers as suggestions.

Now, of course, we are trying this out on bits of the gene ontology to see if there are any patterns that can be mined from the databases that correpond to GO classes. Trouble is, the GO is both large and, in many areas, relatively sparsely instantiated. The question that arises is, for a given class (term..) when we try to find a pattern than discriminates its members from those outside the class, how do we choose the negative set? In our test case, the negative set for any particular class was simply everything outside of it, but when the set in question contains only 10-100 things and everything else contains a million things this isn't really a good way to go.

Thinking of starting with only the closest neighbors for the class in question (kind of like the logic behind SVMs).

Any thoughts?