dependencies should allow multiple heads

From a discussion on the mailing list:

[Steven Bethard]
Stanford collapsed dependencies can have multiple heads, e.g.  in
the sentence:

"So she thanked him for it and took the milk with her."

The Stanford dependency parse marks "she" as the "nsubj" of "thanked"
and also the "nsubj" of "took". There's another example of this
multiple-headedness in the documentation:

http://nlp.stanford.edu/software/stanford-dependencies.shtml

However, the current DependencyNode type has the structure:

DependencyNode
* Head: DependencyNode
* DependencyType: String
* Children: FSArray of DependencyNode

We could change it to something like this:

DependencyNode
* Heads: FSArray of DependencyNode
* DependencyTypes: FSArray of String
* Children: FSArray of DependencyNode

But that seems confusing and clunky - the Heads and DependencyTypes
would be two parallel arrays, but I could easily imagine someone
thinking the DependencyTypes were parallel with the Children instead.

Another alternative would be something like:

DependencyNode
* HeadRelations: FSArray of DependencyRelation
* ChildRelations: FSArray of DependencyRelation

DependencyRelation
* Head: DependencyNode
* Relation: String
* Child: DependencyNode

You'd then just have a single DependencyRelation for each relation,
but you could access it through either the Head link or the Child
link.

[Lee Becker]
I was talking with Jinho about this and he is of the opinion that it
is no longer a dependency tree when you do this, and he suggested that
this collapsed type would be a subtype of the dependency types.  I
also asked him about the type system for doing dependency based
semantic role labeling, and that shares the multiheadedness of
Stanford's collapsed dependencies.

I'm not sure if I totally agree with Jinho's first statement, but
given its use for SRL, we may want to consider your Node/Relation
suggestion as a new type.

[Steven Bethard]
Well, it can't be a subtype of dependency types since the features of
a DependencyNode are totally different in the two different paradigms.
It could be a separate type though.

I'm trying it right now, and so far I'm quite happy with the
DependencyNode + DependencyRelation approach.

I guess the question is how many different dependency formalisms we
want to have in our type system. My inclination is that the two
situations are more alike than they are different, and we would be
better off having a single type system for that. But YMMV...

[Lee Becker]
I am not as much of a stickler for dependency formalisms, and I see
the collapsed dependencies as essentially the same thing from a data
structure point of view.  That said, I'm for the Dependency Node +
Dependency Relation approach, and would be willing to make changes to
the ClearParser wrapper if that's the route that's decided upon.
Original issue reported on code.google.com by steven.b...@gmail.com on 23 Mar 2011 at 10:58
JamesHe1990 / cleartk

dependencies should allow multiple heads #238
