Agent-hoisting

Before I get to the main point of this post, here's a link to the GitHub page where I'll be putting up the code that I write for this project. For the unfamiliar, GitHub is a place to upload source code, and it is an integral component of the Open Source movement, a trend in the last decade of making source code public. I use GitHub frequently, as you can see if you look at my profile where I have listed several other projects.

"Hoisting" is a term I just invented to describe a transformation that, when used on the correct node of the knowledge description graph (KDG), I propose will simplify the task of converting between KDGs and other logical forms (and I'll get to this later). It applies to acyclic directed graphs, which KDGs are. Imagine the following directed graph:

A->B->E
|
v
C->D

This graph satisfies the acyclic condition because you can't start at any node and get back to it by following arrows. If we envision each arrow as a "step down," then A is the "top" node because everything is "down" from it. To "hoist" a node, we change the arrows to make it the top node.

For example, let's hoist E:

A<-B<-E
|
v
C->D

Now E is the "highest" node in the graph. However, while doing this one needs to remember that the arrows have names that will not be the same when the arrow is reversed. Look at an example of a KDG (previous post) and you'll see things like "agent" and "instance_of." These describe the relation between nodes. For example, if node A (in our above example) is an event and B is the entity taking part in the event A, then the edge connecting A to be would be called "agent." This is simply convention for denoting the entity that is performing the action. The "instance_of" edge is used in classifying entities. Node E could be the general category (called a "Class") that B falls into, so the edge going from B to E would be an "instance_of" edge, telling us that entity B is an instance of class E. When reversing these arrows, we need to "invert" the meaning of the edge as well. If A to B is an agent edge, B to A would have to be something like a "performed_action" edge, telling us that B performed the action A.

The motivation for this transformation can be easily seen with an analogy. When translating between two spoken languages, one cannot simply map words from one language onto the other; sentence structure among other factors must be taken into consideration. When translating knowledge description graphs into Lambda DCS queries, there is no direct formula, so some steps must be taken to modify one side to make it easier to translate. I noticed that Lambda DCS queries focus more on the actor rather than the event occurring while KDGs focus on events; most graphs that are generated have events at the top. By hoisting the agent of an event to the top, I can make KDGs focus a little more on the objects that carry out the event rather than the event itself. It's a small step, but a necessary one.

Here is a real example of a KDG and its agent-hoisted version, both of the question "Who killed Abraham Lincoln?" A quick primer on notation: The data is presented in outline format which should be simple to understand. Any "word-5" pretty much just means "word," you can ignore the number. E<something> means "something" is an event. <something> means "something" is a category. Pretty much everything else is an entity. The question mark denotes what is unknown, and in this case, it's who killed Abraham Lincoln.

No hoisting:

root: E<killed-2>
  recipient: Abraham_Lincoln-3
    semantic_role: :corpse
    instance_of: <Abraham_Lincoln>
      is_subclass_of: <person>
  instance_of: <kill>
    is_subclass_of: <contact>
  agent: ?-1
    semantic_role: :killer
    instance_of: <?>
      is_subclass_of: <person>

Agent-hoisting:

root: ?-1
  semantic_role: :killer
  instance_of: <?>
    is_subclass_of: <person>
  performed_action: E<killed-2>
    recipient: Abraham_Lincoln-3
      semantic_role: :corpse
      instance_of: <Abraham_Lincoln>
        is_subclass_of: <person>
    instance_of: <kill>
      is_subclass_of: <contact>

In other news, I will be going to the lab on Monday to find out where I can set up a copy of Freebase, a task that requires far more computing resources than I have.