Tuesday, September 30, 2008

Expressiveness of Semantic MediaWiki

Semantic MediaWiki (SMW) represents a concept as a page. Each page is exactly one concept. Each link to another page is potentially a triple, with an annotation on the link identifying the relation. This in a nutshell is the syntactic representation of triples in SMW. Categories potentially reflect classes, while normal pages reflect individuals. This gives a class-instance distinction.

This simple approach allows us to represent a variety of knowledge. But there are many other key constructs required for authoring a full ontology. I'll just give one example here: template vs own slots. These terms require some explanation. Template slots are defined on classes. Suppose (C1 r V2) is a triple representing a specification of a template slot. C1 is a class, and V2 is some valid value for r. By stating this triple, we're asserting that the filler of r in an instance of C1 must be V2. If r were an own slot, by contrast, C1 itself would have a value V2 in the filler of r. The instances of C1 would not be directly aware of this triple.

Further, the assumption that a single page describes only one concept is not tenable in any realistic situation. All but the simplest articles deal with multiple concepts. Splitting an article into components is often not feasible, as the content becomes too scattered for easy human consumption. I deal with both issues in the remainder of this post.

Given that we want to represent knowledge as succinctly as possible within the general wiki syntax, creating every semantic distinction within the wiki is a significant challenge. The SMW syntax is very simple, but the knowledge one can describe through it is too simplistic. A few straightforward changes can make SMW much more expressive.

Let's start with classes and instances. I don't think it is a good idea to conflate a class with a category, and an instance with an article. Each of these objects have distinct roles that are then lost. For example, each article is an instance of a class Document. The article discusses subjects that can be mapped to concepts. But the article is not itself a concept.

Here's a simple mechanism for producing such mappings. Each time an article discusses something that can be related to a concept, declare a start tag. At the end of the discussion, close with a end tag.

But, if an article no longer represents something in the KB, we can no longer rely on links to describe triples. This is easily addressed. Insofar as an article talks about anything, it is generally possible to define a primary topic for the article. Then a link is substituted with that primary topic when we're defining triples.

The nesting of topics also represents a relationship between those topics. This is similar to annotated links describing relations between concepts in the KB.

Allow a document to represent a class, an individual, or neither. This can be easily declared, just as categories are declared. This will enable documents to describe either classes or instances, or a combination of the two. The current SMW implementation supports linking categories to anything one wishes. However, categories do not show factboxes, except in previews. Asking for the OWL export of a category does not include the properties that had been included there. These may just be bugs, but as far as I know there exists no specification of the meaning of linking a category to another via a relation. One needs to be able to say whether a property linking two classes is intended as an own slot, a template slot, or a restriction on the slot filler of the source class. I would contend that in most cases one can deduce the intended meaning by considering the domain and range restrictions for a slot.

Effectively, my experience is that SMW can't describe anything but the most rudimentary content about classes. One cannot really develop an ontology in SMW as it exists today. At best one can describe basic taxonomy.

Thursday, September 25, 2008

Photography class

I have registered for a photography class. Digital nature photography, offered through the Palo Alto Camera Club. First time I'm taking a photography class, rather excited! I've learned a bit on my own so far about photography, but I really feel like I'm missing something... That I won't really get any better just working at it on my own.

Long overdue update

I have been meaning to put together a blog entry for a long time, but finding time has been difficult. We went to the Eastern Sierras, where I was chased (briefly) by a bear. Lehman has tanked, and AIG has been on the brink. Freddie and Fannie are gone. Our house still needs work. I finally got my green card, right in time to see the economy go south. Lightroom 2 came out. And there were more events besides that I would rather not mention here. Where do I begin?

About the only big thing that I haven't covered here is programming and work. So I'll focus on that. My lisp hacking of late has been pretty routine. In fact, all my hacking has been pretty routine. I've been developing the server portion of our software, and it has been going as well as can be expected. Try as I might, I can't think of anything truly interesting I've done over the past few weeks. Time has been spent on bug fixing and other such tasks. Instead, I'll turn to one of the key aspects of our software: the manipulation of knowledge as a graph. This also ties in with one of my previous posts on hypergraphs.

We have viewed graphs as labeled edges connecting nodes. This has the obvious deficiency that this type of data structure falls outside the scope of many standard graph algorithms. My initial approach to addressing this problem was to construct different types of graphs to tackle the various algorithmic problems we faced.

One of the graph types was an edge graph. This graph has two types of nodes: one representing nodes, and the other representing edges. Suppose we have a triple (n1 s n2) in our KB. This translates to a graph with three nodes: n1, n1sn2, and n2. The edges in this graph are n1->n1sn2, n1sn2->n2. Slots don't have an explicit representation in this scheme. They are instead replaced with a representation of the complete edge.

Another type of graph is the node graph. Given a triple (n1 s n2) in our KB, we reduce it to an edge n1->n2 in our graph. Similarly, we can also define an "edge graph". Suppose we have two triples (n1 s1 n2) and (n2 s2 n3) in our KB. We can define an edge in our graph n1s1n2->n2s2n3 in our graph.

It is critical that these are not general purpose KB representation schemes. These are merely mechanisms for reducing the KB to a representation useful for solving certain problems. Hypergraphs by contrast provide a faithful representation of the triples in a knowledge base. A hypergraph could thus serve both purposes: represent the KB and provide a basis for implementing various knowledge manipulation algorithms.

So, how would DFS look in a hypergraph? I've picked on DFS as it is a key algorithm for finding certain structures in our KB. The answer is heavily dependent on the graph representation we choose. Suppose we choose to represent edges as a directed hypergraph. This can be done in one of two ways for a triple (n1 s n2): n1->{s,n2}, and . The former differentiates between the subject, predicate and object by assuming that the predicate is always clearly distinguishable from the object. This assumption is probably not going to hold for arbitrary KBs, so we must abandon this representation. The alternative has us store each hyperedge as an ordered tuple, which tends to go against standard hypergraph formalisms. However, it can reliably represent arbitrary triples correctly.

I must end this blog entry here, as I don't have a formal representation of the hypergraph. Implementing DFS over a representation is straightforward. The basic principle for DFS still applies: start with a root. Mark the current object as visited, then visit the next object. Don't visit any object multiple times. As such, DFS and BFS are straightforward general purpose graph algorithms. So most of the algorithms that build upon these can be straightforwardly translated to hypergraphs. But! It isn't the case that the results of the algorithms would be interpreted the same way as in ordinary graphs.