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.

The advantage of using Kparser

To answer questions, you need to know what they mean. For example, to answer the question "Where did the battle of New Orleans start?" you need to know that "battle of New Orleans" represents a specifc event, "start" represents a more specific event (a specific time during the battle) and "where" represents the location of the event. Kparser is a tool that gets this information out of the text, and it models it as a graph. Each "object" is a node and each relation between objects is a connection between nodes, otherwise called an edge. Here is how the graph of the question above would look:

You can use Kparser too: just go to http://kparser.org and put in a question and see what it gives you. It's not perfect yet; some things don't parse correctly, but really there's no perfect semantic parser yet.

The research I'm doing is motivated by Percy Liang's research into the same idea, answering questions using a semantic parser and Freebase. You can find his main paper on the topic here. At the bottom of this paper in the section "Error analysis" he notes that the semantic parser that he used has difficulty on certain phrases and he notes the example I showed above as one. Kparser handles this sentence just fine, as it does other sentences that did not work with the style of semantic parse Liang used, and this is why Kparser might be better suited for this task, the motivation of my research.

Lambda DCS Logical Forms

As I dove into the problem, I needed to learn the basic concepts surrounding it, and this involved learning a way of expressing knowledge base queries: Lambda DCS. I'm converting plain-text questions ("How often does the Washington Post come out?") to a "targetFormula," which is a lambda DCS logical form (DCS stands for dependency-based compositional semantics) and this looks like this:

(!fb:book.periodical_frequency.issues_per_year (!fb:book.periodical.frequency_or_issues_per_year fb:en.the_washington_post))

For some examples, this can get very confusing and isn't what it seems. It might look like simple function application but it is far from that, and I had been staring at these for too long before realizing this. This page explains them in full detail and makes them very easy to understand.

A single entity such as fb:en.the_washington_post is what it is: the Washington Post. More complicated are entities such as fb:book.periodical.frequency_or_issues_per_year store a set of key-value pairs, and in this case, stores each "periodical" along with its corresponding "frequency or issues per year," using the terminology provided. When they're put together inside the parentheses, the second part is matched against the right hand part of the first, and any matching tuples are returned. In this case, because there is a ! before the first part, each tuple it represents will be reversed. It's like saying "give me all the periodicals and their frequency and tell me the frequency of the one called 'the washington post'." Note that this is just the inner section of the logical form, but the outer section does essentially the same thing.

Lambda DCS is an interesting tool to use because it handles data in a novel way, at least to me. I'm excited to see how well Kparser-generated graphs can map onto them.