Thinking Clearly .

We’re happy to announce the release of Pronto 0.2—our Pellet-based probabilistic reasoner for OWL DL ontologies.

Pronto 0.2 is an optimization and bug fix release; there are no reasonably important new features, at least as far end users are concerned. We have very much been concerned with performance and scalability issues which were (and some still are) problematic in 0.1.

Our success in improving performance and scalability has been mixed so far. There’re pretty substantial performance improvements, i.e. Pronto 0.2 is more predictable and at least a few times faster than Pronto 0.1 when running on our test data. Simply put, if Pronto 0.1 is capable of reasoning with some probabilistic ontology, Pronto 0.2. will reason with that ontology much faster. How much faster depends on the KB.

Regarding scalability, the progress has been less impressive; Pronto still doesn’t scale beyond around 15 generic (TBox) conditional constraints. Being a little more technical here: it’s polynomially better than Pronto 0.1, but that doesn’t entirely solve the problem with exponential complexity of probabilistic DL reasoning. More news about the ongoing progress in that direction is expected towards the end of summer 2008.

Now let’s turn to the nature of the performance improvements. The main one is the new lexicographic entailment algorithm that replaced the original Lukasiewicz TLexEnt procedure that was based on brute force search for the preferred models. Recall that Pronto is a non-monotonic reasoner, so it infers knowledge from the set of preferred models of the KB, not from the set of all models.

The new algorithm is based on the idea of carefully identifying and eliminating small pieces of the KB that can’t be satisfied by the preferred models. This is similar to computing the maximal satisfiable (or minimal unsatifiable) subsets of ontology, which are techniques are used for debugging classical OWL ontologies. The algorithm helps to make reasoning a lot more predictable and robust, i.e. reduces the difference between the easy ontologies and hard ones that previously required 10-15x reasoning time.

There are also other optimization techniques, most of which try to reduce the excessive amount of classical DL reasoning performed during the probabilistic entailment.

Improvements are illustrated on the following diagram. It compares the performance of Pronto 0.1 and Pronto 0.2 on a set of randomly generated probabilistic ontologies. The Y axis shows the reasoning time and X axis shows the metric that we developed to assess the “hardness” of specific probabilistic KBs before reasoning with them.

Basically we wanted to understand what makes KBs hard for reasoning and it seemed that “connectivity”, i.e., number of all possible subsumption relations between OWL classes in probabilistic statements might matter. The intuition is that the higher the connectivity, the easier must be the
KB.

The results show that in addition to simply being faster, Pronto 0.2 is also more robust as there are no “hard outliers”—KBs that take a lot more reasoning time as compared to others of the same size. And it’s more predictable, i.e. by using the metric (which is fast to compute) one can roughly estimate reasoning time for Pronto 0.2.

We are currently working on the scalability problem. Hopefully soon we’ll have a better idea of how large probabilistic ontologies can still be reasoned with. Scalability improvements after that point will likely be concerned with partitioning or decomposing probabilistic KBs into smaller probabilistically independent fragments.

This entry was posted on Wednesday, July 16th, 2008 at 10:05 am and is filed under Probabilistic Reasoning. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.